数据结构课程设计 插队买票

数据结构课程设计插队买票专业计算机科学与技术班级XXXXXXXXX学号XXXXXXXXX学生姓名XX数据结构课程设计——散列表的应用：插入买票目录1设计题目...................................................................................................................12设计分析.................................................................................................................13设计实现.................................................................................................................34测试方法...............................................................................................................104.1测试目的............................................................................................................104.2测试输入...........................................................................................................104.3正确输出...........................................................................................................114.4实际输出...........................................................................................................125分析与探讨...........................................................................................................125.1测试结果分析...................................................................................................125.2探讨与改进.......................................................................................................126设计小结...............................................................................................................12数据结构课程设计——散列表的应用：插入买票11设计题目春节前夕,一年一度的运输高潮也开始了,成千上万的外出人员都往家赶.火车站售票窗前买票队伍一眼望不到头.运气好的,碰到一个已经在排队的朋友,直接走过去,排他后面,这就叫插队,但对队伍里的其他人来说是不公平的.本课程设计的任务是写一个程序模拟这种情况.每个队伍都允许插队.如果你在排队,有一个以上的朋友要求插队,则你可以安排他们的次序.每次一个人入队,并且如果这个入队的人发现队伍中有自己的朋友,则可以插入到这个朋友的后面;当队伍中的朋友不止一个的时候,这个人会排在最后一个朋友的后面;如果队伍中没有朋友,则他只能够排在这个队伍的最后面.每一个入队的人都先进行上述的判断.当队伍前面的人买到车票之后.依次出队.2设计分析本题目主要解决两个问题：一是怎么存放和查找大量数据（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。用散列表来存放和查找数据。由于最多有1000个朋友组，每组最多1000人，使用平方探测法解决冲突，则表的大小至少是2*（1000*1000），所以选择TableSize=2000003。同一个组内的都是朋友，所以每个人除了记录他的名字name，还要记录他属于哪个朋友组group，另外用info来表示该单元是否被占用，数据结构如图所示。散列函数是根据Honer法则计算一个以64为阶的多项式，如图2。#defineTabSize2000003/*散列表大小TabSizetypedefstructhashtab*PtrToHash;structhashtab/*散列表数据结构*/{charname[5];/*名字*/intgroup;/*属于哪个朋友组*/charinfo;/*标志位，该单元是否被占用*/};数据结构：散列表IntHash(char*key,intTableSize){intHashVal=0;while(key!=NULL)数据结构课程设计——散列表的应用：插入买票2HashVal=(HashVal6)+*key;ReturnHashVal%TableSize;}longintFind(PtrToHashhash,char*c)/*查找在散列表中的位置*/{char*key;longintCurrentPos,CollisionNum;key=c;for(CurrentPos=0;*key;++key)/*散列函数，计算散列值*/CurrentPos=(CurrentPos6)+*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;returnCurrentPos;/*返回在散列表中的位置*/}用平方探测法处理冲突第二个问题关于怎么操作“ENQUEUE”和“DEQUEUE”命令。这可以用队列来模拟。由于有插队现象的存在，不能单纯地用一个数组来表示队列，因为这样的话，插入一个朋友，则他后面的人都要往后移一个单位，删除一个人，则他后面的人都要前移一个，会降低效率。所以，采用一个Index标记来表示当前元素的后继元素，最后一个单元的后继元素是第0个，形成环，数据结构如下图所示。不用链表是因数据结构课程设计——散列表的应用：插入买票3为链表存放指针也需要空间，并且链表插入、删除的效率没有数组高。typedefstructQue*PtrToQue;structQue{longintHashVal;/*散列值*/longintIndex;/*在中的队列序号*/};数据结构：队列输入ENQUEUE命令，如果队伍里有朋友，则排在朋友后面；如果没有遇到朋友，则排到队尾。入队时，用一个数组记录每个朋友组的最后一位，以便下一个朋友到来时排到他后面，这个数组被称为“插入数组”。输入“DEQUEUE”命令，则根据“先进先出”，按照各个元素和它后继元素的先后顺序，每次删除队列中的第一个。程序结构如下图所示。While(读测试文件){if(输入“ENQUEUE”){读入名字；插入散列表；插入队列；}elseif(输入“DEQUEUE”){删除队列第一个名字；将该名字输出到文件；}Elsestop;}入队、出队操作3设计实现#includestdio.h#includemalloc.h#includestring.h#defineTabSize2000003/*散列表大小TabSize是大于表最大空数据结构课程设计——散列表的应用：插入买票4间的素数*/#defineMax1000001/*队列空间最大值*/structhashtab;typedefstructhashtab*PtrToHash;structhashtab/*散列表数据结构*/{charname[5];/*名字*/intgroup;/*属于哪个朋友组*/charinfo;/*标志位，该单元是否被占用*/};structQue;typedefstructQue*PtrToQue;structQue/*队列数据结构*/{longintHashVal;/*散列值*/longintIndex;/*在中的队列序号*/};inthashedx=0;/*标记元素是否已经在散列表里*/longintFind(PtrToHashhash,char*c)/*查找在散列表中的位置*/{char*key;longintCurrentPos,CollisionNum;key=c;for(CurrentPos=0;*key;++key)/*散列函数，计算散列值*/CurrentPos=(CurrentPos6)+*key;CurrentPos%=TabSize;/*散列值*/CollisionNum=0;/*如果当前单元被占用：单元内的元素与当前操作的名字不同，使用平方探测法解决冲突；与当前操作的名字相同，则直接返回在散列中的位置*/while((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)))数据结构课程设计——散列表的应用：插入买票5{/*平方探测法*/CurrentPos+=2*(++CollisionNum)-1;if(CurrentPos=TabSize)CurrentPos-=TabSize;}if((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)==0))/*元素已经在散列表里*/hashedx=1;else/*元素不在散列表里*/hashedx=0;returnCurrentPos;/*返回在散列表中的位置*/}intmain(){longintFind(PtrToHashhash,char*c);/*查找在散列表中的位置*/PtrToHashhash;/*散列表*/PtrToQuequeue;/*队列*/int*grouppos;/*记录每个朋友组的最后一位，即插队数组*/intn;/*测试用例数目*/intnum;/*当前测试用例序号*/longinti,ii,j,key,temp;longinthead,last;/*队列的头和尾*/charc[8],tempc[8];/*名字*/FILE*fpin,*fpout;/*输入、输出文件指针*/if(!(fpin=fopen(input.txt,r)))/*打开测试文件*/{printf(fopenerror!);/*文件打开错误*/return-1;数据结构课程设计——散列表的应用：插入买票6}if(!(fpout=fopen(output.txt,w)))/*打开输出文件*/{printf(fopenerror!);return-1;}hash=(PtrToHash)malloc(