1.cpp

数据结构算法的小作业

#include <iostream.h>
#include <cstring>
#include <windows.h>
#include <fstream.h>

const int SIZEA = 17;


class NumDict{//测试用的类
private:
	int k;
	char english[20];
	NumDict * next;
	//int length;
public:
	NumDict(){ k=-1; strcpy(english,"");next=NULL; }
	NumDict( int a, char *  eng ){ k=a; strcpy(english,eng);next=NULL; }
	int getkey(){ return k; }
	char * getdata(){ return english; }
	
};

NumDict TOMB(-255,"TOMB");//删除元素后标记用的墓碑

class NumDictComp{//测试用的比较类
public:
	static bool lt(NumDict x, NumDict y){ return x.getkey()<y.getkey(); };
	static bool eq(NumDict x, NumDict y){ return x.getkey()==y.getkey(); };
	static bool eq(int x, NumDict y){ return x==y.getkey(); };
	static bool gt(NumDict x, NumDict y){ return x.getkey()>y.getkey(); };
};

//class intComp{
//public:
//	static bool lt(int x, int y) {return x < y;};
//	static bool eq(int x, int y) {return x == y;};
//	static bool gt(int x, int y) {return x > y;};
//};

//散列表hashdict2

template< class Key, class Elem, class EEComp >
//Key:   关键码类型
//Elem:  存储在中的数据记录或元素的类型
//KEComp:关键码与元素进行比较的类
//EEcomp:关键码与关键码进行比较的类

class hashdict2{				  //散列字典类(开散列方法)
	
private:

	Elem ** HT;				  //散列表
	int M;					  //散列表大小
	int current;		 	  //现有元素数目
	Elem EMPTY;				  //空槽 

	int h( int x ) const{	  //散列函数int( 除余法 )
		return x % M;
	}
	int h( char * str ) const{//散列函数char *( ELFhash字符串散列函数 )
		unsigned long h = 0;
		while( * str ){
			h = ( h << 4 ) + * key ++;
			unsigned long g = h & 0xF0000000L;
			if( g )
				h ^= g >> 24;
		}
		return h % M;
	}

public:

	hashdict2( int size, Elem e ){					//构造函数,e用来定义空槽
		M = size;
		EMPTY = e;
		current = 0;
		HT = new Elem*[ size ];
		for( int i = 0; i < M; i ++ )
			HT[i] = EMPTY;
	}
	~ hashdict2(){									//析构函数
		delete [] HT;
	}
	
	int getkey(Elem e) {							//取关键码函数
		return e.getkey();
	}
	bool hashSearch( const Key & K, Elem & e ) { //检索函数

		Elem * tmp = HT[h( K )];


	}
	bool hashInsert( const Elem & e ){			    //插入函数
		int home = h( getkey( e ) );
		int i = 0, insplace;
		bool tomb_pos = false;
		int pos = home;			//探查序列的初始位置
		
		while( ! EEComp::eq( EMPTY, HT[pos] ) ){
			if( EEComp::eq( e, HT[pos] ) )
				return false;
			if( EEComp::eq( TOMB, HT[pos] ) && ! tomb_pos ){
				insplace = pos;	//记录第一个墓碑的问题
				tomb_pos = true;
			}
			i ++;
			pos = ( home + p( getkey( e ), i ) ) % M;
		}
		if( ! tomb_pos )
			insplace = pos;		//如果没有墓碑,插入空位置
		HT[ insplace ] = e;		//插入e
		
		return true;
	}
			
	Elem hashDelete( const Key & K ){				//删除函数
		
		int home = h( K );
		int i = 0;
		int pos = home;
		
		while( ! EEComp::eq( EMPTY, HT[pos] ) ){
			if( EEComp::eq( K, HT[pos] ) ){//yuansuuuuuuuuuuuuuuuuuuuuuu ke -> ee
				NumDict temp = HT[pos];
				HT[pos] = TOMB;
				return temp;
			}
			i ++;
			pos = ( home + p( K, i ) ) % M;
		}
		
		return EMPTY;
	}

	int size(){								 		 //散列表中现有元素数
		return current;
	}
	void Display(){									 //打印函数

		for (int i = 0; i < M; i ++)
			cout << HT[i].getkey() << " " << HT[i].getdata() << endl;

		cout << endl;
	}
};

void welcome();						  //欢迎界面
void gotoxy(int,int);				  //光标定位函数


void main(){
	//welcome();
	//NumDict A[] = { NumDict(26,"twenty-six"), NumDict(36,"thirty-six"), NumDict(41,"forty-one"), NumDict(38,"thirty-eight"), NumDict(44,"forty-four"),
	//NumDict(15,"fifteen"),NumDict(68,"sixty-eight"), NumDict(12,"twelve"), NumDict(6,"six"), NumDict(51,"fifty-one"), NumDict(25,"twenty-five")};
	//int n = sizeof(A)/sizeof(NumDict);							 // 建立HASH表
	
	//int n = 10;
	hashdict2<int, NumDict, NumDictComp> aHash( SIZEA, NumDict() ); // 插入HASH关键码
	ifstream fin( "data.txt", ios::in );

	int tmp;
	char tmpc[20];
	while( fin>>tmp&&tmp!=-1){
		fin>>tmpc;
		aHash.hashInsert( NumDict( tmp, tmpc ) );
	}

	//for (int i = 0; i < n; i ++){

	//	aHash.hashInsert(A[i]);

	//}
	aHash.Display(); //输出结果

	cout << "插入? 输入数据，格式: 整数 + 空格 + 字符串" << endl;
	
	//int e;

	//if (aHash.hashSearch(68, e))
	//	cout << "Find is : " << e << endl << endl;
	//else
	//	cout << "No Find" << endl << endl; // 删除一个关键码
	cout << "Delete which?" << endl;
	int del;
	cin >> del;
	aHash.hashDelete(del);
	aHash.Display();
}