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

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

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

3、de "stdafx.h"#include <iostream>using namespace std;template<class T> class Chain;template<class T>class ChainNodefriend Chain<T>private:T data;ChainNode<T> *link;template<class T>class Chainpublic:Chain()first=0;Chain();bool IsEmpty()constreturn first=0

4、;int Length()const;bool Find(int k,T&x) ;Chain<T>&Insert(int k,const T&x);Chain<T>& Change(int k,T x);Chain<T>& Delete(int k, T &x);Chain<T>& Search(const T&x)const;int OutPut();private:ChainNode<T>*first; ;/*析构函数删除链表的所有节点*/template<cl

5、ass T> Chain<T>:Chain()ChainNode<T>*next;while(first)next=first->link;delete first;first=next;/*确定链表的长度*/template<class T> int Chain<T>:Length()constChainNode<T>*current=first;int len=0;while(current)len+;current=current->link;return len;/*在链表中查找第K个元素*/template

6、<class T> bool Chain<T>:Find(int k,T &x) ChainNode<T>*current=first;int index=0;while(index<k&&current)current=current->link;index+;if(current) x=current->data;return true;return false;/*向链表中插入元素*/template<class T>Chain<T>& Chain<T>:Insert

7、(int k,const T&x)ChainNode<T>*p=first;for(int index=1;index<k&&p;index+)p=p->link;ChainNode<T>*y=new ChainNode<T>y->data=x;if(k)y->link=p->link;p->link=y;else y->link=first;first=y;return *this;/*改变链表第k个元素的值*/template<class T>Chain<T>&am

8、p; Chain<T>:Change(int k,T x)ChainNode<T> *p=first;for(int index=0;p&&index<k;index+)p=p->link;if (p) p->data=x;return *this;/*删除链表第k个元素*/template<class T>Chain<T>&Chain<T>:Delete(int k, T &x)if(k=0)first=first->link;elseChainNode<T>* p

9、 = first;ChainNode<T>* q = first;for(int index=1;index<k-1&&q;index+)q=q->link;p=q->link;q-link=p->link;x=P->data;delete p;return *this;/*搜索第k个元素*/template<class T>Chain<T>&Chain<T>:Search(const T&x)constChainNode<T> *current=first;int ind

10、ex=1;while(current && current->data !=x)current = current->link;index +;if(current)return index;return 0;/*倒序输出链表*/template<class T>int Chain<T>:OutPut()ChainNode<T>*current=first;int index=0;int len=0;while(current)len+;current=current->link;int *arry=new intlen;c

11、urrent=first;while(current) arryindex=current->data;current=current->link;index+;index=index-1;cout<<arryindex;index=index-1;for(index;index>=0;index-)cout.fill('0');cout.width(3);cout<<arryindex;cout<<endl;return 0;int main()Chain<int> A;int n,i,j,k;int l=0;

12、A.Insert(0,1);cout<<"please enter a number :"<<endl;cin>>n;for(i=1;i<=n;i+)int m=A.Length();for(j=0;j<m;j+)A.Find(j,k);k=i*k;A.Change(j,k);for(j=0;j<m;j+)A.Find(j,k);if(k>=1000)if(j<m-1) A.Find(j+1,l);else A.Insert(j+1,0);l=0;l+=k/1000;A.Change(j+1,l);k=k%1

13、000;A.Change(j,k);cout<<"Length = "<<A .Length()<<endl;cout<<"阶乘为："A.OutPut();return 0;【测试数据】 1n20，n！2432902021176640000 2n30，n！【运行结果】实习题目二算术表达式求值【根本要求】1正确解释表达式；(2)符合四那么运算规那么： 先乘除、后加减 从左到右运算先括号内，后括号外(3)输出最后的计算结果 【实现关键】两个栈的使用两位数以上、负数、小数点？【实现方式】根本：控制台程序【实现提示

14、】1使用两个工作栈：一个栈：存放运算符.另一个栈：存放操作数2运算符之间的优先关系可用二维数组算符优先顺序如下：【实现代码】#include "stdafx.h"#include<iostream> using namespace std;template<class T>class Stackpublic:Stack(int MaxStackSize=10);Stack()delete stack;bool IsEmpty()const return top=-1;bool IsFull()constreturn top=MaxTop;T Top(

15、)const;Stack<T>&Add(const T &x);Stack<T>&Delete(T&x);private:int top;int MaxTop;T*stack;template <class T>Stack<T>:Stack(int MaxStackSixe)MaxTop=MaxStackSixe-1;stack=new TMaxStackSixe;top=-1; template<class T>T Stack<T>:Top()constreturn stacktop;te

16、mplate<class T>Stack<T>&Stack<T>:Add(const T&x)stack+top=x;return *this;template<class T>Stack<T>&Stack<T>:Delete(T&x)x=stacktop-;return *this;/此函数用来比拟两个符号的优先级int Comp( char left, char right) char t9='+','-','*','/',

17、'%','','(',')','#'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

18、(int i=0;i<9;i+)if(left=ti)j=i;if(right=ti)k=i;switch(smaxjk)case 1:return 1;case 2:return -1;case 3:return 0;default: cout<<"ERROR!"<<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

19、 '-':return d-e; / 计算- case '*':return d*e; / 计算* case '/': / 计算/ if(e=0) cout<<"被除数为0，有错！"<<endl; return false; else return d/e;default: return 0; int main() char x; Stack<char> op;Stack<char> k; op.Add('#'); cout<<"请输入中缀表

20、达式并以#结尾"<<endl; char s20; char expr20; cin.getline(s,20); cout<<"后缀表达式为："<<endl; for(int j=0;j<strlen(s);j+) if(sj>='0'&&sj<='9') cout<<sj; k.Add(sj); else if(sj!=')') if(Comp(op.Top(),sj)=-1) op.Add(sj); else if(Comp(op

21、.Top(),sj)=1) cout<<op.Top(); k.Add(op.Top(); op.Delete(x); op.Add(sj); if(sj=')') while(op.Top()!='(') cout<<op.Top(); k.Add(op.Top(); op.Delete(x); if(op.Top()='(') op.Delete(x); if(sj='#') op.Delete(x); while(op.Top()!='#') cout<<op.Top();

22、 k.Add(op.Top(); op.Delete(x); int i=0; char a;char b;double n;char m; while(!k.IsEmpty() k.Delete(expri); i+; for(i=i-1;i>=0;i-) if(expri>='0'&&expri<='9') k.Add(expri); else k.Delete(a); k.Delete(b); n=Cal(b,expri,a); m=n+'0' k.Add(m); cout<<"表达式

23、的值为："<<endl; cout<<(double)k.Top()-48<<endl; return 0;【运行结果】-实习题目三二叉树根本算法的实现【功能要求】实现Create方法，要求键盘输入二叉树结点序列，创立一棵二叉树提示：前序递归 实现SwapTree方法，以根结点为参数，交换每个结点的左子树和右子树提示：前序递归 增加InorderTree方法，采用非递归方法实现二叉树的中序遍历 你可以选择：对BinaryTree模板进行功能扩充；自己定义并实现二叉树类要求键盘输入二叉树结点序列结点序列可以是前序，也可以是层次空结点以#表示【代码实现

24、】#include "stdafx.h"#include <iostream>using namespace std;template<class T>class BinaryTreeNode;template<class T>class BinaryTreepublic:BinaryTree()root=0;BinaryTree(const BinaryTree<T> &Tree )copy(Tree.root,root);BinaryTree();bool IsEmpty()constreturn (root)?f

25、alse:true);void Creat();bool Root (T&x)const;void MakeTree(const T&element,BinaryTree<T>&left,BinaryTree<T>&right);void BreakTree( T&element,BinaryTree<T>&left,BinaryTree<T>&right);void PreOrder(void (*Visit)(BinaryTreeNode<T>*u) PreOrder(Vis

26、it,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);void PreOutput() PreOrder(Output,root); cout<<endl;void InOutput()InOrder(Outpu

27、t,root); cout<<endl;void Postput() PostOrder(Output,root); cout<<endl;void LevelOutPut()LevelOrder(Output);cout<<endl;void Delete()PostOrder(Free,root);root=0;int Height()constreturn Height(root);int Size()constreturn Size(root);BinaryTreeNode<T>*iCreat();bool equal(BinaryTre

28、e<T>&Tree)return compare(root,Tree.root);void swap()swap(root);int leave()return leave(root);int noleave()return noleave(root);private:BinaryTreeNode<T>*root;void PreOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);void InOrder(void(*Visit)(BinaryTreeNode<T

29、>*u),BinaryTreeNode<T>*t);void PostOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);static void Output(BinaryTreeNode<T>* t)cout<<t->data <<" "static void Free(BinaryTreeNode<T>*t)delete t;int Height(BinaryTreeNode<T>*t)cons

30、t;int Size(BinaryTreeNode<T>*t)const; bool compare(BinaryTreeNode<T>*t1,BinaryTreeNode<T>*t2); void copy(const BinaryTreeNode<T>*t1,BinaryTreeNode<T>*&t2);void swap(BinaryTreeNode<T>*t);int leave(BinaryTreeNode<T>*t);int noleave(BinaryTreeNode<T>*t

31、);template<class T>class LinkedQueue;template<class T>class Nodefriend LinkedQueue<T>private:T data;Node<T>*link;template<class T>class LinkedQueue public:LinkedQueue()front=rear=0;LinkedQueue();bool IsEmpty()constreturn (front)?false:true);bool IsFull()const;T First()c

32、onst;T Last()const;LinkedQueue<T>&Add(const T &x);LinkedQueue<T>&Delete(T&x);private:Node<T>*front;Node<T>*rear;template<class T>bool BinaryTree<T>:Root(T&x)constif(root)x=root->data;return true;else return false;template<class T>void

33、BinaryTree<T>:MakeTree(const T &element ,BinaryTree<T>&left,BinaryTree<T>&right)root=new BinaryTreeNode<T>(element,left.root,right.root);left.root=right.root=0;template<class T>void BinaryTree<T>:BreakTree(T&element ,BinaryTree<T>&left,Bi

34、naryTree<T>&right)element=root->data;left.root=root->LeftChild;right.root=root->RightChild;delete root;root=0;template<class T>void BinaryTree<T>:PreOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t)if(t) Visit(t);PreOrder(Visit,t->LeftChild);P

35、reOrder(Visit,t->RightChild);template<class T> void BinaryTree<T>:InOrder(void(*Visit)(BinaryTreeNode<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(*Visi

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

37、>*t;t=root;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);template<class T>int BinaryTree<T>:Height(BinaryTreeNode<T>*t)constif(!t) return 0;int hl=Height(t->LeftChild);int hr=He

38、ight(t->RightChild);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&

39、lt;T>:iCreat( ) 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-

40、>root = iCreat();template<class T>bool BinaryTree<T>:compare(BinaryTreeNode<T> *t1, BinaryTreeNode<T> *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-&g

41、t;data) return false;else return (compare(t1->leftChild,t2->leftChild)&&compare(t1->RightChild,t2->RightChild);template<class T>void BinaryTree<T>:copy(const BinaryTreeNode<T>*t1,BinaryTreeNode<T>*&t2)if(t1)t2=new BinaryTreeNode<T>t2->data=t1-

42、>data;copy(t1->LeftChild,t2->LeftChild);copy(t1->RightChild,t2->RightChild);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(

43、t->leftChild);swap(t->RightChild);template<class T>int BinaryTree<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&

44、gt;int BinaryTree<T>:noleave(BinaryTreeNode<T> *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;template<class T>class BinaryTree;template<class T>class Binar

45、yTreeNodefriend 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;RightChild=r;private:T data;BinaryTreeNode<T>*LeftChild,*RightChild;te

46、mplate<class T>LinkedQueue<T>:LinkedQueue()Node<T>*next;while(front)next=front->link;delete front;front=next;template<class T>LinkedQueue<T>&LinkedQueue<T>:Add(const T &x)Node<T>*p=new Node<T>p->data=x;p->link=0; if (front) rear->link=p; else front=p;rear=p;return *this;template<class T>LinkedQueue<T>&Linked