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

数据结构课程设计

插队买票

专班学

业 级 号

计算机科学与技术 XXXXXXXXX XXXXXXXXX

XX

学生姓名

数据结构课程设计——散列表的应用：插入买票

目 录

1 设计题目 ................................................................................................................... 1 2 设计分析 ................................................................................................................. 1 3 设计实现 ................................................................................................................. 3 4测试方法 ............................................................................................................... 10 4.1测试目的 ............................................................................................................ 10 4.2 测试输入 ........................................................................................................... 10 4.3 正确输出 ........................................................................................................... 11 4.4 实际输出 ........................................................................................................... 12 5 分析与探讨 ........................................................................................................... 12 5.1 测试结果分析 ................................................................................................... 12 5.2 探讨与改进 ....................................................................................................... 12 6 设计小结 ............................................................................................................... 12

数据结构课程设计——散列表的应用：插入买票

1 设计题目 春节前夕,一年一度的运输高潮也开始了,成千上万的外出人员都往家赶.火车站售票 窗前买票队伍一眼望不到头.运气好的,碰到一个已经在排队的朋友,直接走过去,排他后 面,这就叫\插队\但对队伍里的其他人来说是不公平的.本课程设计的任务是写一个程序模拟这种情况.每个队伍都允许插队.如果你在排队,有一个以上的朋友要求插队,则你可以安排他们的次序.每次一个人入队,并且如果这个入队的人发现队伍中有自己的朋友,则可以插入到这个朋友的后面;当队伍中的朋友不止一个的时候,这个人会排在最后一个朋友的后面;如果队伍中没有朋友,则他只能够排在这个队伍的最后面.每一个入队的人都先进行上述的判断.当队伍前面的人买到车票之后.依次出队.

2 设计分析

本题目主要解决两个问题：一是怎么存放和查找大量数据（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。

用散列表来存放和查找数据。由于最多有1000个朋友组，每组最多1000人，使用平方探测法解决冲突，则表的大小至少是2*（1000*1000），所以选择TableSize=2000003。同一个组内的都是朋友，所以每个人除了记录他的名字name，还要记录他属于哪个朋友组group，另外用info来表示该单元是否被占用，数据结构如图所示。散列函数是根据Honer法则计算一个以64为阶的多项式，如图2。 #define TabSize 2000003 /*散列表大小TabSize typedef struct hashtab *PtrToHash; struct hashtab /*散列表数据结构*/ { }; 数据结构：散列表

Int Hash(char *key,int TableSize) { int HashVal=0; while(key!=NULL)

1

char name[5]; /*名字*/ int group; /*属于哪个朋友组*/ char info; /*标志位，该单元是否被占用*/ 数据结构课程设计——散列表的应用：插入买票

HashVal=(HashVal<<6)+*key; Return HashVal %TableSize; } long int Find(PtrToHash hash,char *c) /*查找在散列表中的位置*/ { } 用平方探测法处理冲突

第二个问题关于怎么操作“ENQUEUE”和“DEQUEUE”命令。这可以用队列来模拟。由于有插队现象的存在，不能单纯地用一个数组来表示队列，因为这样的话，插入一个朋友，则他后面的人都要往后移一个单位，删除一个人，则他后面的人都要前移一个，会降低效率。所以，采用一个Index标记来表示当前元素的后继元素，最后一个单元的后继元素是第0个，形成环，数据结构如下图所示。不用链表是因

char *key; long int CurrentPos,CollisionNum; key=c; for(CurrentPos=0;*key;++key) /*散列函数，计算散列值*/ CurrentPos=(CurrentPos<<6)+*key; CurrentPos%=TabSize; /*散列值*/ CollisionNum=0; /*如果当前单元被占用：单元内的元素与当前操作的名字不同，使用平方探测while((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c))) { /*平方探测法*/ } hashedx=1; CurrentPos+=2*(++CollisionNum)-1; if(CurrentPos>=TabSize) CurrentPos-=TabSize; 法解决冲突； */ if((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)==0)) else /*元素不在散列表里*/ hashedx=0; return CurrentPos;/*返回在散列表中的位置*/ 2