C/C++语言实现单链表(带头结点)

2019/02/22 10:29
阅读数 29

彻底理解链表中为何使用二级指针或者一级指针的引用

数据结构之链表-链表实现及常用操作(C++篇)

  C语言实现单链表,主要功能为空链表创建,链表初始化(头插法),链表元素读取,按位置插入,(有序链表)按值插入,按位置删除,按值删除,清空链表,销毁链表。

  关键思路:(1)将结点创建结构体;(2)链表中添加头结点,以便统一操作;(3)使用结点一级指针和二级指针的异同点;(4)链表的最小操作单位是结点;(5)操作的起始位置是头结点还是第一个结点,及起始索引是0还是1. 

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <time.h>
  4 
  5 //涉及到结构体自引用
  6 typedef struct Node{
  7     int data;
  8     struct Node *next;
  9 }Node;
 10 
 11 //创建空链表
 12 //必须用二级指针,涉及到头指针的创建
 13 int iniList(Node **List){
 14     *List = (Node *)malloc(sizeof(Node));
 15     if (NULL == *List){
 16         return 0;
 17     }
 18 
 19     (*List)->next = NULL; //创建头结点
 20     return 1;
 21 }
 22 
 23 //初始化链表(头插法)
 24 //必须二级指针
 25 int iniListHead(Node **List, int n){
 26     *List = (Node *)malloc(sizeof(Node));
 27     if (NULL == *List){
 28         return 0;
 29     }
 30     (*List)->next = NULL;
 31     srand(time(0));
 32 
 33     int i = 0;
 34     while (i < n){
 35         Node *tmpNode = (Node *)malloc(sizeof(Node));
 36         if (NULL == tmpNode){
 37             return 0;
 38         }
 39         tmpNode->data = rand() % 100 + 1;
 40         tmpNode->next = (*List)->next;
 41         (*List)->next = tmpNode;
 42         
 43 
 44         ++i;
 45     }
 46     return 1;
 47 }
 48 
 49 //初始化链表(尾插法)
 50 //必须二级指针
 51 //需要借助辅助变量pCurrent,将每次尾插的新元素当做当前元素
 52 int iniListTail(Node **List, int n){
 53     *List = (Node *)malloc(sizeof(Node));
 54     if (NULL == *List){
 55         return 0;
 56     }
 57     (*List)->next = NULL;
 58     srand(time(0));
 59 
 60     Node *pCurrent = *List;
 61 
 62     int i = 0;
 63     while (i < n){
 64         Node *tmpNode = (Node *)malloc(sizeof(Node));
 65         if (NULL == tmpNode){
 66             return 0;
 67         }
 68         tmpNode->data = rand() % 100 + 1;
 69         tmpNode->next = NULL;
 70         pCurrent->next = tmpNode;
 71         pCurrent = tmpNode;
 72 
 73         ++i;
 74     }
 75     return 1;
 76 }
 77 
 78 //清空链表(不删除头结点)
 79 //一级,二级指针均可
 80 //首先找到链表地址,然后移动至表尾
 81 //判断条件为指针域是否为空,即到达结尾
 82 int deleteList(Node *List){
 83 
 84     //这种方法无法删除尾结点
 85     //Node *p= List;
 86     //Node *q = NULL;
 87     //
 88     //while (p->next){
 89     //    q = p;
 90     //    free(p);
 91     //    p = q->next;
 92     //}
 93 
 94     Node *p = List->next;
 95     Node *q = NULL;
 96 
 97     while (p){
 98         q = p->next;
 99         free(p);
100         p = q;
101     }
102 
103     List->next = NULL;
104     return 1;
105 }
106 
107 //销毁链表
108 //必须使用二级指针,销毁头结点和头指针
109 //最后将链表头指针置空
110 int desrotyList(Node **List){
111 
112     Node *p = *List;
113     Node *q = NULL;
114 
115     //如果为空链表,直接删除头结点
116     //如果不是空链表,从头结点开始删除
117     while (p){
118         q = p->next;
119         free(p);
120         p = q;
121     }
122     (*List) = NULL;
123 
124     //下面是从第一个结点开始删除
125     //最后释放掉头结点
126     //Node *p = (*List)->next;
127     //Node *q = NULL;
128     //
129     //while (p){
130     //    q = p->next;
131     //    free(p);
132     //    p = q;
133     //}
134     //free(*List);
135     //(*List) = NULL;
136 
137     return 1;
138 }
139 
140 //链表获取元素
141 //一级,二级指针均可
142 //头结点无意义,从第一个结点开始遍历,i从1开始
143 //每次都指向下一结点,到pos-1即可
144 int getList(Node *List, int pos, int *element){
145     Node *p = List->next;
146     
147     int i = 1;
148     while (p && i < pos){
149         p = p->next;
150         ++i;
151     }
152     *element = p->data;
153     return 1;
154 }
155 
156 //链表按位置插入
157 //一级,二级指针均可
158 //从头结点开始,有可能插入在第一个位置,遍历从1开始
159 int insertListPos(Node *List, int pos, int value){
160     Node *p = List;
161 
162     int i = 1;
163     while (p && i < pos){
164         p = p->next;
165         ++i;
166     }
167     Node *tmpNode = (Node *)malloc(sizeof(Node));
168     tmpNode->data = value;
169     tmpNode->next = p->next;
170     p->next = tmpNode;
171     return 1;
172 }
173 
174 //有序链表,按值插入
175 //一二级指针均可
176 int insertListValue(Node *List, int value){
177     Node *pCur = List->next;
178     Node *pPer = List;
179     while (pCur && pCur->data < value){
180         pPer = pCur;
181         pCur = pCur->next;
182     }
183 
184     Node *tmpNode = (Node *)malloc(sizeof(Node));
185     if (NULL == tmpNode){
186         return 0;
187     }
188     tmpNode->data = value;
189     tmpNode->next = pPer->next;
190     pPer->next = tmpNode;
191     return 1;
192 }
193 
194 //链表按位置删除
195 //一二级指针均可
196 //记得释放结点内存
197 //如果删除第一个结点,需要操纵头结点
198 int deleteListPos(Node *List, int pos){
199     Node *p = List;
200 
201     int i = 1;
202     while (p && i < pos){
203         p = p->next;
204         ++i;
205     }
206     if (NULL == p->next)
207         return 0;
208 
209     Node *tmpNode = p->next;
210     p->next = p->next->next;
211     
212     free(tmpNode);
213     return 1;
214 }
215 
216 //链表按值删除元素
217 //一二级指针均可
218 //从第一个结点开始
219 int deleteListValue(Node *List, int value){
220     Node *pCur = List->next;
221     Node *pPer = List;
222 
223     while (pCur && pCur->data != value){
224         pPer = pCur;
225         pCur = pCur->next;
226     }
227     if (pCur == NULL){ //空链表不删除任何结点
228         return 0;
229     }
230     else{
231         pPer->next = pCur->next;
232         free(pCur);
233     }
234     return 1;
235 }
236 
237 int main(){
238 
239     Node *testList = NULL;
240     iniList(&testList);
241     //iniListHead(&testList, 3);
242     //iniListTail(&testList, 3);
243     
244 
245     insertListPos(testList, 1, 2);
246     insertListPos(testList, 2, 4);
247     insertListPos(testList, 3, 5);
248     insertListPos(testList, 4, 10);
249     //insertListPos(testList, 1, 1);
250     insertListValue(testList, 1);
251 
252     //deleteListPos(testList, 1);
253     //deleteListValue(testList, 4);
254 
255     //deleteList(testList);
256 
257     //printf("%d\n", testList);
258     //desrotyList(&testList);
259     //printf("%d\n", testList);
260 
261     Node * tmpNode = testList->next;
262     while (tmpNode){
263         printf("%d\n", tmpNode->data);
264         tmpNode = tmpNode->next;
265     }
266 
267     printf("----------------------\n");
268 
269     int a = 0;
270     getList(testList, 2, &a);
271     printf("%d\n", a);
272 
273     system("pause");
274 
275     return 0;
276 }
C语言完整代码

  通过C++实现C语言的链表,主要区别:(1)struct可以不通过typedef,直接使用Node;(2)将malloc和free更换为new和delete

  1 #include<iostream>
  2 #include<ctime>
  3 
  4 using namespace std;
  5 
  6 struct Node{
  7     int data;
  8     Node *next;
  9 };
 10 
 11 //创建空链表
 12 //必须用二级指针,涉及到头指针的创建
 13 int iniList(Node **List){
 14     *List = new Node;
 15 
 16     (*List)->next = NULL; //创建头结点
 17     return 1;
 18 }
 19 
 20 //初始化链表(头插法)
 21 //必须二级指针
 22 int iniListHead(Node **List, int n){
 23     *List = new Node;
 24 
 25     (*List)->next = NULL;
 26     srand(time(0));
 27 
 28     int i = 0;
 29     while (i < n){
 30         Node *tmpNode = new Node;
 31 
 32         tmpNode->data = rand() % 100 + 1;
 33         tmpNode->next = (*List)->next;
 34         (*List)->next = tmpNode;
 35 
 36         ++i;
 37     }
 38     return 1;
 39 }
 40 
 41 //初始化链表(尾插法)
 42 //必须二级指针
 43 //需要借助辅助变量pCurrent,将每次尾插的新元素当做当前元素
 44 int iniListTail(Node **List, int n){
 45     *List = new Node;
 46 
 47     (*List)->next = NULL;
 48     srand(time(0));
 49 
 50     Node *pCurrent = *List;
 51 
 52     int i = 0;
 53     while (i < n){
 54         Node *tmpNode = new Node;
 55 
 56         tmpNode->data = rand() % 100 + 1;
 57         tmpNode->next = NULL;
 58         pCurrent->next = tmpNode;
 59         pCurrent = tmpNode;
 60 
 61         ++i;
 62     }
 63     return 1;
 64 }
 65 
 66 //清空链表(不删除头结点)
 67 //一级,二级指针均可
 68 //首先找到链表地址,然后移动至表尾
 69 //判断条件为指针域是否为空,即到达结尾
 70 int deleteList(Node *List){
 71 
 72     //这种方法无法删除尾结点
 73     //Node *p= List;
 74     //Node *q = NULL;
 75     //
 76     //while (p->next){
 77     //    q = p;
 78     //    free(p);
 79     //    p = q->next;
 80     //}
 81 
 82     Node *p = List->next;
 83     Node *q = NULL;
 84 
 85     while (p){
 86         q = p->next;
 87         delete p;
 88         p = q;
 89     }
 90 
 91     List->next = NULL;
 92     return 1;
 93 }
 94 
 95 //销毁链表
 96 //必须使用二级指针,销毁头结点和头指针
 97 //最后将链表头指针置空
 98 int desrotyList(Node **List){
 99 
100     Node *p = *List;
101     Node *q = NULL;
102 
103     //如果为空链表,直接删除头结点
104     //如果不是空链表,从头结点开始删除
105     while (p){
106         q = p->next;
107         delete p;
108         p = q;
109     }
110     (*List) = NULL;
111 
112     //下面是从第一个结点开始删除
113     //最后释放掉头结点
114     //Node *p = (*List)->next;
115     //Node *q = NULL;
116     //
117     //while (p){
118     //    q = p->next;
119     //    free(p);
120     //    p = q;
121     //}
122     //free(*List);
123     //(*List) = NULL;
124 
125     return 1;
126 }
127 
128 //链表获取元素
129 //一级,二级指针均可
130 //头结点无意义,从第一个结点开始遍历,i从1开始
131 //每次都指向下一结点,到pos-1即可
132 int getList(Node *List, int pos, int *element){
133     Node *p = List->next;
134 
135     int i = 1;
136     while (p && i < pos){
137         p = p->next;
138         ++i;
139     }
140     *element = p->data;
141     return 1;
142 }
143 
144 //链表按位置插入
145 //一级,二级指针均可
146 //从头结点开始,有可能插入在第一个位置,遍历从1开始
147 int insertListPos(Node *List, int pos, int value){
148     Node *p = List;
149 
150     int i = 1;
151     while (p && i < pos){
152         p = p->next;
153         ++i;
154     }
155     Node *tmpNode = new Node;
156     tmpNode->data = value;
157     tmpNode->next = p->next;
158     p->next = tmpNode;
159     return 1;
160 }
161 
162 //有序链表,按值插入
163 //一二级指针均可
164 int insertListValue(Node *List, int value){
165     Node *pCur = List->next;
166     Node *pPer = NULL;
167     while (pCur && pCur->data < value){
168         pPer = pCur;
169         pCur = pCur->next;
170     }
171 
172     Node *tmpNode = new Node;
173     if (NULL == tmpNode){
174         return 0;
175     }
176     tmpNode->data = value;
177     tmpNode->next = pPer->next;
178     pPer->next = tmpNode;
179     return 1;
180 }
181 
182 //链表按位置删除
183 //一二级指针均可
184 //记得释放结点内存
185 //如果删除第一个结点,需要操纵头结点
186 int deleteListPos(Node *List, int pos){
187     Node *p = List;
188 
189     int i = 1;
190     while (p && i < pos){
191         p = p->next;
192         ++i;
193     }
194     Node *tmpNode = p->next;
195     p->next = p->next->next;
196 
197     delete tmpNode;
198     return 1;
199 }
200 
201 //链表按值删除元素
202 //一二级指针均可
203 //从第一个结点开始
204 int deleteListValue(Node *List, int value){
205     Node *pCur = List->next;
206     Node *pPer = List;
207 
208     while (pCur && pCur->data != value){
209         pPer = pCur;
210         pCur = pCur->next;
211     }
212     if (pCur == NULL){
213         return 0;
214     }
215     else{
216         pPer->next = pCur->next;
217         delete pCur;
218     }
219     return 1;
220 }
C++完整代码

结点结构体

  将结点创建为结构体,其中包含数据域和指针域成员,指针域涉及结构体自引用。指针域成员之所以为结点类指针,一是为了编译时能明确结构体大小,二是为了指向下一个结点,因此初始化时不用开辟内存,只需要赋值为NULL即可。当然了,开辟内存也是可以的,这样在删除结点,及清空链表时需要记得将其释放,多此一举,不提倡。

1 //涉及到结构体自引用
2 typedef struct Node{
3     int data;
4     struct Node *next;
5 }Node;

 

空链表创建(二级指针)

  空链表创建时,建议创建头结点。在插入和删除第一个位置的元素时,需要用结点的二级指针移动头指针,但普通结点的插入和删除并不需要移动头指针。为了便于操作的统一(指插入和删除操作),这里先创建头结点。

  另外,在创建空链表时,需要传入二级指针,主要是为了操作头指针,只要涉及操作头指针的都需要使用二级指针。

 1 //创建空链表
 2 //必须用二级指针,涉及到头指针的创建
 3 int iniList(Node **List){
 4     *List = (Node *)malloc(sizeof(Node));
 5     if (NULL == *List){
 6         return 0;
 7     }
 8 
 9     (*List)->next = NULL; //创建头结点,将其指针域置空
10     return 1;
11 }

 

链表初始化(二级指针)

  链表初始化,即是创建空链表,并对链表中的n个元素进行赋值。一般来说,有头插法、尾插法两种,头插法是在头结点后插入,尾插法是在链表尾插入。

  头插法

  头插法一般思路:(1)创建带头结点的空链表;(2)创建新结点,对新结点赋值;(3)新结点指向头结点的下一个结点,头结点指向新结点。

 1 //初始化链表(头插法)
 2 //必须二级指针
 3 int iniListHead(Node **List, int n){
 4     *List = (Node *)malloc(sizeof(Node));
 5     if (NULL == *List){
 6         return 0;
 7     }
 8     (*List)->next = NULL;
 9     srand(time(0));
10 
11     int i = 0;
12     while (i < n){
13         Node *tmpNode = (Node *)malloc(sizeof(Node));
14         if (NULL == tmpNode){
15             return 0;
16         }
17         tmpNode->data = rand() % 100 + 1;
18         tmpNode->next = (*List)->next;
19         (*List)->next = tmpNode;
20         
21 
22         ++i;
23     }
24     return 1;
25 }

 

  尾插法

  尾插法一般思路:(1)创建带头结点的空链表;(2)创建新结点,对新结点数据域赋值,指针域置空;(3)建立临时变量指向头结点,头结点指向新结点;(4)将临时变量往后移动,指向新结点。

 1 //初始化链表(尾插法)
 2 //必须二级指针
 3 //需要借助辅助变量pCurrent,将每次尾插的新元素当做当前元素
 4 int iniListTail(Node **List, int n){
 5     *List = (Node *)malloc(sizeof(Node));
 6     if (NULL == *List){
 7         return 0;
 8     }
 9     (*List)->next = NULL;
10     srand(time(0));
11 
12     Node *pCurrent = *List;
13 
14     int i = 0;
15     while (i < n){
16         Node *tmpNode = (Node *)malloc(sizeof(Node));
17         if (NULL == tmpNode){
18             return 0;
19         }
20         tmpNode->data = rand() % 100 + 1;
21         tmpNode->next = NULL;
22         pCurrent->next = tmpNode;
23         pCurrent = tmpNode;
24 
25         ++i;
26     }
27     return 1;
28 }

 

链表元素读取(一、二级指针)

  链表元素读取,需要涉及到索引位置。我们知道头结点的数据域没有意义,因此起始位置从第一个结点开始,遍历值从1开始,到pos-1为止,此时p指向pos结点。

 1 //链表获取元素
 2 //一级,二级指针均可
 3 //头结点无意义,从第一个结点开始遍历,i从1开始
 4 //每次都指向下一结点,到pos-1即可
 5 int getList(Node *List, int pos, int *element){
 6     Node *p = List->next;
 7     
 8     int i = 1;
 9     while (p && i < pos){
10         p = p->next;
11         ++i;
12     }
13     *element = p->data;
14     return 1;
15 }

 

按位置插入(一、二级指针)

  插入时,需要考虑任意位置,由于头结点的设立,我们不需要单独考虑第一个位置的结点插入。

  一般思路:(1)起始位置从头结点开始,遍历值从1开始,到pos-1为止,此时指向pos-1结点;(2)创建新结点,给新结点数据域赋值;(3)新结点指向pos位置的下一结点,pos位置指向新结点。

 1 //链表按位置插入
 2 //一级,二级指针均可
 3 //从头结点开始,有可能插入在第一个位置,遍历从1开始
 4 int insertListPos(Node *List, int pos, int value){
 5     Node *p = List;
 6 
 7     int i = 1;
 8     while (p && i < pos){
 9         p = p->next;
10         ++i;
11     }
12     Node *tmpNode = (Node *)malloc(sizeof(Node));
13     tmpNode->data = value;
14     tmpNode->next = p->next;
15     p->next = tmpNode;
16     return 1;
17 }

 

有序链表按值插入(一、二级指针)

  有序链表中涉及到按值插入,按值删除时,需要建立两个临时变量,不同于按位置插入,我们可以在pos前一个停止遍历,按值插入,我们需要遍历找到插入位置,操作插入位置的前一个结点。

  一般思路:(1)从第一个结点开始遍历;(2)创建per变量标记当前结点的前一结点;(3)创建新结点,操作per结点;(4)常规插入操作。

 1 //有序链表,按值插入
 2 //一二级指针均可
 3 int insertListValue(Node *List, int value){
 4     Node *pCur = List->next;
 5     Node *pPer = NULL;
 6     while (pCur && pCur->data < value){
 7         pPer = pCur;
 8         pCur = pCur->next;
 9     }
10 
11     Node *tmpNode = (Node *)malloc(sizeof(Node));
12     if (NULL == tmpNode){
13         return 0;
14     }
15     tmpNode->data = value;
16     tmpNode->next = pPer->next;
17     pPer->next = tmpNode;
18     return 1;
19 }

 

按位置删除(一、二级指针)

  删除时,由于头结点的设立,因此不需要特殊考虑第一个位置的操作和头指针的移动。需要设置临时变量是释放p->next后,后面还会使用p->next的结点,这样会造成访问出错。

  一般思路:(1)起始位置从头结点开始,遍历从1开始,到pos-1为止,此时指向pos-1结点;(2)创建临时变量,指向pos结点;(3)将pos-1结点指向pos的下一结点,释放掉pos结点。

 1 //链表按位置删除
 2 //一二级指针均可
 3 //记得释放结点内存
 4 //如果删除第一个结点,需要操纵头结点
 5 int deleteListPos(Node *List, int pos){
 6     Node *p = List;
 7 
 8     int i = 1;
 9     while (p && i < pos){
10         p = p->next;
11         ++i;
12     }
13     Node *tmpNode = p->next;
14     p->next = p->next->next;
15     
16     free(tmpNode);
17     return 1;
18 }

 

按值删除(一、二级指针)

  按值删除与按值插入一样,需要两个临时变量。

  一般思路:(1)起始位置从第一个结点开始,(2)设立per结点指针保存当前结点的上一结点;(3)常规删除操作。

 1 //链表按值删除元素
 2 //一二级指针均可
 3 //从第一个结点开始
 4 int deleteListValue(Node *List, int value){
 5     Node *pCur = List->next;
 6     Node *pPer = List;
 7 
 8     while (pCur && pCur->data != value){
 9         pPer = pCur;
10         pCur = pCur->next;
11     }
12     if (pCur == NULL){ //空链表不删除任何结点
13         return 0;
14     }
15     else{
16         pPer->next = pCur->next;
17         free(pCur);
18     }
19     return 1;
20 }

 

清空链表(一、二级指针)

  清空链表,只是将链表中的结点删除,并释放掉结点空间,保留头结点,并将头结点的指针域置空。

  一般思路:(1)起始位置从第一个结点开始;(2)设置临时变量q指向当前结点p的下一结点,释放掉当前结点p,将临时变量q赋给p;(3)最后将头结点的指针置空。

 1 //清空链表(不删除头结点)
 2 //一级,二级指针均可
 3 //首先找到链表地址,然后移动至表尾
 4 //判断条件为指针域是否为空,即到达结尾
 5 int deleteList(Node *List){
 6 
 7     //这种方法无法删除尾结点,当p->next是尾结点上一节点时,走一遍程序
 8     //Node *p= List;
 9     //Node *q = NULL;
10     //
11     //while (p->next){
12     //    q = p;
13     //    free(p);
14     //    p = q->next;
15     //}
16 
17     Node *p = List->next;
18     Node *q = NULL;
19 
20     while (p){
21         q = p->next;
22         free(p);
23         p = q;
24     }
25 
26     List->next = NULL;
27     return 1;
28 }

 

销毁链表(二级指针)

  销毁链表,是在清空链表的基础上,删除头结点,将头指针置空,涉及到头指针的操作,需要二级指针。

  思路一:(1)与清空链表操作相同,从第一个结点开始删除;(2)最后释放掉头结点,将头指针置空

  思路二:(1)起始位置从头结点开始删除;(2)将头指针置空

 1 //销毁链表
 2 //必须使用二级指针,销毁头结点和头指针
 3 //最后将链表头指针置空
 4 int desrotyList(Node **List){
 5 
 6     Node *p = *List;
 7     Node *q = NULL;
 8 
 9     //如果为空链表,直接删除头结点
10     //如果不是空链表,从头结点开始删除
11     while (p){
12         q = p->next;
13         free(p);
14         p = q;
15     }
16     (*List) = NULL;
17 
18     //下面是从第一个结点开始删除
19     //最后释放掉头结点
20     //Node *p = (*List)->next;
21     //Node *q = NULL;
22     //
23     //while (p){
24     //    q = p->next;
25     //    free(p);
26     //    p = q;
27     //}
28     //free(*List);
29     //(*List) = NULL;
30 
31     return 1;
32 }

 二级指针和一级指针插入解析

 

-------------------------------------------------------------------------------------------------------------

如果上面的资料对你有启发,麻烦点个推荐,让更多人的人看到哦。

关注公众号【两猿社】,懂点互联网,懂点IC的程序猿,带你丰富项目经验哦。

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部