大數(shù)階乘數(shù)據(jù)結(jié)構(gòu)算法課程設(shè)計(jì) - 副本

1、實(shí)習(xí)題目一線性表及其應(yīng)用【問(wèn)題描述】 大數(shù)運(yùn)算計(jì)算n的階乘（n=20）。【基本要求】（1）數(shù)據(jù)的表示和存儲(chǔ)；） 累積運(yùn)算的中間結(jié)果和最終的計(jì)算結(jié)果的數(shù)據(jù)類型要求是整型這是問(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)乘法操作，要求從鍵盤上輸入n值，在屏幕上顯示最終計(jì)算結(jié)果。【實(shí)現(xiàn)提示】（1）設(shè)計(jì)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)： 介于階乘運(yùn)算的精確性以及實(shí)型數(shù)據(jù)表示的不精確性，本題不能采用實(shí)型表示累積運(yùn)算的中間結(jié)果和最終的計(jì)算結(jié)果，而只能用整型。然而由于普通整型和長(zhǎng)整型所能表述數(shù)的范圍受其字長(zhǎng)的限制，不能表示大數(shù)階乘的累積

2、結(jié)果，故必須設(shè)計(jì)一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)對(duì)數(shù)據(jù)的存儲(chǔ)，例如可以讓每個(gè)元素或節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)的若干位數(shù)值。 從問(wèn)題描述不難看出n值為任意值，故為使程序盡量不受限制，應(yīng)采用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。（2） 數(shù)據(jù)的操作及其實(shí)現(xiàn)：）累積運(yùn)算的特點(diǎn)是當(dāng)前的計(jì)算結(jié)果是下次乘法運(yùn)算的乘數(shù)； （）實(shí)現(xiàn)兩個(gè)數(shù)的乘法運(yùn)算須考慮： （1）乘數(shù)的各位數(shù)都要與被乘數(shù)進(jìn)行乘法運(yùn)算； （2）乘法過(guò)程中的進(jìn)位問(wèn)題及其實(shí)現(xiàn)； （3）因每個(gè)元素或節(jié)點(diǎn)最多存儲(chǔ)數(shù)據(jù)的3位數(shù)值，故當(dāng)元素或節(jié)點(diǎn)中的數(shù)值大于999，需向前一個(gè)元素或節(jié)點(diǎn)進(jìn)位。 【實(shí)現(xiàn)結(jié)構(gòu)】（1）采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)（普通單鏈表，循環(huán)單鏈表，普通雙項(xiàng)鏈表和雙向循環(huán)鏈表中任選一種結(jié)構(gòu)）。 （2

3、）采用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)?！緦?shí)現(xiàn)程序】#include stdafx.h#include using namespace std;template class Chain;templateclass ChainNodefriend Chain;private:T data;ChainNode *link;templateclass Chainpublic:Chain()first=0;Chain();bool IsEmpty()constreturn first=0;int Length()const;bool Find(int k,T&x) ;Chain&Insert(int k,const T&

4、x);Chain& Change(int k,T x);Chain& Delete(int k, T &x);Chain& Search(const T&x)const;int OutPut();private:ChainNode*first; ;/*析構(gòu)函數(shù)（刪除鏈表的所有節(jié)點(diǎn)）*/template Chain:Chain()ChainNode*next;while(first)next=first-link;delete first;first=next;/*確定鏈表的長(zhǎng)度*/template int Chain:Length()constChainNode*current=first;i

5、nt len=0;while(current)len+;current=current-link;return len;/*在鏈表中查找第K個(gè)元素*/template bool Chain:Find(int k,T &x) ChainNode*current=first;int index=0;while(indexlink;index+;if(current) x=current-data;return true;return false;/*向鏈表中插入元素*/templateChain& Chain:Insert(int k,const T&x)ChainNode*p=first;for

6、(int index=1;indexlink;ChainNode*y=new ChainNode;y-data=x;if(k)y-link=p-link;p-link=y;else y-link=first;first=y;return *this;/*改變鏈表第k個(gè)元素的值*/templateChain& Chain:Change(int k,T x)ChainNode *p=first;for(int index=0;p&indexlink;if (p) p-data=x;return *this;/*刪除鏈表第k個(gè)元素*/templateChain&Chain:Delete(int k,

7、 T &x)if(k=0)first=first-link;elseChainNode* p = first;ChainNode* q = first;for(int index=1;indexlink;p=q-link;q-link=p-link;x=P-data;delete p;return *this;/*搜索第k個(gè)元素*/templateChain&Chain:Search(const T&x)constChainNode *current=first;int index=1;while(current & current-data !=x)current = current-lin

8、k;index +;if(current)return index;return 0;/*倒序輸出鏈表*/templateint Chain:OutPut()ChainNode*current=first;int index=0;int len=0;while(current)len+;current=current-link;int *arry=new intlen;current=first;while(current) arryindex=current-data;current=current-link;index+;index=index-1;cout=0;index-)cout.f

9、ill(0);cout.width(3);coutarryindex;coutendl;return 0;int main()Chain A;int n,i,j,k;int l=0;A.Insert(0,1);coutplease enter a number :n;for(i=1;i=n;i+)int m=A.Length();for(j=0;jm;j+)A.Find(j,k);k=i*k;A.Change(j,k);for(j=0;j=1000)if(jm-1) A.Find(j+1,l);else A.Insert(j+1,0);l=0;l+=k/1000;A.Change(j+1,l)

10、;k=k%1000;A.Change(j,k);coutLength = A .Length()endl;cout階乘為：;A.OutPut();return 0;【測(cè)試數(shù)據(jù)】 （1）n20，n！2432902008176640000 （2）n30，n！【運(yùn)行結(jié)果】實(shí)習(xí)題目二算術(shù)表達(dá)式求值【基本要求】（1）正確解釋表達(dá)式；(2)符合四則運(yùn)算規(guī)則： 先乘除、后加減 從左到右運(yùn)算先括號(hào)內(nèi)，后括號(hào)外(3)輸出最后的計(jì)算結(jié)果 【實(shí)現(xiàn)關(guān)鍵】?jī)蓚€(gè)棧的使用兩位數(shù)以上、負(fù)數(shù)、小數(shù)點(diǎn)？【實(shí)現(xiàn)方式】基本：控制臺(tái)程序【實(shí)現(xiàn)提示】（1）使用兩個(gè)工作棧：一個(gè)棧：存放運(yùn)算符.另一個(gè)棧：存放操作數(shù)（2）運(yùn)算符之間的優(yōu)先關(guān)系

11、可用二維數(shù)組（算符優(yōu)先順序如下：）【實(shí)現(xiàn)代碼】#include stdafx.h#include using namespace std;templateclass Stackpublic:Stack(int MaxStackSize=10);Stack()delete stack;bool IsEmpty()const return top=-1;bool IsFull()constreturn top=MaxTop;T Top()const;Stack&Add(const T &x);Stack&Delete(T&x);private:int top;int MaxTop;T*stack;

12、template Stack:Stack(int MaxStackSixe)MaxTop=MaxStackSixe-1;stack=new TMaxStackSixe;top=-1; templateT Stack:Top()constreturn stacktop;templateStack&Stack:Add(const T&x)stack+top=x;return *this;templateStack&Stack:Delete(T&x)x=stacktop-;return *this;/此函數(shù)用來(lái)比較兩個(gè)符號(hào)的優(yōu)先級(jí)int Comp( char left, char right) ch

13、ar t9=+,-,*,/,%,(,),#;int smax99=/*+*/1,1,2,2,2,2,2,1,1, /*-*/ 1,1,2,2,2,2,2,1,1, /*/ 1,1,1,1,1,2,2,1,1, /*/*/ 1,1,1,1,1,2,2,1,1, /*%*/ 1,1,1,1,1,2,2,1,1, /*/ 1,1,1,1,1,1,2,1,1, /*(*/ 2,2,2,2,2,2,2,3,0, /*)*/ 1,1,1,1,1,1,0,1,1, /*#*/ 2,2,2,2,2,2,2,0,3; int j,k;for(int i=0;i9;i+)if(left=ti)j=i;if(rig

14、ht=ti)k=i;switch(smaxjk)case 1:return 1;case 2:return -1;case 3:return 0;default: coutERROR!endl;return 2;double Cal(char b, char op, char a) double d=(int)b-48; double e=(int)a-48; switch(op) case +:return d+e; / 計(jì)算+ case -:return d-e; / 計(jì)算- case *:return d*e; / 計(jì)算* case /: / 計(jì)算/ if(e=0) cout被除數(shù)為0，

15、有錯(cuò)！endl; return false; else return d/e;default: return 0; int main() char x; Stack op;Stack k; op.Add(#); cout請(qǐng)輸入中綴表達(dá)式并以#結(jié)尾endl; char s20; char expr20; cin.getline(s,20); cout后綴表達(dá)式為：endl; for(int j=0;j=0&sj=9) coutsj; k.Add(sj); else if(sj!=) if(Comp(op.Top(),sj)=-1) op.Add(sj); else if(Comp(op.Top(

16、),sj)=1) coutop.Top(); k.Add(op.Top(); op.Delete(x); op.Add(sj); if(sj=) while(op.Top()!=() coutop.Top(); k.Add(op.Top(); op.Delete(x); if(op.Top()=() op.Delete(x); if(sj=#) op.Delete(x); while(op.Top()!=#) cout=0;i-) if(expri=0&expri=9) k.Add(expri); else k.Delete(a); k.Delete(b); n=Cal(b,expri,a);

17、 m=n+0; k.Add(m); cout表達(dá)式的值為：endl; cout(double)k.Top()-48endl; return 0;【運(yùn)行結(jié)果】-實(shí)習(xí)題目三二叉樹基本算法的實(shí)現(xiàn)【功能要求】實(shí)現(xiàn)Create方法，要求鍵盤輸入二叉樹結(jié)點(diǎn)序列，創(chuàng)建一棵二叉樹（提示：前序遞歸） 實(shí)現(xiàn)SwapTree方法，以根結(jié)點(diǎn)為參數(shù)，交換每個(gè)結(jié)點(diǎn)的左子樹和右子樹（提示：前序遞歸） 增加InorderTree方法，采用非遞歸方法實(shí)現(xiàn)二叉樹的中序遍歷 你可以選擇：對(duì)BinaryTree模板進(jìn)行功能擴(kuò)充；自己定義并實(shí)現(xiàn)二叉樹類要求鍵盤輸入二叉樹結(jié)點(diǎn)序列結(jié)點(diǎn)序列可以是前序，也可以是層次空結(jié)點(diǎn)以#表示【代碼實(shí)現(xiàn)】

18、#include stdafx.h#include using namespace std;templateclass BinaryTreeNode;templateclass BinaryTreepublic:BinaryTree()root=0;BinaryTree(const BinaryTree &Tree )copy(Tree.root,root);BinaryTree();bool IsEmpty()constreturn (root)?false:true);void Creat();bool Root (T&x)const;void MakeTree(const T&eleme

19、nt,BinaryTree&left,BinaryTree&right);void BreakTree( T&element,BinaryTree&left,BinaryTree&right);void PreOrder(void (*Visit)(BinaryTreeNode*u) PreOrder(Visit,root);void InOrder(void (*Visit)(BinaryTreeNode*u)InOrder(Visit,root);void PostOrder(void (*Visit)(BinaryTreeNode*u)PostOrder(Visit,root);void

20、 LevelOrder(void(*Visit)(BinaryTreeNode*u);void PreOutput() PreOrder(Output,root); coutendl;void InOutput()InOrder(Output,root); coutendl;void Postput() PostOrder(Output,root); coutendl;void LevelOutPut()LevelOrder(Output);coutendl;void Delete()PostOrder(Free,root);root=0;int Height()constreturn Hei

21、ght(root);int Size()constreturn Size(root);BinaryTreeNode*iCreat();bool equal(BinaryTree&Tree)return compare(root,Tree.root);void swap()swap(root);int leave()return leave(root);int noleave()return noleave(root);private:BinaryTreeNode*root;void PreOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t

22、);void InOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);void PostOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);static void Output(BinaryTreeNode* t)coutdata ;static void Free(BinaryTreeNode*t)delete t;int Height(BinaryTreeNode*t)const;int Size(BinaryTreeNode*t)const; bool compare(Bi

23、naryTreeNode*t1,BinaryTreeNode*t2); void copy(const BinaryTreeNode*t1,BinaryTreeNode*&t2);void swap(BinaryTreeNode*t);int leave(BinaryTreeNode*t);int noleave(BinaryTreeNode*t);templateclass LinkedQueue;templateclass Nodefriend LinkedQueue;private:T data;Node*link;templateclass LinkedQueue public:Lin

24、kedQueue()front=rear=0;LinkedQueue();bool IsEmpty()constreturn (front)?false:true);bool IsFull()const;T First()const;T Last()const;LinkedQueue&Add(const T &x);LinkedQueue&Delete(T&x);private:Node*front;Node*rear;templatebool BinaryTree:Root(T&x)constif(root)x=root-data;return true;else return false;

25、templatevoid BinaryTree:MakeTree(const T &element ,BinaryTree&left,BinaryTree&right)root=new BinaryTreeNode(element,left.root,right.root);left.root=right.root=0;templatevoid BinaryTree:BreakTree(T&element ,BinaryTree&left,BinaryTree&right)element=root-data;left.root=root-LeftChild;right.root=root-Ri

26、ghtChild;delete root;root=0;templatevoid BinaryTree:PreOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t)if(t) Visit(t);PreOrder(Visit,t-LeftChild);PreOrder(Visit,t-RightChild);template void BinaryTree:InOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t)if(t)InOrder(Visit,t-LeftChild);Visit(

27、t);InOrder(Visit,t-RightChild);templatevoid BinaryTree:PostOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t)if(t)PostOrder(Visit,t-LeftChild);PostOrder(Visit,t-RightChild);Visit(t);templatevoid BinaryTree:LevelOrder(void(*Visit)(BinaryTreeNode*u)LinkedQueueBinaryTreeNode* Q;BinaryTreeNode*t;t=r

28、oot;while(t)Visit(t);if(t-LeftChild) Q.Add(t-LeftChild);if(t-RightChild) Q.Add(t-RightChild);if(Q.IsEmpty() return ;else Q.Delete(t);templateint BinaryTree:Height(BinaryTreeNode*t)constif(!t) return 0;int hl=Height(t-LeftChild);int hr=Height(t-RightChild);if(hlhr) return +hl;else return +hr;template

29、int BinaryTree:Size(BinaryTreeNode*t)const if(!t) return 0; int sl=Size(t-LeftChild); int sr=Size(t-RightChild); return (1+sl+sr);templateBinaryTreeNode*BinaryTree:iCreat( ) T ch;cinch;BinaryTreeNode * root;if(ch=#) root=NULL;elseroot=new BinaryTreeNode;root-data=ch;root-LeftChild=this-iCreat();root

30、-RightChild=this-iCreat();return root; templatevoid BinaryTree:Creat() this-root = iCreat();templatebool BinaryTree:compare(BinaryTreeNode *t1, BinaryTreeNode *t2)if (t1=NULL&t2=NULL) return true;else if (t1!=NULL&t2=NULL) return false;else if (t1=NULL&t2!=NULL) return false;else if (t1-data!=t2-dat

31、a) return false;else return (compare(t1-leftChild,t2-leftChild)&compare(t1-RightChild,t2-RightChild);templatevoid BinaryTree:copy(const BinaryTreeNode*t1,BinaryTreeNode*&t2)if(t1)t2=new BinaryTreeNode;t2-data=t1-data;copy(t1-LeftChild,t2-LeftChild);copy(t1-RightChild,t2-RightChild);templatevoid Bina

32、ryTree:swap(BinaryTreeNode *t)BinaryTreeNode *temp;if(!t) return;elsetemp=t-LeftChild;t-LeftChild=t-RightChild;t-RightChild=temp;swap(t-leftChild);swap(t-RightChild);templateint BinaryTree:leave(BinaryTreeNode*t)if(!t) return 0;if(t-LeftChild=0&t-RightChild=0)return 1;int leafl=leave(t-LeftChild);in

33、t leafr=leave(t-RightChild); return leafl+leafr;templateint BinaryTree:noleave(BinaryTreeNode *t)if(!t) return 0;if(!t-LeftChild&!t-RightChild)return 0;int leafl=noleave(t-LeftChild);int leafr=noleave(t-RightChild);return leafl+leafr+1;templateclass BinaryTree;templateclass BinaryTreeNodefriend Bina

34、ryTree;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;RightChild=r;private:T data;BinaryTreeNode*LeftChild,*RightChild;templateLinkedQueue:LinkedQueue()Node*next;while(front)next=front-link;delete front;front=next;t