main.cpp

数据结构试验 实验一 线性表的顺序表示与实现 实验二 线性表的链式表示与实现 实验三 栈与队列及其应用 实验四 二叉树的应用 实验五 图的遍历与应用 实验六 查找技术 实验七 内部排序

#include <iostream>
#define INFINITY 32767
#define MAX_VEX 20
#define QUEUE_SIZE (MAX_VEX+1)
using namespace std;
bool *visited; 
//图的邻接矩阵存储结构
typedef struct{ 
  char *vexs;
  int arcs[MAX_VEX][MAX_VEX]; 
  int vexnum,arcnum;
}Graph;
//队列类
class Queue{
  public:
  void InitQueue(){
    base=(int *)malloc(QUEUE_SIZE*sizeof(int));
    front=rear=0;
  }
  void EnQueue(int e){
    base[rear]=e;
    rear=(rear+1)%QUEUE_SIZE;
  }
  void DeQueue(int &e){
    e=base[front];
    front=(front+1)%QUEUE_SIZE;
  }
  public:
  int *base;
  int front;
  int rear;
};
int Locate(Graph G,char c){
  for(int i=0;i<G.vexnum;i++)
  if(G.vexs[i]==c) return i;
  return -1;
}
void CreateUDN(Graph &G){
  int i,j,w,s1,s2;
  char a,b;
  cout<<"输入顶点数和弧数:";
  cin>>G.vexnum>>G.arcnum;
  G.vexs=(char *)malloc(G.vexnum*sizeof(char));
  cout<<"输入"<<G.vexnum<<"个顶点.\n";
  for(i=0;i<G.vexnum;i++){
    cout<<"输入顶点"<<i<<":";
    cin>>G.vexs[i];
    }
  for(i=0;i<G.vexnum;i++)
    for(j=0;j<G.vexnum;j++)
      G.arcs[i][j]=INFINITY;
  cout<<"输入"<<G.arcnum<<"条弧.\n";
  for(i=0;i<G.arcnum;i++){
    cout<<"输入弧"<<i<<":";
    cin>>a >>b >> w;
    s1=Locate(G,a);
    s2=Locate(G,b);
    G.arcs[s1][s2]=G.arcs[s2][s1]=w;
  }
}
int FirstVex(Graph G,int k){
  if(k>=0 && k<G.vexnum){
    for(int i=0;i<G.vexnum;i++)
      if(G.arcs[k][i]!=INFINITY) return i;
  }
  return -1;
}

int NextVex(Graph G,int i,int j){
  if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){
    for(int k=j+1;k<G.vexnum;k++)
      if(G.arcs[i][k]!=INFINITY) return k;
  }
  return -1;
}
//深度优先遍历
void DFS(Graph G,int k){
  int i;
  if(k==-1){
    for(i=0;i<G.vexnum;i++)
      if(!visited[i]) DFS(G,i);
  }
  else{ 
    visited[k]=true;
    cout<<G.vexs[k]<<" ";
    for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
      if(!visited[i]) DFS(G,i);
  }
}
//广度优先遍历
void BFS(Graph G){
  int k;
  Queue Q;
  Q.InitQueue();
  for(int i=0;i<G.vexnum;i++)
    if(!visited[i]){
      visited[i]=true;
      cout<<G.vexs[i]<<" ";
      Q.EnQueue(i);
      while(Q.front!=Q.rear){
        Q.DeQueue(k);
        for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
          if(!visited[w]){ 
			visited[w]=true;
            cout<<G.vexs[w]<<" ";
            Q.EnQueue(w);
          }
      }
    }
}

//主函数
void main(){
  int i;
  Graph G;
  CreateUDN(G);
  visited=(bool *)malloc(G.vexnum*sizeof(bool)); 
  cout<<"\n广度优先遍历: ";
  for(i=0;i<G.vexnum;i++)
  visited[i]=false;
  DFS(G,-1);
  cout<<"\n深度优先遍历: ";
  for(i=0;i<G.vexnum;i++)
  visited[i]=false;
  BFS(G);
  cout<<"\n程序结束.\n";
}