漳州网站建设哪家最正规,广州网站建设V芯ee8888e,wordpress 添加icon,wordpress为什么感觉加载慢引言-线性表 线性表#xff1a; 线性表#xff08;linear list#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构#xff0c;也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上…引言-线性表 线性表 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上存储时通常以数组和链式结构的形式存储。 我们今天的主角顺序表和链表其实都是线性表当然线性表不止包含这两个 线性表 顺序表链表栈队列字符串…… 再次声明线性表的逻辑结构是线性的物理结构不一定是线性 顺序表
概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表一般可以分为
1.静态顺序表使用定长存储元素 2.动态顺序表使用动态开辟数组的存储 来跟我一起手搓个顺序表吧
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间大小所以下面我们手搓动态顺序表。
我们先写一个头文件里面写好我们维护的动态顺序表以及要实现的接口函数
结构及接口Sqlist.h
//Sqlist.h
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includeassert.h
#define INIT_CAPACITY 4
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{SLDataType* a;//指向动态开辟数组int size; // 有效数据个数int capacity; // 空间容量
}SL;//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
//顺序表打印
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//头部插入删除 / 尾部插入删除
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);
//顺序表查找数据
int SLFind(SL* ps,SLDataType x);
往下就可以开始实现我们的顺序表内容了下面对于接口的实现放在 Sqlist.c 中
初始化和销毁
void SLInit(SL* ps)
{ps-a NULL; //开始时给一个空指针ps-capacity ps-size 0;
}void SLDestroy(SL* ps)
{assert(ps); //断言防止ps为空指针ps-capacity ps-size 0;free(ps-a);ps-a NULL;
}顺序表打印
void SLPrint(SL* ps)
{assert(ps);for (int i 0; i ps-size; i) {printf(%d\n,ps-a[i]);}printf(\n);
} 这里需要注意的是在打印过程中往顺序表中放置的数据类型不同所打印的方式也会有所不同在头文件Sqlist.h中 typedef int SLDataType; 这句代码说明放入的数据类型是int所以我这里就使用int的打印方式了。
扩容
void SLCheckCapacity(SL* ps)
{if (ps-size ps-capacity) {int newCapacity ps-capacity 0 ? 4 : 2 * ps-capacity;SLDataType* tmp (SLDataType*)realloc(ps-a, newCapacity * sizeof(SLDataType));//防止开辟空间失败返回空指针if (tmp NULL) {perror(malloc fail:);exit(1);}ps-a tmp;//更新容量ps-capacity newCapacity;}
}
扩容的部分在整个动态顺序表中占据非常重要的地位关系到堆中空间的开辟保证后续数据操作的顺利进行。
头部插入删除和尾部插入删除数据
//头部插入删除
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//保证插入时不会越界for (int i ps-size; i 0; i--) {ps-a[i] ps-a[i - 1];}ps-a[0] x;ps-size;
}
void SLPopFront(SL* ps)
{assert(ps);assert(ps-size);for (int i 0; i ps-size - 1; i) {ps-a[i] ps-a[i 1];}ps-size--;
}
//尾部插入删除
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);ps-a[ps-size] x;
}void SLPopBack(SL* ps)
{assert(ps);assert(ps-size ! 0);ps-size--;
}这里要注意的是头部插入删除的实现方式是将整个后面的数据做了一个移动操作时间耗费比较大所以顺序表在实际应用当中尽量避免使用头插头删。
指定位置之前插入数据和指定位置删除数据
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos 0 pos ps-size);SLCheckCapacity(ps);for (int i ps-size; i pos; i--) {ps-a[i] ps-a[i - 1];}ps-a[pos] x;ps-size;
}void SLErase(SL* ps, int pos)
{assert(ps);assert(pos 0 pos ps-size);for (int i pos; i ps-size - 1; i) {ps-a[i] ps-a[i 1];}ps-size--;
}
这里的插入和删除操作在顺序表中其实也避免不了数据的移动这也体现了顺序表的一个缺陷中间部分数据的插入删除的时间复杂度较高。
查找数据
最后就是查找列表中数据返回找到的下标
int SLFind(SL* ps,SLDataType x)
{assert(ps);for (int i 0; i ps-size; i) {if (ps-a[i] x)return i;}return -1;
}
这里注意一下数据的匹配查找其实也要匹配 a 动态数组中的的数据类型这里我们定义的数据类型为int就以int的查找方式查找。
体验体验手搓的动态顺序表
以下是体验码
#includeSqlist.h
int main()
{struct SeqList sq;SLInit(sq);SLPushBack(sq, 1);SLPushBack(sq, 2);SLPushBack(sq, 5);SLPushBack(sq, 6);SLPushBack(sq, 3);SLPushFront(sq, 4);SLPrint(sq);//4 1 2 5 6 3 SLPopBack(sq);SLPrint(sq);//4 1 2 5 6SLPopFront(sq);SLPrint(sq);//1 2 5 6int pos1 SLFind(sq, 5);SLErase(sq, pos1);SLPrint(sq);//1 2 6int pos2 SLFind(sq, 6);SLInsert(sq, pos2, 100);SLPrint(sq);//1 2 100 6SLDestroy(sq);return 0;
} 以上就是手搓的动态顺序表以及使用了。
链表
链表的概念及结构 链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 大概是这样一个东西 注 从图上可以看出链式结构在逻辑上是连续的但是在物理上不一定连续现实中的结点一般都是从堆上申请出来的从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续 链表的分类
其实链表不止我刚刚展示的一种以下情况组合起来就有8种链表结构
1.单像或者双向 图中上面的是单向下面为双向
2.带头或者不带头 图中上面是不带头下面是带头
3.循环或者非循环 图中上面是不循环下面是循环
它们两两排列组合 2 * 2 * 2 刚好就为8
虽然有这么多结构但是实际上最常用的只有两种结构 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了后面我们代码实现了就知道了 这次手搓个单链表怎样
这里的单链表当然指的是无头单项非循环链表喽。
SList.h存放了单链表结点结构和函数声明
//SList.h
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//打印单向链表内容
void SLTPrint(SLTNode* phead);
//创建新节点
SLTNode* CreatNewNode(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);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);
下面来实现函数声明的源代码
链表打印
void SLTPrint(SLTNode* phead)
{assert(phead);SLTNode* pcur phead;while (pcur ! NULL) {printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}
动态申请一个结点
SLTNode* CreatNewNode(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 SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode CreatNewNode(x);newnode-next *pphead;*pphead newnode;
}
void SLTPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* prev *pphead;*pphead (*pphead)-next;free(prev);prev NULL;
}
//尾部插入删除
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode CreatNewNode(x);if (*pphead NULL) {*pphead newnode;return;}SLTNode* ptail *pphead;while (ptail-next) {ptail ptail-next;}ptail-next newnode;
}
void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);if ((*pphead)-next NULL) {free(*pphead);*pphead NULL;return;}SListNode* ptail *pphead;SListNode* prev NULL;while (ptail-next) {prev ptail;ptail ptail-next;}prev-next NULL;free(ptail);ptail NULL;
}
这里链表头插头删的时间复杂度相比顺序表就大大降低了可是尾插尾删还是有一定缺陷的其操作必须走到链表末尾才能进行。
查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur phead;while (pcur) {if (pcur-data x) {return pcur;}pcur pcur-next;}return NULL;
}
这里查找的逻辑非常简单就是遍历链表匹配元素如果没找到返回一个空指针。
删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);assert(*pphead);if (*pphead pos) {SLTNode* del *pphead;*pphead (*pphead)-next;free(del);del NULL;}SLTNode* pcur *pphead;while (pcurpcur-next ! pos) {pcur pcur-next;}pcur-next pos-next;free(pos);pos NULL;
}
这里稍微注意传入的pos是一个指针指向链表中的元素
这里你是否注意到pphead是一个二级指针是的当pos指向头结点时需要改变外部phead结点的指向改变phead指针指向就需要使用二级指针pphead了。
指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode CreatNewNode(x);newnode-next pos-next;pos-next newnode;
}
为什么不提供在指定数据之前插入数据呢是由于此单链表的无头和单向性使其很难确定前驱节点的位置和情况不过硬要提供其实也是可实现的。
同时这里的pos也是一个指针
删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos pos-next);SLTNode* del pos-next;pos-next del-next;free(del);del NULL;
}删除链表释放空间
void SListDesTroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* next (*pphead)-next;SLTNode* pcur (*pphead);while (pcur) {next pcur-next;free(pcur);pcur next;}*pphead NULL;
}
注这里的链表是一个结点一个结点释放的。
体验下手搓的单链表
int main()
{SLTNode* phead NULL;SLTPushBack(phead, 1);SLTPushBack(phead, 2);SLTPushBack(phead, 3);SLTPushBack(phead, 4);SLTPushFront(phead, 5);SLTPrint(phead);//5-1-2-3-4-NULLSLTPopBack(phead);SLTPopFront(phead);SLTPrint(phead);//1-2-3-NULLSLTNode* ret1 SLTFind(phead, 3);SLTInsert(phead, ret1, 100);SLTPrint(phead);//1-2-100-3-NULLSLTNode* ret2 SLTFind(phead, 2);SLTErase(phead, ret2);SLTPrint(phead);//1-100-3-NULLSLTDestroy(phead);return 0;
} 以上就是单项不循环链表的内容了。
来来来再手搓个双向链表可否
这里的双向链表便是带头循环双向链表复杂了些但用起来确实不知道比单链表爽多少倍。
下面放到LTList.h中
//LTList.h
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* prev;struct ListNode* next;
}LTNode;//创建双向链表结点
LTNode* LTBuyNode(LTDataType x);
//下面有两种初始化方式这里我们选择第二种两个其实差别不大
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//销毁链表
void LTDestroy(LTNode* phead);
//打印链表
void LTPrint(LTNode* phead);
//判断链表是否为空
bool LTEmpty(LTNode* phead);
//双向链表的尾插和尾删
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
//双向链表的头插和头删
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);
//在pos位置之后插入和删除数据
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
然后就可以实现我们函数声明的源代码了放到LTList.c中
创建双向链表结点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));newnode-data x;newnode-next newnode-prev newnode;return newnode;
}
初始化链表
LTNode* LTInit()
{LTNode* phead (LTNode*)malloc(sizeof(LTNode));if (phead NULL) {perror(malloc phead fail:);exit(1);}phead-data -1;phead-next phead-prev phead;return phead;
}
头节点data里其实放什么值都无所谓
销毁链表
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;LTNode* pnext pcur-next;while (pcur ! phead) {free(pcur);pcur pnext;pnext pnext-next;}free(phead);pcur pnext phead NULL;
}
这里和单链表销毁同理
打印链表
void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead) {printf(%d-, pcur-data);pcur pcur-next;}printf(\n);
}
判断链表是否为空
bool LTEmpty(LTNode* phead)
{assert(phead);if (phead-next phead)return true;elsereturn false;
}
链表头和链表末尾的插入删除
//链表头的插入和删除
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);newnode-next phead-next;newnode-prev phead;phead-next-prev newnode;phead-next newnode;
}
void LTPopFront(LTNode* phead)
{assert(phead);LTNode* del phead-next;phead-next del-next;del-next-prev phead;free(del);del NULL;
}
//链表末尾的插入和删除
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);newnode-next phead;newnode-prev phead-prev;phead-prev-next newnode;phead-prev newnode;
}void LTPopBack(LTNode* phead)
{assert(phead);LTNode* del phead-prev;phead-prev del-prev;del-prev-next phead;free(del);del NULL;
}
这里链表尾的插入删除就和单链表尾的插入删除不一样了双向链表可以直接通过head-prev直接找到链表末尾因此时间复杂度大大降低。
在pos元素之后插入和删除结点
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);newnode-prev pos;newnode-next pos-next;pos-next-prev newnode;pos-next newnode;
}
void LTErase(LTNode* pos)
{assert(pos);pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);pos 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;
}
以上便是双向链表源代码实现的全部内容了 再来试试我们写的双向链表
int main()
{LTNode* phead LTInit();LTPushBack(phead, 1);LTPushBack(phead, 2);LTPushBack(phead, 3);LTPushFront(phead, 4);LTPushFront(phead, 100);LTPrint(phead);//100-4-1-2-3-LTPopFront(phead);LTPopBack(phead);LTPrint(phead);//4-1-2-LTNode* ret LTFind(phead, 2);LTInsert(ret, 120);LTPrint(phead);//4-1-2-120-LTErase(ret-next);LTPrint(phead);//4-1-2-LTDestroy(phead);return 0;
} 很好到这里双向链表的内容也就差不多了。
顺序表和链表小结
顺序表和链表虽然在物理上都是线性的在实际包装好使用时差别也不大但是底层却天差地别
合理运用顺序表和链表各自的优势很有利于一些项目的开发下面是对顺序表和链表的对比总结
不同点顺序表链表存储空间上物理上一定连续逻辑上连续但物理上不一定连续 随机访问 支持O(1)不支持O(N)任意位置插入或者删除元素可能需要搬移元素效率低O(N)只需修改指针指向插入动态顺序表空间不够需要扩容没有容量的概念应用场景元素高效存储频繁访问让人难以位置插入和删除频繁缓存利用率高低
如果你想了解缓存利用率相关的知识可以看看下面博客 与程序员相关的CPU缓存知识
结语
今天的内容到这里就结束了本来想着把这篇博客分成三部分的不知咋回事一口气给写完了一万多字其实很多一部分是代码。后续博主还会继续产出数据结构系列的内容。如果本篇博客对你有帮助的话还请多多支持博主感谢大家♥
