算法分析与设计：习题选讲第七章

1、第七章1426 电话号码前缀检索1310 二叉查找树，前序中序后序遍历1210 二叉树 ，知道前序、后序求可能的方法数1090 最小生成树1156 二叉树的前序遍历1252 字符串划分前后缀1155 判断两个点是否连通，并查集1132 ROUTES 用括号序列表示树，求两节点最近公共祖先1306 排序，可用堆排序1083 最小生成树1426 电话号码前缀检索给出N个电话号码（N = 10000）,每个电话号码的长度不大于10，当存在一个电话号码是另外一个电话号码的前缀时，则会发生冲突。如果不存在冲突输出YES，否则输出NO解题思路1. 把n个电话号码放进一个set内2. 枚举每个电话号码的前缀

2、，查询是否存在于set里int n;string c11000;set ss;bool isConsistent()ss.clear();for (int i = 0; i n; i+) ss.insert(ci);for (int i = 0; i n; i+) string st = ;for (int j = 0; j ci.size() - 1; j+) st += cij;if (ss.count(st) return false;return true;1310 二叉查找树给出N个数，按照顺序建立一棵二叉查找树，然后输出该树的前序遍历，中序遍历，后序遍历。struct Node i

3、nt val;int left, right;Node(int val = 0):val(val), left(0),right(0) ; p300000;void Add(int root, int val) while (true) if (proot.val val) if (proot.right) root = proot.right; else proot.right = +tot； ptot = Node(val); return; else if (proot.left) root = proot.left; else proot.left = +tot; ptot = Nod

4、e(val); return; inline void Preorder(int root)if (!root) return;printf( %d, proot.val);Preorder(proot.left);Preorder(proot.right);inline void Inorder(int root)if (!root) return;Inorder(proot.left);printf( %d, proot.val);Inorder(proot.right);inline void Postorder(int root)if (!root) return;Postorder(

5、proot.left);Postorder(proot.right);printf( %d, proot.val);1210 二叉树给出一棵二叉树前序遍历和后序遍历的顺序，要求出总共有多少棵不同形态的二叉树满足这样的遍历顺序。解题思路1. 前序遍历第一个元素是根，后序遍历最后一个元素是根 2. 前序遍历第二个元素是某子树的根，但左右不确定 3. 在后序遍历中找到前序遍历的第二个元素，那么以这个元素为基准，可以划分新的左右子树 4. 当前序遍历的第二个元素出现在后序遍历的倒数第二位，以后序遍历倒数第三位起向左数都是子树的元素，但是左右不确定，因此有2种情况 long long calc(stri

6、ng pre, string post) long long ans = 1;int len=pre.size();for(int i= 0; i len - 1; i+) int current = len - 1;while(prei != postcurrent) current-;if(current & prei+1 = postcurrent - 1) ans *= 2;return ans;1090 最小生成树题目大意：给出N=500个节点的无向图，每两个点之间都有一条无向边。问该无向图的最小生成树中，最长的一条边的长度。解题思路求最小生成树的算法中，有Prim算法和kruska

7、l算法。Prim算法复杂度N2（N为点数）, Kruskal算法MlogM（M为边数） 因此，对于稠密图而言，Prim算法的复杂度更高效率。int solve()for (int i = 0; i n; i+) ui = false, disti = e0i;int ans = 0, p;for (int i = 0; i n; i+) p = -1; for (int j = 0; j distj) p = j; up = true; ans = max(ans, distp); for (int j = 0; j n; j+) if (uj | distj = epj) continue;

8、 distj = epj; return ans;1156 二叉树的前序遍历给定一棵N个节点的二叉树，输出其前序遍历的顺序解题思路：1.按照题目要求把二叉树读入2.以前序遍历顺序输出（可参考1310）void Read_Tree()memset(is_root, 0, sizeof(is_root);char c;int l, r, m; for (int i = 0; i m c l r; is_rootm = !is_rootm; is_rootl = !is_rootl; is_rootr = !is_rootr; pm.Left = l; pm.Right = r; pm.ch = c

9、;for (int i = 1; i = 1000; i+) if (is_rooti) root = i;void Preorder(int root)if (!root) return;cout proot.ch;Preorder(proot.Left);Preorder(proot.Right);1252 字符串划分前后缀给一个单词word将一个前缀换成解释1252 字符串划分前后缀将一个后缀换成解释1252 字符串划分前后缀单词的后缀与单词更紧密例如：unvaporizenot vaporizenot change into vapor 解题思路先处理前缀strstr函数判断单词是否有

10、前缀去掉前缀递归处理后缀反转字符串strstr函数判断单词是否有后缀的反转去掉后缀反转字符scanf(%s,r);if(strstr(r,anti)=r) printf(against ); suffixe(r+4); puts();else if(strstr(r,re)=r) suffixe(r+2); printf( againn);.else suffixe(r); puts();int n=strlen(r);reverse(r,r+n);if(strstr(r,re)=r) reverse(r,r+n); rn-2=0; printf(one who %ss,r);else if(

11、strstr(r,gni)=r) reverse(r,r+n); rn-3=0; printf(to actively %s,r);else reverse(r,r+n); printf(%s,r);1155 判断两个点是否连通，并查集一个有向图有N个点(=200)问能否从点0到点N-1解题思路DFSBFS用floyed算法求出任意两点是否可达n=200最后判断0到n-1是否可达#define rep(i,n) for(i=0;in;i+)#define PB push_backconst int oo=0 x3fffffff;rep(i,n) rep(j,n) rij=oo; rii=0;r

12、ep(i,m) scanf(%d%d,&a,&b); rab=0;rep(b,n)rep(a,n)rep(c,n) rac=min(rac,rab+rbc);1132 ROUTES 用括号序列表示树，求两节点最近公共祖先给出一棵树求从一个叶节点到另一个叶节点的路径树的表达式：T(B(FHM(RJK)WD(L)E)T(B(FHM(RJK)WD(L)E)解题思路用stack处理树表达式计算出每一个节点的父节点求出从开始节点到根节点的路径A求出从结束节点到根节点的路径B删除AB路径末尾相同的元素顺序输出路径A倒序输出路径Brep(i,27) fi=0;stack S; S.push(0);for(i

13、=0;rsi;i+)if(rsi=) S.pop();else if(rsi!=) frsi-A+1=S.top(); if(rsi+1=() S.push(rsi-A+1);puts(rs);while(gets(rs)!=0 & rs0) sscanf(rs,%s%s,s1,s2); An=0; for(x=s10-A+1;x;x=fx) AAn+=x; Bn=0; for(x=s20-A+1;x;x=fx) BBn+=x; while(An & Bn & AAn-1=BBn-1) An-; Bn-; rep(i,An) if(i) printf(-); putchar(Ai+A-1);

14、for(i=Bn;i=0;i-) printf(-%c,Bi+A-1); puts();1306 排序，可用堆排序给一个数组从小到大排序每隔m个位置输出数组里的元素解题思路堆排序make_heap(a,a+n,cmp);a0;an+=key; push_heap(a,a+n,cmp);pop_heap(a,a+n,cmp);用sort排序，直接输出即可rep(i,n) scanf(%d,&ri);sort(r,r+n);for(i=0;in;i+=m) if(i) putchar( ); printf(%d,ri);puts();1083 最小生成树一个无向图求最小生成树解题思路kruskal算法按边的长度排序从小到大遍历边(a,b)用并查集判断ab两点是否属于联通集合如果ab不联通合并ab所在的集合答案累加边(a,b)int F(int x) if(x=fx) return x; return fx=F(fx);bool cmp(int a,int b) return CaCb;rep(i,m) scanf(%d%d%d,&Ai,&Bi,&Ci); idi=i;sort(id,id+m,cmp);ans=0;rep(i,m) a=Aidi; b