數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-插隊買票

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告插隊買票專業(yè)學(xué)生姓名班級學(xué)號指導(dǎo)教師完成日期2015年1月24日1目 錄1、設(shè)計題目12、課題目的及要求23、設(shè)計分析44、調(diào)試與測試65、小 結(jié)86、參考文獻97、源程序清單101數(shù)據(jù)結(jié)構(gòu)課程的設(shè)計 1、設(shè)計題目春節(jié)前夕,一年一度的運輸高潮也開始了,成千上萬的外出人員都往家趕.火車站售票 窗前買票隊伍一眼望不到頭.運氣好的,碰到一個已經(jīng)在排隊的朋友,直接走過去,排他后 面,這就叫"插隊",但對隊伍里的其他人來說是不公平的.本課程設(shè)計的任務(wù)是寫一個程序模擬這種情況.每個隊伍都允許插隊.如果你在排隊,有一個以上的朋友要求插隊,則你可以安排他

2、們的次序.每次一個人入隊,并且如果這個入隊的人發(fā)現(xiàn)隊伍中有自己的朋友,則可以插入到這個朋友的后面;當隊伍中的朋友不止一個的時候,這個人會排在最后一個朋友的后面;如果隊伍中沒有朋友,則他只能夠排在這個隊伍的最后面.每一個入隊的人都先進行上述的判斷.當隊伍前面的人買到車票之后.依次出隊.2、課題目的及要求2.1目的：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計是為數(shù)據(jù)結(jié)構(gòu)課程獨立開設(shè)的實踐性教學(xué)環(huán)節(jié)。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計對于鞏固數(shù)據(jù)結(jié)構(gòu)知識，加強學(xué)生的實際動手能力和提高學(xué)生綜合素質(zhì)是十分必要的。  本題目主要解決兩個問題：一是怎么存放和查找大量數(shù)據(jù)（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。

3、2.2要求：1）輸入要求：程序從“input. txt”文件讀入測試用例，一個文件可包含多個測試用例。每個用例的第一行是朋友組的數(shù)目n（1<=n<=1000).對于一個朋友組以朋友的數(shù)目j(1<=j<=1000)開始，由朋友的個數(shù)以及他們的名字組成，一個空格后接該組朋友的名字，以空格分開，并且每個人的名字都不同。每個名字不超過4個字母，由A,B,Z,a,b,z 組成。一個朋友組最多有1000個人，每個人只屬于一個朋友組。n=0時，測試數(shù)據(jù)結(jié)束。下面是一些具體命令：ENQUEUEXX入隊DEQUEUE排隊頭的人買票，離開隊伍，即出隊STOP一個測用例結(jié)束2）、輸出要求：測

4、試結(jié)果輸出到“output.txt”文件中。每個測試用例的第一行輸出“Scenario#k”，k是測試用例的序號（從1開始）。對每一個DEQUEUE命令，輸出剛買票離開隊伍的人名。兩個測試用例之間隔一空行，最后一個用例結(jié)束不輸出空行。3、設(shè)計分析圖1 系統(tǒng)總圖3.1用散列表來存放和查找數(shù)據(jù)由于最多有1000個朋友組，每組最多1000人，使用平方探測法解決沖突，則表的大小至少是2*（1000*1000），所以選擇TableSize=2000003。同一個組內(nèi)的都是朋友，所以每個人除了記錄他的名字name，還要記錄他屬于哪個朋友組group，另外用info來表示該單元是否被占用，數(shù)據(jù)結(jié)構(gòu)如圖2所示

5、。散列函數(shù)是根據(jù)Honer法則計算一個以64為階的多項式，如圖3所示。沖突解決方法采用平方探測法，如圖4所示。#define TabSize 2000003 typedef struct hashtab *PtrToHash;struct hashtab char name5; int group; char info; /*用來表示該單元是否被占用*/;圖2數(shù)據(jù)結(jié)構(gòu)：散列表int Hash(char *key,int TableSize) int HashVal=0; while(key!=NULL) HashVal=(HashVal<<6)+*key;Return HashVa

6、l%TableSize;圖3 散列函數(shù)long int Find(PtrToHash hash,char *c)   key=c;   CurrentPos=Hash(key,TabSize);                     /*計算散列值*/   CollisionN

7、um=0;    while(單元被占用)and(單元內(nèi)的名字與查找的名字不同)   /*發(fā)生沖突*/          /*平方探測法*/   CurrentPos+=2*(+CollisionNum)-1;   if(CurrentPos>=TabSize)    CurrentPos-=TabSize;    

8、60;     return CurrentPos;/*返回在散列表中的位置*/  圖4 用平方探測法處理沖突3.2怎么操作“ENQUEUE”和“DEQUEUE”命令這可以用隊列來模擬。由于有插隊現(xiàn)象的存在，不能單純地用一個數(shù)組來表示隊列，因為這樣的話，插入一個朋友，則他后面的人都要往后移一個單位，刪除一個人，則他后面的人都要前移一個，會降低效率。所以，采用一個Index標記來表示當前元素的后繼元素，最后一個單元的后繼元素是第0個，形成環(huán)，數(shù)據(jù)結(jié)構(gòu)如圖5所示。不用鏈表是因為鏈表存放指針也需要空間，并且鏈表插入、刪除的效率沒有

9、數(shù)組高。typedef struct Que *PtrToQue; struct Que  long int HashVal;              /*散列值*/   long int Index;          

10、60;     /*在中的隊列序號*/ 圖5 數(shù)據(jù)結(jié)構(gòu)：隊列1）輸入ENQUEUE命令，如果隊伍里有朋友，則排在朋友后面；如果沒有遇到朋友，則排到隊尾。入隊時，用一個數(shù)組記錄每個朋友組的最后一位，以便下一個朋友到來時排到他后面，這個數(shù)組被稱為“插入數(shù)組”。 2）輸入“DEQUEUE”命令，則根據(jù)“先進先出”，按照各個元素和它后繼元素的先后順序，每次刪除隊列中的第一個。程序結(jié)構(gòu)如圖6所示。While(讀測試文件)  if(輸入“ENQUEUE”) 讀入名字； 插入散列表； 插入

11、隊列；  else if(輸入“DEQUEUE”) 刪除隊列第一個名字；  將該名字輸出到文件；  Else stop;  圖6 入隊、出隊操作4、調(diào)試與測試4.1調(diào)試先運行，出現(xiàn)如圖7所示：圖7 運行4.2 測試1）測試輸入23 Ann Bob Joe3 Zoe Jim FatENQUEUE AnnENQUEUE ZoeENQUEUE BobENQUEUE JimENQUEUE JoeENQUEUE FatDEQUEUEDEQUEUEDEQUEUEDEQUEUEDEQUEUEDEQUEUEST

12、OP25 Anny Jack Jean Bill Jane6 Eva Mike Ron Sony Geo ZoroENQUEUE AnnyENQUEUE EvaENQUEUE JackENQUEUE JeanENQUEUE BillENQUEUE JaneDEQUEUEDEQUEUEENQUEUE MikeENQUEUE RonDEQUEUEDEQUEUEDEQUEUEDEQUEUESTOP02）正確輸出Scenario #1AnnBobJoeZoeJimFatScenario #2AnnyJackJeanBillJaneEva4.3實際結(jié)果1）實際輸入圖8 輸入數(shù)據(jù)2）實際輸出圖9 輸出數(shù)據(jù)

13、5、小 結(jié) 在前面的學(xué)習(xí)過程中我們學(xué)到了很多知識,而這次課程設(shè)計又是對我們所學(xué)的一次總結(jié).我們必須掌握很多已學(xué)的知識才能很好的完成本次的課程設(shè)計。在這次課程設(shè)計中,總的感覺是我遇到了很多困難,這主要是由于我編寫代碼的經(jīng)驗不足,有時雖然是一個很小的問題,但解決起來卻花費了我不少的時間,值得欣慰的是,當自己苦思冥想或者和其它同學(xué)一起探討,把問題解決的時候我還是覺得獲益非淺,這就是在摸索中尋求到的知識。設(shè)計期間,我發(fā)現(xiàn)只有有目的的去學(xué)習(xí)一些將要用到的東西,充分的運用所學(xué)知識，才能順利的完成設(shè)計。在設(shè)計時也免不了存在著一些不足，所以在今后的學(xué)習(xí)中我會努力取得更大的進步，對于我不足的地方希望老師能夠及時

14、給予批評，以便我在今后的學(xué)習(xí)中能夠及時的改正。 通過這次課程設(shè)計，我收獲的不僅僅是課程上的知識得到實際應(yīng)用，還有編程的基本習(xí)慣和應(yīng)注意的細節(jié)。6、參考文獻1范策，周世平，胡嘵琨.算法與數(shù)據(jù)結(jié)構(gòu)（C語言版）M. 北京：機械工業(yè)出版社，20042 嚴蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）. 北京：清華大學(xué)出版社，20043 許卓群，楊冬青，唐世渭，張銘. 數(shù)據(jù)結(jié)構(gòu)與算法. 北京：高等教育出版社，20044 徐孝凱. 數(shù)據(jù)結(jié)構(gòu)實用教程（第二版）. 北京：清華大學(xué)出版社，20067、源程序清單#include<stdio.h>#include<malloc.h>#include&

15、lt;string.h>#define TabSize 2000003 /*散列表大小TabSize 是大于表最大空間的素數(shù)*/#define Max 1000001 /*隊列空間最大值*/struct hashtab;typedef struct hashtab *PtrToHash;struct hashtab /*散列表數(shù)據(jù)結(jié)構(gòu)*/char name5; /*名字*/int group; /*屬于哪個朋友組*/char info; /*標志位，該單元是否被占用*/;struct Que;typedef struct Que *PtrToQue;struct Que /*隊列數(shù)據(jù)結(jié)構(gòu)

16、*/long int HashVal; /*散列值*/long int Index; /*在中的隊列序號*/;int hashedx=0; /*標記元素是否已經(jīng)在散列表里*/long int Find(PtrToHash hash,char *c) /*查找在散列表中的位置*/char *key;long int CurrentPos,CollisionNum;key=c;for(CurrentPos=0;*key;+key) /*散列函數(shù)，計算散列值*/CurrentPos=(CurrentPos<<6)+*key;CurrentPos%=TabSize; /*散列值*/Coll

17、isionNum=0;/*如果當前單元被占用：單元內(nèi)的元素與當前操作的名字不同，使用平方探測法解決沖突；與當前操作的名字相同，則直接返回在散列中的位置*/while(hashCurrentP)&&(strcmp(hashCurrentP,c) /*平方探測法*/CurrentPos+=2*(+CollisionNum)-1;if(CurrentPos>=TabSize)CurrentPos-=TabSize; if(hashCurrentP)&&(strcmp(hashCurrentP,c)=0) /

18、*元素已經(jīng)在散列表里*/hashedx=1;else /*元素不在散列表里*/hashedx=0;return CurrentPos;/*返回在散列表中的位置*/int main()long int Find(PtrToHash hash,char *c); /*查找在散列表中的位置*/PtrToHash hash; /*散列表*/PtrToQue queue; /*隊列*/int *grouppos; /*記錄每個朋友組的最后一位，即插隊數(shù)組*/int n; /*測試用例數(shù)目*/int num; /*當前測試用例序號*/long int i,ii,j,key,temp;long int he

19、ad,last; /*隊列的頭和尾*/char c8,tempc8; /*名字*/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;h

20、ash=(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<Max;+i,+j) /*初始化隊列，queuei的后繼單元是queuei1*/queuei.Index=j;queuei-1.Index=0; /*最后一個單元的后繼單元是第0個，形成環(huán)*

21、/num=0;for(fscanf(fpin,"%d",&n);n;fscanf(fpin,"%d",&n)/*輸入當前測試用例的朋友組數(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<TabSize;)hashi+.info=0; /*初始化散列表，標記位

22、置0*/for(i=0;i<n;+i) /*對每一組朋友*/fscanf(fpin,"%d",&j); /*當前組里的人數(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<sizeof(tempc);ii+) /*tempc清空，處理異常輸入名字*/ tempcii='0'strcp

23、y(tempc,c);ii=0;while(tempcii!='0') /* 是否由四個以內(nèi)字母組成*/if(tempcii<'A'|('Z'<tempcii&&tempcii<'a')|tempcii>'z'|ii>4)fprintf(fpout,"Group %d: Nonstandard namen ",i); return -1;ii+;key=Find(hash,c); /*找到在散列表中的位置*/if(hashedx=1) /*重名*/f

24、printf(fpout,"repeated name %sn",c); return -1;strcpy(,c);/*插入散列表*/=1; /*標記置1，該單元被占用*/hashkey.group=i; /*記錄他屬于哪個組*/for(i=0;i<1000;)groupposi+=0; /*初始化插隊數(shù)組*/head=0; /*初始化隊列頭、尾標記*/last=0;fprintf(fpout,"Scenario #%dn",num); /*輸出當前用例序號到文件*/for(fscanf(fpin,&

25、quot;%s",c);fscanf(fpin,"%s",c) /*輸入命令*/if(*c='E') /*入隊命令*/fscanf(fpin,"%s",c); /*輸入名字*/key=Find(hash,c); /*查找在散列表中的位置*/if(hashedx=0) /*散列表里沒這個人*/fprintf(fpout,"no %sn",c); return -1;temp=queue0.Index; /*隊列第0個位置記錄隊尾的后繼單元*/queue0.Index=queuetemp.Index; /*在隊列中申請一個新單元，隊尾標記后移一個位置 */queuetemp.HashVal=key; /*入隊*/if(!head) /*如果是隊列里的第一個元素 */last=head=temp; /*隊頭、隊尾標記指向第一個元素*/if(!groupposhashkey.group) /*如果隊列里沒朋友*/queuetemp.Index=0; /*隊尾指向?qū)︻^，形成環(huán)*/queuelast.Index=temp;/*前一次隊尾的后繼元素是當前元素*/last=temp; /*隊尾標記指向當前元素*/groupposhashkey.group=temp;/*插隊數(shù)組記錄該