課程名稱資料結構成績
實驗專案圖指導教師
學生姓名學號班級專業
實驗地點實驗日期年月日
圖一、實習目的
熟悉圖的兩種常用的儲存結構,以及在這兩種儲存結構上的兩種遍歷圖的方法,即深度優先遍歷和廣度優先遍歷。進一步掌握遞迴演算法的設計方法。
關於各種典型著名的複雜演算法,在上機實習方面不做基本要求。更適合於安排大型課程設計。
二、例項
1. 圖的鄰接矩陣儲存(陣列表示)、簡單輸出。
本題的目的是給出乙個無向圖陣列表示的簡單啟示,在此基礎上稍加改動可以實現網(邊上帶權值的圖)的鄰接矩陣表示。
# include
# include
# define max 20
typedef int vextype;
typedef vextype mgraph[max][max]; /* mgraph是二維陣列型別識別符號 */
/* 函式原形宣告 */
void creat_mg(mgraph g);
void out_mg(mgraph g);
mgraph g1g1是鄰接矩陣的二維陣列名 */
int n,e,v0;
/* 主函式 */
void main()
/* main */
/* 建立鄰接矩陣 */
void creat_mg(mgraph g)
} /* creat_mg */
/* 鄰接矩陣簡單輸出,為了檢查輸入是否正確 */
void out_mg(mgraph g)
/* 輸出所存在的邊 */
for(i=1; i<=n;i++)
for(j=1;j<=n;j++)
if(g[i][j]==1)printf("\n 存在邊< %d,%d >",i,j);
printf("\n\n 打回車鍵,繼續。"); ch=getchar();
} /* out_mg */
程式執行結果輸出如下:
2.圖的鄰接鍊錶儲存及遞迴深度優先遍歷。
# include
# include
# define max 20
typedef int vextype;
typedef struct vnode
vnodevnode是頂點的結點結構 */
typedef vnode lgraph[maxlgraph是一維陣列型別識別符號 */
/* 函式原形宣告 */
void creat_l(lgraph g);
void out_l(lgraph g);
void dfsl(lgraph g,int v);
lgraph gaga是鄰接鍊錶的表頭陣列名 */
int n,e, vis[max
/* 主函式 */
void main()
/* main */
/* 建立鄰接鍊錶 */
void creat_l(lgraph g)
for(k=1;k<=e; k++)
/* creat_l */
/* 鄰接鍊錶的簡單輸出,為了檢查輸入是否正確 */
/*鄰接鍊錶的輸出*/
void out_l(lgraph g)
}printf("\n\n 打回車鍵,繼續。");
ch=getcharout_l */
/* 深度優先遍歷圖 */
void dfsl(lgraph g,int v)
/* dfs */
程式執行介面輸出如下:
注:圖的廣度優先遍用非遞迴方法容易理解,非遞迴方法需要輔助佇列q以及出隊、入隊函式。由於篇幅所限這裡不在給出完整的源程式,僅給出粗略的演算法(但比書上演算法描述的更加具體詳細)供參考。
/* 廣度優先遍歷圖 */
void bfsl(lgraph g,int v_)
printf("\n\n 打回車鍵,繼續。「); ch=getch();
} /* bfsl */
三.實習題
資料結構實驗
資訊23 2120502060 古碧野一 實驗題目 建立乙個線性表,實現線性表的建立,插入,刪除和遍歷 二.實驗目的和要求 實驗目的 熟練掌握線性表的基本操作在順序儲存結構上的實現。實驗要求 用c語言編寫源程式,並除錯通過,測試正確。三.主要儀器裝置 windows xp操作平台,visual c ...
資料結構實驗
一 實驗目的 1 了解二叉樹的定義及基本運算。2 掌握二叉樹的描述方法 特點 性質及儲存結構。3 掌握二叉樹的基本操作演算法。4 自主設計二叉樹建立 遍歷等操作的整個程式。二 實驗內容 根據建立任意給定的二叉樹,並對此二叉樹進行前序 中序 後序 層次四種遍歷。基本要求 1 具有二叉樹的建立功能 2 ...
資料結構實驗
一 實驗題目編寫乙個程式實現雙鏈隊的各種基本運算,並在此基礎上設計乙個主程式完成如下功能 1 初始化鏈隊q 2 判斷鏈隊q是否為空 3 依次進隊元素a,b,c 4 出隊乙個元素,輸出該元素 5 輸出鏈隊q的元素個數 6 依次進鏈隊元素d,e,f 7 輸出鏈隊q的元素個數 8 輸出出隊序列 9 釋放鏈...