商城网站建设服务哪家好,中职网站建设与维护考试题,母婴网站建设方案,网站模版免费#x1f493;博主csdn个人主页#xff1a;小小unicorn#x1f493; ⏩专栏分类#xff1a;c #x1f69a;代码仓库#xff1a;小小unicorn的学习足迹#x1f69a; #x1f339;#x1f339;#x1f339;关注我带你学习编程知识 前面我们讲的线性表的顺序存储结构。它… 博主csdn个人主页小小unicorn ⏩专栏分类c 代码仓库小小unicorn的学习足迹 关注我带你学习编程知识 前面我们讲的线性表的顺序存储结构。它是有缺点的最大的缺点就是插入和删除时需要移动大量元素这显然就需要耗费时间那能不能想办法解决呢 要解决这个问题我们就得考虑一下导致这个问题的大致原因 为什么当插入和制除时就要移动大量元素仔细分析后发现原因就在于自元素的存储位置也具有邻居关系。它们编号是123…n它们在内存中的位最的是按着的中间没有空源当然就无法快速插入而删除后当中就会留出空像自然需要弥补。问题就出在这里。 A同学思路让当中每个元素之间都留有一个空位置这样要插入时就不至于动可一个空位置如何解决多个相同位置插入数据的问题呢所以这个想法显然不行。 B同学思路那就让当中每个元素之间都留足够多的位置根据实际情况制定空像大小比如10个这样插入时就不需要移动了。万一10个空位用完了再考虑移动使得每个位置之间都有10个空位置。如果删除就直接删掉把位置留空即可。这样似乎蓄时解决了插入和删除的移动数据问题。可这对于超过10个同位置数据的插入效率上还是存在问题。对于数据的遍历也会因为空位置太多而造成判断时间上的浪费。而且显然这里空间复杂度还增加了因为每个元素之间都有若干个空位置。 C同学思路我们反正也是要让相邻元素间留有足够余地那干脆所有的元素都不要考虑相邻位置了哪有空位就到哪里而只是让每个元素知道它下一个元素的位置在哪里这样我们可以在第一个元素时就知道第二个元素的位置(内存地址)而找到它在第二个元素时再找到第三个元素的位置(内存地址)。这样所有的元素我们就都可以通过遍历而找到。 好大棒了这个想法非常好 C同学可惜生晚了几十年不然c同学的想法对于数据结构来讲就是划时代的意义。我们要的就是这个思路。 链表 1.线性表的联试存储结构1.1线性表链式存储结构定义1.2头指针与头结点的异同1.3线性表链式存储结构代码描述 2.单链表的具体实现2.1开辟节点2.2遍历链表以及开辟新节点 3.接口函数的实现增删查改3.1尾插3.2头插3.3尾删3.4头删3.5查找3.6在pos位置之前插入x3.7在pos位置以后插入x3.8删除pos位置3.9删除pos的后一个位置 4.单链表结构与顺序存储结构的优缺点5.链表完整代码5.1 SList.h5.2 SList.c5.3 Test.c 1.线性表的联试存储结构
1.1线性表链式存储结构定义
在解释这个思路之前我们先来谈另一个话题。前几年有一本书风靡了全世界它叫《达·芬奇密码》成为世界上最畅销的小说之一书的内容集合了侦探、惊使和阴谋论等多种风格很好看。这本书和绝大部分负小说一样都是同一种处理办法。那就是作者不会让你事先知道整个过程的全部而是在一步一步地到这某个环节才根据现场的信息获得或推断出下一步是什么也就是说每一步除了对你侦破的信息进一步确认外之前信息也不一定都是对的有时是证明某个信息不正确)还有就是对下一步如何操作或行动的指引。
不过这个例子也不完全与线性表相符合因为案件侦破的线案可能是错综复杂的有点像我们之后要讲到的树和图的数据结构。今天我们要讲的是单线索无分支的情况。即线性表的链式存储结构。
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素这组存储单元可以是连续的也可以是不连续的。这就意 味着这些数据元素可以存在内存未被占用的任意位置 (如下图所示)。
以前在顺序结构中每个数据元素只需要存储数据 元素信息就可以了。现在链式结构中除了要存储数据 元素信息外还要存储它的后继元素的存储地址。
因此为了表示每个数据元素ai与其直接后继数据 元素ai1(i是下标)之间的逻辑关系对数据元素ai来说除了存储 其本身的信息之外还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像称为结点(Node)。
n个结点(a的存储映像)链结成一个链表即为线性表(aay·a)的链式存储结构因为此链表的每个结点中只包含一个指针域所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。
对于线性表来说总得有个头有个尾链表也不例外。我们把链表中第一个结点的存储位置叫做头指针那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点其实就是上一个的后继指针指向的位置。想象一下最后一个结点它的指针指向哪里
最后一个当然就意味着直接后继不存在了所以我们规定线性链表的最后一个结点指针为“空”(通常用NULL或“^”符号表示如下图所示)。
有时我们为了更加方便地对链表进行操作会在单链表的第一个结点前附设一个结点称为头结点。头结点的数据域可以不存储任何信息谁叫它是第一个呢有这个特权。也可以存储如线性表的长度等附加信息头结点的指针域存储指向第一个结点的指针如下图所示。
1.2头指针与头结点的异同
头指针与头结点的异同点如下图所示
1.3线性表链式存储结构代码描述
若线性表为空则头结点的指针域为“空”如下图所示
这里我们大概用图示表达了内存中单链表的存储状态。看着满图的省略号“…”就知道是有多么不方便。而我们真正关心的它在内存中的实际位置吗不是的。这只是它所表示的线性表中的数据元素及数据元素之间色逻辑关系。所以我们改用更方便的存储示意图来表示单链表如下图所示
若带有头结点的单链表则如下图所示
空链表如下图所示
单链表中我们在c语言中可用结构指针来描述
//线性表的单链表的存储结构
typedef struct Node
{ElemType data;struct Node*next;
}Node;
typedef struct Node*LinkList;//定义linkList从这个结构定义中我们也就知道结点由存放数据元素的数据域和存放后继结点地址的指针域组成。假设p是指向线性表第i个元素的指针则该结点ai 的数据域我们可以用p-data来表示p-data的值是一个数据元素结点ai的指针域可以用p-next来表示p-next的值是一个指针。p-next指向谁呢当然是指向第i1个元素即指向ail的指针。也就是说如果p-data等于a那么pnext-data等于ai1(如下图所示)。
2.单链表的具体实现
2.1开辟节点
首先创建一个新项目分为三个模块SList.c用来实现接口函数SList.h用来结构体创建与函数声明test.c则用来进行测试我们的接口函数。 创建节点如下 2.2遍历链表以及开辟新节点 咱们首先用一个cur来存放头结点的地址 那后面节点的数据怎么访问呢咱们可以让cur-next赋给cur; 依次内推当cur为空时说明已经访问结束。 最后打印即可。 为方便测试我们可以先写一个交互性的链表测试 写交互性测试的时候会涉及到开辟新节点这里我们可以抽离一个函数来专门进行开辟新节点。 测试结果如下
3.接口函数的实现增删查改
3.1尾插
那么如何实现尾插呢尾插我们首先得先找到尾。 那么如何找呢 先看下面这个代码。 如果要是这样找尾的话就会出现一个问题。我们画图分析一下。 这个代码是不是首先有三个指针变量 plist tail newnode; 随着代码运行最后taill的地址为空假设新节点的地址为0x0012ff00,那节点newnode存放的地址也就是0x0012ff00最后呢又把newnode的地址给了taill,看起来没问题但有没有想过这三个指针变量出了作用域呢 出了作用域这三个指针变量是不是都销毁了这不仅造成了内存泄漏还没有吧链表链接起来。基于这个问题我们在回过来思考这个问题如何找尾 所以我们的尾用taii找的时候条件不是null结束而是存放null前一个的地址。 继续思考一下我们写完了吗那如果本身就是个空链表呢也就是说空链表传过来的时候。第一次尾插怎么插呢看下面这个代码。 这个代码就会有一个明显的错误插入不进去。为什么会这样呢 看pheadnewnode这一步这一步是把0x0012ffcc给了phead,出了作用域phead,newnode****销毁那么显然我们的plist的地址并没有发生任何变化所以插入不进去。 这就是典型的形参与实参之间的区别形参只是实参的一份临时拷贝。那么怎们样才能改变呢那就需要传地址了。 经过以上的不断修改最终尾插的接口函数完整代码如下 测试结果如下 总结一下 3.2头插
有了尾插的思想头插就简单了。 实质也就是修改plist所以还是传值还是用二级指针。 完整代码如下 测试结果如下 3.3尾删 如果是空链表我们可以直接使用断言。 一个节点直接释放掉plist.两个节点以上就首先需要找尾先看下面这个代码。**pphead就是plist 上面这个代码找到尾后直接把taill置空肯定不行 freetaill的本质是把tail指向的节点给free了再把taill置空。出了作用域taill销毁那他前一个还是空。所以还需要找到taill的前一个。 以下两种解决办法都可以。 最终完整代码如下 测试结果如下 删除6个。 3.4头删
同理头删与尾删大同小异头删实现更简单。 测试结果如下 3.5查找 查找实质还是遍历链表 3.6在pos位置之前插入x
pos是任意一个节点防止为空呢我们先检查一下 那他还有什么特殊情况呢头插尾插就是其中两种其次处理pos在中间位置。 完整代码如下 测试结果如下在给定数字前面插它的十倍 3.7在pos位置以后插入x 要是后插就会便捷很多。因为他不可能实现头插所以就会很简单。 如果是第一个代码测试结果如下 进入了死循环。 修改后完整代码如下 测试结果如下 3.8删除pos位置 删除部分就简单了。分情况头删首先需要单独处理其次尾删是不需要单独处理的因为正常删就已经包含尾删情况了。 完整代码如下 测试结果如下 3.9删除pos的后一个位置 删后一个考虑的就是要找到前一个处理好这个就简单了。其次有个坑它删不了头。 完整代码 4.单链表结构与顺序存储结构的优缺点 简单地对单链表结构和顺序存储结构做对比 通过上面的对比我们可以得出一些经验性的结论
1.若线性表需要频繁查找很少进行插入和删除操作时宜采用顺序存储结构。若需要频繁插入和删除时宜采用单链表结构。比如说游戏开发中对于用户注册的个人信息除了注册时插入数据外绝大多数情况都是读取所以应该考虑用顺序存储结构。而游戏中的玩家的武器或者装备列表随着玩家的游戏过程中可能会随时增加或删除此时再用顺序存储就不太合适了单链表结构就可以大展拳脚。当然这只是简单的类比现实中的软件开发要考虑的问题会复杂得多。
2.当线性表中的元素个数变化较大或者根本不知道有多大时最好用单链表给构。这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度比如一年12个月一周就是星期一至星期日共七天这种用顺序存储结构效率会高很多。
总之线性表的顺序存储结构和单链表结构各有其优缺点不能简单地说哪个好哪个不好需要根据实际情况来综合平衡采用哪种数据结构更能满足和达到需求和性能。
5.链表完整代码
5.1 SList.h
#includestdio.h
#includestdlib.h
#includeassert.htypedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);
SLTNode* BuySListNode(SLTDataType x);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在pos位置以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);5.2 SList.c
#define _CRT_SECURE_NO_WARNINGS
#includeSList.h//打印函数
void SLTPrint(SLTNode* phead)
{SLTNode* cur phead;//while (cur ! NULL)while (cur){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}//开辟新节点
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);if (*pphead NULL){//改变的结构体的指针*pphead newnode;}else{SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}//改变的结构体tail-next newnode;}
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}//尾删
void SLTPopBack(SLTNode** pphead)
{//空assert(*pphead);//一个节点//一个以上节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* tail *pphead;while (tail-next-next){tail tail-next;}free(tail-next);tail-next NULL;/*SLTNode* tailprev NULL;SLTNode* tail *pphead;while (tail-next){tailprev tail;tail tail-next;}free(tail);tail NULL;tailprev-next NULL;*/}
}//头删
void SLTPopFront(SLTNode** pphead)
{//空assert(*pphead);//非空SLTNode* newnode (*pphead)-next;free(*pphead);*pphead newnode;
}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;}//在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newnode BuySListNode(x);prev-next newnode;newnode-next pos;}
}//在pos位置以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuySListNode(x);/*pos-next newnode;*/newnode-next pos-next;pos-next newnode;
}//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (pos *pphead){SLTPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);//pos NULL;}
}//删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//检查Pos是否为尾节点assert(pos-next);SLTNode* posNext pos-next;pos-next posNext posNext-next;free(posNext);posNext NULL;
}
5.3 Test.c
#define _CRT_SECURE_NO_WARNINGS
#includeSList.h//交互链表测试
void TestSList1()
{int n;printf(请输入链表的长度\n);scanf(%d, n);printf(请依次输入每个节点的值\n);SLTNode* plist NULL;for (size_t i 0; i n; i){int val;scanf(%d, val);SLTNode* newnode BuySListNode(val);//头插newnode-next plist;plist newnode;}SLTPrint(plist);}//测试尾插头插
void TestSList2()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);SLTPrint(plist);}//测试尾删
void TestSList3()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);/*SLTPopBack(plist);SLTPrint(plist);*/}//测试头删
void TestSList4()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);/*SLTPopFromt(plist);SLTPrint(plist);*/
}void TestSList5()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);SLTNode* pos SLTFind(plist, 40);if (pos){pos-data * 10;}SLTPrint(plist);int x;scanf(%d, x);pos SLTFind(plist, x);if (pos){SLTInsert(plist, pos, x * 10);}SLTPrint(plist);}void TestSList6()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);int x;scanf(%d, x);SLTNode* pos SLTFind(plist, x);if (pos){SLTErase(plist, pos);}SLTPrint(plist);
}void TestSList7()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);SLTPrint(plist);int x;scanf(%d, x);SLTNode* pos SLTFind(plist, x);if (pos){SLTEraseAfter(pos);pos NULL;}SLTPrint(plist);//SLTPopFront(plist);//SLTPrint(plist);//SLTPopFront(plist);//SLTPrint(plist);//SLTPopFront(plist);//SLTPrint(plist);//SLTPopFront(plist);//SLTPrint(plist);}int main()
{TestSList7();
}
