学位论文 > 优秀研究生学位论文题录展示

堆栈和二叉树数据结构在DNA计算机中的设计与实现

作　者: 朱雅莉
导　师: 李肯立
学　校: 湖南大学
专　业: 计算机应用技术
关键词: DNA计算机数据结构堆栈二叉树
分类号: TP38
类　型: 硕士论文
年　份: 2007年
下　载: 225次
引　用: 1次
阅　读: 论文下载

内容摘要

自从1994年Adleman用DNA链解决一个简单有向哈密顿图问题以来,DNA计算已经形成国际科学前沿领域内研究的一个新的热点,引起许多不同学科学者们的兴趣。DNA计算机的研制需要诸如生物工程、计算机科学等许多学科的共同协作攻关。已有研究表明DNA计算机具备完整的图灵机功能,这为DNA计算机能否成为目前意义下真正的计算机提供理论支持。DNA计算机要走向实际应用,必须像电子计算机一样,需要解决DNA计算机中信息的组织问题,这就需要合理的数据结构来有效地组织DNA计算机需要处理的信息。因此,数据结构的设计对DNA计算机的具体实现有重要研究价值。首先,本文在参考已有队列数据结构设计方法的基础上,提出了DNA计算机中堆栈数据结构的设计方法。该方法根据堆栈的特点,利用两种不同的限制性内切酶完成入栈和出栈操作。并给出DNA计算机中堆栈存储结构的形式描述;详细阐述了DNA计算机中堆栈初始化、入栈、出栈、判断空堆栈等操作的生物实现方法;给出一个具体的DNA编码以及算法实例,实例仿真了DNA计算机中该算法的运行机制,实例结果表明此堆栈数据结构的设计方法在DNA计算机上切实可行。然后,提出了DNA计算机中基于顺序存储方式的二叉树数据结构的设计方法。该方法利用DNA分子和限制性内切酶的生物特性,完成二叉树的顺序存储结构和基本操作。并给出一个二叉树的DNA编码以及仿真实例,实例结果表明该设计方法在DNA计算机上的可行性。最后,给出DNA计算机中二叉树链式存储结构的形式描述。在连接酶的作用下,各结点之间产生杂交和连接反应,形成DNA双链。并给出一棵二叉树的链式存储结构实例,实例表明该设计方法构造的DNA双链对应二叉树的中序遍历序列。文中用到的生物技术在实验室中都能实现,这些方法可推广到DNA计算机中其他类型的数据结构,帮助DNA计算机合理、有效地组织需要处理的信息,从而使DNA计算机走向实际应用。

全文目录

摘要  5-6
ABSTRACT  6-10
插图索引  10-12
第1章绪论  12-16
  1.1 研究目的与意义  12
  1.2 选题的背景  12-13
  1.3 国内外研究现状  13-14
  1.4 本文研究内容与组织结构  14-16
第2章理论基础与依据  16-32
  2.1 引言  16
  2.2 DNA分子的组成、结构和类型  16-19
    2.2.1 DNA分子的组成  16-17
    2.2.2 DNA分子的结构  17-18
    2.2.3 DNA分子的类型  18-19
  2.3 生物酶  19-20
  2.4 DNA分子的性质与基本操作  20-25
    2.4.1 DNA分子的变性和复性  20-21
    2.4.2 DNA分子的杂交、复制和延长  21-23
    2.4.3 DNA分子的连接、切割与合成  23-25
    2.4.4 DNA分子的长度及测量  25
    2.4.5 DNA分子的提取、检测与替换  25
  2.5 DNA分子存储技术  25-26
  2.6 DNA计算与 DNA计算机  26-31
    2.6.1 DNA计算的基本原理  26-27
    2.6.2 DNA计算机的优点  27-28
    2.6.3 DNA计算模型  28-31
  2.7 小结  31-32
第3章 DNA计算机中堆栈数据结构的设计与实现  32-49
  3.1 引言  32
  3.2 DNA计算机中队列数据结构的设计及实现  32-38
    3.2.1 队列的基本概念  32
    3.2.2 DNA计算机中队列的存储结构  32-33
    3.2.3 DNA计算机中队列的基本操作  33-35
    3.2.4 DNA计算机中队列的算法实例  35-36
    3.2.5 方法评价  36-38
  3.3 DNA计算机中堆栈数据结构的设计及实现  38-46
    3.3.1 堆栈的基本概念  38
    3.3.2 DNA计算机中堆栈的存储结构  38-40
    3.3.3 DNA计算机中堆栈的基本操作  40-43
    3.3.4 DNA计算机中堆栈的DNA编码及算法实例  43-46
  3.4 优缺点分析  46-47
    3.4.1 主要优点  46-47
    3.4.2 主要缺点  47
  3.5 小结  47-49
第4章二叉树数据结构在DNA计算机中的设计  49-67
  4.1 引言  49
  4.2 二叉树的基本概念与性质  49-51
    4.2.1 二叉树的定义  49-50
    4.2.2 二叉树的性质  50
    4.2.3 二叉树的遍历  50-51
  4.3 DNA计算机中基于顺序存储方式的二叉树数据结构  51-63
    4.3.1 顺序存储结构  51-54
    4.3.2 二叉树的基本操作  54-59
    4.3.3 二叉树 DNA编码及算法实例  59-63
  4.4 DNA计算机中基于链式存储方式的二叉树数据结构  63-66
    4.4.1 方法与规则  63-64
    4.4.2 可行性分析  64-66
  4.5 小结  66-67
结论  67-69
参考文献  69-73
致谢  73-74
附录 A(攻读硕士期间所发表的学术论文)  74

堆栈和二叉树数据结构在DNA计算机中的设计与实现

内容摘要

全文目录

相似论文