文档章节

静态查找表的实现

把南墙撞开
 把南墙撞开
发布于 2017/02/03 23:22
字数 706
阅读 2
收藏 0
#ifndef SSTABLE_H
#define SSTABLE_H

#include <iostream>
using namespace std;

/*************************************************************
SSTable:stastic search table
静态查找表的模板类实现
顺序存储结构
*************************************************************/

template <typename ElemType>
class SSTable
{
private:
	ElemType *elem;
	int length;

public:
	SSTable();
	SSTable(const SSTable &rhs);
	void clear();
	const SSTable& operator=(const SSTable &rhs);
	~SSTable();

	void create(const ElemType *r, int n);
	void ascend();
	void createOrder(const ElemType *r, int n);
	void show() const;

	/*模板类中的模板方法
	@function 从后向前顺序查找关键字为key的元素
	@parameter key ElemType中的关键字
	@return 返回关键字为key的元素在静态查找表中的位置,若无关键字为key的元素则返回0
	*/
	template <typename KeyType>
	int searchSeq(KeyType key) const
	{
		//将key包装进临时ElemType对象tmp中
		ElemType tmp;
		tmp.key = key;

		//将0号下标元素置为临时对象tmp,起哨兵作用
		elem[0] = tmp;
		int i = length;
		while( elem[i].key != elem[0].key)
			--i;
		return i;
	}


	/*模板类中的模板方法
	@function 对排序表二分查找关键字为key的元素
	@parameter key ElemType中的关键字
	@return 返回关键字为key的元素在静态查找表中的位置,若无关键字为key的元素则返回0
	*/
	template <typename KeyType>
	int searchBin(KeyType key) const
	{
		int low = 1;
		int high = length;
		while (low <= high)
		{
			int middle = (high + low) / 2;
			if (elem[middle].key == key)
				return middle;
			else if (elem[middle].key < key)
				low = middle + 1;
			else
				high = middle - 1;
		}
		return 0;
	}
};

//默认构造函数
template <typename ElemType>
SSTable<ElemType>::SSTable()
{
	elem = nullptr;
	length = 0;
}

//复制构造函数
template <typename ElemType>
SSTable<ElemType>::SSTable(const SSTable &rhs)
{
	length = rhs.length;
	elem = (ElemType *)calloc(length+1, sizeof(ElemType));
	for (int i = 1; i <= length; ++i)
		elem[i] = rhs.elem[i];
}

//置空函数
template <typename ElemType>
void SSTable<ElemType>::clear()
{
	if (elem != nullptr)
		free(elem);
	elem = nullptr;
	length = 0;
}

/*
*赋值函数
*@call clear()
*/
template <typename ElemType>
const SSTable<ElemType>& SSTable<ElemType>::operator=(const SSTable &rhs)
{
	clear();
	elem = (ElemType *)calloc(length);
	for (int i = 1; i <= length; ++i)
		elem[i] = rhs.elem[i];
	length = rhs.length;
}

//析构函数
template <typename ElemType>
SSTable<ElemType>::~SSTable()
{
	clear();
}

/*
*@function 根据一个大小为n的ElemType型数组,初始化SSTable对象
*@parameter r 一个ElemType型的数组
*@parameter n  数组r的大小
*/
template <typename ElemType>
void SSTable<ElemType>::create(const ElemType *r, int n)
{
	//分配大小为n+1的数组,0号位置不放元素
	elem = (ElemType *)calloc(n + 1, sizeof(ElemType));
	if (elem == nullptr)
		exit(-1);
	for (int i = 0; i < n; ++i)
		elem[i+1] = r[i];
	length = n;
}

//将elem指向的数组进行比较排序,递增
template <typename ElemType>
void SSTable<ElemType>::ascend()
{
	int index;
	for (int i = 1; i <= length; ++i)
	{
		index = i;
		for (int j = i + 1; j <= length; ++j)
			if (elem[j].key < elem[index].key)
				index = j;
		ElemType tmp = elem[i];
		elem[i] = elem[index];
		elem[index] = tmp;
	}
}

/*
*@function 根据一个大小为n的ElemType型数组,初始化SSTable对象,SSTable中elem所指向的数组为递增排序
*@call create(const ElemType *r, int n)
*@call ascend()
*@parameter r 一个ElemType型的数组
*@parameter n  数组r的大小
*/
template <typename ElemType>
void SSTable<ElemType>::createOrder(const ElemType *r, int n)
{
	create(r, n);
	ascend();
}

//将elem指向的数组输出到控制台
template <typename ElemType>
void SSTable<ElemType>::show() const
{
	for (int i = 1; i <= length; ++i)
		cout << elem[i].key << " ";
	cout << endl;
}

#endif

本文转载自:http://blog.csdn.net/weixin_37289816/article/details/54695766

把南墙撞开
粉丝 0
博文 73
码字总数 21068
作品 0
昌平
私信 提问
算法——顺序查找和二分查找

顺序查找(无序链表): 符号表中使用的数据结构的一个简单选择就是链表,每个结点存储一个键值对。get()方法和put()方法的实现即为遍历链表。代码实现如下: 性能分析: 在表中查找一个不存...

嘿胖丁
2018/03/08
4
0
Nginx中hash表的设计与实现

在nginx中使用的hash中一个非常核心的函数就是ngxhashinit,由于nginx这个hash表是静态只读的,即不能在运行时动态添加新元素的,一切的结构和数据都在配置初始化的时候就已经规划完毕,所以...

晓亮1210
2013/12/18
0
0
红黑树与Hash的区别与选择

什么是Hash Hash,也可以称为“散列”,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。这是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同...

Hosee
2016/02/23
2.2K
0
查找——顺序查找

一、顺序查找的概念 顺序查找(Sequential Search)是最简单的一种查找方法。其基本思想是:从线性表的一端开始,依次将每个记录的关键字与给定值进行比较,若某个记录的关键字等于给定值,表示查找...

翼动动空
2016/06/27
3.5K
0
3、HashMap与HashTable

一、 数组: 存储区间是连续的,占内存严重 易查找、插入删除困难 链表: 存储区间是离散的,占内存少 难查找,插入删除容易 哈希表: 查找易、插入删除也易 原理: hash表是由 数组+链表 组...

李李李李格儿楞
2018/04/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

typescript 接口 函数类型 可索引类型

函数类型 可索引类型 数字索引签名 字符串索引签名 数字索引签名返回值 必须是 字符串索引签名返回值的子集 只读索引签名

lilugirl
今天
3
0
Oracle SQL语法实例合集

如需转载请注明出处https://my.oschina.net/feistel/blog/3052024 目的:迅速激活Oracle SQL 参考:《Oracle从入门到精通》 ------------------------------------------------------------......

LoSingSang
今天
2
0
增加 PostgreSQL 服务进程的最大打开文件数

https://serverfault.com/questions/628610/increasing-nproc-for-processes-launched-by-systemd-on-centos-7 要在systemd的配置里加才行...

helloclia
今天
2
0
组合模式在商品分类列表中的应用

在所有的树形结构中最适合的设计模式就是组合模式,我们看看常用商品分类中如何使用。 先定义一个树形结构的商品接口 public interface TreeProduct { List<TreeProduct> allProducts(...

算法之名
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部