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

1、优秀学习资料欢迎下载数据结构课后习题参考答案第一章绪论1.3 (1) o(n) (2)(2)o(n) (3)(3)o(n) (4)(4)o(n1/2)(5)(5)执行程序段的过程中，x,y 值变化如下：循环次数x y 0（初始）91 100 1 92 100 2 93 100 9 100 100 10 101 100 11 91 99 12 92 100 20 101 99 21 91 98 30 101 98 31 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 ,

2、 nlog2n , 2 n ,n! , n n 第二章线性表 ( 参考答案 ) 在以下习题解答中，假定使用如下类型定义：（1）顺序存储结构：#define maxsize 1024 typedef int elemtype;/ 实际上， elemtype 可以是任意类型typedef struct elemtype datamaxsize; int last; / last表示终端结点在向量中的位置sequenlist; （2）链式存储结构（单链表）typedef struct node elemtype data; struct node *next； linklist; （3）链式存储结构

3、（双链表）typedef struct node elemtype data; struct node *prior,*next；dlinklist; （4）静态链表typedef struct elemtype data; int next; 精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 1 页，共 44 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 1 页，共 44 页 - - - - - - - - -优秀学习资料欢迎下载node; node samaxsiz

4、e; 2.1 头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是la，往往简称为“链表 la” 。头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品），其指针域指向头结点。这样在插入和删除中头结点不变。开始结点：即上面所讲第一个元素的结点。2.2 只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。23 void insert(elemtype a,int elenum,elemt

5、ype x) / 向量 a目前有 elenum 个元素， 且递增有序， 本算法将x 插入到向量a中，并保持向量的递增有序。 int i=0,j; while (ielenum & 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; /暂存起

6、点元素值，temp 与向量中元素类型相同 empty=start; /保存空位置下标 next=(start-k+n) %n; / 计算下一右移元素的下标 while (next !=start) aempty=anext;/ 右移 num+; / 右移元素数加1 empty=next; next=(next-k+n) %n; / 计算新右移元素的下标 aempty=temp; / 把一轮右移中最后一个元素放到合适位置 num+; start+; / 起点增 1，若 numn则开始下一轮右移。 / 算法结束算法二算法思想： 先将左面n-k 个元素逆置， 接着将右面k 个元素逆置， 最后再将这n

7、 个元素逆置。void rightrotate(elemtype a,int n,k) / 以向量作存储结构，本算法将向量中的n 个元素循环右移k 位，且只用一个辅助空间。 elemtype temp; for(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 为前驱指针，指向当前元素的前驱

8、s=(linklist *)malloc(sizeof(linklist);/申请空间，不判断溢出s-data=x; while (p & p-datanext; / 查找插入位置 pre-next=s; s-next=p; / 插入元素 / 算法结束26void invert(linklist *l) / 本算法将带头结点的单链表l 逆置。/ 算法思想是先将头结点从表上摘下，然后从第一个元素结点开始，依次前插入以l 为头结点的链表中。 linklist *p=l-next,*s; / p为工作指针，指向当前元素，s 为 p 的后继指针l-next=null;/头结点摘下，指针域置空。

9、算法中头指针l 始终不变 while (p) s=p-next; / 保留后继结点的指针 p-next=l-next; / 逆置l-next=p; p=s; / 将 p 指向下个待逆置结点 / 算法结束27(1) int length1(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 中元素的个数

10、。 int p=sa0.next, i=0; / p为工作指针，指向当前元素，i 表示元素的个数，静态链指针等于-1 时链表结束 while (p！=-1) i+; p=sap.next; return(i); / 算法结束28void union_invert(linklist *a,*b,*c) / a和 b 是两个带头结点的递增有序的单链表，本算法将两表合并成/ 一个带头结点的递减有序单链表c，利用原表空间。 linklist *pa=a-next,*pb=b-next,*c=a,*r; 精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 3 页，

11、共 44 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 3 页，共 44 页 - - - - - - - - -优秀学习资料欢迎下载/ pa,pb 为工作指针，分别指向a表和 b表的当前元素， r 为当前逆置/ 元素的后继指针 , 使逆置元素的表避免断开。/ 算法思想是边合并边逆置， 使递增有序的单链表合并为递减有序的单链表。c-next=null;/头结点摘下，指针域置空。算法中头指针c 始终不变 while (pa & pb) / 两表均不空时作 if (pa-datadata) / 将 a表中元素

12、合并且逆置 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; / 恢复待逆置

13、结点的指针 while (pb) / 将 b表中剩余元素逆置 r=pb-next; / 保留后继结点的指针 pb-next=c-next; / 逆置c-next=pb; pb=r; / 恢复待逆置结点的指针 free(b);/释放 b表头结点 / 算法结束29 void deleteprior(linklist *l) / 长度大于 1 的单循环链表，既无头结点，也无头指针，本算法删精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 4 页，共 44 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - -

14、 - - - - - 第 4 页，共 44 页 - - - - - - - - -优秀学习资料欢迎下载除*s 的前驱结点 linklist *p=s-next,*pre=s; / p 为工作指针，指向当前元素，/ pre为前驱指针，指向当前元素*p 的前驱 while (p-next!=s) pre=p; p=p-next; / 查找*s 的前驱 pre-next=s; free(p); / 删除元素 / 算法结束210void one_to_three(linklist *a,*b,*c) / a是带头结点的的单链表，其数据元素是字符字母、字符、数字字符、其他字符。本算法/ 将 a表分成/

15、三个带头结点的循环单链表a、b和 c，分别含有字母、数字和其它符号的同一类字符，利用原表空间。 linklist *p=a-next,r; / p为工作指针，指向a表的当前元素，r 为当前元素的后继指针, 使表避免断开。/ 算法思想是取出当前元素，根据是字母、数字或其它符号，分别插入相应表中。b=(linklist *)malloc(sizeof(linklist);/申请空间，不判断溢出 b-next=null; / 准备循环链表的头结点c=(linklist *)malloc(sizeof(linklist);/申请空间，不判断溢出 c-next=null; / 准备循环链表的头结点whi

16、le(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-next=c-next; c-next=p;/ 将其它符号插入c 表p=r; / 恢复后继结点的指针 /while / 算法结束211void locate(dlinklist *l) / l是带头结点的按访问频度递减的双向链表，本算法先查找数据x

17、, / 查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。 linklist *p=l-next,*q; /p为工作指针，指向l 表的当前元素，q 为 p 的前驱，用于查找插入位置。 while (p & p-data !=x) p=p-next; / 查找值为x 的结点。if (!p) return (“不存在值为x 的结点” ); else p-freq+; / 令元素值为x 的结点的freq域加 1 。 p-next-prir=p-prior; / 将 p 结点从链表上摘下。 p-prior-next=p-next; q=p-prior; / 以下查找 p

18、 结点的插入位置 while (q !=l & q-freqprior; p-next=q-next; q-next-prior=p;/ 将 p 结点插入 p-prior=q; q-next=p； / 算法结束第三章栈和队列 ( 参考答案 ) 精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 5 页，共 44 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 5 页，共 44 页 - - - - - - - - -优秀学习资料欢迎下载/ 从数据结构角度看，栈和队列是

19、操作受限的线性结构，其顺序存储结构/ 和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。3.1 1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 1 1 2 4 3 2 1 4 3 3 2 4 1 1 3 2 4 2 3 1 4 3 4 2 1 1 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被 p

20、k压在下面，后进先出。由以上两条， 不可能存在ijk使 pjpknext; 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.4 int match() / 从键盘读入算术表达式，本算法判断圆括号是否正确配对（init s;/初始化栈 s scanf( “%c ”,&ch);while (ch!=#) /#是

21、表达式输入结束符号switch (ch) case ( : push(s,ch); break; case ) : if (empty(s) printf(“括号不配对” ); exit(0); pop(s); if (!empty(s) printf(“括号不配对” ); else printf(“括号配对” ); / 算法结束3.5 typedef struct / 两栈共享一向量空间 elemtype vm; / 栈可用空间0m-1 int top2 / 栈顶指针twostack; int push(twostack *s,int i, elemtype x) / 两栈共享向量空间,i是

22、 0 或 1，表示两个栈，x 是进栈元素，/ 本算法是入栈操作 if (abs(s-top0 - s-top1)=1) return(0);/ 栈满 else switch (i) case 0: s-v+(s-top)=x; break; case 1: s-v-(s-top)=x; break; 精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 6 页，共 44 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 6 页，共 44 页 - - - - - - - - -优

23、秀学习资料欢迎下载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; case 1: if(s-top1=m) return(0);/栈空

24、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) return(0);/栈空else x=s-vs-top; break; d

25、efault: printf(“栈编号输入错误” );return(0); return(x); / 取栈顶元素成功 / 算法结束36 void 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是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空

26、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; / 修改队尾指针精品学习资料 可选择p d f - - - - - - - - - - - -

27、 - - 第 7 页，共 44 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 7 页，共 44 页 - - - - - - - - -优秀学习资料欢迎下载return (q); / 算法结束(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;

28、 / 若队列中只一个元素，置空队列else q-next-next=s-next;/ 修改队头元素指针free (s); / 释放出队结点 return (q); / 算法结束。算法并未返回出队元素3.8 typedef struct elemtype datam;/ 循环队列占m个存储单元int front,rear; / front和 rear 为队头元素和队尾元素的指针/ 约定 front指向队头元素的前一位置，rear指向队尾元素sequeue; int queuelength(sequeue *cq) / cq为循环队列，本算法计算其长度 return (cq-rear - cq-f

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

30、/ 队满else cq-rear=(cq-rear+1) % 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-seq

31、ufront); / 返回队头元素 / 算法结束第四章串 ( 参考答案 ) 在以下习题解答中，假定使用如下类型定义：#define maxsize 1024 精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 8 页，共 44 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 8 页，共 44 页 - - - - - - - - -优秀学习资料欢迎下载typedef struct char datamaxsize; int curlen; / curlen表示终端结点在向量中

32、的位置seqstring; typedef struct node char data; struct node *next ；linkstring; 4.2 int index(string s,t) /s,t 是字符串，本算法求子串t 在主串 s 中的第一次出现，若s 串中包含t 串，返回其/第一个字符在s 中的位置，否则返回0 m=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 &

33、; q) ch=p-data; / 取 x中的字符 while (q & q-data!=ch) q=q-next; / 和 y中字符比较 if (!q) return(ch); / 找到 y中没有的字符else pre=p-next; / 上一字符在y中存在， p=pre; / 取 x中下一字符。精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 9 页，共 44 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 9 页，共 44 页 - - - - - - - -

34、 -优秀学习资料欢迎下载 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 int i=0; while (s-chi!=0 & t - chi!=0) if (s-chit-chi) return(1); else if (s-chichi) return(-1); else i+; / 比较下一字

35、符 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 是/ 模式串。本算法是先模式匹配，查找t 在 s中的第一次出现。如模式匹/ 配成功，则将s中的子串（ t 串）逆置。linkstring *pre,*sp, *tp; pre=s; / pre是前驱指针

36、，指向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!=null) return (null); / 匹配失败，没有逆置 else / 以下是 t 串逆置 tp=pre-next; / tp是逆置的工作指针，现在指向待

37、逆置的第一个字符pre-next=sp; / 将 s中与 t串匹配时的前驱指向匹配后的后继while (tp!=sp) r=tp-next; tp-next=pre-next; pre-next=tp; tp=r / 算法结束第五章多维数组和广义表（参考答案）5.1 a2323 a0000, a0001, a0002a0010, a0011, a0012a0100, a0101, a0102a0110, a0111, a0112a0200, a0201, a0202精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 10 页，共 44 页 - - - -

38、 - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 10 页，共 44 页 - - - - - - - - -优秀学习资料欢迎下载a0210, a0211, a0212将第一维的0 变为 1 后，可列出另外18 个元素。以行序为主（即行优先）时，先改变右边的下标，从右到左进行。5.2 设各维上下号为c1d1，c2d2，c3 d3，每个元素占l 个单元。loc(aijk)=loc(ac1c2c3)+(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3)*l 推广到n 维数组！ （下界和上界）

39、为（ci，di） ，其中1=i=n. 则：其数据元素的存储位置为：loc（aj1j2 .jn）=loc（ac1c2cn）+（d2-c2+1） （dn-cn+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 （aj1j2 jn）=loc(a000)+(b2* b3* * bn*j1+ b3* * bn*+ j

40、2+ 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)/3 ( 0=k3n-2 ) j=k-2*i 5.4 void saddlepoint(int amn); / a是 m行 n 列的二维数组 , 本算法求所有马鞍点 / b是一维数组 , 存放一行中可能的马鞍点的列值,k 记相等值个数 / c是一维数组 , 存放某列可能马鞍点的行值,kk 记相等值个数 for(i=0;im;i+) min=ai,0; / 最小值初始化 b0=0; k=1; / b数组记

41、最小值的列号，k 记最小值的个数 for(j=1;jn;j+) / 找每一行中的最小值if (aijmin) b0=j; min=aij;k=1;/ 重新确定最小值 else if (aij=min) bk+1=j; k+; / 有相等的最小值 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 最坏时间复

42、杂度为o(m*(n+n*m). (最坏时所有元素相同，都是马鞍点) 解法 2: 若矩阵中元素值互不相同, 则用一维数组row 记下各行最小值， 再用一维数组col记下各列最大值，相等者为马鞍点。for (i=0;im;i+) rowi=ai0; / 最小值初始化精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 11 页，共 44 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 11 页，共 44 页 - - - - - - - - -优秀学习资料欢迎下载 for (j=1

43、;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 记各行的最小值所在列号第 j 列的最大值为amaxjj,第 i

44、 行的最小值是aimini void 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

45、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

46、=pt-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 精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 13 页，共 44 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 13 页，共 44 页 - - -

47、 - - - - - -优秀学习资料欢迎下载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; ptb-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;p

48、a=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) 5.8 (1) (2) 5.9(1) 精品学习资料 可选择p d f - - - - - - - - - -

49、- - - - 第 14 页，共 44 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 14 页，共 44 页 - - - - - - - - -优秀学习资料欢迎下载第 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+1 n=1n1+2n2+ +mnm+1 (2) 由（ 1）和（ 2）有：精品学习资料 可选择p d

50、f - - - - - - - - - - - - - - 第 15 页，共 44 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 15 页，共 44 页 - - - - - - - - -优秀学习资料欢迎下载n0=n2+2n3+ +(m-1)nm+1 6.4 (1) ki-1 (i为层数 ) (2) (n-2)/k+1 (3) (n-1)*k+i+1 (4) (n-1)%k !=0; 其右兄弟的编号 n+1 6.5（1）顺序存储结构1 2 3 4 5 6 7 8 9 10 11 12 13 14 a b c d

51、 # e f # g # # # # h 注： #为空结点6.6 (1) 前序 abdgcefh (2) 中序 dgbaechf (3) 后序 gdbehfca 6.7 (1) 空二叉树或任何结点均无左子树的非空二叉树(2) 空二叉树或任何结点均无右子树的非空二叉树(3) 空二叉树或只有根结点的二叉树6.8 int height(bitree bt) / bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt 的高度 int bl,br; / 局部变量，分别表示二叉树左、右子树的高度 if (bt=null) return(0); else bl=height(bt-lchild); br=h

52、eight(bt-rchild); return(blbr? bl+1: br+1); / 左右子树高度的大者加1（根） / 算法结束6.9 void preorder(cbt,int n,int i); / cbt是以完全二叉树形式存储的n 个结点的二叉树，i 是数a b c d h f e g 精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 16 页，共 44 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 16 页，共 44 页 - - - - - - - - -

53、优秀学习资料欢迎下载/ 组下标，初始调用时为1。本算法以非递归形式前序遍历该二叉树 int i=1,s,top=0; / s是栈，栈中元素是二叉树结点在cbt 中的序号 / top是栈顶指针，栈空时top=0 if (n=0) printf(“输入错误”);exit（0） ； while (i0) while(i=n) visit(cbti); / 访问根结点 if (2*i+10) i=stop-; / 退栈，先序访问右子树 / end of while (i0) / 算法结束/ 以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用* 表示void preorder(bt,int n,i

54、nt i); / bt是以完全二叉树形式存储的一维数组，n 是数组元素个数。i 是数/ 组下标，初始调用时为1。 if (idata!=t2-data) return(0);/ 根结点值不等else return(equal(t1-lchild,t2-lchild)&equal(t1-rchild,t2-rchild) / 判左右子树等价/ 算法结束611 void levelorder (bitree ht); 本算法按层次遍历二叉树ht if (ht!=null) initqueue(q); 处始化队列，队列元素为二叉树结点的指针 enqueue(q,ht); 根结点指针入队列 w

55、hile (!empty(q) p=delqueue(q); visit(p); / 访问结点 if (p-lchild!=null) enqueue (q,p-lchild); 精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 17 页，共 44 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 17 页，共 44 页 - - - - - - - - -优秀学习资料欢迎下载 /若左子女非空，则左子女入队列 if (p-rchild!=null) enqueue (q,p-

56、rchild)； /若右子女非空，则右子女入队列 / 算法结束612 void 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 (t!=null |

57、 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(stop

58、-.t-data:3); if (top) stop.tag=1; t=stop.t-rchild ; / 算法结束6.13 bitree *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); 精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 18 页，

59、共 44 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 18 页，共 44 页 - - - - - - - - -优秀学习资料欢迎下载 else find=(dissect(&(*t)-lchild),x); / 在左子树中查找并拆开 / 若在左子树中未找到，就到右子树中查找并拆开 if (!find) find=(dissect(&(*t)-rchild),x); return(find); else return(null); / 空二叉树 / 算法结束6.14 int search(bit

60、ree t,elemtype x) / 设二叉树t 中，值为x 的结点至多一个，本算法打印x 的所有祖先/ 算法思想是，借助后序非递归遍历，用栈装遍历过程的结点，当查到/ 值为 x 的结点时，栈中元素都是x 的祖先 typedef struct bitree p; int tag; snode; snode s; int top=0; while (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); else while (top0 & stop.tag=1) top-;/退出右子树已访问的结点 if (top0) / 置访问标志1，访