链接列表不能连接节点。

I created a list and i checked through the countnodes function if the nodes are connected. The countnodes functions gave me the right answer and i thought that everything it's okay. But , when i tried to delete a node i realised that the nodes are not even connected to the head. I know that the problem is in the insert function because the cur always gives something different from zero and the insert function returns zero and the nodes never connect to each other.

我创建了一个列表，并通过countnodes函数检查节点是否连接。countnode函数给出了正确的答案，我认为一切都没问题。但是，当我试图删除一个节点时，我意识到节点甚至连头部都没有连接。我知道问题在于插入函数，因为cur总是给出与0不同的东西，并且插入函数返回0，而节点之间从不连接。

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

struct node
{
    int datum;


    struct node *next;
};

struct node *search(struct node *head, int id, struct node **prev)
{
    struct node *tmp = 0;
    tmp = (struct node*)malloc(sizeof(struct node));
    *prev = (struct node*)malloc(sizeof(struct node));

    tmp = head;
    printf("\n\ntmp->datum = %d",tmp->datum);

    while(tmp!=NULL && tmp->datum < id)
    {
        *prev = tmp;
        tmp = tmp->next;


    }

    if(tmp==NULL || tmp->datum != id)
    {

         return NULL;
    }


    return tmp;
};


int insert(struct node **H, struct node *tmp)
{
    struct node *cur = 0 , *prev = 0;
   // tmp = (struct node*)malloc(sizeof(struct node));
    cur = (struct node*)malloc(sizeof(struct node));

    printf("\n\ninsert datum = %d\n\n",tmp->datum);
        cur = search(*H,tmp->datum,&prev);



    if(cur) return 0;
    printf("\nox\n");

    if(prev==NULL)
    {
        printf("\nNULL\n");
        tmp->next = *H;
        *H = &tmp;
    }
    else
    {
        printf("\nELSE\n");
        tmp->next = (prev->next);
        prev->next = tmp;
    }

    return 1;

}

int delete(struct node **h,int price)
{
    struct node *cur, *prev;
    cur = (struct node*)malloc(sizeof(struct node));
    cur = search(*h,price,&prev);

    if(!cur) return 0;

    if(prev)
    {
        prev->next = cur->next;
        free(cur);
        printf("\n\nsimple delete\n\n");
    }
    else
    {
        *h = cur->next;
         free(cur);
         printf("\n\nhead delete\n\n");
    }

    return 1;
}

int countnodes(struct node *h)
{
    int n=0;
    struct node *tmp = 0;
    tmp = (struct node*)malloc(sizeof(struct node));
    tmp = h;
    while(tmp!=NULL)
    {
        n++;
        printf("\n\ndatum = %d\n",tmp->datum);
        tmp = tmp->next;



    }

    printf("\n\n\nNodes = %d\n",n);
    return n;

}

int main()
{
    struct node *head;
    struct node  *cur;
    int i=0;

    head = (struct node*)malloc(sizeof(struct node));
    cur = (struct node*)malloc(sizeof(struct node));

    head->datum = i;
    head->next = NULL;

    cur = head;

    for(i=1;i<5;i++)
    {

        cur->next = malloc(sizeof(struct node));

        insert(&head,cur);
        cur = cur->next;
        cur->datum = i;
        cur->next = 0;


    }



        delete(&head,0);
        //countnodes(head);



    return 0;
}

2 个解决方案

#1

Problems I see in your code:

我在您的代码中看到的问题:

1. In search:

   在搜索:

   tmp = (struct node*)malloc(sizeof(struct node));
   *prev = (struct node*)malloc(sizeof(struct node));
   

   These are unnecessary mallocs. They are also memory leaks. Change them to:

   这些是不必要的malloc。它们也是内存泄漏。改变他们:

   *prev = NULL;
   

2. In insert:

   在插入:

   *H = &tmp;
   

   This line is wrong. The two sides are different pointer types. Perhaps this is a typo. It needs to be:

   这条线是错误的。双方是不同的指针类型。也许这是一个印刷错误。它需要:

   *H = tmp;
   

3. In delete:

   删除:

   cur = (struct node*)malloc(sizeof(struct node));
   

   This is also an unnecessary malloc and a memory leak.

   这也是一个不必要的malloc和内存泄漏。

4. In countnodes:

   在countnodes:

   tmp = (struct node*)malloc(sizeof(struct node));
   

   This is also an unnecessary malloc and a memory leak.

   这也是一个不必要的malloc和内存泄漏。

5. In main:

   主要:

   cur = (struct node*)malloc(sizeof(struct node));
   

   This is also an unnecessary malloc and a memory leak.

   这也是一个不必要的malloc和内存泄漏。

   Also, the following line doesn't server any purpose.

   另外，下面的行不用于任何目的。

   cur = head;
   

   In the for loop, you have:

   在for循环中，有:

   cur->next = malloc(sizeof(struct node));
   insert(&head,cur);
   cur = cur->next;
   cur->datum = i;
   cur->next = 0;
   

   I think what you are trying to do is add a node whose datum is i. However, you are calling insert before setting the data on a node. What you need is:

   我认为您要做的是添加一个节点，该节点的数据是I。你需要的是:

   cur = malloc(sizeof(struct node));
   cur->datum = i;
   cur->next = 0;
   insert(&head,cur);
   

Hopefully I didn't miss anything.

希望我没有错过任何东西。

Update

更新

I missed another unnecessary malloc and memory leak. You don't need the following line in insert.

我错过了另一个不必要的malloc和内存泄漏。插入时不需要下面一行。

cur = (struct node*)malloc(sizeof(struct node));

#2

As indicated in several comments, the question code reveals an improper understanding of malloc() and pointers.

正如在几个注释中所指出的，问题代码揭示了对malloc()和指针的错误理解。

Below is a representation of the question code with a single malloc():

下面是带有一个malloc()的问题代码的表示:

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

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

struct node *search(struct node *cur, int id, struct node **prev)
   {
   while(cur && cur->datum < id)
      {
      *prev = cur;
      cur = cur->next;
      }

   if(cur)
      if(cur->datum != id)
         cur=NULL;

   return(cur);
   };

int delete(struct node **head, int price)
   {
   struct node *cur, *prev=NULL;

   cur = search(*head, price, &prev);
   if(NULL == cur)
      return 0;

   if(prev)
      {
      prev->next = cur->next;
      free(cur);
      }
   else
      {
      *head = cur->next;
      free(cur);
      }

   return 1;
   }

int countnodes(struct node *tmp)
   {
   int n=0;

   for(;tmp; tmp = tmp->next)
      n++;

   return(n);
   }

int insert(struct node **head, struct node *new)
   {
   struct node *cur = NULL;
   struct node *prev = NULL;

   if(*head)
      {
      cur = search(*head, new->datum, &prev);
      if(cur)
         return(0);
      }      

   if(prev)
      {
      new->next = prev->next;
      prev->next = new;
      }
   else
      {
      new->next = *head;
      *head = new;
      }

   return(1);
   }

int main()
   {
   struct node *head = NULL;
   int i;

   for(i=0;i<5;i++)
      {
      struct node *new = malloc(sizeof(*new));
      if(NULL == new)
         {
         fprintf(stderr, "malloc() failed\n");
         exit(1);
         }

      new->datum = i;
      new->next = NULL;
      printf("insert datum = %d\n", new->datum);
      insert(&head, new);
      }

   delete(&head,0);
   printf("countnodes = %d\n", countnodes(head));

   return 0;
   }