《数据结构课程设计-插队买票(共15页).doc》由会员分享，可在线阅读，更多相关《数据结构课程设计-插队买票(共15页).doc（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上数据结构课程设计插队买票专业计算机科学与技术班级XXXXXXXXX学号XXXXXXXXX学生姓名XX专心-专注-专业目 录1 设计题目 春节前夕,一年一度的运输高潮也开始了,成千上万的外出人员都往家赶.火车站售票 窗前买票队伍一眼望不到头.运气好的,碰到一个已经在排队的朋友,直接走过去,排他后 面,这就叫插队,但对队伍里的其他人来说是不公平的.本课程设计的任务是写一个程序模拟这种情况.每个队伍都允许插队.如果你在排队,有一个以上的朋友要求插队,则你可以安排他们的次序.每次一个人入队,并且如果这个入队的人发现队伍中有自己的朋友,则可以插入到这个朋友的后面;当队伍中的朋友
2、不止一个的时候,这个人会排在最后一个朋友的后面;如果队伍中没有朋友,则他只能够排在这个队伍的最后面.每一个入队的人都先进行上述的判断.当队伍前面的人买到车票之后.依次出队.2 设计分析本题目主要解决两个问题：一是怎么存放和查找大量数据（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。用散列表来存放和查找数据。由于最多有1000个朋友组，每组最多1000人，使用平方探测法解决冲突，则表的大小至少是2*（1000*1000），所以选择TableSize=。同一个组内的都是朋友，所以每个人除了记录他的名字name，还要记录他属于哪个朋友组group，另外用info来表示该单元是
3、否被占用，数据结构如图所示。散列函数是根据Honer法则计算一个以64为阶的多项式，如图2。#define TabSize /*散列表大小TabSizetypedef struct hashtab *PtrToHash;struct hashtab /*散列表数据结构*/char name5; /*名字*/int group; /*属于哪个朋友组*/char info; /*标志位，该单元是否被占用*/;数据结构：散列表Int Hash(char *key,int TableSize)int HashVal=0;while(key!=NULL) HashVal=(HashVal6)+*key;
4、Return HashVal %TableSize;long int Find(PtrToHash hash,char *c) /*查找在散列表中的位置*/char *key;long int CurrentPos,CollisionNum;key=c;for(CurrentPos=0;*key;+key) /*散列函数，计算散列值*/CurrentPos=(CurrentPos=TabSize)CurrentPos-=TabSize; if(hashCurrentPos.info)&(strcmp(hashCurrentPos.name,c)=0) hashedx=1;else /*元素不在
5、散列表里*/hashedx=0;return CurrentPos;/*返回在散列表中的位置*/用平方探测法处理冲突第二个问题关于怎么操作“ENQUEUE”和“DEQUEUE”命令。这可以用队列来模拟。由于有插队现象的存在，不能单纯地用一个数组来表示队列，因为这样的话，插入一个朋友，则他后面的人都要往后移一个单位，删除一个人，则他后面的人都要前移一个，会降低效率。所以，采用一个Index标记来表示当前元素的后继元素，最后一个单元的后继元素是第0个，形成环，数据结构如下图所示。不用链表是因为链表存放指针也需要空间，并且链表插入、删除的效率没有数组高。typedef struct Que *Ptr
6、ToQue;struct Quelong int HashVal; /*散列值*/long int Index; /*在中的队列序号*/;数据结构：队列输入ENQUEUE命令，如果队伍里有朋友，则排在朋友后面；如果没有遇到朋友，则排到队尾。入队时，用一个数组记录每个朋友组的最后一位，以便下一个朋友到来时排到他后面，这个数组被称为“插入数组”。输入“DEQUEUE”命令，则根据“先进先出”，按照各个元素和它后继元素的先后顺序，每次删除队列中的第一个。程序结构如下图所示。While(读测试文件)if(输入“ENQUEUE”)读入名字；插入散列表；插入队列；else if(输入“DEQUEUE”)删
7、除队列第一个名字；将该名字输出到文件；Else stop;入队、出队操作3 设计实现#include#include#include#define TabSize /*散列表大小TabSize 是大于表最大空间的素数*/#define Max /*队列空间最大值*/struct hashtab;typedef struct hashtab *PtrToHash;struct hashtab /*散列表数据结构*/char name5; /*名字*/int group; /*属于哪个朋友组*/char info; /*标志位，该单元是否被占用*/;struct Que;typedef struc
8、t 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=TabSize)Curr
9、entPos-=TabSize; if(hashCurrentPos.info)&(strcmp(hashCurrentPos.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; /*记录每个朋友组的最后一位，即插队数组
10、*/int n; /*测试用例数目*/int num; /*当前测试用例序号*/long int i,ii,j,key,temp;long int head,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
11、-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;iMax;+i,+j) /*初始化队列，queuei的后继单元是queuei1*/queuei.Index=j;queuei-1.Index=0; /*最后一个单元的后继单元是第0个，形成环*
12、/num=0;for(fscanf(fpin,%d,&n);n;fscanf(fpin,%d,&n)/*输入当前测试用例的朋友组数*/ if(n1000) /*处理异常输入n*/ fprintf(fpout,n is out of rangen); return -1;num+;if(num!=1) /*两个测试用例间输入一空行*/fprintf(fpout,n);for(i=0;iTabSize;)hashi+.info=0; /*初始化散列表，标记位置0*/for(i=0;in;+i) /*对每一组朋友*/fscanf(fpin,%d,&j); /*当前组里的人数*/ if(j1000)
13、/*处理异常输入j*/ fprintf(fpout,j is out of rangen); return -1;for(;j;-j)fscanf(fpin,%s,c); /*输入名字*/ for(ii=0;iisizeof(tempc);ii+) /*tempc清空，处理异常输入名字*/ tempcii=0;strcpy(tempc,c);ii=0;while(tempcii!=0) /* 是否由四个以内字母组成*/if(tempciiA|(Ztempcii&tempciiz|ii4)fprintf(fpout,Group %d: Nonstandard namen ,i); return
14、-1;ii+;key=Find(hash,c); /*找到在散列表中的位置*/if(hashedx=1) /*重名*/fprintf(fpout,repeated name %sn,c); return -1;strcpy(hashkey.name,c);/*插入散列表*/hashkey.info=1; /*标记置1，该单元被占用*/hashkey.group=i; /*记录他属于哪个组*/for(i=0;i1000;)groupposi+=0; /*初始化插队数组*/head=0; /*初始化队列头、尾标记*/last=0;fprintf(fpout,Scenario #%dn,num);
15、/*输出当前用例序号到文件*/for(fscanf(fpin,%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; /*在队列中申请一个新单元，队尾标记后移一个位置 */queu
16、etemp.HashVal=key; /*入队*/if(!head) /*如果是队列里的第一个元素 */last=head=temp; /*队头、队尾标记指向第一个元素*/if(!groupposhashkey.group) /*如果队列里没朋友*/queuetemp.Index=0; /*队尾指向对头，形成环*/queuelast.Index=temp;/*前一次队尾的后继元素是当前元素*/last=temp; /*队尾标记指向当前元素*/groupposhashkey.group=temp;/*插队数组记录该朋友组里已入队的最后一位*/else/*如果队列中已经有他的朋友*/queuete
17、mp.Index=queuegroupposhashkey.group.Index;/*插队到朋友的后面*/queuegroupposhashkey.group.Index=temp; /*插队到朋友后面一位的前面*/groupposhashkey.group=temp;/*替换插队数组里该组的元素为当前元素*/if(hashqueuelast.HashVal.group=hashkey.group)/*如果当前元素和前一元素是朋友，队尾标志指向当前元素*/last=temp;else if(*c=D) /*出队命令*/if(last=0) /*不能对空队列执行出队命令*/fprintf(fp
18、out,Empty queue!nCant execute DEQUEUE!n);return -1;fprintf(fpout,%sn,hashqueuehead.HashVal.name);/*输出队头元素到文件*/temp=head;head=queuetemp.Index; /*队列第一位出队，队头标记后移一位*/queuetemp.Index=queue0.Index; /*队列第0个元素后移一位*/queue0.Index=temp; /*释放空间*/if(groupposhashqueuetemp.HashVal.group=temp) /*当前删除的元素是该朋友组在队列里的最后
19、一位*/groupposhashqueuetemp.HashVal.group=0;if(last=temp) /*出队后，队列为空*/last=0;else /*输入 STOP*/break; /*测试结束*/fprintf(fpout,b);fclose(fpin);fclose(fpout);return 1;4测试方法4.1测试目的目的是为了每个队伍都允许插队，如果你在排队，有一个以上的朋友要求插队，则你可以安排他们的次序。每次一个人入队，并且如果这个入队的人发现队伍中有自己的朋友，则可以插到朋友后面，当队伍中的朋友不止一个得时候，这个人会排在最后一个朋友的后面，如果队伍中没有朋友，则
20、他只能排在最后面，每一个人的人都先进行上述的判断。4.2 测试输入23 Ann Bob Joe3 Zoe Jim FatENQUEUE AnnENQUEUE ZoeENQUEUE JimENQUEUE JoeENQUEUE FatDEQUEUEDEQUEUEDEQUEUEDEQUEUESTOP25 Anny Jack Jean Bill Jane6 Eva Mike Ron Sony Geo ZoroENQUEUE AnnyENQUEUE EvaENQUEUE JackENQUEUE MikeENQUEUE BillENQUEUE JaneDEQUEUEDEQUEUEENQUEUE SonyE
21、NQUEUE GeoDEQUEUEDEQUEUEDEQUEUEDEQUEUEDEQUEUESTOP04.3 正确输出Scenario #1AnnJoeZoeJimScenario #2AnnyJackBillJaneEvaMikeSony4.4 实际输出 5 分析与探讨5.1 测试结果分析 上面的测试方法中进行了4次特殊情况的测试，所得出的结果均与预测结果一致。此次试验很成功，各方面的问题都想到，一些小的错误也被很好的解决掉了。5.2 探讨与改进在试验过程中，我们还需加强动手能力，在最短的时间内完成好程序代码的编写和调试，做到又快又好的完成课程设计。6 设计小结在前面的学习过程中我们学到了很多
22、知识,而这次课程设计又是对我们所学的一次总结.我们必须掌握很多已学的知识才能很好的完成本次的课程设计。在这次课程设计中,总的感觉是我遇到了很多困难,这主要是由于我编写代码的经验不足,有时虽然是一个很小的问题,但解决起来却花费了我不少的时间,值得欣慰的是,当自己苦思冥想或者和其它同学一起探讨,把问题解决的时候我还是觉得获益非浅,这就是在摸索中寻求到的知识。设计期间,我发现只有有目的的去学习一些将要用到的东西,充分的运用所学知识，才能顺利的完成设计。在设计时也免不了存在着一些不足，所以在今后的学习中我会努力取得更大的进步，对于我不足的地方希望老师能够及时给予批评，以便我在今后的学习中能够及时的改正。通过这次课程设计，我收获的不仅仅是课程上的知识得到实际应用，还有编程的基本习惯和应注意的细节。