main.cpp

图形演示数据结构的树与图遍历算法,vc环境下的windows编程

# include "windows.h"
# include "winuser.h"
# include "resource.h"
# include "main.h"
# include "tchar.h"
# include "stdlib.h"
# include "string.h"
# include "stdio.h"
# include "iostream.h" 

long WINAPI WndProc(HWND hWnd,UINT iMessage,UINT wParam,LONG lParam);
BOOL InitWindowsClass(HINSTANCE hInstance);
BOOL InitWindows(HINSTANCE hInstance,int nCmdShow);
BOOL CALLBACK DlgProc(HWND hdlg,UINT message,WPARAM wParam,LPARAM lParam);
BOOL CALLBACK GDlgProc(HWND hdlg,UINT message,WPARAM wParam,LPARAM lParam);
BOOL CALLBACK NGDlgProc(HWND hdlg,UINT message,WPARAM wParam,LPARAM lParam);
BOOL CALLBACK HELPProc(HWND hdlg,UINT message,WPARAM wParam,LPARAM lParam);
BOOL CALLBACK WARN(HWND hdlg,UINT message,WPARAM wParam,LPARAM lParam);
BOOL CALLBACK CREATEGRAPH(HWND hdlg,UINT message,WPARAM wParam,LPARAM lParam);

void preordertraverse(BTree *);
void inordertraverse(BTree *);
void postordertraverse(BTree *);
void bfs(adjlist);
void dfs(adjlist);

HWND hWnd;
HFONT hF;
HMENU hmenu,Hmenu,hMenu,hSubMenu;
RECT lpRect,windowrect;
HDC hdc;
HFONT hfont;
HINSTANCE hInst;
HPEN hpen;
HBRUSH hbrush;
int cxscreen,cyscreen;



//树变量
char lpString[2];
struct nd nf[9];
BTree *tree;
BTree *bt[9];
int x,y,i,j=0,nx=0,ny=0;
int root=1,node=0;
int ix,iy;
int createflag=0;
char p[]={'a','b','c','d','e','f','g','h','i'};
//图变量
adjlist graph;
struct edgenode *w,*q;
int gnode=0;
struct gnd  ginfo[9];
char gp[]={'a','b','c','d','e','f','g','h','i'};
char glpstring[2];
int visited[9];
int graphtype=IDC_WSGRAPH;

int WINAPI WinMain(HINSTANCE hInstance,HINSTANCE ,LPSTR lpCmdLine,int nCmdShow)
{   
	char lpszClassName[]="window";
	MSG Message;
	WNDCLASS WndClass;
    WndClass.cbClsExtra=0;
	WndClass.cbWndExtra=0;
	WndClass.hbrBackground=(HBRUSH)(GetStockObject(WHITE_BRUSH));
	WndClass.hCursor=LoadCursor(NULL,IDC_ARROW);
	WndClass.hIcon=LoadIcon(NULL,IDI_APPLICATION);
	WndClass.hInstance=hInstance;
	WndClass.lpfnWndProc=WndProc;
	WndClass.lpszClassName=lpszClassName;
	WndClass.lpszMenuName=MAKEINTRESOURCE(IDM_MENU);
	WndClass.style=0;
	if(!RegisterClass(&WndClass))
		return FALSE;
    cxscreen=GetSystemMetrics(SM_CXFULLSCREEN);
	cyscreen=GetSystemMetrics(SM_CYFULLSCREEN);
	
	if(cxscreen==1024)
		hWnd=CreateWindow(lpszClassName,
		              "数据结构课程设计",
			          WS_SYSMENU|
					  WS_MINIMIZEBOX|
					  WS_CAPTION,
					  150,80,750,600,
					  NULL,
					  NULL,
					  hInstance,
					  NULL);
    else if(cxscreen==800)
         hWnd=CreateWindow(lpszClassName,
		              "数据结构课程设计",
			          WS_SYSMENU|
					  WS_CAPTION,
					  80,30,650,500,
					  NULL,
					  NULL,
					  hInstance,
					  NULL);
    else
		return 1;
	
	if(!hWnd)
		return FALSE;
	
	
	ShowWindow(hWnd,nCmdShow);
	UpdateWindow(hWnd);
    while(GetMessage(&Message,0,0,0))
	{
		TranslateMessage(&Message);
		DispatchMessage(&Message);
	}
	return Message.wParam;
}


LRESULT CALLBACK WndProc(HWND hWnd,UINT iMessage,UINT wParam,LONG lParam)//消息处理函数
{   PAINTSTRUCT ps;
	switch(iMessage)
	{
	    case WM_PAINT:
	  	     int m,n;
			 hdc=BeginPaint(hWnd,&ps);
			 UpdateWindow(hWnd);
			 hpen=CreatePen(PS_SOLID,2,RGB(0,0,255));
		     SelectObject(hdc,hpen);
             hbrush=CreateSolidBrush(RGB(0,0,255));
		     SelectObject(hdc,hbrush);
			 SetBkColor(hdc,RGB(0,0,255));
		     SetTextColor(hdc,RGB(255,0,0));
			 hfont=CreateFont(15,15,0,0,400,0,0,0,
			            ANSI_CHARSET,OUT_DEFAULT_PRECIS,
			            CLIP_DEFAULT_PRECIS,DEFAULT_QUALITY,
			            DEFAULT_PITCH|FF_DONTCARE,
				        "黑体");
			 SelectObject(hdc,hfont);
			 switch(createflag)
			 {
			 case 1:
			   for(n=0;n<node&&root==0;n++)
			   {
				   if(n==0)
				   {
					 
		             Pie(hdc,nf[0].nx,nf[0].ny,nf[0].nx+40,nf[0].ny+40,0,0,0,0);
				     TextOut(hdc,nf[0].nx+8,nf[0].ny+12,&bt[0]->data,1);
				   }
				 else
				 {
					 for(m=0;m<n;m++)
					 {
						 if(nf[n].nx==nf[m].nx-70&&nf[n].ny==nf[m].ny+70)
						 {
							 
		                     Pie(hdc,nf[n].nx,nf[n].ny,nf[n].nx+40,nf[n].ny+40,0,0,0,0);
                             MoveToEx(hdc,nf[n].nx+40,nf[n].ny,NULL);	
			                 LineTo(hdc,nf[m].nx,nf[m].ny+40);
				             TextOut(hdc,nf[n].nx+8,nf[n].ny+12,&bt[n]->data,1);
							 break;
						 }
						 else if(nf[n].nx==nf[m].nx+70&&nf[n].ny==nf[m].ny+70)
						 {
							
		                     Pie(hdc,nf[n].nx,nf[n].ny,nf[n].nx+40,nf[n].ny+40,0,0,0,0);
                             MoveToEx(hdc,nf[m].nx+40,nf[m].ny+40,NULL);
				             LineTo(hdc,nf[n].nx,nf[n].ny);
				             TextOut(hdc,nf[n].nx+8,nf[n].ny+12,&bt[n]->data,1);
							 break;
						 }
						 else
							 ;
					 }
				 }
			 }
			 break;
			 case 2:
				 int q;
				 struct edgenode *p;
				 for(q=0;q<gnode;q++)
				 {
					 Pie(hdc,ginfo[q].gx,ginfo[q].gy,ginfo[q].gx+40,ginfo[q].gy+40,0,0,0,0);
			         TextOut(hdc,ginfo[q].gx+10,ginfo[q].gy+10,&graph[q].data,1); 
				 }
				 for(q=0;q<gnode;q++)
				 {
					 p=graph[q].link;
					 while(p)
					 {
						  MoveToEx(hdc,ginfo[q].gx+10,ginfo[q].gy+10,NULL);	
     					  LineTo(hdc,ginfo[p->adjvex].gx+10,ginfo[p->adjvex].gy+10);
						  TextOut(hdc,ginfo[q].gx+10,ginfo[q].gy+10,&graph[q].data,1);
			              TextOut(hdc,ginfo[p->adjvex].gx+10,ginfo[p->adjvex].gy+10,&graph[p->adjvex].data,1);
     					  p=p->next;
					 }
				 }

				 break;
			 default:
				 break;
			 }

			 EndPaint(hWnd,&ps);
			 break;
	    case WM_CREATE:
		     hMenu=GetMenu(hWnd);
             hSubMenu=GetSubMenu(hMenu,0);
             EnableMenuItem(hSubMenu,2,MF_BYPOSITION|MF_DISABLED|MF_GRAYED);
             EnableMenuItem(hSubMenu,3,MF_BYPOSITION|MF_DISABLED|MF_GRAYED);
             EnableMenuItem(hSubMenu,4,MF_BYPOSITION|MF_DISABLED|MF_GRAYED);
             hSubMenu=GetSubMenu(hMenu,1);
			 EnableMenuItem(hSubMenu,2,MF_BYPOSITION|MF_DISABLED|MF_GRAYED);
             EnableMenuItem(hSubMenu,3,MF_BYPOSITION|MF_DISABLED|MF_GRAYED);
             
		 	 break;
       	case WM_COMMAND:
			 hdc=GetDC(hWnd);
		     switch(LOWORD(wParam))
			 {    
		     case IDM_ABOUT://显示帮助对话框
			      if(DialogBox(hInst,LPSTR(IDD_ABOUT),hWnd,(DLGPROC)HELPProc)==0)
				  return 0;
			      break;
		     case IDM_QUIT://关闭窗口
                  PostQuitMessage(0);
			      return 0;
			 case IDM_CREATETREE://创建树
				  createflag=1;
				  root=1;
				  node=0;
				  tree=NULL;
				  graph[0].link=NULL;
				  hpen=CreatePen(PS_NULL,2,RGB(0,0,255));
		          SelectObject(hdc,hpen);
                  hbrush=CreateSolidBrush(RGB(255,255,255));
		          SelectObject(hdc,hbrush);
		          Rectangle(hdc,0,0,750,600);
				  hMenu=GetMenu(hWnd);
                  hSubMenu=GetSubMenu(hMenu,0);
                  EnableMenuItem(hSubMenu,2,MF_BYPOSITION|MF_ENABLED);
                  EnableMenuItem(hSubMenu,3,MF_BYPOSITION|MF_ENABLED);
				  EnableMenuItem(hSubMenu,4,MF_BYPOSITION|MF_ENABLED);
				  hSubMenu=GetSubMenu(hMenu,1);
			      EnableMenuItem(hSubMenu,2,MF_BYPOSITION|MF_DISABLED|MF_GRAYED);
                  EnableMenuItem(hSubMenu,3,MF_BYPOSITION|MF_DISABLED|MF_GRAYED);
			      break;
			 case IDM_PRE://先序遍历
				  preordertraverse(tree);   
			      break;
			 case IDM_IN://中序遍历
				  inordertraverse(tree);
			      break;
			 case IDM_POST://后序遍历
				  postordertraverse(tree);
			      break;
			case IDM_INPUT://输入树结点值
	              DialogBox(hInst,LPSTR(IDD_INPUT),hWnd,(DLGPROC)DlgProc);
			      break;
			 case IDM_CREATEGRAPH://创建图
				  createflag=2;
				  gnode=0;
				  tree=NULL;
                  graph[0].data=NULL;
				  graph[0].link=NULL;
				  hpen=CreatePen(PS_NULL,2,RGB(0,0,255));
		          SelectObject(hdc,hpen);
                  hbrush=CreateSolidBrush(RGB(255,255,255));
		          SelectObject(hdc,hbrush);
		          Rectangle(hdc,0,0,750,600);
				  hMenu=GetMenu(hWnd);
                  hSubMenu=GetSubMenu(hMenu,1);
                  EnableMenuItem(hSubMenu,2,MF_BYPOSITION|MF_ENABLED);
                  EnableMenuItem(hSubMenu,3,MF_BYPOSITION|MF_ENABLED);
				  hSubMenu=GetSubMenu(hMenu,0);
                  EnableMenuItem(hSubMenu,2,MF_BYPOSITION|MF_DISABLED|MF_GRAYED);
                  EnableMenuItem(hSubMenu,3,MF_BYPOSITION|MF_DISABLED|MF_GRAYED);
                  EnableMenuItem(hSubMenu,4,MF_BYPOSITION|MF_DISABLED|MF_GRAYED);
				  DialogBox(hInst,LPSTR(IDD_GRAPHTYPE),hWnd,(DLGPROC)CREATEGRAPH);
				  break;
			 case IDM_BFS://广度优先搜索
                  bfs(graph);
				  break;
			 case IDM_DFS://深度优先搜索
				  int i;
                  for (i=0;i<9;i++)
	        	  visited[i]=0;
             	  dfs(graph);
				  break;
			 case IDM_INPUTG://输入图结点值
				  DialogBox(hInst,LPSTR(IDD_NGINPUT),hWnd,(DLGPROC)NGDlgProc);
                  break;
		     case IDM_LINKG://创建邻接点
                  DialogBox(hInst,LPSTR(IDD_GINPUT),hWnd,(DLGPROC)GDlgProc);
                  break;
			 case IDM_CREATEG://创建图结点
				 if(gnode>8)
				  {
					  MessageBox(hWnd,_T("创建的结点数不能太多! "),_T("警告"),MB_ICONEXCLAMATION|MB_OK);
                      break;
				  }
                  graph[gnode].data=gp[gnode];
				  graph[gnode].link=NULL;
               	  ginfo[gnode].gx=ix;
			      ginfo[gnode].gy=iy;
				  ginfo[gnode].gorder=gnode;
				  hpen=CreatePen(PS_SOLID,2,RGB(0,0,255));
		          SelectObject(hdc,hpen);
                  hbrush=CreateSolidBrush(RGB(0,0,255));
		          SelectObject(hdc,hbrush);
		          Pie(hdc,ix,iy,ix+40,iy+40,0,0,0,0);
				  SetBkColor(hdc,RGB(0,0,255));
		    	  SetTextColor(hdc,RGB(255,0,0));
			      hfont=CreateFont(15,15,0,0,400,0,0,0,
							 ANSI_CHARSET,OUT_DEFAULT_PRECIS,
							 CLIP_DEFAULT_PRECIS,DEFAULT_QUALITY,
							 DEFAULT_PITCH|FF_DONTCARE,
							 "黑体");
			      SelectObject(hdc,hfont);
			      TextOut(hdc,ginfo[gnode].gx+10,ginfo[gnode].gy+10,&gp[gnode],1);
			      gnode++;
	              break;
			
			 case IDM_ROOT://创建根结点
                  root=0;  
			      if(cxscreen==1024)
					  nf[0].nx=350;
				  else
					  nf[0].nx=280;
				  nf[0].ny=0;
		          nf[0].lc=1;
				  nf[0].rc=1;
                  nf[0].order=node;
			      tree=new BTree;             
				  tree->rchild=NULL;
				  tree->lchild=NULL;
				  tree->data=p[0];
				  bt[0]=tree;
				  hpen=CreatePen(PS_SOLID,2,RGB(0,0,255));
		          SelectObject(hdc,hpen);
                  hbrush=CreateSolidBrush(RGB(0,0,255));
		          SelectObject(hdc,hbrush);
		          Pie(hdc,nf[0].nx,nf[0].ny,nf[0].nx+40,nf[0].ny+40,0,0,0,0);
				  SetBkColor(hdc,RGB(0,0,255));
		    	  SetTextColor(hdc,RGB(255,0,0));
			      hfont=CreateFont(15,15,0,0,400,0,0,0,
							 ANSI_CHARSET,OUT_DEFAULT_PRECIS,
							 CLIP_DEFAULT_PRECIS,DEFAULT_QUALITY,
							 DEFAULT_PITCH|FF_DONTCARE,
							 "黑体");
			      SelectObject(hdc,hfont);
			      TextOut(hdc,nf[0].nx+8,nf[0].ny+12,&p[0],1);
	              break;
		     case IDM_LCHILD://创建左孩子
                  if(node>=8)
				  {
					  MessageBox(hWnd,_T("创建的结点数不能太多! "),_T("警告"),MB_ICONEXCLAMATION|MB_OK);
                      break;
				  }
	              node++;
			      nx=(int)(ix/70)*70;			 
			      ny=(int)(iy/70)*70;
			      for ( i=0;i<=node;i++)
				  {
				      if(nx==nf[i].nx&&ny==nf[i].ny)	
					  break;
				  }
			    			 
			      nf[i].lc=0;
				  nf[node].nx=nf[i].nx-70;
				  nf[node].ny=nf[i].ny+70;
				  nf[node].lc=1;
			      nf[node].rc=1;
				  nf[node].order=node;
				  bt[node]=new BTree;
				  bt[node]->data=p[node];
                  bt[node]->lchild=NULL; 
				  bt[node]->rchild=NULL;
                  bt[i]->lchild=bt[node];
				  hpen=CreatePen(PS_SOLID,2,RGB(0,0,255));
		          SelectObject(hdc,hpen);
                  hbrush=CreateSolidBrush(RGB(0,0,255));
		          SelectObject(hdc,hbrush);
		          Pie(hdc,nf[node].nx,nf[node].ny,nf[node].nx+40,nf[node].ny+40,0,0,0,0);
                  MoveToEx(hdc,nf[node].nx+40,nf[node].ny,NULL);	
			      LineTo(hdc,nf[i].nx,nf[i].ny+40);
				  SetBkColor(hdc,RGB(0,0,255));
		    	  SetTextColor(hdc,RGB(255,0,0));
			      hfont=CreateFont(15,15,0,0,400,0,0,0,
							 ANSI_CHARSET,OUT_DEFAULT_PRECIS,
							 CLIP_DEFAULT_PRECIS,DEFAULT_QUALITY,
							 DEFAULT_PITCH|FF_DONTCARE,
							 "黑体");
			      SelectObject(hdc,hfont);
			      TextOut(hdc,nf[node].nx+8,nf[node].ny+12,&p[node],1);
		   	      break;
         
		     case IDM_RCHILD://创建右孩子   
			      
				  if(node>=8)
				  {
					  MessageBox(hWnd,_T("创建的结点数不能太多! "),_T("警告"),MB_ICONEXCLAMATION|MB_OK);
                      break;
				  }node++;
			      nx=(int)(ix/70)*70;
				  ny=(int)(iy/70)*70;
			      for (i=0;i<=node;i++)
				  {
				      if(nx==nf[i].nx&&ny==nf[i].ny)
					  break;
				  }
				  nf[i].rc=0;
			      nf[node].nx=nf[i].nx+70;
				  nf[node].ny=nf[i].ny+70;
				  nf[node].rc=1;
				  nf[node].lc=1;
			      nf[node].order=node;
				  bt[node]=new BTree;
				  bt[node]->data=p[node];
		          bt[node]->lchild=NULL;
                  bt[node]->rchild=NULL;
                  bt[i]->rchild=bt[node];
                  hpen=CreatePen(PS_SOLID,2,RGB(0,0,255));
		          SelectObject(hdc,hpen);
                  hbrush=CreateSolidBrush(RGB(0,0,255));
		          SelectObject(hdc,hbrush);
		          Pie(hdc,nf[node].nx,nf[node].ny,nf[node].nx+40,nf[node].ny+40,0,0,0,0);
                  MoveToEx(hdc,nf[i].nx+40,nf[i].ny+40,NULL);
				  LineTo(hdc,nf[node].nx,nf[node].ny);
				  SetBkColor(hdc,RGB(0,0,255));
		    	  SetTextColor(hdc,RGB(255,0,0));
			      hfont=CreateFont(15,15,0,0,400,0,0,0,
							 ANSI_CHARSET,OUT_DEFAULT_PRECIS,
							 CLIP_DEFAULT_PRECIS,DEFAULT_QUALITY,
							 DEFAULT_PITCH|FF_DONTCARE,
							 "黑体");
			      SelectObject(hdc,hfont);
			      TextOut(hdc,nf[node].nx+8,nf[node].ny+12,&p[node],1);
			      break;
				  }
			
			
    case WM_MOUSEMOVE:
         GetClientRect(hWnd,&lpRect);
		 ix=LOWORD(lParam);
		 iy=HIWORD(lParam);
	     x=LOWORD(lParam)+lpRect.left; 
		 y=HIWORD(lParam)+lpRect.top+50;
		 break;

    case WM_RBUTTONDOWN://单击右键	 
         if(createflag==0)
			 break;
		 else if(createflag==1)
		 {
			nx=(int)(ix/70)*70;
			ny=(int)(iy/70)*70;
			for ( i=0;i<=node;i++)
				 {
					 if(nx==nf[i].nx&&ny==nf[i].ny)
						 break;
				}
			hmenu=CreatePopupMenu();
			if(root)
			{   AppendMenu(hmenu,MF_ENABLED,IDM_ROOT,"创建根结点(&C)");
				AppendMenu(hmenu,MF_GRAYED,IDM_LCHILD,"创建左子树(&L)");
				AppendMenu(hmenu,MF_GRAYED,IDM_RCHILD,"创建右子树(&R)");
        		AppendMenu(hmenu,MF_GRAYED,IDM_INPUT,"输入结点值(&C)");
			
			}	
			else if(i<=node)
			{
				if(root)
					AppendMenu(hmenu,MF_ENABLED,IDM_ROOT,"创建根结点(&C)");
				else
					AppendMenu(hmenu,MF_GRAYED,IDM_ROOT,"创建根结点(&C)");
				if(nf[i].lc)
					AppendMenu(hmenu,MF_ENABLED,IDM_LCHILD,"创建左子树(&L)");
				else
					AppendMenu(hmenu,MF_GRAYED,IDM_LCHILD,"创建左子树(&L)");
				if(nf[i].rc)
					AppendMenu(hmenu,MF_ENABLED,IDM_RCHILD,"创建右子树(&R)");
				else
					AppendMenu(hmenu,MF_GRAYED,IDM_RCHILD,"创建右子树(&R)");
        
				AppendMenu(hmenu,MF_ENABLED,IDM_INPUT,"输入结点值(&C)");
			    //AppendMenu(hmenu,MF_GRAYED,IDM_INPUT,"输入结点值(&C)");
		
				}
		
		    else
			{
				AppendMenu(hmenu,MF_GRAYED,IDM_ROOT,"创建根结点(&C)");
				AppendMenu(hmenu,MF_GRAYED,IDM_LCHILD,"创建左子树(&L)");
				AppendMenu(hmenu,MF_GRAYED,IDM_RCHILD,"创建右子树(&R)");
        		AppendMenu(hmenu,MF_GRAYED,IDM_INPUT,"输入结点值(&C)");
				}
			GetWindowRect(hWnd,&windowrect);	
			TrackPopupMenu(hmenu,TPM_NONOTIFY ,windowrect.left+x,windowrect.top+y,0,hWnd,NULL);
				break;
		 }
		 else if(createflag==2)
		 {   
             
			 Hmenu=CreatePopupMenu();
             AppendMenu(Hmenu,MF_ENABLED,IDM_CREATEG,"创建结点(&G)");
             for ( i=0;i<gnode;i++)
			 {