Как удалить любой узел в односвязном списке

Question

Вот мой код:

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

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

struct node *addNode(struct node *head, int y)
{
       struct node *traverser;
       traverser = head;
       if(traverser!=NULL)
       {                 
             while(traverser->next!=NULL)
             traverser=traverser->next;

             traverser -> next = malloc(sizeof(struct node));
             traverser -> next -> x = y;
             traverser -> next -> next = NULL;
       }
       else
       {
             head= malloc(sizeof(struct node));
             head -> x=y;
             head -> next = NULL;
       }    
       return head;
 }

 void display(struct node *head)
 {   
     struct node *traverser;
     traverser = head;

     while(traverser!=NULL)
     {
          printf("%d\n",traverser->x);
          traverser=traverser->next; 
     }
 }

 struct node *InitializeList(void)
 {
       return NULL;
 }

int main()
{
    struct node *head;
    head = InitializeList();
    head = addNode(head,2);
    head = addNode(head,15);
    head = addNode(head,5);
    head = addNode(head,8);
    display(head);  

    free(head);
    getchar();
}

Мне нужно удалить узел в main, как этотмоя программа.

Но как я могу это сделать?Removenode () - это просто имя функции, какой алгоритм мне использовать?Или что или как это убрать?

Answer 1

Не совсем ответ, просто какой-то общий совет

Для выяснения такого рода вещей, как правило, достаточно решить ровно три случая

• Узел длябыть удаленным - это голова
• удаляемый узел - это хвост
• удаляемый узел находится внутри списка

---

Большойисточником проблем, с которыми вы столкнетесь, являются

• , гарантирующие, что поле "next" в любых предыдущих узлах будет правильно сброшено
• , гарантирующее, что вызывающий абонент получает или сохраняет valid указатель на new head.

Обратите внимание, что существует рекурсивная реализация (думаю, n.next = remove(n.next,val)), которая делает эти две проблемы одинаковыми, и что вы можетеПреобразуйте его в основном в цикл, чтобы предотвратить переполнение стека в очень длинных списках.

---

Подзадача, которая может возникнуть, - это поиск узла, который будет удален в списке.Можете ли вы сделать вашу жизнь проще, отделив часть о поиске целевого узла от remove(node* head, node* target)?

Answer 2

Прототип алгоритма должен быть:

struct node * removenode(struct node *head, int y);

Поскольку, если вы удаляете первый элемент, исходный указатель "head" больше не будет действительным.

Алгоритмпросто пройтись по списку, запомнив предыдущий элемент (и заголовок) и ища данные.Если найден, установите следующий указатель предыдущего элемента следующим.

Answer 3

На высоком уровне, чтобы удалить любой узел, вам нужно сделать следующее:

1) Указать элемент, указывающий на узел, который вы хотите удалить.

2) Установите ссылку на элемент, который вы хотите удалить, на элемент, который вы хотите удалить, следующий элемент.

3) Удалить элемент, который вы хотите удалить.

Таким образом, ваша цепочка сохраняется, и вы освободили этот элемент из памяти.

Примерно так:

Head -> Item1 -> Item2 -> Item3 -> NULL

Если вы хотите удалить Item2, вы идете так:

Head -> Item1 -> Item2 -> Item3 -> NULL
          ^       ^   (Grab pointers to these items)

Установите Item1 рядом с Item2 следующим, затем удалите Item2.

           /--------------\
Head -> Item1    Item2 -> Item3 -> NULL
          ^       ^ (Delete 2)

РЕДАКТИРОВАТЬ: Удаление элемента или элемента 3:

Head -> Item1 -> Item2 -> Item3 -> NULL
 ^       ^   (Grab pointers to these items)

Направьте голову на элемент 2, затем удалите элемент 1:

   /--------------\
Head    Item1 -> Item2 -> Item3 -> NULL
 ^       ^ (Delete 1)

ИЛИ

Head -> Item1 -> Item2 -> Item3 -> NULL
                    ^       ^   (Grab pointers to these items)

Направьте голову на Item2, затем удалите Item1:

                    /--------------\
Head -> Item1 -> Item2   Item3 -> NULL
                   ^       ^ (Delete 3)

Answer 4

Я написал учебник по связанным спискам на C, возможно, он поможет:

http://www.4pmp.com/2009/10/linked-lists-in-c-push-pop-shift-and-unshift/

Answer 5

Посмотрите, сработает ли это для вас или нет, возможно, где-то хранился на моем ПК для такой ситуации:

void RemoveNode(struct node*x)
{
    struct node *temp=x,*tempo=NULL;
    int i=0,n;
    printf("\nWould you like to delete a node?\nPress 1 for Yes 2 for No: ");
    scanf("%d",&i);
    if(i==1)
    {
        printf("Enter nth node to be deleted");
        scanf("%d",&n);
        i=0;
        if(n==1)
        {
        x=temp->next;
        free(temp);
        }
        while(i<n-2)
        {
        temp=temp->next;
        i++;
        }
        if(temp->next->next==NULL)
        {
        tempo=temp->next;
        temp->next=NULL;
        free(tempo);
        }
        else
        {
        tempo=temp->next;
        temp->next=temp->next->next;
        free(tempo);
        }
    }
    else
    printf("\n No Changes Made\nExiting....");
}

Всегда имеет значение Голова.