數(shù)據(jù)結(jié)構(gòu)實習(xí)題目

1、n n（n>20）的階乘n 【問題描述】n 大數(shù)運算計算n的階乘（n>=20）。n 【基本要求】n （1）數(shù)據(jù)的表示和存儲；n （1.1） 累積運算的中間結(jié)果和最終的計算結(jié)果的數(shù)據(jù)類型要求是整型這是問題本身的要求；n （1.2） 試設(shè)計合適的存儲結(jié)構(gòu)，要求每個元素或結(jié)點最多存儲數(shù)據(jù)的3位數(shù)值。 n （2）數(shù)據(jù)的操作及其實現(xiàn)：n 基于設(shè)計的存儲結(jié)構(gòu)實現(xiàn)乘法操作，要求從鍵盤上輸入n值，在屏幕上顯示最終計算結(jié)果。n 【測試數(shù)據(jù)】n （1）n20，n！2432902008176640000n （2）n30，n！265252859812191058636308480000000n #incl

2、ude "stdafx.h"n #include <iostream>n #include<iomanip>n using namespace std;n template <class T>n class Chain;n template <class T>n class ChainNoden n friend Chain<T>n private:n T data;n ChainNode<T> *link;n ;n template<class T>n class Chainn n pub

3、lic:n Chain() first = 0;/構(gòu)造函數(shù)n Chain();/析構(gòu)函數(shù)n bool IsEmpty() const return first = 0;/判斷鏈表是否為空n int Length() const;/求鏈表的長度n bool Find(int k, T& x) const;/查找第k個元素n int Search(const T& x) const;/查找元素xn Chain<T>& Delete(int k, T& x);/刪除第k個元素n Chain<T>& Insert(int k, const

4、 T& x);/在第k個元素之后插入xn void Output(ostream& out) const;/單鏈表的輸出n Chain<T>& Fac(long n);n /求大數(shù)階乘n private:n ChainNode<T> *first;/ 指向第一個節(jié)點n ;nn template<class T>n Chain<T>:Chain()n /刪除所有的節(jié)點n ChainNode<T> *next; n while (first) n n next = first->link;n delete f

5、irst;n first = next;n n n template<class T>n bool Chain<T>:Find(int k, T& x) constn / 查找第k個元素，并賦值給xn if (k < 1) return false;n ChainNode<T> *current = first;n int index = 1; n while (index < k && current)n n current = current->link;n index+;n n if (current)n n

6、x = current->data;n return true;n n return false; n nn template<class T>n int Chain<T>:Search(const T& x) constn /查找元素x，返回該元素的下標(biāo)n ChainNode<T> *current = first;n int index = 1; n while (current && current->data != x) n n current = current->link;n index+;n n if

7、(current) return index;n return 0;n nn template<class T>n Chain<T>& Chain<T>:Delete(int k, T& x)n / 刪除第k個元素，并賦值給x，返回改變后的鏈表n ChainNode<T> *p = first;n if (k = 1) n first = first->link; n elsen n ChainNode<T> *q = first;n for (int index = 1; index < k - 1 &a

8、mp;& q;index+)n q = q->link;n p = q->link; n q->link = p->link;n n x = p->data;n delete p;n return *this;n n template<class T>n int Chain<T>:Length() const / 返回鏈表的長度n n ChainNode<T> *current = first;n int len = 0;n while (current) n n len+;n current = current->

9、;link;n n return len;n n template<class T>n Chain<T>& Chain<T>:Insert(int k, const T& x) /在第k個元素之后插入x，返回插入后的鏈表n n ChainNode<T> *p = first;n for (int index = 1; index < k && p;index+) n p = p->link;n ChainNode<T> *y = new ChainNode<T>n y->d

10、ata = x;n if (k) n n y->link = p->link;n p->link = y;n n else n n y->link = first;n first = y;n n return *this;n n template<class T>n void Chain<T>:Output(ostream& out) const / 輸出鏈表元素n n ChainNode<T> *current;n int i=0,j=Length();n for (current = first; current;curr

11、ent = current->link)n n i+;n if(i=j&&j>=1)n n if(current->link)n out <<setw(3)<<setfill('0')<< current->data << " "n else n out<< current->data << " "n i=1;n j-;n current=first;n n n out<<setw(3)<<setf

12、ill('0')<<first->data<<" "n n template <class T> /重載運算符<<n ostream& operator<<(ostream& out, const Chain<T>& x)n x.Output(out); return out;nn template <class T>n Chain<T>& Chain<T>:Fac(long n) /初始化n n n int i=

13、0;n long j=n;n while(j>999)n n Insert(i,j%1000);n i+;n j=j/1000;n n Insert(i,j); /通過插入來建立鏈表(0,20)n /計算n long m=0, k=0;n ChainNode<T> *current;n for(;n>2;n-)n n for (current = first;current;current = current->link)/?n n m=k;n k=(current->data*(n-1)+k)/1000; /向前進位n current->data=(

14、current->data*(n-1)+m)%1000;n if(!current->link&&k>0) /?n n while(k>999)n n Insert(Length(),k%1000);n k=k/1000;n n Insert(Length(),k); /鏈表長度加一n k=0;n break;n n n n return *this;n n int main()n n long n;n char ch;n don n cout<<"請輸入需要階乘的數(shù)字n: "n cin>>n;n Chain&

15、lt;long> a;n a.Fac(n);n cout<<n<<"的階乘為:"<<endl;n cout<<a;n cout<<endl;n cout<<"是否進行計算:"n cout<<endl;nn cin>>ch;n while(ch='Y');n return 0;n 2:題目：表達式求值v 要求：實現(xiàn)關(guān)鍵§ 棧的使用§ 兩位數(shù)以上、負(fù)數(shù)、小數(shù)點？v 實現(xiàn)方式§ 控制臺程序§ MFC對話框

16、#include "stdafx.h"#include <iostream>using namespace std;#include<assert.h>#include <cstdlib>#include <math.h>template<class T>class Stackpublic:Stack(int sz=50);Stack()deleteelements;void Push(const T &x); /壓入棧bool Pop(T&x);/彈出棧T GetTop(void)const;/取

17、棧頂元素bool IsEmpty()constreturn(top=-1)?true:false;bool IsFull()/判斷棧是否滿return (top=MaxSize-1)?true:false;int GetSize()const/?return top+1;void MakeEmpty()top=-1;private:T *elements;int top;int MaxSize;void overflowProcess();/棧溢出處理;template<class T>Stack<T>:Stack(int sz)top=-1;MaxSize=sz;el

18、ements=new TMaxSize;/創(chuàng)建棧的數(shù)組空間assert(elements!=NULL);/判斷動態(tài)內(nèi)存是否分配成功是否template<class T>void Stack<T>:Push(const T&x)if(IsFull()=true)overflowProcess();top+;elementstop=x;template<class T>bool Stack<T>:Pop(T&x)if(IsEmpty()=true)return false;x=elementstop-;return true;temp

19、late<class T>T Stack<T>:GetTop(void)const/返回棧頂元素if(IsEmpty()=true)cerr<<"棧為空!"<<endl;exit(1);return elementstop;template<class T>void Stack<T>:overflowProcess() /溢出處理T *newArray=new T2*MaxSize; /擴充棧的空間for(int i=0;i<=top;i+)MaxSize=2*MaxSize;newArrayi=

20、elementsi;deleteelements;/釋放原來舊的空間class Calculater/計算的聲明public:Calculater()void Run();/執(zhí)行表達式計算void Clear();/清空處理private:Stack<double>s;/聲明double型的棧對象void AddOperand(double value);/把數(shù)值壓入棧中bool GetOperand(double &left,double& right);/判斷取操作數(shù)操作是否成功void DoOperator(char ch);/進行操作;void Calcul

21、ater:AddOperand(double value)s.Push(value);bool Calculater:GetOperand(double&left,double&right)if(s.IsEmpty()=true)cerr<<"缺少右操作數(shù)"<<endl;return false;s.Pop(right);if(s.IsEmpty()=true)cerr<<"缺少左操作數(shù)"<<endl;return false;s.Pop(left);return true;void Cal

22、culater:Clear()s.MakeEmpty();void Calculater:DoOperator(char ch)double left,right,value;bool result;result=GetOperand(left,right);if(result=true)switch(ch)case'+':value=left+right;s.Push(value);break;case'-':value=left-right;s.Push(value);break;case'*':value=left*right;s.Push

23、(value);break;case'/':if(right=0.0)cerr<<"Divide by 0!"<<endl;Clear();elsevalue=left/right;s.Push(value);break;cout<<"="<<s.GetTop()<<" "else Clear();void Calculater:Run()char ch;double newOperand;while(cin>>ch,ch!='#'

24、)switch(ch) case '+':case'-':case'*':case'/':/是操作數(shù)，執(zhí)行計算DoOperator(ch);break;default: /其實也是一種case，只不過就是指“除了指定的幾個case以外的其他情況”，不是操作符cin.putback(ch);/字符放回輸入流cin>>newOperand;/重新讀取操作數(shù)，一個操作數(shù)的第一個字符AddOperand(newOperand);/將操作數(shù)放入棧中int main()Calculater call;cout<<&qu

25、ot;輸入計算表達式:"call.Run();return 0;3.題目:v 題目：二叉樹基本算法的實現(xiàn)v 功能要求：v 鍵盤輸入二叉樹結(jié)點序列，創(chuàng)建一棵二叉樹v 實現(xiàn)SwapTree方法，以根結(jié)點為參數(shù)，交換每個結(jié)點的左子樹和右子樹（提示：前序遞歸）v 實現(xiàn)Find方法，查找值為key的結(jié)點，并輸出該結(jié)點的所有祖先結(jié)點v 你可以選擇：v 對BinaryTree模板進行功能擴充；v 自己定義并實現(xiàn)二叉樹類v 要求鍵盤輸入二叉樹結(jié)點序列v 結(jié)點序列可以是前序，也可以是層次v 空結(jié)點以#表示 /binarytree.h#ifndef BINARYTREE_H#define BINARYT

26、REE_H#include<iostream.h>template<class T>class BinaryTreeNode/二叉樹結(jié)點/friend BinaryTree<T>public:BinaryTreeNode()LeftChild=RightChild=0;BinaryTreeNode(const T&e)data=e;LeftChild=RightChild=0;BinaryTreeNode(const T&e,BinaryTreeNode *l,BinaryTreeNode *r)data=e;LeftChild=l;Righ

27、tChild=r;public:T data;BinaryTreeNode<T>*LeftChild,*RightChild;template<class T>class BinaryTreefriend BinaryTreeNode<T>public:BinaryTree()root=0;BinaryTree()bool IsEmpty()constreturn (root)?false:true);void Creat();void PreOrder(void (*Visit)(BinaryTreeNode<T>*u)/前序遍歷 PreOrd

28、er(Visit,root);void InOrder(void (*Visit)(BinaryTreeNode<T>*u)/中序遍歷InOrder(Visit,root);void PostOrder(void (*Visit)(BinaryTreeNode<T>*u)/后序遍歷PostOrder(Visit,root);void LevelOrder(void(*Visit)(BinaryTreeNode<T>*u)/層次遍歷 PreOrder(Output,root); cout<<endl;void InOutput()/中序輸出InOr

29、der(Output,root); cout<<endl;void Postput()/后序輸出 PostOrder(Output,root); cout<<endl;void LevelOutPut()/層次輸出LevelOrder(Output);cout<<endl;int Height()const/計算樹的高度return Height(root);int Size()const/計算樹的大小return Size(root);BinaryTreeNode<T>*iCreat();void swap()/交換左右節(jié)點swap(root)

30、;int leave()/計算葉子節(jié)點個數(shù)return leave(root);int noleave()/計算非葉子節(jié)點個數(shù)return noleave(root);private:BinaryTreeNode<T>*root;void PreOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);void InOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);void PostOrder(voi

31、d(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);/void LevelOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);static void Output(BinaryTreeNode<T>* t)/輸出樹的所有節(jié)點cout<<t->data <<" "int Height(BinaryTreeNode<T>*t)const;int Size(B

32、inaryTreeNode<T>*t)const; void swap(BinaryTreeNode<T>*t);int leave(BinaryTreeNode<T>*t);int noleave(BinaryTreeNode<T>*t);template<class T>int BinaryTree<T>:Height(BinaryTreeNode<T>*t)constif(!t) return 0;int hl=Height(t->LeftChild);int hr=Height(t->Rig

33、htChild);if(hl>hr) return +hl;else return +hr;template<class T>int BinaryTree<T>:Size(BinaryTreeNode<T>*t)const if(!t) return 0; int sl=Size(t->LeftChild); int sr=Size(t->RightChild); return (1+sl+sr);template<class T>BinaryTreeNode<T>*BinaryTree<T>:iCrea

34、t( ) T ch;cin>>ch;BinaryTreeNode<T> * root;if(ch='#') root=NULL;elseroot=new BinaryTreeNode<T>root->data=ch;root->LeftChild=this->iCreat();root->RightChild=this->iCreat();return root; template<class T>void BinaryTree<T>:Creat() this->root = iCr

35、eat();template<class T>void BinaryTree<T>:PreOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t)if(t) Visit(t);PreOrder(Visit,t->LeftChild);PreOrder(Visit,t->RightChild);template<class T> void BinaryTree<T>:InOrder(void(*Visit)(BinaryTreeNode<T&g

36、t;*u),BinaryTreeNode<T>*t)if(t)InOrder(Visit,t->LeftChild);Visit(t);InOrder(Visit,t->RightChild);template<class T>void BinaryTree<T>:PostOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t)if(t)PostOrder(Visit,t->LeftChild);PostOrder(Visit,t->RightCh

37、ild);Visit(t);template<class T>void BinaryTree<T>:swap(BinaryTreeNode<T> *t)BinaryTreeNode<T> *temp;if(!t) return;elsetemp=t->LeftChild;t->LeftChild=t->RightChild;t->RightChild=temp;swap(t->LeftChild);swap(t->RightChild);template<class T>int BinaryTree

38、<T>:leave(BinaryTreeNode<T>*t)if(!t) return 0;if(t->LeftChild=0&&t->RightChild=0)return 1;int leafl=leave(t->LeftChild);int leafr=leave(t->RightChild); return leafl+leafr;template<class T>int BinaryTree<T>:noleave(BinaryTreeNode<T> *t)if(!t) return 0

39、;if(!t->LeftChild&&!t->RightChild)return 1;int leafl=noleave(t->LeftChild);int leafr=noleave(t->RightChild);return leafl+leafr+1;#endif #include "stdafx.h"#include"binarytree.h"#include <iostream.h>void main() cout<<"輸入二叉樹:"<<endl;B

40、inaryTree<char> Tree;Tree.Creat();/cout<<"前序遍歷:"/Tree.PreOutput();cout<<"中序遍歷:"Tree.InOutput();cout<<"后序遍歷:"Tree.Postput();cout<<"二叉樹的葉節(jié)點數(shù)目為:"cout<<Tree.leave()<<endl;Tree.swap();cout<<"交換前序遍歷:"/Tree.Pr

41、eOutput();實習(xí)題目4.v 任務(wù)：輸入一棵二叉樹的前序遍歷序列和中序遍歷序列，重構(gòu)這棵二叉樹v 功能要求：Ø 在題目三的基礎(chǔ)之上，增加一個方法，重構(gòu)這棵二叉樹Ø 要求以圖示效果，層次輸出這棵二叉樹/bintree.h #ifndef BINTREE_H#define BINTREE_H#include<iostream.h>#include"queue.h"template<class T>class BinaryTree;template<class T>/二叉樹的二叉鏈表class BinaryTreeNo

42、defriend BinaryTree<T>public:BinaryTreeNode()LeftChild=RightChild=0;/構(gòu)造函數(shù)BinaryTreeNode(const T&e)data=e;LeftChild=RightChild=0;BinaryTreeNode(const T&e,BinaryTreeNode *l,BinaryTreeNode *r)data=e;LeftChild=l;RightChild=r;private:T data;BinaryTreeNode<T>*LeftChild,*RightChild;temp

43、late<class T>class BinaryTreepublic:BinaryTree()/構(gòu)造函數(shù) 空樹root=0;BinaryTree()bool IsEmpty()constreturn (root)?false:true);/void BinaryTree<T>:LevelOrder(void(* Visit)(BinaryTreeNode<T>*u);void LevelOrder(void(BinaryTree<T>:* Visit)(BinaryTreeNode<T>*u);/層次訪問,在訪問某一層結(jié)點時把下一層

44、結(jié)點記憶在隊列（尾）中，然后在訪問在隊頭的結(jié)點void LevelOutPut()if(!root)/空樹return;cout<<root->data;LevelOrder(Output);cout<<endl;BinaryTreeNode<T>*createBinaryTree(T *VLR,T*LVR,int n)/構(gòu)造二叉樹前 中 n為元素個數(shù)if(n=0)return NULL;int k=0;while(VLR0!=LVRk)/在中序前序結(jié)合找根k+;BinaryTreeNode<T>*t=new BinaryTreeNode&

45、lt;T>(VLR0);/根結(jié)點為tt->LeftChild=createBinaryTree(VLR+1,LVR,k);/從前序VLR+1開始對中序0k-1左子序列的k個元素遞歸建立左子樹t->RightChild=createBinaryTree(VLR+k+1,LVR+k+1,n-k-1);/從前序VLR+k+1開始對中序k+1n-1左子序列的n-k-1個元素遞歸建立右子樹return t; BinaryTreeNode<T>*root;void Output(BinaryTreeNode<T>* t)if(t->LeftChild|t-&

46、gt;RightChild)/左或又子樹不為空if(t->LeftChild)cout<<t->LeftChild->data;elsecout<<"#"if(t->RightChild)cout<<t->RightChild->data;elsecout<<"#"template<class T>void BinaryTree<T>:LevelOrder(void (BinaryTree<T>:*Visit)(BinaryTreeNo

47、de<T> *u)/void BinaryTree<T>:LevelOrder(void(* Visit)(BinaryTreeNode<T>*u)LinkedQueue<BinaryTreeNode<T>*>Q;BinaryTreeNode<T> *p=root;Q.EnQueue(p);/根節(jié)點進隊while(!Q.IsEmpty ()Q.DeQueue(p);/根節(jié)點出隊(this->*Visit)(p);/訪問根結(jié)點if(p->LeftChild!=NULL)Q.EnQueue(p->LeftCh

48、ild);/左子女進隊if(p->RightChild!=NULL)Q.EnQueue(p->RightChild); /右子女進隊#endif/queqe.h#ifndef QUEQE_H#define QUEQE_H/單鏈表的鏈?zhǔn)疥犃衪emplate<class T>class LinkedQueue;template<class T>class Nodefriend LinkedQueue<T>private:T data;Node<T>*link;template<class T>class LinkedQueue

49、 public:LinkedQueue()/構(gòu)造函數(shù)front=rear=0;/建立空隊列LinkedQueue();/析構(gòu)函數(shù)bool IsEmpty()constreturn (front)?false:true);LinkedQueue<T>&EnQueue(const T &x);/往隊尾隊列中插入元素LinkedQueue<T>&DeQueue(T&x);/從隊頭刪除元素private:Node<T>*front;Node<T>*rear;template<class T>LinkedQueu

50、e<T>:LinkedQueue()/析構(gòu)函數(shù)的實現(xiàn)Node<T>*next;while(front)next=front->link;delete front;front=next;template<class T>LinkedQueue<T>&LinkedQueue<T>:EnQueue(const T &x)Node<T>*p=new Node<T>p->data=x;p->link=0; if (front) rear->link=p;/在列尾添加新的結(jié)點 els

51、e/隊列為空，新結(jié)點成為第一個結(jié)點 front=p;rear=p;return *this;template<class T>LinkedQueue<T>&LinkedQueue<T>:DeQueue( T&x)/隊頭結(jié)點刪去Node<T>*p=front;/暫存隊頭結(jié)點x=front->data;front=front->link;/隊頭修改delete p;return*this;#endif#include "stdafx.h"#include"binarytree.h"#

52、include <iostream.h>void main()BinaryTree<char> Tree;/char 類型的int n;cout<<"二叉樹中元素個數(shù):"cin>>n;char *L=new charn; char *R=new charn;cout<<"前序序列為:"int i=0,j=0;while(i<n)cin>>Li;i+;cout<<"中序序列為:"while(j<n)cin>>Rj;j+;Tree.

53、root=Tree.createBinaryTree(L,R,n); cout<<"層次遍歷:"Tree.LevelOutPut();deleteL;deleteR;實習(xí)題目5.最優(yōu)二叉樹v 基本要求：對Huffman樹的方法進行擴充，實現(xiàn)如下功能：v 1）鍵盤輸入一個字符串，統(tǒng)計每個字符出現(xiàn)的頻率；v 2）輸出每個字符的Huffman編碼v 3）計算并輸出WPLv 提高要求：改鍵盤輸入為讀文件（任何類型）/huffmantree.h#ifndef HUFFMANTREE_H#define HUFFMANTREE_H#include <iostream.h>#include "minheap.h"#include <stdlib.h>/const int MaxN = 100;template <class Type> class HuffmanTree;template <class Type> class HuffmanTreeNode/樹結(jié)點的類定義 /friend class HuffmanTree; public: i