[其它考试]Chap5-2.ppt

第五章 数组与广义表 复习： 数组的特点 只有引用型操作，没有加工型操作; 数组是多维结构，而物理存储是一维的连续空间。 数组的两种映象方式： 以行序为主序(低下标优先); 以列序为主序(高下标优先); 二维数组A中任一元素a[i,j ]的存储位置 LOC(i,j) = LOC(0,0) + (b2×i＋j)×L 随机的稀疏矩阵 三种存储方式： 广义表可以被其他表引用 F = (d, (e)) D = ((a,(b,c)), F) 对于一个输入规模为 n 的问题，用某 种方法把输入分割成 k(1k≤n)个子集，从 而产生 l 个相同特征属性的子问题，分别求 解这 l 个问题，得出 l 个问题的子解，再用 某种方法把它们组合成原来问题的解。若子 问题还相当大，则可以反复使用分治法，直 至最后所分得的子问题足够小，以至可以直 接求解为止。 分治法的设计思想为: 在利用分治法求解时，所得子问题的类型常常和原问题相同，因而很自然地导致递归求解。 例如: 焚塔问题: Hanoi(n, x, y, z) 可递归求解 Hanoi(n-1, x, z, y) 将 n 个盘分成两个子集(1至n-1 和 n )，从而产生下列三个子问题: 1) 将1至n-1号盘从 x 轴移动至 y 轴; 3) 将1至n-1号盘从y轴移动至z轴; 2) 将 n号盘从 x 轴移动至 z 轴; 可递归求解 Hanoi(n-1, x, z, y) 又如: 遍历二叉树: Traverse(BT) 可递归求解 Traverse(LBT) 将 n 个结点分成三个子集(根结点、左子树 和右子树 )，从而产生下列三个子问题: 1) 访问根结点; 3) 遍历右子树; 2) 遍历左子树; 可递归求解 Traverse(RBT) 广义表从结构上可以分解成 广义表 = 表头 + 表尾 或者 广义表 = 子表1 + 子表2 + ··· + 子表n 因此常利用分治法求解之。 算法设计中的关键问题是，如何将 l 个子问题的解组合成原问题的解。 广义表的头尾链表存储表示： typedef enum {ATOM, LIST} ElemTag; // ATOM==0:原子, LIST==1:子表 typedef struct GLNode { ElemTag tag; // 标志域 union{ AtomType atom; // 原子结点的数据域 struct {struct GLNode *hp, *tp;} ptr; }; } *GList tag=1 hp tp ptr 表结点 例一 求广义表的深度 例二 复制广义表 例三 创建广义表的存储结构 广义表的深度=Max {子表的深度} +1 例一 求广义表的深度 可以直接求解的两种简单情况为: 空表的深度 = 1 原子的深度 = 0 将广义表分解成 n 个子表，分别(递归)求得每个子表的深度, int GlistDepth(Glist L) { // 返回指针L所指的广义表的深度 for (max=0, pp=L; pp; pp=pp-ptr.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; 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 1 1 1 L … ? 例二 复制广义表 新的广义表由新的表头和表尾构成。 可以直接求解的两种简单情况为: 空表复制求得的新表自然也是空表; 原子结点可以直接复制求得。 将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾， 若 ls= NIL 则 newls = NIL 否则 构造结点 newls, 由 表头ls-ptr.hp 复制得 newhp 由 表尾 ls-