科研实训报告-3

PAGEPAGE12科研实训报告题目：二项堆和Fibonacci堆的分析与实现院系：数学与计算机科学学院专业：计算机科学与技术___年级：2009级__________学号：_____110901004_______姓名：陈伟______指导教师：陈欢______实习地点：在校实习年月日二项堆和Fibonacci堆的分析与实现研究背景、概况及意义在信息化时代，电子计算机在我们日常生活中扮演利益重要的作用。从电子邮件到网上视频，从网络游戏到三色定理证明，程序无处不在。随着处理规模的日益增加，如何让程序高效稳定运行成为人们思考的问题。此时良好的数据结构和精心设计的算法便成为解决问题的重点。数据结构是计算机科学中一个普遍而又重要的概念。数据结构是指计算机内部存储和组织数据的方式。通常包括链式数据结构比如数组，单链表，双链表，还有循环链表，树式数据结构比如二叉树，2-3树等等。通过精心设计数据结构和建立在对应数据结构上的各种操作，通常情况下能够使得程序运行的更加高效和稳定。常见的数据结构包括红黑树，AVL树，B树，二叉堆，栈等等。在面对现实世界中的具体问题时，我们通过抽象来建立对应的数学描述，选择合理的数据结构能够对问题的高效解决起到事半功倍的作用。堆是计算机科学中最常用的数据结构之一。从抽象的角度来讲，堆是部分有序的树形结构。它满足任意节点的关键字值总是比起父节点的关键字值来的小（最小堆）或者任意节点的关键字值总是比起父节点的关键来的大（最大堆）。在本文的正文部份，如果没有特殊说明，我们总是假定在讨论最小堆。它高效支持插入，弹出，删除和改变关键字值的操作。由于这些特殊性质，使得它在许多具体算法中得到普遍应用，例如最短路算法的快速实现，最优编码的哈夫曼树实现，优先级调度算法等等。从物理的角度来讲，堆的节点在内存中可以连续分布也可以分散分布，前者是二叉堆，后者是二项堆和斐波纳契堆。二叉堆的实现相对简单，运行时间的常数因子也小，但是同时也存在一些不足之处。由于二叉堆要求连续的存储空间，因此对于增量数据即我们无法事先预知数据总的规模的情况下，我们无法确定应该分配的内存大小。通常这种情况下我们倾向于分配一个较大的内存，但是极有可能造成内存的浪费，同时当数据规模超过分配的内存时还要重新分配内存，其中就要涉及较大的数据复制操作，这对运行效率是极其不利的。另外一种情况下及时我们事先知道数据规模的大小，但是由于内存有限无法分配出足够大连续的内存空间。由于这两个原因使得二叉堆的应用得到限制，许多人开始探索离散空间上实现堆的方法。二项堆和斐波纳契堆是离散空间上堆的实现，克服了二叉堆要求分配连续内存的缺点同时维持了相关操作的高效性。在渐近时间复杂度上二项堆和二叉堆的时间复杂度是相同的。斐波纳契堆由于采用了循环双向链表的数据结构使得在不涉及删除操作的情况下时间复杂度为O(1)，从而大大提高时间效率。不过由于数据结构相对复杂，斐波那契堆的常数因子较大，在较小规模的数据上的时间优势并不明显。本文通过学习两种数据结构的数学性质和实现算法给出具体的代码实现，同时比较了两种数据结构的时间效率。二、研究主要内容1．学习《离散数学及其应用》中关于树形结构的数学定义和对应的数学性质以及在程序设计中的应用。2.学习《算法导论》中关于二项树的定义和对应数学性质，同时学习二项树支持的基本操作。3.学习《算法导论》中二项堆和斐波纳契堆的定义以及数学性质。4.学习二项堆和斐波那契对支持的基本操作的算法实现细节。5.学习如何利用势函数和均摊分析的方法分析斐波那契堆的算法性能。6．学习如何设计测试函数对具体模块进行测试。三、采用的方法 主要通过阅读相关书籍和文献来加深理论准备，同时对代码进行初步设计，说明如下： 1.二项堆涉及到的数据结构主要包括bin_node和bin_heap，具体定义如下：structbin_node{ structbin_node*father; structbin_node*lchild; structbin_node*rsibling; void*data; intdegree;};structbin_heap{ structbin_node*head; intsize;}; 主要涉及到的函数如下：bin_Make(),此函数分配一个bin_heap结构体指针并且初始化然后返回对应的结构体指针。bin_link(),此函数接受两个bin_node结构体指针作为参数，将对应的两棵二项树合并并且返回结果树的根节点指针。bin_merge(),此函数接受两个bin_heap结构体指针作为参数，将对应的两个二项堆的主链按序合并，并将结果主链的头部指针返回。bin_Union(),此函数接受两个bin_heap结构体指针作为参数，内部调用bin_merge()合并主链，然后对主链上相同度数的节点进行进一步合并。bin_replace(),此函数改变某个节点的关键字值，并且通过递归的父节点比较关键字值来维持堆的有序结构。bin_size(),此函数返回二项堆的节点数目。bin_empty(),此函数返回一个布尔值来判定对应的二项堆是否为空。bin_delete()，此函数删除某个给定的节点，通过进一步的操作来保证二项堆的数学性质和结构。bin_Push(),bin_Pop(),bin_Top(),这些函数对堆的基本操作进行封装，提供抽象的接口。bin_func_test(),二项堆的测试函数，不包括效率测试，主要是对Push,Pop，Top接口函数的测试。2.斐波那契堆涉及到的数据结构主要包括fib_node和fib_heap，具体定义如下：structfib_node{ structfib_node*left; structfib_node*right; structfib_node*child; structfib_node*father; intmark; intdegree; void*data;};structfib_heap{ structfib_node*head; intsize;}; 主要涉及到的函数如下：fib_Make(),此函数在内存中分配一个fib_heap的结构体并且初始化，函数返回对应结构体的指针。fib_link(),此函数接受两个fib_node结构体指针，将两个无序的二项树合并，并且返回对应结果树的根节点。fib_replace(),此函数改变某个节点的关键值，同时经过级联剪切的操作的维护斐波那契堆的数学性质和结构。fib_Union(),此函数接受两个fib_heap结构体指针，将对应的斐波纳契堆合并，返回合并后的堆的根节点。_listsize(),此函数接受一个fib_heap结构体指针，通过遍历根链得到根链长度的最大度数，通过这些计算要用到的临时数组的大小。consolidate(),此函数实现级联剪切的操作。fib_Push(),fib_Pop(),fib_Top()实现对斐波那契堆的基本操作进行封装，提供抽象的接口。fib_func_test（）,斐波纳契堆的测试函数，不包括性能测试，主要是对Push,Pop和Top操作进行测试。 3.性能测试部分主要通过profiler()函数来实现。对每个函数在调用前和调用后执行clock()函数，根据结果计算对应挂钟时间。四、技术准备 1.学习Vim编辑器(1)查找

/xxx(?xxx)

表示在整篇文档中搜索匹配xxx的字符串,/表示向下查找,?表示向上查找.其中xxx可以是正规表达式,关于正规式就不多说，一般来说是区分大小写的,要想不区分大小写,那得先输入:setignorecase查找到以后,再输入n查找下一个匹配处,输入N反方向查找.

*(#)

当光标停留在某个单词上时,输入这条命令表示查找与该单词匹配的下(上)一个单词.同样,再输入n查找下一个匹配处,输入N反方向查找.

g*(g#)

此命令与上条命令相似,只不过它不完全匹配光标所在处的单词,是匹配包含该单词的所有字符串.

gd本命令查找与光标所在单词相匹配的单词,并将光标停留在文档的非注释段中第一次出现这个单词的地方.

%本命令查找与光标所在处相匹配的反括号,包括()[]{}

f(F)x本命令表示在光标所在行进行查找,查找光标右(左)方第一个x字符，找到后:输入;表示继续往下找，输入,表示反方向查找

（2）快速移动光标

在vi中,移动光标和编辑是两件事,正因为区分开来,所以可以很方便的进行光标定位和编辑.因此能更快一点移动光标是很有用的.

w(e)

移动光标到下一个单词.

b

移动光标到上一个单词.

0

移动光标到本行最开头.

^

移动光标到本行最开头的字符处.

$

移动光标到本行结尾处.

H

移动光标到屏幕的首行.

M

移动光标到屏幕的中间一行.

L

移动光标到屏幕的尾行.

gg

移动光标到文档首行.

G

移动光标到文档尾行.

(3)拷贝,删除与粘贴

在vi中y表示拷贝,d表示删除,p表示粘贴.其中拷贝与删除是与光标移动命令结合的,看几个例子就能够明白了.

yw

表示拷贝从当前光标到光标所在单词结尾的内容.

dw

表示删除从当前光标到光标所在单词结尾的内容.

y0

表示拷贝从当前光标到光标所在行首的内容.

d0

表示删除从当前光标到光标所在行首的内容.

y$

表示拷贝从当前光标到光标所在行尾的内容.

d$

表示删除从当前光标到光标所在行尾的内容.

yfa

表示拷贝从当前光标到光标后面的第一个a字符之间的内容.

dfa

表示删除从当前光标到光标后面的第一个a字符之间的内容.

yy

表示拷贝光标所在行.

dd

表示删除光标所在行.

D

表示删除从当前光标到光标所在行尾的内容

2.学习Gcc的使用方法 通常所说的GCC是GUNCompilerCollection的简称，除了编译程序之外，它还含其他相关工具，所以它能把易于人类使用的高级语言编写的源代码构建成计算机能够直接执行的二进制代码。GCC是Linux平台下最常用的编译程序，它是Linux平台编译器的事实标准。同时，在Linux平台下的嵌入式开发领域，GCC也是用得最普遍的一种编译器。GCC之所以被广泛采用，是因为它能支持各种不同的目标体系结构。例如，它既支持基于宿主的开发（简单讲就是要为某平台编译程序，就在该平台上编译），也支持交叉编译（即在A平台上编译的程序是供平台B使用的）。目前，GCC支持的体系结构有四十余种，常见的有X86系列、Arm、PowerPC等。同时，GCC还能运行在不同的操作系统上，如Linux、Solaris、Windows等对于GUN编译器来说，程序的编译要经历预处理、编译、汇编、连接四个阶段，如下图所示：

在预处理阶段，输入的是C语言的源文件，通常为*.c。它们通常带有.h之类头文件的包含文件。这个阶段主要处理源文件中的#ifdef、#include和#define命令。该阶段会生成一个中间文件*.i，但实际工作中通常不用专门生成这种文件，因为基本上用不到；若非要生成这种文件不可，可以利用下面的示例命令：gcc-E

test.c-otest.i在编译阶段，输入的是中间文件*.i，编译后生成汇编语言文件*.s。这个阶段对应的GCC命令如下所示：GCC-Stest.i-otest.s在汇编阶段，将输入的汇编文件*.s转换成机器语言*.o。这个阶段对应的GCC命令如下所示：GCC-ctest.s-otest.o在连接阶段将输入的机器代码文件*.s（与其它的机器代码文件和库文件）汇集成一个可执行的二进制代码文件。这一步骤，可以利用下面的示例命令完成：GCCtest.o-otest上面介绍GCC编译过程的四个阶段以及相应的命令。下面我们进一步介绍常用的GCC的模式。这里介绍GCC追常用的两种模式：编译模式和编译连接模式。下面以一个例子来说明各种模式的使用方法。为简单起见，假设我们全部的源代码都在一个文件test.c中，要想把这个源文件直接编译成可执行程序，可以使用以下命令：$GCC-otest这里test.c是源文件，生成的可执行代码存放在一个名为test的文件中（该文件是机器代码并且可执行）。-o是生成可执行文件的输出选项。如果我们只想让源文件生成目标文件（给文件虽然也是机器代码但不可执行），可以使用标记-c，详细命令如下所示：$GCC-ctest.c默认情况下，生成的目标文件被命名为test.o，但我们也可以为输出文件指定名称，如下所示：$GCC-ctest.c-o上面这条命令将编译后的目标文件命名为mytest.o，而不是默认的test.o。迄今为止，我们谈论的程序仅涉及到一个源文件；现实中，一个程序的源代码通常包含在多个源文件之中，这该怎么办？没关系，即使这样，用GCC处理起来也并不复杂，见下例：$GCC-otest

first.csecond.cthird.c该命令将同时编译三个源文件，即first.c、second.c和third.c，然后将它们连接成一个可执行程序，名为test。 3.熟悉Unix系统的使用环境UNIX构成：UNIX核心、用户进程（：由C语言编写，汇编代码）、文件系统（/dev目录下的一个设备文件）。根目录文件系统（目录名“/”）其他文件系统挂接在根目录或其它子文件系统目录上。UNIX中每个事物都是一个文件。UNIX完成的最基本任务：处理硬件终端和例外、提供系统服务、建立用户进程并调度执行。UNIX账户：用户名称和ID、组的名称和ID、用户目录、默认使用的SHELL注：用户ID＝0的用户就是管理员。介绍并演示了不同的UNIX命令。太多了，不一一例举。4．对相关算法的实现细节进行深入学习。五、本课题的重点和难点 1.理解二项堆根链上的根节点至多不会超过logn+1个。 2.理解级联剪切操作的具体作用和意义。 3.理解怎样使用势函数和均摊性能分析的方法来分析斐波纳契堆的算法性能。4.理解