tu.rar_tu

/**********************************以下为头文件*****************************************************************/ #include <stdio.h> #include <iostream> #include<malloc.h> using namespace std; #define LEN 60 #define NULL 0 /*********************************以下结构体定义**********************************************************/ typedef struct arc { bool mark; //访问标志 int num; //顶点编号 struct arc *link; //指向与该顶点连接的其余边的指针 }ARC; typedef struct node { bool mark; //访问标志 char letter; //顶点数据域 ARC *out; //指向该顶点边表的指针 }NODE; /**********************************以下为各个函数声明*********************************************************/ void creat (NODE *NODElist,int n); //输入并生成一个图函数 void DFS (NODE *NODElist,int n); //深度优先遍历函数 void BFS (NODE *NODElist,int n); //广度优先遍历函数 int pop (int *stack,int &i,int top); //出栈函数 int push (int *stack,int i,int top); //入栈函数 /***********************************以下为主函数********************************************************/ int main () { NODE NODElist[LEN]; int i,c,n=0; cout<<"请输入所要建立的顶点的个数:"; cin>>n; creat(NODElist,n); cout<<"建立图表完毕"<<endl; cout<<endl; for (;;)//循环输入 { cout<<"************ 程序功能如下，请输入您想实现的功能 ************"<<endl; cout<<"************ 按 1 键：深度优先遍历！ ************"<<endl; cout<<"************ 按 2 键：宽度优先遍历！ ************"<<endl; cout<<"************ 按 3 键：退出！ ************"<<endl; cin>>c; switch(c) { case 1: cout<<"深度优先遍历结果如下："<<endl; DFS(NODElist,n); cout<<endl; break; case 2: cout<<"宽度优先遍历结果如下："<<endl; BFS(NODElist,n); cout<<endl; break; case 3: return(0); cout<<"退出成功！"<<endl; break; default: cout<<"输入错误，请重新输入！"<<endl; cout<<endl; } } return (0); } /********************************以下为各个函数定义***********************************************************/ void creat (NODE *NODElist,int n) { int i,j,m; ARC *q,*p; for (i=0;i<n;i++) //输入顶点数据 { cout<<"请输入"<<i+1<<"个顶点: ", cin>>NODElist[i].letter; NODElist[i].mark=false; //设置访问标志初始为false NODElist[i].out=NULL; }; cout<<endl; for (i=0;i<n;i++) //设置顶点的边表 { cout<<"请输入第"<<i+1<<"个顶点关联边数: "; cin>>m; if (m) { NODElist[i].out=(ARC *)malloc(sizeof(ARC)); cout<<"***请输入第"<<i+1<<"个顶点的第"<<1<<"条边: "; cin>>NODElist[i].out->num; // 与第i个顶点相邻的图顶点编号 NODElist[i].out->link=NULL; NODElist[i].out->mark=false; p=NODElist[i].out; for(j=1;j<m;j++) { q=(ARC *)malloc(sizeof(ARC)); cout<<"***请输入第"<<i+1<<"个顶点的第"<<j+1<<"条边: "; cin>>q->num; q->link=NULL; q->mark=false; p->link=q; p=q; }; }; cout<<endl; }; } /***********************************************************************************************************/ int pop (int *stack,int &i,int top) { if (top>-1) { i=stack[top]; top--; }; return(top); } /***********************************************************************************************************/ int push (int *stack,int i,int top) { if (top<LEN) { top++; stack[top]=i-1; }; return(top); } /***********************************************************************************************************/ void BFS (NODE *NODElist,int n) { int i,head,rear,queen[LEN]; for (i=1;i<=n;i++) { if (NODElist[i-1].mark==false) { head=rear=-1; rear=push(queen,i,rear); while (head<rear) { head++; //查看队列中下一个顶点 cout<<NODElist[queen[head]].letter<<" "; if (NODElist[queen[head]].out) //如果出度不为0 { ARC *temp=NODElist[queen[head]].out; while (temp) //邻接到的顶点全部入队 { if (NODElist[(temp->num)-1].mark==false) //未被访问就入队 { rear=push(queen,temp->num,rear); NODElist[(temp->num)-1].mark=true; //访问过标记 }; temp=temp->link; }; }; }; }; }; for (i=0;i<n;i++) //清除访问标记，为其它优先遍历做准备 NODElist[i].mark=false; cout<<endl; } /***********************************************************************************************************/ void DFS (NODE *NODElist,int n) { int i,k,top=-1,p; bool numtfinished; int stack[LEN]; ARC *next[LEN]; //next[i]是每个顶点边表要检查的下一条边 for (i=0;i<n;i++) next[i]=NODElist[i].out; //next[i]初始化指向各顶点边表第一条边 for (k=0;k<n;k++) //搜索顶点集合中未被访问的顶点k，并从此出发遍历该顶点生成子树 { if (NODElist[k].mark==false) //此顶点未访问 { i=k; cout<<NODElist[i].letter<<" "; //访问此顶点 NODElist[i].mark=true; //该顶点已访问标记 numtfinished=true; while (numtfinished) //从此出发遍历该顶点的生成子树 { while (next[i]==NULL) //如果边表空则可以回溯顶点 { if (top==-1) //若栈空则该顶点生成子树遍历结束跳出循环 { numtfinished=false; cout<<endl; break; }; int &pi=i; top=pop(stack,pi,top); //否则深度搜索路径上的一个顶点出栈 i++; }; if (numtfinished) //检查与第i个顶点关联的一条尚未搜索的边 { p=next[i]->num; //指向边的另一端邻接顶点p p-=1; //因为顶点编号从1开始而数组下标从0开始 if (NODElist[p].mark==false)//顺此顶点的深度方向遍历 { top=push(stack,i,top); //当前顶点的前趋进栈 next[i]->mark=true; //前趋边访问过标记 cout<<NODElist[p].letter<<" "; //访问此顶点 NODElist[p].mark=true; //访问过标记 next[i]=next[i]->link; //指向顶点i边表的下一节点（边） i=p; //更换到邻接顶点p的边表 } else next[i]=next[i]->link; //此顶点已经标记过，更换边 }; }; }; }; for (i=0;i<n;i++) //清除访问标记，为其它优先遍历做准备 NODElist[i].mark=false; cout<<endl; } /***********************************************************************************************************/