济南大学数据结构第五章

1、第五章数组和广义表数组和广义表均是元素为复合结构的线性结构。5.1数组的定义以二维数组为例，二维数组通常可以描述为两种形式:以行序为主序 : PASCAL、 C可以看成 A = ( ， ， . . .， )T01m-1其中 i 是一个行向量形式的线性表，0i m-1i = ( ai 0， ai 1， . . . ， ai n-1 )以列序为主序 :FORTRAN可以看成 A = ( ， ， )01n-1其中 是一个列向量形式的线性表，0j n-1jj = ( a0 j， a1 j， am-1j)T5.2数组的表示和实现数组一旦被定义，其维数和维界就不再改变，故通常采用顺序存储结构。如何将多维数

2、组结构转换对应一组连续的存储单元？以列序为主序以行序为主序对于数组，一旦规定了维数和维界，如何计算数组元素的存储位置?设数组以行序为主序。二维数组Amn数组元素aij 的存储位置为LOC(i，j) =LOC(0，0) + ( n i +Lj )LOC(0，0)是 a00 的存储位置；是每个数组元素占用的存储单元数；例， LOC(1， 1) =LOC(0， 0) + ( n1 + 1 ) L三维数组A ( b1，b2，b3 )LOC(0， 0， 0)是 a000 的存储位置；是每个数组元素占用的存储单元数；LOC(1， 1， 1) = LOC(0，0，0) + ( b2 b3 1 + b3 1

3、+ 1 ) L 数组元素 aijk 的存储位置为 :LOC(i，j，k) = LOC(0，0，0) + ( b2 b3 i + b3 j + k ) L维数组 A ( b1，b2， ， bn )的元素存储位置可计算为 : LOC(j1,j2, ,jn)= LOC(0,0, ,0) +( b2 bnj1 + b3 bn j2 + + bnjn-1 + jn ) L 5.3 矩阵的压缩存储矩阵元素如何存储？通常利用二维数组来存储矩阵元素。Bmna i jb i-1,j-1实际中，存在许多特殊矩阵，例如在矩阵中有许多值相同的元素或者零元素。用定长数组存储造成浪费。为了节省存储空间，需要对这类矩阵进行

4、压缩存储。压缩存储是指为多个值相同的元素只分配一个存储空间；对零元素不分配空间。对称矩阵三角矩阵对角矩阵稀疏矩阵阶对称矩阵n 阶矩阵 A 满足 :ai j = aj i通常表示为 :n2 个矩阵元素只需占用n(n+1)/2 个存储空间设计用一维数组SAn(n+1)/2 存储 n 阶对称矩阵A 。关键问题 :如何建立数组元SAk 和矩阵元aij 之间的一一对应关系。一定是 i ，j 的函数a i+b j+ca i + j + ca n + 1 + c=a=,b=1 ,c=-1三角矩阵所谓下 (上)三角矩阵是指矩阵的上(下)三角 (不包括对角线 )中的元均为常数c 的阶矩阵。下三角矩阵和对称矩阵基

5、本一样，只需除存储其下 (上)三角中的元之外，再增加一个存储单元存放 c 。关键问题 :如何建立数组元SAk 和矩阵元aij 之间的一一对应关系。对角矩阵所有的非零元都集中在以主对角线为中心的带状区域中。一般情况三对角矩阵关键问题:如何建立数组元SAk 和矩阵元aij之间的一一对应关系。一定是 i ，j 的函数 a i + b j + c= a i+j+ca (n-1) + (n-2) + c3n-7代入解得： a=2 ,b=1 , c=-3K = 2i + j - 3(| i - j | 1)作业 :五对角矩阵稀疏矩阵非零元很少的矩阵。稀疏因子 :设 mn 的矩阵，有t 个非零元，令通常认为

6、 0.05时称为稀疏矩阵。稀疏矩阵的压缩存储三元组顺序表行逻辑链接顺序表十字链表三元组顺序表三元组 ( i ，j ， aij )表示非零元素i 行数， j 列数， aij 非零元。5.4广义表的定义广义表 (列表 )LS= ( a1，a2，an )LS:列表名称: 列表长度 (元素的个数 )ai:可以是单个数据，也可以是子列表，分别称为原子和子表。a1:LS 的表头 (第一个元素 )。( a2，a3， an ) :LS 的表尾 (列表 )。列表的举例 :(1)A=() A 是一个空列表，长度为0 。(2)B = ( e ) B 中只有一个原子 e ，长度为 1 。(3)C = ( a ,( b

7、 ,c ,d ) ) C 有两个元素， 原子 a 和子表 ( b ,c ,d ) ，长度为 2 。(4)D = ( ( ) ,( e ) ,( a ,( b ,c ,d ) ) ) D 有三个元素，都是子表，长度为3 。(5)E = ( a ,E ) E 为一个递归的表，长度为2 。例 E = ( a ,( a ,( a , ) ) ) 。列表的性质 :列表是一个多层次的结构。例 D = ( ( ) ,( e ) ,( a ,( b ,c ,d ) ) )列表可为其它列表的子表所调用。例，D=(A,B,C)列表可以是一个递归的表。例， E = ( a ,E )任何一个非空列表，其表头可能是原子

8、或列表，而表尾一定是列表。例， B = ( e )表头为原子 e；表尾为空表 ( ) 。例， B = ( ( a ,b ) ,c )表头为列表 ( a ,b ) ；表尾为列表 ( c ) 。()=()？( ) 为空表，长度0；( ( ) ) 长度为1 的列表，可分解得到表头、表尾。5.5广义表的存储结构由于广义表中的数据元素可以具有不同的结构 (原子、列表 )，难以用顺序存储结构表示，通常采用链式存储结构。结点结构 :tag :标志域， 1 为表结点， 0 为原子结点。hp:指向表的表头元素结点。atom:原子结点的值域。tp:指向下一个元素域。例 D = ( ( ) ,( e ) ,( a

9、,( b ,c ,d ) ) )作业：求 (a,b),(c,d),(e,f)的表头和表尾出师表两汉：诸葛亮先帝创业未半而中道崩殂， 今天下三分， 益州疲弊， 此诚危急存亡之秋也。然侍卫之臣不懈于内，忠志之士忘身于外者，盖追先帝之殊遇，欲报之于陛下也。诚宜开张圣听，以光先帝遗德，恢弘志士之气，不宜妄自菲薄，引喻失义，以塞忠谏之路也。宫中府中，俱为一体；陟罚臧否，不宜异同。若有作奸犯科及为忠善者，宜付有司论其刑赏，以昭陛下平明之理；不宜偏私，使内外异法也。侍中、侍郎郭攸之、费祎、董允等，此皆良实，志虑忠纯，是以先帝简拔以遗陛下：愚以为宫中之事，事无大小，悉以咨之，然后施行，必能裨补阙漏，有所广益。

10、将军向宠，性行淑均，晓畅军事，试用于昔日，先帝称之曰愚以为营中之事，悉以咨之，必能使行阵和睦，优劣得所。“能 ”，是以众议举宠为督：亲贤臣， 远小人， 此先汉所以兴隆也； 亲小人， 远贤臣， 此后汉所以倾颓也。 先帝在时，每与臣论此事， 未尝不叹息痛恨于桓、 灵也。 侍中、尚书、 长史、 参军，此悉贞良死节之臣，愿陛下亲之、信之，则汉室之隆，可计日而待也。臣本布衣，躬耕于南阳，苟全性命于乱世，不求闻达于诸侯。先帝不以臣卑鄙，猥自枉屈，三顾臣于草庐之中，咨臣以当世之事，由是感激，遂许先帝以驱驰。后值倾覆，受任于败军之际，奉命于危难之间，尔来二十有一年矣。先帝知臣谨慎，故临崩寄臣以大事也。受命以来，夙夜忧叹，恐托付不效，以伤先帝之明；故五月渡泸，深入不毛。今南方已定，兵甲已足，当奖率三军，北定中原，