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

每个结点只有一个前续结点每个结点只有一个后续结点首结点没有前续结点尾结点没有后续结点专业术语首结点第一个有效结点存放第一个有效数据尾结点最后一个有效结点存放最后一个有效数据头结点在首结点之前的一个结点既不存放有效数据也不存放有效结点的个数加头结点的主要目的是为了方便对链表的操作头结点的数据类型和其他结点的数据类型是一样的头指针指向头结点的指针变量存放了头结点的地址尾指针指向尾结点的指针变量存放了尾结点的地址确定一个链表至少需要哪些参数只需要一个参数头指针因为我们通过头指针就可以推出链表的其他所有信息链表的分类单链表每一个结点只有一个指针域双链表每一个结点有两个指针域循环链表能通过任何一个结点找到其他所有的结点非循环链表优缺点优点空间没有限制插入删除元素很快缺点存取速度很慢算法狭义的算法是与数据存储方式密切相关的广义的算法与数据存储方式无关泛型你用某种技术达到的效果就是不同的存储方式执行的操作是一样的/* file main.c brief 线性结构之链表 author EricsT (EricsT163.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; } } }