链表|数据结构|C语言深入学习
什么是链表
离散，就是“分离的、散开的”
链表是什么样子的：
有限个节点离散分配
彼此间通过指针相连
除了首尾节点，每个节点都只有一个前驱节点和一个后继节点
首节点没有前驱结点，尾节点没有后继节点
基本概念术语：
首节点：第一个存放有效数据的节点；
尾节点：最后一个存放有效数据的节点
头节点是首节点前面的那个节点。头结点里面不存放数据，有效数据是从首节点开始存的
头结点存在的目的是什么？
对链表进行操作的时候，在前面加上一个没有实际含义的头节点可以方便对链表进行操作
头指针：指向头节点的指针变量，存放了头节点的地址
尾指针：指向尾节点的指针变量，存放了尾节点的地址
链表中所有的节点的数据类型都是一样的，包括头结点
确定一个链表最少需要几个参数
只需要一个参数：头指针
通过头指针可以得到一个链表的其他所有信息
链表节点的数据类型怎么表示
每一个节点都有数据域和指针域两部分
尾节点除外的每一个节点的指针域指向了下一个节点的[节点整体]
这个[节点整体]的数据类型跟他的前一个节点的数据类型是完全一样的
也就是说，一个结构体变量中的某一成员指向了跟它整体（这个结构体变量）一样的数据类型
因为第一个节点的指针域指向了第二个节点整体，而第二个节点整体和第一个节点整体的数据类型是一模一样的
说的抽象一点，就是：某一结构体的变量中的一个成员指向了和它本身的数据类型一样的另一个变量
| typedef?struct?Node?{ int?data;//数据域 struct?Node* pNext;//指针域 ? }NODE,*PNODE; //NODE是struct Node类型，PNODE是struct Node*类型 /* 指针域指向了和它整体本身的数据类型一模一样的另一个变量的整体 指针域存放的是下一个节点的地址，所以应该是【下一个节点的数据类型*】 类型的指针变量 下一个节点跟这个节点本身的数据类型一样，都是struct Node类型 所以，指针域的指针变量的类型是struct Node*类型 */ |
链表的分类
·单链表
·双链表
每一个节点都有两个指针域
·循环链表
能通过任何一个节点找到其他所有的节点
·非循环链表
非循环单链表的创建和遍历
| #include<stdio.h> #include<malloc.h> #include<stdlib.h> typedef?struct?Node?{ int?data;//数据域 struct?Node* pNext;//指针域 ? }NODE, * PNODE; //NODE是struct Node类型，PNODE是struct Node*类型 /* ??指针域指向了和它整体本身的数据类型一模一样的另一个变量的整体 ??指针域存放的是下一个节点的地址，所以应该是【下一个节点的数据类型*】 类型的指针变量 ??下一个节点跟这个节点本身的数据类型一样，都是struct Node类型 ??所以，指针域的指针变量的类型是struct Node*类型 ?*/ PNODE?createList(); void?traverseList(PNODE?pHead); int?main() { PNODE?pHead = NULL; //等价于struct Node* PHead = NULL; pHead = createList();//创建一个非循环单链表，并将链表的头结点的地址赋给pHead traverseList(pHead); return?0; } PNODE?createList() { int?len;//用来存放链表有效节点的个数 int?val;//用来临时存放用户输入的节点的个数 /* ??pHead是一个头指针，pHead指向了头结点 ??这个头结点不存放有效数据*/ PNODE?pHead = (PNODE)malloc(sizeof(NODE)); if?(pHead == NULL) { printf("内存分配失败，程序终止\n"); exit(-1); } PNODE?pTail = pHead; pTail->pNext = NULL; printf("请输入需要生成的链表节点的个数："); scanf("%d", &len); for?(int?i = 0; i < len; i++) { printf("请输入需要生成的链表节点值："); scanf("%d", &val); PNODE?pNew = (PNODE)malloc(sizeof(NODE)); if?(pHead == NULL) { printf("内存分配失败，程序终止\n"); exit(-1); } pNew->data = val; pTail->pNext = pNew; pNew->pNext = NULL; pTail = pNew; } /* ??循环了len次，每一次都创建并分配了一个新节点，用pNew（指针变量）表示这个新节点 ??创建了新节点后，为新节点数据域赋值 ??创建了一个pTail指针变量，链表中没有有效节点之前pTail指向头结点（此时，头指针pHead和pTail都指向头结点） ??创建了一个新节点之后，为新节点赋值数据域，pNew->data = val ??pTail指针变量指向的节点（最开始是头结点，之后是链表中最后一个节点）的指针域存上新节点的地址pTail->pNext = pNew ??此时pTail指针变量指向的是倒数第二个节点 ??将新茶入的节点的指针域置空pNew->pNext = NULL ??将pTail指针变量指到最后一个新插入的节点上，确保下一次插入新节点之前pTail总是指到当前链表最后一个节点上 ??pTail = pNew*/ return?pHead; } void?traverseList(PNODE?pHead) { PNODE?p = pHead->pNext; while?(NULL?!= p) { printf("%d ", p->data); p = p->pNext; } printf("\n"); } |
非循环单链表插入节点
非循环单链表删除节点
链表排序算法
链表冒泡排序：
| void?sortList(PNODE pHead) { if?(isEmpty(pHead)) { printf("链表为空，无法排序"); exit(-1); } PNODE p, q; int?i, j; int?n = numNode(pHead);//求链表有效节点个数 for?(i = 0, p = pHead->pNext; i < n - 1; i++, p = p->pNext) { for?(j = 0, q = pHead->pNext; j < n - 1 - i; j++, q = q->pNext) { if?(q->data > q->pNext->data) { int?t = q->data; q->data = q->pNext->data; q->pNext->data = t; } } } } |
由以下数组冒泡排序改编：
| //数组冒泡排序： for?(int?i = 0; i < n - 1; i++) { for?(int?j = 0; j < n - 1 - i; j++) { if?(a[j] < a[j + 1]) { int?t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } } |
链表完整代码
| #include<stdio.h> #include<malloc.h> #include<stdlib.h> typedef?struct?Node?{ int?data;//数据域 struct?Node* pNext;//指针域 ? }NODE, * PNODE; //NODE是struct Node类型，PNODE是struct Node*类型 /* ??指针域指向了和它整体本身的数据类型一模一样的另一个变量的整体 ??指针域存放的是下一个节点的地址，所以应该是【下一个节点的数据类型*】 类型的指针变量 ??下一个节点跟这个节点本身的数据类型一样，都是struct Node类型 ??所以，指针域的指针变量的类型是struct Node*类型 ?*/ PNODE?createList();//创建 void?traverseList(PNODE?pHead);//遍历 bool?isEmpty(PNODE?pHead);//判空 int?numNode(PNODE?pHead);//求链表有效节点个数 void?sortList(PNODE?pHead);//排序 bool?insertNode(PNODE?pHead, int?pos, int?val);//插入节点 bool?deleteNode(PNODE?pHead, int?pos);//删除节点 int?main() { PNODE?pHead = NULL; //等价于struct Node* PHead = NULL; pHead = createList();//创建一个非循环单链表，并将链表的头结点的地址赋给pHead traverseList(pHead);//遍历 if?(isEmpty(pHead)) printf("链表为空"); else printf("链表非空"); //求链表有效节点的个数 printf("链表中有效节点的个数为%d\n", numNode(pHead)); sortList(pHead); traverseList(pHead);//遍历 insertNode(pHead, 1, 125); traverseList(pHead);//遍历 deleteNode(pHead, 1); traverseList(pHead);//遍历 return?0; } PNODE?createList() { int?len;//用来存放链表有效节点的个数 int?val;//用来临时存放用户输入的节点的个数 /* ??pHead是一个头指针，pHead指向了头结点 ??这个头结点不存放有效数据*/ PNODE?pHead = (PNODE)malloc(sizeof(NODE)); if?(pHead == NULL) { printf("内存分配失败，程序终止\n"); exit(-1); } PNODE?pTail = pHead; pTail->pNext = NULL; printf("请输入需要生成的链表节点的个数："); scanf("%d", &len); for?(int?i = 0; i < len; i++) { printf("请输入需要生成的链表节点值："); scanf("%d", &val); PNODE?pNew = (PNODE)malloc(sizeof(NODE)); if?(pHead == NULL) { printf("内存分配失败，程序终止\n"); exit(-1); } pNew->data = val; pTail->pNext = pNew; pNew->pNext = NULL; pTail = pNew; } /* ??循环了len次，每一次都创建并分配了一个新节点，用pNew（指针变量）表示这个新节点 ??创建了新节点后，为新节点数据域赋值 ??创建了一个pTail指针变量，链表中没有有效节点之前pTail指向头结点（此时，头指针pHead和pTail都指向头结点） ??创建了一个新节点之后，为新节点赋值数据域，pNew->data = val ??pTail指针变量指向的节点（最开始是头结点，之后是链表中最后一个节点）的指针域存上新节点的地址pTail->pNext = pNew ??此时pTail指针变量指向的是倒数第二个节点 ??将新茶入的节点的指针域置空pNew->pNext = NULL ??将pTail指针变量指到最后一个新插入的节点上，确保下一次插入新节点之前pTail总是指到当前链表最后一个节点上 ??pTail = pNew*/ return?pHead; } void?traverseList(PNODE?pHead) { PNODE?p = pHead->pNext; while?(NULL?!= p) { printf("%d ", p->data); p = p->pNext; } printf("\n"); } bool?isEmpty(PNODE?pHead) { if?(pHead->pNext == NULL) return?true; else return?false; } int?numNode(PNODE?pHead) { PNODE?p = pHead->pNext; int?num = 0; while?(p != NULL) { num++; p = p->pNext; } return?num; } void?sortList(PNODE?pHead) { if?(isEmpty(pHead)) { printf("链表为空，无法排序"); exit(-1); } PNODE?p, q; int?i, j; int?n = numNode(pHead);//求链表有效节点个数 for?(i = 0, p = pHead->pNext; i < n - 1; i++, p = p->pNext) { for?(j = 0, q = pHead->pNext; j < n - 1 - i; j++, q = q->pNext) { if?(q->data > q->pNext->data) { int?t = q->data; q->data = q->pNext->data; q->pNext->data = t; } } } } bool?insertNode(PNODE?pHead, int?pos, int?val) { PNODE?p = pHead; int?i = 0; while?(p && i < pos) { p = p->pNext; i++; } if?(p == NULL?|| i > pos) { return?false; } PNODE?pNew = (PNODE)malloc(sizeof(NODE)); if?(pNew == NULL) { printf("动态内存分配失败"); return?false; } pNew->data = val; pNew->pNext = p->pNext; p->pNext = pNew; return?true; } bool?deleteNode(PNODE?pHead, int?pos) { int?i = 0; PNODE?p = pHead; while?(p && i < pos) { p = p->pNext; i++; } if?(!p || i > pos) return?false; PNODE?q = (PNODE)malloc(sizeof(NODE)); q = p->pNext; p->pNext = p->pNext->pNext; free(q); return?true; } |
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
- Python教程
- 深入理解 MySQL 中的 HAVING 关键字和聚合函数
- Qt之QChar编码（1）
- MyBatis入门基础篇
- 用Python脚本实现FFmpeg批量转换
- 如何精选WordPress插件
- 网络层的异构网络互连
- UML相关问题及答案（2024）
- jmeter解决返回unicode编辑
- 网络安全面试题（附答案）
- Spring IOC—基于注解配置和管理Bean 万字详解（通俗易懂）
- 【教3妹学编程-算法题】找到最大周长的多边形
- 【MySQL】ANY函数 的巧用（筛选字段 = ANY(语句)）
- QScrollBar滑块颜色通过setStyleSheet设置时未生效现象
- Web后端开发：事务管理