数据结构(第二版)习题答案
数据结构
（C语言版）
（第 2版）
习题解析
揭安全 李云清 杨庆红
江西师范大学计算机信息工程学院
联系方式：janquan@https://www.wendangku.net/doc/3f8151357.html,（习题答案仅供参考）
第
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)。
上述定义表明，函数
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.9算法的空间复杂度指的是什么？如何表示？
【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表
示为问题规模的函数，并通过大写O符号表示空间复杂度。
1.10对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度
T(n)。
（1） i++;
（2） for(i=0;i
（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
【答】：（1）O（1）；（2）O（n）；（3）O（n2）；（4）O（n）；（5）O（n2）
第
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什么是顺序表？什么是栈？什么是队列？
【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表
现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶），
因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约
定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具
有先进先出，后进后出的特点。
2.3设计一个算法，求顺序表中值为
x的结点的个数。
【答】：顺序表的存储结构定义如下（文件名
seqlist.h）：
#include
#define N 100 /*预定义最大的数据域空间
*/
typedef int datatype; /*假设数据类型为整型
*/
typedef struct {
datatype data[N]; /*此处假设数据元素只包含一个整型的关键字域
*/
int length; /*线性表长度*/
} seqlist; /*预定义的顺序表类型
*/
算法
countx（L,x）用于求顺序表
L中值为
x的结点的个数。
int countx(seqlist *L,datatype x)
{ int c=0;
int i;
for (i=0;i
if
(L->data[i]==x) c++;
return c;
}
2.4设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组
a中，倒
置的结果是使得数组
a中的
a[0]等于原来的最后一个元素，
a[1] 等于原来的倒数第
2个元
素，…，a的最后一个元素等于原来的第一个元素。
【答】：顺序表的存储结构定义同题
2.3，实现顺序表倒置的算法程序如下：
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的结点，
使顺序表中的结点仍然是从小到大有序。
【答】：顺序表的定义同题
2.3，实现本题要求的算法程序如下：
void insertx(seqlist *L,datatype x)
{int j;
if (L->length
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，2，3，4
全排列中的一个元素。由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：对于
序列中的任何一个数其后面所有比它小的数应该是倒序的，例如
4321是一个有效的出栈序列，
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_1.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
else {if (str[j]>b[0]) {flag=0;}
else b[0]=str[j];
}
}
}
if(flag) /*满足出栈规则则输出
str[]中的序列*/
{ printf(" %2d:",cont++);
for(i=0;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_7_8.c）
对一组数穷尽所有排列，还可一种更直接的方法，将一个排列看作一个长整数，则所有排
列对应着一组整数，将这组整数按从小到大的顺序排成一个数列，从对应最小的整数开始，按
数列的递增顺序逐一列举每个排列对应的每一个整数，这能更有效地完成排列的穷举。从一个
排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为
1,2,4,6,5,3，并令其对应的长整数为
124653。要寻找比长整数
124653更大的排列，可从该排列
的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大时，如本例中
的
6比它的前一位数字
4大，则说明还有可能对应更大整数的排列。但为顺序从小到大列举出
所有的排列，不能立即调整得太大，如本例中将数字
6与数字
4交换得到的排列为
126453就
不是排列
124653的下一个排列。为得到排列
124653的下一个排列，应从已考察过的那部分数
字中选出比数字
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("stack.txt", "w") ; /*pl.txt用于存放进出栈序列结果
*/
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]
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]
*/
else
{j=i-1;i=n;/*若找到,则在该位置的后面从右向左找第一个比该元素大的值*/
while (i>j && a[i]
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
}
}
}
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
(
+
21n
)
)!
n!n!
第
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(nlog2
n)
（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
#include
typedef struct node
{ int data;
struct node *next;
}linknode;
typedef linknode *linklist;
/*尾插法创建带头结点的单链表
*/
linklist creatlinklist()
{ linklist head,r,x,s;
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)
{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;
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)
{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)
{/*本函数的功能是就地倒置带头结点的单链表
*/
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() /*测试函数*/
{lin
klist 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;
}
}
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;
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;
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;
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);
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);
}
第
4章字符串、数组和特殊矩阵
4.1稀疏矩阵常用的压缩存储方法有（ 三元组顺序存储 ）和（十字链表 ）两种。
4.2设有一个 10 × 10的对称矩阵 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 i,m=0,len;
len=s1.length
if(s1.str[i]>s2.str[i])
{m=1;break;}
else if(s1.str[i]
return m;
}
int main()
{ seqstring s1,s2;
int i,m;
printf("input char to s1:\n");
gets(s1.str);
s1.length=strlen(s1.str);
printf("input char to s2:\n");
gets(s2.str);
s2.length=strlen(s2.str);
m=strcompare(s1,s2);
if(m==1) printf("s1>s2\n");
else if(m==-1) printf("s2>s1\n");
else if(m==0) printf("s1=s2\n");
}
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(i
{
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;
i=temppos,j=0;
while (i
{
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;i
S->str[i-lent1+lent2]=S->str[i];
for(i=0;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;i
S->str[pos+i]=T2->str[i];
S->length+=lent2-lent1; //修改长度
}
else //T1长度与
T2长度相等
{ for(i=0;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("\n\n本程序用来实现字符串替换，将
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: \n\n");
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("%s\n",S->str);
free(S);
free(T1);
free(T2);
}
【参考程序
2】：
#include
#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||p.str[i]==p.str[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(i
{ j=0;
while(i
{i++; j++;}
else j=next[j];
}
if(j==t1.length) //匹配成功
{ c=i-t1.length;
if(t1.length==t2.length) //两串长度相等直接替换
for(k=0;k
else if(t1.length
)
{ for(m=s->length-1;m>i-1;m--)
s->str[t2.length-t1.length+m]=s->str[m]; //后移留空
for(k=0;k
s->str[c+k]=t2.str[k];
s->length=s->length-t1.length+t2.length;
s->str[s->length]='\0';
}
else
{ for(m=i-1;m
s->str[m-t1.length+t2.length]=s->str[m];
for(k=0;k
s->str[c+k]=t2.str[k];
s->length=s->length-t1.length+t2.length;
s->str[s->length]='\0';
}
i=i+t2.length-t1.length;
}
i++;
}
}
int main()
{ int next[MAXSIZE];
seqstring s,t1,t2;
printf("Input string s:"); //输入主串
gets(s.str);
printf("\nInput string t1:"); //输入模式串
gets(t1.str);
printf("\nInput string t2:"); //输入拟替换的串
gets(t2.str);
s.length=strlen(s.str);
t1.length=strlen(t1.str);
t2.length=strlen(t2.str);
getnext(t1,next);
replace(&s,t1,t2,next);
puts(s.str);
}
4.10试编写一个函数，实现在链式存储方式下字符串的
strcompare（S1，S2）运算。
【参考程序】：
/*建立字符串链式存储结构文件
linkstring.h*/
#include
#include
typedef struct node
{
char data;
struct node *next;
} linkstrnode;
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->data
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
printf("s1==s2");
}
4.11试编写一个函数，实现在链式存储方式下字符串的
replace（S，T1，T2）运算。
/*题目：链式存储方式下字符串的
replace(S,T1,T2）运算*/
【参考程序】：
#include "linkstring.h"
/*单链表拷贝函数
*/
linkstring copy(linkstring head)
{ links
tring 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;
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不为空*/
{ 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”
【答】：-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
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][0]=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];
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; i
for (j=0;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;
i=0;
printf("the spmatrix is:\n");
while(i<=B[0][2])
{ printf("%d%5d%5d\n",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
;j++)
{
scanf("%d",&data);
s->data[i][j]=data;
}
printf("the array is:\n");
for(i=0;i
{ for(j=0;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");
while(i<=c[0][2])
{ printf("%d%5d%5d\n",c[i][0],c[i][1],c[i][2]);
i++;
}
}
程序运行时先输入矩阵的行和列，然后按普通矩阵格式输入矩阵值，一组程序测试用例运
行结果如下图：
【参考程序
2】：
#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])
{
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];
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);
free(C);
return 0;
}
程序运行时按照三元组的格式输入矩阵信息，程序运行结果如下图所示：
4.16写出两个稀疏矩阵相乘的算法，计算：
Cpn = Apm .Bmn
其中，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;
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;i
for (j=0;j
{
s=0;
for (k=0;k
//找
A[i][k];
{
p=1;
while (p<=A->value)
if (A->data[p][0]==i&&A->data[p][1]==k)
break;
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;
}
程序运行时，要求按照三元组的格式输入矩阵信息。
第
5章递归
5.1试述递归程序设计的特点。
【答】：
（1）具备递归出口。递归出口定义了递归的终止条件，当程序的执行使它得到满足时，
递归执行过程便终止。有些问题的递归程序可能存在几个递归出口。
（2）在不满足递归出口的情况下，根据所求解问题的性质，将原问题分解成若干子问题，
子问题的求解通
过以一定的方式修改参数进行函数自身调用加以实现，然后将子问题的解组合
成原问题的解。递归调用时，参数的修改最终必须保证递归出口得以满足。
5.2试简述简单递归程序向非递归程序转换的方法。
【答】：简单递归程序转换为非递归程序可以采用算法设计中的递推技术。递归方法与递
推方法共同采用的分划技术，为使用递推技术解决递归问题奠定了基础。由于简单递归问题求
解过程中无需回溯，因而要转换成非递归方式实现完全可以使用递推技术。为了使用自底向上
的递推方式来解决递归问题，利用子问题已有的解构造规模较大子问题的解，进而构造原问题
的解，必须建立原问题与子问题解之间的递推关系，然后定义若干变量用于记录求解过程中递
推关系的每个子问题的解；程序的执行便是根据递推关系，不断修改这些变量的值，使之成为
更大子问题的解的过程；当得到原问题解时，递推过程便可结束了。
5.3 试简述复杂递归程序向非递归程序转换的方法，并说明栈在复杂递归程序转换成非
递归程序的过程中所起的作用。
【答】：复杂递归问题在求解的过程中无法保证求解动作一直向前，需要设置一些回溯点，
当求解无法进行下去或当前处理的工作已经完成时，必须退回到所设置的回溯点，继续问题的
求解。因此，在使用非递归方式实现一个复杂递归问题的算法时，经常使用栈来记录和管理所
设置的回溯点。
5.4试给出例题
5.1中
Fact(5)的执行过程分析。
【答】：Fact(5)的执行过程如下图所示：
2 + … + anxn
5.5已知多项式
pn(x) = a0 + a1x + a2x的系数按顺序存储在数组
a中，试：
（1）编写一个递归函数，求
n阶多项式的值；
（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("%f\n",p);
p=pnx2(a,n,x);
printf(“%f\n”,p);
free(a);
}
5.6已知两个一维整型数组
a和
b，分别采用递归和非递归方式编写函数，求两个数组的
内积（数组的内积等于两个数组对应元素相乘后再相加所得到的结果）。
【答】：
#include
using namespace std;
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<<"输入数组的长度
:"<
a=new int [n];
b=new int [n];
cout<<"请输入数组
a的值"<
cin>>a[i];
cout<<"请输入数组
b的值"<
cin>>b[i];
s=sum1(a,b,5);
cout<<"非递归计算的和
="<
cout<<"递归计算的和
="<
delete []b;
return 0;
}
5.7写出求
Ackerman函数
Ack(m，n)值的递归函数，
Ackerman函数在
m ≥ 0和
n ≥ 0时的
定义为：
Ack(0，n)=n+1;
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 n\n");
scanf ("%d%d",&m,&n);
printf ("Ack (m,n) = %d\n",Ack (m,n));
return 0;
}
5.8
已知多项式
Fn(x)的定义如下：
.1 n =
0
.
Fx() =
2x
n =
1
n
.
.
.
2xFn.1( ) .
2( n .1) Fn.2 xn >1
x ()
试写出计算
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)
{ return 2 * x;
}
else
{ return 2 * x * Function (n - 1,x) - 2 * (n - 1) * Function (n - 2,x);
}
}
int main ()
{
int n,x;
printf ("input n,x:\n");
scanf ("%d%d",&n,&x);
printf ("F(x) = %d\n",Function (n,x));
return 0;
}
5.9 n阶
Hanoi塔问题：设有
3个分别命名为
X，Y和
Z的塔座，在塔座
X上从上到下放有
n个直径各不相同、编号依次为
1，2，3，…，n的圆盘（直径大的圆盘在下，直径小的圆盘在上），
现要求将
X塔座上的
n个圆盘移至塔座
Z上，并仍然按同样的顺序叠放，且圆盘移动时必须遵循以
下规则：
（1）每次只能移动一个圆盘；
（2）圆盘可以插在塔座
X，Y和
Z中任何一个塔座上；
（3）任何时候都不能将一个大的圆盘压在一个小的圆盘之上。
试编写一个递归程序实现该问题。
【答】：
#include
void Hanoi(int n,char x,char y,char z)
{
if (n==1)
printf("%c-->%c\n",x,z);
else
{
Hanoi(n-1,x,z,y);
printf("%c-->%c\n",x,z);
Hanoi(n-1,y,x,z);
}
}
int main()
{
int n;
printf("请输入盘子个数：
");
scanf("%d",&n);
Hanoi(n,'X','Y','Z');
return 0;
}
5.10八皇后问题：在一个
8×8格的国际象棋棋盘上放上
8个皇后，使其不能相互攻击，
即任何两个皇后不能处于棋盘的同一行、同一列和同一斜线上。试编写一个函数实现八皇后问
题。
【答】：
解法一：（程序
place.cpp）
解向量：(x1，x2，…，xn)
显约束：xi=1，2，…，n
隐约束：
1）不同列：xi≠xj
2）不处于同一正、反对角线：
|i-j|≠|xi-xj|
#include
#include
#define n 8
int x[n+1]={0}; //x[i]的含义表示第
i行放置在
x[i]列
int sum=0; //sum用于记录
n后问题的所有解
void print(); //输出
n后问题的解
int Place(int k) //检测第
k行的皇后放置是否符后规则
{ for (int j=1;j
return 0;
return 1;
}
void Backtrack(int t) //放置
n后问题的第
t行
{ if (t>n) { sum++;
print(); //输出一种解方案
getchar();
}
else
for (int i=1;i<=n;i++)
{ x[t]=i; //试探在第
t行放在第
i列
if (Place(t)) Backtrack(t+1);
}
}
void print() //输出
n后问题的解
{ int i;
printf("%d皇后问题的第
%d种解为:\n",n,sum);
for (i=1;i<=n;i++)
printf("%d:%d\n",i,x[i]);
}
int main()
{
Backtrack(1);
}
解法二：
程序思想：
用
3个数组分别存放
8列，15个左对角线和
15个右对角线的值
,同时用一个
8元素大小的
数组记录下放置的皇后的位置。
初始时将三个数组全部标记为
0。
一，从第一行开始，从左向右开始查找。当找到第一个能够放下棋子的点
x,y（其对应的
列，左对角，右对角全部为
0）后，将此棋子所对应的列，左对角，右对角全部设置为
1，然
后继续放置下一行——x + 1行（调用自身的子函数）。
二，当其子函数执行完毕后，将放在
x,y上的点拿起，然后将这点对应的列，左对角，右
对角元素全部置
0，然后继续在此行的
y后查找能放置的点。
三，如果当前要放置的棋子为第
9个棋子的时候，打印结果。
程序见
5_10.c（递归法）
5_10_byStack.c (用栈回溯法
)
/*****************************************************/
/*八皇后问题递归解法 */
/*****************************************************/
#include
int left[16],right[16],row[9],queen[9],count=0; /*分别用来存放左对角线和右对角线的使用
情况
,row数组记录行数的棋子摆放情况，未使用的话就赋予
0，使用的话就赋予
1*/
/*row 的数组用来存放列的使用情