爱站小工具圣经,万能短视频素材库免费,wordpress打赏后插件,网站的建设论文目录
链表的概念
链表的相关操作#xff1a;
链表的创建#xff1a;
打印链表#xff1a;
申请新节点#xff1a;
链表的尾插#xff1a; #xff01;#xff01;#xff01;对于传参中二级指针的解释#xff1a;
链表的头插#xff1a;
链表的尾删#xff…目录
链表的概念
链表的相关操作
链表的创建
打印链表
申请新节点
链表的尾插 对于传参中二级指针的解释
链表的头插
链表的尾删
链表的头删
寻找结点
在链表的指定位置前插入
在链表的指定位置后插入
删除pos位置的结点
删除pos位置后的结点
销毁链表
最终结果
SList.h文件
SList.c文件
test.c文件 链表的概念 链表是线性表的一种它是⼀种物理存储结构上⾮连续、⾮顺序的存储结构数据元素的逻
辑顺序是通过链表中的指针链接次序实现的 。其实链表就相当于一列火车 链表的结构跟⽕⻋⻋厢相似淡季⻋厢会相应减少旺季时⻋厢会额外增加减少和增加车厢并不会影响其它车厢每节⻋厢都是独⽴存在的。且每节⻋厢都有⻋⻔。 假设每节⻋厢的⻋⻔都被锁上且打开这些车厢所需要的钥匙各不相同那么如果乘务员从第一节车厢开始向后面的车厢走去如何从⻋头⾛到⻋尾 答案每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。 而每节车厢里面肯定是有人或者货物的所以这就引申出了一条新的概念在链表⾥每节“⻋厢”是由 下一个车厢的 和 本节车厢中存储的“数据 组成的。 当你对后续的链表内容有问题请重新回来仔细观看下图 当你对后续的链表内容有问题请重新回来仔细观看上图 与顺序表不同的是链表⾥的每节⻋厢都是独⽴申请下来的空间我们称之为“ 结点/节点 ”。 结点 当前节点中保存的数据data 保存下⼀个节点地址的指针变量next 有了车厢我们就需要有一节火车头来带动这些车厢链表中的火车头就是 头结点头结点不存储数据它 指向链表的第一个有效结点存储数据的地址在这里plist就为头结点 为什么需要指针变量来保存下⼀个节点的位置 因为链表在内存空间上的存储是非连续的 就和火车车厢一样根据需求进行增加和删除通俗来讲就是用到你这块儿了我用指针火车挂钩给你连上你就得给我进链表不用你的时候把脸上你的指针火车挂钩断开你就一边闲着去。 链表的相关操作 以下链表内容为不带头单向不循环链表 链表的创建
创建链表需要经历以下操作
1、定义一个结构体来表示链表的结点SList.h文件
//定义一种链表节点的结构实际应用中有多种这里只演示最基本的结构
typedef int SLDataType; //便于切换链表中存储数据的类型
struct SListNode { SLDataType data; //存储数据struct SListNode* next; //用来保存下一个节点地址的指针变量next
};
typedef struct SListNode SLNode; //将链表结点的结构体重命名为SLNode2、编写创建链表的函数第二点这里的 内容只是为了方便理解后续内容具体情况请看下面的实际操作有个简单的了解 该函数主要进行的操作是 ①创建新节点并为其开辟内存空间 ②将新结点的next指针指向下一个结点 //申请结点函数
void slttest()
{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;node1-next node2;node2-next node3;node3-next node4;node4-next NULL;//打印链表SLNode* plist node1; SLPrint(plist);
}打印链表
//用phead表示头结点它指向链表的第一个结点如果思路出现混乱一定要再看一边前面的链表图
void SLPrint(SLNode* phead)
{ //循环打印//为了能在遍历后仍能找到刚开始的起点我们就需要利用一个临时指针pcur来存储头结点的地址SLNode* pcur phead;//当头结点不为空时进行循环while (pcur){//打印此时所处结点中的数据printf(%d -, pcur-data);//打印结束后让pcur指向下一个结点的地址pcur pcur-next;}//到最后时现有结点遍历完成空间为NULLprintf(NULL\n);
} 申请新节点
//申请有效结点函数并在该结点中存储数据
SLNode* SLByNode(SLDataType x)
{//为链表的新结点申请一个新的空间SLNode* node (SLNode*)malloc(sizeof(SLNode));//该节点中存储的数据为xnode-data x;//将该结点的下一个结点置为空因为我们也不知道它后面到底还要不要结点了node-next NULL;//返回申请的新结点return node;
}
链表的尾插
//链表的尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{//判断传入的头结点plist是否为空assert(pphead);//如果存在头结点则进行后续操作//先申请一个新的有效结点SLNode* node SLByNode(x);//如果第一个有效结点为空则令*pphead指向新创建的有效结点if (*pphead NULL){*pphead node;return;}//如果第一个有效结点不为空则通过循环读取至链表的结尾//先定义一个临时的指针变量pcur令pcur指向第一个有效结点SLNode* pcur *pphead;//然后利用pcur-next遍历至链表的末尾while (pcur-next){pcur pcur-next;}//当遍历至链表的末尾时让pcur指向新的有效结点pcur-next node;
} 对于传参中二级指针的解释
//pphead是一个二级指针通过判断它的非空情况可以得到整个链表是否存在
plist 获取的是plist这个指针的地址 pphead//对于pphead的解引用
plist头结点的地址 *pphead
如果第一个结点为空那么该结点的地址为空//对于*pphead的解引用得到头节点中的地址
*plist第一个结点的内存块 **pphead链表的头插
//链表的头插
void SLPushFront(SLNode** pphead, SLDataType x)//相当于两个互相赋值
{//判断传入的头结点plist是否为空assert(pphead);SLNode* node SLByNode(x);//下面两条进行的其实就是简单的交接工作//先将当前头指针指向的结点交给了node-nextnode-next *pphead;//然后让头指针指向新节点的地址*pphead node;
} 链表的尾删
//链表的尾删链表为空的情况下不能尾删
void SLPopBack(SLNode** pphead)
{ //判断传入的头结点plist是否为空assert(pphead);//判断第一个有效结点是否为空链表为空不能进行尾删assert(*pphead);//当有且只有一个有效结点时if ((*pphead)-next NULL){free(*pphead)*pphead NULL;}else{//当不止一个有效结点时//未防止删除后空指针的出现在寻找尾节点的时候我们也要找到尾节点的前一个节点//找尾结点和尾结点的前一个结点//定义prev为尾结点的前一个结点SLNode* prev NULL;//定义ptai为用于找尾结点的指针先让它接收第一个有效结点的地址SLNode* ptail *pphead;while (ptail-next ! NULL){//先令prev将ptail保存下来当ptail-next为空时此时到达尾指针就不会进入循环将ptail //存入prev中此时prev保存的就是尾结点的前一个结点prev ptail;ptail ptail-next;}//此时prev尾结点的前一个结点的next指针不再指向ptail尾结点而是指向ptail的下一个结点prev-next ptail-next;free(ptail);ptail NULL;}
} 链表的头删
//链表的头删
void SLPopPront(SLNode** pphead)
{//判断传入的头结点plist是否为空assert(pphead);//判断第一个有效结点是否为空链表为空不能进行尾删assert(*pphead);//当有且只有一个有效结点时if ((*pphead)-next NULL){//直接把头结点删除free(*pphead);*pphead NULL;}//当整个链表//使用临时指针指向头结点SLNode* del *pphead;//令头结点指向新的头结点*pphead (*pphead)-next;//将临时指针指向的结点头结点释放掉free(del);del NULL;
}
寻找结点
//查找结点
SLNode* SLFind(SLNode** pphead, SLDataType x)
{//判断传入的头结点plist是否为空assert(pphead);SLNode* pcur *pphead;while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}//该函数需要与在指定位置插入删除结合返回的结果使用一个指针来接收在test.c文件中的使用情况如下
SLNode* find SLFind(plist,2);//查找数据为2的结点
SLInsert(plist,find,x)//在find数据为2的结点前插入含有数据x的新节点 在完成以下代码后需要考虑的三种情况 1、pos是头结点 2、pos是中间结点 3、pos是最后一个结点 在链表的指定位置前插入
//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{//判断传入的头结点plist是否为空assert(pphead);//约定链表不能为空pos也不能为空assert(pos);assert(*pphead);SLNode* node SLByNode(x);//有且只有一个有效结点此时在该有效结点前进行插入操作就相当于头插if(pos *pphead){node-next *pphead;*pphead node;return;}//当不只有一个有效结点的时候先通过循环找到pos的前一个结点SLNode* prev *pphead; //当prev-next指向pos的时候跳出循环while (prev-next ! pos){prev prev-next;}//此时循环结束prev指向pos//最后处理插入位置两边的结点与新结点三者之间的关系prve node pos//此时下面的两个操作顺序可以交换node-next pos;prev-next node;
} 在链表的指定位置后插入
//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x)
{//确定能找到该结点assert(pos);SLNode* node SLByNode(x);//pos node pos-nextnode-next pos-next;pos-next pos;
}//使用案例
//SLNode* find SLFind(plist,1);
//SLInsertAfter(find,100);
删除pos位置的结点
//删除pos结点
void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//当pos为第一个有效结点时if (pos *pphead){*pphead (*pphead)-next;free(pos);return;}//当pos不为第一个有效结点时//先找到pos的前一个结点然后后续内容与之前的操作类似SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//先完成pos两边结点的交接工作然后再释放pos结点prev-next pos-next;free(pos);pos NULL;
} 删除pos位置后的结点
//删除pos结点之后的数据
void SLEraseAfter(SLNode* pos)
{//除了pos不为空以外还需要pos-next不为空因为pos刚好是最后一个结点你总不能删除一个NULLassert(pos pos-next);SLNode* del pos-next;pos-next del-next;free(del);
}销毁链表
//销毁链表
void SLDestroy(SLNode** pphead)
{assert(pphead);SLNode* pcur *pphead;//循环删除while (pcur){SLNode* next pcur-next;free(pcur);pcur next;}//此时链表所有的有效结点已经结束了最后将头结点置为空即可*pphead NULL;
}
最终结果
SList.h文件
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h//定义链表节点的结构
typedef int SLDataType;
struct SListNode { //定义一个表示链表节点的结构体SLDataType data; //链表中用于存储数据的成员某个节点的数据struct SListNode* next; //用来保存下一个节点地址的指针变量next
};
typedef struct SListNode SLNode; //将指向下一个节点的指针类型重命名为SLNode//创建几个结点组成的链表并打印链表
void SLPrint(SLNode* phead);
//链表的尾插
void SLPushBack(SLNode** phead, SLDataType x);
//链表的头插
void SLPushFront(SLNode** phead, SLDataType x);
//链表的尾删
void SLPopBack(SLNode** pphead);
//链表的头删
void SLPopPront(SLNode** pphead);
//找结点,这里传一级指针实际上就可以了因为不改变头节点但是这里还是要写成二级指针因为要保证接口一致性
SLNode* SLFind(SLNode** pphead,SLDataType x);//链表的在指定位置之前插入
void SLInsert(SLNode** phead, SLNode* pos,SLDataType x);
//链表的指定位置删除
void SLInsertAfter(SLNode* pos, SLDataType x);//此时不需要第一个参数
//删除pos位置的结点
void SLErase(SLNode** pphead, SLNode* pos);
//删除pos后的结点
void SLEraseAfter(SLNode* pos);
//销毁链表
void SLDestroy(SLNode** pphead);
SList.c文件
#include SList.h
//用phead表示头结点它指向链表的第一个结点如果思路出现混乱一定要再看一边前面的链表图
void SLPrint(SLNode* phead)
{//循环打印//为了能在遍历后仍能找到刚开始的起点我们就需要利用一个临时指针pcur来存储头结点的地址SLNode* pcur phead;//当头结点不为空时进行循环while (pcur){//打印此时所处结点中的数据printf(%d -, pcur-data);//打印结束后让pcur指向下一个结点的地址pcur pcur-next;}//到最后时现有结点遍历完成空间为NULLprintf(NULL\n);
}//申请有效结点函数并在该结点中存储数据
SLNode* SLByNode(SLDataType x)
{//为链表的新结点申请一个新的空间SLNode* node (SLNode*)malloc(sizeof(SLNode));//该节点中存储的数据为xnode-data x;//将该结点的下一个结点置为空因为我们也不知道它后面到底还要不要结点了node-next NULL;//返回申请的新结点return node;
}//链表的尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{//判断传入的头结点plist是否为空assert(pphead);//如果存在头结点则进行后续操作//先申请一个新的有效结点SLNode* node SLByNode(x);//如果第一个有效结点为空则令*pphead指向新创建的有效结点if (*pphead NULL){*pphead node;return;}//如果第一个有效结点不为空则通过循环读取至链表的结尾//先定义一个临时的指针变量pcur令pcur指向第一个有效结点SLNode* pcur *pphead;//然后利用pcur-next遍历至链表的末尾while (pcur-next){pcur pcur-next;}//当遍历至链表的末尾时让pcur指向新的有效结点pcur-next node;
}//链表的头插
void SLPushFront(SLNode** pphead, SLDataType x)//相当于两个互相赋值
{//判断传入的头结点plist是否为空assert(pphead);SLNode* node SLByNode(x);//下面两条进行的其实就是简单的交接工作//先将当前头指针指向的结点交给了node-nextnode-next *pphead;//然后让头指针指向新节点的地址*pphead node;
}//链表的尾删链表为空的情况下不能尾删
void SLPopBack(SLNode** pphead)
{//判断传入的头结点plist是否为空assert(pphead);//判断第一个有效结点是否为空链表为空不能进行尾删assert(*pphead);//当有且只有一个有效结点时if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}//当不止一个有效结点时//未防止删除后空指针的出现在寻找尾节点的时候我们也要找到尾节点的前一个节点//找尾结点和尾结点的前一个结点//定义prev为尾结点的前一个结点else{SLNode* prev NULL;//定义ptai为用于找尾结点的指针先让它接收第一个有效结点的地址SLNode* ptail *pphead;while (ptail-next ! NULL){//先令prev将ptail保存下来当ptail-next为空时此时到达尾指针就不会进入循环将ptail //存入prev中此时prev保存的就是尾结点的前一个结点prev ptail;ptail ptail-next;}//此时prev尾结点的前一个结点的next指针不再指向ptail尾结点而是指向ptail的下一个结点prev-next ptail-next;free(ptail);ptail NULL;}
}//链表的头删
void SLPopPront(SLNode** pphead)
{//判断传入的头结点plist是否为空assert(pphead);//判断第一个有效结点是否为空链表为空不能进行尾删assert(*pphead);//当有且只有一个有效结点时if ((*pphead)-next NULL){//直接把头结点删除free(*pphead);*pphead NULL;}//当整个链表//使用临时指针指向头结点SLNode* del *pphead;//令头结点指向新的头结点*pphead (*pphead)-next;//将临时指针指向的结点头结点释放掉free(del);del NULL;
}//查找结点
SLNode* SLFind(SLNode** pphead, SLDataType x)
{//判断传入的头结点plist是否为空assert(pphead);SLNode* pcur *pphead;while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}
//
该函数需要与在指定位置插入删除结合返回的结果使用一个指针来接收在test.c文件中的使用情况如下
//SLNode* find SLFind(plist, 2);//查找数据为2的结点
//SLInsert(plist, find, x)//在find数据为2的结点前插入含有数据x的新节点//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{//判断传入的头结点plist是否为空assert(pphead);//约定链表不能为空pos也不能为空assert(pos);assert(*pphead);SLNode* node SLByNode(x);//有且只有一个有效结点此时在该有效结点前进行插入操作就相当于头插if (pos *pphead){node-next *pphead;*pphead node;return;}//当不只有一个有效结点的时候先通过循环找到pos的前一个结点SLNode* prev *pphead;//当prev-next指向pos的时候跳出循环while (prev-next ! pos){prev prev-next;}//此时循环结束prev指向pos//最后处理插入位置两边的结点与新结点三者之间的关系prve node pos//此时下面的两个操作顺序可以交换node-next pos;prev-next node;
}//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x)
{//确定能找到该结点assert(pos);SLNode* node SLByNode(x);//pos node pos-nextnode-next pos-next;pos-next pos;
}//使用案例
//SLNode* find SLFind(plist,1);
//SLInsertAfter(find,100);//删除pos结点
void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//当pos为第一个有效结点时if (pos *pphead){*pphead (*pphead)-next;free(pos);return;}//当pos不为第一个有效结点时//先找到pos的前一个结点然后后续内容与之前的操作类似SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//先完成pos两边结点的交接工作然后再释放pos结点prev-next pos-next;free(pos);pos NULL;
}//销毁链表
void SLDestroy(SLNode** pphead)
{assert(pphead);SLNode* pcur *pphead;//循环删除while (pcur){SLNode* next pcur-next;free(pcur);pcur next;}//此时链表所有的有效结点已经结束了最后将头结点置为空即可*pphead NULL;
}
test.c文件
#include SList.h
//申请结点函数
//void slttest()
//{
// //使用malloc函数动态分配创建链表的头节点它不包含任何数据知识用来指向链表的第一个实际节点
// SLNode* node1 (SLNode*)malloc(sizeof(SLNode));
// //head
// 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;
//
// //实现四个节点的链接
// //初始化头节点的next指针为node2指针变量
// node1-next node2;
// node2-next node3;
// node3-next node4;
// node4-next NULL;
//
// //打印链表
// SLNode* plist node1; //定义一个SLNode*类型的指针变量plist他也叫头指针我们用它指向链表的头节点
//
// //注意头节点和头指针的概念是不同的
// /*在链表的上下文中通常将链表的第一个节点称为头节点Head Node但是头节点和头指针Head Pointer是不同的概念。
// 头节点是链表中的第一个实际节点它包含数据和指向下一个节点的指针。头节点是链表的起始点它可以存储实际的数据也可以只是一个占位符节点不存储实际的数据。
// 头指针是指向链表的头节点的指针。它是一个指针变量存储着头节点的地址。通过头指针我们可以访问链表中的每个节点或者进行其他链表操作。
// 因此头节点是链表中的一个节点而头指针是指向头节点的指针。它们是不同的概念但在某些情况下人们可能会将它们混用或将它们视为相同的概念因为头节点通常通过头指针来访问。*/
//
// SLNPrint(plist);
//}void slttest()
{SLNode* plist NULL; //尾插SLPushBack(plist, 1); SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);//1-2-3-4-NULLSLPrint(plist);头插//SLPushFront(plist, 1);//SLPushFront(plist, 2);//SLPushFront(plist, 3);//SLPushFront(plist, 4);//4-3-2-1-NULL//SLPrint(plist);//尾删SLPopBack(plist);SLPopBack(plist);SLPopBack(plist);头删//SLPopPront(plist);//SLPopPront(plist);//SLPopPront(plist);//SLPopPront(plist);//SLPopPront(plist);//SLPopPront(plist);指定位置插入//SLNode* find SLFind(plist, 4);//SLInsert(plist, find,11);//1-11-2-3-4-NULL在指定位置之后插入数据//SLInsertAfter(find, 100);删除pos位置的节点//SLErase(plist, find);//1-2-3-NULL删除pos之后的节点//SLEraseAfter(find);////销毁链表//SLDestory(plist);//检验是否成功销毁SLPrint(plist);
}int main()
{slttest();return 0;
} 注意事项 1、判断条件的等号都是 2、冒号是否写了 3、函数或者指针变量的名字是否书写正确 4、最后的test.c文件实验时可能会存在一些多删之类的问题函数写多了请自行检查~ 如果还有其它你编写时出现的错误也可以说一下~
~over~
