中國(guó)地質(zhì)大學(xué)(武漢)信息工程學(xué)院 數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告

1、?數(shù)據(jù)結(jié)構(gòu)?課程設(shè)計(jì)學(xué)生姓名： 占 昭 班 學(xué) 號(hào)： 20211003494 指導(dǎo)教師： 吳 亮 中國(guó)地質(zhì)大學(xué)武漢信息工程學(xué)院 2021 年 11 月1.題目: nn20的階乘【問(wèn)題描述】 大數(shù)運(yùn)算計(jì)算n的階乘n=20?！靖疽蟆?1數(shù)據(jù)的表示和存儲(chǔ)； 累積運(yùn)算的中間結(jié)果和最終的計(jì)算結(jié)果的數(shù)據(jù)類(lèi)型要求是整型這是問(wèn)題本身的要求； 試設(shè)計(jì)適宜的存儲(chǔ)結(jié)構(gòu)，要求每個(gè)元素或結(jié)點(diǎn)最多存儲(chǔ)數(shù)據(jù)的3位數(shù)值。 2數(shù)據(jù)的操作及其實(shí)現(xiàn)： 基于設(shè)計(jì)的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)乘法操作，要求從鍵盤(pán)上輸入n值，在屏幕上顯示最終計(jì)算結(jié)果?！緶y(cè)試數(shù)據(jù)】 1n20，n！2432902021176640000 2n30，n！【實(shí)現(xiàn)提示】1設(shè)

2、計(jì)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)： 介于階乘運(yùn)算的精確性以及實(shí)型數(shù)據(jù)表示的不精確性，此題不能采用實(shí)型表示累積運(yùn)算的中間結(jié)果和最終的計(jì)算結(jié)果，而只能用整型。然而由于普通整型和長(zhǎng)整型所能表述數(shù)的范圍受其字長(zhǎng)的限制，不能表示大數(shù)階乘的累積結(jié)果，故必須設(shè)計(jì)一個(gè)適宜的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)對(duì)數(shù)據(jù)的存儲(chǔ)，例如可以讓每個(gè)元素或結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)的假設(shè)干位數(shù)值。 從問(wèn)題描述不難看出n值為任意值，故為使程序盡量不受限制，應(yīng)采用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)【可采用的數(shù)據(jù)結(jié)構(gòu)】 1采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)普通單鏈表，循環(huán)單鏈表，普通雙項(xiàng)鏈表和雙向循環(huán)鏈表中任選一種結(jié)構(gòu)。 2采用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)。設(shè)計(jì)思路：此題思路較為簡(jiǎn)單,將大數(shù)數(shù)存于一個(gè)數(shù)組里,每個(gè)元素存一個(gè)3位數(shù),然

3、后設(shè)計(jì)好數(shù)與數(shù)之間的乘法,已經(jīng)將數(shù)存入數(shù)組的函數(shù)即可;輸入：1n20，輸出：n！2432902021176640000輸入：2n30，輸出：n！/源碼：/ test21.cpp : Defines the entry point for the console application./#include stdafx.h#include iostreamusing namespace std;int trans(int b,int a);int mult(int *b,int l,int *c,int n);void OutPut(int b,int k);int add(int b,int

4、k);int main(int argc, char* argv)int c60;memset(c,0,60);int i(1);int L=trans(c,i);/將i存入c中int b60;memset(b,0,60);int sum(1);int k=trans(b,sum);/把sum存入b中int n;cinn;while(n-)k=mult(b,k,c,L);/sum=i*sumL=add(c,L);/i+OutPut(b,k);return 0;int trans(int b,int a)/把a(bǔ)存入b中int i=0;memset(b,0,60);while(a!=0)bi+=a

5、%1000;a=a/1000;/每三位存入數(shù)組b中return i;/b的位數(shù)3個(gè)3個(gè)的int mult(int *b,int l,int *c,int n)/l為b的長(zhǎng)度int s60;memset(s,0,60);for(int j=0;jn;j+)/cfor(int i=0;il;i+)/bsi+j+=bi*cj;/s【k】：b中第i+j位的數(shù)之和int max=n+l-1;/當(dāng)前長(zhǎng)度f(wàn)or(int i=0;imax;i+)bi=si;for (int k=0;k999)int s=bk/1000;bk%=1000;bk+1+=s;if(bmax!=0) +max;return max;

6、void OutPut(int b,int k)/輸出結(jié)果for(int i=0;ik;i+)if(i=0) cout=100) coutbk-i-1;/三位數(shù)else if(bk-i-19) cout0bk-i-1;/兩位數(shù)else cout00bk-i-1;/一位數(shù)cout999)/進(jìn)位,注意進(jìn)位后b【i】=0的情況int s=btemp/1000;btemp+%=1000;btemp+=s;+temp;return (ktemp? k:temp);/題目2:題目：表達(dá)式求值要求：實(shí)現(xiàn)關(guān)鍵棧的使用兩位數(shù)以上、負(fù)數(shù)、小數(shù)點(diǎn)？實(shí)現(xiàn)方式控制臺(tái)程序MFC對(duì)話框設(shè)計(jì)思路：參照課本上把中綴表達(dá)式改為后

7、綴表達(dá)式輸出的方法，略作改良，運(yùn)用兩個(gè)棧，一個(gè)符號(hào)棧char型，存儲(chǔ)運(yùn)算符，一個(gè)數(shù)字棧，存儲(chǔ)數(shù)字設(shè)為double型；接著解決輸入的問(wèn)題，本程序運(yùn)用了一個(gè)二維數(shù)組，以便暫時(shí)存儲(chǔ)double型數(shù)字和運(yùn)算符剛開(kāi)始二者均為char型，主要是為了方便解決浮點(diǎn)中小數(shù)點(diǎn)的輸入以及存儲(chǔ)問(wèn)題，然后取每次輸入的第一個(gè)字符，假設(shè)為數(shù)字，那么運(yùn)用atof函數(shù)將字符串轉(zhuǎn)換為浮點(diǎn)數(shù)，將其壓人數(shù)字棧中；假設(shè)為運(yùn)算符，那么根據(jù)isp函數(shù)和icp函數(shù)進(jìn)行判斷是將其壓人字符棧中還是進(jìn)行運(yùn)算從數(shù)據(jù)棧中退出2個(gè)數(shù)據(jù)，根據(jù)運(yùn)算符進(jìn)行運(yùn)算，然后將運(yùn)算結(jié)果壓人棧中；重復(fù)以上步驟，直至字符棧為空，最后取數(shù)據(jù)棧內(nèi)數(shù)據(jù)，此即為最終的運(yùn)算結(jié)果，輸

8、出即可。測(cè)試數(shù)據(jù)：*6/5=;逐個(gè)輸入字符，如下列圖輸出結(jié)果：運(yùn)行正確！源碼/r.cpp#include stdafx.h#include LinkedStack.h#include iostreamusing namespace std;int isp(char ch);int icp(char ch);int main(int argc, char* argv)char p2030;/二維數(shù)組，p【i】i20表示一個(gè)字符串cout請(qǐng)輸入要計(jì)算的算式：p0;int i(0);while(pi0!= & ip+i;cout中綴表示為：endl;for(int j=0;ji;j+)coutpj;

9、coutendl;LinkedStack s1;/char型棧，儲(chǔ)存運(yùn)算符LinkedStack s2;/double型棧，儲(chǔ)存數(shù)字char ch=;/相當(dāng)于一個(gè)輸入的終止符s1.Push(ch); char ch1,op;int k=0;while(s1.IsEmpty()=false )ch=pk0;/取輸入字符串的數(shù)字符，以便判斷它是數(shù)字還是運(yùn)算符if(isdigit(ch)/如果是數(shù)字，那么壓人double棧s2double x=atof(pk);s2.Push(x);k+;/進(jìn)入下一個(gè)字符串的判斷else/如果是運(yùn)算符s1.getTop(ch1);if(isp(ch1)icp(ch)

10、 s1.Pop(op);s2.DoOperator(op);elses1.Pop(op);if(op=() k+;double x;s2.getTop(x);cout最終結(jié)果為：xendl;return 0;int isp(char ch)if(ch=)return 0;else if(ch=() return 1;else if(ch=* | ch=/ | ch=%) return 5;else if(ch=+ |ch=-) return 3;else if(ch=) return 6;else coutch;int icp(char ch)if(ch=)return 0;else if(c

11、h=() return 6;else if(ch=* | ch=/ | ch=%) return 4;else if(ch=+ |ch=-) return 2;else if(ch=) return 1;else coutch;/注意到以上程序的輸入比擬麻煩,每輸入一個(gè)數(shù)都要換行,可做一些改良,改良后運(yùn)行如下:改良后的代碼如下:/ test12.cpp : Defines the entry point for the console application./#include stdafx.h#include iostreamusing namespace std;#include Link

12、edStack.hint isp(char ch)if(ch=)return 0;else if(ch=() return 1;else if(ch=* | ch=/ | ch=%) return 5;else if(ch=+ |ch=-) return 3;else if(ch=) return 6;else coutch;int icp(char ch)if(ch=)return 0;else if(ch=() return 6;else if(ch=* | ch=/ | ch=%) return 4;else if(ch=+ |ch=-) return 2;else if(ch=) re

13、turn 1;else coutch;int main(int argc, char* argv)char ch50;char ch1=,op;LinkedStack s1;/char型棧，儲(chǔ)存運(yùn)算符LinkedStack s2;/double型棧，儲(chǔ)存數(shù)字coutch;s1.Push(ch1);while(!s1.IsEmpty()intn=strlen(ch);/為字符時(shí)可能還要用到nif (isdigit(ch0)double x=atof(ch);s2.Push(x);int i(0);while(isdigit(chi) | chi=.)/是數(shù)字就被后面的覆蓋for(int j(0)

14、;jn;j+)chj=chj+1;n-;else/如果是運(yùn)算符s1.getTop(ch1);if(isp(ch1)icp(ch0) s1.Push(ch0);for(int j(0);jicp(ch0) s1.Pop(op);s2.DoOperator(op);elses1.Pop(op);if(op=() for(int j(0);jn;j+)chj=chj+1;n-;double x;s2.getTop(x);cout最終結(jié)果為：xLoadIcon(IDR_MAINFRAME);void CTestDlg:DoDataExchange(CDataExchange* pDX)CDialog:

15、DoDataExchange(pDX);/AFX_DATA_MAP(CTestDlg)/ NOTE: the ClassWizard will add DDX and DDV calls here/AFX_DATA_MAPBEGIN_MESSAGE_MAP(CTestDlg, CDialog)/AFX_MSG_MAP(CTestDlg)ON_WM_SYSCOMMAND()ON_WM_PAINT()ON_WM_QUERYDRAGICON()ON_BN_CLICKED(IDC_BUTTON1, OnButton1)ON_WM_CTLCOLOR()ON_BN_CLICKED(IDC_BUTTON2,

16、 OnButton2)ON_BN_CLICKED(IDC_BUTTON3, OnButton3)ON_BN_CLICKED(IDC_BUTTON4, OnButton4)ON_BN_CLICKED(IDC_BUTTON5, OnButton5)ON_BN_CLICKED(IDC_BUTTON6, OnButton6)ON_BN_CLICKED(IDC_BUTTON9, OnButton9)ON_BN_CLICKED(IDC_BUTTON8, OnButton8)ON_BN_CLICKED(IDC_BUTTON7, OnButton7)ON_BN_CLICKED(IDC_BUTTON10, On

17、Button10)ON_BN_CLICKED(IDC_BUTTON11, OnButton11)ON_BN_CLICKED(IDC_BUTTON12, OnButton12)ON_BN_CLICKED(IDC_BUTTON13, OnButton13)ON_BN_CLICKED(IDC_BUTTON14, OnButton14)ON_BN_CLICKED(IDC_BUTTON15, OnButton15)ON_BN_CLICKED(IDC_BUTTON16, OnButton16)ON_BN_CLICKED(IDC_BUTTON17, OnButton17)ON_BN_CLICKED(IDC_

18、BUTTON18, OnButton18)ON_BN_CLICKED(IDC_BUTTON19, OnButton19)/AFX_MSG_MAPEND_MESSAGE_MAP()/ CTestDlg message handlersBOOL CTestDlg:OnInitDialog()CDialog:OnInitDialog();/ Add About. menu item to system menu./ IDM_ABOUTBOX must be in the system command range.ASSERT(IDM_ABOUTBOX & 0 xFFF0) = IDM_ABOUTBO

19、X);ASSERT(IDM_ABOUTBOX AppendMenu(MF_SEPARATOR);pSysMenu-AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);/ Set the icon for this dialog. The framework does this automatically/ when the applications main window is not a dialogSetIcon(m_hIcon, TRUE);/ Set big iconSetIcon(m_hIcon, FALSE);/ Set small

20、icon/ TODO: Add extra initialization herereturn TRUE; / return TRUE unless you set the focus to a controlvoid CTestDlg:OnSysCommand(UINT nID, LPARAM lParam)if (nID & 0 xFFF0) = IDM_ABOUTBOX)CAboutDlg dlgAbout;dlgAbout.DoModal();elseCDialog:OnSysCommand(nID, lParam);/ If you add a minimize button to

21、your dialog, you will need the code below/ to draw the icon. For MFC applications using the document/view model,/ this is automatically done for you by the framework.void CTestDlg:OnPaint() if (IsIconic()CPaintDC dc(this); / device context for paintingSendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSa

22、feHdc(), 0);/ Center icon in client rectangleint cxIcon = GetSystemMetrics(SM_CXICON);int cyIcon = GetSystemMetrics(SM_CYICON);CRect rect;GetClientRect(&rect);int x = (rect.Width() - cxIcon + 1) / 2;int y = (rect.Height() - cyIcon + 1) / 2;/ Draw the icondc.DrawIcon(x, y, m_hIcon);elseCDialog:OnPain

23、t();/ The system calls this to obtain the cursor to display while the user drags/ the minimized window.HCURSOR CTestDlg:OnQueryDragIcon()return (HCURSOR) m_hIcon;/以下是我自己添加的代碼，以粗體顯示：char ch50;char ch1=,op;LinkedStack s1;/char型棧，儲(chǔ)存運(yùn)算符LinkedStack s2;/double型棧，儲(chǔ)存數(shù)字void CTestDlg:OnButton1() /777777777/ T

24、ODO: Add your control notification handler code herestrcat(ch,7);SetDlgItemText(IDC_STATIC1,ch);HBRUSH CTestDlg:OnCtlColor(CDC* pDC, CWnd* pWnd, UINT nCtlColor) HBRUSH hbr = CDialog:OnCtlColor(pDC, pWnd, nCtlColor);/ TODO: Change any attributes of the DC hereif(nCtlColor=CTLCOLOR_STATIC)pDC-SetTextC

25、olor(RGB(0,0,0);pDC-SetBkColor(RGB(247,255,246);/文字背景色HBRUSH b=CreateSolidBrush(RGB(247,255,246);/控件背景色return b;/ TODO: Return a different brush if the default is not desiredreturn hbr;void CTestDlg:OnButton2() /888888888/ TODO: Add your control notification handler code herestrcat(ch,8);SetDlgItemT

26、ext(IDC_STATIC1,ch);void CTestDlg:OnButton3() /9999999999/ TODO: Add your control notification handler code herestrcat(ch,9);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton4() /44444444444/ TODO: Add your control notification handler code herestrcat(ch,4);SetDlgItemText(IDC_STATIC1,ch);void CT

27、estDlg:OnButton5() /555555555/ TODO: Add your control notification handler code herestrcat(ch,5);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton6() /66666666/ TODO: Add your control notification handler code herestrcat(ch,6);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton9() /11111111/ T

28、ODO: Add your control notification handler code herestrcat(ch,1);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton8()/2222222222 / TODO: Add your control notification handler code herestrcat(ch,2);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton7() /333333333/ TODO: Add your control notific

29、ation handler code herestrcat(ch,3);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton10() /000000000/ TODO: Add your control notification handler code herestrcat(ch,0);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton11() /./ TODO: Add your control notification handler code herestrcat(ch,.);

30、SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton12() /+/ TODO: Add your control notification handler code herestrcat(ch,+);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton13() /- -/ TODO: Add your control notification handler code herestrcat(ch,-);SetDlgItemText(IDC_STATIC1,ch);void CTestD

31、lg:OnButton14() / */ TODO: Add your control notification handler code herestrcat(ch,*);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton15() / / TODO: Add your control notification handler code herestrcat(ch,/);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton16() /-刪掉char數(shù)組最后一個(gè)字符/ TODO: Add

32、 your control notification handler code hereint n=strlen(ch);char cht20;for (int i(0);in-1;i+)chti=chi;chti=0;strcpy(ch,cht);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnButton17() /(/ TODO: Add your control notification handler code herestrcat(ch,();SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:On

33、Button18() /)/ TODO: Add your control notification handler code herestrcat(ch,);SetDlgItemText(IDC_STATIC1,ch);int isp(char ch)if(ch=)return 0;else if(ch=() return 1;else if(ch=* | ch=/ | ch=%) return 5;else if(ch=+ |ch=-) return 3;else if(ch=) return 6;else coutch;int icp(char ch)if(ch=)return 0;el

34、se if(ch=() return 6;else if(ch=* | ch=/ | ch=%) return 4;else if(ch=+ |ch=-) return 2;else if(ch=) return 1;else coutch;void CTestDlg:OnButton19()/= / TODO: Add your control notification handler code herestrcat(ch,=);s1.Push(ch1);while(!s1.IsEmpty()intn=strlen(ch);/為字符時(shí)可能還要用到nif (isdigit(ch0)double

35、 x=atof(ch);s2.Push(x);int i(0);while(isdigit(chi) | chi=.)/是數(shù)字就被后面的覆蓋for(int j(0);jn;j+)chj=chj+1;n-;else/如果是運(yùn)算符s1.getTop(ch1);if(isp(ch1)icp(ch0) s1.Push(ch0);for(int j(0);jicp(ch0) s1.Pop(op);s2.DoOperator(op);elses1.Pop(op);if(op=() for(int j(0);jn;j+)chj=chj+1;n-;double x;s2.getTop(x);char s20;

36、sprintf(s, %f, x);strcpy(ch,s);SetDlgItemText(IDC_STATIC1,ch);void CTestDlg:OnCancel() /去除/ TODO: Add extra cleanup herestrcpy(ch,);SetDlgItemText(IDC_STATIC1,ch);/CDialog:OnCancel();/#ifndef LINKEDSTACK_H#define LINKEDSTACK_H#include iostreamusing namespace std;template class LinkedNodepublic:T dat

37、a;LinkedNode *link;LinkedNode(LinkedNode *ptr=NULL) link=ptr;LinkedNode(T d,LinkedNode *ptr=NULL) data=d;link=ptr;/每次push插入操作都在表頭進(jìn)行;template class LinkedStackprivate:LinkedNode *top;public:LinkedStack():top(NULL) /空棧，附加頭結(jié)點(diǎn)不占內(nèi)存不須newLinkedStack() makeEmpty();void makeEmpty()LinkedNode *p; while(top!=N

38、ULL)p=top;top=top-link;delete p;void Push(T x)top=new LinkedNode(x,top);if(top=NULL) cerr 存儲(chǔ)分配失敗！endl;bool Pop(T& x)if(IsEmpty()=true) return false;LinkedNode *p=top;x=p-data;top=top-link;delete p;return true;bool IsEmpty()const return top=NULL?true:false;bool getTop(T &x)if(top=NULL) return false;x

39、=top-data;return true;/void DoOperator(char op)/一op為運(yùn)算符計(jì)算，并將結(jié)果壓棧double left,right,value;int result;result=get2Operands(left,right);if(result=true)switch(op)case +:value=left+right;Push(value);break;case -:value=left-right;Push(value);break;case *:value=left*right;Push(value);break;case /:if(right=0.

40、0)cerrDivide by 0!endl;Clear();else value=left/right;Push(value);break;elseClear();void Clear()makeEmpty();bool get2Operands(double &left,double &right)/取左右操作數(shù)if(IsEmpty()=true)cerr缺少右操作數(shù)endl;return false;Pop(right);if(IsEmpty()=true)cerr缺少左操作數(shù)endl;return false;Pop(left);return true;void AddOperand(

41、double value)/將結(jié)果壓棧Push(value);#endif/3.題目:題目：二叉樹(shù)根本算法的實(shí)現(xiàn)功能要求：鍵盤(pán)輸入二叉樹(shù)結(jié)點(diǎn)序列，創(chuàng)立一棵二叉樹(shù)實(shí)現(xiàn)SwapTree方法，以根結(jié)點(diǎn)為參數(shù)，交換每個(gè)結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)提示：前序遞歸實(shí)現(xiàn)Find方法，查找值為key的結(jié)點(diǎn)，并輸出該結(jié)點(diǎn)的所有祖先結(jié)點(diǎn) 你可以選擇： 對(duì)BinaryTree模板進(jìn)行功能擴(kuò)充； 自己定義并實(shí)現(xiàn)二叉樹(shù)類(lèi)要求鍵盤(pán)輸入二叉樹(shù)結(jié)點(diǎn)序列 結(jié)點(diǎn)序列可以是前序，也可以是層次 空結(jié)點(diǎn)以#表示設(shè)計(jì)思路：首先，運(yùn)用遞歸的方法，按前序輸入建立一棵二叉樹(shù)，接著，運(yùn)用類(lèi)似交換兩變量值的方法，交換根結(jié)點(diǎn)的左右子樹(shù)，實(shí)現(xiàn)SwapTree

42、方法；然后，通過(guò)前序遍歷，找到值為key的結(jié)點(diǎn)，并實(shí)現(xiàn)parent函數(shù)，用到一個(gè)棧，實(shí)現(xiàn)parent結(jié)點(diǎn)的逆序輸出，即可輸出該節(jié)點(diǎn)的所有祖先結(jié)點(diǎn)。前序輸入：abdk#e#cf#g#交換前輸出：abdkecfg交換后輸出：acfgbdke測(cè)試程序如下：/.cpp#include stdafx.h#include BinaryTree.h#include iostreamusing namespace std;template void CreateBinTree(BinTreeNode *& subTree)/鍵盤(pán)輸入二叉樹(shù)結(jié)點(diǎn)序列，創(chuàng)立一棵二叉樹(shù)T item;cinitem;if(item!=

43、#)subTree=new BinTreeNode(item);CreateBinTree(subTree-leftChild);CreateBinTree(subTree-rightChild);template void SwapTree(BinTreeNode *& subTree)/SwapTree方法BinTreeNode* t;t=subTree-rightChild;subTree-rightChild=subTree-leftChild;subTree-leftChild=t;int main(int argc, char* argv)BinaryTree b;cout前序建立

44、一棵二叉樹(shù)：endl;CreateBinTree(b.root);/用前序遍歷建立二叉樹(shù)cout前序輸出：;b.preOrder();coutendl;SwapTree(b.root);/交換左右子樹(shù)cout交換后前序輸出：;b.preOrder();/交換后再輸出一遍，便于檢驗(yàn)是否有誤coutendl;coutch;coutch的祖先節(jié)點(diǎn)：;b.Find(b.root,ch);coutendl;return 0;/源碼：#ifndef BINARYTREE_H#define BINARYTREE_H#include iostream#include LinkedStack.husing na

45、mespace std;template class BinTreeNodepublic:T data;BinTreeNode *leftChild,*rightChild;BinTreeNode(T d,BinTreeNode *l=NULL,BinTreeNode *r=NULL):data(d),leftChild(l),rightChild(r);template class BinaryTreeprotected:T RefValue;public:BinTreeNode *root;BinaryTree():root(NULL)BinaryTree(T value):RefValu

46、e(value),root(NULL)BinaryTree() destroyTree(root);void preOrder() preOrder(root);bool IsEmpty() return root=NULL? false:true;void visit(BinTreeNode *subTree)coutdata ;private:void preOrder(BinTreeNode *subTree)if(subTree!=NULL)coutdataleftChild);preOrder(subTree-rightChild);void destroyTree(BinTreeN

47、ode *subTree)if(subTree!=NULL)destroyTree(subTree-leftChild);destroyTree(subTree-rightChild);delete subTree;public:/求父親節(jié)點(diǎn)BinTreeNode* parent(BinTreeNode* subTree)LinkedStackBinTreeNode* s;BinTreeNode* q=root;s.Push(NULL);while(q!=NULL)if(q-leftChild=subTree | q-rightChild=subTree)coutdatarightChild!

48、=NULL)s.Push(q-rightChild);if(q-leftChild!=NULL)q=q-leftChild;elses.Pop(q);cout輸出不成功！endl;return NULL;/找keyvoid Find(BinTreeNode* subTree,const T& key)/用類(lèi)似后序遍歷的方法找到值為key的結(jié)點(diǎn)LinkedStackBinTreeNode* s;BinTreeNode*p=subTree;s.Push(NULL);while(p!=NULL)if(p-data=key)/cout查找成功！rightChild!=NULL)s.Push(p-rig

49、htChild);if(p-leftChild!=NULL)p=p-leftChild;elses.Pop(p);while(p!=root)p=parent(p);#endif/4.任務(wù)：輸入一棵二叉樹(shù)的前序遍歷序列和中序遍歷序列，重構(gòu)這棵二叉樹(shù) 功能要求： 在題目一的根底之上，增加一個(gè)方法，重構(gòu)這棵二叉樹(shù) 要求以圖示效果，層次輸出這棵二叉樹(shù)設(shè)計(jì)思路：題目要求在題目一的根底上增加一個(gè)方法,重構(gòu)二叉樹(shù),可以輸入二叉樹(shù)的后序遍歷和中序遍歷,然后根據(jù)后序和中序序列建立二叉樹(shù)。最后，用到一個(gè)隊(duì)列，層次輸出此二叉樹(shù)。后序輸入：DBFCA輸出：BDACF層次輸出：ABCDF測(cè)試程序如下：#include

50、 stdafx.h#include BinaryTree.hint main(int argc, char* argv)char ch120,ch220;cout請(qǐng)輸入后序遍歷：ch1;cout請(qǐng)輸入中序中序：ch2;cout建立此樹(shù)：endl;BinaryTree B;int n=strlen(ch1);B.CreateTree(B.root,ch1,ch2,n);cout前序輸出：endl;B.preOrder();coutendl中序輸出：endl;B.InOrder(B.root);coutendl;cout層次輸出：;B.levelOrder();coutendl;return 0;

51、/#ifndef BINARYTREE_H#define BINARYTREE_H#include iostream#include LinkedQueue.husing namespace std;template class BinTreeNodepublic:T data;BinTreeNode *leftChild,*rightChild;/BinTreeNode():leftChild(NULL),rightChild(NULL)BinTreeNode(T d,BinTreeNode *l=NULL,BinTreeNode *r=NULL):data(d),leftChild(l),

52、rightChild(r);template class BinaryTreeprotected:T RefValue;public:BinTreeNode *root;BinaryTree():root(NULL)BinaryTree(T value):RefValue(value),root(NULL)BinaryTree() destroyTree(root);void preOrder() preOrder(root);bool IsEmpty() return root=NULL? false:true;private:void preOrder(BinTreeNode *subTr

53、ee)if(subTree!=NULL)coutdataleftChild);preOrder(subTree-rightChild);void destroyTree(BinTreeNode *subTree)if(subTree!=NULL)destroyTree(subTree-leftChild);destroyTree(subTree-rightChild);delete subTree;public:int Index(T key,T *y)/返回key在中序數(shù)組y中的下標(biāo)int n=strlen(y);for(int j=0;jn;j+)if(yj=key)return j;co

54、ut查無(wú)此值！endl;/增加此句，方便調(diào)試return 0;void InOrder(BinTreeNode*p)/中序輸出if(p!=NULL)InOrder(p-leftChild);coutdatarightChild);void levelOrder()LinkedQueueBinTreeNode* q;BinTreeNode*p=root;q.EnQueue(p);while(q.IsEmpty()=false)q.DeQueue(p);coutdataleftChild!=NULL)q.EnQueue(p-leftChild);if(p-rightChild!=NULL)q.En

55、Queue(p-rightChild);void Insert(BinTreeNode *&p,T* x,T* y,int i)/把x【i】插入樹(shù)中類(lèi)似二叉樹(shù)的插入)if(p=NULL)p=new BinTreeNode(xi);elseif(Index(xi,y)data,y) )Insert(p-leftChild,x,y,i);elseInsert(p-rightChild,x,y,i);void CreateTree(BinTreeNode *&p,T* x,T* y,int n)/n為后序數(shù)組長(zhǎng)度f(wàn)or(int i=n-1;i=0;i-)Insert(p,x,y,i);#endif5

56、./最優(yōu)二叉樹(shù)根本要求：對(duì)Huffman樹(shù)的方法進(jìn)行擴(kuò)充，實(shí)現(xiàn)如下功能：1鍵盤(pán)輸入一個(gè)字符串，統(tǒng)計(jì)每個(gè)字符出現(xiàn)的頻率；2輸出每個(gè)字符的Huffman編碼3計(jì)算并輸出WPL提高要求：改鍵盤(pán)輸入為讀文件任何類(lèi)型設(shè)計(jì)思路:1.先建一個(gè)鏈表：輸入一段字符串，將其放入鏈表中，刪除重復(fù)節(jié)點(diǎn)data相同并統(tǒng)計(jì)各個(gè)節(jié)點(diǎn)頻率存入count中，將鏈表按各節(jié)點(diǎn)count的大小排序按小到大順序；2.建huffman樹(shù)：(1).將鏈表前兩元素合并，建成一顆小樹(shù)小樹(shù)中，令左節(jié)點(diǎn)code=0，右節(jié)點(diǎn)code=1，刪去表中前兩元素，將小樹(shù)根節(jié)點(diǎn)插入鏈表中按count大小順序 (2).循環(huán)操作1，直至表中只剩下一個(gè)節(jié)點(diǎn)3.輸出

57、編碼：根據(jù)parent指針找到節(jié)點(diǎn)的祖先節(jié)點(diǎn)，然后逆序輸出其code值，此即為節(jié)點(diǎn)的編碼4.求WPL：根據(jù)parent指針求節(jié)點(diǎn)的深度h，然后每個(gè)節(jié)點(diǎn)的h+1之和除以節(jié)點(diǎn)數(shù)即為該樹(shù)的成功搜索長(zhǎng)度/源碼/源碼/源碼/源碼/源碼/源碼/源碼/源碼#include stdafx.h#include iostream#include HuffmanTree.husing namespace std;int main(int argc, char* argv)char ch30;coutch;HuffmanTree H;H.InputHuffmanTree(ch);H.Count();H.Sort();

58、H.Frequency();H.Output();H.Build();H.levelOrder();H.levelOrder1();H.WPL();return 0;/*#ifndef HUFFMANTREE_H#define HUFFMANTREE_H#include LinkedQueue.h#include LinkedStack.htemplatestruct NodeT data;/字符float count;/頻率bool code;/編碼Node *leftChild,*rightChild,*parent;/Node(Node* l=NULL,Node* r=NULL,Node

59、* ptr=NULL):leftChild(l),rightChild(r),parent(ptr)Node(T d,float cnt=1.0,bool co=0,Node* l=NULL,Node* r=NULL,Node* ptr=NULL):data(d),count(cnt),code(co),leftChild(l),rightChild(r),parent(ptr);template class HuffmanTreepublic:HuffmanTree()root=new Node(#);HuffmanTree() makeEmpty(root);/前插法建立鏈表/前插法建立鏈

60、表/前插法建立鏈表(尚未對(duì)其排序)void InputHuffmanTree(T *ch)int i(0),n=strlen(ch);while(in)Node *newNode=new Node(chi);if(newNode=NULL) cerr存儲(chǔ)分配有誤！parent=root-parent;root-parent=newNode;i+;/統(tǒng)計(jì)各節(jié)點(diǎn)的code值/統(tǒng)計(jì)各節(jié)點(diǎn)的code值/統(tǒng)計(jì)各節(jié)點(diǎn)的code值中下一步就是根據(jù)code大小進(jìn)行排序void Count()Node*p=root-parent,*q=NULL;while(p!=NULL)q=p-parent;while(q!