ds_btreedlg.cpp

数据结构中B-树经典算法的可视化执行程序

// DS_BTreeDlg.cpp : implementation file
//

#include "stdafx.h"
#include "DS_BTree.h"
#include "DS_BTreeDlg.h"
#include "BTree.h"

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

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CDS_BTreeDlg dialog

CDS_BTreeDlg::CDS_BTreeDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CDS_BTreeDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CDS_BTreeDlg)
	m_DeleteData = 0;
	m_InsertData = 0;
	m_RandCount = 0;
	m_NodeCount = 0;
	m_TreeKey = 0;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CDS_BTreeDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CDS_BTreeDlg)
	DDX_Control(pDX, ID_CreateRandNode, m_CreateRandNode);
	DDX_Control(pDX, IDC_RAND_SPIN, m_RandSpin);
	DDX_Text(pDX, IDC_DELETE_DATA, m_DeleteData);
	DDV_MinMaxInt(pDX, m_DeleteData, 0, 999);
	DDX_Text(pDX, IDC_INSERT_DATA, m_InsertData);
	DDV_MinMaxInt(pDX, m_InsertData, 0, 999);
	DDX_Text(pDX, IDC_RAND_COUNT, m_RandCount);
	DDV_MinMaxInt(pDX, m_RandCount, 0, 100);
	DDX_Text(pDX, IDC_NODE_COUNT, m_NodeCount);
	DDX_Text(pDX, IDC_TREE_KEY, m_TreeKey);
	DDV_MinMaxInt(pDX, m_TreeKey, 3, 20);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CDS_BTreeDlg, CDialog)
	//{{AFX_MSG_MAP(CDS_BTreeDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_SET_TREE_KEY, OnSetTreeKey)
	ON_BN_CLICKED(IDC_INSERT_NODE, OnInsertNode)
	ON_BN_CLICKED(IDC_DELETE_NODE, OnDeleteNode)
	ON_BN_CLICKED(ID_CreateRandNode, OnCreateRandNode)
	ON_BN_CLICKED(IDC_ERASEALL, OnEraseall)
	ON_WM_HSCROLL()
	ON_BN_CLICKED(IDC_About, OnAbout)
	ON_BN_CLICKED(IDC_help, Onhelp)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CDS_BTreeDlg message handlers

BOOL CDS_BTreeDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// 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
	
	// TODO: Add extra initialization here

	srand(time(0)); //用来设置随机时间的种子,使rand得到的随机数不一样
	pos_x=0;
	m_NodeCount=0;             //结点数
	m_InsertData=rand()%1000;  //随机插入的结点
	m_DeleteData=rand()%1000;  //随机删除的结点
	m_RandCount=10;            //随机插入的结点数初始设为10
	m_TreeKey=3;               //树的阶初始设为3
	m_BTree=NULL;
	NodeWidth=38;              //结点的宽
	NodeHeight=15;             //结点的高
	SetDC();
	m_RandSpin.SetRange(0,100);   //设置微调控件的范围
	hScroll=(CScrollBar *)GetDlgItem(IDC_H_SCROLL_BAR);//获得一个指向标识为IDC_H_SCROLL_BAR的控件(这里是一个ScrollBar)的指针. 然后你可以控制它的一些状态
	UpdateData(false);
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CDS_BTreeDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// 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 CDS_BTreeDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();

	//*****************Add extra code***********************************	
		if(m_BTree!=NULL)		
			DrawDetail();
						
		hScroll->SetScrollRange(0,MaxWidth);	
		hScroll->SetScrollPos(pos_x);
	}
		
}

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


void CDS_BTreeDlg::CreateBTree(int key) //创建B－树
{
	if(m_BTree!=NULL){
		if(m_BTree->GetKey()!=m_TreeKey){//若阶数改变，擦除原有B－树
			OnEraseall();
			delete m_BTree;
		}
		else  //若没有改变阶数，不做处理
			return;
	}
	m_BTree=new BTree(key);
	DeepHeight=m_BTree->GetRoot()->GetKEY()*16;  //设置树各层之间的距离
}


void CDS_BTreeDlg::OnSetTreeKey() //设置B－树的阶
{
	if(UpdateData()==FALSE)  return;
	CreateBTree(m_TreeKey);
	UpdateData(false);
}

void CDS_BTreeDlg::OnInsertNode() //插入指定结点
{

	if(UpdateData()==FALSE)  return;
	if(m_BTree==NULL)  
		CreateBTree(m_TreeKey);
	if(m_BTree->Search(m_InsertData)==true){ //插入的结点已存在
		MessageBox("该结点已经存在！"); 
		m_InsertData=rand()%1000;  //给m_InsertData赋值以1000以内的随机数
		UpdateData(false); //将m_InsertData的值反馈到Edit Box上
		return;
	}
	m_BTree->Insert(m_InsertData); //B－树插入关键字
	m_NodeCount++;  //结点总数加1
	InvalidateRect(&m_VisRect); //使矩形区域m_VisRect无效，系统发WM_PAINT消息重绘无效区域
	SetNodePos();  //设置B－树中各结点的位置