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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)插隊(duì)買票專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級XXXXXXXXX學(xué)號XXXXXXXXX學(xué)生姓名XX專心-專注-專業(yè)目 錄1 設(shè)計(jì)題目 春節(jié)前夕,一年一度的運(yùn)輸高潮也開始了,成千上萬的外出人員都往家趕.火車站售票 窗前買票隊(duì)伍一眼望不到頭.運(yùn)氣好的,碰到一個(gè)已經(jīng)在排隊(duì)的朋友,直接走過去,排他后 面,這就叫"插隊(duì)",但對隊(duì)伍里的其他人來說是不公平的.本課程設(shè)計(jì)的任務(wù)是寫一個(gè)程序模擬這種情況.每個(gè)隊(duì)伍都允許插隊(duì).如果你在排隊(duì),有一個(gè)以上的朋友要求插隊(duì),則你可以安排他們的次序.每次一個(gè)人入隊(duì),并且如果這個(gè)入隊(duì)的人發(fā)現(xiàn)隊(duì)伍中有自己的朋友,則可以插入到這個(gè)朋

2、友的后面;當(dāng)隊(duì)伍中的朋友不止一個(gè)的時(shí)候,這個(gè)人會排在最后一個(gè)朋友的后面;如果隊(duì)伍中沒有朋友,則他只能夠排在這個(gè)隊(duì)伍的最后面.每一個(gè)入隊(duì)的人都先進(jìn)行上述的判斷.當(dāng)隊(duì)伍前面的人買到車票之后.依次出隊(duì).2 設(shè)計(jì)分析本題目主要解決兩個(gè)問題：一是怎么存放和查找大量數(shù)據(jù)（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。用散列表來存放和查找數(shù)據(jù)。由于最多有1000個(gè)朋友組，每組最多1000人，使用平方探測法解決沖突，則表的大小至少是2*（1000*1000），所以選擇TableSize=。同一個(gè)組內(nèi)的都是朋友，所以每個(gè)人除了記錄他的名字name，還要記錄他屬于哪個(gè)朋友組group，另外

3、用info來表示該單元是否被占用，數(shù)據(jù)結(jié)構(gòu)如圖所示。散列函數(shù)是根據(jù)Honer法則計(jì)算一個(gè)以64為階的多項(xiàng)式，如圖2。#define TabSize /*散列表大小TabSizetypedef struct hashtab *PtrToHash;struct hashtab /*散列表數(shù)據(jù)結(jié)構(gòu)*/char name5; /*名字*/int group; /*屬于哪個(gè)朋友組*/char info; /*標(biāo)志位，該單元是否被占用*/;數(shù)據(jù)結(jié)構(gòu)：散列表Int Hash(char *key,int TableSize)int HashVal=0;while(key!=NULL) HashVal=(Has

4、hVal<<6)+*key;Return HashVal %TableSize;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)前操作的名字不同，使

5、用平方探測法解決沖突； */while(hashCurrentP)&&(strcmp(hashCurrentP,c) /*平方探測法*/CurrentPos+=2*(+CollisionNum)-1;if(CurrentPos>=TabSize)CurrentPos-=TabSize; if(hashCurrentP)&&(strcmp(hashCurrentP,c)=0) hashedx=1;else /*元素不在散列表里*/hashedx=0;return CurrentPos;/*返回在散列表中

6、的位置*/用平方探測法處理沖突第二個(gè)問題關(guān)于怎么操作“ENQUEUE”和“DEQUEUE”命令。這可以用隊(duì)列來模擬。由于有插隊(duì)現(xiàn)象的存在，不能單純地用一個(gè)數(shù)組來表示隊(duì)列，因?yàn)檫@樣的話，插入一個(gè)朋友，則他后面的人都要往后移一個(gè)單位，刪除一個(gè)人，則他后面的人都要前移一個(gè)，會降低效率。所以，采用一個(gè)Index標(biāo)記來表示當(dāng)前元素的后繼元素，最后一個(gè)單元的后繼元素是第0個(gè)，形成環(huán)，數(shù)據(jù)結(jié)構(gòu)如下圖所示。不用鏈表是因?yàn)殒湵泶娣胖羔樢残枰臻g，并且鏈表插入、刪除的效率沒有數(shù)組高。typedef struct Que *PtrToQue;struct Quelong int HashVal; /*散列值*/lo

7、ng int Index; /*在中的隊(duì)列序號*/;數(shù)據(jù)結(jié)構(gòu)：隊(duì)列輸入ENQUEUE命令，如果隊(duì)伍里有朋友，則排在朋友后面；如果沒有遇到朋友，則排到隊(duì)尾。入隊(duì)時(shí)，用一個(gè)數(shù)組記錄每個(gè)朋友組的最后一位，以便下一個(gè)朋友到來時(shí)排到他后面，這個(gè)數(shù)組被稱為“插入數(shù)組”。輸入“DEQUEUE”命令，則根據(jù)“先進(jìn)先出”，按照各個(gè)元素和它后繼元素的先后順序，每次刪除隊(duì)列中的第一個(gè)。程序結(jié)構(gòu)如下圖所示。While(讀測試文件)if(輸入“ENQUEUE”)讀入名字；插入散列表；插入隊(duì)列；else if(輸入“DEQUEUE”)刪除隊(duì)列第一個(gè)名字；將該名字輸出到文件；Else stop;入隊(duì)、出隊(duì)操作3 設(shè)計(jì)實(shí)現(xiàn)#

8、include<stdio.h>#include<malloc.h>#include<string.h>#define TabSize /*散列表大小TabSize 是大于表最大空間的素?cái)?shù)*/#define Max /*隊(duì)列空間最大值*/struct hashtab;typedef struct hashtab *PtrToHash;struct hashtab /*散列表數(shù)據(jù)結(jié)構(gòu)*/char name5; /*名字*/int group; /*屬于哪個(gè)朋友組*/char info; /*標(biāo)志位，該單元是否被占用*/;struct Que;typedef s

9、truct 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

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

11、amp;(strcmp(hashCurrentP,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; /*記錄每個(gè)朋友組的最后一位，即插隊(duì)數(shù)組*/int n; /*測試用例數(shù)目*/int num; /*當(dāng)前測試用例序

12、號*/long int i,ii,j,key,temp;long int head,last; /*隊(duì)列的頭和尾*/char c8,tempc8; /*名字*/FILE *fpin,*fpout; /*輸入、輸出文件指針*/ if(!(fpin=fopen("input.txt","r") /*打開測試文件*/printf("fopen error!"); /*文件打開錯(cuò)誤*/return -1;if(!(fpout=fopen("output.txt","w") /*打開輸出文件*/print

13、f("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); /*申請空間記錄每個(gè)朋友組的最后一位*/for(i=0,j=1;i<Max;+i,+j) /*初始化隊(duì)列，queuei的后繼單元是queuei1*/queuei.Index=j;q

14、ueuei-1.Index=0; /*最后一個(gè)單元的后繼單元是第0個(gè)，形成環(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) /*兩個(gè)測試用例間輸入一空行*/fprintf(fpout,"n");for(i=0;i&

15、lt;TabSize;)hashi+.info=0; /*初始化散列表，標(biāo)記位置0*/for(i=0;i<n;+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<sizeof(tempc);ii+) /*temp

16、c清空，處理異常輸入名字*/ tempcii='0'strcpy(tempc,c);ii=0;while(tempcii!='0') /* 是否由四個(gè)以內(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,

17、c); /*找到在散列表中的位置*/if(hashedx=1) /*重名*/fprintf(fpout,"repeated name %sn",c); return -1;strcpy(,c);/*插入散列表*/=1; /*標(biāo)記置1，該單元被占用*/hashkey.group=i; /*記錄他屬于哪個(gè)組*/for(i=0;i<1000;)groupposi+=0; /*初始化插隊(duì)數(shù)組*/head=0; /*初始化隊(duì)列頭、尾標(biāo)記*/last=0;fprintf(fpout,"Scenario #%dn"

18、,num); /*輸出當(dāng)前用例序號到文件*/for(fscanf(fpin,"%s",c);fscanf(fpin,"%s",c) /*輸入命令*/if(*c='E') /*入隊(duì)命令*/fscanf(fpin,"%s",c); /*輸入名字*/key=Find(hash,c); /*查找在散列表中的位置*/if(hashedx=0) /*散列表里沒這個(gè)人*/fprintf(fpout,"no %sn",c); return -1;temp=queue0.Index; /*隊(duì)列第0個(gè)位置記錄隊(duì)尾的后繼

19、單元*/queue0.Index=queuetemp.Index; /*在隊(duì)列中申請一個(gè)新單元，隊(duì)尾標(biāo)記后移一個(gè)位置 */queuetemp.HashVal=key; /*入隊(duì)*/if(!head) /*如果是隊(duì)列里的第一個(gè)元素 */last=head=temp; /*隊(duì)頭、隊(duì)尾標(biāo)記指向第一個(gè)元素*/if(!groupposhashkey.group) /*如果隊(duì)列里沒朋友*/queuetemp.Index=0; /*隊(duì)尾指向?qū)︻^，形成環(huán)*/queuelast.Index=temp;/*前一次隊(duì)尾的后繼元素是當(dāng)前元素*/last=temp; /*隊(duì)尾標(biāo)記指向當(dāng)前元素*/groupposhash

20、key.group=temp;/*插隊(duì)數(shù)組記錄該朋友組里已入隊(duì)的最后一位*/else/*如果隊(duì)列中已經(jīng)有他的朋友*/queuetemp.Index=queuegroupposhashkey.group.Index;/*插隊(duì)到朋友的后面*/queuegroupposhashkey.group.Index=temp; /*插隊(duì)到朋友后面一位的前面*/groupposhashkey.group=temp;/*替換插隊(duì)數(shù)組里該組的元素為當(dāng)前元素*/if(hashqueuelast.HashVal.group=hashkey.group)/*如果當(dāng)前元素和前一元素是朋友，隊(duì)尾標(biāo)志指向當(dāng)前元素*/last

21、=temp;else if(*c='D') /*出隊(duì)命令*/if(last=0) /*不能對空隊(duì)列執(zhí)行出隊(duì)命令*/fprintf(fpout,"Empty queue!nCan't execute DEQUEUE!n");return -1;fprintf(fpout,"%sn",hashqueuehead.HashV);/*輸出隊(duì)頭元素到文件*/temp=head;head=queuetemp.Index; /*隊(duì)列第一位出隊(duì)，隊(duì)頭標(biāo)記后移一位*/queuetemp.Index=queue0.Index; /*隊(duì)列

22、第0個(gè)元素后移一位*/queue0.Index=temp; /*釋放空間*/if(groupposhashqueuetemp.HashVal.group=temp) /*當(dāng)前刪除的元素是該朋友組在隊(duì)列里的最后一位*/groupposhashqueuetemp.HashVal.group=0;if(last=temp) /*出隊(duì)后，隊(duì)列為空*/last=0;else /*輸入 "STOP"*/break; /*測試結(jié)束*/fprintf(fpout,"b");fclose(fpin);fclose(fpout);return 1;4測試方法4.1測試目的目

23、的是為了每個(gè)隊(duì)伍都允許插隊(duì)，如果你在排隊(duì)，有一個(gè)以上的朋友要求插隊(duì)，則你可以安排他們的次序。每次一個(gè)人入隊(duì)，并且如果這個(gè)入隊(duì)的人發(fā)現(xiàn)隊(duì)伍中有自己的朋友，則可以插到朋友后面，當(dāng)隊(duì)伍中的朋友不止一個(gè)得時(shí)候，這個(gè)人會排在最后一個(gè)朋友的后面，如果隊(duì)伍中沒有朋友，則他只能排在最后面，每一個(gè)人的人都先進(jìn)行上述的判斷。4.2 測試輸入23 Ann Bob Joe3 Zoe Jim FatENQUEUE AnnENQUEUE ZoeENQUEUE JimENQUEUE JoeENQUEUE FatDEQUEUEDEQUEUEDEQUEUEDEQUEUESTOP25 Anny Jack Jean Bill Jane6 Eva M