算法分析与设计3.doc

《算法分析与设计3.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法设计与分析》精品快线之计算机最短路径：•算法实现：(1)输入e条弧〈j,k>,建立AOE-网的存储结构；(2)从vO出发，令ve[0]=0,按拓扑排序求ve[i],若拓扑排序的结果顶点数少于网中顶点数，说明图中有网，结束；否则执行(3)；(3)从汇点vn出发，令vl[n-l]=ve[n-l],按逆拓扑排序求出vl[i];(4)根据各顶点的ve和vl的值，求出每条弧s的e(s)和1(s),若满足e(s)=1(s),则s为关键活动。算法描述：StatusTopologicalOrder(AlGraphG,Stack&T){Findindegree(G,indegree);InitSta

2、ck(T);count=0:ve[0・・G.vexnum-1]=0;wh订e(!StackEmpty(S)){pop(S,j):Push(T,j);++count;for(p=G・vertices[j]・firstare;p;p=p->nextarc){k=p->adjvex;if(!(一indegree[k]))Push(S,k);if(ve[j]+*(p->info)>ve[k])ve[k]=ve[j]+*(p->info);}}if(count

3、pologicalOrder(G,T))returnERROR;vl[0・・G・vexnum-1]=ve[0・・G・vexnum-1];while(!StackEmpty(T))for(pop(T,j),p=G・vexticestj]・firstarc;p;p=p->nextarc){k=p->adjvex;dut=*(p->info);if(vl[k]-dutnextare){k=p->adjvex;dut二*(p->info);ee二ve

4、[j];el=vl[k]-dut;tag=(ee==el)?'printf(j,k,dut,ee,el,tag);}}内部排序：全部记录都可以同时调入内存进行的排序。外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排序。直接插入徉序直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序希尔排序(缩小增量法)排序过程：先取一个正整数dl

5、程将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[l].key>r[2].key,则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止一第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止快速排序基本思想：通过一趟排序，将某关键字通过比较直接到位，并将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序排序过

6、程：对r[s・・・・・・t]中记录进行一趟快速排序，附设两个指针i和j,设枢轴记录rp=r[s],x=rp・key初始时令i二s,j二t首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和:rp交换重复上述两步，直至i=j为止再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止简单选择排序排序过程首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换再通过旷2次比较，从剩余的旷1个记录中找出关键字次小的记录，将它与第二个记录交换重复上述操作，共进行「1趟排序后，排序结束归并排序归并

7、——将两个或两个以上的有序表组合成一个新的有序表，叫归并2-路归并排序排序过程设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1两两合并，得到Ln/2j个长度为2或1的有序子序列再两两合并，・・・・・・如此重复，直至得到一个长度为n的有序序列为止第n个Fibonacci数可递归地计算如下：publicstaticintfibonacci(intn)if(n<=1)return1;returnfibonacci(n-