《数据结构-用C语言描述》课后习题答案资料1

数据结构课后习题参考答案第一章绪论TOC\o"1-5"\h\z1.3(1)O(n)(2)O(n)(3)O(n)(4)O(n1/)2(5)执行程序段的过程中，x,y值变化如下:循环次数xy0(初始)911001921002„„93„„100„„9100100101011001191991292100„„20„„101„„9921„„91„„98„„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)顺序存储结构：实际上，可以是任意类型表示终端结点在向量中的位置sequenlist;(2)链式存储结构(单链表)(3)链式存储结构(双链表)(4)静态链表头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是la,往往简称为“链表la”。头结点：为了链表操作统一,在链表第一元素结点（称为首元结点,或首结点）之前增加的一个结点,该结点称为头结点,其数据域不无实际意义（当然,也可以存储链表长度,这只是副产品）,其指针域指向头结点。这样在插入和删除中头结点不变。开始结点：即上面所讲第一个元素的结点。只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。2・3向量目前有个元素，且递增有序，本算法将插入到向量中，并保持向量的递增有序。查找插入位置向后移动元素插入元素算法结束2・4以向量作存储结构，本算法将向量中的个元素循环右移位，且只用一个辅助空间。计数，最终应等于记录开始位置（下标）暂存起点元素值，与向量中元素类型相同保存空位置下标计算下一右移元素的下标右移右移元素数加计算新右移元素的下标把一轮右移中最后一个元素放到合适位置起点增,若则开始下一轮右移。算法结束算法二算法思想：先将左面个元素逆置，接着将右面个元素逆置，最后再将这个元素逆以向量作存储结构，本算法将向量中的个元素循环右移位，且只用一个辅助空间。ElemTypetemp;左面2个元素逆置{temp=A[i];A[i]=A[n-k-1-i];A[n-k-1-i右面个元素逆置{temp=A[n-k-i];A[n-k-i]=A[n-i];A[n-i2全部个元素逆置算/法/结束2・5带头结点的单链表递增有序，本算法将插入到链表中，并保持链表的递增有序。L为工作指针，指向当前元素，为前驱指针，指向当前元素的前驱申请空间，不判断溢出查找插入位置插入元素算法结束2・6voidinvert(linklist*L)本算法将带头结点的单链表逆置。算法思想是先将头结点从表上摘下，然后从第一个元素结点开始，依次前插入以为头结点的链表中。{linklist*p=L->next,*s;为工作指针，指向当前元素，为的后继指针头结点摘下，指针域置空。算法中头指针始终不变while(p)保留后继结点的指针逆置L->next=p;将指向下个待逆置结点}}/算/法结束2・7本算法计算带头结点的单链表的长度linklist*p=L->next;为工作指针，指向当前元素，表示链表的长度}/算法/结束(2)intlength1(nodesa[MAXSIZE])本算法计算静态链表中元素的个数。{intp=sa[0].next,i=0;为工作指针，指向当前元素，表示元素的个数，静态链指针等于时链表结束whi！l=e-1()p{i++;p=sa[p].next;}return(i);}算//法结束2・8voidunion_invert(linklist*A和是两个带头结点的递增有序的单链表，本算法将两表合并成一个带头结点的递减有序单链表，利用原表空间。为工作指针，分别指向表和表的当前元素，为当前逆置//元素的后继指针,使逆置元素的表避免断开。/算/法思想是边合并边逆置，使递增有序的单链表合并为递减有序的单链表。头结点摘下，指针域置空。算法中头指针始终不变两表均不空时作将表中元素合并且逆置保留后继结点的指针逆置C->next=pa;pa=r;恢时复时待逆置结点的指针}将表中元素合并且逆置保留后继结点的指针逆置pb=r;恢时复待时逆置结点的指针}以下和语句，只执行一个将表中剩余元素逆置保留后继结点的指针逆置pa=r;恢时复时待逆置结点的指针}将表中剩余元素逆置保留后继结点的指针逆置pb=r;恢时复时待逆置结点的指针}释放表头结点}时时算法结束2・9时时长度大于1的单循环链表，既无头结点，也无头指针，本算法删除的前驱结点inip=>netpre二p为工作指针，指向当前元素，pr为前驱指针，指向当前元素的前驱ie(p>net!=)pre=p;p=p>ne土查找S勺前驱pre->next=s;free(p);//删除元素}//算法结束2・10voidone_to_three(linklist*A,*B,*C)是带头结点的的单链表，其数据元素是字符字母、字符、数字字符、其他字符。本算法将A表分成三个带头结点的循环单链表A、和，分别含有字母、数字和其它符号的同一类字符，利用原表空间。{linklist*p=A->next,r;为工作指针，指向A表的当前元素，r为当前元素的后继指针使表避免断开。将将算法思想是取出当前元素，根据是字母、数字或其它符号，分别插入相应表中。=(init)a(ize£(申逾空间i不判断溢出B->next=null;准备将循将环链表的头结点=(init)a(ize£(申逾空间i不判断溢出C->next=null;准备将循将环链表的头结点while(p){r=p->next;将用以将记住后继结点if(p->data>=’a’&&p->data<=’z’||p->data>=’A’&&p->data<=’Z’)p>net=A>net;A>net=p将字母字符插入A表elseif(>pd-ata>=’0’&&p->data<=’9’)p>net=>net;>ne=将数字字符插入表eep>net=>net;>9将其窃符号插入表p=r;将将恢复后继结点的指针ie}将算将法结束2・11voidlocate(dlinklist*L)是带头结点的按访问频度递减的双向链表，本算法先查找数据将将查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。{linklist*p=L->next,*q;为工作指针，指向表的当前元素，为p的前驱，用于查找插入位置。ie(p&&p>data!=)p=p>ne查找值为的结点。if(!p)return("不存在值为的结点”)；eep>fre令元素值为的结点的fre域加1。p>net>prir=p>prir;将p结点从链表上摘下。p->prior->next=p->next;=p>prir;以下查找p结点的插入位置while(q!=L&&q->freq<p-freq)q=q->prior;p>net=>net;>net>pr^pr缔点插入p->prior=q;q->ne；xt=p算将法结束第三章栈和队列(参考答案)//从数据结构角度看，栈和队列是操作受限的线性结构，其顺序存储结构//和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。3.1123421343214432112432143324113242314342113421432设入栈序列元素数为n,23412431则可能的出栈序列数为C2nn=(1/n+1)*(2n!/(n!)2)证明：由和pp说明p在p之前出栈，即在k未进栈之前p已出栈，之后k进栈，然后p出栈；由和pp说明p在p之后出栈，即p被p压在下面，后进先出。由以上两条，不可能存在i使kppp。也就是说，若有，，顺序入栈，不可能有，1，2的出栈序列。voidsympthy(linklist*head,stack*s)〃判断长为n的字符串是否中心对称{inti=1;linklist*p=head->next;while(i<=n/2)//前一半字符进栈{push(s,p->data);p=p->next;}if(n%!==0)p=pnext;奇数个结点时跳过中心结点while(p&&p->data==pop(s))p=p->next;if(p二二null)printf(“链表中心对称”)elseprintf(“链表不是中心对称”)}//算法结束intmatch()//从键盘读入算术表达式，本算法判断圆括号是否正确配对(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(“括号配对”)；}//算法结束typedefstruct//两栈共享一向量空间{lemypem；栈可用空间0-minttop[2]栈/顶/指针}twostack;intpush(twostack*s,inti,ElemTypex)//两栈共享向量空间，i是0或，表示两个栈，x是进栈元素，//本算法是入栈操作{if(abs(stp0stp)==)栈满rn(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)两栈共享向量空间是0或，表示两个栈，本算法是退栈操作{ElemTypex;if(i0i)return(0编号错误else{switch(i)ae0:if(tp0)栈空urn(0);elsex=s->v[s->top--];break;ae:if(tp)栈空urn(0);elsex=s->v[s->top++];break;default:printf("栈编号输入错误”)；return(0);}return(x);/退/栈成功}}//算法结束ElemTypetop(twostack*s,inti)两栈共享向量空间是0或，表示两个栈，本算法是取栈顶元素操作{ElemTypex;switch(i)ae0:if(tp0)栈空urn(0);elsex=s->v[s->top];break;ae:if(tp)栈空urn(0);elsex=s->v[s->top];break;default:printf("栈编号输入错误”)；return(0);}return(x);/取/栈顶元素成功}/算/法结束voidAckerman(intm,intn)e函巍的递归算法{if(m==0)return(n+1);elseif(m!=0&&n==0)return(Ackerman(m-1,1);elsereturn(Ackerman(m-1,Ackerman(m,n-1))}//算法结束linklist*init(linklist*q)是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空(linlit)all(ief(lin请空间t)不判断空间溢出q->next=q;return(q);}//算法结束linklist*enqueue(linkl，isEtle*mqTypex)是以带头结点的循环链表表示的队列的尾指针，本算法将元素入队(linlit)all(ief(lSn请空间t)不判断空间溢出netnet将元素结点入队列q->next=s;q=s;修/改/队尾指针算/法/结束是以带头结点的循环链表表示的队列的尾指针，这是出队算法判断队列是否为空指向出队元素若队列中只一个元素，置空队列修改队头元素指针释放出队结点//算//法结束。算法并未返回出队元素循环队列占个存储单元和为队头元素和队尾元素的指针约定指向队头元素的前一位置，指向队尾元素为循环队列，本算法计算其长度算/法/结束循环队列占个存储单元指向队尾元素为元素个数为循环队列，本算法判断队列是否为空/算/法结束是如上定义的循环队列，本算法将元素入队队满计算插入元素位置将元素入队列修;改队列长度算//法结束是以如上定义的循环队列，本算法是出队算法，且返回出队元素队空出队元素位置修;改队列长度返回队头元素}/算/法结束第四章串（参考答案在以下习题解答中，假定使用如下类型定义：表示终端结点在向量中的位置intindex(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”则U：（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”和是用带头结点的结点大小为的单链表表示的串，本算法查找中第一个不在中出现的字符。算法思想是先从中取出一个字符，到中去查找，如找到，则在中取下一字符，重复以上过程；若没找到，则该字符为所求为工作指针，控制循环取中的字符和中字符比较找到中没有的字符上一字符在中存在，取中下一字符。再从的第一个字符开始比较t)中字符在中均存在的算法结束intstrcmp(seqstring*S,seqstring*T)和是指向两个顺序串的指针，本算法比较两个串的大小，若串大于串，返回1若串等于串，返回0；否则返回{inti=0;while>(chs[i-]!=’\0’&&t->ch[i]!=’\0’)if(s->ch[i]>t->ch[i])return(1);elseif(s->ch[i]<t->ch[i])return(-1);i比较下一字符if(>sch-[i]!=’\0’&&t->ch[i]==0)return(1);elseif>ch([is]=-=’\0’&&t->ch[i]!=0)return(-1);elsereturn(0);}的的算法结束4.7linkstring*invert(linkstring*S,linkstring*T)和是用带头结点的结点大小为的单链表表示的串，是主串，是模式串。本算法是先模式匹配，查找在中的第一次出现。如模式匹配成功，则将中的子串(串)逆置。{linkstring*pre,*sp,*tp;=是前驱指针，指向中与匹配时，中的前驱=>tt=和=分别是和串上的工作指针while(sp&&tp)i>t==t>相等时后移指针{sp=sp->next;tp=tp->next;}else失的配的时主串回溯到下一个字符，子串再以第一个字符开始{pre=pre->next;sp=pre->next;tp=T->next;}it!=)t匹配失败，没有逆置以下是串逆置t=>是逆置的工作指针，现在指向待逆置的第一个字符>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,A0202A0210,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(加…jn)=LOC3c2…c/+[(d2-C2+1)…(dnQ+1)。1-%)+巴$+1)…(dnG+1)n(j2-C2)+„+(dn-Cn+1)(jn-1-Cn-1)+(jn-Cn)]*l=LOC(ac1c2c3)+工。i=1n其中an(1()若从c开始，c数组下标从0开始，各维长度为bi(1<=i<=n)则：LOC(523)=LOC(a00…0)+(b2*b3*…*bn*L+b3*…*bn*+^2„+bn*第+Q*1n=L0c(a00…0)+£。其中：a，abi*a，是行列的二维数组本算法求所有马鞍点是一维数组存放一行中可能的马鞍点的列值记相等值个数是一维数组存放某列可能马鞍点的行值记相等值个数or(i=0;i<m;i++)最小值初始化数组记最小值的列号，记最小值的个数找每一行中的最小值重新确定最小值有相等的最小值第行有个相等的最小值是否是马鞍点while(kk<m&&max>=a[i][

“马鞍点”最坏时间复杂度为最坏时所有元素相同，都是马鞍点解法若矩阵中元素值互不相同则用一维数组记下各行最小值，再用一维数组记下各列最大值,相等者为马鞍点。最小值初始化

找每一行中的最小值重新确定最小值最大值初始化找每一列中的最大值重新确定最大值“马鞍点

“马鞍点

时间复杂度

解法3:设定两个数组：第列的最大值为记各列的最大值所在行号记各行的最小值所在列号第行的最小值是是行列的二维数组本算法求所有马鞍点重新确定第列最大值的行号

重新确定第行最小值的列号是］否;是马鞍点/“马鞍点时间复杂度为（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））算法分析：两矩阵A和B相加的结果是一矩阵C,其元素Cij有三种情况；(1)CjAij(Bij=0)；(2)Cij=Bij(Aij=0)；(3)Cij=Aij+Bij。在(3)种情况下，要看结果是否为0，c矩阵只有非零元素。1J1J1J1JVoidmatrixaddition(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;〃WB表行表头指针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(pb->col<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;}(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)BAClbII』44lbII』44口a口第6章树和二叉树（参考答案）设树的结点数是，则设树的分支数为，有由（1）和（2）有：为层数其右兄弟的编号6.5（1）顺序存储结构1234567891011121314ABCD#EF#G####H注：#为空结点）前序ABDGCEFH）中序DGBAECHF）后序GDBEHFCA）空二叉树或任何结点均无左子树的非空二叉树）空二叉树或任何结点均无右子树的非空二叉树）空二叉树或只有根结点的二叉树是以二叉链表为存储结构的二叉树，本算法求二叉树的高度局部变量，分别表示二叉树左、右子树的高度左右子树高度的大者加（根）}算/法/结束preorder（cbt[],intn,inti）;是以完全二叉树形式存储的个结点的二叉树，是数

组下标，初始调用时为1。本算法以非递归形式前序遍历该二叉树是栈，栈中元素是二叉树结点在中的序是栈顶指针，栈空时“输入错误”(0i)；“输入错误”(0i)；访问根结点若右子树非空，其编号进栈先序访问左子树访问根结点若右子树非空，其编号进栈先序访问左子树退栈，先序访问右子树退栈，先序访问右子树//算法结束/以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示是以完全二叉树形式存储的一维数组，是数组元素个数。是数组下标，初始调用时为1。，，//算法结束/以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示是以完全二叉树形式存储的一维数组，是数组元素个数。是数组下标，初始调用时为1。，，/算法/结束和是两棵二叉树，本算法判断和是否等价和都是空二叉树则等价和只有一棵为空，另一棵非空，则不等价和均非空，且根结点值相等，则比较其左、右子树同为空二叉树只有一棵为空根结点值不等lsereturn(equal(T1->lchild,T/判左右子树等价//算法结束本算法按层次遍历二叉树if(ht!=null)处始化队列，队列元素为二叉树结点的指针根结点指针入队列访问结点若左子女非空/，/则左子女入队列if(p->rchi若右子女非/空/，则右子女入队列}算/法结束前序非递归遍历是指针数组，数组中元素为二叉树节点的指针算/法结束中序非递归遍历算/法结束后序非递归遍历}算/法/结束13tree*dissect(bitree**t,Ele二叉树至多有一个结点的数据域为，本算法拆去以为根的子树拆开后的第一棵树用表示，成功拆开后返回第二棵二叉树根结点数据域为

在左子树中查找并拆开若在左子树/中/未找到，就到右子树中查找并拆开空二叉树算/法结束设二叉树中，值为的结点至多一个，本算法打印的所有祖先算法思想是，借助后序非递归遍历，用栈装遍历过程的结点，当查到值为的结点时，栈中元素都是的祖先沿左分支向下输出，设元素为字符退出右子树已访问的结点置访问标志1访问右子树没有值为的结点/算/法结束6.15中序序歹BDCEAFHG后序序歹DECBHGFA6.15nullnull前序序列ABCDEFGH6.16后序线索树:只有空指针处才能加线索。线索链表:查找前序线索二叉树上给定结点的前序后继；左标记为时，若的右子树非空，的右子树的根为的后继；若右子树为空，指向后继左标记为时，的左子女为的后继}左算左法结束6.18bitree*search（b：tree*p）//在后序线索二叉树中查找给定结点的后序前驱的算法

{if(p->rtag==0)return(p->rchild);//p有右子女时，其右子女p->rchild是p的后序前驱elsereturn(p->lchild);else//p的左标记为0,左子女p->lchild是后序前驱，否则，线索p->lchild指向p的后序前驱}6.19前序序列：ABCDEFGHIJKLMPQRNO序前驱}6.19前序序列：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)邻接矩阵中非零元素的个数的一半为无向图的边数；A[i][j]==0为顶点，I和j无边，否则j和j有边相通;(3)任一顶点I的度是第I行非0元素的个数。7．2(1)任一顶点间均有通路，故是强连通；(2)简单路径V4V3V1V2;TOC\o"1-5"\h\z\/。1818888(88/逆邻接表7．3(1)邻接表(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)从顶点开始深度优先遍历图。在遍历中若发现顶点，则说明顶点和间有路径。置访问标记if(y==j)有通路，退出找的第一邻接点(!visiift)eddf[sk(]k);下一邻接点}}voidconnect_DFS(adjlisttpg)基于图的深度优先遍历策略，本算法判断一邻接表为存储结构的图种，是否存在顶点i到顶点的路径。设{visited[1..n]=0;found=0;scanf(&i,&j);dfs(i);if(found)printf("顶点”,i,“和顶点”,j,“有路径”)；elseprintf("顶点”,i,”和顶点”,j,"无路径”)；}//

(2宽)度优先遍历全程变量，调用函数与(1)相同，下面仅写宽度优先遍历部分。{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。假定该有向图以邻接表存储，各顶点的邻接点按增序排歹V1,V3,V6,V7,V4,V2,V5,V8V1,V3,V4,V6,V7,V2,V5,V8DFS序歹1」：BFS序歹1」：DFS森林V2V5BFSV1,V3,V6,V7,V4,V2,V5,V8V1,V3,V4,V6,V7,V2,V5,V8DFS序歹1」：BFS序歹1」：DFS森林V2V5BFS森林V6V7V2V6V8V5V77．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)7.7(1)PRIM算法的最小生成树(2)KRUSKAL算法的最小生成树(权值相同的边选取无顺序)7.8所选顶点已选定点的集合尚未被选顶点的集合DIST[2][3][4][5][6]初态{1}{2,3,4,5,6}20158883{1,3}{2,4,5,6}19882{1,3,2}{4,5,6}86{1,3,2,6}{4,5}29294{1,3,2,6,4}{5}295{1,3,2,6,4,5}{}注：选定点4和5时无优先顺序，二者最短路径均为29

7．9Z08%A0=308V7．9Z08%A0=308V2”1238:1到3没有直接通路Z088A1=308I52cj同加入顶点后无变化A2=X用邻接表存储结构，邻接点逆序即编号大的排在前面。入度为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(num<n)printf(“从”,“v",”顶点开始拓扑排序不能顺利完成”)；elseprints"拓扑排序成功，输出的是一个逆拓扑序列.\n")；}7.12a1=5a1=5V1'Qa3=6顶点VeVl活动ell-eV100a1000V259a2594V366a3000V41212a4660V51516a56137V61620a612131V71717a712124V81920a815160V92222a912164V102424a1015161a1117170a1216204a1319201a1422220关键路径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第八章排序(参考答案)本章所用数据结构待排序记录的个数为结构体数组8.2稳定排序有：直接插入排序、起泡排序、归并排序、基数排序不稳定排序有：希尔排序、直接选择排序、堆排序希尔排序例：49，38,_49，90，70，25直接选择排序例：2,万，1堆排序例：1,2，2对静态链表进行表插入排序，并调整结果，使表物理上排序机器最大整数为结构体数组头结点和第一个记录组成循环链表从第2个/元/素开始，依次插入有序链表中(i<=n)指向当前最小元素，是的前驱查找插入位置将第个元素链入静态链表的插入以下是重排静态链表，使之物理有序[■i算/法/结束对进行双向冒泡排序。即相邻两遍向两个相反方向起泡设标记hile(exchange)假定本趟无交换向前起泡，一趟有一最小冒出[有交换向后起泡，一趟有一最大沉底[有交换}/算法/结束8.5(1)在n=7时，最好情况下进行10次比较。6次比较完成第一趟快速排序，将序列分成相等程度的序列(各3个元素)，再各进行2次比较，完成全部排序。(2)最好的初始排列：4，1，3，2，6，5，7对进行快速排序的非递归算法函数声明算/法/结束一/次/划分算法结束dQuickSort(rectyper[n+对进行快速排序的非递归算法对算法的改进pedsetfruct{intlow,high;}nodees；[n+1]top;函数声明=1;s[top].low=1;s[top].hs[top].low;tt=s[top].highile(flag||top>0){k=quickpass(r,ss,tt);一趟排序后分割成左右两部分左部子序列长度大于右部，左部进栈{top++;s[top].lo右部短的直接处理右部处理完，需退栈}右部子序列长度大于左部，右部进栈{top=top+1;s[to左部短的直接处理左部处理完，需退栈算/法/结束用“三者取中法”对8.进6行改进三者/取/中：最佳次比较三者/取/中：最佳次比较3次移动；最差3次比较10次移动)e}一/次/划分算法结束viodsearchjrec(rectyper[]，intj)〃在无序记录r[n]中，找到第j(0<=j<n)个记录。算法利用快速排序思想，找到第一〃轴元素的位置i，若i=j则查找结束。否则根据j<i或j>i在0〜i、1或i+1〜n+1之间查〃找，直到/i=j为止。{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算法结束viodrearrange(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)进行整理，使关键字为负值的记录排在非负值的记录之前将关键字取负值的记录放到前面将关键字取非负值的记录放到后面/算/法结束/本算法并未判断轴枢的关键字的正负，在排序中并未和轴枢/记录比较，而是按正负区分，提高了效率是单链表的头指针，本算法对其进行直接选择排序。设指向无序区第一个记录（开始是链表的第一个记录），用指向一趟排序中的最小记录，为简便起见，将和所指结点的数据交换。{p=head->next;剩最后一个元素时，排序结束{q=p;设当前结点为最/小/指向待比较结点用指向新的最小if（q!=p）{x=q->data;链表指针后移，指向下一个最小值结点}}/算/法结束8.11按极小化堆取调整（若已是极大化堆则维持不变）（1）

（2）（4），待排序元素在向量中，从素调整成堆。1到（2）（4），待排序元素在向量中，从素调整成堆。1到已是堆，现将第个元素加入，本算法这个元用［暂存第个元素，为其关键字设表示第个元素的下标，是其双亲的下标，本算法将子女与双亲比较，若符合堆的定义，则排序结束；否则将双亲和子女交换。之后，双亲的下标为新的子女，再与新的双亲比较，直至根结点（无双亲）已符合堆的定义，排序结束仅将双亲移至子女将暂存记录（原第个记录）放入合适位置算待法结束利用上述排序思想，从空堆开始，一个一个添加元素的建堆算法如下：向量的第到第个元素为待排序元素，本算法将这个元素建成堆。}/算/法结束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;//最后一个子序列下界〃以下为两两归并，当最后只剩下一个有序子序列(即lrear-front=1l)时，合并结束。while((front+1)%m!=rear){newrear=rear;while((front+1)%m!=rear)//从r合并到ri中合并{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有序，并拷贝到al中{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++];}.14voidCountSort(rectype对进行计数排序intc[n]={0};数组初始化，元素值指其在中的位置。如则意味着应在的第位置上。一趟扫描比较选出大小，给数组赋值若)则正好是第个元素否则，需要调整{k=c[i];和交换将存入已是第个记录//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)//本算法按key[i]自小到大将f[j]不等于0所指各子表链成一个链表，e用为相应子表的尾//指针，，函数返回链接后链表头指针。{j=0;while(f[j]==0)j++;//找第一个非空子表p=f[j]；t=e[j]；//p为链表头指针while(j<=27){j++;while(j<=27&&f[j]==0)j++;//找下一个非空子表if(f[j]!=0){r[t].next=f[j];t=e[j]}//链接两个非空子表}r[t].next=0;//置链表尾return(p);}//collectintradixwordsort()//n个英文单词为关键字的元素存放在静态链表的数据域中。本算法按基数排序思想对这些//英文字母进行排序。排序后按关键字自小到大升序相链，算法返回指向第一个记录的下标//值。{for(i=0;i<n-1;i++)r[i].next=i+1;//形成初始链表r[n-1].next=0;//0表示链表尾p=0;for(i=d;i>0;i--){p=distribute(i,p);p=collect(i);}return(p)}见8.3s=Togkm「//s为归并趟数，m为顺串个数，k为归并路数因为m=100和s=3所以k>=5,故至少取5路归并即可第九章