《算法分析与设计3》由会员分享，可在线阅读，更多相关《算法分析与设计3（8页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析精品快线之计算机最短路径：算法实现：(1) 输入e条弧j, k,建立AOE-网的存储结构；(2) 从vO出发，令ve0=0,按拓扑排序求vei,若拓扑排序的结果顶点数少 于网中顶点数，说明图中有网，结束；否则执行(3)；(3) 从汇点vn出发，令vln-l=ven-l,按逆拓扑排序求出vli;(4) 根据各顶点的ve和vl的值，求出每条弧s的e (s)和1 (s),若满足e (s) =1 (s), 则s为关键活动。算法描述：Status TopologicalOrder(AlGraph G, Stack &T) Findindegree( G, indegree); InitSt
2、ack(T);count=0: ve0G.vexnum-1 = 0;wh订e ( !StackEmpty(S) pop ( S, j ): Push (T, j); +count;for (p=Gverticesjfirstare; p ; p = p-nextarc ) k = p-adjvex; if(!(一indegreek)Push(S, k);if(vej+*(p-info)vek) vek = vej+*(p-info);if (count nextarc) k = p-adjvex ; dut =*(p-info);if (vlk-dutvlj) vlj = vlk - dut;
3、 for (j=0;jnextare) k = p-adjvex; dut 二 *(p-info); ee 二 vej ; el = vlk-dut; tag = (ee=el)?printf (j,k, dut, ee, el, tag); 内部排序：全部记录都可以同时调入内存进行的排序。外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排序。直接插入徉序直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序希尔排序(缩小增量法)排序过程：先取一个正整数dln,把所有相隔dl的记录放一组，组内
4、进行直接插 入排序；然后取d2r2.key,则交换；然后比较第二个记录与第三个记录；依次类推，直 至第n-1个记录和第n个记录比较为止一第一趟冒泡排序，结果关键字最大的记 录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个 记录位置重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止快速排序基本思想：通过一趟排序，将某关键字通过比较直接到位，并将待排序记录分割成独立的 两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两 部分记录进行排序，以达到整个序列有序排序过程：对rst中记录进行一趟快速排序，附设两个指
5、针i和j,设枢轴 记录 rp=rs, x=rp key初始时令i二s, j二t首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换 再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和:rp交换 重复上述两步，直至i=j为止再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止 简单选择排序排序过程首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个 记录交换再通过旷2次比较，从剩余的旷1个记录中找出关键字次小的记录，将它与第二个 记录交换重复上述操作，共进行1趟排序后，排序结束归并排序归并将两个或两个以上的有序表组合成一个新的有序表，叫归并2-
6、路归并排序排序过程设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1 两两合并，得到Ln/2j个长度为2或1的有序子序列再两两合并，如此重复，直至得到一个长度为n的有序序列为止第n个Fibonacci数可递归地计算如下：public static int fibonacci(int n)if (n 0)hanoi (n-1, a, c, b);move (a, b); hanoi (nT, c, b, a);二分搜索技术 给定已按升序排好序的n个元素a0:n-l,现要在这n个元素中找出一特定元素X。据此容易设计岀二分搜索算法：public static int binaryS
7、earch(int a, int x, int n)/ 在 a0 = al 二 =an-l中搜索 x/找到x时返回其在数组中的位置，否则返回int left = 0; int right = n - 1;wh订e (left amiddle) left = middle + 1;else right = middle - 1;return -1; / 未找到 x背包问题public static float knapsack(float c, float w, float v, float x)int n=v. length;new Element(wi, vi, i);Element d =
8、 new Element n; for (int i = 0; i n; i+) di MergeSort. mergcSort(d);int i;float optP;for (i=0;in;i+) xi=0;for (i二0;in;i+) if (di.wc) break;xdi.i二 1;opt+=di.v;c-=di, w;if (in)xdi. i=c/di. w;opt+=xd订.i*di. v;最优装载public static float loading(float c, float w, int x)int n二w. length;Elernent d = new Eleme
9、nt n;for (int i = 0; i n; i+)di = new Element(wi, i);MergeSort.【nergeSort (d);float opt=0;for (int i 二 0; i n;卄+) xi = 0;for (int i = 0; i n & di.w = c; i+) xd订.i = 1;opt+=di. w;c -= di. w;return opt;哈夫曼树(最优二叉树)1、最优二叉树(Huffman Tree)树的路径长度：是从树根到每一结点的路径长度之和。(完全二叉树)树的带权路径长度：树中所有叶子结点的带权路径长度(该结点到树根之间路 径长
10、度与结点上权的乘积)之和。哈夫曼树算法实现void HuffmaCoding (HuffmanTree &HT, HuffmanCode &HC, int *w, int n) if( n=l ) return;m = 2*n-l;HT = (HuffmanTree)malloc(m+1)*sizeof(Htnode):for( p - HT, i=l; i=n; +i, +p, +w) *p - *w, 0, 0,0;for( ; i=m; +i,+p) *p = 0,0,0,0;ford = n+1; i=m; +i) Select (HT, iT , si, s2):HTsl. pare
11、nt 二 i; HTs2. parent = i;HTi. lchild = si; HTi. rchild = s2;HTi. weight = HTsl. weight+HTs2. weight; /*哈夫曼编码*/HC = (HuffmanCode)malloc(n+1)*sizeof(char *);cd = (char )malloc(n*sizeof(char);cdn-l = “0” ;for(i=l ; i=n ; +i ) start = n-1;for ( c=I , f=HTi. parent ; f!=0; c=f, f = HTf. parent)if(HTf. lc
12、hild = c) cdstart = 0” ;else cdstart - 1;HCI = (char * )malloc(n-start)*sizeof(char):Strcpy(HCi, feedstart);free(cd);n后问题解向量：(XI, X2,，Xn)显约束:Xi=l, 2,，n隐约束：1) 不同列：XiHXj2) 不处于同一正、反对角线：|i-j Xi-Xj|private static boolean place (int k)for (int j=l;jn) sum+;elsefor (int i=l;i=n;i+) xt二 i;if (place(t) backtrack(t+1);1Jo-l背包问题解private static double bound(int i)/计算上界double cleft 二 c - cw; / 剩余容量double b
