大数据结构实习题目

1、实用文档n ( n>20)的阶乘【问题描述】大数运算计算 n的阶乘(n>=20).【根本要求】(1)数据的表示和存储；(1.1) 累积运算的中间结果和最终的计算结果的数据类型要求是整型一一这 是问题本身的要求；(1.2) 试设计适宜的存储结构,要求每个元素或结点最多存储数据的3位数 值.(2 )数据的操作及其实现：基于设计的存储结构实现乘法操作,要求从键盘上输入n值,在屏幕上显示最终计算结果.【测试数据】(1) n = 20, n!= 2432902021176640000(2) n=30, n!= 265252859812191058636308480000000#i nclud

2、e "stdafx.h"#i nclude <iostream>#in clude<ioma nip> using n amespace std; template <class T> class Cha in;template <class T>class ChainN odefriend Chain< T>private:T data;Chai nN ode<T> *li nk;template<class T>class Chai npublic:/构造函数/析构函数/判断链表是否为空

3、/求链表的长度/查找第k个元素/查找元素x/删除第k个元素/在第k个元素之后/单链表的输出Chai n() first = 0;Chai n();bool lsEmpty() const retur n first = 0; int Len gth() con st;bool Fi nd(i nt k, T& x) const; int Search(c onst T& x) con st;Chai n<T>& Delete(i nt k, T& x);Chai n<T>& In sert(i nt k, con st T&

4、; x); 插入xvoid Output(ostream& out) con st;Chai n<T>& Fac(lo ng n); /求大数阶乘private:/指向第一个节点Chai nN ode<T> *first;template<class T>Chai n< T>:Chai n()删除所有的节点Chai nN ode<T> *n ext;while (first)n ext = first->li nk;delete first;first = n ext;template<class T>

5、;bool Chai n< T>:Fi nd(i nt k, T& x) con st/查找第k个元素,并赋值给 xif (k < 1) return false;ChainN ode<T> *curre nt = first;int in dex = 1;while (in dex < k && curre nt)curre nt = curre nt->li nk;in dex+;if (curre nt)x = curre nt->data;return true;return false;template<c

6、lass T>int Chain< T>:Search(c onst T& x) const/查找元素x,返回该元素的下标ChainN ode<T> *curre nt = first;int in dex = 1;while (curre nt && curre nt->data != x)curre nt = curre nt->li nk;in dex+;if (curre nt) retur n in dex;return 0;template<class T>Chai n<T>& Cha

7、i n< T>:Delete(i nt k, T& x)/删除第k个元素,并赋值给x,返回改变后的链表Chai nN ode<T> *p = first;if (k = 1)first = first->li nk;elseChai nN ode<T> *q = first;for (int in dex = 1; in dex < k - 1 && q;i ndex+)q = q->li nk;p = q->li nk;q->li nk = p->li nk;x = p->data;dele

8、te p;return *this;template<class T>int Chai n<T>:Le ngth() con st/返回链表的长度ChainN ode<T> *curre nt = first;int len = 0;while (curre nt)len+;curre nt = curre nt->li nk;return len;template<class T>Chai n<T >& Chai n<T>:l nsert(i ntk, con st T& x) / 在第 k 个元素

9、之后插入 x,返回插入后的链表Chai nN ode<T> *p = first;for (int in dex = 1; in dex < k && p;i ndex+)p = p->li nk;Chai nN ode<T> *y = new Chai nN ode<T>y->data = x;if (k)y->li nk = p->li nk;p->li nk = y;elsey->li nk = first;first = y;return *this;template<class T&g

10、t;void Chai n<T>:Output(ostrea m& out) const /输出链表元素ChainN ode<T> *curre nt;int i=O,j=Le ngth();for (curre nt = first; curre nt;curre nt = curre nt->li nk)i+;if(i=j &&j>=1)if(curre nt->li nk)out <<setw (3)<<setfill('0')<< curre nt->data &

11、lt;< "" elseout<< curre nt->data << ""i=1;j-;curre nt=first;out<<setw (3) <<setfill('0')<<first->data<<""template <class T> /重载运算符 <<ostream& operator<<(ostrea m& out, const Chain<T>&am

12、p; x)x.Output(out); return out;template <class T>Chai n<T>& Cha in< T>:Fac(lo ng n) /初始化int i=0;long j=n;while(j>999)In sert(i,j%1000);i+；j=j/1000;In sert(i,j);/通过插入来建立链表 (0,20)/计算long m=0, k=0;ChainN ode<T> *curre nt;for(; n> 2; n-)for (curre nt = first;curre nt;cu

13、rre nt = curre nt->li nk)？m=k;k=(curre nt->data*( n-1)+k)/1000; /向前进位curren t->data=(curre nt->data*( n-1)+m)%1000;if(!curre nt->li nk&&k>0)/?while(k>999)In sert(Le ngth(),k%1000);k=k/1000;In sert(Le ngth(),k);/链表长度加一k=0;break;return *this;int mai n()long n;char ch;docou

14、t<<"请输入需要阶乘的数字n:"cin»n;Chain<long> a;a.Fac( n);cout<<*<"的阶乘为:"<<endl;cout<<a;cout<<e ndl;cout<<"是否进行计算："；cout<<e ndl;cin> >ch;while(ch='Y');return 0;2:题目：表达式求值要求：实现关键栈的使用两位数以上、负数、小数点？ 实现方式限制台程序MFC对话框#

15、i nclude "stdafx.h"#in clude <iostream>using n amespace std;#in clude<assert.h>#in clude <cstdlib>#in clude <math.h>template<class T>class Stackpublic:Stack(i nt sz=50);Stack() deleteeleme nts;void Push(co nst T &x); / 压入栈bool Pop(T&x);/ 弹出栈T GetTop(vo

16、id)const;/ 取栈顶元素bool lsEmpty()c onst return(top=-1)?true:false;bool lsFull()判断栈是否满return (top=MaxSize-1)?true:false;int GetSize()co nst/?retur n top+1;void MakeEmpty()top=-1;private:T *eleme nts;int top;int MaxSize;void overflowProcess();栈溢出处理template<class T> Stack<T>:Stack(i nt sz) top

17、=-1;MaxSize=sz;eleme nts=new TMaxSize; assert(eleme nts!=NULL);template<class T>void Stack<T>:Push(co nst T&x) if(lsFull()=true)overflowProcess();top+;eleme ntstop=x;template<class T>bool Stack<T>:Pop(T &x)创立栈的数组空间判断动态内存是否分配成功是否if(IsEmpty()=true)return false;x=eleme n

18、tstop-; return true;template<class T>T Stack<T>:GetTop(void)co nst/返回栈顶元素if(lsEmpty()=true)cerr<<"栈为空!"<<endl; exit(1);return eleme ntstop;template<class T>void Stack<T>:overflowProcess() /溢出处理T *n ewArray=new T2*MaxSize; /扩充栈的空间for(i nt i=O;i<=top;i+

19、)MaxSize=2*MaxSize;n ewArrayi=eleme ntsi;deleteeleme nts;释放原来旧的空间class Calculater/ 计算的声明public:Calculater()void Run ();/执行表达式计算void Clear();/ 清空处理private:Stack<double>s;/ 声明 double 型的栈对象void AddOpera nd(double value);/把数值压入栈中bool GetOpera nd(double & left,double & right);/判断取操作数操作是否成功v

20、oid DoOperator(char ch);/进行操作;void Calculater:AddOpera nd(double value)s.Push(value);bool Calculater:GetOpera nd(double&left,double&right)if(ssEmpty()=true)cerr<<"缺少右操作数"<<endl;return false;s.Pop(right);if(s.lsEmpty()=true) cerr<<"缺少左操作数"<<endl; re

21、turn false;s.Pop(left);return true;void Calculater:Clear()s.MakeEmpty();void Calculater:DoOperator(char ch)double left,right,value;bool result;result=GetOpera nd(left,right);if(result=true)switch(ch)case'+':value=left+right;s.Push(value);break;case'-':value=left-right;s.Push(value);b

22、reak;case'*':value=left*right;s.Push(value);break;case'/':if(right=0.0)cerr<<"Divide by 0!"<<e ndl; Clear();elsevalue=left/right; s.Push(value);break;cout<<"="<<s.GetTop()<<""elseClear();void Calculater:R un()char ch;double

23、n ewOpera nd;while(ci n>> ch,ch!='#')switch(ch)case '+':case'-':case'*':case7':是操作数,执行计算DoOperator(ch);break;default: / 其实也是一种case,只不过就是指“除了指定的几个case以外的其他情况,不是操作符cin. putback(ch);/字符放回输入流cin>>n ewOpera nd;/重新读取操作数,一个操作数的第一个字符AddOpera nd( newOpera nd);/

24、 将操作数放入栈中int mai n()Calculater call;cout<<"输入计算表达式："；call.Ru n();return 0;3.题目:题目：二叉树根本算法的实现功能要求：键盘输入二叉树结点序列,创立一棵二叉树实现SwapTree方法,以根结点为参数,交换每个结点的左子树和右子树 (提 示：前序递归)实现Find方法,查找值为key的结点,并输出该结点的所有祖先结点你可以选择：对BinaryTree模板进行功能扩充；自己定义并实现二叉树类要求键盘输入二叉树结点序列结点序列可以是前序,也可以是层次 空结点以#表示/bi narytree.h#

25、ifndef BINARYTREE_H#defi ne BINARYTREE_H#in clude<iostream.h>template<class T>class Bin aryTreeNode/二叉树结点/friend Bin aryTree<T>public:Bin aryTreeNode()LeftChild=RightChild=0;Bin aryTreeNode(c onst T&e)data=e;LeftChild=RightChild=0;Bin aryTreeNode(c onst T&e,Bi naryTreeNode

26、*l,Bi naryTreeNode *r)data=e;LeftChild=l; RightChild=r;public:T data;Bin aryTreeNode<T>*LeftChild,*RightChild;template<class T>class Bin aryTreefriend Bin aryTreeNode<T>public:Bin aryTree()root=0;Bi naryTree()bool IsEmpty()c onstreturn (root)?false:true);void Creat();void PreOrder(

27、void (*Visit)(Bi naryTreeNode<T>*u)前序遍历PreOrder(Visit,root);void InO rder(void (*Visit)(Bi naryTreeNode<T>*u)In Order(Visit,root);void PostOrder(void (*Visit)(Bi naryTreeNode<T>*u)PostOrder(Visit,root);void LevelOrder(void(*Visit)(Bi naryTreeNode<T>*u)PreOrder(Output,root);co

28、ut<<e ndl;void InO utput() 中序输出In Order(Output,root);cout<<e ndl;void Postput()后序输出PostOrder(Output,root);cout<<e ndl;void LevelOutPut()层次输出LevelOrder(Output);cout<<e ndl;int Height()c on st/计算树的高度return Height(root);int Size()co nst计算树的大小return Size(root);Bin aryTreeNode<

29、T>*iCreat();void swap()交换左右节点中序遍历后序遍历层次遍历swap(root);实用文档int leave()计算叶子节点个数return leave(root);int noleave()/计算非叶子节点个数retur n no leave(root);private:Bin aryTreeNode<T>*root;void PreOrder(void(*Visit)(B in aryTreeNode<T>*u),B in aryTreeNode<T>*t); void InO rder(void(*Visit)(Bi nar

30、yTreeNode<T>*u),Bi naryTreeNode<T>*t);void PostOrder(void(*Visit)(Bi naryTreeNode<T>*u),Bi naryTreeNode<T>*t); /void LevelOrder(void(*Visit)(Bi naryTreeNode<T>*u),Bi naryTreeNode<T>*t); static void Output(B in aryTreeNode<T>* t)/输出树的所有节点cout<<t->dat

31、a <<""int Height(B in aryTreeNode<T>*t)c on st;int Size(B in aryTreeNode<T>*t)c on st;void swap(B in aryTreeNode<T>*t);int leave(B in aryTreeNode<T>*t);int no leave(B in aryTreeNode<T>*t);template<class T>int Bin aryTree<T>:Height(B in aryTre

32、eNode<T>*t)c onstif(!t) return 0;int hl=Height(t->LeftChild);int hr=Height(t->RightChild);if(hl>hr) retur n +hl;else retur n +hr;template<class T>int Bin aryTree<T>:Size(B in aryTreeNode<T>*t)c onstif(!t) return 0;int sl=Size(t->LeftChild);int sr=Size(t->RightC

33、hild);return (1+sl+sr);Bin aryTreeNode<T>*B in aryTree<T>:iCreat()T ch;cin> >ch;Bin aryTreeNode<T> * root;if(ch='#')root=NULL;elseroot =new Bin aryTreeNode<T>root->data=ch;root->LeftChild=this->iCreat();root->RightChild=this->iCreat();return root;

34、template<class T>void Bi naryTree<T>:Creat()this->root = iCreat();template<class T>voidBin aryTree<T>:PreOrder(void(*Visit)(Bi naryTreeNode<T>*u),Bi naryTreeNode<T>*t)if(t)Visit(t);PreOrder(Visit,t->LeftChild);PreOrder(Visit,t->RightChild);template<cla

35、ss T>实用文档voidBin aryTree<T>:l nO rder(void(*Visit)(Bi naryTreeNode<T>*u),Bi naryTreeNode<T>*t)if(t)In Order(Visit,t->LeftChild);Visit(t);In Order(Visit,t->RightChild);template<class T>voidBin aryTree<T>:PostOrder(void(*Visit)(Bi naryTreeNode<T>*u),Bi nary

36、TreeNode<T>*t)if(t)PostOrder(Visit,t->LeftChild);PostOrder(Visit,t->RightChild);Visit(t);template<class T>void Bin aryTree<T>:swap(B in aryTreeNode<T> *t)Bin aryTreeNode<T> *temp;if(!t) return;elsetemp=t->LeftChild;t->LeftChild=t->RightChild;t->RightCh

37、ild=temp;sw ap(t->LeftChild);sw ap(t->RightChild);template<class T>int Bin aryTree<T>:leave(B in aryTreeNode<T>*t)if(!t) return 0;if(t->LeftChild=0&&t->RightChild=O)return 1;int leafl=leave(t->LeftChild);int leafr=leave(t->RightChild);retur n leafl+leafr;t

38、emplate<class T>int Bin aryTree<T>: no leave(B in aryTreeNode<T> *t) if(!t) return 0;if(!t->LeftChild&&!t->RightChild)return 1;int leafl=noleave(t->LeftChild);int leafr=no leave(t->RightChild);retur n leafl+leafr+1;#en dif#i nclude "stdafx.h"#i nclude&

39、quot;bi narytree.h"#in clude <iostream.h>void mai n()cout<<"输入二叉树:"<<endl;Bin aryTree<char> Tree;Tree.Creat();cout<<"前序遍历:"/Tree.PreOutput(); cout<<"中序遍历:"Tree.I nO utput();cout<<"后序遍历:"Tree.Postput();cout<<

40、"二叉树的叶节点数目为："；cout<<Tree .l eave()<<e ndl;Tree.swap();cout<<"交换前序遍历："；/Tree.PreOutput();实习题目4.任务：输入一棵二叉树的前序遍历序列和中序遍历序列,重构这棵二叉树 功能要求：在题目三的根底之上,增加一个方法,重构这棵二叉树 要求以图示效果,层次输出这棵二叉树/bi ntree.h#ifndef BINTREE_H#defi ne BINTREE_H#in clude<iostream.h>#in clude"

41、queue.h"template<class T>class Bin aryTree;template<class T>/二叉树的二叉链表class Bin aryTreeNodefriend Bin aryTree<T>public:Bin aryTreeNode()LeftChild=RightChild=0;构造函数Bin aryTreeNode(c onst T&e)data=e;LeftChild=RightChild=0;Bin aryTreeNode(c onst T&e,Bi naryTreeNode *l,Bi n

42、aryTreeNode *r)data=e;LeftChild=l;RightChild=r;private:T data;Bin aryTreeNode<T>*LeftChild,*RightChild;template<class T>class Bin aryTreepublic:Bin aryTree()/构造函数空树root=0;Bi naryTree()bool IsEmpty()c onstreturn (root)?false:true);/void Bin aryTree<T>:LevelOrder(void(* Visit)(Bi nar

43、yTreeNode<T>*u);void LevelOrder(void(B in aryTree<T>:* Visit)(B in aryTreeNode<T>*u);层次访问,在访问某一层结点时把下一层结点记忆在队列(尾)中,然后在访问在队头的结点void LevelOutPut()if(!root)空树return;cout<<root->data;LevelOrder(Output);cout<<e ndl;Bin aryTreeNode<T>*createBi naryTree(T *VLR,T*LVR,i

44、 nt n)构造二叉树前中 n为元素个数if(n=0)return NULL;int k=0;while(VLRO!=LVRk)在中序前序结合找根k+;BinaryTreeNode<T>*t =new BinaryTreeNode<T>(VLR0);根结点为 tt->LeftChild=createBinaryTree(VLR+1,LVR,k);从前序 VLR+1 开始对中序0k-1左子序列的k个元素递归建立左子树t->RightChild=createBi naryTree(VLR+k+1, LVR+k+1, n-k-1);从前序 VLR+k+1开始对中序

45、k+1n-1左子序列的n-k-1个元素递归建立右子树return t;Bin aryTreeNode<T>*root;void Output(B in aryTreeNode<T>* t)if(t->LeftChild|t->RightChild)左或又子树不为空if(t->LeftChild)cout<<t->LeftChild->data;elsecout<<"#"if(t->RightChild)cout<<t->RightChild->data;elsecou

46、t<<"#"template<class T>voidBin aryTree<T>:LevelOrder(void(Bin aryTree<T>:*Visit)(Bi naryTreeNode<T> *u)/void Bin aryTree<T>:LevelOrder(void(* Visit)(Bi naryTreeNode<T>*u)Lin kedQueue<Bi naryTreeNode<T>*>Q;Bin aryTreeNode<T> *p=roo

47、t;Q.E nQueue(p);/根节点进队while(!Q.lsEmpty ()Q.DeQueue(p);/根节点出队(this->*Visit)(p);/访问根结点if(p->LeftChild!=NULL)Q.E nQueue(p->LeftChild); 左子女进队if(p->RightChild!=NULL)Q.E nQueue(p->RightChild); /右子女进队#en dif/queqe.h#ifndef QUEQE_H#define QUEQE_H单链表的链式队列template<class T>class Lin kedQue

48、ue;template<class T>class Nodefriend Lin kedQueue<T>private:T data;Node<T>*li nk;template<class T>class Lin kedQueuepublic:LinkedQueue()/ 构造函数fron t=rear=0;/建立空队列LinkedQueue();/ 析构函数实用文档bool lsEmpty()c onstreturn (fro nt)?false:true);Li nkedQueue<T >&En Queue(co nst

49、 T &x);往队尾队列中插入元素LinkedQueue<T>&DeQueue(T&x); 从队头删除元素private:Node<T>*fro nt;Node<T>*rear;template<class T>Li nkedQueue<T>:Li nkedQueue()析构函数的实现Node<T>* next;while(fr ont)n ext=fr on t->li nk;delete front;front=n ext;template<class T>Lin kedQue

50、ue<T >&Lin kedQueue<T>:E nQueue(c onst T &x)Node<T>*p=new Node<T>p->data=x;p->li nk=0;if (front) rear->li nk=p;在列尾添加新的结点else/队列为空,新结点成为第一个结点fron t=p;rear=p;return *this;template<class T>Li nkedQueue<T >&Li nkedQueue<T>:DeQueue( T& x)

51、队头结点删去Node<T>*p=fro nt;暂存队头结点实用文档x=fron t->data;fron t=fro nt->li nk;队头修改delete p;return*this;#en dif#i nclude "stdafx.h"#i nclude"bi narytree.h"#in clude <iostream.h>void mai n()Bin aryTree<char> Tree;/char类型的int n;cout<<"二叉树中元素个数："；cin

52、87;n;char *L=new char n;char *R=new char n;cout<<"前序序列为:"int i=0,j=0;while(i< n)cin> >Li;i+;cout<<"中序序列为:"while(j< n)ci n»Rj;j+;Tree.root=Tree.createBi naryTree(L,R, n);cout<<"层次遍历:"Tree.LevelOutPut();deleteL;deleteR;实习题目5.最优二叉树根本要求：对

53、Huffman树的方法进行扩充,实现如下功能:1) 键盘输入一个字符串,统计每个字符出现的频率；2) 输出每个字符的Huffman编码3) 计算并输出WPL提升要求：改键盘输入为读文件(任何类型)实用文档/huffma ntree.h#ifndef HUFFMANTREE_H#defi ne HUFFMANTREE_H#in elude <iostream.h>#in clude "min heap.h"#i nclude <stdlib.h>con st int MaxN = 100;template <class Type>class

54、 Huffma nTree;template <class Type>class Huffma nTreeNode/树结点的类定义/friend class Huffma nTree;public:int arrkey;Type data;/结点数据Huffma nTreeNode <Type> *leftChild, *rightChild, *pare nt;template <class Type>class Huffma nCodeNode/friend class Huffma nTree;public:Huffma nTreeNode <T

55、ype> *dataptr;int bitMaxN;int start;template <class Type>class Huffma nTree/friend class Huffma nTreeNode;/friend class Huffma nCodeNode;public:Huffma nTree();Huffma nTree(Type weight, i nt n);HuffmanCode();求 huffman 编码protected:Huffma nTreeNode <Type> *hfTree;Huffma nCodeNode <Typ

56、e> *hfCode;int curre ntSize;Huffma nTreeNodevoidMergeTree(Huffma nTreeNode<Type> &bt1,<Type >&bt2, Huffma nTreeNode <Type> *pt)/合并二叉树pt->leftChild = & bt1;实用文档pt->rightChild = & bt2;pt->data = btl.data + bt2.data;pt->pare nt = NULL;btl.pare nt = pt; b

57、t2.pare nt = pt;template <class Type>HuffmanTree <Type> : HuffmanTree(Type weighty, int n)/n个权值为 W1.Huffma nTreeNode <Type> *firstchild, *sec on dchild, *pare nt;Huffma nTreeNode <Type> *TNode;if(n > MaxN)cout<<"Error!"<<e ndl;exit(-1);curre ntSize =

58、n;hfCode = new Huffma nCodeNode <Type> n;TNode = new Huffma nTreeNode <Type> n;for(i nt i = 0;i < n ;i+)森林各颗树初始化hfCodei.dataptr = &TNodei;TNodei.data = weighti;TNodei.arrkey = i;=NULL;TNodei.pare nt= TNodei.leftChild = TNodei.rightChildMinH eap <Huffma nTreeNode <Type> > hp(TNode ,n);for(i = 0;i < n-1;i+)pare nt = new Huffma nTreeNode <Type>firstchild = hp.RemoveMi