数据结构与算法 --- 2.线性表
2018-10-24 本文已影响15人
下页天
线性表的概念
-
线性表简称表,是零个或多个元素的有穷序列,通常可 以表示成 k0,k1, ...,kn-1(n ≥ 1)
- 表目:线性表中的元素(可包含多个数据项,记录)
- 索引(下标):i 称为表目 ki 的“索引”或“下标”
- 表的长度:线性表中所含元素的个数 n
- 空表:长度为零的线性表 ( n = 0 )
-
线性表特点:
- 操作灵活,其长度可以增长、缩短
- 有一个唯一的开始结点,它没有前驱,有一个唯一的直接后继
- 一个唯一的终止结点,它有一个唯一的直接前驱,而没有后继
- 其它的结点皆称为 内部结点,每一个内部结点都有且仅有一个唯一的直 接有前驱,也有一个唯一的直接后继
- 均匀性:虽然不同线性表的数据元素可以是各种各样 的,但对于同一线性表的各数据元素必定具有相同的 数据类型和长度
- 有序性:各数据元素在线性表中都有自己的位置,且 数据元素之间的相对位置是线性的
-
按复杂程度划分
- 简单的:线性表、栈、队列、散列表
- 高级的:广义表、多维数组、文件......
-
按访问方式划分
- 直接访问型 (direct access)
- 顺序访问型 (sequential access)
- 目录索引型 (directory access)
-
按操作划分
-
线性表
- 所有表目都是同一类型结点的线性表
- 不限制操作形式
- 根据存储的不同分为:顺序表,链表
-
栈 (LIFO, Last In First Out)
- 插入和删除操作都限制在表的同一端进行
-
队列 (FIFO, First In First Out)
- 插入操作在表的一端, 删除操作在另一端
-
线性表包括三个方面,线性表的逻辑结构,线性表的存储结构,线性表运算
-
线性表逻辑结构主要属性包括
- 线性表的长度
- 表头 (head)
- 表尾 (tail)
- 当前位置 (current position)
-
线性表的存储结构
- 顺序表
- 按索引值从小到大存放在一片相邻的连续区域
- 紧凑结构,存储密度为 1
- 链表
- 单链表
- 双链表
- 循环链表
- 顺序表
-
线性表的运算
- 建立线性表
- 清除线性表
- 插入一个新元素
- 删除某个元素
- 修改某个元素
- 排序
- 检索
顺序表
也称向量,采用定长的一维数组存储结构
- 主要特性
- 元素的类型相同
- 元素顺序地存储在连续存储空间中,每一个元素有唯一
的索引值 - 使用常数作为向量长度
读写其元素很方便 ,通过下标即可指定位置,只要确定了首地址,顺序表中任意数据元素都可以随机 存取
- 在顺序表中每个位置上插入和删除元素的 概率相同时间代价为O(n)
链表(linked list)
通过指针把它的一串存储结点链接成一个链,存储结点由两部分组成:数据域 + 指针域(后继地址)
- 链表根据链接方式和指针多寡分类
- 单链 时间复杂度O(n) 查找复杂度O(n)+插入复杂度O(1)
- 双链 为弥补单链表的不足,而产生双链表. 单链表的 next 字段仅仅指向后继结点,不能有效地找
到前驱, 反之亦然 增加一个指向前驱的指针 - 循环链. 将单链表或者双链表的头尾结点链接起来,就是一个循 环链表 不增加额外存储花销,却给不少操作带来了方便,从循环表中任一结点出发,都能访问到表中其他结点
线性表实现方法的比较
-
顺序表的主要优点
- 没有使用指针,不用花费额外开销
- 线性表元素的读访问非常简洁便利
-
链表的主要优点
- 无需事先了解线性表的长度
- 允许线性表的长度动态变化
- 能够适应经常插入删除内部元素的情况
总结:顺序表是存储静态数据的不二选择,链表是存储动态变化数据的良方
-
顺序表
- 插入、删除运算时间代价 O(n),查找则可常数时间完成
- 预先申请固定长度的连续空间
- 如果整个数组元素很满,则没有结构性存储开销
-
链表
- 插入、删除运算时间代价 O(1),但找第i个元素运算时间
代价 O(n) - 存储利用指针,动态地按照需要为表中新的元素分配存
储空间 - 每个元素都有结构性存储开销
- 插入、删除运算时间代价 O(1),但找第i个元素运算时间
应用场合的选择
-
顺序表不适用的场合
- 经常插入删除时,不宜使用顺序表
- 线性表的最大长度也是一个重要因素
-
链表不适用的场合
- 当读操作比插入删除操作频率大时,不应选择链表
- 当指针的存储开销,和整个结点内容所占空间相比其 比例较大时,应该慎重选择