第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告
揚州大學(xué)信息工程學(xué)院
《數(shù)據(jù)結(jié)構(gòu)》
---課程設(shè)計報告
題目： 校園導(dǎo)游咨詢
班級： 學(xué)號： 姓名 指導(dǎo)教師：
一、設(shè)計題目
設(shè)計一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。
二、需求分析
要求：
（1）設(shè)計你所在學(xué)校的校園平面圖，所含景點不少于10個，以圖中頂點表示校內(nèi)各景點，存放景點名稱，代號，簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。
（2）為來訪客人提供圖中任意景點相關(guān)信息的查詢。
（3）為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短的簡單路徑。實現(xiàn)提示：
一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個無向網(wǎng)。頂點和邊均含有相關(guān)信息。
三、概要設(shè)計
1．創(chuàng)建校園圖：
（1）先定義節(jié)點個數(shù)N，邊的最大值（MAXedg），節(jié)點（景點名稱、景點信息），鄰接點，邊，頂點向量，當(dāng)前頂點數(shù)和邊數(shù)。
（2）先給一個節(jié)點賦上其相關(guān)信息，然后再用p =(Node)malloc(sizeof(edgenode))語句申請下一結(jié)點，再給所申請的節(jié)點賦上相關(guān)信息，直到節(jié)點數(shù)為N=10為止。
（3）讀入道路的起始點，為鄰接矩陣的邊賦相應(yīng)的值。
（4）節(jié)點和邊的相關(guān)信息都弄好了后，校園圖也就創(chuàng)建好了。
2．利用函數(shù)Name給10個節(jié)點賦上相應(yīng)的名稱，利用函數(shù)Information給各節(jié)點添加相應(yīng)的介紹信息。
3．利用函數(shù)travgraph來查找景點信息，要查找景點名稱時調(diào)用Name函數(shù)，要查找景點介紹信息時調(diào)用Information函數(shù)。
4．手動創(chuàng)建一個校園圖creat(Matrix_Graph *G)，然后為相應(yīng)的邊賦上真正的值。
5．用path函數(shù)來求任意兩景點之間的最短路徑。
6．用main函數(shù)來輸出結(jié)果：用switch語句分別輸出，要創(chuàng)建校園圖時調(diào)用creatgraph函數(shù)；查找景點相關(guān)信息時調(diào)用travgraph函數(shù)；要查找任意兩景點之間的最短路徑時，先輸入你目前所在的位置，再輸入你的目的地，最后調(diào)用path函數(shù)。
四、詳細設(shè)計
typedef int AdjMatrix[MAX][MAX];typedef struct { int vexs[MAX];AdjMatrix arcs;}Matrix_Graph;//圖的矩陣表示法。typedef struct edgenode { int adjvex;//臨接點序號
int length;//道路長度
char info[10];//景點名稱
char info2[100];//景點詳細信息
struct edgenode *next;}edgenode, *Node;typedef struct { char name[10];//存儲景點的名稱.char information[100];//具體的介紹此景點
struct edgenode *link;//指向下一個景點 }vexnode;//景點及其信息.typedef struct Edge { int lengh;//邊的權(quán)值，表示路徑長度.int ivex, jvex;//邊的兩端頂點號
struct Edge *next;//指向下一條邊 } EdgeType;//邊及其信息.typedef struct { int num;//頂點編號。
char name[10];//頂點名稱 } vertex;
typedef struct { vertex vexs[MAX];//頂點集合int edges[MAX][MAX];//臨街矩陣 }adjmax;//adj
（1）首先創(chuàng)建一個校園圖并用鄰接矩陣存儲，程序會自動調(diào)用creatgraph(g,&n,e,&adj)，函數(shù)進入到創(chuàng)建校園圖界面，用循環(huán)語句來完成：
for(i = 1;i <= b;i++){
fscanf(fp,“%d %d %dn”,&e[i].lengh,&e[i].ivex,&e[i].jvex);//讀入道路長度和起始點
s = e[i].ivex;//s是起點，d是終點。
d = e[i].jvex;
len = e[i].lengh;
adj->edges[s][d] = e[i].lengh;//為鄰接矩陣中相應(yīng)的邊賦值
adj->edges[d][s] = e[i].lengh;
p =(Node)malloc(sizeof(edgenode));//申請一個弧節(jié)點。
p->next = NULL;
q =(Node)malloc(sizeof(edgenode));
q->next = NULL;
p->adjvex = d;// 弧p指向的定點
p->length = len;
strcpy(p->info,g[d].name);//為景點賦名稱
strcpy(p->info2,g[d].information);//為景點賦介紹信息
q->adjvex = s;// 弧q指向的定點
q->length = len;
strcpy(q->info,g[s].name);//為景點賦名稱
strcpy(q->info2,g[s].information);//為景點賦介紹信息
p->next = g[s].link;//頭插法建立鄰接表
g[s].link = p;
q->next = g[d].link;
g[d].link = q;}
（2）調(diào)用Name(i)和information(i)完成對校園景點的名稱和信息的介紹。
（3）當(dāng)游客選擇了要查找景點的信息的介紹這一項功能的時候，程序就會調(diào)用travgraph(g,n,adj);函數(shù)進入到查找景點的介紹的界面，當(dāng)游客輸入了需要查找的景點的名稱的時候，程序利用循環(huán)語句：
do{
printf(“是否繼續(xù)? Y/N”);
scanf(“%c”,&ch);
getchar();
if(ch == 'Y' || ch == 'y')//繼續(xù)
{
flag = 1;
i = 1;
printf(“請輸入您要查詢的景點序號:n”);
scanf(“%d”,&len);
getchar();
printf(“此景點的名稱是:”);
Name(len);
printf(“此景點的介紹是:”);
Information(len);
continue;
}
else
flag = 0;//不繼續(xù)
break;}while(1);
（4）手動給校園圖賦上相關(guān)信息（景點名稱、代號、簡介），路徑及路徑長度。得到一個模擬的校園圖：
（5）當(dāng)游客選擇了要查找兩個景點之間的最短距離這一項功能的時候，程序就會調(diào)用path(&G,i,j)；函數(shù)進入到查找兩個景點之間的最短距離的操作界面當(dāng)中，當(dāng)游客輸入了兩個景點的名稱過后，程序會調(diào)用creat(&G);函數(shù)給校園圖賦上相關(guān)信息（景點名稱、代號、簡介），路徑及路徑長度，然后調(diào)用path(&G,i,j);函數(shù)進入到查找最短路徑問題的程序當(dāng)中。for(i=0;i<=N;i++)
for(j=0;j<=N;j++)r[i][j]=0;//初始值為0。
for(i=1;i<=N;i++)
{
T[i]=-1;//初始值為-1。
flag[i]=1;//初始值為1。
d[i]=MAX;//路徑長度初始值為無窮大，用MAX表示。
}
flag[s]=0;//修改標(biāo)識。
while(c<=N)
{
t=MAX;
for(i=1;i<=N;i++)
if(flag[i]&&G->arcs[s][i] { t=G->arcs[s][i];v=i;r[v][1]=v;} for(i=1;i<=c;i++) for(j=1;j<=N;j++) if(flag[j]&&d[i]+G->arcs[T[i]][j] { t=d[i]+G->arcs[T[i]][j];v=j; if(r[v][0]!=-1) { u=1; while(r[T[i]][u]!=0) { r[v][u]=r[T[i]][u];u++;} } r[v][u]=v; } r[v][0]=-1; T[c]=v; flag[v]=0; d[c]=t; c++; } printf(“nThe path is:n(%d)”,s); j=1; while(r[e][j]!=0) { printf(“-->(%d)”,r[e][j]);j++;}//顯示路徑。 （6）主函數(shù)是一個程序的主體，當(dāng)我們要進行我們所需要的操作的時候我們就要根據(jù)主函數(shù)中的顯示信息和它給我們的相關(guān)的提示信息來進行所需要的操作。 五、測試數(shù)據(jù)及運行結(jié)果 1.運行結(jié)果界面： 2．由于我編寫創(chuàng)建校園圖的程序時，不會編寫打開一個文本的程序，所以創(chuàng)建校園圖的運行結(jié)果顯示的是“打開文本錯誤”。 3．查找景點相關(guān)信息的結(jié)果： 4．查找最短路徑的結(jié)果： 六、源程序 #define N 10 #define MAX 20 //圖中頂點數(shù)的最大值 #define MAXedg 30 //圖中邊數(shù)的最大值 #include int length;//道路長度 char info[10];//景點名稱 char info2[100];//景點詳細信息 struct edgenode *next;}edgenode, *Node;typedef struct { char name[10];//存儲景點的名稱.char information[100];//具體的介紹此景點 struct edgenode *link;//指向下一個景點 }vexnode;//景點及其信息.typedef struct Edge { int lengh;//邊的權(quán)值，表示路徑長度.int ivex, jvex;//邊的兩端頂點號 struct Edge *next;//指向下一條邊 } EdgeType;//邊及其信息.typedef struct { int num;//頂點編號。 char name[10];//頂點名稱 } vertex; typedef struct { vertex vexs[MAX];//頂點集合int edges[MAX][MAX];//臨街矩陣 }adjmax;//adj FILE *fp;//文件的讀取 void clrscr()//清屏 { system(“cls”);} void creatgraph(vexnode g[],int *n, EdgeType e[],adjmax *adj)//創(chuàng)建校園圖 { int b,i,s,d,len;struct edgenode *p,*q;//定義圖的結(jié)構(gòu)體 if((fp = fopen(“file.txt”,“r”))== NULL)//打開文件 { printf(“文件打開錯誤！n”); getchar(); exit(0);} fscanf(fp,“%d %dn”,n,&b);//讀入景點個數(shù)和邊數(shù) for(i = 1;i <= *n;i++)//讀入景點名稱和詳細介紹信息 { fscanf(fp,“%s %sn”,&g[i].name,&g[i].information); strcpy(adj->vexs[i].name,g[i].name); g[i].link = NULL;//初始化 } for(i = 1;i <= b;i++){ fscanf(fp,“%d %d %dn”,&e[i].lengh,&e[i].ivex,&e[i].jvex);//讀入道路長度和起始點 s = e[i].ivex;//s是起點，d是終點。 d = e[i].jvex; len = e[i].lengh; adj->edges[s][d] = e[i].lengh;//為鄰接矩陣中相應(yīng)的邊賦值 adj->edges[d][s] = e[i].lengh; p =(Node)malloc(sizeof(edgenode));//申請一個弧節(jié)點。 p->next = NULL; q =(Node)malloc(sizeof(edgenode)); q->next = NULL; p->adjvex = d;// 弧p指向的定點 p->length = len; strcpy(p->info,g[d].name);//為景點賦名稱 strcpy(p->info2,g[d].information);//為景點賦介紹信息 q->adjvex = s;// 弧q指向的定點 q->length = len; strcpy(q->info,g[s].name);//為景點賦名稱 strcpy(q->info2,g[s].information);//為景點賦介紹信息 p->next = g[s].link;//頭插法建立鄰接表 g[s].link = p; q->next = g[d].link; g[d].link = q;} printf(“校園旅游圖已經(jīng)建立！n”);getchar();} void Name(int i){ switch(i){ case 1: printf(“1:學(xué)校正門nn”);break;case 2: printf(“2:教學(xué)樓區(qū)nn”);break;case 3: printf(“3:圖書館nn”);break;case 4: printf(“4:社團辦公室nn”);break;case 5: printf(“5:宿舍區(qū)nn”);break;case 6: printf(“6:食堂nn”);break;case 7: printf(“7:校園商業(yè)區(qū)nn”);break;case 8: printf(“8:大操場nn”);break;case 9: printf(“9:校醫(yī)院nn”);break;case 10: printf(“10: 大學(xué)活動中心nn”);break;default: printf(“景點編號輸入錯誤！請輸入1->10的數(shù)字編號！nn”);break;} } /*Name*/ void Information(int i){/*景點介紹*/ switch(i){ case 1: printf(“學(xué)校正門:正門旁邊是一條寬敞的馬路，交通方便；進門后直對面就是兩棟高大的主樓，氣勢宏偉。nn”);break;case 2: printf(“教學(xué)樓區(qū): 教學(xué)樓眾多且形狀各異，教室大小不一，適宜各種人數(shù)班級使用。nn”);break;case 3: printf(“圖書館: 學(xué)校信息資源中心，外表呈三角形，宏偉壯觀，藏有大量各種書刊，設(shè)有電子查閱室和自習(xí)室，是學(xué)生學(xué)習(xí)的好地方。nn”);break;case 4: printf(“社團辦公室:是學(xué)校各個學(xué)生組織開會，策劃活動的辦公處。nn”);break;case 5: printf(“宿舍區(qū): 有八個公寓，是大部分學(xué)生的住所。nn”);break;case 6: printf(“食堂: 位于教學(xué)樓與宿舍區(qū)之間，里面有各個地方的小吃，味道不錯，是學(xué)生就餐的主要餐廳。nn”);break;case 7: printf(“校園商業(yè)區(qū):里面有書店、打印和復(fù)印的地方、教育超市、水果超市，為學(xué)生們提供了方便。nn”);break;case 8: printf(“大操場:有足球場，籃球場，是學(xué)生和老師體育鍛煉的主要地方。nn”);break;case 9: printf(“校醫(yī)院: 設(shè)備不太齊全，只能治療一些常見的小病，但是價格很便宜。nnn”);break;case 10: printf(“大學(xué)活動中心:里面還可以舉行各項文藝活動。nn”);break;default: printf(“景點編號輸入錯誤！請輸入1->10的數(shù)字編號！nn”);break;} }/*Information*/ void travgraph(vexnode g[],int n,adjmax adj)//查找指定景點信息 { int i = 1,flag = 1,len;//len存儲要查詢的景點的序號 char ch;printf(“請輸入您要查詢的景點序號:n”);scanf(“%d”,&len);getchar();printf(“此景點的名稱是:”);Name(len);printf(“此景點的介紹是:”);Information(len);do{ printf(“是否繼續(xù)? Y/N”); scanf(“%c”,&ch); getchar(); if(ch == 'Y' || ch == 'y')//繼續(xù) { flag = 1; i = 1; printf(“請輸入您要查詢的景點序號:n”); scanf(“%d”,&len); getchar(); printf(“此景點的名稱是:”); Name(len); printf(“此景點的介紹是:”); Information(len); continue; } else flag = 0;//不繼續(xù) break;}while(1);} void creat(Matrix_Graph *G){ int i,j;for(i=1;i<=N;i++)G->vexs[i]=i;//初始化，0號位不用。 for(i=1;i<=N;i++) for(j=1;j<=N;j++)G->arcs[i][j]=0;//初始值為0。 G->arcs[1][2]=2;G->arcs[1][9]=5;//表示景點一到景點二的距離是2。 G->arcs[2][1]=2;G->arcs[2][3]=5;G->arcs[2][4]=4;G->arcs[2][9]=6;G->arcs[3][2]=5;G->arcs[3][4]=7;G->arcs[3][7]=5;G->arcs[3][9]=6;G->arcs[3][10]=6; G->arcs[4][2]=4;G->arcs[4][6]=7;G->arcs[4][10]=7; G->arcs[5][6]=4;G->arcs[5][7]=6;G->arcs[5][8]=8;G->arcs[6][4]=7;G->arcs[6][5]=4;G->arcs[6][7]=3;G->arcs[6][10]=7; G->arcs[7][6]=3;G->arcs[7][8]=4;G->arcs[7][10]=6; G->arcs[8][5]=8;G->arcs[8][7]=4;G->arcs[8][9]=9;G->arcs[9][1]=5;G->arcs[9][2]=6;G->arcs[9][3]=6;G->arcs[9][8]=9;G->arcs[10][3]=6;G->arcs[10][4]=7;G->arcs[10][6]=7;G->arcs[10][7]=6; for(i=1;i<=N;i++) for(j=1;j<=N;j++) if(G->arcs[i][j]==0)G->arcs[i][j]=MAX;//沒有被重新賦值的，表示兩景點之間 //沒有路，用MAX表示無窮大。} void path(Matrix_Graph *G,int s,int e){ int i,j,u,c=1,t,v;int r[N+1][N+1];//用來存放路徑上的景點。 int T[N],flag[N],d[N];for(i=0;i<=N;i++) for(j=0;j<=N;j++)r[i][j]=0;//初始值為0。 for(i=1;i<=N;i++) { T[i]=-1;//初始值為-1。 flag[i]=1;//初始值為1。 d[i]=MAX;//路徑長度初始值為無窮大，用MAX表示。 } flag[s]=0;//修改標(biāo)識。 while(c<=N) { t=MAX; for(i=1;i<=N;i++) if(flag[i]&&G->arcs[s][i] { t=G->arcs[s][i];v=i;r[v][1]=v;} for(i=1;i<=c;i++) for(j=1;j<=N;j++) if(flag[j]&&d[i]+G->arcs[T[i]][j] { t=d[i]+G->arcs[T[i]][j];v=j; if(r[v][0]!=-1) { u=1; while(r[T[i]][u]!=0) { r[v][u]=r[T[i]][u];u++;} } r[v][u]=v; } r[v][0]=-1; T[c]=v; flag[v]=0; d[c]=t; c++; } printf(“nThe path is:n(%d)”,s); j=1; while(r[e][j]!=0) { printf(“-->(%d)”,r[e][j]);j++;}//顯示路徑。 printf(“nn”);} void main()//主函數(shù) { int i,j;Matrix_Graph G;creat(&G);int n = 0;//景點數(shù)目 vexnode g[MAX];//保存頂點及其信息 EdgeType e[MAXedg];//保存邊及其信息 adjmax adj;//保存邊和定點 char choice = 'x';while(1){ clrscr(); printf(“nnttt***校園導(dǎo)游系統(tǒng)***”);printf(“ntt*************************************nn”); printf(“ttt1.文件讀入并創(chuàng)建校園圖:nn”); printf(“ttt2.查詢景點詳細信息:nn”); printf(“ttt3.查找兩景點間最短路徑:nn”); printf(“ttt0.退出nn”); printf(“tttt2013/06/29”);printf(“ntt************************************nn”); printf(“Please enter your choice(0-3):n ”); choice = getchar(); switch(choice) { case '1': clrscr(); creatgraph(g,&n,e,&adj);//創(chuàng)建圖(景點，景點數(shù)，邊，邊和景點) printf(“n打開文件錯誤n”); getchar(); break; case '2': clrscr(); travgraph(g,n,adj);//查詢景點信息 getchar(); break; case '3': clrscr(); printf(“2你目前的位置是：n”); scanf(“%d”,&i); getchar(); printf(“2你的目的地是：n”); scanf(“%d”,&j); getchar(); } path(&G,i,j);//查找最短路徑 getchar(); creat(&G); do{ printf(“是否繼續(xù)? Y/N”); char ch; int flag=1; scanf(“%c”,&ch); getchar(); if(ch == 'Y' || ch == 'y')//繼續(xù) { flag = 1; i = 1; printf(“2你目前的位置是：n”); scanf(“%d”,&i); getchar(); printf(“2你的目的地是：n”); scanf(“%d”,&j); getchar(); path(&G,i,j);//查找最短路徑 getchar(); creat(&G); continue; } else flag = 0;//不繼續(xù) break; }while(1); break;case '0': clrscr(); printf(“n*******按任意鍵退出********n”); getchar(); exit(0); break;default: printf(“n輸入錯誤,請重新輸入0-3之間的數(shù)字:n”); getchar(); break;} } getchar(); 計算機科學(xué)與工程系 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 課程設(shè)計題目 迷宮 航班信息查詢系統(tǒng) 學(xué) 號 姓 名 班 級 專 業(yè) 網(wǎng)絡(luò)工程 完 成 時 間 2013-1-4 指 導(dǎo) 教 師 數(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ī)定：當(dāng)位置（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)，在利用順序棧時，沒有定義順序棧的向量空間大小，導(dǎo)致程序出錯。但不要對向量空間定義過大，否則會浪費空間。 （2）算法的時空分析： 由于鏈棧實際上是運算受限制的單鏈表。所以取棧頂元素運算的算法、置空棧運算的算法執(zhí)行時間與問題的規(guī)模無關(guān)，則該算法的時間復(fù)雜度為O(1)；而其入棧運算的算法與出棧運算的算法相當(dāng)于在鏈表的表尾進行插入和刪除操作，不需要移動元素，時間復(fù)雜度也為O（1）。建立迷宮矩陣的時間復(fù)雜度為O（x*y）。在查找路徑的過程中，最壞的情況下可能要考察每一個非障礙的位置。因此，查找路徑的時間復(fù)雜度應(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è)計過程中由于掌握的知識不牢固，在編程序的過程中得到了同學(xué)的幫助和指導(dǎo)，在此表示感謝。課程設(shè)計的過程中，遇到了一些問題，大部分是課本中的知識掌握的不牢固，還有就是在以前學(xué)習(xí)C++的過程中相關(guān)的知識掌握的不夠全面。在以后的學(xué)習(xí)過程中，自己一定要把各種知識掌握牢固。 { } 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 訪問過的標(biāo)記為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;放入堆棧 /標(biāo)志入口已訪問 &stack->col==NULL))&&(!(stack->row==x2&&stack->col==y2)))//循環(huán)條件直到找到輸入的出口 { mg[stack->row][stack->col]=1;//將 訪問過的標(biāo)記為1 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 迷宮 void tonglu()//將坐標(biāo)的頂點輸出 { 始化 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è)過程中，遇到問題時，通過與同學(xué)、老師交流，在圖書館查閱資料，使問題得以解決。 （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)實復(fù)雜問題的分析建模和解決方法（包括問題描述、系統(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大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：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大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：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大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：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大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：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)二者之間的選擇，在同學(xué)和參考書的幫助下終于得到解決。 3、關(guān)于偽隨機和再哈希的相關(guān)內(nèi)容覺得很難懂，看了很久參考書才有所了解 六測試結(jié)果 1、根據(jù)姓名查找 1)姓名查找成功 2)姓名查找失敗 xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 5 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 3)哈希表 xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 6 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 2、根據(jù)電話號碼查找 1)電話號碼輸入錯誤 xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 7 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 2)電話號碼查詢成功 3)電話號碼查詢失敗 xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 8 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 4)哈希表 xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 9 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 七用戶使用說明 1、選擇數(shù)據(jù)來源 根據(jù)提示信息進行操作，選擇已存在的“old.txt”文件中的數(shù)據(jù)或系統(tǒng)當(dāng)前自動生成的“new.txt”文件。 xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 10 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 2、選擇查找方式 根據(jù)提示信息進行操作，選擇“根據(jù)姓名查找”或“根據(jù)電話號碼查找”兩種查找方式。 3、選擇功能 根據(jù)提示信息進行操作，選擇輸入已知信息或查看哈希表。 xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 11 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 4、顯示結(jié)果 xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 13 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 14 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 5、查看文件 xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 15 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 八課程設(shè)計總結(jié) 1、收獲 學(xué)會了C++的跟蹤。更進一步了解和熟悉了關(guān)于哈希表的運用和文件的讀取與寫入操作。同時鍛煉了對話形式的菜單的創(chuàng)建和熟練運用。 2、心得體會 在這次數(shù)據(jù)結(jié)構(gòu)設(shè)計中遇到了很多實際性的問題，在實際設(shè)計中才發(fā)現(xiàn)，書本上理論性的東西與在實際運用中的還是有一定的出入的，所以有些問題要不斷地更正以前的錯誤思維。通過這次設(shè)計，我懂得了學(xué)習(xí)的重要性，了解到理論知識與實踐相結(jié)合的重要意義，xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：xxxxxxx姓名：jenery6 16 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計 學(xué)會了堅持、耐心和努力，這將為自己今后的學(xué)習(xí)和工作做出了最好的榜樣。我覺得作為一名計科專業(yè)的學(xué)生，這次課程設(shè)計是很有意義的。更重要的是如何把自己平時所學(xué)的東西應(yīng)用到實際中。雖然自己對于這門課懂的并不多，很多基礎(chǔ)的東西都還沒有很好的掌握，覺得很難，也沒有很有效的辦法通過自身去理解，但是靠著學(xué)習(xí)，漸漸對這門課逐漸產(chǎn)生了些許的興趣，自己開始主動學(xué)習(xí)并逐步從基礎(chǔ)慢慢開始弄懂它。 xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：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;//當(dāng)前數(shù)據(jù)元素個數(shù) int sizeindex;//哈希表的長度 char *sign;//沖突的標(biāo)志 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大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：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è)置沖突標(biāo)志 } xxxx大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：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大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：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大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：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大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：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大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：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大學(xué)xxxx學(xué)院xxxx專業(yè)學(xué)號：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è)計報告
第三篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告