数据结构——单循环链表及函数实现（C语言）

一、什么是单循环链表1.单循环链表是另一种形式的链式存储结构。2.特点表中最后一个节点的指针域指向头结点整个链表形成一个环。由此从表中任一结点出发均可找到表中其他结点。二、单循环链表结构体设计及函数实现C语言单循环链表的操作和线性链表基本一致差别仅在于算法中的循环条件不是p或p-next是否为空而是它们是否等于头指针。线性链表单链表详见数据结构——线性表的链式存储结构及函数实现C语言https://blog.csdn.net/wy_05136/article/details/159086043?spm1001.2014.3001.5501一单循环链表有效结点/头结点的结构体设计#include stdio.h #include Circle_List.h #include corecrt_malloc.h #include cassert #include alg.h #include vld.h typedef int ELEMTYPE; typedef struct CNode { ELEMTYPE data; //数据域 struct CNode* next; //指针域 存储下一个有效结点的位置 }CNode, * PCNode;注意头结点的结构体通常不去单独设计而是让其和有效结点共享一个结构体设计。但是只使用指针域数据域则直接浪费掉不使用即可二单循环链表的C语言函数实现1.初始化因为此时链表还没有有效结点是空链表只有一个头结点。因此在进行初始化时只需将头结点的指针域指向它自己即可数据域浪费掉。void Insert_LinkList(CNode* plist) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.头结点的数据域浪费掉指针域指向它自己 plist-next plist; //表示当前是空链表没有有效结点 }2.购买新结点CNode* BuyNode(ELEMTYPE val) { //1.调用malloc申请一块大小为sizeof(CNode)的内存用来存放结点 CNode* pnewnode (CNode*)malloc(sizeof(CNode)); if (pnewnode NULL) return NULL; //检查malloc是否成功 //2.结点初始化 pnewnode-data val; //将val赋值给新结点的数据域 pnewnode-next NULL; //将新结点的指针域置空确保它暂时不指向其他结点 return pnewnode; //返回新结点指针 }3.判断单循环链表是否为空若单循环链表为空则说明此时的链表中只有头结点没有有效结点。若头结点的指针域指向它自己则说明此时的链表中只有头结点为空返回true若头结点的指针域不指向它自己则说明此时的链表不为空返回falsebool IsEmpty(CNode* plist) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.判断头结点的指针域是否指向它自己 return plist-next plist; }4.获取单循环链表的长度从第一个有效结点开始往后遍历链表当p等于头指针时说明已经遍历到链表末尾循环结束。int Get_Length(CNode* plist) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.从第一个有效结点开始往后遍历 int count 0; CNode* p plist-next; for (; p ! plist; p p-next) count; return count; }5.查找查找val值出现的位置并返回其地址从第一个有效结点开始依次往后遍历链表对比每个结点的数据域与val值是否相等若找到目标结点则立即返回该结点的地址若遍历完整个链表仍未找到则说明该链表中没有val值查找失败返回NULLCNode* Search(CNode* plist, ELEMTYPE val) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.从第一个有效结点开始往后遍历查找 CNode* p plist-next; for (; p ! plist; p p-next) { if (p-data val) return p; //若找到与val值相等的结点立即返回该结点的指针 } return NULL; //若遍历完整个链表仍未找到与val值相等的结点说明该链表中没有val值返回NULL }6.插入元素1头部插入首先需要先购买一个新结点然后先将新结点的指针域指向第一个结点最后再将头结点的指针域指向新结点注意先修改新结点的指针域再修改头结点的指针域。如果先修改头结点的指针域就会导致第一个结点的地址丢失其内存无法被访问和释放进而造成内存泄漏。bool Insert_head(CNode* plist, ELEMTYPE val) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.购买新结点 CNode* pnewnode BuyNode(val); //2.找到合适的插入位置(相当于要找到插入在谁的后面) // 用指针p指向(头插的话比较特殊肯定是插入辅助结点的后面) CNode* p plist; //可不写 //3.通过修改两个指针域来实现pnewnode结点插入在p结点的后面 // (注意:先修改外来者的指针域不要先修改辅助结点的指针域) pnewnode-next plist-next; plist-next pnewnode; return true; }2尾部插入首先需要先购买一个新结点然后从头结点开始往后遍历链表当p的指针域为头指针时说明此时p指向的就是我要找的最后一个结点最后将新结点的指针域指向头结点并将最后一个结点的指针域指向新结点注意单循环链表的尾结点的指针域需要指向新结点bool Insert_tail(CNode* plist, ELEMTYPE val) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.购买新结点 CNode* pnewnode BuyNode(val); //2.找到合适的插入位置相当于要找到插入在谁的后面用指针p指向 CNode* p plist; for (; p-next ! plist; p p-next); //注意:尾结点的指针域指向的是头结点 //3.通过修改两个指针域来实现pnewnode结点插入在p结点的后面 pnewnode-next plist; p-next pnewnode; return true; }3按位置插入默认pos0代表头部插入首先需要先购买一个新结点新p3然后从头结点出发通过for循环向后走pos步让指针p指向待插入位置的前一个结点p2最后先将新结点新p3的指针域指向待插入位置的后一个结点p3再将待插入位置的前一个结点p2的指针域指向新结点新p3注意先修改新结点新p3的指针域再修改插入位置的前一个结点p2的指针域。如果先修改插入位置的前一个结点p2的指针域就会导致插入位置的后一个结点p3的地址丢失其内存无法被访问和释放进而造成内存泄漏。bool Insert_pos(CNode* plist, ELEMTYPE val, int pos) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.检查是否是有效插入 assert(pos 0 pos Get_Length(plist)); //2.购买新结点 CNode* pnewnode BuyNode(val); //3.找到合适的插入位置相当于要找到插入在谁的后面用指针p指向 CNode* p plist; for (int i 0; i pos; i) p p-next; //4.通过修改两个指针域来实现pnewnode结点插入在p结点的后面(注意:先修改新结点的指针域) pnewnode-next p-next; p-next pnewnode; return true; }7.删除元素1头部删除让头结点跨越待删除结点直接连接到原第二个有效结点即p-nextq-next然后释放待删除结点的内存bool Delete_head(CNode* plist) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.判空:若链表为空则没有可删除元素返回false if (IsEmpty(plist)) return false; //2.找到待删除结点用指针q指向 CNode* q plist-next; //3.找到待删除结点的上一个结点用指针p指向 CNode* p plist; //4.跨越指针(指的是p结点把q结点跨过去)释放待删除结点的内存 p-next q-next; free(q); q NULL; //避免野指针 return true; }2尾部删除首先从头结点开始往后遍历链表当q的指针域指向头结点时说明此时q指向的就是最后一个结点即待删除结点然后从头结点开始再次往后遍历链表当p的指针域为q时说明此时p指向的就是待删除结点的前一个结点最后将p-next指向q-next即头指针使p成为新的尾节点然后释放待删除结点的内存。bool Delete_tail(CNode* plist) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.判空:若链表为空则没有可删除元素返回false if (IsEmpty(plist)) return false; //2.找到待删除结点用指针q指向 CNode* q plist; for (; q-next ! plist; q q-next); //3.找到待删除结点的上一个结点用指针p指向 CNode* p plist; for (; p-next ! q; p p-next); //4.跨越指针(指的是p结点把q结点跨过去)释放待删除结点的内存 p-next plist; free(q); q NULL; //避免野指针 return true; }3按位置删除默认pos0代表头部删除首先从头结点出发通过for循环向后走pos1步让指针p指向待删除结点然后从头结点开始再次往后遍历链表当p的指针域为q时说明此时p指向的就是待删除结点的前一个结点最后将p-next指向q-next即p-nextq-next然后释放待删除结点的内存。bool Delete_pos(CNode* plist, int pos) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.检查是否是有效删除 assert(pos 0 pos Get_Length(plist)); //2.判空:若链表为空则没有可删除元素返回false if (IsEmpty(plist)) return false; //3.找到待删除结点用指针q指向 CNode* q plist; for (int i 0; i pos; i) q q-next; //4.找到待删除结点的上家用指针p指向 CNode* p plist; for (; p-next ! q; p p-next); //5.跨越指针(指的是p结点把q结点跨过去)释放待删除结点的内存 p-next q-next; free(q); q NULL; //避免野指针 return true; }4按值删只删除这个值第一次出现的位置首先调用Search函数查找值为val的第一个结点即为待删除结点用指针q指向然后从头结点出发通过for循环让指针p指向待删除结点的前一个结点最后将p-next指向q-next即p-nextq-next然后释放待删除结点的内存bool Delete_val_First(CNode* plist, ELEMTYPE val) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.判空:若链表为空则没有可删除元素返回false if (IsEmpty(plist)) return false; //2.找到待删除结点用指针q指向 CNode* q Search(plist, val); if (NULL q) return false; //未找到与val值相等的结点 //3.找到待删除结点的上一个结点用指针p指向 CNode* p plist; for (; p-next ! q; p p-next); //4.跨越指针(指的是p结点把q结点跨过去)释放待删除结点的内存 p-next q-next; free(q); q NULL; //避免野指针 return true; }5按值删删除这个值出现的所有位置首先让p指向头结点作为前驱指针q指向第一个有效结点作为当前遍历指针然后进入while循环遍历整个链表遍历过程中若当前结点q的数据域等于val则将p的指针域指向q的后继结点以跨越待删结点释放q所指向的结点的内存并将q重置为p的后继结点若数据域不匹配则p和q同步向后移动继续遍历。整个过程仅需一次遍历即可完成所有匹配结点的删除保证了链表结构的完整性和操作的高效性。bool Delete_val_All(CNode* plist, ELEMTYPE val) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.判空:若链表为空则没有可删除元素返回false if (IsEmpty(plist)) return false; //2.申请两个指针p和q CNode* q plist-next; //让指针q从第一个有效结点位置出发 CNode* p plist; //让指针p从辅助结点出发 //3.进入while循环(循环条件是q不能等于头指针) while (q ! plist) { //4.如果此时q指向的结点的数据域是val值则跨越指针(指的是p结点把q结点跨过去) // 释放待删除结点的内存然后只让指针q往后挪动一下 if (q-data val) { p-next q-next; free(q); q NULL; //避免野指针 q p-next; } //5.如果此时q指向的结点的数据域不是val值则直接让两个指针p和q都往后挪动一下 else { p p-next; q q-next; } } //6.当while退出,代表所有val值全部删除完毕 return true; }8.销毁链表1方法一无限头删反复调用头部删除函数逐个移除链表的第一个数据节点直到链表变为空。void Destroy1(CNode* plist) { //0.断言 assert(plist ! NULL); while (!IsEmpty(plist)) { Delete_head(plist); } plist-next plist; }2方法二不需要辅助结点的介入但是需要两个指针相互配合利用while循环每次先让p保存q的后继结点地址再释放p所指结点的内存最后将p重置为q继续遍历下一个节点直到所有数据结点都被释放最后将头结点的指针域置为空。这种方式仅需一次遍历即可完成所有节点内存的释放效率更高且直接操作底层内存释放逻辑避免了重复调用删除函数的开销保证了内存安全无泄漏。void Destroy2(CNode* plist) { //0.断言 assert(plist ! NULL); CNode* p plist-next; CNode* q NULL; while (p ! plist) { q p-next; free(p); p q; } plist-next plist; }9.打印链表从第一个有效结点开始向后遍历链表依次打印当p等于头指针时说明已经遍历到链表末尾打印结束。void Show(CNode* plist) { //0.断言:检查传入的指针是否为空 assert(plist ! NULL); //1.从第一个有效结点开始向后遍历链表依次打印 CNode* p plist-next; for (; p ! plist; p p-next) printf(%d , p-data); printf(\n); }10.主函数测试int main() { CNode head; //初始化 Insert_LinkList(head); //插入函数(其中包含购买新结点函数) Insert_head(head, 1); Insert_head(head, 2); Insert_head(head, 3); Insert_head(head, 1); Insert_head(head, 2); Insert_head(head, 3); printf(头部插入:); Show(head); Insert_tail(head, 4); printf(尾部插入:); Show(head); Insert_pos(head, 5, 2); printf(按位置插入:); Show(head); Insert_pos(head, 6, 0); printf(按位置插入(头部插入):); Show(head); Insert_pos(head, 7, Get_Length(head)); printf(按位置插入(尾部插入):); Show(head); //删除函数 Delete_head(head); printf(头部删除:); Show(head); Delete_tail(head); printf(尾部删除:); Show(head); Delete_pos(head, 2); printf(按位置删除:); Show(head); Delete_pos(head, 0); printf(按位置删除(头部删除):); Show(head); Delete_pos(head, Get_Length(head) - 1); printf(按位置删除(尾部删除):); Show(head); Delete_val_First(head, 1); //其中包含查找函数 printf(按值删除(删除首次出现的位置):); Show(head); Delete_val_All(head, 2); printf(按值删除(删除所有出现的位置):); Show(head); printf(\n); //获取单链表的长度 printf(length%d\n, Get_Length(head)); printf(\n); //销毁链表判空函数 Destroy1(head); if (IsEmpty(head)) printf(链表为空\n); Insert_head(head, 1); Insert_head(head, 2); Insert_head(head, 3); Show(head); Destroy2(head); if (IsEmpty(head)) printf(链表为空\n); return 0; }