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

'数据结构课后习题参考答案第一章绪论1.3(1)O(n)(2)(2)         O(n)(3)(3)         O(n)(4)(4)         O(n1/2)(5)(5)         执行程序段的过程中，x,y值变化如下：循环次数xy0（初始）91100192100293100………………9100100101011001191991292100………………2010199219198………………3010198319197到y=0时，要执行10*100次，可记为O（10*y）=O（n）1.52100,(2/3)n,log2n,n1/2,n3/2,(3/2)n,nlog2n,2n,n!,nn第二章线性表(参考答案)在以下习题解答中，假定使用如下类型定义：（1）顺序存储结构：#defineMAXSIZE1024typedefintElemType;//实际上，ElemType可以是任意类型typedefstruct{ElemTypedata[MAXSIZE];intlast;//last表示终端结点在向量中的位置}sequenlist;（2）链式存储结构（单链表）typedefstructnode{ElemTypedata;structnode*next；}linklist;（3）链式存储结构（双链表）typedefstructnode{ElemTypedata;structnode*prior,*next；}dlinklist;（4）静态链表typedefstruct{ElemTypedata;intnext; }node;nodesa[MAXSIZE];2.1头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是la，往往简称为“链表la”。头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品），其指针域指向头结点。这样在插入和删除中头结点不变。开始结点：即上面所讲第一个元素的结点。2.2只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。2·3voidinsert(ElemTypeA[],intelenum,ElemTypex)//向量A目前有elenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的递增有序。{inti=0,j;while(i=i;j--)A[j+1]=A[j];//向后移动元素A[i]=x;//插入元素}//算法结束2·4voidrightrotate(ElemTypeA[],intn,k)//以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。{intnum=0;//计数，最终应等于nintstart=0;//记录开始位置（下标）while(numnext,*pre=L，*s;//p为工作指针，指向当前元素，pre为前驱指针，指向当前元素的前驱s=(linklist*)malloc(sizeof(linklist));//申请空间，不判断溢出s->data=x;while(p&&p->data<=x){pre=p;p=p->next;}//查找插入位置pre->next=s;s->next=p;//插入元素}//算法结束2·6voidinvert(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指向下个待逆置结点}}//算法结束2·7(1)intlength1(linklist*L)//本算法计算带头结点的单链表L的长度{linklist*p=L->next;inti=0;//p为工作指针，指向当前元素，i表示链表的长度while(p){i++;p=p->next;}return(i);}//算法结束(2)intlength1(nodesa[MAXSIZE])//本算法计算静态链表s中元素的个数。{intp=sa[0].next,i=0;//p为工作指针，指向当前元素，i表示元素的个数，静态链指针等于-1时链表结束while(p！=-1){i++;p=sa[p].next;}return(i);}//算法结束2·8voidunion_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->data<=pb->data)//将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表头结点}//算法结束2·9voiddeleteprior(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);//删除元素}//算法结束2·10voidone_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->data<=’z’||p->data>=’A’&&p->data<=’Z’){p->next=A->next;A->next=p;}//将字母字符插入A表elseif(p->data>=’0’&&p->data<=’9’){p->next=B->next;B->next=p;}//将数字字符插入B表else{p->next=C->next;C->next=p;}//将其它符号插入C表p=r;//恢复后继结点的指针}//while}//算法结束2·11voidlocate(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.112342134321443211243214332411324231434211342234114322431设入栈序列元素数为n，则可能的出栈序列数为C2nn=(1/n+1)*(2n!/(n!)2)3.2证明：由jpk说明pj在pk之后出栈，即pj被pk压在下面，后进先出。由以上两条，不可能存在inext;while(i<=n/2)//前一半字符进栈{push(s,p->data);p=p->next;}if(n%2!==0)p=p->next;//奇数个结点时跳过中心结点while(p&&p->data==pop(s))p=p->next;if(p==null)printf(“链表中心对称”)；elseprintf(“链表不是中心对称”)；}//算法结束3.4intmatch()//从键盘读入算术表达式，本算法判断圆括号是否正确配对（inits;//初始化栈sscanf(“%c”,&ch);while(ch!=’#’)//’#’是表达式输入结束符号switch(ch){case’(’:push(s,ch);break;case’)’:if(empty(s)){printf(“括号不配对”);exit(0);}pop(s);}if(!empty(s))printf(“括号不配对”);elseprintf(“括号配对”);}//算法结束3.5typedefstruct//两栈共享一向量空间{ElemTypev[m];//栈可用空间0—m-1inttop[2]//栈顶指针}twostack;intpush(twostack*s,inti,ElemTypex)//两栈共享向量空间,i是0或1，表示两个栈，x是进栈元素，//本算法是入栈操作{if(abs(s->top[0]-s->top[1])==1)return(0);//栈满else{switch(i){case0:s->v[++(s->top)]=x;break;case1:s->v[--(s->top)]=x;break; default:printf(“栈编号输入错误”);return(0);}return(1);//入栈成功}}//算法结束ElemTypepop(twostack*s,inti)//两栈共享向量空间,i是0或1，表示两个栈，本算法是退栈操作{ElemTypex;if(i!=0&&i!=1)return(0);//栈编号错误else{switch(i){case0:if(s->top[0]==-1)return(0);//栈空elsex=s->v[s->top--];break;case1:if(s->top[1]==m)return(0);//栈空elsex=s->v[s->top++];break;default:printf(“栈编号输入错误”);return(0);}return(x);//退栈成功}}//算法结束ElemTypetop(twostack*s,inti)//两栈共享向量空间,i是0或1，表示两个栈，本算法是取栈顶元素操作{ElemTypex;switch(i){case0:if(s->top[0]==-1)return(0);//栈空elsex=s->v[s->top];break;case1:if(s->top[1]==m)return(0);//栈空elsex=s->v[s->top];break;default:printf(“栈编号输入错误”);return(0);}return(x);//取栈顶元素成功}//算法结束3．6voidAckerman(intm,intn)//Ackerman函数的递归算法{if(m==0)return(n+1);elseif(m!=0&&n==0)return(Ackerman(m-1,1);elsereturn(Ackerman(m-1,Ackerman(m,n-1))}//算法结束3．7(1)linklist*init(linklist*q)//q是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空{q=(linklist*)malloc(sizeof(linklist));//申请空间，不判断空间溢出q->next=q;return(q);}//算法结束(2)linklist*enqueue(linklist*q，ElemTypex)//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;//若队列中只一个元素，置空队列elseq->next->next=s->next;//修改队头元素指针free(s);//释放出队结点}return(q);}//算法结束。算法并未返回出队元素3.8typedefstruct{ElemTypedata[m];//循环队列占m个存储单元intfront,rear;//front和rear为队头元素和队尾元素的指针//约定front指向队头元素的前一位置，rear指向队尾元素}sequeue;intqueuelength(sequeue*cq)//cq为循环队列，本算法计算其长度{return(cq->rear-cq->front+m)%m;}//算法结束3.9typedefstruct{ElemTypesequ[m];//循环队列占m个存储单元intrear,quelen;//rear指向队尾元素,quelen为元素个数}sequeue;(1)intempty(sequeue*cq)//cq为循环队列，本算法判断队列是否为空{return(cq->quelen==0?1:0);}//算法结束(2)sequeue*enqueue(sequeue*cq，ElemTypex)//cq是如上定义的循环队列，本算法将元素x入队{if(cq->quelen==m)return(0);//队满else{cq->rear=(cq->rear+1)%m;//计算插入元素位置cq->sequ[cq->rear]=x;//将元素x入队列cq->quelen++;//修改队列长度}return(cq);}//算法结束ElemTypedelqueue(sequeue*cq)//cq是以如上定义的循环队列，本算法是出队算法，且返回出队元素{if(cq->quelen==0)return(0);//队空else{intfront=(cq->rear-cq->quelen+1+m)%m;//出队元素位置cq->quelen--;//修改队列长度return(cq->sequ[front]);//返回队头元素}}//算法结束第四章串(参考答案)在以下习题解答中，假定使用如下类型定义：#defineMAXSIZE1024 typedefstruct{chardata[MAXSIZE];intcurlen;//curlen表示终端结点在向量中的位置}seqstring; typedefstructnode{chardata;structnode*next；}linkstring;4.2intindex(strings,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;elsei++;if(i<=m-n+1)return(i);//模式匹配成功elsereturn(0);//s串中无子串t}//算法index结束4.3设A=””,B=”mule”,C=”old”,D=”my”则：（a）（a）      strcat（A,B）=”mule”（b）（b）      strcat(B,A)=”mule”（c）（c）      strcat(strcat(D,C),B)=”myoldmule”（d）（d）      substr(B,3,2)=”le”（e）（e）      substr(C,1,0)=””（f）（f）       strlen(A)=0（g）（g）      strlen(D)=2（h）（h）      index(B,D)=0（i）（i）        index(C,”d”)=3（j）（j）        insert(D,2,C)=”moldy”（k）（k）      insert(B,1,A)=”mule”（l）（l）        delete(B,2,2)=”me”（m）（m）    delete(B,2,0)=”mule”（n）（n）      replace(C,2,2,”k”)=”ok”4.4将S=“（xyz）*”转为T=“（x+z）*y”S=concat(S,substr(S,3,1))//”(xyz)*y”S=replace(S,3,1,”+”)//”(x+z)*y”4.5charsearch(linkstring*X,linkstring*Y)//X和Y是用带头结点的结点大小为1的单链表表示的串，本算法查找X中第一个不在Y中出现的字符。算法思想是先从X中取出一个字符，到Y中去查找，如找到，则在X中取下一字符，重复以上过程；若没找到，则该字符为所求 {linkstring*p,*q,*pre;//p,q为工作指针，pre控制循环p=X->next;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.6intstrcmp(seqstring*S,seqstring*T)//S和T是指向两个顺序串的指针，本算法比较两个串的大小，若S串大于T串，返回1；若S串等于T串，返回0；否则返回-1{inti=0;while(s->ch[i]!=’’&&t->ch[i]!=’’)if(s->ch[i]>t->ch[i])return(1);elseif(s->ch[i]ch[i])return(-1);elsei++;//比较下一字符if(s->ch[i]!=’’&&t->ch[i]==0)return(1);elseif(s->ch[i]==’’&&t->ch[i]!=0)return(-1);elsereturn(0);}//算法结束4.7linkstring*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.1A[2][3][2][3]A0000,A0001,A0002A0010,A0011,A0012A0100,A0101,A0102A0110,A0111,A0112A0200,A0201,A0202 A0210,A0211,A0212将第一维的0变为1后，可列出另外18个元素。以行序为主（即行优先）时，先改变右边的下标，从右到左进行。5.2设各维上下号为c1…d1，c2…d2，c3…d3，每个元素占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（ac1c2…cn）+[（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=1n其中αi∏（dk-ck+1）（1<=i<=n）k=i+1若从c开始，c数组下标从0开始，各维长度为bi（1<=i<=n）则：LOC（aj1j2…jn）=LOC(a00…0)+(b2*b3*…*bn*j1+b3*…*bn*+j2…+bn*jn-1+jn)*ln=LOC(a00…0)+∑αiji其中：αi=l，αi-1=bi*αi，1=a[i][kk])kk++;if(kk>=m)printf(“马鞍点i=%d,j=%d,a[i][j]=%d”,i,j,a[i][j]);}//ENDOFforjj}//ENDOFfori最坏时间复杂度为O(m*(n+n*m)).(最坏时所有元素相同，都是马鞍点)解法2:若矩阵中元素值互不相同,则用一维数组row记下各行最小值，再用一维数组col记下各列最大值，相等者为马鞍点。for(i=0;icol[j])col[j]=a[i][j];//重新确定最大值}for(i=0;iA[max[j]][j])max[j]=i;//重新确定第j列最大值的行号if(A[i][j]next;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元素；elseif(pb==cb)cb=cb->next//B表在该行无非0元素；elseif(pb->colcol)//B的非0元素插入A中；{j=pb->col;pt=chb[j];pre=pt//取到表头指针；while(pt->down_colcol){pre=pt;pt=pt->down;}pre->down=pt->down;//该结点从B表相应列摘下i=pb->right;pt=chb[i];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=cha[j];pre=pt;while(pt->down!=cha[j]&&pt->down->rowrow){pre=pt;pt=pt->down} pre->down=pbt;pbt->down=pt;//以下是将pbt插入A表相应行链表中i=pbt->right;pt=cha[i];pre=pt;while(pt->right!=cha[i]&&pt->right-colcol){pre=pt;pt=pt->right;}pre->right=ptb;ptb->right=pt;}//endof“if(pb->colcol)elseif(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)根结点a6.2三个结点的树的形态：三个结点的二叉树的形态：（2）（3）（1）（1）（2）（4）（5）6．3设树的结点数是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)%k!=0;其右兄弟的编号n+16.5（1）顺序存储结构1234567891011121314ABCD#EF#G####H注：#为空结点ACB^^E^F^^D^H^^G^6.6(1)前序ABDGCEFH(2)中序DGBAECHF(3)后序GDBEHFCA6.7(1)空二叉树或任何结点均无左子树的非空二叉树(2)空二叉树或任何结点均无右子树的非空二叉树(3)空二叉树或只有根结点的二叉树6.8intheight(bitreebt)//bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度{intbl,br;//局部变量，分别表示二叉树左、右子树的高度if(bt==null)return(0);else{bl=height(bt->lchild);br=height(bt->rchild);return(bl>br?bl+1:br+1);//左右子树高度的大者加1（根）}}//算法结束6.9voidpreorder(cbt[],intn,inti);//cbt是以完全二叉树形式存储的n个结点的二叉树，i是数 //组下标，初始调用时为1。本算法以非递归形式前序遍历该二叉树{inti=1,s[],top=0;//s是栈，栈中元素是二叉树结点在cbt中的序号//top是栈顶指针，栈空时top=0if(n<=0){printf(“输入错误”);exit（0）；}while(i<=n||top>0){while(i<=n){visit(cbt[i]);//访问根结点if(2*i+1<=n)s[++top]=2*i+1;//若右子树非空，其编号进栈i=2*i;//先序访问左子树}if(top>0)i=s[top--];//退栈，先序访问右子树}//ENDOFwhile(i<=n||top>0)}//算法结束//以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示voidpreorder(bt[],intn,inti);//bt是以完全二叉树形式存储的一维数组，n是数组元素个数。i是数//组下标，初始调用时为1。{if(i<=n&&bt[i]!=’*’){visit(bt[i]);preorder(bt,n,2*i);preorder(bt,n,2*i+1);}//算法结束6.10intequal(bitreeT1,bitreeT2);//T1和T2是两棵二叉树，本算法判断T1和T2是否等价//T1和T2都是空二叉树则等价//T1和T2只有一棵为空，另一棵非空，则不等价//T1和T2均非空，且根结点值相等，则比较其左、右子树{if(T1==null&&T2==null)return(1);//同为空二叉树elseif(T1==null||T2==null)return(0);//只有一棵为空elseif(T1->data!=T2->data)return(0);//根结点值不等elsereturn(equal(T1->lchild,T2->lchild)&&equal(T1->rchild,T2->rchild))//判左右子树等价}//算法结束6．11voidlevelorder(bitreeht);{本算法按层次遍历二叉树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)；//若右子女非空，则右子女入队列}}}//算法结束6．12voidpreorder(bitree*t);(前序非递归遍历){bitree*s[n+1];//s是指针数组，数组中元素为二叉树节点的指针top=0;while(t!=null||top!=0){while(t!=null){visit(*t);s[++top]=t;t=t->lchild}if(top!=0){t=s[top--];t=t->rchild;}}}//算法结束voidinorder(bitree*t);(中序非递归遍历){bitree*s[n+1];top=0;while((t!=null||top!=0){while(t!=null){s[++top]=t;t=t->lchild}if(top!=0){t=s[top--];visit(*t);t=t->rchild;}}//算法结束voidpostorder(bitree*t);(后序非递归遍历){typedefstructnode{bitree*t;tag:0..1}stack;stacks[n+1];top=0;while(t||top){while(t){s[++top].t=t;s[top].tag=0;t=t->lchild;}while(top&&s[top].tag==1){printf(s[top--].t->data:3);}if(top){s[top].tag=1;t=s[top].t->rchild;}}}//算法结束6.13bitree*dissect(bitree**t,ElemTypex)//二叉树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);//在左子树中查找并拆开//若在左子树中未找到，就到右子树中查找并拆开if(!find)find=(dissect(&(*t)->rchild),x);return(find);}}elsereturn(null);//空二叉树}//算法结束6.14intsearch(bitreet,ElemTypex)//设二叉树t中，值为x的结点至多一个，本算法打印x的所有祖先//算法思想是，借助后序非递归遍历，用栈装遍历过程的结点，当查到//值为x的结点时，栈中元素都是x的祖先{typedefstruct{bitreep;inttag;}snode;snodes[];inttop=0;while(t&&t->data!=x||top){while(t&&t->data!=x)//沿左分支向下{s[++top].p=t;s[top].tag=0;t=t->lchild;}if(t->data==x)//{for(i=1;i<=top;++i)printf(“%cn”,s[i].p->data);//输出，设元素为字符return(1);}elsewhile(top>0&&s[top].tag==1)top--;//退出右子树已访问的结点if(top>0)//置访问标志1，访问右子树{s[top].tag=1;t=s[top].p;t=t->rchild;}}return(0);//没有值为x的结点}//算法结束6.15中序序列BDCEAFHGA后序序列DECBHGFAFBGC DHE前序序列ABCDEFGHA6.16后序线索树：BCDEFHEnull只有空指针处才能加线索。线索链表：0A00C00B10F11E11001H1^1G16.17bitree*search(bitree*p)//查找前序线索二叉树上给定结点p的前序后继{if(p->ltag==1)return(p->rchild)；//左标记为1时，若p的右子树非空，p的右子树的根p->rchild为p的后继；若右子树为空，p->rchild指向后继elsereturn(p->lchild);//左标记为0时，p的左子女p->lchild为p的后继.}//算法结束6.18bitree*search（b：tree*p）//在后序线索二叉树中查找给定结点的后序前驱的算法 {if(p->rtag==0)return(p->rchild);//p有右子女时，其右子女p->rchild是p的后序前驱elsereturn(p->lchild);//p的左标记为0，左子女p->lchild是后序前驱,否则，线索p->lchild指向p的后序前驱}A6.19GBLHCMIDNPJEOQKFR前序序列：ABCDEFGHIJKLMPQRNO后序序列：BDEFCAIJKHGQRPMNOL6.216.227,19,2,6,32,3,21,10其对应字母分别为a,b,c,e,f,g,h。 哈夫曼编码：a：0010b：10c：00000d：0001e：01f：00001g：11h：0011第七章图（参考答案）7．1（1）邻接矩阵中非零元素的个数的一半为无向图的边数；（2）A[i][j]==0为顶点，I和j无边，否则j和j有边相通；（3）任一顶点I的度是第I行非0元素的个数。7．2（1）任一顶点间均有通路，故是强连通；（2）简单路径V4V3V1V2;（3）01∞1∞01∞1∞0∞∞∞10邻接矩阵V1V4||V2|^|V2V3|^|V1|^|V3V4V3|^|邻接表V1V3|^|V2V1|^| V2|^|V4|^|V3V4V1|^|逆邻接表7．3（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,V27．4（1）①adjlisttpg;vtxptri,j;//全程变量②voiddfs(vtxptrx)//从顶点x开始深度优先遍历图g。在遍历中若发现顶点j，则说明顶点i和j间有路径。{visited[x]=1;//置访问标记if(y==j){found=1;exit(0);}//有通路，退出else{p=g[x].firstarc;//找x的第一邻接点while(p!=null){k=p->adjvex;if（!visited[k]）dfs(k);p=p->nextarc;//下一邻接点}}③voidconnect_DFS(adjlisttpg)//基于图的深度优先遍历策略，本算法判断一邻接表为存储结构的图g种，是否存在顶点i//到顶点j的路径。设1<=i,j<=n,i<>j.{visited[1..n]=0;found=0;scanf(&i,&j);dfs(i);if(found)printf（”顶点”,i,”和顶点”,j,”有路径”）；elseprintf（”顶点”,i,”和顶点”,j,”无路径”）；}//voidconnect_DFS (2)宽度优先遍历全程变量，调用函数与（1）相同，下面仅写宽度优先遍历部分。voidbfs(vtxptrx)//{initqueue(q);enqueue(q,x);while(!empty(q));{y=delqueue(q);if(y==j)　{found=1;exit(0);}//有通路，退出else{p=g[x].firstarc;//第一邻接点while(p!=null){k=p->adjvex;if(!Visted[k])enqueue(q,k);p=p->nextarc}}//if(y==j)}//while(!empty(q))7．5。假定该有向图以邻接表存储，各顶点的邻接点按增序排列DFS序列：V1,V3,V6,V7,V4,V2,V5,V8BFS序列：V1,V3,V4,V6,V7,V2,V5,V8DFS森林BFS森林V1V2V1V2V3V4V3V4V5V5V6V7V6V8V8V77．6简单回路指起点和终点相同的简单路径。算法基本思想是利用图的遍历，以顶点VK开始，若遍历中再通到VK，则存在简单回路，否则不存在简单回路。Adjlisttpg;visited[1..n]=0;Intfound=0;//全程变量Intdfs(btxptrx)//从k顶点深度优先遍历图g，看是否存在k的简单回路{visited[x]=1;p=g[x].firstarc;while(p!=null){w=p->adjvex;if(w==k){found=1;exit(0);}//有简单回路，退出if(!visited[k])dfs(w);p=p->nextarc; }//while(p!=null)}//dfs7．7（1）PRIM算法的最小生成树bbbeb222222addadaa1ccbebgeeb222222dada222da1111111hacfc1hfc1111（2）KRUSKAL算法的最小生成树dbggee122cda211111hachf111（权值相同的边选取无顺序）7．8所选顶点已选定点的集合尚未被选顶点的集合DIST[2][3][4][5][6]初态{1}{2，3，4，5，6}2015∞∞∞3{1，3}{2，4，5，6}19∞∞252{1，3，2}{4，5，6}∞29256{1，3，2，6}{4，5}29294{1，3，2，6，4}{5}295{1，3，2，6，4，5}{}注：选定点4和5时无优先顺序，二者最短路径均为29 7．908∞1200:1->1A0=30∞path0=1201:1->2520123∞:1到3没有直接通路08∞path1同path0,加入顶点1后无变化A1=30∞52008∞A2=30∞path2同path152∞08∞A3=30∞本题不好，终态和初态无变化V4V6V3520V27．10V1V5V6V6V3V4V2V3V4V6V4V6V5V3V1V6V1V2V6V4V2V3V3V2V4V4V3共七种用TOPOSORT算法求得第七种，即V5,V6,V1,V2,V3,V4.用邻接表存储结构，邻接点逆序即编号大的排在前面。入度为0顶点用栈结构存储，初始时从顶点1到顶点N扫描，入度为0的顶点进栈，得V5在栈顶。7．11voidtoposort_dfs（graphg；vtptrv）//从顶点v开始，利用深度优先遍历对图g进行拓扑排序。 //基本思想是利用栈s存放顶点，首先出栈的顶点是出度为0的顶点，是拓扑序列中最后一个顶//点。若出栈元素个数等于顶点数，则拓扑排序成功，输出的是逆拓扑排序序列。{visited[1..n]=0;top=0;num=0;//初始化；top为栈顶指针，num记出栈元素数s[++top]=v;//顶点入栈while(top!=0){w=firstadj(g,v);//求顶点v的第一邻接点while(w！=0)//w!=0的含义是w存在{if(!visited[w])s[++top]=w;w=nextadj(g,v,w);//求下一个邻接点}if(top!=0){v=s[top--];num++;printf(v);}//输出顶点}printf(“n”);if(numV3->V4->V7->V9->V10长22关键活动a3,a4,a7,a11,a14顶点VeVl活动ell-eV100a1000 V259V366V41212V51516V61620V71717V81920V92222V102424a2594a3000a4660a56137a612131a712124a815160a912164a1015161a1117170a1216204a1319201a1422220关键路径V1->V3->V4->V7->V9->V10长22关键活动a3,a4,a7,a11,a14第八章排序（参考答案）本章所用数据结构#defineN待排序记录的个数typedefstruct{intkey;ElemTypeother;}rectype;rectyper[n+1];//r为结构体数组8.2稳定排序有：直接插入排序、起泡排序、归并排序、基数排序不稳定排序有：希尔排序、直接选择排序、堆排序希尔排序例：49，38，49，90，70，25直接选择排序例：2，2，1堆排序例：1，2，28.3voidStlinkedInsertSort(s,n);//对静态链表s[1..n]进行表插入排序，并调整结果，使表物理上排序{#defineMAXINT机器最大整数typedefstruct{intkey;intnext;}rec;recs[n+1];//s为结构体数组s[0].key=maxint;s[1].next=0;//头结点和第一个记录组成循环链表i=2;//从第2个元素开始，依次插入有序链表中while(i<=n){q=0;p=s[0].next;//p指向当前最小元素，q是p的前驱while(p!=0&&s[p].key=i+1;j--)//向前起泡，一趟有一最小冒出if(r[j]r[j-1];exchange=1;}//有交换for(j=i+1;j>=n-I;j++)//向后起泡，一趟有一最大沉底if(r[j]>r[j+1]){r[j]ß>r[j+1];exchange=1;}//有交换i++;}//endofWHILEexchange}//算法结束8.5（1）在n=7时，最好情况下进行10次比较。6次比较完成第一趟快速排序，将序列分成相等程度的序列（各3个元素），再各进行2次比较，完成全部排序。（2）最好的初始排列：4，1，3，2，6，5，78.6voidQuickSort(rectyper[n+1];intn)//对r[1..n]进行快速排序的非递归算法{typedefstruct{intlow,high;}nodenodes[n+1]；inttop;intquickpass(rectyper[],int,int);//函数声明top=1;s[top].low=1;s[top].high=n;while(top>0){ss=s[top].low;tt=s[top].high;top--;if(ss1){top++;s[top].low=ss;s[top].high=k-1;}if(tt-k>1){top++;s[top].low=k+1;s[top].high=tt;}}}//算法结束intquickpass(rectyper[];ints,t){i=s;j=t;rp=r[i];x=r[i].key;while（i=r[j].key)i++;if(i0){k=quickpass(r,ss,tt);if(k-ss>tt-k)//一趟排序后分割成左右两部分{if(k-ss>1)//左部子序列长度大于右部，左部进栈{top++;s[top].low=ss;s[top].high=k-1;}if(tt-k>1)ss=k+1;//右部短的直接处理elseflag=false;//右部处理完，需退栈}elseif(tt-k>1)//右部子序列长度大于左部，右部进栈{top=top+1;s[top].low=k+1;s[top].high=tt;}if(k-ss>1)tt=k-1//左部短的直接处理elseflag=false//左部处理完，需退栈}if(!flag&&top>0){ss=s[top].low;tt=s[top].high;top--;flag=true;}}//endofwhile(flag||top>0)}//算法结束intquickpass(rectyper[];ints,t) //用“三者取中法”对8.6进行改进{inti=s,j=t,mid=(s+t)/2;rectypetmp;if(r[i].key>r[mid].key){tmp=r[i];r[i]=r[mid];r[mid]=tmp}if(r[mid].key>r[j].key){tmp=r[j];r[j]=r[mid];if(tmp>r[i])r[mid]=tmp;else{r[mid]=r[i];r[i]=tmp}}{tmp=r[i];r[i]=r[mid];r[mid]=tmp}//三者取中：最佳2次比较3次移动；最差3次比较10次移动rp=r[i];x=r[i].key;while（i=r[j].key)i++;if(ii在0~i、1或i+1~n+1之间查//找，直到/i=j为止。{intquichpass(rectyper[],int,int)//函数声明i=quichpass(r,0,n-1);//查找枢轴位置whilehile(i!=j)if(j=0)j--;if(i=0)j--;if(inext;while(p->next!=null)//剩最后一个元素时，排序结束{q=p;//设当前结点为最小s=p->next;//s指向待比较结点while(s!=null)if(s->data>q->data)s=s->next;else{q=s;s=s->next;}//用指向新的最小if(q!=p){x=q->data;q->data=p->data;p->data=x;}p=p->next;//链表指针后移，指向下一个最小值结点}}//算法结束8.11按极小化堆取调整（若已是极大化堆则维持不变）（1） （2）（3）（4）8.11voidheapadjust(K[]，n)//待排序元素在向量K中，从K1到Kn已是堆，现将第n+1个元素加入，本算法这n+1个元素调整成堆。{rp=K[n+1];x=K[n+1].key;//用rp暂存第n+1个元素，x为其关键字intc=n+1,f=c/2;//设c表示第n+1个元素的下标，f是其双亲的下标，本算法将子女与双亲比较，若符合堆的定义，则排序结束；否则将双亲和子女交换。之后，双亲的下标为新的子女，再与新的双亲比较，直至根结点（无双亲）while(f>0)if(K[f].key<=x)break;//已符合堆的定义，排序结束else{K[c]=k[f];c=f;f=c/2;}//仅将双亲移至子女K[c]=rp;//将暂存记录rp（原第n+1个记录）放入合适位置}//算法结束//利用上述排序思想，从空堆开始，一个一个添加元素的建堆算法如下： voidheapbuilder(rectypeR[])//向量R的第1到第n个元素为待排序元素，本算法将这n个元素建成堆。{for(i=0;i=r[i].key)i++;q[++rear]=i;//一个子序列上界I++;//I指向下一子序列下界}if(q[rear]r[j])c[i]=c[i]+1elsec[j]=c[j]+1;for(i=0;i0;i--){p=distribute(i,p);p=collect(i);}return(p)}8.16见8.38.17s=┌logkm┐//s为归并趟数，m为顺串个数，k为归并路数因为m=100和s=3所以k>=5，故至少取5路归并即可第九章查找（参考答案）9.1intseqsearch(rectyper[],keytypek)//监视哨设在n个元素的升序顺序表低下标端，顺序查找关键字为k的数据//元素。若存在，则返回其在顺序表中的位置，否则，返回0r[0].key=k;i=n;while(r[i].key>k)i--;if(i>0&&r[i].key==k)return(i);elsereturn(0)}//算法结束查找过程的判定树是单支树。 查找成功的平均查找长度为ASL=∑PICI=1/n*∑i=1/2*(n+1)查找不成功的平均查找长度为ASL=1/(n+1)(∑i+(n+1))=(n+2)/2.9.2typedefstructlnode{intfreq;//访问频率域keytypekey;//关键字ElemTypeother;structlnode*prior,*next;//双向链表}seqlist;typedefstructsnode{intfreq;//访问频率域keytypekey;//关键字ElemTypeother;}snode;voidlocate(seqlistL,keytypeX)//在链表中查找给定值为X的结点，并保持访问频繁的结点在前//调用本函数前，各结点的访问频率域（freq）值均为0。{seqlist*p;//p是工作指针p=L->next;//p指向第一元素while(p!=null&&p->key!=X)p=p->next;//查找X结点if(p==null){printf(“noX”);return;}else{q=p->prior;//q是p的前驱p->next->prior=p->prior;//先将p结点从链表中摘下q->next=p->next;while(q!=L&&q->freqprior;//找p结点位置q->next->prior=p;//将p结点插入链表p->next=q->next;p->prior=q;q->next=p;}//算法结束voidlocate(snodeL[],intn;keytypeX)//在具有n个元素顺序存储的线性表L中查找给定值为X的结点，并保持//访问频繁的结点在前。调用本函数前，各结点的访问频率域值为0。{inti=0,freq;L[n].key=X;//监视哨while(L[i].key!=X)i++;if(i==n){printf(“noX”);return;}else{freq=L[i].freq;while(L[i-1].freqkreturn(binsearch(s,low,mid-1,k)elsereturn(mid);}elsereturn(0);}//算法结束9.5intlevel(bstnode*bst,keytypeK)//在二叉排序树bst中，求关键字K所在结点的层次{bstnode*p;//p为工作指针intnum=0;//记层数p=bst;while(p&&p->key!=K)//二叉排序树不空且关键字不等if(p->keyrchild;}//沿右子树else{num++;p=p->lchild;}//沿左子树if(p->key==K)return(++num);//查找成功elsereturn(0);//查找失败}//算法结束其递归算法如下：intlevel(bstnode*bst,keytypeK，intnum)//在二叉排序树中，求关键字K所在结点的层次的递归算法，调用时num=0{if(bst==null)return0;elseif(bst->key==K)return++num;elseif(bst->keyrchild,K,num++);elsereturn(bst->lchild,K,num++); }//算法结束9.6bstnode*ancestor(bstnode*bst)//bst是非空二叉排序树根结点的指针。//A和B是bst树上的两个不同结点，本算法求A和B的最近公共祖先。//设A和B的关键字分别为a和b，不失一般性，设akey==a){printf(“A是B的祖先。n”);return(p);}elseif(p->key==b){printf(“B是A的祖先。n”);return(p);}elseif(p-key>a&&p->keykey>b)return(ancestor(p->lchild));//沿左子树elsereturn(ancestor(p->rchild));//沿右子树}//算法结束9.7intbstree(bstnode*bst,bstnode*pre)//bst是二叉树根结点的指针,pre总指向当前访问结点的前驱，调用本函数//时为null。本算法判断bst是否是二叉排序树。设一全程变量flag,初始值//为1，调用本函数后，若仍为1，是二叉排序树，否则，不是二叉排序树。{if(bst!=null){bstree(bst->lchild,pre);if(pre==null)pre=bst;elseif(pre->key>bst->key){printf(“非二叉排序树n”);flag=0;return0;}elsepre=p;bstree(bst->rchild,pre);}}JAN9.8（1）MARFEBMAYJUNAPRSEPAUGJULOCTDECNOVASL=(1*1+2*2+3*3+3*4+2*5+1*6)/12=42/12 JAN(2)MARFEBLMAYAPRJUNRJULAUG(一)JANMARAUGMAYJUNFEBAPRRSEPJULLOCTJAN（二）MARAUGRROCTAPRFEBJUNSEPMAYJULNOV(三)MARRCOTJAN MAYAUGJUGSEPFEBNOVDECAPR（四）ASL=(1*1+2*2+4*3+4*4+1*5)/12=38/124050409.950205030L40LR60301010LRL90553020(LL型)(LR型)(RL型)4040205555206050103070503010R708060R(RR型)80G9.10CIM JKHDENOAB（1）插入关键字B后，B-树的结点无变化GKIMCNOLHJDEAB（2）插入关键字L后，结点E和G产生分裂GKCIMOPNLJHABDE（3）插入关键字P后，结点H产生分裂GKCIMOPQNLJHABDE （4）插入关键字Q后，结点不变KOGQMICRPNLJHDEAB（5）插入关键字R后，三个层次结点产生分裂，使B-树增高9.11hegtypehashdelete(hashtableht,hegtypek)//ht是拉链法解决冲突的散列表，本算法删除关键字//为k的指定结点，若删除成功，返回K；否则//返回null{设I=H(heg);//I为关键字k用指定哈希函数计算的哈希地址if(ht[i]=null){printf(“没有关键字k”);return(null);}else{p=ht[i];pre=p;while(p&&p->data!=k){pre=p;p=p->next;}if(p==null){printf(“没有关键字k”);return(null);}else{pre->next=p->next;free(p);return(k);}}}//hashdelete9.12（1）0123456789101112140168275519208479231110121431139113H(19)=19%13=6H(14)=14%13=1H(23)=23%13=10H(01)=01%13=1冲突，2次成功H(68)=68%13=3H(20)=20%13=7H(84)=84%13=6冲突，3次成功H(27)=27%13=1冲突，4次成功H(55)=55%13=3冲突，3次成功H(11)=11%13=11 H(10)=10%13=10冲突，3次成功H(79)=79%13=1冲突，9次成功成功时的平均查找长度=（1*6+1*2+3*3+1*4+1*9）/12=30/12查找不成功时的平均查找长度=（1+13+12+11+10+9+8+7+6+5+4+3+2+1）/13=92/13^^^^^^^（2）01479^2701126855^34584^1962078910^231011^1112查找成功时平均查找长度=（1*6+4*2+1*3+1*4）/12=21/12查找不成功时的平均查找长度=（1*7+2*2+3*3+1*5）/13=25/139.13各种查找方法均有优点和缺点，不能笼统地说某种方法的好坏。顺序查找的时间为o（n），在n较小时使用较好，它对数据元素的排列没有要求；二分查找时间为o（log2n），效率高但它要求数据元素有序排列；散查找时间为o（1），它只能按关键字随机查找（使用散列函数），不能顺序查找，也不能折半查找。'