数据结构与算法学习情境8查找与演示项目开发

《数据结构与算法学习情境8查找与演示项目开发》由会员分享，可在线阅读，更多相关《数据结构与算法学习情境8查找与演示项目开发（126页珍藏版）》请在金锄头文库上搜索。

1、学习情境8 查找与演示项目开发学习情境学习情境8 8 查找与演示工程开发查找与演示工程开发8.1 任务一任务一 认识查找认识查找8.2 任务二任务二 线性表的查找线性表的查找8.3 任务三任务三 二叉排序树查找二叉排序树查找8.4 任务四任务四 哈希表哈希表学习情境8 查找与演示项目开发查找和排序是软件设计中最常用的运算之一，本学习情境主要学习顺序查找、折半查找、分块查找、二叉树排序查找和哈希查找等几种查找的算法实现。为了方便教学，也为了学生能具备综合应用Java的编程技能解决实际问题的能力，有必要开发既有一定代码量、又能解决实际问题的工程。本学习情境根据查找的数据结构和算法，利用Java图形

2、界面开发演示工程，其中提供了折半查找、二叉树排序查找和哈希查找等演示工程。 学习情境8 查找与演示项目开发8.1 任务一任务一 认识查找认识查找查找查找(search)就是在数据集中寻找指定数就是在数据集中寻找指定数据。如日常生活中的查字典、据。如日常生活中的查字典、 号码、图书等，号码、图书等，以及高考考生在考试后通过网络信息系统查询以及高考考生在考试后通过网络信息系统查询成绩和录取情况等。成绩和录取情况等。1查找查找查找：对给定的一个关键字的值，在数据查找：对给定的一个关键字的值，在数据表中搜索出一个关键字的值等于该值的记录或表中搜索出一个关键字的值等于该值的记录或数据。假设找到了指定的数

3、据，那么称之为查数据。假设找到了指定的数据，那么称之为查找成功，通常是返回该数据在查找表中的位置，找成功，通常是返回该数据在查找表中的位置，以便于存取整个数据的信息。假设表中不存在以便于存取整个数据的信息。假设表中不存在指定的数据，这称为查找不成功或查找失败，指定的数据，这称为查找不成功或查找失败，此时一般是返回一个能标识查找失败的值。此时一般是返回一个能标识查找失败的值。学习情境8 查找与演示项目开发2查找表的结构查找表的结构有多种查找表的形式，本学习情境主要介绍三类表有多种查找表的形式，本学习情境主要介绍三类表顺顺序表、二叉树表和哈希表，另外，还涉及索引表结构。显然，序表、二叉树表和哈希表

4、，另外，还涉及索引表结构。显然，不同形式的表对应不同的查找方法，因而查找的时间性能也有不同形式的表对应不同的查找方法，因而查找的时间性能也有所不同。所不同。3查找性能查找性能查找算法的时间性能一般以查找长度来衡量。所谓查找长查找算法的时间性能一般以查找长度来衡量。所谓查找长度，是指查找一个数据所进行的关键字的比较次数。通常情况度，是指查找一个数据所进行的关键字的比较次数。通常情况下，由于各数据的查找长度有所差异，因而常以平均查找长度、下，由于各数据的查找长度有所差异，因而常以平均查找长度、最大查找长度等来衡量查找算法的总的时间性能。最大查找长度等来衡量查找算法的总的时间性能。 学习情境8 查找

5、与演示项目开发8.2 任务二任务二 线性表的查找线性表的查找线性表的查找算法主要有顺序查找、折半线性表的查找算法主要有顺序查找、折半查找和分块查找，分别适用于普通线性表查找和分块查找，分别适用于普通线性表(有有序无序均可序无序均可)、有序顺序表和索引顺序表三种、有序顺序表和索引顺序表三种结构。结构。8.2.1 子任务子任务1 顺序查找顺序查找1顺序查找顺序查找顺序查找：从表的一端开始，依次将每个顺序查找：从表的一端开始，依次将每个数据的关键字与给定值进行比较，假设相等，数据的关键字与给定值进行比较，假设相等，那么查找成功，返回相应位置；假设所有数据那么查找成功，返回相应位置；假设所有数据的关键

6、字与给定值不等，那么返回查找不成功。的关键字与给定值不等，那么返回查找不成功。顺序查找又称为线性查找，是最根本、最顺序查找又称为线性查找，是最根本、最简单的一种查找算法，主要用于数据量较小的简单的一种查找算法，主要用于数据量较小的线性表。线性表。学习情境8 查找与演示项目开发2顺序查找的根本程序实现顺序查找的根本程序实现package ch8Search;import ;public class SequenceSimple public static int Data = 20, 10, 11, 47, 20, 69, 26, 1, 57;public static int Counter

7、= 1; /顺序查找顺序查找学习情境8 查找与演示项目开发 public static boolean Seq_Search(int Key) int i, n;/数组下标变量，数组长度 for (i = 0, n = Data.length; i n; i+) System.out.print( + (int) Datai + ); if (int) Key = (int) Datai) /查找到数据时 return true;/返回true Counter+; return false;/查找不到，返回false 学习情境8 查找与演示项目开发public static void main

8、(String args) (请输入要查找的数据:); Scanner scan = new ); int KeyValue = (); if (Seq_Search(int) KeyValue) (找到该数据，查找次数 = + (int) Counter); else /输出没有找到的数据 (找不到该数据!); 学习情境8 查找与演示项目开发3顺序查找算法分析顺序查找算法分析在等概率情况下，查找成功的平均查找长度为线性表长在等概率情况下，查找成功的平均查找长度为线性表长度的一半，查找不成功的平均查找长度为线性表的长度。假度的一半，查找不成功的平均查找长度为线性表的长度。假设线性表已排序，那么

9、查找不成功的平均查找长度也为线性设线性表已排序，那么查找不成功的平均查找长度也为线性表长度的一半，表长度的一半，ASL(不成功不成功)=(n+1)/2。 学习情境8 查找与演示项目开发8.2.2 子任务子任务2 折半查找折半查找1折半查找折半查找折半查找折半查找(binary search)：要求顺序表已排序，假定从小：要求顺序表已排序，假定从小到大排序到大排序, 从表的中间位置开始比较：从表的中间位置开始比较：(1) 如果当前数据的关键字等于给定值，那么查找成功；如果当前数据的关键字等于给定值，那么查找成功；(2) 如果查找值小于当前数据的关键字，那么在表的前半如果查找值小于当前数据的关键字

10、，那么在表的前半段继续查找；段继续查找；(3) 如果查找值大于当前数据的关键字，那么在表的后半如果查找值大于当前数据的关键字，那么在表的后半段继续查找。段继续查找。以此重复，直到获得查找结果以此重复，直到获得查找结果(表示成功表示成功)，或数据段已空，或数据段已空(表示不成功表示不成功)。折半查找是一种典型的采用分治策略的算法，它将问题分折半查找是一种典型的采用分治策略的算法，它将问题分解为规模更小的子问题，分而治之，逐一解决。解为规模更小的子问题，分而治之，逐一解决。 学习情境8 查找与演示项目开发2折半查找算法分析折半查找算法分析折半查找其实是一棵二叉判定树，树高为折半查找其实是一棵二叉判

11、定树，树高为k=int(lbn)+1，查找成功的比较次数为，查找成功的比较次数为1k次，查找不成功的比较次数为次，查找不成功的比较次数为k-1或或k次，平均查找长度为次，平均查找长度为O(lbn)。在顺序表长度相同的情况下，虽然折半查找算法效率比顺序在顺序表长度相同的情况下，虽然折半查找算法效率比顺序查找算法效率高，但是折半查找算法要求数据必须是已排序查找算法效率高，但是折半查找算法要求数据必须是已排序的。的。顺序查找和折半查找均适用于数据量较小的情况。顺序查找和折半查找均适用于数据量较小的情况。3演示程序的实现演示程序的实现以下程序实现图形界面显示折半查找的过程，文件名为，以下程序实现图形界

12、面显示折半查找的过程，文件名为，代码量为代码量为400行，以下是完整代码行，以下是完整代码(供参考供参考)： 学习情境8 查找与演示项目开发package ch8Search;/图形演示折半查找import ;import ;import ;import ;import .*;import ;import ;import ;import ;import ;import ;学习情境8 查找与演示项目开发import ;import ;import ;import ;import java.awt.Rectangle;import java.awt.Font;public class DemoBi

13、narySearch private JFrame jFrame = null; private JPanel jContentPane = null; private JLabel jLabel2 = null; private JLabel jLabel3 = null; private JLabel jLabel31 = null;学习情境8 查找与演示项目开发 private JLabel jLabel32 = null; private JLabel jLabel33 = null; private JLabel jLabel34 = null; private JLabel jLa

14、bel35 = null; private JLabel jLabel36 = null; private JLabel jLabel37 = null; private JLabel jLabel4 = null; private JTextField jTextField = null; private JButton jButton = null; private JButton jButton1 = null; private JButton jButton2 = null; private JButton jButton3 = null; private JLabel label1

15、= new JLabel8; private int array = 21, 4, 5, 74, 85, 12, 43, 32;学习情境8 查找与演示项目开发 private long time = 0; private Object lock = new Object(); private boolean isMove = false; private int oldx; private Bin_search thread = null; private JLabel jLabel5 = null; private JPanel jPanel = null; private JSlider

16、jSlider = null; private JLabel jLabel = null; private JLabel jLabel1 = null; /二分法查找运行时程序出现的界面框架功能实现学习情境8 查找与演示项目开发 private JFrame getJFrame() if (jFrame = null) jFrame = new JFrame(); ); jFrame.setBounds(new Rectangle(0, 0, 800, 625); jFrame.setContentPane(getJContentPane(); (分块查找图形演示); return jFram

17、e; 学习情境8 查找与演示项目开发 /构造面板 private JPanel getJContentPane() if (jContentPane = null) for (int i = 0; i label1.length; i+) label1i = new JLabel(); label1i.setText(String.valueOf(arrayi); jLabel5 = new JLabel(); jLabel5.setBounds(new Rectangle(14, 165, 30, 37); jLabel5.setDisplayedMnemonic(KeyEvent.VK_U

18、NDEFINED); jLabel5.setText(序号); jLabel4 = new JLabel(); jLabel4.setBounds(new Rectangle(35, 72, 105, 37);学习情境8 查找与演示项目开发 jLabel4.setFont(new Font(Dialog, , 14); jLabel4.setHorizontalAlignment(SwingConstants.CENTER); jLabel4.setText(请输入要查找的数); jLabel37 = new JLabel(); jLabel37.setBounds(new Rectangle

19、(645, 166, 51, 36); jLabel37.setHorizontalAlignment(SwingConstants.CENTER); jLabel37.setFont(new Font(Dialog, , 14); jLabel37.setText(8); jLabel36 = new JLabel(); jLabel36.setBounds(new Rectangle(558, 166, 51, 36); jLabel36.setHorizontalAlignment(SwingConstants.CENTER); jLabel36.setFont(new Font(Dia

20、log, , 14); jLabel36.setText(7); jLabel35 = new JLabel(); jLabel35.setBounds(new Rectangle(478, 166, 51, 36);学习情境8 查找与演示项目开发 jLabel35.setHorizontalAlignment(SwingConstants.CENTER); jLabel35.setFont(new Font(Dialog, , 14); jLabel35.setText(6); jLabel34 = new JLabel(); jLabel34.setBounds(new Rectangle

21、(390, 166, 51, 36); jLabel34.setHorizontalAlignment(SwingConstants.CENTER); jLabel34.setFont(new Font(Dialog, , 14); jLabel34.setText(5); jLabel33 = new JLabel(); jLabel33.setBounds(new Rectangle(302, 166, 51, 36); jLabel33.setHorizontalAlignment(SwingConstants.CENTER); jLabel33.setFont(new Font(Dia

22、log, , 14); jLabel33.setText(4); jLabel32 = new JLabel();学习情境8 查找与演示项目开发 jLabel32.setBounds(new Rectangle(214, 166, 51, 36); jLabel32.setHorizontalAlignment(SwingConstants.CENTER); jLabel32.setFont(new Font(Dialog, , 14); jLabel32.setText(3); jLabel31 = new JLabel(); jLabel31.setBounds(new Rectangle

23、(126, 166, 51, 36); jLabel31.setHorizontalAlignment(SwingConstants.CENTER); jLabel31.setFont(new Font(Dialog, , 14); jLabel31.setText(2); jLabel3 = new JLabel(); jLabel3.setBounds(new Rectangle(38, 166, 51, 36); jLabel3.setHorizontalAlignment(SwingConstants.CENTER); jLabel3.setFont(new Font(Dialog,

24、, 14); jLabel3.setText(1);学习情境8 查找与演示项目开发 jLabel2 = new JLabel(); jLabel2.setBounds(new Rectangle(39, 261, 53, 63); oldx = jLabel2.getX(); jLabel2.setFont(new Font(Dialog, , 36); jLabel2.setHorizontalAlignment(SwingConstants.CENTER); jLabel2.setText(); jLabel2.setVisible(false); label17.setBounds(ne

25、w Rectangle(645, 212, 60, 57); label17.setFont(new Font(Dialog, , 14); label17.setHorizontalAlignment(SwingConstants.CENTER); label16.setBounds(new Rectangle(558, 212, 60, 57); label16.setFont(new Font(Dialog, , 14); label16.setHorizontalAlignment(SwingConstants.CENTER); label15.setBounds(new Rectan

26、gle(471, 212, 60, 57);学习情境8 查找与演示项目开发 label15.setFont(new Font(Dialog, , 14); label15.setHorizontalAlignment(SwingConstants.CENTER); label14.setBounds(new Rectangle(384, 212, 60, 57); label14.setFont(new Font(Dialog, , 14); label14.setHorizontalAlignment(SwingConstants.CENTER); label13.setBounds(new

27、 Rectangle(297, 212, 60, 57); label13.setFont(new Font(Dialog, , 14); label13.setHorizontalAlignment(SwingConstants.CENTER); label12.setBounds(new Rectangle(210, 212, 60, 57); label12.setFont(new Font(Dialog, , 14); label12.setHorizontalAlignment(SwingConstants.CENTER); label11.setBounds(new Rectang

28、le(123, 212, 60, 57); label11.setFont(new Font(Dialog, , 14); label11.setHorizontalAlignment(SwingConstants.CENTER);学习情境8 查找与演示项目开发 label10.setBounds(new Rectangle(36, 212, 60, 57); label10.setFont(new Font(Dialog, , 14); label10.setHorizontalAlignment(SwingConstants.CENTER); jContentPane = new JPan

29、el(); jContentPane.setLayout(null); for (int i = 0; i label1.length; i+) jContentPane.add(label1i, null); jContentPane.add(jLabel2, null); jContentPane.add(jLabel3, null); jContentPane.add(jLabel31, null); jContentPane.add(jLabel32, null); jContentPane.add(jLabel33, null); jContentPane.add(jLabel34,

30、 null);学习情境8 查找与演示项目开发 jContentPane.add(jLabel35, null); jContentPane.add(jLabel36, null); jContentPane.add(jLabel37, null); jContentPane.add(jLabel4, null); jContentPane.add(getJTextField(), null); jContentPane.add(getJButton(), null); jContentPane.add(getJButton1(), null); jContentPane.add(getJBut

31、ton2(), null); jContentPane.add(getJButton3(), null); jContentPane.add(jLabel5, null); jContentPane.add(getJPanel(), null); return jContentPane; 学习情境8 查找与演示项目开发 /输入查找数据的文本框 private JTextField getJTextField() if (jTextField = null) jTextField = new JTextField(); jTextField.setBounds(new Rectangle(153

32、, 74, 177, 37); jTextField.setFont(new Font(Dialog, , 14); return jTextField; 学习情境8 查找与演示项目开发 /查找按钮，事件处理 private JButton getJButton() if (jButton = null) jButton = new JButton(); jButton.setBounds(new Rectangle(361, 76, 112, 34); jButton.setFont(new Font(Dialog, , 14); (查找该数); jButton.addActionListe

33、ner(new () Override public void e) String s = (); if (!() jLabel2.setVisible(false); jLabel2.setLocation(oldx, jLabel2.getY(); jButton1.setEnabled(false);学习情境8 查找与演示项目开发 isMove = true; int searchNum = Integer.parseInt(s); /要查找的数值等于将字符串转换成整形 thread = new Bin_search(searchNum); thread.setDaemon(true);

34、 (); jButton3.setEnabled(true); jButton2.setEnabled(false); ); return jButton; 学习情境8 查找与演示项目开发 /产生随机数按钮 private JButton getJButton1() if (jButton1 = null) jButton1 = new JButton(); jButton1.setBounds(new Rectangle(494, 77, 150, 34); jButton1.setText(产生随机数); jButton1.setFont(new Font(Dialog, Font.ITA

35、LIC, 15); jButton1.addActionListener(new java.awt.event.ActionListener() Override public void e) jLabel2.setVisible(false); jLabel2.setLocation(oldx, jLabel2.getY(); LinkedList list = new LinkedList(); int temp = 0;学习情境8 查找与演示项目开发 for (int i = 0; i label1.length; i+) temp = (int) () * 100); while (l

36、ist.contains(temp) temp = (int) () * 100); list.add(temp); arrayi = temp; label1i.setText(String.valueOf(arrayi); for (int i = 0; i list.size(); i+) System.out.print(list.get(i) + ); System.out.println(); ); return jButton1; 学习情境8 查找与演示项目开发 /继续查找按钮 private JButton getJButton2() if ( jButton2 = null)

37、 jButton2 = new JButton(); jButton2.setBounds(new Rectangle(466, 492, 142, 42); jButton2.setText(继续查找); jButton2.setEnabled(false); jButton2.setFont(new Font(Dialog, , 14); jButton2.addActionListener(new () 学习情境8 查找与演示项目开发 public void e) jButton2.setEnabled(false); jButton3.setEnabled(true); isMove

38、= true; Bin_notifly(); ); return jButton2; 学习情境8 查找与演示项目开发 /暂停查找按钮 private JButton getJButton3() if (jButton3 = null) jButton3 = new JButton(); jButton3.setBounds(new Rectangle(615, 492, 127, 42); jButton3.setText(暂停查找); jButton3.setEnabled(false); jButton3.setFont(new Font(Dialog, , 14) /暂停查找的按钮字体为

39、粗体字 jButton3.addActionListener(new () public void e) jButton2.setEnabled(true);学习情境8 查找与演示项目开发 jButton3.setEnabled(false); isMove = false; ); return jButton3; /速度调节器 private JPanel getJPanel() if ( jPanel = null) jLabel1 = new JLabel(); jLabel1.setText(慢); jLabel1.setFont(new Font(Dialog, , 14);学习情境

40、8 查找与演示项目开发 jLabel = new JLabel(); (快); jLabel.setFont(new Font(Dialog, , 18); jPanel = new JPanel(); jPanel.setLayout(new FlowLayout(); jPanel.setBounds(new Rectangle(49, 461, 297, 70); jPanel.setBorder(BorderFactory.createTitledBorder(null, u901fu5ea6u8c03u8282, TitledBorder.DEFAULT_JUSTIFICATION,

41、 , new Font(Dialog, , 12), new Color(51, 51, 51); jPanel.add(jLabel, null); jPanel.add(getJSlider(), null); jPanel.add(jLabel1, null); return jPanel; 学习情境8 查找与演示项目开发 /滑动块 private JSlider getJSlider() if ( jSlider = null) jSlider = new JSlider(); time = (); jSlider.addChangeListener(new () Override p

42、ublic void e) time = (); ); return jSlider; 学习情境8 查找与演示项目开发 public static void main(String args) /多线程 SwingUtilities.invokeLater(new Runnable() Override public void run() DemoBinarySearch application = new DemoBinarySearch(); application.getJFrame().setVisible(true); ); 学习情境8 查找与演示项目开发 public void s

43、leeping(long time) try Thread.sleep(time); catch (InterruptedException e) (); public void Bin_wait() synchronized (lock) try (); catch (Exception e) (); 学习情境8 查找与演示项目开发 public void Bin_notifly() synchronized (lock) (); public void move() if (!isMove) Bin_wait(); 学习情境8 查找与演示项目开发 class Bin_search exte

44、nds Thread private int searchNum = 0; private int x; public Bin_search(int searchNum) = searchNum; x = jLabel2.getX(); public void sort() Arrays.sort(array); for (int i = 0; i ; i+) label1i.setText(String.valueOf(arrayi); 学习情境8 查找与演示项目开发 Override public void run() sort(); int mid = 0, low = 0, high

45、= 7; jLabel2.setVisible(true); while (low = high) move(); mid = (low + high) / 2; System.out.println(mid= + mid); jLabel2.setLocation(x + mid * 87, jLabel2.getY(); sleeping(7 * time); if (searchNum = arraymid) (恭喜！您要查找的数值找到啦！); break;学习情境8 查找与演示项目开发 else if (searchNum high) JOptionPane.showMessageDi

46、alog(null, 很遗憾，没有找到。); 学习情境8 查找与演示项目开发 jButton1.setEnabled(true); jButton2.setEnabled(false); jButton3.setEnabled(false); 8.2.3 子任务3 分块索引查找1分块索引查找在许多情况下，可能会遇到这样的表，整个表中的数据未必(递增或递减)有序，但划分为假设干块后，每一块中的所有数据均小于(或大于)其后面块中的数据。这种特性称为分块有序。 学习情境8 查找与演示项目开发对于分块有序表的查找，显然不能采用二分查找方法，但如果采用简单顺序查找方法查找，又因为没有充分利用所给出的条件

47、而浪费时间。针对这种情况，可为该顺序表建一个索引表，索引表中为每一块设置一索引项，每一索引项包括两个局部：该块的起始地址和该块中最大(或最小)关键字的值(或者是所限定的最大(小)关键字)。将这些索引项按顺序排列成一有序表，即为索引表。显然，索引表是按关键字递增或递减次序排列的。图8-1所示是分块索引查找的演示界面。学习情境8 查找与演示项目开发图8-1 分块索引查找的演示界面 学习情境8 查找与演示项目开发2分块索引查找算法分块索引查找算法分块索引查找算法如下：分块索引查找算法如下：(1) 在索引表中查找以确定数据所在的块。在索引表中查找以确定数据所在的块。(2) 在所确定的块中进行查找。在所

48、确定的块中进行查找。由于索引表是按关键字递增由于索引表是按关键字递增(或递减或递减)有序的，因此在索引有序的，因此在索引表的查找即可采用简单顺序方式查找，也可以采用二分查找，表的查找即可采用简单顺序方式查找，也可以采用二分查找，这要取决于索引表的项数：如果项数过多，那么采用二分查找这要取决于索引表的项数：如果项数过多，那么采用二分查找是适宜的，否那么采用顺序查找就可以了。在块内的查找，由是适宜的，否那么采用顺序查找就可以了。在块内的查找，由于块内数据的无序而只能采用简单顺序查找。于块内数据的无序而只能采用简单顺序查找。学习情境8 查找与演示项目开发3分块索引查找算法分析分块索引查找算法分析这种

49、带有索引的分块有序查找的时间性能取决于两步查找时间之和：如前所述，第一步可用简单方式和二分查找方法之一进行，第二步只能采用简单顺序查找，但由于子表长度较原来长度小，因此，其时间性能介于顺序查找和二分查找之间。 学习情境8 查找与演示项目开发8.3 任务三任务三 二叉排序树查找二叉排序树查找在一棵二叉树中查找一个节点，需要在遍在一棵二叉树中查找一个节点，需要在遍历二叉树的过程中对节点逐个进行比较。历二叉树的过程中对节点逐个进行比较。8.3.1 子任务子任务1 认识二叉排序树查找认识二叉排序树查找有序表中采用二分查找算法查找的速度是有序表中采用二分查找算法查找的速度是比较快的，但也存在问题：假设要

50、在其中插入比较快的，但也存在问题：假设要在其中插入或删除数据，那么需要移动表中所有的后续数或删除数据，那么需要移动表中所有的后续数据以保持其有效性。假设这种插入和删除是经据以保持其有效性。假设这种插入和删除是经常性的运算，那么较浪费时间。为此，可采用常性的运算，那么较浪费时间。为此，可采用动态链表结构，二叉排序树便是一种适宜的结动态链表结构，二叉排序树便是一种适宜的结构。构。学习情境8 查找与演示项目开发1二叉排序树二叉排序树二叉排序树二叉排序树(binary sort tree)可以是一棵空树或者具有以可以是一棵空树或者具有以下性质：下性质：(1) 每个节点都有一个作为查找依据的关键字，所有

51、节点每个节点都有一个作为查找依据的关键字，所有节点的关键字互不相同。的关键字互不相同。(2) 假设一个节点的左子树不空，那么左子树上所有节点假设一个节点的左子树不空，那么左子树上所有节点的关键字均为小于这个节点的键值。的关键字均为小于这个节点的键值。(3) 假设一个节点的右子树不空，那么右子树上所有节点假设一个节点的右子树不空，那么右子树上所有节点的关键字均为大于这个节点的键值。的关键字均为大于这个节点的键值。(4) 每个节点的左、右子树也分别为二叉排序法。每个节点的左、右子树也分别为二叉排序法。对二叉排序树按中根次序遍历，可得到按升序排列的关对二叉排序树按中根次序遍历，可得到按升序排列的关键

52、字序列。键字序列。学习情境8 查找与演示项目开发2二叉排序树查找二叉排序树查找在一棵二叉排序树中，查找值为在一棵二叉排序树中，查找值为key的节点：的节点：(1) 从根节点开始，设从根节点开始，设p指向根节点。指向根节点。(2) 将将key与与p节点的关键字进行比较，假设两者相等，那节点的关键字进行比较，假设两者相等，那么查找成功；假设么查找成功；假设key值较小，那么在值较小，那么在p的左子树中继续查找；的左子树中继续查找；假设假设key值较大，那么在值较大，那么在p的右子树中继续查找。的右子树中继续查找。(3) 重复执行上一步，直到查找成功或重复执行上一步，直到查找成功或p为空，假设为空，

53、假设p为为空，那么查找不成功。空，那么查找不成功。学习情境8 查找与演示项目开发3二叉排序树的查找性能分析二叉排序树的查找性能分析在一棵具有在一棵具有n个节点的二叉排序树中查找一个节点，一次个节点的二叉排序树中查找一个节点，一次成功的查找恰好走过一条从根节点到该节点的路径，比较次数成功的查找恰好走过一条从根节点到该节点的路径，比较次数为该节点的层次为该节点的层次level(1levelk，k为这棵二叉排序树的高度为这棵二叉排序树的高度)。因此，二叉排序树查找成功的平均查找长度因此，二叉排序树查找成功的平均查找长度ASL不超过二叉树不超过二叉树的高度。的高度。二叉树的高度与二叉树的形态有关，二叉

54、树的高度与二叉树的形态有关，n个节点的完全二叉个节点的完全二叉树的高度最小，高度为树的高度最小，高度为int(lbn)+1；n个节点的单支二叉树的个节点的单支二叉树的高度最大，高度为高度最大，高度为n。因此二叉树的高度范围是。因此二叉树的高度范围是lbn+1n。学习情境8 查找与演示项目开发8.3.2 子任务子任务2 二叉排序树查找的图形演示工程二叉排序树查找的图形演示工程以下是二叉排序树的查找图形演示过程，文件名为，代码以下是二叉排序树的查找图形演示过程，文件名为，代码量为量为570行，以下是完整代码行，以下是完整代码(供参考供参考)：package ch8Search;/图形演示图形演示二

55、叉排序树查找二叉排序树查找import ;import ;import ;import ;import ;import ;import ;学习情境8 查找与演示项目开发import ;import ;import ;import ;import ;import ;import ;import ;import ;import .*;import ;import ;import ;import ;import ;学习情境8 查找与演示项目开发public class DemoBiTreeSearch private JFrame jFrame = null; private JPanel jCon

56、tentPane = null; private JLabel jLabel15 = null; private JLabel jLabel151 = null; private JLabel jLabel152 = null; private JLabel jLabel153 = null; private JLabel jLabel154 = null; private JLabel jLabel155 = null; private JLabel jLabel156 = null; private JLabel jLabel17 = null; private JTextField jT

57、extField = null; private JButton jButton = null; private JScrollPane jScrollPane = null;学习情境8 查找与演示项目开发 private JList jList = null; private JLabel jLabel18 = null; private JLabel jLabel = new JLabel15; private int s = 3, 4, 1, 6, 5, 11, 31, 12, 9, 10, 2, 13, 32, 15, 14; private long time = 500L; pri

58、vate DefaultListModel lItemsForList1; private JLabel jLabel157 = null; private JLabel jLabel158 = null; private JLabel jLabel159 = null; private JLabel jLabel1510 = null; private JLabel jLabel1511 = null; private JLabel jLabel1512 = null; private JLabel jLabel1513 = null; private JButton jButton1 =

59、null;学习情境8 查找与演示项目开发 private JPanel jPanel = null; private JLabel jLabel1 = null; private JSlider jSlider = null; private JLabel jLabel2 = null; /界面设计框架的实现 private JFrame getJFrame() if (jFrame = null) jFrame = new JFrame(); jFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); jFrame.setBounds(new

60、 Rectangle(0, 0, 800, 800); jFrame.setContentPane(getJContentPane(); jFrame.setTitle(Application); return jFrame; 学习情境8 查找与演示项目开发 /初始化面板 private JPanel getJContentPane() if (jContentPane = null) for (int i = 0; i jLabel.length; i+) jLabeli = new JLabel(); jLabel18 = new JLabel(); jLabel18.setBounds(

61、new Rectangle(517, 23, 86, 32); jLabel18.setText(对照列表如有右所示); jLabel17 = new JLabel(); jLabel17.setBounds(new Rectangle(87, 25, 97, 37); jLabel17.setHorizontalAlignment(SwingConstants.CENTER); jLabel17.setText(请输入您要查找的数值：);学习情境8 查找与演示项目开发 jLabel1513 = new JLabel(); jLabel1513.setBounds(new Rectangle(

62、664, 366, 37, 31); jLabel1513.setHorizontalAlignment(SwingConstants.CENTER); jLabel1513.setFont(new Font(Dialog, , 18); jLabel1513.setText(); jLabel1512 = new JLabel(); jLabel1512.setBounds(new Rectangle(584, 367, 46, 33); jLabel1512.setHorizontalAlignment(SwingConstants.CENTER); jLabel1512.setFont(

63、new Font(Dialog, , 18); jLabel1512.setText(); jLabel1511 = new JLabel(); jLabel1511.setBounds(new Rectangle(476, 365, 41, 36); jLabel1511.setHorizontalAlignment(SwingConstants.CENTER); jLabel1511.setFont(new Font(Dialog, , 18);学习情境8 查找与演示项目开发 jLabel1511.setText(); jLabel1510 = new JLabel(); jLabel15

64、10.setBounds(new Rectangle(402, 370, 39, 28); jLabel1510.setHorizontalAlignment(SwingConstants.CENTER); jLabel1510.setFont(new Font(Dialog, , 18); jLabel1510.setText(); jLabel159 = new JLabel(); jLabel159.setBounds(new Rectangle(284, 374, 58, 28); jLabel159.setHorizontalAlignment(SwingConstants.CENT

65、ER); jLabel159.setFont(new Font(Dialog, , 18); jLabel159.setText(); jLabel158 = new JLabel();学习情境8 查找与演示项目开发 jLabel158.setBounds(new Rectangle(218, 374, 49, 27); jLabel158.setHorizontalAlignment(SwingConstants.CENTER); jLabel158.setFont(new Font(Dialog, , 18); jLabel158.setText(); jLabel157 = new JL

66、abel(); jLabel157.setBounds(new Rectangle(136, 368, 41, 33); jLabel157.setHorizontalAlignment(SwingConstants.CENTER); jLabel157.setFont(new Font(Dialog, , 18); jLabel157.setText(); jLabel156 = new JLabel(); jLabel156.setBounds(new Rectangle(48, 372, 49, 30); jLabel156.setHorizontalAlignment(SwingCon

67、stants.CENTER); jLabel156.setFont(new Font(Dialog, , 18); jLabel156.setText();学习情境8 查找与演示项目开发 jLabel155 = new JLabel(); jLabel155.setBounds(new Rectangle(559, 269, 58, 40); jLabel155.setHorizontalAlignment(SwingConstants.CENTER); jLabel155.setFont(new Font(Dialog, , 18); jLabel155.setText(); jLabel1

68、54 = new JLabel(); jLabel154.setBounds(new Rectangle(454, 270, 48, 34); jLabel154.setHorizontalAlignment(SwingConstants.CENTER); jLabel154.setFont(new Font(Dialog, , 18); jLabel154.setText(); jLabel153 = new JLabel(); jLabel153.setBounds(new Rectangle(212, 284, 64, 24); jLabel153.setHorizontalAlignm

69、ent(SwingConstants.CENTER); jLabel153.setFont(new Font(Dialog, , 18);学习情境8 查找与演示项目开发 jLabel153.setText(); jLabel152 = new JLabel(); jLabel152.setBounds(new Rectangle(120, 284, 65, 22); jLabel152.setHorizontalAlignment(SwingConstants.CENTER); jLabel152.setFont(new Font(Dialog, , 18); jLabel152.setTex

70、t(); jLabel151 = new JLabel(); jLabel151.setBounds(new Rectangle(439, 174, 50, 44); jLabel151.setHorizontalAlignment(SwingConstants.CENTER); jLabel151.setFont(new Font(Dialog, , 18); jLabel151.setText(); jLabel15 = new JLabel(); jLabel15.setBounds(new Rectangle(228, 175, 47, 29);学习情境8 查找与演示项目开发 jLab

71、el15.setHorizontalAlignment(SwingConstants.CENTER); jLabel15.setFont(new Font(Dialog, , 18); jLabel15.setText(); jLabel14.setBounds(new Rectangle(676, 401, 76, 44); jLabel14.setHorizontalAlignment(SwingConstants.CENTER); jLabel14.setText(O); jLabel14.setFont(new Font(Dialog, , 18); jLabel13.setBound

72、s(new Rectangle(550, 402, 76, 44); jLabel13.setHorizontalAlignment(SwingConstants.CENTER); jLabel13.setText(N); jLabel13.setFont(new Font(Dialog, , 18); jLabel12.setBounds(new Rectangle(466, 401, 76, 44); jLabel12.setHorizontalAlignment(SwingConstants.CENTER); jLabel12.setText(M);学习情境8 查找与演示项目开发 jLa

73、bel12.setFont(new Font(Dialog, , 18); jLabel11.setBounds(new Rectangle(374, 401, 76, 44); jLabel11.setHorizontalAlignment(SwingConstants.CENTER); jLabel11.setText(L); jLabel11.setFont(new Font(Dialog, , 18); jLabel10.setBounds(new Rectangle(297, 401, 76, 44); jLabel10.setHorizontalAlignment(SwingCon

74、stants.CENTER); jLabel10.setText(K); jLabel10.setFont(new Font(Dialog, , 18); jLabel9.setBounds(new Rectangle(197, 401, 76, 44); jLabel9.setHorizontalAlignment(SwingConstants.CENTER); jLabel9.setText(J); jLabel9.setFont(new Font(Dialog, , 18); jLabel8.setBounds(new Rectangle(123, 401, 76, 44);学习情境8

75、查找与演示项目开发 jLabel8.setHorizontalAlignment(SwingConstants.CENTER); jLabel8.setText(I); jLabel8.setFont(new Font(Dialog, , 18); jLabel7.setBounds(new Rectangle(20, 401, 76, 44); jLabel7.setHorizontalAlignment(SwingConstants.CENTER); jLabel7.setText(H); jLabel7.setFont(new Font(Dialog, , 18); jLabel6.se

76、tBounds(new Rectangle(602, 318, 76, 44); jLabel6.setHorizontalAlignment(SwingConstants.CENTER); jLabel6.setText(G); jLabel6.setFont(new Font(Dialog, , 18); jLabel5.setBounds(new Rectangle(417, 318, 76, 44); jLabel5.setHorizontalAlignment(SwingConstants.CENTER); jLabel5.setText(F);学习情境8 查找与演示项目开发 jLa

77、bel2.setBounds(new Rectangle(504, 216, 76, 44); jLabel2.setHorizontalAlignment(SwingConstants.CENTER); jLabel2.setText(C); jLabel2.setFont(new Font(Dialog, , 18); jLabel4.setBounds(new Rectangle(248, 317, 76, 44); jLabel4.setHorizontalAlignment(SwingConstants.CENTER); jLabel4.setText(E); jLabel4.set

78、Font(new Font(Dialog, Font.BOLD, 18); jLabel3.setBounds(new Rectangle(82, 318, 76, 44); jLabel3.setHorizontalAlignment(SwingConstants.CENTER); jLabel3.setText(D); jLabel3.setFont(new Font(Dialog, Font.BOLD, 18); jLabel1.setBounds(new Rectangle(170, 216, 76, 44); jLabel1.setHorizontalAlignment(SwingC

79、onstants.CENTER); jLabel1.setText(B);学习情境8 查找与演示项目开发 jLabel1.setFont(new Font(Dialog, Font.BOLD, 18); jLabel0.setBounds(new Rectangle(320, 110, 76, 44); jLabel0.setHorizontalAlignment(SwingConstants.CENTER); jLabel0.setText(A); jLabel0.setFont(new Font(Dialog, Font.BOLD, 18); jContentPane = new JPan

80、el(); jContentPane.setLayout(null); jContentPane.add(jLabel0, null); jContentPane.add(jLabel1, null); jContentPane.add(jLabel2, null); jContentPane.add(jLabel3, null); jContentPane.add(jLabel4, null); jContentPane.add(jLabel5, null);学习情境8 查找与演示项目开发 jContentPane.add(jLabel6, null); jContentPane.add(j

81、Label7, null); jContentPane.add(jLabel8, null); jContentPane.add(jLabel9, null); jContentPane.add(jLabel10, null); jContentPane.add(jLabel11, null); jContentPane.add(jLabel12, null); jContentPane.add(jLabel13, null); jContentPane.add(jLabel14, null); jContentPane.add(jLabel15, null); jContentPane.ad

82、d(jLabel151, null); jContentPane.add(jLabel152, null); jContentPane.add(jLabel153, null);学习情境8 查找与演示项目开发 jContentPane.add(jLabel154, null); jContentPane.add(jLabel155, null); jContentPane.add(jLabel156, null); jContentPane.add(jLabel157, null); jContentPane.add(jLabel158, null); jContentPane.add(jLa

83、bel159, null); jContentPane.add(jLabel1510, null); jContentPane.add(jLabel1511, null); jContentPane.add(jLabel1512, null); jContentPane.add(jLabel1513, null); jContentPane.add(jLabel17, null); jContentPane.add(getJTextField(), null); jContentPane.add(getJButton(), null); jContentPane.add(getJScrollP

84、ane(), null); jContentPane.add(jLabel18, null);学习情境8 查找与演示项目开发 jContentPane.add(getJButton1(), null); jContentPane.add(getJPanel(), null); return jContentPane; class DigitDocument extends PlainDocument private static final long serialVersionUID = 1L; Override学习情境8 查找与演示项目开发 public void insertString(

85、int offset, String s, AttributeSet a) char c = s.charAt(0); if (c = 0) try super.insertString(offset, s, a); catch (BadLocationException e) JOptionPane.showMessageDialog(null, 错误: + (); 学习情境8 查找与演示项目开发 /初始化文本框 private JTextField getJTextField() if (jTextField = null) jTextField = new JTextField(); D

86、igitDocument document = new DigitDocument(); jTextField.setDocument(document); jTextField.setBounds(new Rectangle(193, 26, 165, 39); jTextField.setFont(new Font(Dialog, , 18);/字体为粗体，大小为18 return jTextField; 学习情境8 查找与演示项目开发 /查找初始化及事件响应 private JButton getJButton() if (jButton = null) jButton = new JB

87、utton(); jButton.setBounds(new Rectangle(376, 25, 112, 36); jButton.setFont(new Font(Dialog, , 18);/字体以罗马字体为基准 (查找); jButton.addActionListener(new () 学习情境8 查找与演示项目开发 public void e) /初始化 for (int i = 0; i jLabel.length; i+) ); int tom = new int15; String temp = null; for (int j = 0; j ; j+) temp = (S

88、tring) lItemsForList1.get(j); tomj = Integer.parseInt(temp.substring(6, (); 学习情境8 查找与演示项目开发 String find = (); if (!() MyThread thread = new MyThread(tom); thread.setDaemon(true); (); ); return jButton; 学习情境8 查找与演示项目开发 /滚动条 private JScrollPane getJScrollPane() if (jScrollPane = null) jScrollPane = ne

89、w JScrollPane(); jScrollPane.setBounds(new Rectangle(627, 17, 149, 254); jScrollPane.setViewportView(getJList(); return jScrollPane; 学习情境8 查找与演示项目开发 /数据及字母对应列表 private JList getJList() if (jList = null) lItemsForList1 = new DefaultListModel(); jList = new JList(); String list = new String15; Arrays.

90、sort(s); int k = 7; list0 = jLabelk.getText() + - + s0; list1 = jLabelk / 2.getText() + - + s1; list2 = jLabelk + 1.getText() + - + s2; k = k / 2; /k=3学习情境8 查找与演示项目开发 list3 = jLabelk / 2.getText() + - + s3; list4 = jLabel(k + 1) * 2 + 1.getText() + - + s4; k+; /k=4 /从0开始，所以多加1 list5 = jLabelk.getTex

91、t() + - + s5; list6 = jLabelk * 2 + 2.getText() + - + s6; k = (k - 1) / 2; /k=1; list7 = jLabelk / 2.getText() + - + s7; /下面是右子树 k = 14; list8 = jLabelk.getText() + - + s14; list9 = jLabelk / 2 - 1.getText() + - + s13; list10 = jLabelk - 1.getText() + - + s12;学习情境8 查找与演示项目开发 k = k / 2 - 1; /k=6 list

92、11 = jLabelk / 2 - 1.getText() + - + s11; list12 = jLabel(k - 1) * 2 + 2.getText() + - + s10; k-; /k=5 list13 = jLabelk.getText() + - + s9; list14 = jLabelk * 2 + 1.getText() + - + s8; Arrays.sort(list); for (int i = 0; i list.length; i+) System.out.println(a); lItemsForList1.addElement(listi); jLis

93、t.setModel(lItemsForList1); return jList; 学习情境8 查找与演示项目开发 /产生随机数按钮 private JButton getJButton1() if (jButton1 = null) jButton1 = new JButton(); jButton1.setBounds(new Rectangle(376, 66, 142, 40); jButton1.setText(产生随机数); jButton1.setFont(new Font(Dialog, Font.ROMAN_BASELINE, 18); jButton1.addActionL

94、istener(new java.awt.event.ActionListener() 学习情境8 查找与演示项目开发 public void e) LinkedList list = new LinkedList(); int temp = 0; for (int i = 0; i ; i+) temp = (int) () * 100); while (list.contains(temp) temp = (int) () * 100); list.add(temp); si = temp; /label1i.setText(String.valueOf(arrayi); 学习情境8 查找

95、与演示项目开发 arrange(); for (int i = 0; i (); i+) System.out.print(list.get(i) + ); (); ); return jButton1; 学习情境8 查找与演示项目开发 /数组 public void arrange() lItemsForList1 = new DefaultListModel(); jList = getJList(); String list = new String15; Arrays.sort(s); int k = 7; list0 = jLabelk.getText() + - + s0; lis

96、t1 = jLabelk / 2.getText() + - + s1; list2 = jLabelk + 1.getText() + - + s2; k = k / 2; /k=3 list3 = jLabelk / 2.getText() + - + s3;学习情境8 查找与演示项目开发 list4 = jLabel(k + 1) * 2 + 1.getText() + - + s4; k+; /k=4 /从0开始，所以多加1 list5 = jLabelk.getText() + - + s5; list6 = jLabelk * 2 + 2.getText() + - + s6; k

97、 = (k - 1) / 2; /k=1; list7 = jLabelk / 2.getText() + - + s7; /下面是右子树 k = 14; list8 = jLabelk.getText() + - + s14; list9 = jLabelk / 2 - 1.getText() + - + s13; list10 = jLabelk - 1.getText() + - + s12; 学习情境8 查找与演示项目开发 k = k / 2 - 1; /k=6 list11 = jLabelk / 2 - 1.getText() + - + s11; list12 = jLabel(

98、k - 1) * 2 + 2.getText() + - + s10; k-; /k=5 list13 = jLabelk.getText() + - + s9; list14 = jLabelk * 2 + 1.getText() + - + s8; Arrays.sort(list); for (int i = 0; i si) /从0开始 i = i * 2 + 2; else if (h = ) break; if (i & h = si) ); /查到的数字颜色为蓝绿色 try Thread.sleep(time); catch (InterruptedException e1) )

99、; ); try Thread.sleep(time);学习情境8 查找与演示项目开发 catch (InterruptedException e1) ); ); JOptionPane.showMessageDialog(jLabeli, + 恭喜哦！您要查找的数值找到了。); else JOptionPane.showMessageDialog(null, 抱歉哦！没有找到您要查找的数值。); 学习情境8 查找与演示项目开发8.4 任务四任务四 哈希表哈希表在一个数据结构中查找给定数据，用前述在一个数据结构中查找给定数据，用前述的几种查找算法都需要经过一系列关键字比较的几种查找算法都需要经

100、过一系列关键字比较才能得到查找结果，平均查找长度与数据量有才能得到查找结果，平均查找长度与数据量有关，数据越多，比较次数就越多。而每个数据关，数据越多，比较次数就越多。而每个数据的比较次数由该数据在数据结构中的位置决定，的比较次数由该数据在数据结构中的位置决定，与数据的关键字无关。与数据的关键字无关。如果根据数据的关键字就能够知道该数据如果根据数据的关键字就能够知道该数据的存储位置，那么只要花费的存储位置，那么只要花费O(1)时间就能得时间就能得到查找结果，这是最理想的查找效率，哈希存到查找结果，这是最理想的查找效率，哈希存储和查找就是基于这种思路的方法。储和查找就是基于这种思路的方法。 学习

101、情境8 查找与演示项目开发8.4.1 子任务子任务1 认识哈希表认识哈希表哈希(hash)是一种按关键字编址的存储和查找方法，Hash原意为杂凑。1哈希函数与哈希表哈希函数与哈希表哈希函数(hash function)：在数据的关键字与该数据的存储位置之间建立一种对应关系，将这种关系称为哈希函数，由哈希函数决定的数据存储结构称为哈希表(hash table)。2哈希地址哈希地址设一个数据的关键字为key，由key作为参数的哈希函数为i=hash(key)，这个哈希函数的结果值i就是该数据在哈希表中的存储位置。因此，hash(key)也称为哈希地址。插入、删除、查找操作都是根据哈希地址获得数据的

102、存储位置。 学习情境8 查找与演示项目开发8.4.2 子任务子任务2 哈希函数的构造哈希函数的构造1构造哈希函数的要求构造哈希函数的要求一个好的哈希函数的标准是使哈希地址均匀地分布在哈一个好的哈希函数的标准是使哈希地址均匀地分布在哈希表中，尽量防止或减少冲突。如何设计理想的哈希函数，希表中，尽量防止或减少冲突。如何设计理想的哈希函数，需要考虑以下几方面因素：需要考虑以下几方面因素：(1) 哈希地址必须均匀分布在哈希表的全部地址空间。哈希地址必须均匀分布在哈希表的全部地址空间。(2) 函数简单，计算哈希函数花费时间为函数简单，计算哈希函数花费时间为O(1)。(3) 使关键字的所有成分都起作用，以

103、反映不同关键字的使关键字的所有成分都起作用，以反映不同关键字的差异。差异。(4) 数据的查找频率。数据的查找频率。 学习情境8 查找与演示项目开发2常用哈希函数常用哈希函数每种类型的关键字有各自的特性，关键字集合的大小也每种类型的关键字有各自的特性，关键字集合的大小也不尽相同。因此，不存在一种哈希函数，对任何关键字集合不尽相同。因此，不存在一种哈希函数，对任何关键字集合都是最好的。在实际应用中，应该根据具体情况，比较分析都是最好的。在实际应用中，应该根据具体情况，比较分析关键字与地址之间的对应关系，构造不同的哈希函数，或将关键字与地址之间的对应关系，构造不同的哈希函数，或将根本的哈希函数组合起

104、来使用，以求到达最正确效果。下面根本的哈希函数组合起来使用，以求到达最正确效果。下面介绍常用的哈希函数构造方法。介绍常用的哈希函数构造方法。(1) 除留余数法。除留余数法。除留余数法的哈希函数定义如下：除留余数法的哈希函数定义如下：Hash(k)=k%p函数结果值的范围为函数结果值的范围为0p-1。学习情境8 查找与演示项目开发除留余数法的关键在于如何选取p值，假设p取10的幂次，如p=102，表示取关键字的后两位作为地址，那么后两位相同的关键字(如321与521)产生同义词冲突，产生冲突可能性较大。通常，p取小于哈希表长度的最大素数，取值关系见表8-1。 (2) 平方取中法。平方取中法是将关

105、键字值k的平方k2的中间几位作为hash(k)的值，位数取决于哈希表长度。例如，k=6379，k2= 40691641，假设表长为100，取中间两位，那么hash(k)=91。(3) 折叠法。折叠法是将关键字分为几局部，再按照某种约定把这几局部组合在一起。 学习情境8 查找与演示项目开发表表8-1 哈希表长度与其最大素数哈希表长度与其最大素数 学习情境8 查找与演示项目开发3哈希表的查找哈希表的查找在哈希表中查找数据的过程和构造的过程根本一致：对在哈希表中查找数据的过程和构造的过程根本一致：对给定关键字给定关键字k，由哈希函数，由哈希函数H计算出该数据的地址计算出该数据的地址H(k)。假设。假

106、设表中该位置为空，那么查找失败；否那么，比较关键字，假表中该位置为空，那么查找失败；否那么，比较关键字，假设相等，那么查找成功。设相等，那么查找成功。学习情境8 查找与演示项目开发8.4.3 子任务子任务3 冲突及处理冲突及处理1冲突冲突哈希函数实质上是关键字集合到地址集合的映射，如果哈希函数实质上是关键字集合到地址集合的映射，如果这种映射是一一对应的，那么查找效率就是这种映射是一一对应的，那么查找效率就是O(1)。在实际应。在实际应用中，因为哈希表的存储容量有限，哈希函数是一个压缩映用中，因为哈希表的存储容量有限，哈希函数是一个压缩映射，从关键字集合到地址集合是多对一的映射，所以不可防射，从

107、关键字集合到地址集合是多对一的映射，所以不可防止地会产生冲突。止地会产生冲突。设有两个不同的关键字设有两个不同的关键字k1和和k2, k1k2，hash(k1)=hash(k2), k1和和k2的哈希函数值相同，即表示不同的哈希函数值相同，即表示不同关键字的多个数据映射到同一个存储位置，冲突是不可完全关键字的多个数据映射到同一个存储位置，冲突是不可完全防止的。防止的。 学习情境8 查找与演示项目开发2处理冲突的方法处理冲突的方法由于冲突不可能完全防止，因此，妥善处理冲突是构造由于冲突不可能完全防止，因此，妥善处理冲突是构造哈希表必须解决的问题。哈希表必须解决的问题。假设哈希表的地址范围为假设哈

108、希表的地址范围为0m-1，当对给定的关键字，当对给定的关键字k，由哈希函数由哈希函数H(k)计算出的位置上已有数据时，那么出现冲突，计算出的位置上已有数据时，那么出现冲突，此时必须为该数据另外找一个位置。如何确定这一空位置？此时必须为该数据另外找一个位置。如何确定这一空位置？对此，有以下几种常用的方法。对此，有以下几种常用的方法。(1) 开放定址法。开放定址法。H(k)=(H(k)+i)%m i = 1, 2, , q其中其中qm-1，m为表长，为表长，d为增量序列，为增量序列，d的取值常用以下的取值常用以下两种形式，分别称为线性探测法和二次探测法。两种形式，分别称为线性探测法和二次探测法。

109、学习情境8 查找与演示项目开发 线性探测法：d = i，即d依次取1，2，因此H(k) = (H(k) + i) %m。换句话说，在这种情况下，从H(k)开始向后逐个搜索空位置，假设后面没有空位置，就从头开始搜索，直到搜索到空位或者回到H(k)为止。故这种搜索方法称为线性探测法。例：哈希表的地址区间为011，哈希函数为H(k)= k%11，采用线性探测法处理冲突，试将关键字序列9，19，59，4，8，12，18，63，19依次存储到哈希表中，构造出该哈希表，并求出在等概率情况下查找成功时的平均查找长度。学习情境8 查找与演示项目开发解：为构造哈希表，需要依次计算每个数据的哈希地址，并根据已计算

110、出的位置中是否有数据而作不同的处理：如果还没有存放数据，那么将该数据直接存放进去，否那么，就向后搜索空位置，如果后面没有空位置，就绕到最前面重新搜索，直到找到空位置，再将该数据存放进去即可(假设数组为A)。各个数据的存放过程如下：H(9)=9，可直接存放到A9中去。H(19)=8，可直接存放到A8中去。H(59)=4，可直接存放到A4中去。H(4)=4，因为A4已经被70占用，故向后搜索到A5并存放。学习情境8 查找与演示项目开发H(8)=8，因为A8、A9已分别被30，20占用，故向后搜索到A10并存放。H(12)=1，可直接存放到A1中去。H(18)=7，可直接存放到A7中去。H(63)=

111、8，因A8、A9、A10均被占用，故向后搜索到A11并存放。H(19)=8，因下标为811的数据均被占用，故向后搜索到A0存放。在运用线性探测法处理冲突时，可能会出现这样的情况：某一连续的存储区已经存放满了，因此在经过这一区域向后搜索空位置时，需要比较较多的数据，从而导致查找长度增大。二次探测法可改善这一问题。 学习情境8 查找与演示项目开发 二次探测法：d的取值可能为1、-1、4、-4、9、-9、16、-16、kk、-kk(km/2)，这称为二次探测再散列。也就是说，该方法是在原定位置的两边交替地搜索，其偏移位置是次数的平方，故称这种方法为二次探测法。(2) 再散列法。当出现冲突时，可用另外

112、不同的哈希函数来计算哈希地址。假设此时还有冲突，那么再用另外的哈希函数，依次类推，直至找到空位置。也就是要依次用H1(k), H2(k), , Hi(k),(i=1, 2, )。(3) 链地址法。链地址法也称开哈希表。这一方法是将所有冲突记录(同义词)存储在一个链表中，并将这些链表的表头指针存放在数组中，这类似于图结构的邻接表存储结构和数结构的孩子链表结构。学习情境8 查找与演示项目开发8.4.4 子任务子任务4 哈希表操作演示工程哈希表操作演示工程前面两个演示工程将所有内容都放在一个前面两个演示工程将所有内容都放在一个Java文件中不文件中不同，哈希演示工程采用多个类实现。同，哈希演示工程采

113、用多个类实现。1构造哈希数据类构造哈希数据类完整代码如下：完整代码如下：package ch8Search;学习情境8 查找与演示项目开发import ;public class HashData public static JLabel lb1 = new JLabel(56); public static JLabel lb2 = new JLabel(12); public static JLabel lb3 = new JLabel(70); public static JLabel lb4 = new JLabel(15); public static JLabel lb5 = ne

114、w JLabel(18); public static JLabel lb6 = new JLabel(30); public static JLabel lb7 = new JLabel(20);学习情境8 查找与演示项目开发2. 构造哈希标签类构造哈希标签类完整代码如下：package ch8Search;import .*;public class HashLabel public static Label lb0 = new Label(); public static Label lb1 = new Label(); public static Label lb2 = new Lab

115、el(); public static Label lb3 = new Label();学习情境8 查找与演示项目开发 public static Label lb4 = new Label(); public static Label lb5 = new Label(); public static Label lb6 = new Label(); public static Label lb7 = new Label(); public static Label lb8 = new Label(); public static void delay(long delay) try java

116、.lang.Thread.sleep(delay); catch (Exception ex) (); 学习情境8 查找与演示项目开发3构造哈希按钮类构造哈希按钮类完整代码如下：package ch8Search;import .*;import .*;public class HashBtn implements ActionListener public static Button btn1 = new Button(搜索); public int s = 0; public static TextField tf1 = null; static int n = 0; static int

117、 lo = 0;学习情境8 查找与演示项目开发 public static Label label1 = new Label(); HashData lb1 = new HashData(); int s1 = Integer.parseInt(lb1.lb1.getText().trim(); int s2 = Integer.parseInt(lb1.lb2.getText().trim(); int s3 = Integer.parseInt(lb1.lb3.getText().trim(); int s4 = Integer.parseInt(lb1.lb4.getText().tri

118、m(); int s5 = Integer.parseInt(lb1.lb5.getText().trim(); int s6 = Integer.parseInt(lb1.lb6.getText().trim(); int s7 = Integer.parseInt(lb1.lb7.getText().trim(); HashLabel lb3 = new HashLabel(); String st = null; int str1 = new int8; static Label str2 = new Label9; int str3 = s1, s2, s3, s4, s5, s6,

119、s7, 0;学习情境8 查找与演示项目开发 HashBtn() tf1 = new TextField(); str1 = str3; str20 = lb3.lb1; str21 = lb3.lb2; str22 = lb3.lb3; str23 = lb3.lb4; str24 = lb3.lb5; str25 = lb3.lb6; str26 = lb3.lb7; str27 = lb3.lb8; btn1.addActionListener(this); 学习情境8 查找与演示项目开发 public void actionPerformed(ActionEvent e) st = tf

120、1.getText(); String str4 = (); int i = 0; int j = 0; str2n.setText(); boolean pa = false; if () = btn1) try int str = Integer.parseInt(str4); s = Integer.parseInt(tf1.getText(); lo = s % 7;学习情境8 查找与演示项目开发 for (i = lo; i 8; i+) str2i.setText(); if (str = str1i) n = i; pa = true; break; lb3.delay(1000

121、); str2i.setText(); if (lo != 0) if (!pa) str27.setText(); out:学习情境8 查找与演示项目开发 for (j = 0; j lo; j+) str2j.setText(); if (str1j = str) pa = true; break out; lb3.delay(1000); str2j.setText(); else label1.setText(找到了); if (pa) label1.setText(找到了);学习情境8 查找与演示项目开发 else label1.setText(找不到); else if (pa)

122、label1.setText(找到了); else label1.setText(找不到); catch (Exception ee) label1.setText(你必须输入数据); 学习情境8 查找与演示项目开发4构造哈希查找类构造哈希查找类完整代码如下：package ch8Search;import .*;import java.awt.event.*;import javax.swing.*;public class DemoHashSearch public static Frame frame = new Frame();学习情境8 查找与演示项目开发 public DemoHa

123、shSearch() frame.addWindowListener(new WindowAdapter() public void windowClosing(WindowEvent e) frame.setVisible(false); public void closedWindow(WindowEvent e) frame.setVisible(false); ); HashBtn bt = new HashBtn(); Label lbl2 = new Label(输入查找的数据:); frame.add(lbl2);学习情境8 查找与演示项目开发 final int FRAME_W

124、IDTH = 350; final int FRAME_HEIGHT = 400; frame.setSize(FRAME_WIDTH, FRAME_HEIGHT); (哈希函数的线性探测法); Component add = frame.add(HashBtn.tf1); Component add1 = frame.add(HashBtn.btn1); frame.add(HashBtn.label1); frame.setLayout(null); /布局 lbl2.setBounds(20, 90, 100, 30); HashBtn.label1.setBounds(176, 90,

125、 90, 25); HashBtn.tf1.setBounds(121, 90, 55, 25); HashBtn.btn1.setBounds(125, 50, 40, 30); HashData lb5 = new HashData(); Component add2 = frame.add(HashData.lb1);学习情境8 查找与演示项目开发 Component add3 = frame.add(HashData.lb2); frame.add(HashData.lb3); frame.add(HashData.lb4); frame.add(HashData.lb5); Comp

126、onent add4 = frame.add(HashData.lb6); frame.add(HashData.lb7); HashData.lb1.setBounds(15, 195, 40, 20);/中序排序数据存放的位置 HashData.lb1.setBorder(BorderFactory.createEtchedBorder(); HashData.lb2.setBounds(60, 195, 40, 20); HashData.lb2.setBorder(BorderFactory.createEtchedBorder(); HashData.lb3.setBounds(10

127、5, 195, 40, 20); HashData.lb3.setBorder(BorderFactory.createEtchedBorder(); HashData.lb4.setBounds(150, 195, 40, 20); HashData.lb4.setBorder(BorderFactory.createEtchedBorder(); HashData.lb5.setBounds(200, 195, 40, 20);学习情境8 查找与演示项目开发 HashData.lb5.setBorder(BorderFactory.createEtchedBorder(); HashDat

128、a.lb6.setBounds(250, 195, 40, 20); HashData.lb6.setBorder(BorderFactory.createEtchedBorder(); HashData.lb7.setBounds(295, 195, 40, 20); HashData.lb7.setBorder(BorderFactory.createEtchedBorder(); HashLabel lb3 = new HashLabel(); Component add5 = frame.add(HashLabel.lb1); frame.add(HashLabel.lb1); Com

129、ponent add6 = frame.add(HashLabel.lb2); frame.add(HashLabel.lb3); Component add7 = frame.add(HashLabel.lb4); frame.add(HashLabel.lb5);学习情境8 查找与演示项目开发 Component add8 = frame.add(HashLabel.lb6); frame.add(HashLabel.lb7); Component add9 = frame.add(HashLabel.lb8); HashLabel.lb0.setBounds(0, 215, 30, 20

130、); HashLabel.lb1.setBounds(15, 215, 40, 20); HashLabel.lb2.setBounds(60, 215, 40, 20); HashLabel.lb3.setBounds(105, 215, 40, 20); HashLabel.lb4.setBounds(150, 215, 40, 20); HashLabel.lb5.setBounds(200, 215, 40, 20); HashLabel.lb6.setBounds(250, 215, 40, 20); HashLabel.lb7.setBounds(295, 215, 40, 20)

131、; HashLabel.lb8.setBounds(315, 215, 40, 20); frame.setVisible(true); 学习情境8 查找与演示项目开发 public static void main(String args) DemoHashSearch twotree = new DemoHashSearch(); 学习情境8 查找与演示项目开发课后任务课后任务1学习各种查找方法，模仿或按照教程中的程序代码，学习各种查找方法，模仿或按照教程中的程序代码，构建各种查找方法程序实现。构建各种查找方法程序实现。2运行自己完成的各种查找方法程序实现，并进行测试，运行自己完成的各种查找方法程序实现，并进行测试，以帮助理解本学习情境的数据结构和算法内容。以帮助理解本学习情境的数据结构和算法内容。3对各种查找方法中程序实现的不完善之处进行改进，对各种查找方法中程序实现的不完善之处进行改进，或者写出更好的、创新的程序实现。或者写出更好的、创新的程序实现。