《数据结构（c语言版）严尉敏编第5章》由会员分享，可在线阅读，更多相关《数据结构（c语言版）严尉敏编第5章（95页珍藏版）》请在金锄头文库上搜索。
1、第五章 数组和广义表 dsjiaoxue 5.1 数组的类型定义 5.3 稀疏矩阵的压缩存储 5.2 数组的顺序表示和实现 5.4 广义表的类型定义 5.5 广义表的表示方法 5.6 广义表操作的递归函数 5.7 本章小结 5.8 习 题 第五章 数组和广义表 dsjiaoxue 5.1 数组的类型定义 由于数组中各元素具有统一的类型，并且数组元素 的下标一般具有固定的上界和下界，因此，数组的处 理比其它复杂的结构更为简单。多维数组是向量的推 广。例如，二维数组： (a) a01 a11 am-1,1 a0,n-1 a1 ,n-1 am-1 ,n-1 a00 a01 am-1,0 Amn= (
2、b) Amn=（a00,a01,a0,n-1),(a10,a11,a1,n-1),(am-1,0 , am-1,1,am-1,n-1) (c) 第五章 数组和广义表 dsjiaoxue typedef Elemtype array2mn; 等价于： typedef Elemtype array1n; typedef array1 array2m; 一般地：多维数组的定义如下页所示： 第五章 数组和广义表 dsjiaoxue ADT Array 数据对象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,n 数据关系： RR1, R2, ., Rn Ri | 0 j
3、k bk -1, 1 k n 且k i, 0 ji bi -2, i=2,.,n 基本操作: ADT Array 第五章 数组和广义表 dsjiaoxue InitArray(/我们所选择的 2)以列序为主序(高下标优先); 以“行序为主序”的存储映象 a0,1a0,0a0,2 a1,0a1,1a1,2 a0,1a0,0a0,2a1,0a1,1a1,2 L 第五章 数组和广义表 dsjiaoxue 按行序为主序存放 0 1 n-1 m*n-1 n am-1n-1 am-11 am-10 . a1n-1 a11 a10 a0n-1 . a01 a00 a00 a01 a0n-1 a10 a11
4、a1n-1 am-10 am-11 am-1n-1 . Loc(i,j)=Loc(0,0)+(n*i+ j)*L 第五章 数组和广义表 dsjiaoxue 二维数组A中任一元素aij 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij) L 称为基地址或基址 每个元素占L个存储单元 已经存储的元素个数 如果有： int a1020; 则有： loc(7,13)=loc(0,0)+(20*7+13)*sizeof(int); 如果有： int b768; 则有： loc(4，5， 6)=loc(0,0,0)+(6*8*4+8*5+6)*sizeof(int); 第五章 数组和广义
5、表 dsjiaoxue 推广到一般情况，可得到 n 维数组数据元素存储位 置的映象关系： 其中 cn = L，ci-1 = bi ci , 1 j=j; p-e=e; /生成结点 if( M.rheadi=NULL| M.rheadi-jj) /插在表头 p-right=M.rheadi; M.rheadi=p; else /将p插在合适的位置上 for(q=M.rheadi; q-right p-right=q-right; q-right=p; /行插入，在q后 if( M.cheadj=NULL| M.cheadj-ii) /插在表头 p-down=M.cheadj; M.rheadj=
6、p; else /将p插在合适的位置上 第五章 数组和广义表 dsjiaoxue for(q=M.cheadj; q-down p-down=q-down; q-down=p; /列插入，在q后 return OK; / CreatMatrix_OL 第五章 数组和广义表 dsjiaoxue 3.2 十字链表存储时两矩阵相加运算算法 void addMatrix(CrossList rowjpb-j:产生一个结点p；p所指结点 的值=pb所指结点的值；将p 插在pa的前面（pre的后面） 完成行插入；将p插在相应列 的适当位置上,pb后移,pre=p; break; case pa-jj: p
7、re=pa;pa=pa-right;break; case pa-j= =pb-j: k=pa-e+pb-e; 第五章 数组和广义表 dsjiaoxue if( k) pa-e=k; pre=pa;pa=pa-right; pb=pb-right; else 在相应的行、列中，删除pa所指结点；pa、pb后 移；break; /switch /while /for / addMatrix 第五章 数组和广义表 dsjiaoxue 5.4 广义表的定义 ADT Glist 数据对象：Dei | i=1,2,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据
8、关系： R1| ei-1 ,eiD, 2in 基本操作: P107 12 种基本操作 ADT Glist ( a , ( b , c ) , ( d , ( e , f ) ) ,g ) ( 3 , ( 2 , 4 ) , ( 6 , ( 4 , 6 ) ) ,12 ) 第五章 数组和广义表 dsjiaoxue InitGList( DestroyGList( CreateGList( CopyGList( GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); InsertFirst_GL( DeleteFi
9、rst_GL( Traverse_GL(L, Visit( ); 第五章 数组和广义表 dsjiaoxue 广义表是递归定义的线性结构，可以形式的写为： LS = ( 1, 2, , n ) 其中：i或为原子或为广义表 例如: A = ( ) B= ( e ) C = ( a , ( b , c , d ) ) D=( A , B , C ) E=( a , E ) 相当于一个无限的列表 ( a , ( a , ( a ,) ) ) 基本概念： 原子、子表、表长、 空表、表头、表尾、 表的深度 第五章 数组和广义表 dsjiaoxue 广义表是一个多层次的线性结构 例如：D=( A , B ,
10、 C ) A C ae B b c d D 第五章 数组和广义表 dsjiaoxue 任何一个非空广义表 LS = ( 1, 2, , n ) 均可分解为 表头 Head(LS) = 1和 表尾 Tail(LS) = (2, , n ) 两部分 例如：F=( ( a , b ) , c, ( d ) ) Head(F)= ( a , b ) Tail(F)=( c , ( d ) ) Head(Head(F)=a; Tail (Head(F)=( b ) 第五章 数组和广义表 dsjiaoxue 5.5 广义表的存储结构 1) 通常采用头、尾指针的链表结构 tag=0 atom原子结点： LS
11、= (a , ( b , c ),d ) Head(LS)=a; Tail(LS)=(b,c),d) 表结点: tag=1 hp tp ptr 第五章 数组和广义表 dsjiaoxue /-广义表的头尾链表存储表示- typedef enum ATOM, LIST ElemTag ;/元素的标志类型 typedef struct GLNode ElemTag tag;/公共部分，用于区分原子结点和表结点 union /atom是原子结点的值域，AtomType 由用户定义 AtomType atom ; struct struct GLNode *hp,*tp; ptr; ;/ptr是表结点的
12、指针域，ptr.hp和ptr.tp分别指向表头和表尾 *Glist ;/广义表类型 第五章 数组和广义表 dsjiaoxue 空表 LS = NULL 若表头为原子，则为tag=0 atom 否则，依次类推。 非空表 LS tag=1 指向表头的指针 指向表尾的指针 第五章 数组和广义表 dsjiaoxue A = ( ) B= ( e ) C = ( a , ( b , c , d ) ) D=( A , B , C ) B 1 0 e 1 1 1 1 10 a 0 b 0 d0 c C 1 1 1 D A=NULL 即: A 第五章 数组和广义表 dsjiaoxue ls =( a , (
13、 ) , ( ( b , c ) , d ) ) 1 1 1 1 1 1 1 0 a 0 b 0 c 0 d ls 第五章 数组和广义表 dsjiaoxue 2）广义表的扩展线性链表存储结构 typedef enum ATOM, LIST ElemTag ; / typedef struct GLNode ElemTag tag;/公共部分，用于区分原子结点和表结点 union AtomType atom ; /atom是原子结点的值域 struct GLNode *hp; ; / 表结点的表头指针 struct GLNode *tp; /相当于线性链表的next，指向下一个 /元素结点 *G
14、list ;/广义表类型 原子结点： tag=1 hp tptag=0 atom tp 表结点: 第五章 数组和广义表 dsjiaoxue A = ( ) B= ( e ) C = ( a , ( b , c , d ) ) D=( A , B , C ) A 1 B 1 0 e 1 1 1 D 1 C 1 1 0 d 0 a 0 b 0 c 第五章 数组和广义表 dsjiaoxue 5.6 m元多项式的表示：P 110-112 自学！ 第五章 数组和广义表 dsjiaoxue 5.7 广义表的递归算法 递归函数 一个含直接或间接调用本函数语句的函数被称 之为递归函数，它必须满足以下两个条件: 1)在每一次调用自己时，必须是(在某种意义上)更接 近于解; 2)必须有一个终止处理或计算的准则。 第五章 数组和广义表 dsjiaoxue 例如: 梵塔的递归函数 void hanoi (int n, char x, char y, char z) if (n=1) move(x, 1, z); else hanoi(n-1, x, z, y); move(x, n, z); hanoi(n-1, y, x, z); / hanoi 第五章 数组和广义表 dsjiaox
