《算法分析与设计》实验指导书(学时).doc

数理学院 算法分析与设计  目 录 实验一 排序…………………………..…..………3 实验二 …………………..…………..5 实验三 ……………………….8 实验四 最短路径问题……………………10 实验一 排序 实验目的 1）以排序问题为例，掌握分治法的基本设计策略 2）熟练掌握排序算法的实现； 3）熟练掌握快速排序算法的实现； 4) 理解常见的算法经验分析方法 实验环境 计算机、C语言程序设计环境 实验学时 2学时 实验内容与步骤 实验数据 要求：编写一个函数datagenerate，生成2000个在区间[1,10000]上的随机整数，并将这些数输出到外部文件data.txt中。这些数作为实验的数据。 实现排序算法 要求：实现算法。 输入data.txt； 输出文件resultsS.txt（注：建议将此排好序的数据作为实验二的算法输入）；运行时间TimeS。 算法： /* A[] 中包含待排元素；array B[] is a work array */ TopDownMergeSort(A[], B[], n) { TopDownSplitMerge(A, 0, n, B); } // iBegin is inclusive; iEnd is exclusive (即：A[iEnd]不是待排元素) TopDownSplitMerge(A[], iBegin, iEnd, B[]) { if(iEnd - iBegin 2) // 如果只有1个待排元素，返回。 return; // recursively split runs into two halves until run size == 1, // then merge them iMiddle = (iEnd + iBegin) / 2; // 划分 TopDownSplitMerge(A, iBegin, iMiddle, B); TopDownSplitMerge(A, iMiddle, iEnd, B); TopDownMerge(A, iBegin, iMiddle, iEnd, B); // 合并；元素放到数组B中。 CopyArray(B, iBegin, iEnd, A); // copy the merged runs back to A } // left half is A[iBegin : iMiddle-1] // right half is A[iMiddle : iEnd-1] TopDownMerge(A[], iBegin, iMiddle, iEnd, B[]) { i0 = iBegin, i1 = iMiddle; // While there are elements in the left or right runs for (j = iBegin; j iEnd; j++) { // If left run head exists and is = existing right run head. if (i0 iMiddle (i1 = iEnd || A[i0] = A[i1])) { B[j] = A[i0]; i0 = i0 + 1; } else { B[j] = A[i1]; i1 = i1 + 1; } } } CopyArray(B[], iBegin, iEnd, A[]) { for(k = iBegin; k iEnd; k++) A[k] = B[k]; } 实现快速排序算法 要求：实现QuickSort 算法。 输入：待排数据文件data.txt； 输出文件resultsQS.txt；运行时间TimeQS。 快速排序算法： Procedure QuickSortp, q) integer p, q；global n, A(1:n) if p q then j ← q+1 Partition(p, j)A(p)划分元素表A[p : j-1]；划分后，划分元素下标由参数j带出。 QuickSort (p, j-1); QuickSort(j+1, q); end if end QuickSort 用元素A(m)划分元素表A[m : p-1]： Procedure partition(m, p