如何实现带头结点的单链表操作？

本文共计3463个文字，预计阅读时间需要14分钟。

带有头结点的单链表与顺序表相同，都是一种线性表。与顺序表不同的，是链表的物理存储结构是用一组地址任意分布的存储单元存储数据元素。它不像顺序表那样需要占用一段连续的地址空间。

带头结点的单链表

  与顺序表相同，链表也是一种线性表。与顺序表不同的是，链表的物理存储结构是用一组地址任意的存储单元存储数据。它不像顺序表那样需要占据一段地址连续存储空间，而是将存储单元分散在内存的任意地址上。

  在链表结构中，每个数据元素都存放在链表中的一个结点（node）上，而每个结点之间通过指针将其连接起来，这样就形成了一条如“链”的结构。

  在C程序中，链表中的每个结点都可以用结构体来表示。在链表的每个结点中都必须有一个存放指针（地址）的域，也叫做指针域，指针域用来保存后继结点的地址，这样就将每个结点连接在一起，形成一条链。

  一个链表中通常有一个表头，表头的用来保存第一个结点的地址。一个链表的最后一个结点的指针域要置空（NULL），因为它没有后继结点。

单链表的特点：

• 除“第一个”数据元素外，其余数据元素有且仅有一个 前驱元素 prev，

• 除“最后一个”数据元素外，其余数据元素有且仅有一个 后继元素 next

• 单链表的每个结点只有一个指针域

结点：每一个结点都包含两个部分：数据域和指针域。数据域用于存放数据元素，指针域用于存放后继结点的地址。

头指针：无论链表是否为空，头指针均不为空，头指针是链表的必要元素，头指针指向表头结点
头结点：放在第一个元素结点之前，其数据域一般无意义（当然也可以用来存放链表的长度等）
首元结点：第一个元素的结点，它是表头结点之后的第一个结点。

  带头结点的单链表在后期的维护中更方便，头结点与其他结点一样拥有数据域和指针域，头结点的数据域可以不存储任何信息，但也可以存储如链表长度等附加信息。 头结点的指针域用于保存首元结点的地址。带头结点的单链表的相关代码如下。

---

带头结点的单链表操作

---

单链表元素结点

单链表的结点（LNode）通常使用结构体表示。

typedef struct node { //结点数据域 int data; //结点指针域 struct node *next; }LNode;

---

单链表头结点

单链表的头结点（HNode）也使用结构体表示，头结点的指针域保存首元结点的地址，所以其指针域的类型需要与元素结点类型相同。

typedef struct head { //记录链表长度 int len; LNode *next; }HNode;

---

创建带头结点的单链表

创建一个带头结点的单链表，并返回一个指向单链表头结点的头指针。头指针用来标识单链表，保存单链表的入口地址。

/*************************************************************** 函数功能: 创建带头结点的单链表 入口参数: 无 返回值: head（单链表头指针） ****************************************************************/ HNode *create_linked_list(void) { //创建一个头指针 HNode*head = NULL; //创建一个头结点，并将头指针指向头结点 head = (HNode*)malloc(sizeof(HNode)); head->len = 0; head->next = NULL; return head; }

---

打印单链表

打印单链表的所有元素。

/*************************************************************** 函数功能: 打印带头结点的单链表 入口参数: head（单链表头指针)） 返回值: 无 ****************************************************************/ void print_linked_list(HNode*head) { LNode *list = NULL; list = head->next; while(list) { printf("%d ", list->data); list = list->next; } printf("\n"); }

例如：

单链表：1 2 3 4 5 6 7 8 9

输出：1 2 3 4 5 6 7 8 9

---

尾插法

在单链表最后一个结点之后插入一个新结点，并将新插入的结点的指针域置NULL，单链表最后一个结点没有后继节点。

/*************************************************************** 函数功能: 在单链表最后一个结点之后插入一个结点 入口参数: 参数1：head（单链表头指针) 参数2：x(需要保存的元素数据) 返回值: head（单链表头指针） ****************************************************************/ HNode *add_linked_list_last(HNode *head,int x) { LNode *last_node = NULL; last_node = head->next; //判断是否为最后一个结点 while(last_node->next) { last_node=last_node->next; } //申请开辟一个结点空间 LNode *new_node = (LNode*)malloc(sizeof(LNode)); new_node->data = x; new_node->next=NULL; //将结点插入最后 last_node->next = new_node; last_node = new_node; head->len++;//链表长度加1 return head; }

例如：

单链表：1 2 3 4 5 6 7 8 9

插入10后：1 2 3 4 5 6 7 8 9 10

---

头插法

在单链表首元结点之前插入一个新结点，并将头结点的指针指向新结点。

/*************************************************************** 函数功能: 在单链表首元结点之前插入一个结点 入口参数: 参数1：head（单链表头指针) 参数2：x(需要保存的元素数据) 返回值: head（单链表头指针） ****************************************************************/ HNode *add_linked_list_first(HNode *head,int x) { LNode *new_node = NULL; //申请开辟一个结点空间 new_node = (LNode*)malloc(sizeof(LNode)); new_node->data = x;//保存需要插入的元素 new_node->next = NULL; //将新结点插入到第一个结点之前 new_node->next = head->next; head->next = new_node; head->len++; return head; }

例如：

单链表：2 4 7 8 9 1

插入11后：11 2 4 7 8 9 1

---

删除单链表中第N个结点

删除单链表中的第N个结点，需要将第N-1个结点的后继指针指向第N+1个结点，然后将第N个结点的后继指针置NULL，然后再释放第N个结点的空间。

/*************************************************************** 函数功能: 删除单链表中的第N个结点 入口参数: 参数1：head（单链表头指针) 参数2：n（第N个结点） 返回值: head（单链表头指针） ****************************************************************/ HNode *delete_theN_node(HNode *head,int n) { //判断n是否大于链表长度 if (n > head->len || n < 1) { printf("该结点不存在！\n"); return 0; } LNode *now_node = NULL; LNode *prev_node = NULL; now_node = head->next; //删除第一个结点 if (1 == n) { head->next = now_node->next; now_node->next = NULL; free(now_node); now_node = NULL; head->len--; } //删除最后一个结点 else if(head->len == n) { while(--n) { prev_node = now_node; now_node = now_node->next; } prev_node->next = NULL; free(now_node); now_node = NULL; head->len--; } //删除中间某个结点 else { while(--n) { prev_node = now_node; now_node = now_node->next; } prev_node->next = now_node->next; now_node->next = NULL; free(now_node); now_node = NULL; head->len--; } return head; }

例如：

单链表：2 4 7 8 9 1

删除第2个结点后： 2 7 8 9 1

---

删除单链表中元素为X的结点

前提：单链表中不包含重复元素。

/*************************************************************** 函数功能: 删除单链表中元素为X的结点（单链表中不包含重复元素） 入口参数: 参数1：head（单链表头指针) 参数2：x(删除的元素数据) 返回值: head（单链表头指针） ****************************************************************/ HNode *delete_num(HNode *head,int x) { LNode *now_node = NULL; LNode *prev_node = NULL; now_node = head->next; //判断X是不是第一个结点的元素 if(x == now_node->data){ head->next = now_node->next; now_node->next = NULL; free(now_node); now_node = NULL; head->len--; return head; } //判断中间 while(now_node->next) { if(x == now_node->data){ prev_node->next = now_node->next; now_node->next = NULL; free(now_node); now_node = NULL; head->len--; return head; } else{ prev_node = now_node; now_node = now_node->next; } } //判断最后一个结点的元素是否为X if(x == now_node->data){ prev_node->next = NULL; free(now_node); now_node = NULL; head->len--; } else{ printf("链表中无%d这个元素\n",x); return 0; } return head; }

例如：

单链表：2 4 7 8 9 1

删除元素9后：2 4 7 8 1

---

删除单链表中连续重复的元素只保留一个

/*************************************************************** 函数功能: 删除单链表中的重复元素 入口参数: head（单链表头指针) 返回值: head（单链表头指针） ****************************************************************/ HNode *delete_repetitive_num(HNode*head) { LNode *now_node = NULL; LNode *prev_node = NULL; now_node = head->next; while(now_node->next){ prev_node = now_node; now_node = now_node->next; //判断相邻两个元素是否相等 if(prev_node->data == now_node->data){ prev_node->next = now_node->next; now_node->next = NULL; free(now_node); now_node = prev_node; } } return head; }

例如：

单链表：1 1 2 2 3 3 3 5 5

删除后：1 2 3 5

---

销毁单链表

销毁除头结点之外的结点。

/*************************************************************** 函数功能: 销毁除头结点之外的结点 入口参数: head（单链表头指针)） 返回值: head（单链表头指针） ****************************************************************/ HNode *destroy_linked_list(HNode *head) { LNode *now_node = NULL; //从第一个元素结点开始销毁 while(head->next){ now_node = head->next; if(now_node->next == NULL){ head->next = NULL; free(now_node); now_node = NULL; head->len--; break; } head->next = now_node->next; now_node->next = NULL; free(now_node); now_node = NULL; head->len--; } return head; }

---

单链表逆置

说明：此逆置不改变结点原来的位置，只交换两个结点存储的数据。

/*************************************************************** 函数功能: 逆置单链表（交换元素数据） 入口参数: head（单链表头指针) 返回值: head（单链表头指针） ****************************************************************/ HNode *reverse_linked_list(HNode *head) { int n = head->len; int temp; int i,j; printf("链表长度：%d\n",n); LNode *first_node = NULL; LNode *temp1_node = NULL; LNode *temp2_node = NULL; first_node = head->next; temp1_node = first_node; //如果链表元素个数为奇数则(n-1)%2,反之n%2 if(n%2 == 0||(n-1)%2==0) { //不管是奇数个元素还是偶数个元素，都只需要交换n/2次 //奇数个元素其最中间那一个元素不需要交换 for(i=0;i<n/2;i++) { temp2_node = first_node; for(j=0;j<n-i-1;j++) { temp2_node = temp2_node->next; } temp = temp1_node->data; temp1_node->data = temp2_node->data; temp2_node->data = temp; //指向第一个结点的指针往后移动一个 temp1_node = temp1_node->next; } } return head; }

例如：

单链表：3 2 4 5 10 8 1

逆置后：1 8 10 5 4 2 3

---

将两个链表归并为一个有序链表

/*************************************************************** 函数功能: 将两个链表归并为一个有序链表 入口参数: 参数1：head1（单链表头指针) 参数2：head2（单链表头指针） 返回值: head3（单链表头指针） ****************************************************************/ HNode *combine_linked_list(HNode*head1,HNode*head2) { HNode *head3 = NULL; LNode *now_node = NULL; LNode *next_node = NULL; int flag = 0; int temp; int n; now_node = head1->next; //找head1的最后一个结点 while(now_node->next){ now_node = now_node->next; } //连接head1和head2 now_node->next = head2->next; //合并 head3 = head1; head3->len = (head1->len) + (head2->len); n = head3->len; //冒泡排序 for(int i=0;i<n-1;i++) { now_node = head3->next; next_node = now_node; for(int j=0;j<n-1-i;j++) { next_node = next_node->next; if(now_node->data > next_node->data) { temp = now_node->data; now_node->data = next_node->data; next_node->data = temp; flag = 1; } now_node = now_node->next; } if(flag == 0){ break; } } return head3; }

例如：

单链表1：5 4 3 2 1

单链表2：9 6 8 7

归并后：1 2 3 4 5 6 7 8 9

---

更新第N个结点的数据

/*************************************************************** 函数功能: 修改第N个结点的数据 入口参数: 参数1：head（单链表头指针) 参数2：n（第N个结点） 参数3：更新的数据 返回值: head3（单链表头指针） ****************************************************************/ HNode *change_theN_node(HNode *head,int n,int x) { //判断n是否大于链表长度 if (n > head->len || n < 1) { printf("该结点不存在！\n"); return 0; } LNode *now_node = NULL; now_node = head->next; while(--n) { now_node = now_node->next; } now_node->data = x; return head; }

例如：

单链表：5 4 3 2 1

更新第2个结点数据为12：5 12 3 2 1

---

查找值为X的元素

/*************************************************************** 函数功能: 查找值为X的元素 入口参数: 参数1：head（单链表头指针) 参数2：x（查找的值） 返回值: 0 表示不存在，1表示存在 ****************************************************************/ int find_data_linked_list(HNode *head,int x) { LNode *now_node = NULL; now_node = head->next; while(now_node){ if(now_node->data == x){ return 1; } now_node = now_node->next; } return 0; }

---

主函数参考

int main(int argc, char const *argv[]) { int num; int n; //创建一个头指针用于标识链表 HNode *phead = NULL; //创建一个带头结点的单链表 phead = create_linked_list(); LNode*new_node = NULL; LNode*last_node = NULL; printf("请向单链表输入数据："); do{ scanf("%d",&num); new_node = (LNode*)malloc(sizeof(LNode)); new_node->data = num; new_node->next = NULL; if (phead->next == NULL) { phead->next = new_node; last_node = new_node; phead->len++; } else { last_node->next = new_node; last_node = new_node; phead->len++; } }while(getchar() != '\n'); //打印链表所有元素 printf("链表长度：%d\n",phead->len); printf("链表所有元素："); print_linked_list(phead); //尾插法 //头插法 //删除第N个结点 //查找数据 return 0; }

注意：该文章仅供学习交流不得转载商用。