main.cpp

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

				 if(ix<=ginfo[i].gx+40&&iy<=ginfo[i].gy+40&&ix>=ginfo[i].gx&&iy>=ginfo[i].gy)
					 break;
			 }
			 if(i>=gnode)
		         AppendMenu(Hmenu,MF_GRAYED,IDM_INPUTG,"输入结点值(&I)");
			 else
				 AppendMenu(Hmenu,MF_ENABLED,IDM_INPUTG,"输入结点值(&I)");
			 for ( i=0;i<gnode;i++)
			 {
				 if(ix<=ginfo[i].gx+40&&iy<=ginfo[i].gy+40&&ix>=ginfo[i].gx&&iy>=ginfo[i].gy)
					 break;
			 }
			 if(i>=gnode)
			     AppendMenu(Hmenu,MF_GRAYED,IDM_LINKG,"创建邻接点(&L)");
             else
			     AppendMenu(Hmenu,MF_ENABLED,IDM_LINKG,"创建邻接点(&L)");
			 GetWindowRect(hWnd,&windowrect);
             TrackPopupMenu(Hmenu,TPM_NONOTIFY ,windowrect.left+x,windowrect.top+y,0,hWnd,NULL);
		     break;
		 }
	     else 
			 break;
		
		 case WM_DESTROY:
             PostQuitMessage(0);
			 return 0;
	default:
			return (DefWindowProc(hWnd,iMessage,wParam,lParam));
	}
	return 0;
}

//帮助对话框处理函数
BOOL CALLBACK HELPProc(HWND hdlg,UINT message,WPARAM wParam,LPARAM lParam)
{
	switch(message)
	{
	case WM_INITDIALOG:
		 break;
	case WM_COMMAND:
		switch(LOWORD(wParam))
		{
		case IDOK:
           EndDialog(hdlg,0);
           break;
		}
	case WM_CLOSE:
       EndDialog(hdlg,0);
    	break;
	}
return 0;
}  

void preordertraverse(BTree *btree)          //先序遍历
{   char pchar[170]="先序遍历结果:   ";
	BTree *pp,*stack[9];
	int top,a1=0;
	if(btree!=NULL)
	{
		top=0;
		stack[top]=btree;
		while(top>=0)
		{
			pp=stack[top];
			top--;
            while(pchar[a1]!='\0')
				a1++;
			pchar[a1]=pp->data;
            strcat(pchar,"       ");
			pchar[a1+5]='\0';   
			if(pp->rchild!=NULL)
			{
				top++;
				stack[top]=pp->rchild;
			}
			if(pp->lchild!=NULL)
			{
				top++;
				stack[top]=pp->lchild;
			}
		}
	}
 MessageBox(hWnd,pchar,"先序遍历",MB_OK);
}

void inordertraverse(BTree *btree)       //中序遍历
{   char pchar[170]="中序遍历结果:   ";
	BTree *stack[15],*pp;
	int top=0,a1=0;
	pp=btree;
	do
	{
		while(pp!=NULL)
		{
			top++;
			stack[top]=pp;
			pp=pp->lchild;
		
		}
		if(top>0)
		{
			pp=stack[top];
			top--;
    	   	while(pchar[a1]!='\0')
				a1++;
			pchar[a1]=pp->data;
            strcat(pchar,"       ");
			pchar[a1+5]='\0';   
	    	pp=pp->rchild;
		}
	}while(pp!=NULL|| top!=0);
   	MessageBox(hWnd,pchar,"中序遍历",MB_OK);
}

void postordertraverse(BTree *btree) //后序遍历
{
	char pchar[170]="后序遍历结果:   ";
	BTree *stack[15],*pp;
	int tag[15],top=0,a1=0;
	pp=btree;
	do{
		while(pp!=NULL)
		{
			top++;
			stack[top]=pp;
	 		tag[top]=0;
	        pp=pp->lchild;
		}
		if(top>0)
		{
			
			if(tag[top]==1)
			{
			    while(pchar[a1]!='\0')
				a1++;
			    pchar[a1]=stack[top]->data;
                strcat(pchar,"       ");
			    pchar[a1+5]='\0';   
				top--;
			}
			else
			{   pp=stack[top];
				if(top>0)
				{
				   pp=pp->rchild;
				   tag[top]=1;
				}
			}
		}
	}while(pp!=NULL||top!=0);
	MessageBox(hWnd,pchar,"后序遍历",MB_OK);
}
//修改结点值对话框
BOOL CALLBACK DlgProc(HWND hdlg,UINT message,WPARAM wParam,LPARAM lParam)
{   
	char cha1,cha2;
	switch(message)
	{
	case WM_INITDIALOG:
		 return 1;
	case WM_COMMAND:
		switch(LOWORD(wParam))
		{
		case IDOK:
			int i;
			char aa[3]="  ";
			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;
			 }
			 if(i>node)
             {
				 EndDialog(hdlg,1);
				 return 1;
			 }

			GetDlgItemText(hdlg,IDEDIT,lpString,2);
			EndDialog(hdlg,1);
			cha1=lpString[0];
			for(int j=0;j<=node;j++)
			{
                cha2=bt[j]->data;   
				if(cha2==cha1)
				{
					MessageBox(hWnd,_T("结点值已经存在! "),_T("警告"),MB_ICONEXCLAMATION|MB_OK);
					return 1;
				}
			}
			if(cha1==NULL)
				lpString[0]=bt[i]->data;
			else
				bt[i]->data=lpString[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[i].nx+8,nf[i].ny+12,aa,2);
			TextOut(hdc,nf[i].nx+8,nf[i].ny+12,&lpString[0],1);//strlen(lpString));
			
			return 1;
		}
		break;
	case WM_CLOSE:
		EndDialog(hdlg,1);
		return 1;
	}
	return 0;
}

 //图的广度优先搜索
void bfs(adjlist adj)                                                    
{   
	char pchar[70]="广度优先结果:   ";
	int front=0,rear=1,v,i,a1=0;
	struct edgenode *p1;
    int visited[9];
	int queue[9];
	for (i=0;i<9;i++)
		visited[i]=0;
	visited[0]=1;
	while(pchar[a1]!='\0')
         a1++;
	pchar[a1]=adj[0].data;
    strcat(pchar,"    ");
	pchar[a1+4]='\0';   
    queue[rear]=0;
	while(front!=rear)
	{
		front=(front+1)%9;
		v=queue[front];
		p1=adj[v].link;
		while(p1!=NULL)
		{
			if(visited[p1->adjvex]==0)
			{
				visited[p1->adjvex]=1;
				while(pchar[a1]!='\0')
				      a1++;
			    pchar[a1]=adj[p1->adjvex].data;
                strcat(pchar,"    ");
			    pchar[a1+4]='\0';   
				rear=(rear+1)%9;
				queue[rear]=p1->adjvex;
			}
			p1=p1->next;
		}
	}

	MessageBox(hWnd,pchar,"广度优先",MB_OK);
}

//图的深度优先搜索
void dfs(adjlist adj)                                    
{
	char pchar[70]="深度优先结果:   ";
	struct edgenode *stack[9],*p1;
	int visited[9],top=0,i,a1=0;
	for (i=0;i<9;i++)
		visited[i]=0;
	visited[0]=1;
	while(pchar[a1]!='\0')
        a1++;
	pchar[a1]=adj[0].data;
    strcat(pchar,"    ");
	pchar[a1+4]='\0';   
	p1=adj[0].link;
	while(top>0||p1!=NULL)
	{
		while(p1!=NULL)
		
			if(visited[p1->adjvex]!=0)
				p1=p1->next;
			else
			{
				while(pchar[a1]!='\0')
				    a1++;
			    pchar[a1]=adj[p1->adjvex].data;
                strcat(pchar,"    ");
			    pchar[a1+4]='\0';  
				visited[p1->adjvex]=1;
				top++;
				stack[top]=p1;
				p1=adj[p1->adjvex].link;
			}
			if(top>0)
			{   
				
				p1=stack[top];
                top--;
				p1=p1->next;
			}
		}

	MessageBox(hWnd,pchar,"深度优先",MB_OK);
}

//创建邻接点对话框
BOOL CALLBACK GDlgProc(HWND hdlg,UINT message,WPARAM wParam,LPARAM lParam)
{
	switch(message)
	{
	case WM_INITDIALOG:
		 return 1;
	case WM_COMMAND:
		switch(LOWORD(wParam))
		{
		case IDOK:
			int i,j;
			struct edgenode *p1,*q1; 
			for ( i=0;i<gnode;i++)
			 {
				 if(ix<=ginfo[i].gx+40&&iy<=ginfo[i].gy+40&&ix>=ginfo[i].gx&&iy>=ginfo[i].gy)
					 break;
			 }
			 if(i>=gnode)
             {
				 EndDialog(hdlg,1);
				 return 1;
			 }

			GetDlgItemText(hdlg,GIDEDIT,glpstring,2);
	        for(j=0;j<gnode;j++)
			{
				if(gp[j]==glpstring[0])
					break;
			}
			
			EndDialog(hdlg,1);
			if(j<gnode)
			{
		   	    hpen=CreatePen(PS_SOLID,2,RGB(0,0,255));
		        SelectObject(hdc,hpen);
			    MoveToEx(hdc,ginfo[i].gx+10,ginfo[i].gy+10,NULL);	
			    LineTo(hdc,ginfo[j].gx+10,ginfo[j].gy+10);
		    }
            else
			{	
				EndDialog(hdlg,1);
			    return 1;
			}
			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[i].gx+10,ginfo[i].gy+10,&gp[i],1);
			TextOut(hdc,ginfo[j].gx+10,ginfo[j].gy+10,&gp[j],1);
			if(graphtype==IDC_YSGRAPH)
			{
				int wy=(ginfo[i].gx+10+ginfo[j].gx+10)/2;
		        int wx=(ginfo[i].gy+10+ginfo[j].gy+10)/2;
			    wy=(wy+ginfo[j].gx+10)/2;
			    wx=(wx+ginfo[j].gy+10)/2;
                hpen=CreatePen(PS_SOLID,2,RGB(255,0,0));
		        SelectObject(hdc,hpen);
                hbrush=CreateSolidBrush(RGB(255,255,255));
		        SelectObject(hdc,hbrush);
			    if(gp[i]!=glpstring[0])
				   Pie(hdc,wy-5,wx-5,wy+5,wx+5,0,0,0,0);
			}
			if(graphtype==IDC_WSGRAPH)
			{
				p1=new struct edgenode;
			    q1=new struct edgenode;
			    p1->adjvex=i;
			    q1->adjvex=j;
			    p1->next=graph[j].link;
			    graph[j].link=p1;
			    q1->next=graph[i].link;
			    graph[i].link=q1;
			}
			else
			{
				q1=new struct edgenode;
				q1->adjvex=j;
				q1->next=graph[i].link;
				graph[i].link=q1;
			}
			return 1;
	      
		}
		break;
	case WM_CLOSE:
		EndDialog(hdlg,1);
		return 1;
	}
	return 0;
}

//输入图结点值对话框
BOOL CALLBACK NGDlgProc(HWND hdlg,UINT message,WPARAM wParam,LPARAM lParam)
{   char cha1,cha2;
	switch(message)
	{
	case WM_INITDIALOG:
		 return 1;
	case WM_COMMAND:
		switch(LOWORD(wParam))
		{
		case IDOK:
			int i;
			char aa[3]="  ";
			 for ( i=0;i<gnode;i++)
			 {
				 if(ix<=ginfo[i].gx+40&&iy<=ginfo[i].gy+40&&ix>=ginfo[i].gx&&iy>=ginfo[i].gy)
					 break;
			 }
			 if(i>=gnode)
             {
				 EndDialog(hdlg,1);
				 return 1;
			 }

			GetDlgItemText(hdlg,GIDEDIT,glpstring,2);
			EndDialog(hdlg,1);
			cha1=glpstring[0];
			for(int j=0;j<=gnode;j++)
			{
                cha2=graph[j].data;
				if(cha1==cha2&&cha1!=NULL)
				{
					MessageBox(hWnd,_T("结点值已经存在! "),_T("警告"),MB_ICONEXCLAMATION|MB_OK);
					return 1;
				}
			}
			
			if(cha1==NULL)
				glpstring[0]=graph[i].data;
            else
			{
				graph[i].data=glpstring[0];
			    gp[i]=graph[i].data;
			}
            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[i].gx+10,ginfo[i].gy+10,aa,2);
			TextOut(hdc,ginfo[i].gx+10,ginfo[i].gy+10,&glpstring[0],1);
			return 1;
			
		}
		break;
	case WM_CLOSE:
		EndDialog(hdlg,1);
		return 1;
	}
	return 0;
}
//创建图类型对话框
BOOL CALLBACK CREATEGRAPH(HWND hdlg,UINT message,WPARAM wParam,LPARAM lParam)
{
	int oldgraphtype=graphtype;
	switch(message)
	{
	case WM_INITDIALOG:
		CheckRadioButton(hdlg,IDC_WSGRAPH,IDC_YSGRAPH,IDC_WSGRAPH);
		return 0L;
	case WM_COMMAND:
		{
			switch(wParam)
			{
			case IDC_WSGRAPH:
				graphtype=IDC_WSGRAPH;
				break;
			case IDC_YSGRAPH:
				graphtype=IDC_YSGRAPH;
				break;
			case IDC_WSDQGRAPH:
				graphtype=IDC_WSDQGRAPH;
				break;
			case IDC_YSDQGRAPH:
				graphtype=IDC_YSDQGRAPH;
				break;
			case IDOK:
				EndDialog(hdlg,0);
				break;
			case IDCANCEL:
				graphtype=oldgraphtype;
				EndDialog(hdlg,0);
				break;
			}
		}
		break;
	case WM_CLOSE:
		EndDialog(hdlg,0);
		break;
	}
	return 0L;
}