第1章 数据结构习题讲解.pptVIP

存在问题 书写不规范，存在较多语法错误 符号“.”的应用 输入输出参数 一条语句的结束 符号“ ▌”的应用 标志算法结束 C++的语法、格式(最好上机调试) 要养成写注释的好习惯 //单行注释 /*多行注释 注意格式*/ 注意程序的可读性 习题 2-1 若S是n个元素的集合，则S的幂集是S的所有可能子集的集合。例如，若S = {a,b,c}，则Powerset (S) = { {} , {a} , {b} , {c} , {a , b} , {a , c} , {b , c} , {a , b , c} }请给出一个计算幂集Powerset (S) 的递归算法。 递归算法的思想 递归算法指的是包含递归过程的算法，递归过程指的是调用自身的过程。 算法的有限性要求必须存在递归出口。 递归算法中通过对自身的调用，总能逐步逼近，直到满足递归出口。 习题 2-1 观察幂集的性质 习题 2-1 | P(S) | = | P(S-1) | * 2 | P(S) |=2n P(S) = P(S-a) ∪ {?P(S-a) ∪ a} /* S的幂集P(S)可以表示为S-a的幂集P(S-a)然后再并上 P(S-a)中任意一个集合并上元素a */ 习题 2-1 利用性质 | P(S) |=2n 集合S={ a , b , c } 习题 2-1 P(S) = P(S-a) ∪ {x ∪ a |x ∈ P(S-a)} 习题 2-1 算法 POWERSET(s.p) //计算集合s的幂集p PS1 [递归出口] IF s={} THEN (p←{?}. RETURN. ) PS2 [递归调用] x←anyelement(s). POWERSET(s-{x}.q). p = q; FOR ? (y∈q) p=p∪(y∪{x}) . ▌ 习题 2-3 证明对正整数 n ≥ 3，算法BS的元素比较次数 T（n）≤ 5n/3 - 2 数学归纳法证明 证明 n=3 时成立 假设3 ? n k 时都成立 证明 n= k时也成立 习题 2-3 证明（数学归纳法）： 当n=3时，T（3）=T（2）+T（1）+2=3 ?（5*3）/3 - 2=3； 命题成立。 假设nk时命题成立，即 T（i） ≤ 5i/3 – 2 i k 习题 2-4 算法 IBS(A,1,n.fmax,fmin) //计算最大最小元 IBS1 [初始化] fmin ← fmax ← A[1]. CREATS(S). S ? (1,n). IBS2 [迭代过程] WHILE (S ≠ NULL) （ （l,r）? S. IF r-l =0 THEN ( fmax ← max(fmax, A[r]). fmin ← min(fmin, A[r]). ) IF r – l =1 THEN (IF A[l] A[r] THEN ( fmax ← max(fmax, A[r]). fmin ← min(fmin, A[l]). ) ELSE ( fmax ← max(fmax, A[l]). fmin ← min(fmin, A[r]). ) ) mid ← S ? (1,mid). S ? (mid+1,n). ) ▌ * * 16 8 4 2 4 3 2 1 23 P(S)={{},{a},{b},{c},{a,b}…{a,b,c}} S={a,b,c} 22 P(S)={{},{a},{b},{a,b}} S={a,b} 24 21 P(S)={{},{a},{b},{c},{d}{ab},{bc}…{a,b,c,d}} S={a,b,c,d} P(S)={{},{a}} S={a} 幂集元素个数 集合元素个数 b c 1 1 0 b c 1 1 a 1