c中不使用双指针的链表实现

Question

我已经用C语言实现了一个简单的链表，但它可以在不使用双指针（**）的情况下实现吗？我想只使用单指针来实现相同的程序。

#include <stdio.h>
#include <stdlib.h>
struct node
{
  int data;
  struct node *next;
};

void push(struct node** head_ref, int new_data)
{
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data  = new_data;
    new_node->next = (*head_ref);
    (*head_ref)    = new_node;
}

void append(struct node** head_ref, int new_data)
{
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    struct node *last = *head_ref;  /* used in step 5*/
    new_node->data  = new_data;
    new_node->next = NULL;
    if (*head_ref == NULL)
    {
       *head_ref = new_node;
       return;
    }
    while (last->next != NULL)
        last = last->next;
    last->next = new_node;
    return;
}
void printList(struct node *node)
{
  while (node != NULL)
  {
     printf(" %d ", node->data);
     node = node->next;
  }
}
int main()
{
  struct node* head = NULL;
  append(&head, 6);
  push(&head, 7);
  push(&head, 1);
  append(&head, 4);
  printf("n Created Linked list is: ");
  printList(head);
  getchar();
  return 0;
}

是否可以将"结构节点**head_ref"替换为"结构节点*head_ref"？

---

建议后更改的代码（仍然无法获得输出）

#include <stdio.h>
#include <stdlib.h>
struct node
{
  int data;
  struct node *next;
};

struct node* push(struct node* head, int new_data)
{
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data  = new_data;
    new_node->next = head;
    head   = new_node;
    return head;
}
struct node* append(struct node* head, int new_data)
{
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    struct node *last = head;  /* used in step 5*/
    new_node->data  = new_data;
    new_node->next = NULL;
    if (head == NULL)
    {
       head = new_node;
       return head;
    }
    while (last->next != NULL)
        last = last->next;
    last->next = new_node;
    return head;
}

void printList(struct node *node)
{
  while (node != NULL)
  {
     printf(" %d ", node->data);
     node = node->next;
  }
}
int main()
{
  struct node* head = NULL;
  head= append(&head, 6);
  head=push(&head, 7);
  head=push(&head, 1);
  head=append(&head, 4);
  printf("n Created Linked list is: ");
  printList(head);
  getchar();
  return 0;
}

Answer 1

是的，您可以只使用单个指针重写此代码，但您必须更改API的语义及其使用模式。

从本质上讲，您可以替换中的第二级间接

void push(struct node** head_ref, int new_data)

具有客户端分配，即

struct node* push(struct node* head, int new_data)

这意味着代替

push(&head, num);

呼叫者必须写

head = push(head, num);

append的实现也是如此。

Answer 2

用（head，6

另一个解决方案是创建一个名为head的空节点，然后创建一个指向该节点的指针list。然后，您可以将list传递给所有函数，比如这个

#include <stdio.h>
#include <stdlib.h>
struct node
{
    int data;
    struct node *next;
};
void push(struct node *list, int new_data)
{
    struct node* new_node = malloc(sizeof(struct node));
    new_node->data = new_data;
    new_node->next = list->next;
    list->next = new_node;
}
void append(struct node *list, int new_data)
{
    while ( list->next != NULL ) 
        list = list->next;
    push( list, new_data );
}
void printList(struct node *node)
{
    for ( node=node->next; node != NULL; node=node->next )
        printf(" %d ", node->data);
    printf( "n" );
}
int main( void )
{
    struct node head = { 0, NULL };
    struct node *list = &head;
    append(list, 6);
    push(list, 7);
    push(list, 1);
    append(list, 4);
    printf("n Created Linked list is: ");
    printList(list);
    getchar();
    return 0;
}