純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);
}