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

156 0 0

作者:romantichuaner

单链表的定义

什么是单链表

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

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

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

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

先理解并记住专业术语：

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

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

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

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

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

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

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

用代码定义一个单链表

大概思路：由一个个节点组成一个单链表，所以从定义节点出发，来创建单链表。那节点里都有什么呢？每个节点里不光有存放的数据元素，还要有一个指向下一个节点的指针。这两个也称为数据域和指针域。为什么要有指针域呢？因为单链表的每个节点在物理上是离散存放的，有了一个节点后，那下一个节点就需要通过这个节点找到，这个节点的指针域可以理解为起着连接的作用。需要注意的是指针域的类型是我们此时定义的节点类型。之后为了方便写代码和区分，用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("删除的数是：%dn",e);
145             }
146             getchar();
147             break;
148         case 3: //3,查找数据
149             printf("查找的元素是：%dn",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 }