第1章 绪论
1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。
1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。
1.3 设有数据结构(D,R)，其中
，，
试按图论中图的画法惯例画出其逻辑结构图。
解：
1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。
解：
ADT Complex{
数据对象：D={r,i|r,i为实数}
数据关系：R={<r,i>}
基本操作：
InitComplex(&C,re,im)
操作结果：构造一个复数C，其实部和虚部分别为re和im
DestroyCmoplex(&C)
操作结果：销毁复数C
Get(C,k,&e)
操作结果：用e返回复数C的第k元的值
Put(&C,k,e)
操作结果：改变复数C的第k元的值为e
IsAscending(C)
操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0
IsDescending(C)
操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0
Max(C,&e)
操作结果：用e返回复数C的两个元素中值较大的一个
Min(C,&e)
操作结果：用e返回复数C的两个元素中值较小的一个
}ADT Complex
ADT RationalNumber{
数据对象：D={s,m|s,m为自然数，且m不为0}
数据关系：R={<s,m>}
基本操作：
InitRationalNumber(&R,s,m)
操作结果：构造一个有理数R，其分子和分母分别为s和m
DestroyRationalNumber(&R)
操作结果：销毁有理数R
Get(R,k,&e)
操作结果：用e返回有理数R的第k元的值
Put(&R,k,e)
操作结果：改变有理数R的第k元的值为e
IsAscending(R)
操作结果：若有理数R的两个元素按升序排列，则返回1，否则返回0
IsDescending(R)
操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0
Max(R,&e)
操作结果：用e返回有理数R的两个元素中值较大的一个
Min(R,&e)
操作结果：用e返回有理数R的两个元素中值较小的一个
}ADT RationalNumber
1.5 试画出与下列程序段等价的框图。
(1) product=1; i=1;
while(i<=n){
product *= i;
i++;
}
(2) i=0;
do {
i++;
} while((i!=n) && (a[i]!=x));
(3) switch {
case x<y: z=y-x; break;
case x=y: z=abs(x*y); break;
default: z=(x-y)/abs(x)*abs(y);
}
1.6 在程序设计中，常用下列三种不同的出错处理方式：
(1) 用exit语句终止执行并报告错误；
(2) 以函数的返回值区别正确返回或错误返回；
(3) 设置一个整型变量的函数参数以区别正确返回或某种错误返回。
试讨论这三种方法各自的优缺点。
解：(1)exit常用于异常错误处理，它可以强行中断程序的执行，返回操作系统。
(2)以函数的返回值判断正确与否常用于子程序的测试，便于实现程序的局部控制。
(3)用整型函数进行错误处理的优点是可以给出错误类型，便于迅速确定错误。
1.7 在程序设计中，可采用下列三种方法实现输出和输入：
(1) 通过scanf和printf语句；
(2) 通过函数的参数显式传递；
(3) 通过全局变量隐式传递。
试讨论这三种方法的优缺点。
解：(1)用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。
(2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。
(3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。
1.8 设n为正整数。试确定下列各程序段中前置以记号@的语句的频度：
(1) i=1; k=0;
while(i<=n-1){
@ k += 10*i;
i++;
}
(2) i=1; k=0;
do {
@ k += 10*i;
i++;
} while(i<=n-1);
(3) i=1; k=0;
while (i<=n-1) {
i++;
@ k += 10*i;
}
(4) k=0;
for(i=1; i<=n; i++) {
for(j=i; j<=n; j++)
@ k++;
}
(5) for(i=1; i<=n; i++) {
for(j=1; j<=i; j++) {
for(k=1; k<=j; k++)
@ x += delta;
}
(6) i=1; j=0;
while(i+j<=n) {
@ if(i>j) j++;
else i++;
}
(7) x=n; y=0; // n是不小于1的常数
while(x>=(y+1)*(y+1)) {
@ y++;
}
(8) x=91; y=100;
while(y>0) {
@ if(x>100) { x -= 10; y–; }
else x++;
}
解：(1) n-1
(2) n-1
(3) n-1
(4) n+(n-1)+(n-2)+…+1=
(5) 1+(1+2)+(1+2+3)+…+(1+2+3+…+n)=
=
=
(6) n
(7) 向下取整
(8) 1100
1.9 假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。
int Time(int n) {
count = 0; x=2;
while(x<n/2) {
x *= 2; count++;
}
return count;
}
解：
count=
1.11 已知有实现同一功能的两个算法，其时间复杂度分别为和，假设现实计算机可连续运算的时间为秒（100多天），又每秒可执行基本操作（根据这些操作来估算算法时间复杂度）次。试问在此条件下，这两个算法可解问题的规模（即n值的范围）各为多少？哪个算法更适宜？请说明理由。
解： n=40
n=16
则对于同样的循环次数n，在这个规模下，第二种算法所花费的代价要大得多。故在这个规模下，第一种算法更适宜。
1.12 设有以下三个函数：
，，
请判断以下断言正确与否：
(1) f(n)是O(g(n))
(2) h(n)是O(f(n))
(3) g(n)是O(h(n))
(4) h(n)是O(n3.5)
(5) h(n)是O(nlogn)
解：(1)对 (2)错 (3)错 (4)对 (5)错
1.13 试设定若干n值，比较两函数和的增长趋势，并确定n在什么范围内，函数的值大于的值。
解：的增长趋势快。但在n较小的时候，的值较大。
当n>438时，
1.14 判断下列各对函数和，当时，哪个函数增长更快？
(1) ，
(2) ，
(3) ，
(4) ，
解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快
1.15 试用数学归纳法证明：
(1)
(2)
(3)
(4)
1.16 试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值
解：
int max3(int x,int y,int z)
{
if(x>y)
if(x>z) return x;
else return z;
else
if(y>z) return y;
else return z;
}
1.17 已知k阶斐波那契序列的定义为
，，…，，；
，
试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。
解：k>0为阶数，n为数列的第n项
int Fibonacci(int k,int n)
{
if(k<1) exit(OVERFLOW);
int *p,x;
p=new int[k+1];
if(!p) exit(OVERFLOW);
int i,j;
for(i=0;i<k+1;i++){
if(i<k-1) p[i]=0;
else p[i]=1;
}
for(i=k+1;i<n+1;i++){
x=p[0];
for(j=0;j<k;j++) p[j]=p[j+1];
p[k]=2*p[k-1]-x;
}
return p[k];
}
1.18 假设有A，B，C，D，E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为
|
项目名称 |
性别 |
校名 |
成绩 |
得分 |
编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。
解：
typedef enum{A,B,C,D,E} SchoolName;
typedef enum{Female,Male} SexType;
typedef struct{
char event[3]; //项目
SexType sex;
SchoolName school;
int score;
} Component;
typedef struct{
int MaleSum; //男团总分
int FemaleSum; //女团总分
int TotalSum; //团体总分
} Sum;
Sum SumScore(SchoolName sn,Component a[],int n)
{
Sum temp;
temp.MaleSum=0;
temp.FemaleSum=0;
temp.TotalSum=0;
int i;
for(i=0;i<n;i++){
if(a[i].school==sn){
if(a[i].sex==Male) temp.MaleSum+=a[i].score;
if(a[i].sex==Female) temp.FemaleSum+=a[i].score;
}
}
temp.TotalSum=temp.MaleSum+temp.FemaleSum;
return temp;
}
1.19 试编写算法，计算的值并存入数组a[0..arrsize-1]的第i-1个分量中(i=1,2,…,n)。假设计算机中允许的整数最大值为maxint，则当n>arrsize或对某个，使时，应按出错处理。注意选择你认为较好的出错处理方法。
解：
#include<iostream.h>
#include<stdlib.h>
#define MAXINT 65535
#define ArrSize 100
int fun(int i);
int main()
{
int i,k;
int a[ArrSize];
cout<<“Enter k:”;
cin>>k;
if(k>ArrSize-1) exit(0);
for(i=0;i<=k;i++){
if(i==0) a[i]=1;
else{
if(2*i*a[i-1]>MAXINT) exit(0);
else a[i]=2*i*a[i-1];
}
}
for(i=0;i<=k;i++){
if(a[i]>MAXINT) exit(0);
else cout<<a[i]<<” “;
}
return 0;
}
1.20 试编写算法求一元多项式的值的值，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为，和，输出为。
解：
#include<iostream.h>
#include<stdlib.h>
#define N 10
double polynomail(int a[],int i,double x,int n);
int main()
{
double x;
int n,i;
int a[N];
cout<<“输入变量的值x:”;
cin>>x;
cout<<“输入多项式的阶次n:”;
cin>>n;
if(n>N-1) exit(0);
cout<<“输入多项式的系数a[0]–a[n]:”;
for(i=0;i<=n;i++) cin>>a[i];
cout<<“The polynomail value is “<<polynomail(a,n,x,n)<<endl;
return 0;
}
double polynomail(int a[],int i,double x,int n)
{
if(i>0) return a[n-i]+polynomail(a,i-1,x,n)*x;
else return a[n];
}
本算法的时间复杂度为o(n)。
第2章 线性表
2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。
解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。
2.2 填空题。
解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。
(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。
(3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。
(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。
2.3 在什么情况下用顺序表比链表好？
解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。
2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。
解：
2.5 画出执行下列各行语句后各指针及链表的示意图。
L=(LinkList)malloc(sizeof(LNode)); P=L;
for(i=1;i<=4;i++){
P->next=(LinkList)malloc(sizeof(LNode));
P=P->next; P->data=i*2-1;
}
P->next=NULL;
for(i=4;i>=1;i–) Ins_LinkList(L,i+1,i*2);
for(i=1;i<=3;i++) Del_LinkList(L,i);
解：
2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a. 在P结点后插入S结点的语句序列是__________________。
b. 在P结点前插入S结点的语句序列是__________________。
c. 在表首插入S结点的语句序列是__________________。
d. 在表尾插入S结点的语句序列是__________________。
(1) P->next=S;
(2) P->next=P->next->next;
(3) P->next=S->next;
(4) S->next=P->next;
(5) S->next=L;
(6) S->next=NULL;
(7) Q=P;
(8) while(P->next!=Q) P=P->next;
(9) while(P->next!=NULL) P=P->next;
(10) P=Q;
(11) P=L;
(12) L=S;
(13) L=P;
解：a. (4) (1)
b. (7) (11) (8) (4) (1)
c. (5) (12)
d. (9) (1) (6)
2.7 已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a. 删除P结点的直接后继结点的语句序列是____________________。
b. 删除P结点的直接前驱结点的语句序列是____________________。
c. 删除P结点的语句序列是____________________。
d. 删除首元结点的语句序列是____________________。
e. 删除尾元结点的语句序列是____________________。
(1) P=P->next;
(2) P->next=P;
(3) P->next=P->next->next;
(4) P=P->next->next;
(5) while(P!=NULL) P=P->next;
(6) while(Q->next!=NULL) { P=Q; Q=Q->next; }
(7) while(P->next!=Q) P=P->next;
(8) while(P->next->next!=Q) P=P->next;
(9) while(P->next->next!=NULL) P=P->next;
(10) Q=P;
(11) Q=P->next;
(12) P=L;
(13) L=L->next;
(14) free(Q);
解：a. (11) (3) (14)
b. (10) (12) (8) (3) (14)
c. (10) (12) (7) (3) (14)
d. (12) (11) (3) (14)
e. (9) (11) (3) (14)
2.8 已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。
a. 在P结点后插入S结点的语句序列是_______________________。
b. 在P结点前插入S结点的语句序列是_______________________。
c. 删除P结点的直接后继结点的语句序列是_______________________。
d. 删除P结点的直接前驱结点的语句序列是_______________________。
e. 删除P结点的语句序列是_______________________。
(1) P->next=P->next->next;
(2) P->priou=P->priou->priou;
(3) P->next=S;
(4) P->priou=S;
(5) S->next=P;
(6) S->priou=P;
(7) S->next=P->next;
(8) S->priou=P->priou;
(9) P->priou->next=P->next;
(10) P->priou->next=P;
(11) P->next->priou=P;
(12) P->next->priou=S;
(13) P->priou->next=S;
(14) P->next->priou=P->priou;
(15) Q=P->next;
(16) Q=P->priou;
(17) free(P);
(18) free(Q);
解：a. (7) (3) (6) (12)
b. (8) (4) (5) (13)
c. (15) (1) (11) (18)
d. (16) (2) (10) (18)
e. (14) (9) (17)
2.9 简述以下算法的功能。
(1) Status A(LinkedList L) { //L是无表头结点的单链表
if(L && L->next) {
Q=L; L=L->next; P=L;
while(P->next) P=P->next;
P->next=Q; Q->next=NULL;
}
return OK;
}
(2) void BB(LNode *s, LNode *q) {
p=s;
while(p->next!=q) p=p->next;
p->next =s;
}
void AA(LNode *pa, LNode *pb) {
//pa和pb分别指向单循环链表中的两个结点
BB(pa,pb);
BB(pb,pa);
}
解：(1) 如果L的长度不小于2，将L的首元结点变成尾元结点。
(2) 将单循环链表拆成两个单循环链表。
2.10 指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。
Status DeleteK(SqList &a,int i,int k)
{
//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素
if(i<1||k<0||i+k>a.length) return INFEASIBLE;//参数不合法
else {
for(count=1;count<k;count++){
//删除第一个元素
for(j=a.length;j>=i+1;j–) a.elem[j-i]=a.elem[j];
a.length–;
}
return OK;
}
解：
Status DeleteK(SqList &a,int i,int k)
{
//从顺序存储结构的线性表a中删除第i个元素起的k个元素
//注意i的编号从0开始
int j;
if(i<0||i>a.length-1||k<0||k>a.length-i) return INFEASIBLE;
for(j=0;j<=k;j++)
a.elem[j+i]=a.elem[j+i+k];
a.length=a.length-k;
return OK;
}
2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
解：
Status InsertOrderList(SqList &va,ElemType x)
{
//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法
int i;
if(va.length==va.listsize)return(OVERFLOW);
for(i=va.length;i>0,x<va.elem[i-1];i–)
va.elem[i]=va.elem[i-1];
va.elem[i]=x;
va.length++;
return OK;
}
2.12 设和均为顺序表，和分别为和中除去最大共同前缀后的子表。若空表，则；若=空表，而空表，或者两者均不为空表，且的首元小于的首元，则；否则。试写一个比较，大小的算法。
解：
Status CompareOrderList(SqList &A,SqList &B)
{
int i,k,j;
k=A.length>B.length?A.length:B.length;
for(i=0;i<k;i++){
if(A.elem[i]>B.elem[i]) j=1;
if(A.elem[i]<B.elem[i]) j=-1;
}
if(A.length>k) j=1;
if(B.length>k) j=-1;
if(A.length==B.length) j=0;
return j;
}
2.13 试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x);
解：
int LocateElem_L(LinkList &L,ElemType x)
{
int i=0;
LinkList p=L;
while(p&&p->data!=x){
p=p->next;
i++;
}
if(!p) return 0;
else return i;
}
2.14 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。
解：
//返回单链表的长度
int ListLength_L(LinkList &L)
{
int i=0;
LinkList p=L;
if(p) p=p-next;
while(p){
p=p->next;
i++;
}
return i;
}
2.15 已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。
解：
void MergeList_L(LinkList &ha,LinkList &hb,LinkList &hc)
{
LinkList pa,pb;
pa=ha;
pb=hb;
while(pa->next&&pb->next){
pa=pa->next;
pb=pb->next;
}
if(!pa->next){
hc=hb;
while(pb->next) pb=pb->next;
pb->next=ha->next;
}
else{
hc=ha;
while(pa->next) pa=pa->next;
pa->next=hb->next;
}
}
2.16 已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法是否正确？若有错，请改正之。
Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len)
{
if(i<0||j<0||len<0) return INFEASIBLE;
p=la; k=1;
while(k<i){ p=p->next; k++; }
q=p;
while(k<=len){ q=q->next; k++; }
s=lb; k=1;
while(k<j){ s=s->next; k++; }
s->next=p; q->next=s->next;
return OK;
}
解：
Status DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len)
{
LinkList p,q,s,prev=NULL;
int k=1;
if(i<0||j<0||len<0) return INFEASIBLE;
// 在la表中查找第i个结点
p=la;
while(p&&k<i){
prev=p;
p=p->next;
k++;
}
if(!p)return INFEASIBLE;
// 在la表中查找第i+len-1个结点
q=p; k=1;
while(q&&k<len){
q=p->next;
k++;
}
if(!q)return INFEASIBLE;
// 完成删除，注意，i=1的情况需要特殊处理
if(!prev) la=q->next;
else prev->next=q->next;
// 将从la中删除的结点插入到lb中
if(j=1){
q->next=lb;
lb=p;
}
else{
s=lb; k=1;
while(s&&k<j-1){
s=s->next;
k++;
}
if(!s)return INFEASIBLE;
q->next=s->next;
s->next=p; //完成插入
}
return OK;
}
2.17 试写一算法，在无头结点的动态单链表上实现线性表操作Insert(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。
解：
Status Insert(LinkList &L,int i,int b)//在无头结点链表L的第i个元素之前插入元素b
{
p=L;q=(LinkList*)malloc(sizeof(LNode));
q.data=b;
if(i==1)
{
q.next=p;L=q; //插入在链表头部
}
else
{
while(–i>1) p=p->next;
q->next=p->next;p->next=q; //插入在第i个元素的位置
}
}//Insert
2.18试写一算法，实现线性表操作Delete(L,i)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。
解：
Status Delete(LinkList &L,int i)//在无头结点链表L中删除第i个元素
{
if(i==1) L=L->next; //删除第一个元素
else
{
p=L;
while(–i>1) p=p->next;
p->next=p->next->next; //删除第i个元素
}
}//Delete
2.19 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。
解：
Status ListDelete_L(LinkList &L,ElemType mink,ElemType maxk)
{
LinkList p,q,prev=NULL;
if(mink>maxk)return ERROR;
p=L;
prev=p;
p=p->next;
while(p&&p->data<maxk){
if(p->data<=mink){
prev=p;
p=p->next;
}
else{
prev->next=p->next;
q=p;
p=p->next;
free(q);
}
}
return OK;
}
2.20 同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度。
解：
void ListDelete_LSameNode(LinkList &L)
{
LinkList p,q,prev;
p=L;
prev=p;
p=p->next;
while(p){
prev=p;
p=p->next;
if(p&&p->data==prev->data){
prev->next=p->next;
q=p;
p=p->next;
free(q);
}
}
}
2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表逆置为。
解：
// 顺序表的逆置
Status ListOppose_Sq(SqList &L)
{
int i;
ElemType x;
for(i=0;i<L.length/2;i++){
x=L.elem[i];
L.elem[i]=L.elem[L.length-1-i];
L.elem[L.length-1-i]=x;
}
return OK;
}
2.22 试写一算法，对单链表实现就地逆置。
解：
// 带头结点的单链表的逆置
Status ListOppose_L(LinkList &L)
{
LinkList p,q;
p=L;
p=p->next;
L->next=NULL;
while(p){
q=p;
p=p->next;
q->next=L->next;
L->next=q;
}
return OK;
}
2.23 设线性表，，试写一个按下列规则合并A，B为线性表C的算法，即使得
当时；
当时。
线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。
解：
// 将合并后的结果放在C表中，并删除B表
Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C)
{
LinkList pa,pb,qa,qb;
pa=A->next;
pb=B->next;
C=A;
while(pa&&pb){
qa=pa; qb=pb;
pa=pa->next; pb=pb->next;
qb->next=qa->next;
qa->next=qb;
}
if(!pa)qb->next=pb;
pb=B;
free(pb);
return OK;
}
2.24 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。
解：
// 将合并逆置后的结果放在C表中，并删除B表
Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)
{
LinkList pa,pb,qa,qb;
pa=A;
pb=B;
qa=pa; // 保存pa的前驱指针
qb=pb; // 保存pb的前驱指针
pa=pa->next;
pb=pb->next;
A->next=NULL;
C=A;
while(pa&&pb){
if(pa->data<pb->data){
qa=pa;
pa=pa->next;
qa->next=A->next; //将当前最小结点插入A表表头
A->next=qa;
}
else{
qb=pb;
pb=pb->next;
qb->next=A->next; //将当前最小结点插入A表表头
A->next=qb;
}
}
while(pa){
qa=pa;
pa=pa->next;
qa->next=A->next;
A->next=qa;
}
while(pb){
qb=pb;
pb=pb->next;
qb->next=A->next;
A->next=qb;
}
pb=B;
free(pb);
return OK;
}
2.25 假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素有依值递增有序排列。试对顺序表编写求C的算法。
解：
// 将A、B求交后的结果放在C表中
Status ListCross_Sq(SqList &A,SqList &B,SqList &C)
{
int i=0,j=0,k=0;
while(i<A.length && j<B.length){
if(A.elem[i]<B.elem[j]) i++;
else
if(A.elem[i]>B.elem[j]) j++;
else{
ListInsert_Sq(C,k,A.elem[i]);
i++;
k++;
}
}
return OK;
}
2.26 要求同2.25题。试对单链表编写求C的算法。
解：
// 将A、B求交后的结果放在C表中，并删除B表
Status ListCross_L(LinkList &A,LinkList &B,LinkList &C)
{
LinkList pa,pb,qa,qb,pt;
pa=A;
pb=B;
qa=pa; // 保存pa的前驱指针
qb=pb; // 保存pb的前驱指针
pa=pa->next;
pb=pb->next;
C=A;
while(pa&&pb){
if(pa->data<pb->data){
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt);
}
else
if(pa->data>pb->data){
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt);
}
else{
qa=pa;
pa=pa->next;
}
}
while(pa){
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt);
}
while(pb){
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt);
}
pb=B;
free(pb);
return OK;
}
2.27 对2.25题的条件作以下两点修改，对顺序表重新编写求得表C的算法。
(1) 假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；
(2) 利用A表空间存放表C。
解：
(1)
// A、B求交，然后删除相同元素，将结果放在C表中
Status ListCrossDelSame_Sq(SqList &A,SqList &B,SqList &C)
{
int i=0,j=0,k=0;
while(i<A.length && j<B.length){
if(A.elem[i]<B.elem[j]) i++;
else
if(A.elem[i]>B.elem[j]) j++;
else{
if(C.length==0){
ListInsert_Sq(C,k,A.elem[i]);
k++;
}
else
if(C.elem[C.length-1]!=A.elem[i]){
ListInsert_Sq(C,k,A.elem[i]);
k++;
}
i++;
}
}
return OK;
}
(2)
// A、B求交，然后删除相同元素，将结果放在A表中
Status ListCrossDelSame_Sq(SqList &A,SqList &B)
{
int i=0,j=0,k=0;
while(i<A.length && j<B.length){
if(A.elem[i]<B.elem[j]) i++;
else
if(A.elem[i]>B.elem[j]) j++;
else{
if(k==0){
A.elem[k]=A.elem[i];
k++;
}
else
if(A.elem[k]!=A.elem[i]){
A.elem[k]=A.elem[i];
k++;
}
i++;
}
}
A.length=k;
return OK;
}
2.28 对2.25题的条件作以下两点修改，对单链表重新编写求得表C的算法。
(1) 假设在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；
(2) 利用原表（A表或B表）中的结点构成表C，并释放A表中的无用结点空间。
解：
(1)
// A、B求交，结果放在C表中，并删除相同元素
Status ListCrossDelSame_L(LinkList &A,LinkList &B,LinkList &C)
{
LinkList pa,pb,qa,qb,pt;
pa=A;
pb=B;
qa=pa; // 保存pa的前驱指针
qb=pb; // 保存pb的前驱指针
pa=pa->next;
pb=pb->next;
C=A;
while(pa&&pb){
if(pa->data<pb->data){
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt);
}
else
if(pa->data>pb->data){
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt);
}
else{
if(pa->data==qa->data){
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt);
}
else{
qa=pa;
pa=pa->next;
}
}
}
while(pa){
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt);
}
while(pb){
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt);
}
pb=B;
free(pb);
return OK;
}
(2)
// A、B求交，结果放在A表中，并删除相同元素
Status ListCrossDelSame_L(LinkList &A,LinkList &B)
{
LinkList pa,pb,qa,qb,pt;
pa=A;
pb=B;
qa=pa; // 保存pa的前驱指针
qb=pb; // 保存pb的前驱指针
pa=pa->next;
pb=pb->next;
while(pa&&pb){
if(pa->data<pb->data){
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt);
}
else
if(pa->data>pb->data){
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt);
}
else{
if(pa->data==qa->data){
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt);
}
else{
qa=pa;
pa=pa->next;
}
}
}
while(pa){
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt);
}
while(pb){
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt);
}
pb=B;
free(pb);
return OK;
}
2.29 已知A，B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。
解：
// 在A中删除既在B中出现又在C中出现的元素，结果放在D中
Status ListUnion_Sq(SqList &D,SqList &A,SqList &B,SqList &C)
{
SqList Temp;
InitList_Sq(Temp);
ListCross_L(B,C,Temp);
ListMinus_L(A,Temp,D);
}
2.30 要求同2.29题。试对单链表编写算法，请释放A表中的无用结点空间。
解：
// 在A中删除既在B中出现又在C中出现的元素，并释放B、C
Status ListUnion_L(LinkList &A,LinkList &B,LinkList &C)
{
ListCross_L(B,C);
ListMinus_L(A,B);
}
// 求集合A-B，结果放在A表中，并删除B表
Status ListMinus_L(LinkList &A,LinkList &B)
{
LinkList pa,pb,qa,qb,pt;
pa=A;
pb=B;
qa=pa; // 保存pa的前驱指针
qb=pb; // 保存pb的前驱指针
pa=pa->next;
pb=pb->next;
while(pa&&pb){
if(pb->data<pa->data){
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt);
}
else
if(pb->data>pa->data){
qa=pa;
pa=pa->next;
}
else{
pt=pa;
pa=pa->next;
qa->next=pa;
free(pt);
}
}
while(pb){
pt=pb;
pb=pb->next;
qb->next=pb;
free(pt);
}
pb=B;
free(pb);
return OK;
}
2.31 假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。
解：
// 在单循环链表S中删除S的前驱结点
Status ListDelete_CL(LinkList &S)
{
LinkList p,q;
if(S==S->next)return ERROR;
q=S;
p=S->next;
while(p->next!=S){
q=p;
p=p->next;
}
q->next=p->next;
free(p);
return OK;
}
2.32 已知有一个单向循环链表，其每个结点中含三个域：pre，data和next，其中data为数据域，next为指向后继结点的指针域，pre也为指针域，但它的值为空，试编写算法将此单向循环链表改为双向循环链表，即使pre成为指向前驱结点的指针域。
解：
// 建立一个空的循环链表
Status InitList_DL(DuLinkList &L)
{
L=(DuLinkList)malloc(sizeof(DuLNode));
if(!L) exit(OVERFLOW);
L->pre=NULL;
L->next=L;
return OK;
}
// 向循环链表中插入一个结点
Status ListInsert_DL(DuLinkList &L,ElemType e)
{
DuLinkList p;
p=(DuLinkList)malloc(sizeof(DuLNode));
if(!p) return ERROR;
p->data=e;
p->next=L->next;
L->next=p;
return OK;
}
// 将单循环链表改成双向链表
Status ListCirToDu(DuLinkList &L)
{
DuLinkList p,q;
q=L;
p=L->next;
while(p!=L){
p->pre=q;
q=p;
p=p->next;
}
if(p==L) p->pre=q;
return OK;
}
2.33 已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其他字符），试编写算法将该线性表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。
解：
// 将单链表L划分成3个单循环链表
Status ListDivideInto3CL(LinkList &L,LinkList &s1,LinkList &s2,LinkList &s3)
{
LinkList p,q,pt1,pt2,pt3;
p=L->next;
pt1=s1;
pt2=s2;
pt3=s3;
while(p){
if(p->data>=’0′ && p->data<=’9′){
q=p;
p=p->next;
q->next=pt1->next;
pt1->next=q;
pt1=pt1->next;
}
else
if((p->data>=’A’ && p->data<=’Z’) ||
(p->data>=’a’ && p->data<=’z’)){
q=p;
p=p->next;
q->next=pt2->next;
pt2->next=q;
pt2=pt2->next;
}
else{
q=p;
p=p->next;
q->next=pt3->next;
pt3->next=q;
pt3=pt3->next;
}
}
q=L;
free(q);
return OK;
}
在2.34至2.36题中，“异或指针双向链表”类型XorLinkedList和指针异或函数XorP定义为：
typedef struct XorNode {
char data;
struct XorNode *LRPtr;
} XorNode, *XorPointer;
typede struct { //无头结点的异或指针双向链表
XorPointer Left, Right; //分别指向链表的左侧和右端
} XorLinkedList;
XorPointer XorP(XorPointer p, XorPointer q);
// 指针异或函数XorP返回指针p和q的异或值
2.34 假设在算法描述语言中引入指针的二元运算“异或”，若a和b为指针，则a⊕b的运算结果仍为原指针类型，且
a⊕(a⊕b)=(a⊕a)⊕b=b
(a⊕b)⊕b=a⊕(b⊕b)=a
则可利用一个指针域来实现双向链表L。链表L中的每个结点只含两个域：data域和LRPtr域，其中LRPtr域存放该结点的左邻与右邻结点指针（不存在时为NULL）的异或。若设指针L.Left指向链表中的最左结点，L.Right指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法按任一方向依次输出链表中各元素的值。
解：
Status TraversingLinkList(XorLinkedList &L,char d)
{
XorPointer p,left,right;
if(d==’l’||d==’L’){
p=L.Left;
left=NULL;
while(p!=NULL){
VisitingData(p->data);
left=p;
p=XorP(left,p->LRPtr);
}
}
else
if(d==’r’||d==’R’){
p=L.Right;
right=NULL;
while(p!=NULL){
VisitingData(p->data);
right=p;
p=XorP(p->LRPtr,right);
}
}
else return ERROR;
return OK;
}
2.35 采用2.34题所述的存储结构，写出在第i个结点之前插入一个结点的算法。
解：
Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)//在异或链表L的第i个元素前插入元素x
{
p=L.left;pre=NULL;
r=(XorNode*)malloc(sizeof(XorNode));
r->data=x;
if(i==1) //当插入点在最左边的情况
{
p->LRPtr=XorP(p.LRPtr,r);
r->LRPtr=p;
L.left=r;
return OK;
}
j=1;q=p->LRPtr; //当插入点在中间的情况
while(++j<i&&q)
{
q=XorP(p->LRPtr,pre);
pre=p;p=q;
}//while //在p,q两结点之间插入
if(!q) return INFEASIBLE; //i不可以超过表长
p->LRPtr=XorP(XorP(p->LRPtr,q),r);
q->LRPtr=XorP(XorP(q->LRPtr,p),r);
r->LRPtr=XorP(p,q); //修改指针
return OK;
}//Insert_XorLinkedList
2.36 采用2.34题所述的存储结构，写出删除第i个结点的算法。
解：
Status Delete_XorLinkedList(XorlinkedList &L,int i)//删除异或链表L的第i个元素
{
p=L.left;pre=NULL;
if(i==1) //删除最左结点的情况
{
q=p->LRPtr;
q->LRPtr=XorP(q->LRPtr,p);
L.left=q;free(p);
return OK;
}
j=1;q=p->LRPtr;
while(++j<i&&q)
{
q=XorP(p->LRPtr,pre);
pre=p;p=q;
}//while //找到待删结点q
if(!q) return INFEASIBLE; //i不可以超过表长
if(L.right==q) //q为最右结点的情况
{
p->LRPtr=XorP(p->LRPtr,q);
L.right=p;free(q);
return OK;
}
r=XorP(q->LRPtr,p); //q为中间结点的情况,此时p,r分别为其左右结点
p->LRPtr=XorP(XorP(p->LRPtr,q),r);
r->LRPtr=XorP(XorP(r->LRPtr,q),p); //修改指针
free(q);
return OK;
}//Delete_XorLinkedList
2.37 设以带头结点的双向循环链表表示的线性表。试写一时间复杂度O(n)的算法，将L改造为。
解：
// 将双向链表L=(a1,a2,…,an)改造为(a1,a3,…,an,…,a2)
Status ListChange_DuL(DuLinkList &L)
{
int i;
DuLinkList p,q,r;
p=L->next;
r=L->pre;
i=1;
while(p!=r){
if(i%2==0){
q=p;
p=p->next;
// 删除结点
q->pre->next=q->next;
q->next->pre=q->pre;
// 插入到头结点的左面
q->pre=r->next->pre;
r->next->pre=q;
q->next=r->next;
r->next=q;
}
else p=p->next;
i++;
}
return OK;
}
2.38 设有一个双向循环链表，每个结点中除有pre，data和next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次Locate(L,x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的Locate操作的算法。
解：
DuLinkList ListLocate_DuL(DuLinkList &L,ElemType e)
{
DuLinkList p,q;
p=L->next;
while(p!=L && p->data!=e) p=p->next;
if(p==L) return NULL;
else{
p->freq++;
// 删除结点
p->pre->next=p->next;
p->next->pre=p->pre;
// 插入到合适的位置
q=L->next;
while(q!=L && q->freq>p->freq) q=q->next;
if(q==L){
p->next=q->next;
q->next=p;
p->pre=q->pre;
q->pre=p;
}
else{
// 在q之前插入
p->next=q->pre->next;
q->pre->next=p;
p->pre=q->pre;
q->pre=p;
}
return p;
}
}
在2.39至2.40题中，稀疏多项式采用的顺序存储结构SqPoly定义为
typedef struct {
int coef;
int exp;
} PolyTerm;
typedef struct { //多项式的顺序存储结构
PolyTerm *data;
int last;
} SqPoly;
2.39 已知稀疏多项式，其中，，。试采用存储量同多项式项数m成正比的顺序存储结构，编写求的算法（为给定值），并分析你的算法的时间复杂度。
解：
typedef struct{
int coef;
int exp;
} PolyTerm;
typedef struct{
PolyTerm *data;
int last;
} SqPoly;
// 建立一个多项式
Status PolyInit(SqPoly &L)
{
int i;
PolyTerm *p;
cout<<“请输入多项式的项数:”;
cin>>L.last;
L.data=(PolyTerm *)malloc(L.last*sizeof(PolyTerm));
if(!L.data) return ERROR;
p=L.data;
for(i=0;i<L.last;i++){
cout<<“请输入系数:”;
cin>>p->coef;
cout<<“请输入指数:”;
cin>>p->exp;
p++;
}
return OK;
}
// 求多项式的值
double PolySum(SqPoly &L,double x0)
{
double Pn,x;
int i,j;
PolyTerm *p;
p=L.data;
for(i=0,Pn=0;i<L.last;i++,p++){
for(j=0,x=1;j<p->exp;j++) x=x*x0;
Pn=Pn+p->coef*x;
}
return Pn;
}
2.40 采用2.39题给定的条件和存储结构，编写求的算法，将结果多项式存放在新辟的空间中，并分析你的算法的时间复杂度。
解：
// 求两多项式的差
Status PolyMinus(SqPoly &L,SqPoly &L1,SqPoly &L2)
{
PolyTerm *p,*p1,*p2;
p=L.data;
p1=L1.data;
p2=L2.data;
int i=0,j=0,k=0;
while(i<L1.last&&j<L2.last){
if(p1->exp<p2->exp){
p->coef=p1->coef;
p->exp=p1->exp;
p++; k++;
p1++; i++;
}
else
if(p1->exp>p2->exp){
p->coef=-p2->coef;
p->exp=p2->exp;
p++; k++;
p2++; j++;
}
else{
if(p1->coef!=p2->coef){
p->coef=(p1->coef)-(p2->coef);
p->exp=p1->exp;
p++; k++;
}
p1++; p2++;
i++; j++;
}
}
if(i<L1.last)
while(i<L1.last){
p->coef=p1->coef;
p->exp=p1->exp;
p++; k++;
p1++; i++;
}
if(j<L2.last)
while(j<L2.last){
p->coef=-p2->coef;
p->exp=p2->exp;
p++; k++;
p2++; j++;
}
L.last=k;
return OK;
}
在2.41至2.42题中，稀疏多项式采用的循环链表存储结构LinkedPoly定义为
typedef struct PolyNode {
PolyTerm data;
struct PolyNode *next;
} PolyNode, *PolyLink;
typedef PolyLink LinkedPoly;
2.41 试以循环链表作稀疏多项式的存储结构，编写求其导函数的方法，要求利用原多项式中的结点空间存放其导函数多项式，同时释放所有无用结点。
解：
Status PolyDifferential(LinkedPoly &L)
{
LinkedPoly p,q,pt;
q=L;
p=L->next;
while(p!=L){
if(p->data.exp==0){
pt=p;
p=p->next;
q->next=p;
free(pt);
}
else{
p->data.coef=p->data.coef*p->data.exp;
p->data.exp–;
q=p;
p=p->next;
}
}
return OK;
}
2.42 试编写算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表。
解：
// 将单链表L划分成2个单循环链表
Status ListDivideInto2CL(LinkedPoly &L,LinkedPoly &L1)
{
LinkedPoly p,p1,q,pt;
q=L;
p=L->next;
p1=L1;
while(p!=L){
if(p->data.exp%2==0){
pt=p;
p=p->next;
q->next=p;
pt->next=p1->next;
p1->next=pt;
p1=p1->next;
}
else{
q=p;
p=p->next;
}
}
return OK;
}
第3章 栈和队列
3.1 若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答：
(1) 如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？
(2) 如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以 ‘S’表示进栈和以 ‘X’表示出栈的栈操作序列）。
解：(1) 123 231 321 213 132
(2) 可以得到135426的出站序列，但不能得到435612的出站序列。因为4356出站说明12已经在栈中，1不可能先于2出栈。
3.2 简述栈和线性表的差别。
解：线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。
3.3 写出下列程序段的输出结果（栈的元素类型SElemType为char）。
void main()
{
Stack S;
char x,y;
InitStack(S);
x= ‘c’; y= ‘k’;
Push(S,x); Push(S, ‘a’); Push(S,y);
Pop(S,x); Push(S, ‘t’); Push(S,x);
Pop(S,x); Push(S, ‘s’);
while(!StackEmpty(S)) { Pop(S,y); printf(y); }
printf(x);
}
解：stack
3.4 简述以下算法的功能（栈的元素类型SElemType为int）。
(1) status algo1(Stack S)
{
int i,n,A[255];
n=0;
while(!StackEmpty(S)) { n++; Pop(S,A[n]); }
for(i=1;i<=n;i++) Push(S,A[i]);
}
(2) status algo2(Stack S,int e)
{
Stack T; int d;
InitStack(T);
while(!StackEmpty(S)){
Pop(S,d);
if(d!=e) Push(T,d);
}
while(!StackEmpty(T)){
Pop(T,d);
Push(S,d);
}
}
解：(1) 栈中的数据元素逆置 (2) 如果栈中存在元素e，将其从栈中清除
3.5 假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。
解：任何前n个序列中S的个数一定大于X的个数。
设两个合法序列为：
T1=S……X……S……
T2=S……X……X……
假定前n个操作都相同，从第n+1个操作开始，为序列不同的起始操作点。由于前n个操作相同，故此时两个栈（不妨为栈A、B）的存储情况完全相同，假设此时栈顶元素均为a。
第n+1个操作不同，不妨T1的第n+1个操作为S，T2的第n+1个操作为X。T1为入栈操作，假设将b压栈，则T1的输出顺序一定是先b后a；而T2将a退栈，则其输出顺序一定是先a后b。由于T1的输出为……ba……，而T2的输出顺序为……ab……，说明两个不同的合法栈操作序列的输出元素的序列一定不同。
3.6 试证明：若借助栈由输入序列12…n得到的输出序列为(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i<j<k使<<。
解：这个问题和3.1题比较相似。因为输入序列是从小到大排列的，所以若<<，则可以理解为通过输入序列可以得到输出序列，显然通过序列123是无法得到312的，参见3.1题。所以不可能存在着i<j<k使<<。
3.7 按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例，并仿照教科书3.2节例3-2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：
A-B×C/D+E↑F
解：BC=G G/D=H A-H=I E^F=J I+J=K
|
步骤 |
OPTR栈 |
OPND栈 |
输入字符 |
主要操作 |
|
1 |
# |
A-B*C/D+E^F# |
PUSH(OPND,A) |
|
|
2 |
# |
A |
-B*C/D+E^F# |
PUSH(OPTR,-) |
|
3 |
#- |
A |
B*C/D+E^F# |
PUSH(OPND,B) |
|
4 |
#- |
A B |
*C/D+E^F# |
PUSH(OPTR,*) |
|
5 |
#-* |
A B |
C/D+E^F# |
PUSH(OPND,C) |
|
6 |
#-* |
A B C |
/D+E^F# |
Operate(B,*,C) |
|
7 |
#- |
A G |
/D+E^F# |
PUSH(OPTR,/) |
|
8 |
#-/ |
A G |
D+E^F# |
PUSH(OPND,D) |
|
9 |
#-/ |
A G D |
+E^F# |
Operate(G,/,D) |
|
10 |
#- |
A H |
+E^F# |
Operate(A,-,H) |
|
11 |
# |
I |
+E^F# |
PUSH(OPTR,+) |
|
12 |
#+ |
I |
E^F# |
PUSH(OPND,E) |
|
13 |
#+ |
I E |
^F# |
PUSH(OPTR,^) |
|
14 |
#+^ |
I E |
F# |
PUSH(OPND,F) |
|
15 |
#+^ |
I E F |
# |
Operate(E,^,F) |
|
16 |
#+ |
I J |
# |
Operate(I,+,J) |
|
17 |
# |
K |
# |
RETURN |
3.8 试推导求解n阶梵塔问题至少要执行的move操作的次数。
解：
3.9 试将下列递推过程改写为递归过程。
void ditui(int n)
{
int i;
i = n;
while(i>1)
cout<<i–;
}
解：
void ditui(int j)
{
if(j>1){
cout<<j;
ditui(j-1);
}
return;
}
3.10 试将下列递归过程改写为非递归过程。
void test(int &sum)
{
int x;
cin>>x;
if(x==0) sum=0;
else
{
test(sum);
sum+=x;
}
cout<<sum;
}
解：
void test(int &sum)
{
Stack s;
InitStack(s);
int x;
do{
cin>>x;
Push(s,x);
}while(x>0);
while(!StackEmpty(s)){
Pop(s,x);
sum+=x;
cout<<sum<<endl;
}
DestoryStack(s);
}
3.11 简述队列和堆栈这两种数据类型的相同点和差异处。
解：栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。
队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。
3.12 写出以下程序段的输出结果（队列中的元素类型QElemType为char）。
void main()
{
Queue Q;
InitQueue(Q);
char x= ‘e’, y= ‘c’;
EnQueue(Q, ‘h’);
EnQueue(Q, ‘r’);
EnQueue(Q, y);
DeQueue(Q, x);
EnQueue(Q, x);
DeQueue(Q, x);
EnQueue(Q, ‘a’);
While(!QueueEmpty(Q))
{
DeQueue(Q,y);
cout<<y;
}
cout<<x;
}
解：char
3.13 简述以下算法的功能（栈和队列的元素类型均为int）。
void algo3(Queue &Q)
{
Stack S;
int d;
InitStack(S);
while(!QueueEmpty(Q))
{
DeQueue(Q, d);
Push(S, d);
}
while(!StackEmpty(S))
{
Pop(S, d);
EnQueue(Q, d);
}
}
解：队列逆置
3.14 若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列：
(1) 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。
(2) 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。
(3) 既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。
3.15 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。
解：
class DStack{
ElemType *top[2];
ElemType *p;
int stacksize;
int di;
public:
DStack(int m)
{
p=new ElemType[m];
if(!p) exit(OVERFLOW);
top[0]=p+m/2;
top[1]=top[0];
stacksize=m;
}
~DStack(){delete p;}
void Push(int i,ElemType x)
{
di=i;
if(di==0){
if(top[0]>=p) *top[0]–=x;
else cerr<<“Stack overflow!”;
}
else{
if(top[1]<p+stacksize-1) *++top[1]=x;
else cerr<<“Stack overflow!”;
}
}
ElemType Pop(int i)
{
di=i;
if(di==0){
if(top[0]<top[1]) return *++top[0];
else cerr<<“Stack empty!”;
}else{
if(top[1]>top[0]) return *top[1]–;
else cerr<<“Stack empty!”;
}
return OK;
}
};
// 链栈的数据结构及方法的定义
typedef struct NodeType{
ElemType data;
NodeType *next;
}NodeType,*LinkType;
typedef struct{
LinkType top;
int size;
}Stack;
void InitStack(Stack &s)
{
s.top=NULL;
s.size=0;
}
void DestroyStack(Stack &s)
{
LinkType p;
while(s.top){
p=s.top;
s.top=p->next;
delete p;
s.size–;
}
}
void ClearStack(Stack &s)
{
LinkType p;
while(s.top){
p=s.top;
s.top=p->next;
delete p;
s.size–;
}
}
int StackLength(Stack s)
{
return s.size;
}
Status StackEmpty(Stack s)
{
if(s.size==0) return TRUE;
else return FALSE;
}
Status GetTop(Stack s,ElemType &e)
{
if(!s.top) return ERROR;
else{
e=s.top->data;
return OK;
}
}
Status Push(Stack &s,ElemType e)
{
LinkType p;
p=new NodeType;
if(!p) exit(OVERFLOW);
p->next=s.top;
s.top=p;
p->data=e;
s.size++;
return OK;
}
Status Pop(Stack &s,ElemType &e)
{
LinkType p;
if(s.top){
e=s.top->data;
p=s.top;
s.top=p->next;
delete p;
s.size–;
}
return OK;
}
// 从栈顶到栈底用Visit()函数遍历栈中每个数据元素
void StackTraverse(Stack s,Status (*Visit)(ElemType e))
{
LinkType p;
p=s.top;
while(p) Visit(p->data);
}
3.16 假设如题3.1所属火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度，试编写算法，输出对这n节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调整到硬席车厢之前。
解：
int main()
{
Stack s;
char Buffer[80];
int i=0,j=0;
InitStack(s);
cout<<“请输入硬席(H)和软席车厢(S)序列：”;
cin>>Buffer;
cout<<Buffer<<endl;
while(Buffer[i]){
if(Buffer[i]==’S’){
Buffer[j]=Buffer[i];
j++;
}
else Push(s,Buffer[i]);
i++;
}
while(Buffer[j]){
Pop(s,Buffer[j]);
j++;
}
cout<<Buffer<<endl;
return 0;
}
3.17 试写一个算法，识别一次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不是。
解：
BOOL Symmetry(char a[])
{
int i=0;
Stack s;
InitStack(s);
ElemType x;
while(a[i]!=’&’ && a[i]){
Push(s,a[i]);
i++;
}
if(a[i]) return FALSE;
i++;
while(a[i]){
Pop(s,x);
if(x!=a[i]){
DestroyStack(s);
return FALSE;
}
i++;
}
return TRUE;
}
3.18 试写一个判别表达式中开、闭括号是否配对出现的算法。
解：
BOOL BracketCorrespondency(char a[])
{
int i=0;
Stack s;
InitStack(s);
ElemType x;
while(a[i]){
switch(a[i]){
case ‘(‘:
Push(s,a[i]);
break;
case ‘[‘:
Push(s,a[i]);
break;
case ‘)’:
GetTop(s,x);
if(x=='(‘) Pop(s,x);
else return FALSE;
break;
case ‘]’:
GetTop(s,x);
if(x=='[‘) Pop(s,x);
else return FALSE;
break;
default:
break;
}
i++;
}
if(s.size!=0) return FALSE;
return TRUE;
}
3.19 假设一个算术表达式中可以包括三种括号：圆括号“（”和“）”、方括号“[”和“]”和花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…）。编写判别给定表达式中所含括号是否正确配对出现的算法（已知表达式已存入数据元素为字符的顺序表中）。
解：
Status AllBrackets_Test(char *str)//判别表达式中三种括号是否匹配
{
InitStack(s);
for(p=str;*p;p++)
{
if(*p=='(‘||*p=='[‘||*p=='{‘) push(s,*p);
else if(*p==’)’||*p==’]’||*p==’}’)
{
if(StackEmpty(s)) return ERROR;
pop(s,c);
if(*p==’)’&&c!='(‘) return ERROR;
if(*p==’]’&&c!='[‘) return ERROR;
if(*p==’}’&&c!='{‘) return ERROR; //必须与当前栈顶括号匹配
}
}//for
if(!StackEmpty(s)) return ERROR;
return OK;
}//AllBrackets_Test
3.20 假设以二维数组g(1…m, 1…n)表示一个图像区域，g[i,j]表示该区域中点(i,j)所具颜色，其值为从0到k的整数。编写算法置换点(i0,j0)所在区域的颜色。约定和(i0,j0)同色的上、下、左、右的邻接点为同色区域的点。
解：
#include <iostream.h>
#include <stdlib.h>
typedef struct{
int x;
int y;
}PosType;
typedef struct{
int Color;
int Visited;
PosType seat;
}ElemType;
#include “d:\VC99\Stack.h”
#define M 8
#define N 8
ElemType g[M][N];
void CreateGDS(ElemType g[M][N]);
void ShowGraphArray(ElemType g[M][N]);
void RegionFilling(ElemType g[M][N],PosType CurPos,int NewColor);
int main()
{
CreateGDS(g);
ShowGraphArray(g);
PosType StartPos;
StartPos.x=5;
StartPos.y=5;
int FillColor=6;
RegionFilling(g,StartPos,FillColor);
cout<<endl;
ShowGraphArray(g);
return 0;
}
void RegionFilling(ElemType g[M][N],PosType CurPos,int FillColor)
{
Stack s;
InitStack(s);
ElemType e;
int OldColor=g[CurPos.x][CurPos.y].Color;
Push(s,g[CurPos.x][CurPos.y]);
while(!StackEmpty(s)){
Pop(s,e);
CurPos=e.seat;
g[CurPos.x][CurPos.y].Color=FillColor;
g[CurPos.x][CurPos.y].Visited=1;
if(CurPos.x<M &&
!g[CurPos.x+1][CurPos.y].Visited &&
g[CurPos.x+1][CurPos.y].Color==OldColor
)
Push(s,g[CurPos.x+1][CurPos.y]);
if(CurPos.x>0 &&
!g[CurPos.x-1][CurPos.y].Visited &&
g[CurPos.x-1][CurPos.y].Color==OldColor
)
Push(s,g[CurPos.x-1][CurPos.y]);
if(CurPos.y<N &&
!g[CurPos.x][CurPos.y+1].Visited &&
g[CurPos.x][CurPos.y+1].Color==OldColor
)
Push(s,g[CurPos.x][CurPos.y+1]);
if(CurPos.y>0 &&
!g[CurPos.x][CurPos.y-1].Visited &&
g[CurPos.x][CurPos.y-1].Color==OldColor
)
Push(s,g[CurPos.x][CurPos.y-1]);
}
}
void CreateGDS(ElemType g[M][N])
{
int i,j;
for(i=0;i<M;i++)
for(j=0;j<N;j++){
g[i][j].seat.x=i;
g[i][j].seat.y=j;
g[i][j].Visited=0;
g[i][j].Color=0;
}
for(i=2;i<5;i++)
for(j=2;j<4;j++)
g[i][j].Color=3;
for(i=5;i<M-1;i++)
for(j=3;j<6;j++)
g[i][j].Color=3;
}
void ShowGraphArray(ElemType g[M][N])
{
int i,j;
for(i=0;i<M;i++){
for(j=0;j<N;j++)
cout<<g[i][j].Color;
cout<<endl;
}
}
3.21 假设表达式有单字母变量和双目四则运算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰表达式。
解：
// 输入的表达式串必须为#…#格式
void InversePolandExpression(char Buffer[])
{
Stack s;
InitStack(s);
int i=0,j=0;
ElemType e;
Push(s,Buffer[i]);
i++;
while(Buffer[i]!=’#’){
if(!IsOperator(Buffer[i])){ // 是操作数
Buffer[j]=Buffer[i];
i++;
j++;
}
else{ // 是操作符
GetTop(s,e);
if(Prior(e,Buffer[i])){// 当栈顶优先权高于当前序列时，退栈
Pop(s,e);
Buffer[j]=e;
j++;
}
else{
Push(s,Buffer[i]);
i++;
}
}
}
while(!StackEmpty(s)){
Pop(s,e);
Buffer[j]=e;
j++;
}
}
Status IsOpertor(char c)
{
char *p=”#+-*/”;
while(*p){
if(*p==c)
return TRUE;
p++;
}
return FALSE;
}
Status Prior(char c1,char c2)
{
char ch[]=”#+-*/”;
int i=0,j=0;
while(ch[i] && ch[i]!=c1) i++;
if(i==2) i–; // 加和减可认为是同级别的运算符
if(i==4) i–; // 乘和除可认为是同级别的运算符
while(ch[j] && ch[j]!=c2) j++;
if(j==2) j–;
if(j==4) j–;
if(i>=j) return TRUE;
else return FALSE;
}
3.22 如题3.21的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。
解：
char CalVal_InverPoland(char Buffer[])
{
Stack Opnd;
InitStack(Opnd);
int i=0;
char c;
ElemType e1,e2;
while(Buffer[i]!=’#’){
if(!IsOperator(Buffer[i])){
Push(Opnd,Buffer[i]);
}
else{
Pop(Opnd,e2);
Pop(Opnd,e1);
c=Cal(e1,Buffer[i],e2);
Push(Opnd,c);
}
i++;
}
return c;
}
char Cal(char c1,char op,char c2)
{
int x,x1,x2;
char ch[10];
ch[0]=c1;
ch[1]=’\0′;
x1=atoi(ch);
ch[0]=c2;
ch[1]=’\0′;
x2=atoi(ch);
switch(op){
case ‘+’:
x=x1+x2;
break;
case ‘-‘:
x=x1-x2;
break;
case ‘*’:
x=x1*x2;
break;
case ‘/’:
x=x1/x2;
break;
default:
break;
}
itoa(x,ch,10);
return ch[0];
}
3.23 如题3.21的假设条件，试写一个算法，判断给定的非空后缀表达式是否为正确的逆波兰表达式，如果是，则将它转化为波兰式。
解：
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include “d:\VC99\DSConstant.h”
typedef char ARRAY[30];
typedef ARRAY ElemType;
typedef struct NodeType{
ElemType data;
NodeType *next;
}NodeType,*LinkType;
typedef struct{
LinkType top;
int size;
}Stack;
void InitStack(Stack &s);
Status Push(Stack &s,ElemType e);
Status Pop(Stack &s,ElemType e);
Status IsOperator(char c);
Status StackEmpty(Stack s);
Status InvToFroPoland(char a[]);
int main()
{
char a[30];
cout<<“请输入逆波兰算术表达式字符序列：”;
cin>>a;
if(InvToFroPoland(a)) cout<<a<<endl;
else cout<<“输入逆波兰算术表达式字符序列错误!”;
return 0;
}
Status InvToFroPoland(char a[])
{
Stack s;
InitStack(s);
int i=0;
ElemType ch;
ElemType c1;
ElemType c2;
while(a[i]!=’#’){
if(!IsOperator(a[i])){
if(a[i]>=’0′ && a[i]<=’9′){
ch[0]=a[i]; ch[1]=’\0′;
Push(s,ch);
}
else return FALSE;
}
else{
ch[0]=a[i];
ch[1]=’\0′;
if(!StackEmpty(s)){
Pop(s,c2);
if(!StackEmpty(s)){
Pop(s,c1);
strcat(ch,c1);
strcat(ch,c2);
Push(s,ch);
}
else return FALSE;
}
else return FALSE;
}
i++;
}
if(!StackEmpty(s)){
Pop(s,c1);
strcpy(a,c1);
}
else return FALSE;
if(!StackEmpty(s)) return FALSE;
return OK;
}
void InitStack(Stack &s)
{
s.top=NULL;
s.size=0;
}
Status Push(Stack &s,ElemType e)
{
LinkType p;
p=new NodeType;
if(!p) exit(OVERFLOW);
p->next=s.top;
s.top=p;
strcpy(p->data,e);
s.size++;
return OK;
}
Status Pop(Stack &s,ElemType e)
{
LinkType p;
if(s.top){
strcpy(e,s.top->data);
p=s.top;
s.top=p->next;
delete p;
s.size–;
}
return OK;
}
Status StackEmpty(Stack s)
{
if(s.size==0) return TRUE;
else return FALSE;
}
Status IsOperator(char c)
{
char *p=”#+-*/”;
while(*p){
if(*p==c)
return TRUE;
p++;
}
return FALSE;
}
3.24 试编写如下定义的递归函数的递归算法，并根据算法画出求g(5,2)时栈的变化过程。
解：
int g(int m,int n);
int main()
{
int m,n;
cout<<“请输入m和n的值：”;
cin>>m>>n;
if(n>=0) cout<<g(m,n)<<endl;
else cout<<“No Solution!”;
return 0;
}
int g(int m,int n)
{
if(m>0)
return(g(m-1,2*n)+n);
else return 0;
}
假设主函数的返回地址为0，递归函数3条语句的地址分别为1、2、3。
|
3 |
0 |
64 |
|
3 |
1 |
32 |
|
3 |
2 |
16 |
|
3 |
3 |
8 |
|
3 |
4 |
4 |
|
0 |
5 |
2 |
3.25 试写出求递归函数F(n)的递归算法，并消除递归：
解：
#include <iostream.h>
#define N 20
int main()
{
int i;
int a[N];
int n;
cout<<“请输入n:”;
cin>>n;
for(i=0;i<n+1;i++){
if(i<1) a[i]=1;
else a[i]=i*a[i/2];
}
cout<<a[n]<<endl;
return 0;
}
3.26 求解平方根的迭代函数定义如下：
其中，p是A的近似平方根，e是结果允许误差。试写出相应的递归算法，并消除递归。
解：
#include <iostream.h>
double Sqrt(double A,double p,double e);
int main()
{
double A,p,e;
cout<<“请输入A p e:”;
cin>>A>>p>>e;
cout<<Sqrt(A,p,e)<<endl;
return 0;
}
double Sqrt(double A,double p,double e)
{
if((p*p-A)>-e && (p*p-A)<e)
return p;
else
return Sqrt(A,(p+A/p)/2,e);
}
3.27 已知Ackerman函数的定义如下：
(1) 写出递归算法；
(2) 写出非递归算法；
(3) 根据非递归算法，画出求akm(2,1)时栈的变化过程。
解：
unsigned int akm(unsigned int m,unsigned int n)
{
unsigned int g;
if(m==0)
return n+1;
else
if(n==0) return akm(m-1,1);
else{
g=akm(m,n-1);
return akm(m-1,g);
}
}
非递归算法：
int akm1(int m,int n)
{
Stack s;
InitStack(s);
ElemType e,e1,d;
e.mval=m; e.nval=n;
Push(s,e);
do{
while(e.mval){
while(e.nval){
e.nval–;
Push(s,e);
}
e.mval–; e.nval=1;
}
if(StackLength(s)>1){
e1.nval=e.nval;
Pop(s,e);
e.mval–;
e.nval=e1.nval+1;
}
}while(StackLength(s)!=1||e.mval!=0);
return e.nval+1;
}
0,akm(2,1) 0 2 1 g=akm(2,0)
1,akm(2,0) 6 2 0 akm=akm(m-1,1)=akm(1,1)
2,akm(1,1) 4 1 1 g=akm(m,n-1)=akm(1,0)
3,akm(1,0) 6 1 0 akm=akm(m-1,1)=akm(0,1)
4,akm(0,1) 4 0 1 akm=n+1=2 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)
1,akm(2,0) 6 2 0 akm=akm(m-1,1)=akm(1,1)
2,akm(1,1) 4 1 1 g=akm(m,n-1)=akm(1,0)
3,akm(1,0) 6 1 0 akm=akm(m-1,1)=akm(0,1)=2 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)
1,akm(2,0) 6 2 0 akm=akm(m-1,1)=akm(1,1)
2,akm(1,1) 4 1 1 g=akm(m,n-1)=akm(1,0)=2; akm=akm(m-1,g)=akm(0,2);
3,akm(0,2) 7 0 2 akm=n+1=3 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)
1,akm(2,0) 6 2 0 akm=akm(m-1,1)=akm(1,1)
2,akm(1,1) 4 1 1 g=akm(m,n-1)=akm(1,0)=2; akm=akm(m-1,g)=akm(0,2)=3; 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)
1,akm(2,0) 6 2 0 akm=akm(m-1,1)=akm(1,1)=3 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g)
2,akm(1,2) 6 1 2 g=akm(1,1); akm(m-1,g)
3,akm(1,1) 6 1 1 g=akm(1,0); akm(m-1,g)
4,akm(1,0) 6 1 0 akm=akm(0,1)
5,akm(0,1) 4 0 1 akm(0,1)=2退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g)
2,akm(1,2) 6 1 2 g=akm(1,1); akm(m-1,g)
3,akm(1,1) 6 1 1 g=akm(1,0); akm(m-1,g)
4,akm(1,0) 6 1 0 akm=akm(0,1)=2退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g)
2,akm(1,2) 6 1 2 g=akm(1,1); akm(m-1,g)
3,akm(1,1) 6 1 1 g=akm(1,0)=2; akm(m-1,g)=akm(0,2)
4,akm(0,2) 7 0 2 akm=n+1=3 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g)
2,akm(1,2) 6 1 2 g=akm(1,1); akm(m-1,g)
3,akm(1,1) 6 1 1 g=akm(1,0)=2; akm(m-1,g)=akm(0,2)=3退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g)
2,akm(1,2) 6 1 2 g=akm(1,1)=3; akm(m-1,g)=akm(0,3)
3,akm(0,3) 7 0 3 akm=n+1=4 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g)
2,akm(1,2) 6 1 2 g=akm(1,1)=3; akm(m-1,g)=akm(0,3)=4 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2)=4; akm(m-1,g)=akm(0,4)
2,akm(0,4) 7 0 4 akm=n+1=5 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2)=4; akm(m-1,g)=akm(0,4)=5退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)=5退栈
akm(2,1)=5;
3.28 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列何处队列的算法。
解：
typedef int ElemType;
typedef struct NodeType{
ElemType data;
NodeType *next;
}QNode,*QPtr;
typedef struct{
QPtr rear;
int size;
}Queue;
Status InitQueue(Queue& q)
{
q.rear=NULL;
q.size=0;
return OK;
}
Status EnQueue(Queue& q,ElemType e)
{
QPtr p;
p=new QNode;
if(!p) return FALSE;
p->data=e;
if(!q.rear){
q.rear=p;
p->next=q.rear;
}
else{
p->next=q.rear->next;
q.rear->next=p;
q.rear=p;
}
q.size++;
return OK;
}
Status DeQueue(Queue& q,ElemType& e)
{
QPtr p;
if(q.size==0)return FALSE;
if(q.size==1){
p=q.rear;
e=p->data;
q.rear=NULL;
delete p;
}
else{
p=q.rear->next;
e=p->data;
q.rear->next=p->next;
delete p;
}
q.size–;
return OK;
}
3.29 如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0和1来区分，尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。
解：
#define MaxQSize 4
typedef int ElemType;
typedef struct{
ElemType *base;
int front;
int rear;
Status tag;
}Queue;
Status InitQueue(Queue& q)
{
q.base=new ElemType[MaxQSize];
if(!q.base) return FALSE;
q.front=0;
q.rear=0;
q.tag=0;
return OK;
}
Status EnQueue(Queue& q,ElemType e)
{
if(q.front==q.rear&&q.tag) return FALSE;
else{
q.base[q.rear]=e;
q.rear=(q.rear+1)%MaxQSize;
if(q.rear==q.front)q.tag=1;
}
return OK;
}
Status DeQueue(Queue& q,ElemType& e)
{
if(q.front==q.rear&&!q.tag)return FALSE;
else{
e=q.base[q.front];
q.front=(q.front+1)%MaxQSize;
q.tag=0;
}
return OK;
}
设标志节省存储空间，但运行时间较长。不设标志则正好相反。
3.30 假设将循环队列定义为:以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。
解：
#define MaxQSize 4
typedef int ElemType;
typedef struct{
ElemType *base;
int rear;
int length;
}Queue;
Status InitQueue(Queue& q)
{
q.base=new ElemType[MaxQSize];
if(!q.base) return FALSE;
q.rear=0;
q.length=0;
return OK;
}
Status EnQueue(Queue& q,ElemType e)
{
if((q.rear+1)%MaxQSize==(q.rear+MaxQSize-q.length)%MaxQSize)
return FALSE;
else{
q.base[q.rear]=e;
q.rear=(q.rear+1)%MaxQSize;
q.length++;
}
return OK;
}
Status DeQueue(Queue& q,ElemType& e)
{
if((q.rear+MaxQSize-q.length)%MaxQSize==q.rear)
return FALSE;
else{
e=q.base[(q.rear+MaxQSize-q.length)%MaxQSize];
q.length–;
}
return OK;
}
3.31 假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。
解：
Status SymmetryString(char* p)
{
Queue q;
if(!InitQueue(q)) return 0;
Stack s;
InitStack(s);
ElemType e1,e2;
while(*p){
Push(s,*p);
EnQueue(q,*p);
p++;
}
while(!StackEmpty(s)){
Pop(s,e1);
DeQueue(q,e2);
if(e1!=e2) return FALSE;
}
return OK;
}
3.32 试利用循环队列编写求k阶菲波那契序列中前n+1项的算法，要求满足：而，其中max为某个约定的常数。（注意：本题所用循环队列的容量仅为k，则在算法执行结束时，留在循环队列中的元素应是所求k阶菲波那契序列中的最后k项）
解：
int Fibonacci(int k,int n)
{
if(k<1) exit(OVERFLOW);
Queue q;
InitQueue(q,k);
ElemType x,e;
int i=0;
while(i<=n){
if(i<k-1){
if(!EnQueue(q,0)) exit(OVERFLOW);
}
if(i==k-1){
if(!EnQueue(q,1)) exit(OVERFLOW);
}
if(i>=k){
// 队列求和
x=sum(q);
DeQueue(q,e);
EnQueue(q,x);
}
i++;
}
return q.base[(q.rear+q.MaxSize-1)%q.MaxSize];
}
3.33 在顺序存储结构上实现输出受限的双端循环队列的入列和出列（只允许队头出列）算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。
解：
// Filename:Queue.h
typedef struct{
ElemType *base;
int front;
int rear;
Status tag;
int MaxSize;
}DQueue;
Status InitDQueue(DQueue& q,int size)
{
q.MaxSize=size;
q.base=new ElemType[q.MaxSize];
if(!q.base) return FALSE;
q.front=0;
q.rear=0;
q.tag=0;
return OK;
}
Status EnDQueue(DQueue& q,ElemType e)
{
if(q.front==q.rear&&q.tag) return FALSE;
if(q.front==q.rear&&!q.tag){ // 空队列
q.base[q.rear]=e;
q.rear=(q.rear+1)%q.MaxSize;
if(q.rear==q.front)q.tag=1;
}
else{ // 非空非满
if(e<(q.base[q.front]+q.base[(q.rear+q.MaxSize-1)%q.MaxSize])/2){
// 从队头入队
q.front=(q.front+q.MaxSize-1)%q.MaxSize;
q.base[q.front]=e;
if(q.rear==q.front)q.tag=1;
}
else{ // 从队尾入队
q.base[q.rear]=e;
q.rear=(q.rear+1)%q.MaxSize;
if(q.rear==q.front)q.tag=1;
}
}
return OK;
}
Status DeDQueue(DQueue& q,ElemType& e)
{
if(q.front==q.rear&&!q.tag)return FALSE;
else{ // 非空队列
e=q.base[q.front];
q.front=(q.front+1)%q.MaxSize;
q.tag=0;
}
return OK;
}
// Filename:XT333.cpp 主程序文件
#include <iostream.h>
#include <stdlib.h>
typedef int ElemType;
#include “D:\VC99\Queue.h”
int main()
{
int t1,t2,t3,t4;
ElemType e;
cout<<“请输入作业a1、a2、a3、a4的执行时间: “;
cin>>t1>>t2>>t3>>t4;
DQueue dq;
InitDQueue(dq,5);
EnDQueue(dq,t1);
EnDQueue(dq,t2);
EnDQueue(dq,t3);
EnDQueue(dq,t4);
while(dq.front!=dq.rear||dq.tag){
DeDQueue(dq,e);
cout<<e<<endl;
}
return 0;
}
3.34 假设在如教科书3.4.1节中图3.9所示的铁道转轨网的输入端有n节车厢：硬座、硬卧和软卧（分别以P,H和S表示）等待调度，要求这三种车厢在输出端铁道上的排列次序为：硬座在前，软卧在中，硬卧在后。试利用输出受限的双端队列对这n节车厢进行调度，编写算法输出调度的操作序列：分别以字符‘E’和‘D’表示对双端队列的头端进行入队列和出队列的操作；以字符A表示对双端队列的尾端进行入队列的操作。
解：
int main()
{
ElemType e;
DQueue dq;
InitDQueue(dq,20);
char ch[20];
cout<<“请输入待调度的车厢字符序列(仅限PHS)：”;
cin>>ch;
int i=0;
while(ch[i]){
if(ch[i]==’P’) cout<<ch[i];
if(ch[i]==’S’) EnDQueue(dq,ch[i],0);// 从队头入队
if(ch[i]==’H’) EnDQueue(dq,ch[i],1);// 从队尾入队
i++;
}
while(dq.front!=dq.rear||dq.tag){
DeDQueue(dq,e);
cout<<e;
}
cout<<endl;
return 0;
}
第4章 串
4.1 解：空格串是指一个或多个空格字符(ASCII码为20H)组成的串，而空串中没有任何字符。
4.2 解：串赋值(StrAssign)、串比较(StrCompare)、求串长(StrLength)、串连接(Concat)、求子串(SubString)这五种基本操作构成串类型的最小操作子集。
4.6 解：
s1=SubString(s,3,1)
s2=SubString(s,6,1)
Replace(s,s1,s2)
Concat(s3,s,s1)
Concat(t,SubString(s3,1,5),SubString(s3,7,2))
算法设计题：
// Filename: String.h
#include <stdlib.h>
#include <string.h>
#define MaxSize 128
class String{
char *ch;
int curlen;
public:
String(const String& ob);
String(const char* init);
String();
~String();
void StrAssign(String t);
int StrCompare(String t);
int StrLength();
void Concat(String t);
String SubString(int start,int len);
void show();
};
String::String(const String& ob)
{
ch=new char[MaxSize+1];
if(!ch) exit(1);
curlen=ob.curlen;
strcpy(ch,ob.ch);
}
String::String(const char* init)
{
ch=new char[MaxSize+1];
if(!ch) exit(1);
curlen=strlen(init);
strcpy(ch,init);
}
String::String()
{
ch=new char[MaxSize+1];
if(!ch) exit(1);
curlen=0;
ch[0]=’\0′;
}
String::~String()
{
delete ch;
curlen=0;
}
void String::StrAssign(String t)
{
strcpy(ch,t.ch);
curlen=t.curlen;
}
int String::StrCompare(String t)
{
return strcmp(ch,t.ch);
}
int String::StrLength()
{
return curlen;
}
void String::Concat(String t)
{
strcat(ch,t.ch);
curlen=curlen+t.curlen;
}
String String::SubString(int start,int len)
{
String temp;
int i,j;
if(start>=0 && start+len<=curlen && len>0){
temp.curlen=len;
for(i=0,j=start;i<len;i++,j++)
temp.ch[i]=ch[j];
temp.ch[len]=’\0′;
}
return temp;
}
void String::show()
{
cout<<ch<<endl;
}
4.10 解1：
void StrReverse(String& s)
{
String t;
int i,j;
j=s.StrLength();
for(i=j-1;i>=0;i–)
t.Concat(s.SubString(i,1));
s.StrAssign(t);
}
解2：
void String_Reverse(Stringtype s,Stringtype &r)//求s的逆串r
{
StrAssign(r,”); //初始化r为空串
for(i=Strlen(s);i;i–)
{
StrAssign(c,SubString(s,i,1));
StrAssign(r,Concat(r,c)); //把s的字符从后往前添加到r中
}
}//String_Reverse
4.11 解：
void String_Subtract(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r
{
StrAssign(r,”);
for(i=1;i<=Strlen(s);i++)
{
StrAssign(c,SubString(s,i,1));
for(j=1;j<i&&StrCompare(c,SubString(s,j,1));j++); //判断s的当前字符c是否第一次出现
if(i==j)
{
for(k=1;k<=Strlen(t)&&StrCompare(c,SubString(t,k,1));k++); //判断当前字符是否包含在t中
if(k>Strlen(t)) StrAssign(r,Concat(r,c));
}
}//for
}//String_Subtract
4.12
int Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数
{
for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围
if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串
{ //分别把T的前面和后面部分保存为head和tail
StrAssign(head,SubString(S,1,i-1));
StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1));
StrAssign(S,Concat(head,V));
StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串
i+=Strlen(V); //当前指针跳到插入串以后
n++;
}//if
return n;
}//Replace
分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S=’place’, T=’ace’, V=’face’,则省掉i+=Strlen(V);运行时会出现什么结果?
4.13
int Delete_SubString(Stringtype &s,Stringtype t)//从串s中删除所有与t相同的子串,并返回删除次数
{
for(n=0,i=1;i<=Strlen(s)-Strlen(t)+1;i++)
if(!StrCompare(SubString(s,i,Strlen(t)),t))
{
StrAssign(head,SubString(S,1,i-1));
StrAssign(tail,SubString(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+1));
StrAssign(S,Concat(head,tail)); //把head,tail连接为新串
n++;
}//if
return n,
}//Delete_SubString
4.14
Status NiBoLan_to_BoLan(Stringtype str,Stringtype &new)//把前缀表达式str转换为后缀式new
{
Initstack(s); //s的元素为Stringtype类型
for(i=1;i<=Strlen(str);i++)
{
r=SubString(str,i,1);
if(r为字母) push(s,r);
else
{
if(StackEmpty(s)) return ERROR;
pop(s,a);
if(StackEmpty(s)) return ERROR;
pop(s,b);
StrAssign(t,Concat(r,b));
StrAssign(c,Concat(t,a)); //把算符r,子前缀表达式a,b连接为新子前缀表达式c
push(s,c);
}
}//for
pop(s,new);
if(!StackEmpty(s)) return ERROR;
return OK;
}//NiBoLan_to_BoLan
分析:基本思想见书后注释3.23.请读者用此程序取代作者早些时候对3.23题给出的程序.
4.15
void StrAssign(Stringtype &T,char chars&#;)//用字符数组chars给串T赋值,Stringtype的定义见课本
{
for(i=0,T[0]=0;chars[i];T[0]++,i++) T[i+1]=chars[i];
}//StrAssign
4.16
char StrCompare(Stringtype s,Stringtype t)//串的比较,s>t时返回正数,s=t时返回0,s<t时返回负数
{
for(i=1;i<=s[0]&&i<=t[0]&&s[i]==t[i];i++);
if(i>s[0]&&i>t[0]) return 0;
else if(i>s[0]) return -t[i];
else if(i>t[0]) return s[i];
else return s[i]-t[i];
}//StrCompare
4.17
int String_Replace(Stringtype &S,Stringtype T,Stringtype V);//将串S中所有子串T替换为V,并返回置换次数
{
for(n=0,i=1;i<=S[0]-T[0]+1;i++)
{
for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++);
if(k>T[0]) //找到了与T匹配的子串:分三种情况处理
{
if(T[0]==V[0])
for(l=1;l<=T[0];l++) //新子串长度与原子串相同时:直接替换
S[i+l-1]=V[l];
else if(T[0]<V[0]) //新子串长度大于原子串时:先将后部右移
{
for(l=S[0];l>=i+T[0];l–)
S[l+V[0]-T[0]]=S[l];
for(l=1;l<=V[0];l++)
S[i+l-1]=V[l];
}
else //新子串长度小于原子串时:先将后部左移
{
for(l=i+V[0];l<=S[0]+V[0]-T[0];l++)
S[l]=S[l-V[0]+T[0]];
for(l=1;l<=V[0];l++)
S[i+l-1]=V[l];
}
S[0]=S[0]-T[0]+V[0];
i+=V[0];n++;
}//if
}//for
return n;
}//String_Replace
4.18
typedef struct {
char ch;
int num;
} mytype;
void StrAnalyze(Stringtype S)//统计串S中字符的种类和个数
{
mytype T[MAXSIZE]; //用结构数组T存储统计结果
for(i=1;i<=S[0];i++)
{
c=S[i];j=0;
while(T[j].ch&&T[j].ch!=c) j++; //查找当前字符c是否已记录过
if(T[j].ch) T[j].num++;
else T[j]={c,1};
}//for
for(j=0;T[j].ch;j++)
printf(“%c: %d\n”,T[j].ch,T[j].num);
}//StrAnalyze
4.19
void Subtract_String(Stringtype s,Stringtype t,Stringtype &r)//求所有包含在串s中而t中没有的字符构成的新串r
{
r[0]=0;
for(i=1;i<=s[0];i++)
{
c=s[i];
for(j=1;j<i&&s[j]!=c;j++); //判断s的当前字符c是否第一次出现
if(i==j)
{
for(k=1;k<=t[0]&&t[k]!=c;k++); //判断当前字符是否包含在t中
if(k>t[0]) r[++r[0]]=c;
}
}//for
}//Subtract_String
4.20
int SubString_Delete(Stringtype &s,Stringtype t)//从串s中删除所有与t相同的子串,并返回删除次数
{
for(n=0,i=1;i<=s[0]-t[0]+1;i++)
{
for(j=1;j<=t[0]&&s[i+j-1]==t[i];j++);
if(j>m) //找到了与t匹配的子串
{
for(k=i;k<=s[0]-t[0];k++) s[k]=s[k+t[0]]; //左移删除
s[0]-=t[0];n++;
}
}//for
return n;
}//Delete_SubString
4.21
typedef struct{
char ch;
LStrNode *next;
} LStrNode,*LString; //链串结构
void StringAssign(LString &s,LString t)//把串t赋值给串s
{
s=malloc(sizeof(LStrNode));
for(q=s,p=t->next;p;p=p->next)
{
r=(LStrNode*)malloc(sizeof(LStrNode));
r->ch=p->ch;
q->next=r;q=r;
}
q->next=NULL;
}//StringAssign
void StringCopy(LString &s,LString t)//把串t复制为串s.与前一个程序的区别在于,串s业已存在.
{
for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next)
{
p->ch=q->ch;pre=p;
}
while(q)
{
p=(LStrNode*)malloc(sizeof(LStrNode));
p->ch=q->ch;
pre->next=p;pre=p;
}
p->next=NULL;
}//StringCopy
char StringCompare(LString s,LString t)//串的比较,s>t时返回正数,s=t时返回0,s<t时返回负数
{
for(p=s->next,q=t->next;p&&q&&p->ch==q->ch;p=p->next,q=q->next);
if(!p&&!q) return 0;
else if(!p) return -(q->ch);
else if(!q) return p->ch;
else return p->ch-q->ch;
}//StringCompare
int StringLen(LString s)//求串s的长度(元素个数)
{
for(i=0,p=s->next;p;p=p->next,i++);
return i;
}//StringLen
LString * Concat(LString s,LString t)//连接串s和串t形成新串,并返回指针
{
p=malloc(sizeof(LStrNode));
for(q=p,r=s->next;r;r=r->next)
{
q->next=(LStrNode*)malloc(sizeof(LStrNode));
q=q->next;
q->ch=r->ch;
}//for //复制串s
for(r=t->next;r;r=r->next)
{
q->next=(LStrNode*)malloc(sizeof(LStrNode));
q=q->next;
q->ch=r->ch;
}//for //复制串t
q->next=NULL;
return p;
}//Concat
LString * Sub_String(LString s,int start,int len)//返回一个串,其值等于串s从start位置起长为len的子串
{
p=malloc(sizeof(LStrNode));q=p;
for(r=s;start;start–,r=r->next); //找到start所对应的结点指针r
for(i=1;i<=len;i++,r=r->next)
{
q->next=(LStrNode*)malloc(sizeof(LStrNode));
q=q->next;
q->ch=r->ch;
} //复制串t
q->next=NULL;
return p;
}//Sub_String
4.22
void LString_Concat(LString &t,LString &s,char c)//用块链存储结构,把串s插入到串t的字符c之后
{
p=t.head;
while(p&&!(i=Find_Char(p,c))) p=p->next; //查找字符c
if(!p) //没找到
{
t.tail->next=s.head;
t.tail=s.tail; //把s连接在t的后面
}
else
{
q=p->next;
r=(Chunk*)malloc(sizeof(Chunk)); //将包含字符c的节点p分裂为两个
for(j=0;j<i;j++) r->ch[j]=’#’; //原结点p包含c及其以前的部分
for(j=i;j<CHUNKSIZE;j++) //新结点r包含c以后的部分
{
r->ch[j]=p->ch[j];
p->ch[j]=’#’; //p的后半部分和r的前半部分的字符改为无效字符’#’
}
p->next=s.head;
s.tail->next=r;
r->next=q; //把串s插入到结点p和r之间
}//else
t.curlen+=s.curlen; //修改串长
s.curlen=0;
}//LString_Concat
int Find_Char(Chunk *p,char c)//在某个块中查找字符c,如找到则返回位置是第几个字符,如没找到则返回0
{
for(i=0;i<CHUNKSIZE&&p->ch[i]!=c;i++);
if(i==CHUNKSIZE) return 0;
else return i+1;
}//Find_Char
4.23
int LString_Palindrome(LString L)//判断以块链结构存储的串L是否为回文序列,是则返回1,否则返回0
{
InitStack(S);
p=S.head;i=0;k=1; //i指示元素在块中的下标,k指示元素在整个序列中的序号(从1开始)
for(k=1;k<=S.curlen;k++)
{
if(k<=S.curlen/2) Push(S,p->ch[i]); //将前半段的字符入串
else if(k>(S.curlen+1)/2)
{
Pop(S,c); //将后半段的字符与栈中的元素相匹配
if(p->ch[i]!=c) return 0; //失配
}
if(++i==CHUNKSIZE) //转到下一个元素,当为块中最后一个元素时,转到下一块
{
p=p->next;
i=0;
}
}//for
return 1; //成功匹配
}//LString_Palindrome
4.24
void HString_Concat(HString s1,HString s2,HString &t)//将堆结构表示的串s1和s2连接为新串t
{
if(t.ch) free(t.ch);
t.ch=malloc((s1.length+s2.length)*sizeof(char));
for(i=1;i<=s1.length;i++) t.ch[i-1]=s1.ch[i-1];
for(j=1;j<=s2.length;j++,i++) t.ch[i-1]=s2.ch[j-1];
t.length=s1.length+s2.length;
}//HString_Concat
4.25
int HString_Replace(HString &S,HString T,HString V)//堆结构串上的置换操作,返回置换次数
{
for(n=0,i=0;i<=S.length-T.length;i++)
{
for(j=i,k=0;k<T.length&&S.ch[j]==T.ch[k];j++,k++);
if(k==T.length) //找到了与T匹配的子串:分三种情况处理
{
if(T.length==V.length)
for(l=1;l<=T.length;l++) //新子串长度与原子串相同时:直接替换
S.ch[i+l-1]=V.ch[l-1];
else if(T.length<V.length) //新子串长度大于原子串时:先将后部右移
{
for(l=S.length-1;l>=i+T.length;l–)
S.ch[l+V.length-T.length]=S.ch[l];
for(l=0;l<V.length;l++)
S[i+l]=V[l];
}
else //新子串长度小于原子串时:先将后部左移
{
for(l=i+V.length;l<S.length+V.length-T.length;l++)
S.ch[l]=S.ch[l-V.length+T.length];
for(l=0;l<V.length;l++)
S[i+l]=V[l];
}
S.length+=V.length-T.length;
i+=V.length;n++;
}//if
}//for
return n;
}//HString_Replace
4.26
Status HString_Insert(HString &S,int pos,HString T)//把T插入堆结构表示的串S的第pos个字符之前
{
if(pos<1) return ERROR;
if(pos>S.length) pos=S.length+1;//当插入位置大于串长时,看作添加在串尾
S.ch=realloc(S.ch,(S.length+T.length)*sizeof(char));
for(i=S.length-1;i>=pos-1;i–)
S.ch[i+T.length]=S.ch[i]; //后移为插入字符串让出位置
for(i=0;i<T.length;i++)
S.ch[pos+i-1]=T.ch[pos]; //插入串T
S.length+=T.length;
return OK;
}//HString_Insert
4.27
int Index_New(Stringtype s,Stringtype t)//改进的定位算法
{
i=1;j=1;
while(i<=s[0]&&j<=t[0])
{
if((j!=1&&s[i]==t[j])||(j==1&&s[i]==t[j]&&s[i+t[0]-1]==t[t[0]]))
{ //当j==1即匹配模式串的第一个字符时,需同时匹配其最后一个
i=i+j-2;
j=1;
}
else
{
i++;j++;
}
}//while
if(j>t[0]) return i-t[0];
}//Index_New
4.28
void LGet_next(LString &T)//链串上的get_next算法
{
p=T->succ;p->next=T;q=T;
while(p->succ)
{
if(q==T||p->data==q->data)
{
p=p->succ;q=q->succ;
p->next=q;
}
else q=q->next;
}//while
}//LGet_next
4.29
LStrNode * LIndex_KMP(LString S,LString T,LStrNode *pos)//链串上的KMP匹配算法,返回值为匹配的子串首指针
{
p=pos;q=T->succ;
while(p&&q)
{
if(q==T||p->chdata==q->chdata)
{
p=p->succ;
q=q->succ;
}
else q=q->next;
}//while
if(!q)
{
for(i=1;i<=Strlen(T);i++)
p=p->next;
return p;
} //发现匹配后,要往回找子串的头
return NULL;
}//LIndex_KMP
4.30
void Get_LRepSub(Stringtype S)//求S的最长重复子串的位置和长度
{
for(maxlen=0,i=1;i<S[0];i++)//串S2向右移i格
{
for(k=0,j=1;j<=S[0]-i;j++)//j为串S2的当前指针,此时串S1的当前指针为i+j,两指针同步移动
{
if(S[j]==S[j+i]) k++; //用k记录连续相同的字符数
else k=0; //失配时k归零
if(k>maxlen) //发现了比以前发现的更长的重复子串
{
lrs1=j-k+1;lrs2=mrs1+i;maxlen=k; //作记录
}
}//for
}//for
if(maxlen)
{
printf(“Longest Repeating Substring length:%d\n”,maxlen);
printf(“Position1:%d Position 2:%d\n”,lrs1,lrs2);
}
else printf(“No Repeating Substring found!\n”);
}//Get_LRepSub
分析:i代表”错位值”.本算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,…与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明”重复子串”是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2).
4.31
void Get_LPubSub(Stringtype S,Stringtype T)//求串S和串T的最长公共子串位置和长度
{
if(S[0]>=T[0])
{
StrAssign(A,S);StrAssign(B,T);
}
else
{
StrAssign(A,T);StrAssign(B,S);
} //为简化设计,令S和T中较长的那个为A,较短的那个为B
for(maxlen=0,i=1-B[0];i<A[0];i++)
{
if(i<0) //i为B相对于A的错位值,向左为负,左端对齐为0,向右为正
{
jmin=1;jmax=i+B[0];
}//B有一部分在A左端的左边
else if(i>A[0]-B[0])
{
jmin=i;jmax=A[0];
}//B有一部分在A右端的右边
else
{
jmin=i;jmax=i+B[0];
}//B在A左右两端之间.
//以上是根据A和B不同的相对位置确定A上需要匹配的区间(与B重合的区间)的端点:jmin,jmax.
for(k=0,j=jmin;j<=jmax;j++)
{
if(A[j]==B[j-i]) k++;
else k=0;
if(k>maxlen)
{
lps1=j-k+1;lps2=j-i-k+1;maxlen=k;
}
}//for
}//for
if(maxlen)
{
if(S[0]>=T[0])
{
lpsS=lps1;lpsT=lps2;
}
else
{
lpsS=lps2;lpsT=lps1;
} //将A,B上的位置映射回S,T上的位置
printf(“Longest Public Substring length:%d\n”,maxlen);
printf(“Position in S:%d Position in T:%d\n”,lpsS,lpsT);
}//if
else printf(“No Repeating Substring found!\n”);
}//Get_LPubSub
分析:本题基本思路与上题同.唯一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o（strlrn（s）*strlen（t））。
第5章 数组与广义表
5.1 解：
(1) 6×8×6=288 Byte
(2) LOC(5,7)=1000+(5×8+7)×6=1282
(3) LOC(1,4)=1000+(1×8+4)×6=1072
(4) LOC(4,7)=1000+(7×6+4)×6=1276
5.2 解：
(1) LOC(0,0,0,0)=100
(2) LOC(1,1,1,1)=100+(1×3×5×8 + 1×5×8 + 1×8 + 1)×4=776
(3) LOC(3,1,2,5)=100+(3×3×5×8 + 1×5×8 + 2×8 + 5)×4=1784
(4) LOC(8,2,4,7)=100+(8×3×5×8 + 2×5×8 + 4×8 + 7)×4=4416
5.3 解：
(0,0,0,0) (1,0,0,0) (0,1,0,0) (1,1,0,0) (0,0,1,0) (1,0,1,0) (0,1,1,0) (1,1,1,0)
(0,0,2,0) (1,0,2,0) (0,1,2,0) (1,1,2,0) (0,0,0,1) (1,0,0,1) (0,1,0,1) (1,1,0,1)
(0,0,1,1) (1,0,1,1) (0,1,1,1) (1,1,1,1) (0,0,2,1) (1,0,2,1) (0,1,2,1) (1,1,2,1)
(0,0,0,2) (1,0,0,2) (0,1,0,2) (1,1,0,2) (0,0,1,2) (1,0,1,2) (0,1,1,2) (1,1,1,2)
(0,0,2,2) (1,0,2,2) (0,1,2,2) (1,1,2,2)
5.4 解：
其中，a=Max(i,j)，b=Min(i,j)
5.5 解： (，，)
5.6 解：u=i-j+1 v=j-1
5.7 解：(1) k=2(i-1)+j-1 ()
(2) i=(k+1) DIV 3 + 1 ()
j=k+1-2(k DIV 3)
5.8 解：i为奇数时，k=i+j-2
j为偶数时，k=i+j-1
k=2(i DIV 2)+j-1
5.9 解：设稀疏矩阵为n行n列，其中的非零元为m个，m远小于。从时间上来说，采用二维数组存储稀疏矩阵需要-1次加法运算，而用三元组只需m-1次加法运算。从空间上来说，用二维数组需要个基本存储单元，而三元组需要m个基本存储单元外加2m个整型存储单元。由于远远大于m，故实际存储空间也较大。
5.10 解：
(1) GetHead【(p,h,w)】= p
(2) GetTail【(b,k,p,h)】= (k,p,h)
(3) GetHead【((a,b),(c,d))】= (a,b)
(4) GetTail【((a,b),(c,d))】= ((c,d))
(5) GetHead【GetTail【((a,b),(c,d))】】= GetHead【((c,d))】= (c,d)
(6) GetTail【GetHead【((a,b),(c,d))】】= GetTail【(a,b)】= (b)
(7) GetHead【GetTail【GetHead【((a,b),(c,d))】】】= GetHead【(b)】= b
(8) GetTail【GetHead【GetTail【((a,b),(c,d))】】】= GetTail【(c,d)】= (d)
5.11 解：
(1) GetHead【GetTail【GetTail【L1】】】
(2) GetHead【GetHead【GetTail【L2】】】
(3) GetHead【GetHead【GetTail【GetTail【GetHead【L3】】】】】
(4) GetHead【GetHead【GetHead【GetTail【GetTail【L4】】】】】
(5) GetHead【GetHead【GetTail【GetTail【L5】】】】
(6) GetHead【GetTail【GetHead【L6】】】
(7) GetHead【GetHead【GetTail【GetHead【GetTail【L7】】】】】
5.12 解：
5.13 解：
(1) List=((x,(y)),(((())),(()),(z)))
(2) List=(((a,b,()),()),(a,(b)),())
5.14 解： (n>=1)
ElemType s(int i)
{
if(i>1)
return s(i-1)+a1+(i-1)*d;
else
return a1;
}
5.16 解：
5.17 解：
int Max(SqList &L,int k)
{
if(k<L.length-1)
if(L.elem[k]<Max(L,k+1))
return Max(L,k+1);
else
return L.elem[k];
else
return L.elem[k];
}
int Min(SqList &L,int k)
{
if(k<L.length-1)
if(L.elem[k]>Min(L,k+1))
return Min(L,k+1);
else
return L.elem[k];
else
return L.elem[k];
}
int Sum(SqList &L,int k)
{
if(k==0)
return L.elem[0];
else
return L.elem[k]+Sum(a,k-1);
}
int Product(SqList &L,int k)
{
if(k==0)
return L.elem[0];
else
return L.elem[k]*Sum(a,k-1);
}
double Avg(SqList &L,int k)
{
if(k==0)
return L.elem[0];
else
return (Avg(a,k-1)*k+L.elem[k])/(k+1);
}
5.18 解：算法的基本思想是将数组分成k组，将第一组与第二组进行两两交换，再将第一组与第三组进行两两交换，…，总共需进行n-k次交换。注意最后一组可能出现不足k个元素的情况，此时最后一组为剩余元素加第一组的前几个元素共k个构成最后一组。
void RRMove(ElemType A[],int k,int n)
{
ElemType e;
int i=0,j,p;
while(i<n-k){
p=i/k+1;
for(j=0;j<k;j++){
e=A[j];
A[j]=A[(p*k+j)%n];
A[(p*k+j)%n]=e;
i++;
}
}
}
5.19 解：
#include <iostream.h>
#define RS 4
#define CS 4
typedef int ElemType;
typedef struct{
ElemType e;
int i,j;
int Flags;
}NodeType;
void Initialize(NodeType a[RS][CS],ElemType A[RS][CS]);
void SaddlePoint(NodeType a[RS][CS]);
ElemType RowMin(NodeType a[RS][CS],int k);
ElemType ColMax(NodeType a[RS][CS],int k);
void Show(NodeType a[RS][CS]);
int main()
{
ElemType A[RS][CS]={
{2,1,3,4},
{1,3,1,2},
{2,7,1,3},
{3,2,4,1}
};
NodeType a[RS][CS];
Initialize(a,A);
SaddlePoint(a);
Show(a);
return 0;
}
void Initialize(NodeType a[RS][CS],ElemType A[RS][CS])
{
int i,j;
for(i=0;i<RS;i++){
for(j=0;j<CS;j++){
a[i][j].e=A[i][j];
a[i][j].i=i;
a[i][j].j=j;
a[i][j].Flags=0;
}
}
}
void SaddlePoint(NodeType a[RS][CS])
{
int i,j;
ElemType x,y;
for(i=0;i<RS;i++){
x=RowMin(a,i);
for(j=0;j<CS;j++){
y=ColMax(a,j);
if(a[i][j].e==x&&a[i][j].e==y)
a[i][j].Flags=1;
}
}
}
ElemType RowMin(NodeType a[RS][CS],int k)
{
ElemType x;
x=a[k][0].e;
int i;
for(i=1;i<CS;i++)
if(x>a[k][i].e){
x=a[k][i].e;
}
return x;
}
ElemType ColMax(NodeType a[RS][CS],int k)
{
ElemType x;
x=a[0][k].e;
int i;
for(i=1;i<RS;i++)
if(x<a[i][k].e){
x=a[i][k].e;
}
return x;
}
void Show(NodeType a[RS][CS])
{
for(int i=0;i<RS;i++)
for(int j=0;j<CS;j++)
if(a[i][j].Flags)
cout<<i<<” “<<j<<” is a saddle point”<<endl;
}
5.20解：
int exps[MAXSIZE]; //exps数组用于存储某一项的各变元的指数
int maxm,n; //maxm指示变元总数,n指示一个变元的最高指数
void Print_Poly_Descend(int *a,int m)//按降幂顺序输出m元多项式的项，各项的系数已经按照题目要求存储于m维数组中，数组的头指针为a
{
maxm=m;
for(i=m*n;i>=0;i–) //按降幂次序,可能出现的最高项次数为mn
Get_All(a,m,i,0); //确定并输出所有次数为i的项
}//Print_Poly_Descend
void Get_All(int *a,int m,int i,int seq)//递归求出所有和为i的m个自然数
{
if(seq==maxm) Print_Nomial(a,exps); //已经求完时,输出该项
else
{
min=i-(m-1)*n; //当前数不能小于min
if(min<0) min=0;
max=n<i?n:i; //当前数不能大于max
for(j=min;j<=max;j++)
{
exps[seq]=j; //依次取符合条件的数
Get_All(a,m-1,i-j,seq+1); //取下一个数
}
}//else
exps[seq]=0; //返回
}//Get_All
void Print_Nomial(int *a,int exps[ ])//输出一个项,项的各变元的指数已经存储在数组exps中
{
pos=0;
for(i=0;i<maxm;i++) //求出该项的系数在m维数组a中低下标优先的存储位置pos
{
pos*=n;
pos+=exps[i];
}
coef=*(a+pos); //取得该系数coef
if(!coef) return; //该项为0时无需输出
else if(coef>0) printf(“+”); //系数为正时打印加号
else if(coef<0) printf(“-“); //系数为负时打印减号
if(abs(coef)!=1) printf(“%d”,abs(coef)); //当系数的绝对值不为1时打印系数
for(i=0;i<maxm;i++)
if(exps[i]) //打印各变元及其系数
{
printf(“x”);
printf(“%d”,i);
printf(“E”);
if(exps[i]>1) printf(“%d”,exp[i]); //系数为1时无需打印
}
}//Print_Nomial
分析:本算法的关键在于如何按照降幂顺序输出各项.这里采用了一个递归函数来找到所有满足和为i的m个自然数作为各变元的指数.只要先取第一个数为j,然后再找到所有满足和为i-j的m-1个自然数就行了.要注意j的取值范围必须使剩余m-1个自然数能够找到,所以不能小于i-(m-1)*maxn,也不能大于i.只要找到了一组符合条件的数,就可以在存储多项式系数的数组中确定对应的项的系数的位置,并且在系数不为0时输出对应的项.
5.21 解：
typedef int ElemType;
class Triple{
public:
int row;
int col;
ElemType e;
Triple(){}
virtual ~Triple(){}
BOOL operator<(Triple b);
BOOL operator==(Triple b);
};
BOOL Triple::operator<(Triple b)
{
if(row<b.row) return TRUE;
if(row==b.row&&col<b.col) return TRUE;
return FALSE;
}
BOOL Triple::operator==(Triple b)
{
if(row==b.row && col==b.col)
return TRUE;
else
return FALSE;
}
class CSparseMat
{
public:
CSparseMat(){}
virtual ~CSparseMat(){}
CSparseMat(int r,int c,int n);
CSparseMat operator+(CSparseMat B);
void ShowSparse(CDC* pDC);
Triple *m_pt; // 指向非零元的指针
int m_nCol; // 矩阵列数
int m_nRow; // 矩阵行数
int m_nTrs; // 非零元个数
};
CSparseMat::CSparseMat(int r, int c, int n)
{
m_nRow=r;
m_nCol=c;
m_nTrs=n;
m_pt=new Triple[m_nTrs];
// 输入矩阵的所有三元组
int i;
for(i=0;i<m_nTrs;i++){
CInputDlg dlg1;
if(dlg1.DoModal()==IDOK){
m_pt[i].row=dlg1.m_nRow;
m_pt[i].col=dlg1.m_nCol;
m_pt[i].e=dlg1.m_nElem;
}
}
}
void CSparseMat::ShowSparse(CDC *pDC)
{
char str[10];
int k=0;
for(int i=0;i<m_nRow;i++){
for(int j=0;j<m_nCol;j++){
if(m_pt[k].row==i && m_pt[k].col==j){
itoa(m_pt[k].e,str,10);
k++;
}
else itoa(0,str,10);
pDC->TextOut(0+j*20,0+i*20,str,strlen(str));
}
}
}
// 矩阵相加的运算符重载函数
CSparseMat CSparseMat::operator+(CSparseMat B)
{
CSparseMat temp(m_nRow,m_nCol,0);
if(m_nRow!=B.m_nRow || m_nCol!=B.m_nCol)
return temp;
temp.m_pt=new Triple[m_nTrs+B.m_nTrs];
if(!temp.m_pt) return temp;
temp.m_nTrs=m_nTrs+B.m_nTrs;
int i=0;
int j=0;
int k=0;
while(i<m_nTrs && j<B.m_nTrs){
if(m_pt[i]<B.m_pt[j]){
temp.m_pt[k].row=m_pt[i].row;
temp.m_pt[k].col=m_pt[i].col;
temp.m_pt[k].e=m_pt[i].e;
i++;
}
else{
if(m_pt[i]==B.m_pt[j]){
temp.m_pt[k].row=m_pt[i].row;
temp.m_pt[k].col=m_pt[i].col;
temp.m_pt[k].e=m_pt[i].e+B.m_pt[j].e;
i++; j++;
}
else{
temp.m_pt[k].row=B.m_pt[j].row;
temp.m_pt[k].col=B.m_pt[j].col;
temp.m_pt[k].e=B.m_pt[j].e;
j++;
}
}
k++;
}
while(i<m_nTrs){
temp.m_pt[k].row=m_pt[i].row;
temp.m_pt[k].col=m_pt[i].col;
temp.m_pt[k].e=m_pt[i].e;
i++;
k++;
}
while(j<B.m_nTrs){
temp.m_pt[k].row=B.m_pt[j].row;
temp.m_pt[k].col=B.m_pt[j].col;
temp.m_pt[k].e=B.m_pt[j].e;
j++;
k++;
}
temp.m_nTrs=k;
return temp;
}
5.22
void TSMatrix_Addto(TSMatrix &A,TSMatrix B)//将三元组矩阵B加到A上
{
for(i=1;i<=A.tu;i++)
A.data[MAXSIZE-A.tu+i]=A.data[i];/把A的所有元素都移到尾部以腾出位置
pa=MAXSIZE-A.tu+1;pb=1;pc=1;
for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法
{
while(A.data[pa].i<x) pa++;
while(B.data[pb].i<x) pb++;
while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素
{
if(A.data[pa].j==B.data[pb].j)
{
ne=A.data[pa].e+B.data[pb].e;
if(ne) //和不为0
{
A.data[pc].i=x;
A.data[pc].j=A.data[pa].j;
A.data[pc].e=ne;
pa++;pb++;pc++;
}
}//if
else if(A.data[pa].j>B.data[pb].j)
{
A.data[pc].i=x;
A.data[pc].j=B.data[pb].j;
A.data[pc].e=B.data[pb].e;
pb++;pc++;
}
else
{
A.data[pc].i=x;
A.data[pc].j=A.data[pa].j;
A.data[pc].e=A.data[pa].e
pa++;pc++;
}
}//while
while(A.data[pa]==x) //插入A中剩余的元素(第x行)
{
A.data[pc].i=x;
A.data[pc].j=A.data[pa].j;
A.data[pc].e=A.data[pa].e
pa++;pc++;
}
while(B.data[pb]==x) //插入B中剩余的元素(第x行)
{
A.data[pc].i=x;
A.data[pc].j=B.data[pb].j;
A.data[pc].e=B.data[pb].e;
pb++;pc++;
}
}//for
A.tu=pc;
for(i=A.tu;i<MAXSIZE;i++) A.data[i]={0,0,0}; //清除原来的A中记录
}//TSMatrix_Addto
5.23 解：
#include<iostream.h>
#include<stdlib.h>
#define Max 128
typedef int ElemType;
typedef struct{
int col;
ElemType e;
}Twin;
class CSparseMat
{
public:
CSparseMat(){}
CSparseMat(int r,int c,int n);
virtual ~CSparseMat(){}
void ShowSparse(int i,int j);
Twin* m_pt; // 指向非零元的指针
int rpos[Max];
int m_nCol; // 矩阵列数
int m_nRow; // 矩阵行数
int m_nTws; // 非零元个数
};
CSparseMat::CSparseMat(int r, int c, int n)
{
m_nRow=r;
m_nCol=c;
m_nTws=n;
m_pt=new Twin[m_nTws];
if(!m_pt) return;
// 输入矩阵的所有二元组
int i;
for(i=0;i<m_nTws;i++){
cout<<“请输入非零元二元组的列标和值：”;
cin>>m_pt[i].col>>m_pt[i].e;
}
for(i=0;i<m_nRow;i++){
cout<<“请输入每行第一个非零元在二元组中的序号(没有输入-1)：”;
cin>>rpos[i]; // 该行没有非零元输入-1
}
}
void CSparseMat::ShowSparse(int i,int j)
{
if(i>m_nRow||j>m_nCol) return;
ElemType x=0;
int s,d;
if(i==m_nRow){
s=rpos[i];
d=m_nTws;
}
else{
s=rpos[i];
int m=1;
d=rpos[i+m];
while(d<0){
if(i+m<m_nRow){
m++;
d=rpos[i+m];
}
else
d=m_nTws;
}
}
if(s>=0){
int k=s;
while(k<d){
if(m_pt[k].col==j)
x=m_pt[k].e;
k++;
}
}
cout<<x<<endl;
}
int main()
{
CSparseMat A(3,3,5);
A.ShowSparse(2,1);
return 0;
}
5.24 解：
typedef struct{
int seq; //该元素在以行为主序排列时的序号
int e;
} SElem;
typedef struct{
SElem data[MAXSIZE];
int mu,nu,tu;
} SMatrix; //单下标二元组矩阵类型
Status SMatrix_Locate(SMatrix A,int i,int j,int &e)//求单下标二元组矩阵的元素A[i][j]的值e
{
s=i*A.nu+j+1;p=1;
while(A.data[p].seq<s) p++; //利用各元素seq值逐渐递增的特点
if(A.data[p].seq==s) //找到了元素A[i][j]
{
e=A.data[p].e;
return OK;
}
return ERROR;
}//SMatrix_Locate
5.25 解：
typedef enum{0,1} bool;
typedef struct{
int mu,nu;
int elem[MAXSIZE];
bool map[mu][nu];
} BMMatrix; //用位图表示的矩阵类型
void BMMatrix_Add(BMMatrix A,BMMatrix B,BMMatrix &C)//位图矩阵的加法
{
C.mu=A.mu;C.nu=A.nu;
pa=1;pb=1;pc=1;
for(i=0;i<A.mu;i++) //每一行的相加
for(j=0;j<A.nu;j++) //每一个元素的相加
{
if(A.map[i][j]&&B.map[i][j]&&(A.elem[pa]+B.elem[pb]))//结果不为0
{
C.elem[pc]=A.elem[pa]+B.elem[pb];
C.map[i][j]=1;
pa++;pb++;pc++;
}
else if(A.map[i][j]&&!B.map[i][j])
{
C.elem[pc]=A.elem[pa];
C.map[i][j]=1;
pa++;pc++;
}
else if(!A.map[i][j]&&B.map[i][j])
{
C.elem[pc]=B.elem[pb];
C.map[i][j]=1;
pb++;pc++;
}
}
}//BMMatrix_Add
5.26 解：
typedef int ElemType;
typedef struct OLNode{
int row;
int col;
ElemType e;
struct OLNode *right,*down;
}OLNode,*OLink;
class CCrossListMat
{
public:
OLink *RHead,*CHead; // 行与列指针向量的头指针
int m_nCol; // 矩阵列数
int m_nRow; // 矩阵行数
int m_nNum; // 非零元个数
public:
CCrossListMat(){}
CCrossListMat(int r,int c,int n);
virtual ~CCrossListMat(){}
void ShowMat(int i,int j);
};
CCrossListMat::CCrossListMat(int r, int c, int n)
{
m_nRow=r;
m_nCol=c;
m_nNum=n;
int i;
RHead=new OLink[m_nRow];
if(!RHead) exit(-2);
CHead=new OLink[m_nCol];
if(!CHead) exit(-2);
for(i=0;i<m_nRow;i++)
RHead[i]=NULL;
for(i=0;i<m_nCol;i++)
CHead[i]=NULL;
OLink p,q,qf;
for(i=0;i<m_nNum;i++){
p=new OLNode;
if(!p) exit(-2);
cout<<“请输入非零元的行标、列标和值：”;
cin>>p->row>>p->col>>p->e;
q=RHead[p->row];
if(!q){
RHead[p->row]=p;
p->right=NULL;
}
else{
qf=q;
while(q && q->col<p->col){
qf=q;
q=q->right;
}
p->right=qf->right;
qf->right=p;
}
q=CHead[p->col];
if(!q){
CHead[p->col]=p;
p->down=NULL;
}
else{
qf=q;
while(q && q->row<p->row){
qf=q;
q=q->down;
}
p->down=qf->down;
qf->down=p;
}
}
}
void CCrossListMat::ShowMat(int i,int j)
{
ElemType x=0;
OLink p;
p=RHead[i];
while(p && p->col!=j)
p=p->right;
if(p)
x=p->e;
cout<<x<<endl;
}
5.27 解：
#include<iostream.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct OLNode{
int row;
int col;
ElemType e;
struct OLNode *right,*down;
}OLNode,*OLink;
class CCrossListMat
{
public:
OLink *RHead,*CHead; // 行与列指针向量的头指针
int m_nCol; // 矩阵列数
int m_nRow; // 矩阵行数
int m_nNum; // 非零元个数
public:
CCrossListMat(){}
virtual ~CCrossListMat(){}
CCrossListMat(int r,int c,int n);
void Add(CCrossListMat B);
void ShowMat();
};
CCrossListMat::CCrossListMat(int r, int c, int n)
{
m_nRow=r;
m_nCol=c;
m_nNum=n;
int i;
RHead=new OLink[m_nRow];
if(!RHead) exit(-2);
CHead=new OLink[m_nCol];
if(!CHead) exit(-2);
for(i=0;i<m_nRow;i++)
RHead[i]=NULL;
for(i=0;i<m_nCol;i++)
CHead[i]=NULL;
OLink p,q,qf;
for(i=0;i<m_nNum;i++){
p=new OLNode;
if(!p) exit(-2);
cout<<“请输入非零元的行标、列标和值：”;
cin>>p->row>>p->col>>p->e;
q=RHead[p->row];
if(!q){
RHead[p->row]=p;
p->right=NULL;
}
else{
qf=q;
while(q && q->col<p->col){
qf=q;
q=q->right;
}
p->right=qf->right;
qf->right=p;
}
q=CHead[p->col];
if(!q){
CHead[p->col]=p;
p->down=NULL;
}
else{
qf=q;
while(q && q->row<p->row){
qf=q;
q=q->down;
}
p->down=qf->down;
qf->down=p;
}
}
}
void CCrossListMat::Add(CCrossListMat B)
{
int i,k=0;
OLink pa,pb;
OLink pre,p; // 按行插入
OLink qpre,q; // 按列插入
for(i=0;i<m_nRow;i++){
pa=RHead[i];
pb=B.RHead[i];
pre=NULL;
while(pb){
while(pa&&pa->col<pb->col){
pre=pa;
pa=pa->right;
}
if(pa&&pa->col==pb->col){
pa->e=pa->e+pb->e;
pb=pb->right;
pre=pa;
pa=pa->right;
}
else{
// 在A中插入一个新结点
p=new OLNode;
p->row=pb->row;
p->col=pb->col;
p->e=pb->e;
pb=pb->right;
if(!pre){
p->right=pa;
RHead[i]=p;
}
else{
p->right=pre;
pre->right=p;
}
// 处理列指针
qpre=NULL;
q=CHead[p->col];
while(q&&q->row<i){
qpre=q;
q=q->down;
}
if(!qpre){
p->down=q;
CHead[p->col]=p;
}
else{
p->down=pre;
pre->down;
}
k++;
}
} // end while(pb)
} // end for
m_nNum=m_nNum+k;
}
void CCrossListMat::ShowMat()
{
int i,j;
OLink p;
for(i=0;i<m_nRow;i++){
p=RHead[i];
for(j=0;j<m_nCol;j++){
if(p && p->row==i && p->col==j){
cout<<p->e<<” “;
p=p->right;
}
else
cout<<0<<” “;
}
cout<<endl;
}
}
int main()
{
CCrossListMat A(3,3,4),B(3,3,2);
A.Add(B);
A.ShowMat();
return 0;
}
以下是关于广义表算法涉及的描述及方法
#include “DSConst.h” // 常量定义头文件
#include “StrStat.h” // 字符串定义头文件
// 广义表数据结构声明
typedef char AtomType;
typedef enum{ATOM,LIST} ElemTag;
typedef struct GLNode{
ElemTag tag;
union{
AtomType atom;
struct GLNode *hp;
};
struct GLNode *tp;
}*GList;
// 将非空串Str分割成两部分，HStr为第一个，TStr为之后的子串
int StrDistrict(CString& Str,CString& HStr,CString& TStr)
{
int n,i,k;
CString s1;
CString s2(“,”), s3(“(“), s4(“)”); // 定义常量串
n=Str.StrLength();
i=1;
k=0;
while(i<=n && s1.StrCompare(s2) || k!=0){
s1=Str.SubString(i,1);
if(!s1.StrCompare(s3)) k++;
else if(!s1.StrCompare(s4)) k–;
i++;
}
if(i<=n){
HStr=Str.SubString(1,i-2);
TStr=Str.SubString(i,n-i+1);
}
else{
HStr=Str;
TStr.StrClear();
}
return OK;
}
// 用串s建立广义表L
int CreateGList(GList& L,CString& s)
{
CString Sub,HSub,TSub; // 子串，表头串，表尾串
if(s.StrEmpty()) L=NULL;
else{ // 非空串，建立广义表
L=new GLNode; // 开辟一个结点
if(!L) exit(OVERFLOW);
if(s.StrLength()>1){ // 如果串长大于1，说明是表结点
L->tag=LIST;
Sub=s.SubString(2,s.StrLength()-2); // 取括号内子串
if(!Sub.StrEmpty()){ // 建立子表
StrDistrict(Sub,HSub,TSub);
if(!HSub.StrEmpty()) // 表头不空
CreateGList(L->hp,HSub);
else L->hp=NULL;
if(!TSub.StrEmpty()) // 表尾不空
CreateGList(L->tp,TSub);
else L->tp=NULL;
}
else{ // 空表
L->hp=NULL;
L->tp=NULL;
}
}
else{ // 建立原子结点
L->tag=ATOM;
L->atom=s.GetStr()[0];
L->tp=NULL;
}
}
return OK;
}
// 显示广义表串
void ShowGList(GList &L)
{
if(L){
if(L->tag==LIST){
cout<<“(“;
if(L->hp)
ShowGList(L->hp);
if(L->tp){
cout<<“,”;
ShowGList(L->tp);
}
cout<<“)”;
}
else cout<<L->atom;
}
}
5.28解：
void MPList_PianDao(MPList &L)//对广义表存储结构的多元多项式求第一变元的偏导
{
for(p=L->hp->tp;p&&p->exp;pre=p,p=p->tp)
{
if(p->tag) Mul(p->hp,p->exp);
else p->coef*=p->exp; //把指数乘在本结点或其下属结点上
p->exp–;
}
pre->tp=NULL;
if(p) free (p); //删除可能存在的常数项
}//MPList_PianDao
void Mul(MPList &L,int x)//递归算法,对多元多项式L乘以x
{
for(p=L;p;p=p->tp)
{
if(!p->tag) p->coef*=x;
else Mul(p->hp,x);
}
}//Mul
5.29解：
void MPList_Add(MPList A,MPList B,MPList &C)//广义表存储结构的多项式相加的递归算法
{
C=(MPLNode*)malloc(sizeof(MPLNode));
if(!A->tag&&!B->tag) //原子项,可直接相加
{
C->coef=A->coef+B->coef;
if(!C->coef)
{
free(C);
C=NULL;
}
}//if
else if(A->tag&&B->tag) //两个多项式相加
{
p=A;q=B;pre=NULL;
while(p&&q)
{
if(p->exp==q->exp)
{
C=(MPLNode*)malloc(sizeof(MPLNode));
C->exp=p->exp;
MPList_Add(A->hp,B->hp,C->hp);
pre->tp=C;pre=C;
p=p->tp;q=q->tp;
}
else if(p->exp>q->exp)
{
C=(MPLNode*)malloc(sizeof(MPLNode));
C->exp=p->exp;
C->hp=A->hp;
pre->tp=C;pre=C;
p=p->tp;
}
else
{
C=(MPLNode*)malloc(sizeof(MPLNode));
C->exp=q->exp;
C->hp=B->hp;
pre->tp=C;pre=C;
q=q->tp;
}
}//while
while(p)
{
C=(MPLNode*)malloc(sizeof(MPLNode));
C->exp=p->exp;
C->hp=p->hp;
pre->tp=C;pre=C;
p=p->tp;
}
while(q)
{
C=(MPLNode*)malloc(sizeof(MPLNode));
C->exp=q->exp;
C->hp=q->hp;
pre->tp=C;pre=C;
q=q->tp;
} //将其同次项分别相加得到新的多项式,原理见第二章多项式相加一题
}//else if
else if(A->tag&&!B->tag) //多项式和常数项相加
{
x=B->coef;
for(p=A;p->tp->tp;p=p->tp);
if(p->tp->exp==0) p->tp->coef+=x; //当多项式中含有常数项时,加上常数项
if(!p->tp->coef)
{
free(p->tp);
p->tp=NULL;
}
else
{
q=(MPLNode*)malloc(sizeof(MPLNode));
q->coef=x;q->exp=0;
q->tag=0;q->tp=NULL;
p->tp=q;
} //否则新建常数项,下同
}//else if
else
{
x=A->coef;
for(p=B;p->tp->tp;p=p->tp);
if(p->tp->exp==0) p->tp->coef+=x;
if(!p->tp->coef)
{
free(p->tp);
p->tp=NULL;
}
else
{
q=(MPLNode*)malloc(sizeof(MPLNode));
q->coef=x;q->exp=0;
q->tag=0;q->tp=NULL;
p->tp=q;
}
}//else
}//MPList_Add
5.30 解：
// 求广义表深度的递归算法
int GListDepth(GList& L)
{
int Depth=0;
int HDepth,TDepth; // 表头深度，表尾深度
if(!L) return Depth; // 广义表不存在
if(L->tag==ATOM) return Depth; // 原子结点深度为0
else{
Depth++; // 表结点深度为1
HDepth=Depth+GListDepth(L->hp);
TDepth=Depth+GListDepth(L->tp);
return HDepth>TDepth?HDepth:TDepth;
}
}
5.31 解：
// 由广义表L复制广义表T
int CopyGList(GList& T,GList& L)
{
if(!L) T=NULL;
else{
T=new GLNode;
if(!T) exit(OVERFLOW);
T->tag=L->tag;
if(L->tag==ATOM) T->atom=L->atom;
else{
CopyGList(T->hp,L->hp);
CopyGList(T->tp,L->tp);
}
}
return OK;
}
5.32 解：
// 判两广义表是否相等，相等返回OK，否则返回FALSE
Status GListCompare(GList& L1,GList& L2)
{
if(!L1 && !L2) return OK; // L1和L2均为空表
if((!L1 && L2) || (L1 && !L2)) return FALSE;
else{ // L1和L2均非空表
if(L1->tag==L2->tag){ // 表属性相同
if(L1->tag==ATOM){ // 均为原子结点
if(L1->atom==L2->atom) return OK;
else return FALSE;
}
else{ // 均为表结点
if(GListCompare(L1->hp,L2->hp) &&
GListCompare(L1->tp,L2->tp))
return OK; // 表头、表尾均相同
else return FALSE;
}
}
else return FALSE; // 表属性不同
}
}
5.33 解：
void GList_PrintElem(GList A,int layer)//递归输出广义表的原子及其所在层次,layer表示当前层次
{
if(!A) return;
if(!A->tag) printf(“%d %d\n”,A->atom,layer);
else
{
GList_PrintElem(A->ptr.hp,layer+1);
GList_PrintElem(A->ptr.tp,layer); //注意尾表与原表是同一层次
}
}//GList_PrintElem
5.34
void GList_Reverse(GList A)//递归逆转广义表A
{
GLNode *ptr[MAX_SIZE];
if(A->tag&&A->ptr.tp) //当A不为原子且表尾非空时才需逆转
{
for(i=0,p=A;p;p=p->ptr.tp,i++)
{
if(p->ptr.hp) GList_Reverse(p->ptr.hp); //逆转各子表
ptr[i]=p->ptr.hp;
}
for(p=A;p;p=p->ptr.tp) //重新按逆序排列各子表的顺序
p->ptr.hp=ptr[–i];
}
}//GList_Reverse
5.35
Status Create_GList(GList &L)//根据输入创建广义表L,并返回指针
{
scanf(“%c”,&ch);
if(ch==’ ‘)
{
L=NULL;
scanf(“%c”,&ch);
if(ch!=’)’) return ERROR;
return OK;
}
L=(GList)malloc(sizeof(GLNode));
L->tag=1;
if(isalphabet(ch)) //输入是字母
{
p=(GList)malloc(sizeof(GLNode)); //建原子型表头
p->tag=0;p->atom=ch;
L->ptr.hp=p;
}
else if(ch=='(‘) Create_GList(L->ptr.hp); //建子表型表头
else return ERROR;
scanf (“%c”,&ch);
if(ch==’)’) L->ptr.tp=NULL;
else if(ch==’,’) Create_GList(L->ptr.tp); //建表尾
else return ERROR;
return OK;
}//Create_GList
分析:本题思路见书后解答.
5.36
void GList_PrintList(GList A)//按标准形式输出广义表
{
if(!A) printf(“()”); //空表
else if(!A->tag) printf(“%d”,A->atom);//原子
else
{
printf(“(“);
for(p=A;p;p=p->ptr.tp)
{
GList_PrintList(p->ptr.hp);
if(p->ptr.tp) printf(“,”); //只有当表尾非空时才需要打印逗号
}
printf(“)”);
}//else
}//GList_PrintList
5.37
void GList_DelElem(GList &A,int x)//从广义表A中删除所有值为x的原子
{
if(A&&A->ptr.hp)
{
if(A->ptr.hp->tag) GList_DelElem(A->ptr.hp,x);
else if(!A->ptr.hp->tag&&A->ptr.hp->atom==x)
{
q=A;
A=A->ptr.tp; //删去元素值为x的表头
free(q);
GList_DelElem(A,x);
}
}
if(A&&A->ptr.tp) GList_DelElem(A->ptr.tp,x);
}//GList_DelElem
5.38
void GList_PrintElem_LOrder(GList A)//按层序输出广义表A中的所有元素
{
InitQueue(Q);
for(p=L;p;p=p->ptr.tp) EnQueue(Q,p);
while(!QueueEmpty(Q))
{
DeQueue(Q,r);
if(!r->tag) printf(“%d”,r->atom);
else
for(r=r->ptr.hp;r;r=r->ptr.tp) EnQueue(Q,r);
}//while
}//GList_PrintElem_LOrder
分析:层序遍历的问题,一般都是借助队列来完成的,每次从队头取出一个元素的同时把它下一层的孩子插入队尾.这是层序遍历的基本思想.
6章 树和二叉树
6.1 已知一棵树边的集合为{<I,M>, <I,N>, <E,I>, <B,E>, <B,D>, <A,B>, <G,J>, <G,K>, <C,G>, <C,F>, <A,C>}，请画出这棵树，并回答下列问题：
(1) 哪个是根结点？
(2) 哪些是叶子结点？
(3) 哪个是结点G的双亲？
(4) 哪些是结点G的祖先？
(5) 哪些是结点G的孩子？
(6) 哪些是结点E的子孙？
(7) 那些是结点E的子孙？
(8) 结点B和N的层次号分别是什么？
(9) 树的深度是多少？
(10) 以结点C为根的子树的深度是多少？
解：
6.2 一棵度为2的树与一棵二叉树有何区别？
解：二叉树是颗有序树，但度为2的树则未必有序。
6.3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
解：
6.4 一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序从1开始对全部结点编号，问：
(1) 各层的结点数目是多少？
(2) 编号为p的结点的父结点（若存在）的编号是多少？
(3) 编号为p的结点的第i个儿子结点（若存在）的编号是多少？
(4) 编号为p的结点有右兄弟的条件是什么？其右兄弟的编号是多少？
解：(1)
(2)如果p是其双亲的最小的孩子（右孩子），则p减去根结点的一个结点，应是k的整数倍，该整数即为所在的组数，每一组为一棵满k叉树，正好应为双亲结点的编号。如果p是其双亲的最大的孩子（左孩子），则p+k-1为其最小的弟弟，再减去一个根结点，除以k，即为其双亲结点的编号。
综合来说，对于p是左孩子的情况，i=(p+k-2)/k；对于p是右孩子的情况，i=(p-1)/k
如果左孩子的编号为p，则其右孩子编号必为p+k-1，所以，其双亲结点的编号为
向下取整，如1.5向下取整为1
(3)结点p的右孩子的编号为kp+1，左孩子的编号为kp+1-k+1=k(p-1)+2，第i个孩子的编号为k(p-1)+2+i-1=kp-k+i+1。
(4)当(p-1)%k != 0时，结点p有右兄弟，其右兄弟的编号为p+1。
6.5 已知一棵度为k的树中有个度为1的结点，个度为2的结点，…，个度为k的结点，问该树中有多少个叶子结点？
解：根据树的定义，在一颗树中，除树根结点外，每个结点有且仅有一个前驱结点，也就是说，每个结点与指向它的一个分支一一对应，所以除树根结点之外的结点树等于所有结点的分支数，即度数，从而可得树中的结点数等于所有结点的度数加1。总结点数为
而度为0的结点数就应为总结点数减去度不为0的结点数的总和，即
6.6 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点。试求该树含有的叶子节点数目。
解：利用上题结论易得结果。设度为k的结点个数为，则总结点数为。叶子结点的数目应等于总结点数减去度不为0的结点的数目，即
6.7 一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？
解：能达到最大深度的树是单支树，其深度为n。满k叉树的深度最小，其深度为
(证明见徐孝凯著数据结构实用教程P166)
6.8 证明：一棵满k叉树上的叶子结点数和非叶子结点数之间满足以下关系：
解：一棵满k叉树的最后一层(深度为h)的结点数(叶子结点数)为，其总结点数为，则非叶子结点数，从而得
6.9 试分别推导含有n个结点和含个叶子结点的完全三叉树的深度H。
解：(1) 根据完全三叉树的定义
(2) 设总的结点数为n，非叶子结点数为注意到每个非叶子结点的度均为3，则
由
6.10 对于那些所有非叶子结点均含有左右子数的二叉树：
(1) 试问：有n个叶子结点的树中共有多少个结点？
(2) 试证明：，其中n为叶子结点的个数，表示第i个叶子结点所在的层次（设根节点所在层次为1）。
解：（1）总结点数为，其中为非叶子结点数，则叶子结点数为，所以总结点数为 。
（2）用归纳法证明。
i=1，说明二叉树只有一个叶子结点，则整棵树只有一个根结点，,
，结论成立。
设有n个叶子结点时也成立，即，现假设增加一个叶子结点，这意味着在某叶子结点p上新生两个叶子结点，而结点p则成为非叶子结点，可见，总结点数增2，叶子结点数增1。此时，所有叶子结点是原结点除去p，然后加上两个深度为的新叶子结点，由此，
则当i=n+1时，也成立，由此即得到证明。
6.11 在二叉树的顺序存储结构中，实际上隐含着双亲的信息，因此可和三叉链表对应。假设每个指针域占4个字节，每个信息域占k个字节。试问：对于一棵有n个结点的二叉树，且在顺序存储结构中最后一个节点的下标为m，在什么条件下顺序存储结构比三叉链表更节省空间？
解：采用三叉链表结构，需要n(k+12)个字节的存储空间。采用顺序存储结构，需要mk个字节的存储空间，则当mk<n(k+12)时，即时，采用顺序存储比采用三叉链表更节省空间。
6.12 对题6.3所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。
解：
6.13 假设n和m为二叉树中两结点，用1、0或#（分别表示肯定、恰恰相反或不一定）填写下表：
|
问 已知 |
前序遍历时 |
中序遍历时 |
后序遍历时 |
|
n在m左方 |
|||
|
n在m右左方 |
|||
|
n是m祖先 |
|||
|
n是m子孙 |
注：如果(1)离a和b最近的共同祖先p存在，且(2)a在p的左子树中，b在p的右子树中，则称a在b的左方（即b在a的右方）。
解：
6.14 找出所有满足下列条件的二叉树：
(a) 它们在先序遍历和中序遍历时，得到的节点访问序列相同；
(b) 它们在后序遍历和中序遍历时，得到的结点访问序列相同；
(c) 它们在先序遍历和后序遍历时，得到的节点访问序列相同。
解：(a) 不含左子树的二叉树。
(b) 不含右子树的二叉树。
(c) 即不含左子树，也不含右子树的二叉树。
6.15 解：
6.16 解：1 2 3 4 5 6 7 8 9 10 11 12 13 14
|
Info |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N |
|
Ltag |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
Lchild |
2 |
4 |
6 |
2 |
7 |
3 |
10 |
14 |
12 |
13 |
13 |
9 |
10 |
11 |
|
Rtag |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|
Rchild |
3 |
5 |
6 |
5 |
8 |
9 |
11 |
3 |
12 |
13 |
14 |
0 |
11 |
8 |
6.17 解：其错误在于中序遍历应先访问其左子树，可做如下修改：
BiTree InSucc(BiTree q){
// 一直q是指向中序线索二叉树上某个结点的指针，
// 本函数返回指向*q的后继的指针。
r=q->rchild;
if(!r->ltag)
while(!r->ltag) r=r->lchild;
return r;
} // InSucc
6.18 解：如果p是根结点，则其后继为空。否则需查找p的双亲结点。从p结点开始中序线索遍历，如果某结点的左指针域等于p，说明该结点是p的双亲结点，且p是它的左孩子；如果某结点的右指针域等于p，说明该结点是p的双亲结点，且p是它的右孩子；如此即可确定访问次序。若是右孩子，其后继是双亲结点；若是左孩子，其后继是其兄弟最左下的子孙，如果兄弟不存在，其后继是其双亲结点。
6.19 分别画出和下列树对应的各个二叉树：
解：
6.20 解：
(1) 先序：1 2 3 4 5 6 8 7 9 10 11 12 13 15 14
(2) 中序：3 4 8 6 7 5 2 1 10 9 11 15 14 13 12
(3) 后序：8 7 6 5 4 3 2 10 15 14 13 12 11 9 1
6.23 解：树的先根序列为GFKDAIEBCHJ，后根序列为DIAEKFCJHBG，可以先转化成二叉树，再通过二叉树转换成树。注意二叉树的先根序列与等价树的先根序列相同，二叉树的中序序列对应着树的后根序列。
GFKDAIEBCHJ为所求二叉树的先序序列，DIAEKFCJHBG为二叉树的中序序列。通过观察先序序列，G为二叉树的根结点，再由中序序列，G的左子树序列为DIAEKFCJHB，右子为空。可以表示成如下形式：
G(DIAEKFCJHB，NULL)
对于子树先序序列为FKDAIEBCHJ，中序序列为DIAEKFCJHB，显然子树根为F。再由中序序列可以看到，F的左子树是DIAEK，右子树为CJHB。进一步表示成：
G(F(DIAEK,CJHB),NULL)
对于DIAEK（中序表示），先序为KDAIE，K为根，左子为DIAE，右子为空；对于CJHB，B为根，左子为CJH，右子为空。进一步表示成：
G(F(K(DIAE,NULL),B(CJH,NULL)),NULL)
G(F(K(D(NULL,IAE),NULL),B(C(NULL,JH),NULL)),NULL)
G(F(K(D(NULL,A(I,E)),NULL),B(C(NULL,H(J,NULL)),NULL)),NULL)
由此画出二叉树，进而画出树。
6.24 解：本题应注意下列转换：
树 森林 二叉树
先根 先序 先序
后根 中序 中序
6.25 解；用归纳法证明。
当n=2时，要使其成为最优二叉树，必须使两个结点都成为叶子结点。
设n=k时成立，则当n=k+1时，要使其成为最优，必须用k个结点的哈夫曼树与第k+1个结点组成一个新的最优二叉树，所以n=k+1时也成立。
6.26 解：不妨设这8个结点为A、B、C、D、E、F、G、H，其相应的权为7、19、2、6、32、3、21、10。
A:1101 B:01 C:11111 D:1110 E:10 F:11110 G:00 H:1100
采用这种方式编码，电文最短。
6.27 解：
6.33 解：
int Visit(int u,int v)
{
if(u==v) return 1;
if(L[v]==0){//左子树不存在
if(R[v]==0)//右子树也不存在
return 0;
else{// 右子树存在，继续访问右子树
if(Visit(u,R[v])) return 1;
else return 0;
}
}
else{// 左子树存在
if(Visit(u,L[v]))// 左子树中存在目标
return 1;
else{// 左子树中没有目标，需访问右子树
if(R[v]==0)// 没有右子树
return 0;
else{// 右子树存在，继续访问右子树
if(Visit(u,R[v])) return 1;
else return 0;
}
}
}
}
6.34 解：
int Visit(int u,int v)
{
int Nv;
Nv=NumElem(v); // 返回结点v的下标
if(Nv==-1) exit(-2); // 结点v不存在，退出
if(u==v) return 1;
if(L[Nv]==0){//左子树不存在
if(R[Nv]==0)//右子树也不存在
return 0;
else{// 右子树存在，继续访问右子树
if(Visit(u,R[Nv])) return 1;
else return 0;
}
}
else{// 左子树存在
if(Visit(u,L[Nv]))// 左子树中存在目标
return 1;
else{// 左子树中没有目标，需访问右子树
if(R[Nv]==0)// 没有右子树
return 0;
else{// 右子树存在，继续访问右子树
if(Visit(u,R[Nv])) return 1;
else return 0;
}
}
}
}
// 返回结点在数组T中的下标
int NumElem(int x)
{
int i=0;
while(i<N&&T[i]!=x) i++;
if(T[i]==x) return i;
else return -1;
}
6.35 解：
#define N 8
char T[N]={‘0′,’a’,’b’,’c’,’d’,’e’,’f’,’g’};
// 用顺序数组存储，0为头结点，
// a为根结点，b为左子树，c为右子树，…
// 若某结点编号为奇数，
// 则它必为其双亲的右孩子，否则为左孩子
// 编号为k的结点的双亲结点的编号为k/2
int NumTree(char c);// 求结点在树中的编号
int Exp(int a,int b);// 求a的b次方
int NumElem(char c);// 返回元素在数组中的下标
int main()
{
char c;
cout<<“请输入结点的值：”;
cin>>c;
cout<<NumTree(c)<<endl;
return 0;
}
int NumTree(char c)// 求结点在树中的编号
{
int k,i=0;
int Code[N];
k=NumElem(c); // 返回结点c的下标
if(k==-1) exit(-2); // 结点c不存在，退出
while(k){
// 如果k为偶数，记录一个代码1
if(k%2==1) Code[i]=1;
else Code[i]=0;
k=k/2;
i++;
}
int x=0,j;
for(j=0;j<i;j++)
x=x+Code[j]*Exp(2,j);
return x;
}
int Exp(int a,int b)
{
int i;
int x=1;
for(i=0;i<b;i++)
x=x*a;
return x;
}
// 返回结点在数组T中的下标
int NumElem(char c)
{
int i=0;
while(i<N&&T[i]!=c) i++;
if(T[i]==c) return i;
else return -1;
}
6.36 解：
Status SimilarTree(BiTree& T1,BiTree& T2)
{
if(!T1){// T1是空树
if(!T2) return TRUE;// T2是空树
else return FALSE;
}
else{// T1是非空树
if(!T2) return FALSE;
else{// T2是非空树
if(SimilarTree(T1->lchild,T2->lchild)
&& SimilarTree(T1->rchild,T2->rchild))
return TRUE;
else return FALSE;
}
}
}
6.37 解：
// 先序遍历的非递归算法
Status POTraverse(BiTree& T,Status (*Visit)(TElemType e))
{
BiTree p;
Stack s;
InitStack(s);
p=T;
while(p||!StackEmpty(s)){
if(p){
// 如果根指针不空，访问根结点，
// 右指针域压栈，继续遍历左子树
if(!Visit(p->data)) return ERROR;
Push(s,p->rchild);
p=p->lchild;
} // 根指针已空，本子树已遍历完毕，
// 退栈返回上一层，继续遍历未曾访问的结点
else Pop(s,p);
}
return OK;
}
6.38解：
typedef struct {
BTNode* ptr;
enum {0,1,2} mark;
} PMType; //有mark域的结点指针类型
void PostOrder_Stack(BiTree T)//后续遍历二叉树的非递归算法,用栈
{
PMType a;
InitStack(S); //S的元素为PMType类型
Push (S,{T,0}); //根结点入栈
while(!StackEmpty(S))
{
Pop(S,a);
switch(a.mark)
{
case 0:
Push(S,{a.ptr,1}); //修改mark域
if(a.ptr->lchild) Push(S,{a.ptr->lchild,0}); //访问左子树
break;
case 1:
Push(S,{a.ptr,2}); //修改mark域
if(a.ptr->rchild) Push(S,{a.ptr->rchild,0}); //访问右子树
break;
case 2:
visit(a.ptr); //访问结点,返回
}
}//while
}//PostOrder_Stack
分析:为了区分两次过栈的不同处理方式,在堆栈中增加一个mark域,mark=0表示刚刚访问此结点,mark=1表示左子树处理结束返回,mark=2表示右子树处理结束返回.每次根据栈顶元素的mark域值决定做何种动作.
6.39解：
typedef struct {
int data;
EBTNode *lchild;
EBTNode *rchild;
EBTNode *parent;
enum {0,1,2} mark;
} EBTNode,EBitree; //有mark域和双亲指针域的二叉树结点类型
void PostOrder_Nonrecursive(EBitree T)//后序遍历二叉树的非递归算法,不用栈
{
p=T;
while(p)
switch(p->mark)
{
case 0:
p->mark=1;
if(p->lchild) p=p->lchild; //访问左子树
break;
case 1:
p->mark=2;
if(p->rchild) p=p->rchild; //访问右子树
break;
case 2:
visit(p);
p->mark=0; //恢复mark值
p=p->parent; //返回双亲结点
}
}//PostOrder_Nonrecursive
分析:本题思路与上一题完全相同,只不过结点的mark值是储存在结点中的,而不是暂存在堆栈中,所以访问完毕后要将mark域恢复为0,以备下一次遍历.
6.40 解：
typedef struct {
int data;
PBTNode *lchild;
PBTNode *rchild;
PBTNode *parent;
} PBTNode,PBitree; //有双亲指针域的二叉树结点类型
void Inorder_Nonrecursive(PBitree T)//不设栈非递归遍历有双亲指针的二叉树
{
p=T;
while(p->lchild) p=p->lchild; //向左走到尽头
while(p)
{
visit(p);
if(p->rchild) //寻找中序后继:当有右子树时
{
p=p->rchild;
while(p->lchild) p=p->lchild; //后继就是在右子树中向左走到尽头
}
else if(p->parent->lchild==p) p=p->parent; //当自己是双亲的左孩子时后继就是双亲
else
{
p=p->parent;
while(p->parent&&p->parent->rchild==p) p=p->parent;
p=p->parent;
} //当自己是双亲的右孩子时后继就是向上返回直到遇到自己是在其左子树中的祖先
}//while
}//Inorder_Nonrecursive
6.41 解：
// 求位于先序序列中第k个位置的结点的值，
// e中存放结点的返回值，i为计数器
Status PONodeK(TElemType& e,int& i,int k,BiTree& T)
{
if(T){
i++;
if(i==k) e=T->data;
else{
PONodeK(e,i,k,T->lchild);
PONodeK(e,i,k,T->rchild);
}
}
return OK;
}
6.42 解：
// 求二叉树中叶子结点的数目
Status POLeafNodeNum(int& i,BiTree& T)
{
if(T){
if(!T->lchild && !T->rchild) i++;
POLeafNodeNum(i,T->lchild);
POLeafNodeNum(i,T->rchild);
}
return OK;
}
6.43 解：
// 按先序交换二叉树的左右子树
Status ExchangeBiTree(BiTree& T)
{
BiTree p;
if(T){
p=T->lchild;
T->lchild=T->rchild;
T->rchild=p;
ExchangeBiTree(T->lchild);
ExchangeBiTree(T->rchild);
}
return OK;
}
6.44 解：
// 求二叉树中以元素值为x的结点为根的子树的深度
Status ChildTreeDepth(BiTree& T,TElemType x,int& depth)
{
BiTree T1;
if(PreOrderLocate(T,x,T1)){
depth=BiTDepth(T1);
return OK;
}
else return ERROR;
}
// 按先序在树中查找根为x的子树，T1为指向子树根的指针
Status PreOrderLocate(BiTree& T,TElemType x,BiTree& T1)
{
if(T){
if(T->data==x){
T1=T;
return OK;
}
else{
if(PreOrderLocate(T->lchild,x,T1))
return OK;
else{
if(PreOrderLocate(T->rchild,x,T1))
return OK;
else return ERROR;
}
}
}
else return ERROR;
}
// 求二叉树的深度
int BiTDepth(BiTree& T)
{
int ldep,rdep;
if(!T) return 0;
else{
ldep=BiTDepth(T->lchild)+1;
rdep=BiTDepth(T->rchild)+1;
return ldep>rdep?ldep:rdep;
}
}
6.45 解：
// 删除以元素值为x的结点为根的子树
Status DelChildTree(BiTree& T,TElemType x)
{
if(T){
if(T->data==x){
DelBTree(T);
T=NULL;
return OK;
}
else{
if(DelChildTree(T->lchild,x))
return OK;
else{
if(DelChildTree(T->rchild,x))
return OK;
else return ERROR;
}
}
}
else return ERROR;
}
// 删除二叉树
Status DelBTree(BiTree& T)
{
if(T){
DelBTree(T->lchild);
DelBTree(T->rchild);
delete T;
return OK;
}
else return ERROR;
}
6.46 解：
// 复制一棵二叉树
Status CopyBiTree(BiTree& T,BiTree& T1)
{
BiTree p;
if(T){
p=new BiTNode;
if(!p) return ERROR;
p->data=T->data;
T1=p;
CopyBiTree(T->lchild,T1->lchild);
CopyBiTree(T->rchild,T1->rchild);
}
else{
T1=T;
}
return OK;
}
6.47 解：
typedef BiTree QElemType;
#include “c:\Yin\include\Queue.h”
Status LevelOrderTraverse(BiTree& T,Status (*Visit)(TElemType e))
{
QElemType p;
Queue q;
InitQueue(q);
if(T) EnQueue(q,T);
while(!QueueEmpty(q)){
DeQueue(q,p);
Visit(p->data);
if(p->lchild) EnQueue(q,p->lchild);
if(p->rchild) EnQueue(q,p->rchild);
}
return OK;
}
6.48 解：
// 在二叉树T中求结点*p和*q的共同最小祖先e
Status MinComAncst(BiTree& T,TElemType& e,TElemType *p,TElemType *q)
{
if(!T) return ERROR;
BiTree T1,T2,pt=NULL;
if(!CopyBiTree(T,T1)) return ERROR;
if(!CopyBiTree(T,T2)) return ERROR;
if(!PathTree(T1,p))
return ERROR;// 求根结点到结点p的路径树T1
else ShowBiTree(T1);
cout<<endl;
if(!PathTree(T2,q))
return ERROR;// 求根结点到结点q的路径树T2
else ShowBiTree(T2);
cout<<endl;
while(T1 && T2 && T1->data==T2->data){
pt=T1;
if(T1->lchild){
T1=T1->lchild;
T2=T2->lchild;
}
else{
if(T1->rchild){
T1=T1->rchild;
T2=T2->rchild;
}
}
}
if(!pt) return ERROR;
else{
e=pt->data;
return OK;
}
}
// 在二叉树T中求根到结点p的路径树，该操作将剪去除路径之外的所有分支
Status PathTree(BiTree& T,TElemType *p)
{
if(!T || !p) return ERROR;
if(T->data==*p){// 找到目标，删除目标的左右子树
if(T->lchild) DelBiTree(T->lchild);
if(T->rchild) DelBiTree(T->rchild);
return OK;
}
else{// 没找到目标，继续递归查找
if(PathTree(T->lchild,p)){// 目标在左子树中，删除右子树
if(T->rchild) DelBiTree(T->rchild);
return OK;
}
else
if(PathTree(T->rchild,p)){// 目标在右子树中，删除左子树
if(T->lchild) DelBiTree(T->lchild);
return OK;
}
else return ERROR;// 找不到目标
}
}
6.49 解：
Status CompleteBiTree(BiTree& T)
{
int d;
if(T){
d=BiTDepth(T->lchild)-BiTDepth(T->rchild);
if(d<0 || d>1) return ERROR;
else{
if(CompleteBiTree(T->lchild) &&
CompleteBiTree(T->rchild)) return OK;
else return ERROR;
}
}
else return OK;
}
6.50解：
Status CreateBitree_Triplet(Bitree &T)//输入三元组建立二叉树
{
if(getchar()!=’^’) return ERROR;
T=(BTNode*)malloc(sizeof(BTNode));
p=T;p->data=getchar();
getchar(); //滤去多余字符
InitQueue(Q);
EnQueue(Q,T);
while((parent=getchar())!=’^’&&(child=getchar())&&(side=getchar()))
{
while(QueueHead(Q)!=parent&&!QueueEmpty(Q)) DeQueue(Q,e);
if(QueueEmpty(Q)) return ERROR; //未按层序输入
p=QueueHead(Q);
q=(BTNode*)malloc(sizeof(BTNode));
if(side==’L’) p->lchild=q;
else if(side==’R’) p->rchild=q;
else return ERROR; //格式不正确
q->data=child;
EnQueue(Q,q);
}
return OK;
}//CreateBitree_Triplet
6.51 解：
Status ShowBiTExpress(BiTree& T)
{
if(T){
if(T->lchild){
if(Low(T->lchild->data,T->data)){
cout<<‘(‘;
ShowBiTExpress(T->lchild);
cout<<‘)’;
}
else ShowBiTExpress(T->lchild);
}
cout<<T->data;
if(T->rchild){
if(Low(T->rchild->data,T->data)){
cout<<‘(‘;
ShowBiTExpress(T->rchild);
cout<<‘)’;
}
else ShowBiTExpress(T->rchild);
}
}
return OK;
}
Status Low(char a,char b)
{
if((a==’+’ || a==’-‘) && (b==’*’ || b==’/’)) return TRUE;
else return FALSE;
}
6．52 解：
int BiTreeThrive(BiTree& T)
{
int i,d,nn[20];
d=BiTDepth(T);
BiTree p=T;
Stack s1,s2;
InitStack(s1); InitStack(s2);
for(i=0;i<20;i++){
nn[i]=0; // 每层结点个数
}
if(p) Push(s1,p);
else return 0;
for(i=0;i<d;i++){
if(!StackEmpty(s1) && StackEmpty(s2)){
while(!StackEmpty(s1)){
Pop(s1,p); nn[i]++;// s1中存放第i层的结点
if(p->lchild) Push(s2,p->lchild);//s2中存放第i+1层结点
if(p->rchild) Push(s2,p->rchild);
}
}
else{
if(StackEmpty(s1) && !StackEmpty(s2)){
while(!StackEmpty(s2)){
Pop(s2,p); nn[i]++;
if(p->lchild) Push(s1,p->lchild);
if(p->rchild) Push(s1,p->rchild);
}
}
}
}
int max=nn[0];
for(i=0;i<d;i++)
if(max<nn[i]) max=nn[i];
return max*d;
}
6.53 解：
// 所有从根到叶子最长路径树
Status MaxPathBiTree(BiTree& T)
{
if(T){
if(BiTDepth(T)-BiTDepth(T->lchild)!=1)
DelBiTree(T->lchild);
else
MaxPathBiTree(T->lchild);
if(BiTDepth(T)-BiTDepth(T->rchild)!=1)
DelBiTree(T->rchild);
else
MaxPathBiTree(T->rchild);
}
return OK;
}
// 从根到叶子最长路径中最左方的路径树
Status LMaxPathBiTree(BiTree& T)
{
if(T){
if(BiTDepth(T)-BiTDepth(T->lchild)==1){
DelBiTree(T->rchild);
LMaxPathBiTree(T->lchild);
}
else{
DelBiTree(T->lchild);
if(BiTDepth(T)-BiTDepth(T->rchild)==1)
LMaxPathBiTree(T->rchild);
else
DelBiTree(T->rchild);
}
}
return OK;
}
6.54 解：
// 根据完全二叉顺序树创建完全二叉链表树
Status CreateCompleteBiTree(SqList<TElemType>& ST,BiTree& LT)
{
BiTree p;
int i=0,len;
if(ST.Length==0) return OK;
p=new BiTNode;
if(!p) return ERROR;
p->data=ST.Get(i);
p->lchild=NULL;
p->rchild=NULL;
LT=p;
Queue q;
InitQueue(q);
EnQueue(q,p);
len=ST.Length();
while(!QueueEmpty(q)&&i<len-1){
DeQueue(q,p);
if(i<len-1 && i%2==0){
p->lchild=new BiTNode;
if(!p->lchild) return ERROR;
p->lchild->data=ST.Get(++i);
p->lchild->lchild=NULL;
p->lchild->rchild=NULL;
EnQueue(q,p->lchild);
}
if(i<len-1 && i%2==1){
p->rchild=new BiTNode;
if(!p->rchild) return ERROR;
p->rchild->data=ST.Get(++i);
p->rchild->lchild=NULL;
p->rchild->rchild=NULL;
EnQueue(q,p->rchild);
}
}
return OK;
}
6.55 解：
Status PreOrderTraverse(BiTree& T)
{
if(T){
T->DescNum=DescendNum(T);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
return OK;
}
int DescendNum(BiTree& T)
{
if(!T) return 0;
if(!T->lchild){
if(!T->rchild) return 0;
else return DescendNum(T->rchild)+1;
}
else{
if(!T->rchild) return DescendNum(T->lchild)+1;
else return DescendNum(T->rchild)+DescendNum(T->lchild)+2;
}
}
6.56 解：
先对二叉树T进行先序线索，得到先序线索二叉树Thrt。然后再进行查找。
// 先序线索二叉树算法
Status PreOrderThreading(BiThrTree& Thrt,BiThrTree& T)
{
BiThrTree pre;
Thrt=new BiThrNode; // 为线索二叉树建立头结点
if(!Thrt) exit(OVERFLOW);
Thrt->LTag=Thread;
Thrt->RTag=Link;
Thrt->lchild=Thrt;// 左子树回指
if(!T) Thrt->rchild=Thrt;// 若二叉树空，右子树回指
else{
Thrt->rchild=T;
pre=Thrt;
PreThreading(T,pre); // 先序遍历进行先序线索化
pre->rchild=Thrt; // 最后一个结点线索化
pre->RTag=Thread;
Thrt->lchild=pre;
}
return OK;
}
Status PreThreading(BiThrTree& T,BiThrTree& pre)
{
if(T){
if(!T->lchild){
T->LTag=Thread;
T->lchild=pre;
}
if(pre && !pre->rchild){
pre->RTag=Thread;
pre->rchild=T;
}
pre=T;
if(T->LTag==Link) PreThreading(T->lchild,pre);
if(T->RTag==Link) PreThreading(T->rchild,pre);
}
return OK;
}
// 从二叉线索树上任一结点q开始查找结点*p。
// 如果找到，将*p的后继结点指针存于q中，返回TRUE；否则返回FALSE
Status FindNextInBiThrTree(BiThrTree& q,TElemType *p)
{
BiThrTree pt=q;
if(!pt) return FALSE;
if(pt->data==*p){
if(pt->LTag==Link) q=pt->lchild;
else q=pt->rchild;
return OK;
}
pt=q->rchild;
while(pt!=q && pt->data!=*p){
if(pt->LTag==Link) pt=pt->lchild;
else pt=pt->rchild;
}
if(pt==q) return FALSE;
if(pt->data==*p){
if(pt->LTag==Link) q=pt->lchild;
else q=pt->rchild;
}
return OK;
}
6.57 解：
Status PostOrderThreading(BiThrTree& T,BiThrTree& pre);//首先建立后序线索树
Status FindNextInBiThrTree(BiThrTree& q,TElemType *p);//再进行查找
// 后序线索二叉树的算法
Status PostOrderThreading(BiThrTree& Thrt,BiThrTree& T)
{
BiThrTree pre;
Thrt=new BiThrNode; // 为线索二叉树建立头结点
if(!Thrt) exit(OVERFLOW);
Thrt->LTag=Link;
Thrt->RTag=Thread;
Thrt->rchild=Thrt;// 右子树回指
if(!T) Thrt->lchild=Thrt;// 若二叉树空，左子树回指
else{
Thrt->lchild=T;
pre=Thrt;
PostThreading(T,pre); // 后序遍历进行后序线索化
pre->rchild=Thrt;// 最后一个结点线索化
pre->RTag=Thread;
Thrt->rchild=pre;
}
return OK;
}
Status PostThreading(BiThrTree& T,BiThrTree& pre)
{
if(T){
if(T->LTag==Link) PostThreading(T->lchild,pre);
if(T->RTag==Link) PostThreading(T->rchild,pre);
if(!T->lchild){
T->LTag=Thread;
T->lchild=pre;
}
if(pre && !pre->rchild){
pre->RTag=Thread;
pre->rchild=T;
}
pre=T;
}
return OK;
}
6.58 解：
typedef char TElemType;
typedef struct CSNode{
TElemType data;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
// 建立树的二叉链表表示
Status CreateTree(CSTree& T)
{
char ch;
cout<<“输入结点的值(一个字符，’@’表示空树)”;
cin>>ch;
if(ch==’@’){
T=NULL;
}
else{
T=new CSNode;
if(!T) return ERROR;
T->data=ch;
CreateTree(T->firstchild);
CreateTree(T->nextsibling);
}
return OK;
}
// 输出树的各边
Status ShowTree(CSTree& T,CSTree& Father)
{
if(T && Father)
cout<<“(“<<Father->data<<“,”<<T->data<<“)”;
if(T->firstchild) ShowTree(T->firstchild,T);
if(T->nextsibling) ShowTree(T->nextsibling,Father);
return OK;
}
6.59解：
void Print_CSTree(CSTree T)//输出孩子兄弟链表表示的树T的各边
{
for(child=T->firstchild;child;child=child->nextsib)
{
printf(“(%c,%c),”,T->data,child->data);
Print_CSTree(child);
}
}//Print_CSTree
6.60 解：
int LeafNum(CSTree& T)
{
if(T){
if(!T->firstchild)
return 1+LeafNum(T->nextsibling);
else
return LeafNum(T->firstchild)+LeafNum(T->nextsibling);
}
else return 0;
}
6.61 解：
int DegreeNum(CSTree& T)
{
int d,dl,dr;
if(T){
if(!T->firstchild) d=0;
else d=1+RSiblingNum(T->firstchild);
dl=DegreeNum(T->firstchild);
dr=DegreeNum(T->nextsibling);
return Max(d,dl,dr); // 三数中求最大者
}
else return 0;
}
// 返回当前结点的兄弟数
int RSiblingNum(CSTree& T)
{
int i=0;
while(T->nextsibling){
i++;
T=T->nextsibling;
}
return i;
}
6.62 解：
// 树的深度
int Depth(CSTree& T)
{
int d1,d2;
if(T){
d1=1+Depth(T->firstchild);
d2=Depth(T->nextsibling);
return d1>d2?d1:d2;
}
else return 0;
}
6.63 解：
int GetDepth_CTree(CTree A)//求孩子链表表示的树A的深度
{
return SubDepth(A.r);
}//GetDepth_CTree
int SubDepth(int T)//求子树T的深度
{
if(!A.nodes[T].firstchild) return 1;
for(sd=1,p=A.nodes[T].firstchild;p;p=p->next)
if((d=SubDepth(p->child))>sd) sd=d;
return sd+1;
}//SubDepth
6.64解：
int GetDepth_PTree(PTree T)//求双亲表表示的树T的深度
{
maxdep=0;
for(i=0;i<T.n;i++)
{
dep=0;
for(j=i;j>=0;j=T.nodes[j].parent) dep++; //求每一个结点的深度
if(dep>maxdep) maxdep=dep;
}
return maxdep;
}//GetDepth_PTree
6.65解：
char Pred,Ind; //假设前序序列和中序序列已经分别储存在数组Pre和In中
Bitree Build_Sub(int Pre_Start,int Pre_End,int In_Start,int In_End)//由子树的前序和中序序列建立其二叉链表
{
sroot=(BTNode*)malloc(sizeof(BTNode)); //建根
sroot->data=Pre[Pre_Start];
for(i=In_Start;In[i]!=sroot->data;i++); //在中序序列中查找子树根
leftlen=i-In_Start;
rightlen=In_End-i; //计算左右子树的大小
if(leftlen)
{
lroot=Build_Sub(Pre_Start+1,Pre_Start+leftlen,In_Start,In_Start+leftlen-1);
sroot->lchild=lroot;
} //建左子树,注意参数表的计算
if(rightlen)
{
rroot=Build_Sub(Pre_End-rightlen+1,Pre_End,In_End-rightlen+1,In_End);
sroot->rchild=rroot;
} //建右子树,注意参数表的计算
return sroot; //返回子树根
}//Build_Sub
main()
{
…
Build_Sub(1,n,1,n); //初始调用参数,n为树结点总数
…
}
分析:本算法利用了这样一个性质,即一棵子树在前序和中序序列中所占的位置总是连续的.因此,就可以用起始下标和终止下标来确定一棵子树.Pre_Start,Pre_End,In_Start和In_End分别指示子树在前序子序列里的起始下标,终止下标,和在中序子序列里的起始和终止下标.
6.66解：
typedef struct{
CSNode *ptr;
CSNode *lastchild;
} NodeMsg; //结点的指针和其最后一个孩子的指针
Status Build_CSTree_PTree(PTree T)//由树T的双亲表构造其孩子兄弟链表
{
NodeMsg Tree[MAXSIZE];
for(i=0;i<T.n;i++)
{
Tree[i].ptr=(CSNode*)malloc(sizeof(CSNode));
Tree[i].ptr->data=T.node[i].data; //建结点
if(T.nodes[i].parent>=0) //不是树根
{
j=T.nodes[i].parent; //本算法要求双亲表必须是按层序存储
if(!(Tree[j].lastchild)) //双亲当前还没有孩子
Tree[j].ptr->firstchild=Tree[i].ptr; //成为双亲的第一个孩子
else //双亲已经有了孩子
Tree[j].lastchild->nextsib=Tree[i].ptr; //成为双亲最后一个孩子的下一个兄弟
Tree[j].lastchild=Tree[i].ptr; //成为双亲的最后一个孩子
}//if
}//for
}//Build_CSTree_PTree
6.67解：
typedef struct{
char data;
CSNode *ptr;
CSNode *lastchild;
} NodeInfo; //结点数据,结点指针和最后一个孩子的指针
Status CreateCSTree_Duplet(CSTree &T)//输入二元组建立树的孩子兄弟链表
{
NodeInfo Treed;
n=1;k=0;
if(getchar()!=’^’) return ERROR; //未按格式输入
if((c=getchar())==’^’) T=NULL; //空树
Tree[0].ptr=(CSNode*)malloc(sizeof(CSNode));
Tree[0].data=c;
Tree[0].ptr->data=c;
while((p=getchar())!=’^’&&(c=getchar())!=’^’)
{
Tree[n].ptr=(CSNode*)malloc(sizeof(CSNode));
Tree[n].data=c;
Tree[n].ptr->data=c;
for(k=0;Tree[k].data!=p;k++); //查找当前边的双亲结点
if(Tree[k].data!=p) return ERROR; //未找到:未按层序输入
r=Tree[k].ptr;
if(!r->firstchild)
r->firstchild=Tree[n].ptr;
else Tree[k].lastchild->nextsib=Tree[n].ptr;
Tree[k].lastchild=Tree[n].ptr; //这一段含义同上一题
n++;
}//while
return OK;
}//CreateCSTree_Duplet
6.68解：
Status CreateCSTree_Degree(char node[ ],int degree[ ])//由结点的层序序列和各结点的度构造树的孩子兄弟链表
{
CSNode * ptr[MAXSIZE]; //树结点指针的辅助存储
ptr[0]=(CSNode*)malloc(sizeof(CSNode));
i=0;k=1; //i为当前结点序号,k为当前孩子的序号
while(node[i])
{
ptr[i]->data=node[i];
d=degree[i];
if(d)
{
ptr[k]=(CSNode*)malloc(sizeof(CSNode)); //k为当前孩子的序号
ptr[i]->firstchild=ptr[k]; //建立i与第一个孩子k之间的联系
for(j=2;j<=d;j++)
{
ptr[k]=(CSNode*)malloc(sizeof(CSNode));
ptr[k-1]->nextsib=ptr[k]; //当结点的度大于1时,为其孩子建立兄弟链表
k++;
}//for
ptr[k-1]->nextsib=NULL;
}//if
i++;
}//while
}//CreateCSTree_Degree
6.69解：
void Print_BiTree(BiTree T,int i)//按树状打印输出二叉树的元素,i表示结点所在层次,初次调用时i=0
{
if(T->rchild) Print_BiTree(T->rchild,i+1);
for(j=1;j<=i;j++) printf(” “); //打印i个空格以表示出层次
printf(“%c\n”,T->data); //打印T元素,换行
if(T->lchild) Print_BiTree(T->rchild,i+1);
}//Print_BiTree
分析:该递归算法实际上是带层次信息的中序遍历,只不过按照题目要求,顺序为先右后左.
6.70解：
Status CreateBiTree_GList(BiTree &T)//由广义表形式的输入建立二叉链表
{
c=getchar();
if(c==’#’) T=NULL; //空子树
else
{
T=(CSNode*)malloc(sizeof(CSNode));
T->data=c;
if(getchar()!='(‘) return ERROR;
if(!CreateBiTree_GList(pl)) return ERROR;
T->lchild=pl;
if(getchar()!=’,’) return ERROR;
if(!CreateBiTree_GList(pr)) return ERROR;
T->rchild=pr;
if(getchar()!=’)’) return ERROR; //这些语句是为了保证输入符合A(B,C)的格式
}
return OK;
}//CreateBiTree_GList
6.71解：
void Print_CSTree(CSTree T,int i)//按凹入表形式打印输出树的元素,i表示结点所在层次,初次调用时i=0
{
for(j=1;j<=i;j++) printf(” “); //留出i个空格以表现出层次
printf(“%c\n”,T->data); //打印元素,换行
for(p=T->firstchild;p;p=p->nextsib)
Print_CSTree(p,i+1); //打印子树
}//Print_CSTree
6.72解：
void Print_CTree(int e,int i)//按凹入表形式打印输出树的元素,i表示结点所在层次
{
for(j=1;j<=i;j++) printf(” “); //留出i个空格以表现出层次
printf(“%c\n”,T.nodes[e].data); //打印元素,换行
for(p=T.nodes[e].firstchild;p;p=p->next)
Print_CSTree(p->child,i+1); //打印子树
}//Print_CSTree
main()
{
…
Print_CTree(T.r,0); //初次调用时i=0
…
}//main
6.73解：
char c; //全局变量,指示当前字符
Status CreateCSTree_GList(CSTree &T)//由广义表形式的输入建立孩子兄弟链表
{
c=getchar();
T=(CSNode*)malloc(sizeof(CSNode));
T->data=c;
if((c=getchar())=='(‘) //非叶结点
{
if(!CreateCSTree_GList(fc)) return ERROR; //建第一个孩子
T->firstchild=fc;
for(p=fc;c==’,’;p->nextsib=nc,p=nc) //建兄弟链
if(!CreateCSTree_GList(nc)) return ERROR;
p->nextsib=NULL;
if((c=getchar())!=’)’) return ERROR; //括号不配对
}
else T->firtchild=NULL; //叶子结点
return OK;
}//CreateBiTree_GList
分析:书后给出了两个间接递归的算法,事实上合成一个算法在形式上可能更好一些.本算法另一个改进之处在于加入了广义表格式是否合法的判断.
6.74解：
void PrintGlist_CSTree(CSTree T)//按广义表形式输出孩子兄弟链表表示的树
{
printf(“%c”,T->data);
if(T->firstchild) //非叶结点
{
printf(“(“);
for(p=T->firstchild;p;p=p->nextsib)
{
PrintGlist_CSTree(p);
if(p->nextsib) printf(“,”); //最后一个孩子后面不需要加逗号
}
printf(“)”);
}//if
}//PrintGlist_CSTree
6.75解：
char c;
int pos=0; //pos是全局变量,指示已经分配到了哪个结点
Status CreateCTree_GList(CTree &T,int &i)//由广义表形式的输入建立孩子链表
{
c=getchar();
T.nodes[pos].data=c;
i=pos++; //i是局部变量,指示当前正在处理的子树根
if((c=getchar())=='(‘) //非叶结点
{
CreateCTree_GList();
p=(CTBox*)malloc(sizeof(CTBox));
T.nodes[i].firstchild=p;
p->child=pos; //建立孩子链的头
for(;c==’,’;p=p->next) //建立孩子链
{
CreateCTree_GList(T,j); //用j返回分配得到的子树根位置
p->child=j;
p->next=(CTBox*)malloc(sizeof(CTBox));
}
p->next=NULL;
if((c=getchar())!=’)’) return ERROR; //括号不配对
}//if
else T.nodes[i].firtchild=NULL; //叶子结点
return OK;
}//CreateBiTree_GList
分析:该算法中,pos变量起着”分配”结点在表中的位置的作用,是按先序序列从上向下分配,因此树根T.r一定等于0,而最终的pos值就是结点数T.n.
6.76解：
void PrintGList_CTree(CTree T,int i)//按广义表形式输出孩子链表表示的树
{
printf(“%c”,T.nodes[i].data);
if(T.nodes[i].firstchild) //非叶结点
{
printf(“(“);
for(p=T->firstchild;p;p=p->nextsib)
{
PrintGlist_CSTree(T,p->child);
if(p->nextsib) printf(“,”); //最后一个孩子后面不需要加逗号
}
printf(“)”);
}//if
}//PrintGlist_CTree
第7章 图
7.1 解：(1) ID(1)=3 OD(1)=0
ID(2)=2 OD(2)=2
ID(3)=1 OD(3)=2
ID(4)=1 OD(4)=3
ID(5)=2 OD(5)=1
ID(6)=2 OD(6)=3
(2) 0 0 0 0 0 0
1 0 0 1 0 0
0 1 0 0 0 1
0 0 1 0 1 1
1 0 0 0 0 0
1 1 0 0 1 0
(3)
(4)
(5) 有三个连通分量1、5、2346
7.2 解：k=1，说明了各结点之间的相互连通关系；k=2说明了结点之间按路径长度为2的相互连通关系；…。
7.3 解：邻接表：
邻接多重表：
深度优先搜索的顺序为 1 5 6 4 3 2
广度优先搜索的顺序为 1 5 6 3 2 4， 15 16 13 12 24
7.14 解：
Status CreateAG(ALGraph &G)
{
int n,e,k,i,j;
cout<<“请输入顶点数：”;
cin>>n;
cout<<“请输入边数：”;
cin>>e;
G.vernum=n;
G.arcnum=e;
// 建立顶点数组
for(k=0;k<G.vernum;k++){
cout<<“请输入顶点信息：”;
cin>>G.vertices[k].data;
G.vertices[k].firstarc=NULL;
}
// 建立邻接表
VertexType v1,v2;
ArcNode *p,*q;
for(k=0;k<G.arcnum;k++){
cout<<“请输入弧的始点和终点信息，中间用空格分开:”;
cin>>v1>>v2;
i=LocateVex(G,v1);
if(i<0 || i>G.vernum-1) return ERROR;
j=LocateVex(G,v2);
if(j<0 || j>G.vernum-1) return ERROR;
if(i==j) return ERROR;
p=new ArcNode;
if(!p) return ERROR;
p->adjvex=j;
p->nextarc=NULL;
q=G.vertices[i].firstarc;
if(!q) G.vertices[i].firstarc=p;
else{
while(q->nextarc) q=q->nextarc; // 指针定位于邻接表的尾结点
q->nextarc=p;
}
}
return OK;
}
int LocateVex(ALGraph& G,VertexType v)
{
int i=0;
while(G.vertices[i].data!=v&&i<G.vernum) i++;
if(G.vertices[i].data==v) return i;
else return -1;
}
7.15 解：
//本题中的图G均为有向无权图,其余情况容易由此写出
Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v
{
if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE;
G.vexs[++G.vexnum]=v;
return OK;
}//Insert_Vex
Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
if(i==j) return ERROR;
if(!G.arcs[i][j].adj)
{
G.arcs[i][j].adj=1;
G.arcnum++;
}
return OK;
}//Insert_Arc
Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上删除顶点v
{
n=G.vexnum;
if((m=LocateVex(G,v))<0) return ERROR;
G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点
for(i=0;i<n;i++)
{
G.arcs[i][m]=G.arcs[i][n];
G.arcs[m][i]=G.arcs[n][i]; //将边的关系随之交换
}
G.arcs[m][m].adj=0;
G.vexnum–;
return OK;
}//Delete_Vex
分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加.
Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
if(G.arcs[i][j].adj)
{
G.arcs[i][j].adj=0;
G.arcnum–;
}
return OK;
}//Delete_Arc
7.16
//为节省篇幅,本题只给出Insert_Arc算法.其余算法请自行写出.
Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;p->nextarc=NULL;
if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p;
else
{
for(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc)
if(q->adjvex==j) return ERROR; //边已经存在
q->nextarc=p;
}
G.arcnum++;
return OK;
}//Insert_Arc
7.17
//为节省篇幅,本题只给出较为复杂的Delete_Vex算法.其余算法请自行写出.
Status Delete_Vex(OLGraph &G,char v)//在十字链表表示的图G上删除顶点v
{
if((m=LocateVex(G,v))<0) return ERROR;
n=G.vexnum;
for(i=0;i<n;i++) //删除所有以v为头的边
{
if(G.xlist[i].firstin->tailvex==m) //如果待删除的边是头链上的第一个结点
{
q=G.xlist[i].firstin;
G.xlist[i].firstin=q->hlink;
free(q);G.arcnum–;
}
else //否则
{
for(p=G.xlist[i].firstin;p&&p->hlink->tailvex!=m;p=p->hlink);
if(p)
{
q=p->hlink;
p->hlink=q->hlink;
free(q);G.arcnum–;
}
}//else
}//for
for(i=0;i<n;i++) //删除所有以v为尾的边
{
if(G.xlist[i].firstout->headvex==m) //如果待删除的边是尾链上的第一个结点
{
q=G.xlist[i].firstout;
G.xlist[i].firstout=q->tlink;
free(q);G.arcnum–;
}
else //否则
{
for(p=G.xlist[i].firstout;p&&p->tlink->headvex!=m;p=p->tlink);
if(p)
{
q=p->tlink;
p->tlink=q->tlink;
free(q);G.arcnum–;
}
}//else
}//for
for(i=m;i<n;i++) //顺次用结点m之后的顶点取代前一个顶点
{
G.xlist[i]=G.xlist[i+1]; //修改表头向量
for(p=G.xlist[i].firstin;p;p=p->hlink)
p->headvex–;
for(p=G.xlist[i].firstout;p;p=p->tlink)
p->tailvex–; //修改各链中的顶点序号
}
G.vexnum–;
return OK;
}//Delete_Vex
7.18
//为节省篇幅,本题只给出Delete_Arc算法.其余算法请自行写出.
Status Delete_Arc(AMLGraph &G,char v,char w)在邻接多重表表示的图G上删除边(v,w)
{
if((i=LocateVex(G,v))<0) return ERROR;
if((j=LocateVex(G,w))<0) return ERROR;
if(G.adjmulist[i].firstedge->jvex==j)
G.adjmulist[i].firstedge=G.adjmulist[i].firstedge->ilink;
else
{
for(p=G.adjmulist[i].firstedge;p&&p->ilink->jvex!=j;p=p->ilink);
if (!p) return ERROR; //未找到
p->ilink=p->ilink->ilink;
} //在i链表中删除该边
if(G.adjmulist[j].firstedge->ivex==i)
G.adjmulist[j].firstedge=G.adjmulist[j].firstedge->jlink;
else
{
for(p=G.adjmulist[j].firstedge;p&&p->jlink->ivex!=i;p=p->jlink);
if (!p) return ERROR; //未找到
q=p->jlink;
p->jlink=q->jlink;
free(q);
} //在i链表中删除该边
G.arcnum–;
return OK;
}//Delete_Arc
7.19
Status Build_AdjMulist(AMLGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表
{
InitAMLGraph(G);
scanf(“%d”,&v);
if(v<0) return ERROR; //顶点数不能为负
G.vexnum=v;
scanf(%d”,&a);
if(a<0) return ERROR; //边数不能为负
G.arcnum=a;
for(m=0;m<v;m++)
G.adjmulist[m].data=getchar(); //输入各顶点的符号
for(m=1;m<=a;m++)
{
t=getchar();h=getchar(); //t为弧尾,h为弧头
if((i=LocateVex(G,t))<0) return ERROR;
if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到
p=(EBox*)malloc(sizeof(EBox));
p->ivex=i;p->jvex=j;
p->ilink=NULL;p->jlink=NULL; //边结点赋初值
if(!G.adjmulist[i].firstedge) G.adjmulist[i].firstedge=p;
else
{
q=G.adjmulist[i].firstedge;
while(q)
{
r=q;
if(q->ivex==i) q=q->ilink;
else q=q->jlink;
}
if(r->ivex==i) r->ilink=p;//注意i值既可能出现在边结点的ivex域中,
else r->jlink=p; //又可能出现在边结点的jvex域中
}//else //插入i链表尾部
if(!G.adjmulist[j].firstedge) G.adjmulist[j].firstedge=p;
else
{
q=G.adjmulist[i].firstedge;
while(q)
{
r=q;
if(q->jvex==j) q=q->jlink;
else q=q->ilnk;
}
if(r->jvex==j) r->jlink=p;
else r->ilink=p;
}//else //插入j链表尾部
}//for
return OK;
}//Build_AdjList
7.20
int Pass_MGraph(MGraph G)//判断一个邻接矩阵存储的有向图是不是可传递的,是则返回1,否则返回0
{
for(x=0;x<G.vexnum;x++)
for(y=0;y<G.vexnum;y++)
if(G.arcs[x][y])
{
for(z=0;z<G.vexnum;z++)
if(z!=x&&G.arcs[y][z]&&!G.arcs[x][z]) return 0;//图不可传递的条件
}//if
return 1;
}//Pass_MGraph
分析:本算法的时间复杂度大概是O(n^2*d).
7.21
int Pass_ALGraph(ALGraph G)//判断一个邻接表存储的有向图是不是可传递的,是则返回1,否则返回0
{
for(x=0;x<G.vexnum;x++)
for(p=G.vertices[x].firstarc;p;p=p->nextarc)
{
y=p->adjvex;
for(q=G.vertices[y].firstarc;q;q=q->nextarc)
{
z=q->adjvex;
if(z!=x&&!is_adj(G,x,z)) return 0;
}//for
}//for
}//Pass_ALGraph
int is_adj(ALGraph G,int m,int n)//判断有向图G中是否存在边(m,n),是则返回1,否则返回0
{
for(p=G.vertices[m].firstarc;p;p=p->nextarc)
if(p->adjvex==n) return 1;
return 0;
}//is_adj
7.22
int visited[MAXSIZE]; //指示顶点是否在当前路径上
int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
if(i==j) return 1; //i就是j
else
{
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径
}//for
}//else
}//exist_path_DFS
7.23
int exist_path_BFS(ALGraph G,int i,int j)//广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0
{
int visited[MAXSIZE];
InitQueue(Q);
EnQueue(Q,i);
while(!QueueEmpty(Q))
{
DeQueue(Q,u);
visited[u]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(k==j) return 1;
if(!visited[k]) EnQueue(Q,k);
}//for
}//while
return 0;
}//exist_path_BFS
7.24
void STraverse_Nonrecursive(Graph G)//非递归遍历强连通图G
{
int visited[MAXSIZE];
InitStack(S);
Push(S,GetVex(S,1)); //将第一个顶点入栈
visit(1);
visited=1;
while(!StackEmpty(S))
{
while(Gettop(S,i)&&i)
{
j=FirstAdjVex(G,i);
if(j&&!visited[j])
{
visit(j);
visited[j]=1;
Push(S,j); //向左走到尽头
}
}//while
if(!StackEmpty(S))
{
Pop(S,j);
Gettop(S,i);
k=NextAdjVex(G,i,j); //向右走一步
if(k&&!visited[k])
{
visit(k);
visited[k]=1;
Push(S,k);
}
}//if
}//while
}//Straverse_Nonrecursive
分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37.由于是强连通图,所以从第一个结点出发一定能够访问到所有结点.
7.25
见书后解答.
7.26
Status TopoNo(ALGraph G)//按照题目要求顺序重排有向图中的顶点
{
int new[MAXSIZE],indegree[MAXSIZE]; //储存结点的新序号
n=G.vexnum;
FindInDegree(G,indegree);
InitStack(S);
for(i=1;i<G.vexnum;i++)
if(!indegree[i]) Push(S,i); //零入度结点入栈
count=0;
while(!StackEmpty(S))
{
Pop(S,i);
new[i]=n–; //记录结点的拓扑逆序序号
count++;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(!(–indegree[k])) Push(S,k);
}//for
}//while
if(count<G.vexnum) return ERROR; //图中存在环
for(i=1;i<=n;i++) printf(“Old No:%d New No:%d\n”,i,new[i])
return OK;
}//TopoNo
分析:只要按拓扑逆序对顶点编号,就可以使邻接矩阵成为下三角矩阵.
7.27
int visited[MAXSIZE];
int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径
{
if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求
else if(k>0)
{
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
l=p->adjvex;
if(!visited[l])
if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一
}//for
visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中
}//else
return 0; //没找到
}//exist_path_len
7.28
int path[MAXSIZE],visited[MAXSIZE]; //暂存遍历过程中的路径
int Find_All_Path(ALGraph G,int u,int v,int k)//求有向图G中顶点u到v之间的所有简单路径,k表示当前路径长度
{
path[k]=u; //加入当前路径中
visited[u]=1;
if(u==v) //找到了一条简单路径
{
printf(“Found one path!\n”);
for(i=0;path[i];i++) printf(“%d”,path[i]); //打印输出
}
else
for(p=G.vertices[u].firstarc;p;p=p->nextarc)
{
l=p->adjvex;
if(!visited[l]) Find_All_Path(G,l,v,k+1); //继续寻找
}
visited[u]=0;
path[k]=0; //回溯
}//Find_All_Path
main()
{
…
Find_All_Path(G,u,v,0); //在主函数中初次调用,k值应为0
…
}//main
7.29
int GetPathNum_Len(ALGraph G,int i,int j,int len)//求邻接表方式存储的有向图G的顶点i到j之间长度为len的简单路径条数
{
if(i==j&&len==0) return 1; //找到了一条路径,且长度符合要求
else if(len>0)
{
sum=0; //sum表示通过本结点的路径数
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
l=p->adjvex;
if(!visited[l])
sum+=GetPathNum_Len(G,l,j,len-1)//剩余路径长度减一
}//for
visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中
}//else
return sum;
}//GetPathNum_Len
7.30
int visited[MAXSIZE];
int path[MAXSIZE]; //暂存当前路径
int cycles[MAXSIZE][MAXSIZE]; //储存发现的回路所包含的结点
int thiscycle[MAXSIZE]; //储存当前发现的一个回路
int cycount=0; //已发现的回路个数
void GetAllCycle(ALGraph G)//求有向图中所有的简单回路
{
for(v=0;v<G.vexnum;v++) visited[v]=0;
for(v=0;v<G.vexnum;v++)
if(!visited[v]) DFS(G,v,0); //深度优先遍历
}//DFSTraverse
void DFS(ALGraph G,int v,int k)//k表示当前结点在路径上的序号
{
visited[v]=1;
path[k]=v; //记录当前路径
for(p=G.vertices[v].firstarc;p;p=p->nextarc)
{
w=p->adjvex;
if(!visited[w]) DFS(G,w,k+1);
else //发现了一条回路
{
for(i=0;path[i]!=w;i++); //找到回路的起点
for(j=0;path[i+j];i++) thiscycle[j]=path[i+j];//把回路复制下来
if(!exist_cycle()) cycles[cycount++]=thiscycle;//如果该回路尚未被记录过,就添加到记录中
for(i=0;i<G.vexnum;i++) thiscycle[i]=0; //清空目前回路数组
}//else
}//for
path[k]=0;
visited[k]=0; //注意只有当前路径上的结点visited为真.因此一旦遍历中发现当前结点visited为真,即表示发现了一条回路
}//DFS
int exist_cycle()//判断thiscycle数组中记录的回路在cycles的记录中是否已经存在
{
int temp[MAXSIZE];
for(i=0;i<cycount;i++) //判断已有的回路与thiscycle是否相同
{ //也就是,所有结点和它们的顺序都相同
j=0;c=thiscycle�; //例如,142857和857142是相同的回路
for(k=0;cycles[i][k]!=c&&cycles[i][k]!=0;k++);//在cycles的一个行向量中寻找等于thiscycle第一个结点的元素
if(cycles[i][k]) //有与之相同的一个元素
{
for(m=0;cycles[i][k+m];m++)
temp[m]=cycles[i][k+m];
for(n=0;n<k;n++,m++)
temp[m]=cycles[i][n]; //调整cycles中的当前记录的循环相位并放入temp数组中
if(!StrCompare(temp,thiscycle)) //与thiscycle比较
return 1; //完全相等
for(m=0;m<G.vexnum;m++) temp[m]=0; //清空这个数组
}
}//for
return 0; //所有现存回路都不与thiscycle完全相等
}//exist_cycle
分析:这个算法的思想是,在遍历中暂存当前路径,当遇到一个结点已经在路径之中时就表明存在一条回路;扫描路径向量path可以获得这条回路上的所有结点.把结点序列(例如,142857)存入thiscycle中;由于这种算法中,一条回路会被发现好几次,所以必须先判断该回路是否已经在cycles中被记录过,如果没有才能存入cycles的一个行向量中.把cycles的每一个行向量取出来与之比较.由于一条回路可能有多种存储顺序,比如142857等同于285714和571428,所以还要调整行向量的次序,并存入temp数组,例如,thiscycle为142857第一个结点为1,cycles的当前向量为857142,则找到后者中的1,把1后部分提到1前部分前面,最终在temp中得到142857,与thiscycle比较,发现相同,因此142857和857142是同一条回路,不予存储.这个算法太复杂,很难保证细节的准确性,大家理解思路便可.希望有人给出更加简捷的算法.
7.31
int visited[MAXSIZE];
int finished[MAXSIZE];
int count; //count在第一次深度优先遍历中用于指示finished数组的填充位置
void Get_SGraph(OLGraph G)//求十字链表结构储存的有向图G的强连通分量
{
count=0;
for(v=0;v<G.vexnum;v++) visited[v]=0;
for(v=0;v<G.vexnum;v++) //第一次深度优先遍历建立finished数组
if(!visited[v]) DFS1(G,v);
for(v=0;v<G.vexnum;v++) visited[v]=0; //清空visited数组
for(i=G.vexnum-1;i>=0;i–) //第二次逆向的深度优先遍历
{
v=finished(i);
if(!visited[v])
{
printf(“\n”); //不同的强连通分量在不同的行输出
DFS2(G,v);
}
}//for
}//Get_SGraph
void DFS1(OLGraph G,int v)//第一次深度优先遍历的算法
{
visited[v]=1;
for(p=G.xlist[v].firstout;p;p=p->tlink)
{
w=p->headvex;
if(!visited[w]) DFS1(G,w);
}//for
finished[++count]=v; //在第一次遍历中建立finished数组
}//DFS1
void DFS2(OLGraph G,int v)//第二次逆向的深度优先遍历的算法
{
visited[v]=1;
printf(“%d”,v); //在第二次遍历中输出结点序号
for(p=G.xlist[v].firstin;p;p=p->hlink)
{
w=p->tailvex;
if(!visited[w]) DFS2(G,w);
}//for
}//DFS2
分析:求有向图的强连通分量的算法的时间复杂度和深度优先遍历相同,也为O(n+e).
7.32
void Forest_Prim(ALGraph G,int k,CSTree &T)//从顶点k出发,构造邻接表结构的有向图G的最小生成森林T,用孩子兄弟链表存储
{
for(j=0;j<G.vexnum;j++) //以下在Prim算法基础上稍作改动
if(j!=k)
{
closedge[j]={k,Max_int};
for(p=G.vertices[j].firstarc;p;p=p->nextarc)
if(p->adjvex==k) closedge[j].lowcost=p->cost;
}//if
closedge[k].lowcost=0;
for(i=1;i<G.vexnum;i++)
{
k=minimum(closedge);
if(closedge[k].lowcost<Max_int)
{
Addto_Forest(T,closedge[k].adjvex,k); //把这条边加入生成森林中
closedge[k].lowcost=0;
for(p=G.vertices[k].firstarc;p;p=p->nextarc)
if(p->cost<closedge[p->adjvex].lowcost)
closedge[p->adjvex]={k,p->cost};
}//if
else Forest_Prim(G,k); //对另外一个连通分量执行算法
}//for
}//Forest_Prim
void Addto_Forest(CSTree &T,int i,int j)//把边(i,j)添加到孩子兄弟链表表示的树T中
{
p=Locate(T,i); //找到结点i对应的指针p,过程略
q=(CSTNode*)malloc(sizeof(CSTNode));
q->data=j;
if(!p) //起始顶点不属于森林中已有的任何一棵树
{
p=(CSTNode*)malloc(sizeof(CSTNode));
p->data=i;
for(r=T;r->nextsib;r=r->nextsib);
r->nextsib=p;
p->firstchild=q;
} //作为新树插入到最右侧
else if(!p->firstchild) //双亲还没有孩子
p->firstchild=q; //作为双亲的第一个孩子
else //双亲已经有了孩子
{
for(r=p->firstchild;r->nextsib;r=r->nextsib);
r->nextsib=q; //作为双亲最后一个孩子的兄弟
}
}//Addto_Forest
main()
{
…
T=(CSTNode*)malloc(sizeof(CSTNode)); //建立树根
T->data=1;
Forest_Prim(G,1,T);
…
}//main
分析:这个算法是在Prim算法的基础上添加了非连通图支持和孩子兄弟链表构建模块而得到的,其时间复杂度为O(n^2).
7.33
typedef struct {
int vex; //结点序号
int ecno; //结点所属的连通分量号
} VexInfo;
VexInfo vexs[MAXSIZE]; //记录结点所属连通分量号的数组
void Init_VexInfo(VexInfo &vexs[ ],int vexnum)//初始化
{
for(i=0;i<vexnum;i++)
vexs[i]={i,i}; //初始状态:每一个结点都属于不同的连通分量
}//Init_VexInfo
int is_ec(VexInfo vexs[ ],int i,int j)//判断顶点i和顶点j是否属于同一个连通分量
{
if(vexs[i].ecno==vexs[j].ecno) return 1;
else return 0;
}//is_ec
void merge_ec(VexInfo &vexs[ ],int ec1,int ec2)//合并连通分量ec1和ec2
{
for(i=0;vexs[i].vex;i++)
if(vexs[i].ecno==ec2) vexs[i].ecno==ec1;
}//merge_ec
void MinSpanTree_Kruscal(Graph G,EdgeSetType &EdgeSet,CSTree &T)//求图的最小生成树的克鲁斯卡尔算法
{
Init_VexInfo(vexs,G.vexnum);
ecnum=G.vexnum; //连通分量个数
while(ecnum>1)
{
GetMinEdge(EdgeSet,u,v); //选出最短边
if(!is_ec(vexs,u,v)) //u和v属于不同连通分量
{
Addto_CSTree(T,u,v); //加入到生成树中
merge_ec(vexs,vexs[u].ecno,vexs[v].ecno); //合并连通分量
ecnum–;
}
DelMinEdge(EdgeSet,u,v); //从边集中删除
}//while
}//MinSpanTree_Kruscal
void Addto_CSTree(CSTree &T,int i,int j)//把边(i,j)添加到孩子兄弟链表表示的树T中
{
p=Locate(T,i); //找到结点i对应的指针p,过程略
q=(CSTNode*)malloc(sizeof(CSTNode));
q->data=j;
if(!p->firstchild) //双亲还没有孩子
p->firstchild=q; //作为双亲的第一个孩子
else //双亲已经有了孩子
{
for(r=p->firstchild;r->nextsib;r=r->nextsib);
r->nextsib=q; //作为双亲最后一个孩子的兄弟
}
}//Addto_CSTree
分析:本算法使用一维结构体变量数组来表示等价类,每个连通分量所包含的所有结点属于一个等价类.在这个结构上实现了初始化,判断元素是否等价(两个结点是否属于同一个连通分量),合并等价类(连通分量)的操作.
7.34
Status TopoSeq(ALGraph G,int new[ ])//按照题目要求给有向无环图的结点重新编号,并存入数组new中
{
int indegree[MAXSIZE]; //本算法就是拓扑排序
FindIndegree(G,indegree);
Initstack(S);
for(i=0;i<G.vexnum;i++)
if(!indegree[i]) Push(S,i);
count=0;
while(!stackempty(S))
{
Pop(S,i);new[i]=++count; //把拓扑顺序存入数组的对应分量中
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
if(!(–indegree[k])) Push(S,k);
}
}//while
if(count<G.vexnum) return ERROR;
return OK;
}//TopoSeq
7.35
int visited[MAXSIZE];
void Get_Root(ALGraph G)//求有向无环图的根,如果有的话
{
for(v=0;v<G.vexnum;v++)
{
for(w=0;w<G.vexnum;w++) visited[w]=0;//每次都要将访问数组清零
DFS(G,v); //从顶点v出发进行深度优先遍历
for(flag=1,w=0;w<G.vexnum;w++)
if(!visited[w]) flag=0; //如果v是根,则深度优先遍历可以访问到所有结点
if(flag) printf(“Found a root vertex:%d\n”,v);
}//for
}//Get_Root,这个算法要求图中不能有环,否则会发生误判
void DFS(ALGraph G,int v)
{
visited[v]=1;
for(p=G.vertices[v].firstarc;p;p=p->nextarc)
{
w=p->adjvex;
if(!visited[w]) DFS(G,w);
}
}//DFS
7.36
void Fill_MPL(ALGraph &G)//为有向无环图G添加MPL域
{
FindIndegree(G,indegree);
for(i=0;i<G.vexnum;i++)
if(!indegree[i]) Get_MPL(G,i);//从每一个零入度顶点出发构建MPL域
}//Fill_MPL
int Get_MPL(ALGraph &G,int i)//从一个顶点出发构建MPL域并返回其MPL值
{
if(!G.vertices[i].firstarc)
{
G.vertices[i].MPL=0;
return 0; //零出度顶点
}
else
{
max=0;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
j=p->adjvex;
if(G.vertices[j].MPL==0) k=Get_MPL(G,j);
if(k>max) max=k; //求其直接后继顶点MPL的最大者
}
G.vertices[i]=max+1;//再加一,就是当前顶点的MPL
return max+1;
}//else
}//Get_MPL
7.37
int maxlen,path[MAXSIZE]; //数组path用于存储当前路径
int mlp[MAXSIZE]; //数组mlp用于存储已发现的最长路径
void Get_Longest_Path(ALGraph G)//求一个有向无环图中最长的路径
{
maxlen=0;
FindIndegree(G,indegree);
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++) visited[j]=0;
if(!indegree[i]) DFS(G,i,0);//从每一个零入度结点开始深度优先遍历
}
printf(“Longest Path:”);
for(i=0;mlp[i];i++) printf(“%d”,mlp[i]); //输出最长路径
}//Get_Longest_Path
void DFS(ALGraph G,int i,int len)
{
visited[i]=1;
path[len]=i;
if(len>maxlen&&!G.vertices[i].firstarc) //新的最长路径
{
for(j=0;j<=len;j++) mlp[j]=path[j]; //保存下来
maxlen=len;
}
else
{
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
j=p->adjvex;
if(!visited[j]) DFS(G,j,len+1);
}
}//else
path[i]=0;
visited[i]=0;
}//DFS
7.38
void NiBoLan_DAG(ALGraph G)//输出有向无环图形式表示的表达式的逆波兰式
{
FindIndegree(G,indegree);
for(i=0;i<G.vexnum;i++)
if(!indegree[i]) r=i; //找到有向无环图的根
PrintNiBoLan_DAG(G,i);
}//NiBoLan_DAG
void PrintNiBoLan_DAG(ALGraph G,int i)//打印输出以顶点i为根的表达式的逆波兰式
{
c=G.vertices[i].data;
if(!G.vertices[i].firstarc) //c是原子
printf(“%c”,c);
else //子表达式
{
p=G.vertices[i].firstarc;
PrintNiBoLan_DAG(G,p->adjvex);
PrintNiBoLan_DAG(G,p->nexarc->adjvex);
printf(“%c”,c);
}
}//PrintNiBoLan_DAG
7.39
void PrintNiBoLan_Bitree(Bitree T)//在二叉链表存储结构上重做上一题
{
if(T->lchild) PrintNiBoLan_Bitree(T->lchild);
if(T->rchild) PrintNiBoLan_Bitree(T->rchild);
printf(“%c”,T->data);
}//PrintNiBoLan_Bitree
7.40
int Evaluate_DAG(ALGraph G)//给有向无环图表示的表达式求值
{
FindIndegree(G,indegree);
for(i=0;i<G.vexnum;i++)
if(!indegree[i]) r=i; //找到有向无环图的根
return Evaluate_imp(G,i);
}//NiBoLan_DAG
int Evaluate_imp(ALGraph G,int i)//求子表达式的值
{
if(G.vertices[i].tag=NUM) return G.vertices[i].value;
else
{
p=G.vertices[i].firstarc;
v1=Evaluate_imp(G,p->adjvex);
v2=Evaluate_imp(G,p->nextarc->adjvex);
return calculate(v1,G.vertices[i].optr,v2);
}
}//Evaluate_imp
分析:本题中,邻接表的vertices向量的元素类型修改如下:
struct {
enum tag{NUM,OPTR};
union {
int value;
char optr;
};
ArcNode * firstarc;
} Elemtype;
7.41
void Critical_Path(ALGraph G)//利用深度优先遍历求网的关键路径
{
FindIndegree(G,indegree);
for(i=0;i<G.vexnum;i++)
if(!indegree[i]) DFS1(G,i); //第一次深度优先遍历:建立ve
for(i=0;i<G.vexnum;i++)
if(!indegree[i]) DFS2(G,i); //第二次深度优先遍历:建立vl
for(i=0;i<=G.vexnum;i++)
if(vl[i]==ve[i]) printf(“%d”,i); //打印输出关键路径
}//Critical_Path
void DFS1(ALGraph G,int i)
{
if(!indegree[i]) ve[i]=0;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
dut=*p->info;
if(ve[i]+dut>ve[p->adjvex])
ve[p->adjvex]=ve[i]+dut;
DFS1(G,p->adjvex);
}
}//DFS1
void DFS2(ALGraph G,int i)
{
if(!G.vertices[i].firstarc) vl[i]=ve[i];
else
{
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
DFS2(G,p->adjvex);
dut=*p->info;
if(vl[p->adjvex]-dut<vl[i])
vl[i]=vl[p->adjvex]-dut;
}
}//else
}//DFS2
7.42
void ALGraph_DIJ(ALGraph G,int v0,Pathmatrix &P,ShortestPathTable &D)//在邻接表存储结构上实现迪杰斯特拉算法
{
for(v=0;v<G.vexnum;v++)
D[v]=INFINITY;
for(p=G.vertices[v0].firstarc;p;p=p->nextarc)
D[p->adjvex]=*p->info; //给D数组赋初值
for(v=0;v<G.vexnum;v++)
{
final[v]=0;
for(w=0;w<G.vexnum;w++) P[v][w]=0; //设空路径
if(D[v]<INFINITY)
{
P[v][v0]=1;
P[v][v]=1;
}
}//for
D[v0]=0;final[v0]=1; //初始化
for(i=1;i<G.vexnum;i++)
{
min=INFINITY;
for(w=0;w<G.vexnum;w++)
if(!final[w])
if(D[w]<min) //尚未求出到该顶点的最短路径
{
v=w;
min=D[w];
}
final[v]=1;
for(p=G.vertices[v].firstarc;p;p=p->nextarc)
{
w=p->adjvex;
if(!final[w]&&(min+(*p->info)<D[w])) //符合迪杰斯特拉条件
{
D[w]=min+edgelen(G,v,w);
P[w]=P[v];
P[w][w]=1; //构造最短路径
}
}//for
}//for
}//ALGraph_DIJ
分析:本算法对迪杰斯特拉算法中直接取任意边长度的语句作了修改.由于在原算法中,每次循环都是对尾相同的边进行处理,所以可以用遍历邻接表中的一条链来代替.
第八章 动态存储管理
8.11
typedef struct {
char *start;
int size;
} fmblock; //空闲块类型
char *Malloc_Fdlf(int n)//遵循最后分配者最先释放规则的内存分配算法
{
while(Gettop(S,b)&&b.size<n)
{
Pop(S,b);
Push(T,b); //从栈顶逐个取出空闲块进行比较
}
if(StackEmpty(S)) return NULL; //没有大小足够的空闲块
Pop(S,b);
b.size-=n;
if(b.size) Push(S,{b.start+n,b.size});//分割空闲块
while(!StackEmpty(T))
{
Pop(T,a);
Push(S,a);
} //恢复原来次序
return b.start;
}//Malloc_Fdlf
mem_init()//初始化过程
{
…
InitStack(S);InitStack(T); //S和T的元素都是fmblock类型
Push(S,{MemStart,MemLen}); //一开始,栈中只有一个内存整块
…
}//main
8.12
void Free_Fdlf(char *addr,int n)//与上一题对应的释放算法
{
while(Gettop(S,b)&&b.start<addr)
{
Pop(S,b);
Push(T,b);
} //在按地址排序的栈中找到合适的插入位置
if(Gettop(T,b)&&(b.start+b.size==addr)) //可以与上邻块合并
{
Pop(T,b);
addr=b.start;n+=b.size;
}
if(Gettop(S,b)&&(addr+n==b.start)) //可以与下邻块合并
{
Pop(S,b);
n+=b.size;
}
Push(S,{addr,n}); //插入到空闲块栈中
while(!StackEmpty(T))
{
Pop(T,b);
Push(S,b);
} //恢复原来次序
}//Free_Fdlf
8.13
void Free_BT(Space &pav,Space p)//在边界标识法的动态存储管理系统中回收空闲块p
{
n=p->size;
f=p+n-1; //f指向空闲块底部
if((p-1)->tag&&(f+1)->tag) //回收块上下邻块均为占用块
{
p->tag=0;f->tag=0;
f->uplink=p;
if(!pav)
{
p->llink=p;
p->rlink=p;
}
else
{
q=pav->llink;
p->llink=q;p->rlink=pav;
q->rlink=p;pav->llink=p;
}
pav=p;
}//if
else if(!(p-1)->tag&&(f+1)->tag) //上邻块为空闲块
{
q=(p-1)->uplink;
q->size+=n;
f->uplink=q;
f->tag=0;
}
else if((p-1)->tag&&!(f+1)->tag) //下邻块为空闲块
{
q=f+1;
s=q->llink;t=q->rlink;
p->llink=s;p->rlink=t;
s->rlink=p;t->llink=p;
p->size+=q->size;
(q+q->size-1)->uplink=p;
p->tag=0;
}
else //上下邻块均为空闲块
{
s=(p-1)->uplink;
t=f+1;
s->size+=n+t->size;
t->llink->rlink=t->rlink;
t->rlink->llink=t->llink;
(t+t->size-1)->uplink=s;
}
}//Free_BT,该算法在课本里有详细的描述.
8.14
void Free_BS(freelist &avail,char *addr,int n)//伙伴系统的空闲块回收算法
{
buddy=addr%(2*n)?(addr-n):(addr+n); //求回收块的伙伴地址
addr->tag=0;
addr->kval=n;
for(i=0;avail[i].nodesize<n;i++); //找到这一大小的空闲块链
if(!avail[i].first) //尚没有该大小的空闲块
{
addr->llink=addr;
addr->rlink=addr;
avail[i].first=addr; //作为唯一一个该大小的空闲块
}
else
{
for(p=avail[i].first;p!=buddy&&p!=avail[i].first;p=p->rlink);//寻找伙伴
if(p==buddy) //伙伴为空闲块,此时进行合并
{
if(p->rlink==p) avail[i].first=NULL;//伙伴是此大小的唯一空闲块
else
{
p->llink->rlink=p->rlink;
p->rlink->llink=p->llink;
} //从空闲块链中删去伙伴
new=addr>p?p:addr; //合并后的新块首址
Free_BS(avail,new,2*n); //递归地回收新块
}//if
else //伙伴为占用块,此时插入空闲块链头部
{
q=p->rlink;
p->rlink=addr;addr->llink=p;
q->llink=addr;addr->rlink=q;
}
}//else
}//Free_BS
8.15
FBList *MakeList(char *highbound,char *lowbound)//把堆结构存储的的所有空闲块链接成可利用空间表,并返回表头指针
{
p=lowbound;
while(p->tag&&p<highbound) p++; //查找第一个空闲块
if(p>=highbound) return NULL; //没有空闲块
head=p;
for(q=p;p<highbound;p+=cellsize) //建立链表
if(!p->tag)
{
q->next=p;
q=p;
}//if
p->next=NULL;
return head; //返回头指针
}//MakeList
8.16
void Mem_Contract(Heap &H)//对堆H执行存储紧缩
{
q=MemStart;j=0;
for(i=0;i<Max_ListLen;i++)
if(H.list[i].stadr->tag)
{
s=H.list[i].length;
p=H.list[i].stadr;
for(k=0;k<s;k++) *(q++)=*(p++); //紧缩内存空间
H.list[j].stadr=q;
H.list[j].length=s; //紧缩占用空间表
j++;
}
}//Mem_Contract
第9章 查找
9.1 解：(1)相同，平均查找长度为
(2)相同，平均查找长度为
(3)对于有序顺序表，平均查找长度为，对于无序顺序表，则为。
9.2 解：查找e的过程如下：
9.3 解：
9.4 解：
9.5 解：
9.7 解：
9.9 解：(1)
(3)
9.25
int Search_Sq(SSTable ST,int key)//在有序表上顺序查找的算法,监视哨设在高下标端
{
ST.elem[ST.length+1].key=key;
for(i=1;ST.elem[i].key>key;i++);
if(i>ST.length||ST.elem[i].key<key) return ERROR;
return i;
}//Search_Sq
分析:本算法查找成功情况下的平均查找长度为ST.length/2,不成功情况下为ST.length.
9.26
int Search_Bin_Recursive(SSTable ST,int key,int low,int high)//折半查找的递归算法
{
if(low>high) return 0; //查找不到时返回0
mid=(low+high)/2;
if(ST.elem[mid].key==key) return mid;
else if(ST.elem[mid].key>key)
return Search_Bin_Recursive(ST,key,low,mid-1);
else return Search_Bin_Recursive(ST,key,mid+1,high);
}
}//Search_Bin_Recursive
9.27
int Locate_Bin(SSTable ST,int key)//折半查找,返回小于或等于待查元素的最后一个结点号
{
int *r;
r=ST.elem;
if(key<r.key) return 0;
else if(key>=r[ST.length].key) return ST.length;
low=1;high=ST.length;
while(low<=high)
{
mid=(low+high)/2;
if(key>=r[mid].key&&key<r[mid+1].key) //查找结束的条件
return mid;
else if(key<r[mid].key) high=mid;
else low=mid;
} //本算法不存在查找失败的情况,不需要return 0;
}//Locate_Bin
9.28
typedef struct {
int maxkey;
int firstloc;
} Index;
typedef struct {
int *elem;
int length;
Index idx[MAXBLOCK]; //每块起始位置和最大元素,其中idx[0]不利用,其内容初始化为{0,0}以利于折半查找
int blknum; //块的数目
} IdxSqList; //索引顺序表类型
int Search_IdxSeq(IdxSqList L,int key)//分块查找,用折半查找法确定记录所在块,块内采用顺序查找法
{
if(key>L.idx[L.blknum].maxkey) return ERROR; //超过最大元素
low=1;high=L.blknum;
found=0;
while(low<=high&&!found) //折半查找记录所在块号mid
{
mid=(low+high)/2;
if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey)
found=1;
else if(key>L.idx[mid].maxkey)
low=mid+1;
else high=mid-1;
}
i=L.idx[mid].firstloc; //块的下界
j=i+blksize-1; //块的上界
temp=L.elem[i-1]; //保存相邻元素
L.elem[i-1]=key; //设置监视哨
for(k=j;L.elem[k]!=key;k–); //顺序查找
L.elem[i-1]=temp; //恢复元素
if(k<i) return ERROR; //未找到
return k;
}//Search_IdxSeq
分析:在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失.
9.29
typedef struct {
LNode *h; //h指向最小元素
LNode *t; //t指向上次查找的结点
} CSList;
LNode *Search_CSList(CSList &L,int key)//在有序单循环链表存储结构上的查找算法,假定每次查找都成功
{
if(L.t->data==key) return L.t;
else if(L.t->data>key)
for(p=L.h,i=1;p->data!=key;p=p->next,i++);
else
for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++);
L.t=p; //更新t指针
return p;
}//Search_CSList
分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3.
9.30
typedef struct {
DLNode *pre;
int data;
DLNode *next;
} DLNode;
typedef struct {
DLNode *sp;
int length;
} DSList; //供查找的双向循环链表类型
DLNode *Search_DSList(DSList &L,int key)//在有序双向循环链表存储结构上的查找算法,假定每次查找都成功
{
p=L.sp;
if(p->data>key)
{
while(p->data>key) p=p->pre;
L.sp=p;
}
else if(p->data<key)
{
while(p->data<key) p=p->next;
L.sp=p;
}
return p;
}//Search_DSList
分析:本题的平均查找长度与上一题相同,也是n/3.
9.31
int last=0,flag=1;
int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0
{
if(T->lchild&&flag) Is_BSTree(T->lchild);
if(T->data<last) flag=0; //与其中序前驱相比较
last=T->data;
if(T->rchild&&flag) Is_BSTree(T->rchild);
return flag;
}//Is_BSTree
9.32
int last=0;
void MaxLT_MinGT(BiTree T,int x)//找到二叉排序树T中小于x的最大元素和大于x的最小元素
{
if(T->lchild) MaxLT_MinGT(T->lchild,x); //本算法仍是借助中序遍历来实现
if(last<x&&T->data>=x) //找到了小于x的最大元素
printf(“a=%d\n”,last);
if(last<=x&&T->data>x) //找到了大于x的最小元素
printf(“b=%d\n”,T->data);
last=T->data;
if(T->rchild) MaxLT_MinGT(T->rchild,x);
}//MaxLT_MinGT
9.33
void Print_NLT(BiTree T,int x)//从大到小输出二叉排序树T中所有不小于x的元素
{
if(T->rchild) Print_NLT(T->rchild,x);
if(T->data<x) exit(); //当遇到小于x的元素时立即结束运行
printf(“%d\n”,T->data);
if(T->lchild) Print_NLT(T->lchild,x); //先右后左的中序遍历
}//Print_NLT
9.34
void Delete_NLT(BiTree &T,int x)//删除二叉排序树T中所有不小于x元素结点,并释放空间
{
if(T->rchild) Delete_NLT(T->rchild,x);
if(T->data<x) exit(); //当遇到小于x的元素时立即结束运行
q=T;
T=T->lchild;
free(q); //如果树根不小于x,则删除树根,并以左子树的根作为新的树根
if(T) Delete_NLT(T,x); //继续在左子树中执行算法
}//Delete_NLT
9.35
void Print_Between(BiThrTree T,int a,int b)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素
{
p=T;
while(!p->ltag) p=p->lchild; //找到最小元素
while(p&&p->data<b)
{
if(p->data>a) printf(“%d\n”,p->data); //输出符合条件的元素
if(p->rtag) p=p->rtag;
else
{
p=p->rchild;
while(!p->ltag) p=p->lchild;
} //转到中序后继
}//while
}//Print_Between
9.36
void BSTree_Insert_Key(BiThrTree &T,int x)//在后继线索二叉排序树T中插入元素x
{
if(T->data<x) //插入到右侧
{
if(T->rtag) //T没有右子树时,作为右孩子插入
{
p=T->rchild;
q=(BiThrNode*)malloc(sizeof(BiThrNode));
q->data=x;
T->rchild=q;T->rtag=0;
q->rtag=1;q->rchild=p; //修改原线索
}
else BSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中
}//if
else if(T->data>x) //插入到左子树中
{
if(!T->lchild) //T没有左子树时,作为左孩子插入
{
q=(BiThrNode*)malloc(sizeof(BiThrNode));
q->data=x;
T->lchild=q;
q->rtag=1;q->rchild=T; //修改自身的线索
}
else BSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中
}//if
}//BSTree_Insert_Key
9.37
Status BSTree_Delete_key(BiThrTree &T,int x)//在后继线索二叉排序树T中删除元素x
{
BTNode *pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继
p=T;last=NULL; //last始终指向当前结点p的前一个(前驱)
while(!p->ltag) p=p->lchild; //找到中序起始元素
while(p)
{
if(p->data==x) //找到了元素x结点
{
pre=last;
ptr=p;
}
else if(last&&last->data==x) suc=p; //找到了x的后继
if(p->rtag) p=p->rtag;
else
{
p=p->rchild;
while(!p->ltag) p=p->lchild;
} //转到中序后继
last=p;
}//while //借助中序遍历找到元素x及其前驱和后继结点
if(!ptr) return ERROR; //未找到待删结点
Delete_BSTree(ptr); //删除x结点
if(pre&&pre->rtag)
pre->rchild=suc; //修改线索
return OK;
}//BSTree_Delete_key
void Delete_BSTree(BiThrTree &T)//课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动
{
q=T;
if(!T->ltag&&T->rtag) //结点无右子树,此时只需重接其左子树
T=T->lchild;
else if(T->ltag&&!T->rtag) //结点无左子树,此时只需重接其右子树
T=T->rchild;
else if(!T->ltag&&!T->rtag) //结点既有左子树又有右子树
{
p=T;r=T->lchild;
while(!r->rtag)
{
s=r;
r=r->rchild; //找到结点的前驱r和r的双亲s
}
T->data=r->data; //用r代替T结点
if(s!=T)
s->rchild=r->lchild;
else s->lchild=r->lchild; //重接r的左子树到其双亲结点上
q=r;
}//else
free(q); //删除结点
}//Delete_BSTree
分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了.
9.38
void BSTree_Merge(BiTree &T,BiTree &S)//把二叉排序树S合并到T中
{
if(S->lchild) BSTree_Merge(T,S->lchild);
if(S->rchild) BSTree_Merge(T,S->rchild); //合并子树
Insert_Key(T,S); //插入元素
}//BSTree_Merge
void Insert_Node(Bitree &T,BTNode *S)//把树结点S插入到T的合适位置上
{
if(S->data>T->data)
{
if(!T->rchild) T->rchild=S;
else Insert_Node(T->rchild,S);
}
else if(S->data<T->data)
{
if(!T->lchild) T->lchild=S;
else Insert_Node(T->lchild,S);
}
S->lchild=NULL; //插入的新结点必须和原来的左右子树断绝关系
S->rchild=NULL; //否则会导致树结构的混乱
}//Insert_Node
分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.
9.39
void BSTree_Split(BiTree &T,BiTree &A,BiTree &B,int x)//把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部大于x
{
if(T->lchild) BSTree_Split(T->lchild,A,B,x);
if(T->rchild) BSTree_Split(T->rchild,A,B,x); //分裂左右子树
if(T->data<=x) Insert_Node(A,T);
else Insert_Node(B,T); //将元素结点插入合适的树中
}//BSTree_Split
void Insert_Node(Bitree &T,BTNode *S)//把树结点S插入到T的合适位置上
{
if(!T) T=S; //考虑到刚开始分裂时树A和树B为空的情况
else if(S->data>T->data) //其余部分与上一题同
{
if(!T->rchild) T->rchild=S;
else Insert_Node(T->rchild,S);
}
else if(S->data<T->data)
{
if(!T->lchild) T->lchild=S;
else Insert_Node(T->lchild,S);
}
S->lchild=NULL;
S->rchild=NULL;
}//Insert_Key
9.40
typedef struct {
int data;
int bf;
int lsize; //lsize域表示该结点的左子树的结点总数加1
BlcNode *lchild,*rchild;
} BlcNode,*BlcTree; //含lsize域的平衡二叉排序树类型
BTNode *Locate_BlcTree(BlcTree T,int k)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针
{
if(!T) return NULL; //k小于1或大于树结点总数
if(T->lsize==k) return T; //就是这个结点
else if(T->lsize>k)
return Locate_BlcTree(T->lchild,k); //在左子树中寻找
else return Locate_BlcTree(T->rchild,k-T->lsize); //在右子树中寻找,注意要修改k的值
}//Locate_BlcTree
9.41
typedef struct {
enum {LEAF,BRANCH} tag; //结点类型标识
int keynum;
BPLink parent; //双亲指针
int key[MAXCHILD]; //关键字
union {
BPLink child[MAXCHILD];//非叶结点的孩子指针
struct {
rectype *info[MAXCHILD];//叶子结点的信息指针
BPNode *next; //指向下一个叶子结点的链接
} leaf;
}
} BPNode,*BPLink,*BPTree;//B+树及其结点类型
Status BPTree_Search(BPTree T,int key,BPNode *ptr,int pos)//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos
{
p=T;
while(p.tag==BRANCH) //沿分支向下查找
{
for(i=0;i<p->keynum&&key>p->key[i];i++); //确定关键字所在子树
if(i==p->keynum) return ERROR; //关键字太大
p=p->child[i];
}
for(i=0;i<p->keynum&&key!=p->key[i];i++); //在叶子结点中查找
if(i==p->keynum) return ERROR; //找不到关键字
ptr=p;pos=i;
return OK;
}//BPTree_Search
9.42
void TrieTree_Insert_Key(TrieTree &T,StringType key)//在Trie树T中插入字符串key,StringType的结构见第四章
{
q=(TrieNode*)malloc(sizeof(TrieNode));
q->kind=LEAF;
q->lf.k=key; //建叶子结点
klen=key[0];
p=T;i=1;
while(p&&i<=klen&&p->bh.ptr[ord(key[i])])
{
last=p;
p=p->bh.ptr[ord(key[i])];
i++;
} //自上而下查找
if(p->kind==BRANCH) //如果最后落到分支结点(无同义词):
{
p->bh.ptr[ord(key[i])]=q; //直接连上叶子
p->bh.num++;
}
else //如果最后落到叶子结点(有同义词):
{
r=(TrieNode*)malloc(sizeof(TrieNode)); //建立新的分支结点
last->bh.ptr[ord(key[i-1])]=r; //用新分支结点取代老叶子结点和上一层的联系
r->kind=BRANCH;r->bh.num=2;
r->bh.ptr[ord(key[i])]=q;
r->bh.ptr[ord(p->lf.k[i])]=p; //新分支结点与新老两个叶子结点相连
}
}//TrieTree_Insert_Key
分析:当自上而下的查找结束时,存在两种情况.一种情况,树中没有待插入关键字的同义词,此时只要新建一个叶子结点并连到分支结点上即可.另一种情况,有同义词,此时要把同义词的叶子结点与树断开,在断开的部位新建一个下一层的分支结点,再把同义词和新关键字的叶子结点连到新分支结点的下一层.
9.43
Status TrieTree_Delete_Key(TrieTree &T,StringType key)//在Trie树T中删除字符串key
{
p=T;i=1;
while(p&&p->kind==BRANCH&&i<=key[0]) //查找待删除元素
{
last=p;
p=p->bh.ptr[ord(key[i])];
i++;
}
if(p&&p->kind==LEAF&&p->lf.k=key) //找到了待删除元素
{
last->bh.ptr[ord(key[i-1])]=NULL;
free(p);
return OK;
}
else return ERROR; //没找到待删除元素
}//TrieTree_Delete_Key
9.44
void Print_Hash(HashTable H)//按第一个字母顺序输出Hash表中的所有关键字,其中处理冲突采用线性探测开放定址法
{
for(i=1;i<=26;i++)
for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex]) //线性探测
if(H(H.elem[j].key)==i) printf(“%s\n”,H.elem[j]);
}//Print_Hash
int H(char *s)//求Hash函数
{
if(s) return s[0]-96; //求关键字第一个字母的字母序号(小写)
else return 0;
}//H
9.45
typedef *LNode[MAXSIZE] CHashTable; //链地址Hash表类型
Status Build_Hash(CHashTable &T,int m)//输入一组关键字,建立Hash表,表长为m,用链地址法处理冲突.
{
if(m<1) return ERROR;
T=malloc(m*sizeof(WORD)); //建立表头指针向量
for(i=0;i<m;i++) T[i]=NULL;
while((key=Inputkey())!=NULL) //假定Inputkey函数用于从键盘输入关键字
{
q=(LNode*)malloc(sizeof(LNode));
q->data=key;q->next=NULL;
n=H(key);
if(!T[n]) T[n]=q; //作为链表的第一个结点
else
{
for(p=T[n];p->next;p=p->next);
p->next=q; //插入链表尾部.本算法不考虑排序问题.
}
}//while
return OK;
}//Build_Hash
9.46
Status Locate_Hash(HashTable H,int row,int col,KeyType key,int &k)//根据行列值在Hash表表示的稀疏矩阵中确定元素key的位置k
{
h=2*(100*(row/10)+col/10); //作者设计的Hash函数
while(H.elem[h].key&&!EQ(H.elem[h].key,key))
h=(h+1)%20000;
if(EQ(H.elem[h].key,key)) k=h;
else k=NULL;
}//Locate_Hash
分析:本算法所使用的Hash表长20000,装填因子为50%,Hash函数为行数前两位和列数前两位所组成的四位数再乘以二,用线性探测法处理冲突.当矩阵的元素是随机分布时,查找的时间复杂度为O(1).
第十章 内部排序
10.23
void Insert_Sort1(SqList &L)//监视哨设在高下标端的插入排序算法
{
k=L.length;
for(i=k-1;i;–i) //从后向前逐个插入排序
if(L.r[i].key>L.r[i+1].key)
{
L.r[k+1].key=L.r[i].key; //监视哨
for(j=i+1;L.r[j].key>L.r[i].key;++j)
L.r[j-1].key=L.r[j].key; //前移
L.r[j-1].key=L.r[k+1].key; //插入
}
}//Insert_Sort1
10.24
void BiInsert_Sort(SqList &L)//二路插入排序的算法
{
int d[MAXSIZE]; //辅助存储
x=L.r.key;d=x;
first=1;final=1;
for(i=2;i<=L.length;i++)
{
if(L.r[i].key>=x) //插入前部
{
for(j=final;d[j]>L.r[i].key;j–)
d[j+1]=d[j];
d[j+1]=L.r[i].key;
final++;
}
else //插入后部
{
for(j=first;d[j]<L.r[i].key;j++)
d[j-1]=d[j];
d[(j-2)%MAXSIZE+1]=L.r[i].key;
first=(first-2)%MAXSIZE+1; //这种形式的表达式是为了兼顾first=1的情况
}
}//for
for(i=first,j=1;d[i];i=i%MAXSIZE+1,j++)//将序列复制回去
L.r[j].key=d[i];
}//BiInsert_Sort
10.25
void SLInsert_Sort(SLList &L)//静态链表的插入排序算法
{
L.r[0].key=0;L.r[0].next=1;
L.r[1].next=0; //建初始循环链表
for(i=2;i<=L.length;i++) //逐个插入
{
p=0;x=L.r[i].key;
while(L.r[L.r[p].next].key<x&&L.r[p].next)
p=L.r[p].next;
q=L.r[p].next;
L.r[p].next=i;
L.r[i].next=q;
}//for
p=L.r[0].next;
for(i=1;i<L.length;i++) //重排记录的位置
{
while(p<i) p=L.r[p].next;
q=L.r[p].next;
if(p!=i)
{
L.r[p]<->L.r[i];
L.r[i].next=p;
}
p=q;
}//for
}//SLInsert_Sort
10.26
void Bubble_Sort1(int a[ ],int n)//对包含n个元素的数组a进行改进的冒泡排序
{
change=n-1; //change指示上一趟冒泡中最后发生交换的元素
while(change)
{
for(c=0,i=0;i<change;i++)
if(a[i]>a[i+1])
{
a[i]<->a[i+1];
c=i+1; //c指示这一趟冒泡中发生交换的元素
}
change=c;
}//while
}//Bubble_Sort1
10.27
void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法
{
low=0;high=n-1; //冒泡的上下界
change=1;
while(low<high&&change)
{
change=0;
for(i=low;i<high;i++) //从上向下起泡
if(a[i]>a[i+1])
{
a[i]<->a[i+1];
change=1;
}
high–; //修改上界
for(i=high;i>low;i–) //从下向上起泡
if(a[i]<a[i-1])
{
a[i]<->a[i-1];
change=1;
}
low++; //修改下界
}//while
}//Bubble_Sort2
10.28
void Bubble_Sort3(int a[ ],int n)//对上一题的算法进行化简,循环体中只包含一次冒泡
{
int b[ 3 ]; //b[0]为冒泡的下界,b[ 2 ]为上界,b[1]无用
d=1;b[0]=0;b[ 2 ]=n-1; //d为冒泡方向的标识,1为向上,-1为向下
change=1;
while(b[0]<b[ 2 ]&&change)
{
change=0;
for(i=b[1-d];i!=b[1+d];i+=d) //统一的冒泡算法
if((a[i]-a[i+d])*d>0) //注意这个交换条件
{
a[i]<->a[i+d];
change=1;
}
b[1+d]-=d; //修改边界
d*=-1; //换个方向
}//while
}//Bubble_Sort3
10.29
void OE_Sort(int a[ ],int n)//奇偶交换排序的算法
{
change=1;
while(change)
{
change=0;
for(i=1;i<n-1;i+=2) //对所有奇数进行一趟比较
if(a[i]>a[i+1])
{
a[i]<->a[i+1];
change=1;
}
for(i=0;i<n-1;i+=2) //对所有偶数进行一趟比较
if(a[i]>a[i+1])
{
a[i]<->a[i+1];
change=1;
}
}//while
}//OE_Sort
分析:本算法的结束条件是连续两趟比较无交换发生
10.30
typedef struct {
int low;
int high;
} boundary; //子序列的上下界类型
void QSort_NotRecurve(int SQList &L)//快速排序的非递归算法
{
low=1;high=L.length;
InitStack(S); //S的元素为boundary类型
while(low<high&&!StackEmpty(S)) //注意排序结束的条件
{
if(high-low>2) //如果当前子序列长度大于3且尚未排好序
{
pivot=Partition(L,low,high); //进行一趟划分
if(high-pivot>pivot-low)
{
Push(S,{pivot+1,high}); //把长的子序列边界入栈
high=pivot-1; //短的子序列留待下次排序
}
else
{
Push(S,{low,pivot-1});
low=pivot+1;
}
}//if
else if(low<high&&high-low<3)//如果当前子序列长度小于3且尚未排好序
{
Easy_Sort(L,low,high); //直接进行比较排序
low=high; //当前子序列标志为已排好序
}
else //如果当前子序列已排好序但栈中还有未排序的子序列
{
Pop(S,a); //从栈中取出一个子序列
low=a.low;
high=a.high;
}
}//while
}//QSort_NotRecurve
int Partition(SQList &L,int low,int high)//一趟划分的算法,与书上相同
{
L.r[0]=L.r[low];
pivotkey=L.r[low].key;
while(low<high)
{
while(low<high&&L.r[high].key>=pivotkey)
high–;
L.r[low]=L.r[high];
while(low<high&&L.r[low].key<=pivotkey)
low++;
L.r[high]=L.r[low];
}//while
L.r[low]=L.r[0];
return low;
}//Partition
void Easy_Sort(SQList &L,int low,int high)//对长度小于3的子序列进行比较排序
{
if(high-low==1) //子序列只含两个元素
if(L.r[low].key>L.r[high].key) L.r[low]<->L.r[high];
else //子序列含有三个元素
{
if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];
if(L.r[low+1].key>L.r[high].key) L.r[low+1]<->L.r[high];
if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];
}
}//Easy_Sort
10.31
void Divide(int a[ ],int n)//把数组a中所有值为负的记录调到非负的记录之前
{
low=0;high=n-1;
while(low<high)
{
while(low<high&&a[high]>=0) high–; //以0作为虚拟的枢轴记录
a[low]<->a[high];
while(low<high&&a[low]<0) low++;
a[low]<->a[high];
}
}//Divide
10.32
typedef enum {RED,WHITE,BLUE} color; //三种颜色
void Flag_Arrange(color a[ ],int n)//把由三种颜色组成的序列重排为按照红,白,蓝的顺序排列
{
i=0;j=0;k=n-1;
while(j<=k)
switch(a[j])
{
case RED:
a[i]<->a[j];
i++;
j++;
break;
case WHITE:
j++;
break;
case BLUE:
a[j]<->a[k];
k–; //这里没有j++;语句是为了防止交换后a[j]仍为蓝色的情况
}
}//Flag_Arrange
分析:这个算法中设立了三个指针.其中,j表示当前元素;i以前的元素全部为红色;k以后的元素全部为蓝色.这样,就可以根据j的颜色,把其交换到序列的前部或者后部.
10.33
void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法
{
for(p=L;p->next->next;p=p->next)
{
q=p->next;x=q->data;
for(r=q,s=q;r->next;r=r->next) //在q后面寻找元素值最小的结点
if(r->next->data<x)
{
x=r->next->data;
s=r;
}
if(s!=q) //找到了值比q->data更小的最小结点s->next
{
p->next=s->next;s->next=q;
t=q->next;q->next=p->next->next;
p->next->next=t;
} //交换q和s->next两个结点
}//for
}//LinkedList_Select_Sort
10.34
void Build_Heap(Heap &H,int n)//从低下标到高下标逐个插入建堆的算法
{
for(i=2;i<n;i++)
{ //此时从H.r[1]到H.r[i-1]已经是大顶堆
j=i;
while(j!=1) //把H.r[i]插入
{
k=j/2;
if(H.r[j].key>H.r[k].key)
H.r[j]<->H.r[k];
j=k;
}
}//for
}//Build_Heap
10.35
void TriHeap_Sort(Heap &H)//利用三叉树形式的堆进行排序的算法
{
for(i=H.length/3;i>0;i–)
Heap_Adjust(H,i,H.length);
for(i=H.length;i>1;i–)
{
H.r[1]<->H.r[i];
Heap_Adjust(H,1,i-1);
}
}//TriHeap_Sort
void Heap_Adjust(Heap &H,int s,int m)//顺序表H中,H.r[s+1]到H.r[m]已经是堆,把H.r[s]插入并调整成堆
{
rc=H.r[s];
for(j=3*s-1;j<=m;j=3*j-1)
{
if(j<m&&H.r[j].key<H.r[j+1].key) j++;
if(j<m&&H.r[j].key<H.r[j+1].key) j++;
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc;
}//Heap_Adjust
分析:本算法与课本上的堆排序算法相比,只有两处改动:1.建初始堆时,i的上限从H.length/3开始(为什么?) 2.调整堆的时候,要从结点的三个孩子结点中选择最大的那一个,最左边的孩子的序号的计算公式为j=3*s-1(为什么?)
10.36
void Merge_Sort(int a[ ],int n)//归并排序的非递归算法
{
for(l=1;l<n;l*=2) //l为一趟归并段的段长
for(i=0;(2*i-1)*l<n;i++) //i为本趟的归并段序号
{
start1=2*l*i; //求出待归并的两段的上下界
end1=start1+l-1;
start2=end1+1;
end2=(start2+l-1)>(n-1)?(n-1):(start2+l-1);//注意end2可能超出边界
Merge(a,start1,end1,start2,end2); //归并
}
}//Merge_Sort
void Merge(int a[ ],int s1,int e1,int s2,int e2)//将有序子序列a[s1]到a[e1]和a[s2]到a[e2]归并为有序序列a[s1]到a[e2]
{
int b[MAXSIZE]; //设立辅助存储数组b
for(i=s1,j=s2,k=s1;i<=e1&&j<=e2;k++)
{
if(a[i]<a[j]) b[k]=a[i++];
else b[k]=a[j++];
}
while(i<=e1) b[k++]=a[i++];
while(j<=e2) b[k++]=a[j++]; //归并到b中
for(i=s1;i<=e2;i++) //复制回去
a[i]=b[i];
}//Merge
10.37
void LinkedList_Merge_Sort1(LinkedList &L)//链表结构上的归并排序非递归算法
{
for(l=1;l<L.length;l*=2) //l为一趟归并段的段长
for(p=L->next,e2=p;p->next;p=e2)
{
for(i=1,q=p;i<=l&&q->next;i++,q=q->next);
e1=q;
for(i=1;i<=l&&q->next;i++,q=q->next);
e2=q; //求出两个待归并子序列的尾指针
if(e1!=e2) LinkedList_Merge(L,p,e1,e2); //归并
}
}//LinkedList_Merge_Sort1
void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)//对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2
{
q=p->next;r=e1->next; //q和r为两个子序列的起始位置
while(q!=e1->next&&r!=e2->next)
{
if(q->data<r->data) //选择关键字较小的那个结点接在p的后面
{
p->next=q;p=q;
q=q->next;
}
else
{
p->next=r;p=r;
r=r->next;
}
}//while
while(q!=e1->next) //接上剩余部分
{
p->next=q;p=q;
q=q->next;
}
while(r!=e2->next)
{
p->next=r;p=r;
r=r->next;
}
}//LinkedList_Merge
10.38
void LinkedList_Merge_Sort2(LinkedList &L)//初始归并段为最大有序子序列的归并排序,采用链表存储结构
{
LNode *end[MAXSIZE]; //设立一个数组来存储各有序子序列的尾指针
for(p=L->next->next,i=0;p;p=p->next) //求各有序子序列的尾指针
if(!p->next||p->data>p->next->data) end[i++]=p;
while(end[0]->next) //当不止一个子序列时进行两两归并
{
j=0;k=0; //j:当前子序列尾指针存储位置;k:归并后的子序列尾指针存储位置
for(p=L->next,e2=p;p->next;p=e2) //两两归并所有子序列
{
e1=end[j];e2=end[j+1]; //确定两个子序列
if(e1->next) LinkedList_Merge(L,p,e1,e2); //归并
end[k++]=e2; //用新序列的尾指针取代原来的尾指针
j+=2; //转到后面两个子序列
}
}//while
}//LinkedList_Merge_Sort2
void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)//对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2
{
q=p->next;r=e1->next;
while(q!=e1->next&&r!=e2->next)
{
if(q->data<r->data)
{
p->next=q;p=q;
q=q->next;
}
else
{
p->next=r;p=r;
r=r->next;
}
}//while
while(q!=e1->next)
{
p->next=q;p=q;
q=q->next;
}
while(r!=e2->next)
{
p->next=r;p=r;
r=r->next;
}
}//LinkedList_Merge,与上一题完全相同
10.39
void SL_Merge(int a[ ],int l1,int l2)//把长度分别为l1,l2且l1^2<(l1+l2)的两个有序子序列归并为有序序列
{
start1=0;start2=l1; //分别表示序列1和序列2的剩余未归并部分的起始位置
for(i=0;i<l1;i++) //插入第i个元素
{
for(j=start2;j<l1+l2&&a[j]<a[start1+i];j++); //寻找插入位置
k=j-start2; //k为要向右循环移动的位数
RSh(a,start1,j-1,k);//将a[start1]到a[j-1]之间的子序列循环右移k位
start1+=k+1;
start2=j; //修改两序列尚未归并部分的起始位置
}
}//SL_Merge
void RSh(int a[ ],int start,int end,int k)//将a[start]到a[end]之间的子序列循环右移k位,算法原理参见5.18
{
len=end-start+1;
for(i=1;i<=k;i++)
if(len%i==0&&k%i==0) p=i; //求len和k的最大公约数p
for(i=0;i<p;i++) //对p个循环链分别进行右移
{
j=start+i;l=start+(i+k)%len;temp=a[j];
while(l!=start+i)
{
a[j]=temp;
temp=a[l];
a[l]=a[j];
j=l;l=start+(j-start+k)%len; //依次向右移
}
a[start+i]=temp;
}//for
}//RSh
10.40
书后给出的解题思路在表述上存在问题,无法理解.比如说,”把第一个序列划分为两个子序列,使其中的第一个子序列含有s1个记录,0<=s1<s,第二个子序列有s个记录.”可是题目中并没有说明,第一个序列的长度<2s.请会做的朋友提供解法.
10.41
void Hash_Sort(int a[ ])//对1000个关键字为四位整数的记录进行排序
{
int b[10000];
for(i=0;i<1000;i++) //直接按关键字散列
{
for(j=a[i];b[j];j=(j+1)%10000);
b[j]=a[i];
}
for(i=0,j=0;i<1000;j++) //将散列收回a中
if(b[j])
{
for(x=b[j],k=j;b[k];k=(k+1)%10000)
if(b[k]==x)
{
a[i++]=x;
b[k]=0;
}
}//if
}//Hash_Sort
10.42
typedef struct {
int gt; //大于该记录的个数
int lt; //小于该记录的个数
} place; //整个序列中比某个关键字大或小的记录个数
int Get_Mid(int a[ ],int n)//求一个序列的中值记录的位置
{
place b[MAXSIZE];
for(i=0;i<n;i++) //对每一个元素统计比它大和比它小的元素个数gt和lt
for(j=0;j<n;j++)
{
if(a[j]>a[i]) b[i].gt++;
else if(a[j]<a[i]) b[i].lt++;
}
mid=0;
min_dif=abs(b[0].gt-b[0].lt);
for(i=0;i<n;i++) //找出gt值与lt值最接近的元素,即为中值记录
if(abs(b[i].gt-b[i].lt)<min_dif) mid=i;
return mid;
}//Get_Mid
10.43
void Count_Sort(int a[ ],int n)//计数排序算法
{
int c[MAXSIZE];
for(i=0;i<n;i++) //对每一个元素
{
for(j=0,count=0;j<n;j++) //统计关键字比它小的元素个数
if(a[j]<a[i]) count++:
c[i]=count;
}
for(i=0;i<n;i++) //依次求出关键字最小,第二小,…,最大的记录
{
min=0;
for(j=0;j<n;j++)
if(c[j]<c[min]) min=j; //求出最小记录的下标min
a[i]<->a[min]; //与第i个记录交换
c[min]=INFINITY; //修改该记录的c值为无穷大以便下一次选取
}
}//Count_Sort
10.44
void Enum_Sort(int a[ ],int n)//对关键字只能取v到w之间任意整数的序列进行排序
{
int number[w+1],pos[w+1];
for(i=0;i<n;i++) number[a[i]]++; //计数
for(pos[0]=0,i=1;i<n;i++)
pos[i]=pos[i-1]+num[i]; //pos数组可以把关键字的值映射为元素在排好的序列中的位置
for(i=0;i<n;i++) //构造有序数组c
c[pos[a[i]]++]=a[i];
for(i=0;i<n;i++)
a[i]=c[i];
}//Enum_Sort
分析:本算法参考了第五章三元组稀疏矩阵转置的算法思想,其中的pos数组和那里的cpot数组起的是相类似的作用.
10.45
typedef enum {0,1,2,3,4,5,6,7,8,9} digit; //个位数类型
typedef digit[3] num; //3位自然数类型,假设低位存储在低下标,高位存储在高下标
void Enum_Radix_Sort(num a[ ],int n)//利用计数实现基数排序,其中关键字为3位自然数,共有n个自然数
{
int number ,pos ;
num c[MAXSIZE];
for(j=0;j<3;j++) //依次对个位,十位和百位排序
{
for(i=0;i<n;i++) number[a[i][j]]++; //计数
for(pos[0]=0,i=1;i<n;i++)
pos[i]=pos[i-1]+num[i]; //把关键字的值映射为元素在排好的序列中的位置
for(i=0;i<n;i++) //构造有序数组c
c[pos[a[i][j]]++]=a[i];
for(i=0;i<n;i++)
a[i]=c[i];
}//for
}//Enum_Radix_Sort
分析:计数排序是一种稳定的排序方法.正因为如此,它才能够被用来实现基数排序.
10.46
typedef struct {
int key;
int pos;
} Shadow; //影子序列的记录类型
void Shadow_Sort(Rectype b[ ],Rectype &a[ ],int n)//对元素很大的记录序列b进行排序,结果放入a中,不移动元素
{
Shadow d[MAXSIZE];
for(i=0;i<n;i++) //生成影子序列
{
d[i].key=b[i].key;
d[i].pos=i;
}
for(i=n-1,change=1;i>1&&change;i–) //对影子序列执行冒泡排序
{
change=0;
for(j=0;j<i;j++)
if(d[j].key>d[j+1].key)
{
d[j]<->d[j+1];
change=1;
}
}//for
for(i=0;i<n;i++) //按照影子序列里记录的原来位置复制原序列
a[i]=b[d[i].pos];
}//Shadow_Sort