win7 iis网站无法显示该页面,看看铜陵新闻,网址之家大全,做外贸网站推广一.前言 数据结构思维导图如下#xff0c;灰色标记的是之前讲过的#xff0c;本文将带你走近单链表(红色标记部分)#xff0c;希望大家有所收获#x1f339;#x1f339; 二.链表的定义和概念
在讲单链表之前#xff0c;我们先学习一下链表
2.1 链表的定义
链表是一种…一.前言 数据结构思维导图如下灰色标记的是之前讲过的本文将带你走近单链表(红色标记部分)希望大家有所收获 二.链表的定义和概念
在讲单链表之前我们先学习一下链表
2.1 链表的定义
链表是一种物理存储单元上非连续非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的即
逻辑结构线性物理结构非线性
2.2 节点的构成要素
链表由一系列结点链表中每一个元素称为结点组成结点可以在运行时动态生成。 每个结点包括两个部分一个是存储数据元素的数据域另一个是存储下一个结点地址的指针域。即数据指向下一个结点的指针节点常用结构体实现。
struct ListNode
{
LTDataType data;
struct ListNode* next;
}2.3 与数组结构的对比差异
数组链表存储方式连续存储需要预先分配固定大小的内存空间非连续存储通过指针连接动态分配内存不需要预先确定大小内存使用空间利用率高 (因为所有元素都紧密排列)可能存在未使用的空间e.g.数组大小固定但实际使用元素少空间利用率相对较低每个节点需要额外的内存来存储指针插入和删除操作可能需要移动大量元素以保持连续性时间复杂度为O(n)因为可能需要移动插入点之后的所有元素通常只需要改变指针不需要移动元素 时间复杂度为O(1) (已知插入或删除位置的节点)随机访问支持高效的随机访问可通过索引快速访问任意元素 访问时间复杂度为O(1)不支持高效的随机访问必须从头节点开始遍历链表访问时间复杂度为O(n)。空间局部性有很好的空间局部性因为元素连续存储适合缓存优化空间局部性差因为元素分散存储可能导致缓存未命中实现复杂度实现简单大多数编程语言内置支持实现相对复杂需要手动管理节点和指针适用场景适合需要频繁随机访问的场景适合元素数量已知且变化不大的场景适合插入和删除操作频繁的场景适合元素数量频繁变化的场景
三.链表的分类
链表的结构非常多样以下情况组合起来就有8种2*2*2链表结构 链表说明 虽然有这么多的链表结构但是我们实际中最常用的还是两种结构
单链表不带头单向不循环链表双向链表带头双向循环链表
四.单链表
前期准备
创建三个文件
SList.h 存放各种头文件和函数声明SLIst.c 各种函数的实现test.c 测试和执行代码 最好写完一部分测试一部分 防止后期调试一堆bug
实现
首先在头文件中写上
#include stdio.h
#include stdlib.h
#include assert.h接下来我们一步步实现单链表各种操作
1.定义链表结构
typedef int SLTDataType;//方便之后一键替换类型typedef struct SListNode
{SLTDataType data; //结点数据struct SListNode* next; //指针保存下⼀个结点的地址
}SLTNode;2.申请新节点和打印函数
因为后面会多次用到申请新节点和打印函数所以我们把它们都各自封装成函数方便调用
//申请新节点
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node (SLTNode*)malloc(sizeof(SLTNode));if (node NULL){perror(malloc fail!);exit(1);}node-data x;node-next NULL;return node;
}
//打印函数
void SLTPrint(SLTNode* phead)
{SLTNode* pcur phead;while (pcur){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}3.查找数据
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur phead;while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}//没有找到return NULL;
}4.插入操作
包括尾插、头插、在指定位置之前插入数据、在指定位置之后插入数据 1尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//pphead -- plist// *pphead -- plist//申请新节点SLTNode* newnode SLTBuyNode(x);if (*pphead NULL){*pphead newnode;}else{//找尾结点SLTNode* pcur *pphead;while (pcur-next){pcur pcur-next;}//pcur newnodepcur-next newnode;}
}2头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x);//newnode *ppheadnewnode-next *pphead;*pphead newnode;
}3在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos *pphead){SLTPushFront(pphead, x);}else{SLTNode* newnode SLTBuyNode(x);//找prev :pos的前一个结点SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//prev newnode -- posnewnode-next pos;prev-next newnode;}
}4在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode SLTBuyNode(x);//pos newnode -- pos-nextnewnode-next pos-next;pos-next newnode;
}测试如下
5.删除操作
包括尾删、头删、删除指定节点、删除指定位置之后的结点、删除指定位置之前的结点(该操作是给你们留的作业 学完这篇自己独立实现一下 答案可以让我发给你或者其实调试通过了应该没什么问题跟前面的实现逻辑一样 1尾删
void SLTPopBack(SLTNode** pphead)
{//链表为空不可以删除assert(pphead *pphead);//处理只有一个结点的情况:要删除的就是头结点 if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{//找 prev ptailSLTNode* ptail *pphead;SLTNode* prev NULL;while (ptail-next){prev ptail;ptail ptail-next;}prev-next NULL;free(ptail);ptail NULL;}
}测试如下
2头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead *pphead);SLTNode* next (*pphead)-next;//*pphead -- nextfree(*pphead);*pphead next;
}3删除指定节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead *pphead);assert(pos);//头删if (pos *pphead){SLTPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//prev pos pos-nextprev-next pos-next;free(pos);pos NULL;}
}4删除指定位置之后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos pos-next);//pos pos-next pos-next-nextSLTNode* del pos-next;pos-next pos-next-next;free(del);del NULL;
}6.销毁链表
void SListDestroy(SLTNode** pphead)
{assert(pphead *pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}五.总结 单链表的详细实现代码已经上传到我的资源了大家点进主页或者在本文最上方可以下载查看自己去写一下边写边调试会更容易理解和掌握。 接下来会逐步介绍上述思维导图数据结构剩下的部分创作不易希望大家多多支持有什么想法欢迎讨论
