呼...今天在家蹲了一天,除了中午出去去单位办房子的手续.虽然没有办成,少了一些必要的条件.
其余的,最近比较累,越发得累...我想,贵在坚持吧.还能怎么样呢.只能这样了.呵呵.听起来像是很悲观,其实,还是很乐观的.
好久没有代码出来了,真够郁闷的啊!确实!郁闷得够呛啊!简直,都因为这个有些烦躁了...
还好吧...今天辛苦了一天,屁股坐得直疼,还好写出来了.一点小欣慰.
连纸上研究,再代码实现...加起来大概用了20小时.只比这个时间多,不比这个时间少了啊.
写这个东西,居然对指针加深了了解.虽然自觉地对指针没什么可说的,可是,真到用到了"*"的时候,总是有些惊悚.还好吧,这次用的时候,多了些思考,于是,也就比较顺畅了.
这东西,写出来了之后,也就不想去说太多了...都在脑袋里了.
有些时候,寂寞得要死啊....没办法啊.硬撑.
很遗憾,这个斐波那契堆没有真刀真枪地使用过.但估计不会有问题,毕竟已经测试过足够次了.
斐波那契堆啊,哈哈.很高级的数据结构啊.我给写出来了.
这章是十一章了,摊还分析,说不清楚.给问题增加了一个维度,很科学,我会继续研究.
好吧,贴代码,久等了!
/* FibonacciHeap.h -- 斐波那契堆头文件 */ /* 代码阶段耗时14小时. 2011-03-01-22.32完成 */ #include <stdio.h> #include <stdlib.h> #include <assert.h> /* 明显常量定义 */ #define FALSE (0) #define TRUE (1) #define EMPTY (1 << 31) #define NEGATIVE_INFINTY (1 << 30) #define BE_RELEASED (1 << 31) /* 数据类型定义 */ typedef int BOOL ; typedef int Item ; typedef struct node { Item item ; struct node * left, * right, * parent, * child ; int degree ; BOOL index ; } Node ; typedef struct fibonacciheap { Node * min ; int current ; } * FibonacciHeap ; /* 接口函数声明 */ /* 操作: 创建并初始化一个斐波那契堆 */ /* 操作前: pfh 指向一个斐波那契堆 */ /* 操作后: 如果内存分配成功, 创建并初始化该斐波那契堆, 返回 TRUE ; 否则返回 FALSE ; */ /* 摊还时间: O (1) */ BOOL Initialize_F (FibonacciHeap * const pfh) ; /* 操作: 确定一个斐波那契堆是否为空 */ /* 操作前: pfh 指向一个已初始化的斐波那契堆 */ /* 操作后: 如果该斐波那契堆为空, 返回 TRUE ; 否则返回 FALSE */ /* 摊还时间: O (1) */ BOOL IsEmpty_F (const FibonacciHeap * const pfh) ; /* 操作: 向斐波那契堆中插入一个具有指定数据的结点 */ /* 操作前: pfh 指向一个已初始化的斐波那契堆, pi 指向待添加的数据 */ /* 操作后: 如果内存分配成功, 向该斐波那契堆中插入1个数据域为该数据的结点, 返回 TRUE ; 否则返回 FALSE */ /* 摊还时间: O (1) */ BOOL Insert_F (const FibonacciHeap * const pfh, const Item * const pi) ; /* 操作: 删除并返回斐波那契堆中最小结点的数据 */ /* 操作前: pfh 指向一个已初始化的斐波那契堆 */ /* 操作后: 如果该斐波那契堆不为空, 删除该斐波那契堆中最小结点, 返回该结点的数据 ; 否则返回 EMPTY */ /* 摊还时间: O (log N) */ Item DeleteMin_F (const FibonacciHeap * const pfh) ; /* 操作: 降低斐波那契堆中指定数据的值 */ /* 操作前: pfh 指向一个已初始化的斐波那契堆, pn 指向指定的结点, delta 指示改变量的大小 */ /* 操作后: 如果该斐波那契堆不为空, 使该斐波那契堆中 pn 指向结点数据的值减少 delta , 返回 TRUE ; 否则返回 FALSE */ /* 摊还时间: O (1) */ BOOL DecreaseKey_F (const FibonacciHeap * const pfh, Node * const pn, const int delta) ; /* 操作: 删除斐波那契堆中指定结点 */ /* 操作前: pfh 指向一个已初始化的斐波那契堆, pn 指向待删除的结点 */ /* 操作后: 如果该斐波那契堆不为空, 删除 pn 指向的结点, 返回 TRUE ; 否则返回 FALSE */ /* 摊还时间: O (log N) */ BOOL Delete_F (const FibonacciHeap * const pfh, Node * const pn) ; /* 操作: 释放一个斐波那契堆所占用的内存空间 */ /* 操作前: pfh 指向一个已初始化的斐波那契堆 */ /* 操作后: 该斐波那契堆所占用的内存空间被释放 */ /* 摊还时间: O (N) */ void Release_F (const FibonacciHeap * const pfh) ;
