demo.java

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

import java.awt.*;


public class Demo extends Canvas implements NodeInterface 
{
	private		DNode	m_Data[];
	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		boolean m_bStepInto=false;
	
	
	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++)
		{
			if(i!=0)m_Data[i].m_cData =sData.charAt(i-1);
			else m_Data[i].m_cData='\0';
			m_Data[i].m_nLink =0;
			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;
		if(m_bSortType)
			m_Data[0].m_cData =0xff;
		else
			m_Data[0].m_cData =0;		
		
	}
	public void reset()
	{
		m_nStep=-1;
		m_nStatus=NO_START;
		m_bSortType=true;
		m_bStepInto=false;
		m_nIIndex=0;
		m_nJIndex=0;
		m_nKIndex=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;
					nextStep=0;
					break;
			case 0:
					nextStep=2;
					break;
			case 2:
					//m_Data[0].m_cData =(char)0xff;
					nextStep=3;
					break;
			case 3:
					m_Data[0].m_nLink =1;
					m_Data[1].m_nLink =0;
					nextStep=4;
					m_nIIndex=1;
					break;
			case 4:
					m_nIIndex++;
					m_nJIndex=0;
					m_nKIndex=0;
					if(m_nIIndex<=m_Data.length-1)
						nextStep=5;
					else
						nextStep=11;
					break;
			case 5:	
					m_nJIndex=m_nKIndex;
					m_nKIndex=m_Data[m_nKIndex].m_nLink ;
					Graphics g=getGraphics();
					repaint();
					for(int i=0;i<3;i++)
					{
						m_Data[m_nKIndex].drawData (g,Color.yellow ,Color.cyan );
						m_Data[m_nIIndex].drawData (g,Color.yellow ,Color.cyan );					
						delay(120);
						m_Data[m_nKIndex].drawData (g,Color.yellow ,Color.red );
						m_Data[m_nIIndex].drawData (g,Color.yellow ,Color.red );					
						delay(120);
					}
					if(compare(m_Data[m_nKIndex].m_cData ,m_Data[m_nIIndex].m_cData ))
					{				
						nextStep=7;						
					}
					else
					{
						nextStep=8;
					}
					break;
			case 7:
					nextStep=5;
					break;
					
			case 8:
					m_Data[m_nJIndex].m_nLink =m_nIIndex;					
					nextStep=9;
					break;
			case 9:
					m_Data[m_nIIndex].m_nLink =m_nKIndex;				
					nextStep=10;
					break;
			case 10:					
					nextStep=4;
					break;
			case 11:
					//break;
					
					arrange();
					nextStep=12;
					break;
			case 12:
					m_nStatus=HAS_OVER;
					nextStep=-1;
					break;
			case 20:
					m_bStepInto=true;
					nextStep=22;
					m_nIIndex=0;
					m_nJIndex=-1; //p
					m_nKIndex=-1; //q
					break;
			case 22:
					m_nJIndex=m_Data[0].m_nLink ;
					nextStep=23;					
					break;
			case 23:
					m_nIIndex++;
					if(m_nIIndex<m_Data.length)
						nextStep=25;
					else
						nextStep=33;
					break;
			case 25:
					if(m_nJIndex<m_nIIndex)
					{
						m_nJIndex=m_Data[m_nJIndex].m_nLink ;
						nextStep=25;
					}
					else
						nextStep=26;
					break;
			case 26:
					m_nKIndex=m_Data[m_nJIndex].m_nLink ;
					nextStep=27;
					break;
			case 27:
					if(m_nJIndex!=m_nIIndex)
						nextStep=28;
					else
						nextStep=30;
					break;
			case 28:	
									
										
					swapNode(m_nIIndex,m_nJIndex);					
					nextStep=29;					
					break;
			case 29:
					m_Data[m_nIIndex].m_nLink =m_nJIndex;
					nextStep=30;
					break;
			case 30:
					nextStep=31;
					break;
			case 31:
					m_nJIndex=m_nKIndex;
					nextStep=32;
					break;
			case 32:
					nextStep=23;
					break;
			case 33:	
					nextStep=12;
					m_bStepInto=false;
					break;						
	
		}
		repaint();
		return nextStep;	
	}
	/*
	"void Arrange ( Elem SL[ ], int n )                ",		//0
	    "{                                                 ",		//1	
		"    p = SL[0].next;                               ",		//2
		"    for ( i=1; i<n; ++i )                         ",		//3
		"    {                                             ",		//4	
		"         while (p<i) p = SL[p].next;              ",		//5
		"         q = SL[p].next;                          ",		//6
		"         if ( p!= i ) {                           ",		//7
	    "            SL[p]←→SL[i];                       ", 		//8				
		"            SL[i].next = p;                       ",		//9
	    "         }                                        ",		//10
		"         p = q;                                   ",		//11
		"    }                                             ",		//12
	    "} // Arrange                                      "		//13
	*/
		
	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+(1+i)*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+1)*SpanX+Width/3+1,TopY+Height*7/6);
		}
		
	}
	public void arrange()
	{
		int p=m_Data[0].m_nLink ;
		for(int i=1;i<m_Data.length ;i++)
		{
			while(p<i) p=m_Data[p].m_nLink ;
			int q=m_Data[p].m_nLink ;
			if(p!=i){
				char ch=m_Data[p].m_cData ;
				m_Data[p].m_cData =m_Data[i].m_cData ;
				m_Data[p].m_nLink =m_Data[i].m_nLink; 
				m_Data[i].m_cData =ch;
				m_Data[i].m_nLink =p;
			}
			p=q;
		}		
	}
	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_nKIndex)
				m_Data[i].drawData (g,Color.yellow ,Color.magenta);
			else				
				m_Data[i].drawData (g,fg,bk);
			if(i==m_nIIndex||i==m_nKIndex||i==m_nJIndex)
				m_Data[i].drawLink(g,Color.green ,Color.pink.darker () );
			else
				m_Data[i].drawLink (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=0;i<m_Data.length ;i++)
		{
			m_Data[i].drawData (g,old,color);
			m_Data[i].drawLink (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>=1&&m_nIIndex<m_Data.length )
								drawArrow('i',m_nIIndex,12,Color.blue ,m_offG);
							if(!m_bStepInto){
								if(m_nJIndex>=0)
									drawArrow('j',m_nJIndex,12,Color.blue ,m_offG);
								if(m_nKIndex>=0)
									drawArrow('k',m_nKIndex,12,Color.blue,m_offG);
							}else{
								if(m_nJIndex>=0)
									drawArrow('p',m_nJIndex,13,Color.red ,m_offG);
								if(m_nKIndex>=0)
									drawArrow('q',m_nKIndex,12,Color.blue,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){}
	}
	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=25;
		
		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 ;
		int  link=m_Data[i].m_nLink ;
		
		m_Data[i].m_cData =m_Data[j].m_cData ;	
		
		m_Data[j].m_cData =tc;
		m_Data[j].m_nLink =link;
		
		m_Data[i].setXY (TopX+SpanX*i,TopY+SpanY*8);
		m_Data[j].setXY (TopX+SpanX*j,TopY+SpanY*8);
	}
	
	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*3/2+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="";
			if(m_cData==0xff) c="MAX";			
			else if(m_cData==0) c="MIN";
			else 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 drawLink(Graphics g,Color fgColor,Color bkColor)
		{
			int h=m_nHeight/2;
			Color old_fg=g.getColor ();
			g.setColor (fgColor);
			g.draw3DRect (m_nX,m_nY+m_nHeight,m_nWidth,h,false);
			g.setColor (bkColor);
			g.fillRect (m_nX+2,m_nY+m_nHeight+2,m_nWidth-4,h-4);
			g.setColor (fgColor);
			String str=""+m_nLink;			
			g.drawString (str,m_nX+m_nWidth/3+1,m_nY+m_nHeight+h*2/3+2);
			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);			
			drawLink(g,Color.black ,Color.lightGray);
		}
		public void setXY(int x,int y)
		{
			m_nX=x;
			m_nY=y;
		}
	}
	
}