KJHの博客

记录&回忆

0%

发表于 更新于 分类于
本文字数： 3.7k 阅读时长 ≈ 3 分钟

哈希表，也叫散列表，是根据关键字而直接访问在内存存储位置的数据结构。也就是说，它通过把键值经过一个映射函数的计算，映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称作散列函数，存放记录的数组称作散列表。

由哈希表的定义可知，散列函数关系到关键字映射到什么散列表的什么位置，实际上散列表的单元是有限的，但是关键字的个数却往往远大于该单元个数，我们必须又同时保证每个关键字通过映射函数的计算都会对应到散列表的某个位置，这样不可避免的就存在冲突的问题，即多个关键字对应于散列表的同一位置，我们必须解决这个问题。

所以哈希表就有了两个关键点：散列函数和解决冲突。散列函数和解决冲突的方法请参考维基百科，这里不做赘述。

这里的散列函数采用除留余数法，解决冲突采用分离链接法。

阅读全文 »

发表于 更新于 分类于
本文字数： 2.6k 阅读时长 ≈ 2 分钟

平衡二叉树是一棵带有平衡条件的二叉查找树，其删除操作是在二叉查找树的基础上添加平衡调整算法。

二叉查找树的删除操作参见博文：二叉查找树的删除（第七点）

先看一下示意图（）

/二叉查找树的性质让我们可以很方便的查找最小最大键值/

阅读全文 »

发表于 更新于 分类于
本文字数： 4.3k 阅读时长 ≈ 4 分钟

AVL 树是带有平衡条件的二叉查找树，所谓的平衡条件就是每个节点的左子树和右子树的高度最大差别为1。平衡二叉树的实现大部分过程和二叉查找树是一样的，区别在于要时刻保持树的平衡，所以在插入和删除之后要添加一个旋转算法来保持平衡，保持平衡需要借助一个节点高度的属性。

一、AVL 节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class AvlTree;

class AvlNode
{
public:
	AvlNode(int val) :data(val), leftchild(NULL),
		rightchild(NULL)/*, height(0)*/ {}
	//~AvlNode();
	friend class AvlTree;

private:
	int data;
	AvlNode *leftchild;
	AvlNode *rightchild;
//	int height;
};

AVL 节点同二叉查找树节点类似，这里可以额外添加一个节点的高度属性，来判断是否平衡。考虑到后面都需要函数来获取节点的高度以及尽量减少类对象的大小，这里单独通过函数获取高度属性并比较（后面程序）。

阅读全文 »

发表于 更新于 分类于
本文字数： 4k 阅读时长 ≈ 4 分钟

二叉堆（也叫堆）是一个部分排序的二叉树，其排序规则体现在它的堆序性质上：最大堆和最小堆，最大堆就是其对于任一节点，每个节点的键值都大于等于它的孩子节点，所以根节点键值最大。最小堆则相反。

堆是一棵完全二叉树，具备完全二叉树的性质，可以用一个数组表示而不需要指针，在起始位置为 0 的数组中任一位置 i 上的元素，其左儿子在位置 2*1+1 上，右儿子在左儿子的后面邻近位置上，它的父节点则在位置 (i-1)/2。因此，一个堆数据结构将由一个数组（不管键值是什么类型）、一个代表最大容量的整数以及当前的堆大小组成。

下面用C++ 来实现堆，并补充基于堆这一数据结构上的堆排序，不同于前面介绍的堆排序

  1. 堆的类结构
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template <class Elem>
class BinaryHeap
{
public:
	BinaryHeap(int MaxSize = 50);
	BinaryHeap(const BinaryHeap<Elem> &rhs);
	BinaryHeap(Elem *Array, int ElemNum, int MaxSize);
	~BinaryHeap(void);

	Elem *Sort(void);              //堆排序
	bool Add(const Elem &Item);    //添加元素
	Elem Remove(void);             //移除（堆顶）元素
	 
	inline int GetSize(void);      //获取当前堆大小

protected:
	Elem *Data;                    
	int CurrentNum;
	const int MAX_SIZE;

	void HeapifyUp(int Node);            //向上调整堆  
	void HeapifyDown(int Node);          //向下调整堆
	 
	inline int ParentOf(int Node);       //得到节点的父节点位置
	inline int LeftChildOf(int Node);    //得到节点的左儿子位置

};
  1. 构造函数，拷贝构造函数，析构函数
阅读全文 »

发表于 更新于 分类于
本文字数： 6.7k 阅读时长 ≈ 6 分钟

对于二叉查找树，前面有博文介绍：关于二叉树的三种遍历方式介绍，参见前面链接。二叉树的遍历关键在于：出的去要回得来。以中序遍历为例，先遍历左子树，再访问根节点，最后遍历右子树，当遍历完左子树，即发现访问到左子树的叶子节点了，下一步便是访问该叶子节点的根节点，再右子树。接下来还需要一层一层的回到根节点。这就给了我们提示，如何在非递归的情况下，遍历二叉树：保存回去的路或搭建回去的桥。这里先讨论第一种，提供栈实现迭代的方法，即直接导用STL 中的 stack 容器保存回去的路实现。需要注意的是压栈的顺序将直接影响到树的下一层压栈的顺序，因为栈这一数据结构每次只能提取栈顶的元素。

代码其余部分下载：http://download.csdn.net/detail/yeswenqian/6977693

阅读全文 »