《数据结构(c语言版)数组》由会员分享，可在线阅读，更多相关《数据结构(c语言版)数组（96页珍藏版）》请在金锄头文库上搜索。
1、5.1 数组的类型定义5.3 稀疏矩阵的压缩存储 5.2 数组的顺序表示和实现5.4 广义表的类型定义5.5 广义表的表示方法5.6 广义表操作的递归函数5.1 数组的类型定义 ADT Array 数据对象：Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,n 数据关系：RR1, R2, ., RnRi | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,.,n ADT Array 基本操作:二维数组的定义:数据对象:D = aij | 0ib1-1, 0 jb2-1数据关系:R = ROW, COL ROW = | 0ib1-2,
2、0jb2-1COL = | 0ib1-1, 0 jb2-2基本操作 ： InitArray(Q.dataQ.tu = arow, ccol, ctempccol; / if处理 的每一行M分析上述算法的时间复杂度累加器ctemp初始化的时间复杂度为(M.muN.nu)， 求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)， 进行压缩存储的时间复杂度为(M.muN.nu)， 总的时间复杂度就是(M.muN.nu+M.tuN.tu/N.mu)。 若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵， 则M中非零元的个数 M.tu = Mmn，N中非零元的个数 N.tu = Nnp， 相乘算法
3、的时间复杂度就是 (mp(1+nMN) ， 当M| ei-1 ,eiD, 2in ADT Glist基本操作:广义表是递归定义的线性结构，LS = ( 1, 2, , n ) 其中：i 或为原子 或为广义表例如: A = ( )F = (d, (e)D = (a,(b,c), F)C = (A, D, F)B = (a, B) = (a, (a, (a, , ) ) )广义表是一个多层次的线性结构例如： D=(E, F)其中:E=(a, (b, c)F=(d, (e)DEF a( ) d( )bce广义表 LS = ( 1, 2, , n )的结构特点:1) 广义表中的数据元素有相对次序；2)
4、 广义表的长度定义为最外层包含元素个数 ；3) 广义表的深度定义为所含括弧的重数；注意：“原子”的深度为 0 “空表”的深度为 1 4) 广义表可以共享；5) 广义表可以是一个递归的表。递归表的深度是无穷值，长度是有限值。6) 任何一个非空广义表 LS = ( 1, 2, , n)均可分解为表头 Head(LS) = 1 和表尾 Tail(LS) = ( 2, , n) 两部分。例如: D = ( E, F ) = (a, (b, c)，F )Head( D ) = E Tail( D ) = ( F ) Head( E ) = a Tail( E ) = ( ( b, c) )Head( (
5、 b, c) ) = ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( ) 结构的创建和销毁InitGList( DestroyGList(CreateGList( CopyGList(基本操作 状态函数GListLength(L); GListDepth(L);GListEmpty(L); GetHead(L); GetTail(L); 插入和删除操作InsertFirst_GL(DeleteFirst_GL( 遍历Traver
6、se_GL(L, Visit();5.5 广义表的表示方法通常采用头、尾指针的链表结构表结点:原子结点：tag=1 hp tptag=0 data1) 表头、表尾分析法：构造存储结构的两种分析方法:若表头为原子，则为空表 ls=NIL非空表 lstag=1 指向表头的指针指向表尾的指针tag=0 data否则，依次类推。L = ( a, ( x, y ), ( ( x ) ) )a ( x, y ) ( )1 LL = ( )0 a 1 1 1 1 1 0 a ( )x2) 子表分析法：若子表为原子，则为空表 ls=NIL非空表1 指向子表1的指针tag=0 data否则，依次类推。1 指向子
7、表2的指针1 指向子表n的指针ls例如:a (x, y) (x) LS=( a, (x,y), (x) )ls5.6 广义表操作的递归函数递归函数一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足 以下两个条件：1)在每一次调用自己时，必须是(在某种意义上)更接近于解;2)必须有一个终止处理或计算的准则。例如: 梵塔的递归函数 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); 二
8、叉树的遍历void PreOrderTraverse( BiTree T,void (Visit)(BiTree P) if (T) Visit(T-data);(PreOrderTraverse(T-lchild, Visit);(PreOrderTraverse(T-rchild, Visit); / PreOrderTraverse一、分治法 (Divide and Conquer)(又称分割求解法)如何设计递归函数？二、后置递归法(Postponing the work)三、回溯法(Backtracking)对于一个输入规模为 n 的函数或问题，用某种方法把输入分割成 k(1ptr.t
9、p)dep = GlistDepth(pp-ptr.hp);if (dep max) max = dep;return max + 1; / GlistDepthif (!L) return 1; if (L-tag = ATOM) return 0; 1 1 1 Lfor (max=0, pp=L; pp; pp=pp-ptr.tp)dep = GlistDepth(pp-ptr.hp);if (dep max) max = dep;例如: pppp-ptr.hppppppp-ptr.hppp-ptr.hp例二 复制广义表新的广义表由新的表头和表尾构成。可以直接求解的两种简单情况为：空表复制
10、求得的新表自然也是空表;原子结点可以直接复制求得。将广义表分解成表头和表尾两部分， 分别(递归)复制求得新的表头和表尾，若 ls= NIL 则 newls = NIL否则构造结点 newls, 由 表头ls-ptr.hp 复制得 newhp由 表尾 ls-ptr.tp 复制得 newtp并使 newls-ptr.hp = newhp,newls-ptr.tp = newtp复制求广义表的算法描述如下:Status CopyGList(Glist / 复制空表else if ( !(T = (Glist)malloc(sizeof(GLNode) ) exit(OVERFLOW); / 建表结点
11、T-tag = L-tag;if (L-tag = ATOM) T-atom = L-atom; / 复制单原子结点else / elsereturn OK; / CopyGList分别复制表头和表尾CopyGList(T-ptr.hp, L-ptr.hp);/ 复制求得表头T-ptr.hp的一个副本L-ptr.hp CopyGList(T-ptr.tp, L-ptr.tp);/ 复制求得表尾T-ptr.tp 的一个副本L-ptr.tp语句 CopyGList(T-ptr.hp, L-ptr.hp);等价于CopyGList(newhp, L-ptr.tp);T-ptr.hp = newhp;
12、例三 创建广义表的存储结构对应广义表的不同定义方法相应地有不同的创建存储结构的算法。假设以字符串 S = (1, 2, , n ) 的形式 定义广义表 L，建立相应的存储结构。由于S中的每个子串i定义 L 的一个子表 ，从而产生 n 个子问题，即分别由这 n个子 串 (递归)建立 n 个子表，再组合成一个广义表。可以直接求解的两种简单情况为：由串( )建立的广义表是空表；由单字符建立的子表只是一个原子结点。如何由子表组合成一个广义表？首先分析广义表和子表在存储结构中的关系。先看第一个子表和广义表的关系:1 L指向广义表 的头指针指向第一个 子表的头指针再看相邻两个子表之间的关系:1 1 指向第
13、i+1个 子表的头指针指向第i个 子表的头指针可见，两者之间通过表结点相链接。若 S = ( ) 则 L = NIL； 否则，构造第一个表结点 *L，并从串S中分解出第一个子串1，对 应创建第一个子广义表 L-ptr.hp；若剩余串非空，则构造第二个表结点 L-ptr.tp，并从串S中分解出第二个子 串 2，对应创建第二个子广义表 ；依次类推，直至剩余串为空串止。void CreateGList(Glist / 创建空表else L=(Glist) malloc(sizeof(GLNode);L-tag=List; p=L;sub=SubString(S,2,StrLength(S)-1);/
14、脱去串S的外层括弧 / else 由sub中所含n个子串建立n个子表;do sever(sub, hsub); / 分离出子表串hsub=i if (!StrEmpty(sub) p-ptr.tp=(Glist)malloc(sizeof(GLNode);/ 建下一个子表的表结点*(p-ptr.tp) p=p-ptr.tp; while (!StrEmpty(sub); p-ptr.tp = NULL; / 表尾为空表创建由串hsub定义的广义表p-ptr.hp;if (StrLength(hsub)=1) p-ptr.hp=(GList)malloc(sizeof(GLNode);p-ptr.hp-tag=ATOM;p-ptr.hp-atom=hsub; / 创建单原子结点else CreateGList(p-ptr.hp, hsub);/递归建广义表 后置递归的设计思想为:递归的终结状态是，当前的问题可以直接求解，对原问题
