1、n(n20)的階乘【問題描述】大數(shù)運算計算n的階乘(n=20)?！净疽蟆?1)數(shù)據(jù)的表示和存儲；(1.1)累積運算的中間結果和最終的計算結果的數(shù)據(jù)類型要求是整型這是問題本身的要求；(1.2)試設計合適的存儲結構，要求每個元素或結點最多存儲數(shù)據(jù)的3位數(shù)值。(2)數(shù)據(jù)的操作及其實現(xiàn)：基于設計的存儲結構實現(xiàn)乘法操作，要求從鍵盤上輸入n值，在屏幕上顯示最終計算結果?！緶y試數(shù)據(jù)】(1)n=20,n!=2432902008176640000(2)n=30,n!=265252859812191058636308480000000#includestdafx.h#include#includeusingn

2、amespacestd;templateclassChain;templateclassChainNodefriendChain;private:Tdata;ChainNode*link;templateclassChainpublic:Chain()first=0;Chain();boolIsEmpty()constreturnfirst=0;intLength()const;boolFind(intk,T&x)const;intSearch(constT&x)const;Chain&Delete(intk,T&x);Chain&Insert(intk,constT&x);voidOutpu

3、t(ostream&out)const;構造函數(shù)析構函數(shù)判斷鏈表是否為空求鏈表的長度查找第k個元素查找元素x/刪除第k個元素在第k個元素之后插入x/單鏈表的輸出Chain&Fac(longn);/求大數(shù)階乘private:/指向第一個節(jié)點ChainNode*first;templateChain:Chain()刪除所有的節(jié)點ChainNode*next;while(first)next=first-link;deletefirst;first=next;templateboolChain:Find(intk,T&x)const/查找第k個元素，并賦值給xif(k1)returnfalse;Ch

4、ainNode*current=first;intindex=1;while(indexlink;index+;if(current)x=current-data;returntrue;returnfalse;templateintChain:Search(constT&x)const查找元素x,返回該元素的下標ChainNode*current=first;intindex=1;while(current¤t-data!=x)current=current-link;index+;)if(current)returnindex;return0;templateChain&Chai

5、n:Delete(intk,T&x)/刪除第k個元素，并賦值給x,返回改變后的鏈表ChainNode*p=first;if(k=1)first=first-link;elseChainNode*q=first;for(intindex=1;indexlink;p=q-link;q-link=p-link;)x=p-data;deletep;return*this;)templateintChain:Length()const返回鏈表的長度ChainNode*current=first;intlen=0;while(current)len+;current=current-link;)retur

6、nlen;)templateChain&Chain:Insert(intk,constT&x)/在第k個元素之后插入x，返回插入后的鏈表ChainNode*p=first;for(intindex=1;indexlink;ChainNode*y=newChainNode;y-data=x;if(k)y-link=p-link;p-link=y;elsey-link=first;first=y;return*this;templatevoidChain:Output(ostream&out)const輸出鏈表元素ChainNode*current;inti=OJ=Length();for(cur

7、rent=first;current;current=current-link)i+；if(i=j&j=l)if(current-link)outsetw(3)setfill(0,)current-dataelseoutcurrent-datai=l；current=first;)outsetw(3)setfill(,0,)first-datatemplate重載運算符ostream&operator(ostream&out,constChain&x)x.Output(out);returnout;templateChain&Chain:Fac(longn)初始化inti=0;longj=n;

8、while(j999)(Insert(i,j%1000);i+；j=j/1000；)Insert(i,j);/通過插入來建立鏈表(0,20)/計算longm=0,k=0;ChainNode*current;for(;n2;n-)(for(current=first;current;current=current-link)/?(m=k;k=(current-data*(n-1)+k)/1000;向前進位current-data=(current-data*(n-1)+m)%1000;if(!current-link&k0)/?(while(k999)(Insert(Length(),k%100

9、0);k=k/1000;)Insert(Length(),k);/鏈表長度加一k=0;break;)return*this;)intmain()(longn;charch;do(coutn;Chaina;a.Fac(n);coutn的階乘為:endl;couta;coutendl;cout”是否進行計算:“；coutch;while(ch=Y);return0;2:題目：表達式求值:要求：實現(xiàn)關鍵棧的使用兩位數(shù)以上、負數(shù)、小數(shù)點？實現(xiàn)方式控制臺程序MFC對話框#includestdafx.h#includeusingnamespacestd;#include#include#includete

10、mplateclassStackpublic:Stack(intsz=50);Stack()deleteelements;voidPush(constT&x);壓入棧boolPop(T&x);彈出棧TGetTop(void)const;取棧頂元素boolIsEmpty()constreturn(top=-1)?true:false;boolIsFull()/判斷棧是否滿return(top=MaxSize-1)?true:false;intGetSize()const/?returntop+1;voidMakeEmpty()top=-1;private:T*elements;inttop;in

11、tMaxSize;voidoverflowProcess();/棧溢出處理;templateStack:Stack(intsz)top=-1;MaxSize=sz;elements=newTMaxSize;創(chuàng)建棧的數(shù)組空間assert(elements!=NULL);判斷動態(tài)內(nèi)存是否分配成功是否templatevoidStack:Push(constT&x)if(IsFull()=true)overflowProcess();top+;elementstop=x;templateboolStack:Pop(T&x)if(IsEmpty()=true)returnfalse;x=elements

12、top-;returntrue;templateTStack:GetTop(void)const返回棧頂元素if(IsEmpty()=true)cerr棧為空!endl;exit(1);returnelementstop;templatevoidStack:overflowProcess()溢出處理T*newArray=newT2*MaxSize;擴充棧的空間for(inti=0;i=top;i+)MaxSize=2*MaxSize;newArrayi=elementsi;deleteelements;釋放原來舊的空間classCalculater計算的聲明public:Calculater(

13、)voidRun();執(zhí)行表達式計算voidClear();清空處理private:Stacks;聲明double型的棧對象voidAddOperand(doublevalue);把數(shù)值壓入棧中boolGetOperand(double&left,double&right);判斷取操作數(shù)操作是否成功voidDoOperator(charch);進行操作;voidCalculater:AddOperand(doublevalue)s.Push(value);boolCalculater:GetOperand(double&left,double&right)if(s.IsEmpty()=true

14、)cerr缺少右操作數(shù)endl;returnfalse;s.Pop(right);if(s.IsEmpty()=true)cerr缺少左操作數(shù)endl;returnfalse;s.Pop(left);returntrue;voidCalculater:Clear()s.MakeEmpty();voidCalculater:DoOperator(charch)doubleleft,right,value;boolresult;result=GetOperand(left,right);if(result=true)switch(ch)case+:value=left+right;s.Push(v

15、alue);break;case-:value=left-right;s.Push(value);break;case*:value=left*right;s.Push(value);break;case/:if(right=0.0)cerrDivideby0!endl;Clear();elsevalue=left/right;s.Push(value);break;cout=s.GetTop()ch,ch!=#)switch(ch)case+:case-:case*:case/:是操作數(shù)，執(zhí)行計算DoOperator(ch);break;default:其實也是一種case,只不過就是指“除

16、了指定的幾個case以外的其他情況”，不是操作符cin.putback(ch);字符放回輸入流cinnewOperand;重新讀取操作數(shù)，一個操作數(shù)的第一個字符AddOperand(newOperand);將操作數(shù)放入棧中intmain()Calculatercall;8a輸入計算表達式:；call.Run();return0;3.題目：:題目：二叉樹基本算法的實現(xiàn):功能要求：鍵盤輸入二叉樹結點序列，創(chuàng)建一棵二叉樹實現(xiàn)SwapTree方法，以根結點為參數(shù)，交換每個結點的左子樹和右子樹(提示：前序遞歸)實現(xiàn)Find方法，查找值為key的結點，并輸出該結點的所有祖先結點你可以選擇：對BinaryT

17、ree模板進行功能擴充；自己定義并實現(xiàn)二叉樹類要求鍵盤輸入二叉樹結點序列結點序列可以是前序，也可以是層次空結點以#表示/binarytree.h#ifndefBINARYTREE_H#defineBINARYTREE_H#includetemplateclassBinaryTreeNode二叉樹結點/friendBinaryTree;public:BinaryTreeNode()LeftChild=RightChild=0;BinaryTreeNode(constT&e)data=e;LeftChild=RightChild=0;BinaryTreeNode(constT&e,BinaryTr

18、eeNode*l,BinaryTreeNode*r)data=e;LeftChild=l;RightChild=r;public:Tdata;BinaryTreeNode*LeftChild,*RightChild;templateclassBinaryTreefriendBinaryTreeNode;public:BinaryTree()root=0;BinaryTree()boolIsEmpty()constreturn(root)?false:true);voidCreat();voidPreOrder(void(*Visit)(BinaryTreeNode*u)/F遍歷PreOrder

19、(Visit,root);voidInOrder(void(*Visit)(BinaryTreeNode*u中/序遍歷InOrder(Visit,root);voidPostOrder(void(*Visit)(BinaryTreeNode*u遍歷PostOrder(Visit,root);voidLevelOrder(void(*Visit)(BinaryTreeNode*u)|/C遍歷PreOrder(Output,root);coutendl;voidInOutput()/h序輸出InOrder(Output,root);coutendl;voidPostput()/f序輸出PostOr

20、der(Output,root);coutendl;voidLevelOutPut()/層I次輸出LevelOrder(Output);coutendl;intHeight()const/計算樹的高度returnHeight(root);intSize()const/計算樹的大小returnSize(root);BinaryTreeNode*iCreat();voidswap()/交換左右節(jié)點swap(root);intleave()計算葉子節(jié)點個數(shù)returnleave(root);intnoleave()/計算非葉子節(jié)點個數(shù)returnnoleave(root);private:Binar

21、yTreeNode*root;voidPreOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);voidInOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);voidPostOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);/voidLevelOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);staticvoidOutput(BinaryTreeNode*t)

22、輸出樹的所有節(jié)點coutdata；intHeight(BinaryTreeNode*t)const;intSize(BinaryTreeNode*t)const;voidswap(BinaryTreeNode*t);intleave(BinaryTreeNode*t);intnoleave(BinaryTreeNode*t);templateintBinaryTree:Height(BinaryTreeNode*t)constif(!t)return0;inthl=Height(t-LeftChild);inthr=Height(t-RightChild);if(hlhr)return+hl;

23、elsereturn+hr;templateintBinaryTree:Size(BinaryTreeNode*t)constif(!t)return0;intsl=Size(t-LeftChild);intsr=Size(t-RightChild);return(1+sl+sr);templateBinaryTreeNode*BinaryTree:iCreat()Tch;cinch;BinaryTreeNode*root;if(ch=#)root=NULL;elseroot=newBinaryTreeNode;root-data=ch;root-LeftChild=this-iCreat()

24、;root-RightChild=this-iCreat();returnroot;templatevoidBinaryTree:Creat()this-root=iCreat();templatevoidBinaryTree:PreOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t)if(t)Visit(t);PreOrder(Visit,t-LeftChild);PreOrder(Visit,t-RightChild);templatevoidBinaryTree:InOrder(void(*Visit)(BinaryTreeNode

25、*u),BinaryTreeNode*t)if(t)InOrder(Visit,t-LeftChild);Visit(t);InOrder(Visit,t-RightChild);templatevoidBinaryTree:PostOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t)if(t)PostOrder(Visit,t-LeftChild);PostOrder(Visit,t-RightChild);Visit(t);templatevoidBinaryTree:swap(BinaryTreeNode*t)BinaryTreeN

26、ode*temp;if(!t)return;elsetemp=t-LeftChild;t-LeftChild=t-RightChild;t-RightChild=temp;swap(t-LeftChild);swap(t-RightChild);templateintBinaryTree:leave(BinaryTreeNode*t)if(!t)return0;if(t-LeftChild=0&t-RightChild=0)return1;intleafl=leave(t-LeftChild);intleafr=leave(t-RightChild);returnleafl+leafr;templ