数据结构及算法答案

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(n^3.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)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。

2.18试写一算法，实现线性表操作Delete(L,i)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。

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个结点之前插入一个结点的算法。

2.36 采用2.34题所述的存储结构，写出删除第i个结点的算法。

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.20 假设以二维数组g(1…m, 1…n)表示一个图像区域，g[i,j]表示该区域中点(i,j)所具颜色，其值为从0到k的整数。编写算法置换点(i₀,j₀)所在区域的颜色。约定和(i₀,j₀)同色的上、下、左、右的邻接点为同色区域的点。

解：

#include <iostream.h>

#include <stdlib.h>

typedef struct{

int x;

int y;

}PosType;

typedef struct{

int Color;

int Visited;

PosType seat;

}ElemType;

#include "d:VC99Stack.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]='';

x1=atoi(ch);

ch[0]=c2;

ch[1]='';

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:VC99DSConstant.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]='';

Push(s,ch);

}

else return FALSE;

}

else{

ch[0]=a[i];

ch[1]='';

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 退栈