外贸网站制作费用,信誉好的永州网站建设,wordpress考试主题,公司小程序定制开发本章概述 前情回顾单链表实现单链表彩蛋时刻#xff01;#xff01;#xff01; 前情回顾
咱们在上一章博客点击#xff1a;《顺序表》的末尾#xff0c;提出了一个问题#xff0c;讲出了顺序表的缺点——有点浪费空间。所以#xff0c;为了解决这个问题#xff0c;我… 本章概述 前情回顾单链表实现单链表彩蛋时刻 前情回顾
咱们在上一章博客点击《顺序表》的末尾提出了一个问题讲出了顺序表的缺点——有点浪费空间。所以为了解决这个问题我们今天就要讲解链表咱们在讲结构体的时候有提到过链表链表的最大优点——一点空间也不浪费用多少就开辟多少。
单链表
概念一种在逻辑上成线性结构在物理空间上不一定成线性结构的数据结构。因为链表是线性表的一种所以在逻辑上成线性结构从“ 链 ”字上就能猜到在逻辑上成线性结构。我们链表的开辟用的内存函数是malloc。知识点忘记的同学自行回顾点击《动态内存管理》。因为内存开辟是随机的所以我们也不知道它会在内存的那一块区域开辟空间这就导致开辟的空间可能是连续的也可能不是连续的。所以在物理空间上不一定成线性结构。节点每一个个独立而且还能存放数据的空间被称为节点。数据结构是用来存储数据的链表自然也是来存储数据的。存储数据就需要有空间自然有malloc来给我们开辟空间。万事俱备只欠东风可是有想过一个问题吗——malloc开辟的空间东一块西一块的。它不像realloc那样开辟的连续空间我们可以挨着挨着找到空间它的空间是散乱的不连续的。那么我们该怎样进行数据的存储而且还能找到一个一个的数据呢我们可以在这个节点内部划分两部分一部分用来存储我们想要存储的数据另一部分部分用来存储下一个节点的地址因为我们的节点空间是用nalloc开辟的所以每个节点自然就有个地址。这就需要用到结构体了进行链表的结构展示
typedef int SLDatatype ;
typedef struct Sqlist
{SLDatatype data; //存放数据这里假设存放整型类型struct Sqlist* next; //存放下一个节点的地址
}SLND; //定义节点类型这样我们就能通过地址找到下一个节点了以此类推我们就能顺次找到各个节点找到数据了。如图所示 当我们不想再存储数据时要给最后一个节点的next指针赋值NULL下一个节点为NULL就相当于没有下一个节点就表示到此结束了。
链表的性质 1、链式机构在逻辑上是连续的在物理结构上不⼀定连续。2、结点⼀般是从堆上申请的。3、从堆上申请来的空间是按照⼀定策略分配出来的每次申请的空间可能连续可能不连续。 链表的打印我们讲过了节点的存储结构了我们可以通过next指针找到下一个节点然后就能打印我们想要的数据了。直观体验链表我们先给大家直观感受一下链表让大家有个感觉我们就按照上面的结构图进行展示
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include stdlib.h
#include assert.h
typedef int SLDatatype;
typedef struct Sqlist
{SLDatatype data;struct Sqlist* next;
}SLND;void my_printf(SLND* ps)
{assert(ps);while (ps){printf(%d-, ps-data);ps ps-next;}printf(NULL);
}
void test()
{SLND* plistNULL; //创立一个带头指针用来牵引后面的链表就像火车头一样SLND* node1 (SLND*)malloc(sizeof(SLND)); //创立3个节点SLND* node2 (SLND*)malloc(sizeof(SLND));SLND* node3 (SLND*)malloc(sizeof(SLND));node1-data 1; //分别对3个节点·进行·数据的存储node2-data 2;node3-data 3;node1-next node2; //每个节点的next的指针指向下一个节点的地址node2-next node3;node3-next NULL;plist node1;my_printf(plist);
}
int main()
{test();return 0;
}结果运行图 我们的指针plist就是个牵引的作用就像高铁一样没有高铁头车厢照样能跑就是不美观没有它也可以正常访问链表。有了它就是逻辑上和美观上要舒服很多。如图所示
实现单链表
和顺序表一样我们也是创建3个文件: Sqlist .h Sqlist.c和test .c文件。具体的原因个顺序表一样的。接下来我直接给大家展示代码我会在注释中详细讲解的。
Sqlist.h:
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
typedef int SListDatatype;
typedef struct SListNode
{SListDatatype data;struct SListNode* next;
}SLND;SLND* SListFind(SLND* phead, SListDatatype x);//找对应的节点
SLND* SLTButnode(SListDatatype x);//申请新的节点
void my_printf(SLND* phead); //·打印链表信息void SListpushback(SLND** pphead, SListDatatype x); //尾插
void SListpopback(SLND** pphead);//尾删void SListpushFront(SLND** pphead, SListDatatype x); //头插
void SListpopFront(SLND** pphead);//头删void SListrdFrontpush(SLND** pphead, SLND* find, SListDatatype x);//在任意节点之前插入数据
void SListrdBackpush(SLND* find, SListDatatype x);//在任意节点之后插入数据void SListposePop(SLND* phead, SLND* pose); //删除指定节点
void SListDestry(SLND** pphead); //销毁链表Sqlist.c:
#include SList.h
//打印链表信息
void my_printf(SLND* phead) //打印信息便于我们看信息的输出
{SLND* pcur phead;while (pcur){printf(%d- ,pcur-data);pcur pcur-next;}printf(NULL\n); //第N1个为空没有链表
}
SLND * SLTButnode(SListDatatype x) //申请新空间返回新空间地址便于咱们找到新空间插入数据
{SLND* newnode (SLND*)malloc(sizeof(SLND));if (newnode NULL){perror(malloc fail!);exit(1); //若开辟失败就直接退出程序也可以写成 return 1;}else{newnode-data x; //走到这里就开辟成功进行初始化newnode-next NULL;}return newnode;
}
void SListpushback(SLND** pphead, SListDatatype x) //尾插数据
{assert(pphead); //检查传递的指针是否为空指针SLND* newnode SLTButnode(x);if (*ppheadNULL) {*pphead newnode; //如果起始没有节点先创立个节点}else{SLND* ptail *pphead;while (ptail-next) //遍历节点找到最后一个节点的next为空的情况跳出循环{ptail ptail-next; }ptail-next newnode; //走到这里说明找到了最后一个节点在此之后插入新的节点}
}
void SListpopback(SLND** pphead) //尾删数据
{assert(pphead*pphead); //检查传递的指针是否为空指针 SLND* ptail *pphead; //我们把起始节点的地址给ptail用ptail进行遍历数据去寻找最后的尾节点SLND* prev NULL; //prev是用来记录尾节点前一个节点不记录的话就会随着我们删除最后一个节点而丢失信息while (ptail-next){prev ptail;ptail ptail-next;}prev-next NULL;free(ptail); //找到最后一个节点进行空间释放ptail NULL; //释放后要置空防止产生野指针
}
void SListpushFront(SLND**pphead,SListDatatype x) //头插数据
{assert(pphead); //判断传递的地址是否为空指针SLND* newnode SLTButnode(x);newnode-next *pphead;*pphead newnode;
}
void SListpopFront(SLND**pphead)//头删
{assert(pphead*pphead); //判断传递的地址是否为空指针SLND*next (*pphead)-next;free(*pphead); //释放头节点*pphead next; //释放头节点后要使得plist指向第二个节点
}
SLND* SListFind(SLND*phead,SListDatatype x) //找对应的节点
{assert(phead); //判断传递的地址是否为空指针while (phead){if (phead-data x)return phead; //找到目标节点就返回目标节点的地址phead phead-next;}return NULL; //没找到就返回空指针
}
void SListrdFrontpush(SLND**pphead,SLND*find,SListDatatype x)//在任意节点之前插入数据
{assert(pphead*pphead); //判断传递的地址是否为空指针if (*pphead find) //任意位置刚好是头节点时相当于头插数据SListpushFront(pphead, x); //头插数据else {SLND*newnode SLTButnode(x);//申请新的节点SLND* prev NULL;SLND* ptail *pphead;while (ptail! find){prev ptail;ptail ptail-next;}prev-next newnode; //指定位置之前的节点的next指针指向要插入的新节点newnode-next ptail; //这个新节点的next指针指向下一个节点}
}
void SListrdBackpush( SLND* find, SListDatatype x)//在任意节点之后插入数据
{assert(find); //判断传递的地址是否为空指针SLND* newnode SLTButnode(x);newnode-next find-next; //新节点的next指针指向下一个节点find-next newnode; //新节点之前的节点next指针指向这个新节点
}
void SListposePop(SLND**pphead, SLND* pose) //删除指定节点
{assert(*ppheadpose); //判断传递的地址是否为空指针if(pose*pphead) //当删除的节点是头节点时就相当于头删SListpopFront(pphead);//头删else{SLND* prev NULL; SLND* ptail *pphead;while (ptail ! pose) //遍历节点找到目标节点{prev ptail;ptail ptail-next;}SLND* next ptail-next; prev-next next;free(ptail); //删除指定的节点ptail NULL; //置空指针防止发生野指针}
}//链表的销毁和顺序表不一样
void SListDestry(SLND**pphead) //链表的销毁不像顺序表那样直接释放内存就欧克因为每个
{ //节点都是独立的所以我们需要去遍历每个节点去销毁assert(*pphead); //判断传递的地址是否为空指针SLND* prev NULL;SLND* ptail *pphead;while (ptail-next) //一直遍历到最后一个节点才结束{prev ptail;ptail ptail-next;free(prev); //每遍历一个节点就释放prev NULL; //置空指针防止产生野指针}ptail NULL; //置空指针防止产生野指针*pphead NULL; //置空指针防止产生野指针
}test.h
#define _CRT_SECURE_NO_WARNINGS 1
#include SList.h
void test()
{ //这里给大家演示一下尾插数据其它功能大家可以自行尝试一下SLND* plist NULL;SListpushback(plist,1);//尾插SListpushback(plist,2);//尾插SListpushback(plist,3);//尾插SListpushback(plist,4);//尾插my_printf(plist);
}int main()
{test();return 0;
}结果运行图
彩蛋时刻
歌曲《All Falls Down》听会儿歌曲放松一下呗 每章一句道路是曲折的前途是光明的感谢你能看到这里点赞关注收藏转发是对我最大的鼓励咱们下期见
