数据结构:第五章 - 数组、矩阵、广义表 594次阅读 数据结构 2022-07-25 目录 [TOC] ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) 压缩存储:指为多个值相同的元素只分配一个存储空间,而对于零元素不分配空间,其目的就是节省存储空间。 # 一、数组 数组是用来存储具有 "一对一" 逻辑关系数据的线性存储结构。 数组和其他线性存储结构不同。顺序表、链表、栈和队列存储的都是不可再分的数据元素,而数组既可以用来存储不可再分的数据元素,也可以用来存储像顺序表、链表这样的数据结构。 无论数组的维数是多少,数组中的数据类型都必须一致。 ## (一)逻辑表示 ### 1、一维数组 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit5/DS.Unit5.%281.1.1_1%29.png) ```c dataType a[n]; //其中dataType为数据类型,如int型 ``` ### 2、二维数组 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit5/DS.Unit5.%281.1.2_1%29.png) ```c dataType a[m][n]; //其中dataType为数据类型,如int型 ``` ## (二)二维数组存储方式及地址计算公式 ### 1、存储方式 数组 A [ n ] [ m ],行优先时,**n 为行****m 为列**(前行后列);列优先时,**m 为行****n 为列**(前列后行)。 #### (1)行优先存储 先存储在第一行中,本行存满转至下行继续存储。 即,以行序为主(先行后序):按照列号从小到大的顺序,依次存储每一行的元素。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit5/DS.Unit5.%281.2.1.1_1%29.png) #### (2)列优先存储 先存储在第一列中,本行存满转至下列继续存储。 即,以列序为主(先列后行):按照行号从小到大的顺序,依次存储每一列的元素。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit5/DS.Unit5.%281.2.1.2_1%29.png) ### 2、计算公式 设有数组 A [ n ] [ m ](n∈[1 , n],m∈[1, m. ]),数组的每个元素长度为 L ,求 A [ i , j ]的存储地址。 #### (1)行优先 * 首下标 1:LOC( i , j ) = LOC( 1 , 1 ) + ( ( i - 1 ) * n + ( j - 1 ) ) * L * 首下标 0:LOC( i , j ) = LOC( 0 , 0 ) + ( i * n + j ) * L #### (2)列优先 * 首下标 1:LOC( i , j ) = LOC( 1 , 1 ) + ( ( j - 1 ) * m + ( i - 1 ) ) * L * 首下标 0:LOC( i , j ) = LOC( 0 , 0 ) + ( j * m + i ) * L > 注: > > * LOC( i , j ):a( i , j ) 的存储位置。 > * LOC( 0 , 0 ):a( 0 , 0 ) 的存储位置。 > * m(n):数组的总行(列)数。 > * L:单个数据元素占据的存储单元,即元素长度。 > * 偏移量:相对于某个元素,距离其有几个存储单元。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 二、矩阵 ## (一)矩阵 A~mn~ 为一个矩阵的逻辑表示,可用二维数组来存储。 ```c #define m 4 #define n 4 dataType A[m][n]; //其中dataType为数据类型,常用int、float型 //m、n可预先宏定义 ``` ## (二)基本操作 ### 1、矩阵转置 ```c void trsmat(int A[][maxsize],int B[][maxsize],int m,int n) { for(int i=0;i = j 时,存储下三角元素。 * i < j 时,存储上三角元素。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit5/DS.Unit5.%282.3.1_3%29.png) > 对称矩阵的实现过程是:将各元素所在的行标 i 和列标 j 代入公式,得到数组中的地址 k。 ### 2、三角矩阵 #### (1)上三角矩阵 上三角矩阵是指下三角区所有元素均为同一常量,设有下三角矩阵 a~i,j~[ j ]如下图所示: ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit5/DS.Unit5.%282.3.2.1_1%29.png) 元素下标之间的对应关系为:(1 <= i,j <= n) * **按行优先存储,并存储上三角:** ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit5/DS.Unit5.%282.3.2.1_2%29.png) * **按列优先存储,并存储上三角:** ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit5/DS.Unit5.%282.3.2.1_3%29.png) 上三角矩阵在内存中的压缩存储形式如下: ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit5/DS.Unit5.%282.3.2.1_4%29.png) #### (2)下三角矩阵 下三角矩阵是指上三角区所有元素均为同一常量,设有下三角矩阵 a~i,j~ 如下图所示: ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit5/DS.Unit5.%282.3.2.2_1%29.png) 元素下标之间对应关系为:(1 <= i,j <= n) * **按行优先存储,并存储下三角:** ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit5/DS.Unit5.%282.3.2.3_2%29.png) * **按列优先存储,并存储下三角:** ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/%E6%8A%80%E6%9C%AF%E5%9F%9F/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/Unit5/DS.Unit5.%282.3.2.2_3%29.png) 上三角矩阵在内存中的压缩存储形式如下: ### 3、对角矩阵 对角矩阵指所有非零元素都集中在以主对角线为中心的 3 条对角线的区域,其他区域均为零的矩阵; 设有对角矩阵 a~i,j~如下图所示: 对角矩阵采用压缩存储时,是将 3 条对角线上的元素 a~i,j~(1= 对其压缩后: 或这种表示形式: ##### (1)结构体定义 /*三元组结构体*/ typedef struct { int val;//int可替换,元素的值 int i,j;//行、列 }Trimat; /*矩阵的结构表示*/ typedef struct { Trimat data[number];//存储该矩阵中所有非0元素的三元组 int n,m,num;//n和m分别记录矩阵的行数和列数,num记录矩阵中所有的非0元素的个数 }TSMatrix; ##### (2)定义一个含有 maxterms 个非零元素的稀疏矩阵 Trimat triamt[maxterms+1];//maxterms是已经定义的常量 trimat[k].val;//表示取第k个非零元素的值 trimat[k].i;trimat[k].j;//表示取第k个非零元素在矩阵中的行下标和列下标 ##### (3)数组形式表示 int trimat[maxterms+1][3]; /*第k个非零元素操作*/ trimat[k][0];//表示原矩阵元素按行优先顺序的第k个非零元素的值 trimat[k][1];//表示第k个非零元素在矩阵中的位置 /*第0行元素*/ trimat[0][0];//表示存储非零元素 个数 trimat[0][1];// 行数 trimat[0][2];// 列数 /*float型数组取元素位置,需强制转换类型*/ (int)trimat[k][1]; (int)trimat[k][2]; ### 2、链式存储 #### (1)邻接表表示法 将矩阵中的每一行的非零元素串连成一个链表,链表结点有两个分量,分别为该结点对应的元素值及其列号。 > 与“图”中的邻接表是一个东西 #### (2)十字链表表示法 该存储方式采用的是 "链表 + 数组" 结构。 使用十字链表压缩存储稀疏矩阵时,矩阵中的各行各列都各用一个链表存储,与此同时,所有行链表的表头存储到一个数组(rhead),所有列链表的表头存储到另一个数组(chead)中。 各个链表中结点的结构: 行标(row)、列标(col)、数据域分量(val)、指向下方结点的指针 A(rhead)、指向右方结点的指针 B(chead)。 其中,最左边和最上边是头结点数组,不存储数据信息,左上角的结点为整个十字链表的头结点,有 5 个分量,分别存储矩阵的行数、列数、非零元素的个数、以及指向两个头结点数组的指针。 ∧:表示已无下个结点 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 三、广义表 ## (一)概念 * 广义表:表元素可以是原子或者广义表的一种线性表的扩展结构,表中存储的单个元素称为 "原子",而存储的广义表称为 "子表"。 * 表长度:表中最上层元素的个数。 广义表规定,空表{} 的长度为 0。 > 由于广义表中可以同时存储原子和子表两种类型的数据,因此在计算广义表的长度时规定,广义表中存储的每个原子、子表只算作是一个数据元素。 > * 表深度:表中括号的最大层数,即有几个括号。 * 表头和表尾:当广义表不是空表时,称第一个数据(原子或子表)为"表头",剩下的数据构成的新广义表为"表尾"。 ``` GetHead(表名) = 头数据元素;//得到广义表中第一个原子 GetTail(表名) = 尾数据元素;//得到除首原子外剩下的元素构成的表 ``` > 强调一下,除非广义表为空表,否则广义表一定具有表头和表尾,且广义表的表尾一定是一个广义表。tail 得到的元素需在外层加一个()。 ## (二)存储结构 ### 1、常用形式 * A = ( ):A 是一个空表,⻓度为 0,深度为 1。 * B = (d, e):B 的元素全是原子,d 和 e,⻓度为 2,深度为 1。 * C = (b, (c, d)):C 有两个元素,分别是原子 b 和子表(c, d),⻓度为 2,深度为 2。 * D = (B, C):D 中存两个元素 B 和 C,⻓度为 2,深度为 3,D = ((d, e),(b, (c, d))) 。 * E = (a, E):E 有两个元素,原子 a 和它本身,⻓度为 2,这是一个递归广义表,等同于:E = (a,(a,(a,…)))。 > A=()和 A=(( ))不同。前者是空表,而后者是包含一个子表为空表的广义表。GetHead(D)=B;GetTail=C;GetHead((B,C))=B;GetTail((B,C))=((C '解析引用锚文本失败,请尝试更新该引用指向的定义块后再重新打开该文档')) ### 2、头尾链表存储结构 * 原子结点:标记域(tag)、数据域(atom)。 * 广义表结点:标记域(tag)、头指针域(hp)、尾指针域(tp)。 * 标记域:用于区分当前结点是原子(用 0 来表示)、广义表(用 1 来表示)。 * 头指针域:指向原子或广义表结点。 * 尾指针域:为空或指向本层中的下一个广义表结点。 ### 3、扩展线性表存储结构 * 原子结点:标记域(tag)、数据域(atom)、尾指针域(tp)。 * 广义表结点:标记域(tag)、头指针域(hp)、尾指针域(tp)。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 参考资料 > **版权声明**:个人学习记录,本博客所有文章均采用 CC-BY-NC-SA 许可协议。转载请注明出处!若有侵权,请留言联系! > > * 2022 天勤计算机考研高分笔记-数据结构 > * 2022 王道计算机考研复习指导-数据结构 > * 解学武数据结构与算法教程(C 语言版):http://data.biancheng.net/ 如果您觉得文章对您有帮助,请点击文章正下方的小**红心**一下。您的鼓励是博主的最大动力! 2 最后一次更新于2022-10-23 None
0 条评论