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

1、数据结构与算法上机课程设计报告指导老师:姓 名:班 级:学 号:2010年1月实习题目一线性表及其应用【问题描述】 大数运算计算n的阶乘（n>=20）。【基本要求】（1）数据的表示和存储； （1.1） 累积运算的中间结果和最终的计算结果的数据类型要求是整型这是问题本身的要求； （1.2） 试设计合适的存储结构，要求每个元素或节点最多存储数据的3位数值。 （2）数据的操作及其实现： 基于设计的存储结构实现乘法操作，要求从键盘上输入n值，在屏幕上显示最终计算结果。【实现提示】（1）设计数据的存储结构： 介于阶乘运算的精确性以及实型数据表示的不精确性，本题不能采用实型表示累积运算的中间结果和最

2、终的计算结果，而只能用整型。然而由于普通整型和长整型所能表述数的范围受其字长的限制，不能表示大数阶乘的累积结果，故必须设计一个合适的数据结构实现对数据的存储，例如可以让每个元素或节点存储数据的若干位数值。 从问题描述不难看出n值为任意值，故为使程序尽量不受限制，应采用动态存储结构。（2） 数据的操作及其实现： （2.1）累积运算的特点是当前的计算结果是下次乘法运算的乘数； （2.2）实现两个数的乘法运算须考虑： （1）乘数的各位数都要与被乘数进行乘法运算； （2）乘法过程中的进位问题及其实现； （3）因每个元素或节点最多存储数据的3位数值，故当元素或节点中的数值大于999，需向前一个元素或节点

3、进位。 【实现结构】（1）采用链式存储结构实现（普通单链表，循环单链表，普通双项链表和双向循环链表中任选一种结构）。 （2）采用动态数组实现。【实现程序】#include "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<cl

4、ass T>class Chainpublic:Chain()first=0;Chain();bool IsEmpty()constreturn first=0;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)co

5、nst;int OutPut();private:ChainNode<T>*first; ;/析构函数（删除链表的所有节点）template<class 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

6、;while(current)len+;current=current->link;return len;/在链表中查找第K个元素template<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;

7、/向链表中插入元素template<class T>Chain<T>& Chain<T>:Insert(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;fir

8、st=y;return *this;/改变链表第k个元素的值template<class T>Chain<T>& 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(in

9、t k, T &x)if(k=0)first=first->link;elseChainNode<T>* p = 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>:Sea

10、rch(const T&x)constChainNode<T> *current=first;int index=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

11、(current)len+;current=current->link;int *arry=new intlen;current=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<<en

12、dl;return 0;int main()Chain<int> A;int n,i,j,k;int l=0;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+

13、1,l);else A.Insert(j+1,0);l=0;l+=k/1000;A.Change(j+1,l);k=k%1000;A.Change(j,k);cout<<"Length = "<<A .Length()<<endl;cout<<"阶乘为："A.OutPut();return 0;【测试数据】 （1）n20，n！2432902008176640000 （2）n30，n！265252859812191058636308480000000【运行结果】please enter a number:20

14、Length=7;阶乘为： 2432902008176640000实习题目二算术表达式求值【问题描述】对一个合法的中缀表达式求值。假设表达式只包含+、-、*、/ 四个双目运算符，并且允许有括号出现，运算符本身不具有二义性。例如：3.5*(7+2) /(-6)【基本要求】（1）正确解释表达式；(2)符合四则运算规则： 先乘除、后加减 从左到右运算先括号内，后括号外(3)输出最后的计算结果 【实现关键】两个栈的使用两位数以上、负数、小数点？【实现方式】基本：控制台程序【实现提示】（1）使用两个工作栈：一个栈OPTR：存放运算符；stack<char>另一个栈OPND：存放操作数；sta

15、ck<double>（2）运算符之间的优先关系可用二维数组（算符优先顺序如下：）+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=【实现代码】#include "stdafx.h"#include<iostream> us

16、ing 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()const;Stack<T>&Add(const T &x);Stack<T>&Delete(T&x);private:int top;int MaxTop;T*stack;

17、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;template<class T>Stack<T>&Stack<T>:Add(const T&x)stack+top=x;return *this;template<class

18、T>Stack<T>&Stack<T>:Delete(T&x)x=stacktop-;return *this;/此函数用来比较两个符号的优先级int Comp( char left, char right) char t9='+','-','*','/','%','','(',')','#'int smax99=/*+*/1,1,2,2,2,2,2,1,1, /*-*/ 1,1,2,2,2,2,2,1,1

19、, /*/ 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;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;def

20、ault: 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 '-':return d-e; / 计算- case '*':return d*e; / 计算* case '/': / 计算/ if(e=0) cout<<"

21、被除数为0，有错！"<<endl; return false; else return d/e;default: return 0; int main() char x; Stack<char> op;Stack<char> k; op.Add('#'); cout<<"请输入中缀表达式并以#结尾"<<endl; char s20; char expr20; cin.getline(s,20); cout<<"后缀表达式为："<<endl; fo

22、r(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.Top(),sj)=1) cout<<op.Top(); k.Add(op.Top(); op.Delete(x); op.Add(sj); if(sj=')') while(op.Top()!=

23、9;(') 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(); 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

24、=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<<"表达式的值为："<<endl; cout<<(double)k.Top()-48<<endl; return 0;【运行结果】请输入中缀表达式并以#结尾（4+2）/3-4*3后缀表达式为:42

25、+3/43*-表达式的值为:-10实习题目三二叉树基本算法的实现【功能要求】实现Create方法，要求键盘输入二叉树结点序列，创建一棵二叉树（提示：前序递归） 实现SwapTree方法，以根结点为参数，交换每个结点的左子树和右子树（提示：前序递归） 增加InorderTree方法，采用非递归方法实现二叉树的中序遍历 你可以选择：对BinaryTree模板进行功能扩充；自己定义并实现二叉树类要求键盘输入二叉树结点序列结点序列可以是前序，也可以是层次空结点以#表示【代码实现】/ 二叉树01.cpp : Defines the entry point for the console applicat

26、ion./#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 (roo

27、t)?false: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

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

29、utput,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(Binar

30、yTree<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&

31、lt;T>*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)

32、const;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&g

33、t;*t);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 Firs

34、t()const;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>v

35、oid 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>&lef

36、t,BinaryTree<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->LeftChil

37、d);PreOrder(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(*

38、Visit)(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&

39、lt;T>*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 h

40、r=Height(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>*BinaryT

41、ree<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() t

42、his->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!=t

43、2->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

44、=t1->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;s

45、wap(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<clas

46、s T>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 B

47、inaryTreeNodefriend 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,*RightChil

48、d;template<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-&g

49、t;link=p; else front=p;rear=p;return *this;template<class T>LinkedQueue<T>&LinkedQueue<T>:Delete(T&x)x=front->data;Node<T>*p=front;front=front->link;delete p;return*this;template<class T>bool LinkedQueue<T>:IsFull()constNode<T>*p;tryp=new Node&

50、lt;T>delete p;return false;catch (NoMem) return true;template <class T>T LinkedQueue<T>:First()constif(IsEmpty() throw OutOfBounds;return front->data;template<class T>T LinkedQueue<T>:Last()constif(IsEmpty() throw OutOfBounds;return rear->data;BinaryTree<int> a

51、,x,y,z;void main() cout<<"输入二叉树:"<<endl;BinaryTree<char> Tree;Tree.Creat();cout<<"前序遍历："<<" "Tree.PreOutput();cout<<"后序遍历："<<" "Tree.Postput();cout<<"中序遍历："<<endl;Tree.InOutput();cout<

52、;<"层序遍历："<<" "Tree.LevelOutPut();cout<<"叶子节点的数目"<<" "cout<<Tree.leave()<<endl;cout<<"非叶子节点的数目"<<endl;cout<<Tree.noleave()<<" "cout<<"树的高度"<<endl;cout<<Tree

53、.Height()<<endl;BinaryTree<char> *b=NULL;b= new BinaryTree<char>(Tree);cout<<"拷贝Tree建立二叉树b"<<endl;cout<<"b的前序遍历"<<endl;b->PreOutput();【输出结果】实习题目四【题目要求】用邻接矩阵和链接链表实现图【代码要求】template<class T>class AdjacenyWGraph;template <class T&

54、gt;class AdjacencyWDigraph friend AdjacenyWGraph<T>public:AdjacencyWDigraph(int Vertices = 15, T noEdge = 0); AdjacencyWDigraph();/void Make2DArray(T *x,int rows,int cols);/void Delete2DArray(T *x,int rows);bool Exist(int i, int j)const;int Edges()const return e;/边int Vertices()const return n;

55、/顶点AdjacencyWDigraph<T>& Add(int i, int j,const T& w);AdjacencyWDigraph<T>& Delete(int i,int j);int OutDegree(int i)const;int InDegree(int i)const;void InitializePos()pos = new int n+1;void DeactivatePos()delete pos;int Begin(int i);int NextVertex(int i);void BFS(int v, int r

56、each, int label);void DFS(int i,int reach,int lable);void dfs(int i,int reach,int lable);void ShortestPaths(int s,T d,int p);private:T NoEdge;/用于没有边存在的情况int n;/顶点数目int e;/边数T *a;/二维数组int *pos;template <class T>class AdjacencyDigraph:public AdjacencyWDigraph<int> public:AdjacencyDigraph(int Veryices = 10):AdjacencyWDigraph<int>(Vertices,0)AdjacencyDigraph&