demo.java

学习数据结构的最好辅助工具,快速帮助你熟悉数据结构的相关技术

import java.awt.*;

public class Demo extends Canvas 
{
	public static final int TopX  =20;
	public static final int TopY  =20;
	public static final int SpanX =40;
	public static final int	SpanY =15;
	public static final int Width =27;
	public static final int Height=27;
	public static final int Over  =1;
	public static final int None  =0;
	public static final int Start =-1;
	
	
										  
	private boolean		m_bSortType	= true;
	private boolean		m_bStepInto = true;
	private char		m_Data[]	= new char [11];
	private int			m_nCount	= 0;
		
	private int			m_nIndexI	= 0;
	private int			m_nIndexJ	= 0;
	private int			m_nS,m_nM;	
	private int			m_Status	= None;								  
	private int			m_nIndexOld	=0;
	private int			m_nStepOld  =0;
	private char		rc;
	private Graphics	m_offG;
	private Image		m_offImg;
	
	private Point getLoc(int index)
	{
		Point p=new Point ();
		
		p.x = TopX+4*SpanX;
		p.y = TopY+3*SpanY;
		
		int i = index;
		int w = 150;
		
		do
		{	
			p.y = p.y+2*SpanY+10;
			w = w*3/5;
		}while((i=i/2)>=1);
		p.x = getX(index,w);
		return p;
		
	}
	private int getX(int index,int w)
	{		
		if(index==1)
			return TopX+4*SpanX;
		else if(index>1)
		{
			if(index%2==1) 
				return getX(index/2,w*5/3)+w;
			else
				return getX(index/2,w*5/3)-w;				
		}
		return 0;
			
	}
	public void setStepIn(boolean bStep)
	{
		m_bStepInto = bStep;
	}
	public void setData(String s,boolean bSort,boolean bStep)
	{		
		for(int i=0;i<s.length ();i++)
			m_Data[i+1] = s.charAt (i);
		m_nCount	  = s.length ();	
		m_bSortType	  = bSort;
		m_bStepInto	  = bStep;
		m_Status	  = Start;				
	}					
									
	private boolean compare(char ch1,char ch2)
	{		
		if(m_bSortType)
			return(ch1<ch2);
		return(ch1>ch2);		
	}
	public void reset()
	{
		m_Status	= None;
		m_nCount	= 0;
		m_nIndexI	= 0;
		m_nIndexJ	= 0;
		m_nS		= 0;
		
		repaint();
	}
		
	private void heapAdjust(int start,int end)
	{		
		char c = m_Data[start];
		for (int j=2*start; j<=end; j*=2 ) {
	
		if ( j<end && compare(m_Data[j],m_Data[j+1]))
				 ++j; 
		if ( !compare(c,m_Data[j])) break; 
	
		m_Data[start] = m_Data[j];
		start = j;
		}
		m_Data[start] = c; // 插入
	} // HeapAdjust
	

	public int proceed(int nStep)
	{
		int nextStep=-1;
		
		switch(nStep)
		{
			case -1:
					m_nS	 = 0;
					m_nIndexJ= 0;
					m_nIndexI= 0;
					nextStep = 0;
					m_Status = Start;
					
					break;
			case 0:	
					nextStep = 1;					
					break;
			case 1: if(m_nIndexI==0)
						m_nIndexI = m_nCount/2;					
					else
						m_nIndexI = m_nIndexOld-1;						
					if(m_nIndexI>0)
						nextStep = 2;						
					else						
						nextStep = 3;
					break;
			case 2:	
					
					m_nIndexOld	= m_nIndexI;
					if(m_bStepInto)
					{
						m_nStepOld	= 1;
						m_nS = m_nIndexI;
						m_nM = m_nCount;					
						nextStep = 9;
					}
					else
					{
						heapAdjust(m_nIndexI,m_nCount);
						m_nS = 0;
						m_nM = 0;
						m_nIndexJ =0;
						nextStep = 1;
					}
					break;
			case 3:
					if(m_nIndexI==0)
						m_nIndexI = m_nCount;
					else
						m_nIndexI--;
					
					if(m_nIndexI>1)
						nextStep = 4;
					else
						nextStep = 7;
					break;
			case 4:
					
					char tc	= m_Data[1];
					m_Data[1] = m_Data[m_nIndexI];
					m_Data[m_nIndexI] = tc;
					nextStep = 5;
					break;
			case 5:if(m_bStepInto){
						m_nIndexOld= m_nIndexI;
						m_nStepOld = 6;
						m_nS = 1;
						m_nM = m_nIndexI-1;
						nextStep = 9;
					}else{
						heapAdjust(1,m_nIndexI-1);
						m_nS = 0;
						m_nM = 0;
						m_nIndexJ=0;
						nextStep=6;
					}
					break;
			case 6:
					nextStep = 3;
					break;					
			case 7: 
					nextStep = -1;
					m_Status = Over;
					break;
			case 9:
					nextStep = 10;
					break;
			case 10:
					rc = m_Data[m_nS];
					nextStep = 11;
					m_nIndexJ = m_nS;
					break;
			case 11:
					m_nIndexJ = m_nIndexJ*2;					
					if(m_nIndexJ<=m_nM)
						nextStep = 12;
					else
						nextStep = 17;
					break;
			case 12:
					Graphics g = getGraphics();
					if(m_nIndexJ<m_nM){
						for(int i=1;i<=3;i++)
						{
							g.setColor(Color.cyan);
							g.fillOval (getLoc(m_nIndexJ).x-14,getLoc(m_nIndexJ).y-14,28,28);
							g.fillOval (getLoc(m_nIndexJ+1).x -14,getLoc(m_nIndexJ+1).y -14,28,28);
							g.setColor (Color.yellow );
							g.drawString (""+m_Data[m_nIndexJ],getLoc(m_nIndexJ).x-2,getLoc(m_nIndexJ).y+5);
							g.drawString (""+m_Data[m_nIndexJ+1],getLoc(m_nIndexJ+1).x-2,getLoc(m_nIndexJ+1).y+5);
							delay(80);
							g.setColor(Color.red);
							g.fillOval (getLoc(m_nIndexJ).x-14,getLoc(m_nIndexJ).y-14,28,28);
							g.fillOval (getLoc(m_nIndexJ+1).x -14,getLoc(m_nIndexJ+1).y -14,28,28);						
							g.setColor (Color.yellow );
							g.drawString (""+m_Data[m_nIndexJ],getLoc(m_nIndexJ).x-2,getLoc(m_nIndexJ).y+5);
							g.drawString (""+m_Data[m_nIndexJ+1],getLoc(m_nIndexJ+1).x-2,getLoc(m_nIndexJ+1).y+5);
							delay(80);
						}
						if(compare(m_Data[m_nIndexJ],m_Data[m_nIndexJ+1]))
							nextStep = 13;
						else
							nextStep = 14;
					}
					else
						nextStep = 14;
					break;
			case 13:
					m_nIndexJ++;
					nextStep = 14;
					break;
			case 14:if(compare(m_Data[m_nIndexJ],rc)) 
						nextStep = 17;
					else
						nextStep = 15;
					break;
			case 15:
					Graphics mg = getGraphics();				
					int dx;
					int dy;
					for(int i=0;i<=3;i++)
					{
						dx = ((3-i)*getLoc(m_nIndexJ).x+i*getLoc(m_nS).x)/3;
						dy = ((3-i)*getLoc(m_nIndexJ).y+i*getLoc(m_nS).y)/3;
						mg.setColor(Color.cyan);
						mg.fillOval (dx-14,dy-14,28,28);
						mg.drawString (""+m_Data[m_nIndexJ],dx-2,dy+5);
						delay(50);							
					}					
					m_Data[m_nS] = m_Data[m_nIndexJ];					
					delay(100);
					m_nS = m_nIndexJ;
					nextStep = 16;
					break;
			case 16:
					nextStep = 11;
					break;
			case 17:m_Data[m_nS]=rc;
					nextStep = 18;
					break;
			case 18:
					nextStep = m_nStepOld;
					break;
		}
		repaint();
		return nextStep;	
	}
	public void delay(int time)	
	{
		try{ Thread.sleep(time); }
		catch(InterruptedException e){}
	}

		
										   
	public void update(Graphics g)
	{
		paint(g); 
	} 
	public void addNotify()
	{ 
		super.addNotify(); 
		m_offImg	= createImage(getSize().width, getSize().height);
		m_offG		= m_offImg.getGraphics(); 
	}
	public void drawArrow(Graphics g,int x,int y,char c)
	{
		Color old=g.getColor ();
		g.setColor(Color.blue );
		g.drawLine (x,y,x-17,y-10);
		g.drawLine (x-17,y-10,x-22,y-7);
		g.drawLine (x-22,y-7,x-29,y-12);
		g.drawLine (x,y,x-5,y);
		g.drawLine (x,y,x-2,y-4);
		g.setColor (Color.red );
		g.drawString(""+c,x-22,y-8);
		g.setColor (old);
	}
	public void paint(Graphics g)
	{
		m_offG.clearRect (0,0,this.getSize ().width ,this.getSize ().height );		
		switch(m_Status)
		{
			case None:
						
						break;
			case Start:
						m_offG.drawString("排序数据:",TopX,TopY);
						for(int i=1;i<=m_nCount;i++)
						{
							m_offG.drawRect (TopX+i*SpanX-20,TopY+SpanY,Width,Height);							
							if(i==m_nS||i==m_nIndexJ)
							{
								m_offG.setColor (Color.cyan );
								m_offG.fillRect (TopX+i*SpanX-20,TopY+SpanY,Width,Height);
								m_offG.setColor (Color.black );
							}
							m_offG.drawString (""+m_Data[i],TopX+i*SpanX-20+Width/3,TopY+SpanY+Height*2/3);														
							if(i>1) 
								m_offG.drawLine (getLoc(i).x,getLoc(i).y ,getLoc(i/2).x,getLoc(i/2).y);
							m_offG.drawOval (getLoc(i).x-15,getLoc(i).y-15,30,30);			
							
						}
						
						for(int i=1;i<=m_nCount;i++)
						{
							m_offG.setColor(this.getBackground ());
							m_offG.fillOval (getLoc(i).x-14,getLoc(i).y-14,28,28);
							m_offG.setColor (Color.black );
							m_offG.drawString (""+m_Data[i],getLoc(i).x-2,getLoc(i).y+5);
						}
						
						if(m_nS>0&&(m_nS<=m_nCount))						
							drawArrow(m_offG,getLoc(m_nS).x-13,getLoc(m_nS).y-13,'S');
						if(m_nIndexJ>0&&(m_nIndexJ<=m_nCount)&&(m_nIndexJ!=m_nS))
							drawArrow(m_offG,getLoc(m_nIndexJ).x-13,getLoc(m_nIndexJ).y -13,'J');
						if(m_bStepInto)
							m_offG.drawString ("rc = "+rc,TopX,5*SpanY+TopY);
						
						
						break;
			case Over:
						m_offG.drawString ("排序结果",TopX,TopY);
						for(int i=1;i<=m_nCount;i++)
						{
							m_offG.drawRect (TopX+i*SpanX-20,TopY+SpanY,Width,Height);							
							m_offG.drawString (""+m_Data[i],TopX+i*SpanX-20+Width/3,TopY+SpanY+Height*2/3);														
						}						
						break;
		}
		g.drawImage (m_offImg,0,0,this);
		
	}
	
}