网站建设 收费明细,网站设计联系电话,php网站作业模版,推广怎么做?个人主页#xff1a;平行线也会相交 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 平行线也会相交 原创 收录于专栏【数据结构初阶#xff08;C实现#xff09;】 文章标题回顾链表链表的概念及结构各种节点打印链表尾插创建节点尾删头插头删查找在pos… 个人主页平行线也会相交 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 平行线也会相交 原创 收录于专栏【数据结构初阶C实现】 文章标题回顾链表链表的概念及结构各种节点打印链表尾插创建节点尾删头插头删查找在pos之前去插入在pos之后去插入删除pos位置的值销毁链表总代码test.cSlist.cSlist.h回顾
在讲解链表之前我们先来看看顺序表有哪些缺陷呢 1.空间不够需要增容而增容就需要付出代价realloc增容一种是原地扩容另一种是异地扩容时会容易产生内存碎片异地扩容时。 2.顺序表为了频繁扩容所以空间一旦满了基本上就是扩2倍可能会存在空间的浪费因为扩出来的空间可能用不了那么多。 3.顺序表要求数据从头开始位置连续存储那么我们在头部或者中间位置插入删除数据就需要挪动数据效率不高。 realloc原地扩容
int main()
{int* p1 (int*)malloc(10 * sizeof(int));int* p2 (int*)realloc(p1, 11 * sizeof(int));return 0;
}realloc异地扩容
#includestdlib.hint main()
{int* p1 (int*)malloc(10 * sizeof(int));int* p2 (int*)realloc(p1, 1000 * sizeof(int));return 0;
}链表
针对顺序表存在的一些缺陷所以就设计出来了链表。然而顺序表也并不是一无是处对于顺序表是一块连续的空间只需要存储第一个空间的地址就可以找到所有的数据对于这种物理上是连续的好处比如a[i]等价于*(ai)。 而对于链表倘若要遍历所有的数据就需要通过指针来进行链接第一个存第二个的地址、第二个存第三个的地址、第三个存第四个的地址…所以这也是链表的代价每存储一个数据就需要伴随一个指针,即每个数据都要存一个指针去链接后面数据节点不支持随机访问用下标直接访问第i个。 同时链表一定程度上也更好的解决了顺序表头部、中间插入数据时还需要挪动数据。链表就不需要这么麻烦只需要改指针的链接不需要挪动数据。 这里指的是单链表当然链表不仅仅只是这一种结构我们先从最简单的单链表开始循序渐进。
链表的概念及结构 概念链表是一种物理存储结构上非连接、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的可以根据自己的需要按需申请空间。 typedef int SLTDateType;struct SListNode
{SLTDateType data;//data就是我们要存储的数据struct SListNode* next;
};各种节点
void SListPrint(SLTNode* phead);void SListPushBack(SLTNode** pphead,SLTDateType x);void SListPustFront(SLTNode** pphead, SLTDateType x);void SListPopBack(SLTNode** pphead);void SListPopFront(SLTNode** pphead);SLTNode* SListFind(SLTNode* phead, SLTDateType x);//查找//在pos位置之前去插入一个节点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);//某个位置插入
//void SListInsert(SLTNode* phead, int pos, SLTDateType x);//某个位置插入void SListInsertAfter(SLTNode* pos, SLTDateType x);void SListErase(SLTNode** pphead, SLTNode* pos);
//void SListErase(SLTNode** phead, int pos);void SListEraseAfter( SLTNode* pos);void SListDestory(SLTNode** pphead);//销毁链表
打印链表
首先phead是一个结构体指针指向第一个节点cur也是如此循环打印每个节点的数据就是通过cur cur-next;走下去的直到cur为空指针为止。
void SListPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}尾插
//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* newnode BuyListNode(x);//起初链表中是啥也没有的if (*pphead NULL){*pphead newnode;}else{//找到尾部节点SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}注意第一种情况倘若链表中起初啥也没有的所以就需要我们先创建一个节点。 第二种情况此时链表中是有数据的此时我们要想尾插一个尾节点就需要先找到尾。找到尾部节点的空指针后直接把此空指针置为新节点的指针即tail-next newnode;。 我们发现即使链表是否为空我们都需要新创建一个节点。所以我们专门分装一个专门创建一个节点的函数并把这个节点的地址返回就好了。这样我们也方便以后头插等情况时候创建新节点。 还有一个点需要注意请看这里void SListPushBack(SLTNode** pphead, SLTDateType x)我们在进行尾插的时候为什么要传二级指针过去呢这的确是一个值得思考的问题。当我们想要进行尾插即SListPushBack(plist, 1); SListPushBack(plist, 2);的时候如果我们不传plist的地址的话那么在尾插函数SListPushBack内部pphead的改变是无法改变外部的plist的。所以我们就需要传plist的地址过去此时我们也就需要二级指针来进行接收因为plist本身就是一个指针。 总之我们如果想改变plist的值的话就需要将其地址传过去否则形参就是实参的一份临时拷贝形参的改变是无法改变实参的。
创建节点
SLTNode* BuyListNode(SLTDateType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));//检查是否开辟成功if (newnode NULL){printf(malloc fail\n);//内存申请失败的话说明已经没有多少空间了exit(-1);//申请失败则直接结束程序}newnode-data x;newnode-next NULL;return newnode;
}尾删
void SlistPopBack(SLTNode** pphead)
{//温柔一点if (*pphead NULL){return;}//粗暴一点//assert(*pphead ! NULL);//走到这里意味着一定有一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* prev NULL;SLTNode* tail *pphead;//while (tail-next ! NULL)while (tail-next){prev tail;tail tail-next;}free(tail);tail NULL;prev-next NULL;}
}进行尾删时总共三种情况第一链表为空第二链表只要一个节点第三链表有1个以上的节点。 这里我们来看一下最复杂的情况第三种当链表有一个以上的节点时当我们尾删链表的最后一个节点时我们还需要把最后一个链表的前一个链表的next置为空指针否则其就变成了野指针。但是由于单链表是无法找到前一个节点的next指针的。所以我们定义一个prev在tail往下走即tail tail-next;之前先进行prev tail;。另外tail置不置空无所谓因为出了tail的作用域其就被销毁了。
头插
void SListPustFront(SLTNode** pphead, SLTDateType x)
{SLTNode* newnode BuyListNode(x);newnode-next *pphead;*pphead newnode;
}头删
void SListPopFront(SLTNode** pphead)
{//空//一个节点//一个以上节点assert(pphead);//处理一个或者多个节点都可以但是唯独不能处理节点为空/*if (*pphead NULL){return;}*/assert(*pphead ! NULL);//节点为空直接报错SLTNode* next (*pphead)-next;free(*pphead);*pphead next;//实际上我们可以把一个节点或者一个以上节点进行统一处理。
}这里我们先明确一个问题问题1free释放的是指针呢还是释放的是内存呢应该是这样的free释放的是指针指向的内存。 问题2内存泄漏是内存丢了还是指针丢了应该是这样的内存泄漏是指针丢了我们直到如果指针在的话可以找到我们依然可以随时释放指针指向的空间但是如果指针真的丢了找不到了那我们连哪些内存没有释放都不知道。内存是不会丢的因为内存一直是在那个位置free只是把这块空间的使用权还给系统同时把这块空间置为随机值。
查找
查找返回的是一个指针。
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{SLTNode* cur phead;while (cur){if (cur-data x){return cur;}else{cur cur-next;}}return NULL;//来到这里说明到最后都没有找到返回空
}在pos之前去插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{assert(pphead);assert(pos);SLTNode* newnode BuyListNode(x);if (*pphead pos){//相当于头插了可以调用其函数newnode-next *pphead;*pphead newnode;}else{//找到pos的前一个位置SLTNode* posPrev *pphead;while (posPrev-next ! pos){posPrev posPrev-next;}posPrev-next newnode;newnode-next pos;}
}在pos之后去插入
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos);SLTNode* newnode BuyListNode(x);newnode-next pos-next;pos-next newnode;
}注意顺序不要颠倒newnode-next pos-next; pos-next newnode;。
删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead pos){//相当于头删/**pphead pos-next;free(pos);*/SListPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);}
}销毁链表
void SListDestory(SLTNode** pphead)//销毁链表
{assert(pphead);SLTNode* cur *pphead;while (cur){SLTNode* next cur-next;free(cur);cur next;}*pphead NULL;
}总代码
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#includeSList.hvoid TestSList1()
{SLTNode* plist NULL;SListPushBack(plist, 1);SListPushBack(plist, 2);SListPushBack(plist, 3);SListPushBack(plist, 4);SListPrint(plist);SListPushFront(plist, 1);SListPushFront(plist, 2);SListPushFront(plist, 3);SListPushFront(plist, 4);SListPrint(plist);}void TestSList2()
{SLTNode* plist NULL;SListPushFront(plist, 1);SListPushFront(plist, 2);SListPushFront(plist, 3);SListPushFront(plist, 4);SlistPopBack(plist);SListPrint(plist);}void TestSList3()//测试头删
{SLTNode* plist NULL;SListPushFront(plist, 1);SListPushFront(plist, 2);SListPushFront(plist, 3);SListPushFront(plist, 4);SListPopFront(plist);SListPrint(plist);SListPopFront(plist);SListPrint(plist);SListPrint(plist);SListPopFront(plist);SListPrint(plist);
}void TestSList4()//测试查找
{SLTNode* plist NULL;SListPushFront(plist, 1);SListPushFront(plist, 2);SListPushFront(plist, 3);SListPushFront(plist, 2);SListPushFront(plist, 4);SListPushFront(plist, 2);SListPushFront(plist, 2);SListPushFront(plist, 4);SListPrint(plist);//找SLTNode* pos SListFind(plist, 2);int i 1;while (pos){printf(第%d个pos节点:%p-%d\n, i, pos, pos-data);pos SListFind(pos-next, 2);}//修改3-30pos SListFind(plist, 3);if (pos){pos-data 30;}SListPrint(plist);
}void TestSList5()//测试查找
{SLTNode* plist NULL;SListPushFront(plist, 1);SListPushFront(plist, 2);SListPushFront(plist, 3);SListPushFront(plist, 4);SListPrint(plist);SLTNode* pos SListFind(plist, 3);if (pos){SListInsert(plist, pos, 30);}SListPrint(plist);pos SListFind(plist, 1);if (pos){SListInsert(plist, pos, 10);}SListPrint(plist);pos SListFind(plist, 4);if (pos){SListInsert(plist, pos, 40);}SListPrint(plist);}
TestSList6()
{SLTNode* plist NULL;SListPushBack(plist, 1);SListPushBack(plist, 2);SListPushBack(plist, 3);SListPushBack(plist, 4);SListPrint(plist);SListDestory(plist);//销毁链表}
int main()
{//TestSList1();//TestSList2();//TestSList3();//TestSList4();//TestSList5();TestSList6();return 0;
}Slist.c
#define _CRT_SECURE_NO_WARNINGS 1#includeSList.hSLTNode* BuyListNode(SLTDateType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));//检查是否开辟成功if (newnode NULL){printf(malloc fail\n);//内存申请失败的话说明已经没有多少空间了exit(-1);//申请失败则直接结束程序}newnode-data x;newnode-next NULL;return newnode;
}void SListPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* newnode BuyListNode(x);//起初链表中是啥也没有的if (*pphead NULL){*pphead newnode;}else{//找到尾部节点SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}//头插
void SListPushFront(SLTNode** pphead, SLTDateType x)
{SLTNode* newnode BuyListNode(x);newnode-next *pphead;*pphead newnode;
}//头删
void SlistPopBack(SLTNode** pphead)
{//温柔一点if (*pphead NULL){return;}//粗暴一点//assert(*pphead ! NULL);//走到这里意味着一定有一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* prev NULL;SLTNode* tail *pphead;//while (tail-next ! NULL)while (tail-next){prev tail;tail tail-next;}free(tail);tail NULL;prev-next NULL;}
}void SListPopFront(SLTNode** pphead)
{//空//一个节点//一个以上节点assert(pphead);//处理一个或者多个节点都可以但是唯独不能处理节点为空/*if (*pphead NULL){return;}*/assert(*pphead ! NULL);//节点为空直接报错SLTNode* next (*pphead)-next;free(*pphead);*pphead next;
}SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{SLTNode* cur phead;while (cur){if (cur-data x){return cur;}else{cur cur-next;}}return NULL;//来到这里说明到最后都没有找到返回空
}//在pos位置之前去插入一个节点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{assert(pphead);assert(pos);SLTNode* newnode BuyListNode(x);if (*pphead pos){//相当于头插了可以调用其函数newnode-next *pphead;*pphead newnode;}else{//找到pos的前一个位置SLTNode* posPrev *pphead;while (posPrev-next ! pos){posPrev posPrev-next;}posPrev-next newnode;newnode-next pos;}
}//在pos之后去插入更合适也更简单
void SListInsertAfter(SLTNode* pos, SLTDateType x)
{assert(pos);SLTNode* newnode BuyListNode(x);newnode-next pos-next;pos-next newnode;
}void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead pos){//相当于头删/**pphead pos-next;free(pos);*/SListPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);}
}//删除后一个
void SListEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);//报错就说明你用错来SLTNode* next pos-next;pos-next next-next;free(next);//next NULL;//置不置空没有意义
}void SListDestory(SLTNode** pphead)//销毁链表
{assert(pphead);SLTNode* cur *pphead;while (cur){SLTNode* next cur-next;free(cur);cur next;}*pphead NULL;
}Slist.h
#define _CRT_SECURE_NO_WARNINGS 1#pragma once
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLTDateType;typedef struct SListNode
{SLTDateType data;//data就是我们要存储的数据struct SListNode* next;
}SLTNode;void SListPrint(SLTNode* phead);void SListPushBack(SLTNode** pphead,SLTDateType x);void SListPushFront(SLTNode** pphead, SLTDateType x);void SListPopBack(SLTNode** pphead);void SListPopFront(SLTNode** pphead);SLTNode* SListFind(SLTNode* phead, SLTDateType x);//查找//在pos位置之前去插入一个节点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);//某个位置插入
//void SListInsert(SLTNode* phead, int pos, SLTDateType x);//某个位置插入void SListInsertAfter(SLTNode* pos, SLTDateType x);void SListErase(SLTNode** pphead, SLTNode* pos);
//void SListErase(SLTNode** phead, int pos);void SListEraseAfter( SLTNode* pos);void SListDestory(SLTNode** pphead);//销毁链表以上就是单链表的基本操作就到这里吧再见啦
