文档介绍：v .. . ..
: .
数据结构课程设计报告
插队买票
专业
学生姓名
班级
学号
指导教师
完成日期
2015年1月24日
. . . 资 料. .
v .. . ..
目 录
1、设计题目 1
2、课题目的及要求 1
_Toc22401 3、设计分析 4
4、调试与测试 4
5、小 结 6
6、参考文献 7
7、源程序清单 EF _Toc10922 7
. . . 资 料. .
v .. . ..
数据结构课程的设计
1、设计题目
春节前夕,一年一度的运输高潮也开始了, ,碰到一个已经在排队的朋友,直接走过去,排他后 面,这就叫"插队",,有一个以上的朋友要求插队,,并且如果这个入队的人发现队伍中有自己的朋友,则可以插入到这个朋友的后面;当队伍中的朋友不止一个的时候,这个人会排在最后一个朋友的后面;如果队伍中没有朋友,.
2、课题目的及要求
：
数据结构课程设计是为数据结构课程独立开设的实践性教学环节。数据结构课程设计对于巩固数据结构知识，加强学生的实际动手能力和提高学生综合素质是十分必要的。
  本题目主要解决两个问题：一是怎么存放和查找大量数据（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。
：
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）、输出要求：
测试结果输出到“”文件中。每个测试用例的第一行输出“Scenario#k”，k是测试用例的序号（从1开始）。对每一个DEQUEUE命令，输出刚买票离开队伍的人名。两个测试用例之间隔一空行，最后一个用例结束不输出空行。
3、设计分析
图1 系统总图
由于最多有1000个朋友组，每组最多1000人，使用平方探测法解决冲突，则表的大小至少是2*（1000*1000），所以选择TableSize=2000003。同一个组内的都是朋友，所以每个人除了记录他的名字name，还要记录他属于哪个朋友组group，另外用info来表示该单元是否被占用，数据结构如图2所示。散列函数是根据Honer法则计算一个以64为阶的多项式，如图3所示。冲突解决方法采用平方探测法，如图4所示。
#define TabSize 2000003
typedef struct hashtab *PtrToHash;
struct hashtab