那种网站打不开,做摄影网站的目的是什么意思,ui设计师找工作,某些网站字号设置样式文章目录 单链表概念链接存储方法头指针head和终端结点链接过程单链表的优缺点#xff1a;实现代码一览 单链表概念 链表中的数据是以结点来表示的#xff0c;每个结点的构成#xff1a;元素(数据元素的映象) 指针(指示后继元素存储位置)#xff0c;元素就是存储数据的存储… 文章目录 单链表概念链接存储方法头指针head和终端结点链接过程单链表的优缺点实现代码一览 单链表概念 链表中的数据是以结点来表示的每个结点的构成元素(数据元素的映象) 指针(指示后继元素存储位置)元素就是存储数据的存储单元指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表单链表单链表是链式存取的结构。 链接存储方法 链接方式存储的线性表简称为链表Linked List。 链表的具体存储表示为 ① 用一组任意的存储单元来存放线性表的结点这组存储单元既可以是连续的也可以是不连续的 ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系在存储每个结点值的同时还必须存储指示其后继结点的地址或位置信息称为指针pointer或链(link) 链式存储是最常用的存储方式之一它不仅可用来表示线性表而且可用来表示各种非线性的数据结构。 结点结构 data域–存放结点值的数据域 next域–存放结点的直接后继的地址位置的指针域链域 链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的每个结点只有一个链域的链表称为单链表Single Linked List。 头指针head和终端结点 单链表中每个结点的存储地址是存放在其前趋结点next域中而开始结点无前趋故应设头指针head指向开始结点。链表由头指针唯一确定单链表可以用头指针的名字来命名。 终端结点无后继故终端结点的指针域为空即NULL。 链接过程
从逻辑上 从物理上
单链表的优缺点
1、优点 插入和删除操作方便在单链表中插入和删除节点时只需修改相邻节点的游标即可不需要移动大量数据因此操作效率较高。适合动态存储单链表可以随时插入和删除节点因此适合动态存储数据。空间利用率高单链表不需要连续的存储空间因此可以更有效地利用内存空间。 2、缺点 查找效率低在单链表中查找某个元素需要从头节点开始遍历整个链表因此查找效率较低。 需要额外的空间存储游标单链表需要额外的空间存储游标这会增加内存空间的消耗。实现复杂度较高相比数组等数据结构单链表的实现复杂度较高需要维护节点的引用关系。 实现
一.思路 1.利用结构体来储存数据和指针结构体能够存储不同类型数据 2.每增加一个数据就通过malloc函数来扩展一个空间 3.通过多文件的方式来实现 4.我们实现打印、扩容、尾插、头插、尾删、头删接口函数 二.框架 结构体创建、一些定义
#includestdio.h
#includestdlib.h//动态内存函数的头文件
typedef int SLTDataType;//类型定义
struct SListNode
{SLTDataType data;//数据struct SListNode* next;//链接点
};
typedef struct SListNode SLTNode;//类型定义主函数
void Test() {SLTNode* plist NULL;//头指针初始化 因为开始是没有数据}
int main() {Test();//调用函数return 0;
}三.接口函数的实现 1.打印函数 1参数结构体指针类型接收头指针由于不需要改变头指针所以传一个头指针变量过来就行 2迭代将后一个链接的指针变量 next 传给指针phead来找到下一个结点 代码实现
void SListPrint(SLTNode* phead) {//打印函数//由于不需要改变头指针所以传一个头指针变量过来就行了while (phead ! NULL) {//将phead不是空指针之前的数据打印printf(%d-, phead-data);//打印数据phead phead-next;//迭代}printf(NULL);//最后打印指向的NUll
}2.扩容函数 1我们通过malloc函数来实现扩容 2参数插入的数据 3返回类型返回扩建的空间指针变量 4过程在扩容后将插入的数据存储到这个空间里。并把指针变量置空 代码实现
SLTNode* uuu(SLTDataType x) {//扩容和储存数据SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));newnode-data x;//储存数据newnode-next NULL;//将扩容和的链接点置空return newnode;//放回这个空间的地址
}3.尾插函数 有两种情况 1头指针为空此时将扩建的第一个空间直接当头指针 2头指针不为空此时将我们要通过头指针找到最后一个结点再用这个结点来链接我们扩建的空间 注意 1.在实现这个过程可能会改变头指针所以传参需要使用传址调用 2.第二种情况不要改变头指针
代码实现
void SListPushBack(SLTNode** pphead, SLTDataType x) {//尾插
//注意这里需要传参需要进行传址调用SLTNode* newnode uuu(x);//插入一个数据需要再创建一个新的空间if (*pphead NULL)//判断是否是第一种情况*pphead newnode;else{SLTNode* cat *pphead;//防止头指针被改变while(cat-next!NULL){//找到最后一个结点cat cat-next;//迭代}cat-next newnode;//将扩展的空间连接在最后一个结点的next上}
}检查 我们尾插 1、2
SListPushBack(plist, 1);
SListPushBack(plist, 2);
SListPrint(plist);4.头插函数 1我们直接将创建的空间的next与第一个结点连接即可 注意在实现这个过程会改变头指针所以传参需要使用传址调用 代码实现
void SListPushFront(SLTNode** pphead, SLTDataType x) {头插SLTNode* newnode uuu(x);//扩建空间newnode-next *pphead;//与第一个结点连接即头指针*pphead newnode;//将头指针改为头插的空间
}检查 我们头插一个 0
void Test() {SLTNode* plist NULL;SListPushBack(plist, 1);SListPushBack(plist, 2);SListPushFront(plist, 0);SListPrint(plist);
}运行结果 5头删函数 1这个我们不用创建新的空间但是要释放空间。释放函数 ferr 2我们可以创建一个新的指针变量来接收第一个结点的next第二个结点的地址然后将第一个结点释放掉再然后将新的指针变量当作头指针 3在实现这个过程会改变头指针所以传参需要使用传址调用 代码实现
void SListPopFront(SLTNode** pphead) {//头删SLTNode* next (*pphead)-next;//创建一个新的指针变量来接收第一个结点的next第二个结点的地址free(*pphead);//释放*pphead next;//重新设置头指针
}检查 头删一个数据
void Test() {SLTNode* plist NULL;SListPushBack(plist, 1);SListPushBack(plist, 2);SListPushFront(plist, 0);SListPopFront(plist);SListPrint(plist);
}运行结果 6.尾删函数 分三种情况 1没有结点 返回NULL 2有一个结点 将其直接释放并置空 3多个结点 我们要创建两个新的变量分别来找倒数第一和第二个结点释放最后一个结点倒数第二个结点next置空
代码实现
void SListPopBack(SLTNode** pphead) {//尾删if (*pphead NULL)//当为空是直接返回空return;else if ((*pphead)-next NULL) {//只有一个结点时直接释放掉pphead并将其置空free(*pphead);*pphead NULL;}else {//多个结点SLTNode* cat *pphead;//为了不改变头指针创建一个新的变量SLTNode* cat1 NULL;//用于找到倒数第二个结点最后将其next置空while (cat-next ! NULL) {//找最后一个结点cat1 cat;cat cat-next;}free(cat);//释放最后一个结点cat1-next NULL;//倒数第二个结点next置空}
}检查 尾删一个数据
void Test() {SLTNode* plist NULL;SListPushBack(plist, 1);SListPushBack(plist, 2);SListPushFront(plist, 0);SListPopFront(plist);SListPopBack(plist); SListPrint(plist);
}运行结果
代码一览
SList.h
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestdlib.h//动态内存函数的头文件
typedef int SLTDataType;//类型定义
struct SListNode
{SLTDataType data;//数据struct SListNode* next;//链接点
};
typedef struct SListNode SLTNode;//类型定义// 不会改变链表的头指针传一级指针
void SListPrint(SLTNode* phead);// 可能会改变链表的头指针传二级指针
void SListPushBack(SLTNode** pphead, SLTDataType x);//尾插
void SListPushFront(SLTNode** pphead, SLTDataType x);//头插
void SListPopFront(SLTNode** pphead);头删
void SListPopBack(SLTNode** pphead);//尾删SList.c
#define _CRT_SECURE_NO_WARNINGS
#includeSList.hvoid SListPrint(SLTNode* phead) {//打印函数//由于不需要改变头指针所以传一个头指针变量过来就行了while (phead ! NULL) {//将phead不是空指针之前的数据打印printf(%d-, phead-data);//打印数据phead phead-next;//迭代}printf(NULL);//最后打印指向的NUll
}SLTNode* uuu(SLTDataType x) {//扩容和储存数据SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));newnode-data x;//储存数据newnode-next NULL;//将扩容和的链接点置空return newnode;//放回这个空间的地址
}void SListPushBack(SLTNode** pphead, SLTDataType x) {//尾插SLTNode* newnode uuu(x);if (*pphead NULL)*pphead newnode;else{SLTNode* cat *pphead;while(cat-next!NULL){cat cat-next;}cat-next newnode;}
}
void SListPushFront(SLTNode** pphead, SLTDataType x) {头插SLTNode* newnode uuu(x);newnode-next *pphead;*pphead newnode;
}
void SListPopFront(SLTNode** pphead) {//头删SLTNode* next (*pphead)-next;free(*pphead);*pphead next;
}void SListPopBack(SLTNode** pphead) {//尾删if (*pphead NULL)return;else if ((*pphead)-next NULL) {free(*pphead);*pphead NULL;}else {SLTNode* cat *pphead;SLTNode* cat1 NULL;while (cat-next ! NULL) {cat1 cat;cat cat-next;}free(cat);cat1-next NULL;}
}Test:
#define _CRT_SECURE_NO_WARNINGS
#includeSList.hvoid Test() {SLTNode* plist NULL;SListPushBack(plist, 1);SListPushBack(plist, 2);SListPushFront(plist, 0);SListPopFront(plist);SListPopBack(plist);SListPrint(plist);
}
int main() {Test();return 0;
}还有查改等没写有兴趣的可以去试试哦 以上就是我的分享了如果有什么错误欢迎在评论区留言。 最后谢谢大家的观看
