《数据结构-用C语言描述》习题答案

1、 HYPERLINK /computer/book/read/data-structure/h971111102.html /computer/book/read/data-structure/h971111102.html习题解答(唐策善版)(其他版本在上面)第一章 绪论（参考答案）1.3 (1) O(n)(2) O(n)(3) O(n)(4) O(n1/2)(5) 执行程序段的过程中，x,y值变化如下：循环次数 x y0（初始） 91 1001 92 1002 93 100 9 100 10010 101 10011 91 9912 92 100 20 101 9921 91 98 30

2、101 9831 91 97 到y=0时，要执行10*100次，可记为O（10*y）=O（n）1.5 2100 , (2/3)n , log2n , n1/2 , n3/2 , (3/2)n , nlog2n , 2 n , n! , n n第二章 线性表(参考答案)在以下习题解答中，假定使用如下类型定义：（1）顺序存储结构：#define MAXSIZE 1024typedef int ElemType;/ 实际上，ElemType可以是任意类型 typedef struct ElemType dataMAXSIZE;int last; / last表示终端结点在向量中的位置 sequenl

3、ist;（2）链式存储结构（单链表）typedef struct nodeElemType data; struct node *next； linklist;（3）链式存储结构（双链表）typedef struct nodeElemTypedata;struct node *prior,*next；dlinklist;（4）静态链表typedef structElemType data;int next;node;node saMAXSIZE;2.1 头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是l

4、a，往往简称为“链表la”。头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品），其指针域指向头结点。这样在插入和删除中头结点不变。开始结点：即上面所讲第一个元素的结点。2.2 只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。23 void insert(ElemType A,int elenum,ElemType x)/ 向量A目前有elenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的递增有序。 int i=0,j; while (ielenum

5、 & Ai=i;j-) Aj+1=Aj;/ 向后移动元素 Ai=x; / 插入元素 / 算法结束24 void rightrotate(ElemType A,int n,k)/ 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。 int num=0; / 计数，最终应等于n int start=0; / 记录开始位置（下标） while (numn) temp=Astart; /暂存起点元素值，temp与向量中元素类型相同 empty=start; /保存空位置下标 next=(start-K+n) %n; / 计算下一右移元素的下标 while (next !=st

6、art) Aempty=Anext;/ 右移 num+; / 右移元素数加1 empty=next; next=(next-K+n) %n; / 计算新右移元素的下标 Aempty=temp; / 把一轮右移中最后一个元素放到合适位置 num+; start+; / 起点增1，若numn则开始下一轮右移。 / 算法结束 算法二 算法思想：先将左面n-k个元素逆置，接着将右面k个元素逆置，最后再将这n个元素逆置。void rightrotate(ElemType A,int n,k)/ 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。 ElemType temp; f

7、or(i=0;i(n-k)/2;i+) /左面n-k个元素逆置 temp=Ai; Ai=An-k-1-i; An-k-1-i=temp; for(i=1;i=k;i+) /右面k个元素逆置 temp=An-k-i; An-k-i=An-i; An-i=temp; for(i=0;inext, *pre=L，*s;/ p为工作指针，指向当前元素，pre为前驱指针，指向当前元素的前驱 s=(linklist *)malloc(sizeof(linklist);/申请空间，不判断溢出s-data=x; while (p & p-datanext; / 查找插入位置 pre-next=s; s-nex

8、t=p; / 插入元素 / 算法结束 26void invert(linklist *L)/ 本算法将带头结点的单链表L逆置。 /算法思想是先将头结点从表上摘下，然后从第一个元素结点开始，依次前插入以L为头结点的链表中。 linklist *p=L-next,*s;/ p为工作指针，指向当前元素，s为p的后继指针 L-next=null;/头结点摘下，指针域置空。算法中头指针L始终不变 while (p) s=p-next; / 保留后继结点的指针 p-next=L-next; / 逆置 L-next=p; p=s; / 将p指向下个待逆置结点 / 算法结束 27(1) int length1

9、(linklist *L)/ 本算法计算带头结点的单链表L的长度 linklist *p=L-next; int i=0;/ p为工作指针，指向当前元素，i 表示链表的长度 while (p) i+; p=p-next; return(i); / 算法结束(2) int length1(node saMAXSIZE)/ 本算法计算静态链表s中元素的个数。 int p=sa0.next, i=0;/ p为工作指针，指向当前元素，i 表示元素的个数，静态链指针等于-1时链表结束 while (p！=-1) i+; p=sap.next; return(i); / 算法结束 28void union

10、_invert(linklist *A,*B,*C)/ A和B是两个带头结点的递增有序的单链表，本算法将两表合并成 / 一个带头结点的递减有序单链表C，利用原表空间。 linklist *pa=A-next,*pb=B-next,*C=A,*r;/ pa,pb为工作指针，分别指向A表和B表的当前元素，r为当前逆置/元素的后继指针, 使逆置元素的表避免断开。 /算法思想是边合并边逆置，使递增有序的单链表合并为递减有序的单链表。 C-next=null;/头结点摘下，指针域置空。算法中头指针C始终不变 while (pa & pb) / 两表均不空时作 if (pa-datadata) / 将A表

11、中元素合并且逆置 r=pa-next; / 保留后继结点的指针 pa-next=C-next; / 逆置 C-next=pa; pa=r; / 恢复待逆置结点的指针 else / 将B表中元素合并且逆置 r=pb-next; / 保留后继结点的指针 pb-next=C-next; / 逆置 C-next=pb; pb=r; / 恢复待逆置结点的指针 / 以下while (pa)和while (pb)语句，只执行一个 while (pa) / 将A表中剩余元素逆置 r=pa-next; / 保留后继结点的指针 pa-next=C-next; / 逆置 C-next=pa; pa=r; / 恢复待

12、逆置结点的指针 while (pb) / 将B表中剩余元素逆置 r=pb-next; / 保留后继结点的指针 pb-next=C-next; / 逆置 C-next=pb; pb=r; / 恢复待逆置结点的指针 free(B);/释放B表头结点 / 算法结束 29 void deleteprior(linklist *L)/ 长度大于1的单循环链表，既无头结点，也无头指针，本算法删除*s 的前驱结点 linklist *p=s-next,*pre=s; / p为工作指针，指向当前元素，/ pre为前驱指针，指向当前元素*p的前驱 while (p-next!=s) pre=p; p=p-nex

13、t; / 查找*s的前驱 pre-next=s; free(p); / 删除元素 / 算法结束 210void one_to_three(linklist *A,*B,*C)/ A是带头结点的的单链表，其数据元素是字符字母、字符、数字字符、其他字符。本算法/将A表分成 / 三个带头结点的循环单链表A、B和C，分别含有字母、数字和其它符号的同一类字符，利用原表空间。 linklist *p=A-next,r;/ p为工作指针，指向A表的当前元素，r为当前元素的后继指针,使表避免断开。 /算法思想是取出当前元素，根据是字母、数字或其它符号，分别插入相应表中。 B=(linklist *)mallo

14、c(sizeof(linklist);/申请空间，不判断溢出 B-next=null; / 准备循环链表的头结点 C=(linklist *)malloc(sizeof(linklist);/申请空间，不判断溢出 C-next=null; / 准备循环链表的头结点 while(p) r=p-next; / 用以记住后继结点 if (p-data=a&p-datadata=A& p-data next=A-next; A-next=p; / 将字母字符插入A表 else if (p-data=0&p-datanext=B-next; B-next=p; / 将数字字符插入B 表 else p-n

15、ext=C-next; C-next=p;/ 将其它符号插入C 表 p=r; / 恢复后继结点的指针 /while / 算法结束 211void locate(dlinklist *L)/ L是带头结点的按访问频度递减的双向链表，本算法先查找数据x,/ 查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。 linklist *p=L-next,*q;/p为工作指针，指向L表的当前元素，q为p的前驱，用于查找插入位置。 while (p & p-data !=x) p=p-next; / 查找值为x的结点。 if (!p) return (“不存在值为x的结点”); els

16、e p-freq+; / 令元素值为x的结点的freq域加1 。 p-next-prir=p-prior; / 将p结点从链表上摘下。 p-prior-next=p-next;q=p-prior; / 以下查找p结点的插入位置 while (q !=L & q-freqprior; p-next=q-next; q-next-prior=p;/ 将p结点插入 p-prior=q; q-next=p； / 算法结束 第三章 栈和队列(参考答案)/ 从数据结构角度看，栈和队列是操作受限的线性结构，其顺序存储结构 / 和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。3.1 1 2 3 4

17、 2 1 3 4 3 2 1 4 4 3 2 11 2 4 3 2 1 4 3 3 2 4 1 1 3 2 4 2 3 1 4 3 4 2 11 3 4 2 2 3 4 1 1 4 3 2 2 4 3 1 设入栈序列元素数为n，则可能的出栈序列数为C2nn=(1/n+1)*(2n!/(n!)2)3.2 证明：由jk和pjpk 说明pj在pk之前出栈，即在k未进栈之前pj已出栈，之后k进栈，然后pk出栈；由jpk 说明pj在pk之后出栈，即pj被pk 压在下面，后进先出。由以上两条，不可能存在ijk使pjpknext;while (idata); p=p-next; if (n % 2 !=0)

18、 p=p-next;/ 奇数个结点时跳过中心结点 while (p & p-data=pop(s) p=p-next; if (p=null) printf(“链表中心对称”)； else printf(“链表不是中心对称”)； / 算法结束 3.4 int match()/从键盘读入算术表达式，本算法判断圆括号是否正确配对（init s;/初始化栈s scanf(“%c”,&ch); while (ch!=#) /#是表达式输入结束符号switch (ch) case (: push(s,ch); break; case ): if (empty(s) printf(“括号不配对”); ex

19、it(0); pop(s); if (!empty(s) printf(“括号不配对”); else printf(“括号配对”); / 算法结束 3.5typedef struct / 两栈共享一向量空间 ElemType vm; / 栈可用空间0m-1 int top2 / 栈顶指针twostack;int push(twostack *s,int i, ElemType x) / 两栈共享向量空间,i是0或1，表示两个栈，x是进栈元素，/ 本算法是入栈操作 if (abs(s-top0 - s-top1)=1) return(0);/ 栈满 else switch (i) case 0:

20、 s-v+(s-top)=x; break; case 1: s-v-(s-top)=x; break; default: printf(“栈编号输入错误”); return(0); return(1); / 入栈成功 / 算法结束 ElemType pop(twostack *s,int i) / 两栈共享向量空间,i是0或1，表示两个栈，本算法是退栈操作 ElemType x;if (i!=0 & i!=1) return(0);/ 栈编号错误 else switch (i) case 0: if(s-top0=-1) return(0);/栈空else x=s-vs-top-;break

21、; case 1: if(s-top1=m) return(0);/栈空else x=s-vs-top+; break; default: printf(“栈编号输入错误”);return(0); return(x); / 退栈成功 / 算法结束 ElemType top (twostack *s,int i) / 两栈共享向量空间,i是0或1，表示两个栈，本算法是取栈顶元素操作 ElemType x; switch (i) case 0: if(s-top0=-1) return(0);/栈空else x=s-vs-top; break; case 1: if(s-top1=m) retur

22、n(0);/栈空else x=s-vs-top; break; default: printf(“栈编号输入错误”);return(0); return(x); / 取栈顶元素成功 / 算法结束 36void Ackerman(int m,int n) / Ackerman 函数的递归算法 if (m=0) return(n+1); else if (m!=0 & n=0) return(Ackerman(m-1,1);else return(Ackerman(m-1,Ackerman(m,n-1) / 算法结束 37(1) linklist *init(linklist *q)/ q是以带头

23、结点的循环链表表示的队列的尾指针，本算法将队列置空 q=(linklist *)malloc(sizeof(linklist);/申请空间，不判断空间溢出q-next=q;return (q); / 算法结束 (2) linklist *enqueue(linklist *q，ElemType x)/ q是以带头结点的循环链表表示的队列的尾指针，本算法将元素x入队 s=(linklist *)malloc(sizeof(linklist);/申请空间，不判断空间溢出s-next=q-next; / 将元素结点s入队列 q-next=s;q=s; / 修改队尾指针 return (q); / 算

24、法结束 (3) linklist *delqueue(linklist *q)/q是以带头结点的循环链表表示的队列的尾指针，这是出队算法 if (q=q-next) return (null); / 判断队列是否为空 else linklist *s=q-next-next; / s指向出队元素 if (s=q) q=q-next; / 若队列中只一个元素，置空队列else q-next-next=s-next;/ 修改队头元素指针 free (s); / 释放出队结点 return (q); / 算法结束。算法并未返回出队元素 3.8 typedef structElemType datam

25、;/ 循环队列占m个存储单元 int front,rear; / front和rear为队头元素和队尾元素的指针 / 约定front指向队头元素的前一位置，rear指向队尾元素 sequeue; int queuelength(sequeue *cq) / cq为循环队列，本算法计算其长度 return (cq-rear - cq-front + m) % m; / 算法结束 3.9 typedef structElemType sequm;/ 循环队列占m个存储单元 int rear,quelen; / rear指向队尾元素,quelen为元素个数sequeue;(1) int empty(

26、sequeue *cq) / cq为循环队列，本算法判断队列是否为空 return (cq-quelen=0 ? 1: 0); / 算法结束 (2) sequeue *enqueue(sequeue *cq，ElemType x)/ cq是如上定义的循环队列，本算法将元素x入队if (cq-quelen=m) return(0); / 队满 else cq-rear=(cq-rear+1) % m; / 计算插入元素位置 cq-sequcq-rear=x; / 将元素x入队列 cq-quelen+; / 修改队列长度 return (cq); / 算法结束 ElemType delqueue(

27、sequeue *cq)/ cq是以如上定义的循环队列，本算法是出队算法，且返回出队元素 if (cq-quelen=0) return(0); / 队空 else int front=(cq-rear - cq-quelen + 1+m) % m;/ 出队元素位置 cq-quelen-; / 修改队列长度 return (cq-sequfront); / 返回队头元素 / 算法结束第四章 串 (参考答案)在以下习题解答中，假定使用如下类型定义：#define MAXSIZE 1024typedef struct char dataMAXSIZE;int curlen; / curlen表示终

28、端结点在向量中的位置 seqstring;typedef struct nodechar data;struct node *next ；linkstring;4.2 int index(string s,t) /s,t是字符串，本算法求子串t在主串s中的第一次出现，若s串中包含t串，返回其/第一个字符在s中的位置，否则返回0m=length(s); n=length(t); i=1; while(i=m-n+1) if(strcmp(substr(s,i,n),t)=0) break; else i+;if(inext; q=Y-next; pre=p; while (p & q) ch=p

29、-data; / 取X中的字符 while (q & q-data!=ch) q=q-next; / 和Y中字符比较 if (!q) return(ch); / 找到Y中没有的字符 else pre=p-next; / 上一字符在Y中存在， p=pre; / 取X中下一字符。 q=Y-next; / 再从Y的第一个字符开始比较 return(null); / X中字符在Y中均存在 / 算法结束 4.6 int strcmp(seqstring *S, seqstring *T)/ S和T是指向两个顺序串的指针，本算法比较两个串的大小，若S串大于T串，返回1；若S串等于T串，返回0；否则返回-1

30、 int i=0; while (s-chi!=0 & t-chi!=0) if (s-chit-chi) return(1); else if (s-chichi) return(-1); else i+; / 比较下一字符 if (s-chi!=0& t-chi=0) return(1);else if (s-chi=0& t-chi!=0) return(-1); else return(0);/ 算法结束4.7 linkstring *invert(linkstring *S, linkstring *T)/ S和T是用带头结点的结点大小为1的单链表表示的串，S是主串，T是/ 模式串。

31、本算法是先模式匹配，查找T在S中的第一次出现。如模式匹/ 配成功，则将S中的子串（T串）逆置。linkstring *pre,*sp, *tp; pre=S; / pre是前驱指针，指向S中与T匹配时，T 中的前驱 sp=S-next; tp=T-next;/sp 和tp分别是S和T串上的工作指针 while (sp & tp)if (sp-data=tp-data) / 相等时后移指针 sp=sp-next; tp=tp-next;else / 失配时主串回溯到下一个字符，子串再以第一个字符开始 pre=pre-next; sp=pre-next; tp=T-next;if (tp!=nul

32、l) return (null); / 匹配失败，没有逆置 else / 以下是T串逆置 tp=pre-next; / tp是逆置的工作指针，现在指向待逆置的第一个字符pre-next=sp; / 将S中与T串匹配时的前驱指向匹配后的后继 while (tp!=sp) r=tp-next; tp-next=pre-next; pre-next=tp; tp=r / 算法结束 第五章 多维数组和广义表（参考答案）5.1 A2323A0000 , A0001 , A0002 A0010 , A0011 , A0012 A0100 , A0101 , A0102 A0110 , A0111 , A0

33、112 A0200 , A0201 , A0202 A0210 , A0211 , A0212 将第一维的0变为1后，可列出另外18个元素。以行序为主（即行优先）时，先改变右边的下标，从右到左进行。5.2 设各维上下号为c1d1，c2d2，c3d3，每个元素占l个单元。LOC(aijk)=LOC(ac1c2c3)+(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3)*l推广到n维数组！（下界和上界）为（ci，di），其中1=i=n.则：其数据元素的存储位置为：LOC（aj1j2.jn）=LOC（ac1c2cn）+（d2-c2+1） （dn-cn+

34、1）(j1-c1)+(d3-c3+1) （dn-cn+1）n(j2-c2)+(dn-cn+1)(jn-1-cn-1)+(jn-cn)*l=LOC(ac1c2c3)+ i(ji-ci) i=1 n其中i（dk-ck+1）（1=i=n） k=i+1若从c开始，c数组下标从0开始，各维长度为bi（1=i=n）则：LOC（aj1j2jn）=LOC(a000)+(b2* b3* bn*j1+ b3* * bn*+ j2+ bn* jn-1+ jn)*l n=LOC(a000)+ iji 其中：i=l，i-1=bi*i ，1i=n5.3 (1) k=2*i+j ( 0=k3n-2 )(2) i=(k+1)

35、/3 ( 0=k3n-2 ) j=k-2*i5.4void saddlepoint(int amn); / a是m行n列的二维数组,本算法求所有马鞍点 / b是一维数组,存放一行中可能的马鞍点的列值,k记相等值个数 / c是一维数组,存放某列可能马鞍点的行值,kk记相等值个数 for(i=0;im;i+) min=ai,0; / 最小值初始化 b0=0; k=1; / b数组记最小值的列号，k记最小值的个数 for(j=1;jn;j+) / 找每一行中的最小值 if (aijmin) b0=j; min=aij;k=1;/ 重新确定最小值 else if (aij=min) bk+1=j; k

36、+; / 有相等的最小值 for (jj=0;jjk;k+) / 第i 行有k个相等的最小值 j=bjj; max=aijj; kk=0; / aij是否是马鞍点 while (kk=aikk) kk+; if(kk=m)printf(“马鞍点 i=%d,j=%d,aij=%d”,i,j,aij); / END OF for jj / END OF for i 最坏时间复杂度为O(m*(n+n*m). (最坏时所有元素相同，都是马鞍点) 解法2: 若矩阵中元素值互不相同,则用一维数组row记下各行最小值，再用一维数组col记下各列最大值， 相等者为马鞍点。for (i=0;im;i+) row

37、i=ai0; / 最小值初始化 for (j=1;jn;j+) / 找每一行中的最小值 if (aijrowi) rowi=aij; / 重新确定最小值 for (j=0;jn;j+) colj=a0,j; / 最大值初始化 for (i=1;icolj) colj=aij; / 重新确定最大值 for (i=0;im;i+) for (j=1;jn;j+)if(rowi=colj)printf(“马鞍点 i=%d,j=%d,aij=%d”,i,j,aij); 时间复杂度O( (m*n). 解法3: 设定两个数组： max0.n-1 记各列的最大值所在行号 min0.m-1 记各行的最小值所在

38、列号第j 列的最大值为Amaxjj,第i行的最小值是Aiminivoid saddlepoint(int amn); / a是m行n列的二维数组,本算法求所有马鞍点 int max=0,min=0;for(i=0;im;i+) for(i=0; im; i+) for (j=0; jAmaxjj) maxj=i; / 重新确定第j列最大值的行号if (AijAimini) mini=j; / 重新确定第i行最小值的列号 for (i=0;inext;cb=B-next; while(ca!=A&cb!=B) /设pa和pb为矩阵A和B想加时的工作指针 pa=ca-right;pb=cb-rig

39、ht; if(pa=ca)ca=ca-next;/A表在该行无非0元素； else if(pb=cb)cb=cb-next/B表在该行无非0元素； else if(pb-colcol)/B的非0元素插入A中； j=pb-col;pt=chbj;pre=pt/ 取到表头指针； while(pt-down_colcol) pre=pt;pt=pt-down; pre-down=pt-down;/该结点从B表相应列摘下 i=pb-right;pt=chbi;pre=pt;/取B表行表头指针 while(pt-right-rowrow pre=pt;pt=pt-right; pre-right=pt-

40、riht;/该结点从B表相应行链表中摘下。 Pbt=pb;pb=pb-right;/B表移至下一结点 /以下是将pbt插入A表的相应列链表中 j=pbt-col;pt=chaj;pre=pt; while(pt-down !=chaj&pt-down-rowrow) pre=pt;pt=pt-down pre-down=pbt;pbt-down=pt; /以下是将pbt插入A表相应行链表中 i=pbt-right;pt=chai;pre=pt; while(pt-right !=chai&pt-right-colcol) pre=pt;pt=pt-right; pre-right=ptb; p

41、tb-right=pt; /end of “if (pb-colcol) else if(pa-col=pb-col)/处理两表中行列相同的非0元素 v=pa-data+pb-data; if(v !=0) pa-data+=pb-data;pa=pa-right; 将pb从行链表中删除；pb=pb-right; else将pa,pb从链表中删除;然后 pa=pa-right; pb=pb-right; 5.7 (1) head(p,h,w)=p(2) tail(b,k,p,h)=(k,p,h)(3) head(a,b),(c,d)=(a,b)(4) tail(a,b),(c,d)=(c,d)

42、(5) head(tail(a,b),(c,d)=(c,d)(6) tail(head(a,b),(c,d)=(b)5.8 (1) (2) 5.9(1) 第6章 树和二叉树（参考答案）6.1(1)根结点a 6.2 三个结点的树的形态： 三个结点的二叉树的形态：（2）（3）（1）（1）（2）（4） （5）63 设树的结点数是n，则n=n0+n1+n2+nm+ (1)设树的分支数为B，有n=B+1n=1n1+2n2+mnm+1 (2)由（1）和（2）有：n0=n2+2n3+(m-1)nm+16.4(1) ki-1 (i为层数)(2) (n-2)/k+1(3) (n-1)*k+i+1(4) (n-1

43、)%k !=0; 其右兄弟的编号 n+16.5（1）顺序存储结构 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCD#EF#G#H注：#为空结点 A C B E F D H G 6.6(1) 前序 ABDGCEFH(2) 中序 DGBAECHF(3) 后序 GDBEHFCA6.7(1) 空二叉树或任何结点均无左子树的非空二叉树(2) 空二叉树或任何结点均无右子树的非空二叉树(3) 空二叉树或只有根结点的二叉树6.8int height(bitree bt)/ bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度 int bl,br; / 局部变量，分别表示二叉树左

44、、右子树的高度 if (bt=null) return(0); else bl=height(bt-lchild); br=height(bt-rchild); return(blbr? bl+1: br+1); / 左右子树高度的大者加1（根） / 算法结束 6.9void preorder(cbt,int n,int i); / cbt是以完全二叉树形式存储的n个结点的二叉树，i是数 / 组下标，初始调用时为1。本算法以非递归形式前序遍历该二叉树 int i=1,s,top=0; / s是栈，栈中元素是二叉树结点在cbt中的序号 / top是栈顶指针，栈空时top=0 if (n=0) p

45、rintf(“输入错误”);exit（0）；while (i0) while(i=n) visit(cbti); / 访问根结点 if (2*i+10) i=stop-; / 退栈，先序访问右子树 / END OF while (i0) / 算法结束 /以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用*表示 void preorder(bt,int n,int i); / bt是以完全二叉树形式存储的一维数组，n是数组元素个数。i是数 / 组下标，初始调用时为1。 if (idata!=T2-data) return(0);/ 根结点值不等 else return(equal(T1-l

46、child,T2-lchild)&equal(T1-rchild,T2-rchild) /判左右子树等价/ 算法结束 611void levelorder (bitree ht);本算法按层次遍历二叉树htif (ht!=null) initqueue(q); 处始化队列，队列元素为二叉树结点的指针 enqueue(q,ht); 根结点指针入队列while (!empty(q) p=delqueue(q); visit(p); / 访问结点 if (p-lchild!=null) enqueue (q,p-lchild); /若左子女非空，则左子女入队列 if (p-rchild!=null)

47、 enqueue (q,p-rchild)； /若右子女非空，则右子女入队列 / 算法结束 612void preorder (bitree *t); (前序非递归遍历) bitree *sn+1; / s是指针数组，数组中元素为二叉树节点的指针top=0;while (t!=null | top!=0) while (t!=null) visit(*t); s+top=t; t=t-lchild if (top!=0) t=stop-; t=t-rchild; / 算法结束 void inorder (bitree *t); (中序非递归遍历)bitree *sn+1;top=0;while

48、 (t!=null | top!=0) while (t!=null) s+top=t; t=t-lchild if (top!=0) t=stop-; visit(*t); t=t-rchild; / 算法结束 void postorder (bitree *t); (后序非递归遍历)typedef struct node bitree *t; tag:0.1 stack;stack sn+1 ;top=0;while (t | top) while (t) s+top.t=t; stop.tag=0; t=t-lchild; while (top & stop.tag=1) printf(

49、stop-.t-data:3);if (top) stop.tag=1; t=stop.t-rchild ; / 算法结束 6.13bitree *dissect(bitree *t,ElemType x)/ 二叉树t至多有一个结点的数据域为x，本算法拆去以x为根的子树 / 拆开后的第一棵树用t表示，成功拆开后返回第二棵二叉树bitree *p,*find; if (*t!=null) if (*t)-data=x) / 根结点数据域为x p=*t; *t=null; return(p); else find=(dissect(&(*t)-lchild),x); / 在左子树中查找并拆开 /

50、若在左子树中未找到，就到右子树中查找并拆开 if (!find) find=(dissect(&(*t)-rchild),x); return(find); else return(null); / 空二叉树 / 算法结束 6.14int search(bitree t,ElemType x)/ 设二叉树t中，值为x的结点至多一个，本算法打印x的所有祖先 / 算法思想是，借助后序非递归遍历，用栈装遍历过程的结点，当查到 / 值为x的结点时，栈中元素都是x的祖先 typedef struct bitree p; int tag; snode; snode s; int top=0; while

51、(t & t-data !=x | top) while (t & t-data !=x) / 沿左分支向下 s+top.p=t; stop.tag=0; t=t-lchild; if (t-data=x) / for (i=1;idata);/ 输出，设元素为字符 return(1); elsewhile (top0 & stop.tag=1) top-;/退出右子树已访问的结点 if (top0) / 置访问标志1，访问右子树 stop.tag=1;t=stop.p; t=t-rchild; return(0); / 没有值为x的结点 / 算法结束 6.15 中序序列BDCEAFHGA后序

52、序列DECBHGFAFBGCDHE前序序列 ABCDEFGHA6.16 后序线索树： BCDEFHEnull只有空指针处才能加线索。线索链表： 0 A 0 0 C 0 0 B 1 0 F 1 1 E 1 1 0 0 1 H 1 1 G 1 6.17bitree *search(bitree *p)/ 查找前序线索二叉树上给定结点p的前序后继 if (p-ltag=1) return(p-rchild)； / 左标记为1时，若p的右子树非空，p的右子树的根p-rchild为p的后继；若右子树为空，p-rchild指向后继 else return(p-lchild); / 左标记为0时，p的左子女

53、p-lchild为p的后继 . / 算法结束 6.18 bitree *search（b：tree *p） /在后序线索二叉树中查找给定结点的后序前驱的算法 if(p-rtag=0) return(p-rchild); /p有右子女时，其右子女p-rchild是p的后序前驱else return(p-lchild); /p的左标记为0，左子女p-lchild是后序前驱, 否则，线索p-lchild指向p的后序前驱 A6.19GBLHCMIDNPJEOQKFR前序序列：ABCDEFGHIJKLMPQRNO后序序列：BDEFCAIJKHGQRPMNOL6.21 6.227,19,2,6,32,3,

54、21,10其对应字母分别为a,b,c,e,f,g,h。 哈夫曼编码：a：0010b：10c：00000d：0001e：01f：00001g：11h：0011第七章图（参考答案）71（1）邻接矩阵中非零元素的个数的一半为无向图的边数；（2）Aij= =0为顶点，I 和j无边，否则j和j有边相通；（3）任一顶点I的度是第I行非0元素的个数。72（1）任一顶点间均有通路，故是强连通；（2）简单路径 V4 V3 V1 V2;（3）0 1 1 0 1 1 0 1 0邻接矩阵V1V4 |V2 | |V2V3 |V1 | |V3V4V3 |邻接表V1V3 |V2V1 |V2 | |V4 | |V3V4V1

55、|逆邻接表73（1）邻接表V14 |2 | 6 |5 |3 |V21 | 6 |V31 | 4 |5 |V41 | 6 |3 |5 |V55 | 4 |1 |3 |V61 | 2 |4 |5 |（2）从顶点4开始的DFS序列：V5,V3,V4,V6,V2,V1（3）从顶点4开始的BFS序列：V4,V5,V3,V6,V1,V274（1） adjlisttp g; vtxptr i,j; /全程变量 void dfs(vtxptr x)/从顶点x开始深度优先遍历图g。在遍历中若发现顶点j，则说明顶点i和j间有路径。 visitedx=1; /置访问标记 if (y= =j) found=1;exi

56、t(0);/有通路，退出else p=gx.firstarc;/找x的第一邻接点 while (p!=null) k=p-adjvex; if （!visitedk）dfs(k); p=p-nextarc;/下一邻接点 void connect_DFS (adjlisttp g) /基于图的深度优先遍历策略，本算法判断一邻接表为存储结构的图g种，是否存在顶点i/到顶点j的路径。设 1=i ,j=n,ij. visited1.n=0;found=0; scanf (&i,&j); dfs (i); if (found) printf （” 顶点”,i,”和顶点 ”,j,”有路径 ”）；else

57、printf （” 顶点”,i,”和顶点 ”,j,”无路径 ”）；/ void connect_DFS(2)宽度优先遍历全程变量，调用函数与（1）相同，下面仅写宽度优先遍历部分。void bfs(vtxptr x)/ initqueue(q);enqueue(q,x); while (!empty(q); y=delqueue(q); if (y= =j) found=1;exit(0);/有通路，退出 else p=gx.firstarc;/第一邻接点 while (p!=null) k=p-adjvex; if (! Vistedk) enqueue(q,k); p=p-nextarc /

58、 if(y= =j) /while(!empty(q)75。假定该有向图以邻接表存储，各顶点的邻接点按增序排列DFS序列：V1,V3,V6,V7,V4,V2,V5,V8BFS序列：V1,V3,V4,V6,V7,V2,V5,V8DFS森林 BFS森林V1V2 V1 V2V3 V4V3 V4V5V5V6V7V6V8V8V776简单回路指起点和终点相同的简单路径。算法基本思想是利用图的遍历，以顶点VK开始，若遍历中再通到VK，则存在简单回路，否则不存在简单回路。Adjlisttp g ; visited1.n=0;Int found =0;/全程变量Int dfs(btxptr x)/从k顶点深度优

59、先遍历图g，看是否存在k的简单回路 visitedx=1; p=gx.firstarc; while(p!=null) w=p-adjvex; if(w= =k) found=1;exit(0);/有简单回路，退出 if (!visitedk ) dfs(w ); p=p-nextarc;/while(p!=null)/ dfs77 （1）PRIM算法的最小生成树bbbeb222222addadaa1ccbebgeeb222222dada222da11 1 1111hacfc1hfc1 1 1 1（2）KRUSKAL算法的最小生成树dbggee122cda2 1 1111hachf 1 1 1

60、（权值相同的边选取无顺序）78所选顶点已选定点的集合尚未被选顶点的集合DIST2 3 4 5 6初态12，3，4，5，620 15 31，32，4，5，619 2521，3，24，5，6 29 2561，3，2，64，5 29 2941，3，2，6，45 2951，3，2，6，4，5注：选定点4和5时无优先顺序，二者最短路径均为2979 0 8 1 2 00:1-1A0= 3 0 path0 = 1 2 01:1-2 5 2 01 2 3:1到3没有直接通路 0 8 path1同path0,加入顶点1后无变化A1= 3 0 5 2 0 0 8 A2= 3 0 path2同path15 2 0