《数据结构——C语言描述 教学课件 ppt 作者 王国钧 主编 唐国民 苏晓萍 马瑜 副主编 电子教案 DS05-数组和广义表》由会员分享，可在线阅读，更多相关《数据结构——C语言描述 教学课件 ppt 作者 王国钧 主编 唐国民 苏晓萍 马瑜 副主编 电子教案 DS05-数组和广义表（25页珍藏版）》请在金锄头文库上搜索。
1、本章要点,数组的类型定义和表示方法 特殊矩阵和稀疏矩阵存储方法 及运算的实现 广义表的结构特点,第五章 数组,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表 5.1.1 多维数组组的定义 定义,数组特点 数组结构固定 数据元素同构 数组运算 给定一组下标，存取相应的数据元素 给定一组下标，修改数据元素的值,5.1.2 数组的顺序存储结构 次序约定 以行序为主序 以列序为主序,5.2.1 特殊矩阵 对称矩阵,三角矩阵,对角矩阵,Loc(aij)=Loc(a11)+2(i-1)+(j-1),M由(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4
2、,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩阵维数（6,7）唯一确定,5.2.2稀疏矩阵 定义：非零元较零元少，且分布没有一定规律的矩阵 压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值,稀疏矩阵的压缩存储方法 顺序存储结构 三元组表,#define M 20 typedef struct node int i,j; int v; TriTupleNode ; TriTupleNode maM;,三元组表所需存储单元个数为3(t+1) 其中t为非零元个数,6 7 8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,
3、6 1 15,6 4 -7,ma0.i,ma0.j,ma0.v分别存放 矩阵行列维数和非零元个数,求转置矩阵 问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表 问题分析 一般矩阵转置算法：,for(col=0;coln;col+) for(row=0;rowm;row+) ncolrow=mrowcol; T(n)=O(mn),解决思路：只要做到 将矩阵行、列维数互换 将每个三元组中的i和j相互调换 重排三元组次序，使mb中元素以N的行(M的列)为主序,方法一：按M的列序转置 即按mb中三元组次序依次在ma中找到相应的三元组进行转置。 为找到M中每一列所有非零元素，需对其三元组
4、表ma从第一行 起扫描一遍。由于ma中以M行序为主序,所以由此得到的恰是mb 中应有的顺序,算法描述：,算法分析：T(n)=O(M的列数n非零元个数t) 若 t 与mn同数量级，则,7 6 8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,6 3 14,col=1,col=2,方法二：按行序转置（快速转置） 即按ma中三元组次序转置，转置结果放入b中恰当位置 此法关键是要预先确定M中每一列第一个非零元在mb中位置， 为确定这些位置，转置前应先求得M的每一列中非零元个数,实现：设两个数组 numcol：表示矩阵M中第col列中非零元个数 cpot
5、col：指示M中第col列第一个非零元在mb中位置 显然有：,1,3,5,7,8,8,9,算法分析：T(n)=O(M的列数n+非零元个数t) 若 t 与mn同数量级，则T(n)=O(mn),算法描述：,7 6 8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,6 3 14,4,6,2,9,7,5,3,5.3 广义表,广义表(Lists)也称为列表，它是线性表的推广。大家知道，线性表是n（n0）个元素a1，a2，ai，an的有限序列。其中，线性表的元素仅限于原子项，所谓原子，指的是结构上不可再分割的一种成分，它可以是一个数，或者是一个结构。如果放
6、松对线性表元素的这种限制，允许它们具有其自身独立的类型结构，那么就产生了广义表的概念。 广义表是n（n0）个元素a1，a2，ai，an的有限序列，其中ai或者是原子，或者是一个广义表。通常，广义表可记作LS=(a1,a2,ai,an)。LS是广义表的名字，n为广义表LS的长度。若ai本身也是广义表，则称它为LS的子表。不包含任何元素（即n=0）的广义表称为空表。,需要注意的是： 广义表通常用圆括号括起来，用逗号分隔其中的元素。 为区分原子和广义表，用大写字母表示广义表，用小写字母表示原子。 若广义表LS非空(n1)，则a1称为LS的表头，其余元素组成的表(a2,ai,an)称为LS的表尾。显然
7、，表尾一定是子表，但表头可以是原子，也可以是子表。 广义表是递归定义的，因为在定义广义表时又用到了广义表的概念。,广义表是一个多层次的线性结构。例如: 有A、B、C、D、E五个广义表的描述如下： A=( ) A是一个空表,它的长度为零 B=(e) 列表B只有一个原子e,B的长度为1. C=(a,(b,c,d) 列表C的长度为2,两个元素分别为原子a和子表(b,c,d) D=(A,B,C) 列表D的长度为3,三个元素都是列表,显然,将子表的值代入后,则有D=(),(e),(a,(b,c,d) E=(a,E) 这是一个递归的表,它的长度为2,E相当于一个无限的列表E=(a,(a,(a,.),广义表
8、的结构特点: 1) 广义表中的数据元素有相对次序; 2) 广义表的长度定义为最外层包含的元素个数; 3) 广义表的深度定义为所含括弧的重数; 注意: “原子”的深度为“0”; “空表”的深度为1 4) 表头可以是原子或列表;表尾必定是列表。 5) 广义表可以是一个递归的表; 递归表的深度是无穷值，长度是有限值。,6) 任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为 表头 Head(LS) = 1 和 表尾 Tail(LS) = ( 2, , n) 两部分,例如： Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( ) Head( a,
9、( b, c) ) = a Tail( a,( b, c) ) = ( b,c ) Head( ( c ) ) =(c) Tail( ( c ) ) = ( ),广义表还可以用图形来形象的表示，下图给出了几个广义表的图形表示，其中的分支结点对应广义表，非分支结点（即叶子）对应原子或者空表。,与树对应的广义表称为纯表（Pure List），这种表中没有共享和递归的成分，即没有任何成分出现多次，它限制了表中成分的共享和递归，例如图中的(a)，(b)，(c)都是纯表； 与有向无环图对应的表称为再入表，这种表存在元素共享，在图中表现为存在结点共享，例如图中 (d)，子表A是共享结点，它既是C的一个元素，又是子表B的元素； 与有回路的有向图对应的表称为递归表，这种表的某个成员内含有广义表自己，例如图中 (e)中，表D是其自身的子表。,各种表之间的关系满足： 递归表 再入表 纯表 线性表,广义表的基本运算，除包括线性表的基本运算外，还有求深度、取表头、取表尾、遍历等。这些运算中大部分与对应的线形表、树或者图的运算类似，只是取表头和取表尾是广义表特有的运算。,
