数据结构答案打印版.doc

(1)N2+1(2)2N–1(3)2(4)队空条件:front==rear队满条件:(rear+1)%(m+1)==front 注:假设牺牲数组一个单元,只存放m个元素(6)广度优先搜索(8)14(9)避免在插入和删除操作中将第一个结点看作是特殊结点,使程序编写简单。:(1)存储结构:两个栈使用同一段内存空间,图示如下。栈1只做PUSH操作,对应队列的进队;栈2只做POP操作,对应队列出队操作。(2)队列定义:typedefstruct{ intdata[M]; intTop1;//栈1指针 intTop2;//栈2指针}SqQueue; 队列初始化: SqQueueq; =-1; =0;(3)进队操作: if(==M-1) printf(“队满!”); [++]=e;(4)出队操作: if(==+1)printf(“队空!”); elsee=[++];:voidTopologicalSort(Graphg){ //有向图g采用邻接表存储结构 int indegree[MAX_VER];//定义各顶点入度数组indegree[] int i,k,count; SqQueue q; node *p; FindIndegree(indegree,g);//求出所有顶点的入度 q=InitQueue();//建0入度顶点队列q for(i=0;i<;i++) if(!indegree[i])q=EnQueue(q,i);//入度为0者进队列 count=0;//对输出顶点计数 while(!QueueEmpty(q)) { q=DeQueue(q,&k); printf("%3c",[k].vex); count++;//输出k号顶点并计数 for(p=[k].firstarc;p;p=p->next) { --indegree[p->no];//对k号顶点的每个邻接点的入度减1 if(!indegree[p->no]) q=EnQueue(q,p->no);//若入度为0则进队列}//for }//while if(count<)//该有向图有回路 printf("\nThereisacircuit.");}//TopologicalSort 对于有n个顶点,e条边的有向图的拓扑排序算法的时间复杂性为O(n+e),要求按学生成绩(总分)排名次,若总分相同,则学号在前的,仍排在前面,即要求选择的排序算法具有稳定性,分析具有稳定性的排序算法有如下4种: 再从时间与空间去综合考虑,选择改进的冒泡排序好。算法如下: voidbubble_sort(inta[],intn){ intt=0,done=0; inti,j; for(i=1;i<=n-1&&!done;i++) { done=1; for(j=0;j<=n-i-1;j++) if(a[j]>a[j+1]) {done=0;t=a[j];a[j]=a[j+1];a[j+1]=t;} } }:voidMerge(intb[],inta[],inti,intm,intn){ //将有序的b[i..m]和b[m+1..n]归并为有序的a[i..n] intj,k; for(j=m+1,k=i;(i<=m)&&(j<=n);++k) { cmp++; if(b[i]<b[j]) {a[k]=b[i++];change++;} else{a[k]=b[j++];change++;} } while(i<=m) {a[k++]=b[i++];change++;}//将剩于的b[i..m]复制到a while(j<=n) {a[k++]=b[j++];change++;}//将剩余的b[j..n]复制到a}//MergevoidMSort(inta[],intc[],ints,intt){ //将a[s..t]归并排序为c[s..t] intm; intb[MAX]; if(s==t)c[s]=a[s]; else { m=(s+t)/2;//将a[s..t]平分为a[s..m]和a[m+1..t] MSort(a,b,s,m);//递归地将a[s..m]归并为有序的b[s..m] MSort(a,b,m+1,t);//递归地将a[m+1..t]归并为有序的b[m+1..t] Merge(b,c,s,m,t);//将b[s..m]和b[m+1..t]归并到c[s..t] }}//MSortvoidMergeS