国产精品久久久久高潮,日韩精品无码av中文无码版,色猫咪av在线网址

第一篇：數據結構課程設計報告

計算機科學與工程系

數據結構課程設計報告

課程設計題目迷宮航班信息查詢系統學號姓名班級

專業網絡工程完成時間 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;jrow-1][q->col-1] q=q->next;

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 #include #include typedef struct time { int hour;int min;

{ }

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;

第二篇：數據結構課程設計報告

數據結構課程設計

散列表的應用:插隊買票

專業計算機科學與技術（網絡技術）

金玲計算機131 1310704114 張靜林 2015年1月23日學生姓名班學級號

指導教師完成日期

目錄概述……………………………………………………………………………………1 1.1 課程設計目的……………………………………………………………………….1 1.2 課程設計內容……………………………………………………………………….1 2 系統需求分析……………………………………………………………………….1 2.1 主體功能…………………………………………………………………………....2 3系統概要設計…………………………………………………………………………2 3.1 系統流程圖………………………………………………………………………….2 4 系統詳細設計…………………………………………………………………………3 5 測試……………………………………………………………………………………5 5.1 測試方案…………………………………………………………………………….5 5.2 測試結果…………………………………………………………………………….5 6 小結……………………………………………………………………………………5 參考文獻…………………………………………………………………………………5 附錄………………………………………………………………………………………7 附錄1 源程序清單……………………………………………………………………...7 概述

1.1 課程設計目的

數據結構課程設計是為數據結構課程獨立開設的實踐性教學環節。數據結構課程設計對于鞏固數據結構知識，加強學生的實際動手能力和提高學生綜合素質是十分必要的。課程設計的目的：

1．要求學生達到熟練掌握C語言的基本知識和技能。

2．了解并掌握數據結構與算法的設計方法，具備初步的獨立分析和設計能力。3．提高程序設計和調試能力。學生通過上機實習，驗證自己設計的算法的正確性。學會有效利用基本調試方法，迅速找出程序代碼中的錯誤并且修改。

4．培養算法分析能力。分析所設計算法的時間復雜度和空間復雜度，進一步提高程序設計水平。

5．初步掌握軟件開發過程的問題分析、系統設計、程序編碼、測試等基本方法和技能。

1.2課程設計內容

本課程設計的任務是寫一個程序模擬這種情況。每個隊伍都允許插隊。如果你在排隊，有一個以上的朋友要求插隊，則你可以安排他們的次序。每次一個人入隊，并且如果這個入隊的人發現隊伍中有自己的朋友，則可以插入到這個朋友的后面；當隊伍中的朋友不止一個的時候，這個人會排在最后一個朋友的后面；如果隊伍中沒有朋友，則他只能夠排在這個隊伍的最后面。每一個入隊的人都先進行上述的判斷。當隊伍前面的人買到車票之后，依次出隊。系統需求分析

2.1 主體功能

程序從“input.txt”文件讀入測試用例，一個文件可包含多個測試用例。每個用例的第一行是朋友組的數目n（1<=n<=1000)。對于一個朋友組以朋友的數目j（1<=j<=1000）開始，由朋友的個數以及他們的名字組成，一個空格后接該組朋友的名字，以空格分開，并且每個人的名字都不同。每個名字不超過四個字母，由{A，B，...，Z，a，b，...，z}組成。一個朋友組最多有1000個人，每個人只屬于一個朋友組。n=0時，測試數據結束。

下面是一些具體命令：.ENQUEUE——X入隊;.DEQUEUE——排隊頭的人買票，離開隊伍，即出隊；.STOP——一個測試用例結束。

測試結果輸出到“output.txt”文件中。每個測試用例第一行輸出“Scenario#k”，k是測試用例的序號（從1開始）。對每一個出隊命令，輸出剛買票離開隊伍的人名。兩個測試試用例之間隔一空行，最后一個用例結束不輸出空行。系統概要設計

3.1 系統流程圖系統詳細設計

本題目主要解決兩個問題：一是怎么存放和查找大量數據（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。

用散列表來存放和查找數據。由于最多有1000個朋友組，每組最多有1000人，使用平方探測法解決沖突，則表的大小是2*（1000*1000），所以選擇TableSize=2000003（2000003是大于2000000的最小素數）。同一個組內的都是朋友，所以每個人除了記錄他的名字name，還要記錄他屬于哪個組group，另外用info來表示該單元是否被占用，數據結構如圖4.1所示。散列函數是根據Honer法則計算一個以64為階的多項式，如圖4.2所示。沖突解決方法采用平方探測法，如圖4.3所示。

#define TabSize 2000003 typedef struct hashtab *PtrToHash;struct hashtab

/*散列表數據結構*/ { char name[5];

/*名字*/ int group;

/*屬于哪個朋友組*/ char info;

/*標志位，該單元是否被占用*/ };圖4.1數據結構：散列表

Int Hash(char *key,int TableSize){

Int HashVal=0;

While(key!=NULL)

HashVal=(HashVal<<6)+*key;

Return HashVal%TableSize;} 圖4.2散列函數

Long int Find(PtrToHash hash,char *c){

key=c;

CurrentPos=Hash(key,TableSize);

CollisionNum=0;

While((單元被占用)and(單元內的名字與查找的名字不同))

{

CurrentPos+=2*(++CollisionNum)-1;

If(CurrentPos>=TabSize)

CurrentPos=TabSize;

}

Return CurrentPos;} 圖4.3用平方探測法解決沖突

第二個問題是關于怎么操作“ENQUEUE”和“DEQUEUE”命令。這可以用隊列來模擬。由于有插隊現象的存在，不能單純的用一個數組來表示隊列，因為這樣的話，插入一個朋友，則他后面的人都要往后移一個單位，刪除一個人，則他后面的人都要前移一個，會降低效率。所以，采用一個Index標記來表示當前元素的后繼元素，最后一個單元的后繼元素是第0個，形成環，數據結構如圖4.4所示。不用鏈表是因為鏈表存放指針也需要空間，并且鏈表插入、刪除的效率沒有數組高。

typedef struct Que *PtrToQue;struct Que

/*隊列數據結構*/ { long int HashVal;

/*散列值*/ long int Index;

/*在中的隊列序號*/ };圖4.4數據結構：隊列

輸入ENQUEUE命令，如果隊伍里有朋友，則排在朋友后面；如果沒有朋友，則排在隊尾。入隊時，用一個數組記錄每個朋友組的最后一位，以便下一個朋友到來時排到他后面，這個數組被稱為“插隊數組”。

輸入DEQUEUE命令，則根據“先進先出”，按照各個元素和它后繼元素的先后順序，每次刪除隊列重的第一個。程序結構如圖4.5所示。

While(讀測試文件){

if(輸入”ENQUEUE”)

{

讀入名字；

插入散列表；

插入隊列；

}

else if(輸入”DEQUEUE”)

{

刪除隊列第一個名字；

將該名字輸出到文件；

}

else stop;} 圖4.5入隊、出隊操作測試

5.1 測試方案按輸入要求輸入正常測試數據，測試程序是否能正確解決問題，得到正確答案。應注意邊界測試。例如，將n，j分別取為1的用例和n為1000的用例。n，j比較大時需寫程序生成測試用例。

不按輸入要求輸入數據，測試程序能否對輸入內容進行數據合法性檢測并進行相應的異常處理。例如，將n或j取為小于1或大于1000的數，名字超過4個字母等情況下的測試用例。5.2 測試結果小結

在前面的學習過程中我們學到了很多知識而這次課程設計又是對我們所學的一次總結，剛開始，可以說是沒有頭緒，于是就去圖書館找資料，找到了一些關于程序方面的，可這遠遠不夠，這只是小小的開始。我們必須掌握很多已學的知識才能很好的完成本次的課程設計。在這次課程設計中，總的感覺是我遇到了很多困難這主要是由于我編寫代碼的經驗不足，有時雖然是一個很小的問題但解決起來卻花費了我不少的時間，值得欣慰的是，當自己苦思冥想或者和其它同學一起探討把問題解決的時候我還是覺得獲益非淺，這就是在摸索中尋求到的知識。在設計時也免不了存在著些不足，所以在今后的學習中我會努力取得更大的進步。雖然對著電腦做程序，有些累，可當看到勞動成果時，卻有另一番滋味。

參考文獻

[1]范策，周世平，胡曉琨.《算法與數據結構（C語言版）》[M].北京：機械工業出版社，2004 [2]嚴蔚敏.《數據結構（C語言版）》.北京：清華大學出版社，2004 [3]許卓群，楊冬青，唐世渭，張銘.《數據結構與算法》.北京：高等教育出版社，2004 [4]徐孝凱.《數據結構實用教程（第二版）》.北京：清華大學出版社，2006

附錄

附錄1 源程序清單

#include #include #include #define TabSize 2000003

/*散列表大小TabSize 是大于表最大空間的素數*/ #define Max 1000001

/*隊列空間最大值*/ struct hashtab;typedef struct hashtab *PtrToHash;struct hashtab

/*散列表數據結構*/ { char name[5];

/*名字*/ int group;

/*屬于哪個朋友組*/ char info;

/*標志位，該單元是否被占用*/ };struct Que;typedef struct Que *PtrToQue;struct Que

/*隊列數據結構*/ { long int HashVal;

/*散列值*/ long int Index;

/*在中的隊列序號*/ };

int hashedx=0;

/*標記元素是否已經在散列表里*/ long int Find(PtrToHash hash,char *c)/*查找在散列表中的位置*/ { char *key;long int CurrentPos,CollisionNum;

key=c;for(CurrentPos=0;*key;++key)

/*散列函數，計算散列值*/

CurrentPos=(CurrentPos<<6)+*key;CurrentPos%=TabSize;

/*散列值*/ CollisionNum=0;/*如果當前單元被占用：單元內的元素與當前操作的名字不同，使用平方探測法解決沖突；與當前操作的名字相同，則直接返回在散列中的位置*/ while((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)))

{

/*平方探測法*/

CurrentPos+=2*(++CollisionNum)-1;

if(CurrentPos>=TabSize)

CurrentPos-=TabSize;}

if((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)==0))

/*元素已經在散列表里*/

hashedx=1;else /*元素不在散列表里*/

hashedx=0;return CurrentPos;/*返回在散列表中的位置*/ }

int main(){ long int Find(PtrToHash hash,char *c);

/*查找在散列表中的位置*/

PtrToHash hash;

/*散列表*/ PtrToQue queue;

/*隊列*/ int *grouppos;

/*記錄每個朋友組的最后一位，即插隊數組*/ int n;

/*測試用例數目*/ int num;

/*當前測試用例序號*/ long int i,ii,j,key,temp;long int head,last;

/*隊列的頭和尾*/ char c[8],tempc[8];

/*名字*/ FILE *fpin,*fpout;

/*輸入、輸出文件指針*/

if(!(fpin=fopen(“input.txt”,“r”)))

/*打開測試文件*/ {

printf(“fopen error!”);

/*文件打開錯誤*/

return-1;} if(!(fpout=fopen(“output.txt”,“w”)))

/*打開輸出文件*/ {

printf(“fopen error!”);

return-1;}

hash=(PtrToHash)malloc(sizeof(struct hashtab)*TabSize);/*為散列表申請空間*/ queue=(PtrToQue)malloc(sizeof(struct Que)*Max);/*為隊列申請空間*/ grouppos=(int *)malloc(sizeof(int)*1000);/*申請空間記錄每個朋友組的最后一位*/ for(i=0,j=1;i

queue[i].Index=j;queue[i-1].Index=0;/*最后一個單元的后繼單元是第0個，形成環*/ num=0;for(fscanf(fpin,“%d”,&n);n;fscanf(fpin,“%d”,&n))/*輸入當前測試用例的朋友組數*/ {

if(n<1||n>1000)

/*處理異常輸入n*/

{

fprintf(fpout,“n is out of rangen”);

return-1;

}

num++;

if(num!=1)

/*兩個測試用例間輸入一空行*/

fprintf(fpout,“n”);

for(i=0;i

hash[i++].info=0;

/*初始化散列表，標記位置0*/

for(i=0;i

/*對每一組朋友*/

{

fscanf(fpin,“%d”,&j);

/*當前組里的人數*/

if(j<1||j>1000)

/*處理異常輸入j*/

{

fprintf(fpout,“j is out of rangen”);

return-1;

}

for(;j;--j)

{

fscanf(fpin,“%s”,c);

/*輸入名字*/

for(ii=0;ii

tempc[ii]='

久久99精品久久久久久琪琪,久久人人爽人人爽人人片亞洲,熟妇人妻无码中文字幕,亚洲精品无码久久久久久久

數據結構課程設計報告

第一篇：數據結構課程設計報告

第二篇：數據結構課程設計報告