算法和数据结构C语言习题答案6--9章.docx

1.现在有一个已排序的字典，请改写二分法检索算法，使之当排序码key在字典中重复出现时算法能找出第一个key出现的元素下标(用"position来保存)。保持算法时间代价为O(logn)o【答】思路一般的二分法检索算法只要找出关键码key在字典中的一个下标。在比较的过程中，一旦发现相等，记录下当前下标mid就符合要求。程序如下：数据构造字典采用6.1.4节中的顺序表示法。typedefintKeyType:typedefintDataType;二分法检索算法intbinarySearch(SeqDictionarjr*pdic.KeyTypekey,int*position)(intlow,mid,high;low=0;high=pdic->n-1;while(low<=high)mid=(low+high)/2;if(PdiC->elementmid.key=key)position=mid;returnTRUE;)elseif(pdic->elementlmid.key>key)high=mid-I;elselow=mid+1;)position=low;returnFALSE;)改写后的算法想要找出关键码key在字典中第一次出现的下标。在比较中，如果遇到相等(key与pdic->elementmidj.key相等，那么需要分情形讨论O1如果当前下标mid等于0,或者key与pdic->elementmid-1.key不等，那么mid一定是key第一次出现的下标，返回mid即可。2如果情形1不成立，那么mid一定大于等于key第一次出现的下标，需要在IOW和mid-1之间继续进展搜索，找出key第一次出现的下标。下面算法中，加粗的局部是对原算法的修改。修改后的二分法检索算法intbinarySearch1(SeqDictionary*pdic.KeyTypekey,int*position)产算法完毕后，"position存放key第一次出现的下标*/intlow,mid,high;low=0;high=pdic->n-1;while(low<=high)mid=(low+high)/2;if(pdic->element(mid.key=key)if(mid=OHkey!=pdic->elementmid-lj.kcy)*position=mid;returnTRUE;*此时mid就是key在字典中第一次出现的下标*/elsehigh=mid-1;/*在左半段继续搜索可elseif(pdic->elementmid.key>key)high=mid-1;elselow=mid+1;)*position=low;returnFALSE;代价分析该算法的时间复杂度为O(IOgn)O2 .试编写一算法求出指定结点在给定的二叉排序树中所在的层数。【答】数据构造采用7.1.3节中字典的二叉排序树表示。算法intsearch_layer(PBinTreepbtree.PBinTreeNodepnode)(/*返回二叉排序树*pbtree中结点*pnode所在层数，要求所给结点在树中*/intlayer=0;PBinTreeNodeP=*pbtree;while(p!=NULL)if(p->key=pnode->key)returnlayer;*查找结点成功，返回层数*/if(p->key>pnode->key)(p=p->llink;/*进入左子树继续查找*/layer+;)elsep=p->rlink;/*进入右子树继续查找*/layer+;)return-1;/*查找结点失败*/)代价分析假设二叉排序树有个结点，高度是力(IOg2<=标=)，算法执行的时间代价最坏为Q/?)。*注意根结点为零层。3 .试编写一算法在给定的二叉排序树上找出任意两个不同结点最近的公共祖先(假设在两结点A,B中，A是B的祖先，那么认为A,B最近的公共祖先就是A)。数据构造同上题算法intFindLoWeSlCOmmonAnCeSIor(PBinSearChNoderoot,inivalue1,intvalue2)PBinSearchNodecurnode=root;while(l)if(curno<le->key>value1&&curno<ie->key>value2)curnode=cum<xie->llink;elseif(cumode->key<value1&&cumode->key<value2)curnode=cumode->rlink;elsereturncumode->key;)4 .设计一个有效的算法，在1000个无序的元素中，挑选出其中前5个最大的元素。【答】数据构造IyPedefinlKeyType;typedefintDalaTy四；typedefstructKeyTypekey;/*排序码字段*/DataTypeinfo;/*记录的其它字段*/JRecordNode;typedefstructintn;*n为文件中的记录个数*/RecordNode*record;JSortObject;思路这里不需要整体排序，应选择一种能较快得出最终排序段的前一局部的算法改造即可，如直接选择排序，起泡排序，堆排序都能最先得出前5个最大元素。综合考虑算法的时间代价，选择直接选择排序算法改造即可。算法函数返回一个数组，数组中存着挑出的元素，为动态分配的。RecordNode*Outmax(SortObject*pvector,intout)(inti,j,k;RecordNode*outpart;RecordNodetemp;if(out>pvector->n)(printf("thegivenvalueiswrong!");returnNULL;)outpart=(RecordNode*)malloc(oul*sizeof(RecordNo<le);If(Oulpart=NULL)printf(',Nospace!n");returnNULL;)fbr(i=0;i<out;i+)(k=i;for(j=i+1;j<pveclor->n;j+)if(pvector->recordj.key>pvecior->recordk.key)k=j;if(k!=i)(emp=pvector->recordi;pvector->recordi=vector->recordk;vector->recordk=tem;)outparti=pvector->recordi;)returnoutpart;代价分析0(*w?)(设从n个元素中选出m个最大元素)。5 .写一个算法来判断对给定有向图中的指定顶点是否至少存在一条有向边指向它。【答】图有三种表示方法：出边表邻接表的一种)，入边表邻接表的一种和邻接矩阵。相应的有三种算法。设为顶点数，机为边数。对于出边表，顺次搜索一遍边即可，时间代价为0(6)。对于人边表，判断指定顶点的边表头指针是否非空即可，时间代价为。(1)。对于邻接矩阵，搜索矩阵中指定顶点对应的列，判断其中是否有非。元即可，时间代价为0()。以出边表为例，给出一个算法如下。数据构造采用9.1.3节中有向图的邻接表出边表表示法。算法intis_end(GraphListg,intk)/*判断图g中是否有边指向第A个结点(O<=A<=g.n-l)*/EdgeListp:inti;for(i=0;i<g.n;i+)(p=g.vexsi.edgelist;while(p!=NULL)if(p->endvex=i)return1;=p->nextedge;)returnO;代价分析该算法的时间复杂度为0(6)。6 .设计一个算法，确定(无权)图中每一对结点之间的可达关系。【答】数据构造采用图的邻接矩阵表示法。#defineMAXVEX100typedefchar*Vexl>,pe;typedefintAdjType;typedefstruct(VexTypevexsMAXVEX;*顶点信息*/AdjTypearcsMAXVEXMAXVEX;产边信息*/intn;产图的顶点个数*/)GraphMatrix;思路这里介绍WarShan算法，该算法解决了无权)图的可达性问题。算法用到了一个矩阵。作为算法的参数之一。开场时，对矩阵中元素赋值，使。与图的邻接矩阵相等。这样，矩阵。记录的就是所有直接的边连接。算法的核心局部是一个三重循环。其中外重循环的循环次数为，每次循环更新。中的元素。循环一次后，“中记录的就是所有直接连接或者只经由结点。而形成的通路的情况。循环kIWkWQ次后,a中记录的就是所有至多只经由结点0,1,卜1而形成的通路的情况。这样，算法完毕时，矩阵”中记录的就是每一对结点之间的可达性信息。Mat/为1,表示从结点i到结点,是可达的；为0,那么表示不可达。算法voidwarshall(GraphMatrixpgraph,inta(11MAXVEX)inti,j,m;for(i=0:i<pgraph->n;i+)/*对矩阵a中元素赋值，使a与图的邻接矩阵相等*/for(j=0;j<pgraph->n;j+)aij=pgraph->arcsij;for(m=0;m<pgraph->n;m+)产算法的核心局部，一个三重循环*/for(i=0;i<pgraph->n;i÷+)for(j=0;j<pgraph->n;j+)aij=aiIl(aim&&amj)i代价分析算法的核心局部是一个三重循环，每重的循环次数为，因此该算法的时间代价为0(/)。调试结果该例如程序计算以以下图的可达性：运行结果如下：O1OOOO010000000000111111111000101000