数据结构——链表自实现

专栏链接：《C++学习》、《Linux学习》

头文件实现

#pragmaonce#include<stdio.h>#include<stdlib.h>// 补充bool类型头文件（C语言需手动定义或包含stdbool.h）#include<stdbool.h>// 修正：C语言中结构体指针必须加struct（原代码漏写导致编译报错）structListNode{structListNode*next;intval;};//1.Print函数voidPrint(structListNode*phead){structListNode*cur=phead;if(cur==NULL){printf("NULL\n");}else{while(cur){printf("%d->",cur->val);cur=cur->next;}printf("NULL\n");}}// 创建节点函数structListNode*CreateNode(intx){structListNode*newNode=(structListNode*)malloc(sizeof(structListNode));if(newNode==NULL){perror("malloc error!");exit(1);}newNode->val=x;newNode->next=NULL;returnnewNode;}//1.InsHead头插函数// 二级指针使用原因：要修改原头指针的指向（一级指针传参是值拷贝，无法修改外部指针）structListNode*InsHead(structListNode**pphead,intn){structListNode*newheadNode=CreateNode(n);//先把 头节点拼上去newheadNode->next=*pphead;//然后在把头节点的职位 交给newheadNode*pphead=newheadNode;Print(*pphead);return*pphead;}//2.DelHead头删函数// 二级指针使用原因：删除头节点后需要修改原头指针的指向（比如从h0改为h1），一级指针无法修改外部变量structListNode*DelHead(structListNode**pphead){structListNode*newHead;if(*pphead==NULL){perror("DelHead error!");exit(1);}else{newHead=(*pphead)->next;(*pphead)->next=NULL;free(*pphead);*pphead=NULL;// 释放后置空，避免野指针}Print(newHead);returnnewHead;}//3.InsTail尾插// 注：尾插用一级指针即可（无需修改原头指针指向，仅遍历链表），但空链表时返回新节点更合理structListNode*InsTail(structListNode*phead,intn){structListNode*newNode=CreateNode(n);structListNode*cur=phead;if(phead==NULL){Print(newNode);returnnewNode;}else{while(cur->next!=NULL){cur=cur->next;}cur->next=newNode;}Print(phead);returnphead;}//4.DelTail尾删// 优化：尾删也可封装为二级指针版本（避免返回值覆盖，保持接口一致性），此处保留原逻辑+修复bugstructListNode*DelTail(structListNode*phead){structListNode*head=phead;if(head==NULL){perror("DelTail error: empty list");// 补充错误提示，而非直接exitexit(1);}elseif(head->next==NULL){printf("NULL\n");free(head);// 原代码先置next再free，顺序不影响，但free后head已成野指针，无需置nextreturnNULL;}else{structListNode*tmp=head;while(tmp->next->next!=NULL){tmp=tmp->next;}free(tmp->next);tmp->next=NULL;// 修正：C语言无nullptr，统一用NULL（原代码混用导致编译报错）// tmp->next = nullptr;}Print(head);returnhead;}// 查找函数boolFind(structListNode*phead,intn){structListNode*pcur=phead;if(pcur==NULL){returnfalse;}while(pcur){if(pcur->val==n)returntrue;pcur=pcur->next;}returnfalse;}// 新增：链表销毁函数（避免内存泄漏，必补！）// 二级指针使用原因：销毁后需要将原头指针置空，防止外部使用野指针voidDestroyList(structListNode**pphead){if(pphead==NULL||*pphead==NULL){return;}structListNode*cur=*pphead;while(cur){structListNode*tmp=cur;cur=cur->next;free(tmp);}*pphead=NULL;// 销毁后置空原头指针}

测试文件实现

#include"list.h"voidInit(){ListNode*h0=(ListNode*)malloc(sizeof(ListNode));ListNode*h1=(ListNode*)malloc(sizeof(ListNode));ListNode*h2=(ListNode*)malloc(sizeof(ListNode));ListNode*h3=(ListNode*)malloc(sizeof(ListNode));h0->val=0;h1->val=1;h2->val=2;h3->val=3;h0->next=h1;h1->next=h2;h2->next=h3;h3->next=NULL;Print(h0);}voidtest1(){ListNode*phead=NULL;phead=InsHead(&phead,1);phead=InsHead(&phead,2);phead=InsHead(&phead,3);phead=InsHead(&phead,4);}voidtest2(){ListNode*phead=NULL;phead=InsHead(&phead,1);phead=InsHead(&phead,2);phead=InsHead(&phead,3);phead=InsHead(&phead,4);phead=DelHead(&phead);phead=DelHead(&phead);phead=DelHead(&phead);phead=DelHead(&phead);}voidtest3(){ListNode*head=NULL;head=InsTail(head,3);head=InsTail(head,2);head=InsTail(head,1);head=InsTail(head,0);}voidtest4(){ListNode*phead=NULL;phead=InsHead(&phead,1);phead=InsHead(&phead,2);phead=InsHead(&phead,3);phead=InsHead(&phead,4);phead=DelTail(phead);phead=DelTail(phead);phead=DelTail(phead);phead=DelTail(phead);}voidtest5(){ListNode*head=NULL;head=InsTail(head,3);head=InsTail(head,2);head=InsTail(head,1);head=InsTail(head,0);if(Find(head,2)==true)printf("找到");else{printf("未找到");}}intmain(){printf("----Init函数----\n");Init();printf("----InsHead----\n");test1();printf("----DelHead----\n");test2();printf("----InsTail----\n");test3();printf("----DelTail----\n");test4();printf("----Find----\n");test5();return0;}

易错汇总

1.解释为什么头插参数为二级指针？并且思考总结什么情况下C语言需要用二级指针？
2.思考C语言中的 malloc检验机制与C++中的检验机制有什么不同？ C语言检验机制使用的弊端在哪里？
3.思考在上述代码中为了防止内存泄漏 都做了free野指针、补充销毁函数。请阐述它们的实现方法。
4.思考在上述语法中 C语言和C++的语法上面的不同

1.关于空NULL与nullptr
2.关于结构体 内的成员函数
struct ListNode* 与struct ListNode*