離散數(shù)學(xué)課程設(shè)計(jì)（論文）基于二元樹的隨機(jī)序列獨(dú)立性分析算法與實(shí)現(xiàn)

1、09 屆課程（設(shè)計(jì)）論文 題題 目目基基于于二二元元樹樹的的隨隨機(jī)機(jī)序序列列獨(dú)獨(dú)立立性性分分析析算算法法與與實(shí)實(shí)現(xiàn)現(xiàn) 專專業(yè)業(yè)班班級(jí)級(jí)信信息息與與計(jì)計(jì)算算科科學(xué)學(xué) (2)班班 學(xué)學(xué) 號(hào)號(hào) 學(xué)學(xué)生生姓姓名名 指指導(dǎo)導(dǎo)教教師師 指指導(dǎo)導(dǎo)教教師師職職稱稱副副教教授授 學(xué)學(xué)院院名名稱稱理理學(xué)學(xué)院院 完完成成日日期期： 2011 年年 7 月月 1 日日 目目 錄錄 目 錄 .i 摘 要 .ii 前 言 .iii 第 1 章 課題背景 .1 11 問題背景 .1 12 基礎(chǔ)知識(shí) .1 13 意義.1 14 文獻(xiàn)綜述 .2 第 2 章 基于二元樹的隨機(jī)變量序列相依階數(shù)估計(jì).3 21 算法概述 .3 22

2、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) . 第 3 章 功能函數(shù)實(shí)現(xiàn) .5 31 二叉樹結(jié)點(diǎn)插入 .5 32 二叉樹的建立 .5 33 二叉樹層次遍歷 .6 34 程序與所實(shí)現(xiàn)的調(diào)度方案 .7 35 程序的優(yōu)缺點(diǎn)及改進(jìn) .13 第 4 章 總 結(jié) .14 致 謝.15 參考文獻(xiàn) .16 附 錄 .17 摘摘 要要 隨機(jī)變量序列中的符號(hào)不是獨(dú)立的，通過程序的結(jié)果，統(tǒng)計(jì)出二元隨機(jī)序列 每一維序列頻數(shù)，最后，我們要根據(jù)所得出的頻數(shù)來分析與統(tǒng)計(jì)二元樹隨機(jī)變量 序列相依階數(shù)，找出隨機(jī)序列中的最大獨(dú)立單元。在該程序中，隨機(jī)變量序列為 隨機(jī)的二進(jìn)制串。 關(guān)關(guān)鍵鍵詞詞：二元隨機(jī)序列，頻數(shù)，相依階數(shù)，最大獨(dú)立單元，二進(jìn)制串 前前 言言

3、本文解決了通過二叉樹的鏈表方式存儲(chǔ)數(shù)據(jù)并計(jì)算二叉樹每個(gè)結(jié)點(diǎn)的頻數(shù)。 全文共四章。 第 1 章介紹了 問題背景以及相關(guān)的基礎(chǔ)知識(shí)。在本章中，還給出了具體的實(shí) 例分析和與之相關(guān)的定理。 第 2 章主要介紹了解決課題的算法概述以及數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。 第 3 章主要介紹了功能函數(shù)的實(shí)現(xiàn)，其中包括二叉樹結(jié)點(diǎn)插入、二叉樹的建 立以及二叉樹層次遍歷。 第 4 章是本次課程設(shè)計(jì)的總結(jié)。 全文的最后是致謝、參考文獻(xiàn)和對(duì)程序優(yōu)化處理的源代碼。 * 2011-7-1 于武漢工程大學(xué)理學(xué)院 第第 1 1 章章 課課題題背背景景 1 11 1 問題背景問題背景 隨機(jī)變量序列的獨(dú)立性與相依性是概率論中很重要的概念。許多隨機(jī)變

4、量序 列中的符號(hào)的出現(xiàn)都與其前面若干個(gè)符號(hào)有依賴關(guān)系，在研究分析時(shí)限制隨機(jī)序 列的記憶長(zhǎng)度，當(dāng)記憶長(zhǎng)度固定時(shí)，這樣的記憶信源為馬爾可夫信源。而實(shí)際上， 有很多隨機(jī)序列的記憶長(zhǎng)度不是固定的，這樣隨機(jī)序列相依階數(shù)是變化的?；?二元樹隨機(jī)變量序列相依階數(shù)估計(jì)是通過分析樹結(jié)點(diǎn)的空間分布，可以判定出該 隨機(jī)變量序列是獨(dú)立還是相依的。若隨機(jī)序列是相依的，可以統(tǒng)計(jì)出該序列相依 階數(shù)。 1 12 2 基礎(chǔ)知識(shí)基礎(chǔ)知識(shí) 獨(dú)立性是概率論中一個(gè)重要的概念，兩個(gè)事件之間的獨(dú)立性是指：一個(gè)事件 的發(fā)生不影響另一個(gè)事件的發(fā)生。這在實(shí)際問題中是很多的。譬如在擲顆骰子， 記事件 a 為“第一顆骰子的點(diǎn)數(shù)為 1”，記事件 b

5、 為“第二顆骰子的點(diǎn)數(shù)為 4”。則顯然 a 與 b 的發(fā)生是相互不影響的。若事件a 與 b 相互獨(dú)立，稱 a 與 b 獨(dú)立，否則 a 與 b 不獨(dú)立即 a 與 b 相依。 在多維隨機(jī)變量中，各分量的取值有時(shí)會(huì)相互影響，但有時(shí)會(huì)毫無影響。譬 如一個(gè)人的身高 x 和體重 y 就會(huì)相互影響，但與收入 z 一般無影響。當(dāng)兩個(gè)隨 機(jī)變量取值互不影響時(shí)，就稱它們是相互獨(dú)立的。同理，若它們的取值之間有影 響，則它們之間是相依的。 1 13 3 意義意義 在信息論中，多符號(hào)離散穩(wěn)信源是多符號(hào)離散信源中最簡(jiǎn)單，最常用，而且 也是至今為止討論最充分、理論最成熟的一種信源。多符號(hào)離散信源發(fā)出的消息 是由一系列離散符

6、號(hào)組成的時(shí)間（或空間）序列來表示。例如，電報(bào)系統(tǒng)發(fā)出的 消息，就是由 “正”脈沖表示的 “0”符號(hào)和“負(fù)”脈沖表示的 “1”符號(hào)組成 的一連串 “0”、“1”符號(hào)的時(shí)間序列來表示的。根據(jù)信息的定義，這種由離散 符號(hào)的時(shí)間序列代表的消息要含有信息的前提條件是消息具有隨機(jī)性，也就是每 一單位時(shí)間出現(xiàn)的離散符號(hào)必須具有隨機(jī)性。 1 14 4 文獻(xiàn)綜述文獻(xiàn)綜述 文獻(xiàn)1介紹了二叉樹結(jié)點(diǎn)的形成與層次遍歷。 文獻(xiàn)2介紹了概率論中隨機(jī)連續(xù)型序列與離散型序列獨(dú)立性的分析。 文獻(xiàn)3以實(shí)例較為詳細(xì)地介紹了二叉樹的分析算法與實(shí)現(xiàn)。 第第 2 2 章章 基基于于二二元元樹樹的的隨隨機(jī)機(jī)變變量量序序列列相相依依階階數(shù)數(shù)估

7、估計(jì)計(jì) 2 21 1 算法概述算法概述 根據(jù)課題要求，我們將通過二叉樹的鏈表方式存儲(chǔ)數(shù)據(jù)，計(jì)算二叉樹每個(gè)結(jié) 點(diǎn)的頻數(shù)。當(dāng)將二進(jìn)制序列讀取后，按指定的維數(shù)n，從第一個(gè)字符開始一次 讀取 n 個(gè)字符，依次插入結(jié)點(diǎn)建立二叉樹，再從第二個(gè)字符開始讀取n 個(gè)字符， 從根結(jié)點(diǎn)開始依次插入，依次類推，直到循環(huán)到最后一個(gè)字符讀取n 個(gè)字符依 次插入后，二叉樹建立完成。在插入結(jié)點(diǎn)的過程中，若二叉樹此處結(jié)點(diǎn)已存在， 只需次其頻數(shù)增 1，若結(jié)點(diǎn)不存在，則插入結(jié)點(diǎn)，并將頻數(shù)增1。 當(dāng)輸出二叉樹每個(gè)結(jié)點(diǎn)的頻數(shù)時(shí)，利用二叉樹的層次遍歷。按層次順序訪問 二叉樹的處理需要利用一個(gè)隊(duì)列。在訪問二叉樹的某一層結(jié)點(diǎn)時(shí)，把下一層結(jié)點(diǎn)

8、 指針預(yù)先記憶在隊(duì)列中，利用隊(duì)列安排逐層訪問的次序。因些，當(dāng)訪問一個(gè)結(jié)點(diǎn) 時(shí)，將它的子女依次加到隊(duì)列的隊(duì)尾，然后再訪問已在隊(duì)列隊(duì)頭的結(jié)點(diǎn)。這樣， 二叉樹每個(gè)結(jié)點(diǎn)按照層次遍歷的順序存儲(chǔ)在了隊(duì)列中。 最后，將得到的結(jié)點(diǎn)頻數(shù)通過計(jì)算研究，分析m 元樹同高度的結(jié)點(diǎn)空間分布以 及最大獨(dú)立單元和其狀態(tài)空間，并且通過計(jì)算分析估計(jì)隨機(jī)變量序列的相依階數(shù)。 2 22 2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 定義一個(gè)結(jié)構(gòu)體來表示二叉樹的結(jié)點(diǎn)，結(jié)構(gòu)體里包含結(jié)點(diǎn)頻數(shù)，結(jié)點(diǎn)符號(hào)串， 結(jié)點(diǎn)符號(hào)，結(jié)點(diǎn)左右指針。結(jié)點(diǎn)頻數(shù)表示循環(huán)二叉樹建立后，經(jīng)過該結(jié)點(diǎn)的總次 數(shù)；結(jié)點(diǎn)符號(hào)主要是讀取二進(jìn)制串時(shí)，結(jié)點(diǎn)符號(hào)取0 表示新建結(jié)點(diǎn)為左孩子， 符號(hào)

9、取 1 表示新建結(jié)點(diǎn)為右孩子； 將頻數(shù)、符號(hào)，結(jié)點(diǎn)符號(hào)串存入帶根結(jié)點(diǎn)的二叉樹中，頻數(shù)的屬性取了fre， 標(biāo)志符的屬性取了 flag，結(jié)點(diǎn)符號(hào)串的屬性取了 data，左子女結(jié)點(diǎn)指針為 l，右子女結(jié)點(diǎn)指針為 r。并將 fre，flag，data 和 l，r 封裝在結(jié)點(diǎn)類 treenode 中。其鏈結(jié)點(diǎn) node 的數(shù)據(jù)結(jié)構(gòu)如圖 2-2 所示： 圖 2-2 二叉樹結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu) 其中，fre 為整型， flag 為字符型， data 為字符型指針，而 l，r 為指向二叉樹 結(jié)點(diǎn) treenode 的指針。 將 treenode 定義成結(jié)構(gòu)體，代碼如下： struct treenode/二叉樹結(jié)點(diǎn)類定

10、義 char *data; /結(jié)點(diǎn)頻數(shù) char flag;/結(jié)點(diǎn)標(biāo)志符 int fre;/結(jié)點(diǎn)符號(hào)串 struct treenode *l,*r; /左子女，右子女鏈域 treenode():fre(0),l(null),r(null) /構(gòu)造函數(shù)，初始化新建結(jié)點(diǎn) data=new char50; memset(data,0,50); ; 第第 3 3 章章 功功能能函函數(shù)數(shù)實(shí)實(shí)現(xiàn)現(xiàn) 3 31 1 二叉樹結(jié)點(diǎn)插入二叉樹結(jié)點(diǎn)插入 二叉樹結(jié)點(diǎn)插入函數(shù)帶兩個(gè)參數(shù)，分別為當(dāng)前結(jié)點(diǎn)、待插入結(jié)點(diǎn)。該函數(shù)在 設(shè)計(jì)過程中，有著一定的插入規(guī)則。當(dāng)讀取字符為0，即新建結(jié)點(diǎn)標(biāo)志符取 0，若當(dāng)前結(jié)點(diǎn)左子樹為空，則新

11、建結(jié)點(diǎn)插入到當(dāng)前結(jié)點(diǎn)的左子樹，同時(shí)左孩子 結(jié)點(diǎn)頻數(shù)增 1，若當(dāng)前結(jié)點(diǎn)左子樹不為空，則當(dāng)前左孩子結(jié)點(diǎn)頻數(shù)增1；當(dāng)讀 取字符為 1，即新建結(jié)點(diǎn)標(biāo)志符取 1，若當(dāng)前結(jié)點(diǎn)右子樹為空，則新建結(jié)點(diǎn)插入 到當(dāng)前結(jié)點(diǎn)的右子樹，同時(shí)右孩子結(jié)點(diǎn)頻數(shù)增1，若當(dāng)前結(jié)點(diǎn)右子樹不為空， 則當(dāng)前右孩子結(jié)點(diǎn)頻數(shù)增 1。當(dāng)結(jié)點(diǎn)插入成功后，該結(jié)點(diǎn)即為下個(gè)結(jié)點(diǎn)插入的當(dāng) 前結(jié)點(diǎn)。 結(jié)點(diǎn)插入函數(shù)詳細(xì)設(shè)計(jì)代碼如下： void createtree(treenode * current-l-fre+=1;/結(jié)點(diǎn)頻數(shù)增 1 current=current-l; /左孩子為下個(gè)新建結(jié)點(diǎn)插入的當(dāng)前結(jié)點(diǎn) else if(pnode-flag=1)

12、/當(dāng)新建結(jié)點(diǎn)標(biāo)志符取 1 if(current-r=null) /當(dāng)前結(jié)點(diǎn)右子樹為空 current-r=pnode; current-r-fre+=1; /結(jié)點(diǎn)頻數(shù)增 1 current=current-r; /右孩子為下個(gè)新建結(jié)點(diǎn)插入的當(dāng)前結(jié)點(diǎn) 3 32 2 二叉樹的建立二叉樹的建立 二叉樹的建立是一個(gè)循環(huán)的過程。插入第一次讀取的n 個(gè)字符時(shí)，從根結(jié) 點(diǎn)開始，將從存儲(chǔ)在 temp 中的二進(jìn)制串中讀取出的 n 個(gè)字符作為結(jié)點(diǎn)依次插 入二叉樹，同時(shí)記錄每個(gè)結(jié)點(diǎn)的結(jié)點(diǎn)符號(hào)串；第二次插入讀取的n 個(gè)字符時(shí)， 繼續(xù)是從根結(jié)點(diǎn)開始，依次插入二叉樹。直到將二進(jìn)制串循環(huán)讀取完，二叉樹建 立才完成。在此過程

13、中，每插入n 個(gè)字符后，要將當(dāng)前指針 current 指向根結(jié) 點(diǎn)，同時(shí)要將臨時(shí)存儲(chǔ) n 個(gè)字符的變量 temp1 重新初始化。二叉樹的根結(jié)點(diǎn)不 為空，且其結(jié)點(diǎn)標(biāo)志符為空。 二叉樹的建立詳細(xì)設(shè)計(jì)代碼如下： char *temp1=new char100; for(int j=0;jlen;j+)/循環(huán)建立二叉樹 memset(temp1,0,100); /初始化 temp1 int h=1; for(int i=0;in;i+)/存儲(chǔ)從二進(jìn)制串讀取的 n 個(gè)字符 temp1i=temp(i+j)%len; current=proot;/建立二叉樹從根結(jié)點(diǎn)開始，即當(dāng)前結(jié)點(diǎn)為根結(jié)點(diǎn) for(int

14、 k=0;kflag=temp1k;/讀取的字符賦給新建結(jié)點(diǎn)的符號(hào) for(int l=0;ldatal=temp1l; pnode-datal+1=0; createtree(current,pnode);/插入新建結(jié)點(diǎn) 3 33 3 二叉樹層次遍歷二叉樹層次遍歷 層次遍歷是從二叉樹的根結(jié)點(diǎn)開始，自上而下，自左向右分層依次訪問樹中 的各個(gè)結(jié)點(diǎn)。按層次順序訪問二叉樹的處理需要利用一個(gè)隊(duì)列。在訪問二叉樹的 某一層結(jié)點(diǎn)時(shí)，把下一層結(jié)點(diǎn)指針預(yù)先記憶在隊(duì)列中，利用隊(duì)列安排逐層訪問的 次序。因些，當(dāng)訪問一個(gè)結(jié)點(diǎn)時(shí)，將它的子女依次加到隊(duì)列的隊(duì)尾，然后再訪問 已在隊(duì)列隊(duì)頭的結(jié)點(diǎn)。這樣就可以實(shí)現(xiàn)二叉樹結(jié)點(diǎn)的按

15、層訪問。 二叉樹層次遍歷詳細(xì)設(shè)計(jì)代碼如下： void levelorder(treenode *proot,treenode *queue) int front,rear;/front 標(biāo)記隊(duì)列隊(duì)頭， rear 標(biāo)記隊(duì)列隊(duì)尾 front=-1; rear=0; queuerear=proot;/二叉樹結(jié)點(diǎn)從隊(duì)尾開始添加 while(front!=rear) front+; if(queuefront-l!=null) /左孩子不為空，左孩子進(jìn)隊(duì)列 rear+; queuerear=queuefront-l; if(queuefront-r!=null)/右孩子不為空時(shí)，右孩子進(jìn)隊(duì)列 rear+

16、; queuerear=queuefront-r; 3 34 4 程序與所實(shí)現(xiàn)的調(diào)度方案程序與所實(shí)現(xiàn)的調(diào)度方案 #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 publi

17、c: 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:seqqu

18、eue(int msize) maxsize = msize; q = new tmaxsize; front = rear = 0; template bool seqqueue:front(t return false; x = q(front +1)%maxsize; return true; template bool seqqueue:enqueue(t x) if(isfull() cout full endl; return false; qrear=(rear+1)%maxsize=x; return true; template bool seqqueue:dequeue(t

19、 return false; front=(front +1)%maxsize; x=qfront; return true; #include #include #include/輸出格式控制 #include #includequeue.h #include #define n 4 struct treenode /二叉樹結(jié)點(diǎn)類定義 char *data;/結(jié)點(diǎn)符號(hào)串 char flag;/結(jié)點(diǎn)標(biāo)志符 int fre; /結(jié)點(diǎn)頻數(shù) struct treenode *l,*r; /左子女，右子女鏈域 treenode():fre(0),l(null),r(null) /構(gòu)造函數(shù)，初始化新建結(jié)

20、點(diǎn) data=new char50; memset(data,0,50); ; treenode *proot=new treenode;/為根結(jié)點(diǎn)創(chuàng)建新結(jié)點(diǎn) void insert(treenode * current-l-fre+=1;/結(jié)點(diǎn)頻數(shù)增 1 current=current-l; /左孩子為下個(gè)新建結(jié)點(diǎn)插入的當(dāng)前結(jié)點(diǎn) else if(pnode-flag=1) /當(dāng)新建結(jié)點(diǎn)標(biāo)志符取 1 if(current-r=null) /當(dāng)前結(jié)點(diǎn)右子樹為空 current-r=pnode; current-r-fre+=1; /結(jié)點(diǎn)頻數(shù)增 1 current=current-r; /右孩子為

21、下個(gè)新建結(jié)點(diǎn)插入的當(dāng)前結(jié)點(diǎn) 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該二進(jìn)制串的長(zhǎng)度為： ; coutifs.tellg();/輸出該二進(jìn)制串的長(zhǎng)度 coutendl; ifs.close(); len=i; treenode *current=new treenode; void creattree() gettemp();/獲取二進(jìn)

22、制串 char *temp1=new char100; for(int j=0;jlen;j+) /循環(huán)建立二叉樹 memset(temp1,0,100); /初始化 temp1 int h=1; for(int i=0;in;i+) /存儲(chǔ)從二進(jìn)制串讀取的 n 個(gè)字符 temp1i=temp(i+j)%len; current=proot;/建立二叉樹從根結(jié)點(diǎn)開始，即當(dāng)前結(jié)點(diǎn)為根結(jié)點(diǎn) for(int k=0;kflag=temp1k;/讀取的字符賦給新建結(jié)點(diǎn)的符號(hào) for(int l=0;ldatal=temp1l; /couttemp1ldatal+1=0; insert(current,

23、pnode);/插入新建結(jié)點(diǎn) 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的頻數(shù)為 tfrel != null) /若左孩子非空 q.enqueue (p-l);/左孩子入隊(duì)列 if (p-r!= null)/右孩子非空 q.enqueue (p-r);/右孩子入隊(duì)列 void m

24、ain() creattree();/建立二叉樹 levelorder();/二叉樹層次遍歷 程序運(yùn)行結(jié)果參見圖 3-2。 圖 3-2 策略 2 下的作業(yè)調(diào)度方案 3 35 5 程序的優(yōu)點(diǎn)程序的優(yōu)點(diǎn) 本程序是通過二叉樹的鏈表方式存儲(chǔ)數(shù)據(jù)，計(jì)算二叉樹每個(gè)結(jié)點(diǎn)的頻數(shù)，利 用二叉樹的層次遍歷，輸出二叉樹的每個(gè)結(jié)點(diǎn)的頻數(shù)，對(duì)于較大規(guī)模的作業(yè)都能 很快地得到運(yùn)行結(jié)果。而且整個(gè)程序是基于鏈表和二叉樹這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)的， 編程風(fēng)格一致，容易理解。 第第 4 4 章章 總總 結(jié)結(jié) 通過此次課程設(shè)計(jì)，使我更加扎實(shí)的掌握了有關(guān)用層次遍歷訪問二叉樹序列 頻數(shù)的問題。我們知道，其實(shí)有很多比如像素、圖像等等都用到層次

25、遍歷來計(jì)算 它們的頻數(shù)，由此也為自己第一次踏入這門知識(shí)的領(lǐng)域而感到驕傲。 雖然在本次課程設(shè)計(jì)中，我們?cè)龅竭^種種問題。抱著對(duì)新領(lǐng)域的探索與求 知，我們一遍一遍的檢查，終于找到了問題的所在，也暴露出了前期我們?cè)谶@方 面上的知識(shí)欠缺與經(jīng)驗(yàn)不足。實(shí)踐出真知，通過自己親自動(dòng)手制作，使我們掌握 的知識(shí)不再是紙上談兵。 作為一名信息專業(yè)的學(xué)生，從最開始學(xué)習(xí)的解析幾何 、高等代數(shù) 一直到已經(jīng)即將結(jié)束的 離散數(shù)學(xué) 。我們從終于將所學(xué)習(xí)的數(shù)學(xué)知識(shí)，在計(jì) 算機(jī)上得到了應(yīng)用，我覺得有必要對(duì)這門課程設(shè)計(jì)中自己的所感進(jìn)行一次總結(jié)， 希望對(duì)初學(xué)者有一定的幫助與啟迪。 為為什什么么用用面面向向?qū)?duì)象象的的思思想想來來設(shè)設(shè)計(jì)

26、計(jì)數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu) 用面向過程的程序設(shè)計(jì)方法，來進(jìn)行數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)，學(xué)習(xí)時(shí)比較容易理解 與掌握。但它的數(shù)據(jù)一般是事先具體給定的，是為其功能函數(shù)服務(wù)的，函數(shù)起著 主導(dǎo)作用。 以函數(shù)為中心，對(duì)于函數(shù)的運(yùn)用并不方便。以排序問題為例，用于排序的函 數(shù)不少，但對(duì)于一個(gè)實(shí)際問題，究竟應(yīng)該選擇哪一種排序函數(shù)，還必須根據(jù)實(shí)際 問題的數(shù)據(jù)結(jié)構(gòu)來定。對(duì)于鏈表，你總不能選擇冒泡函數(shù)來進(jìn)行排序吧。 既然以函數(shù)為中心對(duì)于解決實(shí)際問題并不方便，那么，就只能選擇以數(shù)據(jù)為 中心，將為數(shù)據(jù)服務(wù)的函數(shù)與它綁定在一起，使這些服務(wù)于數(shù)據(jù)的函數(shù)成為數(shù)據(jù) 的一部分。這就是面向?qū)ο蟪绦蛟O(shè)計(jì)中類的概念。 致致 謝謝 到此本次課程設(shè)計(jì)終于畫上

27、了一句完美的句號(hào)，非常感謝這一次的課程設(shè)計(jì)， 使我們終于將 解析幾何 、高等代數(shù) 與離散數(shù)學(xué) 里面的知識(shí)融入到 機(jī)器上，進(jìn)行了一次綜合的運(yùn)用。 首先要感謝我的老師給我們提供了這次課程設(shè)計(jì)的機(jī)會(huì)，讓我們將平時(shí)所學(xué) 習(xí)的知識(shí)更加的系統(tǒng)化。老師給予的指導(dǎo)，提供的支持與幫助，是我們能夠完成 本次課程設(shè)計(jì)的最主要的原因。 我還要感謝和我一起奮斗不息的小組成員，我們?cè)环秩找沟囊黄鹪跈C(jī)房里 思考著，拼搏著，努力著。大家互相鼓勵(lì)，互相支持，沒有你們，也就沒有本次 課程設(shè)計(jì)的誕生。 我還要感謝給予我們幫助的網(wǎng)絡(luò)論壇上的朋友們，你們提供的寶貴意見，使 我們的程序能夠進(jìn)一步的優(yōu)化。 最后還要感謝在參考文獻(xiàn)中列出的

28、各位編者，你們所寫的書在我們課程設(shè)計(jì) 完成的道路上給過我們無數(shù)的指導(dǎo)。 這份課程設(shè)計(jì)，是我們對(duì)新領(lǐng)域的一次探索，我們已經(jīng)上路了。 參參考考文文獻(xiàn)獻(xiàn) 1 陳惠南.數(shù)據(jù)結(jié)構(gòu) .北京：清華大學(xué)出版社 ,2007. 2 茆詩松.概率論.北京：高等教育出版社 ,2004. 3 洪帆.離散數(shù)學(xué) .北京：華中科技大學(xué)出版社 .2007. 附附 錄錄 #include template class queue public: virtual bool isempty()const = 0; virtual bool isfull()const = 0; virtual bool front(t virtual

29、 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 cle

30、ar()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 return false; x = q(front +1)%maxsize; return true; template bool seqqueue:enqueue(t x)

31、if(isfull() cout full endl; return false; qrear=(rear+1)%maxsize=x; return true; template bool seqqueue:dequeue(t return false; front=(front +1)%maxsize; x=qfront; return true; #include #include #include/輸出格式控制 #include #includequeue.h #include #define n 4 struct treenode /二叉樹結(jié)點(diǎn)類定義 char *data;/結(jié)點(diǎn)符號(hào)串 char flag;/結(jié)點(diǎn)標(biāo)志符 int fre; /結(jié)點(diǎn)頻數(shù) struct treenode *l,*r; /左子女，右子女鏈域 treenode():fre(0),l(null),r(null) /構(gòu)造函數(shù)，初始化新建結(jié)點(diǎn) data=new char50; memset(data,0,50); ; treenode *proot=new treenode;/為根結(jié)點(diǎn)創(chuàng)建新結(jié)點(diǎn) void insert(treenode * current-l-fre+=1;/結(jié)點(diǎn)頻數(shù)增 1 current=current-l; /左孩子為下個(gè)新建結(jié)點(diǎn)插入的當(dāng)前結(jié)點(diǎn) else if(pnode-