2026.3.15数据结构

Link_List.h#pragma once//有效结点结构体设计typedef int ELEMTYPE;typedef struct Node {//数据域ELEMTYPE data;//指针域 存储下一个有效结点的地址struct Node* next;}Node,*PNode;//辅助结点结构体设计//辅助接点和有效节点共享一个结构体设计只用其指针域不用其数据域/*插入类函数总结1.购买好新节点pnewnode2.找到插在哪一个节点的后面这个结点让p指向3.执行插入的通用代码pnewnode-nextp-next;p-nextpnewnode;*//*1.例如获取有效值长度打印查找等等这些只关心自身指向结点是否存在的函数指针p向后遍历时默认从第一个有效节点出发for(Node*pplist-next;p1NULL;pp-next)2.例如插入删除类函数需要关注指向结点的下一个结点是否存在的函数指针p向后遍历时默认从辅助结点位置出发for(Node*Pplist;p-next!NULL;pp-next;3.使用qq-next而不是用q是因为并不是连续存储4.能理解i清楚就用原本的 不清楚就多用几个变量来赋值辅助自己理解*///1.初始化void Init_LinkList(Node* plist);//2.购买新节点Node* BuyNode(ELEMTYPE val);//3.头插bool Insert_Head(Node* plist);//4.尾插bool Insert_Tail(Node* plist, ELEMTYPE val);//5.按位置插(默认pos0为头插)bool Insert_Pos(Node* plist, ELEMTYPE val, int pos);//6.头删bool Delete_Head(Node* plist);//7.尾删bool Delete_Tail(Node* plist);//8.按位置删bool Del_Pos(Node* plist, ELEMTYPE val, int pos);//9.按值删删除这个值的第一次bool Del_Val_First(Node*plist, ELEMTYPE val);//10.按值删删除这个值的所有次bool Del_Val_ALL(Node*plist, ELEMTYPE val);//11.查找Node* Search(Node* plist, ELEMTYPE val);//12.判空bool IsEmpty(Node* plist);//13.获取有效长度int Get_Length(Node* plist);//14.清空void Destory(Node* plist);//15打印.void Show(Node* plist);Link_List.cpp#includeLink_List.h#includestdio.h#includeassert.h#includestdlib.h//1.初始化函数void Init_LinkList(Node* plist) {assert(plist ! NULL);plist-next NULL;//nullptr指针专用}//2.购买新节点Node* BuyNode(ELEMTYPE val) {Node* pnewnode (Node*)malloc(1 * sizeof(Node));if (pnewnode NULL) {exit(EXIT_FAILURE);pnewnode-data val;pnewnode-next NULL;return pnewnode;}}//3.头插bool Insert_Head(Node* plist,ELEMTYPE val) {//1.购买新结点Node*pnewnodeBuyNode(val);//2.找到合适的插入位置//3.通过修该指针域让pnewnode插入注意先修改外来者的指针域pnewnode-next plist-next;plist-next pnewnode;return true;}//4.尾插bool Insert_Tail(Node* plist, ELEMTYPE val) {//1.购买新节点Node*pnewnodeBuyNode(val);//2.找到合适的插入位置Node* p plist;for (; p-next ! NULL; p p-next) {}//3.将新结点和尾结点串起来pnewnode-next p-next;//这一行写不写都行(?)p-next pnewnode;return true;}//5.按位置插入bool Insert_Pos(Node* plist, ELEMTYPE val, int pos) {//0.断言assert(plist ! NULL);assert(pos 0 pos Get_Length(plist));//1.购买新结点Node* pnewnode BuyNode(val);//2.找到合适的插入位置pos几则让指针p从辅助结点出发向后走几步Node* p plist;while (pos!0) {p p-next;pos--;}/*for(int i0;ipos;i){pp-next;*///3.把指针穿起来pnewnode-next p-next;p-next pnewnode;return true;}//6.头删bool Delete_Head(Node* plist) {//assertassert(plist ! NULL);if (plist NULL) {return false;}//1.判空if (IsEmpty(plist)) {return false;}//2.找到待删除结点用q指向Node*q plist-next;//3.找到待删除结点的上家用p指向Node*p plist;//4.跨越指针释放类似死刑犯,先找两边证据再判刑p-next q-next;free(q);q NULL;//防止重复释放q即下面程序多次使用freeqreturn true;}//7.尾删bool Delete_Tail(Node* plist) {assert(plist ! NULL);if (plist NULL) {return false;}//1.判空if (IsEmpty(plist)) {//plist-nextNULLreturn false;}//2.找到待删除结点用q指向Node* q plist;while(q-next ! NULL) {q q-next;}//for(Node*qplist;q-next!NULL;qq-next);//3.找到待删除结点的上家用p指向Node* p plist;while (p-next ! q) {p p-next;}//for(Node*pplist;p-next!q;pp-next);//4.跨越指针释放类似死刑犯,先找两边证据再判刑p-next q-next;free(q);q NULL;return true;}//8.按位置删bool Del_Pos(Node* plist, int pos) {//默认pos0是头删,即posn则指针p从辅助结点出发走pos步并且指针q多走一步走pos1步//0.断言assert(pos 0 pos Get_Length(plist));//1.判空if (IsEmpty(plist)) {//其实真的空的链表的话过不了第一条因为Get_Length(plist返回值就是0当然也有写的必要 因为在release版本下会自动忽视断言return false;}//2.找到待删除结点的上家用指针p指向Node* p plist;for (int i 0; i pos; i) {//用int来放入for循环p p-next;}//3.直接将指针p的next域给到指针q即可Node* q p-next;//4.跨越指向释放p-next q-next;free(q);q NULL;/** 自行书写版本二assert(plist ! NULL);if (plist NULL) {return false;}assert(pos 0 pos Get_Length(plist) );if (IsEmpty(plist)) {return false;}Node* p plist;while (pos ! 1) {p p-next;pos--;}Node*q p-next;p-next q-next;free(q);q NULL;return true;*//*自行书写版本一assert(plist ! NULL);if (plist NULL) {return false;}assert(pos 0 pos Get_Length(plist)-1);if (IsEmpty(plist)) {//plist-nextNULLreturn false;}Node* q plist;while (pos ! 0) {q q-next;pos--;}Node* p plist;for (; p-next ! q; p p-next) {}p-next q-next;free(q);q NULL;return true;*/}//9.按值删删除这个值的第一次bool Del_Val_First(Node* plist, ELEMTYPE val) {//0.assertassert(plist ! NULL);if (plist NULL) {return false;}//1.判空if (IsEmpty(plist)) {return false;}//2.找到待删除结点用指针q指向Node* q Search(plist, val);if (q NULL) {return false;}//判断这里是否为空很重要//3.再找到待删除结点的上家用指针p指向Node* p plist;for (; p-next ! q; p p-next) {}//4.跨越指向释放p-next q-next;free(q);q NULL;return true;/*assert(plist ! NULL);if (plist NULL) {return false;}if (IsEmpty(plist)) {return false;}Node* q Search(plist, val);Node* p plist;for (; p-next ! q; p p-next) {}p-next q-next;free(q);q NULL;return true;*/}//10.按值删删除这个值的所有次bool Del_Val_ALL(Node* plist, ELEMTYPE val) {//0.判空if (IsEmpty(plist)) {return false;}//1.申请两个指针p和qNode* p plist;Node* q plist-next;//2.让指针p从辅助节点出发指针q从第一个有效节点出发//3.进入while循环 循环条件是q不能为空while (q ! NULL) {//4.如果此时q指向的数据域就是要删除的值val则让p把q跳过只让指针q一个人动if (q-data val) {p-next q-next;free(q);q NULL;//此步可以省略q p-next;} //5.如果q指向的数据域不是要指向的val值此时则让两个指针各走一步else {p p-next;q q-next;}}//6.while循环退出代表所有的val值全部被删除完毕return true;/*assert(plist ! NULL);if (plist NULL) {return false;}if (IsEmpty(plist)) {return false;}for (int i 0; i Get_Length(plist); i) {Node* q Search(plist, val);Node* p plist;for (; p-next ! q; p p-next) {}p-next q-next;free(q);q NULL;i--;}return true;*/}//11.查找Node* Search(Node* plist, ELEMTYPE val) {for(Node * p plist-next; p ! NULL; p p-next) {if (p-data val) {return p;}}return NULL;}//12.判空bool IsEmpty(Node* plist) {return plist-next NULL;}//13.获取有效长度int Get_Length(Node* plist) {//这是从辅助结点来看的也可以从第一个结点来看int count 0;for (Node* p plist-next; p ! NULL; p p-next)count;return count;/*int sum 0;Node* p plist;while (p-next ! NULL) {p p-next;sum;}return sum;*/}//14.销毁1:(无限头删)void Destory(Node* plist) {while (!IsEmpty(plist)) {Delete_Head(plist);}}//14.销毁2:不需要辅助结点介入 但是要两个指针配合void Destory(Node* plist) {//assertNode* p plist-next;Node* q NULL;while (p ! NULL) {q p-next;free(p);p q;}plist-next NULL;}//15打印.void Show(Node* plist) {for (Node* p plist-next; p ! NULL; p p-next) {printf(%d , p-data);}printf(\n);}