顺序表和链表知识点

embedded/2024/9/22 15:01:32/

1 顺序表

顺序表是指用一段物理地址连续的空间去存储数据的线性结构。

顺序表有两种：静态顺序表，动态顺序表。

1.1 静态顺序表结构体定义

typedef int ElemDataSL;typedef struct SequeList {ElemDataSL arr[100];int size;
}SL;

静态顺序表在创建结构体的时候就已经把容量固定，后期空间不够，不允许增加新空间，所以并不方便实际使用。

例子：通讯录（C语言实现）-CSDN博客

1.2 动态顺序表结构体定义

typedef int ElemDataSL;typedef struct SequeList {ElemDataSL* arr;int size;int capatity;
}SL;

 动态顺序表在创建结构体的时候定义了arr的指针作为一段连续内存空间的首地址，如果有需要可以用realloc开辟新空间进行扩容处理。

1.2.1 接口声明

//初始化
void InitSequeList(SL* s);
//尾插
void SequeListPushBack(SL* s,ElemDataSL num);
//尾删
void SequeListPopBack(SL* s);
//头插
void SequeListPushFront(SL* s, ElemDataSL num);
//头删
void SequeListPopFront(SL* s);
//pos处插
void SequeListPushInsert(SL* s,ElemDataSL num,int pos);
//pos处删
void SequeListPopInsert(SL* s,int pos);
//显示
void SequeListShowData(SL* s);
// 顺序表删除pos位置的值
void SequeListErase(SL*s, size_t pos);
// 顺序表销毁
void SequeListDestory(SL* s);

1.2.2 初始化

//初始化
void InitSequeList(SL* s) {assert(s);s->arr = (ElemDataSL*)malloc(DefaultData * sizeof(ElemDataSL));s->capatity = DefaultData;s->size = 0;
}

1.2.3 尾插

//尾插
void SequeListPushBack(SL* s,ElemDataSL num) {assert(s);AddCapatity(s);s->arr[s->size] = num;s->size++;
}

 1.2.4 尾删

//尾删
void SequeListPopBack(SL* s)
{assert(s);s->size--;
}

1.2.5 头插

//头插
void SequeListPushFront(SL* s,ElemDataSL num) {AddCapatity(s);for (int i = s->size-1; i >=0; i--){s->arr[i + 1] = s->arr[i];}s->arr[0] = num;s->size++;
}

1.2.6 头删

//头删
void SequeListPopFront(SL* s)
{for (int i = 0; i <= s->size - 1; i++){s->arr[i] = s->arr[i + 1];}s->size--;
}

1.2.7 中间插入

//pos处插
void SequeListPushInsert(SL* s,ElemDataSL num,int pos)
{AddCapatity(s);for (int i = s->size - 1; i >= pos-1; i--){s->arr[i + 1] = s->arr[i];}s->arr[pos-1] = num;s->size++;
}

1.2.8 中间删除

//pos处删
void SequeListPopInsert(SL* s, int pos) {for (int i = pos-1; i <= s->size - 1; i++){s->arr[i] = s->arr[i + 1];}s->size--;
}

1.2.9 打印顺序表

//显示
void SequeListShowData(SL* s)
{assert(s);for (int i = 0; i < s->size; i++){printf("%d ", s->arr[i]);}printf("\n");
}

1.3 顺序表销毁

// 顺序表销毁
void SequeListDestory(SL* s) {free(s->arr);s->arr = NULL;
}

顺序表优点：可以利用随机访问。

缺点：开辟空间可能会导致空间浪费，增删改查的时间复杂度为O（N）。

2 链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

注意：

1、链式结构在逻辑上是连续的，但在物理上非连续。

2、在堆上开辟空间。

3、在堆上申请空间，按照一定策略进行的，两次开辟的空间可能连续也可能不连续。

2.1 单链表

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。

2.2 接口声明

typedef int SLDATATYPE;
typedef struct SListNode {int data;struct SListNode* next;
}SListNode;
//尾插
void SListPushBack(SListNode** pphead, SLDATATYPE num);
//尾删
void SListPopBack(SListNode* phead);
//头插
void SListPushFront(SListNode** pphead, SLDATATYPE num);
//头删
void SListPopFront(SListNode* phead);
//查找
SListNode* SListFind(SListNode* phead, SLDATATYPE num);
//中间后插
void SListInsertAfter(SListNode* pos, SLDATATYPE num);
//中间删
void SListEraseAfter(SListNode* pos);
//打印
void SListPrint(SListNode* phead);
//销毁链表
void SListDistory(SListNode** phead);

2.3 尾插

//尾插
void SListPushBack(SListNode* *pphead, SLDATATYPE num) {SListNode* NewNode = BuySListNode(num);if (*pphead == NULL){*pphead= NewNode;}else{	SListNode* tail = *pphead;while (tail->next!=NULL){tail = tail->next;}tail->next= NewNode;}
}

2.4 尾删

//尾删
void SListPopBack(SListNode** phead)
{SListNode* tail = *phead;SListNode* prev = tail;if (*phead == NULL){return;}else if ((*phead)->next == NULL){free(*phead);*phead = NULL;}else{while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);prev->next = NULL;}}

2.5 头插

//头插
void SListPushFront(SListNode** pphead, SLDATATYPE num)
{SListNode* newNode = BuySListNode(num);if ((*pphead) == NULL){*pphead = newNode;}else{newNode->next = *pphead;}*pphead = newNode;
}

2.6 头删

//头删
void SListPopFront(SListNode* *pphead)
{	SListNode* head = *pphead;if (head == NULL){return;}else if (head->next == NULL){*pphead = NULL;}else{(*pphead) = (*pphead)->next;free(head);}}

2.7 查找

SListNode* SListFind(SListNode* phead, SLDATATYPE num) {SListNode* ptr = phead;while (ptr){if (ptr->data == num){printf("%d找到了!\n",ptr->data);return  ptr;}ptr = ptr->next;}printf("%d没找到!\n",num);return NULL;
}

2.8 中间后插

void SListInsertAfter(SListNode* *pos, SLDATATYPE num)
{SListNode* newNode = BuySListNode(num);newNode->next = (*pos)->next;(*pos)->next = newNode;
}

2.9 中间后删

void SListEraseAfter(SListNode* pos)
{assert(pos);assert(pos->next);SListNode* next = pos->next;pos->next = next->next;free(next);
}

3 打印

//打印
void SListPrint(SListNode* phead)
{SListNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

3.1 销毁链表

void SListDistory(SListNode** phead)
{assert(*phead);SListNode* next = (*phead)->next;while (next){free(*phead);*phead = next;next = next->next;}free(*phead);*phead = NULL;
}

单链表优点：需要增加多少个元素就开辟多少空间不会导致空间浪费，插入时间复杂度低。

缺点：不能随机访问，只能依次往后访问，无法实现从后往前。

2.2 双链表

头节点不存储有效数据。

2.2.1 接口声明

typedef int ListData;
typedef struct ListNode
{ListData data;struct ListNode* next;struct ListNode* prev;
}ListNode;
//链表创建
ListNode* ListCreate();
//尾插
void ListPushBack(ListNode* phead, ListData x);
//尾删
void ListPopBack(ListNode* phead);
//头插
void ListPushFront(ListNode* phead, ListData x);
//头删
void ListPopFront(ListNode* phead);
//查找
ListNode* ListFind(ListNode* phead, ListData x);
//中间插
void ListInsert(ListNode* pos,ListData x);
//中间删
void ListErase(ListNode* pos);
//显示
void ListPrint(ListNode* phead);
//清空链表
void ListClear(ListNode** phead);
//销毁链表
void ListDestory(ListNode* phead);

2.2.2 创建新节点 


ListNode* BuyListNode(ListData x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));node->data = x;node->next = NULL;node->prev = NULL;return node;
}

2.2.3 双链表创建

ListNode* ListCreate() {ListNode* phead = BuyListNode(0);phead->next = phead;phead->prev = phead;return phead;
}

2.2.4 尾插 

//尾插
void ListPushBack(ListNode* phead, ListData x)
{assert(phead);ListNode* tail = phead->prev;ListNode* newNode = BuyListNode(x);tail->next = newNode;newNode->prev = tail;newNode->next = phead;phead->prev = newNode;
}

 2.2.5 尾删

//尾删
void ListPopBack(ListNode* phead)
{assert(phead->next != phead);/*ListNode* tail = phead->prev;ListNode* tailPrev = tail->prev;tailPrev->next = phead;phead->prev = tailPrev;*/ListErase(phead->prev);
}

2.2.6 头插

//头插
void ListPushFront(ListNode* phead, ListData x)
{ListNode* newNode = BuyListNode(x);ListNode* pheadNext = phead->next;phead->next = newNode;newNode->prev = phead;newNode->next = pheadNext;pheadNext->prev = newNode;
}

2.2.7 头删 

//头删
void ListPopFront(ListNode* phead)
{ListNode* pheadNext = phead->next;phead->next = pheadNext->next;pheadNext->next->prev = phead;free(pheadNext);
}

2.2.8 查找

//查找
ListNode* ListFind(ListNode* phead, ListData x)
{ListNode* pos = NULL;ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){pos = cur;break;}cur = cur->next;}return pos;
}

2.2.9 中间插

//中间插
void ListInsert(ListNode* pos, ListData x)
{assert(pos);/*ListNode* newNode = BuyListNode(x);ListNode* posPrev = pos->prev;newNode->next = pos;pos->prev = newNode;posPrev->next = newNode;newNode->prev = posPrev;*/ListPushFront(pos->prev, x);
}

2.3 中间删

//中间删
void ListErase(ListNode* pos)
{ListNode* posPrev = pos->prev;ListNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);
}

2.3.1 显示

//显示
void ListPrint(ListNode* phead)
{assert(phead);ListNode* tail = phead->next;while (tail != phead){printf("%d ", tail->data);tail = tail->next;}printf("\n");
}

2.3.2 清空链表

void ListClear(ListNode** phead)
{ListNode* cur = (*phead)->next;while (cur != *phead){ListNode* next = cur->next;free(cur);cur = next;}(*phead)->next = *phead;(*phead)->prev = *phead;
}

2.3.3 销毁链表

//销毁链表
void ListDestory(ListNode** phead)
{ListClear(phead);free(*phead);
}

双链表优点：插入时间复杂度比单链表更低，可以前驱访问。

缺点：不能随机访问。

 3 顺序表和链表的区别

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，物理上不一定连续
随机访问支持O（1）不支持O（N）
任意位置插入或者删除元素可能需要搬移元素，效率低O（N）只需修改指针指向
插入动态顺序表，空间不够时需要扩容没有容量概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率高低


http://www.ppmy.cn/embedded/102996.html

相关文章

使用docker compose一键部署 Openldap

使用docker compose一键部署 Openldap

使用docker compose一键部署 Openldap LDAP&#xff08;轻量级目录访问协议&#xff0c;Lightweight Directory Access Protocol&#xff09;是一种用于访问分布式目录服务的网络协议&#xff0c;OpenLDAP 是 LDAP 协议的一个开源实现&#xff0c;由 OpenLDAP 项目提供&#x…
阅读更多...
基于SpringBoot的科研管理系统

基于SpringBoot的科研管理系统

文章目录 项目介绍主要功能截图：部分代码展示设计总结项目获取方式🍅 作者主页：超级无敌暴龙战士塔塔开 🍅 简介：Java领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我，都给你】 🍅文末获取源码联系🍅 项目介绍 基于SpringBoot的科研管理系统,java项目…
阅读更多...
视频压缩怎么操作？三个办法教你无损压缩视频

视频压缩怎么操作？三个办法教你无损压缩视频

随着假期的结束&#xff0c;很多同学和朋友们开始整理自己在假期期间拍摄的各种视频&#xff0c;准备分享到社交媒体或是保存到自己的移动设备上。 然而&#xff0c;面对高清甚至4K视频的大文件体积&#xff0c;不少人都会遇到存储空间不足的问题。这时候&#xff0c;一个好的…
阅读更多...
MyBatis错误

MyBatis错误

说明&#xff1a;记录一次MyBatis错误&#xff0c;错误信息如下&#xff0c;说数字转换异常&#xff0c;显然&#xff0c;把一个字符串类型转为数字类型&#xff0c;肯定是不行的。 2024-08-29 19:44:43.198 ERROR 24216 --- [nio-9090-exec-2] o.a.c.c.C.[.[.[/].[dispatcher…
阅读更多...
P2403 [SDOI2010] 所驼门王的宝藏

P2403 [SDOI2010] 所驼门王的宝藏

~~~~~ P2403 [SDOI2010] 所驼门王的宝藏 ~~~~~ 总题单链接 讲解 ~~~~~ 这道题的关键在于如何连边。 ~~~~~ 对于“横天门”和“纵寰门”建虚点即可。 ~~~~~ 对于“任意门”&#xff0c;用一个 vector 存每行有哪些点&#xff0c;然后二分。 ~~~~~ 连完边之后缩点&#xff0c;然…
阅读更多...
一些关于Vue2的面试题

一些关于Vue2的面试题

1.v-if和v-show的区别&#xff1f; v-show通过css中的display控制隐藏和显示&#xff0c;v-if是真的渲染和销毁 如果显示隐藏切换比较频繁&#xff0c;使用v-show&#xff0c;否则使用v-if 2.为什么v-for要使用key&#xff1f; 快速找到节点&#xff0c;减少渲染次数&#…
阅读更多...
深度学习：革新药物心脏毒性预测的新篇章

深度学习：革新药物心脏毒性预测的新篇章

药物研发是一项充满挑战与风险的领域&#xff0c;尽管科学家们投入大量时间与资源&#xff0c;但仍有高达90%的药物因无法通过临床试验而宣告失败。其中&#xff0c;药物的心脏毒性是一个尤为棘手的问题&#xff0c;不少药物在上市后因被发现对心脏有潜在伤害而被迫召回&#x…
阅读更多...
一、菜单扩展

一、菜单扩展

一、创建文件夹 创建一个名为Editor的文件夹。unity会默认这个名字为工程文件夹 二、创建代码 实现点击unity菜单&#xff0c;对应代码的方法 引用命名空间&#xff1b;使用这个menuitem 注&#xff1a;必须有一个子路径&#xff0c;不然会报错 这里是这个方法的参数 每一个…
阅读更多...
最新文章

Copyright @ 2022~2023