数据结构课后答案

第一章绪论（参考答案）1.3(1)O(n)(2)(2)O(n)(3)(3)O(n)(4)(4)O(n1/：2(5)(5)执行程序段的过程中，x,y值变化如下：循环次数xy0（初始）91100192100293100910010010101100119199129210020101992191983010198319197到y=0时，要执行10*100次，可记为O（10*y）=O（n）1.52100,(2/3)n，1吵,n1/2,n3/2,(3/2)n,nlo§2n,2n,n!,nn第二章线性表(参考答案)在以下习题解答中，假定使用如下类型定义：顺序存储结构：#defineMAXSIZE1024typedefintElemType;//实际上，ElemType可以是任意类型typedefstruct{ElemTypedata[MAXSIZE];intlast;//last表示终端结点在向量中的位置}sequenlist;链式存储结构(单链表)typedefstructnode{ElemTypedata;structnode*next；}linklist;链式存储结构(双链表)typedefstructnode{ElemTypedata;structnode*prior,*next；}dlinklist;静态链表typedefstruct{ElemTypedata;intnext;}node;nodesa[MAXSIZE];2.1头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是la,往往简称为“链表la”。头结点：为了链表操作统一，在链表第一元素结点(称为首元结点，或首结点)之前增加的一个结点，该结点称为头结点，其数据域不无实际意义(当然，也可以存储链表长度，这只是副产品)，其指针域指向头结点。这样在插入和删除中头结点不变。开始结点：即上面所讲第一个元素的结点。2.2只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。2-3voidinsert(ElemTypeA[],intelenum,ElemTypex)//向量A目前有elenum个元素，且递增有序，本算法将乂插入到向量A中，并保持向量的递增有序。{inti=0,j;while(i<elenum&&A[i]<=x)i++;//查找插入位置for(j=elenum-1;j>=i;j--)A[j+1]=A[j];//向后移动元素A[i]=x;//插入元素}//算法结束2-4voidrightrotate(ElemTypeA[],intn,k)//以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。{intnum=0;//计数，最终应等于nintstart=0;//记录开始位置(下标)while(num<n){temp=A[start];//暂存起点元素值，temp与向量中元素类型相同empty=start;//保存空位置下标next=(start-K+n)%n;//计算下一右移元素的下标while(next!=start){A[empty]=A[next];//右移num++;//右移元素数加1empty=next;next=(next-K+n)%n;//计算新右移元素的下标}A[empty]=temp;//把一轮右移中最后一个元素放到合适位置num++;start++;//起点增1，若num<n则开始下一轮右移。}}//算法结束算法二算法思想：先将左面n-k个元素逆置，接着将右面k个元素逆置，最后再将这n个元素逆置。voidrightrotate(ElemTypeA[],intn,k)//以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。{ElemTypetemp;for(i=0;i<(n-k)/2;i++)//左面n-k个元素逆置{temp=A[i];A[i]=A[n-k-1-i];A[n-k-1-i]=temp;}for(i=1;i<=k;i++)//右面k个元素逆置{temp=A[n-k-i];A[n-k-i]=A[n-i];A[n-i]=temp;}for(i=0;i<n/2;i++)//全部n个元素逆置{temp=A[i];A[i]=A[n-1-i];A[n-1-i]=temp;}}//算法结束2•5voidinsert(linklist*L,ElemTypex)//带头结点的单链表L递增有序，本算法将x插入到链表中，并保持链表的递增有序。{linklist*p=L->next,*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-7intlength1(linklist*L)//本算法计算带头结点的单链表L的长度{linklist*p=L->next;inti=0;//p为工作指针，指向当前元素，i表示链表的长度while(p){i++;p=p->next;}return(i);}//算法结束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){r=pa->next;pa->next=C->next;C->next=pa;pa=r;}while(pb){r=pb->next;pb->next=C->next;C->next=pb;pb=r;}free(B);//while(pa){r=pa->next;pa->next=C->next;C->next=pa;pa=r;}while(pb){r=pb->next;pb->next=C->next;C->next=pb;pb=r;}free(B);//释放B表头结点}//算法结束//将A表中剩余元素逆置//保留后继结点的指针//逆置//恢复待逆置结点的指针//将B表中剩余元素逆置//保留后继结点的指针//逆置//恢复待逆置结点的指针//pre为前驱指针，指向当前元素*?的前驱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->freq<p-freq)q=q->prior;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证明：由j<k和pj<pk说明p.在pk之前出栈，即在k未进栈之前p.已出栈，之后k进栈，然后pk出栈；由j<k和p>pk说明p.在pk之后出栈，即p.被pk压在下面，后进先出。由以上两条，不可能存在i<j<k使p<p：<p.。也就是说，若有、，2,3顺序入栈，不可能有3,1，2的出栈序列。J1voidsympthy(linklist*head,stack*s)第三章栈和队列(参考答案)//从数据结构角度看，栈和队列是操作受限的线性结构，其顺序存储结构//和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。〃判断长为n的字符串是否中心对称{inti=1;linklist*p=head->next;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.7linklist*init(linklist*q)//q是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空{q=(linklist*)malloc(sizeof(linklist));//申请空间，不判断空间溢出q->next=q;return(q);}//算法结束linklist*enqueue(linklist*q,ElemTypex)//q是以带头结点的循环链表表示的队列的尾指针，本算法将元素x入队{s=(linklist*)malloc(sizeof(linklist));//申请空间，不判断空间溢出s->next=q->next;//将元素结点s入队列q->next=s;q=s;//修改队尾指针return(q);}//算法结束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;intempty(sequeue*cq)//cq为循环队列，本算法判断队列是否为空{return(cq->quelen==0?1:0);}//算法结束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]);//返回队头元素}}//算法结束第四章串(参考答案)在以下习题解答中，假定使用如下类型定义：#defineMAXSIZE1024typedefstruct{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结束设A=””，B=''mule”，C=''old”，D=''my”则0：(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)*yS=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)//取X中的字符//取X中的字符q=q->next;//和Y中字符比较//找到Y中没有的字符//上一字符在Y中存在，//取X中下一字符。//再从Y的第一个字符开始比较//X中字符在Y中均存在while(q&&q->data!=ch)if(!q)return(ch);else{pre=p->next;p=pre;q=Y->next;}}return(null);}//算法结束4.6intstrcmp(seqstring*S,seqstring*T)//S和T是指向两个顺序串的指针，本算法比较两个串的大小，若S串大于T串，返回1；若S串等于T串，返回0；否则返回-1

{inti=0;while(s->ch[i]!=’\0’&&t->ch[i]!=’\0’)if(s->ch[i]>t->ch[i])return(1);elseif(s->ch[i]<t->ch[i])return(-1);elsei++;//比较下一字符if(s->ch[i]!=’\0’&&t->ch[i]==0)return(1);elseif(s->ch[i]==’\0’&&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.1第五章多维数组和广义表(参考答案)5.1A⑵[3]⑵[3],A0001,A0011,A0101,A0111,A0201,A0211,A0002,A0012,A0102,A0002,A0012,A0102,A0112,A0202,A0212A0010A0100A0110A0200A将第一维的’0变为了后，可列出另外18个元素。以行序为主(即行优先)时，先改变右边的下标，从右到左进行。5.2设各维上下号为C]„d]，c2„d2，c3„d3，每个元素占l个单元。LOC(a)=LOC(ac1c2c3)+[(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3)]*l推广到Jn维数组！！(下界和上界)为(ci，di)，其中1<=i<=n.则：其数据元素的存储位置为：LOC(a”.)=LOC(a]°)+[(d-c+1)••-(d-c+1)(^,-c)+(d-c+1)„(d-c+1)l22nn^11，'33，nn(j-Cc)+…+(d-c+1)(j-cJ+(j-c)]*l=LOC(a)+£a(j-c)22nnn-1n-1nnC1C2C3iiii=1其中a,n(dk-ck+1)(1<=i<=n)k=i+1若从c开始，c数组下标从0开始，各维长度为bi(1<=i<=n)则：LOC(a.”.)=LOC(ag„)+(b*b*„*b*j+b*…*b*+j„+b*j+j)*lliein'Of)(V'D2n1QnJonJn_1J"JIJ匕♦♦.jnUU..♦U23II13II2IIIllIIn=LOC(a000)+£aiji其中：ai=l,ai-i=bi*ai，1<i<=n(1)k=2*i+j(0<=k<3n-2)(2)i=(k+1)/3(0<=k<3n-2)j=k-2*i5.4voidsaddlepoint(inta[m][n]);//a是m行n列的二维数组，本算法求所有马鞍点//b是一维数组,存放一行中可能的马鞍点的列值,k记相等值个数//c是一维数组，存放某列可能马鞍点的行值,kk记相等值个数{for(i=0;i<m;i++){min=a[i,0];//最小值初始化b[0]=0;k=1;//b数组记最小值的列号，k记最小值的个数for(j=1;j<n;j++)//找每一行中的最小值if(a[i][j]<min){b[0]=j;min=a[i][j];k=1;}//重新确定最小值elseif(a[i][j]==min){b[k+1]=j;k++;}//有相等的最小值for(jj=0;jj<k;k++)//第i行有k个相等的最小值{j=b[jj];max=a[i][jj];kk=0;//a[i][j]是否是马鞍点while(kk<m&&max>=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;i<m;i++){row[i]=a[i][0];//最小值初始化for(j=1;j<n;j++)//找每一行中的最小值if(a[i][j]<row[i])row[i]=a[i][j];//重新确定最小值}for(j=0;j<n;j++){col[j]=a[0,j];//最大值初始化for(i=1;i<m;i++)//找每一列中的最大值if(a[i][j]>col[j])col[j]=a[i][j];//重新确定最大值}for(i=0;i<m;i++)for(j=1;j<n;j++)if(row[i]==col[j])printf(“马鞍点i=%d,j=%d,a[i][j]=%d”，i,j,a[i][j]);时间复杂度O((m*n)).解法3:设定两个数组：max[0..n-1]记各列的最大值所在行号min[0..m-1]记各行的最小值所在列号第j列的最大值为A[max[j]][j],第i行的最小值是A[i][min[i]]

voidsaddlepoint（inta[m][n]）;//a是m行n列的二维数组，本算法求所有马鞍点{intmax[]=0,min[]=0;for（i=0;i<m;i++）for（i=0;i<m;i++）for（j=0;j<n;k++）{if（A[i][j]>A[max[j]][j]）max[j]=i;//重新确定第j列最大值的行号if（A[i][j]<A[i][min[i]]）min[i]=j;//重新确定第i行最小值的列号}for（i=0;i<m;i++）{j=min[i];//a[i][j]是否是马鞍点if（max[j]==i）printf（“马鞍点A[%d][%d]=%d”，i,j,a[i][j]）;}//ENDOFforjj}时间复杂度为O（m*n+m）.5.5（1）三元组表（行号0—5，列号0—5）S=（（0，0，15），（0，3，22），（0，5，-15），（1，1，11），（1，2，3），（2，3，-6），（4，0，91），（5，2，28））（2）5.6算法分析：两矩阵A和B相加的结果是一矩阵C，其元素Ci.有三种情况；(1)4=气.(B..=0)；(2)C..=B..(A..=0)；(3)C..=A..+B..。在(3)种情况下，要看结果是否为0,c矩阵只有非零元素？ijij口Voidmatrixaddition(crosslist*A,*B)//稀疏矩阵A和B用十字链表存储结构，本算法将稀疏矩阵B加到矩阵A上(ca=A->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->col<pa->col)//B的非0元素插入A中；(j=pb->col;pt=chb[j];pre=pt//取到表头指针；while(pt->down_col<pb->col){pre=pt;pt=pt->down;}pre->down=pt->down;//该结点从B表相应列摘下i=pb->right;pt=chb[i];pre=pt;//取B表行表头指针while(pt->right->row<pb->row{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->row<ptb->row){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-col<ptb->col){pre=pt;pt=pt->right;}pre->right=ptb;ptb->right=pt;}//endof“if>co<pa->col)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))=ptail((b,k,p,h))=(k,p,h)head(((a,b),(c,d)))=(a,b)tail(((a,b),(c,d)))=((c,d))head(tail(((a,b),(c,d)))=(c,d)tail(head(((a,b),(c,d))))=(b)5.8(1)(2)5.9(1)

第6章树和二叉树（参考答案）6.1⑴根结点a6.2三个结点的树的形态:(1)6.3设树的结点数是n，贝0n=n0+n1+n2++nm+(1)设树的分支数为B,有n=B+1n=1n1+2n2++mnm+1(2)由(1)和(2)有：n0=n2+2n3++第6章树和二叉树（参考答案）6.1⑴根结点a6.2三个结点的树的形态:(1)6.4ki-1(i为层数)(n-2)/k+1

(n-1)*k+i+1(n-1)%k!=0;其右兄弟的编号n+16.5(1)顺序存储结构1234567891011121314ABCD#EF#G####H#为空结点注：6.6(1)6.6⑵(3)中序DGBAECHF后序GDBEHFCA6.7(1)⑵中序DGBAECHF后序GDBEHFCA(1)⑵(3)6.8height(bitreebt)height(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))//判左右子树等价}//算法结束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("％c\n”，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中序序列BDCEAFHG___后序序列DECBHGFAZ'"一一、【A前序序列ABCDEFGH6.16后序线索树：null_/.-E0A0/0B1//0C0100/0A0/0B1//0C0100/1E1/0F1/I1IH6.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的后序前驱}6.196.21}27,19,2,6,32,3,21,10其对应字母分别为a,b,c,e,f,g,h。哈夫曼编码：a：0010b：10c：00000d：0001e：01f：00001g：11h：0011第七章图(参考答案)1(1)邻接矩阵中非零元素的个数的一半为无向图的边数；A[i][j]==0为顶点，I和j无边，否则j和j有边相通;任一顶点I的度是第I行非0元素的个数。7.2(1)任一顶点间均有通路，故是强连通；(2)简单路径V4V3V1V2;(3)01818018180888邻接矩阵10V1=►V4|►V2laV2►V3lAV3V1lAV3|aV4邻接表V1►V3|aV2►V1|AV4|aV2|aV3►V4—V1lA逆邻接表7.3(1)邻接表从顶点4开始的DFS序列：V5,V3,V4,V6,V2,V1从顶点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序歹U：BFS序歹UDFS序歹U：BFS序歹U：DFS森林1V7V1,V3,V6,V7,V4,V2,V5,V8V1,V3,V4,V6,V7,V2,V5,V8、2V5W8BFS森林V2V5J®7.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)}//dfs(2)KRUSKAL算法的最小生成树(权值相同的边选取无顺序)7.8所选顶点已选定点的集合尚未被选顶点的集合DIST[2][3][4][5][6]初态{1}{2,3,4,5,6}20158883{1，3}{2,4,5,6}1988252{1,3,2}{4,5,6}829256{1,3,2,6}{4,5}29294{1,3,2,6,4}{5}295{1,3,2,6,4,5}{}注：选定点4和5时无优先顺序，二者最短路径均为297.9Z0881200:1->1A0=308path0=1201:1->2I5201238：1到3没有直接通路Z088path1同path0,加入顶点1后无变化A1=308520K488^A2=308path2同path1k28/088A3=308本题不好，终态和初态无变化

,V2,V3,共七种用TOPOSORT算法求得第七种，用邻接表存储结构，邻接点逆序即编号大的排在前面。入度为0顶点用栈结构存储，初始时从顶点1到顶点N扫描，入度为0的顶点进栈，得V5在栈顶。,V2,V3,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(num<n)printf(“从”,”v”,”顶点开始拓扑排序不能顺利完成”)；elseprintf(“拓扑排序成功，输出的是一个逆拓扑序列.\n”)；}7.12

V100a1000V259a2594V366a3000V41212a4660V51516a56137V61620a612131V71717a712124V81920a815160V92222a912164V102424a1015161a1117170a1216204a1319201a1422220关键路径V1->V3->V4->V7->V9->V10长22关键活动a3,a4,a7,a11,a14顶点VeVl活动ell-eV100a1000V259a2594V366a3000V41212a4660V51516a56137V61620a612131V71717a712124V81920a815160V92222a912164V102424a1015161a1117170a1216204a1319201a1422220关键路径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<s[i].key)//查找插入位置{q=p;p=s[p].next;}s[i].next=p;s[q].next=i;//将第个元素链入i++；}//while(i<=n)静态链表的插入//以下是重排静态链表，使之物理有序i=1;p=s[0].next;while(i<=n){WHILE(p<i)p=s[p].next;q=s[p].next;if(i!=p){s[i](3s[p];s[i].next=p;p=q;i++;}}}//算法结束8.4voidTwoWayBubbleSort(rectyper[n+1];intn)//对r[1..n]进行双向冒泡排序。即相邻两遍向两个相反方向起泡{inti=1,exchange=1;//设标记while(exchange){exchange=0;//假定本趟无交换for(j=n-i+1j>=i+1;j--)//向前起泡，一趟有一最小冒出if(r[j]<r[j-1]){r[j]Or[j-1];exchange=1;}//有交换for(j=i+1;j>=n-I;j++)//向后起泡，一趟有一最大沉底if(r[j]>r[j+1]){r[j]Or[j+1];exchange=1;}//有交换i++;}//endofWHILEexchange}//算法结束8.5在n=7时，最好情况下进行10次比较。6次比较完成第一趟快速排序，将序列分成相等程度的序列(各3个元素)，再各进行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(ss<tt){k=quickpass(r,ss,tt);if(k-ss>1){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<j){while(i<j&&x<=r[j].key)j—;if(i<j)r[i++]=r[j];while(i<j&&x>=r[j].key)i++;if(i<j)r[j--]=r[i];;]r[i]=rp;return(i);}//一次划分算法结束8.7voidQuickSort(rectyper[n+1];intn)//对r[1..n]进行快速排序的非递归算法对8.6算法的改进{typedefstruct{intlow,high;}nodenodes[n+1]；inttop;intquickpass(rectyper[],int,int);//函数声明top=1;s[top].low=1;s[top].high=n;ss=s[top].low;tt=s[top].high;top—;flag=true;while(flag||top>0){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<j){while(i<j&&x<=r[j].key)j--;if(i<j)r[i++]=r[j];while(i<j&&x>=r[j].key)i++;if(i<j)r[j--]=r[i];;]r[i]=rp;return(i);}//一次划分算法结束8.8viodsearchjrec(rectyper[]，intj)//在无序记录r[n]中，找到第j(0<=j<n)个记录。算法利用快速排序思想，找到第一〃轴元素的位置i，若i=j则查找结束。否则根据j<i或j>i在0〜i、1或i+1〜n+1之间查〃找，直到/i习为止。(intquichpass(rectyper[],int,int)//函数声明i=quichpass(r,0,n-1);//查找枢轴位置whilehile(i!=j)if(j<i)i=quichpass(r,0.i-1);elsei=quichpass(r,i+1.n-1);}//searchjrec算法结束8.9viodrearrange(rectyper[],intn)//本算法重排具有n个元素的数r，使取负值的关键字放到取非负值的关键字之前。(inti=0,j=n-1;rp=r[0];while(i<j){while(i<j&&r[j].key>=0)j--;if(i<j)r[i++]=r[j];//取负值关键字记录放到左面while(i<j&&r[i].key<0)i++;if(i<j)r[j--]=r[i]//取非负值关键字记录放到右面}//while(i<j)8.9voidarrange(rectyper[n+1];intn)//对r[1..n]进行整理，使关键字为负值的记录排在非负值的记录之前[inti=0,j=-1;rp=r[0];while(i<j){while(i<j&&r[j].key>=0)j—;if(i<j)r[i++]=r[j];//将关键字取负值的记录放到前面while(i<j&&r[i].key<0)i++;if(i<j){r[j--]=r[i];//将关键字取非负值的记录放到后面}r[i]=rp;//}〃算法结束〃本算法并未判断轴枢的关键字的正负，在排序中并未和轴枢〃记录比较，而是按正负区分，提高了效率8.10typedefstructnode{ElemTypedata;structnode*next;}linklist;voidsimpleselect(linklist*head)//head是单链表的头指针，本算法对其进行直接选择排序。设p指向无序区第一个记录(开始是链表的第一个记录)，用q指向一趟排序中的最小记录，为简便起见，将P和q所指结点的数据交换。{p=head->next;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)(以T口为根的子树不符合根定义)(3)(4)(以T口为根的子树不符合根定义)(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<n;i++)heapadjust(R，i);}〃算法结束8.13voidsort(rectyper[],intn)//对具有n个元素的数组进排序。算法思想是先对数组扫描一遍，形成若干最大有序子〃列，再两两归并，最后完成排序。各子序列的长度(上界和下界)存储在循环队列中，〃队头指针指向队头元素的前一位置，队尾指针指向队尾元素。#definem100//子队列长度(intq[m+1];i=1;front=0;rear=0;while(i<=n-1)//该循环求出rear个子序列(if(r[i+1].key>=r[i].key)i++;q[++rear]=i;//一个子序列上界I++;//I指向下一子序列下界}if(q[rear]<n)q[++rear]=n;//最后一个子序列下界〃以下为两两归并，当最后只剩下一个有序子序列(即|rear-front=1|)时，合并结束。while((front+1)%m!=rear)(newrear=rear;while((front+1)%m!=rear)//从r合并到r1中合并{low=q[front]+1;//取两个子序列界mid=q[++front%m];if(front+1%m!=rear)high=q[++front%m];elsehigh=mid;merge(r,r1,low,mid,high);newrear=(newrear+1)%m;q[newrear]=high;〃新子序列上界}q[front]=0;rear=newrear;〃下一轮归并初始化while((front+1)%m!=rear)//从n拷入r中{low=q[front]+1;mid=q[++front%m];if(front+1%m!=rear)high=q[++front%m]elsehigh=mid;merge(r1,r,low,mid,high);newrear=++rear%m;q[newrear]=high;}q[front]=0;rear=newrear;//下一轮归并从第一个元素开始}//最外层的while((front+1)%m!=rear)voidmerge(rectypea[],a1[],intl,m,h)〃设a数组中a[l.....m]和a1[m+1.....h]有序，本算法使l....h有序，并拷贝到a1中{i=l;j=m+1;k=l-1;while(i<=m&&j<=h)ifa[i].key<=a[j].keya1[++k]=a[i++]elsea1[++k]=a[j++]while(i<=m)a1[++k]=a[i++];while(j<=h)a1[++k]=a[j++];}8.14voidCountSort(rectyper[];intn);//对r[0..n-1]进行计数排序{intc[n]={0};//c数组初始化，元素值指其在r中的位置。如c[i]=j,(0<=i,j<n)//则意味着r[i]应在r的第j位置上。for(i=0;i<n;i++)//一趟扫描比较选出大小，给数组c赋值for(j=i+1;j<n;j++)if(r[i]>r[j])c[i]=c[i]+1elsec[j]=c[j]+1;for(i=0;i<n;i++)while(c[i]!=i)//若c[i]=i,则r[i]正好是第i个元素;否则，需要调整{k=c[i];temp=r[k];r[k]=r[i];r[i]=temp;//r[k]和r[i]交换c[i]=c[k];〃将c[k]存入c[i],c[k]=k;//r[k]已是第k个记录//while(c[i]!=i)8.15#defineD10//假设每个关键字长度为10typedefstruct{charkey[D];//关键字用字符数组表示anytype:otheritem;//元素的其他信息intnext;//指针域}rcdnode;rcdnoder[n];//为n个英文单词为关键字的记录排序intf[27],e[27];intdistribute(inti;intp)//静态链表r中的记录按key[i+1]，，key[D侑序，p指向链表中第一记录。本算法//第I位关键字key[i]建立子表，同一子表中的key[i]值相同。巾]和e[i]分别指向各子表〃中第一个记录和最后一个记录。0<=j<=27，key[i]为空格时，j=0；而key[i]为字母时，j=〃该字母的ASCII码-64。f[i]=0表示第j个子表为空{for(j=0;j<=27;j++)f[j]=0;//子表初始化为空表while(p!=0)//p=0表示链表到尾(if(r[p].key[i]==’’)j=0；elsej=r[p].key[i]-64;if(f[j]==0)f[j]=p;elsef[e[j]].next=p;e[j]=p;//将p所指结点插入第j个子表}p=r[p].next;//p指向下一个元素}//forintcollet(inti)//