《离散数学课程设计（论文）基于二元树的随机序列独立性分析算法与实现.doc》由会员分享，可在线阅读，更多相关《离散数学课程设计（论文）基于二元树的随机序列独立性分析算法与实现.doc（25页珍藏版）》请在三一办公上搜索。
1、09 届课程（设计）论文题 目基于二元树的随机序列独立性分析算法与实现专业班级信息与计算科学(2)班学 号学生姓名指导教师指导教师职称副教授学院名称理学院完成日期： 2011 年 7月1日目 录目 录I摘 要II前 言III第1章 课题背景111问题背景112 基础知识113 意义114 文献综述2第2章 基于二元树的随机变量序列相依阶数估计321 算法概述322 数据结构设计第3章 功能函数实现531二叉树结点插入532 二叉树的建立533 二叉树层次遍历634 程序与所实现的调度方案735 程序的优缺点及改进13第4章 总 结14致 谢15参考文献16附 录17摘 要随机变量序列中的符号不
2、是独立的，通过程序的结果，统计出二元随机序列每一维序列频数，最后，我们要根据所得出的频数来分析与统计二元树随机变量序列相依阶数，找出随机序列中的最大独立单元。在该程序中，随机变量序列为随机的二进制串。关键词：二元随机序列，频数，相依阶数，最大独立单元，二进制串前 言本文解决了通过二叉树的链表方式存储数据并计算二叉树每个结点的频数。全文共四章。第1章介绍了问题背景以及相关的基础知识。在本章中，还给出了具体的实例分析和与之相关的定理。第2章主要介绍了解决课题的算法概述以及数据结构设计。第3章主要介绍了功能函数的实现，其中包括二叉树结点插入、二叉树的建立以及二叉树层次遍历。第4章是本次课程设计的总结
3、。全文的最后是致谢、参考文献和对程序优化处理的源代码。*2011-7-1于武汉工程大学理学院第1章 课题背景11问题背景随机变量序列的独立性与相依性是概率论中很重要的概念。许多随机变量序列中的符号的出现都与其前面若干个符号有依赖关系，在研究分析时限制随机序列的记忆长度，当记忆长度固定时，这样的记忆信源为马尔可夫信源。而实际上，有很多随机序列的记忆长度不是固定的，这样随机序列相依阶数是变化的。基于二元树随机变量序列相依阶数估计是通过分析树结点的空间分布，可以判定出该随机变量序列是独立还是相依的。若随机序列是相依的，可以统计出该序列相依阶数。12 基础知识独立性是概率论中一个重要的概念，两个事件之
4、间的独立性是指：一个事件的发生不影响另一个事件的发生。这在实际问题中是很多的。譬如在掷颗骰子，记事件A为“第一颗骰子的点数为1”，记事件B为“第二颗骰子的点数为4”。则显然A与B的发生是相互不影响的。若事件A与B相互独立，称A与B独立，否则A与B不独立即A与B相依。在多维随机变量中，各分量的取值有时会相互影响，但有时会毫无影响。譬如一个人的身高X和体重Y就会相互影响，但与收入Z一般无影响。当两个随机变量取值互不影响时，就称它们是相互独立的。同理，若它们的取值之间有影响，则它们之间是相依的。13 意义在信息论中，多符号离散稳信源是多符号离散信源中最简单，最常用，而且也是至今为止讨论最充分、理论最
5、成熟的一种信源。多符号离散信源发出的消息是由一系列离散符号组成的时间（或空间）序列来表示。例如，电报系统发出的消息，就是由“正”脉冲表示的“0”符号和“负”脉冲表示的“1”符号组成的一连串“0”、“1”符号的时间序列来表示的。根据信息的定义，这种由离散符号的时间序列代表的消息要含有信息的前提条件是消息具有随机性，也就是每一单位时间出现的离散符号必须具有随机性。14 文献综述文献1介绍了二叉树结点的形成与层次遍历。文献2介绍了概率论中随机连续型序列与离散型序列独立性的分析。文献3以实例较为详细地介绍了二叉树的分析算法与实现。第2章 基于二元树的随机变量序列相依阶数估计21 算法概述根据课题要求，
6、我们将通过二叉树的链表方式存储数据，计算二叉树每个结点的频数。当将二进制序列读取后，按指定的维数N，从第一个字符开始一次读取N个字符，依次插入结点建立二叉树，再从第二个字符开始读取N个字符，从根结点开始依次插入，依次类推，直到循环到最后一个字符读取N个字符依次插入后，二叉树建立完成。在插入结点的过程中，若二叉树此处结点已存在，只需次其频数增1，若结点不存在，则插入结点，并将频数增1。当输出二叉树每个结点的频数时，利用二叉树的层次遍历。按层次顺序访问二叉树的处理需要利用一个队列。在访问二叉树的某一层结点时，把下一层结点指针预先记忆在队列中，利用队列安排逐层访问的次序。因些，当访问一个结点时，将它
7、的子女依次加到队列的队尾，然后再访问已在队列队头的结点。这样，二叉树每个结点按照层次遍历的顺序存储在了队列中。最后，将得到的结点频数通过计算研究，分析m元树同高度的结点空间分布以及最大独立单元和其状态空间，并且通过计算分析估计随机变量序列的相依阶数。22 数据结构设计定义一个结构体来表示二叉树的结点，结构体里包含结点频数，结点符号串，结点符号，结点左右指针。结点频数表示循环二叉树建立后，经过该结点的总次数；结点符号主要是读取二进制串时，结点符号取0表示新建结点为左孩子，符号取1表示新建结点为右孩子；将频数、符号，结点符号串存入带根结点的二叉树中，频数的属性取了fre，标志符的属性取了flag，
8、结点符号串的属性取了data，左子女结点指针为L，右子女结点指针为R。并将fre，flag，data和L，R封装在结点类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)
9、,L(NULL),R(NULL) /构造函数，初始化新建结点data=new char50;memset(data,0,50);第3章 功能函数实现31 二叉树结点插入二叉树结点插入函数带两个参数，分别为当前结点、待插入结点。该函数在设计过程中，有着一定的插入规则。当读取字符为0，即新建结点标志符取0，若当前结点左子树为空，则新建结点插入到当前结点的左子树，同时左孩子结点频数增1，若当前结点左子树不为空，则当前左孩子结点频数增1；当读取字符为1，即新建结点标志符取1，若当前结点右子树为空，则新建结点插入到当前结点的右子树，同时右孩子结点频数增1，若当前结点右子树不为空，则当前右孩子结点频数增1
10、。当结点插入成功后，该结点即为下个结点插入的当前结点。结点插入函数详细设计代码如下：void CreateTree(TreeNode *&Current,TreeNode *pNode)if(pNode-flag=0)/当新建结点标志符取0if(Current-L=NULL)/当前结点左子树为空Current-L=pNode;Current-L-fre+=1;/结点频数增1Current=Current-L; /左孩子为下个新建结点插入的当前结点else if(pNode-flag=1)/当新建结点标志符取1if(Current-R=NULL) /当前结点右子树为空 Current-R=pNo
11、de;Current-R-fre+=1; /结点频数增1Current=Current-R; /右孩子为下个新建结点插入的当前结点32 二叉树的建立二叉树的建立是一个循环的过程。插入第一次读取的N个字符时，从根结点开始，将从存储在temp中的二进制串中读取出的N个字符作为结点依次插入二叉树，同时记录每个结点的结点符号串；第二次插入读取的N个字符时，继续是从根结点开始，依次插入二叉树。直到将二进制串循环读取完，二叉树建立才完成。在此过程中，每插入N个字符后，要将当前指针Current指向根结点，同时要将临时存储N个字符的变量temp1重新初始化。二叉树的根结点不为空，且其结点标志符为空。二叉树的
12、建立详细设计代码如下：char *temp1=new char100;for(int j=0;jlen;j+)/循环建立二叉树memset(temp1,0,100);/初始化temp1int h=1;for(int i=0;iN;i+)/存储从二进制串读取的N个字符temp1i=temp(i+j)%len; Current=pRoot;/建立二叉树从根结点开始，即当前结点为根结点for(int k=0;kflag=temp1k;/读取的字符赋给新建结点的符号for(int l=0;ldatal=temp1l;pNode-datal+1=0;CreateTree(Current,pNode);/
13、插入新建结点33 二叉树层次遍历层次遍历是从二叉树的根结点开始，自上而下，自左向右分层依次访问树中的各个结点。按层次顺序访问二叉树的处理需要利用一个队列。在访问二叉树的某一层结点时，把下一层结点指针预先记忆在队列中，利用队列安排逐层访问的次序。因些，当访问一个结点时，将它的子女依次加到队列的队尾，然后再访问已在队列队头的结点。这样就可以实现二叉树结点的按层访问。二叉树层次遍历详细设计代码如下：void LevelOrder(TreeNode *pRoot,TreeNode *queue)int front,rear;/front标记队列队头，rear标记队列队尾front=-1;rear=0;
14、queuerear=pRoot;/二叉树结点从队尾开始添加while(front!=rear)front+;if(queuefront-L!=NULL) /左孩子不为空，左孩子进队列rear+;queuerear=queuefront-L;if(queuefront-R!=NULL)/右孩子不为空时，右孩子进队列rear+;queuerear=queuefront-R;34 程序与所实现的调度方案#include templateclass Queue public: virtual bool IsEmpty()const = 0; virtual bool IsFull()const = 0
15、; virtual bool Front(T &x)const =0; virtual bool EnQueue(T x)=0; virtual bool DeQueue(T &x)=0; virtual void Clear()=0;templateclass SeqQueue:public Queue public: SeqQueue(int mSize); SeqQueue()delete q; bool IsEmpty()constreturn front=rear; bool IsFull()constreturn (rear+1)%maxSize =front; bool Fron
16、t(T &x)const; bool EnQueue(T x); bool DeQueue(T&x); void Clear()front = rear = 0; / void LevelOrder(); private: int front, rear; int maxSize; T* q;templateSeqQueue:SeqQueue(int mSize) maxSize = mSize; q = new TmaxSize; front = rear = 0;templatebool SeqQueue:Front(T &x)const if(IsEmpty() cout Empty e
17、ndl; return false; x = q(front +1)%maxSize; return true;templatebool SeqQueue:EnQueue(T x) if(IsFull() cout Full endl; return false; qrear=(rear+1)%maxSize=x; return true;templatebool SeqQueue:DeQueue(T &x) if(IsEmpty() cout Underflow endl; return false; front=(front +1)%maxSize; x=qfront; return tr
18、ue;#include#include#include/输出格式控制#include#includeQueue.h#include#define N 4struct 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);TreeNode *pRoot=new TreeNode;/为根结点创建新结点v
19、oid Insert(TreeNode *&Current,TreeNode *pNode)if(pNode-flag=0)/当新建结点标志符取0if(Current-L=NULL)/当前结点左子树为空 Current-L=pNode;Current-L-fre+=1;/结点频数增1Current=Current-L; /左孩子为下个新建结点插入的当前结点else if(pNode-flag=1)/当新建结点标志符取1if(Current-R=NULL) /当前结点右子树为空 Current-R=pNode;Current-R-fre+=1; /结点频数增1Current=Current-R;
20、 /右孩子为下个新建结点插入的当前结点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; cout该二进制串的长度为：; coutifs.tellg();/输出该二进制串的长度 coutendl; ifs.close(); len=i; TreeNode *Current=new TreeNode; void CreatTree()Gettemp();/获取二进制
21、串 char *temp1=new char100; for(int j=0;jlen;j+) /循环建立二叉树memset(temp1,0,100);/初始化temp1int h=1;for(int i=0;iN;i+)/存储从二进制串读取的N个字符temp1i=temp(i+j)%len; Current=pRoot;/建立二叉树从根结点开始，即当前结点为根结点for(int k=0;kflag=temp1k;/读取的字符赋给新建结点的符号for(int l=0;ldatal=temp1l;/couttemp1ldatal+1=0;Insert(Current,pNode);/插入新建结点
22、 void LevelOrder ()/二叉树的层次遍历 cout层次遍历被访问后endl; if (pRoot = NULL) return; SeqQueue Q(20); TreeNode *p =pRoot; Q.EnQueue (p); while (!Q.IsEmpty () Q.DeQueue (p); if(p!=pRoot) coutdata的频数为tfreL != NULL) /若左孩子非空 Q.EnQueue (p-L);/左孩子入队列 if (p-R!= NULL)/右孩子非空 Q.EnQueue (p-R);/右孩子入队列 void main() CreatTree(
23、);/建立二叉树 LevelOrder();/二叉树层次遍历程序运行结果参见图3-2。图3-2 策略2下的作业调度方案35 程序的优点本程序是通过二叉树的链表方式存储数据，计算二叉树每个结点的频数，利用二叉树的层次遍历，输出二叉树的每个结点的频数，对于较大规模的作业都能很快地得到运行结果。而且整个程序是基于链表和二叉树这种数据结构来实现的，编程风格一致，容易理解。第4章 总 结通过此次课程设计，使我更加扎实的掌握了有关用层次遍历访问二叉树序列频数的问题。我们知道，其实有很多比如像素、图像等等都用到层次遍历来计算它们的频数，由此也为自己第一次踏入这门知识的领域而感到骄傲。虽然在本次课程设计中，我
24、们曾遇到过种种问题。抱着对新领域的探索与求知，我们一遍一遍的检查，终于找到了问题的所在，也暴露出了前期我们在这方面上的知识欠缺与经验不足。实践出真知，通过自己亲自动手制作，使我们掌握的知识不再是纸上谈兵。作为一名信息专业的学生，从最开始学习的解析几何、高等代数一直到已经即将结束的离散数学。我们从终于将所学习的数学知识，在计算机上得到了应用，我觉得有必要对这门课程设计中自己的所感进行一次总结，希望对初学者有一定的帮助与启迪。为什么用面向对象的思想来设计数据结构用面向过程的程序设计方法，来进行数据结构的设计，学习时比较容易理解与掌握。但它的数据一般是事先具体给定的，是为其功能函数服务的，函数起着主
25、导作用。以函数为中心，对于函数的运用并不方便。以排序问题为例，用于排序的函数不少，但对于一个实际问题，究竟应该选择哪一种排序函数，还必须根据实际问题的数据结构来定。对于链表，你总不能选择冒泡函数来进行排序吧。既然以函数为中心对于解决实际问题并不方便，那么，就只能选择以数据为中心，将为数据服务的函数与它绑定在一起，使这些服务于数据的函数成为数据的一部分。这就是面向对象程序设计中类的概念。致 谢到此本次课程设计终于画上了一句完美的句号，非常感谢这一次的课程设计，使我们终于将解析几何、高等代数与离散数学里面的知识融入到机器上，进行了一次综合的运用。首先要感谢我的老师给我们提供了这次课程设计的机会，让
26、我们将平时所学习的知识更加的系统化。老师给予的指导，提供的支持与帮助，是我们能够完成本次课程设计的最主要的原因。我还要感谢和我一起奋斗不息的小组成员，我们曾不分日夜的一起在机房里思考着，拼搏着，努力着。大家互相鼓励，互相支持，没有你们，也就没有本次课程设计的诞生。我还要感谢给予我们帮助的网络论坛上的朋友们，你们提供的宝贵意见，使我们的程序能够进一步的优化。最后还要感谢在参考文献中列出的各位编者，你们所写的书在我们课程设计完成的道路上给过我们无数的指导。这份课程设计，是我们对新领域的一次探索，我们已经上路了。参考文献1 陈惠南.数据结构.北京：清华大学出版社,2007.2 茆诗松.概率论.北京：
27、高等教育出版社,2004.3 洪帆.离散数学.北京：华中科技大学出版社.2007.附 录#include templateclass Queue public: virtual bool IsEmpty()const = 0; virtual bool IsFull()const = 0; virtual bool Front(T &x)const =0; virtual bool EnQueue(T x)=0; virtual bool DeQueue(T &x)=0; virtual void Clear()=0;templateclass SeqQueue:public Queue pu
28、blic: SeqQueue(int mSize); SeqQueue()delete q; bool IsEmpty()constreturn front=rear; bool IsFull()constreturn (rear+1)%maxSize =front; bool Front(T &x)const; bool EnQueue(T x); bool DeQueue(T&x); void Clear()front = rear = 0; / void LevelOrder(); private: int front, rear; int maxSize; T* q;templateS
29、eqQueue:SeqQueue(int mSize) maxSize = mSize; q = new TmaxSize; front = rear = 0;templatebool SeqQueue:Front(T &x)const if(IsEmpty() cout Empty endl; return false; x = q(front +1)%maxSize; return true;templatebool SeqQueue:EnQueue(T x) if(IsFull() cout Full endl; return false; qrear=(rear+1)%maxSize=
30、x; return true;templatebool SeqQueue:DeQueue(T &x) if(IsEmpty() cout Underflow endl; return false; front=(front +1)%maxSize; x=qfront; return true;#include#include#include/输出格式控制#include#includeQueue.h#include#define N 4struct TreeNode/二叉树结点类定义char *data;/结点符号串char flag;/结点标志符int fre;/结点频数struct Tre
31、eNode *L,*R; /左子女，右子女链域TreeNode():fre(0),L(NULL),R(NULL) /构造函数，初始化新建结点data=new char50;memset(data,0,50);TreeNode *pRoot=new TreeNode;/为根结点创建新结点void Insert(TreeNode *&Current,TreeNode *pNode)if(pNode-flag=0)/当新建结点标志符取0if(Current-L=NULL)/当前结点左子树为空 Current-L=pNode;Current-L-fre+=1;/结点频数增1Current=Curren
32、t-L; /左孩子为下个新建结点插入的当前结点else if(pNode-flag=1)/当新建结点标志符取1if(Current-R=NULL) /当前结点右子树为空 Current-R=pNode;Current-R-fre+=1; /结点频数增1Current=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
33、=i+1; cout该二进制串的长度为：; coutifs.tellg();/输出该二进制串的长度 coutendl; ifs.close(); len=i; TreeNode *Current=new TreeNode; void CreatTree()Gettemp();/获取二进制串 char *temp1=new char100; for(int j=0;jlen;j+) /循环建立二叉树memset(temp1,0,100);/初始化temp1int h=1;for(int i=0;iN;i+)/存储从二进制串读取的N个字符temp1i=temp(i+j)%len; Current=
34、pRoot;/建立二叉树从根结点开始，即当前结点为根结点for(int k=0;kflag=temp1k;/读取的字符赋给新建结点的符号for(int l=0;ldatal=temp1l;/couttemp1ldatal+1=0;Insert(Current,pNode);/插入新建结点 void LevelOrder ()/二叉树的层次遍历 cout层次遍历被访问后endl; if (pRoot = NULL) return; SeqQueue Q(20); TreeNode *p =pRoot; Q.EnQueue (p); while (!Q.IsEmpty () Q.DeQueue (p); if(p!=pRoot) coutdata的频数为tfreL != NULL) /若左孩子非空 Q.EnQueue (p-L);/左孩子入队列 if (p-R!= NULL)/右孩子非空 Q.EnQueue (p-R);/右孩子入队列 void main() CreatTree();/建立二叉树 LevelOrder();/二叉树层次遍历
