数据结构--顺序表VS链表

news/2024/11/9 5:03:12/

数据结构–顺序表VS链表

逻辑结构

存储结构

顺序表:
优点:支持随机存取、存储密度高
缺点:大片连续空间分配不方便,改变容量不方便

链表:
优点:离散的小空间分配方便,改变容量方便
缺点:不可随机存取,存储密度低

基本操作

顺序表:
需要预分配大片连续空间。若分配空间过小,则之后不方便拓展容量;若分配空间过大,则浪费内存资源

静态分配:静态数组
动态分配:动态数组( malloc、free)
容量可改变,但需要移动大量元素,时间代价高

链表:
只需分配一个头结点(也可以不要头结点,只声明一头指针)之后方便拓展

增删改查

顺序表:
插入/删除元素要将后续元素都后移/前移
时间复杂度O(n),时间开销主要来自移动元素
若数据元素很大,则移动的时间代价很高

链表:
插入/删除元素只需修改指针即可
时间复杂度O(n),时间开销主要来自查找目标元素
查找元素的时间代价更低

顺序表:
按位查找:O(1)
按值查找:O(n)
若表内元素有序,可在 O ( l o g 2 n ) 时间内找到 \color{red}若表内元素有序,可在O(log_2n)时间内找到 若表内元素有序,可在O(log2n)时间内找到

链表:
按位查找:O(n)
按值查找:O(n)

用顺序表还是链表

表长难以预估、经常要增加 / 删除元素――链表 \color{red}表长难以预估、经常要增加/删除元素 ―― 链表 表长难以预估、经常要增加/删除元素――链表
表长可预估、查询 ( 搜索)操作较多――顺序表 \color{red}表长可预估、查询(搜索)操作较多 ―― 顺序表 表长可预估、查询(搜索)操作较多――顺序表

知识点回顾与重要考点

开放式问题的答题思路:

问题:请描述顺序表和链表的bla bla bla…
实现线性表时,用顺序表还是链表好?

顺序表和链表的逻辑结构都是线性结构,都属于线性表。
但是二者的存储结构不同,顺序表采用顺序存储…(特点,带来的优点缺点);链表采用链式存储… (特点、导致的优缺点)。
由于采用不同的存储方式实现,因此基本操作的实现效率也不同。当初始化时…;当插入一个数据元素时…;当删除一个数据元素时…;当查找一个数据元素时…


http://www.ppmy.cn/news/675962.html

相关文章

VS Code C++迎来套件更新,注释定义方便快捷

近日微软对VS Code C进行套件的更新,新加入名为“Call Hierarchy”的功能,而这个**ERP**功能可以让用户更加直观地理解代码函数之间的引用关系,同时该版本还让开发者更容易复制注释与定义,提升此类内容编写时的自由度。 据悉&am…

EIA-CEA-861-D协议分享(免费)

https://pan.baidu.com/s/1oIhTUm4dc3ZtKCohxvH3bA k3j8

win10系统ISE14.7仿真报错Simulator:861 – Failed to link the design 解决办法

解决方法很简单,亲测有效 找到安装文件夹,依次找到Xilinx\14.7\ISE_DS\ISE\gnu\MinGW\5.0.0\nt\libexec\gcc\mingw32\3.4.2 下的collect2文件即可。

ISE自带仿真器报错:ERROR:Simulator:861 – Failed to link the design 解决办法

Win 10 64bit实测有效 原文链接 http://irootlee.com/isim/ 以下原文: 问题综述: 我使用的是windows 10 32位专业版系统,电脑装的是ISE14.4版本,当我用此ISE自带的仿真器ISIM来仿真时,仿真器总是报错ERROR:Simulat…

861. 翻转矩阵后的得分

有一个二维矩阵 A 其中每个元素的值为 0 或 1 。 移动是指选择任一行或列,并转换该行或列中的每一个值:将所有 0 都更改为 1,将所有 1 都更改为 0。 在做出任意次数的移动后,将该矩阵的每一行都按照二进制数来解释,矩…

Day.2 LeetCode刷题练习(螺旋矩阵)

题目: 例子: 分析题目: 本题给了一个值n要生成一个n*n的矩形,并且是螺旋的生成值。 这样我们可以把它分层来看如n 4时生成一个4*4的矩形由两层矩形构成,这样就能先遍历生成最外面的一层后再去生成里面的一层 那如何…

861. 翻转矩阵后的得分 贪心

有一个二维矩阵 A 其中每个元素的值为 0 或 1 。 移动是指选择任一行或列,并转换该行或列中的每一个值:将所有 0 都更改为 1,将所有 1 都更改为 0。 在做出任意次数的移动后,将该矩阵的每一行都按照二进制数来解释,矩…

LeetCode 861. 翻转矩阵后的得分

原题目:https://leetcode-cn.com/problems/score-after-flipping-matrix/ 思路: 先试用行变换,把每一行的第一个都变成1,然后从第二列开始检查,保证每一列1的个数比0多。 代码: class Solution { public:…