线性结构之链表[基于郝斌课程]

每个结点只有一个前续结点

每个结点只有一个后续结点

首结点没有前续结点

尾结点没有后续结点

专业术语：

首结点：第一个有效结点，存放第一个有效数据

尾结点：最后一个有效结点，存放最后一个有效数据

头结点：在首结点之前的一个结点，既不存放有效数据，也不存放有效结点的个数，加头结点的主要目的是为了方便对链表的操作，头结点的数据类型和其他结点的数据类型是一样的

头指针：指向头结点的指针变量，存放了头结点的地址

尾指针：指向尾结点的指针变量，存放了尾结点的地址

确定一个链表至少需要哪些参数：

只需要一个参数：头指针

因为我们通过头指针就可以推出链表的其他所有信息

链表的分类：

单链表：每一个结点只有一个指针域

双链表：每一个结点有两个指针域

循环链表：能通过任何一个结点找到其他所有的结点

非循环链表

优缺点：

优点：

空间没有限制

插入删除元素很快

缺点：

存取速度很慢

算法：

狭义的算法是与数据存储方式密切相关的

广义的算法与数据存储方式无关

泛型：你用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的

/* @file main.c @brief 线性结构之链表 @author EricsT (EricsT@163.com) @version v1.0.0 @date 2025-09-21 @history 2025-09-21 EricsT - 新建文件 2025-09-22 EricsT - 新增 CreateList\TraverseList 2025-09-22 EricsT - 新增 isEmptyList\GetLenthList\InsertList\DeleteList\SortList */ #include <stdio.h> #include <malloc.h> #include <stdlib.h> typedef struct Node { int data;//数据域 Node* ptrNext;//指针域 }* PtrNode, NODE;//NODE 相当于 Node NODE//ptrNode 相当于 Node* ptrNode PtrNode CreateList();//创建链表 void TraverseList(const PtrNode ptrNode);//遍历链表 bool isEmptyList(const PtrNode ptrNode);//是否为空 int GetLenthList(const PtrNode ptrNode);//获取链表长度 bool InsertList(PtrNode ptrNode, int insertPos, int insertData);//插入结点 bool DeleteList(PtrNode ptrNode, int deletePos);//删除结点 void SortList(PtrNode ptrNode);//排序 int main(void) { PtrNode ptrNode = NULL; ptrNode = CreateList(); TraverseList(ptrNode); if (isEmptyList(ptrNode)) printf("链表为空\n"); else printf("链表非空\n"); printf("链表长度为：%d\n", GetLenthList(ptrNode)); int insertPose; printf("请输入插入位置"); scanf("%d", &insertPose); int insertValue; printf("请输入插入数值"); scanf("%d", &insertValue); InsertList(ptrNode, insertPose, insertValue); TraverseList(ptrNode); int deletePose; printf("请输入删除位置"); scanf("%d", &deletePose); DeleteList(ptrNode, deletePose); TraverseList(ptrNode); SortList(ptrNode); TraverseList(ptrNode); return 0; } PtrNode CreateList() { int len; printf("请输入结点个数len = "); scanf("%d", &len); int addr = 0; PtrNode ptrNodeFirst = (PtrNode)malloc(sizeof(NODE));//头结点 if (NULL == ptrNodeFirst) { printf("分配失败\n"); exit(-1); } PtrNode ptrNodeLast = ptrNodeFirst;//尾结点 ptrNodeLast->ptrNext = NULL; for (int i = 0; i < len; ++i) { PtrNode ptrNode = (PtrNode)malloc(sizeof(PtrNode));//新的尾结点 if (NULL == ptrNodeFirst) { printf("分配失败\n"); exit(-1); } ptrNodeLast->ptrNext = ptrNode;//新的尾结点挂在旧的尾结点后面 printf("请输入%d个结点的数值", i + 1); scanf("%d", &ptrNode->data); ptrNode->ptrNext = NULL; ptrNodeLast = ptrNode;//更新尾结点 } return ptrNodeFirst; } void TraverseList(const PtrNode ptrNode/*头结点*/) { PtrNode ptrNode_ = ptrNode->ptrNext;//首节点 while (NULL != ptrNode_)//结点为空，则是尾结点 { printf("%d ", ptrNode_->data); ptrNode_ = ptrNode_->ptrNext;//下一结点 } printf("\n"); } bool isEmptyList(const PtrNode ptrNode) { PtrNode ptrNode_ = ptrNode->ptrNext;//首节点 if (NULL == ptrNode->ptrNext) return true; return false; } int GetLenthList(const PtrNode ptrNode) { int iLen = 0; PtrNode ptrNode_ = ptrNode->ptrNext;//首节点 while (NULL != ptrNode_)//结点为空，则是尾结点 { ptrNode_ = ptrNode_->ptrNext;//下一结点 iLen++; } return iLen; } bool InsertList(PtrNode ptrNode, int insertPos, int insertData) { if (insertPos < 1) return false; if (insertPos > (GetLenthList(ptrNode) + 1)) return false; PtrNode ptrNodeInsert = (PtrNode)malloc(sizeof(Node)); ptrNodeInsert->data = insertData; PtrNode ptrNodeCur = ptrNode; for (int i = 1; i < insertPos; ++i) ptrNodeCur = ptrNodeCur->ptrNext; ptrNodeInsert->ptrNext = ptrNodeCur->ptrNext; ptrNodeCur->ptrNext = ptrNodeInsert; return true; } bool DeleteList(PtrNode ptrNode, int deletePos) { if (deletePos < 1) return false; if (deletePos > GetLenthList(ptrNode)) return false; PtrNode ptrNodeCur = ptrNode; for (int i = 1; i < deletePos; ++i) ptrNodeCur = ptrNodeCur->ptrNext; ptrNodeCur->ptrNext = ptrNodeCur->ptrNext->ptrNext; return true; } void SortList(PtrNode ptrNode) { int iLen = GetLenthList(ptrNode); PtrNode ptrNodeCur = ptrNode;//头结点 for (int i = 0; i < iLen; ++i) { ptrNodeCur = ptrNodeCur->ptrNext; PtrNode ptrNodeNext = ptrNodeCur->ptrNext; while (NULL != ptrNodeNext) { if (ptrNodeCur->data > ptrNodeNext->data) { int temp = ptrNodeCur->data; ptrNodeCur->data = ptrNodeNext->data; ptrNodeNext->data = temp; } ptrNodeNext = ptrNodeNext->ptrNext; } } }