程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 純C說話:檢索與漫游廣度深度遍歷源碼分享

純C說話:檢索與漫游廣度深度遍歷源碼分享

編輯:關於C++

純C說話:檢索與漫游廣度深度遍歷源碼分享。本站提示廣大學習愛好者:(純C說話:檢索與漫游廣度深度遍歷源碼分享)文章只能為提供參考,不一定能成為您想要的結果。以下是純C說話:檢索與漫游廣度深度遍歷源碼分享正文



#include <stdio.h>
typedef  int  datatype;   /*假定線性表元素的類型為整型*/
#define  maxsize  1024    /*假定線性表的最年夜長度為1024*/
# define n 100            /* 圖的極點最年夜個數 */
typedef char VEXTYPE;  /* 極點的數據類型 */
typedef float ADJTYPE;  /* 權值類型 */
typedef struct
{
 VEXTYPE vexs[n] ;  /* 極點信息數組 */
    ADJTYPE arcs[n][n] ; /* 邊權數組 */
    int num ;    /* 極點的現實個數 */
}GRAPH;

/***********************1。置空圖**********************/
void GraphInit(GRAPH  *L)
{
 L->num=0;
}

/***********************2。求結點數**********************/
int GraphVexs(GRAPH  *L)
{
 return(L->num);
}

/***********************3。創立圖**********************/
void GraphCreate(GRAPH  *L)
{
 int i,j;
 GraphInit(L);
 printf("請輸出極點數量:");
 scanf("%d",&L->num);
 printf("請輸出各極點的信息(單個符號):");
 for(i=0;i<L->num;i++)
 {
  fflush(stdin);
  scanf("%c",&L->vexs[i]);
 }
 printf("請輸出邊權矩陣的信息:");
 for(i=0;i<L->num;i++)
 {
  for(j=0;j<L->num;j++)
  {
   scanf("%f",&L->arcs[i][j]);
  }
 }
 printf("圖曾經創立終了!");
}

/***********************4。圖的輸入**********************/
void GraphOut(GRAPH  L)
{
  int i,j;
  printf("\n圖的極點數量為:%d",L.num);
  printf("\n圖的各極點的信息為:\n");
  for(i=0;i<L.num;i++)
  printf("%c  ",L.vexs[i]);
  printf("\n圖的邊權矩陣的信息為:\n");
  for(i=0;i<L.num;i++)
  {
    for(j=0;j<L.num;j++)
    {
    printf("%6.2f ",L.arcs[i][j]);
    }
    printf("\n");
  }
  printf("圖曾經輸入終了!");
}

/***********************5。圖的深度漫游**********************/
void DFS(GRAPH  g,int qidian,int mark[])
//從第qidian個點動身深度優先漫游圖g中能拜訪的各個極點
{
  int v1;
  mark[qidian]=1;
  printf("%c   ",g.vexs[qidian]);
  for(v1=0;v1<g.num;v1++)
  {
   if(g.arcs[qidian][v1]!=0&&mark[v1]==0)
   DFS(g,v1,mark);
  }
}
/***********************6。圖的深度漫游**********************/
void GraphDFS(GRAPH  g)
//深度優先漫游圖g中能拜訪的各個極點
{
 int qidian,v,v1,mark[maxsize];
 printf("\n深度漫游:");
 printf("\n請輸出終點的下標:");
 scanf("%d",&qidian);
 for(v=0;v<g.num;v++)
 {
  mark[v]=0;
 }
 for(v=qidian;v<g.num+qidian;v++)
 {
  v1=v%g.num;
  if(mark[v1]==0)
   DFS(g,v1,mark);
 }
}
typedef  int DATATYPE;     //隊列元素的數據類型
typedef  struct

 DATATYPE data[maxsize]; //隊中元素
   int front,rear;   //隊頭元素下標、隊尾元素前面地位的下標
} SEQQUEUE;
/*****************************************************************************/
void QueueInit(SEQQUEUE *sq)
//將次序輪回隊列sq置空(初始化)
{
   sq->front=0;
   sq->rear=0;
}
/*****************************************************************************/
int QueueIsEmpty(SEQQUEUE sq)
//假如次序輪回隊列sq為空,勝利前往1,不然前往0
{
   if (sq.rear==sq.front)
      return(1);
   else
      return(0);
}
/*****************************************************************************/
int QueueFront(SEQQUEUE sq,DATATYPE *e)
//將次序輪回隊列sq的隊頭元素保留到e所指地址,勝利前往1,掉敗前往0
{
 if (QueueIsEmpty(sq))
    { printf("queue is empty!\n");return 0;}
    else
    { *e=sq.data[(sq.front)]; return 1;}
}
/*****************************************************************************/
int QueueIn (SEQQUEUE *sq,DATATYPE x)
//將元素x入隊列sq的隊尾,勝利前往1,掉敗前往0
{
 if (sq->front==(sq->rear+1)%maxsize)
 { 
  printf("queue is full!\n");
  return 0;
 }
 else
 {  
  sq->data[sq->rear]=x;
  sq->rear=(sq->rear+1)%maxsize;
  return(1);
 }
}
/*****************************************************************************/
int QueueOut(SEQQUEUE *sq)
//將隊列sq隊首元素出隊列,勝利前往1,掉敗前往0
{
    if (QueueIsEmpty(*sq))
    { 
  printf("queue is empty!\n");
  return 0;
 }
    else
    {       
  sq->front=(sq->front+1)%maxsize;
  return  1;
    }
}
/***********************7。圖的廣度漫游**********************/
void BFS(GRAPH g,int v,int mark[])
//從v動身廣度優先漫游圖g中能拜訪的各個極點
{
  int v1,v2;
  SEQQUEUE q;
  QueueInit(&q);
  QueueIn(&q,v);
  mark[v]=1;
  printf("%c   ",g.vexs[v]);
  while(QueueIsEmpty(q)==0) 
  {
    QueueFront(q,&v1);
    QueueOut(&q);
    for(v2=0;v2<g.num;v2++)
    {
      if(g.arcs[v1][v2]!=0&&mark[v2]==0)
      {
     QueueIn(&q,v2);
     mark[v2]=1;
     printf("%c   ",g.vexs[v2]);
      }
     }
  }
}
/***********************8。圖的廣度漫游**********************/
void GraphBFS(GRAPH  g)
//深度優先漫游圖g中能拜訪的各個極點
{
 int qidian,v,v1,mark[maxsize];
 printf("\n廣度漫游:");
 printf("\n請輸出終點的下標:");
 scanf("%d",&qidian);
 for(v=0;v<g.num;v++)
 {
  mark[v]=0;
 }
 for(v=qidian;v<g.num+qidian;v++)
 {
  v1=v%g.num;
  if(mark[v1]==0)
   BFS(g,v1,mark);
 }
}

/***********************主函數**********************/

void main()
{
 GRAPH tu;
 GraphCreate(&tu);
 GraphOut(tu);
 GraphDFS(tu);
 GraphBFS(tu);
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved