数据结构课程设计
散列表的应用:插队买票
专业 计算机科学与技术（网络技术）
金玲 计算机131 1310704114 张静林 2015年1月23日 学生姓名 班学级 号
指导教师 完成日期
目录
1 概述……………………………………………………………………………………1 1.1 课程设计目的……………………………………………………………………….1 1.2 课程设计内容……………………………………………………………………….1 2 系统需求分析……………………………………………………………………….1 2.1 主体功能…………………………………………………………………………....2 3系统概要设计…………………………………………………………………………2 3.1 系统流程图………………………………………………………………………….2 4 系统详细设计…………………………………………………………………………3 5 测试……………………………………………………………………………………5 5.1 测试方案…………………………………………………………………………….5 5.2 测试结果…………………………………………………………………………….5 6 小结……………………………………………………………………………………5 参考文献…………………………………………………………………………………5 附录………………………………………………………………………………………7 附录1 源程序清单……………………………………………………………………...7
1 概述
1.1 课程设计目的
数据结构课程设计是为数据结构课程独立开设的实践性教学环节。数据结构课程设计对于巩固数据结构知识，加强学生的实际动手能力和提高学生综合素质是十分必要的。课程设计的目的：
1．要求学生达到熟练掌握C语言的基本知识和技能。
2．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。 3．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。
4．培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。
5．初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。
1.2课程设计内容
本课程设计的任务是写一个程序模拟这种情况。每个队伍都允许插队。如果你在排队，有一个以上的朋友要求插队，则你可以安排他们的次序。每次一个人入队，并且如果这个入队的人发现队伍中有自己的朋友，则可以插入到这个朋友的后面；当队伍中的朋友不止一个的时候，这个人会排在最后一个朋友的后面；如果队伍中没有朋友，则他只能够排在这个队伍的最后面。每一个入队的人都先进行上述的判断。当队伍前面的人买到车票之后，依次出队。
2 系统需求分析
2.1 主体功能
程序从“input.txt”文件读入测试用例，一个文件可包含多个测试用例。每个用例的第一行是朋友组的数目n（1
下面是一些具体命令： .ENQUEUE——X入队; .DEQUEUE——排队头的人买票，离开队伍，即出队； .STOP——一个测试用例结束。
测试结果输出到“output.txt”文件中。每个测试用例第一行输出“Scenario#k”，k是测试用例的序号（从1开始）。对每一个出队命令，输出刚买票离开队伍的人名。两个测试试用例
3 之间隔一空行，最后一个用例结束不输出空行。
3 系统概要设计
3.1 系统流程图
4 系统详细设计
本题目主要解决两个问题：一是怎么存放和查找大量数据（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。
用散列表来存放和查找数据。由于最多有1000个朋友组，每组最多有1000人，使用平方探测法解决冲突，则表的大小是2*（1000*1000），所以选择TableSize=2000003（2000003是大于2000000的最小素数）。同一个组内的都是朋友，所以每个人除了记录他的名字name，还要记录他属于哪个组group，另外用info来表示该单元是否被占用，数据结构如图4.1所示。散列函数是根据Honer法则计算一个以64为阶的多项式，如图4.2所示。冲突解决方法采用平方探测法，如图4.3所示。
#define TabSize 2000003 typedef struct hashtab *PtrToHash; struct hashtab
/*散列表数据结构*/ { char name[5];
/*名字*/ int group;
/*属于哪个朋友组*/ char info;
/*标志位，该单元是否被占用*/ }; 图4.1数据结构：散列表
Int Hash(char *key,int TableSize) {
Int HashVal=0;
While(key!=NULL)
HashVal=(HashVal
Return HashVal%TableSize; } 图4.2散列函数
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.3用平方探测法解决冲突
第二个问题是关于怎么操作“ENQUEUE”和“DEQUEUE”命令。这可以用队列来模拟。由于有插队现象的存在，不能单纯的用一个数组来表示队列，因为这样的话，插入一个朋友，则他后面的人都要往后移一个单位，删除一个人，则他后面的人都要前移一个，会降低效率。所以，采用一个Index标记来表示当前元素的后继元素，最后一个单元的后继元素是第0个，形成环，数据结构如图4.4所示。不用链表是因为链表存放指针也需要空间，并且链表插入、删除的效率没有数组高。
typedef struct Que *PtrToQue; struct Que
/*队列数据结构*/ { long int HashVal;
/*散列值*/ long int Index;
/*在中的队列序号*/ }; 图4.4数据结构：队列
输入ENQUEUE命令，如果队伍里有朋友，则排在朋友后面；如果没有朋友，则排在队尾。入队时，用一个数组记录每个朋友组的最后一位，以便下一个朋友到来时排到他后面，这个数组被称为“插队数组”。
输入DEQUEUE命令，则根据“先进先出”，按照各个元素和它后继元素的先后顺序，每次删除队列重的第一个。程序结构如图4.5所示。
While(读测试文件) {
if(输入”ENQUEUE”)
{
读入名字；
插入散列表；
插入队列；
}
else if(输入”DEQUEUE”)
{
删除队列第一个名字；
将该名字输出到文件；
}
else stop; } 图4.5入队、出队操作
5 测试
5.1 测试方案
5 按输入要求输入正常测试数据，测试程序是否能正确解决问题，得到正确答案。 应注意边界测试。例如，将n，j分别取为1的用例和n为1000的用例。n，j比较大时需写程序生成测试用例。
不按输入要求输入数据，测试程序能否对输入内容进行数据合法性检测并进行相应的异常处理。例如，将n或j取为小于1或大于1000的数，名字超过4个字母等情况下的测试用例。 5.2 测试结果
6 小结
在前面的学习过程中我们学到了很多知识而这次课程设计又是对我们所学的 一次总结，刚开始，可以说是没有头绪，于是就去图书馆找资料，找到了一些关于程序方面的，可这远远不够，这只是小小的开始。我们必须掌握很多已学的知识才能很好的完成本次的课程设计。在这次课程设计中，总的感觉是我遇到了很多困难这主要是由于我编写代码的经验不足，有时虽然是一个很小的问题但解决起来却花费了我不少的时间，值得欣慰的是，当自己苦思冥想或者和其它同学一起探讨把问题解决的时候我还是觉得获益非浅，这就是在摸索中寻求到的知识。在设计时也免不了存在着些不足，所以在今后的学习中我会努力取得更大的进步。虽然对着电脑做程序，有些累，可当看到劳动成果时，却有另一番滋味。
参考文献
[1]范策，周世平，胡晓琨.《算法与数据结构（C语言版）》[M].北京：机械工业出版社，2004 [2]严蔚敏.《数据结构（C语言版）》.北京：清华大学出版社，2004 [3]许卓群，杨冬青，唐世渭，张铭.《数据结构与算法》.北京：高等教育出版社，2004 [4]徐孝凯.《数据结构实用教程（第二版）》.北京：清华大学出版社，2006
附录
附录1 源程序清单
#include #include #include #define TabSize 2000003
/*散列表大小TabSize 是大于表最大空间的素数*/ #define Max 1000001
/*队列空间最大值*/ struct hashtab; typedef struct hashtab *PtrToHash; struct hashtab
/*散列表数据结构*/ { char name[5];
/*名字*/ int group;
/*属于哪个朋友组*/ char info;
/*标志位，该单元是否被占用*/ }; struct Que; typedef struct Que *PtrToQue; struct Que
/*队列数据结构*/ { long int HashVal;
/*散列值*/ long int Index;
/*在中的队列序号*/ };
int hashedx=0;
/*标记元素是否已经在散列表里*/ long int Find(PtrToHash hash,char *c) /*查找在散列表中的位置*/ { char *key; long int CurrentPos,CollisionNum;
key=c; for(CurrentPos=0;*key;++key)
/*散列函数，计算散列值*/
CurrentPos=(CurrentPos
/*散列值*/ 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))
/*元素已经在散列表里*/
hashedx=1; else /*元素不在散列表里*/
hashedx=0; return CurrentPos;/*返回在散列表中的位置*/ }
int main() { long int Find(PtrToHash hash,char *c);
/*查找在散列表中的位置*/
PtrToHash hash;
/*散列表*/
7 PtrToQue queue;
/*队列*/ int *grouppos;
/*记录每个朋友组的最后一位，即插队数组*/ int n;
/*测试用例数目*/ int num;
/*当前测试用例序号*/ long int i,ii,j,key,temp; long int head,last;
/*队列的头和尾*/ char c[8],tempc[8];
/*名字*/ FILE *fpin,*fpout;
/*输入、输出文件指针*/
if(!(fpin=fopen(\"input.txt\",\"r\")))
/*打开测试文件*/ {
printf(\"fopen error!\");
/*文件打开错误*/
return -1; } if(!(fpout=fopen(\"output.txt\",\"w\")))
/*打开输出文件*/ {
printf(\"fopen error!\");
return -1; }
hash=(PtrToHash)malloc(sizeof(struct hashtab)*TabSize); /*为散列表申请空间*/ queue=(PtrToQue)malloc(sizeof(struct Que)*Max); /*为队列申请空间*/ grouppos=(int *)malloc(sizeof(int)*1000); /*申请空间记录每个朋友组的最后一位*/ for(i=0,j=1;i
queue[i].Index=j; queue[i-1].Index=0; /*最后一个单元的后继单元是第0个，形成环*/ num=0; for(fscanf(fpin,\"%d\",&n);n;fscanf(fpin,\"%d\",&n))/*输入当前测试用例的朋友组数*/ {
if(n1000)
/*处理异常输入n*/
{
fprintf(fpout,\"n is out of range\\n\");
return -1;
}
num++;
if(num!=1)
/*两个测试用例间输入一空行*/
fprintf(fpout,\"\\n\");
for(i=0;i
hash[i++].info=0;
/*初始化散列表，标记位置0*/
for(i=0;i
/*对每一组朋友*/
{
fscanf(fpin,\"%d\",&j);
/*当前组里的人数*/
if(j1000)
/*处理异常输入j*/
{
fprintf(fpout,\"j is out of range\\n\");
return -1;
}
for(;j;--j)
{
fscanf(fpin,\"%s\",c);
/*输入名字*/
for(ii=0;ii
tempc[ii]=\'\\0\';
strcpy(tempc,c);
ii=0;
while(tempc[ii]!=\'\\0\')
/* 是否由四个以内字母组成*/
{
if(tempc[ii]\'z\'||ii>4)
{
fprintf(fpout,\"Group %d: Nonstandard name\\n \",i);
return -1;
}
ii++;
}
key=Find(hash,c);
/*找到在散列表中的位置*/
if(hashedx==1) /*重名*/
{
fprintf(fpout,\"repeated name %s\\n\",c);
return -1;
}
strcpy(hash[key].name,c);/*插入散列表*/
hash[key].info=1;
/*标记置1，该单元被占用*/
hash[key].group=i;
/*记录他属于哪个组*/
} } for(i=0;i
grouppos[i++]=0; /*初始化插队数组*/ head=0;
/*初始化队列头、尾标记*/ last=0; fprintf(fpout,\"Scenario #%d\\n\",num); /*输出当前用例序号到文件*/ for(fscanf(fpin,\"%s\",c);;fscanf(fpin,\"%s\",c)) /*输入命令*/ {
if(*c==\'E\')
/*入队命令*/
{
fscanf(fpin,\"%s\",c);
/*输入名字*/
key=Find(hash,c);
/*查找在散列表中的位置*/
if(hashedx==0) /*散列表里没这个人*/ {
fprintf(fpout,\"no %s\\n\",c);
return -1; }
temp=queue[0].Index;
/*队列第0个位置记录队尾的后继单元*/ queue[0].Index=queue[temp].Index;
/*在队列中申请一个新单元，队尾标记后移一个位置 */ queue[temp].HashVal=key; /*入队*/ if(!head) /*如果是队列里的第一个元素 */ last=head=temp; /*队头、队尾标记指向第一个元素*/ if(!grouppos[hash[key].group]) /*如果队列里没朋友*/ { queue[temp].Index=0; /*队尾指向对头，形成环*/ queue[last].Index=temp;/*前一次队尾的后继元素是当前元素*/ last=temp;
/*队尾标记指向当前元素*/ grouppos[hash[key].group]=temp; /*插队数组记录该朋友组里已入队的最后一位*/ } else/*如果队列中已经有他的朋友*/ {
queue[temp].Index=queue[grouppos[hash[key].group]].Index;
/*插队到朋友的后面*/
queue[grouppos[hash[key].group]].Index=temp;
/*插队到朋友后面一位的前面*/
grouppos[hash[key].group]=temp;
/*替换插队数组里该组的元素为当前元素*/
if(hash[queue[last].HashVal].group==hash[key].group)
/*如果当前元素和前一元素是朋友，队尾标志指向当前元素*/
last=temp;
}
}
else if(*c==\'D\') /*出队命令*/
{
if(last==0)
/*不能对空队列执行出队命令*/
{
fprintf(fpout,\"Empty queue!\\nCan\'t execute DEQUEUE!\\n\");
return -1;
}
fprintf(fpout,\"%s\\n\",hash[queue[head].HashVal].name);
/*输出队头元素到文件*/
temp=head;
head=queue[temp].Index;
/*队列第一位出队，队头标记后移一位*/
queue[temp].Index=queue[0].Index;
/*队列第0个元素后移一位*/
queue[0].Index=temp;
/*释放空间*/
if(grouppos[hash[queue[temp].HashVal].group]==temp)
/*当前删除的元素是该朋友组在队列里的最后一位*/
grouppos[hash[queue[temp].HashVal].group]=0;
if(last==temp)
/*出队后，队列为空*/
last=0;
}
else
/*输入 \"STOP\"*/
break;
/*测试结束*/
} } fprintf(fpout,\"\\b\"); fclose(fpin); fclose(fpout); return 1; }
