課程設(shè)計報告模板張苗.doc

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

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