《数据结构—用C语言描述》课后习题答案.pdf

《《数据结构—用C语言描述》课后习题答案.pdf》由会员分享，可在线阅读，更多相关《《数据结构—用C语言描述》课后习题答案.pdf（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课后习题参考答案第 一 章 绪论1.3 (1)0(n)(2)(2)0(n)(3)(3)0(n)(4)(4)0(/2)(5)(5)执行程序段的过程中，x,y 值变化如下:循环次数X0 （初始）9 11 0 019 21 0 029 31 0 091 0 01 0 01 01 0 11 0 01 19 19 91 29 21 0 02 01 0 19 92 19 19 83 01 0 19 83 19 19 7到 y=0 时，要执行1 0*1 0 0 次，可记为O (1 0*y)=0 (n)1.5 21 0 0,(2/3)n,l o g2n ,n/2,n3/2,(3/2)n,nl o g2

2、n,2n,n!,n第二章线性表(参考答案)在以下习题解答中，假定使用如下类型定义：(1)顺序存储结构：#defin e M AX S I ZE 1 0 2 4ty pedef in t El em T y pe;/实际上，El em T y pe可以是任意类型ty pedef struct El em T y pe dataM AX S I ZE;in t l ast;加 st表示终端结点在向量中的位置J sequen l ist;(2)链式存储结构(单链表)ty pedef struct n o de El em T y pe data;struct n o de*n ex t；l in k

3、 l ist;(3)链式存储结构(双链表)ty pedef struct n o de El em T y pe data;struct n o de*prio r,*n ex t；dl in k l ist;(4)静态链表ty pedef struct El em T y pe data;in t n ex t;)node;node saMAXSIZE;2.1 头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是la,往往简称为“链表la”。头结点：为了链表操作统一，在链表第一元素结点(称为首元结点，或首

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

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

6、 标 _ _A empty二 temp;/把一轮右移中最后一个元素放到合适位置num+;start+;起 点 增 1,若 num n 则开始下一轮右移。/算法结束算法二算法思想：先将左面n-k个元素逆置，接着将右面k 个元素逆置，最后再将这n 个元素逆置。void rightrotate(ElemType A,int n,k)/以向量作存储结构，本算法将向量中的n 个元素循环右移k 位，且只用一个辅助空间。ElemType temp;for(i=0;i(n-k)/2;i+)左面 nk 个元素逆置temp=Ai;Ai=An-k-l-i;An-k-l-i=temp;for(i=l;i=k;i+)右

7、面k 个元素逆置temp=An-k-i;An-k-i=An-i;An-i=temp;for(i=0;ine x t,*p re=L,*s;p为工作指针，指向当前元素，p re 为前驱指针，指向当前元素的前驱s=(li nk li s t *)malloc(s i z e of (li nk li s t);申请空间,不判断溢出s-dat a=x;w h i le (p&p-dat ane x t;/查找插入位置p re-ne x t=s;s-ne x t=p;/插入元素 /算法结束2 6v oi d i nv e rt (li nk li s t *L)/本算法将带头结点的单链表L 逆置。算法

8、思想是先将头结点从表上摘下，然后从第一个元素结点开始，依次前插入以 L为头结点的链表中。li nk li s t *p=L-ne x t,*s;p为工作指针，指向当前元素，s 为 p的后继指针L-ne x t=nu ll;头结点摘下，指针域置空。算法中头指针L 始终不变w h i le (p)s=p-ne x t;/保留后继结点的指针p-ne x t=L-ne x t;/逆置L-ne x t=p;p=s;/将 p 指向下个待逆置结点)/算法结束2 7(1)i nt le ng t h l(li nk li s t *L)/本算法计算带头结点的单链表L的长度 li nk li s t *p=L-

9、ne x t;i nt i=0;/p为工作指针，指向当前元素，i表示链表的长度w h i le (p)i+;p=p-ne x t;re t u rn(i);/算法结束(2)i nt le ng t h l(node s a M AXS I Z E )/本算法计算静态链表s中元素的个数。i nt p=s a 0.ne x t,i=0;p为工作指针，指向当前元素，i表示元素的个数，静态链指针等于-1时链表结束w h i le (p!=-1)i+;p=s a p .ne x t;re t u rn(i);/算法结束2 8v oi d u ni on_ i nv e rt(li nk li s t *

10、A,*B,*C)A和B是防个带头结点的递增有序的单链表，本算法将两表合并成/一个带头结点的递减有序单链表C,利用原表空间。li nk li s t *p a=A-ne x t,*p b=B-ne x t,*C=A,*r;p a,p b为工作指针，分别指向A 表和B 表的当前元素，r 为当前逆置元素的后继指针，使逆置元素的表避免断开。算法思想是边合并边逆置，使递增有序的单链表合并为递减有序的单链表。C-ne x t=nu ll;头结点摘下，指针域置分。算法中头指针C 始终不变w h i le (p a&p b)/两表均不空时作i f (p a-dat adat a)/将 A 表中元素合并且逆置

11、r=p a-ne x t;p a-ne x t=C-ne x t;C-ne x t=p a;p a=r;)e ls e r=p b-ne x t;p b-ne x t=C-ne x t;C-ne x t=p b;p b=r;保留后继结点的指针/逆置恢复待逆置结点的指针/将 B 表中元素合并且逆置保留后继结点的指针/逆置恢复待逆置结点的指针/以下w h i le (p a)和 w h i le (p b)语句,只执行一个w h i le (p a)r=p a-ne x t;p a-ne x t=C-ne x t;C-ne x t=p a;p a=r;w h i le (p b)r=p b-ne

12、x t;p b-ne x t=C-ne x t;C-ne x t=p b;p b=r;f re e (B);释放B 表头结点 /算法结束/将 A 表中剩余元素逆置保留后继结点的指针/逆置恢复待逆置结点的指针/将 B 表中剩余元素逆置/保留后继结点的指针/逆置恢复待逆置结点的指针2 9v oi d de le t e p ri or(li nk li s t *L)长 度 大 于 1 的单循环链表，既无头结点，也无头指针，本算法删除*S的前驱结点 li nk li s t *p=s-ne x t,*p re=s;/p 为工作指 针,指向当前元素,/p re 为前驱指针，指向当前元素*p的前驱w

13、h i le (p-ne x t!=s)p re=p;p=p-ne x t;/查找*s 的前驱p re-ne x t=s;f re e(p);/删除元素 /算法结束2 10v oi d one _ t o_ t h re e(1i nk li s t *A,*B,*C)/A 是带工结点的的单链表，其数据元素是字符字母、字符、数字字符、其他字符。本算法将A 表分成/三个带头结点的循环单链表A、B 和 C,分别含有字母、数字和其它符号的同一类字符，利用原表空间。li nk li s t *p=A-ne x t,r;p为工作指针，指向A 表的当前元素，r 为当前元素的后继指针，使表避免断开。算法思想

14、是取出当前元素，根据是字母、数字或其它符号，分别插入相应表中。B=(li nk li s t *)malloc(s i z e of (li nk li s t);申请空间,不判断溢出B-ne x t=nu ll;/准备循环链表的头结点C=(li nk li s t *)malloc(s i z e of (li nk li s t);申请空间,不判断溢出C-ne x t=nu ll;/准备循环链表的头结点w h i le (p)r=p-ne x t;/用以记住后继结点i f (p-dat a=,a&p-dat adat a=,A&p-dat a ne x t=A-ne x t;A-ne x

15、t=p;/将字母字符插入 A 表e ls e i f (p-dat a=,O&p-dat ane x t=B-ne x t;B-ne x t=p;/将数字字符插入 B 表e ls e p-ne x t=C-ne x t;C-ne x t=p;/将其它符号插入 C 表P 二 r;恢复后继结点的指针/w h i le /算法结束2 11v oi d locat e(dli nk li s t *L)/L 是带头结点的按访问频度递减的双向链表，本算法先查找数据x,/查找成功时结点的访问频度域增1,最后将该结点按频度递减插入链表中适当位置。li nk li s t *p=L-ne x t,*q;/p

16、为工作指针，指向L表的当前元素，q为 p的前驱，用于查找插入位置。w h i le (p&p-dat a!=x)p=p-ne x t;/查找值为 x 的结点。i f (!p)re t u rn(不存在值为x的结点”)；e ls e p-f re q+;/令元素值为x的结点的f re q 域 加 1。p-ne x t-p ri r=p-p ri or;/将 p结点从链表上摘下。p-p ri or-ne x t=p-ne x t;q=p-p ri or;/以下查找p结点的插入位置w h i le (q !=L&q-f re q p ri or;p-ne x t=q-ne x t;q-ne x t-

17、p ri or=p;/将 p 结点插入p-p ri or=q;q-ne x t=p；/算法结束第三章栈和队列(参考答案)/从数据结构角度看，栈和队列是操作受限的线性结构，其顺序存储结构/和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。3.1 12 3 42 13 43 2 1 44 312 4 32 14 33 2 4 113 2 42 3 143 4 2 113 4 22 3 4 114 3 22 4 3 1设入栈序列元素数为n,则可能的出栈序列数为C2 nn=(l/n+l)*(2 n!/(n!)2)23.2 证明：由 j p k 说明p,在外之后出栈，即 p,被 P k 压在下

18、面，后进先出。由1以上两条，不可能存在i j next;while(idata);p=p-next;if(n%2!=0)p=p-next;/奇数个结点时跳过中心结点while(p&p-data=pop(s)p=p-next;if(p=null)printf(链表中心对称”)；else printf(链表不是中心对称”)；/算法结束3.4i n t m a t c h ()从键盘读入算术表达式，本算法判断圆括号是否正确配对(i n i t s;初始化栈ss c a n f (%c”,&c h);w h i l e (c h!=#)#是表达式输入结束符号s w i t c h (c h)c a s

19、 e :p u s h(s,c h);b r e a k;c a s e :i f (e m p t y(s)p r i n t f(括号不配对);e x i t(0);)p o p(s);i f (!e m p t y(s)p r i n t f (括号不配对”)；e l s e p r i n t f (括 号 配 对);/算法结束3.5t y p e d e f s t r u c t /两栈共享一向量空间 El e m T y p e v m ;/栈可用空间 0m li n t t o p 2 /栈顶指针t w o s t a c k;i n t p u s h(t w o s t a

20、 c k *s,i n t i,El e m T y p e x)/两栈共享向量空间，i 是 0 或 1,表示两个栈，x是进栈元素，/本算法是入栈操作 i f (a b s(s-t o p 0 -s-t o p l )=l)r e t u r n(0);/栈满e l s e s w i t c h (i)c a s e 0:s-v +(s-t o p)=x;b r e a k;c a s e 1:s-v -(s-t o p)=x;b r e a k;d e f a u l t:p r i n t f (栈编号输入错误);r e t u r n (0);)r e t u r n (1);/入栈成

21、功)/算法结束El e m T y p e p o p(t w o s t a c k *s,i n t i)两栈共享向量空间，i 是 0 或 1,表示两个栈，本算法是退栈操作 El e m T y p e x;i f (i!=0&i!=l)r e t u r n(0);/栈编号错误e l s e s w i t c h (i)c a s e 0:i f (s-t o p 0=-l)r e t u r n(0);栈空e l s e x=s-v s-t o p-;b r e a k;c a s e 1:i f (s-t o p l =m)r e t u r n(0);栈空e l s e x=s-

22、v s-t o p+;b r e a k;d e f a u l t:p r i n t f (栈编号输入错误);r e t u r n(0);)r e t u r n (x);/退栈成功)/算法结束El e m T y p e t o p (t w o s t a c k *s,i n t i)/两栈共享向量空间，i 是 0 或 L 表示两个栈，本算法是取栈顶元素操作 El e m T y p e x;s w i t c h (i)c a s e 0:i f (s-t o p 0=-l)r e t u r n(0);栈空e l s e x=s-v s-t o p ;b r e a k;c a

23、 s e 1:i f (s-t o p l =m)r e t u r n(0);/栈空e l s e x=s-v s-t o p ;b r e a k;d e f a u l t:p r i n t f (栈编号输入错误);r e t u r n(0);)r e t u r n (x);/取栈顶元素成功 /算法结束3.6v o i d A c k e r m a n(i n t m,i n t n)/A c k e r m a n 函数的递归算法 i f (m=0)r e t u r n(n+1);e l s e i f (m!=0&n=0)r e t u r n (A c k e r m a

24、 n (m-l,1);e l s e r e t u r n(A c k e r m a n(m-1,A c k e r m a n(m,n-l)/算法结束3.7(1)l i n k l i s t *i n i t(l i n k l i s t *q)/q是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空 q 二(l i n k l i s t *)m a l l o c(s i z e o f (l i n k l i s t);申请空间，不判断空间溢出q-n e x t=q;r e t u r n (q);/算法结束(2)l i n k l i s t *e n q u e u

25、 e(l i n k l i s t *q,El e m T y p e x)/q 是以带头结点的循环链表表示的队列的尾指针，本算法将元素x入队 s=(l i n k l i s t *)m a l l o c(s i z e o f (l i n k l i s t);申请空间,不判断空间溢出s-n e x t=q-n e x t;/将元素结点s入队列q-n e x t=s;q=s;/修改队尾指针return(q);/算法结束(3)linklist*delqueue(linklist*q)/q是以带头结点的循环链表表示的队列的尾指针，这是出队算法 if(q=q-next)return(nul

26、l);/判断队列是否为空else linklist*s=q-next-next;/s 指向出队元素if(s=q)q=q-next;/若队列中巴一个元素，置空队列else q-next-next=s-next;/修改队头元素指针free(s);/释放出队结点)return(q);/算法结束。算法并未返回出队元素3.8typedef structElemType datam;/循环队列占m 个存储单元int front,rear;/front和 rear为队头元素和队尾元素的指针/约定front指向队头元素的前一位置，rear指向队尾元素sequeue;int queuelength(sequeu

27、e*cq)/cq为循环队列，本算法计算其长度 return(cq-rear-cq-front+m)%m;/算法结束3.9typedef structElemType sequm;/循环队列占m 个存储单元int rear,quelen;/rear指向队尾元素，quelen为元素个数sequeue;(1)int empty(sequeue*cq)/cq为循环队列，本算法判断队列是否为空 return(cq-quelen=O?1:0);/算法结束(2)sequeue*enqueue(sequeue*cq,ElemType x)/cq是如上定义的循环队列，本算法将元素x 入队if(cq-quelen

28、=m)return(0);/队满else cq-rear=(cq-rear+l)%m;/计算插入元素位置cq-sequcq-rear=x;/将元素 x 入队列cq-quelen+;/修改队列长度)return(cq);/算法结束ElemType delqueue(sequeue*cq)/cq是以如上定义的循环队列，本算法是出队算法，且返回出队元素if(cq-quelen=0)return(0);/队空else int front=(cq-rear-cq-quelen+1+m)%m;/出队元素位置cq-quelen-；/修改队列长度return(cq-sequfront);/返回队头元素)/算法

29、结束第四章 串(参考答案)在以下习题解答中，假定使用如下类型定义：#define MAXSIZE 1024t y p e d e f s t r u c t c h a r d a t a M A X S IZ E ;in t cu rlen;cu rlen表示终端结点在向量中的位置 seqstrin g;ty p edef stru ct n o de char data;stru ct n o de*n ex t；lin kstrin g;4.2 in t in dex(strin g s,t)s,t是字符串，本算法求子串t在主串s中的第一次出现，若s串中包含t串，返回其第一个字符在s中的

30、位置，否则返回0 m=len gth(s);n=len gth(t);i=l；w hile(i=m-n+l)if(strcmp(su bstr(s,i,n),t)=O)break;else i+;if(i n ex t;q=Y-n ex t;p re=p;w hile(p&q)ch=p-data;/取X中的字符w hile(q&q-data!=ch)q=q-n ex t;/和 Y 中字符比较if (!q)retu rn (ch);/找到Y中没有的字符else p re=p-n ex t;/上一字符在 Y 中存在,p=p re;取X中下一字符。q=Y-n ex t;/再从Y 的第一个字符开始比较

31、)retu rn (n u ll);X中字符在Y 中均存在/算法结束4.6in t strcmp(seqstrin g*S,seqstrin g*T)$和丁是指向两个顺序串的指针，本算法比较两个串的大小，若 S串大于T串，返 回 1；若 S串等于T串，返回0；否则返回T in t i=0;w hile(s-ch i!=,W&t-ch i!=,0,)if (s-ch i t-ch i)retu rn(1);else if (s-ch i ch i)retu rn(-1);else i+;/比较下一字符if (s-ch i!=,0&t-ch i=0)retu rn(1);else if (s-ch

32、 i=,0&t-ch i!=0)retu rn(-1);else retu rn(0);/算法结束4.7lin kstrin g*in v ert(lin kstrin g*S,lin kstrin g*T)$和丁是用带头结点的结点大小为1 的单链表表示的串，S是主串，T是 模 式 串。本算法是先模式匹配，查找T在 S中的第一次出现。如模式匹/配成功，则将S中的子串(T 串)逆 置。lin kstrin g*p re,*sp,*tp;p re=S;/p re是前驱指针,指向S中与T匹配时，T中的前驱sp=S-n ex t;tp=T-n ex t;/sp 和 tp 分别是S 和 T串上的工作指针

33、w hile(sp&tp)if (sp-data=tp-data)/相等时后移指针 sp=sp-n ex t;tp=tp-n ex t;else/失配时主串回溯到下一个字符，子串再以第一个字符开始 p re=p re-n ex t;sp=p re-n ex t;tp=T-n ex t;if (tp!二 n u ll)retu rn (n u ll);/匹配失败，没有逆置else/以下是T串逆置 tp=p re-n ex t;/tp 是逆置的工作指针，现在指向待逆置的第一个字符p re-n ex t=sp;/将 S中与T串匹配时的前驱指向匹配后的后继w hile(tp!=sp)r=tp-n ex

34、 t;tp-n ex t=p re-n ex t;p re-n ex tz:tp;tp=r)/算法结束第五章 多维数组和广 义 表(参考答案)5.1 A 2 3 3 Aoooo，AQOOI，A0002Aooio,Aooi2A o ioo，Aoioi，A()|02A()iio Aoi ii，AOH2A0200，A020I，AQ2O2A()210,AQ2|I,A0212将第一维的0变 为 1 后，可列出另外1 8 个元素。以行序为主(即行优先)时，先改变右边的下标，从右到左进行。5.2 设各维上下号为5d|,C 2 d2，C 3 d3，每个元素占1 个单元。LOC(aijt)=LOC(aciC2

35、c3)+(i-c 1 )*(d2-C 2+1 )*(dj-C 3+l)+(j-c2)*(d3-C 3+l)+(k-cj)*l推广到n维数组！(下界和上界)为(ci,di),其 中 l=i=n.则：其数据元素的存储位置为：LOC(ajij2.jn)=LOC()+(d2-c2+l)(dn-cn+l)(ji-ci)+(d3-c3+l)(d-cn+l)n。2-。2)+(dn_Cn+l)(jii-I-Cn-l)+(jnd)*l=LOC(3cle2c3)+i(jCi)i=ln其中 a E(dk-C k+l)(K=i=n)k=i+l若从c 开始，c 数组下标从0开始，各维长度为bi(l=i=n)贝 I J：

36、LOC(ajij2.jn)=LOC(a()o o)+(b2*b3*bn*ji+b3*-*bn*+j2-+bn*jn.)4-jn)*ln=LOC(aoo.o)+S a i ji 其 中:a 尸1,尸b/a,K i=n5.3 (1)k=2*i+j(0 =k 3 n-2 )(2)i=(k+l)/3 (0 =k 3 n-2 )j=k-2*i5.4v o id saddlep o in t(in t a m n );/a 是 m 行 n列的二维数组,本算法求所有马鞍点/b 是一维数组,存放一行中可能的马鞍点的列值,k 记相等值个数/c 是一维数组,存放某列可能马鞍点的行值,kk记相等值个数 f o r(

37、i=0;i m;i+)min=a i,0 ;/最小值初始化b 0=0;k=l;1)数组记最小值的列号，k 记最小值的个数f o r(j=l;j n;j+)/找每一行中的最小值i f (a i j m i n)b O=j;m i n=a i j;k=l;/重新确定最小值e l s e i f (a i j=m i n)b k+l=j;k+;/有相等的最小值f o r (jj=O;jj k;k+)/第 i行有k个相等的最小值 j=b jj；m a x=a i jj;k k=O;/a i j是否是马鞍点wh i l e (k k=a i k k)k k+;i f(k k =m)pr i n tf (

38、马鞍点 i=%d,j=%d,a i j=%dw,i,j,a i j);/EN D O F f o r jj /EN D O F f o r i最坏时间复杂度为0(m*(n+n*m).(最坏时所有元素相同，都是马鞍点)解法2:若矩阵中元素值互不相同,则用一维数组r o w记下各行最小值,再用一维数组c o l记下各列最大值，相等者为马鞍点。f o r (i=0;i m;i+)r o w i=a i 0;/最小值初始化f o r (j=l;j n;j+)/找每一行中的最小值i f (a i j r o w i)r o w i=a i j;重新确定最小值)f o r (j=0;j n;j+)c o

39、l j=a 0,j：最大值初始化f o r (i=l;i c o l j)重新确定最大值f o r (i=0;i m;i+)f o r (j=l;j n;j+)i f(r o w i=c o l jj)pr i n tf (马鞍点 i=%d,j=%d,a i j=%d”,i,j,a i j);时间复杂度0(m*n).解法3:设定两个数组：m a x 0.n-l 记各列的最大值所在行号m i n 0.m-1 记各行的最小值所在列号第 j 列的最大值为A m a x j j,第 i 行的最小值是A i m i n i vo i d s a d d l e po i n t(i n t a是 m行

40、n列的二维数组,本算法求所有马鞍点 i n t m a x =0,m i n =0;f o r(i=0;i m;i+)f o r(i=0;i m;i+)f o r (j=0;jA m a x j j)m a x j=i;/重新确定第 j 列最大值的行号i f (A i j A i m i n i)m i n i=j;/重新确定第i 行最小值的列号)f o r (i=0;i next;cb=B-next;while(ca!=A&cb!=B)设p a和 p b 为矩阵A 和 B 想加时的工作指针pa=ca-right;pb=cb-right;if(pa=ca)ca=ca-next;/A 表在该行无

41、非 0 元素；elseif(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-rowrowpre=pt;pt=pt-right;pre-right=pt.riht;该结点从B 表相应行链表中摘下。Pbt=pb;pb=p

42、b-right;/B 表移至下一结点以下是将pbt插入A 表的相应列链表中j=pbt-col;pt=cha|jj;pre=pt;while(pt-down!=chafj&pt-down-rowrow)pre=pt;pt=pt-downpre-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;ptb-right=pt;/end of t6if(pb-colcol)else if

43、(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)(5)head(tail(a,b),(c,d)=(c,d)(6)tail(head(a,b),(c,d)=(b)

44、5.8(1)(2)5.9(1)CB第 6章 树和二叉树(参考答案)6.11(1)根结点a三个结点的二叉树的形态:6.3 设树的结点数是n,则n=n O+n l+n 2+.+n m+设树的分支数为B,有n=B+ln=l n l +2n 2+.+m n m+1由(1)和(2)有：n 0=n 2+2n 3+.+(m-1)n m+16.4k (i 为层数)(2)(n-2)/k+l(3)(n-l)*k+i+l(4)(n-l)%k !=0;其右兄弟的编号 n+16.5 (1)顺序存储结构1 2 3 4 5 6 7 8 9 10 11 12 13 14注：#为空结点ABCD#EF#G#H6.6(1)前序 A

45、B DGCEFH(2)中序 DGB AECHF(3)后序 GDB E1IFCA6.7(1)空二叉树或任何结点均无左子树的非空二叉树(2)空二叉树或任何结点均无右子树的非空二叉树(3)空二叉树或只有根结点的二叉树6.8i n t h e i g h t(b i tr e e b t)/b t是以二叉链表为存储结构的二叉树，本算法求二叉树b t 的高度 i n t b l.b r;/局部变量，分别表示二叉树左、右子树的高度i f (b t=n u l l)r e tu r n(0);e l s e b l=h e i g h t(b t-l c h i l d);b r=h e i g h t(b

46、 t-r c h i l d);r e tu r n(b l b r?b l+1:b r+1);/左右子树高度的大者加1(根)/算法结束6.9vo i d pr e o r d e r(c b t,i n t n,i n t i);/c b t是以完全二叉树形式存储的n个结点的二叉树，i 是数/组下标，初始调用时为1。本算法以非递归形式前序遍历该二叉树 i n t i=l,s 口，to p=0;s 是栈，栈中元素是二叉树结点在c b t中的序号/to p是栈顶指针，栈空时to p=0i f (n =0)pr i n tf(“输入错误”);e x i t(0)：)wh i l e (i 0)wh

47、 i l e(i 0)i=s to p;/退栈,先序访问右子树 /EN D O F wh i l e (i 0)/算法结束/以下是非完全二叉树顺序存储时的递归遍历算法，“虚 结 点 用 *表示v oi d pr e or d e r(b t ,i nt n,i nt i);/b t 是以完全二叉树形式存储的一维数组，n 是数组元素个数。i 是数/组下标，初始调用时为l o i f (i d a t a!=T 2-d a t a)r e t u r n(0);/根结点值不等e l s e r e t u r n(e qu a l(T l-l c h i l d,T 2-l c h i l d)&

48、e qu a l(T l-r c h i l d,T 2-r c h i l d)判左右子树等价/算法结束6.1 1v oi d l e v e l or d e r (b i t r e e h t)：本算法按层次遍历二叉树h t i f (h t!=nu l l)(i ni t qu e u e(q);处始化队列，队列元素为二叉树结点的指针e nqu e u e (q,h t);根结点指针入队列w h i l e (!e mpt y(q)p=d e l qu e u e(q);v i s i t(p);/访问结点i f (p-l c h i l d!=nu l l)e nqu e u e

49、(q,p-l c h i l d);/若左子女非空，则左子女入队列i f (p-r c h i l d!=nu l l)e nqu e u e (q,p-r c h i l d)；若右子女非空，则右子女入队列)/算法结束6.1 2v oi d pr e or d e r (b i t r e e *t);(前序非递归遍历)b i t r e e *s n+l ;/s 是指针数组,数组中元素为二叉树节点的指针t op=0;w h i l e (t!=nu l l|t op!=0)w h i l e (t!=nu l l)v i s i t (*t);s +t op=t;t=t-l c h i l

50、 d i f (t op!=0)t=s t op-;t=t-r c h i l d;)/算法结束v oi d i nor d e r (b i t r e e *t);(中序非递归遍历)b i t r e e *s n+l ;t op=0;w h i l e (t!=nu l l I|t op!=0)w h i l e (t!=nu l l)s +t op=t;t=t-l c h i l d i f (t op!=0)t=s t op-;v i s i t(*t);t=t-r c h i l d;/算法结束v oi d pos t or d e r (b i t r e e *t);(后序非递