数据结构笔记9-数组

参考网课数据结构-青岛大学-王卓-第六周

参考书籍《数据结构C语言版第二版》 中国工信出版集团 人民邮电出版社出版 严蔚敏 编著

---

数组：按照一定格式排列起来的具有相同类型的数据元素的集合

一维数组：当线性表中的元素为非结构的简单元素时，称此线性表为一维数组。

声明格式：int num[5] = {1, 2, 3, 4, 5}（等号后面是在进行初始化）

二维数组：当线性表中的元素为一维数组结构，称此线性表为二维数组。

声明格式：int num[5][8]，先行后列（c，java），链长度为5的，块长为8的数组。

注：在c语言中，可以用

typedef ElemType array2[m][n];

或者用分次定义：

typedef ElemType array1[n];typedef array1 array2[m];

三维数组：二维数组中的元素是一个一维数组

n维数组…

Note

1. 线性表是数组结构的特例，数组是线性表的扩展。
2. 数组不做元素插入，结构固定：维数和维界不变，只有取出元素和修改元素操作。

---

数组的顺序存储

本节核心问题：计算元素存储位置

链表的顺序存储的$loc$公式仍然可用。

以三维为例，对三维数组$a[m_1][m_2][m_3]$：

$$LOC(i_1,i_2,i_3)=a+i_1\ast m_2\ast m_3+i_2\ast m_3+i_3$$

二维数组两种优先存取方式：行序优先，列序优先。

c与java都是行序优先，先行后列。

三维数组顺序存储

页→行→列

---

特殊矩阵的压缩存储

压缩存储：若多个数据元素值相同，只分配一个元素值的存储空间，零元素不占空间。

压缩对象：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵（元素个数少于5%）。

对称矩阵存储：用二维数组存下半部分。

对角矩阵存储：用二维数组沿对角线存储。

稀疏矩阵存储1：用三元组$(i,j,v)$储存，”位置+值“

稀疏矩阵存储2：链式存储结构——十字链表

优点：灵活插入在运算中产生的非零元素。

---

广义表

广义表（Lists）是一些元素的有限序列，其中的元素可以是原子，也可以是广义表。

广义表的记法：$LS=(a_1,a_2,a_3...a_n)$

1. 大写字母表示广义表，小写表示原子。
2. 第一个元素$a_1$，是$LS$的表头，记作$head(LS)=a_1$
   • 表头可以是原子，也可以是子表。
3. 表尾，除了表头之外的其他元素构成的表。记作$tail(LS)=(a_2,a_3...a_n)$。
   • 表尾不是最后一个元素，而是一个子表。

一些容易混淆的点：

广义表的性质

1. 广义表中的元素有相对次序
2. 广义表的长度定义为最外层包含的元素个数
3. 广义表的深度定义为展开后包含的括号层数，原子深度为0，空表深度为1.
4. 广义表可以为其他广义表共享：即通过表名引用表示即可。
   1. 如：广义表$B$共享表$A$：$B=(A)$
5. 广义表可以是递归表，深度是无限值，长度是有限值。
   1. 如：$F=(a,F)$
6. 可以图形化
   1. 

Note

当二维数组的每行（或每列）作为子表处理时，二维数组即为一个广义表。

树和有向图也可用广义表来表示。

广义表的基本运算

• 求表头
• 求表尾，表尾一定是一个表

练习：

Note

广义表不能用数组来存储，因为每个元素大小通常都不一样，通常用链式存储。

---

病毒感染检测——串的模式匹配的应用

略