算法導論之十(十一章散列表11.1-4大數組實現直接尋址方式的字典操作)

11.1-4題目：

我們希望在一個非常大的數組上，通過利用直接尋址的方式來實現一個字典。開始時，該數組中可能包含一些無用信息，但要對整個數組進行初始化是不太實際的，因為該數組的規模太大。請給出在大數組上實現直接尋址字典的方式。每個存儲對象占用O(1)空間；SEARCH、INSEART、DELETE操作的時間均為O(1)；並且對數據結構初始化的時間為O(1)。(提示：可以利用一個附加數組，處理方式類似於棧，其大小等於實際存儲在字典中的關鍵字數目，以幫助確定大數組中某個給定的項是否有效)。

想法：

由於大數組太大，不能初始化，我們也就等於不知道到底哪裡有真正的數據，於是乎數據不能存儲在大數組中，因為你根本不知道到底哪裡才是數據。

這裡方式是：將數據存儲到棧上，棧上的增刪查都可以實現O(1)，然後在大數組上，對應key的位置的元素，存放棧上對應的下標，這樣根據key到大數組中找到棧的下標，然後根據棧的下標又可以找到那個key值對應的數據元素了。

然後，還需要解決如何判斷數據是否有效的問題，這個也很簡單，經過上面的查找過程，不難發現，如果該數據是有效的，需要滿足以下幾個條件：

1、key值對應到大數組中位置的值，必須位於[0，棧的棧頂位置]之間，否則肯定不是數據

2、滿足第1條之後，我們到棧上對應的位置，找到那個元素數據，它的key值要反過來等於我們原始的key值，否則表示這個數據也是不存在的。可以參見下面代碼中的isExist函數的寫法；

數據元素類型：_node.h

class node {
public:
	int key;
	node(int key) :
			key(key) {
	}
	node() :
			key(-1) {

	}
};

棧類，存放真實數據：_stack.h

#include 
#include "_node.h"
using namespace std;

/*
 * 用於存放數據的棧，使用單數組實現，這裡的數據為node類型，裡面包含一個key值
 */
class Stack {
	int size;
public:
	int top;
	node* array;

	Stack(int size) :
			size(size), top(-1) {
		array = new node[size];
	}

	~Stack() {
		//做一些內存回收工作
		delete[] array;
	}

	//入棧
	void push(int* hash, int key) {
		if (top == size - 1) {
			cout << "error:stackoverflow" << endl;
			return;
		}

		top++;
		array[top].key = key;

		//讓hash數組中對應key位置的元素與棧上top位置元素掛鉤
		hash[key] = top;
	}

	//出棧
	int pop(int* hash, int key) {
		if (top == -1) {
			cout << "error:stackunderflow" << endl;
			return -1;
		}

		int tmp = array[top].key;
		top--;

		//更新hash表，讓其等於-1，因為棧數組下標不可能為-1，方便以後判斷
		hash[key] = -1;

		return tmp;
	}

	void travel() {
		if (top < 0) {
			return;
		}
		int tmp = top;
		while (tmp >= 0) {
			cout << array[tmp--].key << ' ';
		}
		cout << endl;
	}

	/*
	 * 將pos位置的值與棧頂的值交換
	 */
	void swapTop(int* hash, int key) {
		int pos = (hash)[key];
		//更新散列表
		hash[array[top].key] = pos;
		hash[array[pos].key] = top;

		//交換操作，更新棧
		node tmp = array[top];
		array[top] = array[pos];
		array[pos] = tmp;
	}

};

demo.cpp，包含hash類：

#include 
#include "_stack.h"
using namespace std;

class Hash {

public:
	int* hashArray; //用於存放棧中位置的數組，該數組下標對應於key值

	Stack* s; //存放真實數據的棧

	//構造
	Hash(int hashSize, int stackSize) :
			hashArray(), s() {

		hashArray = new int[hashSize];

		s = new Stack(stackSize);
	}

	//析構
	~Hash() {
		delete[] hashArray;
		delete s;
	}

	//判斷key值是否已經存在的函數
	bool isExist(int* hash, int key) {
		if (hash[key] <= s->top && hash[key] >= 0
				&& key == s->array[hash[key]].key) {
			return true;
		}
		cout << "key does not exist!" << endl;
		return false;
	}

	//插入一個數據
	void insert(int key) {
		s->push(this->hashArray, key);
	}

	//刪除一個數據
	void delete_(int key) {

		//判斷是否存在
		if (!isExist(this->hashArray, key)) {
			return;
		}
		//將對應的棧上的位置的數據與棧頂數據交換，同時刷新hash數組中的值，使其指向正確的棧數組元素
		s->swapTop(this->hashArray, key);

		//出棧，同時刷新hash數組中的值
		s->pop(this->hashArray, key);
	}

	//查找是否已經包含key值
	node* search(int key) {
		if (!isExist(this->hashArray, key)) {
			return NULL;
		} else {
			return s->array + hashArray[key];
		}
	}

	//遍歷所包含的元素
	void travel() {
		int tmp = s->top;
		while (tmp >= 0) {
			cout << s->array[tmp--].key << ' ';
		}
		cout << endl;
	}

};

int main() {

	//測試使用hash數組大小為1000，存放數據的棧大小為100
	Hash* hash = new Hash(1000, 100);

	cout << hash->search(555) << endl;
	hash->insert(555);
	hash->insert(444);
	hash->insert(333);
	hash->travel();
	hash->delete_(555);
	hash->travel();
	cout << hash->search(333)->key << endl;

	return 0;
}