20172329 2018-2019-2 《Java软件结构与数据结构》实验三报告
课程：《Java软件结构与数据结构》
班级： 1723
姓名： 王文彬
学号：20172329
实验教师：王志强
实验日期：2018年11月19日
必修/选修： 必修
一、实验内容
1.1 第一个实验内容
- 要求
- （1）定义一个Searching和Sorting类，并在类中实现linearSearch（教材P162 ）,SelectionSort方法（P169），最后完成测试。
- （2）要求不少于10个测试用例，提交测试用例设计情况（正常，异常，边界，正序，逆序），用例数据中要包含自己学号的后四位
- （3）提交运行结果图。（2分）
1.2 第二个实验内容
- 要求
- （1）重构你的代码把Sorting.java Searching.java放入 cn.edu.besti.cs1723.（姓名首字母+四位学号） 包中（例如：cn.edu.besti.cs1723.G2301）把测试代码放test包中
- （2）重新编译，运行代码，提交编译，运行的截图（IDEA，命令行两种）（2分）
1.3 第三个实验内容
- 要求
- （1）参考http://www.cnblogs.com/maybe2030/p/4715035.html 在Searching中补充查找算法并测试提交运行结果截图(3分）
1.4 第四个实验内容
- 要求
- （1）补充实现课上讲过的排序方法：希尔排序，堆排序，二叉树排序等(至少3个)
- （2）测试实现的算法（正常，异常，边界）提交运行结果截图（3分，如果编写多个排序算法，即使其中三个排序程序有瑕疵，也可以酌情得满分）
1.5 第五个实验内容
- 要求
- （1）编写Android程序对各种查找与排序算法进行测试提交运行结果截图推送代码到码云（加分3，加到实验中）
二、实验过程
2.1 第一个实验过程
过程
- （1）因为之前已经写好过排序和查找的算法，所以不算陌生，就进行了junit测试
结果：
2.2 第二个实验过程
过程
- （1）第二个实验的主要任务是，首先要重构代码，然后重新编译然后进行在虚拟机和idea上进行再一次的测试运行
- 注：学长学姐看这里！！：因为mac电脑本身就是unix系统，是linux系统的进阶版，所以本身的bash和乌班图是一样的，又因为在新电脑中没有安装虚拟机，所以，就在电脑上的bash里直接进行了测试！！
结果：
2.3 第三个实验过程
过程
- 第三个实验应该是我当时花费时间比较长的一个实验了，因为里面涉及补充没有听说过的查找方法：斐波那契额查找。
（1）斐波那契查找
public static boolean fibonacciSearch(int[] table, int keyWord) {
int i = 0;
while (getFibonacci(i) - 1 == table.length) {
i++;
}
int low = 0;
int height = table.length - 1;
while (low <= height) {
int mid = low + getFibonacci(i - 1);
if (table[mid] == keyWord) {
return true;
} else if (table[mid] > keyWord) {
height = mid - 1;
i--;
} else if (table[mid] < keyWord) {
low = mid + 1;
i =i- 2;
}
}
return false;
}
public static int getFibonacci(int n) {
int res = 0;
if (n == 0) {
res = 0;
} else if (n == 1) {
res = 1;
} else {
int first = 0;
int second = 1;
for (int i = 2; i <= n; i++) {
res = first + second;
first = second;
second = res;
}
}
return res;
}
结果：
2.4 第四个实验过程
过程
- （1）第四个实验是补充上课讲过的排序算法，我一共写了堆排序，二叉树排序，希尔排序，这三种新的方法，加上当时学习的选择排序，插入排序，冒泡排序，归并排序，一种七种，其中对于三种新算法进行了编写和测试：
1、堆排序
public static String Heap(Integer[] a){
ArrayHeap q =new ArrayHeap();
String result="";
for (int i =0;i<a.length;i++){
q.addElement(a[i]);
}
for (int i =0;i<a.length;i++){
result+=q.removeMax()+" ";
}
return result;
}
2、希尔排序
public static String xiersort(Integer []arr){
for(int gap=arr.length/2;gap>0;gap/=2){
for(int i=gap;i<arr.length;i++){
int j = i;
while(j-gap>=0 && arr[j]<arr[j-gap]){
swap(arr,j,j-gap);
j-=gap;
}
}
}
return (Arrays.toString(arr));
}
3、二叉树排序
public static String Seachtree(Integer[] a){
LinkedBinarySearchTree c =new LinkedBinarySearchTree();
for (int i =0;i<a.length;i++){
c.addElement(a[i]);
}
String result="";
for (int i =0;i<a.length;i++){
result+=c.removeMin()+" ";
}
return result;
}
结果：
2.5 第五个实验过程
过程
- 这次的实验让我重新拾起了andriod的编写，其中忘记了一些，但是大都还是可以想得起来，所以还OK
结果：
三、 实验过程中遇到的问题和解决过程
- 问题1：主要是在没有了虚拟机，学习了如何在电脑本身的bash上进行命令行操作
- 问题1解决方案：
- 1、首先我们的电脑里必须具有java的jdk，这样我们才可以在bash里输入java时有正确回复；如图1
- 2、然后我们需要找到我们写好的java文件，无论是用vim编辑器还是在文档中写好改为Java文件，我们首先依旧需要将这个文件进行javac的
操作，也就是编译的操作，然后我们就产生了class文件，然后我们就可以继续了。如图2 - 3、在我们准备运行这个class文件的时候，这个我们需要退出到上一级文件进行运行，假如我们进入到这个class文件所在的目录，就会跳出找不到或无法运行的错误，具体原因应该是指定路径设定的问题。如图3
图1
图2
图3
感想
又是接近了期末，自己最近因为事情越来越多，打乱了自己的安排，希望自己可以找到节奏，继续加油！
参考资料
[Data Structure & Algorithm] 七大查找算法
Android Studio的git功能的使用介绍