C中的链表

1. 声明和初始化

/* 节点结构和变量声明: */
struct node { 
    int value; 
    struct node *next; 
}; 
struct node *head, *temp;

/* 为新节点分配空间 */ 
//推荐分配内存语句与判断语句结合
if ((temp = (struct node *) malloc(sizeof(struct node))) == NULL) { 
    printf("Allocation failed.\n"); 
    exit(1); 
}

2. 访问节点元素

1. (*temp).value = 47; (*temp).next = NULL;
2. temp->value = 47; temp->next = NULL;（推荐）

3. 打印链表节点

• /* 打印首节点为h的全部链表节点数据 */
  void print_list(struct node *h) { 
    if (h == NULL) { 
        printf("The list is empty.\n");
    } else { 
        printf("Values in the list are:\n"); 
        while (h != NULL) { 
        printf("%d\n", h->value); 
        h = h->next; 
        }
    } 
  }
  

4. 搜索链表节点

/* 返回指向搜索到节点的指针，若没有返回NULL */ 
struct node *search_list(struct node *h, int x) {
    while (h != NULL) { 
    if (h->value == x) {
        return h; 
    }
    h = h->next; 
    }
  return NULL; 
}

5. 插入节点

• 为什么使用二重指针struct node **h：我们需要操作的节点本身是一个结构体（用指向堆上内存的指针表示*h、*t），我们需要指向节点的指针就是一个二重指针

/* 创建一个值为v的新节点，并添加到首节点为*h，尾节点为*t的链表尾部 */ 
void insert_node (struct node **h, struct node **t, int v) {
    struct node *temp;

    if ((temp = (struct node *)malloc(sizeof(struct node))) == NULL) {              
    printf("Node allocation failed. \n"); 
        exit(1); 
    /* 申请内存失败，终止程序 */ 
    } 
  
  /* 将v拷贝进节点 */ 
    temp->value = v; 
  temp->next = NULL; 
  if (*h == NULL) { 
    /* 如果是空链表 */ 
    *h = *t = temp; 
  } else { 
    /* 非空链表，添加在*t尾部 */  
    (*t)->next = temp; 
    *t = (*t)->next; 
  } 
}

5. 使用typedef来简化

typedef struct node { 
  int value; 
  struct node *next; 
} NODE, *PTRNODE;

在以上声明中：

• NODE 表示struct node
• PTRNODE 表示struct node *
• eg. NODE x; PTRNODE head, tail;