数组、广义表的认识

分手后的思念是犯贱 2024-04-01 12:12 39阅读 0赞

> 本文学自王卓老师，内容比较基础，偏理论和基本概念。  
> 很适合，刚学数据结构的小白进行学习。

#### 文章目录 ####

*  数组
 *   *  1 定义
     *  2 二维数组以及多维数组
     *  3 N维数组的抽象数据类型
     *  4 矩阵
     *  5 特殊矩阵的压缩存储
     *   *  5.1 对称矩阵
         *  5.2 对阵矩阵的存储结构
         *  5.3 稀疏矩阵
         *  5.4 稀疏矩阵的压缩存储方法——顺序存储结构
         *  5.4 稀疏矩阵的链式存储结构：十字链表
 *  广义表
 *   *  1 定义
     *  2 广义表的性质
     *  3 练习题

## 数组 ##

### 1 定义 ###

*  数组：按一定格式排列起来的 具有相同类型的数据元素的集合
 *  一维数组：若线性表中的数据元素为非结构的简单元素则称为一维数组
 *  一维数组的逻辑结构：***线性结构 定长的线性表***
 *  声明格式：数据类型 变量名称【长度】  
    ![在这里插入图片描述][b81db00da9ff4bd4bd42ca42d5cdc15d.png]

### 2 二维数组以及多维数组 ###

![在这里插入图片描述][5df0cd08a04948cf82d3a4c634e8742d.png]

//定义格式：数据类型 变量名称【行数】【列数】
    int num[2][3];
    //在c语言中，一个二维数组类型也可以定义为一个一个一维数组类型
    typedef elemtype arr[m][n];
    //等价于
    typedef elemtype array1[n];
    typedef elemtype array[m];

*  三维数组：若二维数组中的元素又是一个一维数组，则称作三维数组
 *  n维数组：若n-1维数组中的元素又是一个一维数组结构则称作n维数组
 *  结论
    
     *  线性表结构是数组结构的一个特例
     *  而数组结构又是线性表结构的扩展
 *  数组特点：结构固定——定义后，维数和维界不再改变。
 *  数组基本操作：结构的初始化、销毁、获取、修改元素。

### 3 N维数组的抽象数据类型 ###

![在这里插入图片描述][bc89f354f729445bb5144e62c825149d.png]  
![在这里插入图片描述][61d973e9464649cb986f993ef8367edd.png]  
![在这里插入图片描述][f88d79e0f21844c682b2557e609fada0.png]

*  数组的特点：结构固定——维数和维界不变
 *  数组的基本操作：初始化、销毁、获取元素、修改元素
 *  基于数组的常用操作和特点，一般采用顺序存储结构来表示数组。

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

![在这里插入图片描述][c62cec17431945b9a4cf794de31edf62.png]

### 4 矩阵 ###

*  矩阵：一个由m×n个元素排成的m行n列的表
 *  矩阵的常规存储：
    
     *  将矩阵描述为一个二维数组
 *  矩阵的常规存储的特点
    
     *  可以对其元素进行随机存取；
     *  矩阵运算非常简单：存储的密度为1
 *  不适宜常规存储的矩阵：值相同的元素很多且呈某种规律分布；零元素多
 *  矩阵的压缩存储：为多个相同的非零元素只分配一个存储空间；对零元素不分配空间

### 5 特殊矩阵的压缩存储 ###

*  压缩存储
    
     *  若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间
 *  什么样的矩阵能够压缩？
    
     *  一些特殊矩阵，如：对称矩阵，对角矩阵三角矩阵，稀疏矩阵等
 *  稀疏矩阵
    
     *  矩阵中非零元素的个数较少（一般小于5%）  
        ![在这里插入图片描述][33c1a307c9344c0eae351e13b16d43bd.png]

#### 5.1 对称矩阵 ####

*  特点：在nxn的矩阵a中，满足如下性质：aij=aji（1≤i,j≤n）
 *  存储方法:只存储下（或者上）三角（包括主对角线）的数据元素。共占用n（n+1）/2个元素空间.  
    ![在这里插入图片描述][437955bee6a74ce78bcdf204b414ed96.png]

#### 5.2 对阵矩阵的存储结构 ####

*  对称矩阵的存储结构:
    
     *  对称矩阵上下三角中的元素数均为:n(n+1）/2
     *  可以以行序为主序将元素存放在一个一维数组sa\[n（n+1）/2\]中  
        ![在这里插入图片描述][d53c67721fef4fed9b650f4f9d8d3bc1.png]  
        ![在这里插入图片描述][ca766a6d733341dfb44c123c0efe0486.png]  
        ![在这里插入图片描述][124d7796265f4f99a9125b940fe102bf.png]

#### 5.3 稀疏矩阵 ####

![在这里插入图片描述][86c3e84f3a5943e0b4fc9f9d2d50fc90.png]

>  *  压缩存储原则：存各非零元的值、行列位置和矩阵的行列数。
>  *  三元组的不同表示方法可决定稀疏矩阵不同的压缩存储方法。

#### 5.4 稀疏矩阵的压缩存储方法——顺序存储结构 ####

*  三元组顺序表  
    ![在这里插入图片描述][ea81037ef7524ef9b7f5155e64231bd2.png]
 *  三元组顺序表又称有序的双下标法
 *  三元组顺序表的优点：非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算
 *  三元组顺序表的缺点：不能随机存取。若按行号存取某一行中的非零元，则需从头开始进行查找。

#### 5.4 稀疏矩阵的链式存储结构：十字链表 ####

*  优点：
    
     *  它能够灵活地插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的各种运算
 *  在十字链表中，矩阵的每一个非零元素用一个结点表示该结点除了（row，col，value）以外，还要有两个域
    
     *  right：用于链接同一行中的下一个非零元素；
     *  down：用以链接同一列中的下一个非零元素
 *  节点图：  
    ![在这里插入图片描述][7c98f1eafe9e459f91ab2fe045c40dea.png]

![在这里插入图片描述][41bcaa6ee889410a90c241c2a0c92337.png]

## 广义表 ##

### 1 定义 ###

*  ***广义表***（又称列表Lists）是n>=0个元素 a 0 ， a 1 ， . . a n a\_0，a\_1，..a\_n a0，a1，..an的有限序列,其中每一个a；或者是***原子***或者是一个***广义表***
 *  例：中国举办的国际足球邀请赛参赛队名单可表示如下

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

*  广义表通常记作：LS= ( a 1 , a 2 , . . . , a n ) (a\_1,a\_2,...,a\_n) (a1,a2,...,an)
    
     *  LS为表名
     *  n为表的长度
     *  每一个 a i a\_i ai为表的元素

>  *  ***一般用大写字母表示广义表，小写字母表示原子。***

*  表头:若LS非空（n>=1），则其第一个元素a就是表头
    
     *  记作head(Ls）
     *  注：表头可以是原子，也可以是子表
 *  表尾: 除表头之外的其它元素组成的表
    
     *  记作tail（LS)= （ a 2 , . . . , a n ) （a\_2,...,a\_n) （a2,...,an)

>  *  ***注：表尾不是最后个元素，而是一个子表***  
>     ![在这里插入图片描述][1269720eac8643cd8a9533bfc45cddbd.png]  
>     ![在这里插入图片描述][188176baed0e4a34b2910fff89f612c0.png]

### 2 广义表的性质 ###

*  广义表的性质
    
    1.  广义表中的数据元素有相对次序；一个直接前驱和一个直接后继。
    2.  广义表的长度定义为最外层所包含元素的个数
        
         *  如：C=（a（b，d）是长度为2的广义表
    3.  广义表的深度定义为该广义表展开后所含括号的重数；
        
         *  A=(b,c)的深度为1;B=(A,d)的深度为2;C=(f,B,h)的深度为3。

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

4. 广义表可以为其他广义表共享；如：广义表B就共享表A。在B中不必列出A的值，而是通过名称来引用B=（A）
    5. 广义表可以是一个递归的表。如：F=(a，A=(a（a（a，...)）)

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

![在这里插入图片描述][1d8d7f2873f34a93bb20c1ec60a541e6.png]  
![在这里插入图片描述][4ac53d0988a94d74876f5c89ad5bffcf.png]

### 3 练习题 ###

1.  求表头GetHead（L）：非空广义表的第一个元素可以是一个元素，也可以是一个子表。
2.  求表尾GetTail（L）：非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表  
    例：D=(E,F)=（（a，（b，c）），F）  
    ![在这里插入图片描述][5fafc342ed47460aad6640f0f1ec43bc.png]

[b81db00da9ff4bd4bd42ca42d5cdc15d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/78bd6792a0824144a39b3d34bf337be3.png
[5df0cd08a04948cf82d3a4c634e8742d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/8a3e451801c44e1bb1072638a6c72517.png
[bc89f354f729445bb5144e62c825149d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9203264bc8004b6f99713be930b485ac.png
[61d973e9464649cb986f993ef8367edd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/688975c2a9a145ad99110e81b6edc8fb.png
[f88d79e0f21844c682b2557e609fada0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/76c439c8491f40f5bbd418e49ca9543b.png
[c62cec17431945b9a4cf794de31edf62.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0bdfeedb3b2641648f4064a20dd9b4aa.png
[33c1a307c9344c0eae351e13b16d43bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/50fe2e3a863d40b7a32c43c491dd7a0f.png
[437955bee6a74ce78bcdf204b414ed96.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f3933543fdad486c95a2a37589fb8db5.png
[d53c67721fef4fed9b650f4f9d8d3bc1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/6b1366e6f8f547339827a6f1aa1a10c1.png
[ca766a6d733341dfb44c123c0efe0486.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9a01d5dd75dd4631b3d63054e8e03c95.png
[124d7796265f4f99a9125b940fe102bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/efdd92639b3545f0971c14889de6012c.png
[86c3e84f3a5943e0b4fc9f9d2d50fc90.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/bf4a2254d03941089fa7f001c958870e.png
[ea81037ef7524ef9b7f5155e64231bd2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0063cb44fab8429485d7c40bda271291.png
[7c98f1eafe9e459f91ab2fe045c40dea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0ed885a1f0cb43068a9a3b9d20457cce.png
[41bcaa6ee889410a90c241c2a0c92337.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/607d676625e549349ae6c3ed003e2158.png
[1269720eac8643cd8a9533bfc45cddbd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/cb7297b33a214e51a653abec2903325e.png
[188176baed0e4a34b2910fff89f612c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/72e98625eb534383bd37b919a965c12c.png
[1d8d7f2873f34a93bb20c1ec60a541e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/30641994521246a2a317c40b4a505d11.png
[4ac53d0988a94d74876f5c89ad5bffcf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/3c4787329b20409d8bd8e77c8ee29868.png
[5fafc342ed47460aad6640f0f1ec43bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/fc38fa4de44c4d1ebf3028f29643292b.png