5
回答
散列表插队买票之“数组队列”的问题求解
滴滴云服务器,限时包月0.9元,为开发者而生>>>   

对于以下代码

 

#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; /*入队*/
     if(!head) /*如果是队列里的第一个元素 */
      last=head=temp; /*队头、队尾标记指向第一个元素*/

 

求解释!

 

 

<无标签>
举报
举一反三
发帖于6年前 5回/456阅
共有5个答案 最后回答: 6年前

这个代码谁写的,够变态的。哈。

所有空的位置,都会被queue[0]的index索引到。所以先取queue[0]给予tmp,使用,queue[0]再移动到自己曾经指向的下一个,自然也是空的位置。
是啊,我就搞不懂了,难道没来一个来排队都会把值赋给temp么?我实在搞不懂它后面来排队的是怎么进入队列的。

引用来自“中山野鬼”的答案

这个代码谁写的,够变态的。哈。

所有空的位置,都会被queue[0]的index索引到。所以先取queue[0]给予tmp,使用,queue[0]再移动到自己曾经指向的下一个,自然也是空的位置。
是啊,我就搞不懂了,难道每来一个来排队都会把值赋给temp么?我实在搞不懂它后面来排队的是怎么进入队列的。求解释!
--- 共有 1 条评论 ---
中山野鬼你说进queue,还是里面的一个动作,针对group的下标调整index? 6年前 回复

引用来自“举一反三”的答案

引用来自“中山野鬼”的答案

这个代码谁写的,够变态的。哈。

所有空的位置,都会被queue[0]的index索引到。所以先取queue[0]给予tmp,使用,queue[0]再移动到自己曾经指向的下一个,自然也是空的位置。
是啊,我就搞不懂了,难道每来一个来排队都会把值赋给temp么?我实在搞不懂它后面来排队的是怎么进入队列的。求解释!
我说的是进 queue,不理解它以后的一系列的代码是如何让排队等待的人进队列,进入队列的哪个位置的。求解释!
/*第一个人入队*/

temp=queue[0].Index;  /*temp为队列中序号为1的元素。*/

queue[0].Index=queue[temp].Index; /*queue[0].index此时指向序号为2的元素*/

queue[temp].HashVal=key; /*入队*/

if(!head) /*head初始值为0,!head为真*/
	 last=head=temp; /*此时队头队尾都为队列序号temp即1*/
if(!grouppos[hash[key].group]) /*如果队列里没朋友*/
{

		queue[temp].Index=0;  /*队尾指向对头,形成环*/
		queue[last].Index=temp;/*前一次队尾的后继元素是当前元素*/
		last=temp;           /*队尾标记指向当前元素*/
		grouppos[hash[key].group]=temp;
		/*插队数组记录该朋友组里已入队的最后一位*/
}
	
	
	
/*第二个人入队*/

temp=queue[0].Index;  /*temp为队列中序号为2的元素。*/

queue[0].Index=queue[temp].Index; /*queue[0].index此时指向序号为3的元素*/

queue[temp].HashVal=key; /*入队*/

if(!head) /*head此时为1,!head为假*/
	 last=head=temp; 
	 ....

queue[0]并不是用来存储,利用其Index来推进位置。

顶部