demo.java

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

import java.awt.*;

public class Demo extends Canvas 
{
	public final int	NO_START	=-1;
	public final int	HAS_START	=0;
	public final int	HAS_OVER	=1;		
	
	public int	TopX		=20;
	public int	TopY		=20;		
	public int	SpanX		=36;		
	public int	SpanY		=15;
	public int	Width		=27;
	public int  Height		=27;	
	
	
	
	private		DNode	m_Data[];
	private		String	m_sOld;
	private		int		m_nStep=0;
	private		boolean m_bSortType=true;
	private		boolean m_bStepInto=true;
	
	private		int		m_nStatus=NO_START;
	
	private		int		m_nLow	=0;
	private		int		m_nHigh	=0;


	private		int		m_nPivotLoc=0;
	private		char	m_cPivotKey;
	
	public		Stack	stack[];
	private		int		pos=-1;
	
	
	
	private		Graphics	m_Graph;
	private		Graphics	m_offG;
	private		Image		m_offImg;
	
	
	
	public void setData(String sData,boolean bool,boolean bStep)
	{
		if(m_Graph==null) m_Graph=getGraphics();
		
		int num=sData.length ();
		m_sOld=sData;		
		
		m_nStatus	=HAS_START;
		
		m_Data=new DNode [num+1];
		if(stack==null)
		{
			stack =new Stack [15];
			for(int i=0;i<15;i++)
				stack[i]=new Stack();
		}
		
		for(int i=0;i<num+1;i++)
		{
			m_Data[i]=new DNode();
		}				
		
		for(int i=0;i<num+1;i++)
		{
			if(i==0)
				m_Data[i].m_cData =' ';				
			else
				m_Data[i].m_cData =sData.charAt(i-1);						
			m_Data[i].m_nX=i*SpanX+TopX;
			m_Data[i].m_nY=8*SpanY+TopY;
			m_Data[i].m_nWidth =Width;
			m_Data[i].m_nHeight=Height;
		}		
		
		
		m_nStatus	=NO_START;
		m_bSortType	=bool;
		m_bStepInto =bStep;
		m_nStep		=-1;
		pos			=-1;
		m_nLow	=0;
		m_nHigh	=0;		
		
		m_Data[0].m_cData =0x20;
	
		
	}
	public void reset()
	{
		m_nStep=-1;
		pos=-1;
		m_nStatus=NO_START;
		m_bSortType=true;		
		m_nLow=0;
		m_nHigh=0;	
		repaint();		
	}
	public void setStep(boolean bool)
	{
		m_bStepInto = bool;
	}
	
	private boolean compare(char ch1,char ch2)
	{		
		if(m_bSortType)
			return(ch1<ch2);
		return(ch1>ch2);		
	}
	private void QSort(DNode s[],int low,int high)
	{
		if(low<high)
		{
			int pivotLoc = Partition(s,low,high);
			QSort(s,low,pivotLoc-1);
			QSort(s,pivotLoc+1,high);
		}
	}					   

	public int proceed(int nStep)
	{
		int nextStep=-1;
		
		switch(nStep)
		{
			case -1:				
					m_nStatus=HAS_START;
					nextStep=0;
					break;
			case 0:					
					nextStep=2;
					break;
			case 2:if(m_bStepInto)
				   {
						pos++;
						if(pos>=0){
							stack[pos].low =1;
							stack[pos].high =m_Data.length-1;
							stack[pos].nextStep =3;											
							nextStep=5;
							m_nLow=1;
							m_nHigh=m_Data.length-1;
						}else{
							nextStep=5;
						}
				   }else{
					   QSort(m_Data,1,m_Data.length -1);
					   nextStep =3;
				   }
					   
					break;
			case 3:
					nextStep=-1;
					m_nStatus=HAS_OVER;
					break;
			case 5:						
					nextStep=7;
					break;
			case 7: 
					if(m_nLow<=m_nHigh-1)										
						nextStep=9;
					else
						nextStep=12;
					break;
			case 9:
					if(m_bStepInto)
					{
						pos++;
						stack[pos].low =m_nLow;
						stack[pos].high =m_nHigh;
						stack[pos].nextStep=10;
						nextStep=15;
					}else{
						m_nPivotLoc=Partition(m_Data,m_nLow,m_nHigh);					
						nextStep = 10;
					}
					break;
			case 10:
					if(m_bStepInto)
					{
						pos++;
						stack[pos].low =m_nLow;
						stack[pos].high=m_nHigh;
						stack[pos].pivotloc =m_nPivotLoc;
						stack[pos].nextStep =11;					
						m_nHigh=m_nPivotLoc-1;
						nextStep=5;
					}else{
						QSort(m_Data,m_nLow,m_nPivotLoc-1);
						nextStep =11;
					}
						
					break;
			case 11:
					if(m_bStepInto)
					{
						pos++;
						stack[pos].low =m_nLow;
						stack[pos].high =m_nHigh;
						stack[pos].pivotloc =m_nPivotLoc;
						stack[pos].nextStep =12;
						m_nLow=m_nPivotLoc+1;					
						nextStep=5;
					}else{
						QSort(m_Data,m_nPivotLoc+1,m_nHigh);
						nextStep = 12;
					}
					
					break;
			case 12:
					nextStep=13;
					break;
			case 13:
					m_nLow=stack[pos].low ;
					m_nHigh=stack[pos].high ;
					m_nPivotLoc=stack[pos].pivotloc;
					nextStep=stack[pos].nextStep;
					pos--;
					break;
		case 15:
					nextStep=17;
					break;
		case 17:
					
					moveNode(m_nLow,0);
					
					//m_Data[0].m_cData =m_Data[m_nLow].m_cData ;
					nextStep=18;
		case 18:				
					nextStep=19;
		case 19:
					if(m_nLow<m_nHigh)
						nextStep=21;
					else
						nextStep=28;
					break;
		case 21:
					if(m_nLow<m_nHigh)
					{
						Graphics g=getGraphics();
						for(int i=0;i<3;i++)
						{
							m_Data[0].drawData (g,Color.yellow ,Color.cyan );
							m_Data[m_nHigh].drawData (g,Color.yellow ,Color.cyan );					
							delay(120);
							m_Data[0].drawData (g,Color.yellow ,Color.red );
							m_Data[m_nHigh].drawData (g,Color.yellow ,Color.red );					
							delay(120);
						}
						if(compare(m_Data[0].m_cData,m_Data[m_nHigh].m_cData ))
							nextStep=22;
						else 
							nextStep=23;
					}
					else
						nextStep=23;
					break;
		case 22:
					m_nHigh--;
					nextStep=21;
					break;
		case 23:
					moveNode(m_nHigh,m_nLow);
					
					//m_Data[m_nLow].m_cData =m_Data[m_nHigh].m_cData ;
					nextStep=24;
					break;
		case 24:
					if(m_nLow<m_nHigh)
					{
						Graphics g=getGraphics();
						for(int i=0;i<3;i++)
						{
							m_Data[0].drawData (g,Color.yellow ,Color.cyan );
							m_Data[m_nLow].drawData (g,Color.yellow ,Color.cyan );					
							delay(120);
							m_Data[0].drawData (g,Color.yellow ,Color.red );
							m_Data[m_nLow].drawData (g,Color.yellow ,Color.red );					
							delay(120);
						}
						if(compare(m_Data[m_nLow].m_cData ,m_Data[0].m_cData ))
							nextStep=25;
						else 
							nextStep=26;
					}
					else
						nextStep=26;
					break;
		case 25:
					m_nLow++;
					nextStep=24;
					break;
		case 26:					
					moveNode(m_nLow,m_nHigh);
					
					//m_Data[m_nHigh].m_cData =m_Data[m_nLow].m_cData ;
					nextStep=27;
					break;
		case 27:
					nextStep=19;
					break;					
		case 28:
					moveNode(0,m_nLow);
					//m_Data[m_nLow].m_cData =m_Data[0].m_cData ;
					nextStep=29;
					break;
		case 29:
					stack[pos].pivotloc =m_nLow;
					nextStep=30;
					break;
		case 30:
					m_nLow=stack[pos].low ;
					m_nHigh=stack[pos].high;
					m_nPivotLoc=stack[pos].pivotloc;
					nextStep=stack[pos].nextStep ;
					pos--;
					break;					
		}
		repaint();
		return nextStep;	
	}
	private void moveNode(int i,int j)
	{
	
		int x1=TopX+SpanX*i;
		int y1=TopY+SpanY*8;
		int x2=TopX+SpanX*j;
		int y2=TopY+SpanY*8;
		int dx=(x2-x1)/6;
		int dy=30;
		
		if(i==j) return;
		Graphics g=getGraphics();
		
		m_Data[i].moveTo (g,Color.yellow ,Color.magenta,x1,y1-dy);			
		delay(30);
		y1-=dy;		
		
		for(int k=0;k<6;k++)
		{
			m_Data[i].moveTo (g,Color.yellow ,Color.magenta ,x1+dx,y1);			
			delay(50);
			x1+=dx;
			
		}
		m_Data[i].moveTo (g,Color.yellow ,Color.magenta,x1,y1+dy);			
		delay(30);
		y1+=dy;			
		
		delay(80);
		m_Data[j].m_cData =m_Data[i].m_cData ;		
		m_Data[i].setXY (TopX+SpanX*i,TopY+SpanY*8);
		m_Data[j].setXY (TopX+SpanX*j,TopY+SpanY*8);
		
	}
	public int Partition(DNode data[],int low,int high)
	{		
		char pivotkey;
		data[0].m_cData =data[low].m_cData ;
		pivotkey=data[low].m_cData ;
		while(low<high)
		{
			while(low<high&&compare(pivotkey,data[high].m_cData ))
				high--;
			data[low].m_cData=data[high].m_cData ;
			while(low<high&&compare(data[low].m_cData ,pivotkey))
				low++;
			data[high].m_cData =data[low].m_cData;
		}
		data[low].m_cData =data[0].m_cData ;
		return low;		
	}

		
	public void update(Graphics g)
	{
		paint(g); 
	} 
	public void addNotify()
	{ 
		super.addNotify(); 
		m_offImg = createImage(getSize().width-TopX, getSize().height-TopY);
		m_offG = m_offImg.getGraphics(); 
	}
	public void drawInit(Graphics g)
	{
		g.drawString ("初始数据：",TopX,TopY);				
		Color old=g.getColor ();
		Color color=Color.lightGray;
					  
		for(int i=0;i<m_sOld.length();i++)
		{
			g.drawRect (TopX+i*SpanX+SpanX,TopY+Height/2,Width,Height);
			g.setColor(color );			
			//g.fillRect (TopX+(1+i)*SpanX,TopY+Height/2,Width,Height);
			g.setColor (old);
			String c=""+m_sOld.charAt(i);			
			g.drawString(c,TopX+i*SpanX+Width/3+1+SpanX,TopY+Height*7/6);
		}
		
	}
	public void drawData(Graphics g)
	{		
		Color fg=Color.black ;		
		Color bk=getBackground() ;
		for(int i=0;i<m_Data.length ;i++)
		{			
			if(i==m_nLow||i==m_nHigh)
				m_Data[i].drawData (g,Color.yellow ,Color.magenta);
			else				
				m_Data[i].drawData (g,fg,bk);			
			
		}
	}
	private void drawNo(Graphics g)
	{
		
		for(int i=0;i<m_Data.length ;i++)
		{
			String str="";
			str=str+i;
			g.drawString (str,TopX+i*SpanX+Width/3-str.length ()+1,TopY+7*SpanY+SpanX/3);
		}
	}
	private void drawResult(Graphics g)
	{
		g.drawString ("排序结果：",TopX,TopY+8*SpanY-Height/3);				
		Color old=g.getColor ();
		Color color=Color.lightGray;
					  
		for(int i=1;i<m_Data.length ;i++)
		{
			m_Data[i].drawData (g,old,color);			
		}	
	}
	private void drawArrow(char ch,int cx,int cy,Color color,Graphics g)
	{
		
		Color old=g.getColor ();
		g.setColor(color);
		
		String s="";
		if(ch=='i')
			s=s+"L";
		else
			s=s+"H";
		
		int x=TopX+cx*SpanX+Width/3-4;
		int y=TopY+cy*SpanY+Height/5-5;
		g.drawString(s,x,y);			
		x=x+10;y=y-Height/3;
		g.drawLine (x,y,x,y+15);
		g.drawLine (x+1,y,x+1,y+15);		
		g.drawLine (x+1,y,x+3,y+5);
		g.drawLine (x,y,x-2,y+5);
		g.setColor (old);	
	}
	
	public void paint(Graphics g)
	{
		m_offG.clearRect (0,0,getSize().width,getSize().height );
		switch(m_nStatus)
		{
			case NO_START://null paint 						
								
								break;			
			case HAS_START://draw init data
							drawInit(m_offG);
							drawNo(m_offG);
							drawData(m_offG);													
							if(m_nLow>=1&&m_nLow<m_Data.length )
								drawArrow('i',m_nLow,12,Color.blue ,m_offG);
							if(m_nHigh>=m_nLow&&m_nHigh>=1)
								drawArrow('j',m_nHigh,11,Color.red ,m_offG);							
							break;
			
			case HAS_OVER:	//drawData(true,m_offG);			//draw init data
							drawInit(m_offG);
							drawResult(m_offG);														
							break;			
		}	
		g.drawImage (m_offImg,0,0,this);
	}
	public void delay(int time)	
	{
		try{ Thread.sleep(time); }
		catch(InterruptedException e){}
	}
	
	private class DNode
	{
		public char			m_cData;
		public int			m_nLink=0;
		public int			m_nX=0;
		public int			m_nY=0;
		public int			m_nWidth=0;
		public int			m_nHeight=0;
		
		public void clearNode(Graphics g)
		{
			g.clearRect (m_nX-1,m_nY-1,m_nWidth+2,m_nHeight+2);			
		}
		public void drawData(Graphics  g,Color fgColor,Color bkColor)
		{	
			Color old_fg=g.getColor ();	
			g.setColor(fgColor);
			g.draw3DRect(m_nX,m_nY,m_nWidth,m_nHeight,true);			
			g.setColor(bkColor);		
			g.fillRect(m_nX+2,m_nY+2,m_nWidth-4,m_nHeight-4);		
			g.setColor(fgColor);
					
			String c="";
			c=c+m_cData;
			g.drawString(c,m_nX+m_nWidth/3+1-c.length (),m_nY+m_nHeight*2/3+1);			
			g.setColor(old_fg);
		}		
		public void moveTo(Graphics g,Color fgColor,Color bkColor,int x,int y)
		{
			clearNode(g);
			m_nX=x;
			m_nY=y;
			drawData(g,fgColor,bkColor);			
		}
		public void setXY(int x,int y)
		{
			m_nX=x;
			m_nY=y;
		}
	
	}
	class Stack
	{
		public int low;
		public int high;
		public int pivotloc;
		public int nextStep;
	}
}