数据结构(c语言版)第三版习题解答

数据结构

C语言版）（第

习题解析

3版）

（

1

第1章 绪论

1.1什么是数据结构？

【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储

于计算机中，并在这些数据上定义了一个运算集合。

1.2 数据结构涉及哪几个方面？

【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集

合。

1.3 两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义不

一样，它们是否可以认作是同一个数据结构？为什么？

【答】：不能，运算集合是数据结构的重要组成部分，不同的运算集合所确定的数据结构是不

一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一样，

所以它们是两种不同的数据结构。

1.4 线性结构的特点是什么？非线性结构的特点是什么？

【答】：线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端结

点，其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性结构则没有这个特点，元

素之间的关系可以是一对多的或多对多的。

1.5 数据结构的存储方式有哪几种？

【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。

1.6 算法有哪些特点？它和程序的主要区别是什么？

【答】：算法具有（1）有穷性（2）确定性（3）0个或多个输入（4）1个或多个输出（5）可

行性等特征。程序是算法的一种描述方式，通过程序可以在计算机上实现算法。

1.7 抽象数据类型的是什么？它有什么特点？

【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。

抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对一

个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这

些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本

数据类型那样，十分方便地使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操作

的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。

1.8 算法的时间复杂度指的是什么？如何表示？

【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的

机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在

同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以

对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。算

法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为n的数据处理问题，用

T(n)表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写O符号表示算法

的时间复杂度，大写O符号给出了函数f的一个上限。其它义如下：

定义：f (n)=O (g (n)) 当且仅当存在正的常数c和n0，使得对于所有的n≥n0，有f (n) ≤c g(n)。

2

上述定义表明，函数f顶多是函数g的c倍，除非n 小于n0。因此对于足够大的n (如n≥n0)，

g是f 的一个上限（不考虑常数因子c）。在为函数f 提供一个上限函数g 时，通常使用比较

简单的函数形式。比较典型的形式是含有n的单个项（带一个常数系数）。表1-1列出了一些

常用的g函数及其名称。对于表1-1中的对数函数logn，没有给出对数基，原因是对于任何大

于1的常数a和b都有logan =logbn/logba,所以logan和logbn都有一个相对的乘法系数1/logba，

其中a是一个常量。

表1-1常用的渐进函数

函数 名称

1 常数

logn 对数

n 线性

nlogn n个logn

n2 平方

n3 立方

2n 指数

n! 阶乘

1.9 算法的空间复杂度指的是什么？如何表示？

【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表

示为问题规模的函数，并通过大写O符号表示空间复杂度。

1.10 对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度T(n)。

（1） i++;

（2） for(i=0;i

if (a[i]

（3）for(i=0;i

for(j=0;j

printf(“%d”,i+j);

（4）for (i=1;i<=n-1;i++)

{ k=i;

for(j=i+1;j<=n;j++)

if(a[j]>a[j+1]) k=j;

t=a[k]; a[k]=a[i]; a[i]=t;

}

（5）for(i=0;i

for(j=0;j

{++x;s=s+x;}

【答】：（1）O（1）；（2）O（n）；（3）O（n2）；（4）O（n2）；（5）O（n2）

3

第2章 线性表及其顺序存储

2.1 选择题

（1）表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，

插入一个元素所需移动元素的平均个数为（ E ），删除一个元素所需移动元素的平均个数

为（ A ）。

A．（n−1）/2 B．n C．n+1 D．n−1

E．n/2 F．(n+1)/2 G．(n−2)/2

（2）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，

一个元素出栈后即进入队列Q，若6个元素出队的序列为e2、e4、e3、e6、e5和e1，则栈S

的容量至少应该为（ C ）。

A．6 B．4 C．3 D．2

（3）设栈的输入序列为1、2、3… n，若输出序列的第一个元素为n，则第i个输出的元素为

（ B ）。

A．不确定 B．n−i+1 C．i D．n−i

（4）在一个长度为n的顺序表中删除第i个元素（1<=i<=n）时，需向前移动（ A ）个

元素。

A．n−i B．n−i+1 C．n−i−1 D．i

（5）若长度为n的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时

间复杂度为（ A ）。

A．O(n) B．O(1) C．O(n2) D．O(n3)

（6）表达式a*(b+c)−d的后缀表达式是（ B ）。

A．abcd*+− B．abc+*d− C．abc*+d− D．−+*abcd

（7）队列是一种特殊的线性表，其特殊性在于（ C ）。

A．插入和删除在表的不同位置执行 B．插入和删除在表的两端位置执行

C．插入和删除分别在表的两端执行 D．插入和删除都在表的某一端执行

（8）栈是一种特殊的线性表，具有（ B ）性质。

A．先进先出 B．先进后出 C．后进后出 D．顺序进出

（9）顺序循环队列中（数组的大小为n），队头指示front指向队列的第1个元素，队尾

指示rear指向队列最后元素的后1个位置，则循环队列中存放了n 1个元素，即循环队列满

的条件为（ B ）。

A．(rear+1)%n=front−1 B．(rear+1)%n=front

C．(rear)%n=front D．rear+1=front

（10）顺序循环队列中（数组的大小为6），队头指示front和队尾指示rear的值分别为3

和0，当从队列中删除1个元素，再插入2个元素后，front和rear的值分别为（ D ）。

A．5和1 B．2和4 C．1和5 D．4和2

2.2什么是顺序表？什么是栈？什么是队列？

4

【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表

现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶），

因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约

定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具

有先进先出，后进后出的特点。

2.3设计一个算法，求顺序表中值为x的结点的个数。

【答】：顺序表的存储结构定义如下：

#include

#define N 100 /*预定义最大的数据域空间*/

typedef int datatype; /*假设数据类型为整型*/

typedef struct {

datatype a[N]; /*此处假设数据元素只包含一个整型的关键字域*/

int size; /*线性表长度*/

} sequence_list; /*预定义的顺序表类型*/

算法count()用于求顺序表H中值为x的结点的个数。

int count (sequence_list

*H,datatype x)

{ int j=0;

int i;

for (i=0;isize;i++)

if (H->a[i]==x) j++;

return j;

}

2.4 设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组a中，倒

置的结果是使得数组a中的a[0]等于原来的最后一个元素，a[1] 等于原来的倒数第2个元

素，…，a的最后一个元素等于原来的第一个元素。

【答】：实现顺序表倒置的算法程序如下：

void verge(seqlist *L)

{int t,i,j;

i=0;

j=L->length-1;

while (i

{ t=L->data[i];

L->data[i++]=L->data[j];

L->data[j--]=t;

}

}

2.5已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x的结点，

使顺序表中的结点仍然是从小到大有序。

【答】：实现本题要求的算法程序如下：

5

void insertx(seqlist *L,datatype x)

{int j;

if (L->length

{ j=L->length-1;

while (j>=0 && L->data[j]>x)

{ L->data[j+1]=L->data[j];

j--;

}

L->data[j+1]=x;

L->length++;

}

}

2.6 将下列中缀表达式转换为等价的后缀表达式。

(1) 5+6*7

(2) (5-6)/7

(3) 5-6*7*8

(4) 5*7-8

(5) 5*(7-6)+8/9

(6) 7*(5-6*8)-9

【答】：

(7) 5+6*7 后缀表达式：5 6 7*+

(8) (5-6)/7 后缀表达式：5 6-7/

(9) 5-6*7*8 后缀表达式：5 6 7*8*-

(10) 5*7-8 后缀表达式：5 7* 8-

(11) 5*(7-6)+8/9 后缀表达式：5 7 6-*8 9/+

(12) 7*(5-6*8)-9 后缀表达式：7 5 6 8*-*9-

2.7 循环队列存储在一个数组中，数组大小为n，队首指针和队尾指针分别为front和rear，请

写出求循环队列中当前结点个数的表达式。

【答】：循环队列中当前结点个数的计算公式是：(n+rear-front)%n

2.8编号为1,2,3,4的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如果

有n列火车通过调度站，请设计一个算法，输出所有可能的调度结果。

【答】：

方法一：

算法思想：逐次输出所有可能，用回溯法。即：

总体：对原始序列中的每一个元素，总是先入栈，后出栈

1．入栈后的操作：a.该元素出栈；b.下一个元素入栈；

2．出栈后的操作：a.（栈中其他元素）继续出栈；b. （原始序列中）下一个数入栈；

注意：回溯法，关键在于回溯，即在某分支结点X：处理X的一个子分支，再退回分支X，

接着处理X的下一个子分支,若所有X的子分支处理完，再退回上一层分支节点。所谓“退回”，

6

实际上就是恢复。

程序代码：(2_8_1.c)

#include

#define MAX 26

typedef struct s{

char a[MAX];

int top;

}Stack;

/*定义一些全局变量*/

Stack S; /*定义全局性的栈*/

char d[MAX],seq[MAX]; /*d[MAX]用于存储原始入栈序列，int len; /*定义将通过栈的元素个数*/

int count=0; /* 用于统计输出序列的个数 */

void initStack(Stack *S) /*初始化空栈*/

{ S->top=-1; }

void push(Stack *S, char x) /*进栈*/

{ if (S->top>=MAX) return;

S->top++;

S->a[S->top]=x;

}

char pop(Stack *S)/*出栈*/

{ if (S->top==-1)

{ printf("ERROR, POP Empty Stack");

return -1;

}

S->top--;

return S->a[S->top+1];

}

int isEmpty(Stack *S)/*判断栈是否为空*/

{ if (S->top==-1) return 1;

return 0;

}

void outSeq(char *seq, int len)/*输出顶点序列*/

{ int i;

for(i=0; i

printf("%2c",seq[i]);

printf("n");

}

void scheduler(int pos, int seq_pos)

7

seq[MAX]用于存储输出序列*/

{ /* pos: 处理到原始数据中的第pos个元素，

seq_pos：若出栈，应放在当前输出数组的第seq_pos个位置

*/

int i=0;char t;

/*对任何一个数，总是先进栈，再出栈。另外，这里不需要循环，类似于“查找数组中元

素”用递归*/

if(pos

push(&S,d[pos]);

scheduler(pos+1,seq_pos);

pop(&S);

}

if (!isEmpty(&S)){/*一个数出栈后,有两种处理方式：要么继续出栈,要么继续下一个数的进

栈*/

t=pop(&S);

seq[seq_pos++]=t;

scheduler(pos,seq_pos);

push(&S,t);

}

if (pos>=len && isEmpty(&S))

{ outSeq(seq,len); count++; }

}

int main(){

int i;

printf("nplease input the num be scheduled: ");

scanf("%d", &len); /*用len存储待调度的火车数量*/

for(i=0; i

d[i]='a'+i; /*创建火车编号，如a、b、c、...等*/

printf("the original seq is:");

outSeq(d,len);

initStack(&S);

scheduler(0,0);

printf("n count=%5d", count);

return 0;

}

方法二：

解题思路：栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是1，2，3，

4全排列中的一个元素。由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：对

于序列中的任何一个数其后面所有比它小的数应该是倒序的，例如4321是一个有效的出栈序

8

列，1423不是一个有效的出栈结果（4后面比它小的两个数2，3不是倒序）。据此，本题可以

通过算法产生n个数的全排列，然后将满足出栈规则的序列输出。

产生n个数的全排列有递归与非递归两种实现算法。

产生全排列的递归算法：

设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。集合X中元素的全排列记为

perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀ri得到的排列。R的全排

列可归纳定义如下：

当n=1时，perm(R)=(r)，其中r是集合R中惟一的元素；

当n>1时，perm(R)由(r1)perm(R1),(r2)perm(R2),…,(rn)perm(Rn)构成。

依此递归定义，可设计产生perm(R)的递归算法如下：

递归解法：(2_8_2.c)

#include

int cont=1; /*全局变量，用于记录所有可能的出栈序列个数*/

void print(int str[],int n);

/*求整数序列str[]从k到n的全排列*/

void perm(int str[],int k,int n)

{int i,temp;

if (k==n-1) print(str,n);

else

{ for (i=k;i

{temp=str[k]; str[k]=str[i];

str[i]=temp;

perm(str,k+1,n); /*递归调用*/

temp=str[i]; str[i]=str[k];

str[k]=temp;

}

}

}

/*本函数判断整数序列str[]是否满足进出栈规则,若满足则输出*/

void print(int str[],int n)

{int i,j,k,l,m,flag=1,b[2];

for(i=0;i

{ m=0;

for(j=i+1;j

if (str[i]>str[j]) {if (m==0)

b[m++]=str[j];

else {if (str[j]>b[0]) {flag=0;}

else b[0]=str[j];

}

}

}

if(flag) /*满足出栈规则则输出str[]中的序列*/

9

{ printf(" %2d:",cont++);

for(i=0;i

printf("%d",str[i]);

printf("n");

}

}

int main()

{int str[100],n,i;

printf("input a int:"); /*输出排列的元素个数*/

scanf("%d",&n);

for(i=0;i

str[i]=i+1;

printf("input the result:n");

perm(str,0,n);

printf("n");

return 0;

}

当参与进出栈的元素个数为4时，输出的结果如下图所示。

该算法执行的时间复杂度为O（n!）。随着n的增大，算法的执行效率非常的低。

非递归解法：（2_8_3.c）

对一组数穷尽所有排列，还可一种更直接的方法，将一个排列看作一个长整数，则所有排

列对应着一组整数，将这组整数按从小到大的顺序排成一个数列，从对应最小的整数开始，按

数列的递增顺序逐一列举每个排列对应的每一个整数，这能更有效地完成排列的穷举。从一个

排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为

1,2,4,6,5,3，并令其对应的长整数为124653。要寻找比长整数124653更大的排列，可从该排列

的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大时，如本例中

的6比它的前一位数字4大，则说明还有可能对应更大整数的排列。但为顺序从小到大列举出

所有的排列，不能立即调整得太大，如本例中将数字6与数字4交换得到的排列为126453就

不是排列124653的下一个排列。为得到排列124653的下一个排列，应从已考察过的那部分数

10

字中选出比数字4大，但又是它们中最小的那一个数字，比如数字5，与数字4交换。该数字

也是从后向前考察过程中第一个比4大的数字，5与4交换后，得到排列125643。在前面数字

1，2，5固定的情况下，还应选择对应最小整数的那个排列，为此还需将后面那部分数字的排

列颠倒，如将数字6，4，3的排列顺序颠倒，得到排列1,2,5,3,4,6，这才是排列1，2，4，6，

5，3的下一个排列。按照以上想法可以编写非递归程序实现n个数的全排列，对满足进出栈

规则的排列则计数并输出。

/*本程序输出1 2 ... n个序列进栈出栈的序列*/

#include

int pl(int n)

{ int a[100]; /*最大处理范围为99个数*/

int flag=1,flag1=0;

FILE *rf ;

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

rf = fopen("", "w") ; /*用于存放进出栈序列结果*/

for (i=1;i<=n;i++) /*初始序列*/

a[i]=i;

while (flag) /* 还剩余未输出的排列*/

{ flag1=1; /* 判断本次排列是否符合进栈出栈序列 */

for (i=1;i<=n;i++)

{ j=i+1;

while (j<=n && a[j]>a[i]) j++; /* 找a[i]后第一个比a[i]小的元素a[j]*/

k=j+1;

while (k<=n) /* 如果a[j]后还有比a[i]小且比a[j]大的元素,则此排列无效*/

{if ( a[k] a[j]) flag1=0;

k++;

}

}

if (flag1)

{ for (i=1;i<=n;i++) /*输出当前排列*/

{ printf("%4d",a[i]);

fprintf(rf,"%4d",a[i]);}

printf("n");

fprintf(rf,"n");

count++; /*计数器加1*/

}

i=n; /*从后向前找相邻位置后大前小的元素值*/

while (i>1 && a[i]

if (i==1) flag=0; /*未找到则结束*/

else

{j=i-1;i=n;/* 若找到,则在该位置的后面从右向左找第一个比该元素大的值*/

while (i>j && a[i]

11

k=a[j]; /*交换两元素的值*/

a[j]=a[i];

a[i]=k;

k=j+1; /*对交换后后面的数据由小到大排序*/

for ( i=k+1;i<=n;i++) /*插入排序*/

{ j=i-1;

x=a[i];

while (j>=k && x

a[j+1]=x;

}

}

}

fclose(rf);

return count; /*返回排列总个数*/

}

void main()

{int n,m=0;

printf("please input n:"); /*输入排列规模*/

scanf("%d",&n);

m=pl(n);

printf("nm=%d",m); /*输出满足进出栈的排列总个数*/

}

程序运行时如果输入4，则输出的结果如下图所示。

该算法的时间复杂度也是O(n!)。

结论：如果n个数按编号由小到大的顺序进栈，进栈的过程中可以出栈，则所有可能的出栈序

列的总数为：

n

)!2(

nnn!!)1(

12

第3章 线性表的链式存储

3.1 选择题

（1）两个有序线性表分别具有n个元素与m个元素且n≤m，现将其归并成一个有序表，

其最少的比较次数是（ A ）。

A．n B．m C．n−1 D．m+n

（2）非空的循环单链表head的尾结点（由p所指向）满足（ C ）。

A．p->next==NULL B．p==NULL C．p->next==head D．p==head

（3）在带头结点的单链表中查找x应选择的程序体是（ C ）。

A．node *p=head->next; while (p && p->info!=x) p=p->next;

if (p->info==x) return p else return NULL;

B．node *p=head; while (p&& p->info!=x) p=p->next; return p;

C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p;

D．node *p=head; while (p->info!=x) p=p->next ; return p;

（4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。

A．必须是连续的 B．部分地址必须是连续的

C．一定是不连续的 D．连续不连续都可以

（5）在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间

复杂度是（ B ）。

A．O(1) B．O(n) C．O(n2) D．O(nlog2n)

（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队

尾结点，则在进行删除操作时（ D ）。

A．仅修改队头指针 B．仅修改队尾指针

C．队头、队尾指针都要修改 D．队头,队尾指针都可能要修改

（7）若从键盘输入n个元素，则建立一个有序单向链表的时间复杂度为（ B ）。

A．O(n) B．O(n2) C．O(n3) D．O(n×log2n)

（8）下面哪个术语与数据的存储结构无关（ D ）。

A．顺序表 B．链表 C．散列表 D．队列

（9）在一个单链表中，若删除p所指结点的后续结点，则执行（ A ）。

A．p->next=p->next->next; B．p=p->next; p->next=p->next->next;

C．p->next=p->next; D．p =p->next->next;

（10）在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（ B ）。

A．s->next=p;p->next=s; B．s->next=p->next;p->next=s;

C．s->next=p->next;p=s; D．p->next=s;s->next=p;

3.2 设计一个算法，求一个单链表中的结点个数。

【答】：单链表存储结构定义如下（相关文件：linklist.h）

#include

13

#include

typedef struct node

{ int data;

struct node *next;

}linknode;

typedef linknode *linklist;

/*尾插法创建带头结点的单链表*/

linklist creatlinklist()

{ linklist head,r,s;

int x;

head=r=(linklist)malloc(sizeof(linknode));

printf("n请输入一组以0结束的整数序列：

n");

scanf("%d",&x);

while (x)

{ s=(linklist)malloc(sizeof(linknode));

s->data=x;

r->next=s;

r=s;

scanf("%d",&x);

}

r->next=NULL;

return head;

}

/*输出带头结点的单链表*/

void print(linklist head)

{ linklist p;

p=head->next;

printf("List is:n");

while(p)

{ printf("%5d",p->data);

p=p->next;

}

printf("n");

}

基于上述结构定义，求单链表中的结点个数的算法程序如下：

int count(linklist head)

{ int c=0;

linklist p=head;

while (p)

14

{c++;

p=p->next;

}

return c;

}

3.3设计一个算法，求一个带头结点单链表中的结点个数。

【答】：带头结点的单链表的存储结构定义同题3.2，实现本题功能的算法程序如下（3_3.c）

#include "linklist.h"

int count(linklist head)

{ int c=0;

linklist p=head->next;

while (p)

{c++;

p=p->next;

}

return c;

}

main() /*测试函数*/

{linklist head;

head=creatlinklist();

print(head);

printf("nLength of head is:%d",count(head));

getch();

}

当输入5个数据时，产生的输出结果如下图所示：

3.4设计一个算法，在一个单链表中值为y的结点前面插入一个值为x的结点。即使值为x的

新结点成为值为y的结点的前驱结点。

【答】：

#include "linklist.h"

void insert(linklist head,int y,int

x)

{/*

在值为y的结点前插入一个值为x的结点*/

linklist pre,p,s;

pre=head;

15

p=head->next;

while (p && p->data!=y)

{ pre=p;

p=p->next;

}

if (p)/*找到了值为y的结点*/

{ s=(linklist)malloc(sizeof(linknode));

s->data=x;

s->next=p;

pre->next=s;

}

}

void main() /*测试程序*/

{linklist head;

int y,x;

head=creatlinklist(); /*创建单链表*/

print(head); /*输出单链表*/

printf("n请输入y与x的值:n");

scanf("%d %d",&y,&x);

insert(head,y,x);

print(head);

}

程序的一种运行结果如下图所示：

3.5设计一个算法，判断一个单链表中各个结点值是否有序。

【答】：

#include "linklist.h"

int issorted(linklist head,char c)

/*当参数c=a时判断链表是否为升序，当参数c=d是判断链表是否为降序*/

{ int flag=1;

linklist p=head->next;

switch (c)

16

{case 'a':/*判断带头结点的单链表head是否为升序*/

while (p &&p->next && flag)

{if (p->data<=p->next->data) p=p->next;

else flag=0;

}

break;

case 'd':/*判断带头结点的单链表head是否为降序*/

while (p &&p->next && flag)

{if (p->data>=p->next->data) p=p->next;

else flag=0;

}

break;

}

return flag;

}

int main() /*测试程序*/

{ linklist head;

head=creatlinklist();

print(head);

if (issorted(head,'a')) printf("单链表head是升序排列的！n");

else

if (issorted(head,'d')) printf("单链表head是降序排列的！n");

else printf("单链表head是无序的！n");

}

程序运行时的三种输出结果如下图所示：

3.6设计一个算法，利用单链表原来的结点空间将一个单链表就地转置。

【答】：

#include "linklist.h"

void verge(linklist head)

17

{/*本函数的功能是就地倒置带头结点的单链表*/

linklist p,q;

p=head->next;

head->next=NULL;

while (p) /*每次从原表取一个结点插入到新表的最前面*/

{q=p;

p=p->next;

q->next=head->next;

head->next=q;

}

}

int main() /*测试函数*/

{linklist head;

head=creatlinklist(); /*创建单链表*/

print(head); /*输出原单链表*/

verge(head); /*就地倒置单链表*/

print(head); /*输出倒置后的单链表*/

}

3.7设计一个算法，将一个结点值自然数的单链表拆分为两个单链表，原表中保留值为偶数的

结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表。

【答】：

#include "linklist.h"

linklist sprit(linklist head)

{ /*将带头结点的单链表head中的奇数值结点删除生成新的单链表并返回*/

linklist L,pre,p,r;

L=r=(linklist)malloc(sizeof(linknode));

r->next=NULL;

pre=head;

p=head->next;

while (p)

{ if (p->data%2==1) /*删除奇数值结点*/

{ pre->next=p->next;

r->next=p;

r=p;

p=pre->next;

}

else /*保留偶数值结点*/

{ pre=p;

p=p->next;

18

}

}

r->next=NULL; /*置链表结束标记*/

return L;

}

int main() /*测试函数*/

{linklist head,L;

head=creatlinklist(); /*创建单链表*/

print(head); /*输出原单链表*/

L=sprit(head); /*分裂单链表head*/

printf("n原单链表为:n");

print(head); /*输出倒置后的单链表*/

printf("n分裂所得奇数单链表为:n");

print(L);

}

本程序的一组测试情况如下图所示。

3.8设计一个算法，对一个有序的单链表，删除所有值大于x而不大于y的结点。

【答】：

#include "linklist.h"

void deletedata(linklist head,datatype x,datatype

y)

删除带头结点单链表中所有结点值大于x而不大于y的结点*/

{ /* linklist pre=head,p,q;

p=head->next; /*初始化*/

while (p && p->data<=x) /*找第1处大于x的结点位置*/

{ pre=p;

p=p->next;

}

while (p && p->data<=y) /*找第1处小于y的位置*/

p=p->next;

q=pre->next; /*删除大于x而小于y的结点*/

pre->next=p;

19

pre=q->next;

while (pre!=p) /*释放被删除结点所占用的空间*/

{free(q);

q=pre;

pre=pre->next;

}

}

void main() /*测试函数*/

{ linklist head,L;

datatype x,y;

head=creatlinklist(); /*创建单链表*/

print(head); /*输出原单链表*/

printf("n请输入要删除的数据区间:n");

scanf("%d%d",&x,&y);

deletedata(head,x,y);

print(head); /*输出删除后的单链表*/

}

3.9设计一个算法，在双链表中值为y的结点前面插入一个值为x的新结点。即使值为x的新

结点成为值为y的结点的前驱结点。

【答】：

首先定义双链表的数据结构，相关文件dlink.h，内容如下：

typedef int datatype; /*预定义的数据类型*/

typedef struct dlink_node{ /*双链表结点定义*/

datatype data;

struct dlink_node *llink,*rlink;

}dnode;

typedef dnode* dlinklist; /*双链表结点指针类型定义*/

/*尾插法创建带头结点的双链表*/

dlinklist creatdlinklist(void)

{ dlinklist head,r,s;

datatype x;

head=r=(dlinklist) malloc(sizeof(dnode)); /*建立双链表的头结点*/

head->llink=head->rlink=NULL;

printf("n请输入双链表的内容：（整数序列，以0结束）n");

scanf("%d",&x);

while (x) /*输入结点值信息，以0结束*/

{ s=(dlinklist ) malloc(sizeof(dnode));

s->data=x;

20

s->rlink=r->rlink; /*将新结点s插入到双链表链尾*/

s->llink=r;

r->rlink=s;

r=s;

scanf("%d",&x);

}

return head;

}

/*输出双链表的内容*/

void print(dlinklist head)

{ dlinklist p;

p=head->rlink;

printf("n双链表的内容是：n");

while (p)

{ printf("%5d",p->data);

p=p->rlink;

}

}

本题的求解程序如下：

#include

#include "dlink.h"

void insertxaty(dlinklist head,datatype y,datatype

x)

{ dlinklist s,p;

/*首先在双链表中找y所在的结点，然后在y前面插入新结点*/

p=head->rlink;

while (p && p->data!=y)

p=p->rlink;

if (!p) printf("n双链表中不存在值为y的结点,无法插入新结点!n");

else /*插入值为x的新结点*/

{ s=(dlinklist)malloc(sizeof(dnode));

s->data=x;

s->rlink=p;

s->llink=p->llink;

p->llink->rlink=s;

p->llink=s;

}

}

void main() /*测试函数*/

{ dlinklist head;

21

datatype x,y;

head=creatdlinklist();

print(head);

printf("n请输入要输入的位置结点值y:n");

scanf("%d",&y);

printf("n请输入要输入的结点值x:n");

scanf("%d",&x);

insertxaty(head,y,x);/*在值为y的结点前插入值为x的新结点*/

print(head);/*输出新的双链表*/

getch();

}

本程序的一组测试情况如下图所示。

3.10设计一个算法，从右向左打印一个双链表中各个结点的值。

【答】：

本题的双链表定义同题3.9，实现从右向左打印双链表的各个结点的值可以用递归程序实

现如下：

#include

#include "dlink.h"

void vprint(dlinklist head)

{ /*递归方法从右向左打印双链表的值*/

if (head->rlink)

{vprint(head->rlink);

printf("%5d",head->rlink->data);

}

}

void main() /*测试函数*/

{ dlinklist head;

head=creatdlinklist();

print(head);

22

printf("n从右向左打印的双链表的内容是:n");

vprint(head);

getch();

}

本程序的一组测试情况如下图所示。

3.11设计一个算法，将一个双链表改建成一个循环双链表。

【答】：

#include

#include "dlink.h"

/*将一个双链表改成循环双链表*/

void dlinktocdlink(dlinklist head)

{ dlinklist r;

r=head;

while (r->rlink) /*寻找尾结点*/

r=r->rlink;

head->llink=r;

r->rlink=head;

}

void printcdlink(dlinklist head)

{ /*打印双链表*/

dlinklist p;

p=head->rlink;

while (p!=head)

{printf("%5d",p->data);

p=p->rlink;

}

}

int main() /*测试函数*/

{ dlinklist head;

head=creatdlinklist();

dlinktocdlink(head);

printf("n循环双链表的内容是：n");

printcdlink(head);

}

23

第4章 字符串、数组和特殊矩阵

4.1 稀疏矩阵常用的压缩存储方法有（ 三元组顺序存储 ）和（ 十字链表 ）两种。

4.2 设有一个1010的对称矩阵A采用压缩方式进行存储，存储时以按行优先的顺序存

储其下三角阵，假设其起始元素a00的地址为1，每个数据元素占2个字节，则a65的地址为

（ 53 ）。

4.3 若串S=“software”，其子串的数目为（ 36 ）。

4.4 常对数组进行的两种基本操作为（ 访问数据元素 ）和（ 修改数组元素 ）。

4.5 要计算一个数组所占空间的大小，必须已知（数组各维数）和（每个元素占用的空

间）。

4.6 对于半带宽为b的带状矩阵，它的特点是：对于矩阵元素aij ，若它满足（|i-j|>b），

则aij=0。

4.7 字符串是一种特殊的线性表，其特殊性体现在（ 该线性表的元素类型为字符 ）。

4.8 试编写一个函数，实现在顺序存储方式下字符串的strcompare（S1，S2）运算。

【答】：

#include

#include

#define MAXSIZE 100

typedef struct{

char str[MAXSIZE];

int length;

}seqstring;

/* 函数strcompare()的功能是：当s1>s2时返回1，当s1==s2时返回0，当s1

int strcompare(seqstring s1,seqstring s2)

{ int i,m=0,len;

len=< ?:;

for(i=0;i<=len;i++)

if([i]>[i])

{m=1;break;}

else if([i]<[i])

{m=-1;break;}

return m;

}

int main()

{ seqstring s1,s2;

int i,m;

printf("input char to s1:n");

24

gets();

=strlen();

printf("input char to s2:n");

gets();

=strlen();

m=strcompare(s1,s2);

if(m==1) printf("s1>s2n");

else if(m==-1) printf("s2>s1n");

else if(m==0) printf("s1=s2n");

}

4.9 试编写一个函数，实现在顺序存储方式下字符串的replace（S，T1，T2）运算。

【参考程序1】：

/*本程序用来在顺序存储下用快速匹配模式实现在字符串S中用T2替换所有T1出现的可

能*/

#include

#include

#include

# define maxsize 100

typedef struct{

char str[maxsize];

int length ;

} seqstring;

//求next[]函数

void getnext(seqstring*p,int next[])

{int i,j;

next[0]=-1;

i=0;j=-1;

while(ilength)

{

if(j==-1||p->str[i]==p->str[j])

{++i;++j;next[i]=j;}

else

j=next[j];

}

}

//快速模式匹配算法

int kmp(seqstring*t,seqstring*p,int next[],int

temppos)

{int i,j;

25

i=temppos,j=0;

while (ilength && jlength)

{

if(j==-1||t->str[i]==p->str[j])

{i++; j++;}

else j=next[j];

}

if (j==p->length) return (i-p->length);

else return(-1);

}

//替换函数

void

takeplace(seqstring*S,seqstring*T1,seqstring*T2)

{

int next[maxsize],temppos=0,pos,i;

int lent1,lent2;

lent1=strlen(T1->str); //求T1串长度

lent2=strlen(T2->str); //求T2串长度

getnext(T1,next);//求T1串的next[]向量

do

{

pos=kmp(S,T1,next,temppos); //快速模式匹配

temppos=pos+T1->length;

if (pos!=-1) //匹配成功

{

if (lent1>lent2) //T1串长度大于T2串长度

{

for (i=temppos;ilength;i++) //前移

S->str[i-lent1+lent2]=S->str[i];

for(i=0;ilength;i++) //替换

S->str[pos+i]=T2->str[i];

S->length-=lent1-lent2; //修改长度

}

else

if (lent2>lent1) //T2串长度大于T1串长度

{

for (i=S->length-1;i>=temppos;i--) //后移留空

S->str[i+lent2-lent1]=S->str[i];

for(i=0;ilength;i++) //替换

26

S->str[pos+i]=T2->str[i];

S->length+=lent2-lent1; //修改长度

}

else //T1长度与T2长度相等

{ for(i=0;ilength;i++)

S->str[pos+i]=T2->str[i];

}

temppos=pos+T2->length; //修改下一次模式匹配的起点位置

}

}while(pos!=-1);

S->str[S->length]='0';

}

int main()

{ seqstring*S,*T1,*T2;

printf("nn本程序用来实现字符串替换，将S中用T2替换T1所有出现nThis program

is used for characters batch takeing place,The T1 characters batch will take place all the

T2's

appearances in characters batch S: nn");

printf("请输入S中的字符(plese input characters batch S:)n");

S=(seqstring*)malloc(sizeof(seqstring));

T1=(seqstring*)malloc(sizeof(seqstring));

T2=(seqstring*)malloc(sizeof(seqstring));

scanf("%s",S->str);

S->length=strlen(S->str);

printf("输入要被替换的串(input T1):n");

scanf("%s",T1->str);

T1->length=strlen(T1->str);

printf("输入替换串(input T2):n");

scanf("%s",T2->str);

T2->length=strlen(T2->str);

takeplace(S,T1,T2);

printf("替换后的字符串为：n");

printf("%sn",S->str);

free(S);

free(T1);

free(T2);

}

【参考程序2】：

#include

27

#define MAXSIZE 100

typedef struct{

char str[MAXSIZE];

int length;

}seqstring;

void getnext(seqstring p,int next[]) //求模式的next函数

{int i,j;

next[0]=-1;

i=0;

j=-1;

while(i<)

{if(j==-1||[i]==[j])

{++i;++j;next[i]=j;}

else j=next[j];

}

}

void replace(seqstring *s,seqstring t1,seqstring t2,int

next[])

{int i,j,k,c,m;

i=0;j=0;k=0;

while(ilength)

{ j=0;

while(ilength&&j<)

{if(j==-1||s->str[i]==[j])

{i++; j++;}

else j=next[j];

}

if(j==) //匹配成功

{ c=;

if(==) //两串长度相等直接替换

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

s->str[c+k]=[k];

else if(<)

{ for(m=s->length-1;m>i-1;m--)

s->str[+m]=s->str[m]; // for(k=0;k<;k++)

s->str[c+k]=[k];

s->length=s->+;

s->str[s->length]='0';

}

28

后移留空

else

{ for(m=i-1;mlength;m++) //前移

s->str[+]=s->str[m];

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

s->str[c+k]=[k];

s->length=s->+;

s->str[s->length]='0';

}

i=i+;

}

i++;

}

}

int main()

{ int next[MAXSIZE];

seqstring s,t1,t2;

printf("Input string s:"); //输入主串

gets();

printf("nInput string t1:"); //输入模式串

gets();

printf("nInput string t2:"); //输入拟替换的串

gets();

=strlen();

=strlen();

=strlen();

getnext(t1,next);

replace(&s,t1,t2,next);

puts();

}

4.10 试编写一个函数，实现在链式存储方式下字符串的strcompare（S1，【参考程序】：

/*建立字符串链式存储结构文件linkstring.h*/

#include

#include

typedef struct node

{

char data;

struct node *next;

} linkstrnode;

29

S2）运算。

typedef linkstrnode *linkstring;

/*---------------------------------------*/

/* 尾插法建立单链表 */

/*---------------------------------------*/

void strcreate(linkstring *S)

{ char ch;

linkstrnode *p,*r;

*S=NULL; r=NULL;

while ((ch=getchar())!='n')

{ p=(linkstrnode

*)malloc(sizeof(linkstrnode));

p->data=ch; /*产生新结点*/

if (*S==NULL) /*新结点插入空表*/

{ *S=p; r=p;}

else {r->next=p;

r=p;}

}

if (r!=NULL) r->next=NULL; /*处理表尾结点指针域*/

}

/*---------------------------------------------*/

/* 输出单链表的内容 */

/*---------------------------------------------*/

void print(linkstring head)

{

linkstrnode *p;

p=head;

while (p)

{printf("%c-->",p->data);

p=p->next;

}

printf("n");

}

#include “linkstring.h”

int strcompare(linkstrnode*S1,linkstrnode*S2)

{

while(S1&&S2)

{ if(S1->data>S2->data)

return 1;

else if(S1->datadata)

30

return -1;

S1=S1->next;

S2=S2->next;

}

if(S1) return 1;

else if(S2) return -1;

return 0;

}

int main()

{ linkstring s1,s2;

int k;

printf("nPlease input s1:");

strcreate(&s1); /*建立字符串s1*/

print(s1);

printf("nPlease input s2:");

strcreate(&s2); /*建立字符串s2*/

print(s2);

k=strcompare(s1,s2);

if (k==1) printf("s1>s2");

else

if (k==-1)printf("s1

else

printf("s1==s2");

}

4.11 试编写一个函数，实现在链式存储方式下字符串的replace（S，T1，T2）运算。

/*题目：链式存储方式下字符串的replace(S,T1,T2）运算*/

【参考程序】：

#include "linkstring.h"

/*单链表拷贝函数*/

linkstring copy(linkstring head)

{ linkstring L=NULL,r=NULL,s,p;

p=head;

while(p)

{s=(linkstring)malloc(sizeof(linkstrnode));

s->data=p->data;

if (L==NULL) L=r=s;

else

{r->next=s;

31

r=s;

}

p=p->next;

}

if (r!=NULL) r->next=NULL;

return L;

}

/*------------------------------------------------*/

/* 在字符串S中用T2替换T1 */

/*------------------------------------------------*/

linkstring replace(linkstring S,linkstring

T1,linkstring T2)

{linkstring p,q,r,s,pre,temp,pos;

int flag=1;

if (S==NULL|| T1==NULL ) return S; /*若S为空或T1为空,则原串不变*/

pre=NULL;

pos=S; /*pos表示可能的T1串在S中的起始位置*/

while (pos && flag) /*flag表示S中存在T1*/

{ p=pos;

q=T1;

while ( p&&q ) /*从pos开始找子串T1*/

{ if (p->data==q->data)

{ p=p->next;q=q->next;}

else

{pre=pos;

pos=pos->next;

p=pos;

q=T1;

}

}

if (q!=NULL) flag=0; /*未找到子串T1*/

else

{ flag=1; /*找到了子串T1,用T2代替T1*/

r=pos;

while (r!=p) /*首先删除子串T1,最后p指向删除串T1的下一个结点*/

{s=r;

r=r->next;

free(s);

}

if (T2!=NULL) /*T2不为空*/

32

{ temp=r=copy(T2); /*复制一个T2串*/

while (r->next!=NULL) /*找temp串的尾结点*/

r=r->next;

r->next=p;

if (pre==NULL) /*如果T1出现在S的链头*/

S=temp; /*新串成为链首*/

else /*T1不是链首串*/

pre->next=temp;

pre=r;

pos=p; /*从p开始继续找子串T1*/

}

else /*原T2子串为空*/

{ if (pre==NULL) /*T1为链首串*/

S=p;

else

pre->next=p;

pos=p;

}

}

}

return S;

}

int main()

{linkstring S,T1,T2;

printf("nPlease input S:");

strcreate(&S); /*建立字符串S*/

print(S);

printf("nPlease input T1:");

strcreate(&T1); /*建立字符串T1*/

print(T1);

printf("nPlease input T2:");

strcreate(&T2); /*建立字符串T2*/

print(T2);

S=replace(S,T1,T2);

printf("nThe result is:n");

print(S);

}

4.12 已知如下字符串，求它们的next数组值：

（1）“bbdcfbbdac”

33

【答】：-1010001230

（2）“aaaaaaa”

【答】：-1012345

（3）“babbabab”

【答】：-10011232

4.13 已知正文t =“ababbaabaa”，模式p =“aab”，试使用KMP快速模式匹配算法寻找p

在t中首次出现的起始位置，给出具体的匹配过程分析。

【答】：模式p的next向量如下表所示：

0 1 2

a a b

-1 0 1

第一趟匹配：

0 1 2 3 4 5 6 7 8 9

a b a b b a a b a a

a a

i=1，j=1，匹配失败，此时j取next[1]=0，即下一趟匹配从i=1，j=0开始；

第二趟匹配：

0 1 2 3 4 5 6 7 8 9

a b a b b a a b a a

a

i=1，j=0，匹配失败，此时j=next[0]=-1，下一趟匹配从i=2，j=0开始；

第三趟匹配：

0 1 2 3 4 5 6 7 8 9

a b a b b a a b a a

a a

i=3，j=1，匹配失败，此时j=next[1]=0，下一趟匹配从i=3，j=0开始；

第四趟匹配：

0 1 2 3 4 5 6 7 8 9

a b a b b a a b a a

a

i=3，j=0，匹配失败，此时j=next[0]=-1，下一趟匹配从i=4，j=0开始；

第五趟匹配：

0 1 2 3 4 5 6 7 8 9

a b a b b a a b a a

a

i=4，j=0，匹配失败，此时j=next[0]=-1，下一趟匹配从i=5，j=0开始；

第五趟匹配：

0 1 2 3 4 5 6 7 8 9

34

a b a b b a a b a a

a a b

i=8，j=3，匹配完成，表明匹配成功的位置是：i-j=5。

4.14 已知三维数组A[3][2][4]，数组首地址为100，每个元素占用1个存储单元，分别计

算数组元素A[0][1][2]在按行优先和按列优先存储方式下的地址。

【答】：

A[0][1][2]按行优先方式在内存的存储地址为：100+0*8+1*4+2=106

A[0][1][2]按列优先方式在内存的储储地址为：100+2*6+1*3+0*8=115

4.15 已知两个稀疏矩阵A和B，其行数和列数均对应相等，编写一个函数，计算A和B

之和，假设稀疏矩阵采用三元组表示。

【参考程序1】：

#include

typedef struct {

int data[100][100];

int m,n; /*分别存放稀疏矩阵的行数、列数和非零元素的个数*/

} matrix;

typedef int spmatrix[100][3]; //三元组存储结构

spmatrix c;

void add(spmatrix a,spmatrix b,spmatrix c) //基于三元组结构的矩阵相加算法

{int i,j,k,t,r;

i=j=k=1;

while(i<=a[0][2]&&j<=b[0][2])

{if(a[i][0]

]))

c[k][1]=a[i][1];

c[k][2]=a[i][2];

i++;k++;

}

else

if(a[i][0]>b[j][0]||(a[i][0]==b[j][0]&&a[i][1]>b[j][1 { c[k][0]=b[j][0];

]))

c[k][1]=b[j][1];

c[k][2]=b[j][2];

j++;k++;

}

else

if(a[i][0]==b[j][0]&&(a[i][1]==b[j][1]) )

{ c[k][0]=a[i][0];

35

c[k][1]=a[i][1];

c[k][2]=a[i][2]+b[j][2];

i++;j++;

if (c[k][2]!=0 ) k++; /*如果相加的和不为0,则生成一个有效项*/

}

}

while(j<=b[0][2])

{ c[k][0]=b[j][0];

c[k][1]=b[j][1];

c[k][2]=b[j][2];

j++;k++;

}

while(i<=a[0][2])

{

c[k][0]=a[i][0];

c[k][1]=a[i][1];

c[k][2]=a[i][2];

i++;k++;

}

c[0][0]=a[0][0];

c[0][1]=a[0][1];

c[0][2]=k-1;

}

//函数compressmatrix将普通矩阵存储转换为三元组存储结构

void compressmatrix(matrix *A , spmatrix B)

{ int i, j, k;

k=1;

for ( i=0; im; i++)

for (j=0;jn; j++)

if (A->data[i][j] !=0)

{ B[k][0]=i;

B[k][1]=j;

B[k][2]=A->data[i][j];

k++;

}

B[0][0]=A->m;

B[0][1]=A->n;

B[0][2]=k-1;

36

i=0;

printf("the spmatrix is:n");

while(i<=B[0][2])

{ printf("%d%5d%5dn",B[i][0],B[i][1],B[i][2]);

i++;

}

}

void creat(int r,int w,matrix *s)

{ int i,j,data;

printf("input numbers:n");

for(i=0;i

for(j=0;j

{

scanf("%d",&data);

s->data[i][j]=data;

}

printf("the array is:n");

for(i=0;i

{ for(j=0;j

printf("%5d",s->data[i][j]);

printf("n");

}

s->m=r;

s->n=w;

}

int main()

{matrix p,q;

spmatrix a,b,c;

int r,w,i;

i=0;

printf("input r,w:"); /*输入行和列*/

scanf("%d%d",&r,&w);

creat(r,w,&p);

creat(r,w,&q);

compressmatrix(&p,a);

compressmatrix(&q,b);

i=0;

add(a,b,c);

printf("the spmatrix c is:n");

37

while(i<=c[0][2])

{ printf("%d%5d%5dn",c[i][0],c[i][1],c[i][2]);

i++;

}

}

程序运行时先输入矩阵的行和列，然后按普通矩阵格式输入矩阵值，一组程序测试用例运

行结果如下图：

【参考程序2】：

38

#include

#include

#define MAX 100

typedef struct{

int data[MAX][3];

int m,n,value;

}matrix;

matrix *Input(matrix *A)

{ int i,j;

A = (matrix*)malloc(sizeof(matrix));

scanf("%d%d%d",&A->m,&A->n,&A->value);

A->data[0][0] = A->m;

A->data[0][1] = A->n;

A->data[0][2] = A->value;

for(i = 1;i <= A->value;i ++)

{

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

scanf("%d",&A->data[i][j]);

}

return A;

}

void Output(matrix *A)

{ int i,j;

printf("************************************n");

for(i = 0;i <= A->value;i ++)

{

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

printf("%d ",A->data[i][j]);

printf("n");

}

printf("************************************n");

}

matrix *addmatrix(matrix *A,matrix *B,matrix *C)

{ int i = 1,j =1,k = 1;

C = (matrix*)malloc(sizeof(matrix));

while(i <= A->value && j <= B->value)

{

if(A->data[i][0] == B->data[j][0])

{

39

if(A->data[i][1] == B->data[j][1])

{

C->data[k][0] = A->data[i][0];

C->data[k][1] = A->data[i][1];

C->data[k][2] = A->data[i][2] + B->data[j][2];

if(C->data[k][2] != 0) k ++;

i ++;

j ++;

}

else if(A->data[i][1] < B->data[j][1])

{

C->data[k][0] = A->data[i][0];

C->data[k][1] = A->data[i][1];

C->data[k][2] = A->data[i][2];

k ++;

i ++;

}

else

{

C->data[k][0] = B->data[j][0];

C->data[k][1] = B->data[j][1];

C->data[k][2] = B->data[j][2];

k ++;

j ++;

}

}

else if(A->data[i][0] < B->data[j][0])

{

C->data[k][0] = A->data[i][0];

C->data[k][1] = A->data[i][1];

C->data[k][2] = A->data[i][2];

k ++;

i ++;

}

else

{

C->data[k][0] = B->data[j][0];

C->data[k][1] = B->data[j][1];

C->data[k][2] = B->data[j][2];

40

k ++;

j ++;

}

}

while(i <= A->value)

{

C->data[k][0] = A->data[i][0];

C->data[k][1] = A->data[i][1];

C->data[k][2] = A->data[i][2];

k ++;

i ++;

}

while(j <= B->value)

{

C->data[k][0] = B->data[j][0];

C->data[k][1] = B->data[j][1];

C->data[k][2] = B->data[j][2];

k ++;

j ++;

}

C->data[0][0] =

(A->data[0][0]>=B->data[0][0])?A->data[0][0]:B->data[0][0];

C->data[0][1] =

(A->data[0][1]>=B->data[0][1])?A->data[0][1]:B->data[0][1];

C->data[0][2] = k-1;

C->value = k-1;

return C;

}

int main()

{

matrix * A = NULL,*B = NULL,*C = NULL;

printf("提示：请按三元组格式输入矩阵内容。n");

printf("Input A matrix:n");

A = Input(A);

printf("Input B matrix:n");

B = Input(B);

C = addmatrix(A,B,C);

Output(C);

free(A);

free(B);

41

free(C);

return 0;

}

程序运行时按照三元组的格式输入矩阵信息，程序运行结果如下图所示：

4.16 写出两个稀疏矩阵相乘的算法，计算：

Cpn =ApmBmn

其中，A、B和C都采用三元组表示法存储。

【答】：

#include

#include

#define MAX 100

typedef struct{

int data[MAX][3];

int m,n,value;

}matrix;

matrix *Input(matrix *A)

{ int i,j;

A = (matrix*)malloc(sizeof(matrix));

scanf("%d%d%d",&A->m,&A->n,&A->value);

A->data[0][0] = A->m;

42

A->data[0][1] = A->n;

A->data[0][2] = A->value;

for(i = 1;i <= A->value;i ++)

{

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

scanf("%d",&A->data[i][j]);

}

return A;

}

void Output(matrix *A)

{

int i,j;

printf("*******************************n");

for(i = 0;i <= A->value;i ++)

{

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

printf("%d ",A->data[i][j]);

printf("n");

}

printf("*******************************n");

}

/* 基于三元组存储结构的矩阵相乘算法 */

matrix *MulMatrix(matrix *A,matrix *B,matrix *C)

{ int i ,j ,k ,r=1,p,q,s;

C = (matrix*)malloc(sizeof(matrix));

C->m=A->m;

C->n=B->n;

C->data[0][0]=C->m;

C->data[0][1]=C->n;

for (i=0;im;i++)

for (j=0;jn;j++)

{ s=0;

for (k=0;kn;k++)

//找A[i][k];

{

p=1;

while (p<=A->value)

if (A->data[p][0]==i&&A->data[p][1]==k)

break;

43

else p++;

//找B[k][j];

q=1;

while (q<=B->value)

if (B->data[q][0]==k&&B->data[q][1]==j)

break;

else q++;

if (p<=A->value && q<=B->value)

s=s+A->data[p][2]*B->data[q][2];

}

if (s!=0)

{ C->data[r][0]=i;

C->data[r][1]=j;

C->data[r][2]=s;

r++;

}

}

C->data[0][2]=r-1;

C->value=r-1;

return C;

}

int main()

{ matrix * A = NULL,*B = NULL,*C = NULL;

printf("提示：请按三元组格式输入矩阵内容。n");

printf("Input A matrix:n");

A = Input(A);

printf("Input B matrix:n");

B = Input(B);

C = MulMatrix(A,B,C);

Output(C);

free(A);

free(B);

free(C);

return 0;

}

程序运行时，要求按照三元组的格式输入矩阵信息。

44

45

第5章 递归

5.1 试述递归程序设计的特点。

【答】：

（1）具备递归出口。递归出口定义了递归的终止条件，当程序的执行使它得到满足时，

递归执行过程便终止。有些问题的递归程序可能存在几个递归出口。

（2）在不满足递归出口的情况下，根据所求解问题的性质，将原问题分解成若干子问题，

子问题的求解通过以一定的方式修改参数进行函数自身调用加以实现，然后将子问题的解组合

成原问题的解。递归调用时，参数的修改最终必须保证递归出口得以满足。

5.2 试简述简单递归程序向非递归程序转换的方法。

【答】：简单递归程序转换为非递归程序可以采用算法设计中的递推技术。递归方法与递

推方法共同采用的分划技术，为使用递推技术解决递归问题奠定了基础。由于简单递归问题求

解过程中无需回溯，因而要转换成非递归方式实现完全可以使用递推技术。为了使用自底向上

的递推方式来解决递归问题，利用子问题已有的解构造规模较大子问题的解，进而构造原问题

的解，必须建立原问题与子问题解之间的递推关系，然后定义若干变量用于记录求解过程中递

推关系的每个子问题的解；程序的执行便是根据递推关系，不断修改这些变量的值，使之成为

更大子问题的解的过程；当得到原问题解时，递推过程便可结束了。

5.3 试简述复杂递归程序向非递归程序转换的方法，并说明栈在复杂递归程序转换成非

递归程序的过程中所起的作用。

【答】：复杂递归问题在求解的过程中无法保证求解动作一直向前，需要设置一些回溯点，

当求解无法进行下去或当前处理的工作已经完成时，必须退回到所设置的回溯点，继续问题的

求解。因此，在使用非递归方式实现一个复杂递归问题的算法时，经常使用栈来记录和管理所

设置的回溯点。

5.4 试给出例题5.1中Fact(5)的执行过程分析。

【答】：Fact(5)的执行过程如下图所示：

Fact(5)

1

=5*Fact(4)

2

=4*Fact(3)

3

=3*Fact(2)

45

=2*Fact(1)

6

7

8

5.5 已知多项式pn(x) = a0 + a1x + a2x2 + … + anxn的系数按顺序存储在数组a中，试：

（1）编写一个递归函数，求n阶多项式的值；

46

（2）编写一个非递归函数，求n阶多项式的值。

【答】：

#include

#include

#include

double pnx1(double a[],int n,double x) //（1）递归函数

{ if (n==0) return a[0];

else

return pnx1(a,n-1,x)+a[n]*pow(x,n);

}

double pnx2(double a[],int n,double x) //（2）非递归迭代函数

{

double t;

int i;

t=a[n];

for (i=n-1;i>=0;i--)

t=a[i]+t*x;

return t;

}

int main()

{ double *a,x,p;

int n,i;

printf("请输入n,x:n");

scanf("%d%lf",&n,&x);

a=(double*)malloc((n+1)*sizeof(double));

printf("请输入%d项系数：n",n+1);

for (i=0;i<=n;i++)

scanf("%lf",&a[i]);

p=pnx1(a,n,x);

printf("%fn",p);

p=pnx2(a,n,x);

printf(“%fn”,p);

free(a);

}

5.6 已知两个一维整型数组a和b，分别采用递归和非递归方式编写函数，求两个数组的内积（数组的内积等于两个数组对应元素相乘后再相加所得到的结果）。

【答】：

#include

using namespace std;

47

long sum1(int a[],int b[],int n) //非递归函数

{ long s=0;

int i;

for (i=0;i

s+=a[i]*b[i];

return s;

}

long sum2(int a[],int b[],int n) //递归函数

{

if (n==1)

return a[0]*b[0];

else

return sum2(a,b,n-1)+a[n-1]*b[n-1];

}

int main()

{

int i,n,*a,*b;

long s;

cout<<"输入数组的长度:"<

cin>>n;

a=new int [n];

b=new int [n];

cout<<"请输入数组a的值"<

for (i=0;i<5;i++)

cin>>a[i];

cout<<"请输入数组b的值"<

for (i=0;i<5;i++)

cin>>b[i];

s=sum1(a,b,5);

cout<<"非递归计算的和="<

s=sum2(a,b,5);

cout<<"递归计算的和="<

delete []a;

delete []b;

return 0;

}

5.7 写出求Ackerman函数Ack(m，n)值的递归函数，Ackerman函数在m ≥ 0和n ≥ 0时的

定义为：

Ack(0，n)=n+1;

48

Ack(m，0)=Ack(m−1，1);

Ack(m，n)=Ack(m−1，Ack(m，n−1)) n>0且m>0

【答】：

// 输入 m,和 n的值，计算Ack (m,n)

#include

int Ack (int m,int n)

{ if (m == 0)

{ return n + 1;

}

else if (n == 0)

{ return Ack (m - 1,1);

}

else

{ return Ack (m - 1,Ack (m,n - 1));

}

}

int main ()

{ int m,n;

printf ("Please input m nn");

scanf ("%d%d",&m,&n);

printf ("Ack (m,n) = %dn",Ack (m,n));

return 0;

}

5.8 已知多项式Fn(x)的定义如下：

10

Fxxn()21

n

n

试写出计算Fn(x)值的递归函数。

【答】：

// 输入 n，x 计算F(x)

#include

// 为了符合递归函数的表达这里将x作为参数传递，在实际运用中建议使用全局变量。

// C++中也可以传递引用 int Function (int n,const int &x)

int Function (int n,int x)

{ if (n == 0)

{ return 1;

}

else if (n == 1)

49

2()2(1)()1xFxnFxn

nn

12

>