离散数学课程设计（论文）-基于二元树的随机序列独立性分析算法与实现.doc

09 届课程（设计）论文 题题 目目基基于于二二元元树树的的随随机机序序列列独独立立性性分分析析算算法法与与实实现现 专专业业班班级级信信息息与与计计算算科科学学 (2)班班 学学 号号 学学生生姓姓名名 指指导导教教师师 指指导导教教师师职职称称副副教教授授 学学院院名名称称理理学学院院 完完成成日日期期： 2011 年年 7 月月 1 日日 武汉工程大学本科课程设计 (论文) 目目 录录 目 录 .i 摘 要 ii 前 言 .iii 第 1 章 课题背景 .1 11 问题背景 1 12 基础知识 .1 13 意义.1 14 文献综述 .2 第 2 章 基于二元树的随机变量序列相依阶数估计.3 21 算法概述 .3 22 数据结构设计 第 3 章 功能函数实现 5 31 二叉树结点插入 .5 32 二叉树的建立 5 33 二叉树层次遍历 6 34 程序与所实现的调度方案 .7 35 程序的优缺点及改进 .13 第 4 章 总 结 14 致 谢.15 参考文献 .16 附 录 17 武汉工程大学本科课程设计 (论文) i 摘摘 要要 随机变量序列中的符号不是独立的，通过程序的结果，统计出二元随机序列 每一维序列频数，最后，我们要根据所得出的频数来分析与统计二元树随机变量 序列相依阶数，找出随机序列中的最大独立单元。在该程序中，随机变量序列为 随机的二进制串。 关关键键词词：二元随机序列，频数，相依阶数，最大独立单元，二进制串 武汉工程大学本科课程设计 (论文) ii 前前 言言 本文解决了通过二叉树的链表方式存储数据并计算二叉树每个结点的频数。 全文共四章。 第 1 章介绍了 问题背景以及相关的基础知识。在本章中，还给出了具体的实 例分析和与之相关的定理。 第 2 章主要介绍了解决课题的算法概述以及数据结构设计。 第 3 章主要介绍了功能函数的实现，其中包括二叉树结点插入、二叉树的建 立以及二叉树层次遍历。 第 4 章是本次课程设计的总结。 全文的最后是致谢、参考文献和对程序优化处理的源代码。 * 2011-7-1 于武汉工程大学理学院 武汉工程大学本科课程设计 (论文) 0 第第 1 1 章章 课课题题背背景景 1 11 1 问题背景问题背景 随机变量序列的独立性与相依性是概率论中很重要的概念。许多随机变量序 列中的符号的出现都与其前面若干个符号有依赖关系，在研究分析时限制随机序 列的记忆长度，当记忆长度固定时，这样的记忆信源为马尔可夫信源。而实际上， 有很多随机序列的记忆长度不是固定的，这样随机序列相依阶数是变化的。基于 二元树随机变量序列相依阶数估计是通过分析树结点的空间分布，可以判定出该 随机变量序列是独立还是相依的。若随机序列是相依的，可以统计出该序列相依 阶数。 1 12 2 基础知识基础知识 独立性是概率论中一个重要的概念，两个事件之间的独立性是指：一个事件 的发生不影响另一个事件的发生。这在实际问题中是很多的。譬如在掷颗骰子， 记事件 a 为“第一颗骰子的点数为 1”，记事件 b 为“第二颗骰子的点数为 4”。则显然 a 与 b 的发生是相互不影响的。若事件a 与 b 相互独立，称 a 与 b 独立，否则 a 与 b 不独立即 a 与 b 相依。 在多维随机变量中，各分量的取值有时会相互影响，但有时会毫无影响。譬 如一个人的身高 x 和体重 y 就会相互影响，但与收入 z 一般无影响。当两个随 机变量取值互不影响时，就称它们是相互独立的。同理，若它们的取值之间有影 响，则它们之间是相依的。 1 13 3 意义意义 在信息论中，多符号离散稳信源是多符号离散信源中最简单，最常用，而且 也是至今为止讨论最充分、理论最成熟的一种信源。多符号离散信源发出的消息 是由一系列离散符号组成的时间（或空间）序列来表示。例如，电报系统发出的 武汉工程大学本科课程设计 (论文) 1 消息，就是由 “正”脉冲表示的 “0”符号和“负”脉冲表示的 “1”符号组成 的一连串 “0”、“1”符号的时间序列来表示的。根据信息的定义，这种由离散 符号的时间序列代表的消息要含有信息的前提条件是消息具有随机性，也就是每 一单位时间出现的离散符号必须具有随机性。 1 14 4 文献综述文献综述 文献1介绍了二叉树结点的形成与层次遍历。 文献2介绍了概率论中随机连续型序列与离散型序列独立性的分析。 文献3以实例较为详细地介绍了二叉树的分析算法与实现。 武汉工程大学本科课程设计 (论文) 2 第第 2 2 章章 基基于于二二元元树树的的随随机机变变量量序序列列相相依依阶阶数数估估计计 2 21 1 算法概述算法概述 根据课题要求，我们将通过二叉树的链表方式存储数据，计算二叉树每个结 点的频数。当将二进制序列读取后，按指定的维数n，从第一个字符开始一次 读取 n 个字符，依次插入结点建立二叉树，再从第二个字符开始读取n 个字符， 从根结点开始依次插入，依次类推，直到循环到最后一个字符读取n 个字符依 次插入后，二叉树建立完成。在插入结点的过程中，若二叉树此处结点已存在， 只需次其频数增 1，若结点不存在，则插入结点，并将频数增1。 当输出二叉树每个结点的频数时，利用二叉树的层次遍历。按层次顺序访问 二叉树的处理需要利用一个队列。在访问二叉树的某一层结点时，把下一层结点 指针预先记忆在队列中，利用队列安排逐层访问的次序。因些，当访问一个结点 时，将它的子女依次加到队列的队尾，然后再访问已在队列队头的结点。这样， 二叉树每个结点按照层次遍历的顺序存储在了队列中。 最后，将得到的结点频数通过计算研究，分析m 元树同高度的结点空间分布以 及最大独立单元和其状态空间，并且通过计算分析估计随机变量序列的相依阶数。 2 22 2 数据结构设计数据结构设计 定义一个结构体来表示二叉树的结点，结构体里包含结点频数，结点符号串， 结点符号，结点左右指针。结点频数表示循环二叉树建立后，经过该结点的总次 数；结点符号主要是读取二进制串时，结点符号取0 表示新建结点为左孩子， 符号取 1 表示新建结点为右孩子； 将频数、符号，结点符号串存入带根结点的二叉树中，频数的属性取了fre， 标志符的属性取了 flag，结点符号串的属性取了 data，左子女结点指针为 l，右子女结点指针为 r。并将 fre，flag，data 和 l，r 封装在结点类 武汉工程大学本科课程设计 (论文) 3 treenode 中。其链结点 node 的数据结构如图 2-2 所示： 图 2-2 二叉树结点的数据结构 其中，fre 为整型， flag 为字符型， 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 char50; memset(data,0,50); ; 武汉工程大学本科课程设计 (论文) 4 第第 3 3 章章 功功能能函函数数实实现现 3 31 1 二叉树结点插入二叉树结点插入 二叉树结点插入函数带两个参数，分别为当前结点、待插入结点。该函数在 设计过程中，有着一定的插入规则。当读取字符为0，即新建结点标志符取 0，若当前结点左子树为空，则新建结点插入到当前结点的左子树，同时左孩子 结点频数增 1，若当前结点左子树不为空，则当前左孩子结点频数增1；当读 取字符为 1，即新建结点标志符取 1，若当前结点右子树为空，则新建结点插入 到当前结点的右子树，同时右孩子结点频数增1，若当前结点右子树不为空， 则当前右孩子结点频数增 1。当结点插入成功后，该结点即为下个结点插入的当 前结点。 结点插入函数详细设计代码如下： void createtree(treenode * 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; /右孩子为下个新建结点插入的当前结点 武汉工程大学本科课程设计 (论文) 5 3 32 2 二叉树的建立二叉树的建立 二叉树的建立是一个循环的过程。插入第一次读取的n 个字符时，从根结 点开始，将从存储在 temp 中的二进制串中读取出的 n 个字符作为结点依次插 入二叉树，同时记录每个结点的结点符号串；第二次插入读取的n 个字符时， 继续是从根结点开始，依次插入二叉树。直到将二进制串循环读取完，二叉树建 立才完成。在此过程中，每插入n 个字符后，要将当前指针 current 指向根结 点，同时要将临时存储 n 个字符的变量 temp1 重新初始化。二叉树的根结点不 为空，且其结点标志符为空。 二叉树的建立详细设计代码如下： char *temp1=new char100; for(int j=0;jflag=temp1k;/读取的字符赋给新建结点的符号 for(int l=0;ldatal=temp1l; pnode-datal+1=0; createtree(current,pnode);/插入新建结点 武汉工程大学本科课程设计 (论文) 6 3 33 3 二叉树层次遍历二叉树层次遍历 层次遍历是从二叉树的根结点开始，自上而下，自左向右分层依次访问树中 的各个结点。按层次顺序访问二叉树的处理需要利用一个队列。在访问二叉树的 某一层结点时，把下一层结点指针预先记忆在队列中，利用队列安排逐层访问的 次序。因些，当访问一个结点时，将它的子女依次加到队列的队尾，然后再访问 已在队列队头的结点。这样就可以实现二叉树结点的按层访问。 二叉树层次遍历详细设计代码如下： void levelorder(treenode *proot,treenode *queue) int front,rear;/front 标记队列队头， rear 标记队列队尾 front=-1; rear=0; queuerear=proot;/二叉树结点从队尾开始添加 while(front!=rear) front+; if(queuefront-l!=null) /左孩子不为空，左孩子进队列 rear+; queuerear=queuefront-l; if(queuefront-r!=null)/右孩子不为空时，右孩子进队列 rear+; queuerear=queuefront-r; 3 34 4 程序与所实现的调度方案程序与所实现的调度方案 #include template class queue 武汉工程大学本科课程设计 (论文) 7 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()constreturn front=rear; bool isfull()constreturn (rear+1)%maxsize =front; bool front(t bool enqueue(t x); bool dequeue(t void clear()front = rear = 0; / void levelorder(); private: int front, rear; int maxsize; t* q; ; template seqqueue:seqqueue(int msize) maxsize = msize; q = new tmaxsize; front = rear = 0; template bool seqqueue:front(t /结点符号串 char flag;/结点标志符 int fre; /结点频数 struct treenode *l,*r; /左子女，右子女链域 武汉工程大学本科课程设计 (论文) 9 treenode():fre(0),l(null),r(null) /构造函数，初始化新建结点 data=new char50; memset(data,0,50); ; treenode *proot=new treenode;/为根结点创建新结点 void insert(treenode * 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; /右孩子为下个新建结点插入的当前结点 int len; char temp1000000; void gettemp() /读取给定某一序列里的字符串 ifstream ifs(“m8 序列.txt“); char ch; int i=0; while(!ifs.eof() ifs.get(ch); tempi=ch; i=i+1; 武汉工程大学本科课程设计 (论文) 10 coutflag=temp1k;/读取的字符赋给新建结点的符号 for(int l=0;ldatal=temp1l; /coutdatal+1=0; insert(current,pnode);/插入新建结点 void levelorder ()/二叉树的层次遍历 武汉工程大学本科课程设计 (论文) 11 cout q(20); treenode *p =proot; q.enqueue (p); while (!q.isempty () q.dequeue (p); if(p!=proot) coutdatafrel != null) /若左孩子非空 q.enqueue (p-l);/左孩子入队列 if (p-r!= null)/右孩子非空 q.enqueue (p-r);/右孩子入队列 void main() creattree();/建立二叉树 levelorder();/二叉树层次遍历 程序运行结果参见图 3-2。 武汉工程大学本科课程设计 (论文) 12 图 3-2 策略 2 下的作业调度方案 3 35 5 程序的优点程序的优点 本程序是通过二叉树的链表方式存储数据，计算二叉树每个结点的频数，利 用二叉树的层次遍历，输出二叉树的每个结点的频数，对于较大规模的作业都能 很快地得到运行结果。而且整个程序是基于链表和二叉树这种数据结构来实现的， 编程风格一致，容易理解。 武汉工程大学本科课程设计 (论文) 13 第第 4 4 章章 总总 结结 通过此次课程设计，使我更加扎实的掌握了有关用层次遍历访问二叉树序列 频数的问题。我们知道，其实有很多比如像素、图像等等都用到层次遍历来计算 它们的频数，由此也为自己第一次踏入这门知识的领域而感到骄傲。 虽然在本次课程设计中，我们曾遇到过种种问题。抱着对新领域的探索与求 知，我们一遍一遍的检查，终于找到了问题的所在，也暴露出了前期我们在这方 面上的知识欠缺与经验不足。实践出真知，通过自己亲自动手制作，使我们掌握 的知识不再是纸上谈兵。 作为一名信息专业的学生，从最开始学习的解析几何 、高等代数 一直到已经即将结束的 离散数学 。我们从终于将所学习的数学知识，在计 算机上得到了应用，我觉得有必要对这门课程设计中自己的所感进行一次总结， 希望对初学者有一定的帮助与启迪。 为为什什么么用用面面向向对对象象的的思思想想来来设设计计数数据据结结构构 用面向过程的程序设计方法，来进行数据结构的设计，学习时比较容易理解 与掌握。但它的数据一般是事先具体给定的，是为其功能函数服务的，函数起着 主导作用。 以函数为中心，对于函数的运用并不方便。以排序问题为例，用于排序的函 数不少，但对于一个实际问题，究竟应该选择哪一种排序函数，还必须根据实际 问题的数据结构来定。对于链表，你总不能选择冒泡函数来进行排序吧。 既然以函数为中心对于解决实际问题并不方便，那么，就只能选择以数据为 中心，将为数据服务的函数与它绑定在一起，使这些服务于数据的函数成为数据 的一部分。这就是面向对象程序设计中类的概念。 武汉工程大学本科课程设计 (论文) 14 致致 谢谢 到此本次课程设计终于画上了一句完美的句号，非常感谢这一次的课程设计， 使我们终于将 解析几何 、高等代数 与离散数学 里面的知识融入到 机器上，进行了一次综合的运用。 首先要感谢我的老师给我们提供了这次课程设计的机会，让我们将平时所学 习的知识更加的系统化。老师给予的指导，提供的支持与帮助，是我们能够完成 本次课程设计的最主要的原因。 我还要感谢和我一起奋斗不息的小组成员，我们曾不分日夜的一起在机房里 思考着，拼搏着，努力着。大家互相鼓励，互相支持，没有你们，也就没有本次 课程设计的诞生。 我还要感谢给予我们帮助的网络论坛上的朋友们，你们提供的宝贵意见，使 我们的程序能够进一步的优化。 最后还要感谢在参考文献中列出的各位编者，你们所写的书在我们课程设计 完成的道路上给过我们无数的指导。 这份课程设计，是我们对新领域的一次探索，我们已经上路了。 武汉工程大学本科课程设计 (论文) 15 参参考考文文献献 1 陈惠南.数据结构 .北京：清华大学出版社 ,2007. 2 茆诗松.概率论.北京：高等教育出版社 ,2004. 3 洪帆.离散数学 .北京：华中科技大学出版社 .2007. 武汉工程大学本科课程设计 (论文) 16 附附 录录 #include template class queue 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()constreturn front=rear; bool isfull()constreturn (rear+1)%maxsize =front; bool front(t bool enqueue(t x); bool dequeue(t void clear()front = rear = 0; / void levelorder(); private: int front, rear; int maxsize; t* q; ; template seqqueue:seqqueue(int msize) maxsize = msize; q = new tmaxsize; 武汉工程大学本科课程设计 (论文) 17 front = rear = 0; template bool seqqueue:front(t /结点符号串 char flag;/结点标志符 int fre; /结点频数 struct treenode *l,*r; /左子女，右子女