想搭网站做软件首先要学设么,wordpress 主题切换,网络推广培训机构,中国建设公司排名目录
1. 链表的概念及结构#x1f451;
1.1 什么是链表#xff1f;#x1f440;
1.2 为什么需要链表#xff1f;⁉️
1.3 链表的结构是怎么样的#xff1f;❓
2. 链表的分类#x1f99c;
3. 实现单链表#x1faf5;
3.1 要实现的目标#x1f3af;… 目录
1. 链表的概念及结构
1.1 什么是链表
1.2 为什么需要链表⁉️
1.3 链表的结构是怎么样的❓
2. 链表的分类
3. 实现单链表
3.1 要实现的目标
3.2 创建打印
3.2.1 SList.h
3.2.2 SList.c
3.2.3 test.c
3.2.4 代码运行测试 3.3 尾插
3.3.0 尾插思路分析
3.3.1 SList.h
3.3.2 SList.c
3.3.3 test.c
3.3.4 代码运行测试
3.4 头插
3.4.0 头插思路分析
3.4.1 SList.h
3.4.2 SList.c
3.4.3 test.c
3.4.4 代码运行测试
3.5 尾删
3.5.0 尾删思路分析
3.5.1 SList.h
3.5.2 SList.c
3.5.3 test.c
3.5.4 代码运行测
3.6 头删
3.6.0 头删思路分析
3.6.1 SList.h
3.6.2 SList.c
3.6.3 test.c
3.6.4 代码运行测试
3.7 指定节点之前/之后插入节点查找指定位置的数据
3.7.0 指定节点之前/之后插入节点思路分析
3.7.1 SList.h
3.7.2 SList.c
3.7.3 test.c
3.7.4 代码运行测试
3.8 删除pos节点or pos节点之后的节点 3.8.0 删除pos节点or pos节点之后的节点思路分析
3.8.1 SList.h
3.8.2 SList.c
3.8.3 test.c
3.8.4 代码运行测试
3.9 销毁
3.9.0 销毁思路分析
3.9.1 SList.h
3.9.2 SList.c
3.9.3 test.c
3.9.4 代码运行测试 1. 链表的概念及结构
1.1 什么是链表 通过顺序表的学习我们对线性表和顺序表有了一定的了解 其实链表也是线性表的一种链表逻辑上连续物理上不连续地址不连续这一点是和顺序表不同的 为了方便大家具像化理解我们以火车车厢举例 我们发现车厢独立的---可以任意增加or减少but不影响其他车厢是逻辑上连续的排列的但是车厢编号物理上不一定连续排列 假设每节⻋厢的⻋⻔都是锁上的状态需要不同的钥匙才能解锁每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾 最简单的做法每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。 那么链表我们这里特指单链表中的“车厢”是怎样的呢 与顺序表不同的是链表⾥的每节⻋厢都是独⽴申请的空间可能连续也可能不连续我们称之为“结点/节点” 节点的组成主要有两个部分当前节点要保存的数据和保存下⼀个节点的地址指针变量 注意⚠️ 我们这里特指的是单链表所以如图所示当到尾节点的时候尾节点后面没有节点了所以地址为空即指向NULL 1.2 为什么需要链表⁉️ 我们在顺序表的应用那一篇博客提及到了顺序表的思考 1.链表申请的空间都是独立的需要几个我们就申请几个不会造成浪费或者申请空间不够 2.拷贝数据的时候也不需要释放旧空间 3.中间/头部的插入删除只需要修改指针的指向效率较高 ............ 1.3 链表的结构是怎么样的❓
结合前⾯学到的结构体知识我们可以给出每个节点对应的结构体代码
假设当前保存的节点为整型:
struct SListNode
{int data; //节点数据struct SListNode* next; //指针变量⽤保存下⼀个节点的地址
}; 2. 链表的分类 1.单向一个方向---向后链接 2.双向两个方向---前后都可以链接我们下下期会讲 3.带头类似于哨兵位不保存有效数据只是标识一个头哨兵位不能为空也不能改变 4.不带头没有哨兵位第一个节点保存有效数据和下一个节点的地址为了方便我们下面在实现单链表的时候会把第一个节点直接叫作“头节点”但是和哨兵位所指代的头节点不一样 5.循环尾节点不指向NULL而是指向头节点带头or第一个节点不带头的地址使头尾相连---循环♻️ 6.不循环尾节点指向NULL 链表的结构⾮常多样以下情况组合起来就有8种2 x 2 x 2链表结构 但是这么多种链表我们最常用的是单向不带头不循环链表我们接下来简称单链表和双向带头循环链表我们下下期讲的时候简称双链表 3. 实现单链表
3.1 要实现的目标 和顺序表一样我们需要源文件和头文件来实现也需要实现多个接口方便使用也可以为下期的单链表实现通讯录做准备 我们需要多个接口帮助我们实现创建、一系列具体操作、销毁 具体操作一切以实现通讯录为目标包括头部/尾部插入数据、头部/尾部删除数据、打印出单链表、指定节点之后/之前插入节点、删除指定节点之后的节点、查找指定节点 3.2 创建打印
3.2.1 SList.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
#includestring.h//定义单链表节点的结构体(创建
typedef int SLDataType;
typedef struct SListNode
{SLDataType data;//要保存的数据struct SListNode* next;//存储下一个节点的地址
}SlNode;//打印
void SLPrint(SLNode* phead); 3.2.2 SList.c
#includeSList.h
//打印
void SLPrint(SlNode* phead)
{//循环打印SlNode* pcur phead;//pcur从头节点开始遍历链表//不用phead遍历---以后需要用到指向头节点的地址时帮助我找到地址while (pcur)//pcur指向NULL的时候结束遍历{printf(%d-, pcur-data);pcur pcur-next;//pcur指向下一个节点继续遍历}printf(NULL\n);
} 3.2.3 test.c
#includeSList.h
void SLTest()
{//创建节点---申请空间//存储有效数据SlNode* node1 (SlNode*)malloc(sizeof(SlNode));node1-data 1;SlNode* node2 (SlNode*)malloc(sizeof(SlNode));node2-data 2;SlNode* node3 (SlNode*)malloc(sizeof(SlNode));node3-data 3;SlNode* node4 (SlNode*)malloc(sizeof(SlNode));node4-data 4;SlNode* node5 (SlNode*)malloc(sizeof(SlNode));node5-data 5;//存储下一个节点的地址node1-next node2;node2-next node3;node3-next node4;node4-next node5;node5-next NULL;//单向不带头不循环链表//打印SlNode* plist node1;SLPrint(plist);
}
int main()
{SLTest();return 0;
} 3.2.4 代码运行测试 3.3 尾插
3.3.0 尾插思路分析 3.3.1 SList.h
//尾插
void SLPushBack(SlNode** pphead, SLDataType x);//一级指针要二级指针接受才可以改变形参 3.3.2 SList.c
//插入数据都需要创建空间---我们单独写出来避免重复多次
SlNode* SLBuyNNode(SLDataType x)
{SlNode* node (SlNode*)malloc(sizeof(SlNode));if (node NULL){perror(malloc);return 1;}node-data x;node-next NULL;return node;
}
//尾插
void SLPushBack(SlNode** pphead, SLDataType x)//一级指针要二级指针接受才可以改变
{//传过来的指针不能为空assert(pphead);SlNode* node SLBuyNNode(x);//链表为空,直接插入if (*pphead NULL){*pphead node;return 1;}//到这说明不为空遍历SlNode* pcur *pphead;while (pcur-next){pcur pcur-next;}pcur-next node;
} 3.3.3 test.c
#includeSList.h
void SLTest()
{//创建节点---申请空间//存储有效数据SlNode* node1 (SlNode*)malloc(sizeof(SlNode));node1-data 1;SlNode* node2 (SlNode*)malloc(sizeof(SlNode));node2-data 2;SlNode* node3 (SlNode*)malloc(sizeof(SlNode));node3-data 3;SlNode* node4 (SlNode*)malloc(sizeof(SlNode));node4-data 4;SlNode* node5 (SlNode*)malloc(sizeof(SlNode));node5-data 5;//存储下一个节点的地址node1-next node2;node2-next node3;node3-next node4;node4-next node5;node5-next NULL;//单向不带头不循环链表//打印SlNode* plist node1;SLPrint(plist);
}
void SLTest01()
{SlNode* plist NULL;//尾插SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPrint(plist);
}
int main()
{SLTest();SLTest01();return 0;
} 3.3.4 代码运行测试 3.4 头插
3.4.0 头插思路分析 3.4.1 SList.h
//头插
void SLPushFront(SlNode** pphead, SLDataType x);//一级指针要二级指针接受才可以改变形参 3.4.2 SList.c
//头插
void SLPushFront(SlNode** pphead, SLDataType x)//一级指针要二级指针接受才可以改变形参
{//传过来的指针不能为空assert(pphead);SlNode* node SLBuyNNode(x);//新节点和原来的头节点链接node-next *pphead;//新节点成为新的头节点*pphead node;
} 3.4.3 test.c
#includeSList.h
void SLTest()
{//创建节点---申请空间//存储有效数据SlNode* node1 (SlNode*)malloc(sizeof(SlNode));node1-data 1;SlNode* node2 (SlNode*)malloc(sizeof(SlNode));node2-data 2;SlNode* node3 (SlNode*)malloc(sizeof(SlNode));node3-data 3;SlNode* node4 (SlNode*)malloc(sizeof(SlNode));node4-data 4;SlNode* node5 (SlNode*)malloc(sizeof(SlNode));node5-data 5;//存储下一个节点的地址node1-next node2;node2-next node3;node3-next node4;node4-next node5;node5-next NULL;//单向不带头不循环链表//打印SlNode* plist node1;SLPrint(plist);
}
void SLTest01()
{SlNode* plist NULL;//尾插SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPrint(plist);//头插SLPushFront(plist, 5);SLPrint(plist);
}
int main()
{SLTest();SLTest01();return 0;
} 3.4.4 代码运行测试 3.5 尾删
3.5.0 尾删思路分析 3.5.1 SList.h
//尾删
void SLPopBack(SlNode** pphead); 3.5.2 SList.c
///尾删
void SLPopBack(SlNode** pphead)
{assert(pphead*pphead);//只有1个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}//多个节点else{SlNode* prev NULL;SlNode* ptail *pphead;while (prev-next ! NULL){prev ptail;ptail ptail-next;}prev-next ptail-next;free(ptail);ptail NULL;}
} 3.5.3 test.c
#includeSList.h
void SLTest()
{//创建节点---申请空间//存储有效数据SlNode* node1 (SlNode*)malloc(sizeof(SlNode));node1-data 1;SlNode* node2 (SlNode*)malloc(sizeof(SlNode));node2-data 2;SlNode* node3 (SlNode*)malloc(sizeof(SlNode));node3-data 3;SlNode* node4 (SlNode*)malloc(sizeof(SlNode));node4-data 4;SlNode* node5 (SlNode*)malloc(sizeof(SlNode));node5-data 5;//存储下一个节点的地址node1-next node2;node2-next node3;node3-next node4;node4-next node5;node5-next NULL;//单向不带头不循环链表//打印SlNode* plist node1;SLPrint(plist);
}
void SLTest01()
{SlNode* plist NULL;//尾插SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPrint(plist);//头插SLPushFront(plist, 5);SLPrint(plist);//尾删SLPopBack(plist);SLPrint(plist);
}
int main()
{SLTest();SLTest01();return 0;
} 3.5.4 代码运行测 3.6 头删
3.6.0 头删思路分析 3.6.1 SList.h
//头删
void SLPopFront(SlNode** pphead); 3.6.2 SList.c
//头删
void SLPopFront(SlNode** pphead)
{assert(pphead*pphead);SlNode* del *pphead;*pphead (*pphead)-next;free(del);del NULL;
} 3.6.3 test.c
#includeSList.h
void SLTest()
{//创建节点---申请空间//存储有效数据SlNode* node1 (SlNode*)malloc(sizeof(SlNode));node1-data 1;SlNode* node2 (SlNode*)malloc(sizeof(SlNode));node2-data 2;SlNode* node3 (SlNode*)malloc(sizeof(SlNode));node3-data 3;SlNode* node4 (SlNode*)malloc(sizeof(SlNode));node4-data 4;SlNode* node5 (SlNode*)malloc(sizeof(SlNode));node5-data 5;//存储下一个节点的地址node1-next node2;node2-next node3;node3-next node4;node4-next node5;node5-next NULL;//单向不带头不循环链表//打印SlNode* plist node1;SLPrint(plist);
}
void SLTest01()
{SlNode* plist NULL;//尾插SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPrint(plist);//头插SLPushFront(plist, 5);SLPrint(plist);//尾删SLPopBack(plist);SLPrint(plist);//头删SLPopFront(plist);SLPrint(plist);
}
int main()
{SLTest();SLTest01();return 0;
} 3.6.4 代码运行测试 3.7 指定节点之前/之后插入节点查找指定位置的数据
3.7.0 指定节点之前/之后插入节点思路分析 3.7.1 SList.h
//查找数据
SlNode* SLFind(SlNode** pphead, SLDataType x);//指定位置之前插入
void SLInsert(SlNode** pphead,SlNode* pos, SLDataType x);//指定位置之后插入
void SLInsertAfter(SlNode* pos, SLDataType x); 3.7.2 SList.c
//查找数据
SlNode* SLFind(SlNode** pphead, SLDataType x)
{assert(pphead);SlNode* pcur *pphead;while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}//指定位置之前插入
void SLInsert(SlNode** pphead, SlNode* pos, SLDataType x)
{assert(pphead *ppheadpos);//创建空间SlNode* node SLBuyNode(x);//pos为第一个节点(只有1个节点)if (pos (*pphead)){node-next *pphead;*pphead node;return 1;}//pos不为第一个节点//找pos节点的前一个节点SlNode* prev *pphead;while (prev-next ! pos){prev prev-next;}node-next pos;prev-next node;
}
//指定位置之后插入
void SLInsertAfter(SlNode* pos, SLDataType x)
{assert(pos);//创建空间SlNode* node SLBuyNNode(x);node-next pos-next;pos-next node;
} 3.7.3 test.c
#includeSList.h
void SLTest()
{//创建节点---申请空间//存储有效数据SlNode* node1 (SlNode*)malloc(sizeof(SlNode));node1-data 1;SlNode* node2 (SlNode*)malloc(sizeof(SlNode));node2-data 2;SlNode* node3 (SlNode*)malloc(sizeof(SlNode));node3-data 3;SlNode* node4 (SlNode*)malloc(sizeof(SlNode));node4-data 4;SlNode* node5 (SlNode*)malloc(sizeof(SlNode));node5-data 5;//存储下一个节点的地址node1-next node2;node2-next node3;node3-next node4;node4-next node5;node5-next NULL;//单向不带头不循环链表//打印SlNode* plist node1;SLPrint(plist);
}
void SLTest01()
{SlNode* plist NULL;//尾插SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPrint(plist);//头插SLPushFront(plist, 5);SLPrint(plist);//尾删SLPopBack(plist);SLPrint(plist);//头删SLPopFront(plist);SLPrint(plist);//pos之前插入SlNode* find SLFind(plist, 2);SLInsert(plist, find, 6);SLPrint(plist);//pos之后插入SlNode* find SLFind(plist, 3);SLInsertAfter(find, 7);SLPrint(plist);
}
int main()
{SLTest();SLTest01();return 0;
} 3.7.4 代码运行测试 3.8 删除pos节点or pos节点之后的节点 3.8.0 删除pos节点or pos节点之后的节点思路分析 3.8.1 SList.h
//删除pos节点
void SLErase(SlNode** pphead, SlNode* pos);//删除pos节点之后的节点
void SLEraseAfter(SlNode* pos); 3.8.2 SList.c
//删除pos节点
void SLErase(SlNode** pphead, SlNode* pos)
{assert(pphead *pphead pos);//pos是第一个节点if (pos(*pphead)){*pphead (*pphead)-next;free(pos);return 1;}//pos不是第一个节点SlNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;//出于规范
}
//删除pos节点之后的节点
void SLEraseAfter(SlNode* pos)
{//尾节点不行空指针也不行assert(pospos-next);SlNode* del pos-next;pos-next del-next;free(del);
} 3.8.3 test.c
#includeSList.h
void SLTest()
{//创建节点---申请空间//存储有效数据SlNode* node1 (SlNode*)malloc(sizeof(SlNode));node1-data 1;SlNode* node2 (SlNode*)malloc(sizeof(SlNode));node2-data 2;SlNode* node3 (SlNode*)malloc(sizeof(SlNode));node3-data 3;SlNode* node4 (SlNode*)malloc(sizeof(SlNode));node4-data 4;SlNode* node5 (SlNode*)malloc(sizeof(SlNode));node5-data 5;//存储下一个节点的地址node1-next node2;node2-next node3;node3-next node4;node4-next node5;node5-next NULL;//单向不带头不循环链表//打印SlNode* plist node1;SLPrint(plist);
}
void SLTest01()
{SlNode* plist NULL;//尾插SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPrint(plist);//头插SLPushFront(plist, 5);SLPrint(plist);//尾删SLPopBack(plist);SLPrint(plist);//头删SLPopFront(plist);SLPrint(plist);//pos之前插入SlNode* find SLFind(plist, 2);//SLInsert(plist, find, 6);//SLPrint(plist);pos之后插入//SlNode* find SLFind(plist, 3);//SLInsertAfter( find, 7);//SLPrint(plist);//删除pos节点/*SLErase(plist, find);SLPrint(plist);*///删除pos之后SLEraseAfter(find);SLPrint(plist);
}
int main()
{SLTest();SLTest01();return 0;
} 3.8.4 代码运行测试 3.9 销毁
3.9.0 销毁思路分析 3.9.1 SList.h
//销毁
void SLDesTroy(SlNode** pphead); 3.9.2 SList.c
//销毁
void SLDesTroy(SlNode** pphead)
{assert(pphead);SlNode* pcur *pphead;while (pcur)//注意如果是pcur-next那么循环将结束于尾节点没有free的时候{SlNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
} 3.9.3 test.c
#includeSList.h
void SLTest()
{//创建节点---申请空间//存储有效数据SlNode* node1 (SlNode*)malloc(sizeof(SlNode));node1-data 1;SlNode* node2 (SlNode*)malloc(sizeof(SlNode));node2-data 2;SlNode* node3 (SlNode*)malloc(sizeof(SlNode));node3-data 3;SlNode* node4 (SlNode*)malloc(sizeof(SlNode));node4-data 4;SlNode* node5 (SlNode*)malloc(sizeof(SlNode));node5-data 5;//存储下一个节点的地址node1-next node2;node2-next node3;node3-next node4;node4-next node5;node5-next NULL;//单向不带头不循环链表//打印SlNode* plist node1;SLPrint(plist);
}
void SLTest01()
{SlNode* plist NULL;//尾插SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPrint(plist);//头插SLPushFront(plist, 5);SLPrint(plist);//尾删SLPopBack(plist);SLPrint(plist);//头删SLPopFront(plist);SLPrint(plist);//pos之前插入SlNode* find SLFind(plist, 2);//SLInsert(plist, find, 6);//SLPrint(plist);pos之后插入//SlNode* find SLFind(plist, 3);//SLInsertAfter( find, 7);//SLPrint(plist);//删除pos节点/*SLErase(plist, find);SLPrint(plist);*///删除pos之后SLEraseAfter(find);SLPrint(plist);//销毁SLDesTroy(plist);SLPrint(plist);
}
int main()
{SLTest();SLTest01();return 0;
} 3.9.4 代码运行测试 本次的分享到这里就结束了
PS小江目前只是个新手小白。欢迎大家在评论区讨论哦有问题也可以讨论的
如果对你有帮助的话记得点赞收藏⭐️关注➕
