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		int		m_delta[]=new int [4];
	private		String	m_sOld;
	private		int		m_nStep=0;
	private		boolean m_bSortType=true;
	private		int		m_nStatus=NO_START;
	
	private		int		m_nIIndex=0;
	private		int		m_nJIndex=0;
	private		int		m_nKIndex=0;
	private		int		m_nPass=0;
	private		int		m_nDk;
	
	
	
	private		Graphics	m_Graph;
	private		Graphics	m_offG;
	private		Image		m_offImg;
	
	
	public void setData(String sData,boolean bool)
	{
		if(m_Graph==null) m_Graph=getGraphics();
		
		int num=sData.length ();
		m_sOld=sData;		
		
		m_nStatus	=HAS_START;
		
		m_Data=new DNode [num+1];
		for(int i=0;i<num+1;i++)
		{
			m_Data[i]=new DNode();
		}				
		
		for(int i=0;i<num+1;i++)
		{
			m_Data[i].m_cData=0x20;
			if(i!=0)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_nStep		=-1;
		m_nIIndex	=0;
		m_nJIndex	=0;
		m_nKIndex	=0;		
		
		m_Data[0].m_cData =0x20;
		
		m_delta[0]=5;
		m_delta[1]=3;
		m_delta[2]=2;
		m_delta[3]=1;		
		m_nPass=0;
	}
	public void reset()
	{
		m_nStep=-1;
		m_nStatus=NO_START;
		m_bSortType=true;	
		m_nIIndex=0;
		m_nJIndex=0;
		m_nKIndex=0;		
		m_nPass=0;		
		repaint();
		
	}
	
	private boolean compare(char ch1,char ch2)
	{		
		if(m_bSortType)
			return(ch1<ch2);
		return(ch1>ch2);		
	}

	public int proceed(int nStep)
	{
		int nextStep=-1;
		switch(nStep)
		{
			case -1:
					m_nStatus=HAS_START;
					m_nPass=0;
					nextStep=0;
					break;
			case 0:
					nextStep=2;
					m_nKIndex=-1;
					break;
			case 2:
					m_nKIndex++;
					if(m_nKIndex<m_delta.length )
						nextStep=3;
					else
						nextStep=14;
					break;
			case 3:
					m_nDk=m_delta[m_nKIndex];
					m_nPass++;
					m_nIIndex=m_nDk;
					nextStep=4;
					break;
					
			case 4:
					m_nIIndex++;
					if(m_nIIndex<m_Data.length )
						nextStep=6;
					else 
						nextStep=13;
					break;			
			case 6:
					Graphics g=getGraphics();
					for(int i=0;i<3;i++)
					{
						m_Data[m_nIIndex].drawData (g,Color.yellow ,Color.cyan );
						m_Data[m_nIIndex-m_nDk].drawData (g,Color.yellow ,Color.cyan );					
						delay(120);
						m_Data[m_nIIndex].drawData (g,Color.yellow ,Color.red );
						m_Data[m_nIIndex-m_nDk].drawData (g,Color.yellow ,Color.red );					
						delay(120);
					}
					if(compare(m_Data[m_nIIndex].m_cData ,m_Data[m_nIIndex-m_nDk].m_cData))
						nextStep=7;
					else
						nextStep=4;
					break;
			case 7:
					moveNode(m_nIIndex,0);
					//m_Data[0].m_cData =m_Data[m_nIIndex].m_cData ;
					nextStep=8;
					m_nJIndex=m_nIIndex;
					break;
			case 8:
					m_nJIndex-=m_nDk;
					if((m_nJIndex>0)&&(compare(m_Data[0].m_cData ,m_Data[m_nJIndex].m_cData)))
						nextStep=9;
					else
						nextStep=10;
					break;
			case 9:
					//swapNode(m_nIIndex,m_nJIndex);					
					moveNode(m_nJIndex,m_nJIndex+m_nDk);
					//m_Data[m_nJIndex+m_nDk].m_cData =m_Data[m_nJIndex].m_cData ;					
					nextStep=8;
					break;
			case 10:
					moveNode(0,m_nJIndex+m_nDk);
					//m_Data[m_nJIndex+m_nDk].m_cData =m_Data[0].m_cData ;
					nextStep=11;
					break;
			case 11:					
					nextStep=12;
					break;
			case 12:
					nextStep=4;
					break;
			case 13:
					nextStep=2;
					break;
			case 14:
					nextStep=-1;
					m_nStatus=HAS_OVER;
					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=-20;
		
		Graphics g=getGraphics();
		
		for(int k=1;k<3;k++)
		{
			m_Data[i].moveTo (g,Color.yellow ,Color.magenta,x1,y1-dy);			
			delay(80);
			y1-=dy;		
			
		}
		for(int k=0;k<6;k++)
		{
			m_Data[i].moveTo (g,Color.yellow ,Color.magenta ,x1+dx,y1);			
			delay(80);
			x1+=dx;
			
		}
		for(int k=1;k<3;k++)
		{
			m_Data[i].moveTo (g,Color.yellow ,Color.magenta,x1,y1+dy);			
			delay(80);
			y1+=dy;			
		}		
		m_Data[j].m_cData =m_Data[i].m_cData ;
		//m_Data[j].m_cData =tc;
		m_Data[i].setXY (TopX+SpanX*i,TopY+SpanY*8);
		m_Data[j].setXY (TopX+SpanX*j,TopY+SpanY*8);
		
	}
	public void swapNode(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)/5;
		int dy=20;
		
		Graphics g=getGraphics();
		
		for(int k=1;k<3;k++)
		{
			m_Data[i].moveTo (g,Color.yellow ,Color.magenta,x1,y1-dy);
			m_Data[j].moveTo (g,Color.yellow ,Color.magenta ,x2,y2+dy);			
			delay(50);
			y1-=dy;
			y2+=dy;
			
		}
		for(int k=0;k<5;k++)
		{
			m_Data[i].moveTo (g,Color.yellow ,Color.magenta ,x1+dx,y1);
			m_Data[j].moveTo (g,Color.yellow ,Color.magenta ,x2-dx,y2);
			delay(50);
			x1+=dx;
			x2-=dx;
		}
		for(int k=1;k<3;k++)
		{
			m_Data[i].moveTo (g,Color.yellow ,Color.magenta,x1,y1+dy);
			m_Data[j].moveTo (g,Color.yellow ,Color.magenta ,x2,y2-dy);			
			delay(50);
			y1+=dy;
			y2-=dy;
		}
		char tc=m_Data[i].m_cData ;
		m_Data[i].m_cData =m_Data[j].m_cData ;
		m_Data[j].m_cData =tc;
		m_Data[i].setXY (TopX+SpanX*i-SpanX/2,TopY+SpanY*8);
		m_Data[j].setXY (TopX+SpanX*j-SpanX/2,TopY+SpanY*8);
	}
		
	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+SpanX+Width/3+1,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_nIIndex||i==m_nJIndex||i==0||(i==m_nJIndex+m_nDk&&(m_nJIndex+m_nDk<m_nIIndex)))
				m_Data[i].drawData (g,Color.yellow ,Color.magenta);
			else				
				m_Data[i].drawData (g,fg,bk);
			
		}
		if(m_nPass>0)
		{
			g.drawString ("Pass="+m_nPass+" "+" dk="+m_nDk+" "+" t=4",20,SpanY*7);			
		}
	}
	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=""+ch;			
		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_nIIndex>m_nDk&&m_nIIndex<m_Data.length )
								drawArrow('i',m_nIIndex,11,Color.blue ,m_offG);
							if(m_nJIndex>0&&m_nJIndex!=m_nIIndex)
								drawArrow('j',m_nJIndex,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;
		}
	
	}
}