首页 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
资讯 业界资讯 软件杂谈 编程开发 网站建设 网络观查 搜索引擎 移动应用 网站运营 网络地图
开发 移动开发 Web前端 架构设计 编程语言 互联网 数据库 系统运维 云计算 开发杂谈
[编程语言] 算法导论之十(十一章散列表11.1
算法导论之十(十一章散列表11.1

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













 此文从网络中自动搜索生成,不代表本网站赞成被搜索网站的内容或立场    查看原文
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 新闻资讯 小游戏 Chinese Culture 股票 三丰软件 开发 中国文化 网文精选 阅读网 看图 日历 万年历 2018年11日历
2018-11-16 10:55:11
 
  网站联系 软件世界网-www.sjsjw.com ©2014 蜀ICP备06016416号 三峰网旗下网站