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

《数据结构课程设计插队买票》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计——散列表的应用：插入买票数据结构课程设计插队买票专业计算机科学与技术班级XXXXXXXXX学号XXXXXXXXX学生姓名XX1数据结构课程设计——散列表的应用：插入买票目录1设计题目12设计分析13设计实现34测试方法104.1测试目的104.2测试输入104.3正确输出114.4实际输出125分析与探讨125.1测试结果分析125.2探讨与改进126设计小结121数据结构课程设计——散列表的应用：插入买票1设计题目春节前夕,一年一度的运输高潮也开始了,成千上万的外出人员都往家赶.火车站售

2、票窗前买票队伍一眼望不到头.运气好的,碰到一个已经在排队的朋友,直接走过去,排他后面,这就叫"插队",但对队伍里的其他人来说是不公平的.本课程设计的任务是写一个程序模拟这种情况.每个队伍都允许插队.如果你在排队,有一个以上的朋友要求插队,则你可以安排他们的次序.每次一个人入队,并且如果这个入队的人发现队伍中有自己的朋友,则可以插入到这个朋友的后面;当队伍中的朋友不止一个的时候,这个人会排在最后一个朋友的后面;如果队伍中没有朋友,则他只能够排在这个队伍的最后面.每一个入队的人都先进行上述的判断.当队伍前面的人

3、买到车票之后.依次出队.2设计分析本题目主要解决两个问题：一是怎么存放和查找大量数据（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。用散列表来存放和查找数据。由于最多有1000个朋友组，每组最多1000人，使用平方探测法解决冲突，则表的大小至少是2*（1000*1000），所以选择TableSize=2000003。同一个组内的都是朋友，所以每个人除了记录他的名字name，还要记录他属于哪个朋友组group，另外用info来表示该单元是否被占用，数据结构如图所示。散列函数是根据Hon

4、er法则计算一个以64为阶的多项式，如图2。#defineTabSize2000003/*散列表大小TabSizetypedefstructhashtab*PtrToHash;structhashtab/*散列表数据结构*/{charname[5];/*名字*/intgroup;/*属于哪个朋友组*/charinfo;/*标志位，该单元是否被占用*/};数据结构：散列表IntHash(char*key,intTableSize){intHashVal=0;while(key!=NULL)13数据结构课程设计

5、——散列表的应用：插入买票HashVal=(HashVal<<6)+*key;ReturnHashVal%TableSize;}longintFind(PtrToHashhash,char*c)/*查找在散列表中的位置*/{char*key;longintCurrentPos,CollisionNum;key=c;for(CurrentPos=0;*key;++key)/*散列函数，计算散列值*/CurrentPos=(CurrentPos<<6)+*key;CurrentPos%=TabSize;/*散列

6、值*/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[Cu

7、rrentPos].name,c)==0))hashedx=1;else/*元素不在散列表里*/hashedx=0;returnCurrentPos;/*返回在散列表中的位置*/}用平方探测法处理冲突第二个问题关于怎么操作“ENQUEUE”和“DEQUEUE”13数据结构课程设计——散列表的应用：插入买票命令。这可以用队列来模拟。由于有插队现象的存在，不能单纯地用一个数组来表示队列，因为这样的话，插入一个朋友，则他后面的人都要往后移一个单位，删除一个人，则他后面的人都要前移一个，会降低效率。所以，采用一个I

8、ndex标记来表示当前元素的后继元素，最后一个单元的后继元素是第0个，形成环，数据结构如下图所示。不用链表是因为链表存放指针也需要空间，并且链表插入、删除的效率没有数组高。typedefstructQue*PtrToQue;structQue{longintHashVal;/*散列值*/longintIndex;/*在中的队列序号*/};数据结构：队列输入ENQUEUE命令，如果队伍里有朋友，则排在朋友后面；如果