Удаление элемента в одном связанном списке в голове не работает - PullRequest
Новая
       48

Удаление элемента в одном связанном списке в голове не работает

1 голос
/ 10 апреля 2020 
#include <stdio.h>
#include <stdlib.h>

struct node {
   int data;
   struct node *next;
};

struct node *head = NULL;
struct node *second = NULL;
struct node *third = NULL;

void insertAtBeg(struct node *n, int data) {
    struct node *temp;
    temp = (struct node *)malloc(sizeof(struct node));
    temp->data = data;
    temp->next = head;
    head = temp;
}
void insertAtEnd(struct node *n, int data) {
    struct node *temp;
    temp = (struct node*)malloc(sizeof(struct node));
    temp->data = data;
    temp->next = NULL;
    while (n->next != NULL) {
        n = n->next;
    }
    n->next = temp;
}
void deleteElement(struct node *head, int data) {
    if (head->data == data) {
        struct node *temp;
        temp = head;
        head = head->next;
        free(temp);
        printf("after deletion at head in function\n");
        printList(head);
    }
}
void printList(struct node *n) {
    while (n != NULL) {
        printf("%d\n", n->data);
        n = n->next;
    }
}
void main() {
    head = (struct node*)malloc(sizeof(struct node));
    second = (struct node*)malloc(sizeof(struct node));
    third = (struct node*)malloc(sizeof(struct node));
    head->data = 1;
    head->next = second;
    second->data = 2;
    second->next = third;
    third->data = 3;
    third->next = NULL;
    printList(head);
    insertAtBeg(head, 0);
    printf("after insertion at beginning\n");
    printList(head);
    insertAtEnd(head, 4);
    printf("after insertion at End\n");
    printList(head);
    deleteElement(head, 0);
    printf("after deletion at head in main\n");
    printList(head);
}

вывод кода: 

1
2
3
after insertion at beginning
0
1
2
3
after insertion at End
0
1
2
3
4
after deletion at head in function
1
2
3
4
after deletion at head in main
0
1
2
3
4

Почему существует разница в выводе функции, вызываемой в main, и функции, вызываемой в другой функции. ie .aa после удаления в заголовке в функция и после удаления в главном в главном, когда оба должны удалить элемент из одного списка

Ответы [ 2 ]

1 голос
/ 10 апреля 2020

Проблема в том, что вам нужен способ изменить заголовок списка при вставке и / или удалении элементов из списка.

Простой способ сделать это - вернуть этим функциям потенциально обновленное значение. указателя головы и для вызывающей стороны, чтобы сохранить это возвращаемое значение в его head переменной.

Вот модифицированная версия вашего кода со следующей семантикой: 

#include <stdio.h>
#include <stdlib.h>

struct node {
   int data;
   struct node *next;
};

struct node *insertAtBeg(struct node *head, int data) {
    struct node *temp;
    temp = (struct node *)malloc(sizeof(struct node));
    // should test for memory allocation failure
    temp->data = data;
    temp->next = head;
    return temp;
}
struct node *insertAtEnd(struct node *head, int data) {
    struct node *temp;
    struct node *n;
    temp = (struct node*)malloc(sizeof(struct node));
    // should test for memory allocation failure
    temp->data = data;
    temp->next = NULL;
    if (head == NULL)
        return temp;
    n = head;
    while (n->next != NULL) {
        n = n->next;
    }
    n->next = temp;
    return head;
}
struct node *deleteElement(struct node *head, int data) {
    // delete the first node with a given data
    if (head->data == data) {
        struct node *temp = head;
        head = head->next;
        free(temp);
    } else {
        struct node *n = head;
        while (n->next != NULL) {
            if (n->next->data == data) {
                struct node *temp = n->next;
                n->next = temp->next;
                free(temp);
                break;
            }
        }
    }
    return head;
}
void printList(const struct node *n) {
    while (n != NULL) {
        printf("%d\n", n->data);
        n = n->next;
    }
}
int main() {
    struct node *head = NULL;
    head = insertAtBeg(head, 1);
    head = insertAtEnd(head, 2);
    head = insertAtEnd(head, 3);
    printList(head);
    head = insertAtBeg(head, 0);
    printf("after insertion at beginning\n");
    printList(head);
    head = insertAtEnd(head, 4);
    printf("after insertion at End\n");
    printList(head);
    head = deleteElement(head, 0);
    printf("after deletion at head in main\n");
    printList(head);
    // should free the list
    return 0;
}

Альтернативой является передать адрес указателя заголовка списка, чтобы функция могла изменить его при необходимости.

Вот модифицированная версия вашего кода с этим альтернативным подходом: 

#include <stdio.h>
#include <stdlib.h>

struct node {
   int data;
   struct node *next;
};

struct node *insertAtBeg(struct node **headp, int data) {
    struct node *temp = malloc(sizeof(*temp));
    if (temp != NULL) {
        temp->data = data;
        temp->next = *headp;
        *headp = temp;
    }
    return temp;
}
struct node *insertAtEnd(struct node **headp, int data) {
    struct node *temp = malloc(sizeof(*temp));
    if (temp != NULL) {
        temp->data = data;
        temp->next = NULL;
        if (*headp == NULL) {
            *headp = temp;
        } else {
            struct node *n = *headp;
            while (n->next != NULL) {
                n = n->next;
            }
            n->next = temp;
        }
    }
    return temp;
}
int deleteElement(struct node **headp, int data) {
    // delete the first node with a given data
    struct node *head = *headp;
    if (head->data == data) {
        *headp = head->next;
        free(temp);
        return 1;  // node was found and freed
   } else {
        struct node *n = head;
        while (n->next != NULL) {
            if (n->next->data == data) {
                struct node *temp = n->next;
                n->next = temp->next;
                free(temp);
                return 1;  // node was found and freed
            }
        }
        return 0;  // node not found
    }
}
void printList(const struct node *n) {
    while (n != NULL) {
        printf("%d\n", n->data);
        n = n->next;
    }
}
int main() {
    struct node *head = NULL;
    insertAtBeg(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);
    printList(head);
    insertAtBeg(&head, 0);
    printf("after insertion at beginning\n");
    printList(head);
    insertAtEnd(&head, 4);
    printf("after insertion at End\n");
    printList(head);
    deleteElement(&head, 0);
    printf("after deletion at head in main\n");
    printList(head);
    // free the list
    while (head != NULL) {
        deleteElement(&head, head->data);
    }
    return 0;
}

Этот альтернативный подход использует двойные указатели, так что новичкам это немного сложнее понять, но у этого есть сильное преимущество: функции могут обновлять указатель списка и , обеспечивая значимое возвращаемое значение, которое можно протестировать для обнаружения ошибок. Например, insertAtBeg() и insertAtEnd() возвращают NULL, если новый узел не может быть выделен, но сохранить список. Точно так же deleteElement() может возвращать индикатор, показывающий, был ли элемент найден или нет.

При таком подходе вы можете написать функции для выталкивания первого или последнего элемента списка или элемента с заданным индексом, или один с данным data, при необходимости обновляя указатель списка.

0 голосов
/ 10 апреля 2020

В функции void deleteElement (struct node * head, int data) вы передаете указатель на головной узел. Если вы вносите изменения в узел, то это работает, потому что вы указываете на реальный узел. Однако переменная head является локальной копией указателя, а не основной. Когда вы меняете заголовок на заголовок-> следующий, который только изменяет локальную копию, так что он не действует вне deleteElement.

ДОПОЛНИТЕЛЬНЫЕ УКАЗАТЕЛИ УРОВНЯ

Для фактического изменения заголовка вы должны передать указатель чтобы сделать двойной указатель: 

void deleteElement(struct node **phead,int data) {
    struct node *temp;
    temp = *phead;
    *phead = (*phead)->next;

это означает, что вы должны передать адрес заголовка &head в качестве параметра.

...