第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報告
計(jì)算機(jī)科學(xué)與工程系
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報告
課程設(shè)計(jì)題目 迷宮 航班信息查詢系統(tǒng) 學(xué) 號 姓 名 班 級
專 業(yè) 網(wǎng)絡(luò)工程 完 成 時 間 2013-1-4 指 導(dǎo) 教 師
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
迷宮
題目一
1.設(shè)計(jì)內(nèi)容 1.1問題描述
求迷宮從入口到出口的所有路徑。1.2設(shè)計(jì)要求
1．迷宮中不能使用遞歸算法查找路徑。2．試探方向限定為上、下、左、右四個方向。3．迷宮采用隨機(jī)生成和手工生成兩種方式。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ā)，沿某一方向進(jìn)行探索，若能走通，則繼續(xù)向前走；否則沿原路返回，換一方向再進(jìn)行搜索，直到所有可能的通路都探索到為止。即所謂的回溯法。
2.設(shè)計(jì)步驟
2.1 需求分析
（1）題目：迷宮的生成與路由。生成一個N*M（N行M列）的迷宮，0和
1-1數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
迷宮
在該程序中，首先進(jìn)入的是菜單選擇，在菜單中有3種選擇，選1是手動輸入迷宮函數(shù)；選2是隨機(jī)自動生成迷宮；選3是退出程序。在手動生成迷宮時，有兩種輸出方式，一是矩陣輸出，二是圖形輸出。在矩陣輸出時，直接將數(shù)組中的數(shù)進(jìn)行輸出，在圖形輸出時，則要判斷該點(diǎn)的情況，然后輸入迷宮的出入口，再調(diào)用mgpath（）函數(shù)進(jìn)行判斷是否存在路徑，如果存在則將路徑經(jīng)過的點(diǎn)進(jìn)行輸出，并且將經(jīng)過的點(diǎn)進(jìn)入到輔助數(shù)組中（輔助數(shù)組是輔助圖形界面的輸出），并且將輔助數(shù)組初始為1，輔助數(shù)組中點(diǎn)為路徑的重新賦值為0，然后根據(jù)情況輸出圖形界面。在自動生成迷宮時，用到了c語言隨機(jī)函數(shù)，對于其它問題，和手動情況基本相同。
2.3 詳細(xì)設(shè)計(jì)（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è)計(jì)
迷宮
和“class ‘maze’has an illegal zero-sized array”兩行錯誤。雙擊錯誤信息，找到出錯的程序段，經(jīng)過查閱資料發(fā)現(xiàn)，在利用順序棧時，沒有定義順序棧的向量空間大小，導(dǎo)致程序出錯。但不要對向量空間定義過大，否則會浪費(fèi)空間。
（2）算法的時空分析：
由于鏈棧實(shí)際上是運(yùn)算受限制的單鏈表。所以取棧頂元素運(yùn)算的算法、置空棧運(yùn)算的算法執(zhí)行時間與問題的規(guī)模無關(guān)，則該算法的時間復(fù)雜度為O(1)；而其入棧運(yùn)算的算法與出棧運(yùn)算的算法相當(dāng)于在鏈表的表尾進(jìn)行插入和刪除操作，不需要移動元素，時間復(fù)雜度也為O（1）。建立迷宮矩陣的時間復(fù)雜度為O（x*y）。在查找路徑的過程中，最壞的情況下可能要考察每一個非障礙的位置。因此，查找路徑的時間復(fù)雜度應(yīng)為O（unblocked）。
鏈棧的入棧算法、出棧算法、取棧頂元素算法、置空棧算法執(zhí)行時所需要的空間都是用于存儲算法本身所用的指令、常數(shù)、變量，各個算法的空間性能均較好。只是對于存放順序棧的向量空間大小的定義很難把握好，如果定義過大，會造成不必要的空間浪費(fèi)。所以在定義時要慎重考慮。
3.用戶使用說明
運(yùn)行該程序，運(yùn)行的界面的會出現(xiàn)菜單界面，然后用戶可根據(jù)界面的提示進(jìn)行相應(yīng)的操作，生成迷宮的方式有兩種方式，手動生成和自動生成，手動生成時、，用戶可根據(jù)自己的要求輸入迷宮的格式，還需輸入相應(yīng)的入出口，確認(rèn)程序就會生成相應(yīng)的路徑圖形；自動生成只需輸入所需的行數(shù)和列數(shù)，就會生成迷宮，接下來的操作和手動操作相同了。
圖數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
迷宮
圖1-2
圖1-3 退出
5.總結(jié)與心得體會
本次課程設(shè)計(jì)過程中由于掌握的知識不牢固，在編程序的過程中得到了同學(xué)的幫助和指導(dǎo)，在此表示感謝。課程設(shè)計(jì)的過程中，遇到了一些問題，大部分是課本中的知識掌握的不牢固，還有就是在以前學(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è)計(jì)
迷宮
} } 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è)計(jì)
迷宮
void tonglu()//將坐標(biāo)的頂點(diǎn)輸出 {
始化
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(”輸入選項(xiàng)：“);scanf(”%d“,&choice);switch(choice){ case 1://手動建立迷宮 { shuru(); printf(”手動建立for(i=1;i<=m;i++) n“); printf(”# 1-手動生成迷 宮 2-自動生成迷宮 3-退出 #n“);0;//將路徑中的點(diǎn)賦給輔助數(shù)組a 形的界面輸出 迷宮矩陣(0表示可通1表示障礙):n”); for(j=1;j<=n;j++)scanf(“%d”,&mg[i][j]); 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 航班信息查詢與檢索系統(tǒng) 題目二 1.設(shè)計(jì)內(nèi)容 1.1問題描述 設(shè)計(jì)一個航班信息查詢系統(tǒng)，提供信息的管理和使用功能，管理包括更新、添加、刪除功能。 1.2設(shè)計(jì)要求 （1）原始信息存儲在文件中，記錄不少于50條。（2）用戶界面至少包括以下功能： ? 創(chuàng)建 ? 修改（插入、添加、刪除、更新）? 查詢 ? 瀏覽 ? 退出管理系統(tǒng)（3）航班信息包括： ? 航班號：字符序列，具體字符表達(dá)的意思上網(wǎng)查詢 ? 起點(diǎn)站和終點(diǎn)站：字符串 ? 班期：指一周中哪些天有航班 ? 起飛時間：可將時間定義成一個時、分組成的序列 ? 到達(dá)時間：可將時間定義成一個時、分組成的序列 ? 機(jī)型：字符序列，具體字符表達(dá)的意思上網(wǎng)查詢 ? 票價：整型數(shù)，具體值可上網(wǎng)查詢 （4）創(chuàng)建是指從文件中讀取數(shù)據(jù)，并存入所定義的順序表中。 （5）可按航班號、起點(diǎn)站、終點(diǎn)站、起飛時間、到達(dá)時間等進(jìn)行查詢。查詢時要用到順序查找、二分查找方法。輸出查詢結(jié)果時必須排序。 （6）可按航班號、起點(diǎn)站、起飛時間、票價進(jìn)行刪除和更新操作，刪除的記錄存入另外的文件中，作為日志文件保存。 （7）作插入操作前，先對信息按起點(diǎn)站進(jìn)行排序。新記錄插入為起點(diǎn)站相同的最后一條記錄。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 航班信息查詢與檢索系統(tǒng) typedef struct node { Time rh;Time lv;}Pnode;（2）飛機(jī)結(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 詳細(xì)設(shè)計(jì)（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è)計(jì) 航班信息查詢與檢索系統(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(“請輸入選項(xiàng)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.用戶使用說明 程序運(yùn)行后用戶根據(jù)提示輸入要進(jìn)行的操作選項(xiàng)（應(yīng)先選擇創(chuàng)建選項(xiàng)，這樣可以直接讀取保存好的文件），然后選擇要進(jìn)行的操作選項(xiàng)。由于主菜單中有修改、查詢和瀏覽項(xiàng)目，每個項(xiàng)目又有各自的子菜單，所以在進(jìn)行管理和使用時要注意輸入的元素是否正確，需按照提示輸入。輸入操作元素時，元素之間以空格隔開。程序?qū)摧斎氲牟僮髟卣业较鄳?yīng)的算法，然后進(jìn)行處理，然后將結(jié)果打 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 航班信息查詢與檢索系統(tǒng) 圖2-2 查詢信息 圖2-3插入 圖2-4刪除 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 航班信息查詢與檢索系統(tǒng) 時就需要重新寫出一個子函數(shù)，哪怕這個子函數(shù)就是在原有的一個子函數(shù)的基礎(chǔ)上改那么一丁點(diǎn)的地方，例如航班信息查詢系統(tǒng)中的查詢函數(shù)，其實(shí)每個子函數(shù)只是改了一下關(guān)鍵碼而已。 6.附錄 #include { } void search_key(Sqlist L)//按航班號查找 { 號：“); Time rh;Time lv; scanf(”%s“,n);int i; printf(”此航班的航班號，起點(diǎn)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; 終點(diǎn)，班期，起飛時間，到達(dá)時間，票價：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è)計(jì) 航班信息查詢與檢索系統(tǒng) printf(“此航班的航班號，起點(diǎn) ted，{ 終點(diǎn)，班期，起飛時間，到達(dá)時間，票價：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(“此航班的航班號，起點(diǎn) } } [i].price); * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”); printf(“* 1.航班號查詢 2.起點(diǎn)終點(diǎn)查詢 3.班期查詢 4.起飛時間查詢 5.到達(dá)時間查詢 0.退出 *n”); printf(“* * * * * * * * * * * * * * * * * * * * * * * * ** * * * * * * * * * * * * * * *n”); scanf(“%d”,&i); switch(i) { case 晚時間：“);終點(diǎn)，班期，起飛時間，到達(dá)時間，票價：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è)計(jì) 航班信息查詢與檢索系統(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è)計(jì) 航班信息查詢與檢索系統(tǒng) *n“); printf(”* * * * * * * * * * * * * * * * * * * * * * * * *n“); printf(”請輸入選項(xiàng)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(“沒有選項(xiàng)！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 班期 起飛時間 到達(dá)時間 票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(“所刪除的班機(jī)*)malloc((n+10000)*sizeof(Plane));的信息：n”); printf(“n航班號 起點(diǎn)終點(diǎ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è)計(jì) 航班信息查詢與檢索系統(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(”請輸入要添加班機(jī)的scanf(“%d”,&n); printf(“請輸入要添加的班機(jī)printf(”n航班號 起點(diǎn)終點(diǎn) int i,n; //n表示添加的fprintf(fp,“航班號：%sn起點(diǎn)站：%s 終點(diǎn)站：%sn班期：%dn起飛時間：%d:%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”); 班期 起飛時間 到達(dá)時間 票* * * * * * * * * *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è)計(jì) 散列表的應(yīng)用:插隊(duì)買票 專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù)（網(wǎng)絡(luò)技術(shù)） 金玲 計(jì)算機(jī)131 1310704114 張靜林 2015年1月23日 學(xué)生姓名 班學(xué)級 號 指導(dǎo)教師 完成日期 目錄概述……………………………………………………………………………………1 1.1 課程設(shè)計(jì)目的……………………………………………………………………….1 1.2 課程設(shè)計(jì)內(nèi)容……………………………………………………………………….1 2 系統(tǒng)需求分析……………………………………………………………………….1 2.1 主體功能…………………………………………………………………………....2 3系統(tǒng)概要設(shè)計(jì)…………………………………………………………………………2 3.1 系統(tǒng)流程圖………………………………………………………………………….2 4 系統(tǒng)詳細(xì)設(shè)計(jì)…………………………………………………………………………3 5 測試……………………………………………………………………………………5 5.1 測試方案…………………………………………………………………………….5 5.2 測試結(jié)果…………………………………………………………………………….5 6 小結(jié)……………………………………………………………………………………5 參考文獻(xiàn)…………………………………………………………………………………5 附錄………………………………………………………………………………………7 附錄1 源程序清單……………………………………………………………………...7 概述 1.1 課程設(shè)計(jì)目的 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是為數(shù)據(jù)結(jié)構(gòu)課程獨(dú)立開設(shè)的實(shí)踐性教學(xué)環(huán)節(jié)。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)對于鞏固數(shù)據(jù)結(jié)構(gòu)知識，加強(qiáng)學(xué)生的實(shí)際動手能力和提高學(xué)生綜合素質(zhì)是十分必要的。課程設(shè)計(jì)的目的： 1．要求學(xué)生達(dá)到熟練掌握C語言的基本知識和技能。 2．了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力。3．提高程序設(shè)計(jì)和調(diào)試能力。學(xué)生通過上機(jī)實(shí)習(xí)，驗(yàn)證自己設(shè)計(jì)的算法的正確性。學(xué)會有效利用基本調(diào)試方法，迅速找出程序代碼中的錯誤并且修改。 4．培養(yǎng)算法分析能力。分析所設(shè)計(jì)算法的時間復(fù)雜度和空間復(fù)雜度，進(jìn)一步提高程序設(shè)計(jì)水平。 5．初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能。 1.2課程設(shè)計(jì)內(nèi)容 本課程設(shè)計(jì)的任務(wù)是寫一個程序模擬這種情況。每個隊(duì)伍都允許插隊(duì)。如果你在排隊(duì)，有一個以上的朋友要求插隊(duì)，則你可以安排他們的次序。每次一個人入隊(duì)，并且如果這個入隊(duì)的人發(fā)現(xiàn)隊(duì)伍中有自己的朋友，則可以插入到這個朋友的后面；當(dāng)隊(duì)伍中的朋友不止一個的時候，這個人會排在最后一個朋友的后面；如果隊(duì)伍中沒有朋友，則他只能夠排在這個隊(duì)伍的最后面。每一個入隊(duì)的人都先進(jìn)行上述的判斷。當(dāng)隊(duì)伍前面的人買到車票之后，依次出隊(duì)。系統(tǒng)需求分析 2.1 主體功能 程序從“input.txt”文件讀入測試用例，一個文件可包含多個測試用例。每個用例的第一行是朋友組的數(shù)目n（1<=n<=1000)。對于一個朋友組以朋友的數(shù)目j（1<=j<=1000）開始，由朋友的個數(shù)以及他們的名字組成，一個空格后接該組朋友的名字，以空格分開，并且每個人的名字都不同。每個名字不超過四個字母，由{A，B，...，Z，a，b，...，z}組成。一個朋友組最多有1000個人，每個人只屬于一個朋友組。n=0時，測試數(shù)據(jù)結(jié)束。 下面是一些具體命令：.ENQUEUE——X入隊(duì);.DEQUEUE——排隊(duì)頭的人買票，離開隊(duì)伍，即出隊(duì)；.STOP——一個測試用例結(jié)束。 測試結(jié)果輸出到“output.txt”文件中。每個測試用例第一行輸出“Scenario#k”，k是測試用例的序號（從1開始）。對每一個出隊(duì)命令，輸出剛買票離開隊(duì)伍的人名。兩個測試試用例 之間隔一空行，最后一個用例結(jié)束不輸出空行。系統(tǒng)概要設(shè)計(jì) 3.1 系統(tǒng)流程圖 系統(tǒng)詳細(xì)設(shè)計(jì) 本題目主要解決兩個問題：一是怎么存放和查找大量數(shù)據(jù)（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。 用散列表來存放和查找數(shù)據(jù)。由于最多有1000個朋友組，每組最多有1000人，使用平方探測法解決沖突，則表的大小是2*（1000*1000），所以選擇TableSize=2000003（2000003是大于2000000的最小素?cái)?shù)）。同一個組內(nèi)的都是朋友，所以每個人除了記錄他的名字name，還要記錄他屬于哪個組group，另外用info來表示該單元是否被占用，數(shù)據(jù)結(jié)構(gòu)如圖4.1所示。散列函數(shù)是根據(jù)Honer法則計(jì)算一個以64為階的多項(xiàng)式，如圖4.2所示。沖突解決方法采用平方探測法，如圖4.3所示。 #define TabSize 2000003 typedef struct hashtab *PtrToHash;struct hashtab /*散列表數(shù)據(jù)結(jié)構(gòu)*/ { char name[5]; /*名字*/ int group; /*屬于哪個朋友組*/ char info; /*標(biāo)志位，該單元是否被占用*/ };圖4.1數(shù)據(jù)結(jié)構(gòu)：散列表 Int Hash(char *key,int TableSize){ Int HashVal=0; While(key!=NULL) HashVal=(HashVal<<6)+*key; Return HashVal%TableSize;} 圖4.2散列函數(shù) Long int Find(PtrToHash hash,char *c){ key=c; CurrentPos=Hash(key,TableSize); CollisionNum=0; While((單元被占用)and(單元內(nèi)的名字與查找的名字不同)) { CurrentPos+=2*(++CollisionNum)-1; If(CurrentPos>=TabSize) CurrentPos=TabSize; } Return CurrentPos;} 圖4.3用平方探測法解決沖突 第二個問題是關(guān)于怎么操作“ENQUEUE”和“DEQUEUE”命令。這可以用隊(duì)列來模擬。由于有插隊(duì)現(xiàn)象的存在，不能單純的用一個數(shù)組來表示隊(duì)列，因?yàn)檫@樣的話，插入一個朋友，則他后面的人都要往后移一個單位，刪除一個人，則他后面的人都要前移一個，會降低效率。所以，采用一個Index標(biāo)記來表示當(dāng)前元素的后繼元素，最后一個單元的后繼元素是第0個，形成環(huán)，數(shù)據(jù)結(jié)構(gòu)如圖4.4所示。不用鏈表是因?yàn)殒湵泶娣胖羔樢残枰臻g，并且鏈表插入、刪除的效率沒有數(shù)組高。 typedef struct Que *PtrToQue;struct Que /*隊(duì)列數(shù)據(jù)結(jié)構(gòu)*/ { long int HashVal; /*散列值*/ long int Index; /*在中的隊(duì)列序號*/ };圖4.4數(shù)據(jù)結(jié)構(gòu)：隊(duì)列 輸入ENQUEUE命令，如果隊(duì)伍里有朋友，則排在朋友后面；如果沒有朋友，則排在隊(duì)尾。入隊(duì)時，用一個數(shù)組記錄每個朋友組的最后一位，以便下一個朋友到來時排到他后面，這個數(shù)組被稱為“插隊(duì)數(shù)組”。 輸入DEQUEUE命令，則根據(jù)“先進(jìn)先出”，按照各個元素和它后繼元素的先后順序，每次刪除隊(duì)列重的第一個。程序結(jié)構(gòu)如圖4.5所示。 While(讀測試文件){ if(輸入”ENQUEUE”) { 讀入名字； 插入散列表； 插入隊(duì)列； } else if(輸入”DEQUEUE”) { 刪除隊(duì)列第一個名字； 將該名字輸出到文件； } else stop;} 圖4.5入隊(duì)、出隊(duì)操作 測試 5.1 測試方案 按輸入要求輸入正常測試數(shù)據(jù)，測試程序是否能正確解決問題，得到正確答案。應(yīng)注意邊界測試。例如，將n，j分別取為1的用例和n為1000的用例。n，j比較大時需寫程序生成測試用例。 不按輸入要求輸入數(shù)據(jù)，測試程序能否對輸入內(nèi)容進(jìn)行數(shù)據(jù)合法性檢測并進(jìn)行相應(yīng)的異常處理。例如，將n或j取為小于1或大于1000的數(shù)，名字超過4個字母等情況下的測試用例。5.2 測試結(jié)果 小結(jié) 在前面的學(xué)習(xí)過程中我們學(xué)到了很多知識而這次課程設(shè)計(jì)又是對我們所學(xué)的 一次總結(jié)，剛開始，可以說是沒有頭緒，于是就去圖書館找資料，找到了一些關(guān)于程序方面的，可這遠(yuǎn)遠(yuǎn)不夠，這只是小小的開始。我們必須掌握很多已學(xué)的知識才能很好的完成本次的課程設(shè)計(jì)。在這次課程設(shè)計(jì)中，總的感覺是我遇到了很多困難這主要是由于我編寫代碼的經(jīng)驗(yàn)不足，有時雖然是一個很小的問題但解決起來卻花費(fèi)了我不少的時間，值得欣慰的是，當(dāng)自己苦思冥想或者和其它同學(xué)一起探討把問題解決的時候我還是覺得獲益非淺，這就是在摸索中尋求到的知識。在設(shè)計(jì)時也免不了存在著些不足，所以在今后的學(xué)習(xí)中我會努力取得更大的進(jìn)步。雖然對著電腦做程序，有些累，可當(dāng)看到勞動成果時，卻有另一番滋味。 參考文獻(xiàn) [1]范策，周世平，胡曉琨.《算法與數(shù)據(jù)結(jié)構(gòu)（C語言版）》[M].北京：機(jī)械工業(yè)出版社，2004 [2]嚴(yán)蔚敏.《數(shù)據(jù)結(jié)構(gòu)（C語言版）》.北京：清華大學(xué)出版社，2004 [3]許卓群，楊冬青，唐世渭，張銘.《數(shù)據(jù)結(jié)構(gòu)與算法》.北京：高等教育出版社，2004 [4]徐孝凱.《數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（第二版）》.北京：清華大學(xué)出版社，2006 附錄 附錄1 源程序清單 #include /*散列表大小TabSize 是大于表最大空間的素?cái)?shù)*/ #define Max 1000001 /*隊(duì)列空間最大值*/ struct hashtab;typedef struct hashtab *PtrToHash;struct hashtab /*散列表數(shù)據(jù)結(jié)構(gòu)*/ { char name[5]; /*名字*/ int group; /*屬于哪個朋友組*/ char info; /*標(biāo)志位，該單元是否被占用*/ };struct Que;typedef struct Que *PtrToQue;struct Que /*隊(duì)列數(shù)據(jù)結(jié)構(gòu)*/ { long int HashVal; /*散列值*/ long int Index; /*在中的隊(duì)列序號*/ }; int hashedx=0; /*標(biāo)記元素是否已經(jīng)在散列表里*/ long int Find(PtrToHash hash,char *c)/*查找在散列表中的位置*/ { char *key;long int CurrentPos,CollisionNum; key=c;for(CurrentPos=0;*key;++key) /*散列函數(shù)，計(jì)算散列值*/ CurrentPos=(CurrentPos<<6)+*key;CurrentPos%=TabSize; /*散列值*/ CollisionNum=0;/*如果當(dāng)前單元被占用：單元內(nèi)的元素與當(dāng)前操作的名字不同，使用平方探測法解決沖突；與當(dāng)前操作的名字相同，則直接返回在散列中的位置*/ 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)) /*元素已經(jīng)在散列表里*/ hashedx=1;else /*元素不在散列表里*/ hashedx=0;return CurrentPos;/*返回在散列表中的位置*/ } int main(){ long int Find(PtrToHash hash,char *c); /*查找在散列表中的位置*/ PtrToHash hash; /*散列表*/ PtrToQue queue; /*隊(duì)列*/ int *grouppos; /*記錄每個朋友組的最后一位，即插隊(duì)數(shù)組*/ int n; /*測試用例數(shù)目*/ int num; /*當(dāng)前測試用例序號*/ long int i,ii,j,key,temp;long int head,last; /*隊(duì)列的頭和尾*/ 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);/*為隊(duì)列申請空間*/ grouppos=(int *)malloc(sizeof(int)*1000);/*申請空間記錄每個朋友組的最后一位*/ for(i=0,j=1;i queue[i].Index=j;queue[i-1].Index=0;/*最后一個單元的后繼單元是第0個，形成環(huán)*/ num=0;for(fscanf(fpin,“%d”,&n);n;fscanf(fpin,“%d”,&n))/*輸入當(dāng)前測試用例的朋友組數(shù)*/ { 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; /*初始化散列表，標(biāo)記位置0*/ for(i=0;i /*對每一組朋友*/ { fscanf(fpin,“%d”,&j); /*當(dāng)前組里的人數(shù)*/ 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]='
第二篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報告