shenyu
- 浏览: 122540 次
- 性别:
- 来自: 上海
-
文章列表
选择排序
，原理与冒泡
类似，相比之下，交换的时间效率为O(n)，比较的时间效率依然为O(n^2)
代码如下，程序简单，没有提供注释。
class Select {
public static void main(String[] args) {
int[] a = {2,4,6,3,6,2,6,4,9};
sort(a);
print(a);
}
private static void sort(int[] a) {
int temp;
for(int i=0; i<a.leng ...
- 2008-04-27 17:44
- 浏览 1484
- 评论(0)
与2-3-4树
相似，2-3 平衡树是一种搜索树。
但由于每个节点最多有两个数据，分裂算法需要新插入数据的参与，这导致算法与2-3-4树
有一定的差异。
每个节点可能会有2,3,4个子节点，对应可能会有1,2,3个数据。子节点数＝数据数 ＋ 1，不可能有空节点。
插入数据时，树向下遍历以得到恰当的叶子节点时，数据均插入叶子节点，如果子节点需要分裂，则进行节点分裂，分裂产生的新数据向父节点插入，如果父节点是满的，则向上递归调用此过程。当根节点分裂，所有叶子节点的层高都增加一层，以此原理来保证树的平衡。因为分裂需要第三个数据，所以是在插入之后分裂节点的，这与2-3-4树
的插 ...
2-3-4 平衡树是一种搜索树。每个节点可能会有2,3,4个子节点，对应可能会有1,2,3个数据。子节点数＝数据数 ＋ 1，不可能有空节点。
插入数据时，数据均插入叶子节点，树在向下遍历以得到恰当的叶子节点时，每遇到满的节点，则进行节点分裂，当分裂向上累积致根节点位置，根节点分裂，所有叶子节点的层高都增加一层，以此原理来保证树的平衡。
此树没有实现删除数据的算法，如果需要，可考虑将数据标志为作废的方式，以避免真正的删除时的复杂。
插入的数据为了简便起见，假设均为Integer，且不会重复。
方法ordinal是升序打印，为的是测试。
Tree.main 函数提供一个简短的测试。
Node类为辅助 ...
用邻接表法表示的双向图（改单向容易，只要修改connect,disconect方法）。
此处只是表示数据结构，没有相关算法。
其中Vertex是辅助类表示顶点，其中包含一个boolean变量isVisited表示是否遍历过。
Graph表示图，实际存储顶点，以及顶点之间的关系，用一个数组存储顶点，另一个数组中存放与对应的顶点的相连的的顶点的下标。
大部分的代码实际是辅助代码，其中包括：
Vertex：顶点，其中包含一个Boolean变量，表示是否遍历过。
Node，Link：一个单向链表，存储与当前顶点向邻的节点的下标。（单向链表的详细描述见：Link
)
Graph的另一个实现请参见Graph ...
- 2008-04-17 00:08
- 浏览 3003
- 评论(0)
用邻接矩阵法表示的双向图（改单向容易，只要修改connect,disconect方法）。
此处只是表示数据结构，没有相关算法。
其中Vertex是辅助类表示顶点，其中包含一个boolean变量isVisited表示是否遍历过。
Graph表示图，实际存储顶点，以及顶点之间的关系（用二维数组表示）
另一个实现请请参见
class Vertex {
private Object value;
private boolean isVisited;
Vertex(Object value) {
this.value = value;
}
void visit() { isVisited ...
- 2008-04-16 22:56
- 浏览 3533
- 评论(1)
用下面这个例程测试同样的赋值通过反射方式，和通过普通方式（set方法）下的效率差别。
在作者当前的系统下（Linux:ubuntu7.10 java-sun-6)：
反射赋值：set方式 = 170：1 或者 171：2
效率差别还是比较明显。
import java.lang.reflect.*;
class Person {
private int age;
public void setAge(int age) { this.age = age; }
}
class Test {
private static final int TIMES = 10000 ...
- 2008-04-16 18:18
- 浏览 1509
- 评论(0)
这里的堆不是java中内存分配的堆。只是一种数据结构。
堆是二叉满树，满足条件：父节点的键值大于两个子节点的键值，这不同于二叉搜索树（见Tree），堆对于实现优先级队列是一种好的方式，相对于利用数组的优先级队列
，利用链表的优先级队列
来说，其插入与删除的效率都是O(log n)
此堆的实现使选择数组作为内部数据结构，使得此堆能容纳的数据有限，但找到最下一层的作右子节点比交方便。用数组存储树时，求当前节点的父节点和左右子节点的公式如下：假设当前节点坐标为x：
父节点：(x-1)/2
左子节点：2 * x + 1
右子节点：2 * x + 2
API如下：
Heap：构造并指定需要的空间大 ...
- 2008-04-16 00:28
- 浏览 1469
- 评论(0)
HashTable 基于链表地址法
- 博客分类：
- 数据结构
功能上于前面两个HashTable（－）
，HashTable（二）
一致，但实现上采用的链表表示每个Hash桶的位置，这样理论上不用考虑容量问题。实际中HashTable中的每个SortLink太长会导致效率低下，因此HashTable的初始大小比较重要。
链表使用的是有序链表SortLink，这样查找，删除的效率会提高一半，但是新增则会从O(1)降到链表的平均长度的一半。考虑链表不是太长，所以不会对效率产生太大的影响。但终究来说，这种实现更适合查询，不适合大量反复的插入。
关于可以插入的数据的键值，此处假设为整数。
代码中有许多辅助类
其中：
Item：装载有key（关键值）的数据
Node ...
- 2008-04-15 00:49
- 浏览 1646
- 评论(0)
HashTable 基于开放地址法(二）
- 博客分类：
- 数据结构
与前一个HashTable
基本相同（方法说明请参照它），只是当发生Hash冲突时，采用再用哈希法探测步长。
前面当发生Hash冲突时，直接看当前位置下一个有没有空位，这相当于步长为一，但这容易产生聚集，大的聚集产成后Hash的效率会下降，采用Hash法采用的是使用不同的Hash函数来产生一个新的步长。
新的hash有以下要求
非0
与第一个Hash函数不同
除此之外：
这个HashTable的size要求是质数,因此是靠程序自己计算出来的。
基于链表的HashTable请参见HashTable
public class Item {
private int key;
priv ...
- 2008-04-14 19:40
- 浏览 2012
- 评论(0)
HashTable 基于开放地址法
- 博客分类：
- 数据结构
该HashTable基于定常数组的开放地址法，搜索时采用线性探测发
由于删除时使用标志的做法，因此该HashTable常作删除会导致效率的下降。
为了保证此表的操作效率，数组的大小为所需要存储的数据的两倍。如果再细致一些，应该是大于其两倍的的第一个质数，这样可以减小Hash冲突的可能性，不过这里没有这样作，同样是为了代码清晰。
HashTable的遍历不占优势，此处没有实现。
API
find：查找指定键的数据项目
add：添加新数据
remove：删除指定键的数据项目
Item为辅助类，为了简便，关键字使用非负整数，且没有采用标准的set，get方法
HashTable.main提供一个简便的 ...
- 2008-04-13 22:59
- 浏览 1584
- 评论(0)
每个节点最多两个子节点，其中左边节点的值小于该节点的值，右边节点的值大于该节点的值。为了简便起见，该二叉树装入的数据为整数，且不允许有重复的关键字值。
编程中为了简便，采用了递归算法，运算时会带来额外的开销，如果能将相应的算法替换为迭代，则更为有效。删除的算法相应复杂一些，但也可以承受。
API
add：将数加入树
remove：从树中删除指定的节点
contains：树中是否包含指定的数
ordinal：从小到大遍历打印数（测试只用）
max：查找最大值
min：查找最小值
其中Node类是辅助类，为了简单没有写标准的 get，set方法。
因为该树没有自我保持平衡的能力，因此对于随机插入 ...
- 2008-04-11 00:03
- 浏览 1710
- 评论(0)
提供一个基于链表的优先级队列，为了简便，只存储整数，假设数值越大，优先级越高。工作时该队列按照数值的大小排列，出队时出优先级别最高的元素。这已经不是普通意义上的队列（先进先出），叫优先级队列只是习惯。put：入队get：出队isEmpty：是否为空 普通队列请参见LinkedQueue，Queue相对与另一个实现（PriorityQueue），这个优先级队列没有容量的限制。Node是辅助类，提供节点的数据结构，为了简便，没有使用标准的set，getclass Node {
private int value;
private Node next;
Node(int value) {
...
- 2008-04-06 17:57
- 浏览 3449
- 评论(0)
提供一个基于定长数组的优先级队列，为了简便，只存储整数，假设数值越大，优先级越高。工作时该队列按照数值的大小排列，出队时出优先级别最高的元素。这已经不是普通意义上的队列（先进先出），叫优先级队列只是习惯。构造函数：初始化队列大小put：入队get：出队isEmpty：是否为空 普通队列请参见LinkedQueue，Queue另一个实现基于定长数组，见(PriorityQueue) class PriorityQueue {
private int[] array;
private int top = -1;
PriorityQueue(int capacity) {
array = ...
- 2008-04-06 16:57
- 浏览 4346
- 评论(0)
指定最大值的队，底层用数组实现构造函数：指定最大容量put：放入get：取出isEmput：是否为空其他实现请参考LinkedQueueclass Queue {
private int length;
private int begin = -1;
private int end = -1;
private int[] array;
Queue(int capacity) {
array = new int[capacity];
}
void put(int value) {
assert length < array.length;
if(end == ...
- 2008-04-06 13:36
- 浏览 1547
- 评论(1)
用Array实现的栈结构，功能与LinkedStack一致编程上略微比LinkedStack复杂class ArrayStack {
private Array array = new Array();
private int pos = -1;
void push(int value) {
array.set(value,++pos);
}
int pop() {
assert pos > -1;
int result = array.get(pos);
array.truncate(pos--);
return result;
}
boolean ...
- 2008-04-06 12:00
- 浏览 1299
- 评论(0)