C语言单链表的图文示例讲解
[Pokemon]大猫猫 人气:0在上一篇所讲述的 动态顺序表 中存在一些缺陷
1、当空间不够时需要扩容,扩容是有一定的消耗的
如果每次空间扩大一点,可能会造成空间的浪费,而空间扩小了,又会造成频繁的扩容2、在顺序表中进行头部和中部的插入时需要移动数据,效率低下
对于顺序表的这些缺陷,有如下解决方案
1、需要时申请一块空间,不需要时将其释放
2、插入删除不需要移动数据
而链表就符合这两点,本篇介绍 无头单向非循环链表(单链表)
一、单链表的结构
空链表: 此时没有存储数据,只有一个指针指向 NULL
以上便是单链表的结构:
- 每一块空间可以按需申请释放
- 插入和删除不需要移动数据,修改每块空间的指针指向即可
在习惯上将申请的一块一块的空间称为结点,指向第一个结点的指针称为头指针
//数据的类型:这里以 int 来举例 typedef int SLTDataType; //结点的类型 typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;
二、单链表的函数接口
1. 申请结点及打印单链表
在插入时需要申请结点,为了避免麻烦重复的操作,这里将申请结点封装为一个函数
申请结点函数如下:
SLTNode* BuySLTNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if(newnode == NULL) { //开辟空间失败,打印错误信息 perror("malloc"); //结束程序 exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }
为了验证插入、删除等得到的结果是否正确,提供打印单链表的函数,这里数据类型以 int 为例,当读者采用的类型不同时,自行更改函数即可
打印单链表函数如下:
void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; //打印数据 while(cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
2. 尾插尾删
尾插:在链表的最后一个结点之后插入结点
尾插函数如下:
//在链表为空时,需要改变头指针,这里采用传二级指针的方式 void SLTPushBack(SLTNode** pphead, SLTDataType x) { //申请结点 SLTNode* newnode = BuySLTNode(x); //链表为空时 if(*pphead == NULL) { *pphead = newnode; } else { //找到最后一个结点 SLTNode* ptail = *pphead; while(ptail->next) { ptail = ptail->next; } ptail->next = newnode; } }
尾删:删除链表最后一个结点
尾删函数如下:
//链表只有一个结点时,需要改变头指针,这里采用传二级指针的方式 void SLTPopBack(SLTNode** pphead) { //链表为空时,无法删除 assert(*pphead); //链表只有一个结点时 if((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { //找到倒数第二个结点 SLTNode* ptail = *pphead; while(ptail->next->next) { ptail = ptail->next; } free(ptail->next); ptail->next = NULL; } }
3. 头插头删
头插: 在第一个结点之前插入新结点
头插函数如下:
//需要改变头指针,这里采用传二级指针的方式 void SLTPushFront(SLTNode** pphead, SLTDataType x) { //申请结点 SLTNode* newnode = BuySLTNode(x); newnode->next = *pphead; *pphead = newnode; }
头删:删除链表的第一个结点
头删函数如下:
//需要改变头指针,这里采用传二级指针的方式 void SLTPopFront(SLTNode** pphead) { //链表为空时,无法删除 assert(*pphead); //保存第二个结点 SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; }
4. 中间插入和删除
中间插入:通过后面介绍的查找函数 SLTFind 获得指向结点的指针 pos,在 pos 指向的 结点之前 或 之后 插入结点
1. 在 pos 指向的结点之后插入结点
在 pos 之后插入结点函数如下:
void SLTInsertAfter(SLTNode* pos, SLTDataType x) { //pos 不能为空 assert(pos); //申请结点 SLTNode* newnode = BuySLTNode(x); newnode->next = pos->next; pos->next = newnode; }
2. 在 pos 指向的结点之前插入结点
在 pos 之前插入结点函数如下:
//pos 指向头结点时,需要改变头指针,这里采用传二级指针的方式 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { //pos 不能为空 assert(pos); //头插 if(*pphead == pos) { SLTPushFront(pphead, x); } else { //找到 pos 的前一个结点 SLTNode* prev = *pphead; while(prev->next != pos) { prev = prev->next; } //申请结点 SLTNode* newnode = BuySLTNode(x); newnode->next = pos; prev->next = newnode; } }
中间删除:通过后面介绍的查找函数 SLTFind 获得指向结点的指针 pos,删除 pos 指向的结点 或 后一个结点
3. 删除 pos 指向的结点的后一个结点
删除 pos 之后的结点函数如下:
void SLTEraseAfter(SLTNode* pos) { //pos 不能为空 assert(pos); //指向最后一个结点时,不做处理 if(pos->next == NULL) { return; } else { //保存后一个结点 SLTNode* next = pos->next; pos->next = next->next; free(next); } }
4. 删除 pos 指向的结点
删除 pos 指向的结点函数如下:
//pos 指向头结点时,需要改变头指针,这里采用传二级指针的方式 void SLTErase(SLTNode** pphead, SLTNode* pos) { //pos 不能为空 assert(pos); //头删 if (*pphead == pos) { SLTPopFront(pphead); } else { //找到 pos 的前一个结点 SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
6. 查找
查找:如果数据存在,返回该数据结点的指针,不存在返回 NULL
查找函数如下:
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; //查找 while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
7. 销毁单链表
在单链表中,存储数据的结点是由自己开辟的,当不使用单链表时,应将其销毁
销毁单链表函数如下:
需要将头指针置空,这里采用传二级指针的方式 void SLTDestroy(SLTNode** pphead) { SLTNode* cur = *pphead; while (cur) { //保存下一个结点 SLTNode* nextnode = cur->next; free(cur); cur = nextnode; } //将头指针置空 *pphead = NULL; }
加载全部内容