Я пытаюсь написать немного кода, чтобы создать отсортированный связанный список и вставить только уникальные элементы таким образом, чтобы связанный список оставался отсортированным.Кроме того, я реализовал функцию удаления узла с заданным значением и одного для его печати.
У меня есть несколько тестовых случаев, которые необходимо запустить, и для тестирования программного обеспечения требуется файл main.c иmake-файл, и в make-файле мне необходимо использовать fsanitize = address.
Без него тестовые сценарии проходят, но, если он включен в make-файл, код завершится с сообщением
"РЕЗЮМЕ: AddressSanitizer: 64 байта (ов) просочились в 4 выделения (ов)."
или что-то подобное.Это показывает, что некоторые являются прямыми утечками, некоторые косвенными утечками.
Вот обновленный код , который я написал.
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct Node {
int val;
struct Node* next;
};
void ins(struct Node** head, struct Node* node, int* len) {
// check if the val held by the head is equal to the new node's val
// if it is, return
if(*head != NULL && (*head)->val == node->val) {
free(node);
return;
}
/* Special case for the head end */
if (*head == NULL || (*head)->val > node->val) {
node->next = *head;
*head = node;
// increase the length
(*len)++;
return;
} else {
struct Node* current = *head;
/* Locate the node before the point of insertion */
while (current->next != NULL && current->next->val <= node->val) {
current = current->next;
}
// if the node's val is equal to the val of the node
// in which position it should be inserted, return
if(node->val == current->val) {
return;
}
// add the node into the linked list
node->next = current->next;
current->next = node;
// increment the list's length
(*len)++;
}
}
// delete the value from the linked list
void del(struct Node **head, int value, int* len) {
// Store head node
struct Node* temp = *head;
// If head node itself holds the value to be deleted
if (temp != NULL && temp->val == value) {
// change the head
*head = temp->next;
// decrease the length
(*len)--;
// free the memory and return
free(temp);
return;
}
struct Node* prev;
// Search for the key to be deleted, keep track of the
// previous node as we need to change 'prev->next'
while(temp != NULL && temp->val != value) {
prev = temp;
temp = temp->next;
}
// If key was not present in linked list, return
if(temp == NULL) {
return;
}
// delete the node from the list
prev->next = temp->next;
// decrease length
(*len)--;
free(temp); // Free memory
}
void printList(struct Node *head, int len) {
printf("%d :", len);
struct Node *temp = head;
// print the list's content
while(temp != NULL) {
printf(" %d", temp->val);
temp = temp->next;
}
printf("\n");
}
int main() {
/* Start with an empty list and a temporary node */
struct Node* head = NULL;
struct Node* temp;
int len = 0;
char c;
int value;
// while the input is valid
while(1) {
// check that there is still input
if(scanf(" %c", &c) != 1) {
break;
}
// break out of the loop if the first character is other than i and d
if(c != 'i' && c != 'd') {
break;
}
// read the value
if(scanf("%d", &value) != 1) {
break;
}
// do the required operations
if(c == 'i') {
temp = (struct Node*) malloc(sizeof(struct Node));
// put in the val and set the next to null
temp->val = value;
temp->next = NULL;
ins(&head, temp, &len);
} else if(c == 'd') {
del(&head, value, &len);
}
// print the list
printList(head, len);
}
free(head);
return 0;
}
Я попытался исправить некоторыеутечки памяти, но, похоже, все еще есть.Мое лучшее предположение - я выделяю память для некоторых указателей в функции ins () и не освобождаю память после их использования ... Я попытался освободить память после использования некоторых указателей, но это привело бы к другим проблемам с кодом.
Редактировать: вот несколько изображений с использованными входными данными и фактическими "ошибками", которые я получаю.
Обратите внимание, что третий пример не имеет утечек памяти и пройдет тестовый сценарий.