Jumping the Queue C++代码

Project 2: Jumping the Queue The beginning of a winter break near Spring Festival is always the beginning of a peak period of transportation. If you have ever tried to get a train ticket at that time, you must have witnessed the endless queues in front of every ticket box window. If a guy has seen his friend in a queue, then it is very much likely that this lucky guy might go straight to his friend and ask for a favor. This is called "jumping the queue". It is unfair to the rest of the people in the line, but, it is life. Your task is to write a program that simulates such a queue with people jumping in every now and then, assume that, if one in the queue has several friends asking for favors, he would arrange their requests in a queue of his own. Input Specification: Your program must read test cases from a file “input.txt”. The input file will contain one or more test cases. Each test case begins with the number of groups n (1<= n <=1000). Then n group descriptions follow, each one consisting of the number of friends belonging to the group and those people's distinct names. A name is a string of up to 4 characters chosen from {A, B, ..., Z, a, b, ..., z}. A group may consist of up to 1000 friends. You may assume that there is no one belong to two different groups. Finally, a list of commands follows. There are three different kinds of commands:  ENQUEUE X - Mr. or Ms. X goes into the queue  DEQUEUE - the first person gets the ticket and leave the queue  STOP - end of test case The input will be terminated by a value of 0 for n. Output Specification: For each test case, output to a file “output.txt”. First print a line saying "Scenario #k", where k is the number of the test case. Then, for each DEQUEUE command, print the person who just gets a ticket on a single line. Print a blank line between two test cases, but no extra line at the end of output. Sample Input: 2 3 Ann Bob Joe 3 Zoe Jim Fat ENQUEUE Ann ENQUEUE Zoe ENQUEUE Bob ENQUEUE Jim E

#include 
#include 
#include 

typedef unsigned int Index;
typedef Index Position;
struct HashEntry;
struct HashTbl;
typedef struct HashEntry Cell;     
typedef struct HashTbl *HashTable;

Index Hash（const char * keyint Tablesize）;   /*The hash function*/
void InitializeTable（int TableSize）;        /*Function to initialize the Hash table*/
void DestroyTable（）;                        /*Function to destroy the Hash table and free the memory*/
Position Find（char * key）;                  /*Find functiong to get the position of KEY*/
void Insert（char * keyint segnumberint FLAG）;  /*Insert the KEY to Hashtable*/
void Input （char *** Poem  int seg  int line）;  /*Read the Poem*/
void Output （char *** Poem  int seg  int line）; /*Output the Poem to an output file*/

struct HashEntry           /*The structure of each HashTable element CELL*/
{
	char Element[80];/*Used to store the content of each First line or Last line*/
	int Head;        /*First line TAG of each segment used to store the segment number of each “First line“*/
	int Tail;        /*Last line TAG of each segment  used to store the segment number of each “Last line“*/
};

struct HashTbl
{
	int TableSize;
	Cell * TheCells;
};

/*******************************Global Variables definition**********************************/

FILE *fp;     /*To read a file “input.txt“*/
FILE *fout;   /*To output data to  the file “output.txt“*/
HashTable H;
int Scenario_number=1;   /*variable to record the scenario number  Initial value is 1*/

/**************************Functions to operate the Hash table*************************************/

Index Hash（const char * keyint TableSize）
{
	unsigned long int HashVal=0;
	
	while（*key!=‘\0‘）
		HashVal=（HashVal<<5）+*key++;
	
	return HashVal%TableSize;  /*Hash function to return the position of KEY in the Hash table H*/
}

void InitializeTable（int TableSize）
{

	int i;
	
	H=malloc（ sizeof（ struct HashTbl ） ）;  /*Allocate memory for H*/
	if（H==NULL）
		printf（“out of space!!“）;
	
	H->TableSize=TableSize;        /*Initial size*/
	
	H->TheCells=malloc（sizeof（ Cell ） * H->TableSize）;  /*Allocate memory for H->TheCells*/
	if（H->TheCells==NULL）
		printf（ “out of space!!“ ）;
	
	for（i=0;iTableSize;i++）
	{
		H->TheCells[i].Element[0]=‘\0‘;   
		H->TheCells[i].Head=-1;       /*Initial value is -1   means it is empty */
		H->TheCells[i].Tail=-1;	      /*Initial value is -1  means it is empty */
	}
	
	return;
}

void DestroyTable（）            /*Destroy the Hash table*/
{
	free（H->TheCells）;         /*Free the  memory of H->TheCells*/
	free（H）;                   /*Free the memory of  H */
	return;
}

Position Find（char * key）
{
	Position CurrentPos;
	int CollisionNum;
	
	CollisionNum=0;   /*To record the collision numbers */
	CurrentPos=Hash（keyH->TableSize）;   /*Using Hash function to get the first Position of KEY*/
	
	while（ !（H->TheCells[CurrentPos

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        452  2008-10-04 20:38  G06\G06\code\input.txt

     文件       6931  2008-10-04 20:25  G06\G06\code\Project2.c

     文件     196655  2008-10-04 20:25  G06\G06\code\Project2.exe

     文件        496  2008-10-04 20:40  G06\G06\code\Readme.txt

     目录          0  2008-10-08 10:04  G06\G06\code

     目录          0  2009-03-03 21:43  G06\G06

     目录          0  2009-03-03 21:43  G06

----------- ---------  ---------- -----  ----

               204534                    7