課程設(shè)計報告模板張苗.doc
《課程設(shè)計報告模板張苗.doc》由會員分享,可在線閱讀,更多相關(guān)《課程設(shè)計報告模板張苗.doc(19頁珍藏版)》請在裝配圖網(wǎng)上搜索。
內(nèi)蒙古科技大學 本科生課程設(shè)計說明書 題 目:C語言課程設(shè)計 —— 圖的遍歷 學生姓名:張苗 學 號:1376807337 專 業(yè):計算機科學與技術(shù) 班 級:3班 指導教師:周李涌 內(nèi)蒙古科技大學課程設(shè)計任務書 課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 設(shè)計題目 圖的遍歷 指導教師 周李涌 時間 2013年秋學期第15周至第19周 一、教學要求 1. 掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法,具備初步的獨立分析和設(shè)計能力 2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能 3. 提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力 4. 訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā),培養(yǎng)軟件工作者所應具備的科學的工作方法和作風 二、設(shè)計資料及參數(shù) 每個學生在教師提供的課程設(shè)計題目中任意選擇一題,獨立完成,題目選定后不可更換。 圖的遍歷 以數(shù)組表示法或鄰接表表示圖,在此基礎(chǔ)上實現(xiàn)對圖的遍歷。 要求設(shè)計類(或類模板)來描述圖,包含必要的構(gòu)造函數(shù)和析構(gòu)函數(shù),以及其他能夠完成如下功能的成員函數(shù): v 輸入圖、輸出圖 v 求圖中頂點V的第一個鄰接點 v 求圖中頂點V的下一個鄰接點 v 深度優(yōu)先遍歷圖 v 廣度優(yōu)先遍歷圖 并設(shè)計主函數(shù)測試該類(或類模板)。 三、設(shè)計要求及成果 1. 分析課程設(shè)計題目的要求 2. 寫出詳細設(shè)計說明 3. 編寫程序代碼,調(diào)試程序使其能正確運行 4. 設(shè)計完成的軟件要便于操作和使用 5. 設(shè)計完成后提交課程設(shè)計報告 四、進度安排 資料查閱與討論(1天) 系統(tǒng)分析(2天) 系統(tǒng)的開發(fā)與測試(5天) 編寫課程設(shè)計說明書和驗收(2天) 五、評分標準 1. 根據(jù)平時上機考勤、表現(xiàn)和進度,教師將每天點名和檢查 2. 根據(jù)課程設(shè)計完成情況,必須有可運行的軟件。 3. 根據(jù)課程設(shè)計報告的質(zhì)量,如有雷同,則所有雷同的所有人均判為不及格。 4. 根據(jù)答辯的情況,應能夠以清晰的思路和準確、簡練的語言敘述自己的設(shè)計和回答教師的提問 六、建議參考資料 1.《數(shù)據(jù)結(jié)構(gòu) (C語言版)》嚴蔚敏、吳偉民 主編 清華大學出版社 2004.11 2.《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計案例精編(用C/C++描述)》,李建學 等 編著,清華大學出版社 2007.2 3.《數(shù)據(jù)結(jié)構(gòu):用面向?qū)ο蠓椒ㄅcC++語言描述》,殷人昆 主編,清華大學出版社 2007.6 目 錄 內(nèi)蒙古科技大學課程設(shè)計任務書 I 第一章 需求分析 3 1.1 引言 3 1.2 任務概述 3 1.3 數(shù)據(jù)描述 3 1.4 功能需求 3 1.5 性能需求 3 1.6 運行需求 4 1.7 任務計劃 4 第二章 概要設(shè)計 5 2.1 總體設(shè)計 5 2.2 數(shù)據(jù)類型設(shè)計(或數(shù)據(jù)結(jié)構(gòu)設(shè)計) 5 2.3 接口設(shè)計 //函數(shù)聲明 5 2.4 運行界面設(shè)計 5 第三章 詳細設(shè)計 7 3.1 輸入模塊設(shè)計 7 3.2 輸出模塊設(shè)計 7 3.3 查找模塊設(shè)計 7 3.4 排序模塊設(shè)計 7 3.5 保存及讀取模塊設(shè)計 7 第四章 測試分析 8 4.1 測試程序執(zhí)行情況 8 4.2 出現(xiàn)的問題和解決的方法 8 第五章 用戶手冊(可選) 9 5.1 使用說明 9 5.2 運行說明 9 第六章 課程設(shè)計總結(jié) 10 附錄:程序代碼 11 參考文獻 12 致謝 13 第一章 需求分析 1.1 引言 本學期我們對《數(shù)據(jù)結(jié)構(gòu)》這門課程進行了學習。這門課程是一門實踐性非常強的課程,為了讓大家更好地理解與運用所學知識,提高動手能力,我們進行了此次課程設(shè)計實習。這次課程設(shè)計不但要求實習者掌握《數(shù)據(jù)結(jié)構(gòu)》中的各方面知識,還要求實習者具備一定的C語言基礎(chǔ)和編程能力。具體說來,這次課程設(shè)計主要有兩大方面目的。一是讓實習者通過實習掌握《數(shù)據(jù)結(jié)構(gòu)》中的知識。對于《圖的存儲與遍歷》這一課題來說,所要求掌握的數(shù)據(jù)結(jié)構(gòu)知識主要有:圖的鄰接表存貯結(jié)構(gòu)、隊列的基本運算實現(xiàn)、鄰接表的算法實現(xiàn)、圖的廣度優(yōu)先搜索周游算法實現(xiàn)、圖的深度優(yōu)先搜索周游算法實現(xiàn)。二是通過實習鞏固并提高實習者的C語言知識,并初步了解Visual C++的知識,提高其編程能力與專業(yè)水平。 1.2 任務概述 (1) 輸入的形式和輸入值的范圍; (2) 輸出的形式; (3) 程序所能達到的功能; (4) 測試數(shù)據(jù):包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。 1.3 數(shù)據(jù)描述 例子:輸入頂點數(shù)和邊數(shù):4 5 接著輸入頂點字符串:1 2 3 4 1.4 功能需求 以數(shù)組表示法或鄰接表表示圖,在此基礎(chǔ)上實現(xiàn)對圖的遍歷。 要求設(shè)計類(或類模板)來描述圖,包含必要的構(gòu)造函數(shù)和析構(gòu)函數(shù),以及其他能夠完成如下功能的成員函數(shù): v 輸入圖、輸出圖 v 求圖中頂點V的第一個鄰接點 v 求圖中頂點V的下一個鄰接點 v 深度優(yōu)先遍歷圖 v 廣度優(yōu)先遍歷圖 并設(shè)計主函數(shù)測試該類(或類模板)。 1.5 運行需求 在codeblock上運行,c語言程序 1.6 任務計劃 我們需要先進行總體設(shè)計,有一個大致的方向,然后我們需要把數(shù)據(jù)的結(jié)構(gòu)類型確定下來,第三步要把函數(shù)接口設(shè)計出來,第四步把運行界面設(shè)計,我就把大致程序框架做了出來。 我們接下來就應該進行詳細的設(shè)計來完成所需要的功能了 第二章 概要設(shè)計 2.1 總體設(shè)計 圖的實現(xiàn) 深度優(yōu)先遍歷 廣度優(yōu)先遍歷 輸出圖 輸入圖 創(chuàng)建圖 訪問下一個鄰接頂點 訪問鄰接頂點 2.2 數(shù)據(jù)類型設(shè)計(或數(shù)據(jù)結(jié)構(gòu)設(shè)計) 1.定義結(jié)點結(jié)構(gòu)類型 typedef struct node{ int adjvex; struct node *next; }EdgeNode; 2.定義虛擬結(jié)點結(jié)構(gòu)類型 typedef struct vnode{ char vertex; EdgeNode *firstedge; }VertexNode; 3.鄰接表類型 typedef struct { AdjList adjlist; int n,e; } ALGraph; 2.3 接口設(shè)計 可參考用以下表格形式: 表2.1:函數(shù)列表 函數(shù)名 函數(shù)格式 //即函數(shù)首部 函數(shù)功能 CreatALGraph 創(chuàng)建圖 DFS 深度優(yōu)先遍歷 BFS 廣度優(yōu)先遍歷 第三章 詳細設(shè)計 3.1圖的存儲 本課題要求采取鄰接表的存儲結(jié)構(gòu)。鄰接表是一種鏈式的存儲結(jié)構(gòu),在鄰接表中,對圖中每個頂點建立一個單鏈表,第i個單鏈表中的結(jié)點表示依附于頂點Vi的邊(對有向圖是以頂點Vi為尾的?。C總€結(jié)點由3個域組成,其中鄰接點域(adjvex)指示與頂點Vi鄰接的點在圖中的位置,鏈域(nextarc)指示下一條邊或弧的結(jié)點;數(shù)據(jù)域(info)存儲和邊或弧相關(guān)的信息,如權(quán)值等。 所以一開始必須先定義鄰接表的邊結(jié)點類型以及鄰接表類型,并對鄰接表進行初始化,然后根據(jù)所輸入的相關(guān)信息,包括圖的頂點數(shù)、邊數(shù)、是否為有向,以及各條邊的起點與終點序號,建立圖的鄰接表。此時要分兩種情況:有向圖與無向圖。對于無向圖,一條邊的兩的個頂點,互為鄰接點,所以在存儲時,應向起點的單鏈表表頭插入一邊結(jié)點,即終點。同時將終點的單鏈表表頭插入一邊結(jié)點,即起點。對于有向圖,只能向起點的單鏈表的表頭插入一個邊結(jié)點,即終點。但不能反過來。至于鄰接表的輸出,由于不了解C++中的繪圖操作,故采用for語句輸出各結(jié)點,并配合一些符號完成鄰接表的輸出。 3.2 圖的遍歷 3.2.1 圖的深度優(yōu)先遍歷 假設(shè)初始狀態(tài)是圖中所有頂點未曾被訪問,深度優(yōu)先遍歷可以從圖的初始點出發(fā),訪問初始點,然后依次從v未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖,直至圖中所有和v有路徑相通的頂點都被訪問到;若此時仍有頂點未被訪問到,則從另一個未被訪問的頂點出發(fā),重復上述過程,直至所有點都被訪問到為止。這是一個遞歸的過程。所以在實現(xiàn)深度優(yōu)先遍歷的過程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。而且在深度優(yōu)先搜索函數(shù)中必須設(shè)一標志數(shù)組以標記結(jié)點是否被訪問。 具體過程應為:先訪問初始點Vi,并標志其已被訪問。此時定義一指向邊結(jié)點的指針p,并建立一個while()循環(huán),以指針所指對象不為空為控制條件,當Vi的鄰接點未被訪問時,遞歸調(diào)用深度優(yōu)先遍歷函數(shù)訪問之。然后將p指針指向下一個邊結(jié)點。這樣就可以完成圖的深度優(yōu)先遍歷了。 void DFSM(ALGraph *G,int i) { EdgeNode *p; printf("%c ",G->adjlist[i].vertex); visited[i]=TRUE; p=G->adjlist[i].firstedge; while(p) { DFSM(G,p->adjvex); p=p->next; } } void DFS(ALGraph *G) { int i; for(i=0;i- 1.請仔細閱讀文檔,確保文檔完整性,對于不預覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認領(lǐng)!既往收益都歸您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標,表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 課程設(shè)計 報告 模板
鏈接地址:http://appdesigncorp.com/p-8383808.html