算法实验报告

1、实验一快速排序与折半搜索1. 实验描述：具体描述见课本10.4节快速排序和11.3节折半搜索问题。2. 实验目的：通过快速排序问题，巩固并详细分析分治方法思想和解题步骤。3. 实验设计思路：快速排序：leftrieht假设一个待排序的数组如上團所示.排序的目的就是将其从小到大排序。快速排序的主要步 骤就是设定一个待排序的元素（称作主元，记作temp）,经过一轮划分排序后在这个主元左 边的元菊値都小于它在主元右边的元素值都大于它，一轮划分后的效果应该是这样的，如 下图|tempright这样以怕mp元素为分隔就将原来的数组分成了两个左右两个数组，然后再分别艮徒右两个 子数组进行同样的分隔然后再对

2、子子数组进行分割*递归调用这种分隔言到最后不能再 分了，此时数组也就是有序的了.基本原理是相同的.但是具体是您么分隔的有两种不同的思路。一种称作；“左右倒腾袪” 此种方法将数组分成了三个部分，小于主元的部分，大于主元的部分，未划分的部分。left苜先，要选定一个元素作为主元temp（这里将第一个元素left视为主元temp*然后将主元 分别从左右两头开始比较，在右边大元素区遇到小于temp的元素就痔其腰到左边的小元素 瓦同时更新右边比较的下标，转到左边小元素区比较，若在小元素区遇到大于temp的元 素就将其放到右边的夫元素区；下面具体示例下过程。折半查找：以处于区间中间位置记录的关键字和给定值

3、比较， 若相等，则查找成功，如不等, 则缩小范围，直至新的区间中间位置记录的关键字等于给定值或区间大小小于零时为止。其中缩小范围有两种实现方式，一是使用循环的方式，二是使用递归的方式。本次实验选择的是使用循环的方式实现查找。4实验环境及工具：操作系统：win7操作系统开发工具：eclipse3.4 jdk1.6开发工具：java5.实验数据结构及算法：快速排序：Quicksort 类快速排序:public static void quickSort(Eleme nt eleme ntArray,i nt start In dex,i nt endln dex)对子 数组进 行分害U : pub

4、lic static int partition(Element elementArray,int starI ndex,i nt endln dex)输出排序结果： public static void outputResult(Element elementArray)折半查找：SearchEleme nt打印输出结果： public static void PrintResult(int position, int x)查询：public static int Search(int array, int x)存在则返回当前位置，否则返回-1 打印数组中的元素:public static

5、void PrintArray(int array)6实验结果截图:数組中的原始元素如下112233445566查找元素3 2在数组中的位置：是下标：2查找元素三4在数组中的位置：要查找的元素三4不在当箭的数爼中7.实验总结：通过本实验，我了解掌握了快速排序、折半搜索的原理和具体实 现过程，其实只要理解了快速排序、折半搜索算法原理，就可较好的 编程实现快速排序算法。实验二计数基数排序1.实验描述：具体描述见课本10.8节计数排序及10.9节基数排序的实验。2.实验目的：通过计数排序及基数排序问题，更进一步了解排序思想和程序设计思想与技巧。3实验设计思路：基数排序的总体思路就是将待排序数据拆分成

6、多个关键字进行排序，也就是说， 基数排序的实质是多关键字排序。多关键字排序的思路是将待排数据里德排序关键字拆分成多个排序关键字；第1个排序关键字，第2个排序关键字，第3个排序关键字然后，根据子关键字 对待排序数据进行排序。多关键字排序时有两种解决方案：最高位优先法(MSD) (Most Significant Digit first)最低位优先法(LSD)(Least Significant Digit first)4实验环境及工具：操作系统：win7操作系统开发工具：eclipse3.4 jdk1.6开发工具：java5实验数据结构及算法：class MultiKeyRadixSortTes

7、tpublic static void radixSort(int data, int radix, int d) public static void print(int data)实验源码：import java.util.Arrays;public class Mu1tiKeyRadixSortTest public static void main(String args) in t data = new in t 1188,192,221,12,23 ;prin t(data);radixSort(dataj 10; 4);System.out.print1n(” 排序后数组:“);

8、prin t(data);public static void radixSort(i nt data,i nt radixj int d) / /缓存数组in t tmp = new in tdata.1e ngth;/ buckets用于记录待排序元素的信息/ buckets数组定义了 max-min个桶in t buckets = new in tradix;for(i nt i=e,rate=1; id; i+) /重置count数组，开始统计下一个关键字Arrays.fi1l(buckets,O);1将data中的元素完全复制到 tmp数组中System.arraycopy(data

9、j ,tmp,data.1e ngth);/计算每个待排序数据的子关键字for (int j= 8; j data.1e ngth; j+) int subKey = (tmpj 1rate) % radix;buckets subkey+;for (int j= 1; j= e; m-) (int m = data.le ngth- 1;forint subKey = (tmpm /rate) % radix; data-bucketssubKey = tmpm; rate *= radix;public static void print(int data) (inti=e;idata.1

10、e ngth; i+) forSystem.out.pri nt(datai +“ t);System.out.pri nt1n();4.6实验结果截图:exv plain copy print ?1106192 221 1223排序后的数组:1223192 221 11004.7实验总结：通过本实验，自己了解了基数排序的原理和具体实现过程，其实只要理解了基数排序算法原理，就可较好的编程实现基数排序算法。实验二最长公共子序列问题1. 实验描述：具体描述见课本4.3节，最长公共子序列问题。2. 实验目的：通过最长公共子序列问题，巩固并详细分析动态规划思想和解题步骤。3. 实验设计思路：设序列 X

11、=x1,x2, , ,xm和 Y=y1,y2, , ,yn的最长公共子序列为 Z=z1,z2, ,zk， 则(1)若xm=yn，贝U zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。若xm工yn且zk xm，贝U Z是xm-1和Y的最长公共子序列。若xm工yn且zk yn，则Z是X和yn-1的最长公共子序列。由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。 用cij记录序列和的最长公共子序列的长度。其中，Xi=x1,x2, , ,xi ; Yj=y1,y2, , ,yj。当 i=0 或

12、j=0 时，空序列是 Xi 和 Yj 的最长 公共子序列。故此时Cij=0。程序的设计思路是：输入两个字符串，对两个串的存储数组 x， y进行动态分配。调用函数 void IcsLength(char x,char y,int c,int b)，求得最优值;调用函数void lcs(int i,int j,char x,int叩b)构造最长公共子序列调用函数， 最后得出最长公共子序列。4. 实验环境及工具：操作系统：win7操作系统开发工具：eclipse3.4 jdk1.6开发工具：java5. 实验数据结构及算法：Class LCS 类定义resultList来存放结果：public st

13、atic List resultList = new ArrayList();计算最优值：public static void lcsLength(char x,char y,int c,int b) 构造最长公共子序列：public static void lcs(int i,int j,char x,int b) 6实验结果截图：: Problems Javadoc j Dedaratiarr | Q 匚oniole 3、口 口terminated* LCS Java Application E:InstdlISoftwarejavajdkJ i 并羽 | 匪K 国 丁 已yi输入第一串字符系列（披融字7谴诟天亲二卑辜符系列濒数字键1遇出系统）:解得最长公共子系列为土 BHA5XB请倫入第一串字符系列（按数字键丄退岀系绕）:尅 d f 口 Jcit t 匸甘口 niw* 口 请備只第二串字存系列瀕数字键1退