今天，我带来单链表的讲解。

目录

• • 顺序表的缺陷
  • 单链表的三个文档
  • 创建结点函数
  • 按元素从小到大的顺序创建链表
  • 打印链表
  • 尾插函数
  • 尾删函数
  • 头插函数
  • 头删函数
  • 在pos位置后面插入数据的函数
  • 在pos位置插入数据的函数
  • 删除pos位置后面的数据的函数
  • 删除pos位置数据的函数
  • 销毁链表的函数
  • 查找数据的函数
  • 删除相应元素的所有结点
  • 利用数组创建结点的函数
  • 结构体的定义和函数的声明
  • 菜单和主函数
  • SList.h文档的代码
  • SList.c文档的代码
  • test.c文档的代码

顺序表的缺陷

在前面的文章中，我已经写过顺序表的代码。顺序表本身存在着缺陷，如:

1.空间不够，需要扩容(尤其异地扩容)是有一定的代价的，其次，还可能存在一定的空间浪费(没有完全利用空间)。
2.头部或者中部插入或者删除数据，需要挪动数据，效率低下。

优化方案:

1.按需申请释放空间
2.不要挪动数据

链表就是这样的一种存在。

单链表的三个文档

SList.h--------头文件的引用和函数的声明
SList.c--------函数的定义
test.c--------单链表的检验

创建结点函数

//创建节点
SLTNode* BuySLTNode(SListDataType x)
{SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));if (NewNode == NULL){perror("BuySLTNode()");exit(1);}NewNode->data = x;NewNode->next = NULL;return NewNode;
}

按元素从小到大的顺序创建链表

//创建链表
SLTNode* CreatSList(int n)
{SLTNode* Phead = NULL, * Ptail = NULL;for (int i = 0; i < n; i++){SLTNode* NewNode = BuySLTNode(i);if (NewNode == NULL){perror("CreatSList()");exit(1);}if (Phead == NULL){Phead = Ptail = NewNode;}else{Ptail->next = NewNode;Ptail = NewNode;}}return Phead;
}

打印链表

//打印链表
void SLTPrint(SLTNode* Phead)
{SLTNode* cur = Phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

尾插函数

//尾插函数
void SLTPushBack(SLTNode** PPhead, SListDataType x)
{SLTNode* NewNode = BuySLTNode(x);if (NewNode == NULL){perror("SLTPushBack()");exit(1);}if (*PPhead == NULL){*PPhead = NewNode;}else{SLTNode* cur = *PPhead;//找尾while (cur->next != NULL){cur = cur->next;}cur->next = NewNode;}
}

尾删函数

//尾删函数
void SLTPopBack(SLTNode** PPhead)
{assert(PPhead != NULL);if ((*PPhead)->next == NULL){free(*PPhead);*PPhead = NULL;}else{SLTNode* cur = *PPhead;//找尾while (cur->next->next != NULL){cur = cur->next;}free(cur->next);cur->next = NULL;}
}

头插函数

//头插函数
void SLTPushFront(SLTNode** PPhead, SListDataType x)
{SLTNode* NewNode = BuySLTNode(x);NewNode->next = *PPhead;*PPhead = NewNode;
}

头删函数

//头删函数
void SLTPopFront(SLTNode** PPhead)
{assert(PPhead != NULL);SLTNode* next = (*PPhead)->next;free(*PPhead);*PPhead = next;
}

在pos位置后面插入数据的函数

//在pos位置后面插入数据
void SLTInsertAfter(SLTNode* pos,SListDataType x)
{assert(pos != NULL);SLTNode* NewNode = BuySLTNode(x);NewNode->next = pos->next;pos->next = NewNode;
}

在pos位置插入数据的函数

//在pos位置插入数据
void SLTInsert(SLTNode** PPhead, SLTNode* pos, SListDataType x)
{assert(pos != NULL);if ((*PPhead) == pos){SLTPushFront(PPhead,x);}else{SLTNode* cur = *PPhead;SLTNode* NewNode = BuySLTNode(x);//找到pos前的位置while (cur->next != pos){cur = cur->next;}NewNode->next = pos;cur->next = NewNode;}
}

删除pos位置后面的数据的函数

//删除pos位置后面的数据
void SLTEraseAfter(SLTNode* pos)
{assert(pos != NULL);if (pos->next == NULL){return;}else{SLTNode* NextNode = pos->next;pos->next = NextNode->next;free(NextNode);NextNode = NULL;}
}

删除pos位置数据的函数

//删除pos位置的数据
void SLTErase(SLTNode** PPhead,SLTNode* pos)
{assert(*PPhead != NULL);assert(pos != NULL);if (pos == *PPhead){SLTPopFront(PPhead);}else{SLTNode* cur = *PPhead;while (cur->next != pos){cur = cur->next;}cur->next = pos->next;free(pos);pos = NULL;}
}

销毁链表的函数

//销毁链表
void SLTDestroy(SLTNode** PPhead)
{SLTNode* cur = *PPhead;while (cur != NULL){SLTNode* NextNode = cur->next;free(cur);cur = NextNode;}*PPhead = NULL;
}

查找数据的函数

//查找数据的函数
SLTNode* SLTFind(SLTNode* Phead, SListDataType x)
{SLTNode* cur = Phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL; 
}

删除相应元素的所有结点

//删除相应元素的所有结点
SLTNode* RemoveElements(SLTNode* Phead, SListDataType x)
{SLTNode* cur = Phead;SLTNode* NewHead = NULL, *Ptail = NULL;while (cur){if (cur->data != x){if (Ptail == NULL){NewHead = Ptail = cur;}else{Ptail->next = cur;Ptail = Ptail->next;}cur = cur->next;}else{SLTNode* NextNode = cur->next;free(cur);cur = NextNode;}}return NewHead;
}

利用数组创建结点的函数

//使用数组创建链表
SLTNode* CreatSLTByArr(SListDataType* arr, int n)
{SLTNode* Phead = NULL, * Ptail = NULL;for (int i = 0; i < n; i++){SLTNode* NewHead = BuySLTNode(arr[i]);if (Ptail == NULL){Phead = Ptail = NewHead;}else{Ptail->next = NewHead;Ptail = Ptail->next;}}return Phead;
}#define MAX 100//输入数组的元素
SListDataType* CreatArr()
{int N = 0;printf("请输入数组元素个数:>");scanf("%d", &N);SListDataType arr[MAX];printf("请依次输入数组的元素，按空格隔开\n");for (int i = 0; i < N; i++){scanf("%d",&arr[i]);}return CreatSLTByArr(arr,N);
}

结构体的定义和函数的声明

typedef int SListDataType;
typedef struct SListNode
{SListDataType data;struct SListNode* next;
}SLTNode;//创建结点
SLTNode* BuySLTNode(SListDataType x);//创建链表
SLTNode* CreatSList(int n);//打印链表
void SLTPrint(SLTNode* Phead);//尾插函数
void SLTPushBack(SLTNode** PPhead, SListDataType x);//尾删函数
void SLTPopBack(SLTNode** PPhead);//头插函数
void SLTPushFront(SLTNode** PPhead,SListDataType x);//头删函数
void SLTPopFront(SLTNode** PPhead);//在pos位置后面插入数据
void SLTInsertAfter(SLTNode* pos, SListDataType x);//在pos位置插入数据
void SLTInsert(SLTNode** PPhead, SLTNode* pos, SListDataType x);//删除pos位置后面的数据
void SLTEraseAfter(SLTNode* pos);//删除pos位置的数据
void SLTErase(SLTNode** PPhead, SLTNode* pos);//销毁链表
void SLTDestroy(SLTNode** PPhead);//查找数据的函数
SLTNode* SLTFind(SLTNode* Phead, SListDataType x);//删除相应元素的所有结点
SLTNode* RemoveElements(SLTNode* Phead,SListDataType x);//使用数组创建链表
SLTNode* CreatSLTByArr(SListDataType* arr, int n);//输入数组的元素
SListDataType* CreatArr();

菜单和主函数

void menu()
{printf("***********************************************************************************\n");printf("******      1.创建连续的链表                     2.通过数组元素创建链表      ******\n");printf("******      3.在pos位置后面插入数据              4.pos位置后面删除数据       ******\n");printf("******      5.在pos位置插入数据                  6.删除pos位置的数据         ******\n");printf("******      7.删除对应元素的所有结点             8.查找元素                  ******\n");printf("******      9.头插                               10.头删                     ******\n");printf("******      11.尾插                              12.尾删                     ******\n");printf("******      13.打印                              0.退出                      ******\n");printf("***********************************************************************************\n");
}int main()
{int input = 0;int Max = 0;SLTNode* Phead = NULL;int flag = 1;do{menu();if (flag == 1){printf("请优先在选项1或者选项2进行选择，创建一个链表\n");flag = -1;}printf("请选择:>\n");scanf("%d",&input);switch (input){case 1:printf("请输入该连续链表的结点个数:>");scanf("%d", &Max);Phead = CreatSList(Max);break;case 2:Phead = CreatArr();break;case 3:{int FindNum = 0;SListDataType x = 0;printf("请输入你要在哪个值后面插入数据:>\n");scanf("%d", &FindNum);printf("请输入想要插入的值:>\n");scanf("%d",&x);SLTNode* pos = SLTFind(Phead, FindNum);SLTInsertAfter(pos, x);break;}case 4:{int FindNum = 0;printf("请输入你要在哪个值后面删除数据:>\n");scanf("%d", &FindNum);SLTNode* pos = SLTFind(Phead, FindNum);SLTEraseAfter(pos);break;}case 5:{int FindNum = 0;SListDataType x = 0;printf("请输入你要在哪个值的位置插入数据:>\n");scanf("%d", &FindNum);printf("请输入想要插入的值:>\n");scanf("%d",&x);SLTNode* pos = SLTFind(Phead, FindNum);SLTInsert(&Phead, pos, x);break;}case 6:{int FindNum = 0;printf("请输入你删除哪个值的第一次出现的位置:>\n");scanf("%d", &FindNum);SLTNode* pos = SLTFind(Phead, FindNum);SLTErase(&Phead, pos);break;}case 7:{SListDataType Number = 0;printf("请输入你要删除哪个值:>\n");scanf("%d", &Number);Phead = RemoveElements(Phead, Number);break;}case 8:{SListDataType Number = 0;printf("请输入你要查找的元素:>\n");scanf("%d", &Number);SLTNode* Ptail = SLTFind(Phead, Number);printf("地址是:%p   在元素%d的前面\n", Ptail, Ptail->next->data);break;}case 9:{SListDataType Number = 0;printf("请输入你要插入的值:>");scanf("%d", &Number);SLTPushFront(&Phead, Number);break;}case 10:SLTPopFront(&Phead);break;case 11:{SListDataType Number = 0;printf("请输入你要插入的值:>");scanf("%d", &Number);SLTPushBack(&Phead,Number);break;}case 12:SLTPopBack(&Phead);break;case 13:SLTPrint(Phead);break;case 0:printf("销毁链表成功\n");SLTDestroy(&Phead);break;default:printf("选择错误，请重新选择\n");break;}} while (input);
}

SList.h文档的代码

#pragma once#include
#include
#includetypedef int SListDataType;
typedef struct SListNode
{SListDataType data;struct SListNode* next;
}SLTNode;//创建结点
SLTNode* BuySLTNode(SListDataType x);//创建链表
SLTNode* CreatSList(int n);//打印链表
void SLTPrint(SLTNode* Phead);//尾插函数
void SLTPushBack(SLTNode** PPhead, SListDataType x);//尾删函数
void SLTPopBack(SLTNode** PPhead);//头插函数
void SLTPushFront(SLTNode** PPhead,SListDataType x);//头删函数
void SLTPopFront(SLTNode** PPhead);//在pos位置后面插入数据
void SLTInsertAfter(SLTNode* pos, SListDataType x);//在pos位置插入数据
void SLTInsert(SLTNode** PPhead, SLTNode* pos, SListDataType x);//删除pos位置后面的数据
void SLTEraseAfter(SLTNode* pos);//删除pos位置的数据
void SLTErase(SLTNode** PPhead, SLTNode* pos);//销毁链表
void SLTDestroy(SLTNode** PPhead);//查找数据的函数
SLTNode* SLTFind(SLTNode* Phead, SListDataType x);//删除相应元素的所有结点
SLTNode* RemoveElements(SLTNode* Phead,SListDataType x);//使用数组创建链表
SLTNode* CreatSLTByArr(SListDataType* arr, int n);//输入数组的元素
SListDataType* CreatArr();

SList.c文档的代码

#include"SList.h"//创建节点
SLTNode* BuySLTNode(SListDataType x)
{SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));if (NewNode == NULL){perror("BuySLTNode()");exit(1);}NewNode->data = x;NewNode->next = NULL;return NewNode;
}//创建链表
SLTNode* CreatSList(int n)
{SLTNode* Phead = NULL, * Ptail = NULL;for (int i = 0; i < n; i++){SLTNode* NewNode = BuySLTNode(i);if (NewNode == NULL){perror("CreatSList()");exit(1);}if (Phead == NULL){Phead = Ptail = NewNode;}else{Ptail->next = NewNode;Ptail = NewNode;}}return Phead;
}//打印链表
void SLTPrint(SLTNode* Phead)
{SLTNode* cur = Phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}//尾插函数
void SLTPushBack(SLTNode** PPhead, SListDataType x)
{SLTNode* NewNode = BuySLTNode(x);if (NewNode == NULL){perror("SLTPushBack()");exit(1);}if (*PPhead == NULL){*PPhead = NewNode;}else{SLTNode* cur = *PPhead;//找尾while (cur->next != NULL){cur = cur->next;}cur->next = NewNode;}
}//尾删函数
void SLTPopBack(SLTNode** PPhead)
{assert(PPhead != NULL);if ((*PPhead)->next == NULL){free(*PPhead);*PPhead = NULL;}else{SLTNode* cur = *PPhead;//找尾while (cur->next->next != NULL){cur = cur->next;}free(cur->next);cur->next = NULL;}
}//头插函数
void SLTPushFront(SLTNode** PPhead, SListDataType x)
{SLTNode* NewNode = BuySLTNode(x);NewNode->next = *PPhead;*PPhead = NewNode;
}//头删函数
void SLTPopFront(SLTNode** PPhead)
{assert(PPhead != NULL);SLTNode* next = (*PPhead)->next;free(*PPhead);*PPhead = next;
}//在pos位置后面插入数据
void SLTInsertAfter(SLTNode* pos,SListDataType x)
{assert(pos != NULL);SLTNode* NewNode = BuySLTNode(x);NewNode->next = pos->next;pos->next = NewNode;
}//在pos位置插入数据
void SLTInsert(SLTNode** PPhead, SLTNode* pos, SListDataType x)
{assert(pos != NULL);if ((*PPhead) == pos){SLTPushFront(PPhead,x);}else{SLTNode* cur = *PPhead;SLTNode* NewNode = BuySLTNode(x);//找到pos前的位置while (cur->next != pos){cur = cur->next;}NewNode->next = pos;cur->next = NewNode;}
}//删除pos位置后面的数据
void SLTEraseAfter(SLTNode* pos)
{assert(pos != NULL);if (pos->next == NULL){return;}else{SLTNode* NextNode = pos->next;pos->next = NextNode->next;free(NextNode);NextNode = NULL;}
}//删除pos位置的数据
void SLTErase(SLTNode** PPhead,SLTNode* pos)
{assert(*PPhead != NULL);assert(pos != NULL);if (pos == *PPhead){SLTPopFront(PPhead);}else{SLTNode* cur = *PPhead;while (cur->next != pos){cur = cur->next;}cur->next = pos->next;free(pos);pos = NULL;}
}//销毁链表
void SLTDestroy(SLTNode** PPhead)
{SLTNode* cur = *PPhead;while (cur != NULL){SLTNode* NextNode = cur->next;free(cur);cur = NextNode;}*PPhead = NULL;
}//查找数据的函数
SLTNode* SLTFind(SLTNode* Phead, SListDataType x)
{SLTNode* cur = Phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL; 
}//删除相应元素的所有结点
SLTNode* RemoveElements(SLTNode* Phead, SListDataType x)
{SLTNode* cur = Phead;SLTNode* NewHead = NULL, *Ptail = NULL;while (cur){if (cur->data != x){if (Ptail == NULL){NewHead = Ptail = cur;}else{Ptail->next = cur;Ptail = Ptail->next;}cur = cur->next;}else{SLTNode* NextNode = cur->next;free(cur);cur = NextNode;}}return NewHead;
}//使用数组创建链表
SLTNode* CreatSLTByArr(SListDataType* arr, int n)
{SLTNode* Phead = NULL, * Ptail = NULL;for (int i = 0; i < n; i++){SLTNode* NewHead = BuySLTNode(arr[i]);if (Ptail == NULL){Phead = Ptail = NewHead;}else{Ptail->next = NewHead;Ptail = Ptail->next;}}return Phead;
}#define MAX 100//输入数组的元素
SListDataType* CreatArr()
{int N = 0;printf("请输入数组元素个数:>");scanf("%d", &N);SListDataType arr[MAX];printf("请依次输入数组的元素，按空格隔开\n");for (int i = 0; i < N; i++){scanf("%d",&arr[i]);}return CreatSLTByArr(arr,N);
}

test.c文档的代码

void menu()
{printf("***********************************************************************************\n");printf("******      1.创建连续的链表                     2.通过数组元素创建链表      ******\n");printf("******      3.在pos位置后面插入数据              4.pos位置后面删除数据       ******\n");printf("******      5.在pos位置插入数据                  6.删除pos位置的数据         ******\n");printf("******      7.删除对应元素的所有结点             8.查找元素                  ******\n");printf("******      9.头插                               10.头删                     ******\n");printf("******      11.尾插                              12.尾删                     ******\n");printf("******      13.打印                              0.退出                      ******\n");printf("***********************************************************************************\n");
}int main()
{int input = 0;int Max = 0;SLTNode* Phead = NULL;int flag = 1;do{menu();if (flag == 1){printf("请优先在选项1或者选项2进行选择，创建一个链表\n");flag = -1;}printf("请选择:>\n");scanf("%d",&input);switch (input){case 1:printf("请输入该连续链表的结点个数:>");scanf("%d", &Max);Phead = CreatSList(Max);break;case 2:Phead = CreatArr();break;case 3:{int FindNum = 0;SListDataType x = 0;printf("请输入你要在哪个值后面插入数据:>\n");scanf("%d", &FindNum);printf("请输入想要插入的值:>\n");scanf("%d",&x);SLTNode* pos = SLTFind(Phead, FindNum);SLTInsertAfter(pos, x);break;}case 4:{int FindNum = 0;printf("请输入你要在哪个值后面删除数据:>\n");scanf("%d", &FindNum);SLTNode* pos = SLTFind(Phead, FindNum);SLTEraseAfter(pos);break;}case 5:{int FindNum = 0;SListDataType x = 0;printf("请输入你要在哪个值的位置插入数据:>\n");scanf("%d", &FindNum);printf("请输入想要插入的值:>\n");scanf("%d",&x);SLTNode* pos = SLTFind(Phead, FindNum);SLTInsert(&Phead, pos, x);break;}case 6:{int FindNum = 0;printf("请输入你删除哪个值的第一次出现的位置:>\n");scanf("%d", &FindNum);SLTNode* pos = SLTFind(Phead, FindNum);SLTErase(&Phead, pos);break;}case 7:{SListDataType Number = 0;printf("请输入你要删除哪个值:>\n");scanf("%d", &Number);Phead = RemoveElements(Phead, Number);break;}case 8:{SListDataType Number = 0;printf("请输入你要查找的元素:>\n");scanf("%d", &Number);SLTNode* Ptail = SLTFind(Phead, Number);printf("地址是:%p   在元素%d的前面\n", Ptail, Ptail->next->data);break;}case 9:{SListDataType Number = 0;printf("请输入你要插入的值:>");scanf("%d", &Number);SLTPushFront(&Phead, Number);break;}case 10:SLTPopFront(&Phead);break;case 11:{SListDataType Number = 0;printf("请输入你要插入的值:>");scanf("%d", &Number);SLTPushBack(&Phead,Number);break;}case 12:SLTPopBack(&Phead);break;case 13:SLTPrint(Phead);break;case 0:printf("销毁链表成功\n");SLTDestroy(&Phead);break;default:printf("选择错误，请重新选择\n");break;}} while (input);
}

单链表的实现就到此结束，关注点一点，下期更精彩。