散列表之插队买票
本实验假设售票大厅有多个售票窗口，无论到哪个窗口买票都必须排队，但是新来的人不一定排在队尾，允许插队（即直接排在朋友的后面）。
假设已经在排队的人不会离开，也不会移到其他队伍去。买到票的人依次出队。每个人仅买一次票，买完票就离开。每个人都有名字。
每个来买票的人先进行观察判断：
1． 如果所有的队伍中都没有发现朋友，则选择最短的队伍排在其队尾；
2． 如果所有的队伍中仅发现一个朋友，则可以（不是必须）插在此朋友的后面；但是，插队前应考查是否合算，插入此位置离窗口的距离（即队伍前面的人数）必须小于其他队伍的长度，否则应选择最短的队伍排在其队尾；
3． 如果所有的队伍中发现多个朋友，这种情况就比较复杂：
（1） 如果多个朋友是集中在一个队伍里，则可以插在最后那个朋友的后面；
（2） 如果多个朋友是分散在多个队伍里，则插队的原则是离售票窗口最近；
4． 如果朋友排在队伍的第一位（即队首），则不允许插队；
本实验要求编写程序模拟这种排队买票时允许插队的情形。要求程序中应用散列表来存放和查找数据，应用求余法构造合理的散列函数，应用平方探测法来解决Hash映射的冲突现象。程序可能需要四个文本文件：
（1） 初始化文件input.txt，包含售票窗口及其购票队伍的初始设置
（2） 朋友组文件friend.txt，同一个名字也可能出现在不同的组
（3） 来购票的人的完整名单people.txt，其中包含出现在friend.txt中的名字；文件中名字的顺序表示不同的到来顺序；文件中每行有一个名字，如果某行有多个名字则表示他们同时到达售票厅（这是比较复杂的情形）
（4） 售票结果文件output.txt（按售票窗口分组显示），可以考虑各窗口卖票的节奏（即售票员的售票速度）
先上代码。
#include<stdio.h>#include<malloc.h>#include<string.h>#include <fstream.h>#include <iostream.h>#define TabSize 2000003 /*散列表大小TabSize 是大于表最大空间的素数*/#define Max 1000001 /*队列空间最大值*/class hashtab /*散列表数据结构*/{public:char name[5]; /*名字*/int group; /*属于哪个朋友组*/char info; /*标志位，该单元是否被占用*/};class PtrToHash:public hashtab{};class Que /*队列数据结构*/{public:long int HashVal; /*散列值*/long int Index; /*在中的队列序号*/};class PtrToQue:public Que{};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<<6)+*key;CurrentPos%=TabSize; /*散列值*/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; /*散列表*/PtrToQue *queue; /*队列*/int *grouppos; /*记录每个朋友组的最后一位，即插队数组*/int n; /*测试用例数目*/int num; /*当前测试用例序号*/long int i,ii,j,key,temp;long int head,last; /*队列的头和尾*/char c[8],tempc[8]; /*名字*/ifstream fpin;ofstream fpout; /*输入、输出文件指针*/ fpin.open("input.txt"); fpout.open("output.txt");hash=(PtrToHash*)malloc(sizeof(hashtab)*TabSize);queue=(PtrToQue*)malloc(sizeof(Que)*Max); grouppos=(int *)malloc(sizeof(int)*1000);for(i=0,j=1;i<Max;++i,++j) /*初始化队列，queue[i]的后继单元是queue[i＋1]*/ queue[i].Index=j;queue[i-1].Index=0; /*最后一个单元的后继单元是第0个，形成环*/num=0;for(fpin>>n;n;fpin>>n)/*输入当前测试用例的朋友组数*/{ if(n<1||n>1000) /*处理异常输入n*/ { fpout<<"n is out of range\n"; return -1; } num++; if(num!=1) /*两个测试用例间输入一空行*/ fpout<<"\n"; for(i=0;i<TabSize;) hash[i++].info=0; /*初始化散列表，标记位置0*/ for(i=0;i<n;++i) /*对每一组朋友*/ { fpin>>j; /*当前组里的人数*/ if(j<1||j>1000) /*处理异常输入j*/ { fpout<<"j is out of range\n"; return -1; } for(;j;--j) { fpin>>c; /*输入名字*/ for(ii=0;ii<sizeof(tempc);ii++) /*tempc清空，处理异常输入名字*/ tempc[ii]='\0'; strcpy(tempc,c); ii=0; while(tempc[ii]!='\0') /* 是否由四个以内字母组成*/ { if(tempc[ii]<'A'||('Z'<tempc[ii]&&tempc[ii]<'a')||tempc[ii]>'z'||ii>4) { fpout<<"Group"<<i<<":Nonstandard name"<<endl; return -1; } ii++; } key=Find(hash,c); /*找到在散列表中的位置*/ if(hashedx==1) /*重名*/ { fpout<<"repeated name"<<c; return -1; } strcpy(hash[key].name,c);/*插入散列表*/ hash[key].info=1; /*标记置1，该单元被占用*/ hash[key].group=i; /*记录他属于哪个组*/ } } for(i=0;i<1000;) grouppos[i++]=0; /*初始化插队数组*/ head=0; /*初始化队列头、尾标记*/ last=0; fpout<<"Scenario #"<<num<<endl; /*输出当前用例序号到文件*/ for(fpin>>c;;fpin>>c) /*输入命令*/ { if(*c=='E') /*入队命令*/ { fpin>>c; /*输入名字*/ key=Find(hash,c); /*查找在散列表中的位置*/ if(hashedx==0) /*散列表里没这个人*/ { fpout<<"no"<<c<<endl; 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) /*不能对空队列执行出队命令*/ { fpout<<"Empty queue!\nCan't execute DEQUEUE!\n"; return -1; } fpout<<hash[queue[head].HashVal].name<<endl; /*输出队头元素到文件*/ 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; /*测试结束*/ }}fpout<<"\b";fpin.close();fpout.close();return 1;}
temp=queue[0].Index; /*队列第0个位置记录队尾的后继单元*/ queue[0].Index=queue[temp].Index; /*在队列中申请一个新单元，队尾标记后移一个位置 */ queue[temp].HashVal=key; /*入队*/