【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(newNode==NULL){perror("malloc");exit(1);}newNode->data=x;newNode->next=NULL;returnnewNode;}3.链表的打印
//SList.cvoidSLTPrint(SLTNode*phead){SLTNode*pcur=phead;while(pcur){printf("%d->",pcur->data);pcur=pcur->next;}printf("NULL\n");}4.尾插
//SList.cvoidSLTPushBack(SLTNode**pphead,SLTDataType x){assert(pphead)SLTNode*newnode=SLTBuyNode(x);if(*pphead==NULL){*pphead=newnode;}else{SLTNode*ptail=*pphead;while(ptail->next){ptail=ptail->next;}ptail->next=newnode;}}5.头插
//SList.cvoidSLTPushFront(SLTNode**pphead,SLTDataType x){assert(pphead);SLTNode*newnode=SLTBuyNode(x);newnode->next=*pphead;*pphead=newnode;}6.尾删
//SList.cvoidSLTPopBack(SLTNode**pphead){assert(pphead&&*pphead);if((*pphead)->next==NULL){free(*pphead);*pphead=NULL;}else{SLTNode*ptial=*pphead;SLTNode*prev=*pphead;while(ptial->next){prev=ptial;ptial=ptial->next;}free(ptial);ptial=NULL;prev->next=NULL;}}7.头删
//SList.cvoidSLTPopFront(SLTNode**pphead){assert(pphead&&*pphead);SLTNode*next=(*pphead)->next;free(*pphead);*pphead=next;}8.查找
//SList.cSLTNode*SLTFind(SLTNode*phead,SLTDataType x){SLTNode*pcur=phead;while(pcur){if(pcur->data==x)returnpcur;pcur=pcur->next;}returnNULL;}9.在指定位置前后插入数据
9.1在指定位置之前插入数据
//SList.cvoidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x){assert(pphead&&*pphead);assert(pos);SLTNode*newnode=SLTBuyNode(x);if(pos==*pphead){SLTPushFront(pphead,x);}else{SLTNode*prev=*pphead;while(prev->next!=pos){prev=prev->next;}newnode->next=pos;prev->next=newnode;}}9.2在指定位置之后插入数据
//SList.cvoidSLTInsertAfter(SLTNode*pos,SLTDataType x){assert(pos);SLTNode*newnode=SLTBuyNode(x);newnode->next=pos->next;pos->next=newnode;}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){prev=prev->next;}prev->next=pos->next;free(pos);pos=NULL;}}11.删除pos之后的节点
//SList.cvoidSLTEraseAfter(SLTNode*pos){assert(pos&&pos->next);SLTNode*del=pos->nest;pos->next=del->next;free(del);del=NULL;}12.销毁链表
//SList.cvoidSLTDesTroy(SLTNode**pphead){assert(pphead&&*pphead);SLTNode*pcur=*pphead;while(pcur){SLTNode*next=pcur->next;free(pcur);pcur=next;}*pphead=NULL;}四. 总代码
1.SList.h
//SList.h#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefintSLTDataType;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#include"SList.h"//创建节点SLTNode*SLTBuyNode(SLTDataType x){SLTNode*newnode=(SLTNode*)malloc(sizeof(SLTDataType));if(newnode==NULL){perror("malloc ");exit(1);}else{newnode->data=x;newnode->next=NULL;returnnewnode;}}//打印单链表voidSLTPrint(SLTNode*phead){assert(phead);while(phead){printf("%d->",phead->data);phead=phead->next;}printf("NULL\n");}// 尾插voidSLTPushBack(SLTNode**pphead,SLTDataType x){assert(pphead);SLTNode*newnode=SLTBuyNode(x);if(*pphead==NULL){*pphead=newnode;}else{SLTNode*ptail=*pphead;while(ptail->next!=NULL){ptail=ptail->next;}ptail->next=newnode;}}//头插voidSLTPushFront(SLTNode**pphead,SLTDataType x){assert(pphead);SLTNode*newnode=SLTBuyNode(x);newnode->next=*pphead;*pphead=newnode;}//尾删voidSLTPopBack(SLTNode**pphead){assert(pphead&&*pphead);SLTNode*ptail=*pphead;SLTNode*prev=*pphead;while(ptail->next!=NULL){prev=ptail;ptail=ptail->next;}free(ptail);ptail=NULL;prev->next=NULL;}//头删voidSLTPopFront(SLTNode**pphead){assert(pphead&&*pphead);SLTNode*next=(*pphead)->next;free(*pphead);*pphead=next;}//查找SLTNode*SLTFind(SLTNode*phead,SLTDataType x){assert(phead);SLTNode*newnode=SLTBuyNode(x);SLTNode*ptail=phead;while(ptail){if(newnode->data==ptail->data){returnptail;}else{ptail=ptail->next;}}returnNULL;}//在指定位置之前插入数据voidSLTInsert(SLTNode**pphead,SLTNode*pos,SLTDataType x){assert(pphead&&*pphead);assert(pos);SLTNode*newnode=SLTBuyNode(x);if(pos==*pphead){SLTPushFront(pphead,x);}else{SLTNode*prev=*pphead;while(prev->next!=pos){prev=prev->next;}newnode->next=pos;prev->next=newnode;}}//在指定位置之后插入数据voidSLTInsertAfter(SLTNode**pphead,SLTNode*pos,SLTDataType x){assert(pphead&&*pphead);assert(pos);SLTNode*newnode=SLTBuyNode(x);newnode->next=pos->next;pos->next=newnode;}//删除pos节点voidSLTErase(SLTNode**pphead,SLTNode*pos){assert(pphead&&*pphead);assert(pos);SLTNode*prev=*pphead;if(pos==*pphead){SLTPopFront(pphead);}else{while(prev->next!=pos){prev=prev->next;}prev->next=pos->next;free(pos);pos=NULL;}}//删除pos之后的节点voidSLTEraseAfter(SLTNode*pos){assert(pos&&pos->next);SLTNode*del=pos->next;pos->next=del->next;free(del);del=NULL;}//销毁链表voidSLTDesTroy(SLTNode**pphead){assert(pphead&&*pphead);SLTNode*pcur=*pphead;while(pcur->next!=NULL){SLTNode*next=pcur->next;free(pcur);pcur=next;}*pphead=NULL;}3.test.c
//test.c#define_CRT_SECURE_NO_WARNINGS1#include"SList.h"voidSLTist01(){SLTNode*plist=NULL;//测试尾插/*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;}完！
若上述文章有什么错误，欢迎各位大佬及时指出，我们共同进步！