`
MouseLearnJava
  • 浏览: 466257 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

可视化查找之二分查找

阅读更多
如果查找过程和程序执行能结合起来,那么这个过程会更加直观。

本文简单地实现了二分查找的可视化。界面很简单就包括两个部分:界面左侧是可视化查找部分,右侧是二分查找的代码。如下图所示:



程序的关键点主要有两点:
1. 如何在页面上表示出查找程序的运行过程。
2. 如何将排序程序的运行过程和可视化查找结合起来,保持状态一致。

我的解决方法如下:
我采用了JList去模拟程序的执行,JList有一个setSelectedIndex的方法,能高亮显示指定的行。通过改变selectedIndex的值,能够达到模拟程序执行的效果。根据模拟程序中保存的状态值去修改可视化查找。

程序主要是随机产生10个数值,查找数字9.


可以找到的运行情况:











找不到的运行情况:










程序代码如下:

package my.visualization.search.binary;

import java.awt.Container;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.ButtonGroup;
import javax.swing.JFrame;
import javax.swing.JMenu;
import javax.swing.JMenuBar;
import javax.swing.JMenuItem;
import javax.swing.JOptionPane;
import javax.swing.JRadioButtonMenuItem;

/**
 * 
 * @author Eric
 * @version 1.0
 *
 */
public class BinarySearchVisualizationFrame extends JFrame {

	private static final long serialVersionUID = -6725108659717827278L;

	private Container contentPane;

	/**
	 * 设置三个Menu Item,分别用于开始程序,调整运行的速度以及退出程序
	 * 
	 */
	private JMenuItem startMI = new JMenuItem("Start");

	private JMenu speedMenu = new JMenu("Speed");

	private JMenuItem exitMI = new JMenuItem("Exit");
	
	private JMenuItem aboutMI = new JMenuItem("About");

	/**
	 * 设定5个速度级别
	 */
	private JRadioButtonMenuItem speedMI1 = new JRadioButtonMenuItem("Speed1",
			true);

	private JRadioButtonMenuItem speedMI2 = new JRadioButtonMenuItem("Speed2",
			false);

	private JRadioButtonMenuItem speedMI3 = new JRadioButtonMenuItem("Speed3",
			false);

	private JRadioButtonMenuItem speedMI4 = new JRadioButtonMenuItem("Speed4",
			false);

	private JRadioButtonMenuItem speedMI5 = new JRadioButtonMenuItem("Speed5",
			false);

	public int speedFlag = 1;
	
	/**
	 * 冒泡排序可视化的Panel
	 */
	private BinarySearchPanel panel;

	public BinarySearchVisualizationFrame(){
		
		setTitle("可视化查找之二分查找");
		setSize(700, 400);
		setResizable(false);

		JMenuBar menuBar = new JMenuBar();
		setJMenuBar(menuBar);

		JMenu setMenu = new JMenu("Set");
		JMenu helpMenu = new JMenu("Help");
		
		setMenu.setMnemonic('s');
		setMenu.setMnemonic('H');

		menuBar.add(setMenu);
		menuBar.add(helpMenu);

		setMenu.add(startMI);
		setMenu.addSeparator();

		setMenu.addSeparator();
		setMenu.add(speedMenu);
		setMenu.addSeparator();
		setMenu.add(exitMI);

		ButtonGroup group = new ButtonGroup();
		group.add(speedMI1);
		group.add(speedMI2);
		group.add(speedMI3);
		group.add(speedMI4);
		group.add(speedMI5);

		speedMenu.add(speedMI1);
		speedMenu.add(speedMI2);
		speedMenu.add(speedMI3);
		speedMenu.add(speedMI4);
		speedMenu.add(speedMI5);

		startMI.addActionListener(new StartAction());
		speedMI1.addActionListener(new SpeedAction());
		speedMI2.addActionListener(new SpeedAction());
		speedMI3.addActionListener(new SpeedAction());
		speedMI4.addActionListener(new SpeedAction());
		speedMI5.addActionListener(new SpeedAction());
		exitMI.addActionListener(new ExitAction());
		helpMenu.add(aboutMI);
		aboutMI.addActionListener(new AboutAction());
		
		
		contentPane = getContentPane();
		
		panel = new BinarySearchPanel(this);
		contentPane.add(panel);
		startMI.setEnabled(true);
	}
	
	private class StartAction implements ActionListener {
		public void actionPerformed(ActionEvent event) {
			startMI.setEnabled(false);
			panel.timer.start();
		}
	}
	
	private class ExitAction implements ActionListener {
		public void actionPerformed(ActionEvent event) {
			System.exit(0);
		}
	}
	
	private class SpeedAction implements ActionListener {
		public void actionPerformed(ActionEvent event) {
			Object speed = event.getSource();
			if (speed == speedMI1) {
				speedFlag = 1;
			} else if (speed == speedMI2) {
				speedFlag = 2;
			} else if (speed == speedMI3) {
				speedFlag = 3;
			} else if (speed == speedMI4) {
				speedFlag = 4;
			} else if (speed == speedMI5) {
				speedFlag = 5;
			}

			panel.timer.setDelay(1000 - 200 * (speedFlag - 1));
		}
	}
	
	private class AboutAction implements ActionListener {
		public void actionPerformed(ActionEvent event) {
			String string = "说明:\n1.本程序可视化二分查找的过程\n" + "2.查找的数字为9\n" + "3.low的颜色用PINK表示\n"
			+ "4.high的颜色用CYAN表示\n" + "5.如果能找到,找到的数字用蓝色表示\n"+"6. 如果没有找到,颜色全部为绿色";
	JOptionPane.showMessageDialog(BinarySearchVisualizationFrame.this, string);
		}
	}
	
}



package my.visualization.search.binary;

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

import javax.swing.JList;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.Timer;

public class BinarySearchPanel extends JPanel {

	private static final long serialVersionUID = -9149581857139587792L;

	private static final String[] code = {
			"public int binarySearch0(int[] a, int key) {", 
			"   int low = 0;",
			"   int high = a.length - 1;", 
			"   while (low <= high) {",
			"     int mid = (low + high) >>> 1;     ",
			"     int midVal = a[mid];          ", 
			"     if (midVal < key)",
			"	    low = mid + 1;    ",
			"     else if (midVal > key)                           ",
			"       high = mid - 1;                                 ",
			"     else ", 
			"       return mid; ", 
			"   }",
			"   return -1", 
			"}" };

	/**
	 * 初始化10个数据
	 */
	private List<NumberRectangle> numbers = initialNumberRectangles();

	private JList codeList = new JList(code);;

	public TimerAction timerAction;

	public Timer timer;

	public BinarySearchVisualizationFrame frame;

	public BinarySearchPanel(BinarySearchVisualizationFrame frame) {

		timerAction = new TimerAction();
		timer = new Timer(1000, timerAction);

		codeList.setSelectedIndex(1);
		JScrollPane scrollPane1 = new JScrollPane(codeList);
		this.setLayout(new BorderLayout());
		this.add(scrollPane1, BorderLayout.EAST);

		this.frame = frame;
	}

	/**
	 * 判断排序是否已经结束
	 */
	private boolean completed = false;

	public void paintComponent(Graphics g) {
		super.paintComponent(g);
		Graphics2D g2 = (Graphics2D) g;

		drawNumberRectangles(g2);
	}

	private void drawNumberRectangles(Graphics2D g2) {
		for (NumberRectangle rectangle : numbers) {
			rectangle.draw(g2);
		}
	}

	int low = 0;

	int high = 9;

	int selectedIndex = 1;

	int mid = 0;

	int key = 9;

	int midVal = 0;

	private class TimerAction implements ActionListener, Serializable {

		private static final long serialVersionUID = -8671813189049345697L;

		public void actionPerformed(ActionEvent event) {
			if (completed) {
				return;
			}
			/**
			 * 为low 和 high着色
			 */
			switch (selectedIndex) {
			case 1:
				codeList.setSelectedIndex(selectedIndex++);
				break;
			case 2:
				codeList.setSelectedIndex(selectedIndex++);
				break;
			case 3:
				numbers.get(low).setColor(Color.PINK);
				numbers.get(high).setColor(Color.CYAN);
				//while(low <high)
				codeList.setSelectedIndex(selectedIndex);
				if (low <= high) {
					selectedIndex++;
				} else {
					numbers.get(low).setColor(Color.GREEN);
					numbers.get(high).setColor(Color.GREEN);
					selectedIndex = 13;
				}
				break;
			case 4:
				codeList.setSelectedIndex(selectedIndex++);
				mid = (low + high) >>> 1;
				
				break;
			case 5:
				codeList.setSelectedIndex(selectedIndex++);
				midVal = numbers.get(mid).getValue();
				
				break;
				
			case 6 :
				codeList.setSelectedIndex(selectedIndex);
				if(midVal < key){
					selectedIndex = 7;
				}else{
					selectedIndex = 8;
				}
				break;
				
			case 7:
				codeList.setSelectedIndex(selectedIndex);
				numbers.get(low).setColor(Color.GREEN);
				low = mid+1;
				selectedIndex = 3;
				break;
			case 8:
				codeList.setSelectedIndex(selectedIndex);
				if(midVal > key){
					selectedIndex = 9;
				}else{
					selectedIndex = 10;
				}
				break;
			case 9:
				codeList.setSelectedIndex(selectedIndex);
				numbers.get(high).setColor(Color.GREEN);
				high = mid -1;
				selectedIndex = 3;
				break;
			case 10:
				codeList.setSelectedIndex(selectedIndex++);
				break;
			case 11:
				codeList.setSelectedIndex(selectedIndex);
				//mid的方格着色
				completed = true;
				numbers.get(low).setColor(Color.GREEN);
				numbers.get(high).setColor(Color.GREEN);
				numbers.get(mid).setColor(Color.BLUE);
				break;
			case 13:
				codeList.setSelectedIndex(selectedIndex);
				completed = true;
				break;
			default:
				break;
			}

			repaint();

		}
	}

	private List<NumberRectangle> initialNumberRectangles() {
		List<NumberRectangle> list = new ArrayList<NumberRectangle>();
		/**
		 * 随机产生10个数组
		 */
		Random random = new Random();
		int[] values = new int[10];
		for (int i = 1; i <= 10; i++) {
			//list.add(new NumberRectangle(i,1,random.nextInt(15)+1, Color.GREEN));
			values[i - 1] = random.nextInt(15) + 1;
		}
		Arrays.sort(values);
		for (int i = 1; i <= 10; i++) {
			list.add(new NumberRectangle(i, 1, values[i - 1], Color.GREEN));
		}
		return list;
	}

}


package my.visualization.search.binary;

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.geom.Rectangle2D;

public class NumberRectangle {

	private int x;

	private int y;

	private int value;

	private Color color;

	public NumberRectangle() {
	}

	public NumberRectangle(int x, int y, int value, Color color) {
		this.x = x;
		this.y = y;
		this.color = color;
		this.value = value;

	}

	public void draw(Graphics2D g2) {
		int clientX = 30 + x * 30;
		int clientY = 20 + y * 10;
		Rectangle2D.Double rect = new Rectangle2D.Double(clientX, clientY, 20,
				value * 20);
		g2.setPaint(color);
		g2.fill(rect);
		g2.setPaint(Color.BLACK);
		g2.draw(rect);
		g2.drawString(String.valueOf(value), clientX, clientY - 10);
	}

	/**
	 * @return the color
	 */
	public Color getColor() {
		return color;
	}

	/**
	 * @param color
	 *            the color to set
	 */
	public void setColor(Color color) {
		this.color = color;
	}

	/**
	 * @return the x
	 */
	public int getX() {
		return x;
	}

	/**
	 * @param x
	 *            the x to set
	 */
	public void setX(int x) {
		this.x = x;
	}

	/**
	 * @return the y
	 */
	public int getY() {
		return y;
	}

	/**
	 * @param y
	 *            the y to set
	 */
	public void setY(int y) {
		this.y = y;
	}

	/**
	 * @return the value
	 */
	public int getValue() {
		return value;
	}

	/**
	 * @param value
	 *            the value to set
	 */
	public void setValue(int value) {
		this.value = value;
	}

}


package my.visualization.search.binary;

import javax.swing.JFrame;

public class SortApplication {
	@SuppressWarnings("deprecation")
	public static void main(String[] args) {
		BinarySearchVisualizationFrame frame = new BinarySearchVisualizationFrame();
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.show();
	}
}


程序代码也没有优化过,注释也基本上没有加,不好意思。大家如果有其它好的想法,请共享一下哦。
  • 大小: 43.6 KB
  • 大小: 15.9 KB
  • 大小: 39.3 KB
  • 大小: 38.9 KB
  • 大小: 40.7 KB
  • 大小: 41 KB
  • 大小: 41 KB
  • 大小: 42.5 KB
1
2
分享到:
评论

相关推荐

    flash as3 二分查找动画演示

    在这个"flash as3 二分查找动画演示"项目中,我们看到的是一个用Flash AS3实现的二分查找算法的可视化教程。 二分查找(Binary Search)是计算机科学中一种高效的数据检索方法,适用于已排序的数组或列表。它的基本...

    常用算法可视化演示系统

    每种结构都有其特定的插入、删除和查找操作,通过可视化演示,用户可以清晰地看到这些操作如何影响数据的存储和访问。 2. **排序算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。这些...

    数据结构 可视化演示软件

    7. **查找算法**:顺序查找、二分查找、哈希查找的原理和效率。 8. **数据结构的优化**:如哈希表的冲突解决策略,二叉查找树的平衡调整。 使用这样的软件,开发者和学习者可以更直观地理解这些复杂的概念,从而...

    基于MFC的可视化数据结构

    在讲解算法部分,书中涵盖了排序(如冒泡排序、快速排序、归并排序)和查找(如线性查找、二分查找)等经典算法,同样辅以MFC的可视化演示,使得这些复杂的算法步骤变得清晰易懂。这有助于读者不仅了解算法的工作...

    课程设计算法可视化实现

    搜索算法的可视化则能让我们看到查找过程,如在有序或无序数组中寻找目标元素的路径。 为了实现算法可视化,我们需要掌握一定的前端技术,如HTML、CSS和JavaScript。这些技术可以构建交互式的用户界面,展示动态的...

    3D模型可视化方案

    #### 二、三维模型可视化方案的核心价值 为了解决上述问题,三维模型可视化方案应运而生。这种方案旨在帮助企业轻松高效地实现三维模型的轻量化转换与浏览协同,具体来说包括以下几个方面: - **轻量化转换**:...

    基于GPS的基坑监测数据处理及可视化实现.pdf

    二维可视化则多用于平面图表,可以显示数据在二维平面上的分布和变化;三维可视化则更为直观,它能够将数据以立体的形式展现出来,更符合人们的直观感知。 基于上述技术的基坑监测数据处理体系和可视化实现,为基坑...

    最优二分检索树构造及绘制

    此外,最优二分检索树在所有满足二分查找条件的树中,具有最小的平均查找长度,因此在检索效率上达到最优。 在程序设计中,构建最优二分检索树通常涉及动态规划方法。一个基本的思路是,对于n个不同键值的集合,...

    (严蔚敏、吴伟民)数据结构配套可视化算法演示系统

    5. **查找算法**:如顺序查找、二分查找、哈希查找。二分查找适用于有序数组,效率高;哈希查找通过散列函数快速定位,实现近似常数时间的查找。 6. **动态规划**:用于解决具有重叠子问题和最优子结构的问题,如...

    算法可视化系列——排序算法——插入排序

    1. **二分插入排序**:在查找插入位置时,采用二分查找可以减少比较次数,提高效率,但总的时间复杂度仍为O(n^2),只是常数因子变小。 2. **稳定性和不稳定性**:插入排序是稳定的排序算法,即相等的元素在排序后的...

    VC++6.0开发的算法可视化演示平台

    2. **搜索算法**:线性搜索、二分查找、哈希表查找,直观地显示搜索路径和查找效率。 3. **图论算法**:深度优先搜索(DFS)和广度优先搜索(BFS),以及Dijkstra算法和Floyd-Warshall算法求解最短路径问题。 4. **...

    IllustratedAlgorithms交互式可视化算法

    搜索算法(如二分查找)则可以通过条形图或树状结构来直观表示查找过程。 在《Illustrated Algorithms》中,可能会包含以下常见算法的可视化: 1. 排序算法:如冒泡排序、插入排序、选择排序、快速排序、归并排序...

    大数据可视化教案 (2).pdf

    二、数据可视化发展历史 数据可视化的起源可以追溯到公元2世纪,但真正的发展主要集中在近两个半世纪,特别是近四十年。20世纪的可视化图形在政府、商业和科研中广泛应用,而21世纪互联网的兴起带来了新的可视化技术...

    可视化教学系统,专注于对数据结构和算法的可视化.zip

    常见算法包括排序(如冒泡排序、插入排序、快速排序、归并排序)、查找(如线性搜索、二分搜索)、图遍历(如深度优先搜索、广度优先搜索)等。 HTML,全称为超文本标记语言,是创建网页的标准语言。在这个可视化...

    数据结构的有关查找的知识

    判定树是根据二分查找的逻辑构建的一种可视化表示,用于展示查找过程中比较的元素及其次数。 3. **分块查找**:针对按块有序的查找表,通过先查找索引再查找块内的元素来提高效率。索引表可以用顺序或链式存储,...

    基于Matlab若干经典算法的可视化研究.zip

    7. **算法可视化**:对于一些经典算法,如排序算法(快速排序、冒泡排序等)、搜索算法(二分查找、深度优先搜索等)或优化算法(梯度下降、遗传算法等),Matlab可以用来动态展示它们的执行过程,帮助理解算法工作...

    严蔚敏数据结构可视化演示系统

    7. **查找算法**:包括顺序查找、二分查找、哈希查找等,这些在实际应用中非常常见,系统通过动态演示帮助用户掌握查找效率的提升。 通过严蔚敏数据结构可视化演示系统,学习者不仅可以学习到数据结构的基本概念,...

Global site tag (gtag.js) - Google Analytics