order.cpp

几种排序算法的动画演示,包括冒泡排序,选择排序,插入排序,快速排序,堆排序,支持单步演示,

	i=0;
	SelectDraw();
}
void COrder::HeapFirst(void)
{
	p=(n-1)/2;
	i=p;
	j=n;
	adjust=1;
	HeapDraw();
}
int COrder::First(void)
{	
	if (Work<=Work_Heap)
	{	
		Step=0;
		m=i=j=f=u=d=p=adjust=-1;
		for (int a=0;a<n;a++)
		{
			Current[a]=Arrow[a];
			Finish[a]=0;
		}
		DrawSrc();
	}
	if (Work==Work_Bubble)BubbleFirst();
	if (Work==Work_Insert)InsertFirst();
	if (Work==Work_Select)SelectFirst();
	if (Work==Work_Quick)QuickFirst();
	if (Work==Work_Heap)HeapFirst();
	if (Work==Work_Add)AddFirst();
	if (Work==Work_Find)FindFirst();
	return 0;
}
void COrder::DrawSrc(void)
{
	Cls(0,0,Width,Height,GetSysColor(COLOR_BTNFACE));
	RECT r;
	char * tStr;
	r.top=8;
	r.left=8;
	r.bottom=r.top+8+24+8;;
	r.right =r.left+8+72+8+n*(24+8);
	DrawEdge(hDC,&r,EDGE_ETCHED,BF_RECT|BF_MIDDLE);
	r.left=8+8;
	r.right=r.left+72;
	r.top =8+8;
	r.bottom=r.top+24;
	DrawText(hDC,"原始数组:",9,&r,DT_VCENTER|DT_SINGLELINE);
	//tStr=Str(n);
	//DrawText(hDC,tStr,lstrlen(tStr),&r,DT_RIGHT|DT_VCENTER|DT_SINGLELINE);
	SetBkColor(hDC,0x80FF80);
	HBRUSH hBrush=CreateSolidBrush(0x80FF80);
	for (int a=0;a<n;a++)
	{
		r.left=8+8+72+8+a*(24+8);
		r.right=r.left+24;
		FillRect(hDC,&r,hBrush);
		DrawEdge(hDC,&r,EDGE_BUMP,BF_RECT);
		tStr=Str(Arrow[a]);/////////////////////////////////////////////////////////////////
		DrawText(hDC,tStr,lstrlen(tStr),&r,DT_CENTER|DT_VCENTER|DT_SINGLELINE);
	}
	DeleteObject(hBrush);
	SetBkColor(hDC,GetSysColor(COLOR_BTNFACE));
	HDC hDCDest=GetDC(hWnd);
	GetWindowRect (hWnd,&r);
	r.right-=r.left ;
	r.bottom-=r.top;
	BitBlt(hDCDest,0,0 ,r.right,r.bottom,hDC,0,0,SRCCOPY);
	ReleaseDC(hWnd,hDCDest);
}
void COrder::Cls(int x,int y,int cx,int cy,DWORD Color)
{
	RECT r;
	r.left=x;
	r.top=y;
	r.right=r.left+cx;
	r.bottom=r.top+cy;
	HBRUSH hBrush=CreateSolidBrush(Color);
	FillRect(hDC,&r,hBrush);
	DeleteObject(hBrush);
}
void COrder::Paint(HWND hWndDest)
{
	hWnd=hWndDest;
	PAINTSTRUCT ps;
	HDC hDCDest=BeginPaint(hWnd,&ps);
	BitBlt(hDCDest,ps.rcPaint.left,ps.rcPaint.top  ,ps.rcPaint.right,ps.rcPaint.bottom,hDC,ps.rcPaint.left ,ps.rcPaint.top ,SRCCOPY);
	EndPaint(hWnd,&ps);
}
void COrder::SelectDraw(void)
{
	BubbleDraw();
}
void COrder::QuickDraw(void)
{
	BubbleDraw();
}
void COrder::DrawVar(void)
{
	RECT r;
	char * tStr;
	r.left=8+8;
	r.right=r.left+72;
	r.top =8+(8+24+8)+8+8;
	r.bottom=r.top+24;
	DrawText(hDC,"运行参数:",9,&r,DT_VCENTER|DT_SINGLELINE);
	r.left=r.right+8;
	r.right=r.left+56;
	DrawEdge(hDC,&r,BDR_SUNKENOUTER,BF_RECT|BF_MIDDLE);
	r.right=r.left+32;
	DrawText(hDC,"I =",3,&r,DT_VCENTER|DT_CENTER|DT_SINGLELINE);
	if (i!=-1)tStr=Str(i);
	else tStr="?";
	r.left=r.right;
	r.right=r.left+24;
	DrawText(hDC,tStr,lstrlen(tStr),&r,DT_VCENTER|DT_SINGLELINE);
	if (j!=-1)
	{
		r.left=r.right+8;
		r.right=r.left+56;
		DrawEdge(hDC,&r,BDR_SUNKENOUTER,BF_RECT|BF_MIDDLE);
		r.right=r.left+32;
		DrawText(hDC,"J =",3,&r,DT_VCENTER|DT_CENTER|DT_SINGLELINE);
		tStr=Str(j);
		r.left=r.right;
		r.right=r.left+24;
		DrawText(hDC,tStr,lstrlen(tStr),&r,DT_VCENTER|DT_SINGLELINE);
	}
	if (m!=-1)
	{
		r.left=r.right+8;
		r.right=r.left+56;
		DrawEdge(hDC,&r,BDR_SUNKENOUTER,BF_RECT|BF_MIDDLE);
		r.right=r.left+32;
		DrawText(hDC,"M =",3,&r,DT_VCENTER|DT_CENTER|DT_SINGLELINE);
		tStr=Str(m);
		r.left=r.right;
		r.right=r.left+24;
		DrawText(hDC,tStr,lstrlen(tStr),&r,DT_VCENTER|DT_SINGLELINE);
	}
	if (f!=-1)
	{
		r.left=r.right+8;
		r.right=r.left+56;
		DrawEdge(hDC,&r,BDR_SUNKENOUTER,BF_RECT|BF_MIDDLE);
		r.right=r.left+32;
		DrawText(hDC,"F =",3,&r,DT_VCENTER|DT_CENTER|DT_SINGLELINE);
		tStr=Str(f);
		r.left=r.right;
		r.right=r.left+24;
		DrawText(hDC,tStr,lstrlen(tStr),&r,DT_VCENTER|DT_SINGLELINE);
	}
	if (d!=-1)
	{
		r.left=r.right+8;
		r.right=r.left+56;
		DrawEdge(hDC,&r,BDR_SUNKENOUTER,BF_RECT|BF_MIDDLE);
		r.right=r.left+32;
		DrawText(hDC,"D =",3,&r,DT_VCENTER|DT_CENTER|DT_SINGLELINE);
		tStr=Str(d);
		r.left=r.right;
		r.right=r.left+24;
		DrawText(hDC,tStr,lstrlen(tStr),&r,DT_VCENTER|DT_SINGLELINE);
	}
	if (u!=-1)
	{
		r.left=r.right+8;
		r.right=r.left+56;
		DrawEdge(hDC,&r,BDR_SUNKENOUTER,BF_RECT|BF_MIDDLE);
		r.right=r.left+32;
		DrawText(hDC,"U =",3,&r,DT_VCENTER|DT_CENTER|DT_SINGLELINE);
		tStr=Str(u);
		r.left=r.right;
		r.right=r.left+24;
		DrawText(hDC,tStr,lstrlen(tStr),&r,DT_VCENTER|DT_SINGLELINE);
	}
	r.top=8+(8+24+8)+8;
	r.left=8;
	r.bottom=r.top+(8+24+8);
	r.right =r.right+8;
	DrawEdge(hDC,&r,EDGE_ETCHED,BF_RECT);
	SetBkColor(hDC,GetSysColor(COLOR_BTNFACE));
	HDC hDCDest=GetDC(hWnd);
	BitBlt(hDCDest,r.left,r.top,r.right-r.left,r.bottom-r.top,hDC,r.left ,r.top,SRCCOPY);
	ReleaseDC(hWnd,hDC);
}
void COrder::HeapDraw(void)
{
	BubbleDraw();
	RECT r;
	int h=1;
	int w=1;
	while (n>w*2)
	{
		w*=2;
		h++;
	}
	r.left=8;
	r.top=8+(8+24+8)+8+(8+24+8)+8+(8+24+8+24+8+24+8)+8;
	r.right=r.left+w*48;
	r.bottom=r.top+h*56+8+8+8;
	DrawEdge(hDC,&r,EDGE_ETCHED,BF_RECT|BF_MIDDLE);
	HBRUSH hBrush,hBrushOld;
	hBrush=CreateSolidBrush(0xC0C0FF);
	hBrushOld=(HBRUSH)SelectObject(hDC,hBrush);
	HPEN hPen,hPenOld;
	hPen=CreatePen(PS_SOLID,1,0xFF0000);
	hPenOld=(HPEN)SelectObject(hDC,hPen);
	COLORREF Color=SetBkColor(hDC,0xC0C0FF);
	DrawNode(0,8,w*48,r.top+8+16);
	SetBkColor(hDC,Color);
	SelectObject(hDC,hBrushOld);
	DeleteObject(hBrush);
	SelectObject(hDC,hPenOld);
	DeleteObject(hPen);
	HDC hDCDest=GetDC(hWnd);
	BitBlt(hDCDest,r.left,r.top,r.right-r.left,r.bottom-r.top,hDC,r.left ,r.top,SRCCOPY);
	ReleaseDC(hWnd,hDC);
}
void COrder::DrawNode(int node, int x, int w, int y)
{
	POINT point;
	if (node*2+1<n)
	{
		MoveToEx(hDC,x+w/2,y,&point);
		LineTo(hDC,x+w/4,y+56);
		DrawNode(node*2+1,x,w/2,y+56);
	}
	if (node*2+2<n) 
	{
		MoveToEx(hDC,x+w/2,y,&point);
		LineTo(hDC,x+w*3/4,y+56);
		DrawNode(node*2+2,x+w/2,w/2,y+56);
	}
	RECT r;
	char *t=Str(Current[node]);
	r.top=y-16;
	r.left=x+w/2-16;
	r.bottom=r.top+32;
	r.right=r.left+32;
	if (Finish[node]==0)
	{
		Ellipse(hDC,x+w/2-16,y-16,x+w/2+16,y+16);
		DrawText(hDC,t,lstrlen(t),&r,DT_CENTER|DT_VCENTER|DT_SINGLELINE);
	}
	else
	{
		HBRUSH hBrush=CreateSolidBrush(0xFFC0C0);
		HBRUSH hBrushOld=(HBRUSH)SelectObject(hDC,hBrush);
		COLORREF cOld=SetBkColor(hDC,0xFFC0C0);
		Ellipse(hDC,x+w/2-16,y-16,x+w/2+16,y+16);
		DrawText(hDC,t,lstrlen(t),&r,DT_CENTER|DT_VCENTER|DT_SINGLELINE);
		SelectObject(hDC,hBrushOld);
		DeleteObject(hBrush);
		SetBkColor(hDC,cOld);
	}
	if (i==node)
	{
		HBRUSH hBrush=CreateSolidBrush(0x80FF80);
		HBRUSH hBrushOld=(HBRUSH)SelectObject(hDC,hBrush);
		COLORREF cOld=SetBkColor(hDC,0x80FF80);
		Ellipse(hDC,x+w/2-16,y-16,x+w/2+16,y+16);
		DrawText(hDC,t,lstrlen(t),&r,DT_CENTER|DT_VCENTER|DT_SINGLELINE);
		SelectObject(hDC,hBrushOld);
		DeleteObject(hBrush);
		SetBkColor(hDC,cOld);
		cOld=SetBkColor(hDC,GetSysColor(COLOR_BTNFACE));
		r.top=y+16+8;
		r.left=x+w/2-12-3;
		r.right=r.left+24;
		r.bottom=r.top+24;
		DrawText(hDC,"I↑",3,&r,DT_CENTER|DT_VCENTER|DT_SINGLELINE);
		if (Step==1)
		{
			int node=i*2+1;
			if (node+1<j && Current[node+1]>Current[node] && Current[node+1]>Current[i])
			{
				r.top=y;
				r.left=x+w/2+16;
				r.right=r.left+24;
				r.bottom=r.top+24;
				DrawText(hDC,"↘",2,&r,DT_VCENTER|DT_SINGLELINE);
			}
			else if (node<j && Current[node]>Current[i])
			{
				r.top=y;
				r.left=x+w/2-16-24;
				r.right=r.left+24;
				r.bottom=r.top+24;
				DrawText(hDC,"↙",2,&r,DT_RIGHT|DT_VCENTER|DT_SINGLELINE);
			}
		}
		SetBkColor(hDC,cOld);
	}
	if (p==node)
	{
		r.top=y+16+8;
		r.left=x+w/2-12+3;
		r.right=r.left+24;
		r.bottom=r.top+24;
		COLORREF cOld=SetBkColor(hDC,GetSysColor(COLOR_BTNFACE));
		DrawText(hDC,"↑P",3,&r,DT_CENTER|DT_VCENTER|DT_SINGLELINE);
		SetBkColor(hDC,cOld);
	}
}
int COrder::Depth(BTNode * node)
{
	if (node==NULL)	return 0;
	int a=Depth(node->left);
	int b=Depth(node->right);
	if (a<b)a=b;
	return a+1;
}
void COrder::TreeDraw(void)
{
	Cls(0,0,Width,Height,GetSysColor(COLOR_BTNFACE));
	RECT r;
	r.top=8;
	r.left=8;
	r.right=r.left+108+56;
	r.bottom=r.top+8+24+8;
    DrawEdge(hDC,&r,EDGE_ETCHED,BF_RECT|BF_MIDDLE);
	r.left=r.left+6;
	DrawText(hDC,"正在查找数据:",13,&r,DT_VCENTER|DT_SINGLELINE);
	r.left=r.left+6*13+6;
	char *t=Str(ToFind);
	DrawText(hDC,t,lstrlen(t),&r,DT_VCENTER|DT_SINGLELINE);
	if (Work==Work_Find)
	{
		r.left=r.left+6*5;
		if (Parent && Parent->value==ToFind) DrawText(hDC,"已找到",6,&r,DT_VCENTER|DT_SINGLELINE);
		else if (Cur==0)DrawText(hDC,"未找到",6,&r,DT_VCENTER|DT_SINGLELINE);
	}
	int d=Depth();
	int w=1;
	for (int h=0;h<d;h++)w*=2;
	w=w/2;
	r.left=8;
	r.top=8+8+24+8+8;
	r.right=r.left+w*48;
	r.bottom=r.top+h*56+8+8+8;
	DrawEdge(hDC,&r,EDGE_ETCHED,BF_RECT);
	SetBkColor(hDC,0x80FF80);
	HBRUSH hBrush=CreateSolidBrush(0x80FF80);
	HBRUSH hBrushOld=(HBRUSH)SelectObject(hDC,hBrush);
	if (Root)DrawBTNode(Root,r.left,w*48,r.top+8+16);
	SelectObject(hDC,hBrushOld);
	DeleteObject(hBrush);
	SetBkColor(hDC,GetSysColor(COLOR_BTNFACE));
	HDC hDCDest=GetDC(hWnd);
	GetWindowRect (hWnd,&r);
	BitBlt(hDCDest,0,0 ,r.right-r.left,r.bottom-r.top,hDC,0,0,SRCCOPY);
	ReleaseDC(hWnd,hDCDest);
}
void COrder::DrawBTNode(BTNode * node, int x,int w, int y)
{
	POINT point;
	if (node->left)
	{
		MoveToEx(hDC,x+w/2,y,&point);
		LineTo(hDC,x+w/4,y+56);
		DrawBTNode(node->left,x,w/2,y+56);
	}
	if (node->right) 
	{
		MoveToEx(hDC,x+w/2,y,&point);
		LineTo(hDC,x+w*3/4,y+56);
		DrawBTNode(node->right,x+w/2,w/2,y+56);
	}
	RECT r;
	char *t=Str(node->value);
	r.top=y-16;
	r.left=x+w/2-16;
	r.bottom=r.top+32;
	r.right=r.left+32;
	if (node->mark==0)
	{
		Ellipse(hDC,x+w/2-16,y-16,x+w/2+16,y+16);
		DrawText(hDC,t,lstrlen(t),&r,DT_CENTER|DT_VCENTER|DT_SINGLELINE);
	}
	else
	{
		HBRUSH hBrush=CreateSolidBrush(0xFFC0C0);
		HBRUSH hBrushOld=(HBRUSH)SelectObject(hDC,hBrush);
		COLORREF cOld=SetBkColor(hDC,0xFFC0C0);
		Ellipse(hDC,x+w/2-16,y-16,x+w/2+16,y+16);
		DrawText(hDC,t,lstrlen(t),&r,DT_CENTER|DT_VCENTER|DT_SINGLELINE);
		SelectObject(hDC,hBrushOld);
		DeleteObject(hBrush);
		SetBkColor(hDC,cOld);
	}
}
int COrder::Depth(void)
{
	return Depth(Root);
}
void COrder::TreeReset(BTNode * node)
{
	if (node->left)TreeReset(node->left);
	if (node->right)TreeReset(node->right);
	node->mark=0;
}
void COrder::AddFirst(void)
{
	if (Root) TreeReset(Root);
	else Root=new BTNode(ToFind);
	Parent=NULL;
	Cur=Root;
	TreeDraw();
}
int COrder::AddNext(void)
{
	if (Parent && Parent->value==ToFind) return State=State_Stop;
	if (Cur==0)
	{
		if (Parent)
		{
			if (ToFind>Parent->value)Cur=Parent->right=new BTNode(ToFind);
			else Cur=Parent->left=new BTNode(ToFind);
		}
	}
	else
	{
		Parent=Cur;
		Parent->mark=1;
		if (ToFind>Parent->value)Cur=Cur->right;
		else Cur=Cur->left;
	}
	TreeDraw();
	return 1;
}
void COrder::FindFirst(void)
{
	TreeReset(Root);
	Parent=NULL;
	Cur=Root;
	TreeDraw();
}
int COrder::FindNext(void)
{
	if ((Cur==0)||(Parent && Parent->value==ToFind))	return State=State_Stop;
	else
	{
		Parent=Cur;
		Parent->mark=1;
		if (ToFind>Parent->value)Cur=Cur->right;
		else Cur=Cur->left;
	}
	TreeDraw();
	return 1;
}