耿国华 - 数据结构 - C语言的描述 - 课后大部分习题答案

第一章 三、计算下列程序段中X=X+1 的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; [提示]：

i=1 时： 1 = (1+1)×1/2 = (1+1 )/2 i=2 时： 1+2 = (1+2)×2/2 = (2+22)/2 i=3 时： 1+2+3 = (1+3)×3/2 = (3+32)/2 ?

i=n时： 1+2+3+??+n = (1+n)×n/2 = (n+n )/2

f(n) = [ (1+2+3+……+n) + (1 + 2 + 3 + …… + n ) ] / 2 =[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2 =n(n+1)(n+2)/6 =n /6+n /2+n/3

区分语句频度和算法复杂度： O(f(n)) = O(n )

四、试编写算法求一元多项式Pn(x)=a +a x+a x +a x +?a x 的值P (x )，并确定算法中的每 一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能 使用求幂函数。注意：本题中的输入a (i=0,1,?,n), x和n，输出为P (x ).通常算法的输入和输出可采用下列两种方式之一：

（1）通过参数表中的参数显式传递； （2 ）通过全局变量隐式传递。

试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 [提示]：float PolyValue(float a[ ], float x, int n) {??} 核心语句：

p=1; (x 的零次幂) s=0;

i 从0 到n 循环 s=s+a[i]*p; p=p*x; 或：

p=x; (x 的一次幂) s=a[0];

i 从 1 到n 循环 s=s+a[i]*p; p=p*x;

第二章

2.1 描述以下三个概念的区别：头指针，头结点，首元素结点。 2.2 填空：

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

（2 ） 在顺序表中，逻辑上相邻的元素，其物理位置 相邻。在单链表中，逻辑上

相邻的元素，其物理位置 相邻。

（3） 在带头结点的非空单链表中，头结点的存储位置由 指示，首元素结点的存储位置由 指示，除首元素结点外，其它任一元素结点的存储位置由 其直接前趋的next 域 指示。

2.3 已知L 是无表头结点的单链表，且P 结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是： （4 ）、（1） 。 b. 在P结点前插入S结点的语句序列是： （7）、（11）、（8）、（4 ）、（1）。 c. 在表首插入S结点的语句序列是： （5）、（12）。 d. 在表尾插入S结点的语句序列是： （11）、（9）、（1）、（6）。 供选择的语句有： （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;

2.4 已知线性表L 递增有序。试写一算法，将 X 插入到 L 的适当位置上，以保持线性表L的有序性。

[提示]：void insert(SeqList *L; ElemType x) < 方法 1 >

（1）找出应插入位置i，（2 ）移位，（3）?? < 方法2 > 参P. 229

2.5 写一算法，从顺序表中删除自第i 个元素开始的k 个元素。 [提示]：注意检查i 和k 的合法性。（集体搬迁，“新房”、“旧房”） < 方法 1 > 以待移动元素下标m（“旧房号”）为中心，计算应移入位置（“新房号”）： for ( m= i －1+k; m<= L－>last; m++) L －>elem[ m－k ] = L－>elem[ m ];

< 方法2 > 同时以待移动元素下标m 和应移入位置j 为中心： < 方法2 > 以应移入位置j 为中心，计算待移动元素下标：

2.6 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink 且小于maxk 的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink 和maxk 是给定的两个参变量，它们的值为任意的整数）。 [提示]：注意检查mink 和maxk 的合法性：mink < maxk不要一个一个的删除（多次修改next 域）。

（1）找到第一个应删结点的前驱pre pre=L; p=L －>next;

while (p!=NULL && p －>data <= mink) { pre=p; p=p －>next; }

（2 ）找到最后一个应删结点的后继s，边找边释放应删结点 s=p;

while (s!=NULL && s－>data < mink) { t =s; s=s －>next; free(t); } （3）pre －>next = s;

2.7 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a ..., a ）逆置为（a , a ,..., a ）。

（1） 以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum 个分量中。 （2 ） 以单链表作存储结构。 [方法 1]:在原头结点后重新头插一遍

[方法2]:可设三个同步移动的指针p, q, r，将q 的后继r 改为p

2.8 假设两个按元素值递增有序排列的线性表A 和B，均以单链表作为存储结构，请编写算法，将A 表和B 表归并成一个按元素值递减有序的排列的线性表 C，并要求利用原表（即A 表和B 表的）结点空间存放表 C. [提示]：参P.28 例2-1 < 方法 1 >

void merge(LinkList A; LinkList B; LinkList *C) { ……

pa=A －>next; pb=B－>next; *C=A; (*C)－>next=NULL; while ( pa!=NULL && pb!=NULL ) { if ( pa －>data <= pb－>data ) { smaller=pa; pa=pa－>next;

smaller－>next = (*C)－>next; /* 头插法 */ (*C) －>next = smaller; } else

{ smaller=pb; pb=pb－>next; smaller－>next = (*C)－>next; (*C) －>next = smaller; }

while ( pa!=NULL)

{ smaller=pa; pa=pa－>next; smaller －>next = (*C)－>next; (*C) －>next = smaller; }

while ( pb!=NULL)

{ smaller=pb; pb=pb－>next; smaller －>next = (*C)－>next; (*C) －>next = smaller; }

< 方法2 >

LinkList merge(LinkList A; LinkList B) { ……

LinkList C；

pa=A －>next; pb=B－>next; C=A; C－>next=NULL; ?? ??

return C;

2.9 假设有一个循环链表的长度大于 1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针 s 所指结点的前趋结点。 [提示]：设指针p 指向 s 结点的前趋的前趋，则p 与s 有何关系？

2.10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。

2.11 设线性表A=(a, a ,?,a )，B=(b, b ,?,b )，试写一个按下列规则合并A、B为线性表C的算法，使得：

C= (a , b ,?,a , b , b ?,b ) 当m≤n时； 或者 C= (a , b ,?,a , b , a ?,a ) 当m>n时。

线性表 A、B、C 均以单链表作为存储结构，且 C 表利用 A 表和 B 表中的结点空间构成。

注意：单链表的长度值m 和n 均未显式存储。

[提示]：void merge(LinkList A; LinkList B; LinkList *C) 或：LinkList merge(LinkList A; LinkList B)

2.12 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。 [提示]：注明用头指针还是尾指针。

2.13 建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的 data 域存放一个二进制位。并在此链表上实现对二进制数加 1 的运算 。 [提示]：可将低位放在前面。

2.14 设多项式P(x)采用课本中所述链接方法存储。写一算法，对给定的x 值，求P(x)的值。 [提示]：float PolyValue(Polylist p; float x) {??} 第三章

1. 按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：

⑴ 如进站的车厢序列为 123，则可能得到的出站车厢序列是什么？ 123、213、132、231、321 （312）

⑵如进站的车厢序列为 123456，能否得到435612 和 135426 的出站序列，并说明原因。（即 写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。 SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X6

2. 设队列中有A、B、C、D、E 这 5 个元素，其中队首元素为A 。如果对这个队列重复执行下列4 步操作：

（1） 输出队首元素；

（2 ） 把队首元素值插入到队尾； （3） 删除队首元素；

（4 ） 再次删除队首元素。

直到队列成为空队列为止，则是否可能得到输出序列：

（1） A、C、E、C、C （2） A、C、E （3） A、C、E、C、C、C （4 ） A、C、E、C [提示]：

A、B、C、D、E （输出队首元素A ）

A、B、C、D、E、A （把队首元素A 插入到队尾） B、C、D、E、A （删除队首元素A ） C、D、E、A （再次删除队首元素B） C、D、E、A （输出队首元素C）

C、D、E、A、C （把队首元素C 插入到队尾） D、E、A、C （删除队首元素C） E、A、C （再次删除队首元素D ）

3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？ 4. 按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程： A －B ＊Ｃ／Ｄ＋Ｅ↑Ｆ

5. 试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1&序列2’模式的字符序列。其中序列1 和序列2 中都不含字符’&’，且序列2 是序列 1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+ ３& ３－１’则不是。 [提示]：

（1） 边读边入栈，直到&

（2 ） 边读边出栈边比较，直到??

6. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。 [提示]： 例：

中缀表达式：a+b 后缀表达式: ab+

中缀表达式：a+b×c 后缀表达式: abc×+ 中缀表达式：a+b×c-d 后缀表达式: abc×+d- 中缀表达式：a+b×c-d/e 后缀表达式: abc×+de/- 中缀表达式：a+b×(c-d)-e/f 后缀表达式: abcd-×+ef/- ? 后缀表达式的计算过程：（简便） 顺序扫描表达式，

（1） 如果是操作数，直接入栈；

（2 ） 如果是操作符op，则连续退栈两次，得操作数X, Y，计算X op Y，并将结果入栈。

? 如何将中缀表达式转换为后缀表达式？ 顺序扫描中缀表达式，

（1）如果是操作数，直接输出；

（2 ）如果是操作符op ，则与栈顶操作符op 比较： 如果op > op ，则op 入栈； 如果op = op ，则脱括号； 如果op < op ，则输出op ；

7. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设

头指针），试编写相应的队列初始化、入队列和出队列的算法。 [提示]： 参P.56 P.70 先画图. typedef LinkList CLQueue; int InitQueue(CLQueue * Q)

int EnterQueue(CLQueue Q, QueueElementType x) int DeleteQueue(CLQueue Q, QueueElementType *x)

8. 要求循环队列不损失一个空间全部都能得到利用,设置一个标志域tag ,以tag 为0 或 1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 [提示]：

初始状态：front==0, rear==0, tag==0 队空条件：front==rear, tag==0 队满条件：front==rear, tag==1

其它状态：front !=rear, tag==0 （或1、2 ） 入队操作： ?

?（入队）

if (front==rear) tag=1；（或直接tag=1 ） 出队操作： ?

?（出队） tag=0；

[问题]：如何明确区分队空、队满、非空非满三种情况？

9. 简述以下算法的功能（其中栈和队列的元素类型均为int）： （1）void proc_1(Stack S) { int i, n, A[255]; n=0;

while(!EmptyStack(S))

{n++; Pop(&S, &A[n]);} for(i=1; i<=n; i++) Push(&S, A[i]); }

将栈 S 逆序。

（2 ）void proc_2(Stack S, int e) { Stack T; int d; InitStack(&T);

while(!EmptyStack(S)) { Pop(&S, &d);

if (d!=e) Push( &T, d); }

while(!EmptyStack(T)) { Pop(&T, &d); Push( &S, d); } }

删除栈 S 中所有等于e 的元素。 （3）void proc_3(Queue *Q) { Stack S; int d; InitStack(&S);

while(!EmptyQueue(*Q)) {

DeleteQueue(Q, &d); Push( &S, d); }

while(!EmptyStack(S)) { Pop(&S, &d); EnterQueue(Q，d) } }

将队列 Q 逆序。

第四章

1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’。给出下列操作的结果： StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s,’A’,4); StrReplace(s,’STUDENT’,q); StrCat(StrCat(sub1,t), StrCat(sub2,q)); [参考答案]

StrLength(s)=14; sub1= ’I AM A_’; sub2= ’_’; StrIndex(s,’A’,4)=6; StrReplace(s,’STUDENT’,q)= ’I AM A WORKER’;

StrCat(StrCat(sub1,t), StrCat(sub2,q))= ’I AM A GOOD WORKER’; 2. 编写算法，实现串的基本操作 StrReplace(S,T,V)。

3. 假设以块链结构表示串，块的大小为 1，且附设头结点。 试编写算法，实现串的下列基本操作：

StrAsign(S,chars) ； StrCopy(S,T) ； StrCompare(S,T) ； StrLength(S) ； StrCat(S,T) ；

SubString(Sub,S,pos,len)。 [说明]：用单链表实现。

4．叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。

5．已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将 S 转换为T.

6．S 和T 是用结点大小为 1 的单链表存储的两个串，设计一个算法将串S 中首次与T匹配的子串逆置。

7．S 是用结点大小为4 的单链表存储的串,分别编写算法在第k 个字符后插入串T，及从第k 个字符删除len 个字符。 以下算法用定长顺序串： 8．写下列算法：

（1） 将顺序串r 中所有值为ch1 的字符换成ch2 的字符。 （2 ）将顺序串r 中所有字符按照相反的次序仍存放在r 中。 （3） 从顺序串r 中删除其值等于ch 的所有字符。

（4 ） 从顺序串r1 中第index个字符起求出首次与串r2 相同的子串的起始位置。 （5） 从顺序串r 中删除所有与串r1 相同的子串。

9．写一个函数将顺序串s1 中的第i 个字符到第j 个字符之间的字符用 s2 串替换。 [提示]：（1）用静态顺序串 （2 ）先移位，后复制 10． 写算法，实现顺序串的基本操作 StrCompare(s,t)。 11． 写算法，实现顺序串的基本操作 StrReplace(&s,t,v)。 [提示]：

（1） 被替换子串定位（相当于第9 题中i）

（2 ） 被替换子串后面的字符左移或右移（为替换子串准备房间） （3） 替换子串入住（复制） （4 ） 重复上述，直到??

第五章

1．假设有 6 行 8 列的二维数组A，每个元素占用6 个字节，存储器按字节编址。已知A 的基地址为 1000，计算：

（1） 数组A 共占用多少字节； （288 ） （2 ） 数组A 的最后一个元素的地址； （1282） （3） 按行存储时，元素A36 的地址； （1126） （4 ） 按列存储时，元素A36 的地址； （1192） [注意]：本章自定义数组的下标从1 开始。

2． 设有三对角矩阵（a）,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得 ij n×n B[k]= aij ，求：

（1） 用i,j 表示k 的下标变换公式； （2 ） 用k 表示i,j 的下标变换公式。 i = k/3 + 1, j = k%3 + i - 1 = k%3 + k/3 或：

i = k/3 + 1, j = k - 2 ×( k/3 )

2．假设稀疏矩阵 A 和 B 均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元

组表C 存放结果矩阵。

[提示]：参考P.28 例、P.47 例。

4．在稀疏矩阵的快速转置算法5.2 中，将计算position[col]的方法稍加改动，使算法 只占用一个辅助向量空间。

5．写一个在十字链表中删除非零元素aij 的算法。 [提示]：“删除”两次，释放一次。

6．画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 7．求下列广义表运算的结果： （1） HEAD[((a,b),(c,d))]; （2 ） TAIL[((a,b),(c,d))];

（3） TAIL[HEAD[((a,b),(c,d))]];

（4 ） HEAD[TAIL[HEAD[((a,b),(c,d))]]]; b （5） TAIL[HEAD[TAIL[((a,b),(c,d))]]]; (d) 第六章

1．试分别画出具有3 个结点的树和 3 个结点的二叉树的所有不同形态。 2．对题1 所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。

3．已知一棵度为k的树中有n 个度为 1 的结点，n 个度为2 的结点，??，n 个度为k的结点，则该树中有多少个叶子结点？ [提示]：参考 P.116 性质3 ∵ n=n + n + ?? + n B=n + 2n + 3n + …… + kn n= B + 1

∴ n + n + ?? + n = n + 2n + 3n + ?? + kn + 1 ∴ n = n + 2n + ?? + (k-1)n + 1

4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二 叉树。

[提示]：参考 P.148

6． 已知二叉树有50 个叶子结点，则该二叉树的总结点数至少应有多少个？ [提示]：一个叶子结点，总结点数至多有多少个？可压缩一度结点。 7． 给出满足下列条件的所有二叉树： a) 前序和中序相同 b) 中序和后序相同 c) 前序和后序相同 [提示]：去异存同。

a) D L R 与L D R 的相同点：D R，如果无 L，则完全相同, 如果无 LR，?。 b) L D R 与L R D 的相同点：L D，如果无 R，则完全相同。 c) D L R 与L R D 的相同点：D，如果无 L R，则完全相同。 （如果去D，则为空树）

7． n 个结点的K 叉树，若用具有k 个child 域的等长链结点存储树的一个结点，则空的Child域有多少个？ [提示]：参考 P.119

8．画出与下列已知序列对应的树Ｔ：

树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。 [提示]：

（1）先画出对应的二叉树

（2 ）树的后根序列与对应二叉树的中序序列相同

9．假设用于通讯的电文仅由8 个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 （1）请为这8 个字母设计哈夫曼编码， （2 ）求平均编码长度。

10．已知二叉树采用二叉链表存放,要求返回二叉树T 的后序序列中的第一个结点的指针,是否可不用递归且不用栈来完成?请简述原因. [提示]：无右子的“左下端”

11. 画出和下列树对应的二叉树：

12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 13．编写递归算法：对于二叉树中每一个元素值为x 的结点，删去以它为根的子树，并释放相应的空间。

[提示]： [方法 1]：（1）按先序查找；（2 ）超前查看子结点（3）按后序释放； void DelSubTree(BiTree *bt, DataType x) {

if ( *bt != NULL && (*bt) ->data==x ) { FreeTree(*bt); *bt =NULL; }

else DelTree( *bt, x)

void DelTree(BiTree bt, DataType x) { if ( bt )

{ if (bt->LChild && bt->LChild->data==x) { FreeTree(bt->LChild); bt->LChild=NULL; }

if (bt->RChild && bt->RChild->data==x) { FreeTree(bt->RChild); bt->RChild=NULL; }

DelTree(bt->LChild, x); DelTree(bt->RChild, x); } }

[方法2]：（1）先序查找；（2 ）直接查看当前根结点（3）用指针参数； [方法3]：（1）先序查找；（2 ）直接查看当前根结点 （3）通过函数值，返回删除后结果； （参示例程序）

14．分别写函数完成：在先序线索二叉树T 中，查找给定结点*p 在先序序列中的后继。在后序线索二叉树T 中，查找给定结点*p 在后序序列中的前驱。 [提示]：

（1）先查看线索，无线索时用下面规律：

（2 ）结点*p 在先序序列中的后继为其左子或右子； （3）结点*p 在后序序列中的前驱也是其左子或右子。 15．分别写出算法，实现在中序线索二叉树中查找给定结点*p 在中序序列中的前驱与后继。 （参例题）

16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。 [提示]：

（1）可将孩子-兄弟链表划分为根、首子树、兄弟树，递归处理。 （2 ）可利用返回值，或全局变量。

17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。 18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。（参课本）

19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树 是指：在二叉树中不存在子树个数为 1 的结点。

for(m=0;m

G.vertices[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++) {

t=getchar();h=getchar(); //t 为弧尾,h 为弧头 if((i=LocateVex(G,t))<0) return ERROR;

if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 p=(ArcNode*)malloc(sizeof(ArcNode));

if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p; else {

for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc); q->nextarc=p; }

p->adjvex=j;p->nextarc=NULL; }//while return OK; }//Build_AdjList

7．6 试在邻接矩阵存储结构上实现图的基本操作：InsertVertex(G,v)，InsertArc(G, v, w)， DeleteVertex(G,v)和DeleteArc(G, v, w)。

//本题中的图G 均为有向无权图,其余情况容易由此写出

Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G 上插入顶点v {

if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK; }//Insert_Vex

Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G 上插入边 (v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(i==j) return ERROR; if(!G.arcs[i][j].adj) {

G.arcs[i][j].adj=1; G.arcnum++; }

return OK; }//Insert_Arc

Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G 上删除顶点v {

n=G.vexnum;

if((m=LocateVex(G,v))<0) return ERROR;

G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点 for(i=0;i

G.arcs[i][m]=G.arcs[i][n];

G.arcs[m][i]=G.arcs[n][i]; //将边的关系随之交换 }

G.arcs[m][m].adj=0; G.vexnum--; return OK; }//Delete_Vex

分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加.

Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G 上删除边 (v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) {

G.arcs[i][j].adj=0; G.arcnum--; }

return OK; }//Delete_Arc

7．7 试用邻接表存储结构重做题7.6。

//为节省篇幅,本题只给出Insert_Arc 算法.其余算法请自行写出.

Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G 上插入边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j;p->nextarc=NULL;

if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p; else {

for(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc) if(q->adjvex==j) return ERROR; //边已经存在 q->nextarc=p; }

G.arcnum++; return OK; }//Insert_Arc

7．8 试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中，是否存 在由顶点v i 到顶点v j 的路径（i≠j ）。注意：算法中涉及的图的基本操作必须在此存储结

构上实现。

int visited[MAXSIZE]; //指示顶点是否在当前路径上

int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G 中顶点i 到顶点 j 是否有路径,是则返回 1,否则返回0 {

if(i==j) return 1; //i 就是j else {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex;

if(!visited[k]&&exist_path(k,j)) return 1;//i 下游的顶点到j 有路径 }//for }//else

}//exist_path_DFS

7．9 同上题要求。试基于图的广度优先搜索策略写一算法。

int exist_path_BFS(ALGraph G,int i,int j)//广度优先判断有向图G 中顶点i 到顶点 j 是否有路径,是则返回 1,否则返回0 {

int visited[MAXSIZE]; InitQueue(Q); EnQueue(Q,i);

while(!QueueEmpty(Q)) {

DeQueue(Q,u); visited[u]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

k=p->adjvex; if(k==j) return 1;

if(!visited[k]) EnQueue(Q,k); }//for }//while return 0;

}//exist_path_BFS

7．10 试利用栈的基本操作，编写按深度优先策略遍历一个强连通图的非递归形式的算法。算法中不规定具体的存储结构，而将图Graph看成是一种抽象数据类型。 void STraverse_Nonrecursive(Graph G)//非递归遍历强连通图G {

int visited[MAXSIZE]; InitStack(S);

Push(S,GetVex(S,1)); //将第一个顶点入栈 visit(1);

visited=1;

while(!StackEmpty(S)) {

while(Gettop(S,i)&&i) {

j=FirstAdjVex(G,i); if(j&&!visited[j]) {

visit(j);

visited[j]=1;

Push(S,j); // 向左走到尽头 } }//while

if(!StackEmpty(S)) {

Pop(S,j); Gettop(S,i);

k=NextAdjVex(G,i,j); // 向右走一步 if(k&&!visited[k]) {

visit(k); visited[k]=1; Push(S,k); } }//if }//while

}//Straverse_Nonrecursive

分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考 6.37.由于是强连通图,所以从第一个结点出发一定能够访问到所有结点. 7．11 采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（指顶点序列中不含有重现的顶点）的算法。 int visited[MAXSIZE];

int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G 的顶点i 到j 是否存在长度为k 的简单路径 {

if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) {

l=p->adjvex; if(!visited[l])

if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一

}//for

visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else

return 0; //没找到 }//exist_path_len

7．13 已知一棵以二叉链表作存储结构的二叉树，试编写按层次顺序（同一层自左至右）遍历二叉树的算法。

void LayerOrder(Bitree T)//层序遍历二叉树 {

InitQueue(Q); //建立工作队列 EnQueue(Q,T);

while(!QueueEmpty(Q)) {

DeQueue(Q,p); visit(p);

if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); }

}//LayerOrder

第 8 章 查找

8．8 试写一个判别给定二叉树是否为二叉排序树的算法。设此二叉树以二叉链 表作存储结构，且树中结点的关键字均不同。int last=0,flag=1;

int Is_BSTree(Bitree T)//判断二叉树T 是否二叉排序树,是则返回 1,否则返回0 {

if(T->lchild&&flag) Is_BSTree(T->lchild);

if(T->datadata;

if(T->rchild&&flag) Is_BSTree(T->rchild); return flag; }//Is_BSTree

8．14 写一时间复杂度为O(log2n+m)的算法，删除二叉排序树中所有关键字不小于x的结点，并释放结点空间。其中n为树中的结点个数，m为被删除的结点个数。 void Delete_NLT(BiTree &T,int x)//删除二叉排序树T 中所有不小于x 元素结点, 并释放空间 {

if(T->rchild) Delete_NLT(T->rchild,x);

if(T->data

T=T->lchild;

free(q); //如果树根不小于x,则删除树根,并以左子树的根作为新的树根 if(T) Delete_NLT(T,x); //继续在左子树中执行算法 }//Delete_NLT

8．15 在平衡二叉排序树的每个结点中增加一个lsize域，其值为它的左子树中

的结点数加1。编写一时间复杂度为O(log n)的算法，确定数中第k个结点的位置。

typedef struct {

int data; int bf;

int lsize; //lsize 域表示该结点的左子树的结点总数加 1 BlcNode *lchild,*rchild;

} BlcNode,*BlcTree; //含lsize 域的平衡二叉排序树类型

BTNode *Locate_BlcTree(BlcTree T,int k)//在含lsize 域的平衡二叉排序树T 中确 定第k 小的结点指针 {

if(!T) return NULL; //k 小于 1 或大于树结点总数 if(T->lsize==k) return T; //就是这个结点 else if(T->lsize>k)

return Locate_BlcTree(T->lchild,k); //在左子树中寻找

else return Locate_BlcTree(T->rchild,k-T->lsize); //在右子树中寻找,注意要修改k 的值

}//Locate_BlcTree

第 9 章 内部排序

9．6 编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。 void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法 {

low=0;high=n-1; // 冒泡的上下界 change=1;

while(low

change=0;

for(i=low;ia[i+1]) {

a[i]<->a[i+1]; change=1; }

high--; //修改上界

for(i=high;i>low;i--) //从下向上起泡 if(a[i]

a[i]<->a[i-1]; change=1; }

low++; //修改下界 }//while

}//Bubble_Sort2

9．7 编写算法，对 n 个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记 录排在关键字为非负值的记录之前，要求：

采取顺序存储结构，至多使用一个记录的辅助存储空间；

算法的时间复杂度 O(n)； 讨论算法中记录的最大移动次数。

void Divide(int a[ ],int n)//把数组a 中所有值为负的记录调到非负的记录之前 {

low=0;high=n-1; while(low

while(low=0) high--; // 以0 作为虚拟的枢轴记录 a[low]<->a[high];

while(lowa[high]; }

}//Divide

9．8 试以单链表为存储结构实现简单选择排序的算法

void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法 {

for(p=L;p->next->next;p=p->next) {

q=p->next;x=q->data;

for(r=q,s=q;r->next;r=r->next) //在q 后面寻找元素值最小的结点 if(r->next->data

x=r->next->data; s=r; }

if(s!=q) //找到了值比q->data 更小的最小结点s->next {

p->next=s->next;s->next=q;

t=q->next;q->next=p->next->next; p->next->next=t;

} //交换q 和 s->next 两个结点 }//for

}//LinkedList_Select_Sort

9．9 假设含n个记录的序列中，其所有关键字为值介于v和w 之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v...w]且令number[i]为统计关键字取整数I 的记录数，之后按number 重排序列以达到有序，编写算法实现上述排序方法，并讨论此方法的优缺点。

void Enum_Sort(int a[ ],int n)//对关键字只能取v 到w 之间任意整数的序列进行排序 {

int number[w+1],pos[w+1];

for(i=0;i

pos[i]=pos[i-1]+num[i]; //pos 数组可以把关键字的值映射为元素在排好的序列 中的位置

for(i=0;i

分析:本算法参考了第五章三元组稀疏矩阵转置的算法思想,其中的pos 数组和那里的cpot 数组起的是相类似的作用.

9．10 已知两个有序序列(a1, a 2,..., a m)和(a m+1 , a m+2 ,..., a n ),并且其中一个序列的记录个数少于s,且s=?√n?. 试写一个算法,用O(n)时间和O(1)附加空间完成这两个有序序列的归并。

void SL_Merge(int a[ ],int l1,int l2)//把长度分别为l1,l2 且l1^2<(l1+l2)的两个有序 子序列归并为有序序列 {

start1=0;start2=l1; //分别表示序列 1 和序列2 的剩余未归并部分的起始位置 for(i=0;i

for(j=start2;j RSh(a,start1,j-1,k);//将 a[start1]到a[j-1]之间的子序列循环右移k 位 start1+=k+1;

start2=j; //修改两序列尚未归并部分的起始位置 }

}//SL_Merge

void RSh(int a[ ],int start,int end,int k)//将a[start]到a[end]之间的子序列循环右移k 位,算法原理参见 5.18 {

len=end-start+1; for(i=1;i<=k;i++)

if(len%i==0&&k%i==0) p=i; //求len 和k 的最大公约数p for(i=0;i

j=start+i;l=start+(i+k)%len;temp=a[j]; while(l!=start+i) {

a[j]=temp; temp=a[l]; a[l]=a[j];

j=l;l=start+(j-start+k)%len; //依次向右移 }

a[start+i]=temp; }//for }//RSh

9．12 设计一个用链表表示的直接选择排序算法。

void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法

{

for(p=L;p->next->next;p=p->next) {

q=p->next;x=q->data;

for(r=q,s=q;r->next;r=r->next) //在q 后面寻找元素值最小的结点 if(r->next->data

x=r->next->data; s=r; }

if(s!=q) //找到了值比q->data 更小的最小结点s->next {

p->next=s->next;s->next=q;

t=q->next;q->next=p->next->next; p->next->next=t;

} //交换q 和 s->next 两个结点 }//for

}//LinkedList_Select_Sort

9．16 已知（k1,k2,?k n）是堆，写一个算法将（k1,k2,?，k n，k n+1）调整为堆。按此思想写一个从空堆开始一个一个添入元素的建堆算法。

void Build_Heap(Heap &H,int n)//从低下标到高下标逐个插入建堆的算法 {

for(i=2;i

{ //此时从H.r[1]到H.r[i-1] 已经是大顶堆 j=i;

while(j!=1) //把H.r[i]插入 {

k=j/2;

if(H.r[j].key>H.r[k].key) H.r[j]<->H.r[k]; j=k; } }//for

}//Build_Heap/

本文来源：https://www.bwwdw.com/article/mb2x.html