課程設(shè)計(jì)報(bào)告模板張苗.doc

《課程設(shè)計(jì)報(bào)告模板張苗.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《課程設(shè)計(jì)報(bào)告模板張苗.doc（19頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

內(nèi)蒙古科技大學(xué) 本科生課程設(shè)計(jì)說明書 題 目：C語言課程設(shè)計(jì) —— 圖的遍歷 學(xué)生姓名：張苗 學(xué) 號(hào)：1376807337 專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí)：3班 指導(dǎo)教師：周李涌 內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)任務(wù)書 課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 設(shè)計(jì)題目 圖的遍歷 指導(dǎo)教師 周李涌 時(shí)間 2013年秋學(xué)期第15周至第19周 一、教學(xué)要求 1. 掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力 2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能 3. 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力 4. 訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng) 二、設(shè)計(jì)資料及參數(shù) 每個(gè)學(xué)生在教師提供的課程設(shè)計(jì)題目中任意選擇一題，獨(dú)立完成，題目選定后不可更換。 圖的遍歷 以數(shù)組表示法或鄰接表表示圖，在此基礎(chǔ)上實(shí)現(xiàn)對(duì)圖的遍歷。 要求設(shè)計(jì)類（或類模板）來描述圖，包含必要的構(gòu)造函數(shù)和析構(gòu)函數(shù)，以及其他能夠完成如下功能的成員函數(shù)： v 輸入圖、輸出圖 v 求圖中頂點(diǎn)V的第一個(gè)鄰接點(diǎn) v 求圖中頂點(diǎn)V的下一個(gè)鄰接點(diǎn) v 深度優(yōu)先遍歷圖 v 廣度優(yōu)先遍歷圖 并設(shè)計(jì)主函數(shù)測試該類（或類模板）。 三、設(shè)計(jì)要求及成果 1. 分析課程設(shè)計(jì)題目的要求 2. 寫出詳細(xì)設(shè)計(jì)說明 3. 編寫程序代碼，調(diào)試程序使其能正確運(yùn)行 4. 設(shè)計(jì)完成的軟件要便于操作和使用 5. 設(shè)計(jì)完成后提交課程設(shè)計(jì)報(bào)告 四、進(jìn)度安排 資料查閱與討論（1天） 系統(tǒng)分析（2天） 系統(tǒng)的開發(fā)與測試（5天） 編寫課程設(shè)計(jì)說明書和驗(yàn)收（2天） 五、評(píng)分標(biāo)準(zhǔn) 1. 根據(jù)平時(shí)上機(jī)考勤、表現(xiàn)和進(jìn)度，教師將每天點(diǎn)名和檢查 2. 根據(jù)課程設(shè)計(jì)完成情況，必須有可運(yùn)行的軟件。 3. 根據(jù)課程設(shè)計(jì)報(bào)告的質(zhì)量，如有雷同，則所有雷同的所有人均判為不及格。 4. 根據(jù)答辯的情況，應(yīng)能夠以清晰的思路和準(zhǔn)確、簡練的語言敘述自己的設(shè)計(jì)和回答教師的提問 六、建議參考資料 1．《數(shù)據(jù)結(jié)構(gòu) （C語言版）》嚴(yán)蔚敏、吳偉民 主編 清華大學(xué)出版社 2004.11 2．《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)案例精編（用C/C++描述）》，李建學(xué) 等 編著，清華大學(xué)出版社 2007.2 3.《數(shù)據(jù)結(jié)構(gòu):用面向?qū)ο蠓椒ㄅcC++語言描述》，殷人昆 主編，清華大學(xué)出版社 2007.6 目 錄 內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)任務(wù)書 I 第一章 需求分析 3 1.1 引言 3 1.2 任務(wù)概述 3 1.3 數(shù)據(jù)描述 3 1.4 功能需求 3 1.5 性能需求 3 1.6 運(yùn)行需求 4 1.7 任務(wù)計(jì)劃 4 第二章 概要設(shè)計(jì) 5 2.1 總體設(shè)計(jì) 5 2.2 數(shù)據(jù)類型設(shè)計(jì)（或數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)） 5 2.3 接口設(shè)計(jì) //函數(shù)聲明 5 2.4 運(yùn)行界面設(shè)計(jì) 5 第三章 詳細(xì)設(shè)計(jì) 7 3.1 輸入模塊設(shè)計(jì) 7 3.2 輸出模塊設(shè)計(jì) 7 3.3 查找模塊設(shè)計(jì) 7 3.4 排序模塊設(shè)計(jì) 7 3.5 保存及讀取模塊設(shè)計(jì) 7 第四章 測試分析 8 4.1 測試程序執(zhí)行情況 8 4.2 出現(xiàn)的問題和解決的方法 8 第五章 用戶手冊（可選） 9 5.1 使用說明 9 5.2 運(yùn)行說明 9 第六章 課程設(shè)計(jì)總結(jié) 10 附錄：程序代碼 11 參考文獻(xiàn) 12 致謝 13 第一章 需求分析 1.1 引言 本學(xué)期我們對(duì)《數(shù)據(jù)結(jié)構(gòu)》這門課程進(jìn)行了學(xué)習(xí)。這門課程是一門實(shí)踐性非常強(qiáng)的課程，為了讓大家更好地理解與運(yùn)用所學(xué)知識(shí)，提高動(dòng)手能力，我們進(jìn)行了此次課程設(shè)計(jì)實(shí)習(xí)。這次課程設(shè)計(jì)不但要求實(shí)習(xí)者掌握《數(shù)據(jù)結(jié)構(gòu)》中的各方面知識(shí)，還要求實(shí)習(xí)者具備一定的C語言基礎(chǔ)和編程能力。具體說來，這次課程設(shè)計(jì)主要有兩大方面目的。一是讓實(shí)習(xí)者通過實(shí)習(xí)掌握《數(shù)據(jù)結(jié)構(gòu)》中的知識(shí)。對(duì)于《圖的存儲(chǔ)與遍歷》這一課題來說，所要求掌握的數(shù)據(jù)結(jié)構(gòu)知識(shí)主要有：圖的鄰接表存貯結(jié)構(gòu)、隊(duì)列的基本運(yùn)算實(shí)現(xiàn)、鄰接表的算法實(shí)現(xiàn)、圖的廣度優(yōu)先搜索周游算法實(shí)現(xiàn)、圖的深度優(yōu)先搜索周游算法實(shí)現(xiàn)。二是通過實(shí)習(xí)鞏固并提高實(shí)習(xí)者的C語言知識(shí)，并初步了解Visual C++的知識(shí)，提高其編程能力與專業(yè)水平。 1.2 任務(wù)概述 (1) 輸入的形式和輸入值的范圍； 　　(2) 輸出的形式； 　　(3) 程序所能達(dá)到的功能； 　　(4) 測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。 1.3 數(shù)據(jù)描述 例子：輸入頂點(diǎn)數(shù)和邊數(shù)：4 5 接著輸入頂點(diǎn)字符串：1 2 3 4 1.4 功能需求 以數(shù)組表示法或鄰接表表示圖，在此基礎(chǔ)上實(shí)現(xiàn)對(duì)圖的遍歷。 要求設(shè)計(jì)類（或類模板）來描述圖，包含必要的構(gòu)造函數(shù)和析構(gòu)函數(shù)，以及其他能夠完成如下功能的成員函數(shù)： v 輸入圖、輸出圖 v 求圖中頂點(diǎn)V的第一個(gè)鄰接點(diǎn) v 求圖中頂點(diǎn)V的下一個(gè)鄰接點(diǎn) v 深度優(yōu)先遍歷圖 v 廣度優(yōu)先遍歷圖 并設(shè)計(jì)主函數(shù)測試該類（或類模板）。 1.5 運(yùn)行需求 在codeblock上運(yùn)行，c語言程序 1.6 任務(wù)計(jì)劃 我們需要先進(jìn)行總體設(shè)計(jì)，有一個(gè)大致的方向，然后我們需要把數(shù)據(jù)的結(jié)構(gòu)類型確定下來，第三步要把函數(shù)接口設(shè)計(jì)出來，第四步把運(yùn)行界面設(shè)計(jì)，我就把大致程序框架做了出來。 我們接下來就應(yīng)該進(jìn)行詳細(xì)的設(shè)計(jì)來完成所需要的功能了 第二章 概要設(shè)計(jì) 2.1 總體設(shè)計(jì) 圖的實(shí)現(xiàn) 深度優(yōu)先遍歷 廣度優(yōu)先遍歷 輸出圖 輸入圖 創(chuàng)建圖 訪問下一個(gè)鄰接頂點(diǎn) 訪問鄰接頂點(diǎn) 2.2 數(shù)據(jù)類型設(shè)計(jì)（或數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)） 1.定義結(jié)點(diǎn)結(jié)構(gòu)類型 typedef struct node{ int adjvex; struct node *next; }EdgeNode; 2.定義虛擬結(jié)點(diǎn)結(jié)構(gòu)類型 typedef struct vnode{ char vertex; EdgeNode *firstedge; }VertexNode; 3.鄰接表類型 typedef struct { AdjList adjlist; int n,e; } ALGraph; 2.3 接口設(shè)計(jì) 可參考用以下表格形式： 表2.1：函數(shù)列表 函數(shù)名 函數(shù)格式 //即函數(shù)首部 函數(shù)功能 CreatALGraph 創(chuàng)建圖 DFS 深度優(yōu)先遍歷 BFS 廣度優(yōu)先遍歷 第三章 詳細(xì)設(shè)計(jì) 3.1圖的存儲(chǔ) 本課題要求采取鄰接表的存儲(chǔ)結(jié)構(gòu)。鄰接表是一種鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)，在鄰接表中，對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊（對(duì)有向圖是以頂點(diǎn)Vi為尾的?。?。每個(gè)結(jié)點(diǎn)由3個(gè)域組成，其中鄰接點(diǎn)域（adjvex）指示與頂點(diǎn)Vi鄰接的點(diǎn)在圖中的位置，鏈域（nextarc）指示下一條邊或弧的結(jié)點(diǎn)；數(shù)據(jù)域（info）存儲(chǔ)和邊或弧相關(guān)的信息，如權(quán)值等。 所以一開始必須先定義鄰接表的邊結(jié)點(diǎn)類型以及鄰接表類型，并對(duì)鄰接表進(jìn)行初始化，然后根據(jù)所輸入的相關(guān)信息，包括圖的頂點(diǎn)數(shù)、邊數(shù)、是否為有向，以及各條邊的起點(diǎn)與終點(diǎn)序號(hào)，建立圖的鄰接表。此時(shí)要分兩種情況：有向圖與無向圖。對(duì)于無向圖，一條邊的兩的個(gè)頂點(diǎn)，互為鄰接點(diǎn)，所以在存儲(chǔ)時(shí)，應(yīng)向起點(diǎn)的單鏈表表頭插入一邊結(jié)點(diǎn)，即終點(diǎn)。同時(shí)將終點(diǎn)的單鏈表表頭插入一邊結(jié)點(diǎn)，即起點(diǎn)。對(duì)于有向圖，只能向起點(diǎn)的單鏈表的表頭插入一個(gè)邊結(jié)點(diǎn)，即終點(diǎn)。但不能反過來。至于鄰接表的輸出，由于不了解C++中的繪圖操作，故采用for語句輸出各結(jié)點(diǎn)，并配合一些符號(hào)完成鄰接表的輸出。 3.2 圖的遍歷 3.2.1 圖的深度優(yōu)先遍歷 假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)未曾被訪問，深度優(yōu)先遍歷可以從圖的初始點(diǎn)出發(fā)，訪問初始點(diǎn)，然后依次從v未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到；若此時(shí)仍有頂點(diǎn)未被訪問到，則從另一個(gè)未被訪問的頂點(diǎn)出發(fā)，重復(fù)上述過程，直至所有點(diǎn)都被訪問到為止。這是一個(gè)遞歸的過程。所以在實(shí)現(xiàn)深度優(yōu)先遍歷的過程中必須遞歸調(diào)用深度優(yōu)先搜索函數(shù)。而且在深度優(yōu)先搜索函數(shù)中必須設(shè)一標(biāo)志數(shù)組以標(biāo)記結(jié)點(diǎn)是否被訪問。 具體過程應(yīng)為：先訪問初始點(diǎn)Vi，并標(biāo)志其已被訪問。此時(shí)定義一指向邊結(jié)點(diǎn)的指針p，并建立一個(gè)while（）循環(huán)，以指針?biāo)笇?duì)象不為空為控制條件，當(dāng)Vi的鄰接點(diǎn)未被訪問時(shí)，遞歸調(diào)用深度優(yōu)先遍歷函數(shù)訪問之。然后將p指針指向下一個(gè)邊結(jié)點(diǎn)。這樣就可以完成圖的深度優(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;in;i++) visited[i]=FALSE; for(i=0;in;i++) if(!visited[i]) DFSM(G,i); } 3.2.2 圖的廣度優(yōu)先遍歷 廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程。假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪問了v之后訪問它們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)的鄰接點(diǎn)”被訪問，直到圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時(shí)圖中尙有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程是以v為起始點(diǎn)，由近及遠(yuǎn)，依次訪問和v有路徑相通且路徑長度為1，2，……的頂點(diǎn)。 所以要實(shí)現(xiàn)算法必須先建立一個(gè)元素類型為整形的空隊(duì)列，并定義隊(duì)首與隊(duì)尾指針，同時(shí)也要定義一個(gè)標(biāo)志數(shù)組以標(biāo)記結(jié)點(diǎn)是否被訪問。同樣，也是從初始點(diǎn)出發(fā)開始訪問，訪問初始點(diǎn)，標(biāo)志其已被訪問，并將其入隊(duì)。當(dāng)隊(duì)列非空時(shí)進(jìn)行循環(huán)處理。當(dāng)結(jié)點(diǎn)被訪問時(shí)對(duì)其進(jìn)行標(biāo)志，并入隊(duì)列。通過while（）循環(huán)，并以是否被訪問為控制條件，訪問所有結(jié)點(diǎn)，完成圖的廣度優(yōu)先遍歷。 void BFS(ALGraph *G,int k) { int i,f=0,r=0; EdgeNode *p; int cq[MaxVertexNum]; for(i=0;in;i++) visited[i]=FALSE; for(i=0;i<=G->n;i++) cq[i]=-1; printf("%c ",G->adjlist[k].vertex); visited[k]=TRUE; cq[r]=k; while(cq[f]!=-1) { i=cq[f]; f=f+1; p=G->adjlist[i].firstedge; while(p) { if(!visited[p->adjvex]) { printf("%c ",G->adjlist[p->adjvex].vertex); visited[p->adjvex]=TRUE; r=r+1; cq[r]=p->adjvex; } p=p->next; } } } 第四章 測試分析 4.1 測試程序執(zhí)行情況 第五章 用戶手冊（可選） 5.1 使用說明 5.2 運(yùn)行說明 第六章 課程設(shè)計(jì)總結(jié) 轉(zhuǎn)眼，為期兩周的《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)實(shí)習(xí)即將結(jié)束了。在這次實(shí)習(xí)中，自己的C語言知識(shí)和數(shù)據(jù)結(jié)構(gòu)知識(shí)得到了鞏固，編程能力也有了一定的提高。同時(shí)也學(xué)會(huì)了解決問題的方法?？偨Y(jié)起來，自己主要有以下幾點(diǎn)體會(huì)： 1.必須牢固掌握基礎(chǔ)知識(shí)。由于C語言是大一所學(xué)知識(shí)，有所遺忘，且未掌握好這學(xué)期所學(xué)的《數(shù)據(jù)結(jié)構(gòu)》這門課，所以在實(shí)習(xí)之初感到棘手。不知如何下手，但在后來的實(shí)習(xí)過程中自己通過看書和課外資料，并請教其他同學(xué)，慢慢地對(duì)C語言和數(shù)據(jù)結(jié)構(gòu)知識(shí)有所熟悉。這時(shí)才逐漸有了思路。所以，這次實(shí)習(xí)之后，我告誡自己：今后一定要牢固掌握好專業(yè)基礎(chǔ)知識(shí)。 2.必須培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度。自己在編程時(shí)經(jīng)常因?yàn)橐恍╊愃朴凇吧倭朔痔?hào)”的小錯(cuò)誤而導(dǎo)致錯(cuò)誤，不夠認(rèn)真細(xì)致，這給自己帶來了許多麻煩。編程是一件十分嚴(yán)謹(jǐn)?shù)氖虑?，容不得馬虎。所以在今后自己一定要培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度。我想這不僅是對(duì)于程序設(shè)計(jì)，做任何事都應(yīng)如此。 3.這次課程設(shè)計(jì)也讓我充分認(rèn)識(shí)到《數(shù)據(jù)結(jié)構(gòu)》這門課的重要性。它給我們一個(gè)思想和大綱，讓我們在編程時(shí)容易找到思路，不至于無章可循。同時(shí)它也有廣泛的實(shí)際應(yīng)用。 總之，在這次實(shí)習(xí)中，自己的C語言以及數(shù)據(jù)結(jié)構(gòu)知識(shí)得到提高，編程能力也得到了提高。 附錄：程序代碼 #include"stdio.h" #include"stdlib.h" #define MaxVertexNum 50 typedef struct node{ int adjvex; struct node *next; }EdgeNode; typedef struct vnode{ char vertex; EdgeNode *firstedge; }VertexNode; typedef VertexNode AdjList[MaxVertexNum]; typedef struct { AdjList adjlist; int n,e; } ALGraph; void CreatALGraph(ALGraph *G) { int i,j,k; char a; EdgeNode *s; printf("請輸入頂點(diǎn)數(shù)和邊數(shù): "); scanf("%d,%d",&G->n,&G->e); scanf("%c",&a); printf("請輸入頂點(diǎn)字符串:"); for(i=0;in;i++) { scanf("%c",&a); G->adjlist[i].vertex=a; G->adjlist[i].firstedge=NULL; } printf("輸入邊，創(chuàng)造鄰接表：\n"); for(k=0;ke;k++) { scanf("%d%d",&i,&j); s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=j; s->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=s; s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i; s->next=G->adjlist[j].firstedge; G->adjlist[j].firstedge=s; } } typedef enum{FALSE,TRUE} Boolean; Boolean visited[MaxVertexNum]; 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;in;i++) visited[i]=FALSE; for(i=0;in;i++) if(!visited[i]) DFSM(G,i); } void BFS(ALGraph *G,int k) { int i,f=0,r=0; EdgeNode *p; int cq[MaxVertexNum]; for(i=0;in;i++) visited[i]=FALSE; for(i=0;i<=G->n;i++) cq[i]=-1; printf("%c ",G->adjlist[k].vertex); visited[k]=TRUE; cq[r]=k; while(cq[f]!=-1) { i=cq[f]; f=f+1; p=G->adjlist[i].firstedge; while(p) { if(!visited[p->adjvex]) { printf("%c ",G->adjlist[p->adjvex].vertex); visited[p->adjvex]=TRUE; r=r+1; cq[r]=p->adjvex; } p=p->next; } } } int main() { int i; ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph)); CreatALGraph(G); printf("Print Graph DFS: "); DFS(G); printf("\n"); printf("Print Graph BFS: "); BFS(G,3); printf("\n"); } 參考文獻(xiàn) 1． 楊路明 C語言程序設(shè)計(jì)教程 北京郵電大學(xué)出版社 2． 徐孝凱 數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn) 清華大學(xué)出版社 3． 嚴(yán)蔚敏 吳偉民 數(shù)據(jù)結(jié)構(gòu)（C語言版） 清華大學(xué)出版社 致謝