【数据结构初阶】单链表_数据结构单链表
文章目录
- 单链表
-
- 1. 链表的概念及结构
- 2. 单链表的实现
-
- 1.定义结点
- 2.打印数据
- 3.申请新的节点
- 4.尾插
- 5.头插
- 6.尾删
- 7.头删
- 8.查找
- 9.指点位置之前插入
- 10.指定位置后插入
- 11.指定位置前删除
- 12.指定位置后删除
- 13.链表的销毁
- 3.程序源码
单链表
1. 链表的概念及结构
概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的。
链表的结构跟火车厢相似，淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。⻋厢是独⽴存在的，且每节⻋厢都有⻋⻔。想象⼀下这样的场景，假设每节⻋厢的⻋⻔都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾？
最简单的做法：每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。
在链表⾥，每节“⻋厢”是什么样的呢？
与顺序表不同的是，链表⾥的每节\"⻋厢\"都是独⽴申请下来的空间，我们称之为“结点/节点”
节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。
图中指针变量plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0x0012FFA0。
为什么还需要指针变量来保存下⼀个节点的位置？
链表中每个节点都是独⽴申请的（即需要插⼊数据时才去申请⼀块节点的空间），我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。
结合前⾯学到的结构体知识，我们可以给出每个节点对应的结构体代码：
假设当前保存的节点为整型：
struct SListNode{ int data; //节点数据 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址 };当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数
据，也需要保存下⼀个节点的地址（当下⼀个节点为空时保存的地址为空）。
当我们想要从第⼀个节点⾛到最后⼀个节点时，只需要在前⼀个节点拿上下⼀个节点的地址（下⼀个节点的钥匙）就可以了。
给定的链表结构中，如何实现节点从头到尾的打印？
2. 单链表的实现
1.定义结点
typedef int SLTDataType;typedef struct SListNode //s single{SLTDataType data;struct SListNode* next;}SLTNode;2.打印数据
void SLTPrint(SLTNode* phead){SLTNode* pcur = phead;while (pcur)//pcur!=NULL{printf(\"%d->\", pcur->data);pcur = pcur->next;}printf(\"NULL\\n\");}3.申请新的节点
SLTNode* SLTBuyNode(SLTDataType x){SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror(\"malloc fail!\");exit(1);}//申请成功newnode->data = x;newnode->next = NULL;return newnode;}4.尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x){assert(pphead);//pphead不能为空 不能对空指针解引用//空链表和非空链表SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找尾SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail指向尾节点ptail->next = newnode;}}5.头插
void SLTPushFront(SLTNode** pphead, SLTDataType x){assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;}6.尾删
//尾删void SLTPopBack(SLTNode** pphead){//链表不能为空assert(pphead&&*pphead);if ((*pphead)->next == NULL)//->的优先级高于* 所以要加括号{free(*pphead);*pphead = NULL;}else{//找尾SLTNode* prev = *pphead;//要删除的前一个SLTNode* ptail = *pphead;//要删除的while (ptail->next){prev = ptail;ptail = ptail->next;}//prev ptaifree(ptail);ptail = NULL;prev->next = NULL;}}7.头删
void SLTPopFront(SLTNode** pphead){//链表不能为空assert(pphead && *pphead);SLTNode* next= (*pphead)->next;//记得加括号free(*pphead);*pphead = next;}8.查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x){SLTNode* pcur = phead;while (pcur)//pcur != NULL{if (pcur->data == x){return pcur;}pcur = pcur->next;}//pcur == NULLreturn NULL;}9.指点位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){assert(pphead && *pphead);//若*pphead为空 则pos也为空assert(pos);SLTNode* newnode = SLTBuyNode(x);if (pos == *pphead){SLTPushFront(pphead,x);}else{SLTNode* prev = *pphead;//找pos前一个节点while (prev->next != pos){prev = prev->next;}//prev newnode posprev->next = newnode;newnode->next = pos;}}10.指定位置后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x){assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;//为什么顺序不能交换pos->next = newnode;}11.指定位置前删除
void SLTErase(SLTNode** pphead, SLTNode* pos){assert(pphead && *pphead);SLTNode* prev = *pphead;//找pos前一个节点if (pos == *pphead){//头删SLTPopFront(pphead);}while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}12.指定位置后删除
void SLTEraseAfter(SLTNode* pos){assert(pos&&pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del->next = NULL;}13.链表的销毁
void SLTDestroy(SLTNode** pphead){assert(pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = (*pphead)->next;free(pcur);pcur = next;}//pcur 为空*pphead = NULL;}3.程序源码
共分三个文件
SLTist.h 函数的声明
#pragma once#include#include#include//定义节点结构//数据+指向下一个节点的指针typedef int SLTDataType;typedef struct SListNode //s single{SLTDataType data;struct SListNode* next;}SLTNode;void SLTPrint(SLTNode* phead);//尾插void SLTPushBack(SLTNode** pphead, SLTDataType x);//头插void SLTPushFront(SLTNode** pphead, SLTDataType x);//尾删void SLTPopBack(SLTNode** pphead);//头删void SLTPopFront(SLTNode** pphead);//查找SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插入void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在头节点前插入，头节点可能改变//在指定位置之后插入数据void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后的节点void SLTEraseAfter(SLTNode* pos);//销毁链表void SLTDestroy(SLTNode** pphead);SList.c 函数的实现
#define _CRT_SECURE_NO_WARNINGS#include\"SList.h\"void SLTPrint(SLTNode* phead){SLTNode* pcur = phead;while (pcur)//pcur!=NULL{printf(\"%d->\", pcur->data);pcur = pcur->next;}printf(\"NULL\\n\");}SLTNode* SLTBuyNode(SLTDataType x){SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror(\"malloc fail!\");exit(1);}//申请成功newnode->data = x;newnode->next = NULL;return newnode;}//尾插void SLTPushBack(SLTNode** pphead, SLTDataType x){assert(pphead);//pphead不能为空 不能对空指针解引用//空链表和非空链表SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找尾SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail指向尾节点ptail->next = newnode;}}void SLTPushFront(SLTNode** pphead, SLTDataType x){assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;}//尾删void SLTPopBack(SLTNode** pphead){//链表不能为空assert(pphead&&*pphead);if ((*pphead)->next == NULL)//->的优先级高于* 所以要加括号{free(*pphead);*pphead = NULL;}else{//找尾SLTNode* prev = *pphead;//要删除的前一个SLTNode* ptail = *pphead;//要删除的while (ptail->next){prev = ptail;ptail = ptail->next;}//prev ptaifree(ptail);ptail = NULL;prev->next = NULL;}}//头删void SLTPopFront(SLTNode** pphead){//链表不能为空assert(pphead && *pphead);SLTNode* next= (*pphead)->next;//记得加括号free(*pphead);*pphead = next;}//查找SLTNode* SLTFind(SLTNode* phead, SLTDataType x){SLTNode* pcur = phead;while (pcur)//pcur != NULL{if (pcur->data == x){return pcur;}pcur = pcur->next;}//pcur == NULLreturn NULL;}void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){assert(pphead && *pphead);//若*pphead为空 则pos也为空assert(pos);SLTNode* newnode = SLTBuyNode(x);if (pos == *pphead){SLTPushFront(pphead,x);}else{SLTNode* prev = *pphead;//找pos前一个节点while (prev->next != pos){prev = prev->next;}//prev newnode posprev->next = newnode;newnode->next = pos;}}void SLTInsertAfter(SLTNode* pos, SLTDataType x){assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;//为什么顺序不能交换pos->next = newnode;}void SLTErase(SLTNode** pphead, SLTNode* pos){assert(pphead && *pphead);SLTNode* prev = *pphead;//找pos前一个节点if (pos == *pphead){//头删SLTPopFront(pphead);}while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}void SLTEraseAfter(SLTNode* pos){assert(pos&&pos->next);SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del->next = NULL;}void SLTDestroy(SLTNode** pphead){assert(pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = (*pphead)->next;free(pcur);pcur = next;}//pcur 为空*pphead = NULL;}test.c 用来测试
#define _CRT_SECURE_NO_WARNINGS#include\"SList.h\"void SListTest01(){//链表是由一个一个的节点组成SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));node2->data = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));node3->data = 3;SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node4->data = 4;//将四个节点连接起来node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;//调用链表的打印SLTNode* plist = node1;SLTPrint(plist);}void Test02(){SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);//SLTPushFront(&plist, 5);//SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);SLTNode* find = SLTFind(plist,3);/*if (find == NULL){printf(\"没有找到\\n\");}else{printf(\"找到了！\\n\");}*///SLTInsert(&plist, find,11);SLTInsertAfter(find,9);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);SLTEraseAfter(find);SLTDestroy(&plist);SLTPrint(plist);}int main(){//SListTest01();Test02();return 0;}
