第一篇：數據結構課程設計報告
揚州大學信息工程學院
《數據結構》
---課程設計報告
題目： 校園導游咨詢
班級： 學號： 姓名 指導教師：
一、設計題目
設計一個校園導游程序，為來訪的客人提供各種信息查詢服務。
二、需求分析
要求：
（1）設計你所在學校的校園平面圖，所含景點不少于10個，以圖中頂點表示校內各景點，存放景點名稱，代號，簡介等信息；以邊表示路徑，存放路徑長度等相關信息。
（2）為來訪客人提供圖中任意景點相關信息的查詢。
（3）為來訪客人提供圖中任意景點的問路查詢，即查詢任意兩個景點之間的一條最短的簡單路徑。實現提示：
一般情況下，校園的道路是雙向通行的，可設校園平面圖是一個無向網。頂點和邊均含有相關信息。
三、概要設計
1．創建校園圖：
（1）先定義節點個數N，邊的最大值（MAXedg），節點（景點名稱、景點信息），鄰接點，邊，頂點向量，當前頂點數和邊數。
（2）先給一個節點賦上其相關信息，然后再用p =(Node)malloc(sizeof(edgenode))語句申請下一結點，再給所申請的節點賦上相關信息，直到節點數為N=10為止。
（3）讀入道路的起始點，為鄰接矩陣的邊賦相應的值。
（4）節點和邊的相關信息都弄好了后，校園圖也就創建好了。
2．利用函數Name給10個節點賦上相應的名稱，利用函數Information給各節點添加相應的介紹信息。
3．利用函數travgraph來查找景點信息，要查找景點名稱時調用Name函數，要查找景點介紹信息時調用Information函數。
4．手動創建一個校園圖creat(Matrix_Graph *G)，然后為相應的邊賦上真正的值。
5．用path函數來求任意兩景點之間的最短路徑。
6．用main函數來輸出結果：用switch語句分別輸出，要創建校園圖時調用creatgraph函數；查找景點相關信息時調用travgraph函數；要查找任意兩景點之間的最短路徑時，先輸入你目前所在的位置，再輸入你的目的地，最后調用path函數。
四、詳細設計
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;//邊的權值，表示路徑長度.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）首先創建一個校園圖并用鄰接矩陣存儲，程序會自動調用creatgraph(g,&n,e,&adj)，函數進入到創建校園圖界面，用循環語句來完成：
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;//為鄰接矩陣中相應的邊賦值
adj->edges[d][s] = e[i].lengh;
p =(Node)malloc(sizeof(edgenode));//申請一個弧節點。
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）調用Name(i)和information(i)完成對校園景點的名稱和信息的介紹。
（3）當游客選擇了要查找景點的信息的介紹這一項功能的時候，程序就會調用travgraph(g,n,adj);函數進入到查找景點的介紹的界面，當游客輸入了需要查找的景點的名稱的時候，程序利用循環語句：
do{
printf(“是否繼續? Y/N”);
scanf(“%c”,&ch);
getchar();
if(ch == 'Y' || ch == 'y')//繼續
{
flag = 1;
i = 1;
printf(“請輸入您要查詢的景點序號:n”);
scanf(“%d”,&len);
getchar();
printf(“此景點的名稱是:”);
Name(len);
printf(“此景點的介紹是:”);
Information(len);
continue;
}
else
flag = 0;//不繼續
break;}while(1);
（4）手動給校園圖賦上相關信息（景點名稱、代號、簡介），路徑及路徑長度。得到一個模擬的校園圖：
（5）當游客選擇了要查找兩個景點之間的最短距離這一項功能的時候，程序就會調用path(&G,i,j)；函數進入到查找兩個景點之間的最短距離的操作界面當中，當游客輸入了兩個景點的名稱過后，程序會調用creat(&G);函數給校園圖賦上相關信息（景點名稱、代號、簡介），路徑及路徑長度，然后調用path(&G,i,j);函數進入到查找最短路徑問題的程序當中。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;//修改標識。
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）主函數是一個程序的主體，當我們要進行我們所需要的操作的時候我們就要根據主函數中的顯示信息和它給我們的相關的提示信息來進行所需要的操作。 五、測試數據及運行結果 1.運行結果界面： 2．由于我編寫創建校園圖的程序時，不會編寫打開一個文本的程序，所以創建校園圖的運行結果顯示的是“打開文本錯誤”。 3．查找景點相關信息的結果： 4．查找最短路徑的結果： 六、源程序 #define N 10 #define MAX 20 //圖中頂點數的最大值 #define MAXedg 30 //圖中邊數的最大值 #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;//邊的權值，表示路徑長度.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)//創建校園圖 { int b,i,s,d,len;struct edgenode *p,*q;//定義圖的結構體 if((fp = fopen(“file.txt”,“r”))== NULL)//打開文件 { printf(“文件打開錯誤！n”); getchar(); exit(0);} fscanf(fp,“%d %dn”,n,&b);//讀入景點個數和邊數 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;//為鄰接矩陣中相應的邊賦值 adj->edges[d][s] = e[i].lengh; p =(Node)malloc(sizeof(edgenode));//申請一個弧節點。 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(“校園旅游圖已經建立！n”);getchar();} void Name(int i){ switch(i){ case 1: printf(“1:學校正門nn”);break;case 2: printf(“2:教學樓區nn”);break;case 3: printf(“3:圖書館nn”);break;case 4: printf(“4:社團辦公室nn”);break;case 5: printf(“5:宿舍區nn”);break;case 6: printf(“6:食堂nn”);break;case 7: printf(“7:校園商業區nn”);break;case 8: printf(“8:大操場nn”);break;case 9: printf(“9:校醫院nn”);break;case 10: printf(“10: 大學活動中心nn”);break;default: printf(“景點編號輸入錯誤！請輸入1->10的數字編號！nn”);break;} } /*Name*/ void Information(int i){/*景點介紹*/ switch(i){ case 1: printf(“學校正門:正門旁邊是一條寬敞的馬路，交通方便；進門后直對面就是兩棟高大的主樓，氣勢宏偉。nn”);break;case 2: printf(“教學樓區: 教學樓眾多且形狀各異，教室大小不一，適宜各種人數班級使用。nn”);break;case 3: printf(“圖書館: 學校信息資源中心，外表呈三角形，宏偉壯觀，藏有大量各種書刊，設有電子查閱室和自習室，是學生學習的好地方。nn”);break;case 4: printf(“社團辦公室:是學校各個學生組織開會，策劃活動的辦公處。nn”);break;case 5: printf(“宿舍區: 有八個公寓，是大部分學生的住所。nn”);break;case 6: printf(“食堂: 位于教學樓與宿舍區之間，里面有各個地方的小吃，味道不錯，是學生就餐的主要餐廳。nn”);break;case 7: printf(“校園商業區:里面有書店、打印和復印的地方、教育超市、水果超市，為學生們提供了方便。nn”);break;case 8: printf(“大操場:有足球場，籃球場，是學生和老師體育鍛煉的主要地方。nn”);break;case 9: printf(“校醫院: 設備不太齊全，只能治療一些常見的小病，但是價格很便宜。nnn”);break;case 10: printf(“大學活動中心:里面還可以舉行各項文藝活動。nn”);break;default: printf(“景點編號輸入錯誤！請輸入1->10的數字編號！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(“是否繼續? Y/N”); scanf(“%c”,&ch); getchar(); if(ch == 'Y' || ch == 'y')//繼續 { flag = 1; i = 1; printf(“請輸入您要查詢的景點序號:n”); scanf(“%d”,&len); getchar(); printf(“此景點的名稱是:”); Name(len); printf(“此景點的介紹是:”); Information(len); continue; } else flag = 0;//不繼續 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;//修改標識。 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()//主函數 { int i,j;Matrix_Graph G;creat(&G);int n = 0;//景點數目 vexnode g[MAX];//保存頂點及其信息 EdgeType e[MAXedg];//保存邊及其信息 adjmax adj;//保存邊和定點 char choice = 'x';while(1){ clrscr(); printf(“nnttt***校園導游系統***”);printf(“ntt*************************************nn”); printf(“ttt1.文件讀入并創建校園圖: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);//創建圖(景點，景點數，邊，邊和景點) 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(“是否繼續? Y/N”); char ch; int flag=1; scanf(“%c”,&ch); getchar(); if(ch == 'Y' || ch == 'y')//繼續 { 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;//不繼續 break; }while(1); break;case '0': clrscr(); printf(“n*******按任意鍵退出********n”); getchar(); exit(0); break;default: printf(“n輸入錯誤,請重新輸入0-3之間的數字:n”); getchar(); break;} } getchar(); 計算機科學與工程系 數據結構課程設計報告 課程設計題目 迷宮 航班信息查詢系統 學 號 姓 名 班 級 專 業 網絡工程 完 成 時 間 2013-1-4 指 導 教 師 數據結構課程設計 迷宮 題目一 1.設計內容 1.1問題描述 求迷宮從入口到出口的所有路徑。1.2設計要求 1．迷宮中不能使用遞歸算法查找路徑。2．試探方向限定為上、下、左、右四個方向。3．迷宮采用隨機生成和手工生成兩種方式。4．生成從迷宮入口到出口的最短和最長路徑。5．迷宮的入口和出口由鍵盤輸入。 1.3開發環境 Visual C++6.0的集成化環境 1.4研究思路 對這樣的矩形迷宮，可以用N*M的矩陣來描述，N和M分別代表迷宮的行數和列數。這樣，迷宮中的每一個位置都可以用行號和列號來指定。從入口到出口的路徑則是由一個位置構成的，每個位置上都沒有障礙，且每個位置（第一個除外）都是前一個位置的東、南、西或北的鄰居。為了描述迷宮中位置（i,j）處有無障礙，規定：當位置（i,j）處有一個障礙時，其值為1，否則為0。 經分析，一個簡單的求解方法是：從入口出發，沿某一方向進行探索，若能走通，則繼續向前走；否則沿原路返回，換一方向再進行搜索，直到所有可能的通路都探索到為止。即所謂的回溯法。 2.設計步驟 2.1 需求分析 （1）題目：迷宮的生成與路由。生成一個N*M（N行M列）的迷宮，0和 1-1數據結構課程設計 迷宮 在該程序中，首先進入的是菜單選擇，在菜單中有3種選擇，選1是手動輸入迷宮函數；選2是隨機自動生成迷宮；選3是退出程序。在手動生成迷宮時，有兩種輸出方式，一是矩陣輸出，二是圖形輸出。在矩陣輸出時，直接將數組中的數進行輸出，在圖形輸出時，則要判斷該點的情況，然后輸入迷宮的出入口，再調用mgpath（）函數進行判斷是否存在路徑，如果存在則將路徑經過的點進行輸出，并且將經過的點進入到輔助數組中（輔助數組是輔助圖形界面的輸出），并且將輔助數組初始為1，輔助數組中點為路徑的重新賦值為0，然后根據情況輸出圖形界面。在自動生成迷宮時，用到了c語言隨機函數，對于其它問題，和手動情況基本相同。 2.3 詳細設計（1）主菜單偽代碼： while(flag1){ } {shuru();//輸入行列數 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);// 判斷路徑函數 數據結構課程設計 迷宮 和“class ‘maze’has an illegal zero-sized array”兩行錯誤。雙擊錯誤信息，找到出錯的程序段，經過查閱資料發現，在利用順序棧時，沒有定義順序棧的向量空間大小，導致程序出錯。但不要對向量空間定義過大，否則會浪費空間。 （2）算法的時空分析： 由于鏈棧實際上是運算受限制的單鏈表。所以取棧頂元素運算的算法、置空棧運算的算法執行時間與問題的規模無關，則該算法的時間復雜度為O(1)；而其入棧運算的算法與出棧運算的算法相當于在鏈表的表尾進行插入和刪除操作，不需要移動元素，時間復雜度也為O（1）。建立迷宮矩陣的時間復雜度為O（x*y）。在查找路徑的過程中，最壞的情況下可能要考察每一個非障礙的位置。因此，查找路徑的時間復雜度應為O（unblocked）。 鏈棧的入棧算法、出棧算法、取棧頂元素算法、置空棧算法執行時所需要的空間都是用于存儲算法本身所用的指令、常數、變量，各個算法的空間性能均較好。只是對于存放順序棧的向量空間大小的定義很難把握好，如果定義過大，會造成不必要的空間浪費。所以在定義時要慎重考慮。 3.用戶使用說明 運行該程序，運行的界面的會出現菜單界面，然后用戶可根據界面的提示進行相應的操作，生成迷宮的方式有兩種方式，手動生成和自動生成，手動生成時、，用戶可根據自己的要求輸入迷宮的格式，還需輸入相應的入出口，確認程序就會生成相應的路徑圖形；自動生成只需輸入所需的行數和列數，就會生成迷宮，接下來的操作和手動操作相同了。 圖數據結構課程設計 迷宮 圖1-2 圖1-3 退出 5.總結與心得體會 本次課程設計過程中由于掌握的知識不牢固，在編程序的過程中得到了同學的幫助和指導，在此表示感謝。課程設計的過程中，遇到了一些問題，大部分是課本中的知識掌握的不牢固，還有就是在以前學習C++的過程中相關的知識掌握的不夠全面。在以后的學習過程中，自己一定要把各種知識掌握牢固。 { } 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(“輸入行數：n”);scanf(“%d”,&m);printf(“輸入列數：n”);scanf(“%d”,&n);數據結構課程設計 迷宮 } } 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)))//循環條件直到找到輸入的出口 { mg[stack->row][stack->col]=1;//將 訪問過的標記為1 數據結構課程設計 迷宮 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)//循環條件 q=q->next;for(j=0;j 情況 } void create(int mg[][N+2])//創建和菜單 { int i,j,x,choice,flag1=1;chushi();while(flag1){ } printf(“n”);printf(“所有通道為（由下而q=stack;{ 上）：n”);while(q!=NULL)//循環條件 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;//將路徑中的點賦給輔助數組a 形的界面輸出 迷宮矩陣(0表示可通1表示障礙):n”); for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]); 數據結構課程設計 航班信息查詢與檢索系統 題目二 1.設計內容 1.1問題描述 設計一個航班信息查詢系統，提供信息的管理和使用功能，管理包括更新、添加、刪除功能。 1.2設計要求 （1）原始信息存儲在文件中，記錄不少于50條。（2）用戶界面至少包括以下功能： ? 創建 ? 修改（插入、添加、刪除、更新）? 查詢 ? 瀏覽 ? 退出管理系統（3）航班信息包括： ? 航班號：字符序列，具體字符表達的意思上網查詢 ? 起點站和終點站：字符串 ? 班期：指一周中哪些天有航班 ? 起飛時間：可將時間定義成一個時、分組成的序列 ? 到達時間：可將時間定義成一個時、分組成的序列 ? 機型：字符序列，具體字符表達的意思上網查詢 ? 票價：整型數，具體值可上網查詢 （4）創建是指從文件中讀取數據，并存入所定義的順序表中。 （5）可按航班號、起點站、終點站、起飛時間、到達時間等進行查詢。查詢時要用到順序查找、二分查找方法。輸出查詢結果時必須排序。 （6）可按航班號、起點站、起飛時間、票價進行刪除和更新操作，刪除的記錄存入另外的文件中，作為日志文件保存。 （7）作插入操作前，先對信息按起點站進行排序。新記錄插入為起點站相同的最后一條記錄。 數據結構課程設計 航班信息查詢與檢索系統 typedef struct node { Time rh;Time lv;}Pnode;（2）飛機結構體： struct Plane { };（3）靜態鏈表： typedef struct Sqlist { int length;struct Plane *plane;char key[10],sted[20],sche[10];Time rh,lv;int price;}Sqlist;2.3 詳細設計（1）主函數： do{printf(“* * * * * * * * * * * * * 航班查詢系統* * * * * * * * * * * * *n”); printf(“* 1.創建 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; 數據結構課程設計 航班信息查詢與檢索系統 } }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）瀏覽信息：就是循環使用輸出函數，在此就不必多說了 2.4 調試分析 （1）在課設過程中，遇到問題時，通過與同學、老師交流，在圖書館查閱資料，使問題得以解決。 （2）算法中有許多不是很優化的地方。3.用戶使用說明 程序運行后用戶根據提示輸入要進行的操作選項（應先選擇創建選項，這樣可以直接讀取保存好的文件），然后選擇要進行的操作選項。由于主菜單中有修改、查詢和瀏覽項目，每個項目又有各自的子菜單，所以在進行管理和使用時要注意輸入的元素是否正確，需按照提示輸入。輸入操作元素時，元素之間以空格隔開。程序將按輸入的操作元素找到相應的算法，然后進行處理，然后將結果打 數據結構課程設計 航班信息查詢與檢索系統 圖2-2 查詢信息 圖2-3插入 圖2-4刪除 數據結構課程設計 航班信息查詢與檢索系統 時就需要重新寫出一個子函數，哪怕這個子函數就是在原有的一個子函數的基礎上改那么一丁點的地方，例如航班信息查詢系統中的查詢函數，其實每個子函數只是改了一下關鍵碼而已。 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數據結構課程設計 航班信息查詢與檢索系統 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數據結構課程設計 航班信息查詢與檢索系統 n“); } else { } printf(”查找不成功。 i--;if(i==0) { char c[20]; printf(“輸入修改后的scanf(”%s“,c); 內容：”); 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: 內容：“); 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: 內容：“); scanf(”%d:%d“,&a,&b); L.plane[i].rh.hour=a;L.plane[i].rh.min=b;printf(”修改成功！n“);的內容：”);strcpy(L.plane[i].sted,b);}break; }break;{ int a; case 6: case 3: 4數據結構課程設計 航班信息查詢與檢索系統 *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(”請輸入順序表中的內 int i,n;printf(“輸入表中航班的數量： } }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數據結構課程設計 航班信息查詢與檢索系統 n”);} printf(“無法打開文件！} }while(opt!=0); void insert_Sq(Sqlist &L){ 數量 價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); 數量：“); 信息：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; 《數據結構》課程設計 哈希表實現電話號碼查詢系統一目的 利用《數據結構》課程的相關知識完成一個具有一定難度的綜合設計題目，利用C/C++語言進行程序設計，并規范地完成課程設計報告。通過課程設計，鞏固和加深對線性表、棧、隊列、字符串、樹、圖、查找、排序等理論知識的理解；掌握現實復雜問題的分析建模和解決方法（包括問題描述、系統分析、設計建模、代碼實現、結果分析等）；提高利用計算機分析解決綜合性實際問題的基本能力。 二需求分析 1、程序的功能 1)讀取數據 ① 讀取原電話本存儲的電話信息。 ② 讀取系統隨機新建電話本存儲的電話信息。2)查找信息 ① 根據電話號碼查詢用戶信息。② 根據姓名查詢用戶信息。3)存儲信息 查詢無記錄的結果存入記錄文檔。 2、輸出形式 1)數據文件“old.txt”存放原始電話號碼數據。 2)數據文件“new.txt”存放有系統隨機生成的電話號碼文件。3)數據文件“out.txt”存放未查找到的電話信息。4)查找到相關信息時顯示姓名、地址、電話號碼。 3、初步測試計劃 1)從數據文件“old.txt”中讀入各項記錄，或由系統隨機產生各記錄，并且把記錄保存到“new.txt”中。 2)分別采用偽隨機探測再散列法和再哈希法解決沖突。3)根據姓名查找時顯示給定姓名用戶的記錄。4)根據電話號碼查找時顯示給定電話號碼的用戶記錄。 xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 1 《數據結構》課程設計 5)將沒有查找的結果保存到結果文件Out.txt中。 6)系統以菜單界面工作，運行界面友好，演示程序以用戶和計算機的對話方式進行。 三概要設計 1、子函數功能 int Collision_Random(int key,int i)//偽隨機數探量觀測再散列法處理沖突 void Init_HashTable_by_name(string name,string phone,string address)//以姓名為關鍵字建立哈希表 int Collision_Rehash(int key,string str)//再哈希法處理沖突 void Init_HashTable_by_phone(string name,string phone,string address)//以電話號碼為關鍵字建立哈希表 void Outfile(string name,int key)//在沒有找到時輸出未找到的記錄，打開文件out.txt并將記錄儲存在文檔中 void Outhash(int key)//輸出哈希表中的記錄 void Rafile()//隨機生成數據，并將數據保存在new.txt void Init_HashTable(char*fname,int n)//建立哈希表 int Search_by_name(string name)//根據姓名查找哈希表中的記錄 int Search_by_phone(string phone)//根據電話號碼查找哈希表中的記錄 xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 2 《數據結構》課程設計 2、函數調用圖 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專業學號：xxxxxxx姓名：jenery6 3 《數據結構》課程設計 四詳細設計 1、主函數流程圖 開始選擇數據來源21建“new.txt”選擇查找方式12姓名查找電話號碼查找12021輸入姓名顯示哈希表0顯示哈希表輸入電話號碼無此記錄顯示信息無此記錄顯示信息0寫入“out.txt”寫入“out.txt”結束 2、“偽隨機探測再散列處理沖突”偽代碼 若對應位置上已經存在其他數據，則新的關鍵字=（原關鍵字+偽隨機數）%哈希表長。若新的位置上也存在其他數據，則用偽隨機序列的下一個數求新的關鍵字，直到找到合適的位置。 3、“再哈希法處理沖突”偽代碼 用“折疊法”將電話號碼的ASCII碼值定義為關鍵字，分別為前四位、中四位、后三位。 再用“除留余數法”求的新的關鍵字=原關鍵字%哈希表長。 xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 《數據結構》課程設計 4、“以姓名為關鍵字建立哈希表”偽代碼 用“除留余數法”將姓名的ASCII碼值定義為關鍵字。 若對應位置上存在其他數據，則調用偽隨機處理沖突，然后將數據存入哈希表。 5、“以電話號碼為關鍵字建立哈希表”偽代碼 用“除留余數法”將電話號碼的ASCII碼值定義為關鍵字。若對應位置上存在其他數據，則調用再哈希處理沖突。然后將數據存入哈希表。 五調試分析 1、程序的關鍵是掌握文件的相關操作、哈希函數的創建和運用、偽隨機法處理沖突、再哈希法處理沖突等。在編程的過程中，出現了很多問題，如文件無法正常打開、程序進入死循環、無法實現文件的寫入操作、忘了添加頭文件等錯誤。修改后程序運行正確。 2、創建“new.txt”內容用子函數來實現，但是原數據是從“old.txt”文件中讀取的，剛開始不知道怎樣實現二者之間的選擇，在同學和參考書的幫助下終于得到解決。 3、關于偽隨機和再哈希的相關內容覺得很難懂，看了很久參考書才有所了解 六測試結果 1、根據姓名查找 1)姓名查找成功 2)姓名查找失敗 xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 5 《數據結構》課程設計 3)哈希表 xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 6 《數據結構》課程設計 2、根據電話號碼查找 1)電話號碼輸入錯誤 xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 7 《數據結構》課程設計 2)電話號碼查詢成功 3)電話號碼查詢失敗 xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 8 《數據結構》課程設計 4)哈希表 xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 9 《數據結構》課程設計 七用戶使用說明 1、選擇數據來源 根據提示信息進行操作，選擇已存在的“old.txt”文件中的數據或系統當前自動生成的“new.txt”文件。 xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 10 《數據結構》課程設計 2、選擇查找方式 根據提示信息進行操作，選擇“根據姓名查找”或“根據電話號碼查找”兩種查找方式。 3、選擇功能 根據提示信息進行操作，選擇輸入已知信息或查看哈希表。 xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 11 《數據結構》課程設計 4、顯示結果 xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 《數據結構》課程設計 xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 13 《數據結構》課程設計 xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 14 《數據結構》課程設計 5、查看文件 xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 15 《數據結構》課程設計 八課程設計總結 1、收獲 學會了C++的跟蹤。更進一步了解和熟悉了關于哈希表的運用和文件的讀取與寫入操作。同時鍛煉了對話形式的菜單的創建和熟練運用。 2、心得體會 在這次數據結構設計中遇到了很多實際性的問題，在實際設計中才發現，書本上理論性的東西與在實際運用中的還是有一定的出入的，所以有些問題要不斷地更正以前的錯誤思維。通過這次設計，我懂得了學習的重要性，了解到理論知識與實踐相結合的重要意義，xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 16 《數據結構》課程設計 學會了堅持、耐心和努力，這將為自己今后的學習和工作做出了最好的榜樣。我覺得作為一名計科專業的學生，這次課程設計是很有意義的。更重要的是如何把自己平時所學的東西應用到實際中。雖然自己對于這門課懂的并不多，很多基礎的東西都還沒有很好的掌握，覺得很難，也沒有很有效的辦法通過自身去理解，但是靠著學習，漸漸對這門課逐漸產生了些許的興趣，自己開始主動學習并逐步從基礎慢慢開始弄懂它。 xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 《數據結構》課程設計 附錄：源程序 #include using namespace std; ifstream in_file;ofstream out_file; int D[10]={1,3,5,8,13,15,17,21,27,34};//偽隨機數序列 int count;//當前數據元素個數 int sizeindex;//哈希表的長度 char *sign;//沖突的標志 struct Data { string name;string phone;string address;};Data *intermediate_data; int Collision_Random(int key,int i)//偽隨機數探量觀測再散列法處理沖突{ int Re_key;if(sign[key]=='1'){ xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 18 《數據結構》課程設計 } Re_key=(key+D[i])%sizeindex;return Re_key;//歸回新的要害碼 return-1;} void Init_HashTable_by_name(string name,string phone,string address)//以姓名為關鍵字建立哈希表 { 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;//將數據存入哈希表 intermediate_data[key].address=address;intermediate_data[key].phone=phone;sign[key]='1';//設置沖突標志 } xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 19 《數據結構》課程設計 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)//以電話號碼為關鍵字建立哈希表 { 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專業學號：xxxxxxx姓名：jenery6 20 《數據結構》課程設計 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專業學號：xxxxxxx姓名：jenery6 21 《數據結構》課程設計 { for(i=0;i cout< for(i=0;i<8;i++) cout<<“ ”; cout< for(i=0;i<8;i++) cout<<“ ”; cout< void Rafile()//隨機生成數據，并將數據保存在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< 《數據結構》課程設計 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專業學號：xxxxxxx姓名：jenery6 23 《數據結構》課程設計 字 鍵字 } char* str=new char[100];name=”“;phone=”“;address=”“;in_file.getline(str,100,'n');//按行讀入數據 if(str[0]=='*')//判斷數據結束 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);//以姓名為關鍵else Init_HashTable_by_phone(name,phone,address);//以電話號碼為關delete str;in_file.close();} xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 《數據結構》課程設計 int Search_by_name(string name)//根據姓名查找哈希表中的記錄 { 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)//根據電話號碼查找哈希表中的記錄{ int key;char*p;for(key=0,p=&phone[0];*p;p++)key=key+*p;key=key%42;int j=1;xxxx大學xxxx學院xxxx專業學號：xxxxxxx姓名：jenery6 25 《數據結構》課程設計 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第二篇：數據結構課程設計報告
第三篇：數據結構課程設計報告