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 char		m_TR1[]		= new char [11];
	private	char		m_TR2[]		= new char [11];
	private int			m_nCount	= 0;
	
	private int			m_nS		=0;
	private int			m_nT		=0;
	private int			m_nM		=0;
	private int			m_nN		=0;
		
	private int			m_nIndexI	= 0;
	private int			m_nIndexJ	= 0;
	private int			m_nIndexK	= 0;

	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 Stack		m_Stack[]	= new Stack [20];
	
	private int			m_Pos		=0;
	
	
	
	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_TR1[i+1]	= s.charAt (i);
		}
		
		m_nCount	  = s.length ();	
		m_bSortType	  = bSort;
		m_bStepInto	  = bStep;
		m_Status	  = Start;
		
		for(int i=0;i<20;i++)
		{
			if(m_Stack[i]==null)
				m_Stack[i]=new Stack ();
		}
	}					
									
	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;
		for(int i=0;i<m_TR2.length ;i++)
			m_TR2[i] = ' ';
		repaint();
	}
	private void MSort(char sr[],char tr1[],int s,int t)
	{
		if(s==t){
			tr1[s] = sr[s];
		}else{			
			int  m = (s+t)/2;
			char tr2[]  = new char[10]; 
			MSort(sr,tr2,s,m);
			MSort(sr,tr2,m+1,t);
			Merge(tr2,tr1,s,m,t);
		}
	}
	private void  Merge(char sr[],char tr[],int i,int m,int n)
	{
		int j,k;		
		for(j=m+1,k=i;i<=m&&j<=n;++k)
		{
			if(compare(sr[i],sr[j]))
				tr[k] = sr[i++];
			else
				tr[k] = sr[j++];
		}
		if(i<=m) 
		{
			for(int l=k;l<=n;l++)
				tr[l] = sr[i+l-k];
		}
		if(j<=n) 
			for(int l=k;l<=n;l++)
				tr[l] = sr[j+l-k];
	}
	public int proceed(int nStep)
	{
		int nextStep=-1;
		
		switch(nStep)
		{
			case -1:
					nextStep = 0;
					m_Status = Start;					
					break;
			case 0:	
					nextStep = 1;					
					break;
			case 1:
					if(m_bStepInto)
					{	
						m_Stack[m_Pos].m_nS = 1;
						m_Stack[m_Pos].m_nT = m_nCount;
						m_Stack[m_Pos].nextStep = 2;
						m_Pos++;
						m_nS = 1;
						m_nT = m_nCount;
						nextStep=4;						
					}else{
						MSort(m_TR1,m_TR1,1,m_nCount);					
						nextStep = 2;
					}
					break;
			case 2:
					m_Status = Over;
					nextStep = -1;
					break;
					
			case 4:
					//m_nS = m_Stack[m_Pos-1].m_nS ;
					//m_nT = m_Stack[m_Pos-1].m_nT ;
					nextStep = 6;
					break;
			case 6:
					if(m_nS==m_nT)
						nextStep = 7;
					else
						nextStep =8;
					break;
			case 7:
					m_TR2[m_nS] = m_TR1[m_nS];
					nextStep =14;
					break;
			case 8:
					nextStep = 9;
					break;
			case 9:
					m_nM = (m_nS+m_nT)/2;
					nextStep = 10;
					break;
			case 10:
					if(m_bStepInto){
						m_Stack[m_Pos].m_nM = m_nM;
						m_Stack[m_Pos].m_nS = m_nS;
						m_Stack[m_Pos].m_nT = m_nT;
						m_Stack[m_Pos].nextStep = 11;
						m_Pos++;
						m_nS = m_nS;
						m_nT = m_nM;
						nextStep = 4;
					}else{
						MSort(m_TR1,m_TR2,m_nS,m_nM);
						nextStep = 11;
					}
					break;
			case 11:
					if(m_bStepInto){
						m_Stack[m_Pos].m_nM = m_nM;
						m_Stack[m_Pos].m_nS = m_nS;
						m_Stack[m_Pos].m_nT = m_nT;
						m_Stack[m_Pos].nextStep = 12;					
						m_Pos++;					
						m_nS = m_nM+1;					
						m_nT = m_nT;					
						nextStep = 4;
					}else{
						MSort(m_TR1,m_TR2,m_nM+1,m_nT);
						nextStep =12;
					}
						
					break;
			case 12:
					if(m_bStepInto)
					{
						nextStep = 16;
					}else{
						Merge(m_TR2,m_TR1,m_nS,m_nM,m_nT);
						for(int i=m_nS;i<=m_nT;i++)
							m_TR2[i] = m_TR1[i];
						nextStep = 13;
					}
					break;
			case 13:
					nextStep = 14;
					break;
			case 14:
					m_Pos--;
					m_nS = m_Stack[m_Pos].m_nS ;
					m_nM = m_Stack[m_Pos].m_nM ;
					m_nT = m_Stack[m_Pos].m_nT ;
					nextStep = m_Stack[m_Pos].nextStep ;
					break;			
			case 16:
					m_nIndexI = m_nS;
					m_nM	  = m_nM;
					m_nN	  = m_nT;
					m_nIndexK = m_nIndexI-1;
					m_nIndexJ = m_nM+1;
					nextStep  = 18;
					break;
			case 18:					
					m_nIndexK++;
					if(m_nIndexI<=m_nM&&(m_nIndexJ<=m_nN))
					{
						nextStep = 20;
					}
					else
						nextStep  = 24;
					break;
			case 20:
					Graphics g=getGraphics();
					Color old = g.getColor ();
					for(int i=0;i<3;i++)
					{
						g.setColor (Color.cyan );
						g.fillRect (TopX+m_nIndexI*SpanX-20,TopY+5*SpanY,Width,Height);	
						g.fillRect (TopX+m_nIndexJ*SpanX-20,TopY+5*SpanY,Width,Height);
						g.drawString (""+m_TR1[m_nIndexI],TopX+m_nIndexI*SpanX-20+Width/3,TopY+5*SpanY+Height*2/3);								
						g.drawString (""+m_TR1[m_nIndexJ],TopX+m_nIndexJ*SpanX-20+Width/3,TopY+5*SpanY+Height*2/3);								
						delay(80);
						g.setColor (Color.red );								
						g.fillRect (TopX+m_nIndexI*SpanX-20,TopY+5*SpanY,Width,Height);	
						g.fillRect (TopX+m_nIndexJ*SpanX-20,TopY+5*SpanY,Width,Height);
						g.drawString (""+m_TR1[m_nIndexI],TopX+m_nIndexI*SpanX-20+Width/3,TopY+5*SpanY+Height*2/3);								
						g.drawString (""+m_TR1[m_nIndexJ],TopX+m_nIndexJ*SpanX-20+Width/3,TopY+5*SpanY+Height*2/3);								
						delay(80);					
						
					}
					g.setColor (old);
					if(compare(m_TR2[m_nIndexI],m_TR2[m_nIndexJ]))
						nextStep = 21;
					else
						nextStep = 22;
					break;
			case 21:
					m_TR1[m_nIndexK] = m_TR2[m_nIndexI];
					m_nIndexI++;
					nextStep = 23;
					break;
			case 22:
					m_TR1[m_nIndexK] = m_TR2[m_nIndexJ];
					m_nIndexJ++;
					nextStep = 23;
					break;
			case 23:
					nextStep = 18;
					break;
			case 24:
					if(m_nIndexI<=m_nM) 
						for(int i=m_nIndexK;i<=m_nN;i++)
							m_TR1[i] = m_TR2[m_nIndexI+i-m_nIndexK];
					nextStep = 25;
					break;
			case 25:
					if(m_nIndexJ<=m_nN)
						for(int i=m_nIndexK;i<=m_nN;i++)
							m_TR1[i] = m_TR2[m_nIndexJ+i-m_nIndexK];
					nextStep = 26;
					break;
			case 26:
					for(int i=m_nS;i<=m_nT;i++)
							m_TR2[i] = m_TR1[i];
					nextStep = 13;
					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,y+12);
		g.drawLine (x+1,y,x+1,y+12);
		g.drawLine (x,y,x-3,y+3);
		g.drawLine (x+1,y,x+4,y+3);		
		g.setColor (Color.red );
		g.drawString(""+c,x,y+20);
		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);
							m_offG.drawString (""+m_Data[i],TopX+i*SpanX-20+Width/3,TopY+SpanY+Height*2/3);
						}
						
						m_offG.drawString("SR：",TopX,TopY+4*SpanY);
						m_offG.drawString("TR：",TopX,TopY+9*SpanY);
						
						for(int i=1;i<=m_nCount;i++)
						{
							m_offG.drawRect (TopX+i*SpanX-20,TopY+5*SpanY,Width,Height);
							
							if(i==m_nS)
								drawArrow(m_offG,TopX+i*SpanX-20+3,TopY+7*SpanY,'s');
							if(i==m_nT)
								drawArrow(m_offG,TopX+i*SpanX+3,TopY+7*SpanY,'t');
							if(i==m_nS||i==m_nT)
							{
								m_offG.setColor (Color.cyan );
								m_offG.fillRect (TopX+i*SpanX-20,TopY+5*SpanY,Width,Height);	
								m_offG.setColor (Color.black );								
							}							
							m_offG.drawString (""+m_TR1[i],TopX+i*SpanX-20+Width/3,TopY+5*SpanY+Height*2/3);								
						}
						
						for(int i=1;i<=m_nCount;i++)
						{
							m_offG.drawRect (TopX+i*SpanX-20,TopY+10*SpanY,Width,Height);
							if(i==m_nIndexI)
								drawArrow(m_offG,TopX+i*SpanX-20+3,TopY+12*SpanY,'i');
							if(i==m_nIndexJ)
								drawArrow(m_offG,TopX+i*SpanX-10+3,TopY+12*SpanY,'j');
							if(i==m_nIndexK)
								drawArrow(m_offG,TopX+i*SpanX+3,TopY+12*SpanY,'k');
							
							if(i==m_nIndexI||i==m_nIndexJ||i==m_nIndexK)
							{
								m_offG.setColor (Color.cyan );								
								m_offG.fillRect (TopX+i*SpanX-20,TopY+10*SpanY,Width,Height);
								m_offG.setColor (Color.black );
							}
							
							m_offG.drawString (""+m_TR2[i],TopX+i*SpanX-20+Width/3,TopY+10*SpanY+Height*2/3);
						}
						
						break;
			case Over:
						m_offG.drawString ("排序数据：",TopX,TopY);
						m_offG.drawString ("排序结果：",TopX,TopY+4*SpanY);
						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);	
							
							m_offG.drawRect (TopX+i*SpanX-20,TopY+5*SpanY,Width,Height);							
							m_offG.drawString (""+m_TR1[i],TopX+i*SpanX-20+Width/3,TopY+5*SpanY+Height*2/3);														
						}						
						break;
		}
		g.drawImage (m_offImg,0,0,this);
		
	}
	class Stack{
		public  int m_nS,m_nT,m_nM;				
		public  int nextStep;				
	}
	
}