《《离散数学课程设计论文--基于二元树的随机序列独立性分析算法与实现》-公开DOC·毕业论文》由会员分享，可在线阅读，更多相关《《离散数学课程设计论文--基于二元树的随机序列独立性分析算法与实现》-公开DOC·毕业论文（25页珍藏版）》请在金锄头文库上搜索。
1、09 届课程 设计 论文 题题 目目基基于于二二元元树树的的随随机机序序列列独独立立性性分分析析算算法法与与实实现现 专专业业班班级级 信信息息与与计计算算科科学学 2 班班 学学 号号 学学生生姓姓名名 指指导导教教师师 指指导导教教师师职职称称副副教教授授 学学院院名名称称理理学学院院 完完成成日日期期 2011 年年 7 月月 1 日日 武汉工程大学本科课程设计 论文 I 目目 录录 目 录 I 摘 要 II 前 言 III 第 1 章 课题背景 1 1 1 问题背景 1 1 2 基础知识 1 1 3 意义 1 1 4 文献综述 2 第 2 章 基于二元树的随机变量序列相依阶数估计 3
2、2 1 算法概述 3 2 2 数据结构设计 第 3 章 功能函数实现 5 3 1 二叉树结点插入 5 3 2 二叉树的建立 5 3 3 二叉树层次遍历 6 3 4 程序与所实现的调度方案 7 3 5 程序的优缺点及改进 13 第 4 章 总 结 14 致 谢 15 参考文献 16 附 录 17 武汉工程大学本科课程设计 论文 II 摘摘 要要 随机变量序列中的符号不是独立的 通过程序的结果 统计出二元随机序列 每一维序列频数 最后 我们要根据所得出的频数来分析与统计二元树随机变量 序列相依阶数 找出随机序列中的最大独立单元 在该程序中 随机变量序列为 随机的二进制串 关关键键词词 二元随机序列
3、 频数 相依阶数 最大独立单元 二进制串 武汉工程大学本科课程设计 论文 III 前前 言言 本文解决了通过二叉树的链表方式存储数据并计算二叉树每个结点的频数 全文共四章 第 1 章介绍了 问题背景以及相关的基础知识 在本章中 还给出了具体的实 例分析和与之相关的定理 第 2 章主要介绍了解决课题的算法概述以及数据结构设计 第 3 章主要介绍了功能函数的实现 其中包括二叉树结点插入 二叉树的建 立以及二叉树层次遍历 第 4 章是本次课程设计的总结 全文的最后是致谢 参考文献和对程序优化处理的源代码 2011 7 1 于武汉工程大学理学院 武汉工程大学本科课程设计 论文 1 第第 1 1 章章
4、课课题题背背景景 1 1 1 1 问题背景问题背景 随机变量序列的独立性与相依性是概率论中很重要的概念 许多随机变量序 列中的符号的出现都与其前面若干个符号有依赖关系 在研究分析时限制随机序 列的记忆长度 当记忆长度固定时 这样的记忆信源为马尔可夫信源 而实际上 有很多随机序列的记忆长度不是固定的 这样随机序列相依阶数是变化的 基于 二元树随机变量序列相依阶数估计是通过分析树结点的空间分布 可以判定出该 随机变量序列是独立还是相依的 若随机序列是相依的 可以统计出该序列相依 阶数 1 1 2 2 基础知识基础知识 独立性是概率论中一个重要的概念 两个事件之间的独立性是指 一个事件 的发生不影响
5、另一个事件的发生 这在实际问题中是很多的 譬如在掷颗骰子 记事件 A 为 第一颗骰子的点数为 1 记事件 B 为 第二颗骰子的点数为 4 则显然 A 与 B 的发生是相互不影响的 若事件A 与 B 相互独立 称 A 与 B 独立 否则 A 与 B 不独立即 A 与 B 相依 在多维随机变量中 各分量的取值有时会相互影响 但有时会毫无影响 譬 如一个人的身高 X 和体重 Y 就会相互影响 但与收入 Z 一般无影响 当两个随 机变量取值互不影响时 就称它们是相互独立的 同理 若它们的取值之间有影 响 则它们之间是相依的 1 1 3 3 意义意义 在信息论中 多符号离散稳信源是多符号离散信源中最简单
6、 最常用 而且 也是至今为止讨论最充分 理论最成熟的一种信源 多符号离散信源发出的消息 是由一系列离散符号组成的时间 或空间 序列来表示 例如 电报系统发出的 武汉工程大学本科课程设计 论文 2 消息 就是由 正 脉冲表示的 0 符号和 负 脉冲表示的 1 符号组成 的一连串 0 1 符号的时间序列来表示的 根据信息的定义 这种由离散 符号的时间序列代表的消息要含有信息的前提条件是消息具有随机性 也就是每 一单位时间出现的离散符号必须具有随机性 1 1 4 4 文献综述文献综述 文献 1 介绍了二叉树结点的形成与层次遍历 文献 2 介绍了概率论中随机连续型序列与离散型序列独立性的分析 文献 3
7、 以实例较为详细地介绍了二叉树的分析算法与实现 武汉工程大学本科课程设计 论文 3 第第 2 2 章章 基基于于二二元元树树的的随随机机变变量量序序列列相相依依阶阶数数估估计计 2 2 1 1 算法概述算法概述 根据课题要求 我们将通过二叉树的链表方式存储数据 计算二叉树每个结 点的频数 当将二进制序列读取后 按指定的维数N 从第一个字符开始一次 读取 N 个字符 依次插入结点建立二叉树 再从第二个字符开始读取N 个字符 从根结点开始依次插入 依次类推 直到循环到最后一个字符读取N 个字符依 次插入后 二叉树建立完成 在插入结点的过程中 若二叉树此处结点已存在 只需次其频数增 1 若结点不存在
8、 则插入结点 并将频数增1 当输出二叉树每个结点的频数时 利用二叉树的层次遍历 按层次顺序访问 二叉树的处理需要利用一个队列 在访问二叉树的某一层结点时 把下一层结点 指针预先记忆在队列中 利用队列安排逐层访问的次序 因些 当访问一个结点 时 将它的子女依次加到队列的队尾 然后再访问已在队列队头的结点 这样 二叉树每个结点按照层次遍历的顺序存储在了队列中 最后 将得到的结点频数通过计算研究 分析m 元树同高度的结点空间分布以 及最大独立单元和其状态空间 并且通过计算分析估计随机变量序列的相依阶数 2 2 2 2 数据结构设计数据结构设计 定义一个结构体来表示二叉树的结点 结构体里包含结点频数
9、结点符号串 结点符号 结点左右指针 结点频数表示循环二叉树建立后 经过该结点的总次 数 结点符号主要是读取二进制串时 结点符号取0 表示新建结点为左孩子 符号取 1 表示新建结点为右孩子 将频数 符号 结点符号串存入带根结点的二叉树中 频数的属性取了fre 标志符的属性取了 flag 结点符号串的属性取了 data 左子女结点指针为 L 右子女结点指针为 R 并将 fre flag data 和 L R 封装在结点类 武汉工程大学本科课程设计 论文 4 TreeNode 中 其链结点 Node 的数据结构如图 2 2 所示 图 2 2 二叉树结点的数据结构 其中 fre 为整型 flag 为字
10、符型 data 为字符型指针 而 L R 为指向二叉树 结点 TreeNode 的指针 将 TreeNode 定义成结构体 代码如下 struct TreeNode 二叉树结点类定义 char data 结点频数 char flag 结点标志符 int fre 结点符号串 struct TreeNode L R 左子女 右子女链域 TreeNode fre 0 L NULL R NULL 构造函数 初始化新建结点 data new char 50 memset data 0 50 武汉工程大学本科课程设计 论文 5 第第 3 3 章章 功功能能函函数数实实现现 3 3 1 1 二叉树结点插入二
11、叉树结点插入 二叉树结点插入函数带两个参数 分别为当前结点 待插入结点 该函数在 设计过程中 有着一定的插入规则 当读取字符为0 即新建结点标志符取 0 若当前结点左子树为空 则新建结点插入到当前结点的左子树 同时左孩子 结点频数增 1 若当前结点左子树不为空 则当前左孩子结点频数增1 当读 取字符为 1 即新建结点标志符取 1 若当前结点右子树为空 则新建结点插入 到当前结点的右子树 同时右孩子结点频数增1 若当前结点右子树不为空 则当前右孩子结点频数增 1 当结点插入成功后 该结点即为下个结点插入的当 前结点 结点插入函数详细设计代码如下 void CreateTree TreeNode
12、Current L fre 1 结点频数增 1 Current Current L 左孩子为下个新建结点插入的当前结点 else if pNode flag 1 当新建结点标志符取 1 if Current R NULL 当前结点右子树为空 Current R pNode Current R fre 1 结点频数增 1 Current Current R 右孩子为下个新建结点插入的当前结点 武汉工程大学本科课程设计 论文 6 3 3 2 2 二叉树的建立二叉树的建立 二叉树的建立是一个循环的过程 插入第一次读取的N 个字符时 从根结 点开始 将从存储在 temp 中的二进制串中读取出的 N 个
13、字符作为结点依次插 入二叉树 同时记录每个结点的结点符号串 第二次插入读取的N 个字符时 继续是从根结点开始 依次插入二叉树 直到将二进制串循环读取完 二叉树建 立才完成 在此过程中 每插入N 个字符后 要将当前指针 Current 指向根结 点 同时要将临时存储 N 个字符的变量 temp1 重新初始化 二叉树的根结点不 为空 且其结点标志符为空 二叉树的建立详细设计代码如下 char temp1 new char 100 for int j 0 j len j 循环建立二叉树 memset temp1 0 100 初始化 temp1 int h 1 for int i 0 i N i 存储
14、从二进制串读取的 N 个字符 temp1 i temp i j len Current pRoot 建立二叉树从根结点开始 即当前结点为根结点 for int k 0 kflag temp1 k 读取的字符赋给新建结点的符号 for int l 0 ldata l temp1 l pNode data l 1 0 CreateTree Current pNode 插入新建结点 武汉工程大学本科课程设计 论文 7 3 3 3 3 二叉树层次遍历二叉树层次遍历 层次遍历是从二叉树的根结点开始 自上而下 自左向右分层依次访问树中 的各个结点 按层次顺序访问二叉树的处理需要利用一个队列 在访问二叉树的
15、 某一层结点时 把下一层结点指针预先记忆在队列中 利用队列安排逐层访问的 次序 因些 当访问一个结点时 将它的子女依次加到队列的队尾 然后再访问 已在队列队头的结点 这样就可以实现二叉树结点的按层访问 二叉树层次遍历详细设计代码如下 void LevelOrder TreeNode pRoot TreeNode queue int front rear front 标记队列队头 rear 标记队列队尾 front 1 rear 0 queue rear pRoot 二叉树结点从队尾开始添加 while front rear front if queue front L NULL 左孩子不为空
16、左孩子进队列 rear queue rear queue front L if queue front R NULL 右孩子不为空时 右孩子进队列 rear queue rear queue front R 3 3 4 4 程序与所实现的调度方案程序与所实现的调度方案 include template class Queue 武汉工程大学本科课程设计 论文 8 public virtual bool IsEmpty const 0 virtual bool IsFull const 0 virtual bool Front T virtual bool EnQueue T x 0 virtual bool DeQueue T virtual void Clear 0 template class SeqQueue public Queue public SeqQueue int mSize SeqQueue delete q bool IsEmpty const return front rear bool IsFull const return rear 1 maxSize fron
