2023年《数据结构—用C语言描述》课后习题超详细解析答案.pdf

优秀学习资料 欢迎下载 数据结构课后习题参考答案 第一章 绪论 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 ,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）链式存储结构（双链表）typedef struct node ElemType data;struct node *prior,*next；dlinklist;（4）静态链表 typedef struct ElemType data;int next;优秀学习资料 欢迎下载 node;node saMAXSIZE;2.1 头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是 la，往往简称为“链表 la”。头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品），其指针域指向头结点。这样在插入和删除中头结点不变。开始结点：即上面所讲第一个元素的结点。2.2 只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。23 void insert(ElemType A,int elenum,ElemType 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;/暂存起点元素值，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 个元素逆置。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 为前驱指针，指向当前元素的前驱 s=(linklist*)malloc(sizeof(linklist);/申请空间，不判断溢出 s-data=x;while(p&p-datanext;/查找插入位置 pre-next=s;s-next=p;/插入元素 /算法结束 26 void 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(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);/算法结束 28 void union_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表中元素合并且逆置 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;/恢复待逆置结点的指针 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-next;/查找*s 的前驱 pre-next=s;free(p);/删除元素 /算法结束 210 void one_to_three(linklist*A,*B,*C)/A是带头结点的的单链表，其数据元素是字符字母、字符、数字字符、其他字符。本算法/将 A表分成 /三个带头结点的循环单链表 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;/准备循环链表的头结点 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-next=C-next;C-next=p;/将其它符号插入 C 表 p=r;/恢复后继结点的指针 /while /算法结束 211 void 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 的结点”);else 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 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被 pk 压在下面，后进先出。由以上两条，不可能存在 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!=#)/#是表达式输入结束符号 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 是 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;型链式存储结构单链表链式存储结构双链表静态链表表示终端结点在向表的名字往往用头指针来标识如链表的头指针是往往简称为链表头结点产品其指针域指向头结点这样在插入和删除中头结点不变开始结点即上优秀学习资料 欢迎下载 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);/栈空 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;default: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是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空 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);/算法结束 (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 struct ElemType datam;/循环队列占 m个存储单元 int front,rear;/front和 rear 为队头元素和队尾元素的指针 /约定 front指向队头元素的前一位置，rear 指向队尾元素 sequeue;int queuelength(sequeue*cq)/cq为循环队列，本算法计算其长度 return(cq-rear-cq-front+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);/队满 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-sequfront);/返回队头元素 /算法结束 第四章 串(参考答案)在以下习题解答中，假定使用如下类型定义：#define MAXSIZE 1024 型链式存储结构单链表链式存储结构双链表静态链表表示终端结点在向表的名字往往用头指针来标识如链表的头指针是往往简称为链表头结点产品其指针域指向头结点这样在插入和删除中头结点不变开始结点即上优秀学习资料 欢迎下载 typedef struct char dataMAXSIZE;int curlen;/curlen表示终端结点在向量中的位置 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&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中下一字符。型链式存储结构单链表链式存储结构双链表静态链表表示终端结点在向表的名字往往用头指针来标识如链表的头指针是往往简称为链表头结点产品其指针域指向头结点这样在插入和删除中头结点不变开始结点即上优秀学习资料 欢迎下载 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+;/比较下一字符 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是前驱指针，指向 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是逆置的工作指针，现在指向待逆置的第一个字符 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 ,A0002 A0010 ,A0011 ,A0012 A0100 ,A0101 ,A0102 A0110 ,A0111 ,A0112 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+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=n 5.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数组记最小值的列号，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 最坏时间复杂度为 O(m*(n+n*m).(最坏时所有元素相同，都是马鞍点)解法2:若矩阵中元素值互不相同,则用一维数组row 记下各行最小值，再用一维数组col记下各列最大值，相等者为马鞍点。for(i=0;im;i+)rowi=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 记各行的最小值所在列号 第 j 列的最大值为 Amaxjj,第 i 行的最小值是 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-right;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-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;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;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)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+1 n=1n1+2n2+mnm+1 (2)由（1）和（2）有：型链式存储结构单链表链式存储结构双链表静态链表表示终端结点在向表的名字往往用头指针来标识如链表的头指针是往往简称为链表头结点产品其指针域指向头结点这样在插入和删除中头结点不变开始结点即上优秀学习资料 欢迎下载 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#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=height(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 型链式存储结构单链表链式存储结构双链表静态链表表示终端结点在向表的名字往往用头指针来标识如链表的头指针是往往简称为链表头结点产品其指针域指向头结点这样在插入和删除中头结点不变开始结点即上优秀学习资料 欢迎下载/组下标，初始调用时为 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,int 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);根结点指针入队列 while(!empty(q)p=delqueue(q);visit(p);/访问结点 if(p-lchild!=null)enqueue(q,p-lchild);型链式存储结构单链表链式存储结构双链表静态链表表示终端结点在向表的名字往往用头指针来标识如链表的头指针是往往简称为链表头结点产品其指针域指向头结点这样在插入和删除中头结点不变开始结点即上优秀学习资料 欢迎下载 /若左子女非空，则左子女入队列 if(p-rchild!=null)enqueue(q,p-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!=