?? 圖的深度優先遍歷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");
}
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -