数据结构习题集答案C语言版严蔚敏

-

第1章 绪论

1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。

解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序常作为一个整体进行考虑和处理。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构. z.

-

和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。

1.3 设有数据结构(D,R)，其中

Dd1,d2,d3,d4，Rr，rd1,d2,d2,d3,d3,d4

试按图论中图的画法惯例画出其逻辑结构图。

解：

1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。

解：

ADT ple*{

数据对象：D={r,i|r,i为实数}

数据关系：R={}

基本操作：

Initple*(&C,re,im)

操作结果：构造一个复数C，其实部和虚部分别为re和im

DestroyCmople*(&C)

操作结果：销毁复数C

Get(C,k,&e)

操作结果：用e返回复数C的第k元的值

Put(&C,k,e)

操作结果：改变复数C的第k元的值为e

IsAscending(C)

操作结果：如果复数C的两个元素按升序排列，则返回1，否则返回0

. z.

-

IsDescending(C)

操作结果：如果复数C的两个元素按降序排列，则返回1，否则返回0

Ma*(C,&e)

操作结果：用e返回复数C的两个元素中值较大的一个

Min(C,&e)

操作结果：用e返回复数C的两个元素中值较小的一个

}ADT ple*

ADT RationalNumber{

数据对象：D={s,m|s,m为自然数，且m不为0}

数据关系：R={}

基本操作：

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)

. z.

-

操作结果：若有理数R的两个元素按降序排列，则返回1，否则返回0

Ma*(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]!=*));

(3) switch {

case *

case *=y: z=abs(**y); break;

default: z=(*-y)/abs(*)*abs(y);

}

1.6 在程序设计中，常用下列三种不同的出错处理方式：

. z.

-

(1) 用e*it语句终止执行并报告错误；

(2) 以函数的返回值区别正确返回或错误返回；

(3) 设置一个整型变量的函数参数以区别正确返回或*种错误返回。

试讨论这三种方法各自的优缺点。

解：(1)e*it常用于异常错误处理，它可以强行中断程序的执行，返回操作系统。

(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){

. z.

-

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++)

* += delta;

. z.

-

}

(6) i=1; j=0;

while(i+j<=n) {

if(i>j) j++;

else i++;

}

(7) *=n; y=0; // n是不小于1的常数

while(*>=(y+1)*(y+1)) {

y++;

}

(8) *=91; y=100;

while(y>0) {

if(*>100) { * -= 10; y--; }

else *++;

}

解：(1) n-1

(2) n-1

(3) n-1

(4) n+(n-1)+(n-2)+...+1=n(n1)

2n (5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)=i1i(i1)

21n1n21n21n =i(i1)(ii)ii

2i12i12i12i1. z.

-

= (6) n

(7)

111n(n1)(2n1)n(n1)n(n1)(2n3)

12412n 向下取整

(8) 1100

1.9 假设n为2的乘幂，并且n>2，试求下列算法的时间复杂度及变量count的值（以n的函数形式表示）。

int Time(int n) {

count = 0; *=2;

while(*

}

return count;

* *= 2; count++;

}

解：o(log2n)

count=log2n2

1.11 已知有实现同一功能的两个算法，其时间复杂度分别为O2n和On10，假设现实计算机可连续运算的时间为107秒（100多天），又每秒可执行基本操作（根据这些操作来估算算法时间复杂度）105次。试问在此条件下，这两个算法可解问题的规模（即n值的围）各为多少？哪个算法更适宜？请说明理由。

解：2n1012

n101012

n=40

n=16

则对于同样的循环次数n，在这个规模下，第二种算法所花费的代价要大得多。. z.

-

故在这个规模下，第一种算法更适宜。

1.12 设有以下三个函数：

fn21n4n21000，gn15n4500n3，hn500n3.5nlogn

请判断以下断言正确与否：

(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值，比较两函数n2和50nlog2n的增长趋势，并确定n在什么围，函数n2的值大于50nlog2n的值。

解：n2的增长趋势快。但在n较小的时候，50nlog2n的值较大。

当n>438时，n250nlog2n

1.14 判断下列各对函数fn和gn，当n时，哪个函数增长更快？

(1)

fn10n2lnn!10n，gn2n4n7

3(2)

fnlnn!5，gn13n2.5

2(3)

fnn2.1n41，gnlnn!n

2232(4)

fn2n2n，gnnnn5

解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快

1.15 试用数学归纳法证明：

(1)

ii1n2nn12n1/6n0

. z.

-

(2)

xxnii0nn11/x1x1,n0

(3)

2i1ni12n1n1

(4)

2n1

2i1ni11.16试写一算法，自大至小依次输出顺序读入的三个整数*，Y和Z的值

解：

int ma*3(int *,int y,int z)

{

}

1.17 已知k阶斐波那契序列的定义为

f00，f10，…，fk20，fk11；

fnfn1fn2fnk，nk,k1,

if(*>y)

if(*>z) return *;

else return z;

else

if(y>z) return y;

else return z;

试编写求k阶斐波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。

解：k>0为阶数，n为数列的第n项

int Fibonacci(int k,int n)

. z.

-

{

if(k<1) e*it(OVERFLOW);

int *p,*;

p=new int[k+1];

if(!p) e*it(OVERFLOW);

int i,j;

for(i=0;i

}

1.18 假设有A，B，C，D，E五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一表，表中每一行的形式为

项目名称 性别 校名 成绩 得分

}

for(i=k+1;i

}

return p[k];

*=p[0];

for(j=0;j

p[k]=2*p[k-1]-*;

if(i

else p[i]=1;

编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。

解：

. z.

-

typedef enum{A,B,C,D,E} SchoolName;

typedef enum{Female,Male} Se*Type;

typedef struct{

char event[3]; //项目

Se*Type se*;

SchoolName school;

int score;

} ponent;

typedef struct{

int MaleSum; //男团总分

int FemaleSum; //女团总分

int TotalSum; //团体总分

} Sum;

Sum SumScore(SchoolName sn,ponent a[],int n)

{

Sum temp;

m=0;

Sum=0;

um=0;

int i;

for(i=0;i

if(a[i].school==sn){

. z.

-

}

}

}

if(a[i].se*==Male) m+=a[i].score;

if(a[i].se*==Female) Sum+=a[i].score;

um=m+Sum;

return temp;

1.19 试编写算法，计算i!*2i的值并存入数组a[0..arrsize-1]的第i-1个分量中(i=1,2,…,n)。假设计算机中允许的整数最大值为ma*int，则当n>arrsize或对*个k1kn，使k!•2kmaxint时，应按出错处理。注意选择你认为较好的出错处理方法。

解：

*include

*include

*define MA*INT 65535

*define ArrSize 100

int fun(int i);

int main()

{

int i,k;

int a[ArrSize];

cout<<"Enter k:";

. z.

-

}

cin>>k;

if(k>ArrSize-1) e*it(0);

for(i=0;i<=k;i++){

}

for(i=0;i<=k;i++){

}

return 0;

if(a[i]>MA*INT) e*it(0);

else cout<

if(i==0) a[i]=1;

else{

}

if(2*i*a[i-1]>MA*INT) e*it(0);

else a[i]=2*i*a[i-1];

1.20 试编写算法求一元多项式的值Pnxaixi的值Pnx0，并确定算法中每i0n一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为aii0,1,,n，x0和n，输出为Pnx0。

解：

*include

*include

*define N 10

. z.

-

double polynomail(int a[],int i,double *,int n);

int main()

{

double *;

}

double polynomail(int a[],int i,double *,int n)

{

}

本算法的时间复杂度为o(n)。

if(i>0) return a[n-i]+polynomail(a,i-1,*,n)**;

else return a[n];

int n,i;

int a[N];

cout<<"输入变量的值*:";

cin>>*;

cout<<"输入多项式的阶次n:";

cin>>n;

if(n>N-1) e*it(0);

cout<<"输入多项式的系数a[0]--a[n]:";

for(i=0;i<=n;i++) cin>>a[i];

cout<<"The polynomail value is "<

return 0;

. z.

-

第2章 线性表

2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。

2.2 填空题。

解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。

(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。

(3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。

(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。

2.3 在什么情况下用顺序表比链表好？

解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。

2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。

解：

2.5 画出执行下列各行语句后各指针及链表的示意图。

L=(LinkList)malloc(sizeof(LNode)); P=L;

. z.

-

for(i=1;i<=4;i++){

}

P->ne*t=NULL;

for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2);

for(i=1;i<=3;i++) Del_LinkList(L,i);

解：

P->ne*t=(LinkList)malloc(sizeof(LNode));

P=P->ne*t; P->data=i*2-1;

2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是__________________。

b. 在P结点前插入S结点的语句序列是__________________。

c. 在表首插入S结点的语句序列是__________________。

d. 在表尾插入S结点的语句序列是__________________。

(1) P->ne*t=S;

(2) P->ne*t=P->ne*t->ne*t;

(3) P->ne*t=S->ne*t;

(4) S->ne*t=P->ne*t;

(5) S->ne*t=L;

(6) S->ne*t=NULL;

(7) Q=P;

(8) while(P->ne*t!=Q) P=P->ne*t;

. z.

-

(9) while(P->ne*t!=NULL) P=P->ne*t;

(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->ne*t;

(2) P->ne*t=P;

(3) P->ne*t=P->ne*t->ne*t;

(4) P=P->ne*t->ne*t;

(5) while(P!=NULL) P=P->ne*t;

(6) while(Q->ne*t!=NULL) { P=Q; Q=Q->ne*t; }

. z.

-

(7) while(P->ne*t!=Q) P=P->ne*t;

(8) while(P->ne*t->ne*t!=Q) P=P->ne*t;

(9) while(P->ne*t->ne*t!=NULL) P=P->ne*t;

(10) Q=P;

(11) Q=P->ne*t;

(12) P=L;

(13) L=L->ne*t;

(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->ne*t=P->ne*t->ne*t;

(2) P->priou=P->priou->priou;

. z.

-

(3) P->ne*t=S;

(4) P->priou=S;

(5) S->ne*t=P;

(6) S->priou=P;

(7) S->ne*t=P->ne*t;

(8) S->priou=P->priou;

(9) P->priou->ne*t=P->ne*t;

(10) P->priou->ne*t=P;

(11) P->ne*t->priou=P;

(12) P->ne*t->priou=S;

(13) P->priou->ne*t=S;

(14) P->ne*t->priou=P->priou;

(15) Q=P->ne*t;

(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 简述以下算法的功能。

. z.

-

(1) Status A(LinkedList L) { //L是无表头结点的单链表

}

if(L && L->ne*t) {

}

return OK;

Q=L; L=L->ne*t; P=L;

while(P->ne*t) P=P->ne*t;

P->ne*t=Q; Q->ne*t=NULL;

(2) void BB(LNode *s, LNode *q) {

}

void AA(LNode *pa, LNode *pb) {

}

解：(1) 如果L的长度不小于2，将L的首元结点变成尾元结点。

(2) 将单循环链表拆成两个单循环链表。

2.10 指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。

//pa和pb分别指向单循环链表中的两个结点

BB(pa,pb);

BB(pb,pa);

p=s;

while(p->ne*t!=q) p=p->ne*t;

p->ne*t =s;

. z.

-

Status DeleteK(SqList &a,int i,int k)

{

//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素

if(i<1||k<0||i+k>) return INFEASIBLE;//参数不合法

else {

for(count=1;count

}

解：

Status DeleteK(SqList &a,int i,int k)

{

//从顺序存储结构的线性表a中删除第i个元素起的k个元素

//注意i的编号从0开始

int j;

if(i<0||i>-1||k<0||k>-i) return INFEASIBLE;

for(j=0;j<=k;j++)

[j+i]=[j+i+k];

}

//删除第一个元素

for(j=;j>=i+1;j--) [j-i]=[j];

--;

return OK;

=-k;

. z.

-

}

return OK;

2.11 设顺序表va中的数据元素递增有序。试写一算法，将*插入到顺序表的适当位置上，以保持该表的有序性。

解：

Status InsertOrderList(SqList &va,ElemType *)

{

}

2.12 设Aa1,,am和Bb1,,bn均为顺序表，A和B分别为A和B中除去最大共同前缀后的子表。若AB空表，则AB；若A=空表，而B空表，或者两者均不为空表，且A的首元小于B的首元，则AB；否则AB。试写一个比较A，B大小的算法。

解：

Status pareOrderList(SqList &A,SqList &B)

//在非递减的顺序表va中插入元素*并使其仍成为顺序表的算法

int i;

if(==ze)return(OVERFLOW);

for(i=;i>0,*<[i-1];i--)

[i]=[i-1];

[i]=*;

++;

return OK;

. z.

-

{

}

2.13 试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,*);

解：

int LocateElem_L(LinkList &L,ElemType *)

{

int i=0;

LinkList p=L;

while(p&&p->data!=*){

}

p=p->ne*t;

i++;

int i,k,j;

k=>":;

for(i=0;i

}

if(>k) j=1;

if(>k) j=-1;

if(==) j=0;

return j;

if([i]>[i]) j=1;

if([i]<[i]) j=-1;

. z.

-

}

if(!p) return 0;

else return i;

2.14 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。

解：

//返回单链表的长度

int ListLength_L(LinkList &L)

{

}

2.15 已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起，假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。

解：

int i=0;

LinkList p=L;

if(p) p=p-ne*t;

while(p){

}

return i;

p=p->ne*t;

i++;

. z.

-

void MergeList_L(LinkList &ha,LinkList &hb,LinkList &hc)

{

}

2.16 已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第i个元素LinkList pa,pb;

pa=ha;

pb=hb;

while(pa->ne*t&&pb->ne*t){

}

if(!pa->ne*t){

}

else{

}

hc=ha;

while(pa->ne*t) pa=pa->ne*t;

pa->ne*t=hb->ne*t;

hc=hb;

while(pb->ne*t) pb=pb->ne*t;

pb->ne*t=ha->ne*t;

pa=pa->ne*t;

pb=pb->ne*t;

. z.

-

之前。试问此算法是否正确？若有错，请改正之。

Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len)

{

}

解：

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

if(i<0||j<0||len<0) return INFEASIBLE;

p=la; k=1;

while(kne*t; k++; }

q=p;

while(k<=len){

s=lb; k=1;

while(kne*t; k++; }

s->ne*t=p; q->ne*t=s->ne*t;

return OK;

q=q->ne*t; k++; }

. z.

-

}

prev=p;

p=p->ne*t;

k++;

if(!p)return INFEASIBLE;

// 在la表中查找第i+len-1个结点

q=p; k=1;

while(q&&k

}

if(!q)return INFEASIBLE;

// 完成删除，注意，i=1的情况需要特殊处理

if(!prev) la=q->ne*t;

else prev->ne*t=q->ne*t;

// 将从la中删除的结点插入到lb中

if(j=1){

}

else{

s=lb; k=1;

q->ne*t=lb;

lb=p;

q=p->ne*t;

k++;

. z.

-

}

}

while(s&&k

}

if(!s)return INFEASIBLE;

q->ne*t=s->ne*t;

s->ne*t=p; //完成插入

s=s->ne*t;

k++;

return OK;

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

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

2.19 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于ma*k的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和ma*k是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。

解：

Status ListDelete_L(LinkList &L,ElemType mink,ElemType ma*k)

{

LinkList p,q,prev=NULL;

. z.

-

}

if(mink>ma*k)return ERROR;

p=L;

prev=p;

p=p->ne*t;

while(p&&p->data

}

return OK;

if(p->data<=mink){

}

else{

}

prev->ne*t=p->ne*t;

q=p;

p=p->ne*t;

free(q);

prev=p;

p=p->ne*t;

2.20 同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间，并分析你的算法的时间复杂度。

解：

. z.

-

void ListDelete_LSameNode(LinkList &L)

{

LinkList p,q,prev;

p=L;

prev=p;

p=p->ne*t;

while(p){

prev=p;

p=p->ne*t;

if(p&&p->data==prev->data){

prev->ne*t=p->ne*t;

q=p;

p=p->ne*t;

free(q);

}

}

}

2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表a1,,an逆置为an,,a1。

解：

// 顺序表的逆置

Status ListOppose_Sq(SqList &L)

. z.

-

{

int i;

ElemType *;

for(i=0;i

*=[i];

[i]=[-1-i];

[-1-i]=*;

}

return OK;

}

2.22 试写一算法，对单链表实现就地逆置。解：

// 带头结点的单链表的逆置

Status ListOppose_L(LinkList &L)

{

LinkList p,q;

p=L;

p=p->ne*t;

L->ne*t=NULL;

while(p){

q=p;

p=p->ne*t;

. z.

-

}

}

q->ne*t=L->ne*t;

L->ne*t=q;

return OK;

Bb1,b2,,bn，2.23 设线性表Aa1,a2,,am，试写一个按下列规则合并A，B为线性表C的算法，即使得

Ca1,b1,,am,bm,bm1,,bn 当mn时；

Ca1,b1,,an,bn,an1,,am 当mn时。

线性表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->ne*t;

pb=B->ne*t;

C=A;

while(pa&&pb){

qa=pa; qb=pb;

pb=pb->ne*t; pa=pa->ne*t;

. z.

-

}

}

qb->ne*t=qa->ne*t;

qa->ne*t=qb;

if(!pa)qb->ne*t=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->ne*t;

. z.

pb=pb->ne*t;

A->ne*t=NULL;

C=A;

while(pa&&pb){

if(pa->datadata){

qa=pa;

pa=pa->ne*t;

qa->ne*t=A->ne*t;

A->ne*t=qa;

}

else{

qb=pb;

pb=pb->ne*t;

qb->ne*t=A->ne*t;

A->ne*t=qb;

}

}

while(pa){

qa=pa;

pa=pa->ne*t;

qa->ne*t=A->ne*t;

A->ne*t=qa;

.

-

//将当前最小结点插入A表表头//将当前最小结点插入A表表头 z.

-

}

}

while(pb){

}

pb=B;

free(pb);

return OK;

qb=pb;

pb=pb->ne*t;

qb->ne*t=A->ne*t;

A->ne*t=qb;

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< && j<){

if([i]<[j]) i++;

. z.

-

}

}

else

if([i]>[j]) j++;

else{

}

ListInsert_Sq(C,k,[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->ne*t;

pb=pb->ne*t;

. z.

-

C=A;

while(pa&&pb){

if(pa->datadata){

pt=pa;

pa=pa->ne*t;

qa->ne*t=pa;

free(pt);

}

else

if(pa->data>pb->data){

pt=pb;

pb=pb->ne*t;

qb->ne*t=pb;

free(pt);

}

else{

qa=pa;

pa=pa->ne*t;

}

}

while(pa){

pt=pa;

. z.

-

}

}

pa=pa->ne*t;

qa->ne*t=pa;

free(pt);

while(pb){

}

pb=B;

free(pb);

return OK;

pt=pb;

pb=pb->ne*t;

qb->ne*t=pb;

free(pt);

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)

. z.

-

{

}

(2)

int i=0,j=0,k=0;

while(i< && j<){

}

return OK;

if([i]<[j]) i++;

else

if([i]>[j]) j++;

else{

}

if(==0){

}

else

i++;

if([-1]!=[i]){

}

ListInsert_Sq(C,k,[i]);

k++;

ListInsert_Sq(C,k,[i]);

k++;

. z.

-

// A、B求交，然后删除相同元素，将结果放在A表中

Status ListCrossDelSame_Sq(SqList &A,SqList &B)

{

int i=0,j=0,k=0;

while(i< && j<){

if([i]<[j]) i++;

else

if([i]>[j]) j++;

else{

if(k==0){

[k]=[i];

k++;

}

else

if([k]!=[i]){

[k]=[i];

k++;

}

i++;

}

}

=k;

. z.

-

}

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->ne*t;

pb=pb->ne*t;

C=A;

while(pa&&pb){

if(pa->datadata){

. z.

-

pt=pa;

pa=pa->ne*t;

qa->ne*t=pa;

free(pt);

}

else

if(pa->data>pb->data){

pt=pb;

pb=pb->ne*t;

qb->ne*t=pb;

free(pt);

}

else{

if(pa->data==qa->data){

pt=pa;

pa=pa->ne*t;

qa->ne*t=pa;

free(pt);

}

else{

qa=pa;

pa=pa->ne*t;

. z.

-

}

(2)

}

}

}

while(pa){

}

while(pb){

}

pb=B;

free(pb);

return OK;

pt=pb;

pb=pb->ne*t;

qb->ne*t=pb;

free(pt);

pt=pa;

pa=pa->ne*t;

qa->ne*t=pa;

free(pt);

// A、B求交，结果放在A表中，并删除相同元素

Status ListCrossDelSame_L(LinkList &A,LinkList &B)

. z.

-

LinkList pa,pb,qa,qb,pt;

pa=A;

pb=B;

qa=pa; // 保存pa的前驱指针

qb=pb; // 保存pb的前驱指针

pa=pa->ne*t;

pb=pb->ne*t;

while(pa&&pb){

if(pa->datadata){

pt=pa;

pa=pa->ne*t;

qa->ne*t=pa;

free(pt);

}

else

if(pa->data>pb->data){

pt=pb;

pb=pb->ne*t;

qb->ne*t=pb;

free(pt);

}

. z.{

-

else{

if(pa->data==qa->data){

pt=pa;

pa=pa->ne*t;

qa->ne*t=pa;

free(pt);

}

else{

qa=pa;

pa=pa->ne*t;

}

}

}

while(pa){

pt=pa;

pa=pa->ne*t;

qa->ne*t=pa;

free(pt);

}

while(pb){

pt=pb;

pb=pb->ne*t;

. z.

-

}

}

qb->ne*t=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);

}

2.30 要求同2.29题。试对单链表编写算法，请释放A表中的无用结点空间。

解：

ListMinus_L(A,Temp,D);

. z.

-

// 在A中删除既在B中出现又在C中出现的元素，并释放B、C

Status ListUnion_L(LinkList &A,LinkList &B,LinkList &C)

{

}

// 求集合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->ne*t;

pb=pb->ne*t;

while(pa&&pb){

if(pb->datadata){

pt=pb;

pb=pb->ne*t;

qb->ne*t=pb;

free(pt);

ListCross_L(B,C);

ListMinus_L(A,B);

. z.

-

}

else

if(pb->data>pa->data){

qa=pa;

pa=pa->ne*t;

}

else{

pt=pa;

pa=pa->ne*t;

qa->ne*t=pa;

free(pt);

}

}

while(pb){

pt=pb;

pb=pb->ne*t;

qb->ne*t=pb;

free(pt);

}

pb=B;

free(pb);

return OK;

. z.