数据结构之带头节点的单链表增删改查操作实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构之带头节点的单链表增删改查操作实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

文章来源地址https://www.toymoban.com/news/detail-573013.html

单链表的定义

什么是单链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

单链表的各个数据元素在物理上可以是离散存放的，每个结点除了存放数据元素外，还要存储指向下一个节点的指针。而顺序表是连续存放的，每个结点中只存放数据元素。

单链表的优点：不要求大片连续空间，改变容量方便，只需在内存单元中随便找个位置作为新节点的区域；缺点：不可随机存储，要耗费一定空间存放指针。

顺序表的优点：可随机存储，存储密度高；缺点：要求大片连续空间，改变容量不方便，要在内存中再申请一片连续空间。

先理解并记住专业术语：

首节点：第一个有效节点。

尾节点：最后一个有效节点。

头节点：头节点的数据类型和首节点的类型一样，没有存放有效数据，最最前面的，是在首节点之前的，主要是为了方便对链表的操作（不理解的话，先记住）。

头指针：指向头节点的指针变量。

尾指针：指向尾节点的指针。

确定一个链表需要几个参数：（或者说如果期望一个函数对链表进行操作，我们至少需要接收链表的那些信息？？？）

只需要一个参数:头指针，因为通过它我们可以推出链表的所有信息。

用代码定义一个单链表

大概思路：由一个个节点组成一个单链表，所以从定义节点出发，来创建单链表。那节点里都有什么呢？每个节点里不光有存放的数据元素，还要有一个指向下一个节点的指针。这两个也称为数据域和指针域。为什么要有指针域呢？因为单链表的每个节点在物理上是离散存放的，有了一个节点后，那下一个节点就需要通过这个节点找到，这个节点的指针域可以理解为起着连接的作用。需要注意的是指针域的类型是我们此时定义的节点类型。之后为了方便写代码和区分，用typedef 起了节点和节点指针的别名。单链表的英文单词是LinkList，LNode是简写了单链表节点的英文单词 LinkNode。

1 typedef struct LNode{ //定义单链表结点类型    //这种方式代码可读性更强
2     int data;//每个节点存放一个数据元素
3     struct LNode *next;//指针指向下一个节点
4 }LNode, *LinkList; //LNode 是struct LNode 的别名，LinkList是struct LNode *的别名，指针指向整个结构体

在后续代码中，使用LinkList，强调这是一个单链表；使用LNode，强调这是一个节点。

1 void test()
2 {
3       LinkList L; // //声明一个指向单链表的指针,强调声明了一个单链表
4 }

初始化单链表

大概思路：在初始化的过程中，给单链表分配好一个头节点，让头节点的指向下一个节点的指针域指向空，因为在整个单链表中，此时还是空表，也就是没有有效节点，头节点虽然起着节点的名字，并且在写专业术语的时候说过，它只是为了便于操作，注意不要混淆了。

 1 bool InitList(LinkList &L) //初始化一个单链表（带头结点）
 2 {
 3     L = (LNode *)malloc(sizeof(LNode)); //分配一个头节点，malloc函数强调返回是一个节点（LNode *)，如果单链表有头节点，则头指针指向头节点，即 LinkList L = (LNode *)malloc(sizeof(LNode)); 等号有指向作用
 4     if(L == NULL) //内存不足，分配失败，就没有创建出单链表，因为已经分配了一个节点，所以只能内存不足的原因，空表是没有节点
 5         return false;
 6     L->next = NULL;//目前只有一个头节点，头节点之后暂时还没有节点
 7     return true;
 8 }
 9 void test()
10 {
11     LinkList L; //声明一个指向单链表的指针
12     InitList(L); //初始化一个空表
13     // .......后续代码......
14 }

如果要判断带头节点的单链表是否为空，代码如下：

1 bool Empty(LinkList L) //判断单链表是否为空（带头节点） 头节点不存储数据，只有指针域，且表内没有有效节点
2 {
3     if(L->next == NULL)
4         return true;
5     else
6         return false;
7 }

带头结点的单链表的插入操作

InsertList(&L,i,e)：插入操作。在表 L 中的第 i 个位置上插入指定元素 e，刚开始建议看b站的动画，再来理解代码 。

利用while循环找到第 i - 1 个结点，将新结点插入其后，头结点可以看作 “ 第0个” 结点。

 1 bool InsertList(LinkList &L, int i, ElemType e) //在第 i 个位置插入元素 e （带头结点）
 2 {
 3     if(i < 1) //只能在头结点之后插入，头结点是第0个,之后是第1个
 4         return false;
 5     LNode *p; //LNode * 强调这是一个结点，声明一个结点，表示指针p指向当前找到的结点
 6     p = L; //L是指向头结点的头指针，再把刚开始的指针p指向L，表示目前的指针p指向头结点
 7     int j = 0;//记录当前p指向的是第几个结点，从头结点0开始
 8     while(p!= NULL && j < i - 1) //循环找到第 i-1 个结点，j = i-1，不进入循环，内存满了，不进入循环
 9     {
10         p = p->next; //p指向下一个结点
11         j++;
12     }
13     if(p==NULL) //i值不合法，如果有4个结点，那i不能等于6，因为 p = p->next,在第5个位置之后满了，p指向NULL，下一步p->next出错了，根本找不到表的某个位置
14         return false;
15     LNode *s = (LNode *)malloc(sizeof(LNode));//创建一个节点，这个节点的数据域就是e
16     s->data = e;
17     s->next = p->next;  //自己画图理解，一开始p后的节点不是s，这里让p的下一个节点变成了在s的下一个节点
18     p->next = s; //将结点s连到p之后
19     return true; //插入成功
20 }

带头结点的单链表的删除操作

DeleteList(&L,i,&e)：删除操作。删除表L中第 i 个位置的元素，并用e返回删除元素的值。

利用while循环找到第 i - 1 个结点，将其指针指向第 i + 1个结点，并释放第 i 个结点。

 1 bool DeleteList(LinkList &L, int i, ElemType &e)
 2 {
 3     if(i < 1)
 4         return false;
 5     LNode *p;
 6     p = L;
 7     int j = 0;
 8     while(p != NULL && j < i - 1) //循环找第 i-1 个节点
 9     {
10         p = p->next;
11         j++;
12     }
13     if(p == NULL) //i值不合法，导致第 i-1 个节点根本在表中找不到
14         return false;
15     if(p->next == NULL) //第 i-1 个节点能找到，但是刚好第 i-1 个节点之后已无其他节点（第i个结点和第i+1个节点没有了），那就没有办法把第 i-1 个节点的指向下一个节点的指针指向第 i+1 个节点
16         return false;
17     LNode *q = p->next; //p是第 i-1 个节点，p->next是之后的节点，也是第 i 个节点，令q指向被删除节点
18     e = q->data; //用e返回元素的值
19     p->next = q->next; //将*q 节点从链中断开，重新更改指针p的指向，指向第 i + 1个节点
20     free(q); //释放节s点的存储空间
21     return true;
22 }

带头结点的单链表的修改操作

  UpdateList(&L, i, num)：修改操作，把第i个位置的数修改为num

 1 int UpdateList(LinkList &L, int i, int num)//把第i个位置的数修改为num
 2 {
 3    if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0
 4         return 0;
 5     LNode *p;
 6     int j = 0;
 7     p = L;
 8     while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点
 9     {  //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL
10         p = p->next;
11         j++;
12     }
13     p->data = num;
14     return p->data;    
15 }

带头结点的单链表的查找操作

GetList(L,i)：按位查找操作。获取表L中第 i 个位置的元素的值。

 1 int GetList(LinkList L, int i)//按位查找，返回第 i 个元素（带头节点）
 2 {
 3     if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0
 4         return NULL;
 5     LNode *p;
 6     int j = 0;
 7     p = L;
 8     while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点
 9     {  //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL
10         p = p->next;
11         j++;
12     }
13     return p->data;
14 } //平均时间复杂度为O(n)

带头结点的单链表的销毁操作

利用while循环把头节点之后的有效节点free掉。

 1 void Destroy(LinkList &L)
 2 {
 3     LNode *p;
 4     while(L != NULL)
 5     {
 6         p = L;
 7         L = L->next;
 8         free(p);
 9     }
10 }

完整的增删改查操作的代码，我自己一开始全写在main函数里，只能调用成功一个函数，我也不知道为啥，所以就用了switch选择结构来分别实现这些功能。这些代码理解了，就不难，建议多敲几遍！

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 typedef struct LNode{ //定义单链表结点类型    //这种方式代码可读性更强
  4     int data;//每个节点存放一个数据元素
  5     struct LNode *next;//指针指向下一个节点
  6 }LNode, *LinkList; //LNode 是struct LNode 的别名，LinkList是struct LNode *的别名，指针指向整个结构体
  7 bool InitList(LinkList &L) //初始化一个单链表（带头结点）
  8 {
  9     L = (LNode *)malloc(sizeof(LNode)); //分配一个头节点，malloc函数强调返回是一个节点（LNode *)，如果单链表有头节点，则头指针指向头节点，即 LinkList L = (LNode *)malloc(sizeof(LNode)); 等号有指向作用
 10     if(L == NULL) //内存不足，分配失败，就没有创建出单链表，因为已经分配了一个节点，所以只能内存不足的原因，空表是没有节点
 11         return false;
 12     L->next = NULL;//目前只有一个头节点，头节点之后暂时还没有节点
 13     return true;
 14 }
 15 bool InsertList(LinkList &L, int i, int e) //在第 i 个位置插入元素 e （带头结点）
 16 {
 17     if(i < 1) //只能在头结点之后插入，头结点是第0个,之后是第1个
 18         return false;
 19     LNode *p; //LNode * 强调这是一个结点，声明一个结点，表示指针p指向当前找到的结点
 20     p = L; //L是指向头结点的头指针，再把刚开始的指针p指向L，表示目前的指针p指向头结点
 21     int j = 0;//记录当前p指向的是第几个结点，从头结点0开始
 22     while(p!= NULL && j < i - 1) //循环找到第 i-1 个结点，j = i-1，不进入循环，内存满了，不进入循环
 23     {
 24         p = p->next; //p指向下一个结点
 25         j++;
 26     }
 27     if(p==NULL) //i值不合法，如果有4个结点，那i不能等于6，因为 p = p->next,在第5个位置之后满了，p指向NULL，下一步p->next出错了，根本找不到表的某个位置
 28         return false;
 29     LNode *s = (LNode *)malloc(sizeof(LNode));//创建一个节点，这个节点的数据域就是e
 30     s->data = e;
 31     s->next = p->next;  //自己画图理解，一开始p后的节点不是s，这里让p的下一个节点变成了在s的下一个节点
 32     p->next = s; //将结点s连到p之后
 33     return true; //插入成功
 34 }
 35 void ShowList(LinkList L) //显示
 36 {
 37     if(L->next == NULL)
 38        printf("这是一个空表\n"); 
 39     while(L != NULL)
 40     {
 41         L = L->next;
 42         printf("%d ",L->data);
 43     }
 44     
 45 }
 46 bool DeleteList(LinkList &L, int i, int &e)//删除表L中第 i 个位置的元素，并用e返回删除元素的值。
 47 {
 48     if(i < 1)
 49         return false;
 50     LNode *p;
 51     p = L;
 52     int j = 0;
 53     while(p != NULL && j < i - 1) //循环找第 i-1 个节点
 54     {
 55         p = p->next;
 56         j++;
 57     }
 58     if(p == NULL) //i值不合法，导致第 i-1 个节点根本在表中找不到
 59         return false;
 60     if(p->next == NULL) //第 i-1 个节点能找到，但是刚好第 i-1 个节点之后已无其他节点（第i个结点和第i+1个节点没有了），那就没有办法把第 i-1 个节点的指向下一个节点的指针指向第 i+1 个节点
 61         return false;
 62     LNode *q = p->next; //p是第 i-1 个节点，p->next是之后的节点，也是第 i 个节点，令q指向被删除节点
 63     e = q->data; //用e返回元素的值
 64     p->next = q->next; //将*q 节点从链中断开，重新更改指针p的指向，指向第 i + 1个节点
 65     free(q); //释放节s点的存储空间
 66     return true;
 67 }
 68 int GetList(LinkList &L, int i)//按位查找，返回第 i 个元素（带头节点）
 69 {
 70     if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0
 71         return 0;
 72     LNode *p;
 73     int j = 0;
 74     p = L;
 75     while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点
 76     {  //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL
 77         p = p->next;
 78         j++;
 79     }
 80     return p->data;
 81 } //平均时间复杂度为O(n)
 82 int UpdateList(LinkList &L, int i, int num)
 83 {
 84    if(i < 0)//有头节点，头节点是第0个节点，所以查找元素i不能小于0
 85         return 0;
 86     LNode *p;
 87     int j = 0;
 88     p = L;
 89     while(p != NULL && j < i) //找的是第i个节点，插入那里找的是第i-1 个节点
 90     {  //如果i大于表的长度，那循环找到的p会指向NULL，不会进入循环体，最后返回NULL
 91         p = p->next;
 92         j++;
 93     }
 94     p->data = num;
 95     return p->data;    
 96 }
 97 void Destroy(LinkList &L) //销毁单链表 
 98 {
 99     LNode *p;
100     while(L != NULL)
101     {
102         p = L;
103         L = L->next;
104         free(p);
105     }
106 }
107 void ShowMenu()
108 {
109     printf("************************\n");
110     printf("*****  1,添加数据  *****\n");
111     printf("*****  2,删除数据  *****\n");
112     printf("*****  3,查找数据  *****\n");    
113     printf("*****  4,修改数据  *****\n");
114     printf("*****  5,显示数据  *****\n");
115     printf("*****  0,销毁并退出  ***\n");
116 }
117 int main()
118 {
119     LinkList L;//声明一个单链表 
120     InitList(L);//初始化函数调用 
121 
122     int select = 0; //创建选择输入的变量
123     while (true)
124     {
125         //菜单调用
126         ShowMenu();
127         printf("请输入你的选择\n");
128         scanf("%d", &select);
129         switch (select)
130         {
131         case 1: //1,添加数据
132             InsertList(L,1,1);
133             InsertList(L,2,2);  
134             InsertList(L,3,3);
135             InsertList(L,4,4);
136             InsertList(L,5,5);
137             printf("数据添加成功！\n");
138             getchar();
139             break;
140         case 2: //2,删除数据
141             int e;
142             if(DeleteList(L,4,e))
143             {
144                 printf("删除的数是：%d\n",e);
145             }
146             getchar();
147             break;
148         case 3: //3,查找数据
149             printf("查找的元素是：%d\n",GetList(L,1));
150             getchar();
151             break;
152         case 4: //4,修改数据
153             UpdateList(L,1,0);
154             printf("修改成功！\n"); 
155             getchar();
156             break;            
157         case 5: //4,显示数据
158             printf("单链表的数据有："); 
159             ShowList(L);
160             getchar();
161             break;
162         case 0: //0,退出
163             Destroy(L);
164             printf("单链表已销毁！");
165             printf("欢迎下次使用");
166             return 0;
167             break;
168 
169         default:
170             break;
171         }
172     }
173     return 0;
174 }