第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
青島理工大學
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
題目：宿舍管理查詢軟件
院（系）：計算機工程學院
學生姓名:謝茂盛
班級：網(wǎng)絡(luò)121學號: 201207131
起迄日期:2014.07.07-2014.07.20
指導教師:張艷
一、需求分析（所有大標題宋體加粗四號，下同）（小標題宋體加粗小四，下同）
1.問題描述：
以無歧義的陳述詳細說明對自己所選題目的解釋性描述，可以補充說明該設(shè)計中要做的具體任務(wù)。強調(diào)的是程序要做什么？
2.基本功能
要求分別列出該設(shè)計要實現(xiàn)的功能，（每個功能要盡量和概要設(shè)計中的模塊函數(shù)對應(yīng)起來）。
二、概要設(shè)計
1.設(shè)計思路：
解決問題的思路概述，擬采用的算法的簡介。
2.數(shù)據(jù)結(jié)構(gòu)設(shè)計：
要求分別列出擬采用的數(shù)據(jù)結(jié)構(gòu)及其定義，分為邏輯結(jié)構(gòu)（線性？樹狀？圖狀？）和存儲結(jié)構(gòu)（順序？鏈式？）。采用該結(jié)構(gòu)的原因，如果有定義的抽象數(shù)據(jù)類型，可以列出其定義及各種操作。如下為抽象數(shù)據(jù)類型定義的模板。
定義程序中用到的抽象數(shù)據(jù)類型；
設(shè)計中所用到的數(shù)據(jù)結(jié)構(gòu)或抽象數(shù)據(jù)類型的說明，以及在程序中的作用
抽象數(shù)據(jù)類型線性表的定義如下：
ADT List{
數(shù)據(jù)對象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0}
數(shù)據(jù)關(guān)系：R1={
基本操作：
Insert(&L,i,j)
初始條件：線性表L已存在，1≤i≤n+1。
操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素j,L的長度加1。
Del(&L,i,j)
初始條件：線性表L已存在，1≤i≤n。
操作結(jié)果：刪除L的第i個數(shù)據(jù)元素,L的長度減1
Xg(&L,i,j)
初始條件：線性表L已存在。
操作結(jié)果：用新的輸入數(shù)據(jù)項j代替原有的指定要修改的數(shù)據(jù)項i。
Search(&L,i,e)
初始條件：線性表L已存在。
操作結(jié)果：查找指定的某元素i，并將值賦給e,用e 輸出。
}
3.軟件結(jié)構(gòu)設(shè)計：
按需求分析中的功能進行模塊劃分，建立模塊的層次結(jié)構(gòu)及調(diào)用關(guān)系。
三、詳細設(shè)計
實現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型，對每個操作只需要寫出偽代碼算法；對主程序和其他模塊也都需要寫出偽代碼算法（偽代碼算法達到的詳細程度建議為：按照偽代碼算法可以在計算機鍵盤直接輸入高級程序設(shè)計語言程序）)；可采用流程圖、活動圖進行描述，畫
出函數(shù)和過程的調(diào)用關(guān)系圖。
實現(xiàn)設(shè)計中主程序和其他子模塊的算法，以流程圖的形式表示，需畫出函數(shù)和過程的調(diào)用關(guān)系圖。
本小節(jié)內(nèi)所有的圖均要求用Visio或Word進行繪制，不允許用bmp或其他格式的圖片。繪圖內(nèi)文字均采用宋體五號（如果圖比較大，排版不好看的話，可以根據(jù)需要縮小字體），單倍行間距，段前段后均設(shè)置為0行。
1.定義程序中所有用到的數(shù)據(jù)及其數(shù)據(jù)結(jié)構(gòu)，及其基本操作的實現(xiàn)；
2．主函數(shù)和其他函數(shù)的偽碼算法；
3.主要函數(shù)的程序流程圖，實現(xiàn)設(shè)計中主程序和其他子模塊的算法，以流程圖的形式表示。
4.畫出函數(shù)之間的調(diào)用關(guān)系圖。
四、調(diào)試分析
內(nèi)容包括：調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計與實現(xiàn)的回顧討論和分析。
1.實際完成的情況說明（完成的功能，支持的數(shù)據(jù)類型等）；
2.程序的性能分析，包括時空分析；
3.上機過程中出現(xiàn)的問題及其解決方案；
4.程序中可以改進的地方說明；
5.程序中可以擴充的功能及設(shè)計實現(xiàn)假想。
五、測試結(jié)果
列出你的測試結(jié)果，包括輸入和輸出。注意測試數(shù)據(jù)應(yīng)該完整和嚴格，至少給出2組測試結(jié)果（含合法數(shù)據(jù)與非法數(shù)據(jù)）。
六、用戶手冊
說明如何使用你編寫的程序，詳細列出每一步的具體操作步驟。這里可以有適當?shù)倪\行結(jié)果抓圖。用戶手冊與開發(fā)過程無關(guān)，只與使用有關(guān)，必須是Step by Step的。
所有運行結(jié)果截圖均要求有實際數(shù)據(jù)的內(nèi)容，截圖尺寸要求按頁寬排版兩張大小，且要求有每張圖下面有規(guī)范的標題說明如何使用你編寫的程序，詳細列出每一步的操作步驟。
七、體會與自我評價
寫出本設(shè)計的總結(jié)思考，收獲心得體會，要求不少于600字，不得摘抄網(wǎng)上資料，只能參考。
正文（各標題除外），均采用宋體和Times New Roman字體，小四號字，1.25倍行距。
八、參考文獻（列出你參考的書，格式按照下面的例子來寫）例如：
[1]嚴蔚敏．數(shù)據(jù)結(jié)構(gòu)(C語言)．清華大學出版社，2007
第二篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
計算機科學與工程系
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
課程設(shè)計題目 迷宮 航班信息查詢系統(tǒng) 學 號 姓 名 班 級
專 業(yè) 網(wǎng)絡(luò)工程 完 成 時 間 2013-1-4 指 導 教 師
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
迷宮
題目一
1.設(shè)計內(nèi)容 1.1問題描述
求迷宮從入口到出口的所有路徑。1.2設(shè)計要求
1．迷宮中不能使用遞歸算法查找路徑。2．試探方向限定為上、下、左、右四個方向。3．迷宮采用隨機生成和手工生成兩種方式。4．生成從迷宮入口到出口的最短和最長路徑。5．迷宮的入口和出口由鍵盤輸入。
1.3開發(fā)環(huán)境
Visual C++6.0的集成化環(huán)境 1.4研究思路
對這樣的矩形迷宮，可以用N*M的矩陣來描述，N和M分別代表迷宮的行數(shù)和列數(shù)。這樣，迷宮中的每一個位置都可以用行號和列號來指定。從入口到出口的路徑則是由一個位置構(gòu)成的，每個位置上都沒有障礙，且每個位置（第一個除外）都是前一個位置的東、南、西或北的鄰居。為了描述迷宮中位置（i,j）處有無障礙，規(guī)定：當位置（i,j）處有一個障礙時，其值為1，否則為0。
經(jīng)分析，一個簡單的求解方法是：從入口出發(fā)，沿某一方向進行探索，若能走通，則繼續(xù)向前走；否則沿原路返回，換一方向再進行搜索，直到所有可能的通路都探索到為止。即所謂的回溯法。
2.設(shè)計步驟
2.1 需求分析
（1）題目：迷宮的生成與路由。生成一個N*M（N行M列）的迷宮，0和
1-1數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
迷宮
在該程序中，首先進入的是菜單選擇，在菜單中有3種選擇，選1是手動輸入迷宮函數(shù)；選2是隨機自動生成迷宮；選3是退出程序。在手動生成迷宮時，有兩種輸出方式，一是矩陣輸出，二是圖形輸出。在矩陣輸出時，直接將數(shù)組中的數(shù)進行輸出，在圖形輸出時，則要判斷該點的情況，然后輸入迷宮的出入口，再調(diào)用mgpath（）函數(shù)進行判斷是否存在路徑，如果存在則將路徑經(jīng)過的點進行輸出，并且將經(jīng)過的點進入到輔助數(shù)組中（輔助數(shù)組是輔助圖形界面的輸出），并且將輔助數(shù)組初始為1，輔助數(shù)組中點為路徑的重新賦值為0，然后根據(jù)情況輸出圖形界面。在自動生成迷宮時，用到了c語言隨機函數(shù)，對于其它問題，和手動情況基本相同。
2.3 詳細設(shè)計（1）主菜單偽代碼：
while(flag1){
}
{shuru();//輸入行列數(shù)
printf(“手動建立迷宮矩陣(0表示可通1表示障礙):n”);for(i=1;i<=m;i++)
for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]);showplay(mg);// 迷宮輸出 churukou();//迷宮出入口的輸入 x=Mazepath(mg);// 判斷路徑函數(shù)
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
迷宮
和“class ‘maze’has an illegal zero-sized array”兩行錯誤。雙擊錯誤信息，找到出錯的程序段，經(jīng)過查閱資料發(fā)現(xiàn)，在利用順序棧時，沒有定義順序棧的向量空間大小，導致程序出錯。但不要對向量空間定義過大，否則會浪費空間。
（2）算法的時空分析：
由于鏈棧實際上是運算受限制的單鏈表。所以取棧頂元素運算的算法、置空棧運算的算法執(zhí)行時間與問題的規(guī)模無關(guān)，則該算法的時間復雜度為O(1)；而其入棧運算的算法與出棧運算的算法相當于在鏈表的表尾進行插入和刪除操作，不需要移動元素，時間復雜度也為O（1）。建立迷宮矩陣的時間復雜度為O（x*y）。在查找路徑的過程中，最壞的情況下可能要考察每一個非障礙的位置。因此，查找路徑的時間復雜度應(yīng)為O（unblocked）。
鏈棧的入棧算法、出棧算法、取棧頂元素算法、置空棧算法執(zhí)行時所需要的空間都是用于存儲算法本身所用的指令、常數(shù)、變量，各個算法的空間性能均較好。只是對于存放順序棧的向量空間大小的定義很難把握好，如果定義過大，會造成不必要的空間浪費。所以在定義時要慎重考慮。
3.用戶使用說明
運行該程序，運行的界面的會出現(xiàn)菜單界面，然后用戶可根據(jù)界面的提示進行相應(yīng)的操作，生成迷宮的方式有兩種方式，手動生成和自動生成，手動生成時、，用戶可根據(jù)自己的要求輸入迷宮的格式，還需輸入相應(yīng)的入出口，確認程序就會生成相應(yīng)的路徑圖形；自動生成只需輸入所需的行數(shù)和列數(shù)，就會生成迷宮，接下來的操作和手動操作相同了。
圖數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
迷宮
圖1-2
圖1-3 退出
5.總結(jié)與心得體會
本次課程設(shè)計過程中由于掌握的知識不牢固，在編程序的過程中得到了同學的幫助和指導，在此表示感謝。課程設(shè)計的過程中，遇到了一些問題，大部分是課本中的知識掌握的不牢固，還有就是在以前學習C++的過程中相關(guān)的知識掌握的不夠全面。在以后的學習過程中，自己一定要把各種知識掌握牢固。
{ }
mg[i][j]=1;//初始化
矩陣,將最外圍置為1
printf(“n輸入迷宮入口：n”);scanf(“%d%d”,&x1,&y1);printf(“輸入迷宮出口：n”);scanf(“%d%d”,&x2,&y2);
}mlink;mlink *stack;//定義一個棧 int m,n,x1,x2,y1,y2;//定義全局變量
}
void showplay(int mg[][M+2])//迷宮輸出
{
n“);
for(i=1;i<=m;i++){
printf(”n“);for(j=1;j<=n;j++)
printf(”%d “,mg[i][j]);
int i,j;
printf(”迷宮矩陣如下(0可通)：printf(“輸入行數(shù)：n”);scanf(“%d”,&m);printf(“輸入列數(shù)：n”);scanf(“%d”,&n);數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
迷宮
} } printf(“n迷宮圖形如下(白色for(i=1;i<=m;i++){
}
printf(”n“);for(j=1;j<=n;j++){
} if(mg[i][j]==0)printf(”
if(mg[i][j]==1)printf(“
if(mg[stack->row][stack->col+1]==
p->next=stack;
stack=p;{
p=(mlink 可通)：n”);0)//下面位置可通
*)malloc(sizeof(mlink));
p->row=stack->row;p->col=stack->col+1;□“);//為0的輸出□ ■”);//為1的輸出■
//入棧
mg[stack->row][stack->col]=1;//將
} else
訪問過的標記為1 int Mazepath(int mg[][N+2]){
mlink *p;if(mg[x1][y1]==0){ p=(mlink p->row=x1;p->col=y1;p->next=NULL;stack=p;
//將入口
mg[stack->row][stack->col]=1;/while((!(stack->row==NULL&
if(mg[stack->row][stack->col-1]==0)//上面可通
//入棧
stack=p;
p->next=stack;
{
p=(mlink *)malloc(sizeof(mlink));
*)malloc(sizeof(mlink));
p->row=stack->row;p->col=stack->col-1;放入堆棧 /標志入口已訪問
&stack->col==NULL))&&(!(stack->row==x2&&stack->col==y2)))//循環(huán)條件直到找到輸入的出口
{
mg[stack->row][stack->col]=1;//將
訪問過的標記為1
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
迷宮
void tonglu()//將坐標的頂點輸出 {
始化
printf(“(%d%3d)n”,q->row,q->col);
情況
else printf(“□”);//0的 } q=stack;{
} for(i=0;i for(j=0;j = while(q!=NULL)//循環(huán)條件 q=q->next;for(j=0;j 情況 } void create(int mg[][N+2])//創(chuàng)建和菜單 { int i,j,x,choice,flag1=1;chushi();while(flag1){ } printf(“n”);printf(“所有通道為（由下而q=stack;{ 上）：n”);while(q!=NULL)//循環(huán)條件 printf(“ ## printf(”# n“); *********選擇菜單********** #n”); printf(“ ## printf(”輸入選項：“);scanf(”%d“,&choice);switch(choice){ case 1://手動建立迷宮 { shuru(); printf(”手動建立for(i=1;i<=m;i++) n“); printf(”# 1-手動生成迷 宮 2-自動生成迷宮 3-退出 #n“);0;//將路徑中的點賦給輔助數(shù)組a 形的界面輸出 迷宮矩陣(0表示可通1表示障礙):n”); for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]); 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 航班信息查詢與檢索系統(tǒng) 題目二 1.設(shè)計內(nèi)容 1.1問題描述 設(shè)計一個航班信息查詢系統(tǒng)，提供信息的管理和使用功能，管理包括更新、添加、刪除功能。 1.2設(shè)計要求 （1）原始信息存儲在文件中，記錄不少于50條。（2）用戶界面至少包括以下功能： ? 創(chuàng)建 ? 修改（插入、添加、刪除、更新）? 查詢 ? 瀏覽 ? 退出管理系統(tǒng)（3）航班信息包括： ? 航班號：字符序列，具體字符表達的意思上網(wǎng)查詢 ? 起點站和終點站：字符串 ? 班期：指一周中哪些天有航班 ? 起飛時間：可將時間定義成一個時、分組成的序列 ? 到達時間：可將時間定義成一個時、分組成的序列 ? 機型：字符序列，具體字符表達的意思上網(wǎng)查詢 ? 票價：整型數(shù)，具體值可上網(wǎng)查詢 （4）創(chuàng)建是指從文件中讀取數(shù)據(jù)，并存入所定義的順序表中。 （5）可按航班號、起點站、終點站、起飛時間、到達時間等進行查詢。查詢時要用到順序查找、二分查找方法。輸出查詢結(jié)果時必須排序。 （6）可按航班號、起點站、起飛時間、票價進行刪除和更新操作，刪除的記錄存入另外的文件中，作為日志文件保存。 （7）作插入操作前，先對信息按起點站進行排序。新記錄插入為起點站相同的最后一條記錄。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 航班信息查詢與檢索系統(tǒng) typedef struct node { Time rh;Time lv;}Pnode;（2）飛機結(jié)構(gòu)體： struct Plane { };（3）靜態(tài)鏈表： typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price;}Sqlist;2.3 詳細設(shè)計（1）主函數(shù)： do{printf(“* * * * * * * * * * * * * 航班查詢系統(tǒng)* * * * * * * * * * * * *n”); printf(“* 1.創(chuàng)建 2.修改 3.查詢 4.瀏覽 5.表長 6.文件 0.退出 *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *n”); scanf(“%d”,&opt);switch(opt){ case 1:Initlist(L);break; case 2:handle(L);break; case 3:search(L);break; case 4:print(L);break;case 5:Get_Sq(L);break;case 6:File(L);break; 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 航班信息查詢與檢索系統(tǒng) } }while(opt!=0);} （4）文件操作： void File(Sqlist &L){ int ch;do{ printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”); printf(“* *n”); printf(“* 1.保存信息到文件 2.從文件讀取信息 0 退出 *n”); printf(“* *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * *n”); printf(“請輸入選項n”); scanf(“%d”,&ch); switch(ch) { case 1:SaveList(L);break; } }while(ch!=0);case 2:ReadList(L);break; case 0:printf(“退出！n”);break;} （5）瀏覽信息：就是循環(huán)使用輸出函數(shù)，在此就不必多說了 2.4 調(diào)試分析 （1）在課設(shè)過程中，遇到問題時，通過與同學、老師交流，在圖書館查閱資料，使問題得以解決。 （2）算法中有許多不是很優(yōu)化的地方。3.用戶使用說明 程序運行后用戶根據(jù)提示輸入要進行的操作選項（應(yīng)先選擇創(chuàng)建選項，這樣可以直接讀取保存好的文件），然后選擇要進行的操作選項。由于主菜單中有修改、查詢和瀏覽項目，每個項目又有各自的子菜單，所以在進行管理和使用時要注意輸入的元素是否正確，需按照提示輸入。輸入操作元素時，元素之間以空格隔開。程序?qū)摧斎氲牟僮髟卣业较鄳?yīng)的算法，然后進行處理，然后將結(jié)果打 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 航班信息查詢與檢索系統(tǒng) 圖2-2 查詢信息 圖2-3插入 圖2-4刪除 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 航班信息查詢與檢索系統(tǒng) 時就需要重新寫出一個子函數(shù)，哪怕這個子函數(shù)就是在原有的一個子函數(shù)的基礎(chǔ)上改那么一丁點的地方，例如航班信息查詢系統(tǒng)中的查詢函數(shù)，其實每個子函數(shù)只是改了一下關(guān)鍵碼而已。 6.附錄 #include { } void search_key(Sqlist L)//按航班號查找 { 號：“); Time rh;Time lv; scanf(”%s“,n);int i; printf(”此航班的航班號，起點char n[20]; printf(“請輸入要查找的航班 printf(”%dn“,L.length);//表長 }Time;typedef struct node { }Pnode;struct Plane { };typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price; 終點，班期，起飛時間，到達時間，票價：n”); if(strcmp(L.plane[i].key,n)==0) ted，L.plane[i].sche,L.plane[i].lv.hour,L.{ for(i=L.length-1;i>=0;i--){ printf(“%s %s %s %d:%d % d:%d %dn”,L.plane[i].key,L.plane[i].s}Sqlist;int get_Sq(Sqlist &L){ } void Get_Sq(Sqlist &L)return L.length; plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane [i].price); 0數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 航班信息查詢與檢索系統(tǒng) printf(“此航班的航班號，起點 ted，{ 終點，班期，起飛時間，到達時間，票價：n”); if(L.plane[i].lv.hour<=hour) ted，L.plane[i].sche,L.plane[i].lv.hour,L.{ for(i=L.length-1;i>=0;i--){ printf(“%s %s %s %d:%d % d:%d %dn”,L.plane[i].key,L.plane[i].s L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane } void search(Sqlist L){ int i;do { printf(“* * * * * * * * * * * } } printf(”%s %s %s %d:%d %d:%d %dn“,L.plane[i].key,L.plane[i].s[i].price);plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane } void search_rh(Sqlist L){ int hour;printf(”請輸入你所要求的最scanf(“%d”,&hour);printf(“此航班的航班號，起點 } } [i].price); * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”); printf(“* 1.航班號查詢 2.起點終點查詢 3.班期查詢 4.起飛時間查詢 5.到達時間查詢 0.退出 *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”); scanf(“%d”,&i); switch(i) { case 晚時間：“);終點，班期，起飛時間，到達時間，票價：n”); if(L.plane[i].rh.hour<=hour)for(int i=L.length-1;i>=0;i--){ 1:search_key(L);break; 2數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 航班信息查詢與檢索系統(tǒng) n“); } else { } printf(”查找不成功。 i--;if(i==0) { char c[20]; printf(“輸入修改后的scanf(”%s“,c); 內(nèi)容：”); strcpy(L.plane[i].sche,c); printf(“修改成功！n”);}break;{ int a,b; printf(“輸入修改后的int opt;printf(”選擇修改對象：“);scanf(”%d“,&opt);switch(opt){ case 1: printf(”修改成功！n“);printf(”修改成功！n“);{ char a[10];printf(”輸入修改后的scanf(“%s”,a); case 4: 內(nèi)容：“); char b[20];printf(”請輸入修改后scanf(“%s”,b); scanf(“%d:%d”,&a,&b); L.plane[i].lv.hour=a;L.plane[i].lv.min=b;printf(“修改成功！n”);航班號：“); }break;{ int a,b; printf(”輸入修改后的strcpy(L.plane[i].key,a);}break;{ case 5: case 2: 內(nèi)容：“); scanf(”%d:%d“,&a,&b); L.plane[i].rh.hour=a;L.plane[i].rh.min=b;printf(”修改成功！n“);的內(nèi)容：”);strcpy(L.plane[i].sted,b);}break; }break;{ int a; case 6: case 3: 4數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 航班信息查詢與檢索系統(tǒng) *n“); printf(”* * * * * * * * * * * * * * * * * * * * * * * * *n“); printf(”請輸入選項n“); scanf(”%d“,&ch); switch(ch) { case 1:SaveList(L);break;case 2:ReadList(L);break; L.plane[i].sche,&L.plane[i].lv.hour，&L.plane[i].lv.min,&L.plane [i].rh.hour,&L.plane[i].rh.min,&L.pl } void delet_Sq1(Sqlist &L){ char n[10];int i,j; printf(”請輸入您要刪除的航scanf(“%s”,n);if(L.length==0){ printf(“沒有選項！n”);for(i=0;i L.length++; ane[i].price); case 0:printf(“退出！n”);break; } void Initlist(Sqlist &L)//插入存儲 { “); 容：”);價n“); scanf(”%s%s%s%d:%d%d:%d%d“,L.plane[i].key,L.plane[i].sted, for(i=0;i 班期 起飛時間 到達時間 票scanf(”%d“,&n);L.length=0;L.plane=(Plane if(!L.plane)exit(0);printf(”請輸入順序表中的內(nèi) int i,n;printf(“輸入表中航班的數(shù)量： } }while(ch!=0); 班號：”); if(strcmp(L.plane[i].key,n)==0) { printf(“所刪除的班機*)malloc((n+10000)*sizeof(Plane));的信息：n”); printf(“n航班號 起點終點 printf(”%s %s %s %d:%d %d:% d %dn“,L.plane[i].key,L.plane[i].sted，L.plane[i].sche,L.plane[i].lv.hour,L.plane[i].lv.min,L.plane [i].rh.hour,L.plane[i].rh.min,L.plane [i].price); 6數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 航班信息查詢與檢索系統(tǒng) n”);} printf(“無法打開文件！} }while(opt!=0); void insert_Sq(Sqlist &L){ 數(shù)量 價n”); for(i=0;i printf(“* * * * * * * * * * * scanf(”%s%s%s%d:%d%d:%d%d“,&L.plane[L.length].key,&L.plane[L.length].sted，&L.plane[L.length].sche,&L.plane[ { int a=get_Sq(L); printf(”請輸入要添加班機的scanf(“%d”,&n); printf(“請輸入要添加的班機printf(”n航班號 起點終點 int i,n; //n表示添加的fprintf(fp,“航班號：%sn起點站：%s 終點站：%sn班期：%dn起飛時間：%d:%d 到達時間：%d:%dn價格：%dnn”, p.key,p.sted,p.sche,p.lv.hour,p.lv.mi n“);} void delet_Sq(Sqlist &L){ int opt;do { fclose(fp);printf(”保存刪除的信息成功。n,p.rh.hour,p.rh.min,p.price); 數(shù)量：“); 信息：n”); 班期 起飛時間 到達時間 票* * * * * * * * * *n“); printf(”* 1.航班號刪除 printf(“* * * * * * * * * * printf(”輸入你的選擇：“);2.路線刪除 0.退出 *n”);* * * * * * * * * * *n“); scanf(”%d“,&opt); switch(opt){ case 1:delet_Sq1(L);break; case 2:delet_Sq2(L);break; case 0:printf(”退出。} L.length].lv.hour,&L.plane[L.length].lv.min，&L.plane[L.length].rh.hour,&L.plan e[L.length].rh.min,&L.plane[L.length].price); } void handle(Sqlist &L){ } L.length++; n");break; 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 哈希表實現(xiàn)電話號碼查詢系統(tǒng)一目的 利用《數(shù)據(jù)結(jié)構(gòu)》課程的相關(guān)知識完成一個具有一定難度的綜合設(shè)計題目，利用C/C++語言進行程序設(shè)計，并規(guī)范地完成課程設(shè)計報告。通過課程設(shè)計，鞏固和加深對線性表、棧、隊列、字符串、樹、圖、查找、排序等理論知識的理解；掌握現(xiàn)實復雜問題的分析建模和解決方法（包括問題描述、系統(tǒng)分析、設(shè)計建模、代碼實現(xiàn)、結(jié)果分析等）；提高利用計算機分析解決綜合性實際問題的基本能力。 二需求分析 1、程序的功能 1)讀取數(shù)據(jù) ① 讀取原電話本存儲的電話信息。 ② 讀取系統(tǒng)隨機新建電話本存儲的電話信息。2)查找信息 ① 根據(jù)電話號碼查詢用戶信息。② 根據(jù)姓名查詢用戶信息。3)存儲信息 查詢無記錄的結(jié)果存入記錄文檔。 2、輸出形式 1)數(shù)據(jù)文件“old.txt”存放原始電話號碼數(shù)據(jù)。 2)數(shù)據(jù)文件“new.txt”存放有系統(tǒng)隨機生成的電話號碼文件。3)數(shù)據(jù)文件“out.txt”存放未查找到的電話信息。4)查找到相關(guān)信息時顯示姓名、地址、電話號碼。 3、初步測試計劃 1)從數(shù)據(jù)文件“old.txt”中讀入各項記錄，或由系統(tǒng)隨機產(chǎn)生各記錄，并且把記錄保存到“new.txt”中。 2)分別采用偽隨機探測再散列法和再哈希法解決沖突。3)根據(jù)姓名查找時顯示給定姓名用戶的記錄。4)根據(jù)電話號碼查找時顯示給定電話號碼的用戶記錄。 xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 1 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 5)將沒有查找的結(jié)果保存到結(jié)果文件Out.txt中。 6)系統(tǒng)以菜單界面工作，運行界面友好，演示程序以用戶和計算機的對話方式進行。 三概要設(shè)計 1、子函數(shù)功能 int Collision_Random(int key,int i)//偽隨機數(shù)探量觀測再散列法處理沖突 void Init_HashTable_by_name(string name,string phone,string address)//以姓名為關(guān)鍵字建立哈希表 int Collision_Rehash(int key,string str)//再哈希法處理沖突 void Init_HashTable_by_phone(string name,string phone,string address)//以電話號碼為關(guān)鍵字建立哈希表 void Outfile(string name,int key)//在沒有找到時輸出未找到的記錄，打開文件out.txt并將記錄儲存在文檔中 void Outhash(int key)//輸出哈希表中的記錄 void Rafile()//隨機生成數(shù)據(jù)，并將數(shù)據(jù)保存在new.txt void Init_HashTable(char*fname,int n)//建立哈希表 int Search_by_name(string name)//根據(jù)姓名查找哈希表中的記錄 int Search_by_phone(string phone)//根據(jù)電話號碼查找哈希表中的記錄 xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 2 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 2、函數(shù)調(diào)用圖 main()Refile()init-hashtable()init-hashtable-by-name()init-hashtable-by-phone()Seach-by-name()Seach-by-phone()Coiiision-random()Collision-rehash()Outhash()xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 3 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 四詳細設(shè)計 1、主函數(shù)流程圖 開始選擇數(shù)據(jù)來源21建“new.txt”選擇查找方式12姓名查找電話號碼查找12021輸入姓名顯示哈希表0顯示哈希表輸入電話號碼無此記錄顯示信息無此記錄顯示信息0寫入“out.txt”寫入“out.txt”結(jié)束 2、“偽隨機探測再散列處理沖突”偽代碼 若對應(yīng)位置上已經(jīng)存在其他數(shù)據(jù)，則新的關(guān)鍵字=（原關(guān)鍵字+偽隨機數(shù)）%哈希表長。若新的位置上也存在其他數(shù)據(jù)，則用偽隨機序列的下一個數(shù)求新的關(guān)鍵字，直到找到合適的位置。 3、“再哈希法處理沖突”偽代碼 用“折疊法”將電話號碼的ASCII碼值定義為關(guān)鍵字，分別為前四位、中四位、后三位。 再用“除留余數(shù)法”求的新的關(guān)鍵字=原關(guān)鍵字%哈希表長。 xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 4、“以姓名為關(guān)鍵字建立哈希表”偽代碼 用“除留余數(shù)法”將姓名的ASCII碼值定義為關(guān)鍵字。 若對應(yīng)位置上存在其他數(shù)據(jù)，則調(diào)用偽隨機處理沖突，然后將數(shù)據(jù)存入哈希表。 5、“以電話號碼為關(guān)鍵字建立哈希表”偽代碼 用“除留余數(shù)法”將電話號碼的ASCII碼值定義為關(guān)鍵字。若對應(yīng)位置上存在其他數(shù)據(jù)，則調(diào)用再哈希處理沖突。然后將數(shù)據(jù)存入哈希表。 五調(diào)試分析 1、程序的關(guān)鍵是掌握文件的相關(guān)操作、哈希函數(shù)的創(chuàng)建和運用、偽隨機法處理沖突、再哈希法處理沖突等。在編程的過程中，出現(xiàn)了很多問題，如文件無法正常打開、程序進入死循環(huán)、無法實現(xiàn)文件的寫入操作、忘了添加頭文件等錯誤。修改后程序運行正確。 2、創(chuàng)建“new.txt”內(nèi)容用子函數(shù)來實現(xiàn)，但是原數(shù)據(jù)是從“old.txt”文件中讀取的，剛開始不知道怎樣實現(xiàn)二者之間的選擇，在同學和參考書的幫助下終于得到解決。 3、關(guān)于偽隨機和再哈希的相關(guān)內(nèi)容覺得很難懂，看了很久參考書才有所了解 六測試結(jié)果 1、根據(jù)姓名查找 1)姓名查找成功 2)姓名查找失敗 xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 5 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 3)哈希表 xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 6 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 2、根據(jù)電話號碼查找 1)電話號碼輸入錯誤 xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 7 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 2)電話號碼查詢成功 3)電話號碼查詢失敗 xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 8 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 4)哈希表 xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 9 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 七用戶使用說明 1、選擇數(shù)據(jù)來源 根據(jù)提示信息進行操作，選擇已存在的“old.txt”文件中的數(shù)據(jù)或系統(tǒng)當前自動生成的“new.txt”文件。 xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 10 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 2、選擇查找方式 根據(jù)提示信息進行操作，選擇“根據(jù)姓名查找”或“根據(jù)電話號碼查找”兩種查找方式。 3、選擇功能 根據(jù)提示信息進行操作，選擇輸入已知信息或查看哈希表。 xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 11 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 4、顯示結(jié)果 xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 13 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 14 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 5、查看文件 xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 15 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 八課程設(shè)計總結(jié) 1、收獲 學會了C++的跟蹤。更進一步了解和熟悉了關(guān)于哈希表的運用和文件的讀取與寫入操作。同時鍛煉了對話形式的菜單的創(chuàng)建和熟練運用。 2、心得體會 在這次數(shù)據(jù)結(jié)構(gòu)設(shè)計中遇到了很多實際性的問題，在實際設(shè)計中才發(fā)現(xiàn)，書本上理論性的東西與在實際運用中的還是有一定的出入的，所以有些問題要不斷地更正以前的錯誤思維。通過這次設(shè)計，我懂得了學習的重要性，了解到理論知識與實踐相結(jié)合的重要意義，xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 16 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 學會了堅持、耐心和努力，這將為自己今后的學習和工作做出了最好的榜樣。我覺得作為一名計科專業(yè)的學生，這次課程設(shè)計是很有意義的。更重要的是如何把自己平時所學的東西應(yīng)用到實際中。雖然自己對于這門課懂的并不多，很多基礎(chǔ)的東西都還沒有很好的掌握，覺得很難，也沒有很有效的辦法通過自身去理解，但是靠著學習，漸漸對這門課逐漸產(chǎn)生了些許的興趣，自己開始主動學習并逐步從基礎(chǔ)慢慢開始弄懂它。 xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 附錄：源程序 #include using namespace std; ifstream in_file;ofstream out_file; int D[10]={1,3,5,8,13,15,17,21,27,34};//偽隨機數(shù)序列 int count;//當前數(shù)據(jù)元素個數(shù) int sizeindex;//哈希表的長度 char *sign;//沖突的標志 struct Data { string name;string phone;string address;};Data *intermediate_data; int Collision_Random(int key,int i)//偽隨機數(shù)探量觀測再散列法處理沖突{ int Re_key;if(sign[key]=='1'){ xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 18 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 } Re_key=(key+D[i])%sizeindex;return Re_key;//歸回新的要害碼 return-1;} void Init_HashTable_by_name(string name,string phone,string address)//以姓名為關(guān)鍵字建立哈希表 { int i=0;int key;char*p;for(key=0,p=&name[0];*p;p++)key=key+*p;key=key%42;while(sign[key]=='1'){ } if(key==-1)exit(1);key=Collision_Random(key,i+1);count++;intermediate_data[key].name=name;//將數(shù)據(jù)存入哈希表 intermediate_data[key].address=address;intermediate_data[key].phone=phone;sign[key]='1';//設(shè)置沖突標志 } xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 19 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 int Collision_Rehash(int key,string str)//再哈希法處理沖突 { int Re_key;int num1=(str[0]-'0')*1000+(str[1]-'0')*100+(str[2]-'0')*10+(str[3]-'0');int num2=(str[4]-'0')*1000+(str[5]-'0')*100+(str[6]-'0')*10+(str[7]-'0');int num3=(str[8]-'0')*100+(str[9]-'0')*10+(str[10]-'0');Re_key=num1+num2+num3;Re_key=(Re_key+key)%sizeindex;return Re_key;} void Init_HashTable_by_phone(string name,string phone,string address)//以電話號碼為關(guān)鍵字建立哈希表 { int key;char*p;for(key=0,p=&phone[0];*p;p++)key=key+*p;key=key%42;while(sign[key]=='1'){ } count++;intermediate_data[key].name=name;intermediate_data[key].address=address;intermediate_data[key].phone=phone;key=Collision_Rehash(key,phone);xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 20 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 sign[key]='1';} void Outfile(string name,int key)//在沒有找到時輸出未找到的記錄，打開文件out.txt并將記錄儲存在文檔中 { if((key==-1)||(sign[key]=='0')){ out_file.open(“out.txt”); if(out_file.fail()) { cout<<“n”<<“文件打開失?。?n”< exit(1); } out_file< out_file.close();} } void Outhash(int key)//輸出哈希表中的記錄 { unsigned i;if((key==-1)||(sign[key]=='0')){ cout<<“n”<<“無此記錄！!n”< } else xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 21 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 { for(i=0;i cout< for(i=0;i<8;i++) cout<<“ ”; cout< for(i=0;i<8;i++) cout<<“ ”; cout< void Rafile()//隨機生成數(shù)據(jù)，并將數(shù)據(jù)保存在new.txt { int i,j;out_file.open(“new.txt”);if(out_file.fail()){ cout<<“n”<<“文件打開失??！!n”< exit(1);} for(j=0;j<30;j++){ string name=“"; for(i=0;i<20;i++) name+=rand()%26+'a';out_file< 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 string phone=”“; for(i=0;i<11;i++) phone+=rand()%10+'0'; out_file< string address=”“; for(i=0;i<29;i++) address+=rand()%26+'a'; address+=','; out_file< void Init_HashTable(char*fname,int n)//建立哈希表{ string name=”“;string phone=”“;string address=”“;int i,j;in_file.open(fname);if(in_file.fail()){ cout<<”n“<<”文件打開失??！!n“< exit(1);} while(!in_file.eof()){ xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 23 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 字 鍵字 } char* str=new char[100];name=”“;phone=”“;address=”“;in_file.getline(str,100,'n');//按行讀入數(shù)據(jù) if(str[0]=='*')//判斷數(shù)據(jù)結(jié)束 i=0;while(str[i]<=97||str[i]>=122)i++;break;for(;str[i]!=' ';i++)name+=str[i];while(str[i]==' ')i++;for(j=0;str[i]!=' ';j++,i++)phone+=str[i];while(str[i]==' ')i++;for(j=0;str[i]!=',';j++,i++)address+=str[i];if(n==1)Init_HashTable_by_name(name,phone,address);//以姓名為關(guān)鍵else Init_HashTable_by_phone(name,phone,address);//以電話號碼為關(guān)delete str;in_file.close();} xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 int Search_by_name(string name)//根據(jù)姓名查找哈希表中的記錄 { int i=0;int j=1;int key;char*p;for(key=0,p=&name[0];*p;p++)key=key+*p;key=key%42;while(sign[key]=='1'&&(intermediate_data[key].name!=name)){ key=Collision_Random(key,i+1); j++; if(j=count) return-1;} return key;} int Search_by_phone(string phone)//根據(jù)電話號碼查找哈希表中的記錄{ int key;char*p;for(key=0,p=&phone[0];*p;p++)key=key+*p;key=key%42;int j=1;xxxx大學xxxx學院xxxx專業(yè)學號：xxxxxxx姓名：jenery6 25 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 while(sign[key]=='1'&&(intermediate_data[key].phone!=phone)){ key=Collision_Rehash(key,phone); j++; if(j=count) return-1;} return key;} void main(){ count=0;sizeindex=50;int i,k;int ch;char *Fname; sign=new char[sizeindex]; intermediate_data=new Data[sizeindex]; for(i=0;i第三篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告