深圳建网站信科,南京医院网站建设,wordpress 自定义筛选,捕鱼网站怎么做找往期文章包括但不限于本期文章中不懂的知识点#xff1a; 个人主页#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏#xff1a;数据结构 目录
链表的概念及结构
链表与顺序表的区别与优劣势
链表的分类
单链表的实现
单链表中增加节点
单链表中尾插数据
打印单链… 找往期文章包括但不限于本期文章中不懂的知识点 个人主页我要学编程(ಥ_ಥ)-CSDN博客 所属专栏数据结构 目录
链表的概念及结构
链表与顺序表的区别与优劣势
链表的分类
单链表的实现
单链表中增加节点
单链表中尾插数据
打印单链表中节点的数据
单链表中头插数据
单链表中查找数据
单链表中尾删数据
单链表中头删数据
单链表中在指定位置之前插入数据
单链表中在指定位置之后插入数据
单链表中删除pos节点的位置
单链表中删除pos节点之后的位置
销毁链表
单链表源码 数据结构之顺序表的相关知识点及应用-CSDN博客
在前文顺序表中我们学习了什么是线性表以及线性表中的顺序表最后我们也是实现了顺序表。接下来就开始学习线性表的另一种——链表。
链表的概念及结构
概念链表是一种物理存储结构上非连续、非顺序的逻辑结构上是连续的。而数据中元素的逻辑顺序是通过链表中的指针链接次序实现的。也就是通过指针链接起来是线性的。
链表的结构跟火车车厢是类似的当人少或者非节假日时车次的车厢会相应减少当人多或者节假日时车次的车厢会额外增加。只需要将火车的某节车厢去掉或者加上不会影响其他车厢每节车厢都是独立存在的且每节车厢都有车门。想象一下假设每节车厢的车门都是被锁上的需要不同的钥匙才能解锁每次只能携带一把钥匙的情况下如何从车头走到车尾 最简单的做法每节车厢里都放一把下一节车厢的钥匙。下面就是火车和链表的具体图示 与顺序表不同的是链表里的每节“车厢”都是独立申请下来的空间我们称之为“结点/节点” 。节点的组成主要有两个部分当前节点要保存的数据和保存下一个节点的地址指针变量。 图中指针变量 plist 保存的是第一个节点的地址我们称 plist 此时指向第一个节点如果我们希望plist指向第二个节点时只需要把plist保存的内容修改为0x0012FFA0。 为什么还需要指针变量来保存下一个节点的位置 因为链表中每个节点都是独立申请的即需要插入数据时才去申请一块节点的空间我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。 结合前面学到的结构体知识我们可以给出每个节点对应的结构体代码 假设当前保存的节点为整型
struct SListNode
{int data; //节点想保存的数据struct SListNode* next; //指向下一个节点的指针
};
当我们想要保存一个整型数据时实际是向操作系统申请了一块内存这个内存不仅要保存整型数 据也需要保存下一个节点的地址当下一个节点为空时即该节点为最后一个节点时保存的地址为空。 当我们想要从第一个节点走到最后一个节点时只需要在前一个节点拿到下一个节点的地址下一个节点的钥匙就可以了。
链表与顺序表的区别与优劣势
顺序表的优势顺序表可以随机访问其中的元素而链表不可以。就是因为顺序表的底层是数组而数组是可以通过下标达到随机访问的目的。而链表只能通过指针去遍历访问。
链表的优势插入或者删除数据时不需要移动其它元素不需要开辟过多的空间按需所给即用多少给多少不会浪费空间。
链表的分类
链表根据是否带头单双向是否循环分为八大类。
重点有两个单链表和双链表。
单链表不带头单向不循环链表双链表带头双向循环链表。
头指的是头节点也叫做哨兵位。头节点中存放的是无效信息只是一个哨兵的作用。
注意头节点在单链表中不存在只是为了更好的理解才引用了这个。
单向是指
双向是指
从前一个节点指向后一个节点例如1-2的指针被称为后继指针。
从后一个节点指向前一个节点例如2-1的指针被称为前驱指针。
循环是指链表是否成环。 单链表的实现
接下来我们就开始用单链表实现对数据的增加查找删除。
在创建单链表之前要做一些提前准备。创建3个文件SList.h SList.c test.c 前面两个是实现单链表的而后面的test.c文件是测试单链表的各种功能。链表是由一个个的节点串联组成的。
创建节点
typedef int SLTDataType;//创建一个节点
typedef struct SListNode
{SLTDataType data;struct SListNode* next;//注意这里不能写重命名之后的
}SListNode;
其实这个链表不需要初始化因为我们的空间都是按需所给的不存在没有用到的空间。
单链表中增加节点
接下来就是要开始增加数据了在增加数据之前首先得有空间节点因此我们就先得写申请空间的函数以后增加数据都得用到因此就封装成函数。这里不需要判断空间是否充足。
增加节点并初始化节点
//增加节点(空间)
SListNode* SLTBuyNode(SLTDataType x)
{//开辟一个节点的空间SListNode* newnode (SListNode*)malloc(sizeof(SListNode));//判断是否开辟成功if (newnode NULL)//失败{perroe(malloc:);exit(1);}//成功就先把节点数据设置好再返回这个新节点的地址newnode-data x;newnode-next NULL;return newnode;
}
单链表中尾插数据
当我们增加了多个节点之后就可以尝试把节点串联起来形成一个链表了。那怎么串联呢可以把新增加的节点地址给到链表中最后一个节点中的指针。这个过程其实就是尾插数据。 情况一原链表中有节点 思路先把遍历找到 plist-next NULL再把 plist-next 改为新增加的节点的地址就相当于把新增加的节点串联到原链表中去了。
情况二原链表中没有节点
思路这个就只需要把新增加的节点的地址直接给头节点我们给的指针可以看看代码就可以了。
//尾插数据
void SLTPushBack(SListNode** pphead, SLTDataType x)
{assert(pphead);//不能为空否则就会对空指针解引用从而报错//首先判断是否为空再根据判断的情况来尾插if (*pphead NULL)//指向头节点的指针为空也就是链表为空{*pphead SLTBuyNode(x);}else{SListNode* newnode *pphead;//头指针while (newnode-next){newnode newnode-next;}//此时newnode为尾节点newnode-next SLTBuyNode(x);}
} 这里可能会有小伙伴有疑惑为什么要用二级指针来接收这里首先得弄清楚什么时候用用一级指针什么时候用二级指针 要想清楚修改的是指针所指向的对象还是要修改指针本身如果要修改指针指向的对象不要需改变一级指针的值传本身用一级指针就行如果要修改的是指针变量的内容要改变一级指针的值就得传地址就需要对指针变量进行取地址用二级指针接收。那么接下来就得判断是否需要改变头指针的值当链表中没有数据时头指针的值就会被改变此时就需要传一级指针的地址。而有数据的话头指针的指向就不会改变。但因为这里情况不确定就需要全部考虑因此就得用二级指针来接收。 如果在下面的函数中存在要改变头指针的情况我们就需要用二级指针。
打印单链表中节点的数据
尾插完之后我们就需要检测是否正确因此可以封装一个函数——打印节点数据。
//打印节点数据
void SLTPrint(SListNode* phead)
{SListNode* pcur phead;while (pcur){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
} 单链表中头插数据
接下来就开始实现头插。 同样也有两种情况
情况一原链表中有数据
思路先创建一个新的节点把新节点的地址给*pphead再把新节点的next指针指向原来头指针指向的地址。
情况二原链表中没有数据
思路和上面一样这个只要把新的节点的地址给到*pphead就可以了。
//头插数据
void SLTPushFront(SListNode** pphead, SLTDataType x)
{assert(pphead);//判断是否为空if (*pphead NULL){*pphead SLTBuyNode(x);}else{SListNode* pcur *pphead;*pphead SLTBuyNode(x);(*pphead)-next pcur;//注意操作符的优先级}
}
单链表中查找数据
接下来就开始通过给的节点数据来查找该节点的地址。 思路通过头指针来遍历整个链表如果 plist-data x就说明找到了返回 plist 此时的值如果plist NULL了就说明这个链表中没有该数据返回一个空指针就行了。
//查找数据
SListNode* SLTFind(SListNode* phead, SLTDataType x)
{assert(phead);SListNode* plist phead;while (plist){if (plist-data x){return plist;}plist plist-next;}return NULL;
}
有了查找函数就可以实现任意位置的增加数据和删除数据的操作了。
单链表中尾删数据
情况一当链表有多个数据 思路先通过头指针找到尾节点的前一个节点再把尾节点空间释放掉 最后把plist-next 为尾指针的指针置为空。注意顺序不能反过来因为如果先把plist-next置为空之后再去找就找不到了。
情况二当链表只有一个数据当没有数据时采取强制措施
思路就只需要把这个节点给释放掉就行了。
//尾删数据
void SLTPopBack(SListNode** pphead)
{assert(pphead *pphead);//*pphead不能为空否则就是空链表//注意操作符的优先级if ((*pphead)-next NULL)//只有一个节点{free(*pphead);*pphead NULL;}else{SListNode* plist *pphead;//找到尾节点的前一个节点while (plist-next-next){plist plist-next;}free(plist-next);plist-next NULL;}
} 单链表中头删数据
情况一单链表中有多个数据 思路先把头指针的值拷贝一份把这个头指针改为 phead-next再把拷贝指向的节点给给释放掉。
情况二单链表中只有一个节点数据
思路直接把这个空间给释放掉再把头指针置为空。
//头删数据
void SLTPopFront(SListNode** pphead)
{assert(pphead *pphead);//注意操作符的优先级if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SListNode* pcur *pphead;*pphead (*pphead)-next;free(pcur);}
}单链表中在指定位置之前插入数据
注意这里我们所说的指定位置一定要存在不考虑不存在的情况。
情况一指定位置不是头指针 思路先创建一个新的节点在原链表中找到pos的前一个节点在前一个节点的next指针指向新增加的节点接着在把新增加的节点的next指针指向pos这个节点的地址。
情况二指定位置是头指针——头插 情况三链表中没有数据——我们也就不能通过pos找到在哪里插入数据因此我们就采用断言。
//在指定位置之前插⼊数据
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{assert(pphead *pphead);assert(pos);//这个位置肯定要存在//先判断插入的位置if (*pphead pos){//头插SLTPushFront(pphead, x);}else{SListNode* pcur SLTBuyNode(x);//要插入的节点SListNode* prev *pphead;while (prev-next ! pos)//找到pos的前一个节点{prev prev-next;}prev-next pcur;pcur-next pos;}
}
有在指定位置之前插入肯定就有在指定位置之后插入
单链表中在指定位置之后插入数据
情况一pos这个位置存在 思路先创建一个新的节点再把新增加的节点的next指针指向原链表pos下一个节点的地址接着把pos位置的节点的next指针改为新增加的节点的地址。
情况二pos这个位置不存在同样要报错既然是在指定位置之后插入数据就肯定要存在这个位置不然谈何插入呢。
//在指定位置之后插入数据
void SLTInsertAfter(SListNode* pos, SLTDataType x)
{assert(pos);SListNode *pcur SLTBuyNode(x);//下面的顺序不能反过来pcur-next pos-next;pos-next pcur;
}
注意如果把pos下一个节点的地址记录下来了就可以更改顺序。不能更改顺序的原因是原链表中pos下一个节点的地址会找不到。
单链表中删除pos节点的位置
情况一pos这个位置的节点存在 思路先通过头指针遍历找到pos前一个位置的节点把pos前一个节点的next改为指向pos-next再把pos这个节点的空间销毁就行了。
注意因为节点的空间都是我们通动态内存开辟来的因此我们要用free手动销毁它。
还有一种特殊且容易忽略的情况要删除的位置是头节点——头删
情况二pos这个位置不存在——直接报错就行
//删除pos节点
void SLTErase(SListNode** pphead, SListNode* pos)
{assert(pphead *pphead);assert(pos);//先判断是否为头节点if (pos *pphead){//头删SLTPopFront(pphead);}else{SListNode* prev *pphead;//找到pos前一个节点while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}
单链表中删除pos节点之后的位置
情况一存在pos的位置 思路把pos-next-next的值赋值给一个新的指针再把pos-next的空间释放最后把新指针的值给到pos-next就可以了。
情况二不存在pos位置pos-next要不为空也就是pos后面必须要有节点
//删除pos之后的节点
void SLTEraseAfter(SListNode* pos)
{assert(pos pos-next);//如果pos后面没节点了就不能删了SListNode* pcur pos-next;pos-next pos-next-next;free(pcur);pcur NULL;
}
销毁链表 //销毁链表
void SListDesTroy(SListNode** pphead)
{assert(pphead *pphead);//检查SListNode* pcur *pphead;while (pcur){SListNode* nextNode pcur-next;//先把pcur的下一个节点的地址存起来free(pcur);//释放掉pcur的节点空间pcur nextNode;//把pcur指向next}*pphead NULL;
} 上面就是单链表的全部逻辑以及实现。
单链表源码
下面是单链表的源码
SList.h
#include stdio.h
#include assert.h
#include stdlib.htypedef int SLTDataType;//创建一个节点
typedef struct SListNode
{SLTDataType data;struct SListNode* next;//注意这里不能写重命名之后的
}SListNode;//增加节点(空间)
SListNode* SLTBuyNode(SLTDataType x);//尾插数据
void SLTPushBack(SListNode** pphead, SLTDataType x);//打印节点数据
void SLTPrint(SListNode* phead);//头插数据
void SLTPushFront(SListNode** pphead, SLTDataType x);//查找数据
SListNode* SLTFind(SListNode* phead, SLTDataType x);//尾删数据
void SLTPopBack(SListNode** pphead);//头删数据
void SLTPopFront(SListNode** pphead);//在指定位置之前插⼊数据
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x);//在指定位置之后插入数据
void SLTInsertAfter(SListNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SListNode** pphead, SListNode* pos);//删除pos之后的节点
void SLTEraseAfter(SListNode* pos);//销毁链表
void SListDesTroy(SListNode** pphead);
SList.c
#include SList.h//增加节点(空间)并初始化
SListNode* SLTBuyNode(SLTDataType x)
{//开辟一个节点的空间SListNode* newnode (SListNode*)malloc(sizeof(SListNode));//判断是否开辟成功if (newnode NULL)//失败{perror(malloc:);exit(1);}//成功就先把节点数据设置好再返回这个新节点的地址newnode-data x;newnode-next NULL;return newnode;
}//尾插数据
void SLTPushBack(SListNode** pphead, SLTDataType x)
{assert(pphead);//不能为空否则就会对空指针解引用从而报错//首先判断是否为空再根据判断的情况来尾插if (*pphead NULL)//指向头节点的指针为空也就是链表为空{*pphead SLTBuyNode(x);}else{SListNode* newnode *pphead;//头指针while (newnode-next){newnode newnode-next;}//此时newnode为尾节点newnode-next SLTBuyNode(x);}
}//打印节点数据
void SLTPrint(SListNode* phead)
{SListNode* pcur phead;while (pcur){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}//头插数据
void SLTPushFront(SListNode** pphead, SLTDataType x)
{assert(pphead);//判断是否为空if (*pphead NULL){*pphead SLTBuyNode(x);}else{SListNode* pcur *pphead;*pphead SLTBuyNode(x);(*pphead)-next pcur;}
}//查找数据
SListNode* SLTFind(SListNode* phead, SLTDataType x)
{assert(phead);SListNode* plist phead;while (plist){if (plist-data x){return plist;}plist plist-next;}return NULL;
}//尾删数据
void SLTPopBack(SListNode** pphead)
{assert(pphead *pphead);//*pphead不能为空否则就是空链表//注意操作符的优先级if ((*pphead)-next NULL)//只有一个节点{free(*pphead);*pphead NULL;}else{SListNode* plist *pphead;//找到尾节点的前一个节点while (plist-next-next){plist plist-next;}free(plist-next);plist-next NULL;}
}//头删数据
void SLTPopFront(SListNode** pphead)
{assert(pphead *pphead);//注意操作符的优先级if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SListNode* pcur *pphead;*pphead (*pphead)-next;free(pcur);}
}//在指定位置之前插⼊数据
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{assert(pphead *pphead);assert(pos);//这个位置肯定要存在//先判断插入的位置if (*pphead pos){//头插SLTPushFront(pphead, x);}else{SListNode* pcur SLTBuyNode(x);//要插入的节点SListNode* prev *pphead;while (prev-next ! pos)//找到pos的前一个节点{prev prev-next;}prev-next pcur;pcur-next pos;}
}//在指定位置之后插入数据
void SLTInsertAfter(SListNode* pos, SLTDataType x)
{assert(pos);SListNode *pcur SLTBuyNode(x);//下面的顺序不能反过来pcur-next pos-next;pos-next pcur;
}//删除pos节点
void SLTErase(SListNode** pphead, SListNode* pos)
{assert(pphead *pphead);assert(pos);//先判断是否为头节点if (pos *pphead){//头删SLTPopFront(pphead);}else{SListNode* prev *pphead;//找到pos前一个节点while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}//删除pos之后的节点
void SLTEraseAfter(SListNode* pos)
{assert(pos pos-next);//如果pos后面没节点了就不能删了SListNode* pcur pos-next;pos-next pos-next-next;free(pcur);pcur NULL;
}//销毁链表
void SListDesTroy(SListNode** pphead)
{assert(pphead *pphead);SListNode* pcur *pphead;while (pcur){SListNode* nextNode pcur-next;//先把pcur的下一个节点的地址存起来free(pcur);//释放掉pcur的节点空间pcur nextNode;//把pcur指向next}*pphead NULL;
}
好啦本期数据结构单链表的学习就到此为止啦我们下一期再一起学习吧
