Java教程

20202324 2021-2022-1 《数据结构与面向对象程序设计》实验七报告

本文主要是介绍20202324 2021-2022-1 《数据结构与面向对象程序设计》实验七报告,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

# 20202306 2021-2022-1 《数据结构与面向对象程序设计》实验七报告

课程:《程序设计与数据结构》
班级: 2023
姓名: 肖郅宇
学号:20202324
实验教师:王志强
实验日期:2021年11月12日
必修/选修: 必修

## 1.实验内容

  1. 定义一个Searching和Sorting类,并在类中实现linearSearch,SelectionSort方法,最后完成测试。
    要求不少于10个测试用例,提交测试用例设计情况(正常,异常,边界,正序,逆序),用例数据中要包含自己学号的后四位
    提交运行结果图。

  2. 重构你的代码
    把Sorting.java Searching.java放入 cn.edu.besti.cs2023.(姓名首字母+四位学号) 包中(例如:cn.edu.besti.cs1823.G2301)
    把测试代码放test包中
    重新编译,运行代码,提交编译,运行的截图(IDEA,命令行两种)

  3. 参考http://www.cnblogs.com/maybe2030/p/4715035.html ,学习各种查找算法并在Searching中补充查找算法并测试
    提交运行结果截图

  4. 实现排序方法等(至少3个)
    测试实现的算法(正常,异常,边界)
    提交运行结果截图(如果编写多个排序算法,即使其中三个排序程序有瑕疵,也可以酌情得满分)

  5. 编写Android程序对实现各种查找与排序算法进行测试
    提交运行结果截
    推送代码到码云(选做,额外加分)

## 2. 实验过程及结果
  • 定义一个Searching和Sorting类,并在类中实现linearSearch,SelectionSort方法,最后完成测试。   实验结果截图

 

 

 

 以下为Searching和Sorting类代码

 1 import java.util.Arrays;
 2 
 3 public class Sorting {
 4     public static <T>
 5     String positive(int[] a, int size){
 6         int i, j, tempp = 0;
 7         for(i = 0; i < size; i++){
 8             int temp = a[i];
 9             for(j = i + 1; j < size; j++){
10                 if(a[j] < temp){
11                     temp = a[j];
12                     tempp = j;
13                 }
14             }
15             for(j = tempp; j > i; j--){
16                 a[j] = a[j - 1];
17             }
18             a[i] = temp;
19         }
20         return Arrays.toString(a);
21     }
22 
23     public static <T>
24     String inverse(int[] a, int size){
25         int i, j, tempp = 0;
26         for(i = 0; i < size; i++){
27             int temp = a[i];
28             tempp = i;
29             for(j = i + 1; j < size; j++){
30                 if(a[j] > temp){
31                     temp = a[j];
32                     tempp = j;
33                 }
34             }
35             for(j = tempp; j > i; j--){
36                 a[j] = a[j - 1];
37             }
38             a[i] = temp;
39         }
40         return Arrays.toString(a);
41     }
42 }
 1 public class Searching {
 2     public static <T>
 3 
 4     boolean linearSearch(T[] date,T target){
 5         int index;
 6         date[0] = target;
 7 
 8         for(index = date.length-1; !date[index].equals(target); --index){
 9 
10         }
11         return index == 0 ? false : true;
12     }
13 }

 

以下为测试代码
 1 import junit.framework.TestCase;
 2 import org.junit.jupiter.api.Test;
 3 
 4 import static org.junit.jupiter.api.Assertions.assertEquals;
 5 
 6 public class SortingTest extends TestCase {                 //t1—t5为正序检测,t6-t10为逆序检测
 7     String t1 = "[1, 2, 5, 6, 2324]", t2 = "[1, 23, 2324]", t3 = "[2, 6, 2324]",
 8             t4 = "[1, 52, 2324, 9999]", t5 = "[2, 3, 6, 2324]", t6 = "[2324, 25, 16, 8]",
 9             t7 = "[2324, 9, 8]", t8 = "[2324, 10, 5, 4]", t9 = "[9999, 2324, 22, 6]", t10 = "[2324, 55, 9, 8]";
10 
11     @Test
12     public void test1(){
13         int[] t = {2324,1,5,6,2};
14         assertEquals(t1, Sorting.positive(t, t.length));
15     }
16 
17     @Test
18     public void test2(){
19         int[] t = {1,2324,23};
20         assertEquals(t2, Sorting.positive(t, t.length));
21     }
22 
23     @Test
24     public void test3(){
25         int[] t = {2,6,2324};
26         assertEquals(t3, Sorting.positive(t, t.length));
27     }
28 
29     @Test
30     public void test4(){
31         int[] t = {52,1,9999,2324};
32         assertEquals(t4, Sorting.positive(t, t.length));
33     }
34 
35     @Test
36     public void test5(){
37         int[] t = {2,2324,6,3};
38         assertEquals(t5, Sorting.positive(t, t.length));
39     }
40 
41     @Test
42     public void test6(){
43         int[] t = {25,16,2324,8};
44         assertEquals(t6, Sorting.inverse(t, t.length));
45     }
46 
47     @Test
48     public void test7(){
49         int[] t = {9,2324,8};
50         assertEquals(t7, Sorting.inverse(t, t.length));
51     }
52 
53     @Test
54     public void test8(){
55         int[] t = {2324,10,5,4};
56         assertEquals(t8, Sorting.inverse(t, t.length));
57     }
58 
59     @Test
60     public void test9(){
61         int[] t = {22,2324,9999,6};
62         assertEquals(t9, Sorting.inverse(t, t.length));
63     }
64 
65     @Test
66     public void test10(){
67         int[] t = {2324,55,9,8};
68         assertEquals(t10, Sorting.inverse(t, t.length));
69     }
70 }
 1 import junit.framework.TestCase;
 2 import org.testng.annotations.Test;
 3 
 4 import static org.junit.jupiter.api.Assertions.assertEquals;
 5 
 6 public class SearchingTest extends TestCase {
 7     @Test
 8     public void test1(){                                                            //由于设置了哨兵,所以边界index为1
 9         String[] t1 = {" ", "1", "2", "2324", "3", "4"};
10         assertEquals(true, Searching.linearSearch(t1, "2"));         //正常
11         assertEquals(false, Searching.linearSearch(t1, "0"));        //异常
12         assertEquals(true, Searching.linearSearch(t1, "1"));         //边界
13     }
14 
15     @Test
16     public void test2(){
17         String[] t1 = {"", "nice", "16", "2324", "20", "19"};
18         assertEquals(true, Searching.linearSearch(t1, "2324"));      //正常
19         assertEquals(false, Searching.linearSearch(t1, "111"));      //异常
20         assertEquals(true, Searching.linearSearch(t1, "nice"));      //边界
21     }
22 
23     @Test
24     public void test3(){
25         String[] t1 = {"", "2324", "2323", "2020", "456", "654"};
26         assertEquals(true, Searching.linearSearch(t1, "2020"));      //正常
27         assertEquals(false, Searching.linearSearch(t1, "222"));      //异常
28         assertEquals(true, Searching.linearSearch(t1, "2324"));      //边界
29     }
30 
31     @Test
32     public void test4(){
33         String[] t1 = {"", "11", "22", "33", "44", "2324"};
34         assertEquals(true, Searching.linearSearch(t1, "2324"));      //正常
35         assertEquals(false, Searching.linearSearch(t1, "333"));      //异常
36         assertEquals(true, Searching.linearSearch(t1, "11"));        //边界
37     }
38 
39     @Test
40     public void test5(){
41         String[] t1 = {"", "9", "8", "7", "2324", "6"};
42         assertEquals(true, Searching.linearSearch(t1, "7"));         //正常
43         assertEquals(false, Searching.linearSearch(t1, "444"));      //异常
44         assertEquals(true, Searching.linearSearch(t1, "9"));         //边界
45     }
46     @Test
47     public void test6(){
48         String[] t1 = {"", "44", "789", "26", "2324", "321"};
49         assertEquals(true, Searching.linearSearch(t1, "26"));        //正常
50         assertEquals(false, Searching.linearSearch(t1, "555"));      //异常
51         assertEquals(true, Searching.linearSearch(t1, "44"));        //边界
52     }
53     @Test
54     public void test7(){
55         String[] t1 = {"", "23", "66", "2324", "22", "9"};
56         assertEquals(true, Searching.linearSearch(t1, "66"));        //正常
57         assertEquals(false, Searching.linearSearch(t1, "666"));      //异常
58         assertEquals(true, Searching.linearSearch(t1, "23"));        //边界
59     }
60     @Test
61     public void test8(){
62         String[] t1 = {"", "2323", "16", "2324", "20", "19"};
63         assertEquals(true, Searching.linearSearch(t1, "2324"));      //正常
64         assertEquals(false, Searching.linearSearch(t1, "777"));      //异常
65         assertEquals(true, Searching.linearSearch(t1, "2323"));      //边界
66     }
67     @Test
68     public void test9(){
69         String[] t1 = {"", "566", "665", "1", "2", "2324"};
70         assertEquals(true, Searching.linearSearch(t1, "2"));         //正常
71         assertEquals(false, Searching.linearSearch(t1, "888"));      //异常
72         assertEquals(true, Searching.linearSearch(t1, "566"));       //边界
73     }
74 
75     @Test
76     public void test10(){
77         String[] t1 = {"", "33", "3", "abc", "0", "2324"};
78         assertEquals(true, Searching.linearSearch(t1, "2324"));      //正常
79         assertEquals(false, Searching.linearSearch(t1, "999"));      //异常
80         assertEquals(true, Searching.linearSearch(t1, "33"));        //边界
81     }
82 }
  • 重构你的代码

实验结果截图

 

 

 以下为重构后的类代码

 1 import java.util.Arrays;
 2 
 3 public class Sorting2 {
 4     public static <T>
 5     String positive(int[] a, int size){
 6         int i, j, tempp = 0;
 7         for(i = 0; i < size; i++){
 8             int temp = a[i];
 9             for(j = i + 1; j < size; j++){
10                 if(a[j] < temp){
11                     temp = a[j];
12                     tempp = j;
13                 }
14             }
15             for(j = tempp; j > i; j--){
16                 a[j] = a[j - 1];
17             }
18             a[i] = temp;
19         }
20         return Arrays.toString(a);
21     }
22 
23     public static <T>
24     String inverse(int[] a, int size){
25         int i, j, tempp = 0;
26         for(i = 0; i < size; i++){
27             int temp = a[i];
28             tempp = i;
29             for(j = i + 1; j < size; j++){
30                 if(a[j] > temp){
31                     temp = a[j];
32                     tempp = j;
33                 }
34             }
35             for(j = tempp; j > i; j--){
36                 a[j] = a[j - 1];
37             }
38             a[i] = temp;
39         }
40         return Arrays.toString(a);
41     }
42 }
43 
44 
45 /*
46 import java.util.Arrays;
47 
48 public class Sorting2 {
49     public static <T>
50     String positive(int[] a, int size){
51         int i, j, tempp = 0;
52         for(i = 0; i < size; i++){
53             int temp = a[i];
54             for(j = i + 1; j < size; j++){
55                 if(a[j] < temp){
56                     temp = a[j];
57                     tempp = j;
58                 }
59             }
60             for(j = tempp; j > i; j--){
61                 a[j] = a[j - 1];
62             }
63             a[i] = temp;
64         }
65         return Arrays.toString(a);
66     }
67 
68     public static <T>
69     String inverse(int[] a, int size){
70         int i, j, tempp = 0;
71         for(i = 0; i < size; i++){
72             int temp = a[i];
73             tempp = i;
74             for(j = i + 1; j < size; j++){
75                 if(a[j] > temp){
76                     temp = a[j];
77                     tempp = j;
78                 }
79             }
80             for(j = tempp; j > i; j--){
81                 a[j] = a[j - 1];
82             }
83             a[i] = temp;
84         }
85         return Arrays.toString(a);
86     }
87 } */
 1 public class Searching2 {
 2     public static <T>
 3 
 4     boolean linearSearch(T[] date,T target){
 5         int index;
 6         date[0] = target;
 7 
 8         for(index = date.length-1; !date[index].equals(target); --index){
 9 
10         }
11         return index == 0 ? false : true;
12     }
13 }
14 
15 /*
16 import java.io.Serializable;
17 
18 public class Searching2 {
19     public static <T> Serializable linearSearch(T[] date, T target){
20         int index;
21         date[0] = target;
22 
23         for(index = date.length-1; !date[index].equals(target); --index){
24 
25         }
26         if(index != 0){
27             return "index: " + index;
28         }
29         else {
30             return "not this number";
31         }
32     }
33 }
34 */

 

 以下为测试代码

 1 import junit.framework.TestCase;
 2 
 3 public class SortingTest2 extends TestCase {                 //t1—t5为正序检测,t6-t10为逆序检测
 4     String t1 = "[1, 2, 5, 6, 2316]", t2 = "[1, 23, 2316]", t3 = "[2, 6, 2316]",
 5             t4 = "[1, 52, 2316, 9999]", t5 = "[2, 3, 6, 2316]", t6 = "[2316, 25, 16, 8]",
 6             t7 = "[2316, 9, 8]", t8 = "[2316, 10, 5, 4]", t9 = "[9999, 2316, 22, 6]", t10 = "[2316, 55, 9, 8]";
 7 
 8     public void test1(){
 9         int[] t = {2316,1,5,6,2};
10         assertEquals(t1, Sorting2.positive(t, t.length));
11     }
12 
13     public void test2(){
14         int[] t = {1,2316,23};
15         assertEquals(t2, Sorting2.positive(t, t.length));
16     }
17 
18     public void test3(){
19         int[] t = {2,6,2316};
20         assertEquals(t3, Sorting2.positive(t, t.length));
21     }
22 
23     public void test4(){
24         int[] t = {52,1,9999,2316};
25         assertEquals(t4, Sorting2.positive(t, t.length));
26     }
27 
28     public void test5(){
29         int[] t = {2,2316,6,3};
30         assertEquals(t5, Sorting2.positive(t, t.length));
31     }
32 
33     public void test6(){
34         int[] t = {25,16,2316,8};
35         assertEquals(t6, Sorting2.inverse(t, t.length));
36     }
37 
38     public void test7(){
39         int[] t = {9,2316,8};
40         assertEquals(t7, Sorting2.inverse(t, t.length));
41     }
42 
43     public void test8(){
44         int[] t = {2316,10,5,4};
45         assertEquals(t8, Sorting2.inverse(t, t.length));
46     }
47 
48     public void test9(){
49         int[] t = {22,2316,9999,6};
50         assertEquals(t9, Sorting2.inverse(t, t.length));
51     }
52 
53     public void test10(){
54         int[] t = {2316,55,9,8};
55         assertEquals(t10, Sorting2.inverse(t, t.length));
56     }
57 }
58 
59 
60 /*public class SortingTest2 {                 //t1—t5为正序检测,t6-t10为逆序检测
61 
62     public static void main(String[] args) {
63         int[] t1 = {2316, 1, 5, 6, 2}, t2 = {1, 2316, 23}, t3 = {2, 6, 2316},
64                 t4 = {52, 1, 9999, 2316}, t5 = {2, 2316, 6, 3}, t6 = {25, 16, 2316, 8}, t7 = {9, 2316, 8},
65                 t8 = {2316, 10, 5, 4}, t9 = {22, 2316, 9999, 6}, t10 = {2316, 55, 9, 8};
66         System.out.println(Sorting2.positive(t1, t1.length));
67         System.out.println(Sorting2.positive(t2, t2.length));
68         System.out.println(Sorting2.positive(t3, t3.length));
69         System.out.println(Sorting2.positive(t4, t4.length));
70         System.out.println(Sorting2.positive(t5, t5.length));
71         System.out.println(Sorting2.inverse(t6, t6.length));
72         System.out.println(Sorting2.inverse(t7, t7.length));
73         System.out.println(Sorting2.inverse(t8, t8.length));
74         System.out.println(Sorting2.inverse(t9, t9.length));
75         System.out.println(Sorting2.inverse(t10, t10.length));
76     }
77 }
78                */
 1 import junit.framework.TestCase;
 2 
 3 public class SearchingTest2 extends TestCase {
 4 
 5     public void test1(){                                                            //由于设置了哨兵,所以边界index为1
 6         String[] t1 = {" ", "1", "2", "2316", "3", "4"};
 7         assertEquals(true, Searching2.linearSearch(t1, "2"));         //正常
 8         assertEquals(false, Searching2.linearSearch(t1, "0"));        //异常
 9         assertEquals(true, Searching2.linearSearch(t1, "1"));         //边界
10     }
11 
12     public void test2(){
13         String[] t1 = {"", "nice", "16", "2316", "20", "19"};
14         assertEquals(true, Searching2.linearSearch(t1, "2316"));      //正常
15         assertEquals(false, Searching2.linearSearch(t1, "111"));      //异常
16         assertEquals(true, Searching2.linearSearch(t1, "nice"));      //边界
17     }
18 
19     public void test3(){
20         String[] t1 = {"", "2316", "2323", "2019", "456", "654"};
21         assertEquals(true, Searching2.linearSearch(t1, "2019"));      //正常
22         assertEquals(false, Searching2.linearSearch(t1, "222"));      //异常
23         assertEquals(true, Searching2.linearSearch(t1, "2316"));      //边界
24     }
25 
26     public void test4(){
27         String[] t1 = {"", "11", "22", "33", "44", "2316"};
28         assertEquals(true, Searching2.linearSearch(t1, "2316"));      //正常
29         assertEquals(false, Searching2.linearSearch(t1, "333"));      //异常
30         assertEquals(true, Searching2.linearSearch(t1, "11"));        //边界
31     }
32 
33     public void test5(){
34         String[] t1 = {"", "9", "8", "7", "2316", "6"};
35         assertEquals(true, Searching2.linearSearch(t1, "7"));         //正常
36         assertEquals(false, Searching2.linearSearch(t1, "444"));      //异常
37         assertEquals(true, Searching2.linearSearch(t1, "9"));         //边界
38     }
39 
40     public void test6(){
41         String[] t1 = {"", "44", "789", "26", "2316", "321"};
42         assertEquals(true, Searching2.linearSearch(t1, "26"));        //正常
43         assertEquals(false, Searching2.linearSearch(t1, "555"));      //异常
44         assertEquals(true, Searching2.linearSearch(t1, "44"));        //边界
45     }
46 
47     public void test7(){
48         String[] t1 = {"", "23", "66", "2316", "22", "9"};
49         assertEquals(true, Searching2.linearSearch(t1, "66"));        //正常
50         assertEquals(false, Searching2.linearSearch(t1, "666"));      //异常
51         assertEquals(true, Searching2.linearSearch(t1, "23"));        //边界
52     }
53 
54     public void test8(){
55         String[] t1 = {"", "2323", "16", "2316", "20", "19"};
56         assertEquals(true, Searching2.linearSearch(t1, "2316"));      //正常
57         assertEquals(false, Searching2.linearSearch(t1, "777"));      //异常
58         assertEquals(true, Searching2.linearSearch(t1, "2323"));      //边界
59     }
60 
61     public void test9(){
62         String[] t1 = {"", "566", "665", "1", "2", "2316"};
63         assertEquals(true, Searching2.linearSearch(t1, "2"));         //正常
64         assertEquals(false, Searching2.linearSearch(t1, "888"));      //异常
65         assertEquals(true, Searching2.linearSearch(t1, "566"));       //边界
66     }
67 
68 
69     public void test10(){
70         String[] t1 = {"", "33", "3", "abc", "0", "2316"};
71         assertEquals(true, Searching2.linearSearch(t1, "2316"));      //正常
72         assertEquals(false, Searching2.linearSearch(t1, "999"));      //异常
73         assertEquals(true, Searching2.linearSearch(t1, "33"));        //边界
74     }
75 }
76 
77 /*public class SearchingTest2 {
78 
79     public static void main(String[] args) {
80         String[] t1 = {" ", "1", "2", "2316", "3", "4"};
81         String[] t2 = {" ", "9", "8", "2316", "7", "6"};
82         System.out.println(Searching2.linearSearch(t1, "2"));
83         System.out.println(Searching2.linearSearch(t1, "1"));
84         System.out.println(Searching2.linearSearch(t1, "2316"));
85         System.out.println(Searching2.linearSearch(t1, "4"));
86         System.out.println(Searching2.linearSearch(t1, "99"));
87         System.out.println(Searching2.linearSearch(t2, "9"));
88         System.out.println(Searching2.linearSearch(t2, "2316"));
89         System.out.println(Searching2.linearSearch(t2, "6"));
90         System.out.println(Searching2.linearSearch(t2, "7"));
91         System.out.println(Searching2.linearSearch(t2, "99"));
92     }
93 }
94                    */
  • 参考http://www.cnblogs.com/maybe2030/p/4715035.html ,学习各种查找算法并在Searching中补充查找算法并测试
    提交运行结果截图
  • 实现排序方法等(至少3个)

实验结果截图

 

 

 

 

类代码

 1 public class Sorting3 {
 2     private static int a[];
 3     private static int size;
 4     private static String list="";
 5 
 6     //希尔排序,正序
 7     public static <T>
 8     String shellSort_positive(int[] a){
 9         int temp = a.length / 2;
10         int first, last;
11         while (temp > 0){
12             for (int i = 0; i + temp <= a.length - 1; i++){
13                 first = i;
14                 last = i + temp;
15                 if (a[first] > a[last]){
16                     int temp2 = a[first];
17                     a[first] = a[last];
18                     a[last] = temp2;
19                 }
20             }
21             temp = temp / 2;
22         }
23 
24         String result = "";
25         for (int i = 0; i < a.length;  i++){
26             result = result + a[i] + " ";
27         }
28         return result;
29     }
30 
31     //逆序
32     public static <T>
33     String shellSort_inverse(int[] a){
34         int temp = a.length / 2;
35         int first, last;
36         while (temp > 0){
37             for (int i = 0; i + temp <= a.length - 1; i++){
38                 first = i;
39                 last = i + temp;
40                 if (a[first] < a[last]){
41                     int temp2 = a[first];
42                     a[first] = a[last];
43                     a[last] = temp2;
44                 }
45             }
46             temp = temp / 2;
47         }
48 
49         String result = "";
50         for (int i = 0; i < a.length;  i++){
51             result = result + a[i] + " ";
52         }
53         return result;
54     }
55 }
import java.util.Arrays;

public class Searching3 {

    //顺序查找
    public static <T> boolean linearSearch(T[] date,T target){
        int index;
        date[0] = target;

        for(index = date.length-1; !date[index].equals(target); --index){

        }
        return index == 0 ? false : true;
    }

    //二分查找,递归版本
    //需要升序排列,返回-1表示搜索失败
    public static <T> int BinarySearch2(int a[], int value, int low, int high) {
        int mid = low + (high - low) / 2;
        if(a[mid] == value)
            return mid;
        else if(a[mid] > value)
            return BinarySearch2(a, value, low, mid - 1);
        else if(a[mid] < value)
            return BinarySearch2(a, value, mid + 1, high);
        else return -1;
    }

    //插值查找
    //需要升序排列,返回0表示搜索失败
    public static <T> int InsertionSearch(int a[], int value, int low, int high)
    {
        int mid = low+(value - a[low]) / (a[high] - a[low]) * (high - low);
        if(a[mid] == value)
            return mid;
        else if(a[mid] > value)
            return InsertionSearch(a, value, low, mid-1);
        else if(a[mid] < value)
            return InsertionSearch(a, value, mid+1, high);
        else return 0;
    }

    //斐波那契查找
    //需要升序排列,返回0表示搜索失败
    //先建立斐波那契数组,定义其长度
    public static void Fibonacci(int F[]){
        int maxSize = 20;
        F[0] = 0;
        F[1] = 1;
        for (int i = 2; i < maxSize; i++){
            F[i] = F[i - 1] + F[i - 2];
        }
    }

    //斐波那契查找方法
    public static <T> int fibonacciSearching(int a[], int target, int size){
        int low = 0;
        int high = size - 1;
        int maxSize = 20;

        //创建斐波那契数组
        int F[] = new int[maxSize];
        Fibonacci(F);

        //计算n位于斐波那契数列的位置
        int k = 0;
        while (size > F[k] - 1){
            k++;
        }

        int temp[]= Arrays.copyOf(a, F[k]);         //扩展新的数组,F[k]为新的数组长度,新的数值为默认值0

        for(int i = size; i < F[k] - 1; ++i){
            temp[i] = a[size - 1];
        }

        while(low <= high) {
            int mid = low + F[k - 1] - 1;
            if (target < temp[mid]) {
                high = mid - 1;
                k -= 1;
            } else if (target > temp[mid]) {
                low = mid + 1;
                k -= 2;
            } else {
                if (mid < size)
                    return mid;       //说明mid即为查找到的位置
                else
                    return size - 1; //若mid>=size则说明是扩展的数值,返回size-1
            }
        }
        return -1;
    }

    //分块查找
    //index代表索引数组,t代表待查找数组,keytype代表要查找的元素,m代表每块大小
    public static int blockSearch(int[] index,int[]t,int key,int m){
        int i = search(index,key);    //search函数返回值为带查找元素在第几块
        if(i >= 0){
            int j = m*i;              //j为第i块的第一个元素下标
            int site = (i + 1) * m;
            for( ; j < site; j++){
                if(t[j] == key)
                    return j;
            }
        }
        return -1;
    }
    public static int search(int[]index,int keytype){
        int i;
        for(i = 0; ; i++){
            if(index[i] >= keytype){
                break;
            }
        }
        return i;
    }


    //哈希查找,链表内数据个数需大于11
    public static <T> int shellSearch(int[] a, int key){
        int m = key % 11;
        while(a[m] != key && m < a.length - 1){
            m++;
        }
        if(a[m] != key){
            return -1;
        }
        else{
            return m;
        }
    }
}

测试代码

 1 import junit.framework.TestCase;
 2 import org.junit.Test;
 3 
 4 public class Sorting3Test extends TestCase {               //t1—t5为正序检测,t6-t10为逆序检测
 5     String t1 = "1 2 5 6 2324 ", t2 = "1 23 2324 ", t3 = "2 6 2324 ",
 6             t4 = "1 52 2324 9999 ", t5 = "2 3 6 2324 ", t6 = "2324 25 16 8 ",
 7             t7 = "2324 9 8 ", t8 = "2324 10 5 4 ", t9 = "9999 2324 22 6 ", t10 = "2324 55 9 8 ";
 8 
 9     @Test
10     public void test1(){
11         int[] t = {2324,1,5,6,2};
12         assertEquals(t1, Sorting3.shellSort_positive(t));
13     }
14 
15     @Test
16     public void test2(){
17         int[] t = {1,2324,23};
18         assertEquals(t2, Sorting3.shellSort_positive(t));
19     }
20 
21     @Test
22     public void test3(){
23         int[] t = {2,6,2324};
24         assertEquals(t3, Sorting3.shellSort_positive(t));
25     }
26 
27     @Test
28     public void test4(){
29         int[] t = {52,1,9999,2324};
30         assertEquals(t4, Sorting3.shellSort_positive(t));
31     }
32 
33     @Test
34     public void test5(){
35         int[] t = {2,2324,6,3};
36         assertEquals(t5, Sorting3.shellSort_positive(t));
37     }
38 
39     @Test
40     public void test6(){
41         int[] t = {25,16,2324,8};
42         assertEquals(t6, Sorting3.shellSort_inverse(t));
43     }
44 
45     @Test
46     public void test7(){
47         int[] t = {9,2324,8};
48         assertEquals(t7, Sorting3.shellSort_inverse(t));
49     }
50 
51     @Test
52     public void test8(){
53         int[] t = {2324,10,5,4};
54         assertEquals(t8, Sorting3.shellSort_inverse(t));
55     }
56 
57     @Test
58     public void test9(){
59         int[] t = {22,2324,9999,6};
60         assertEquals(t9, Sorting3.shellSort_inverse(t));
61     }
62 
63     @Test
64     public void test10(){
65         int[] t = {2324,55,9,8};
66         assertEquals(t10, Sorting3.shellSort_inverse(t));
67     }
68 }
 1 import junit.framework.TestCase;
 2 
 3 public class Searching3Test extends TestCase {
 4     public void test_linearSearch(){                                                //由于设置了哨兵,所以边界index为1
 5         String[] t = {" ", "1", "2", "2324", "3", "4"};
 6         assertEquals(true, Searching3.linearSearch(t, "2"));         //正常
 7         assertEquals(false, Searching3.linearSearch(t, "0"));        //异常
 8         assertEquals(true, Searching3.linearSearch(t, "1"));         //边界
 9     }
10 
11     public void test_BinarySearch2(){
12         int[] t = {1, 16, 19, 20, 2324};
13         assertEquals(4, Searching3.BinarySearch2(t, 2324, 0, 4));
14     }
15 
16     public void test_InsertionSearch(){
17         int[] t = {1, 16, 19, 20, 2324};
18         assertEquals(1, Searching3.InsertionSearch(t, 16, 0, 4));
19     }
20 
21     public void test_Fibonacci(){
22         int[] t = {1, 16, 19, 20, 2324};
23         assertEquals(1, Searching3.fibonacciSearching(t, 16, t.length));
24     }
25 
26     public void test_shellSearch(){
27         int[] t = {1, 2, 3, 4, 2324, 11, 99, 16, 19, 20, 23};
28         assertEquals(6, Searching3.shellSearch(t, 99));              //正常
29         assertEquals(-1, Searching3.shellSearch(t, 9999));           //异常
30     }
31 
32     public void test_blockSearch(){
33         int index[]={22,48,86};
34         int[] t = {22, 12, 13, 8, 9, 20,  33, 42, 44, 38, 24, 48,  60, 58, 74, 49, 86, 53};
35         assertEquals(15, Searching3.blockSearch(index, t, 49, 6));       //正常
36         assertEquals(11, Searching3.blockSearch(index, t, 48, 6));       //边界
37     }
38 }
  • 在安卓平台实现

 结果截图

 

## 3. 实验过程中遇到的问题和解决过程


- 问题1:Junit疯狂爆红。
- 问题1解决方案:百度并复习了下Junit的配置方法,这方面的知识忘得挺快的还。
- 问题2:Andriod Studio让我的C盘爆炸了。。
- 问题2解决方案:通过修改环境变量修改了AS的avd下载路径。

## 其他(感悟、思考等)


  AS的用户交互体验极差,插件里的中文插件被下架也就算了,就连最基本的选择模拟器安装位置也不给用户,我的C盘啊

 

 总之AS的操作经过前几次的蹂躏我已经差不多搞清楚了,本次实验难点在于搞清几种排列的方式,并用代码实现,除了细心也没啥好讲的

就这样吧

 

 


## 参考资料

-  [《Java和Andriod开发学习指南(第二版)人民邮电出版社》]

-  [《Java软件结构与数据结构(第三版)清华大学出版社》]

-  https://www.cnblogs.com/maybe2030/p/4715035.html

这篇关于20202324 2021-2022-1 《数据结构与面向对象程序设计》实验七报告的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!