数据结构 <插队买票>算法设计~~大家帮个忙~~C++程序

Question

插队买票
题目：春运期间，成千上万的外出人员都往家赶。火车站售票窗前买票队伍一眼望不到头。运气好，碰到一个已在排队的朋友，直接发走过去，排在他后面，这就叫“插队”，但对于队伍里的其他人来说是不公平的。本题目的任务是写一个程序模拟这种情况。每个队伍都允许插队。如果你在排队，有一个以上的朋友要求插队，则你可以安排他们的次序。每次一个入队，并且如果这个主队的人发现队伍中有自己的朋友，则可以手稿到这个朋友的后面；当队伍中的朋友不止一个的时候，这个人会排在最后一个朋友的后面；如果队伍中没有朋友，则他只能排在这个队伍的最后面。每一个入队的都先进行上述的判断。当队全前的人买到车票之后。依次出队。
提示：
解决二个问题：一是怎么存放和查找大量数据（主要是姓名）；二是怎么操作入队和出队命令。

Answer 1

//grouppos.cpp

#include<stdio.h>
#include<malloc.h>
#include<string.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;/*返回在散列表中的位置*/
}

void 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]; /*名字*/
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;
cout<<"输入当前测试用例的朋友组数:"<<endl;
for(cin>>n;n;cin>>n)/*输入当前测试用例的朋友组数*/
{
if(n<1||n>1000) /*处理异常输入n*/
{
cout<<"n is out of range!"<<endl;
}
num++;
if(num!=1) /*两个测试用例间输入一空行*/
cout<<"\n";
for(i=0;i<TabSize;)
hash[i++].info=0; /*初始化散列表，标记位置0*/
for(i=0;i<n;++i) /*对每一组朋友*/
{
cout<<"当前组里的人数:"<<endl;
cin>>j; /*当前组里的人数*/
if(j<1||j>1000) /*处理异常输入j*/
{
cout<<"j is out of range!"<<endl;
}
for(;j;--j)
{
cout<<"输入名字:"<<endl;
cin>>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)
{
cout<<"Group"<<i<<":Not standard name"<<endl;
}
ii++;
}
key=Find(hash,c); /*找到在散列表中的位置*/
if(hashedx==1) /*重名*/
{
cout<<"Repeated name"<<" "<<c<<endl;
}
else
{
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;
for(cout<<"输入命令:I入队/O出队"<<endl,cin>>c;;cout<<"输入命令:I入队/O出队"<<endl,cin>>c) /*输入命令*/
{

if(*c=='I'||*c=='i')/*入队命令*/
{
cout<<"输入名字"<<endl;
cin>>c; /*输入名字*/
key=Find(hash,c);/*查找在散列表中的位置*/

if(hashedx==0) /*散列表里没这个人*/
{
cout<<"no"<<c<<endl;
}

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=='O'||*c=='o') /*出队命令*/
{
if(last==0) /*不能对空队列执行出队命令*/
{
cout<<"Empty queue!\nCan't execute DEQUEUE!"<<endl;
}
else
{
cout<<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; /*测试结束*/
}
}
}