第四讲数组与广义表.pdf

课程回顾 快速存取表中的任一元 优 素（O(1)） 点 无需额外空间表示元素 顺序存 之间的关系 储结构 插入和删除需要移动大 缺 量元素（O(n)） 点 规模需要预定义，不可 变 线性表 插入和删除操作简单 优 （O(1)） 点 规模可变 链式存 储结构 存取表中元素的时间成 缺 本高（O(n)） 点 需要额外空间表示元素 之间的关系 2015年10月13 日 Page 1 数据结构 第四讲 数组与广义表 清华大学 自动化系 黄双喜 博士、副教授 huangsx@tsinghua.edu.cn 数组与广义表 数组是一种人们非常熟悉的数据结构，几乎所有的程序设 计语言都支持这种数据结构或将这种数据结构设定为语言的 固有类型。数组这种数据结构可以看成是线性表的推广。 广义表是另一种推广形式的线性表，是一种灵活的数据结 构，在许多方面有广泛的应用。 矩阵计算 高维问题 复杂网络 社会结构 2015年10月13 日 Page 3 提纲 • 4.1 数组的定义 • 4.2 数组的顺序表示和实现存储结构 • 4.3 矩阵的压缩存储 • 4.4 广义表 2015年10月13 日 Page 4 数组的定义 数组：是线性表的推广。其每一个元素都是由一个（组）值及一 组下标组成。对于每组有定义的下标，都存在一个元素与之对应 。当元素具有n个下标时，该数组称为n维数组。 a a  a