数据结构(C语言版)数组和广义表.ppt

5.1 数组的类型定义 5.3 稀疏矩阵的压缩存储 5.2 数组的顺序表示和实现 5.4 广义表的类型定义 5.5 广义表的表示方法 5.6 广义表操作的递归函数 5.1 数组的类型定义 ADT Array 数据对象 ： D aj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,.,n 数据关系 ： R R1, R2, ., Rn Ri | 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, 0jb2-1 COL = | 0ib1-1, 0 jb2-2 基本操作 ： InitArray( 2) 计算中进行了很多和零值的运算， 遇除法，还需判别除数是否为零 。 1) 尽可能少存或不存零值元素； 解决问题的原则 : 2) 尽可能减少没有实际意义的运算； 3) 操作方便。 即： 能尽可能快地找到与 下标值 (i， j)对应的元素， 能尽可能快地找到同 一行或同一列的非零值元。 1) 特殊矩阵 非零元在矩阵中的分布有一定规则 例如 : 三角矩阵 对角矩阵 2) 随机稀疏矩阵 非零元在矩阵中随机出现 有两类稀疏矩阵 ： 随机稀疏矩阵的压缩存储方法 : 一、三元组顺序表 二、行逻辑联接的顺序表 三、 十字链表 #define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型 一、三元组顺序表 typedef union Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩阵类型 如何求转臵矩阵？ 0280036 00070 500140 005 2800 000 0714 3600 用常规的二维数组表示时的算法 其时间复杂度为 : O(mu nu) for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol; 用“三元组”表示时如何实现？ 1 2 14 1 5 -5 2 2 -7 3 1 36 3 4 28 2 1 14 5 1 -5 2 2 -7 1 3 36 4 3 28 首先应该确定每一行的第一个非零元 在三元组中的位臵。 1 2 15 1 5 -5 2 2 -7 3 1 36 3 4 28 co l 1 2 3 4 5 N um pos 1 2 0 1 1 C pot c ol 1 2 4 4 5 cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; Status FastTransposeSMatrix(TSMatrix M, TSMatrix T.nu = M.mu; T.tu = M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol = 0; for (t=1; t=M.tu; +t) +numM.datat.j; cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; for (p=1; p=M.tu; +p) / if return OK; / FastTransposeSMatrix 转臵矩阵元素 Col = M.datap.j; q = cpotcol; T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; +cpotcol 分析算法 FastTransposeSMatrix的时间 复杂度： 时间复杂度为 : O(M.nu+M.tu) for (col=1; col=M.nu; +col) for (t=1; t=M.tu; +t) for (col=2; col=M.nu; +col) for (p=1; p=M.tu; +p) 三元组顺序表又称 有序的双下标 法 ，它的特点是，非零元在表中按行 序有序存储，因此 便于进行依行顺序 处理的矩阵运算 。然而，若需 随机 存 取某一行中的非零元，则需从头开始 进行查找。 二、行逻辑联接的顺序表 #define MAXMN 500 typedef struct Triple dataMAXSIZE + 1; int rposMAXMN + 1; int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类型 修改前述的稀疏矩阵的结构定义， 增加一个数据成员 rpos，其值在稀疏矩 阵的初始化函数中确定。 例如 ： 给定一组下标，求矩阵的元素值 ElemType value(RLSMatrix M, int r, int c) p = M.rposr; while (M.datap.i=r if (M.datap.i=r else return 0; / value 矩阵乘法的精典算法 : for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 其时间复杂度为 : O(m1 n2 n1) Q初始化； if Q是非零矩阵 / 逐行求积 for (arow=1; arow=M.mu; +arow) / 处理 M的每一行 ctemp = 0; / 累加器清零 计算 Q中第 arow行的积并存入 ctemp 中； 将 ctemp 中非零元压缩存储到 Q.data； / for arow / if 两个稀疏矩阵相乘（ QMN） 的过程可大致描述如下： Status MultSMatrix (RLSMatrix M, RLSMatrix N, RLSMatrix Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; if (M.tu*N.tu != 0) / Q是非零矩阵 for (arow=1; arow=M.mu; +arow) / 处理 M的每一行 / for arow / if return OK; / MultSMatrix ctemp = 0; / 当前行各元素累加器清零 Q.rposarow = Q.tu+1; for (p=M.rposarow; pM.rposarow+1;+p) /对当前行中每一个非零元 brow=M.datap.j; if (brow N.nu ) t = N.rposbrow+1; else t = N.tu+1 for (q=N.rposbrow; q t; +q) ccol = N.dataq.j; / 乘积元素在 Q中列号 ctempccol += M.datap.e * N.dataq.e; / for q / 求得 Q中第 crow( =arow)行的非零元 for (ccol=1; ccol MAXSIZE) return ERROR; 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， 相乘算法的时间复杂度就是 (mp(1+nMN) ， 当 M0.05 和 N0.05及 n 1000时， 相乘算法的时间复杂度就相当于 (mp)。 三、 十字链表 M . c he a d M . rhe a d 3 0 0 5 0 -1 0 0 2 0 0 0 1 1 3 1 4 5 2 2 -1 3 1 2 5.4 广义表的类型定义 ADT Glist 数据对象 ： D ei | i=1,2,.,n; n0; ei AtomSet 或 ei GList, AtomSet为某个数据对象 数据关系： LR | ei-1 ,ei D, 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) D E F a ( ) d ( ) b c e 广义表 LS = ( 1, 2, , n )的结构特点 : 1) 广义表中的数据元素有相对 次序 ； 2) 广义表的 长度 定义为最外层包含元素个数； 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( ( 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( 遍历 Traverse_GL(L, Visit(); 5.5 广义表的表示方法 通常采用头、尾指针的链表结构 表结点 : 原子结点： tag=1 hp tp tag=0 data 1) 表头、表尾分析法： 构造存储结构的两种分析方法 : 若表头为原子，则为 空表 ls=NIL 非空表 ls tag=1 指向表头的指针 指向表尾的指针 tag=0 data 否则，依次类推。 例如 : L=(a, (x, y), (x) ) a (x, y), (x) ) ( x, y) ( (x) ) x (y) (x) ( ) y ( ) (x) ( ) x ( ) L = ( a, ( x, y ), ( ( x ) ) ) a ( x, y ) ( ) 1 L = ( ) 0 a 1 1 1 1 1 0 a ( ) x 2) 子表分析法： 若子表为原子，则为 空表 ls=NIL 非空表 1 指向子表 1 的指针 tag=0 data 否则，依次类推。 1 指向子表 2 的指针 1 指向子表 n 的指针 ls 例如 : a (x, y) (x) LS=( a, (x,y), (x) ) ls 5.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); 二叉树的遍历 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.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; return max + 1; / GlistDepth if (!L) return 1; if (L-tag = ATOM) return 0; 1 1 1 L for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; 例如 : pp pp-ptr.hp pp pp pp-ptr.hp pp-ptr.hp 例二 复制广义表 新的广义表由新的表头和表尾构成。 可以直接求解的两种简单情况为： 空表复制求得的新表自然也是空表 ; 原子结点可以直接复制求得。 将广义表分解成表头和表尾两部分， 分别 (递归 )复制求得新的表头和表尾， 若 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); / 建表结点 T-tag = L-tag; if (L-tag = ATOM) T-atom = L-atom; / 复制单原子结点 else / else return 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; 例三 创建广义表的存储结构 对应广义表的 不同 定义方法 相应地有 不同 的创建存储结构 的算法。 假设以字符串 S = (1, 2, , n ) 的形式 定义广义表 L，建立相应的存储结构 。 由于 S中的每个子串 i定义 L 的一个 子表 ， 从而产生 n 个子问题，即分别由这 n个子串 (递归 )建立 n 个子表，再 组合 成一个广义表。 可以直接求解的两种简单情况为： 由串 ( )建立的广义表是 空表； 由单字符建立的子表只是一个原子结点。 如何由子表组合成一个广义表？ 首先分析广义表和子表在存储结构中 的关系。 先看第一个子表和广义表的关系 : 1 L 指向广义表 的头指针 指向第一个 子表的头指针 再看相邻两个子表之间的关系 : 1 1 指向第 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); /脱去串 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); /递归建广义表 假如某个问题的求解过程可以分成 若干步进行，并且当前这一步的解可 以直接求得，则 先求出当前这一步的 解 ，对于 余下的问题 ，若问题的性质 和原问题类似，则又可 递归求解 。 后臵递归的设计思想为 : 递归的 终结状态 是，当前的问题可以 直接求解 ，对原问题而言，则是已走到 了求解的 最后一步 。 链表是可以如此求解的一个典型例子。 例如：编写“ 删除单链表中所有值为 x 的数据元素 ”的算法。 1) 单链表是一种顺序结构，必须从第 一个结点起，逐个检查每个结点的数 据元素； 分析 : 2) 从另一角度看，链表又是一个递归 结构，若 L 是线性链表 (a1, a2, , an) 的头指针，则 L-next是线性链表 (a2, , an)的头指针。 a1 a2 a3 an L 例如 : a1 a2 a3 an L a1 a2 a3 an L 已知下列链表 1) “a1=x”，则 L 仍为删除 x 后的链表头指针 2) “a1x”，则余下问题是考虑以 L-next 为头 指针的链表 L-next L-next=p-next p=L-next void delete(LinkList L-next=p-next; free(p); delete(L, x); else delete(L-next, x); / delete 删除广义表中所有元素为 x的原子结点 分析 : 比较广义表和线性表的 结构特点 ： 相似处： 都是链表结构。 不同处： 1)广义表的数据元素可能还是个 广义表； 2)删除时，不仅要删除原子结点， 还需要删除相应的表结点。 void Delete_GL(Glist / 考察第一个子表 if (head-tag = Atom) L = L-ptr.tp; / 修改指针 free(head); / 释放原子结点 free(p); / 释放表结点 Delete_GL(L, x); / 递归处理剩余表项 1 L 0 x 1 p L head if (head-tag = LIST) /该项为广义表 Delete_GL(head, x); Delete_GL(L-ptr.tp, x); / 递归 处理剩余表项 1 L 0 a 1 1 head L-ptr.tp 回溯法 是一种“ 穷举 ”方法。其基本思想为： 假设问题的解为 n 元组 (x1, x2, , x n)， 其中 xi 取值于集合 Si。 n 元组的子组 (x1, x2, , x i) (in)的一个合法布局 / 时，输出之。 if (in) 输出棋盘的当前布局 ; else for (j=1; jn) else while ( ! Empty(Si) 从 Si 中取 xi 的一个值 viSi; if (x1, x2, , x i) 满足约束条件 B( i+1, n); / 继续求下一个部分解 从 Si 中删除值 vi; / B 综合几点： 1. 对于 含有递归特性 的问题，最好设计 递归形式的算法。 但也 不要单纯追求形 式 ，应在算法设计的分析过程中“就事 论事”。例如，在利用分割求解设计算 法时，子问题和原问题的性质相同；或 者，问题的当前一步解决之后，余下的 问题和原问题性质相同，则自然导致递 归求解。 2. 实现 递归函数，目前必须利用 “ 栈 ”。 一个递归函数必定能改写 为利用栈实现的非递归函数；反之， 一个用栈实现的非递归函数可以改 写为递归函数。需要注意的是递归 函数递归层次的深度决定所需存储 量的大小。 3. 分析 递归算法的工具是 递归树 ，从 递归树上可以得到递归函数的各种相 关信息。例如： 递归树的深度即为递 归函数的 递归深度 ；递归树上的结点 数目恰为函数中的主要操作 重复进行 的次数 ； 若递归树蜕化为 单支树 或者 递归树中 含有很多相同的结点 ，则表 明该递归函数不适用 。 例如 : n=3的梵塔算法中主要操作 move的 执行次数可以利用下列递归树进行分析 : move(3, a, b, c) move(2, a, c, b) move(2, b, a, c) move(1, a, b, c) move(1, c, a, b) move(1, b, c, a) move(1, a, b, c) 上图递归树的中序序列即为圆盘的移动操作序列。 又如 : 求 n!的递归函数的递归树已退化为一个 单枝树 ;而计算斐波那契递归函数的递归树中 有很多重复出现的结点。 n n-1 1 0 。 。 。 F5 F4 F3 F3 F2 F2 F1 F1 F0 F1 F0 。 4. 递归函数中的 尾递归 容易消除。 例如：先序遍历二叉树可以改写为： void PreOrderTraverse( BiTree T) While (T) Visit(T-data); PreOrderTraverse(T-lchild); T = T-rchild; / PreOrderTraverse void delete(LinkList L=L-next; free(p); delete(L, x); else delete(L-next, x); 又如 : void delete(LinkList pre=L; while (p) if (p-data=x) pre-next=p-next; free(p); p=pre-next; else pre=p; p=p-next; 可 改 写 为 5. 可以用 递归方程 来表述递归函数的 时间性能 。 例如 : 假设解 n个圆盘的梵塔的执行 时间为 T(n) 则递归方程为： T(n) = 2T(n-1) + C， 初始条件为： T(0) = 0 1. 了解数组的两种存储表示方法 ， 并掌握数组在以行为主的存储结构 中的地址计算方法 。 2. 掌握对特殊矩阵进行压缩存储时 的下标变换公式 。 3. 了解稀疏矩阵的两类压缩存储方 法的特点和适用范围 ， 领会以三元 组表示稀疏矩阵时进行矩阵运算采 用的处理方法 。 4. 掌握广义表的结构特点及其存储 表示方法，读者可根据自己的习惯 熟练掌握任意一种结构的链表，学 会对非空广义表进行分解的两种分 析方法：即可将一个非空广义表分 解为表头和表尾两部分或者分解为 n 个子表。 5. 学习利用分治法的算法设计思 想编制递归算法的方法。