图的深度优先遍历c.cpp

深度优先搜索遍历, 数据结构 图的遍历

// 图的深度优先遍历C.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
#include <iomanip.h>
#include <string.h>

//*用student结构体来解决*//
//*在使用student之前源程序一点问题也没有*//
//*用//*//表示在刚开始编的程序基础上改动的地方*//
typedef struct
{
	char number[30];             //*学号*//    //*把NUMBER改成字符型的*//
	char name[20];       //*姓名*//               //*在这里字符比较难协调*//
	char sex[20];           //*性别*//
	int Ctextmark;     //*计算机考试成绩*//
	int Mathmark;      //*数学成绩*//
	char Adreess[50];          //*家庭住址*//
	char IsGood[20];               //*人品*//
}Student;

typedef struct Node
{	
	int  	 another_vertex;
	Student      info;         //*//                 //*表示权的信息*////*最好是把这里改成STUDENGT*//
	Node     *next;
} AdjNode;
//another_vertex表示该边的另外一个顶点在表头结点数组中的下标，
//info表示该边的权等信息，next指向链表中的下一个结点。

typedef struct
{	
	Student 			data;           //*//              //*这里也需要改动*//
	AdjNode        *head;
} AdjList;

typedef struct
{
	AdjList         *head_list;
	int             vertex_num;     //顶点数
	int             edge_num;     	//边数
}AdjGraph;


void Menu_first()
{
	printf("\n\n\n\n\n\n\n");
	printf("              *******************************************    \n\n");
	printf("                 制作者：熊梦非，欧阳猛，王年峰，王曜宇                   \n\n");
	printf("                           指导老师:孙夫雄                  \n");
    printf("                           所在班级:电子商务0702            \n\n");
    printf("              *******************************************    \n\n");
	printf("\n\n");
}


int Menu_second()
{
	int result;
	printf("\n\n\n\n\n");
    printf("               *************************************************\n\n");
	printf("                         1 --------- 建图并阅图      \n");
	printf("                         2 --------- 遍历图        \n");
	printf("                         0 --------- 退出程序        \n\n");
	printf("               *************************************************\n\n\n\n\n");
	printf("请用户输入要进行的功能!\n");
	scanf("%d",&result);
	return result;
}


//*防御性程序*//

void IsFault(int a,int b)          //*判断用户的输入的正确性*////*参数为分数*//
{
	if( (a<0||a>100) || (b<0||b>100) )
	{
		printf("\n\n您输入的数据不合法!\n");
		printf("程序自动退出!\n\n");
		system("pause");
		exit(0);
	}
	else
	{
		printf("\n\n您输入的数据完全合法，请继续操作!\n\n");
	}

}


//基于邻接表表示的有向带权图的建立算法
void CreateGraph(AdjGraph &g)
{  
	int n,first,second;              
	Student weight;                        //*//
    int h;                     //*针对name的*//
	int m;                    //*针对学号*//
	int A;               //*针对家庭住址*//
	int Y;       //*针对性别*//
	int Z;
	AdjNode *p;

	cout<<"请输入边的数量:";
	cin>>g.edge_num;
	cout<<"请输入顶点的数量:";
	cin>>g.vertex_num;

	IsFault(g.edge_num,g.vertex_num);   //*判断用户的输入是否有误*//
    
	g.head_list = new AdjList[g.vertex_num];
	for(n=0;n<g.vertex_num;n++)
		g.head_list[n].head=NULL;

	for(n=0;n<g.edge_num;n++)
	{ 
		printf("***************************************************\n\n");
		
		printf("\n请输入第%d条弧的弧头顶点的序号:",n+1);
		scanf("%d",&first);
		first--;

		printf("\n请输入第%d条弧的弧尾顶点的序号:",n+1);
		scanf("%d",&second);
		second--;

		printf("\n请输入该弧的权:\n\n");                     //*这里是权的输入地点*//

		printf("输入权节点学生的姓名!\n");       //*可能会出问题*//
        for(h=0;h<8;h++)
		{
			scanf("%c",&weight.name[h]);
		}
		printf("\n");

        printf("请输入权节点学生的学号!\n");
		for(m=0;m<10;m++)
		{
		       scanf("%c",&weight.number[m]);
		}
		printf("\n");

       printf("请输入权学生的性别: \n");
	   for(Y=0;Y<4;Y++)
	   {
		   scanf("%c",&weight.sex[Y]);
	   }
	   printf("\n");

        printf("该生人品是否有问题: \n");
		for(Z=0;Z<5;Z++)
		{
			scanf("%c",&weight.IsGood[Z]);
		}

        printf("\n");
		printf("请输入权节点学生的计算机考试分数!\n");
		scanf("%d",&weight.Ctextmark);
        
		printf("\n请输入权节点学生的数学考试分数!\n");
		scanf("%d",&weight.Mathmark);
        printf("\n请输入权节点学生的家庭住址!\n");
		for(A=0;A<8;A++)
		{
			scanf("%c",&weight.Adreess[A]);
		}
		//*判断*//
		IsFault(weight.Mathmark,weight.Ctextmark);                               //*完全用字符数组表示*//
		p = new AdjNode;

        for(h=0;h<8;h++)
			
		{
		     p->info.name[h] = weight.name[h];
		}

        for(m=0;m<10;m++)
		{
		    p->info.number[m] = weight.number[m];
		}

        p->info.Mathmark=weight.Mathmark;

		for(A=0;A<8;A++)
		{
			p->info.Adreess[A]=weight.Adreess[A];
		}
        for(Y=0;Y<4;Y++)
		{
			p->info.sex[Y]=weight.sex[Y];
		}

		for(Z=0;Z<5;Z++)
		{
			p->info.IsGood[Z]=weight.IsGood[Z];
		}

		p->info.Ctextmark = weight.Ctextmark;

		p->another_vertex=second;

		p->next=g.head_list[first].head;

		g.head_list[first].head =p;
   }
}


//基于邻接表表示的有向图的深度优先搜索非递归算法
void DFS(AdjGraph g,int v,int *visited)	                       //*这个函数需要修改*//              
{ 
	int stack[1000];//stack[MAXNODE];                     
	int top;                                  //栈顶指针

	int i;
	int num_1;
	int num_2;                        //*这个函数需要好好休整一下*//
	int num_3;
	int num_4;
	int num_5;

	AdjNode *pt;

	//*把遍历的效果做的好一些*//
	pt=g.head_list[0].head;                                         //进行访问
	printf("   %d\n ",v+1);                       //*将老师的Cout改成printf就OK了，为什么*//
    printf(" ∣\n");
	printf("  ∣\n");
    printf("  ∣\n");
	printf("  ∨");
	printf("------------------>");
    printf(" ∣");
	printf(" ------");               //*姓名*//
	printf(" 姓名:  ");
    for(num_1=1;num_1<8;num_1++)
	{
		printf("%c",pt->info.name[num_1]);
	}

	printf("\n");
	printf("                        ∣");
	printf(" ------");                   //*学号*//
	printf(" 学号: ");

    for(num_2=0;num_2<10;num_2++)
	{
			 printf("%c",pt->info.number[num_2]);
	}

	printf("\n");
    printf("                        ∣");
	printf(" ------");                      //*性别*//
	printf(" 性别: ");

	for(num_3=1;num_3<4;num_3++)
	{
		printf("%c",pt->info.sex[num_3]);
	}

	printf("\n");
	printf("                        ∣");
	printf(" ------");                      //*家庭住址*//
	printf(" 家庭住址: ");
     for(num_4=1;num_4<8;num_4++)
	{
			printf("%c",pt->info.Adreess[num_4]);
	}
    
	printf("\n");
    printf("                        ∣");
	printf(" ------");   
	printf(" 是否有人品问题!---");
	for(num_5=0;num_5<5;num_5++)
	{
		printf("%c",pt->info.IsGood[num_5]);
	}

	printf("\n");
	printf("                        ∣");
	printf(" ------");                        //*数学成绩*//
	printf(" 数学成绩: ");
    printf(" %d",pt->info.Mathmark);
    
	printf("\n");
    printf("                        ∣");
	printf(" ------");                           //*计算机考试成绩*//
	printf(" 计算机成绩: ");
    printf(" %d",pt->info.Ctextmark);

	printf("\n");

	top=0;

	visited[v]=1; 
	               //置已访问标志
	stack[top]=v;
	
	while(top>=0)                     //*这一块有问题*//
	{  
		pt=g.head_list[stack[top]].head;          //*Stack[top]=0*//

		while((pt!=NULL) && visited[pt->another_vertex])      //*是以PT的值来控制输出*//
		
			     pt=pt->next;                        //找一个未被访问过的邻接顶点
		
		      if (!pt)
			  {
		     	        top--;                             //没找到,返回到前一次被访问过的顶点
			  }
	     	   else
			   { 
			         i=pt->another_vertex;             //进行访问
			         printf("  %d\n",i+1);              //*将老师的Cout改成printf就OK了，为什么*//
			         printf(" ∣\n");
			         printf(" ∣\n");
			         printf(" ∣\n");
			         printf(" ∨");
		         	 printf("------------------>");
			         printf("  ∣");
		         	 printf(" ------");        //*姓名*//
			         printf(" 姓名: ");
                     for(num_1=1;num_1<8;num_1++)
					 {
				        printf("%c",g.head_list[i].head->info.name[num_1]);
					 }

                     printf("\n");
	                 printf("                        ∣");
		             printf(" ------");        //*学号*//
		             printf(" 学号: ");
                     for(num_2=0;num_2<10;num_2++)
					 {
			               printf("%c",g.head_list[i].head->info.number[num_2]);
					  }

		             printf("\n");
                     printf("                        ∣");
			         printf(" ------");          //*性别*//
                     printf(" 性别: ");
           
                     for(num_3=1;num_3<4;num_3++)
					{
			             printf("%c",g.head_list[i].head->info.sex[num_3]);
					 }

		             printf("\n");
		             printf("                        ∣");
		             printf(" ------");         //*家庭住址*//
                     printf(" 家庭住址: ");
            
                     for(num_4=1;num_4<8;num_4++)
					{
				         printf("%c",g.head_list[i].head->info.Adreess[num_4]);
					}

			        printf("\n");
					printf("                        ∣");
		            printf(" ------");    
					printf(" 是否有人品问题!---");
                    for(num_5=0;num_5<5;num_5++)
					{
		                      printf("%c",g.head_list[i].head->info.IsGood[num_5]);
					}
                   
					printf("\n");
	                printf("                        ∣");
			        printf(" ------");       //*数学成绩*//
			        printf(" 数学成绩: ");
                    printf(" %d",g.head_list[i].head->info.Mathmark);

		            printf("\n");
                    printf("                        ∣");
		            printf(" ------");          //*计算机考试成绩*//
                    printf(" 计算机成绩: ");
                    printf(" %d",g.head_list[i].head->info.Ctextmark);

                    printf("\n");
						
		            visited[i]=1; 
				                            //置已访问标志
			        top++;
		            stack[top]=i;                //*//
			   }
	}  
}


void DFSTrans(AdjGraph g)
{ 
	int *visited,Q;

	visited = new int[g.vertex_num];                  //*表示存储已经访问过的*//
	memset(visited,0,sizeof(int)*g.vertex_num);
  
	for(Q=0;Q<g.vertex_num;Q++)
		if(!visited[Q])
			DFS(g,Q,visited);
   
	delete []visited;
	
}


void Graphprint(AdjGraph g)                    //*//
{
	AdjNode *p;
	int j;
	int L;
	int f;
	int J;
	for(int n=0;n<g.vertex_num;n++)
	{
		printf("\n\n\n******************************\n");
		printf("\n第%d个顶点的邻接表信息:",n+1);
		p=g.head_list[n].head;
		if(p==NULL)
			printf("没有任何连接顶点",n);
		while(p)
		{
			printf("\n\t连接第%d顶点, \n\n",p->another_vertex+1);        //*这里是打印图的节点的地方*//
			printf("链接的权值的具体信息为：\n\n\n");

			printf("连接权学生的姓名：   ");
			for(j=1;j<8;j++)
			{
				printf("%c",p->info.name[j]);
			}

			printf("\n\n");
			printf("链接的权学生的性别是:    ");
			for(J=1;J<4;J++)
			{
				printf("%c",p->info.sex[J]);
			}

			printf("\n\n");
            printf("连接权的学生的学号是:    ");
			for(L=0;L<10;L++)
			{
			      printf("%c",p->info.number[L]);
			}

            printf("\n\n");
			printf("连接权的学生的计算机考试分数：  %d\n\n",p->info.Ctextmark); //*这是对学生信息的输出*//
			printf("链接权的学生的数学考试分数：    %d\n\n",p->info.Mathmark);
			printf("链接权的学生的家庭住址是：  ");

			for(f=1;f<8;f++)
			{
				printf("%c",p->info.Adreess[f]);
			}
			p=p->next;
		}
		printf("\n");
	}
}

//*主函数模块*//

void main()
{  
   int Flag;
   AdjGraph g;
   
   Menu_first();
   system("pause");
   system("cls");
    printf(" \n\n下面开始建立图!\n\n");
    CreateGraph(g);         //*先建立图*//
    system("pause");
    system("cls");

  while(1)        //*进入循环*//
  {
	  Flag=Menu_second();
      system("pause");
      system("cls");
	switch(Flag)
	{
    	case 1:
			
	        Graphprint(g);                       //*阅读图*//
		    system("pause");
		    system("cls");
	    break;                                       //*这个功能没有问题*//

		case 2:
                   printf("\n\n深度优先搜索非递归算法的结果:\n\n");
		           printf("\n\n下面由上至下的表示遍历顺序！\n\n");
		            printf("从左至右表示遍历的节点的具体的信息!\n\n\n");
	               DFSTrans(g);                         //*遍历图*//         //*开始这里很大问题*//
		           printf("\n\n\n");
		           system("pause");
		           system("cls");                              //*功能已经实现*//
		   break;

		case 0:
            exit(0);           //*退出程序*//
			break;

		default:
			printf("您的输入不合法!\n");
			printf("请重新输入\n");
            system("pause");
			system("cls");
	}
  }
}