夜雨聆风学习资料网 资料列表 开通 VIP 用登录 / 注册 ⌄
PDF

2.3.6_顺序表和链表的比较_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表

查看资料信息、公开预览和下载状态。

共 11 页PDF · 687.4KB
下载

文档在线预览

公开展示前 6 页
100%
1
《2.3.6_顺序表和链表的比较_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第1页预览
2
《2.3.6_顺序表和链表的比较_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第2页预览
3
《2.3.6_顺序表和链表的比较_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第3页预览
4
《2.3.6_顺序表和链表的比较_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第4页预览
5
《2.3.6_顺序表和链表的比较_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第5页预览
6
《2.3.6_顺序表和链表的比较_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_03.计算机数据结构领学_00.资料_第二章线性表》第6页预览

本文档共 11 页 剩余 5 页未展示,请下载后查阅

下载

文档文本内容

本节内容
顺序表
V.S.
链表
王道考研/CSKAOYAN.COM知识总览
顺序表 链表
王道考研/CSKAOYAN.COM:逻辑结构
Round 1
a a a a
1 2 3 4
都属于线性表,都是线性结构
王道考研/CSKAOYAN.COM:存储结构
Round 2
顺序表 链表
(顺序存储) (链式存储)
L
a
1
L
a
1
a a a a
a
1 2 3 4
2
a
a 2
3
a
4
a
4
NULL
都属于线性表,都是线性结构
a
3
优点:支持随机存取、存储密度高 优点:离散的小空间分配方便,改变容量方便
缺点:大片连续空间分配不方便,改变容量不方便 缺点:不可随机存取,存储密度低
王道考研/CSKAOYAN.COM:基本操作
Round 3
复习回忆思路:
创 、增删 查
销 改
王道考研/CSKAOYAN.COM:基本操作
Round 3 创
顺序表 链表
(顺序存储) (链式存储)
L L
头
NULL
需要预分配大片连续空间。 只需分配一个头结点(也可
若分配空间过小,则之后不 以不要头结点,只声明一个
头指针),之后方便拓展
方便拓展容量;若分配空间
过大,则浪费内存资源
容量不
静态分配:静态数组 可改变
动态分配:动态数组(malloc、free)
容量可改变,但需要移动大
量元素,时间代价高
王道考研/CSKAOYAN.COM:基本操作
Round 3 销
顺序表 链表
(顺序存储) (链式存储)
修改 Length = 0 L
依次删除各个 a
1
结点(free)
L
系统自动回收空间
静态分配:静态数组
a
动态分配:动态数组(malloc、free) 2
需要手动 free
typedef struct{ a
4
ElemType *data;
NULL
int MaxSize;
a
int length; malloc 和 free
3
} SeqList; 必须成对出现
L.data = (ElemType *) malloc (sizeof(ElemType) * InitSize);
创
free(L.data); 销
王道考研/CSKAOYAN.COMRound 3 :基本操作 增 删
顺序表 链表
(顺序存储) (链式存储)
L
a
1
L
a
1
a
插入/删除元素只需
2 插入/删除元素要将后续
a
a 修改指针即可 2
元素都后移/前移
3
a
4
a
时间复杂度 O(n),时间开
时间复杂度 O(n),时间开
4
销主要来自移动元素 销主要来自查找目标元素 NULL
a
3
若数据元素很大,则 查找元素的时间
移动的时间代价很高 代价更低
王道考研/CSKAOYAN.COM:基本操作
Round 3 查
顺序表 链表
(顺序存储) (链式存储)
L
a
1
L
a
1
a
2 按位查找:O(1) 按位查找:O(n)
a
a 2
3
a
按值查找:O(n)
按值查找:O(n)
4
a
若表内元素有序,可在
4
O(log n) 时间内找到 NULL
2
a
3
王道考研/CSKAOYAN.COM用顺序表 链表?
or
顺序表 链表
弹性(可扩容) 😭 😁
增、删 😭 😁
查 😁 😭
表长难以预估、经常要增加/删除元素 ——链表
表长可预估、查询(搜索)操作较多 ——顺序表
王道考研/CSKAOYAN.COM知识回顾与重要考点
开放式问题的答题思路:
问题: 请描述顺序表和链表的 bla bla bla…
实现线性表时,用顺序表还是链表好?
顺序表和链表的逻辑结构都是线性结构,都属于线性表。
但是二者的存储结构不同,顺序表采用顺序存储…(特点,带来的优点缺点);链表采用链式存储…(特
点、导致的优缺点)。
由于采用不同的存储方式实现,因此基本操作的实现效率也不同。当初始化时…;当插入一个数据元
素时…;当删除一个数据元素时…;当查找一个数据元素时…
王道考研/CSKAOYAN.COM