程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 算法導論之十(十一章散列表11.1

算法導論之十(十一章散列表11.1

編輯:關於C++

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;
}







  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved