s1.txt

包含图的遍历和线性链表两个内容

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <iostream.h>
#define M 100                                   
typedef struct                     //定义图
{
  int V[M];                        //顶点集
  int R[M][M];                     //二维数组，存放矩阵
  int vexnum;                      //顶点的个数
}Graph;                               
void creatgraph(Graph *g,int n)     //创建图
{
  int i,j,r1,r2;
  g->vexnum=n;
                           
  for(i=1;i<=n;i++)                //顶点用i表示
  {
    g->V[i]=i;                    //初始化u
  }
  
  for(i=1;i<=n;i++)                  //初始化矩阵R
   for(j=1;j<=n;j++)
    {
      g->R[i][j]=0;
    }
  cout<<"输入位于矩阵上半部分，有邻接的2个顶点"<<endl;
  //printf("Please input R,以 0,0 结束:\n");     //输入矩阵的上半部分，有邻接的2个顶点
  scanf("%d,%d",&r1,&r2);
  while(r1!=0&&r2!=0)   //当r1，r2均不为0时
   {
    g->R[r1][r2]=1;
    g->R[r2][r1]=1;      //实现矩阵的对称
    scanf("%d,%d",&r1,&r2);
   }
}
void printgraph(Graph *g)                 //输出图的邻接矩阵
{
   int i,j;
   for(i=1;i<=g->vexnum;i++)
{ 
   for(j=1;j<=g->vexnum;j++)
    {
      printf("%2d ",g->R[i][j]);        //矩阵输出
    }
   printf("\n");
   }
}
int visited[M];                     //全局变量：访问标志数组，初始值非1
void visitvex(Graph *g,int vex)     //访问顶点
{
   printf("%d ",g->V[vex]);
}
int firstadjvex(Graph *g,int vex)   //获取第一个未被访问的邻接节点
{
  int w,i;
  for(i=1;i<=g->vexnum;i++)
   {
    if(g->R[vex][i]==1&&visited[i]==0)
    {
      w=i;         //当w＝i时，跳出此次循环
      break;
    }
   else
    {
      w=0;
    }
  }
  return w;              //返回w值
}
int nextadjvex(Graph *g,int vex,int w)  //获取下一个未被访问的邻接节点(深度遍历)
{
  int t;
  t=firstadjvex(g,w);
  return t;
}
  void dfs(Graph *g,int vex)     //图的深度递归遍历
   {
    int w;
    visited[vex]=1;              //若顶点被访问过置1
    visitvex(g,vex);               //访问顶点
    for(w=firstadjvex(g,vex);w>0;w=nextadjvex(g,vex,w)) //从vex第一个邻接点开始
      if(!visited[w])
       {
        dfs(g,w);       //对尚未被访问过的顶点递归调用dfs深度优先搜索 
       }
   }
   void dfstraverse(Graph *g)      //对图g按深度优先探索遍历
   {
     int i;
     for(i=1;i<=g->vexnum;i++)
       visited[i]=0;          //标志数组初始化
     for(i=1;i<=g->vexnum;i++)
       if(!visited[i])              
    {
     dfs(g,i);}
    }

typedef struct  //定义队列
{
 int V[M];
 int front;   //定义头指针
 int rear;     //定义尾指针
}Queue;

void initqueue(Queue *q)//初始化队列,设定队头对尾指针均为哦0
{
  q->front=0;  
  q->rear=0;
}

int quempty(Queue *q)  //判断队列是否为空
{
  if(q->front==q->rear)
  {
   return 0;  //队列非空返回0
  }
  else
  {
   return 1;  //队列为空返回1
  }
}

enqueue(Queue *q,int x)   //入队操作,把元素x插入队列q
{
  if((q->rear+1)%M==q->front)
   {
    printf("The queue is overflow!\n");
    return 0;
   }
   else
   {
    q->V[q->rear]=x;       //将元素x插入对尾
    q->rear=(q->rear+1)%M; //修改对尾指针
    return 1;             //返回插入成功标志
   } 
}

dequeue(Queue *q)//出队操作，若队列不为空，删除队头元素
{
  int t;
  if(q->front==q->rear)
   {
     printf("The queue is empty!\n");
     return 0;  //队列为空无元素可删返回0
   }
   else
   {
     t=q->V[q->front];
     q->front=(q->front+1)%M;   //修改队头指针
     return t;  //返回队头元素的值
   }
}

void BESTraverse(Graph *g)/*广度遍历*/
{
  int i;
  Queue *q=(Queue *)malloc(sizeof(Queue));   
  for(i=1;i<=g->vexnum;i++)
  {
   visited[i]=0;   //标志数组初始化
  }
  initqueue(q);
  for(i=1;i<=g->vexnum;i++)
  {
    if(!visited[i])
     {
       visited[i]=1;
       visitvex(g,g->V[i]);   //访问该顶点，并置已被访问标志
       enqueue(q,g->V[i]);  //访问过的顶点入队列
       while(!quempty(q))   //当不为空队列时
      {
         int u,w;
         u=dequeue(q);
         for(w=firstadjvex(g,u);w>0;w=nextadjvex(g,u,w))
          {
            if(!visited[w])
            {
              visited[w]=1;
              visitvex(g,w);
              enqueue(q,w);
            }
          }
    }
   }
  }
}

main()   //主程序
{
  int n;    //n为顶点个数
  Graph *g=(Graph *)malloc(sizeof(Graph));
  char choice;
  cout<<"请输入顶点个数:";
  scanf("%d",&n);
  creatgraph(g,n);  //建立图
  cout<<"这是一个无向图的邻接矩阵:"<<endl;
  printgraph(g);    //输出矩阵
  input:
  printf("Please input b or d or q ,Breadth_first: b  Depth_first: d quit: q\n");
  while((choice=getchar())=='\n');
  if(choice=='b')     //当输入b时，采用广度优先探索遍历
    {
      printf("Breadth_first:\n");
      BESTraverse(g);
      printf("\n");
      goto input;
    }
  else if(choice=='d')//当输入d时，采用深度优先探索遍历
    {
      printf("Depth_first:\n");
      dfstraverse(g);
      printf("\n");
      goto input;
    }
  else if(choice=='q')  //当数入q时，退出
    {
     exit(0);
    }
  else
    {
      printf("Input error!Please input b or d!\n");
    }
}