h5网站制作视频,wordpress系统密码忘记,服装企业的网站建设,深圳公众号开发目录 一、线性表二、顺序表2.1 概念及结构2.2 接口实现2.3 一些思考以及顺序表的缺点 三、链表3.1 概念及结构3.2 链表的分类3.3 链表的实现3.3.1 无头单向非循环链表3.3.2 带头双向循环链表 四、顺序表和链表的区别 一、线性表
线性表#xff08;linear list#xff09;是n… 目录 一、线性表二、顺序表2.1 概念及结构2.2 接口实现2.3 一些思考以及顺序表的缺点 三、链表3.1 概念及结构3.2 链表的分类3.3 链表的实现3.3.1 无头单向非循环链表3.3.2 带头双向循环链表 四、顺序表和链表的区别 一、线性表
线性表linear list是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上或者说实际的数据存储中并不一定是连续的线性表中的元素在物理存储时通常以数组或链式结构的形式存储。
二、顺序表
2.1 概念及结构
顺序表Sequence List是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为静态顺序表与动态顺序表。 静态顺序表使用定长数组存储数据元素。 动态顺序表使用动态开辟的数组存储数据元素。
例如
//静态顺序表的实现
#define CAPACITY 10//宏定义数组长度 CAPACITY
typedef int SLDataType//数组元素类型重命名为 SLDataType
typedef struct SeqList
{SLDataType array[NUMSSIZE];//定长数组size_t size;//有效数据的个数
}SeqList;首先是宏定义#define为了方便统一修改与重定义定长数组的长度通常会使用宏定义一个变量作为数组长度这样变量就可以用来定义数组长度了。相似的为了方便统一修改与重定义数组元素的类型通常会使用typedef将数组元素类型重命名为SLDataType。其次是在顺序表的结构体定义中通常除了数组这个结构体成员外还有一个size_t类型的结构体成员用于记录数组的有效元素个数同时也记录了数组最后一个元素的下标即有效数据个数减1。
//动态顺序表的实现
typedef int SLDataType//数组元素类型重命名为SLDataType
typedef struct SeqList
{SLDataType* array;//指向动态数组地址的指针size_t size;//有效数据个数size_t capacity;//动态数组最大容量空间的大小
}SeqList;与静态顺序表一样为了方便修改动态数组元素类型对数组元素类型进行了重命名。在顺序表的结构体内部动态顺序表定义了一个数组元素类型的指针来指向数组所在空间在C语言修炼的指针篇中我们详细介绍过了数组与指针本质上的联系——传送门。动态顺序表相较静态顺序表增加了一个变量用于记录动态开辟出来的数组大小/容量毕竟调用相关函数开辟空间也是有时间空间上的消耗的所以不可能存储一个就开辟一个而是按一定规律提前开辟好空间与扩容。
2.2 接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组如果定大了容易造成空间浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态分配空间大小所以下面我们实现动态顺序表。
动态顺序表增删查改的实现
typedef int SLDataType;//根据需要修改数组元素类型
typedef struct SeqList
{SLDataType* arr;size_t size;//有效数据个数size_t capacity;//空间容量
}SL;//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
//数组空间扩容
void SLCheckCapacity(SL* ps);
//顺序表打印
void SLPrint(SL s);
//头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
//删除指定位置的数据
void SLErase(SL* ps, int pos);
//查找顺序表中的数据
SLDataType SLFind(SL s, SLDataType x);后面需要用到的头文件有
#includestdio.h
#includeassert.h//提供assert断言函数帮助判断指针是否为空或数据是否有效
#includestdlib.h//提供freerealloc函数顺序表的初始化与销毁 当我们定义了顺序表的结构体后我们就可以定义结构体变量了一个结构体变量SL s代表一个顺序表。但定义了变量后还需要进行顺序表的初始化。顺序表不用之后也需要销毁并释放动态开辟的空间。 代码示例如下
void SLInit(SL* ps)//顺序表初始化
{assert(ps);//对 ps 指针判空//顺序表结构体变量的成员变量初始化ps-arr NULL;ps-capacity ps-size 0;
}
void SLDestroy(SL* ps)//顺序表销毁
{assert(ps);if (ps-arr)//判断arr数组是否开辟了空间{free(ps-arr);//释放所开辟空间防止内存泄漏}ps-arr NULL;ps-capacity ps-size 0;
}一定要注意函数的参数问题首先传递过来的一定是顺序表变量SL s的地址传值调用是无法改变实参——顺序表变量的只有传址调用才能改变实参的值。其次是对传递过来的指针参数SL* ps进行判空空指针是无法解引用访问的。 在顺序表的销毁中需要注意对程序申请的空间进行释放程序在关闭时会主动进行内存空间的释放但如果程序一直不结束就会造成内存泄漏问题。
数组空间的扩容 动态顺序表的重点就是动态的空间分配因此扩容函数的实现非常关键。 代码如下
void SLCheckCapacity(SL* ps)//检查空间容量与扩容
{assert(ps);//判空if (ps-size ps-capacity)//判断数组大小是否等于容量{//数组大小等于空间容量则空间不足直接扩容int newCapacity ps-capacity 0 ? 4: 2 * ps-capacity;SLDataType* tmp (SLDataType*)realloc(ps-arr, newCapacity * sizeof(SLDataType));//重新申请空间if (!tmp)//判断空间是否申请成功{//申请失败报错并退出程序perror(realloc fail!);exit(1);//直接退出程序}//空间申请成功ps-arr tmp;//更新arr指针ps-capacity newCapacity;//更新空间容量}
}扩容要注意的是一定不能直接用内存函数realloc对原数组空间进行调整因为存在空间申请失败的可能所以需要先判断是否申请空间成功再将有效的新空间给数组。 在扩容数量的选择上通常按二倍二倍的扩容经过数学统计与分析这是最高效且节省资源的扩容方式。但我们不能直接int newCapacity 2 * ps-capacity;因为在顺序表的初始化中空间容量的初始值是0而0乘以任何数为0所以这里取巧使用了一个三目操作符ps-capacity 0? 4: 2 * ps-capacity如果ps-capacity为0则返回4如果不为0则返回它的2倍三目操作符的返回值又赋值给了newCapacity。
头删尾删头插尾插 数据的头删头插即删除数组的第一个元素或在所有元素之前插入数据。尾删尾插同理删除数组的最后一个有效元素或在所有元素之后插入数据。 代码示例如下
void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);//判空SLCheckCapacity(ps);//检查空间容量ps-arr[ps-size] x;//从后面插入数据
}
void SLPushFront(SL* ps, SLDataType x)//头插
{assert(ps);SLCheckCapacity(ps);for (int i ps-size; i 0; i--)//当前有效元素整体后移一位{ps-arr[i] ps-arr[i - 1];}ps-arr[0] x;//头插赋值ps-size;//更新有效数据个数
}
void SLPopBack(SL* ps)//尾删
{assert(ps);assert(ps-size);//判断元素有效个数是否为0为0报错警告ps-size--;//元素有效个数不为0直接有效元素个数减1即可
}
void SLPopFront(SL* ps)//头删
{assert(ps);for (int i 0; i ps-size - 1; i){//除了第一个有效元素后面元素整体前移一位覆盖第一个元素ps-arr[i] ps-arr[i 1];}ps-size--;//有效元素个数减1
}指定位置插入新数据
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);//确保pos坐标合法SLCheckCapacity(ps);for (int i ps-size; i pos; i--){//从下标pos这个位置到最后一个有效元素整体后移一位空出pos位置ps-arr[i] ps-arr[i - 1];}ps-arr[pos] x;//赋值插入数据ps-size;//有效元素个数加1
}删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);for (int i pos; i ps-size - 1; i){//pos后的元素整体前移一位覆盖pos位置ps-arr[i] ps-arr[i 1];}ps-size--;//有效元素个数减1
}查找指定数据的位置 查找数据只需要返回数据的位置信息即可不需要改变顺序表信息所以顺序表变量的传参为传值调用即可。
SLDataType SLFind(SL s, SLDataType x)
{for (int i 0; i s.size; i)//遍历数组{if (s.arr[i] x)//找到第一个指定数据直接返回{return i;}}return -1;//遍历完数组未找到指定数据则返回特定值视情况设置
}2.3 一些思考以及顺序表的缺点
缺点
中间/头部的插入删除操作不方便需要遍历顺序表时间复杂度为O(N)。增容需要申请新空间拷贝数据释放旧空间会有不小的消耗。增容一般是呈二倍的增长无法避免会存在一定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间而且这种浪费现象有可能随着扩容次数的增加越来越严重。
思考如何解决以上问题呢接下来我们进入链表的学习或许能找到答案。
三、链表
3.1 概念及结构
概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 从上图可以看出
链式结构在逻辑上是连续的但物理存储上并不一定连续。链表结点一般都是从堆上申请的空间。从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续。链表一般分为数据域与指针域两个部分数据域存储了数据信息指针域存储了相关结点的地址信息。
3.2 链表的分类
链表分为带头 / 不带头循环 / 不循环单向 / 双向。可以分别构成8种链表结构。 但实际中最常用的还是 无头单向不循环 / 带头双向循环 链表。
无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等。另外这种结构在笔试面试中出现很多。带头双向循环链表结构最复杂一般用于单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现其带来了很多优势实现反而简单了。
3.3 链表的实现
3.3.1 无头单向非循环链表
//实现单链表 Single Linked List 的增删查改
typedef int SLTDataType;
typedef struct SListNode//定义链表结点的结构体
{SLTDataType data;struct SListNode* next;//下一个结点为结构体类型不是SLTDataType
}SLTNode;//输出单链表数据
void SLTPrint(SLTNode* phead);
//动态申请一个结点
SLTNode* SLBuyNode(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);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);需要用到的头文件
#includestdio.h
#includestdlib.h//提供free,malloc函数
#includeassert.h//提供assert函数头插尾插头删尾删
//动态申请一个结点
SLTNode* SLBuyNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));//动态申请一块空间if (!newnode)//申请失败则报错并退出{perror(malloc fail!\n);exit(1);}newnode-data x;//初始化结点数据域的信息newnode-next NULL;//初始化结点指针域的信息return newnode;//返回新结点
}需要注意的是单向不带头链表的头结点即有效结点创建时需要在堆上动态申请空间所以先实现一个结点申请函数便于后续操作。接着我们就可以借助结点申请函数来创建单链表了。单链表的创建需要创建一个单链表结点结构体类型的指针变量例如SLTNode* phead SLBuyNode(x);。需要知道的是像这样的一个指针作为头节点就可以指向一整个链表这就是单链表的初始化。
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{//要改变指向头节点的指针就需要传递头节点的地址即phead则形参pphead类型为二级指针SLTNode**assert(pphead);//后续需要通过二级指针pphead访问头节点先检查形参的有无有效性即判空SLTNode* newnode SLBuyNode(x);//申请需要尾插的新结点//尾插有两种情况if (!*pphead){//头节点为空*pphead newnode;}else{//头节点不为空SLTNode* ptmp *pphead;while (ptmp-next) //找单链表表尾即最后一个结点ptmp{ptmp ptmp-next;}ptmp-next newnode;//将尾结点的next指向新结点}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLBuyNode(x);newnode-next *pphead;//直接将新结点的next指向原头节点即可*pphead newnode;//更新头节点指针信息指向新头节点
}
//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead *pphead);//删除操作不仅要保证pphead不为空还要保证链表不为空即头节点不为空//如果链表有多个结点尾删需要先找到尾结点以及尾结点的前一结点SLTNode* pcur *pphead;//找尾结点SLTNode* prev *pphead;//找尾结点前一结点if (!pcur-next){//一个结点直接释放头节点同时头结点置为空free(pcur);*pphead NULL;}else{//多个结点遍历链表while (pcur-next){prev pcur;pcur pcur-next;}prev-next NULL;//前结点的next置为空free(pcur);//释放尾结点}
}
//头删
void SLTPopFront(SLTNode** pphead)
{//删除操作需要保证pphead不为空且链表不为空assert(pphead *pphead);SLTNode* del *pphead;//保存需要删除的头结点*pphead (*pphead)-next;//头结点置为原头结点的下一结点free(del);//释放原头结点
}输出链表数据
void SLTPrint(SLTNode* phead)
{//一个简单的遍历即可SLTNode* pcur phead;while (pcur){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}查找特定数据
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur phead;while (pcur)//简单的遍历比较判断{if (pcur-data x){//找到第一个符合条件的结点直接返回该结点即可return pcur;}pcur pcur-next;}return NULL;//遍历链表未找到则返回空指针
}指定位置插入删除 需要注意什么是指定位置呢它又是如何表示的呢由于链表不同于顺序表可以通过下标找到指定位置的数据因此这个指定位置其实是某个结点——一整个结点这里可以配合上面的查找接口完成整个操作逻辑。在插入或删除指定位置操作时我们需要注意保证链表不会断开仔细斟酌前、后结点与指定结点的next。
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{//在指定位置插入亦需要保证pphead链表以及位置有效不为空assert(pphead *pphead pos);SLTNode* newnode SLBuyNode(x);//结点在指定位置前的插入有两种情况if (*pphead pos){//头节点为指定位置newnode-next *pphead;//新结点的next指向头节点*pphead newnode;//头节点置为新结点}else{//指定位置不为头节点SLTNode* prev *pphead;//遍历找到指定位置结点的前一结点while (prev-next ! pos){prev prev-next;}newnode-next pos;//新节点的next指向指定结点prev-next newnode;//指定结点前一结点的next指向新结点}
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{//修改结点结构体内的信息传参结构体类型指针变量即可同时需要确保pos的有效性assert(pos);SLTNode* newnode SLBuyNode(x);newnode-next pos-next;//新结点的next指向pos的下一结点pos-next newnode;//pos的next指向新结点
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{//删除整个结点需要确保结点的地址pphead有效链表不为空以及pos有效assert(pphead *pphead pos);//指定结点的删除有两种情况if (*pphead pos){//指定结点为头节点*pphead (*pphead)-next;//新头节点为原头节点的下一结点free(pos);//释放原头节点}else{//指定结点不为头结点SLTNode* prev *pphead;//找到指定结点前一结点while (prev-next ! pos){prev prev-next;}prev-next prev-next-next;//指定结点前一结点的next指向pos后一结点free(pos);//释放指定结点}
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos pos-next);SLTNode* del pos-next;//保存需要删除的结点pos-next del-next;//pos的next指向删除结点的下一结点free(del);
}销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead);SLTNode* pcur *pphead;while (pcur)//遍历链表{SLTNode* del pcur;//先保存删除结点pcur pcur-next;//再找到下一结点free(del);//释放删除结点}*pphead NULL;//链表置为空
}3.3.2 带头双向循环链表
带头双向循环链表的“头”即哨兵位也称头节点但这里的头节点就没有实际意义了仅仅作为一个标记也不会存储数据信息只会存储前一结点与后一结点的地址信息。
//带头双向循环链表 Linked List 增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//申请结点
LTNode* LTBuyNode(LTDataType x);
//双向循环链表的初始化
LTNode* LTInit();
// 双向链表销毁
void LTDestory(LTNode* phead);
// 双向链表打印
void LTPrint(LTNode* phead);
// 头部插入删除/尾部插入删除
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
// 双向链表查找
LTNode* LTFind(LTNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos);需要用到的头文件与单链表相同。
双向循环链表的初始化与销毁
//申请结点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode));if (!node){perror(malloc fail!\n);exit(1);}node-data x;node-next node-prev node;//只有一个结点的双向循环链表前后结点都是自己return node;
}
//双向循环链表的初始化
LTNode* LTInit()
{LTNode* phead LTBuyNode(-1);//哨兵位取任意值即可return phead;//返回哨兵位结点
}
// 双向链表销毁
void LTDestory(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;//跳过哨兵位找下一有效结点//销毁结点while (pcur ! phead)//遍历链表{//先保存下一结点再销毁上一结点LTNode* ptmp pcur-next;free(pcur);pcur ptmp;}//销毁哨兵位free(phead);pcur phead NULL;
}双向链表打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}头部插入删除/尾部插入删除
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//先修改新尾结点的指针域信息newnode-next phead;//尾插next指向哨兵位newnode-prev phead-prev;//尾插prev指向原尾结点//再修改哨兵位与原哨兵位前结点phead-prev-next newnode;//原哨兵位前结点的next指向新尾结点phead-prev newnode;//哨兵位的prev指向新尾结点
}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead phead-next ! phead);//确保双向循环链表存在有效结点LTNode* del phead-prev;//先保存尾结点//修改尾结点前后结点的指向del-prev-next phead;//尾结点前一结点变为新尾结点next指向哨兵位phead-prev del-prev;//哨兵位的prev指向新尾结点free(del);//删除原尾结点del NULL;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//先修改新结点的指针域信息newnode-prev phead;//头插prev指向哨兵位newnode-next phead-next;//头插next指向哨兵位下一结点//再修改哨兵位与原哨兵位下一结点指向phead-next-prev newnode;//原哨兵位下一结点的prev指向新结点phead-next newnode;//哨兵位的next指向新结点
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead phead-next ! phead);LTNode* del phead-next;del-next-prev phead;phead-next del-next;free(del);del NULL;
}双向链表查找:
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead)//遍历双向链表{if (pcur-data x){//找到第一个符合条件的结点直接返回结点return pcur;}pcur pcur-next;}return NULL;//未找到数据返回空
}双向链表指定位置插入删除
// 双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos pos-prev);LTNode* newnode LTBuyNode(x);newnode-prev pos-prev;newnode-next pos;pos-prev-next newnode;pos-prev newnode;
}
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos)
{assert(pos pos-prev pos-next);pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);pos NULL;
}四、顺序表和链表的区别 顺序表的优点有:连续存储访问方便高效存储缓存利用率高等。 链表的优点在于方便插入删除操作没有容量限制动态申请创建结点。 注缓存利用率参考存储体系结构以及局部原理性。
这里附上一个介绍缓存相关知识的佳文——与程序员相关的CPU缓存知识。 本篇到此结束下一篇将会带来顺序表以及链表相关的OJ题分享用于学习与巩固做更深一步的提升。
