1.1 第 1 章─概论
1.1.1 练习题
1. 下列关于算法的说法中正确的有（ ）。Ⅰ.求解某一类问题的算法是唯一的
Ⅱ.算法必须在有限步操作之后停止
Ⅲ.算法的每一步操作必须是明确的，不能有歧义或含义模糊Ⅳ.算法执行后一定产生确定的结果
A. 1 个 B.2 个 C.3 个 D.4 个
2. T(n)表示当输入规模为 n 时的算法效率，以下算法效率最优的是（ ）。
A.T(n)= T(n-1)+1，T(1)=1 B.T(n)= 2n2
C.T(n)= T(n/2)+1，T(1)=1 D.T(n)=3nlog2n
3. 什么是算法？算法有哪些特征？
4. 判断一个大于 2 的正整数 n 是否为素数的方法有多种，给出两种算法，说明其中一种算法更好的理由。
5. 证明以下关系成立：
（1）10n2-2n=(n2)
（2）2n+1=(2n)
6. 证明 O(f(n))+O(g(n))=O(max{f(n)，g(n)}) 。
7. 有一个含 n（n>2）个整数的数组 a，判断其中是否存在出现次数超过所有元素一半的元素。
8. 一个字符串采用 string 对象存储，设计一个算法判断该字符串是否为回文。
9. 有一个整数序列，设计一个算法判断其中是否存在两个元素和恰好等于给定的整数 k。
10. 有两个整数序列，每个整数序列中所有元素均不相同。设计一个算法求它们的公共元素，要求不使用 STL 的集合算法。
11. 正整数 n（n>1）可以写成质数的乘积形式，称为整数的质因数分解。例如， 12=2*2*3，18=2*3*3，11=11。设计一个算法求 n 这样分解后各个质因数出现的次数，采用 vector 向量存放结果。
12. 有一个整数序列，所有元素均不相同，设计一个算法求相差最小的元素对的个数。如序列 4、1、2、3 的相差最小的元素对的个数是 3，其元素对是（1，2），（2，3），
（3，4）。
13. 有一个 map<string，int>容器，其中已经存放了较多元素。设计一个算法求出其中重复的 value 并且返回重复 value 的个数。
14. 重新做第 10 题，采用 map 容器存放最终结果。
15. 假设有一个含 n（n>1）个元素的 stack<int>栈容器 st，设计一个算法出栈从栈顶到栈底的第 k（1≤k≤n）个元素，其他栈元素不变。
1.1.2 练习题参考答案
1. 答：由于算法具有有穷性、确定性和输出性，因而Ⅱ、Ⅲ、Ⅳ正确，而解决某一类问题的算法不一定是唯一的。答案为 C。
2. 答：选项 A 的时间复杂度为 O(n)。选项 B 的时间复杂度为 O(n2)。选项 C 的时间复杂度为 O(log2n)。选项 D 的时间复杂度为 O(nlog2n)。答案为 C。
3. 答：算法是求解问题的一系列计算步骤。算法具有有限性、确定性、可行性、输入性和输出性 5 个重要特征。
4. 答：两种算法如下：
#include <stdio.h> #include <math.h>
bool isPrime1(int n) //方法 1
{ for (int i=2;i<n;i++)
if (n%i==0)
return false;
return true;
}
bool isPrime2(int n) //方法 2
{ for (int i=2;i<=(int)sqrt(n);i++)
if (n%i==0)
return false;
return true;
}
void main()
{ int n=5;
printf("%d,%d\n",isPrime1(n),isPrime2(n));
}
方法 1 的时间复杂度为 O(n)，方法 2 的时间复杂度为 n，所以方法 2 更好。
5. 答：（1）当 n 足够大时，(10n2-2n)/( n2)=10，所以 10n2-2n=(n2)。
（2）2n+1=2*2n=(2n)。
6. 证明：对于任意 f1(n)∈O(f(n)) ，存在正常数 c1 和正常数 n1，使得对所有 n≥n1， 有 f1(n)≤c1f(n) 。
类似地，对于任意 g1(n)∈O(g(n)) ，存在正常数 c2 和自然数 n2，使得对所有 n≥n2， 有 g1(n)≤c2g(n) 。
令 c3=max{c1，c2}，n3=max{n1，n2}，h(n)= max{f(n)，g(n)} 。则对所有的 n≥n3，有：
f1(n) +g1(n)≤c1f(n) + c2g(n)≤c3f(n)+c3g(n)=c3(f(n)+g(n))
≤c32max{f(n)，g(n)}=2c3h(n)=O(max{f(n)，g(n)})。
7. 解：先将 a 中元素递增排序，再求出现次数最多的次数 maxnum，最后判断是否满足条件。对应的程序如下：
#include <stdio.h> #include <algorithm> using namespace std;
bool solve(int a[],int n,int &x)
{
sort(a,a+n);
int maxnum=0; //递增排序
//出现次数最多的次数
int num=1;
int e=a[0];
for (int i=1;i<n;i++)
{ if (a[i]==e)
{ num++;
if (num>maxnum)
{ maxnum=num;
x=e;
}
}
else
{ e=a[i];
num=1;
}
}
if (maxnum>n/2)
return true;
else
return false;
}
void main()
{ int a[]={2,2,2,4,5,6,2};
int n=sizeof(a)/sizeof(a[0]);
int x;
if (solve(a,n,x))
printf("出现次数超过所有元素一半的元素为%d\n",x);
else
printf("不存在出现次数超过所有元素一半的元素\n");
}
上述程序的执行结果如图 1.1 所示。
图 1.1 程序执行结果
8. 解：采用前后字符判断方法，对应的程序如下：
#include <iostream> #include <string> using namespace std;
bool solve(string str) //判断字符串 str 是否为回文
{ int i=0,j=str.length()-1;
while (i<j)
{ if (str[i]!=str[j])
return false;
i++; j--;
}
return true;
}
void main()
{ cout << "求解结果" << endl;
string str="abcd";
cout << " " << str << (solve(str)?"是回文":"不是回文") << endl;
string str1="abba";
cout << " " << str1 << (solve(str1)?"是回文":"不是回文") << endl;
}
上述程序的执行结果如图 1.2 所示。
图 1.2 程序执行结果
9. 解：先将 a 中元素递增排序，然后从两端开始进行判断。对应的程序如下：
#include <stdio.h> #include <algorithm> using namespace std;
bool solve(int a[],int n,int k)
{ sort(a,a+n); //递增排序
int i=0, j=n-1;
while (i<j) //区间中存在两个或者以上元素
{ if (a[i]+a[j]==k)
return true;
else if (a[i]+a[j]<k)
i++;
else
j--;
}
return false;
}
void main()
{ int a[]={1,2,4,5,3};
int n=sizeof(a)/sizeof(a[0]);
printf("求解结果\n");
int k=9,i,j;
if (solve(a,n,k,i,j))
printf(" 存在: %d+%d=%d\n",a[i],a[j],k);
else
printf(" 不存在两个元素和为%d\n",k);
int k1=10;
if (solve(a,n,k1,i,j))
printf(" 存在: %d+%d=%d\n",a[i],a[j],k1);
else
printf(" 不存在两个元素和为%d\n",k1);
}
上述程序的执行结果如图 1.3 所示。
图 1.3 程序执行结果
10. 解：采用集合 set<int>存储整数序列，集合中元素默认是递增排序的，再采用二路归并算法求它们的交集。对应的程序如下：
#include <stdio.h> #include <set>
using namespace std;
void solve(set<int> s1,set<int> s2,set<int> &s3) //求交集 s3
{ set<int>::iterator it1,it2;
it1=s1.begin(); it2=s2.begin();
while (it1!=s1.end() && it2!=s2.end())
{ if (*it1==*it2)
{ s3.insert(*it1);
++it1; ++it2;
}
else if (*it1<*it2)
++it1;
else
++it2;
}
}
void dispset(set<int> s) //输出集合的元素
{ set<int>::iterator it;
for (it=s.begin();it!=s.end();++it)
printf("%d ",*it);
printf("\n");
}
void main()
{ int a[]={3,2,4,8};
int n=sizeof(a)/sizeof(a[0]);
set<int> s1(a,a+n);
int b[]={1,2,4,5,3};
int m=sizeof(b)/sizeof(b[0]);
set<int> s2(b,b+m);
set<int> s3;
solve(s1,s2,s3);
printf("求解结果\n");
printf(" s1: "); dispset(s1);
printf(" s2: "); dispset(s2);
printf(" s3: "); dispset(s3);
}
上述程序的执行结果如图 1.4 所示。
图 1.4 程序执行结果
11. 解：对于正整数 n，从 i=2 开始查找其质因数，ic 记录质因数 i 出现的次数，当找到这样质因数后，将（i，ic）作为一个元素插入到 vector 容器 v 中。最后输出 v。对应的算法如下：
#include <stdio.h> #include <vector> using namespace std;
struct NodeType //vector 向量元素类型
{ int p; //质因数
int pc; //质因数出现次数
};
void solve(int n,vector<NodeType> &v) //求 n 的质因数分解
{ int i=2;
int ic=0;
NodeType e;
do
{ if (n%i==0)
{ ic++;
n=n/i;
}
else
{ if (ic>0)
{ e.p=i;
e.pc=ic;
v.push_back(e);
}
ic=0;
i++;
}
} while (n>1 || ic!=0);
}
void disp(vector<NodeType> &v) //输出 v
{ vector<NodeType>::iterator it;
for (it=v.begin();it!=v.end();++it)
printf(" 质因数%d 出现%d 次\n",it->p,it->pc);
}
void main()
{ vector<NodeType> v;
int n=100;
printf("n=%d\n",n);
solve(n,v);
disp(v);
}
上述程序的执行结果如图 1.5 所示。
图 1.5 程序执行结果
12. 解：先递增排序，再求相邻元素差，比较求最小元素差，累计最小元素差的个数。对应的程序如下：
#include <iostream> #include <algorithm> #include <vector> using namespace std;
int solve(vector<int> &myv) //求 myv 中相差最小的元素对的个数
{ sort(myv.begin(),myv.end()); //递增排序
int ans=1;
int mindif=myv[1]-myv[0];
for (int i=2;i<myv.size();i++)
{ if (myv[i]-myv[i-1]<mindif)
{ ans=1;
mindif=myv[i]-myv[i-1];
}
else if (myv[i]-myv[i-1]==mindif)
ans++;
}
return ans;
}
void main()
{ int a[]={4,1,2,3};
int n=sizeof(a)/sizeof(a[0]);
vector<int> myv(a,a+n);
cout << "相差最小的元素对的个数: " << solve(myv) << endl;
}
上述程序的执行结果如图 1.6 所示。
图 1.6 程序执行结果
13. 解：对于 map<string，int>容器 mymap，设计另外一个 map<int，int>容器 tmap， 将前者的 value 作为后者的关键字。遍历 mymap，累计 tmap 中相同关键字的次数。一个参考程序及其输出结果如下：
#include <iostream> #include <map> #include <string> using namespace std; void main()
{ map<string,int> mymap;
mymap.insert(pair<string,int>("Mary",80));
mymap.insert(pair<string,int>("Smith",82));
mymap.insert(pair<string,int>("John",80));
mymap.insert(pair<string,int>("Lippman",95));
mymap.insert(pair<string,int>("Detial",82));
map<string,int>::iterator it;
map<int,int> tmap;
for (it=mymap.begin();it!=mymap.end();it++)
tmap[(*it).second]++;
map<int，int>::iterator it1;
cout << "求解结果" << endl;
for (it1=tmap.begin();it1!=tmap.end();it1++)
cout << " " << (*it1).first << ": " << (*it1).second << "次\n";
}
上述程序的执行结果如图 1.7 所示。
图 1.7 程序执行结果
14. 解：采用 map<int，int>容器 mymap 存放求解结果，第一个分量存放质因数，第二个分量存放质因数出现次数。对应的程序如下：
#include <stdio.h> #include <map>
using namespace std;
void solve(int n,map<int,int> &mymap) //求 n 的质因数分解
else
{ if (ic>0)
mymap[i]=ic;
ic=0;
i++;
}
} while (n>1 || ic!=0);
}
void disp(map<int,int> &mymap) //输出 mymap
{ map<int,int>::iterator it;
for (it=mymap.begin();it!=mymap.end();++it)
printf(" 质因数%d 出现%d 次\n",it->first,it->second);
}
void main()
{ map<int,int> mymap;
int n=12345;
printf("n=%d\n",n);
solve(n,mymap);
disp(mymap);
}
上述程序的执行结果如图 1.8 所示。
图 1.8 程序执行结果
15. 解：栈容器不能顺序遍历，为此创建一个临时 tmpst 栈，将 st 的 k 个元素出栈并进栈到 tmpst 中，再出栈 tmpst 一次得到第 k 个元素，最后将栈 tmpst 的所有元素出栈并进栈到 st 中。对应的程序如下：
#include <stdio.h> #include <stack> using namespace std;
int solve(stack<int> &st,int k) //出栈第 k 个元素
{ stack<int> tmpst;
int e;
for (int i=0;i<k;i++) //出栈 st 的 k 个元素并进 tmpst 栈
{ e=st.top();
st.pop();
tmpst.push(e);
}
e=tmpst.top(); //求第 k 个元素
tmpst.pop();
while (!tmpst.empty()) //将 tmpst 的所有元素出栈并进栈 st
{ st.push(tmpst.top());
tmpst.pop();
}
return e;
}
void disp(stack<int> &st) //出栈 st 的所有元素
{ while (!st.empty())
{ printf("%d ",st.top());
st.pop();
}
printf("\n");
}
void main()
{ stack<int> st;
printf("进栈元素 1,2,3,4\n");
st.push(1);
st.push(2);
st.push(3);
st.push(4);
int k=3;
int e=solve(st,k);
printf("出栈第%d 个元素是: %d\n",k,e);
printf("st 中元素出栈顺序: ");
disp(st);
}
上述程序的执行结果如图 1.9 所示。
图 1.9 程序执行结果
1.2 第 2 章─递归算法设计技术
1.2.1 练习题
1. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？
2. 分析以下程序的执行结果：
#include <stdio.h>
void f(int n,int &m)
{ if (n<1) return;
else
{ printf("调用f(%d,%d)前,n=%d,m=%d\n",n-1,m-1,n,m);
n--; m--;
f(n-1,m);
printf("调用f(%d,%d)后:n=%d,m=%d\n",n-1,m-1,n,m);
}
}
void main()
{ int n=4,m=4;
f(n,m);
}
3. 采用直接推导方法求解以下递归方程：
T(1)=1
T(n)=T(n-1)+n 当 n>1
4. 采用特征方程方法求解以下递归方程：
H(0)=0
H(1)=1
H(2)=2
H(n)=H(n-1)+9H(n-2)-9H(n-3) 当 n>2
5. 采用递归树方法求解以下递归方程：
T(1)=1
T(n)=4T(n/2)+n 当 n>1
6. 采用主方法求解以下题的递归方程。
T(n)=1 当 n=1
T(n)=4T(n/2)+n2 当 n>1
7. 分析求斐波那契 f(n)的时间复杂度。
8. 数列的首项 a1=0，后续奇数项和偶数项的计算公式分别为 a2n=a2n-1+2，a2n+1=a2n- 1+a2n-1，写出计算数列第 n 项的递归算法。
9. 对于一个采用字符数组存放的字符串 str，设计一个递归算法求其字符个数（长度）。
10. 对于一个采用字符数组存放的字符串 str，设计一个递归算法判断 str 是否为回文。
11. 对于不带头结点的单链表 L，设计一个递归算法正序输出所有结点值。
12. 对于不带头结点的单链表 L，设计一个递归算法逆序输出所有结点值。
13. 对于不带头结点的非空单链表 L，设计一个递归算法返回最大值结点的地址（假设这样的结点唯一）。
14. 对于不带头结点的单链表 L，设计一个递归算法返回第一个值为 x 的结点的地址，没有这样的结点时返回 NULL。
15. 对于不带头结点的单链表 L，设计一个递归算法删除第一个值为 x 的结点。
16. 假设二叉树采用二叉链存储结构存放，结点值为 int 类型，设计一个递归算法求二叉树 bt 中所有叶子结点值之和。
17. 假设二叉树采用二叉链存储结构存放，结点值为 int 类型，设计一个递归算法求二叉树 bt 中所有结点值大于等于 k 的结点个数。
18. 假设二叉树采用二叉链存储结构存放，所有结点值均不相同，设计一个递归算法求值为 x 的结点的层次（根结点的层次为 1），没有找到这样的结点时返回 0。
1.2.2 练习题参考答案
1. 答：一个 f 函数定义中直接调用 f 函数自己，称为直接递归。一个 f 函数定义中调用 g 函数，而 g 函数的定义中调用 f 函数，称为间接递归。消除递归一般要用栈实现。
2. 答：递归函数f(n，m)中，n是非引用参数，m是引用参数，所以递归函数的状态为
（n）。程序执行结果如下：
调用f(3,3)前,n=4,m=4 调用f(1,2)前,n=2,m=3 调用f(0,1)后,n=1,m=2 调用f(2,1)后,n=3,m=2
3. 解：求 T(n)的过程如下：
T(n)=T(n-1)+n=[T(n-2)+n-1)]+n=T(n-2)+n+(n-1)
=T(n-3)+n+(n-1)+(n-2)
=…
=T(1)+n+(n-1)+…+2
=n+(n-1)+ +…+2+1=n(n+1)/2=O(n2)。
4. 解：整数一个常系数的线性齐次递推式，用 xn 代替 H(n)，有：xn=xn-1+9xn-2-9xn-3， 两边同时除以 xn-3，得到：x3=x2+9x-9，即 x3-x2-9x+9=0。
x3-x2-9x+9=x(x2-9)-(x2-9)=(x-1)(x2-9)=(x-1)(x+3)(x-3)=0。得到 r1=1，r2=-3，r3=3
则递归方程的通解为：H(n)=c1+c2(-3)n+c33n 代入 H(0)=0，有 c1+c2+c3=0
代入 H(1)=1，有 c1-3c2+3c3=1
代入 H(2)=2，有 c1+9c2+9c3=2
( ‒ 1)n ‒ 1
n ‒ 1 1
求出：c1=-1/4，c2=-1/12，c3=1/3，H(n)=c1+c2(-3)n+c33n=( 4 + 1)3
‒ 4。
5. 解：构造的递归树如图 1.10 所示，第 1 层的问题规模为 n，第 2 的层的子问题的问题规模为 n/2，依此类推，当展开到第 k+1 层，其规模为 n/2k=1，所以递归树的高度为log2n+1。
第1层有1个结点，其时间为n，第2层有4个结点，其时间为4(n/2)=2n，依次类推，第k 层有4k-1个结点，每个子问题规模为n/2k-1，其时间为4k-1(n/2k-1)=2k-1n。叶子结点的个数为n 个，其时间为n。将递归树每一层的时间加起来，可得：
T(n)=n+2n+…+ 2k-1n+…+n≈???? ∗ 2log2n=O(n2)。
(n/2)
n n
(n/2) (n/2) (n/2) 2n
高度h为log 2n+1
(n/22)
(n/22)
(n/22)
(n/22)
22n
… … … …
1 1 1 1 n
图 1.10 一棵递归树
6. 解：采用主方法求解，这里 a=4，b=2，f(n)=n2。
logba log24 2
因此，????
logba
=????
2
=n ，它与 f(n)一样大，满足主定理中的情况（2），所以 T(n)=O(
???? log2n)=O(n log2n)。
7. 解：设求斐波那契 f(n)的时间为 T(n)，有以下递推式：
T(1)=T(2)
T(n)=T(n-1)+T(n-2)+1 当 n>2
其中，T(n)式中加 1 表示一次加法运算的时间。
不妨先求 T1(1)=T1(2)=1，T1(n)=T1(n-1)+T1(n-2)，按《教程》例 2.14 的方法可以求
出：
1 1
5 n
1 1
5 n
1 1
5 n
T1(n)=
≈
=
1 1
5 n
所以 T(n)=T1(n)+1≈
+1=O(φn)，其中 φ= 。
8. 解：设 f(m)计算数列第 m 项值。
当 m 为偶数时，不妨设 m=2n，则 2n-1=m-1，所以有 f(m)=f(m-1)+2。
当 m 为奇数时，不妨设 m=2n+1，则 2n-1=m-2，2n=m-1，所以有 f(m)=f(m-2)+f(m-
1)-1。
对应的递归算法如下：
int f(int m)
{ if (m==1) return 0;
if (m%2==0)
return f(m-1)+2;
else
return f(m-2)+f(m-1)-1;
}
9. 解：设 f(str)返回字符串 str 的长度，其递归模型如下：
f(str)=0 当*str='\0'时
f(str)=f(str+1)+1 其他情况
对应的递归程序如下：
#include <iostream> using namespace std;
int Length(char *str) //求str的字符个数
{ if (*str=='\0')
return 0;
else
return Length(str+1)+1;
}
void main()
{ char str[]="abcd";
cout << str << "的长度: " << Length(str) << endl;
}
上述程序的执行结果如图 1.11 所示。
图 1.11 程序执行结果
10. 解：设 f(str，n)返回含 n 个字符的字符串 str 是否为回文，其递归模型如下：
f(str，n)=true 当 n=0 或者 n=1 时
f(str，n)=flase 当 str[0]≠str[n-1]时
f(str，n)=f(str+1，n-2) 其他情况
对应的递归算法如下： #include <stdio.h> #include <string.h>
bool isPal(char *str,int n) //str 回文判断算法
{ if (n==0 || n==1)
return true;
if (str[0]!=str[n-1])
return false;
return isPal(str+1,n-2);
}
void disp(char *str)
{ int n=strlen(str);
if (isPal(str,n))
printf(" %s是回文\n",str);
else
printf(" %s不是回文\n",str);
}
void main()
{ printf("求解结果\n");
disp("abcba");
disp("a");
disp("abc");
}
上述程序的执行结果如图 1.12 所示。
图 1.12 程序执行结果
11. 解：设 f(L)正序输出单链表 L 的所有结点值，其递归模型如下：
f(L) ≡ 不做任何事情 当 L=NULL f(L) ≡ 输出 L->data; f(L->next); 当 L≠NULL 时对应的递归程序如下：
#include "LinkList.cpp" //包含单链表的基本运算算法
void dispLink(LinkNode *L) //正序输出所有结点值
{ if (L==NULL) return;
else
{ printf("%d ",L->data);
dispLink(L->next);
}
}
void main()
{ int a[]={1,2,5,2,3,2};
int n=sizeof(a)/sizeof(a[0]);
LinkNode *L;
CreateList(L,a,n); //由a[0..n-1]创建不带头结点的单链表
printf("正向L: ");
dispLink(L); printf("\n");
Release(L); //销毁单链表
}
上述程序的执行结果如图 1.13 所示。
图 1.13 程序执行结果
12. 解：设 f(L)逆序输出单链表 L 的所有结点值，其递归模型如下：
f(L) ≡ 不做任何事情 当 L=NULL f(L) ≡ f(L->next); 输出 L->data 当 L≠NULL 时对应的递归程序如下：
#include "LinkList.cpp" //包含单链表的基本运算算法
void Revdisp(LinkNode *L) //逆序输出所有结点值
{ if (L==NULL) return;
else
{ Revdisp(L->next);
printf("%d ",L->data);
}
}
void main()
{ int a[]={1,2,5,2,3,2};
int n=sizeof(a)/sizeof(a[0]);
LinkNode *L;
CreateList(L,a,n);
printf("反向L: ");
Revdisp(L); printf("\n");
Release(L);
}
上述程序的执行结果如图 1.14 所示。
图 1.14 程序执行结果
13. 解：设 f(L)返回单链表 L 中值最大结点的地址，其递归模型如下：
f(L) = L 当 L 只有一个结点时
f(L) = MAX{f(L->next)，L->data} 其他情况
对应的递归程序如下：
#include "LinkList.cpp" //包含单链表的基本运算算法
LinkNode *Maxnode(LinkNode *L) //返回最大值结点的地址
{ if (L->next==NULL)
return L; //只有一个结点时
else
{ LinkNode *maxp;
maxp=Maxnode(L->next);
if (L->data>maxp->data)
return L;
else
return maxp;
}
}
void main()
{ int a[]={1,2,5,2,3,2};
int n=sizeof(a)/sizeof(a[0]);
LinkNode *L,*p;
CreateList(L,a,n);
p=Maxnode(L);
printf("最大结点值: %d\n",p->data);
Release(L);
}
上述程序的执行结果如图 1.15 所示。
图 1.15 程序执行结果
14. 解：设 f(L，x)返回单链表 L 中第一个值为 x 的结点的地址，其递归模型如下：
f(L，x) = NULL 当 L=NULL 时
f(L，x) = L 当 L≠NULL 且 L->data=x 时
f(L，x) = f(L->next，x) 其他情况
对应的递归程序如下：
#include "LinkList.cpp" //包含单链表的基本运算算法
LinkNode *Firstxnode(LinkNode *L,int x) //返回第一个值为 x 的结点的地址
{ if (L==NULL) return NULL;
if (L->data==x)
return L;
else
return Firstxnode(L->next,x);
}
void main()
{ int a[]={1,2,5,2,3,2};
int n=sizeof(a)/sizeof(a[0]);
LinkNode *L,*p;
CreateList(L,a,n);
int x=2;
p=Firstxnode(L,x);
printf("结点值: %d\n",p->data);
Release(L);
}
上述程序的执行结果如图 1.16 所示。
图 1.16 程序执行结果
15. 解：设 f(L，x)删除单链表 L 中第一个值为 x 的结点，其递归模型如下：
f(L，x) ≡ 不做任何事情 当 L=NULL
f(L，x) ≡ 删除 L 结点，L=L->next 当 L≠NULL 且 L->data=x f(L，x) ≡ f(L->next，x) 其他情况
对应的递归程序如下：
#include "LinkList.cpp" //包含单链表的基本运算算法
void Delfirstx(LinkNode *&L,int x) //删除单链表 L 中第一个值为 x 的结点
{ if (L==NULL) return;
if (L->data==x)
{ LinkNode *p=L;
L=L->next;
free(p);
}
else
Delfirstx(L->next,x);
}
void main()
{ int a[]={1,2,5,2,3,2};
int n=sizeof(a)/sizeof(a[0]);
LinkNode *L;
CreateList(L,a,n);
printf("删除前L: "); DispList(L);
int x=2;
printf("删除第一个值为%d的结点\n",x);
Delfirstx(L,x);
printf("删除后L: "); DispList(L);
Release(L);
}
上述程序的执行结果如图 1.17 所示。
图 1.17 程序执行结果
16. 解：设 f(bt)返回二叉树 bt 中所有叶子结点值之和，其递归模型如下：
f(bt)=0 当 bt=NULL
f(bt)=bt->data 当 bt≠NULL 且 bt 结点为叶子结点
f(bt)=f(bt->lchild)+f(bt->rchild) 其他情况
对应的递归程序如下：
#include "Btree.cpp" //包含二叉树的基本运算算法
int LeafSum(BTNode *bt) //二叉树 bt 中所有叶子结点值之和
{ if (bt==NULL) return 0;
if (bt->lchild==NULL && bt->rchild==NULL)
return bt->data;
int lsum=LeafSum(bt->lchild);
int rsum=LeafSum(bt->rchild);
return lsum+rsum;
}
void main()
{ BTNode *bt;
Int a[]={5,2,3,4,1,6}; //先序序列
Int b[]={2,3,5,1,4,6}; //中序序列
int n=sizeof(a)/sizeof(a[0]);
bt=CreateBTree(a,b,n); //由a和b构造二叉链bt
printf("二叉树bt:"); DispBTree(bt); printf("\n");
printf("所有叶子结点值之和: %d\n",LeafSum(bt));
DestroyBTree(bt); //销毁树bt
}
上述程序的执行结果如图 1.18 所示。
图 1.18 程序执行结果
17. 解：设 f(bt，k)返回二叉树 bt 中所有结点值大于等于 k 的结点个数&