欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)圖的創(chuàng)建與遍歷實(shí)驗(yàn)示例

 更新時(shí)間:2022年06月06日 17:28:21   作者:拆掉思維的墻  
這篇文章主要為大家介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)圖的創(chuàng)建與遍歷實(shí)驗(yàn)示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

一、 實(shí)驗(yàn)?zāi)康?/h2>

理解圖的基本概念,掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu),實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷算法與廣度優(yōu)先搜索遍歷算法。

二、 實(shí)驗(yàn)內(nèi)容

利用鄰接矩陣描述示例圖,編寫程序輸出示例圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的遍歷序列。

具體步驟如下:

  • 將圖的鄰接矩陣描述為一個(gè)二維數(shù)組,并將該數(shù)組定義為全局變量,以便數(shù)據(jù)的傳遞;
  • 定義一個(gè)隊(duì)列,在廣度優(yōu)先搜索時(shí),該隊(duì)列存儲(chǔ)已被訪問(wèn)的路徑長(zhǎng)度為1,2,…的頂點(diǎn);
  • 定義訪問(wèn)函數(shù)visit()、深度優(yōu)先搜索函數(shù)DFS()和廣度優(yōu)先搜索函數(shù)BFS();
  • 主函數(shù)實(shí)現(xiàn)各函數(shù)的調(diào)用。

三、 實(shí)驗(yàn)工具

Dev-C++

四、 實(shí)驗(yàn)代碼

//Authors:xiaobei
#include<stdio.h>
#include<stdlib.h>
#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
//定義圖結(jié)構(gòu)
typedef struct{
 VerTexType vexs[MVNum];
 ArcType arcs[MVNum][MVNum];
 int vexnum,arcnum;
}AMGraph;
//定義輔助鏈隊(duì)
typedef struct QNode{
 char data;
 struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
 QueuePtr front;
 QueuePtr rear;
}LinkQueue;
//定義全局輔助數(shù)組visited[MVNum]
int visited[MVNum];
//函數(shù)返回定點(diǎn)下標(biāo)
int LocateVex(AMGraph G,char v){
 int i;
 for(i=0;i<G.vexnum;i++)
  if(G.vexs[i]==v)
   return i;
  return -1;
}
//函數(shù)訪問(wèn)并輸出頂點(diǎn),返回下標(biāo)
int visit(AMGraph G,char v){
 int i;
 for(i=0;i<G.vexnum;i++)
  if(v==G.vexs[i])
   printf("%c",v);
 return LocateVex(G,v);
}
//函數(shù)創(chuàng)建無(wú)向圖,以鄰接矩陣形式
int CreateUDN(AMGraph &G){
 int i,j,k,v1,v2,w;
 printf("[輸入總頂點(diǎn)數(shù)和邊數(shù):]\n>>>");
 scanf("%d %d",&G.vexnum,&G.arcnum);
 for(i=0;i<G.vexnum;i++)
 {
  getchar();
  printf("[依次輸入各頂點(diǎn)的信息:]\n>>>");
  scanf("%c",&G.vexs[i]);
 }
 for(i=0;i<G.vexnum;i++)
  for(j=0;j<G.vexnum;j++)
   G.arcs[i][j] = MaxInt;
 for(k=0;k<G.arcnum;k++){
  getchar();
  printf("[輸入一條邊依附的頂點(diǎn)及權(quán)值:]\n>>>"); 
  scanf("%c %c %d",&v1,&v2,&w);
  i = LocateVex(G,v1);
  j = LocateVex(G,v2);
  G.arcs[i][j]=w;
  G.arcs[j][i]=G.arcs[i][j];
 }
 return 1;
}
//函數(shù)深度遍歷連通圖
void DFS_AM(AMGraph G,char v){
 int w,u;
 u = visit(G,v);
 visited[u] = 1;
 for(w=0;w<G.vexnum;w++){
  if((G.arcs[u][w]<MaxInt) && (!visited[w]))
   DFS_AM(G,G.vexs[w]);
 }
}
//函數(shù)初始化鏈隊(duì)
void InitQueue(LinkQueue &Q){
 Q.front = Q.rear = (QNode*)malloc(sizeof(QNode));
 Q.front->next=NULL;
}
//函數(shù)數(shù)據(jù)進(jìn)隊(duì)
void EnQueue(LinkQueue &Q,char e){
 QueuePtr p;
 p = (QNode*)malloc(sizeof(QNode));
 p->data = e;
 p->next = NULL;
 Q.rear->next=p;
 Q.rear = p;
}
//函數(shù)數(shù)據(jù)出隊(duì)
void DeQueue(LinkQueue &Q,char &e){
 QueuePtr p;
 if(Q.front==Q.rear);
 else
 {
  p = Q.front->next;
  e = p->data;
  Q.front->next = p->next;
  if(Q.rear==p)
   Q.rear=Q.front;
  free(p);
 }
}
//函數(shù)判斷鏈隊(duì)是否為空
int QueueEmpty(LinkQueue Q){
 if(Q.front==Q.rear)
  return 1;
 else
  return 0;
}
//函數(shù)返回頂點(diǎn)下一個(gè)鄰接點(diǎn)下標(biāo)
int FirstAdjVex(AMGraph G,int c){
 int j;
 for(j=0;j<G.vexnum;j++)
  if(G.arcs[c][j]<MaxInt && visited[j]==0)
   return j;
  return -1;
}
//函數(shù)返回頂點(diǎn)下一個(gè)相對(duì)鄰接點(diǎn)下標(biāo)
int NextAdjVex(AMGraph G,int c,int w){
 int j;
 for(j=0;j<G.vexnum;j++)
  if(G.arcs[c][j]<MaxInt && visited[j]==0)
   return j;
  return -1;
}
//函數(shù)廣度遍歷連通圖
void BFS_AM(AMGraph G,char v){
 int c,w,i;
 char u;
 LinkQueue Q;
 c = visit(G,v);
 visited[c] = 1;
 InitQueue(Q);
 EnQueue(Q,v);
 while(!QueueEmpty(Q)){
  DeQueue(Q,u);
  c = LocateVex(G,u);
  for(w=FirstAdjVex(G,c);w>=0;w=NextAdjVex(G,c,w))
  {
   if(!visited[w]){
    i = visit(G,G.vexs[w]);
    visited[i] = 1;
    EnQueue(Q,G.vexs[w]);
   }
  }
 }
}
//菜單打印
void Menu(){
 printf("\n————————菜單————————\n");
 printf("\n1.創(chuàng)建圖結(jié)構(gòu);\n");
 printf("\n2.深度遍歷(DFS);\n");
 printf("\n3.廣度遍歷(BFS);\n");
 printf("\n0.退出;\n");
 printf("\n——————————————————\n");
 printf("[請(qǐng)輸入你的選擇:]\n>>>");
}
//主函數(shù)
int main(){
 int i,user;
 char v;
 AMGraph G;
 while(1){
  Menu();
  scanf("%d",&user);
  switch(user){
  case 1:{
   CreateUDN(G);
   break;
  }
  case 2:{
   //初始化輔助數(shù)組
   for(i=0;i<G.vexnum;i++)
    visited[i] = 0;
   printf("[請(qǐng)輸入遍歷開始的頂點(diǎn):]\n>>>");
   getchar();
   scanf("%c",&v);
   DFS_AM(G,v);
   break;
  }
  case 3:{
   //初始化輔助數(shù)組
   for(i=0;i<G.vexnum;i++)
    visited[i] = 0;
   printf("[請(qǐng)輸入遍歷開始的頂點(diǎn):]\n>>>");
   getchar();
   scanf("%c",&v);
   BFS_AM(G,v);
   break;
  }
  case 0:{
   exit(0);
   break;
  }
  }
 }
 return 0;
}

五、 實(shí)驗(yàn)結(jié)果

六、總結(jié)與思考

  • 無(wú)向圖的鄰接矩陣是對(duì)稱的,有向圖鄰接矩陣可能不對(duì)稱。
  • 深度優(yōu)先搜索類似于棧結(jié)構(gòu)的出棧于入棧過(guò)程,模擬遞歸,其實(shí)遞歸也是通過(guò)堆棧的形式實(shí)現(xiàn)的。
  • 廣度遍歷是非遞歸過(guò)程,借助隊(duì)列來(lái)實(shí)現(xiàn)。
  • 輔助數(shù)組需要在全局使用,在主函數(shù)外定義。
  • DFS與BFS空間復(fù)雜度都是O(n),鄰接矩陣時(shí)間復(fù)雜度都是O(n2),鄰接表時(shí)間復(fù)雜度為O(n+e)。

鄰接矩陣示意圖:

以上就是C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)圖的創(chuàng)建與遍歷實(shí)驗(yàn)示例的詳細(xì)內(nèi)容,更多關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)圖的創(chuàng)建遍歷的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • C++數(shù)據(jù)結(jié)構(gòu)之list詳解

    C++數(shù)據(jù)結(jié)構(gòu)之list詳解

    list是一種序列式容器。list容器完成的功能實(shí)際上和數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表是極其相似的,list中的數(shù)據(jù)元素是通過(guò)鏈表指針串連成邏輯意義上的線性表,也就是list也具有鏈表的主要優(yōu)點(diǎn),即:在鏈表的任一位置進(jìn)行元素的插入、刪除操作都是快速的
    2021-11-11
  • C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單通訊錄管理系統(tǒng)

    C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單通訊錄管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單通訊錄管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-07-07
  • C++實(shí)現(xiàn)LeetCode(76.最小窗口子串)

    C++實(shí)現(xiàn)LeetCode(76.最小窗口子串)

    這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(76.最小窗口子串),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • C++ vector模擬實(shí)現(xiàn)的代碼詳解

    C++ vector模擬實(shí)現(xiàn)的代碼詳解

    vector是表示可變大小數(shù)組的序列容器,就像數(shù)組一樣,vector也采用的連續(xù)存儲(chǔ)空間來(lái)存儲(chǔ)元素,本質(zhì)講,vector使用動(dòng)態(tài)分配數(shù)組來(lái)存儲(chǔ)它的元素,本文將給大家詳細(xì)介紹一下C++ vector模擬實(shí)現(xiàn),需要的朋友可以參考下
    2023-07-07
  • C++構(gòu)造函數(shù)的類型,淺拷貝與深拷貝詳解

    C++構(gòu)造函數(shù)的類型,淺拷貝與深拷貝詳解

    這篇文章主要為大家詳細(xì)介紹了C++構(gòu)造函數(shù)的類型,淺拷貝與深拷貝,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助
    2022-03-03
  • 利用C語(yǔ)言解決八皇后問(wèn)題以及解析

    利用C語(yǔ)言解決八皇后問(wèn)題以及解析

    這篇文章主要給大家介紹了關(guān)于利用C語(yǔ)言解決八皇后問(wèn)題以及解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2018-12-12
  • C++中?‘=default?’及‘?=delete?’的使用

    C++中?‘=default?’及‘?=delete?’的使用

    這篇文章主要介紹了C++中?=default?及?=delete?使用,使用=default和=delete可以控制編譯器默認(rèn)函數(shù)體的使用,下面我們就來(lái)看看具體的室友方法吧,需要的朋友也可以參考一下
    2021-12-12
  • C++ continue和break語(yǔ)句

    C++ continue和break語(yǔ)句

    這篇文章主要介紹了C++ continue和break語(yǔ)句,文章圍繞continue和break語(yǔ)句的相關(guān)資料展開詳細(xì)內(nèi)容,需要的朋友可以參考一下,希望對(duì)大家有所幫助
    2021-11-11
  • C語(yǔ)言實(shí)現(xiàn)通訊錄管理系統(tǒng)

    C語(yǔ)言實(shí)現(xiàn)通訊錄管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)通訊錄管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-01-01
  • C語(yǔ)言詳細(xì)講解if語(yǔ)句與switch語(yǔ)句的用法

    C語(yǔ)言詳細(xì)講解if語(yǔ)句與switch語(yǔ)句的用法

    用 if 語(yǔ)句可以構(gòu)成分支結(jié)構(gòu),它根據(jù)給的條件進(jìn)行判定,以決定執(zhí)行哪個(gè)分支程序段,C 語(yǔ)言中還有另外一種分支語(yǔ)句,就是 switch 語(yǔ)句
    2022-05-05

最新評(píng)論