大数阶乘数据结构算法课程设计 - 副本

1、实习题目一线性表及其应用【问题描述】 大数运算计算n的阶乘（n=20）。【基本要求】（1）数据的表示和存储；） 累积运算的中间结果和最终的计算结果的数据类型要求是整型这是问题本身的要求；） 试设计合适的存储结构，要求每个元素或节点最多存储数据的3位数值。 （2）数据的操作及其实现： 基于设计的存储结构实现乘法操作，要求从键盘上输入n值，在屏幕上显示最终计算结果。【实现提示】（1）设计数据的存储结构： 介于阶乘运算的精确性以及实型数据表示的不精确性，本题不能采用实型表示累积运算的中间结果和最终的计算结果，而只能用整型。然而由于普通整型和长整型所能表述数的范围受其字长的限制，不能表示大数阶乘的累积

2、结果，故必须设计一个合适的数据结构实现对数据的存储，例如可以让每个元素或节点存储数据的若干位数值。 从问题描述不难看出n值为任意值，故为使程序尽量不受限制，应采用动态存储结构。（2） 数据的操作及其实现：）累积运算的特点是当前的计算结果是下次乘法运算的乘数； （）实现两个数的乘法运算须考虑： （1）乘数的各位数都要与被乘数进行乘法运算； （2）乘法过程中的进位问题及其实现； （3）因每个元素或节点最多存储数据的3位数值，故当元素或节点中的数值大于999，需向前一个元素或节点进位。 【实现结构】（1）采用链式存储结构实现（普通单链表，循环单链表，普通双项链表和双向循环链表中任选一种结构）。 （2

3、）采用动态数组实现。【实现程序】#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; ;/*析构函数（删除链表的所有节点）*/template Chain:Chain()ChainNode*next;while(first)next=first-link;delete first;first=next;/*确定链表的长度*/template int Chain:Length()constChainNode*current=first;i

5、nt len=0;while(current)len+;current=current-link;return len;/*在链表中查找第K个元素*/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个元素的值*/templateChain& Chain:Change(int k,T x)ChainNode *p=first;for(int index=0;p&indexlink;if (p) p-data=x;return *this;/*删除链表第k个元素*/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个元素*/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;【测试数据】 （1）n20，n！2432902008176640000 （2）n30，n！【运行结果】实习题目二算术表达式求值【基本要求】（1）正确解释表达式；(2)符合四则运算规则： 先乘除、后加减 从左到右运算先括号内，后括号外(3)输出最后的计算结果 【实现关键】两个栈的使用两位数以上、负数、小数点？【实现方式】基本：控制台程序【实现提示】（1）使用两个工作栈：一个栈：存放运算符.另一个栈：存放操作数（2）运算符之间的优先关系

11、可用二维数组（算符优先顺序如下：）【实现代码】#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;/此函数用来比较两个符号的优先级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; / 计算+ case -:return d-e; / 计算- case *:return d*e; / 计算* case /: / 计算/ if(e=0) cout被除数为0，

15、有错！endl; return false; else return d/e;default: return 0; int main() char x; Stack op;Stack k; op.Add(#); cout请输入中缀表达式并以#结尾endl; char s20; char expr20; cin.getline(s,20); cout后缀表达式为：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表达式的值为：endl; cout(double)k.Top()-48endl; return 0;【运行结果】-实习题目三二叉树基本算法的实现【功能要求】实现Create方法，要求键盘输入二叉树结点序列，创建一棵二叉树（提示：前序递归） 实现SwapTree方法，以根结点为参数，交换每个结点的左子树和右子树（提示：前序递归） 增加InorderTree方法，采用非递归方法实现二叉树的中序遍历 你可以选择：对BinaryTree模板进行功能扩充；自己定义并实现二叉树类要求键盘输入二叉树结点序列结点序列可以是前序，也可以是层次空结点以#表示【代码实现】

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