060111038庞崇涛数据结构课程设计

《060111038庞崇涛数据结构课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《数据结构》课程设计HiIbert曲线的绘制及算法实现院（系）名称信息I:程学院专业班级06普木信计1班学号060111038学生姓名庞崇涛指导教师叶茂功2008年12月27H课程设计任务书2008—2009学年第一学期专业班级：06普本信计1班学号:060111038姓名:庞崇涛课程设计名称：数据结构设计题口：Hilbert曲线的绘制及算法实现完成期限：自2008年I2_/]2L0至2009年0L/]040共1周设计依据、要求及主要闪容：一、设计R的Hilbert曲线在图像处理、多维数据索引等领域冇若車要作用，但是由于高维Hilbert曲线的复杂性，

2、绘制高维Hilbert曲线的相关算法的研究很少。木设计根据栈的有关知识和递归函数的调用，在TUrix）C2.0的环境下，实现N维Hilbert曲线的绘制，便干研究与相关的问题。二、设计要1.介绍栈和递归调用的相关知识，说明如何用递归的算法來实现•个程序的运行。2.给出Hilbert曲线的来历，绘制的基本思路及过程。3.能够运用C语g编制Hilbert曲线的绘制程序，在TurboC2.0环境T正确无误地运行出结來，且在规定时间内完成木设计。三、参考文献『11严蔚敏，无伟民.数据结构（C语言版MM1.北京:清华大学出版社，1997.f21谭浩强.C程序设计

3、丨Ml.北京:清华大学出版社，2005.DIS风翥.C++语g基础教程[Ml.」bk:人民邮电出版社，2005.计划答辩时间:2008年01月04曰工作任务与工作量要求：查阅文献资料不少于3篇，课程设计报告1篇不少于3000字。指导教师（签字）：教研室主任（签字）：批准日期：年月曰HiIbert曲线的绘制及算法实现摘要Hilbert[ttl线描述了一种多维空间与一维空间一一映射的方法，在图像处理、多维数据索引等领域有着重要的地位。但因为高维Hilbert曲线的复杂性，高维Hilbert的和关算法的研究很少。本设计通过数据结构屮递归函数的实现，给出了产生

4、N维Hilbert曲线的一个新的算法。该算法基于栈和递归调用算法，自底向上地分析N维Hilbert曲线编码规律，实现N维Hilbert曲线的绘制。与其他的算法相比，本设计的方法易于实现，同吋实验显示该算法具有更好的计算性能。关键词：Hlibert曲线；算法；栈；递归目录1柳細12Hilbert曲线22.1Hilbert介绍22.2Hilbert曲线的提出及算法思想43程所殳计臟去实现6忌、$9参考;献101栈和递归［1］栈(stack)是数据结构中重要的线性结构，它是限定仅在表尾进行插入或删除操作的线性表。它可以广泛应用在各种软件系统屮，在面向对象［2

5、］的设计程序屮，它又是多数据类型。对栈而言，表尾端有其特殊含义，称为栈顶(top)；和应地，表头端称为栈底(bottom)；不含元素的空表称为空栈。栈的修改是按后进先出的原则进行的，故栈又称为后进先出(lastinfirstout)的线性表。栈的基本操作除了在栈顶进行插入和删除外，还冇栈的初始化、判空及取栈顶元素等。栈的表示和实现，同线性表类似，分为栈的顺序表示和链式表乐。顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈屮的位置。通常的习惯做法是以top-0表示空栈，鉴于C语言

6、中数组的下标约定从0开始，则当以C做描述语言时，如此设定会带來很大不便；另一方面，由于栈在使用的过程中所需最大空间的大小难以估计，因此，-•般来说，在初始化设空栈吋不应限定栈的最大容量。一个合理的做法就是：先为栈分配一个基本容量，然后在应用的过程中，当栈的空问不够使用时再逐段扩大。而栈的链式表示及操作易于实现，在此不做详细讨论。栈还宥一个重耍应用就是在程序设计语言中实现递归。一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称为递归函数。递归是程序设计屮的一个强用力的工具。其以，很多数学函数都是递归定义的，如大家熟悉的阶乘函数1n=Qn*Fa

7、ct(n-l)n>02阶Fibonacci数列1n>0Fib(n—l)+Fib(n—2)其他等'其二，有的数据结构，如二叉树，广义表等，由于结构本身固有的递归特性，则它们的操作可以递归地描述；其三，还有一类问题，hi然问题本身没有明显的递归结构，但用递归求解更简单，如八皇盾问题，Hanoi塔［3］问题，还宥本设计中的Hilbert曲线的1栈和递归［1］栈(stack)是数据结构中重要的线性结构，它是限定仅在表尾进行插入或删除操作的线性表。它可以广泛应用在各种软件系统屮，在面向对象［2］的设计程序屮，它又是多数据类型。对栈而言，表尾端有其特殊含义，称为栈

8、顶(top)；和应地，表头端称为栈底(bottom)；不含元素的空表称为空栈。栈的修改是按后进