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

数据结构课程设计报告插队买票专业学生姓名班级学号指导教师完成日期2015年1月24日目录1、设计题目.........................................错误!未定义书签。2、课题目的及要求....................................................13、设计分析.........................................错误!未定义书签。4、调试与测试........................................................45、小结............................................................76、参考文献..........................................................77、源程序清单........................................................7数据结构课程设计1数据结构课程的设计1、设计题目春节前夕,一年一度的运输高潮也开始了,成千上万的外出人员都往家赶.火车站售票窗前买票队伍一眼望不到头.运气好的,碰到一个已经在排队的朋友,直接走过去,排他后面,这就叫插队,但对队伍里的其他人来说是不公平的.本课程设计的任务是写一个程序模拟这种情况.每个队伍都允许插队.如果你在排队,有一个以上的朋友要求插队,则你可以安排他们的次序.每次一个人入队,并且如果这个入队的人发现队伍中有自己的朋友,则可以插入到这个朋友的后面;当队伍中的朋友不止一个的时候,这个人会排在最后一个朋友的后面;如果队伍中没有朋友,则他只能够排在这个队伍的最后面.每一个入队的人都先进行上述的判断.当队伍前面的人买到车票之后.依次出队.2、课题目的及要求2.1目的：数据结构课程设计是为数据结构课程独立开设的实践性教学环节。数据结构课程设计对于巩固数据结构知识，加强学生的实际动手能力和提高学生综合素质是十分必要的。本题目主要解决两个问题：一是怎么存放和查找大量数据（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。2.2要求：1）输入要求：程序从“input.txt”文件读入测试用例，一个文件可包含多个测试用例。每个用例的第一行是朋友组的数目n（1=n=1000).对于一个朋友组以朋友的数目j(1=j=1000)开始，由朋友的个数以及他们的名字组成，一个空格后接该组朋友的名字，以空格分开，并且每个人的名字都不同。每个名字不超过4个字母，由{A,B,…,Z,a,b,…,z}组成。一个朋友组最多有1000个人，每个人只属于一个朋友组。n=0时，测试数据结束。下面是一些具体命令：ENQUEUEX——X入队DEQUEUE——排队头的人买票，离开队伍，即出队STOP——一个测用例结束2）、输出要求：测试结果输出到“output.txt”文件中。每个测试用例的第一行输出“Scenario#k”，k是测试用例的序号（从1开始）。对每一个DEQUEUE命令，输出刚买票离开队伍的人名。两个测试用例之间隔一空行，最后一个用例结束不输出空行。3、设计分析插队买票系统2图1系统总图3.1用散列表来存放和查找数据由于最多有1000个朋友组，每组最多1000人，使用平方探测法解决冲突，则表的大小至少是2*（1000*1000），所以选择TableSize=2000003。同一个组内的都是朋友，所以每个人除了记录他的名字name，还要记录他属于哪个朋友组group，另外用info来表示该单元是否被占用，数据结构如图2所示。散列函数是根据Honer法则计算一个以64为阶的多项式，如图3所示。冲突解决方法采用平方探测法，如图4所示。#defineTabSize2000003typedefstructhashtab*PtrToHash;structhashtab{charname[5];intgroup;charinfo;/*用来表示该单元是否被占用*/};图2数据结构：散列表intHash(char*key,intTableSize){intHashVal=0;while(key!=NULL)HashVal=(HashVal6)+*key;ReturnHashVal%TableSize;}图3散列函数数据结构课程设计3longintFind(PtrToHashhash,char*c){key=c;CurrentPos=Hash(key,TabSize);/*计算散列值*/CollisionNum=0;while((单元被占用)and(单元内的名字与查找的名字不同))/*发生冲突*/{/*平方探测法*/CurrentPos+=2*(++CollisionNum)-1;if(CurrentPos=TabSize)CurrentPos-=TabSize;}returnCurrentPos;/*返回在散列表中的位置*/}图4用平方探测法处理冲突3.2怎么操作“ENQUEUE”和“DEQUEUE”命令这可以用队列来模拟。由于有插队现象的存在，不能单纯地用一个数组来表示队列，因为这样的话，插入一个朋友，则他后面的人都要往后移一个单位，删除一个人，则他后面的人都要前移一个，会降低效率。所以，采用一个Index标记来表示当前元素的后继元素，最后一个单元的后继元素是第0个，形成环，数据结构如图5所示。不用链表是因为链表存放指针也需要空间，并且链表插入、删除的效率没有数组高。typedefstructQue*PtrToQue;structQue{longintHashVal;/*散列值*/longintIndex;/*在中的队列序号*/};图5数据结构：队列1）输入ENQUEUE命令，如果队伍里有朋友，则排在朋友后面；如果没有遇到朋友，则排到队尾。入队时，用一个数组记录每个朋友组的最后一位，以便下一个朋友到来时排到他后面，这个数组被称为“插入数组”。2）输入“DEQUEUE”命令，则根据“先进先出”，按照各个元素和它后继元素的先后顺序，每次删除队列中的第一个。程序结构如图6所示。插队买票系统4While(读测试文件){if(输入“ENQUEUE”){读入名字；插入散列表；插入队列；}elseif(输入“DEQUEUE”){删除队列第一个名字；将该名字输出到文件；}Elsestop;}图6入队、出队操作4、调试与测试4.1调试先运行，出现如图7所示：图7运行4.2测试1）测试输入数据结构课程设计523AnnBobJoe3ZoeJimFatENQUEUEAnnENQUEUEZoeENQUEUEBobENQUEUEJimENQUEUEJoeENQUEUEFatDEQUEUEDEQUEUEDEQUEUEDEQUEUEDEQUEUEDEQUEUESTOP25AnnyJackJeanBillJane6EvaMikeRonSonyGeoZoroENQUEUEAnnyENQUEUEEvaENQUEUEJackENQUEUEJeanENQUEUEBillENQUEUEJaneDEQUEUEDEQUEUEENQUEUEMikeENQUEUERonDEQUEUEDEQUEUEDEQUEUEDEQUEUESTOP0插队买票系统62）正确输出Scenario#1AnnBobJoeZoeJimFatScenario#2AnnyJackJeanBillJaneEva4.3实际结果1）实际输入图8输入数据2）实际输出数据结构课程设计7图9输出数据5、小结在前面的学习过程中我们学到了很多知识,而这次课程设计又是对我们所学的一次总结.我们必须掌握很多已学的知识才能很好的完成本次的课程设计。在这次课程设计中,总的感觉是我遇到了很多困难,这主要是由于我编写代码的经验不足,有时虽然是一个很小的问题,但解决起来却花费了我不少的时间,值得欣慰的是,当自己苦思冥想或者和其它同学一起探讨,把问题解决的时候我还是觉得获益非浅,这就是在摸索中寻求到的知识。设计期间,我发现只有有目的的去学习一些将要用到的东西,充分的运用所学知识，才能顺利的完成设计。在设计时也免不了存在着一些不足，所以在今后的学习中我会努力取得更大的进步，对于我不足的地方希望老师能够及时给予批评，以便我在今后的学习中能够及时的改正。通过这次课程设计，我收获的不仅仅是课程上的知识得到实际应用，还有编程的基本习惯和应注意的细节。6、参考文献[1]范策，周世平，胡哓琨.《算法与数据结构（C语言版）》[M].北京：机械工业出版社，2004[2]严蔚敏.《数据结构（C语言版）》.北京：清华大学出版社，2004[3]许卓群，杨冬青，唐世渭，张铭.《数据结构与算法》.北京：高等教育出版社，2004[4]徐孝凯.《数据结构实用教程（第二版）》.北京：清华大学出版社，20067、源程序清单#includestdio.h#includemalloc.h#includestring.h#defineTabSize2000003/*散列表大小TabSize是大于表最大空间的素数*/插队买票系统8#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))){/*平方探测法*/CurrentPos+=2*(++CollisionNum)-1;if(CurrentPos=TabSize)CurrentPos-=TabSize;}if((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)==0))/*元素已经在散列表里*/数据结构课程设计9hashedx=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(