c - 我对链表感到困惑。解决方案是什么？

Question

特别是我对在函数中传递 head 感到困惑。有人可以解释一下吗？

#include<stdio.h>

struct node    
{    
    int data;

    struct node *next;    
};   

struct node *makeNode(int item)    
{    
    struct node *newNode = (struct node *)malloc(sizeof(struct node));

    newNode->data = item;

    newNode->next = NULL;

    return newNode;
}    

void traverse(struct node *head)    
{    
    struct node *ptr = head;

    while(ptr != NULL)    
    {    
        printf("%d ",ptr->data);

        ptr = ptr->next;
   }

    printf("\n");
}

void push(struct node **headRef, int data)    
{    
    struct node *newNode = makeNode(data);

    newNode->next = *headRef;

    *headRef = newNode;    
}

void append(struct node **headRef, int data)    
{

    struct node *newNode = makeNode(data);

    struct node *ptr = *headRef, *temp;

    if( ptr == NULL )    
    {    
        *headRef = newNode;

        return;
    }

    while(ptr != NULL)    
    {   

        temp = ptr;

        ptr = ptr->next;    
    }

    temp->next = newNode;    
}


void deleteData(struct node **headRef, int key)    
{    
    struct node *ptr = *headRef, *prevNode;

    //If key is in head node

    if( (ptr->data == key) && (ptr != NULL) )    
    {    
        *headRef = ptr->next;

        free(ptr);

        return;    
    }


    while( (ptr != NULL) && (ptr->data!=key) )    
    {    
        prevNode = ptr;

        ptr = ptr->next;    
    }


    if(ptr == NULL)    
        printf("Underflow or Key not found.\n");    
    else    
    {    
        prevNode->next = ptr->next;    
        free(ptr);    
    }    
}

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

    int data;

    printf("Enter Positive Data:\n");

    scanf("%d",&data);

    while( data>=0 )    
    {    
        append(&head,data);

in this function , pass the address of head.

        scanf("%d",&data);    
    }

    printf("\nTraversing...\n");

    traverse(head);

but in this function why i only pass the head?

    printf("\n\nEnter a data to delete:\n");

    scanf("%d",&data);

    deleteData(&head,data);

    printf("\nTraversing...\n");

    traverse(head);    
}

Answer 1

函数内遍历

void traverse(struct node *head) {
    ......
    ......
}

遍历函数有一个参数head这是结构体节点指针类型。
因此调用traverse函数必须传递一个结构节点指针类型的参数。
在主函数中，您将 head 定义为 struct node *head = NULL;
这就是为什么您要调用类似 traverse(head) 的函数。

在函数中追加

void append(struct node **headRef, int data)    
{
    ....
    ....

}

论点headref是“指向指针的指针”类型。

Pointer to Pointer variable stores the address of pointer

因此，您必须将指针的地址作为参数传递，并以 append(&head,data) 的形式调用追加函数。

在追加函数中使用指针作为参数

将函数的返回类型从 void 更改为 struct node*并返回 headRef 指针。

struct node* append(struct node *headRef, int data)    
{
    struct node *newNode = makeNode(data);
    struct node *ptr = headRef, *temp;
    if( ptr == NULL )    
    {    
        headRef = newNode;
        return headRef;
    }
    while(ptr != NULL)    
    {   
        temp = ptr;
        ptr = ptr->next;    
    }
    temp->next = newNode;
    return headref;
}

在main函数中，你应该像这样调用append函数。

head = append(head,data); //since append function is now returning a pointer

使用单指针追加节点的完整代码

#include<stdio.h>
struct node

{

  int data;

  struct node * next;
};

struct node * makeNode(int item)

{

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

  newNode -> data = item;

  newNode -> next = NULL;

  return newNode;
}


void traverse(struct node * head)

{

  struct node * ptr = head;

  while (ptr != NULL)

  {

    printf("%d ", ptr -> data);

    ptr = ptr -> next;

  }

  printf("\n");
}

struct node * append(struct node * headRef, int data)

{

  struct node * newNode = makeNode(data);

  struct node * ptr = headRef, * temp;

  if (ptr == NULL)

  {

    headRef = newNode;

    return headRef;

  }

  while (ptr != NULL)

  {

    temp = ptr;

    ptr = ptr -> next;

  }

  temp -> next = newNode;

  return headRef;
}

int main()

{

  struct node * head = NULL;

  int data;

  printf("Enter Positive Data:\n");

  scanf("%d", & data);

  while (data >= 0)

  {

    head = append(head, data);

    scanf("%d", & data);

  }

  printf("\nTraversing...\n");

  traverse(head);
  return 0;
}