課程設(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為尾的?。Ｃ總€結(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;in;i++) visited[i]=FALSE; for(i=0;in;i++) if(!visited[i]) DFSM(G,i); } 3.2.2 圖的廣度優(yōu)先遍歷 廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程。假設(shè)從圖中某頂點v出發(fā)，在訪問了v之后訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點的鄰接點”被訪問，直到圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尙有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直到圖中所有頂點都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程是以v為起始點，由近及遠，依次訪問和v有路徑相通且路徑長度為1，2，……的頂點。 所以要實現(xiàn)算法必須先建立一個元素類型為整形的空隊列，并定義隊首與隊尾指針，同時也要定義一個標志數(shù)組以標記結(jié)點是否被訪問。同樣，也是從初始點出發(fā)開始訪問，訪問初始點，標志其已被訪問，并將其入隊。當隊列非空時進行循環(huán)處理。當結(jié)點被訪問時對其進行標志，并入隊列。通過while（）循環(huán)，并以是否被訪問為控制條件，訪問所有結(jié)點，完成圖的廣度優(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 運行說明 第六章 課程設(shè)計總結(jié) 轉(zhuǎn)眼，為期兩周的《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計實習即將結(jié)束了。在這次實習中，自己的C語言知識和數(shù)據(jù)結(jié)構(gòu)知識得到了鞏固，編程能力也有了一定的提高。同時也學會了解決問題的方法?？偨Y(jié)起來，自己主要有以下幾點體會： 1.必須牢固掌握基礎(chǔ)知識。由于C語言是大一所學知識，有所遺忘，且未掌握好這學期所學的《數(shù)據(jù)結(jié)構(gòu)》這門課，所以在實習之初感到棘手。不知如何下手，但在后來的實習過程中自己通過看書和課外資料，并請教其他同學，慢慢地對C語言和數(shù)據(jù)結(jié)構(gòu)知識有所熟悉。這時才逐漸有了思路。所以，這次實習之后，我告誡自己：今后一定要牢固掌握好專業(yè)基礎(chǔ)知識。 2.必須培養(yǎng)嚴謹?shù)目茖W態(tài)度。自己在編程時經(jīng)常因為一些類似于“少了分號”的小錯誤而導致錯誤，不夠認真細致，這給自己帶來了許多麻煩。編程是一件十分嚴謹?shù)氖虑?，容不得馬虎。所以在今后自己一定要培養(yǎng)嚴謹?shù)目茖W態(tài)度。我想這不僅是對于程序設(shè)計，做任何事都應如此。 3.這次課程設(shè)計也讓我充分認識到《數(shù)據(jù)結(jié)構(gòu)》這門課的重要性。它給我們一個思想和大綱，讓我們在編程時容易找到思路，不至于無章可循。同時它也有廣泛的實際應用。 總之，在這次實習中，自己的C語言以及數(shù)據(jù)結(jié)構(gòu)知識得到提高，編程能力也得到了提高。 附錄：程序代碼 #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("請輸入頂點數(shù)和邊數(shù): "); scanf("%d,%d",&G->n,&G->e); scanf("%c",&a); printf("請輸入頂點字符串:"); 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"); } 參考文獻 1． 楊路明 C語言程序設(shè)計教程 北京郵電大學出版社 2． 徐孝凱 數(shù)據(jù)結(jié)構(gòu)課程實驗 清華大學出版社 3． 嚴蔚敏 吳偉民 數(shù)據(jù)結(jié)構(gòu)（C語言版） 清華大學出版社 致謝