btreedemodlg.cpp

B-树演示程序(vc++)可执行程序.rar

// BTreeDemoDlg.cpp : implementation file
//

#include "stdafx.h"
#include "BTreeDemo.h"
#include "BTreeDemoDlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

BTree B_Tree;
int deep=2;
int p_y=1;
int B_M=3;
CEvent m_ev;
BOOL  b_run=FALSE;
BOOL  b_finish=TRUE;
//HANDLE m_handle;
CWnd* pwnd;

//m_ev.SetEvent();



/////////////////////////////////////////////////////////////////////////////
// CBTreeDemoDlg dialog

CBTreeDemoDlg::CBTreeDemoDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CBTreeDemoDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CBTreeDemoDlg)
	m_randnum = 0;
	m_BM = 0;
	m_insnum = 0;
	m_delnum = 0;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CBTreeDemoDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CBTreeDemoDlg)
	DDX_Control(pDX, IDC_SET_IT, m_setit);
	DDX_Control(pDX, IDC_TRAV_ORDER, m_travorder);
	DDX_Control(pDX, IDC_BDEMO, m_bdemo);
	DDX_Control(pDX, IDC_DEL_ALL, m_delball);
	DDX_Control(pDX, IDC_DELNUM, m_cdelnum);
	DDX_Control(pDX, IDC_INSNUM, m_cinsnum);
	DDX_Control(pDX, IDC_F_INSERT, m_f_insert);
	DDX_Control(pDX, IDC_F_DELETE, m_f_delete);
	DDX_Control(pDX, IDC_B_M, m_cBM);
	DDX_Control(pDX, IDC_RANDNUM, m_crandnum);
	DDX_Control(pDX, IDC_RANDTREE, m_randtree);
	DDX_Control(pDX, IDC_BIG, m_big);
	DDX_Control(pDX, IDC_SCR_SZ, m_scrsz);
	DDX_Control(pDX, IDC_SCR_SP, m_scrsp);
	DDX_Control(pDX, IDC_EXITME, m_exitme);
	DDX_Text(pDX, IDC_RANDNUM, m_randnum);
	DDX_Text(pDX, IDC_B_M, m_BM);
	DDX_Text(pDX, IDC_INSNUM, m_insnum);
	DDV_MinMaxInt(pDX, m_insnum, 1, 999);
	DDX_Text(pDX, IDC_DELNUM, m_delnum);
	DDV_MinMaxInt(pDX, m_delnum, 1, 999);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CBTreeDemoDlg, CDialog)
	//{{AFX_MSG_MAP(CBTreeDemoDlg)
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_WM_NCHITTEST ()
	ON_WM_ERASEBKGND()
	ON_BN_CLICKED(IDC_EXITME, OnExitme)
	ON_WM_HSCROLL()
	ON_WM_VSCROLL()
	ON_BN_CLICKED(IDC_BIG, OnBig)
    ON_WM_TIMER()
	ON_BN_CLICKED(IDC_RANDTREE, OnRandtree)
	ON_BN_CLICKED(IDC_F_INSERT, OnFInsert)
	ON_MESSAGE(WS_USER_REDRAW,OnThreadRedraw)
	ON_MESSAGE(WS_USER_FINISH,OnThreadFinish)
	ON_BN_CLICKED(IDC_F_DELETE, OnFDelete)
	ON_BN_CLICKED(IDC_DEL_ALL, OnDelAll)
	ON_BN_CLICKED(IDC_TRAV_ORDER, OnTravOrder)
	ON_BN_CLICKED(IDC_SET_IT, OnSetIt)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CBTreeDemoDlg message handlers

BOOL CBTreeDemoDlg::OnInitDialog()
{
	CDialog::OnInitDialog();
 
	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	srand( (unsigned)time( NULL ) );
	// TODO: Add extra initialization here
	m_exitme.SetIcon(IDI_CANCEL);
    m_exitme.DrawTransparent(TRUE);
	m_big.SetIcon(IDI_BIG);
	m_big.DrawTransparent(TRUE);
	m_randtree.SetShade(CShadeButtonST::SHS_METAL);
    m_f_delete.SetShade(CShadeButtonST::SHS_METAL);
	m_f_insert.SetShade(CShadeButtonST::SHS_METAL);
	m_delball.SetShade(CShadeButtonST::SHS_METAL);
    m_travorder.SetShade(CShadeButtonST::SHS_METAL);
	m_setit.SetShade(CShadeButtonST::SHS_HARDBUMP);
    

	//::SetBkColor(m_s_maxnum.setb,RGB(0,0,123));
	
    pwnd=AfxGetMainWnd();

	CFont font;
	font.CreatePointFont(140,"Times New Roman");
	m_crandnum.SetFont(&font);
	m_cBM.SetFont(&font);
	m_cdelnum.SetFont(&font);
	m_cinsnum.SetFont(&font);
	m_bdemo.SetFont(&font);
	m_randnum=13;
	m_insnum=rand()%300+2;
	m_delnum=rand()%400+3;
	m_BM=B_M;

	pos_x=0;
	pos_y=0;
	d_strech=1;
    Dsp_dc=GetDC();

    SCROLLINFO si;
	si.fMask=SIF_ALL;
	si.nMin=0;
	si.nMax=MDCLE-1;
	si.nPage=630;
	si.nPos=pos_y;
	m_scrsz.SetScrollInfo(&si,TRUE);

	si.fMask=SIF_ALL;
	si.nMin=0;
	si.nMax=MDCWD-1;
	si.nPage=540;
	si.nPos=pos_x;
	m_scrsp.SetScrollInfo(&si,TRUE);
	UpdateData(FALSE);

    
	Dsp_pen.CreatePen(PS_SOLID,2,RGB(40,40,190));
	Dsp_Font.CreatePointFont(150,"Times New Roman");
	InitMdc();
	MdcDsp();
/*
	NewNode(&B_Tree);
	Sch_InsBTree(&B_Tree,32);
	Sch_InsBTree(&B_Tree,114);
	Sch_InsBTree(&B_Tree,285);
	Sch_InsBTree(&B_Tree,551);
	Sch_InsBTree(&B_Tree,634);
	Sch_InsBTree(&B_Tree,797);
	Sch_InsBTree(&B_Tree,802);
	Sch_InsBTree(&B_Tree,807);
	Sch_InsBTree(&B_Tree,815);
     DeleteBTree(&B_Tree,634);*/



	return TRUE;  // return TRUE  unless you set the focus to a control
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CBTreeDemoDlg::OnPaint() 
{	

     
     MdcDsp();
	 CDialog::OnPaint();
}

void CBTreeDemoDlg::MdcDsp()  { 
	Dsp_dc->StretchBlt(12,12,540,630,&mdc,pos_x*d_strech,pos_y*d_strech,
		540/d_strech,630/d_strech,SRCCOPY);

}


// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CBTreeDemoDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

UINT CBTreeDemoDlg::OnNcHitTest (CPoint point)
{
    UINT nHitTest =CDialog::OnNcHitTest (point);
    if ((nHitTest == HTCLIENT) && (::GetAsyncKeyState (MK_LBUTTON) < 0))
        nHitTest = HTCAPTION;
    return nHitTest;
}

BOOL CBTreeDemoDlg::OnEraseBkgnd(CDC* pDC)  {
    CDialog :: OnEraseBkgnd (pDC);
//	CBrush brush;
//	CRect rc;
//	GetClientRect (rc);
//	brush.CreateSolidBrush(RGB(130,130,189));
//	pDC->FillRect(rc,&brush);
    return TRUE;
}

void CBTreeDemoDlg::OnExitme() 
{
	//OnOK();
	exit(0);
	// TODO: Add your control notification handler code here
	
}

void CBTreeDemoDlg::InitMdc()   {

	bmap.CreateCompatibleBitmap(GetDC(),MDCWD,MDCLE);
	mdc.CreateCompatibleDC(GetDC());
    mdc.SelectObject(&bmap);
	CBrush brush(RGB(230,230,250));
	mdc.FillRect(CRect(0,0,MDCWD,MDCLE),&brush);
	mdc.SetBkMode(TRANSPARENT);
	mdc.SelectObject(&Dsp_Font);	
    mdc.SetTextColor(RGB(130,10,10));
	mdc.SelectObject(&Dsp_pen);

}

void CBTreeDemoDlg::EreaseMdc()  {   
	CBrush brush(RGB(230,230,250));
	mdc.FillRect(CRect(0,0,MDCWD,MDCLE),&brush);
}



void  CBTreeDemoDlg::OnVScroll(UINT nCode,UINT nPos,CScrollBar* pScrollBar)  {
    CDialog::OnVScroll(nCode,nPos,pScrollBar);
	switch(nCode)  {
	case SB_LINEUP:
	case SB_PAGEUP:
		pos_y-=6; 		
		break;
	case SB_LINEDOWN:
	case SB_PAGEDOWN:
        pos_y+=6;
		break;
	case SB_THUMBTRACK:
		pos_y=nPos;
		break;
	default:
		return;
	}

	if(pos_y<0)  pos_y=0;  
	else if(pos_y>1370)  pos_y=1370;
    MdcDsp();
	pScrollBar->SetScrollPos(pos_y,TRUE);
}

void  CBTreeDemoDlg::OnHScroll(UINT nCode,UINT nPos,CScrollBar* pScrollBar)  {
    CDialog::OnHScroll(nCode,nPos,pScrollBar);
	switch(nCode)  {
	case SB_LINELEFT:
	case SB_PAGELEFT:
		pos_x-=6; 		
		break;
	case SB_LINERIGHT:
	case SB_PAGERIGHT:
        pos_x+=6;
		break;
	case SB_THUMBTRACK:
		pos_x=nPos;
		break;
	default:
		return;
	}

	if(pos_x<0)  pos_x=0;  
	else if(pos_x>1460)  pos_x=1460;
    MdcDsp();
	pScrollBar->SetScrollPos(pos_x,TRUE);
}

void  CBTreeDemoDlg::DrawNode_To_Mdc(BTree p)  {  
	int y=20*p->x , x=30*p->y;
	int i;
	CString cs;
	for(i=1;i<=p->keynum;i++)  {
        cs.Format("%d",p->key[i]);
		mdc.TextOut(x,y,cs);
		mdc.MoveTo(x,y);
		mdc.LineTo(x+30,y);
		mdc.MoveTo(x+30,y);
		mdc.LineTo(x+30,y+20);
		mdc.MoveTo(x+30,y+20);
		mdc.LineTo(x,y+20);
		mdc.MoveTo(x,y+20);
		mdc.LineTo(x,y);
		x+=30;  

	}    
}

void CBTreeDemoDlg::DrawLine_To_Mdc(BTree p)  {
	BTree q=p->parent;
	int x,y,num;
	if(q)  {
		num=Comp_child(p);
	    x=30*q->y+30*num;	y=20*q->x+20;
		mdc.MoveTo(x,y);
        x=30*p->y+15;  y=20*p->x; 
		mdc.LineTo(x,y);
	}
}

void CBTreeDemoDlg::Draw_To_Mdc(BTree t)  {
	int i;
	if(t)  {
		DrawNode_To_Mdc(t);
		DrawLine_To_Mdc(t);
		for(i=0;i<=t->keynum;i++)  {
			Draw_To_Mdc(t->ptr[i]);
		}
	}
}

void CBTreeDemoDlg::OnBig() 
{
	if(d_strech==1)  {
		d_strech=2;
	}
	else  {
		d_strech=1;
	}
	MdcDsp();
	
}

void CBTreeDemoDlg::OnTimer(UINT nID)  {
	if(UpdateData()==FALSE)  return;
	if(rand_ip<=m_randnum)  {
		++rand_ip;
		deep=2;
        p_y=1;
		Sch_InsBTree(&B_Tree,rand()%998+1);
		Set_xy_Zero(B_Tree);
		Compute_xy(B_Tree);
		EreaseMdc();
        Draw_To_Mdc(B_Tree);
		MdcDsp();
		
	}
	else  {
		m_randtree.EnableWindow(TRUE);
	    m_crandnum.EnableWindow(TRUE);
		m_cBM.EnableWindow(TRUE);
		m_f_delete.EnableWindow(TRUE);
		m_f_insert.EnableWindow(TRUE);
		m_cdelnum.EnableWindow(TRUE);
		m_cinsnum.EnableWindow(TRUE);
		m_delball.EnableWindow(TRUE);
		m_setit.EnableWindow(TRUE);
		m_travorder.EnableWindow(TRUE);
		KillTimer(1);
	}

}
//////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////

void NewNode(BTree* p)  {
	int i;
    *p=(BTree)malloc(sizeof(BTNode));
	(*p)->keynum=0;
	(*p)->parent=NULL;
	(*p)->x=(*p)->y=0;
	for(i=0;i<=B_M;i++)  {
		(*p)->ptr[i]=NULL;
		(*p)->key[i]=0;
	}	
}


int Search(BTree p,int k)  {
	int i,pos,found=0;

	for(i=1;i<=p->keynum&&!found;i++)  {
		if(k==p->key[i])  found=1;
	}
	if(found) return i==1?i:i-1;
	pos=0;
	found = 0;
	for(i=1;i<=p->keynum&&!found;i++)  {
		if(k>=p->key[i])  {
			if(i+1<=p->keynum)  {
				if(k<p->key[i+1])  {
					pos=i;  found=1;
				}
			}
			else  pos=i, found=1;
		}
	}

	return pos;
}

Result SearchBTree(BTree T,int k)  {
	BTree p=T,q=NULL;
	int found=0,i=0;
    Result res;
	while(p&&!found)  {
		i=Search(p,k);
		if(i>0&&p->key[i]==k)  found=1;
		else  {q=p;  p=p->ptr[i];  }
	}
	if(found)  {
		res.pt=p;  res.i=i;  res.tag=1;
	}
	else  {
		res.pt=q;  res.i=i;  res.tag=0;
	}

	return res;
}

int Sch_InsBTree(BTree* p,int key)  {
    int x,i,s,finish=0;
	BTree ap=NULL,q;
    Result res;
    res=SearchBTree(*p,key);
    if(res.tag)  return 1;
	q=res.pt;  i=res.i;  x=key;

	while(q&&!finish)  {
		Insert(q,i,x,ap);
		//begin
		if(b_run)  {
			pwnd->SendMessage(WS_USER_REDRAW);
			m_ev.Lock();
            //add!!!
		}
		//end
		if(q->keynum<B_M)  finish=1;
		else  {
			s=B_M%2?B_M/2+1:B_M/2;  
			split(q,s,&ap);
			x=q->key[s];
			q=q->parent;
			if(q)  i=Search(q,x);
			
		}
	}
	if(!finish)  {
		NewRoot(p,q,x,ap);
		if(b_run)  {
			pwnd->SendMessage(WS_USER_REDRAW);
			m_ev.Lock();
				//add!!!
		}
	}
	return 1;
}

void   NewRoot(BTree* T,BTree q,int x, BTree ap)  {
	BTree tmp;
	NewNode(&tmp);

	tmp->keynum=1;
	tmp->key[1]=x;
	tmp->ptr[0]=*T;
	tmp->ptr[1]=ap;
	(*T)->parent=tmp;
	ap->parent=tmp;
	*T=tmp;


}

void   Insert(BTree q,int i,int x,BTree ap)  {
	int j=i+1;  
    ++q->keynum;
	for(j=B_M-1;j>=i+1;j--)  {
		q->key[j+1]=q->key[j];
		q->ptr[j+1]=q->ptr[j];
	}
	q->key[i+1]=x;
	q->ptr[i+1]=ap;

}

void  split(BTree q,int s,BTree* ap)  {
	int i,j=1,k=0;