C语言数据结构2-单向链表实现

数据结构链表链表是数据结构中最常用的线性结构许多非线性结构也都是链表节点魔改后形成的非链式结构。链表的分类按有无头节点分不含头节点的链表这种链表存在操作不统一的问题操作第一个节点和后面的第i个节点代码不同代码简洁性不佳含有头节点的链表操作统一易于编码按链表结构分单向链表每个节点只有一个指针指向自己的后继双向链表每个节点有两个指针一个指向自己的前驱一个指向自己的后继循环链表尾节点指针指向头节点单向循环链表每个节点只有一个指针指向自己的后继双向循环链表每个节点有两个指针一个指向自己的前驱一个指向自己的特殊操作链表栈像弹夹先压入的子弹元素后射出出栈队列像水管先进入队列的元素先出队列一般队列队列一侧只能插入另一侧只能弹出双向队列两侧都可以插入或者删除单向链表的定义与功能声明头文件如下typedef int E;// 对节点内数据起别名如果要其他类型可以修改 typedef struct LinkNode{ E element; // 链表节点元素 struct LinkNode * next; //指向自己后继的指针 }linkNode; typedef struct LinkNode * Node ;// 对链表指针起别名 ​ void InitLinkList(Node Head);// 对链表进行初始化定义头节点初始参数 _Bool insertLinkList(Node Head,E element,int index);//插入节点 _Bool deleteLinkList(Node Head,int index);//删除元素 E GetElementByIndex(Node Head,int index);//根据元素在链表中的位置获取节点的元素值 Node GetPointByElement(Node Head,E element);//根据元素取值寻找对应节点 void printLinkList(Node head);//打印整个链表 int GetLinkListSize(Node head);//获取链表长度(不包括头节点)功能函数初始化函数插入函数删除函数按索引获取节点元素值按元素值获取节点指针打印链表获取链表长度函数的具体实现函数初始化void InitLinkList(Node Head){ if(Head NULL){ printf([ERROR]:undefined LinkList\n ); return; }//判断是否传入无效地址 Head-next NULL;//将头节点指针置空 printf([LOG]:This new LinkList s Adress is %p\n,Head);//打印信息 }插入函数插入的核心就是找到待插入位置的前驱节点将待插入节点的后继置为当前该位置的地址将前驱节点的指针置为待插入节点的地址同时注意插入索引的合法性[1.size1 ]_Bool insertLinkList(Node Head,E element,int index){ if(HeadNULL){ printf([LOG]: undefined LinkList\n); return 0; }//判断传入指针是否为空指针 if(index1){ printf([ERROR]:Wrong index\n); return 0; }//判断插入位置合法性正常的插入位置是1~size1,也就是第一个位置头节点后的第一个到最后一个节点之后 while(--index){ if(Head-next NULL) return 0;//限制只能插入到最后一个节点的后面 Head Head-next;//移动指针 } Node node malloc(sizeof(struct LinkNode)); // malloc是给指针分配内存 node-element element;//给节点元素赋值 node-next Head-next;//修改待插入节点的后继指针为为当前指针的后继 Head-next node;//修改当前指针的后继为待插入节点 printf([LOG]:insert success\n[INFO]:Front Node address %p,Target Node address %p\n,Head,node);//打印信息 return 1; }删除函数删除的核心就是找到待插入位置的前驱节点先记录待删除节点的指针将前驱节点的后继置为待删除节点的后继最后释放待删除节点的内存空间_Bool deleteLinkList(Node Head,int index){ if(HeadNULL){ printf([ERROR]:undefined LinkList\n); return 0; }//判断指针是否为空 if(index1){ printf([ERROR]:Wrong index\n); return 0; }//判断插入位置合法性 Node DeleteNode;//设置指针变量准备记录待删除节点的指针 while(--index){ if(Head-next NULL){ printf([ERROR]:Wrong index\n); return 0; }//寻找待删除节点的前驱 Head Head-next;//移动指针位置 } DeleteNode Head-next;//记录待删除指针的地址 Head-next Head-next-next;//重置待删除节点的前驱节点的指针 printf([LOG]:Delete success,Node Adress %p,Node element %d\n ,DeleteNode,DeleteNode-element); free(DeleteNode);//释放节点的地址空间 return 1; }打印函数void printLinkList(Node head){ if(headNULL){ printf([ERROR]: undefined LinkList\n); return ; } while(head-next! NULL){ head head-next; printf([%d,%p]-,head-element,head-next); } return; }获取链表长度int GetLinkListSize(Node Head){ if(Head NULL){ printf([ERROR]:undefined LinkList\n); return 0; }//指针判空 int Size 0; while(Head-next){ Head Head-next; Size; }//遍历整个链表并更新size变量 return Size; }按位置查找E GetElementByIndex(Node Head,int index){ if(HeadNULL){ printf([ERROR]:undefined LinkList\n); return -1; }//指针判空 if(index1||indexGetLinkListSize(Head)){ printf([ERROR]:Wrong index\n); return -1; }//查找位置合法性判断 while(index--){ Head Head-next; }//移动指针 return Head-element;//返回对应索引的元素 }按值查找节点Node GetPointByElement(Node Head,E element){ if(HeadNULL){ printf([ERROR]:undefined LinkList\n); return NULL; }//指针判空 while(Head-next!NULL){ Head Head-next;//移动指针 if(Head-element element){//和每个节点的元素做匹配 printf([LOG]:Find success\n[INFO]: Node Address %p,Node element %d\n,Head,Head-element); return Head;//找到立刻返回 } } printf([LOG]:this element not in the LinkList\n); return NULL; }功能测试测试代码#include stdio.h #include stdlib.h #include LinkNode.h int main() { printf( 链表完整功能测试 \n\n); ​ // 创建头结点 linkNode Head; Node head Head; InitLinkList(head); ​ printf(\n 1. 插入测试 \n); ​ printf(\n--- 在位置1插入10 ---\n); insertLinkList(head, 10, 1); printLinkList(head); ​ printf(\n--- 在位置2插入20 ---\n); insertLinkList(head, 20, 2); printLinkList(head); ​ printf(\n--- 在位置2插入30 ---\n); insertLinkList(head, 30, 2); printLinkList(head); ​ printf(\n--- 在位置1插入5 ---\n); insertLinkList(head, 5, 1); printLinkList(head); ​ printf(\n--- 在位置4插入25 ---\n); insertLinkList(head, 25, 4); printLinkList(head); ​ printf(\n--- 在位置1插入100 ---\n); insertLinkList(head, 100, 1); printLinkList(head); ​ printf(\n 2. 获取大小 \n); int size GetLinkListSize(head); printf(当前链表大小: %d\n, size); ​ printf(\n 3. 按索引获取元素 \n); for(int i 1; i size; i) { E elem GetElementByIndex(head, i); printf(位置 %d 的元素: %d\n, i, elem); } ​ printf(\n--- 测试无效索引 ---\n); printf(位置0: %d\n, GetElementByIndex(head, 0)); printf(位置100: %d\n, GetElementByIndex(head, 100)); ​ printf(\n 4. 按元素获取节点指针 \n); ​ printf(\n--- 查找存在的元素25 ---\n); Node p GetPointByElement(head, 25); if(p ! NULL) { printf(找到节点值为: %d\n, p-element); } ​ printf(\n--- 查找存在的元素5 ---\n); p GetPointByElement(head, 5); if(p ! NULL) { printf(找到节点值为: %d\n, p-element); } ​ printf(\n--- 查找不存在的元素999 ---\n); p GetPointByElement(head, 999); if(p NULL) { printf(未找到节点\n); } ​ printf(\n 5. 删除测试 \n); ​ printf(\n--- 删除位置3 ---\n); deleteLinkList(head, 3); printLinkList(head); ​ printf(\n--- 删除位置1 ---\n); deleteLinkList(head, 1); printLinkList(head); ​ printf(\n--- 删除最后位置 ---\n); int currentSize GetLinkListSize(head); deleteLinkList(head, currentSize); printLinkList(head); ​ printf(\n--- 删除位置2 ---\n); deleteLinkList(head, 2); printLinkList(head); ​ printf(\n--- 测试无效删除 ---\n); deleteLinkList(head, 0); deleteLinkList(head, 10); printLinkList(head); ​ printf(\n 6. 边界测试 \n); printf(当前链表: ); printLinkList(head); printf(当前大小: %d\n, GetLinkListSize(head)); ​ printf(\n--- 向空链表插入测试 ---\n); linkNode EmptyHead; Node emptyHead EmptyHead; InitLinkList(emptyHead); printf(空链表大小: %d\n, GetLinkListSize(emptyHead)); printf(插入元素999到位置1:\n); insertLinkList(emptyHead, 999, 1); printLinkList(emptyHead); ​ printf(\n--- 从单节点链表删除 ---\n); deleteLinkList(emptyHead, 1); printLinkList(emptyHead); ​ printf(\n 7. 压力测试 \n); linkNode StressHead; Node stressHead StressHead; InitLinkList(stressHead); ​ printf(\n--- 插入100个元素 ---\n); for(int i 1; i 100; i) { insertLinkList(stressHead, i*10, i); if(i % 20 0) { printf(已插入 %d 个元素, 当前大小: %d\n, i, GetLinkListSize(stressHead)); } } ​ printf(\n--- 删除50个元素 (每隔一个删一个) ---\n); for(int i 1; i 50; i) { deleteLinkList(stressHead, i); if(i % 10 0) { printf(已删除 %d 个元素, 当前大小: %d\n, i, GetLinkListSize(stressHead)); } } ​ printf(\n最终压力测试链表: ); printLinkList(stressHead); printf(最终大小: %d\n, GetLinkListSize(stressHead)); ​ printf(\n 8. GetPointByElement 综合测试 \n); linkNode TestHead; Node testHead TestHead; InitLinkList(testHead); ​ // 插入测试数据 insertLinkList(testHead, 11, 1); insertLinkList(testHead, 22, 2); insertLinkList(testHead, 33, 3); insertLinkList(testHead, 44, 4); insertLinkList(testHead, 55, 5); ​ printf(测试链表: ); printLinkList(testHead); ​ printf(\n--- 查找头部元素11 ---\n); Node found GetPointByElement(testHead, 11); if(found) printf(找到: %d at %p\n, found-element, found); ​ printf(\n--- 查找中间元素33 ---\n); found GetPointByElement(testHead, 33); if(found) printf(找到: %d at %p\n, found-element, found); ​ printf(\n--- 查找尾部元素55 ---\n); found GetPointByElement(testHead, 55); if(found) printf(找到: %d at %p\n, found-element, found); ​ printf(\n--- 查找不存在的元素100 ---\n); found GetPointByElement(testHead, 100); if(!found) printf(正确返回NULL\n); ​ printf(\n 9. 综合操作测试 \n); linkNode FinalHead; Node finalHead FinalHead; InitLinkList(finalHead); ​ // 混合操作 printf(\n初始插入: ); insertLinkList(finalHead, 1, 1); insertLinkList(finalHead, 3, 2); insertLinkList(finalHead, 5, 3); printLinkList(finalHead); ​ printf(在位置2插入2: ); insertLinkList(finalHead, 2, 2); printLinkList(finalHead); ​ printf(在位置4插入4: ); insertLinkList(finalHead, 4, 4); printLinkList(finalHead); ​ printf(删除位置3: ); deleteLinkList(finalHead, 3); printLinkList(finalHead); ​ printf(查找元素4: ); Node foundNode GetPointByElement(finalHead, 4); if(foundNode) printf(找到元素4地址: %p\n, foundNode); ​ printf(最终结果: ); for(int i 1; i GetLinkListSize(finalHead); i) { printf(%d , GetElementByIndex(finalHead, i)); } printf(\n); ​ printf(\n 所有测试完成 \n); ​ return 0; ​ }测试结果 9. 综合操作测试 [LOG]:This new LinkList s Adress is 00000044363FF940 ​ 初始插入: [LOG]:insert success [INFO]:Front Node address 00000044363FF940,Target Node address 00000221D6390F20 [LOG]:insert success [INFO]:Front Node address 00000221D6390F20,Target Node address 00000221D6391060 [LOG]:insert success [INFO]:Front Node address 00000221D6391060,Target Node address 00000221D63911A0 [1,00000221D6391060]-[3,00000221D63911A0]-[5,0000000000000000]-在位置2插入2: [LOG]:insert success [INFO]:Front Node address 00000221D6390F20,Target Node address 00000221D6390E20 [1,00000221D6390E20]-[2,00000221D6391060]-[3,00000221D63911A0]-[5,0000000000000000]-在位置4插入4: [LOG]:insert success [INFO]:Front Node address 00000221D6391060,Target Node address 00000221D6391240 [1,00000221D6390E20]-[2,00000221D6391060]-[3,00000221D6391240]-[4,00000221D63911A0]-[5,0000000000000000]-删除位置3: [LOG]:Delete success,Node Adress 00000221D6391060,Node element 3 [1,00000221D6390E20]-[2,00000221D6391240]-[4,00000221D63911A0]-[5,0000000000000000]-查找元素4: [LOG]:Find success [INFO]: Node Address 00000221D6391240,Node element 4 找到元素4地址: 00000221D6391240 最终结果: 1 2 4 5 ​ 所有测试完成