//VS2022 x86编译器下已测试通过
//C语言 链表的基本使用 -- 13个函数,初始化(头插、尾插)、遍历打印、获取元素总个数、插入(按值前插/后插、按位置)、删除(按值、按位置)、逆置、清空、销毁
//如果在CLion中使用,请将这三个文件放在CMakeLists.txt的同级目录下,在CMakeLists.txt中添加如下内容,生成程序后,在终端切换到对应的exe所在文件夹,之后输入程序名称(.Demo.exe) 即可开始运行。或者Run程序,之后在Run的窗口中,修改如下:Edit Run Configuration -- 勾选Run in external console,之后Rerun,也可以运行。测试代码输入1,2,3,4,5,-1,即可得到Demo.c文件中那些被注释的链表结果。
include_directories(.) add_executable(Demo Demo.c linklist.c)
示例代码:三个文件,linklist.h、linklist.c 和Demo.c
linklist.h代码:
1 #pragma once 2 3 #define _CRT_SECURE_NO_WARNINGS 4 #include <stdio.h> 5 #include <stdlib.h> 6 #include <string.h> 7 8 //定义结点 9 struct LinkNode 10 { 11 int num; 12 struct LinkNode* next; 13 }; 14 15 //01.初始化链表:尾插法:可以使遍历链表得出的数据和输入的数据顺序相同 16 struct LinkNode* initLinkListTail(); 17 18 //02.初始化链表:头插法:可以使遍历链表得出的数据和输入的数据顺序相反 19 struct LinkNode* initLinkListHead(); 20 21 //03.遍历链表,并打印输出 22 void foreach_LinkList(struct LinkNode* pHeader); 23 24 //04.获取链表长度,获取链表中元素个数 25 int getElementNums(struct LinkNode* pHeader); 26 27 //05.获取链表中某位置对应的结点的值,假设头结点为第0个结点,pos为链表中第pos个结点 28 int getValueByPos(struct LinkNode* pHeader, int pos); 29 30 //06.向链表插入新结点(根据结点值):到现存结点前面或末尾 31 void insert_LinkListByValueBefore(struct LinkNode* pHeader, int oldVal, int newVal); 32 33 //07.向链表插入新结点(根据结点值):到现存结点后面或末尾,尾插法 34 void insert_LinkListByValueAfter(struct LinkNode* pHeader, int oldVal, int newVal); 35 36 //08.向链表插入新节点(根据给定位置):位置需要为大于0的数 37 void insert_LinkListByPos(struct LinkNode* pHeader, int pos, int newVal); 38 39 //09.删除链表(根据给定结点值):删除链表中某个结点 40 void delete_LinkListByValue(struct LinkNode* pHeader, int delVal); 41 42 //10.删除链表(根据给定位置):删除链表中某个结点 43 void delete_LinkListByPos(struct LinkNode* pHeader, int pos); 44 45 //11.反转链表:逆置 46 void reverse_LinkList(struct LinkNode* pHeader); 47 48 //12.清空链表(可以复用):清空各结点数据域,保留指针域,保留头结点 49 void clear_LinkList(struct LinkNode* pHeader); 50 51 //13.销毁链表:头结点和之后所有结点全部删除,一个不留 52 void destroy_LinkList(struct LinkNode* pHeader);
linklist.c代码
1 #include "linklist.h" 2 3 4 5 //01.尾插法:初始化链表,函数返回值是创建好的链表的头结点 6 struct LinkNode* initLinkListTail() 7 { 8 struct LinkNode* pHeader = (struct LinkNode*)malloc(sizeof(struct LinkNode)); 9 if (pHeader == NULL) 10 { 11 return NULL; 12 } 13 14 pHeader->next = NULL; 15 struct LinkNode* pTail = pHeader; 16 int val = -1; 17 while (1) 18 { 19 printf("请初始化链表,输入一个数字,并按Enter键,如果输入-1则代表结束n"); 20 scanf("%d", &val); 21 if (val == -1) 22 { 23 break; 24 } 25 struct LinkNode* newNode = (struct LinkNode*)malloc(sizeof(struct LinkNode)); 26 newNode->num = val; 27 newNode->next = NULL; 28 29 pTail->next = newNode; 30 pTail = newNode; 31 } 32 33 return pHeader; 34 } 35 36 37 //02.头插法:初始化链表,函数返回值是创建好的链表的头结点 38 struct LinkNode* initLinkListHead() 39 { 40 struct LinkNode* pHeader = (struct LinkNode*)malloc(sizeof(struct LinkNode)); 41 if (pHeader == NULL) 42 { 43 return NULL; 44 } 45 46 pHeader->next = NULL; 47 //struct LinkNode* pTail = pHeader; 48 int val = -1; 49 while (1) 50 { 51 printf("请初始化链表,如果输入-1代表结束n"); 52 scanf("%d", &val); 53 if (val == -1) 54 { 55 break; 56 } 57 struct LinkNode* newNode = (struct LinkNode*)malloc(sizeof(struct LinkNode)); 58 newNode->num = val; 59 newNode->next = pHeader->next; 60 61 pHeader->next = newNode; 62 //pTail = newNode; 63 } 64 65 return pHeader; 66 } 67 68 69 //03.遍历链表,并打印输出 70 void foreach_LinkList(struct LinkNode* pHeader) 71 { 72 if (pHeader == NULL) 73 { 74 return; 75 } 76 struct LinkNode* pCurrent = pHeader->next; 77 int i = 0; 78 while (pCurrent != NULL) 79 { 80 printf("链表中第%d个结点的数据域的值为: %dn", i + 1, pCurrent->num); 81 i++; 82 pCurrent = pCurrent->next; 83 } 84 } 85 86 87 //04.获取链表长度,获取链表中元素个数 88 int getElementNums(struct LinkNode* pHeader) 89 { 90 int nums = 0; 91 if (pHeader == NULL) 92 { 93 return 0; 94 } 95 struct LinkNode* pCurrent = pHeader->next; 96 97 while (pCurrent != NULL) 98 { 99 nums++; 100 pCurrent = pCurrent->next; 101 } 102 return nums; 103 } 104 105 106 //05.获取链表中某位置对应的结点的值,假设头结点为第0个结点,pos为链表中第pos个结点 107 int getValueByPos(struct LinkNode* pHeader, int pos) 108 { 109 struct LinkNode* tmpHeader = pHeader; 110 if (pHeader == NULL) 111 { 112 return -1; 113 } 114 115 int lens = getElementNums(pHeader); 116 if (pos <= 0) 117 { 118 printf("位置值不得为负数或0。请输入正确的位置n"); 119 return -1; 120 } 121 if (pos > lens) 122 { 123 printf("位置值不得大于元素中的个数值,现在链表中已有%d个元素。请输入正确的位置n", lens); 124 return -1; 125 } 126 127 int i = 0; 128 while (i < pos) 129 { 130 tmpHeader = tmpHeader->next; 131 i++; 132 } 133 int value = tmpHeader->num; 134 135 return value; 136 } 137 138 139 //06.向链表插入新结点(根据结点值):到现存结点前面或末尾,如果存在该0ldVal值,就创建新节点,赋值为newVal,并插入到oldVal结点前面,如果不存在,则创建一个新结点,并插入到现有链表的尾部,新节点成为链表中最后一个结点。 140 void insert_LinkListByValueBefore(struct LinkNode* pHeader, int oldVal, int newVal) 141 { 142 if (pHeader == NULL) 143 { 144 return; 145 } 146 147 //创建两个临时的节点 148 struct LinkNode* pPrve = pHeader; 149 struct LinkNode* pCurrent = pHeader->next; 150 151 while (pCurrent != NULL) 152 { 153 if (pCurrent->num == oldVal) 154 { 155 break; 156 } 157 //如果没找到对应的位置,辅助指针向后移动 158 pPrve = pCurrent; 159 pCurrent = pCurrent->next; //如果没找到oldVal,则pCurrent = pCurrent->next = NULL; 160 } 161 162 //创建新节点 163 struct LinkNode* newNode = malloc(sizeof(struct LinkNode)); 164 newNode->num = newVal; 165 newNode->next = NULL; 166 167 168 //建立关系 169 newNode->next = pCurrent; //如果没找到,则pCurrent=NULL 170 pPrve->next = newNode; //将新节点挂在pPrve的后面,即如果找到就是oldVal前面的一个结点,如果没找到就是链表最后一个结点。 171 172 } 173 174 175 //07.向链表插入新结点(根据结点值):到现存结点后面或末尾,如果存在该0ldVal值,就创建新节点,赋值为newVal,并插入到oldVal结点前面,如果不存在,则创建一个新结点,并插入到现有链表的尾部,新节点成为链表中最后一个结点。 176 void insert_LinkListByValueAfter(struct LinkNode* pHeader, int oldVal, int newVal) 177 { 178 if (pHeader == NULL) 179 { 180 return; 181 } 182 183 //创建两个临时的节点 184 struct LinkNode * pTail = pHeader; 185 struct LinkNode* pCurrent = pHeader->next; 186 int flag = 0; 187 188 while (pCurrent != NULL) 189 { 190 if (pCurrent->num == oldVal) 191 { 192 flag = 1; 193 break; 194 } 195 //如果没找到对应的位置,辅助指针向后移动 196 pTail = pCurrent; 197 pCurrent = pCurrent->next; //如果没找到oldVal,则pCurrent = pCurrent->next = NULL; 198 } 199 if (flag == 1) 200 { 201 struct LinkNode* newNode = malloc(sizeof(struct LinkNode)); 202 newNode->num = newVal; 203 newNode->next = pCurrent->next; 204 pCurrent->next = newNode; 205 } 206 else { 207 //printf("未找到,失败n"); 208 struct LinkNode* newNode = malloc(sizeof(struct LinkNode)); 209 newNode->num = newVal; 210 newNode->next = NULL; 211 212 //更改指针的指向 213 pTail->next = newNode; 214 //更新新的尾节点的指向 215 pTail = newNode; 216 } 217 } 218 219 220 //08.向链表插入新节点(根据给定位置):位置需要为大于0的数 221 void insert_LinkListByPos(struct LinkNode* pHeader, int pos, int newVal) 222 { 223 int num = getValueByPos(pHeader, pos); 224 225 //printf("此时:pos= %d, num = %dn", pos, num); //此时pos等于i 226 if (num == -1) 227 { 228 printf("当前pos参数输入错误,本次插入失败n"); 229 } 230 else { 231 insert_LinkListByValueBefore(pHeader, num, newVal); 232 } 233 } 234 235 236 //09.删除链表(根据给定结点值):删除链表中某个结点 237 void delete_LinkListByValue(struct LinkNode* pHeader, int delVal) 238 { 239 if (pHeader == NULL) 240 { 241 return; 242 } 243 244 //创建两个辅助指针变量 245 struct LinkNode* pPrev = pHeader; 246 struct LinkNode* pCurrent = pHeader->next; 247 248 while (pCurrent != NULL) 249 { 250 if (pCurrent->num == delVal) 251 { 252 break; 253 } 254 //没有找到数据,辅助指针向后移动 255 pPrev = pCurrent; 256 pCurrent = pCurrent->next; 257 } 258 259 if (pCurrent == NULL) //没有找到用户要删除的数据 260 { 261 return; 262 } 263 264 //更改指针的指向进行删除 265 pPrev->next = pCurrent->next; 266 267 //删除掉待删除的节点 268 free(pCurrent); 269 pCurrent = NULL; 270 } 271 272 273 //10.删除链表(根据给定位置):删除链表中某个结点 274 void delete_LinkListByPos(struct LinkNode* pHeader, int pos) 275 { 276 int num = getValueByPos(pHeader, pos); 277 if (num == -1) 278 { 279 printf("当前pos参数输入错误,本次删除失败n"); 280 } 281 else { 282 delete_LinkListByValue(pHeader, num); 283 } 284 } 285 286 287 //11.反转链表:逆置 -- 我写的 288 void reverse_LinkList1(struct LinkNode* pHeader) 289 { 290 if (pHeader == NULL) 291 { 292 return; 293 } 294 295 struct LinkNode* pCurrent = pHeader->next; 296 297 if (pCurrent == NULL) 298 { 299 printf("空链表,逆置失败。n"); 300 return; 301 } 302 303 pHeader->next = NULL; 304 305 int tmpValue = pCurrent->next; 306 while (pCurrent != NULL) 307 { 308 insert_LinkListByValueBefore(pHeader, tmpValue, pCurrent->num); 309 tmpValue = pCurrent->num; 310 pCurrent = pCurrent->next; 311 } 312 //删除掉待删除的节点 313 free(pCurrent); 314 pCurrent = NULL; 315 } 316 317 //11-1.反转链表:逆置 -- 课程老师给定 318 void reverse_LinkList(struct LinkNode* pHeader) 319 { 320 if (pHeader == NULL) 321 { 322 return; 323 } 324 325 struct LinkNode* pCurrent = pHeader->next; 326 struct LinkNode* pPrev = NULL; 327 struct LinkNode* pNext = NULL; 328 329 while (pCurrent != NULL) 330 { 331 pNext = pCurrent->next; 332 //更改指针指向 333 pCurrent->next = pPrev; 334 335 //移动辅助指针 336 pPrev = pCurrent; 337 pCurrent = pNext; 338 } 339 340 //更新头结点 341 pHeader->next = pPrev; 342 343 } 344 345 //12.清空链表(可以复用):清空各结点数据域,保留指针域,保留头结点 346 void clear_LinkList(struct LinkNode* pHeader) 347 { 348 if (pHeader == NULL) 349 { 350 return; 351 } 352 353 struct LinkNode* pCurrent = pHeader->next; 354 355 while (pCurrent != NULL) 356 { 357 //先保存住下一个节点的位置 358 struct LinkNode* nextNode = pCurrent->next; 359 360 free(pCurrent); 361 362 pCurrent = nextNode; 363 } 364 365 pHeader->next = NULL; 366 } 367 368 369 //13.销毁链表:头结点和之后所有结点全部删除,一个不留 370 void destroy_LinkList(struct LinkNode* pHeader) 371 { 372 if (pHeader == NULL) 373 { 374 return; 375 } 376 377 //先清空链表 378 clear_LinkList(pHeader); 379 380 //再释放头节点 381 382 free(pHeader); 383 pHeader = NULL; 384 }
Demo.c代码
1 #define _CRT_SECURE_NO_WARNINGS 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <string.h> 5 #include "linklist.h" 6 7 //如果是学习之用,可以将注释分布取消,以观察输出的结果,如果是用例的调用需要,可以直接将注释全部删除 8 void test01() 9 { 10 //初始化 11 struct LinkNode* pHeader = initLinkListTail(); //假设输入1,2,3,4,5,-1 ,尾插法 12 //struct LinkNode* pHeader = initLinkListHead(); 13 14 //遍历 15 foreach_LinkList(pHeader); //尾插法:1,2,3,4,5 ;头插法:5,4,3,2,1 16 17 //获取元素个数 18 int lens = getElementNums(pHeader); 19 printf("lens = %dn", lens); //lens = 5 20 printf("间隔行:1*********************************************nn"); 21 22 //向链表插入新结点(根据结点值):到现存结点前面或末尾 23 //insert_LinkListByValueBefore(pHeader,3, 8); //在链表中如果找到对应给定值的结点,就在该节点的前面插入 24 //foreach_LinkList(pHeader);//1,2,8,3,4,5 25 //printf("间隔行:2*********************************************nn"); 26 //insert_LinkListByValueBefore(pHeader, 6, 9); //在链表中如果没有找到给定值的结点,就在最后插入 27 //foreach_LinkList(pHeader);//1,2,8,3,4,5,9 28 //printf("间隔行:3*********************************************nn"); 29 30 //向链表插入新结点(根据结点值):到现存结点后面或末尾,尾插法 31 //insert_LinkListByValueAfter(pHeader, 3, 10);//在链表中如果找到给定值的结点,就在该结点的后面插入 32 //foreach_LinkList(pHeader);//1,2,8,3,10,4,5,9 33 //printf("间隔行:4*********************************************nn"); 34 //insert_LinkListByValueAfter(pHeader, 6, 11);//在链表中如果没有找到给定值的结点,就在最后插入 35 //foreach_LinkList(pHeader);//1,2,8,3,10,4,5,9,11 36 //printf("间隔行:5*********************************************nn"); 37 38 //向链表插入新节点(根据给定位置):位置需要为大于0的数 39 //insert_LinkListByPos(pHeader, 0,12); 40 insert_LinkListByPos(pHeader, 3, 12); 41 //insert_LinkListByPos(pHeader, 5, 12); 42 //insert_LinkListByPos(pHeader, 6, 12); 43 foreach_LinkList(pHeader); //1,2,12,3,4,5 44 printf("间隔行:6*********************************************nn"); 45 46 //删除链表(根据给定结点值):删除链表中某个结点 47 delete_LinkListByValue(pHeader, 12); 48 foreach_LinkList(pHeader); //1,2,3,4,5 49 printf("间隔行:7*********************************************nn"); 50 //delete_LinkListByValue(pHeader, 4); 51 //foreach_LinkList(pHeader); //1,2,12,3,4,5 52 //printf("间隔行:8*********************************************nn"); 53 //delete_LinkListByValue(pHeader, 8); //链表中并没有8,不做删除 54 //foreach_LinkList(pHeader); //1,2,12,3,4,5 55 //printf("间隔行:9********************************************nn"); 56 57 //删除链表(根据给定位置):删除链表中某个结点 58 delete_LinkListByPos(pHeader, 3); 59 foreach_LinkList(pHeader); //1,2,4,5 60 lens = getElementNums(pHeader); 61 printf("lens = %dn", lens); //lens = 4 62 delete_LinkListByPos(pHeader, lens); 63 foreach_LinkList(pHeader); //1,2,4 64 lens = getElementNums(pHeader); 65 printf("lens = %dn", lens); //lens = 3 66 printf("间隔行:10*********************************************nn"); 67 68 69 //反转链表:逆置 70 reverse_LinkList(pHeader); 71 foreach_LinkList(pHeader); //4,2,1 72 lens = getElementNums(pHeader); 73 printf("lens = %dn", lens); //lens = 3 74 printf("间隔行:11*********************************************nn"); 75 76 //清空链表(可以复用):清空各结点数据域,保留指针域,保留头结点 77 clear_LinkList(pHeader); 78 foreach_LinkList(pHeader); //不打印 79 lens = getElementNums(pHeader); 80 printf("lens = %dn", lens); //lens = 0 81 printf("间隔行:12*********************************************nn"); 82 83 //销毁链表:头结点和之后所有结点全部删除,一个不留 84 destroy_LinkList(pHeader); 85 pHeader = NULL; 86 printf("间隔行:13*********************************************nn"); 87 88 89 } 90 91 int main() 92 { 93 test01(); 94 95 printf("n"); 96 system("pause"); 97 return 0; 98 }
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论,欢迎说说您的想法!