插队买票
#define TabSize 2000003 typedef struct hashtab *PtrToHash; struct hashtab { char name[5]; int group; char info; /*用来表示该单元是否被占用*/ }; 图4-2 数据结构:散列表
int Hash(char *key,int TableSize) { int HashVal=0; while(key!=NULL) HashVal=(HashVal<<6)+*key; Return HashVal%TableSize; } 图4-3 散列函数
long int Find(PtrToHash hash,char *c) { key=c; CurrentPos=Hash(key,TableSize); /*计算散列值*/ CollisionNum=0; while((单元被占用)and(单元内的名字与查找的名字不同)) { /*使用平方探测法*/ CurrentPos+=2*(++CollisionNum)-1; if(CurrentPos>=TabSize) CurrentPos-=TabSize; } return CurrentPos; } 图4-4用平方探测法解决冲突
第二个问题是关于怎么操作“ENQUEUE”和“DEQUEUE”命令。这可以用队列来模拟。由于有插队现象的存在,不能单纯地用一个数组来表示队列,因为这样的话,插入一个朋友,则他后面的人都要往后移一个单位,删除一个人,则他后面的人都要前移一个,会降低效率。所以,采用一个Index标记来表示当前元素的后继元素,最后一个单元的后继元素是第0个,形成环,数据结构如图4-4所示。不用链表是因为链表存放指针也需要空间,并且链表插入、删除的效率没有数组高。 Typedef struct Que *PtrToQue; Struct Que { long int HashVal; long int Index; }; 图4-5 数据结构:队列
输入ENQUEUE命令,如果队伍里有朋友,则排在朋友后面;如果没有朋友,则
4
数据结构课程设计报告(2014)
排在对尾。入队时,用一个数组记录每个朋友组的最后一位,以便下一个朋友到来时排到他后面,这个数组被称为“插队数组”。
输入DEQUEUE命令,则根据“先进先出”,按照各个元素和它后继元素的先后顺序,每次删除队列中的第一个。程序结构如图4-5所示。 While(读测试文件) { if(输入“ENQUEUE”) { 读入名字; 插入散列表; 插入队列; } else if(输入“DEQUEUE”) { 删除队列第一个名字; 将该名字输出到文件; } else stop; } 图4-6 入队、出对操作
5 测试
5.1 测试方案
1.按输入要求输入正常测试数据,测试程序是否能正确解决问题,得到正确答案。 2.应注意边界测试。例如,将n、j分别取为1的用例和n胃1000的用例。n、j比较大时需写程序生成测试用例。
3.不按输入要求输入数据,测试程序能否对输入内容进行数据合法性检测并进行相应的异常处理。例如,将n或j取为小于1或大于1000的数,名字超过4个字母等情况下的测试用例。 5.2 测试结果 1.无任何输入结果:
当输入的n小于程序所要求的1<=n<=1000时,因为n小于1,所以会报错,调用冲突处理模块,程序输出的结果如图
5
插队买票
图4–7 无任何输入结果
2.正确显示结果:
按照输入要求正确的输入几组数据,根据出入队的顺序,先进的回排在最后一个得后面,所以输出结果如图4 – 8所示
6
数据结构课程设计报告(2014)
图4 – 8 正确显示结果
3.举例说明几种异常结果:
7
插队买票
1.Repeated name
当出现人名重复的时候出现的结果,出现异常,调用异常处理模块中人名重复异常处理模块,所以输出结果如图4 - 9所示
图4 – 9 Repeated name
2