数据结构—数组和广义表

4.2数组

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

**一维数组：**若线性表中的数据元素为非结果的简单元素，则称为一维数组。

**一维数组的逻辑结构：**线性结构，定长的线性表。

**声明格式：**数据类型 变量名称 [长度] ；

例如：int num[5] = {0,1,2,3,4}；

**二维数组：**若一维数组中的数据元素又是一维数组结构，则称为二维数组。

二维数组的逻辑结构：

1. 非线性结构：每一个数据元素既在一个行表中，又在一个列表中。
2. 线性结构定长的线性表：该线性表的每个数据元素也是一个定长的线性表。

**声明格式：**数据类型 变量名称 [行数] [列数]；

例如：int num [5] [8];

在C语言中，一个二维数组类型也可以定义为一维数组类型（其分量类型为一维数组类型），即：

  typedef int array2[m][n];
等价于：typedef int array1[n];typedef array1 array2[m];

**三维数组：**若二维数组中的元素又是一个一维数组，则称作三维数组。

**n维数组：**若 n - 1 维数组中的元素又是一个一维数组结构，则称作 n 维数组。

**结论：**线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。

**数组特点：**结构固定——定义后，维数和维界不再改变。

**数组基本操作：**除了结构的初始化和销毁之外，只有取元素和修改元素值的操作。

4.2.1数组的顺序存储结构

数组特点：结构固定——维数和维界不变。

一般都是采用顺序存储结构来表示数组。

**注意：**数组可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。

一维数组：

例：有数组定义：int a[5]

每个元素占用4字节，假设a[0]存储在2000单元，a[3]地址是多少？

LOC(0) = a = 2000 L=4

LOC(3) = 3*4+2000

LOC(i) = i*L + 首地址

存储单元是一维结构，而数组是个多维结构，则用一组连续存储单元存放数组的数据元素就有个次序约定问题。

二维数组可有两种存储方式：

1. 以行序为主序；

   设数组开始存储位置LOC(0,0)，存储每个元素需要L个存储单元

   数组元素a[i] [j]的存储位置是：LOC(i,j)=LOC(0,0) + (n * i + j) * L

2. 以列序为主序。

**三维数组：**按页/行/列存放，页优先的顺序存储。

4.2.2特殊矩阵的压缩存储

**矩阵：**一个由 m*n 个元素排成的 m 行 n 列的表。

**矩阵的常规存储：**将矩阵描述为一个二维数组。

矩阵的常规存储的特点：

1. 可以对其元素进行随机存取。
2. 矩阵运算非常简单；存储的密度为1.

**不适宜常规存储的矩阵：**值相同的元素很多且呈某种规律分布；零元素多。

**矩阵的压缩存储：**为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。

1、什么是压缩存储

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

2、什么样的矩阵能够压缩？

一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。

3、什么叫稀疏矩阵？

矩阵中非零元素的个数较少（一般小于5%）

1.对称矩阵

**【特点】：**在 n*n 的矩阵 a 中，满足如下性质：a_ij=a_ji（1≤i , j≤n）

**【存储方法】：**只存储下（或者上）三角（包括主对角线）的数据元素。共占用 n(n+1)/2个元素空间。

**【存储结构】：**对称矩阵上下三角中的元素数均为：n(n+1)/2

​ 可以以行序为主序将元素存放在一个一维数组 sa[ n(n+1)/2 ]中。

2.三角矩阵

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6FofxLkg-1690537372616)(https://tse1-mm.cn.bing.net/th?id=OIF-C.uHr%2bn0jNJ2j8NRD2iircPA&pid=ImgDet&rs=1)]

**【特点】：**对角线以下（或者以上）的数据元素（不包括对角线）全部为常数c。

**【存储方法】：**重复元素c共享一个元素存储空间，共占用n(n+1)/2+1个元素空间：[1…n(n+1)/2+1]

上三角矩阵：

下三角矩阵：

3.对角矩阵（带状矩阵）

**【特点】：**在n*n的方阵中，所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。

4.稀疏矩阵

**稀疏矩阵：**设在 m*n 的矩阵中有 t 个非零元素。

​ 令 δ = t / (m*n)

​ 当 δ ≤ 0.05 时称为稀疏矩阵。

**压缩存储原则：**存各非零元素的值，行列位置和矩阵的行列数。

4.1三元组顺序表

注意：为更可靠描述，通常再加一个“总体”信息：即总行数、总列数、非零元素总个数。

三元组顺序表又称有序的双下标法。

三元组顺序表的优点：非零元素在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。

三元组顺序表的缺点：不能随机存取。若按行号存取某一行中的非零元素，则需从头开始进行查找。

4.2十字链表

• **优点：**它能够灵活地插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的各种运算。

• 在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了(row，col，value)以外，还要有两个域：

  • right：用于链接同一行中的下一个非零元素。
  • down：用以链接同一列中的下一个非零元素。

• 十字链表中结点的结构示意图：

  

  

4.3广义表

4.3.1广义表定义

广义表（又称列表Lists）是n≥0个元素 a₀，a₁，…，a_n-1的有限序列，其中每一个a_i或者是原子，或者是一个广义表。

例如：中国举办的国际足球邀请赛，参赛队伍名单可表示如下：

（阿根廷，巴西，德国，法国，（），西班牙，意大利，英国，（国家队，山东鲁能，广州恒大））

在这个表中，叙利亚队应排在法国队的后面，但未能参加，成为空表。国家队，山东鲁队，广州恒大均作为东道主的参赛队参加，构成一个小的线性表，成为原线性表的一个数据元素。这种拓宽了的线性表就是广义表。

• 广义表通常记作：LS=( a1，a2，…，an

• 习惯上，一般用大写字母表示广义表，小写字母表示原子。

• **表头：**若LS非空（n≥1），则其第一个元素a1就是表头。记作head（LS）=a1.

  注意：表头可以是原子，也可以是子表。

• 表尾：除表头之外的其他元素组成的表。记作tail（LS）=（a2，…，an）

  注意：表尾不是最后一个元素，而是一个子表。

  例如：（1） A=() 空表，长度为0

  ​ （2）B=(( )) 长度为1，表头、表尾均为（）。

  ​ （3）C=(a,(b,c)) 长度为2，由原子a和子表（b，c）构成。表头为a，表尾为((b，c))

  ​ （4）D=(x,y,z) 长度为3，每一项都是原子。表头为x，表尾为（y，z）

  ​ （5）E=(C,D) 长度为2，每一项都是子表。表头为C，表尾为（D）

  ​ （6）F=(a,F) 长度为2，第一项为原子，第二项为它本身。表头为a，表尾为（F）。F=(a，(a，(a，…)))

4.3.2广义表的性质

1. 广义表的数据元素有相对应次序；一个直接前驱和一个直接后继。

2. 广义表的长度定义为最外层所包括元素的个数，如C=(a,(b,c))是长度为2的广义表。

3. 广义表的深度定义为该广义表展开后所含括号的重数。

   注意：“原子”的深度为0；“空表”的深度为1。

4. 广义表可以为其他广义表共享：如：广义表B就共享表A。在B中不必列出A的值，而是通过名称来引用。B=(A)

5. 广义表可以是一个递归的表。

   注意：递归表的深度是无穷值，长度是有限值。

6. 广义表是一个多层次结构，广义表的元素可以是单元数，也可以是子表，而子表的元素还可以是子表。

   

4.3.3广义表和线性表的区别

广义表可以看成是线性表的推广，线性表是广义表的特例。

广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、数和有向图等各种常见的数据结构。

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

另外，数和有向图也可以用广义表来表示。

由于广义表不仅集中了线性表，数组，数和有向图等常见数据结构的特点，而且可有效地利用存储空间，因此在计算机的许多应用领域都有成功使用广义表的实例。

4.3.4广义表的基本运算

1. 求表头GetHead(L)：非空广义表的第一个元素，可以是一个单一元素，也可以是一个子表。
2. 求表尾GetTail(L)：非空广义表除去表头元素以外其他元素所构成的表，表尾一定是一个表。