#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