【数据结构】单链表详解

单链表详解

1、单链表的概念

链表是一种线性数据结构，有一系列节点组成，每个节点包括两部分：存储当前节点的数据（数据区域）和下一个节点的地址（指针区域）。

简单理解，单链表可以比作火车，有车厢和挂钩，每一节车厢就是一个节点，节点里存储数据data,车厢之间有挂钩（节点里有指针next）。

2、单链表的实现

1.创建三个文件

SList.h文件放函数声明

SList.c文件实现.h文件中函数功能

test.c文件测试函数功能

函数功能目录 .h文件

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>//定义节点的结构//数据+指向下一个结点的指针typedefint SLTDataType;typedefstructSListNode{ SLTDataType data;structSListNode* next;}SLTNode;//打印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* pos, SLTDataType x);//在指定位置删除数据voidSLTErase(SLTNode** pphead, SLTNode* pos);//在指定位置之后删除数据voidSLTEraseAfter(SLTNode* pos);//销毁voidSListDestroy(SLTNode** pphead);

2.单链表功能实现

2.1单链表核心结构

typedefint SLTDataType;typedefstructSListNode{ SLTDataType data;//存储数据structSListNode* next;//存储下一个节点的地址}SLTNode;

2.2单链表的打印

voidSLTPrint(SLTNode* phead){//只用来打印链表 不修改链表 不用二级指针 SLTNode* pcur = phead;//要用pcur充当头节点 遍历后phead指向末尾while(pcur){printf("%d->", pcur->data); pcur = pcur->next;}printf("NULL\n");}

· 只看不改，所以这里不用二级指针

· 用pcur遍历，不动原来的头指针

· 只要节点不为空，就打印数据，然后走到下一个

2.3创建新的节点

SLTNode*SLTBuyNode(SLTDataType x){ SLTNode* newnode =(SLTNode*)malloc(sizeof(SLTNode));//内存不够 报错退出if(newnode ==NULL){perror("malloc error");exit(1);} newnode->data = x; newnode->next =NULL;return newnode;}

· 先向内存要一块能存一个节点的空间

· 把数据data赋值为x

· 先让next指针置为空

· 返回这个节点

2.4查找节点

SLTNode*SLTFind(SLTNode* phead, SLTDataType x){ SLTNode* pcur = phead;while(pcur){if(pcur->data == x){return pcur;} pcur = pcur->next;}returnNULL;}

· 用pcur代替phead遍历链表，找到返回节点地址，找不到返回NULL

3.单链表的插入和删除

3.1尾插

voidSLTPushBack(SLTNode** pphead, SLTDataType x){assert(pphead);//*pphead不能为空 pphead为空说明没有头节点//*pphead就是指向第一个节点的指针//空链表和非空链表 SLTNode* newnode =SLTBuyNode(x);if(*pphead ==NULL){*pphead = newnode;}else{//找尾 SLTNode* ptail =*pphead;while(ptail->next！=NULL){//假如链表为空就是非法访问了 所以先判断是否为空 ptail = ptail->next;}//ptail指向的是尾节点 ptail->next = newnode;}}

· 为什么用二级指针？ 因为要修改头指针本身

· 先创建一个节点，用ptail遍历链表，直到ptail走到尾节点的位置停止遍历，把最后一个节点的指针指向新节点的地址

· 如果链表是空链表，直接将新创建的节点作为头节点

3.2头插

voidSLTPushFront(SLTNode** pphead, SLTDataType x){assert(pphead);//申请新的节点 SLTNode* newnode =SLTBuyNode(x);//newnode 和*pphead连接在一起 newnode->next =*pphead;*pphead = newnode;}

· 头插要改变头指针存放的地址，所以要用二级指针

· 新节点的next指针指向原来的头节点，新节点变成头节点

3.3在指定位置之前插入数据

**voidSLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){assert(pphead &&*pphead);assert(pos); SLTNode* newnode =SLTBuyNode(x);//当pos等于*pphead时是头插if(pos ==*pphead){SLTPushFront(pphead, x);}else{ SLTNode* prev =*pphead;while(prev->next != pos){ prev = prev->next;}//prev newnode pos newnode->next = pos; prev->next = newnode;}}**

· 用prev遍历链表，直到遍历到pos的前一个节点的位置停止遍历，此时需要把prev，newnode，pos连接到一起

3.4在指定位置之后插入数据

**voidSLTInsertAfter(SLTNode* pos, SLTDataType x){//第一种代码//newnode->next=pos->next//pos->next=newnode//第二种代码//pos->next=newnode//newnode->next=pos->nextassert(pos); SLTNode* newnode =SLTBuyNode(x);//顺序不能乱//pos newnode pos->next newnode->next = pos->next; pos->next = newnode;}**

这里需要注意，有两种顺序：

· 先让newnode的指针域指向pos的后一个节点的地址，再让pos的指针域指向newnode的地址（正确）

· 先让pos的指针域指向newnode的地址，再让newnode的指针域指向pos的后一个节点的地址（错误）

错误的代码操作：

pos：节点A

pos→next：节点B

第一步：pos→next=newnode 节点A的箭头指向了节点N 此时pos→next已经不是节点B，而是N

第二步：newnode→next=pos→next 这是pos→next为N，newnode→next也为N 节点N自己指向了自己，形成死循环

3.5头删

voidSLTPopFront(SLTNode** pphead){//链表不能为空assert(pphead &&*pphead); SLTNode* next =(*pphead)->next;free(*pphead);*pphead = next;}

· 头删要改变头指针中存放的地址，所以用二级指针

· 改变头节点前需要先保留原来头节点的地址，否则更换完头节点后找不到原来的头节点了

3.6尾删

voidSLTPopBack(SLTNode** pphead){assert(pphead);//链表不能为空assert(*pphead);//链表只有一个节点if((*pphead)->next ==NULL){free(*pphead);*pphead =NULL;}else{ SLTNode* prev =*pphead; SLTNode* ptail =*pphead;while(ptail->next){ prev = ptail; ptail = ptail->next;}free(ptail); ptail =NULL; prev->next =NULL;//prev是ptail前一个节点 需要将里面的next部分释放为空}}

· 尾删先要遍历一遍链表找到最后一个节点将其释放，要先找到倒数第二个节点，把倒数第二个节点的next指针置为空，再删除尾节点

3.7在指定位置删除数据

voidSLTErase(SLTNode** pphead, SLTNode* pos){assert(pphead &&*pphead);assert(pos);//pos是头节点if(pos ==*pphead){//头删SLTPopFront(pphead);}else{ SLTNode* prev =*pphead;while(prev->next != pos){ prev = prev->next;}//prev pos pos->next prev->next = pos->next;free(pos); pos =NULL;}}

· 当pos是头节点时，调用头删函数

· 用prev找到pos的前一个节点

· 让perv跳过pos，指向pos的下一个节点

· 释放pos

3.8删除pos位置后面的数据

voidSLTEraseAfter(SLTNode* pos){//不能删除pos节点assert(pos && pos->next); SLTNode* del = pos->next;//pos del del->next pos->next = del->next;free(del); del =NULL;}

· 要删除的节点是del，所以把pos的next指针指向del的下一个节点，最后释放del节点

4.单链表的销毁

voidSListDestroy(SLTNode** pphead){assert(pphead &&*pphead); SLTNode* pcur =*pphead;while(pcur){ SLTNode* next = pcur->next;free(pcur); pcur = next;}*pphead =NULL;}

· 所有节点全部释放

· 头节点置为空

3、测试文件

#include"SList.h"voidtest01(){//链表是由一个一个的节点组成//创造几个节点 SLTNode* nodel1 =(SLTNode*)malloc(sizeof(SLTNode)); nodel1->data =1; SLTNode* nodel2 =(SLTNode*)malloc(sizeof(SLTNode)); nodel2->data =2; SLTNode* nodel3 =(SLTNode*)malloc(sizeof(SLTNode)); nodel3->data =3; SLTNode* nodel4 =(SLTNode*)malloc(sizeof(SLTNode)); nodel4->data =4;//结果 1->2->3->4->NULL//将四个节点连接起来 nodel1->next = nodel2; nodel2->next = nodel3; nodel3->next = nodel4; nodel4->next =NULL;//调用链表的打印 SLTNode* plist1 = nodel1;SLTPrint(plist1);}voidtest02(){ SLTNode* plist =NULL;SLTPushBack(&plist,1);SLTPushBack(&plist,2);SLTPushBack(&plist,3);SLTPushBack(&plist,4);//结果 1->2->3->4->NULL//测试头插SLTPushFront(&plist,6);SLTPrint(plist);SLTPushFront(&plist,7);SLTPrint(plist);SLTPushFront(&plist,8);SLTPrint(plist);//结果 8->7->6->1->2->3->4->NULL//测试尾删SLTPopBack(&plist);SLTPrint(plist);SLTPopBack(&plist);SLTPrint(plist);//结果 8->7->6->1->2->NULL//测试头删SLTPopFront(&plist);SLTPrint(plist);SLTPopFront(&plist);SLTPrint(plist);//结果 6->1->2->NULL//测试查找 SLTNode* find =SLTFind(plist,1);if(find ==NULL){printf("没有找到\n");}else{printf("找到了\n");}//测试指定位置之前插入SLTInsert(&plist, find,11);SLTPrint(plist);//结果 6->11->1->2->NULL//测试指定位置之后插入SLTInsertAfter(find,12);SLTPrint(plist);//结果 6->11->1->12->2->NULL//测试在指定位置前删除数据//SLTErase(&plist,find);//SLTPrint(plist);//测试在指定位置后删除数据SLTEraseAfter(find);SLTPrint(plist);//结果 6->11->1->12->NULL}intmain(){//test01();test02();return0;}

如果文章中有错误或不足，欢迎大家指正交流。