【c语言数据结构】——单链表专题

一. 单链表的概念1. 链表的概念链表是一种在物理存储结构上非连续非顺序的存储结构数据在逻辑结构上是以链表中的指针链接次序实现的。2. 单链表是由节点组成的每个节点都有对应的地址节点包含两部分一是要存储的数据二是指向下一个节点的地址的指针。3. 为什么还需要指针变量来保存下一节点的位置答链表中每一节点都是独立申请的即需要插入数据时才会申请一块节点的空间我们需要指针变量保存下一节点的地址才能从当前位置找到下一节点。二. 单链表的结构体实现struct SListNode { int data;//节点的数据 struct SListNode* next;//指针变量用来保存下一节点的地址 }三. 单链表各种操作的实现1.创建单链表的结构体//SList.htypedefintSLTDataType;typedefstructSListNode{SLTDataType data;structSListNode*next;}SLTNode;2.创建节点//SList.cSLTNode*SLTBuyNode(SLTDataType x){SLTNode*newNode(SLTNode*)malloc(sizeof(SLTNode));if(newNodeNULL){perror(malloc);exit(1);}newNode-datax;newNode-nextNULL;returnnewNode;}3.链表的打印//SList.cvoidSLTPrint(SLTNode*phead){SLTNode*pcurphead;while(pcur){printf(%d-,pcur-data);pcurpcur-next;}printf(NULL\n);}4.尾插//SList.cvoidSLTPushBack(SLTNode**pphead,SLTDataType x){assert(pphead)SLTNode*newnodeSLTBuyNode(x);if(*ppheadNULL){*ppheadnewnode;}else{SLTNode*ptail*pphead;while(ptail-next){ptailptail-next;}ptail-nextnewnode;}}5.头插//SList.cvoidSLTPushFront(SLTNode**pphead,SLTDataType x){assert(pphead);SLTNode*newnodeSLTBuyNode(x);newnode-next*pphead;*ppheadnewnode;}6.尾删//SList.cvoidSLTPopBack(SLTNode**pphead){assert(pphead*pphead);if((*pphead)-nextNULL){free(*pphead);*ppheadNULL;}else{SLTNode*ptial*pphead;SLTNode*prev*pphead;while(ptial-next){prevptial;ptialptial-next;}free(ptial);ptialNULL;prev-nextNULL;}}7.头删//SList.cvoidSLTPopFront(SLTNode**pphead){assert(pphead*pphead);SLTNode*next(*pphead)-next;free(*pphead);*ppheadnext;}8.查找//SList.cSLTNode*SLTFind(SLTNode*phead,SLTDataType x){SLTNode*pcurphead;while(pcur){if(pcur-datax)returnpcur;pcurpcur-next;}returnNULL;}9.在指定位置前后插入数据9.1在指定位置之前插入数据//SList.cvoidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x){assert(pphead*pphead);assert(pos);SLTNode*newnodeSLTBuyNode(x);if(pos*pphead){SLTPushFront(pphead,x);}else{SLTNode*prev*pphead;while(prev-next!pos){prevprev-next;}newnode-nextpos;prev-nextnewnode;}}9.2在指定位置之后插入数据//SList.cvoidSLTInsertAfter(SLTNode*pos,SLTDataType x){assert(pos);SLTNode*newnodeSLTBuyNode(x);newnode-nextpos-next;pos-nextnewnode;}10.删除pos节点//SList.cvoidSLErase(SLTNode**pphead,SLTNode*pos){assert(pphead*pphead);assert(pos);if(pos*pphead){SLTPopFront(pphead);}else{SLNode*prev*pphead;while(prev-next!pos){prevprev-next;}prev-nextpos-next;free(pos);posNULL;}}11.删除pos之后的节点//SList.cvoidSLTEraseAfter(SLTNode*pos){assert(pospos-next);SLTNode*delpos-nest;pos-nextdel-next;free(del);delNULL;}12.销毁链表//SList.cvoidSLTDesTroy(SLTNode**pphead){assert(pphead*pphead);SLTNode*pcur*pphead;while(pcur){SLTNode*nextpcur-next;free(pcur);pcurnext;}*ppheadNULL;}四. 总代码1.SList.h//SList.h#pragmaonce#includestdio.h#includestdlib.h#includeassert.htypedefintSLTDataType;typedefstructSListNode{SLTDataType data;structSListNode*next;}SLTNode;//创建节点SLTNode*SLTBuyNode(SLTDataType x);//打印单链表voidSLTPrint(SLTNode*phead);//尾插voidSLTPushBack(SLTNode**pphead,SLTDataType x);//头插voidSLTPushFront(SLTNode**pphead,SLTDataType x);//尾删voidSLTPopBack(SLTNode**pphead);//头删voidSLTPopFront(SLTNode**pphead);//查找SLTNode*SLTFind(SLTNode*phead,SLTDataType x);//在指定位置之前插入数据voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x);//在指定位置之后插入数据voidSLTInsertAfter(SLTNode**pphead,SLTNode*pos,SLTDataType x);//删除pos节点voidSLTErase(SLTNode**pphead,SLTNode*pos);//删除pos之后的节点voidSLTEraseAfter(SLTNode*pos);//销毁链表voidSLTDesTroy(SLTNode**pphead);2.SList.c//SList.c#define_CRT_SECURE_NO_WARNINGS1#includeSList.h//创建节点SLTNode*SLTBuyNode(SLTDataType x){SLTNode*newnode(SLTNode*)malloc(sizeof(SLTDataType));if(newnodeNULL){perror(malloc );exit(1);}else{newnode-datax;newnode-nextNULL;returnnewnode;}}//打印单链表voidSLTPrint(SLTNode*phead){assert(phead);while(phead){printf(%d-,phead-data);pheadphead-next;}printf(NULL\n);}// 尾插voidSLTPushBack(SLTNode**pphead,SLTDataType x){assert(pphead);SLTNode*newnodeSLTBuyNode(x);if(*ppheadNULL){*ppheadnewnode;}else{SLTNode*ptail*pphead;while(ptail-next!NULL){ptailptail-next;}ptail-nextnewnode;}}//头插voidSLTPushFront(SLTNode**pphead,SLTDataType x){assert(pphead);SLTNode*newnodeSLTBuyNode(x);newnode-next*pphead;*ppheadnewnode;}//尾删voidSLTPopBack(SLTNode**pphead){assert(pphead*pphead);SLTNode*ptail*pphead;SLTNode*prev*pphead;while(ptail-next!NULL){prevptail;ptailptail-next;}free(ptail);ptailNULL;prev-nextNULL;}//头删voidSLTPopFront(SLTNode**pphead){assert(pphead*pphead);SLTNode*next(*pphead)-next;free(*pphead);*ppheadnext;}//查找SLTNode*SLTFind(SLTNode*phead,SLTDataType x){assert(phead);SLTNode*newnodeSLTBuyNode(x);SLTNode*ptailphead;while(ptail){if(newnode-dataptail-data){returnptail;}else{ptailptail-next;}}returnNULL;}//在指定位置之前插入数据voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x){assert(pphead*pphead);assert(pos);SLTNode*newnodeSLTBuyNode(x);if(pos*pphead){SLTPushFront(pphead,x);}else{SLTNode*prev*pphead;while(prev-next!pos){prevprev-next;}newnode-nextpos;prev-nextnewnode;}}//在指定位置之后插入数据voidSLTInsertAfter(SLTNode**pphead,SLTNode*pos,SLTDataType x){assert(pphead*pphead);assert(pos);SLTNode*newnodeSLTBuyNode(x);newnode-nextpos-next;pos-nextnewnode;}//删除pos节点voidSLTErase(SLTNode**pphead,SLTNode*pos){assert(pphead*pphead);assert(pos);SLTNode*prev*pphead;if(pos*pphead){SLTPopFront(pphead);}else{while(prev-next!pos){prevprev-next;}prev-nextpos-next;free(pos);posNULL;}}//删除pos之后的节点voidSLTEraseAfter(SLTNode*pos){assert(pospos-next);SLTNode*delpos-next;pos-nextdel-next;free(del);delNULL;}//销毁链表voidSLTDesTroy(SLTNode**pphead){assert(pphead*pphead);SLTNode*pcur*pphead;while(pcur-next!NULL){SLTNode*nextpcur-next;free(pcur);pcurnext;}*ppheadNULL;}3.test.c//test.c#define_CRT_SECURE_NO_WARNINGS1#includeSList.hvoidSLTist01(){SLTNode*plistNULL;//测试尾插/*SLTPushBack(plist, 1); SLTPushBack(plist, 2); SLTPushBack(plist, 3); SLTPushBack(plist, 4); SLTPrint(plist);*///测试头插/*SLTPushFront(plist, 0); SLTPushFront(plist, 1); SLTPushFront(plist, 2); SLTPushFront(plist, 3); SLTPrint(plist);*///测试尾删/*SLTPushFront(plist, 0); SLTPushFront(plist, 1); SLTPushFront(plist, 2); SLTPushFront(plist, 3); SLTPopBack(plist); SLTPrint(plist);*///测试头删/*SLTPushFront(plist, 0); SLTPushFront(plist, 1); SLTPushFront(plist, 2); SLTPushFront(plist, 3); SLTPopFront(plist); SLTPopFront(plist); SLTPopBack(plist); SLTPrint(plist);*///测试查找//SLTPushFront(plist, 0);//SLTPushFront(plist, 1);//SLTPushFront(plist, 2);//SLTPushFront(plist, 3);///*printf(%p \n,SLTFind(plist, 2));*////*SLTInsert(plist, SLTFind(plist, 2), 8);*///SLTInsertAfter(plist, SLTFind(plist, 2), 8);//SLTPrint(plist);//测试删除POS节点/*SLTPushFront(plist, 0); SLTPushFront(plist, 1); SLTPushFront(plist, 2); SLTPushFront(plist, 3); SLTErase(plist, SLTFind(plist, 2)); SLTPrint(plist);*///测试删除pos之后的节点SLTPushFront(plist,0);SLTPushFront(plist,1);SLTPushFront(plist,2);SLTPushFront(plist,3);SLTEraseAfter(SLTFind(plist,2));SLTPrint(plist);}intmain(){SLTist01();return0;}完若上述文章有什么错误欢迎各位大佬及时指出我们共同进步