課程設計報告模板張苗.doc

《課程設計報告模板張苗.doc》由會員分享，可在線閱讀，更多相關《課程設計報告模板張苗.doc（19頁珍藏版）》請在裝配圖網上搜索。

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