文档介绍：.:..、设计题目 12、课题目的及要求 1_Toc224013、设计分析 44、调试与测试 45、小结 76、参考文献 87、源程序清单 、设计题目春节前夕,一年一度的运输高潮也开始了,,碰到一个已经在排队的朋友,直接走过去,排他后面,这就叫"插队",,有一个以上的朋友要求插队,,并且如果这个入队的人发现队伍中有自己的朋友,则可以插入到这个朋友的后面;当队伍中的朋友不止一个的时候,这个人会排在最后一个朋友的后面;如果队伍中没有朋友,、:数据结构课程设计是为数据结构课程独立开设的实践性教学环节。数据结构课程设计对于巩固数据结构知识,加强学生的实际动手能力和提高学生综合素质是十分必要的。 本题目主要解决两个问题:一是怎么存放和查找大量数据(主要是姓名);二是怎么操作“ENQUEUE”和“DEQUEUE”命令。:1)输入要求:程序从“”文件读入测试用例,一个文件可包含多个测试用例。每个用例的第一行是朋友组的数目n(1<=n<=1000).对于一个朋友组以朋友的数目j(1<=j<=1000)开始,由朋友的个数以及他们的名字组成,一个空格后接该组朋友的名字,以空格分开,并且每个人的名字都不同。每个名字不超过4个字母,由{A,B,…,Z,a,b,…,z}组成。一个朋友组最多有1000个人,每个人只属于一个朋友组。n=0时,测试数据结束。下面是一些具体命令:ENQUEUEX——X入队DEQUEUE——排队头的人买票,离开队伍,即出队STOP——一个测用例结束2)、输出要求:测试结果输出到“”文件中。每个测试用例的第一行输出“Scenario#k”,k是测试用例的序号(从1开始)。对每一个DEQUEUE命令,输出刚买票离开队伍的人名。两个测试用例之间隔一空行,最后一个用例结束不输出空行。3、,每组最多1000人,使用平方探测法解决冲突,则表的大小至少是2*(1000*1000),所以选择TableSize=2000003。同一个组内的都是朋友,所以每个人除了记录他的名字name,还要记录他属于哪个朋友组group,另外用info来表示该单元是否被占用,数据结构如图2所示。散列函数是根据Honer法则计算一个以64为阶的多项式,如图3所示。冲突解决方法采用平方探测法,如图4所示。#abSize2000003typedefstructhashtab*PtrToHash;structhashtab{charname[5];intgroup;charinfo;/*用来表示该单元是否被占用*/};图2数据结构:散列表intHash(char*key,intTableSize){intHashVal=0;while(key!=NULL)HashVal=(HashVal<<6)+*key;ReturnHashVal%TableSize;}图3散列函数long int Find(PtrToHash hash,char *c){   key=c;  CurrentPos=Hash(key,TabSize);                     /*计算散列值*/  CollisionNum=0;   while((单元被占用)and(单元内的名字与查找的名字不同))  /*发生冲突*/ {        /*平方探测法*/   CurrentPos+=2*(++CollisionNum)-1;   if(CurrentPos>=TabSize)    CurrentPos-=TabSize;  }      return CurrentPos;/*返回在散列表中的位置*/ } “ENQUEUE”和“DEQUEUE”命令这可以用队列来模拟。由于有插队现象的存在,不能单纯地用一个数组来表示队列,因为这样的话,插入一个朋友,则他后面的人都要往后移一个单位,删除一个人,则他后面的人都要前移一个,会降低效率。所以,采用一