题 目:搜索算法的性能分析与比较

包含完整的论文（字数近4000）+源程序+PPT报告一份，可作为数据结构、数据分析、算法与数据结构等相关课程的课程设计或者大作业；末尾有下载地址

目 录

前言

一、课题来源

1.1课程设计题目

1.2 问题描述

1.3 问题分析

1.4课题内容

二、课题的概要设计和流程

2.1 课题的概要设计

2.2 部分算法的设计流程

三、课题的详细设计

3.1随机生成数据

3.2顺序查找

3.3二分法查找

3.4哈希查找

四、运行与调试

4.1测试结果截图

五、用户手册

六、不足与改进

七、设计心得

八、课程设计项目进度表及任务分配表

8.1组员任务分配表

8.2组员任务安排表

九、参考书目

一、课题来源

—————————————————————————————————

此处省略几百字

—————————————————————————————————

1、 问题描述

（1）顺序表查找的问题描述

顺序查找又称为线性查找，它是一种最简单、最基本的查找方法。从第一个数据开始逐步查找目标元素，找到后计算所用时间，如果没有找到会遍历所有数据后返回所用时间。

（2）折半查找问题描述

折半查找也称为二分查找，作为二分查找对象的数据必须是顺序存储的有序表。如果数据无序则需排序后查找，将目标数据分为两份查找不断缩小目标所在区间直到得到和目标元素相等的元素然后计算出所用时间。

（3）哈希查找的问题描述

哈希表是在关键字和存储位置之间直接建立了映像。哈希函数的“好坏”首先影响出现冲突的频率，假设哈希函数是均匀的，即它对同样一组随机的数据出现冲突的可能性是相同的。因此哈希表的查找效率主要取决于构造哈希表时处理冲突的方法。

（4）比较三种算法搜索的问题描述

对生成的随机数据，可以进行选择一个数查找，三种算法都进行查找，可以得出相对应的搜索时间，然后再对其三种搜索算法所需要的时间进行比较，如若无此数则都返回未找到，但会记录其搜索时间，也可进行比较。

（5）界面设计模块问题描述

设计一个菜单模式界面，让用户可以选择要查找的方式，界面上还有退出按钮，可以退出程序。界面要求简洁明了，便于使用。

（6）按钮动作命令模块问题描述

在设计好图形界面后，就必须对相应的按钮进行事件驱动程序设计。运行Java图形用户界面程序时，程序与用户交互，比如说，在框架中显示多个按钮，当点击按钮时，就会从按钮触发一个事件。同时，查找的操作必须要有输入和输出，则需要使用对话框和命令窗口进行输入关键字和输出结果。

2、问题分析

要完成如下要求：顺序查找、二分查找、哈希查找三者的搜索时间进行比较。本程序的实现需要解决以下几个问题：

（1）如何设计一组随机数据；

（2）如何设计顺序查找的搜索；

（3）如何设计二分查找的搜索；

（4) 如何设计哈希查找的搜索；

（5）如何设计时间记录；

（6）如何让各个程序同时运行正常；

—————————————————————————————————

此处省略几百字

—————————————————————————————————

二、概要设计

2.1 课题的概要设计.

本设计涉及到的数据结构为：散列、顺序搜索、二分法搜索。

2.2 部分算法的设计流程.

三、详细设计

1、查找所需数据

通过自己创建的程序生成的一组随机数据（数据长度可由自己决定，数据大小最大为为数组长度的四分之一，最小即为0。

2、顺序查找

在数据序列中，按照从前往后或者从后往前的顺序依次查找，如果查找到关键字和给定值相等，则返回给定值的位置，查找成功；如果查找值最后一个元素仍未找到，则查找失败。

3 、二分法查找

二分法进行查找时，查找对象的数组必须是有序的，即各数组元素的次序是按其值的大小顺序存储的。

其基本思想是先确定待查数据的范围（可用 [left,right] 区间表示），然后逐步缩小范围直到找到或找不到该记录为止。具体做法是：先取数组中间位置（mid=(left+right)/2）的数据元素与给定值比较。若相等，则查找成功；否则，若给定值比该数据元素的值小（或大），则给定值必在数组的前半部分[left,mid-1]（或后半部分[mid+1,right]），然后在新的查找范围内进行同样的查找。如此反复进行，直到找到数组元素值与给定值相等的元素或确定数组中没有待查找的数据为止。因此，二分查找每查找一次，或成功，或使查找数组中元素的个数减少一半，当查找数组中不再有数据元素时，查找失败。

4、哈希查找—链地址法

将一个哈希值产生冲突关键字放进一个链表里面，某个哈希值产生冲突了，就把这个关键字放到这个哈希值槽的链表里面。Java中的HashMap就是这样解决冲突的。

5、哈希查找—线性探测法

线性探测法中函数是位置i的函数，这相当于当发生冲突的时候，逐个单元甚至回绕查询到一个空单元，也就是说数据都需要放置在这一个表格中，当发生冲突的时候就出发上面的机制，不过这样做，花费的时间是相当多的，这样单元会形成一些区域块，其结果称作为一次聚焦，也就是是说经过多次的查找才能找到一个空的单元：

Hkey（x） = Hkey（n）% 数据长度;

也就是当出现和n重复的hash值的时候，则需要逐个进行探测，因为可以回绕，所以可以只取一个方向继续查找空单元。

四、程序代码

1、顺序查找算法

public class OrderSearch {

    public static String orderSearch(int [] data, int target){
        int len = data.length;
        for(int i = 0; i < len; i++){
            if(data[i] == target){
                System.out.println("找到目标 索引"+i+"目标值"+data[i]);
                return "";
            }
        }
        return "未找到";
    }
}

2、二分查找算法

public class BinarySearch {

    public static String binarySearch(int[] data, int target){
        RandowDataCreate ra = new RandowDataCreate();
        long start = System.currentTimeMillis();
        Arrays.sort(data);
        long end = System.currentTimeMillis();
        double deltaTime = (end-start)*1000;
        int count = 0;
        int l = 0, r = data.length-1;
        int mid = l + r;
        mid = mid/2;
        while(data[mid]!=target){
            if(data[mid] < target){
                l = mid + 1;
            }else if(data[mid] > target){
                r = mid - 1;
            }
            mid = (l + r)/2;
            count++;
            if(l > r){
                return "未找到";
            }
        }
        System.out.println("找到目标 索引"+mid+"目标值"+data[mid]);
        System.out.println("排序耗时"+deltaTime);
        count++;
        String s = "排序耗时"+deltaTime;
        return s;
    }
}

3、哈希查找算法

public class HashSearch {

    private static ArrayList<LinkedList<Integer>> myList = null;

    public static String hashSearch(int[] data, int target){
        int count = 0;
        long s = System.currentTimeMillis();
        count = hashTable(data, data.length);
        long e = System.currentTimeMillis();
        double deltaTime = (e-s)*1000;
        int index = hashCode(target, data.length);
        List<Integer> list = myList.get(index);
        int i = list.indexOf(target);
        if(i==-1){
            System.out.println("未找到元素");
            return "未找到元素";
        }else{
            System.out.println("已找到目标元素:"+list.get(i));
        }
        System.out.println(deltaTime);
        System.out.println("哈希表建表耗时"+deltaTime);
        String msg = "哈希表建表耗时"+deltaTime;
        count+=i;

        return msg;
    }
｝



public class HashSearch2 {

    static Object[] objects;
    RandowDataCreate r = new RandowDataCreate();

    public static void createHashTable(int[] data){
        objects = new Object[data.length];
        int len = data.length;
        for(int i = 0; i < len; i++){
            int value = getValue(data[i]);
            objects[value] = data[i];
        }
    }

    public static String hashSearch2(int[] data, int target){
        long start = System.currentTimeMillis();
        createHashTable(data);
        long end = System.currentTimeMillis();
        int value = getValue(target);
        if((int)objects[value]==target){
            System.out.println(objects[value]);
        }
        double deltaTime = (end-start)*1000;
        String s = "哈希表建表耗时" + deltaTime;
        return s;
    }

    public static int getValue(int key){
        int len = objects.length;
        int value = key%len;
        while(objects[value]!=null){
            if(key==(int)objects[value]){
                break;
            }
            value++;
            if(value>=len){
                value-=len;
            }
        }
        return value;
    }

    @Test
    public void t(){
        int[] nums = r.createData(100);
        String s = r.printInts(nums);
        System.out.println(s);
        hashSearch2(nums, nums[5]);
    }
}

4、测试运行截图（部分）

—————————————————————————————————

此处省略几百字

—————————————————————————————————

五、设计心得

通过课程设计，从刚开始得觉得很难，到最后把这个做出来我们小组付出了很多，也得到了很多。知道编程时要认真仔细，出现错误要及时找出并改正，遇到问题要去查相关的资料。反复的调试程序，最好是多找几个同学来对你的程序进行调试并听其对你的程序的建议，在他们不知道程序怎么写的时候完全以一个用户的身份来用对你的用户界面做一些建议，把各个注意的问题要想到。通过近一周的学习与实践，体验了一下离开课堂的学习，也可以理解为一次实践与理论的很好的连接。特别是本组所做的题目都是课堂上所讲的例子，所以对我们小组的要求就更为严格。实训过程中让我们对懂得的知识做了进一步深入了解,让我们的理解与记忆更深刻，对不懂的知识与不清楚的东西也做了一定的了解,也形成了一定的个人做事风格。通过这次课程设计，让我们小组对一个程序的数据结构有更全面更进一步的认识，也体会到了学以致用、突出自己劳动成果的喜悦心情，也从中发现我们自己平时学习的不足和薄弱环节，从而加以弥补。

—————————————————————————————————

此处省略几百字

—————————————————————————————————

六、下载地址

对应完整的论文+源程序+数据库下载：数据结构课程设计搜索算法的性能分析与比较数据结构与算法课程设计【完整论文+源程序+报告PPT】-算法与数据结构文档类资源-CSDN下载包含完整的论文（字数近4000）+源程序+PPT报告一份，可作为数据结构、数据分析、算法与数据结构等更多下载资源、学习资料请访问CSDN下载频道.

https://download.csdn.net/download/frank2102/65296899