数据结构实习题目

1、n n（n>20）的阶乘n 【问题描述】n 大数运算计算n的阶乘（n>=20）。n 【基本要求】n （1）数据的表示和存储；n （1.1） 累积运算的中间结果和最终的计算结果的数据类型要求是整型这是问题本身的要求；n （1.2） 试设计合适的存储结构，要求每个元素或结点最多存储数据的3位数值。 n （2）数据的操作及其实现：n 基于设计的存储结构实现乘法操作，要求从键盘上输入n值，在屏幕上显示最终计算结果。n 【测试数据】n （1）n20，n！2432902008176640000n （2）n30，n！265252859812191058636308480000000n #incl

2、ude "stdafx.h"n #include <iostream>n #include<iomanip>n using namespace std;n template <class T>n class Chain;n template <class T>n class ChainNoden n friend Chain<T>n private:n T data;n ChainNode<T> *link;n ;n template<class T>n class Chainn n pub

3、lic:n Chain() first = 0;/构造函数n Chain();/析构函数n bool IsEmpty() const return first = 0;/判断链表是否为空n int Length() const;/求链表的长度n bool Find(int k, T& x) const;/查找第k个元素n int Search(const T& x) const;/查找元素xn Chain<T>& Delete(int k, T& x);/删除第k个元素n Chain<T>& Insert(int k, const

4、 T& x);/在第k个元素之后插入xn void Output(ostream& out) const;/单链表的输出n Chain<T>& Fac(long n);n /求大数阶乘n private:n ChainNode<T> *first;/ 指向第一个节点n ;nn template<class T>n Chain<T>:Chain()n /删除所有的节点n ChainNode<T> *next; n while (first) n n next = first->link;n delete f

5、irst;n first = next;n n n template<class T>n bool Chain<T>:Find(int k, T& x) constn / 查找第k个元素，并赋值给xn if (k < 1) return false;n ChainNode<T> *current = first;n int index = 1; n while (index < k && current)n n current = current->link;n index+;n n if (current)n n

6、x = current->data;n return true;n n return false; n nn template<class T>n int Chain<T>:Search(const T& x) constn /查找元素x，返回该元素的下标n ChainNode<T> *current = first;n int index = 1; n while (current && current->data != x) n n current = current->link;n index+;n n if

7、(current) return index;n return 0;n nn template<class T>n Chain<T>& Chain<T>:Delete(int k, T& x)n / 删除第k个元素，并赋值给x，返回改变后的链表n ChainNode<T> *p = first;n if (k = 1) n first = first->link; n elsen n ChainNode<T> *q = first;n for (int index = 1; index < k - 1 &a

8、mp;& q;index+)n q = q->link;n p = q->link; n q->link = p->link;n n x = p->data;n delete p;n return *this;n n template<class T>n int Chain<T>:Length() const / 返回链表的长度n n ChainNode<T> *current = first;n int len = 0;n while (current) n n len+;n current = current->

9、;link;n n return len;n n template<class T>n Chain<T>& Chain<T>:Insert(int k, const T& x) /在第k个元素之后插入x，返回插入后的链表n n ChainNode<T> *p = first;n for (int index = 1; index < k && p;index+) n p = p->link;n ChainNode<T> *y = new ChainNode<T>n y->d

10、ata = x;n if (k) n n y->link = p->link;n p->link = y;n n else n n y->link = first;n first = y;n n return *this;n n template<class T>n void Chain<T>:Output(ostream& out) const / 输出链表元素n n ChainNode<T> *current;n int i=0,j=Length();n for (current = first; current;curr

11、ent = current->link)n n i+;n if(i=j&&j>=1)n n if(current->link)n out <<setw(3)<<setfill('0')<< current->data << " "n else n out<< current->data << " "n i=1;n j-;n current=first;n n n out<<setw(3)<<setf

12、ill('0')<<first->data<<" "n n template <class T> /重载运算符<<n ostream& operator<<(ostream& out, const Chain<T>& x)n x.Output(out); return out;nn template <class T>n Chain<T>& Chain<T>:Fac(long n) /初始化n n n int i=

13、0;n long j=n;n while(j>999)n n Insert(i,j%1000);n i+;n j=j/1000;n n Insert(i,j); /通过插入来建立链表(0,20)n /计算n long m=0, k=0;n ChainNode<T> *current;n for(;n>2;n-)n n for (current = first;current;current = current->link)/?n n m=k;n k=(current->data*(n-1)+k)/1000; /向前进位n current->data=(

14、current->data*(n-1)+m)%1000;n if(!current->link&&k>0) /?n n while(k>999)n n Insert(Length(),k%1000);n k=k/1000;n n Insert(Length(),k); /链表长度加一n k=0;n break;n n n n return *this;n n int main()n n long n;n char ch;n don n cout<<"请输入需要阶乘的数字n: "n cin>>n;n Chain&

15、lt;long> a;n a.Fac(n);n cout<<n<<"的阶乘为:"<<endl;n cout<<a;n cout<<endl;n cout<<"是否进行计算:"n cout<<endl;nn cin>>ch;n while(ch='Y');n return 0;n 2:题目：表达式求值v 要求：实现关键§ 栈的使用§ 两位数以上、负数、小数点？v 实现方式§ 控制台程序§ MFC对话框

16、#include "stdafx.h"#include <iostream>using namespace std;#include<assert.h>#include <cstdlib>#include <math.h>template<class T>class Stackpublic:Stack(int sz=50);Stack()deleteelements;void Push(const T &x); /压入栈bool Pop(T&x);/弹出栈T GetTop(void)const;/取

17、栈顶元素bool IsEmpty()constreturn(top=-1)?true:false;bool IsFull()/判断栈是否满return (top=MaxSize-1)?true:false;int GetSize()const/?return top+1;void MakeEmpty()top=-1;private:T *elements;int top;int MaxSize;void overflowProcess();/栈溢出处理;template<class T>Stack<T>:Stack(int sz)top=-1;MaxSize=sz;el

18、ements=new TMaxSize;/创建栈的数组空间assert(elements!=NULL);/判断动态内存是否分配成功是否template<class T>void Stack<T>:Push(const T&x)if(IsFull()=true)overflowProcess();top+;elementstop=x;template<class T>bool Stack<T>:Pop(T&x)if(IsEmpty()=true)return false;x=elementstop-;return true;temp

19、late<class T>T Stack<T>:GetTop(void)const/返回栈顶元素if(IsEmpty()=true)cerr<<"栈为空!"<<endl;exit(1);return elementstop;template<class T>void Stack<T>:overflowProcess() /溢出处理T *newArray=new T2*MaxSize; /扩充栈的空间for(int i=0;i<=top;i+)MaxSize=2*MaxSize;newArrayi=

20、elementsi;deleteelements;/释放原来旧的空间class Calculater/计算的声明public:Calculater()void Run();/执行表达式计算void Clear();/清空处理private:Stack<double>s;/声明double型的栈对象void AddOperand(double value);/把数值压入栈中bool GetOperand(double &left,double& right);/判断取操作数操作是否成功void DoOperator(char ch);/进行操作;void Calcul

21、ater:AddOperand(double value)s.Push(value);bool Calculater:GetOperand(double&left,double&right)if(s.IsEmpty()=true)cerr<<"缺少右操作数"<<endl;return false;s.Pop(right);if(s.IsEmpty()=true)cerr<<"缺少左操作数"<<endl;return false;s.Pop(left);return true;void Cal

22、culater:Clear()s.MakeEmpty();void Calculater:DoOperator(char ch)double left,right,value;bool result;result=GetOperand(left,right);if(result=true)switch(ch)case'+':value=left+right;s.Push(value);break;case'-':value=left-right;s.Push(value);break;case'*':value=left*right;s.Push

23、(value);break;case'/':if(right=0.0)cerr<<"Divide by 0!"<<endl;Clear();elsevalue=left/right;s.Push(value);break;cout<<"="<<s.GetTop()<<" "else Clear();void Calculater:Run()char ch;double newOperand;while(cin>>ch,ch!='#'

24、)switch(ch) case '+':case'-':case'*':case'/':/是操作数，执行计算DoOperator(ch);break;default: /其实也是一种case，只不过就是指“除了指定的几个case以外的其他情况”，不是操作符cin.putback(ch);/字符放回输入流cin>>newOperand;/重新读取操作数，一个操作数的第一个字符AddOperand(newOperand);/将操作数放入栈中int main()Calculater call;cout<<&qu

25、ot;输入计算表达式:"call.Run();return 0;3.题目:v 题目：二叉树基本算法的实现v 功能要求：v 键盘输入二叉树结点序列，创建一棵二叉树v 实现SwapTree方法，以根结点为参数，交换每个结点的左子树和右子树（提示：前序递归）v 实现Find方法，查找值为key的结点，并输出该结点的所有祖先结点v 你可以选择：v 对BinaryTree模板进行功能扩充；v 自己定义并实现二叉树类v 要求键盘输入二叉树结点序列v 结点序列可以是前序，也可以是层次v 空结点以#表示 /binarytree.h#ifndef BINARYTREE_H#define BINARYT

26、REE_H#include<iostream.h>template<class T>class BinaryTreeNode/二叉树结点/friend 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;Righ

27、tChild=r;public:T data;BinaryTreeNode<T>*LeftChild,*RightChild;template<class T>class BinaryTreefriend BinaryTreeNode<T>public:BinaryTree()root=0;BinaryTree()bool IsEmpty()constreturn (root)?false:true);void Creat();void PreOrder(void (*Visit)(BinaryTreeNode<T>*u)/前序遍历 PreOrd

28、er(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)/层次遍历 PreOrder(Output,root); cout<<endl;void InOutput()/中序输出InOr

29、der(Output,root); cout<<endl;void Postput()/后序输出 PostOrder(Output,root); cout<<endl;void LevelOutPut()/层次输出LevelOrder(Output);cout<<endl;int Height()const/计算树的高度return Height(root);int Size()const/计算树的大小return Size(root);BinaryTreeNode<T>*iCreat();void swap()/交换左右节点swap(root)

30、;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>*u),BinaryTreeNode<T>*t);void PostOrder(voi

31、d(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);/void LevelOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);static void Output(BinaryTreeNode<T>* t)/输出树的所有节点cout<<t->data <<" "int Height(BinaryTreeNode<T>*t)const;int Size(B

32、inaryTreeNode<T>*t)const; void swap(BinaryTreeNode<T>*t);int leave(BinaryTreeNode<T>*t);int noleave(BinaryTreeNode<T>*t);template<class T>int BinaryTree<T>:Height(BinaryTreeNode<T>*t)constif(!t) return 0;int hl=Height(t->LeftChild);int hr=Height(t->Rig

33、htChild);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<T>:iCrea

34、t( ) 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->root = iCr

35、eat();template<class T>void BinaryTree<T>:PreOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t)if(t) Visit(t);PreOrder(Visit,t->LeftChild);PreOrder(Visit,t->RightChild);template<class T> void BinaryTree<T>:InOrder(void(*Visit)(BinaryTreeNode<T&g

36、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(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t)if(t)PostOrder(Visit,t->LeftChild);PostOrder(Visit,t->RightCh

37、ild);Visit(t);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(t->LeftChild);swap(t->RightChild);template<class T>int BinaryTree

38、<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>int BinaryTree<T>:noleave(BinaryTreeNode<T> *t)if(!t) return 0

39、;if(!t->LeftChild&&!t->RightChild)return 1;int leafl=noleave(t->LeftChild);int leafr=noleave(t->RightChild);return leafl+leafr+1;#endif #include "stdafx.h"#include"binarytree.h"#include <iostream.h>void main() cout<<"输入二叉树:"<<endl;B

40、inaryTree<char> Tree;Tree.Creat();/cout<<"前序遍历:"/Tree.PreOutput();cout<<"中序遍历:"Tree.InOutput();cout<<"后序遍历:"Tree.Postput();cout<<"二叉树的叶节点数目为:"cout<<Tree.leave()<<endl;Tree.swap();cout<<"交换前序遍历:"/Tree.Pr

41、eOutput();实习题目4.v 任务：输入一棵二叉树的前序遍历序列和中序遍历序列，重构这棵二叉树v 功能要求：Ø 在题目三的基础之上，增加一个方法，重构这棵二叉树Ø 要求以图示效果，层次输出这棵二叉树/bintree.h #ifndef BINTREE_H#define BINTREE_H#include<iostream.h>#include"queue.h"template<class T>class BinaryTree;template<class T>/二叉树的二叉链表class BinaryTreeNo

42、defriend 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;temp

43、late<class T>class BinaryTreepublic:BinaryTree()/构造函数 空树root=0;BinaryTree()bool IsEmpty()constreturn (root)?false:true);/void BinaryTree<T>:LevelOrder(void(* Visit)(BinaryTreeNode<T>*u);void LevelOrder(void(BinaryTree<T>:* Visit)(BinaryTreeNode<T>*u);/层次访问,在访问某一层结点时把下一层

44、结点记忆在队列（尾）中，然后在访问在队头的结点void LevelOutPut()if(!root)/空树return;cout<<root->data;LevelOrder(Output);cout<<endl;BinaryTreeNode<T>*createBinaryTree(T *VLR,T*LVR,int n)/构造二叉树前 中 n为元素个数if(n=0)return NULL;int k=0;while(VLR0!=LVRk)/在中序前序结合找根k+;BinaryTreeNode<T>*t=new BinaryTreeNode&

45、lt;T>(VLR0);/根结点为tt->LeftChild=createBinaryTree(VLR+1,LVR,k);/从前序VLR+1开始对中序0k-1左子序列的k个元素递归建立左子树t->RightChild=createBinaryTree(VLR+k+1,LVR+k+1,n-k-1);/从前序VLR+k+1开始对中序k+1n-1左子序列的n-k-1个元素递归建立右子树return t; BinaryTreeNode<T>*root;void Output(BinaryTreeNode<T>* t)if(t->LeftChild|t-&

46、gt;RightChild)/左或又子树不为空if(t->LeftChild)cout<<t->LeftChild->data;elsecout<<"#"if(t->RightChild)cout<<t->RightChild->data;elsecout<<"#"template<class T>void BinaryTree<T>:LevelOrder(void (BinaryTree<T>:*Visit)(BinaryTreeNo

47、de<T> *u)/void BinaryTree<T>:LevelOrder(void(* Visit)(BinaryTreeNode<T>*u)LinkedQueue<BinaryTreeNode<T>*>Q;BinaryTreeNode<T> *p=root;Q.EnQueue(p);/根节点进队while(!Q.IsEmpty ()Q.DeQueue(p);/根节点出队(this->*Visit)(p);/访问根结点if(p->LeftChild!=NULL)Q.EnQueue(p->LeftCh

48、ild);/左子女进队if(p->RightChild!=NULL)Q.EnQueue(p->RightChild); /右子女进队#endif/queqe.h#ifndef QUEQE_H#define QUEQE_H/单链表的链式队列template<class T>class LinkedQueue;template<class T>class Nodefriend LinkedQueue<T>private:T data;Node<T>*link;template<class T>class LinkedQueue

49、 public:LinkedQueue()/构造函数front=rear=0;/建立空队列LinkedQueue();/析构函数bool IsEmpty()constreturn (front)?false:true);LinkedQueue<T>&EnQueue(const T &x);/往队尾队列中插入元素LinkedQueue<T>&DeQueue(T&x);/从队头删除元素private:Node<T>*front;Node<T>*rear;template<class T>LinkedQueu

50、e<T>:LinkedQueue()/析构函数的实现Node<T>*next;while(front)next=front->link;delete front;front=next;template<class T>LinkedQueue<T>&LinkedQueue<T>:EnQueue(const T &x)Node<T>*p=new Node<T>p->data=x;p->link=0; if (front) rear->link=p;/在列尾添加新的结点 els

51、e/队列为空，新结点成为第一个结点 front=p;rear=p;return *this;template<class T>LinkedQueue<T>&LinkedQueue<T>:DeQueue( T&x)/队头结点删去Node<T>*p=front;/暂存队头结点x=front->data;front=front->link;/队头修改delete p;return*this;#endif#include "stdafx.h"#include"binarytree.h"#

52、include <iostream.h>void main()BinaryTree<char> Tree;/char 类型的int n;cout<<"二叉树中元素个数:"cin>>n;char *L=new charn; char *R=new charn;cout<<"前序序列为:"int i=0,j=0;while(i<n)cin>>Li;i+;cout<<"中序序列为:"while(j<n)cin>>Rj;j+;Tree.

53、root=Tree.createBinaryTree(L,R,n); cout<<"层次遍历:"Tree.LevelOutPut();deleteL;deleteR;实习题目5.最优二叉树v 基本要求：对Huffman树的方法进行扩充，实现如下功能：v 1）键盘输入一个字符串，统计每个字符出现的频率；v 2）输出每个字符的Huffman编码v 3）计算并输出WPLv 提高要求：改键盘输入为读文件（任何类型）/huffmantree.h#ifndef HUFFMANTREE_H#define HUFFMANTREE_H#include <iostream.h>#include "minheap.h"#include <stdlib.h>/const int MaxN = 100;template <class Type> class HuffmanTree;template <class Type> class HuffmanTreeNode/树结点的类定义 /friend class HuffmanTree; public: i