散列表

Share

散列表是什么？

我在静态查找表与静态查找表两篇文章中表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和给定值比较的关键字个数。

用这类方法表示的查找表，其平均查找长度都不为0。不同的表示方法，其差别仅在于：关键字与给定值进行比较的顺序不同。

More →

红黑树C实现

Share 
红黑树是一门玄学，想活着就千万不要想我一样去碰他（吐出一口老血）

这个轮子是我到目前写的最复杂的一个数据结构的轮子，没有之一。

具体关于红黑树的文章我会在过几天整理出来。

先看代码吧，里面有注释。

More →

动态查找表

Share

由静态查找表观察，可得一下结论

  • 从查找性能看，最好情况能达O(logn)，此时要求表有序
  • 从插入和删除的性能来看，最好情况能达O(1)，此时要求存储结构为链表

本篇文章是对各种查找树的一个简单概括，具体分析会慢慢更新

More →

静态查找表

Share

静态查找表：仅做查询和检索操作的查找表

假设静态查找结构为

1
2
3
4
5
6
typedef struct {
	elemType *elem;
	//数据元素存储空间基址，建表时按数据长度分配，0号单元留空
	int length;
	//表的长度
}SSTable;

More →

二叉查找树

Share

查找树(search tree)是一种数据结构，它支持多种动态集合操作，包括 SEARCH , MINIMUN , MAXIMUN , PREDECESSOR , SUCCESSOR , INSERT 以及 DELETE。它既可以用作字典，也可以用作优先队列。

在二叉查找树(binary search tree)上执行的基本操作的时间与树的高度成正比。对于一颗含有n个结点的完全二叉树，这些操作的最坏运行时间为O(lgn)。但是，如果树是含有n个结点的线性链，则这些操作的最坏情况为O(n)。在下文可以看到，一颗随机构造的二叉查找树的期望高度为O(lgn)，从而这种树上基本动态集合的平均操作时间为O(lgn)

More →