数据结构实习题目

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

2、;stdafx.h"#include <iostream>#include<iomanip> using namespace std; template <class T> class Chain;template <class T> class ChainNode friend Chain<T>private:T data;ChainNode<T> *link;template<class T> class Chain public:/构造函数/析构函数/判断链表是否为空/求链表的长度/查找第k个元

3、素/查找元素x/删除第k个元素/在第k个元素之后插入 x/单链表的输出Chain() first = 0; Chain();bool IsEmpty() const return first = 0; int Length() const;bool Find(int k, T& x) const;int Search(const T& x) const; Chain<T>& Delete(int k, T& x); Chain<T>& Insert(int k, const T& x); void Output(ostre

4、am& out) const;Chain<T>& Fac(long n);/求大数阶乘/指向第一个节点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>bool Chain<T>:Find(int k, T&am

5、p; x) const/查找第 k个元素，并赋值给 xif (k < 1) return false;ChainNode<T> *current = first;int index = 1;while (index < k && current)current = current->link;index+;)if (current)x = current->data;return true;)return false;) template<class T>int Chain<T>:Search(const T&

6、 x) const/查找元素 x,返回该元素的下标ChainNode<T> *current = first;int index = 1;while (current && current->data != x) current = current->link;index+;)if (current) return index; return 0;) template<class T>Chain<T>& Chain<T>:Delete(int k, T& x)/删除第 k个元素，并赋值给x,返回改变后的

7、链表ChainNode<T> *p = first;if (k = 1)first = first->link; else 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;)template<class T>int Chain<T>:Le

8、ngth() const/ 返回链表的长度ChainNode<T> *current = first;int len = 0; while (current) len+;current = current->link; )return len;)template<class T>Chain<T>& Chain<T>:Insert(int k, const T& x)/ 在第 k 个元素之后插入x,返回插入后的链表ChainNode<T> *p = first;for (int index = 1; index &

9、lt; 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;)template<class T>void Chain<T>:Output(ostream& out) const/ 输出链表元素(ChainNode<T&

10、gt; *current;int i=0,j=Length();for (current = first; current;current = current->link) (i+;if(i=j&&j>=1) ( if(current->link)out <<setw(3)<<se情ll('0')<< current->data << ' elseout<< current->data << ""i=1;j;current=first

11、; ) )out<<setw(3)<<setfill('0')<<first->data<<"")template <class T> / 重载运算符 <<ostream& operator<<(ostream& out, const Chain<T>& x)x.Output(out); return out;template <class T>Chain<T>& Chain<T>:Fac(

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

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

14、out<<n<<"的阶乘为:"<<endl; cout<<a; cout<<endl;n.cout<<"是否进行计算 cout<<endl;cin>>ch;while(ch='Y'); return 0;2:题目：表达式求值要求：实现关键 栈的使用 两位数以上、负数、小数点？实现方式控制台程序MFC对话框#include "stdafx.h"#include <iostream> using namespace std;#

15、include<assert.h>#include <cstdlib>#include <math.h> template<class T> class Stack public:Stack(int sz=50);Stack() deleteelements;void Push(const T &x); 压入栈bool Pop(T&x);/ 弹出栈T GetTop(void)const; / 取栈顶元素 bool IsEmpty()const return(top=-1)?true:false; bool IsFull() 判断栈

16、是否满 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;elements=new TMaxSize;/创建栈的数组空间assert(elements!=NULL);

17、判断动态内存是否分配成功是否) 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;)template<class T>T Stack<T>:Ge

18、tTop(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=elementsi; deleteelements; 释放

19、原来旧的空间 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 Calculater:AddOperand(dou

20、ble 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 Calculater:Clear(

21、)(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(value);brea

22、k;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!='#

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

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

25、RYTREE_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;LeftChi

26、ld=l;RightChild=r; public: T data;BinaryTreeNode<T>*LeftChild,*RightChild; ; template<class T> class BinaryTree friend BinaryTreeNode<T> public: BinaryTree() root=0; BinaryTree() bool IsEmpty()const return (root)?false:true); void Creat();前序遍历void PreOrder(void (*Visit)(BinaryTreeN

27、ode<T>*u)/ PreOrder(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<<en

28、dl;)void InOutput()/中序输出(InOrder(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>*iC

29、reat();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>*u),Bin

30、aryTreeNode<T>*t);void PostOrder(void(*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 Heigh

31、t(BinaryTreeNode<T>*t)const;int Size(BinaryTreeNode<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=He

32、ight(t->LeftChild);int hr=Height(t->RightChild);if(hl>hr) return +hl;else return +hr;)template<class T>int BinaryTree<T>:Size(BinaryTreeNode<T>*t)constif(!t) return 0;int sl=Size(t->LeftChild);int sr=Size(t->RightChild);return (1+sl+sr);)template<class T>Binary

33、TreeNode<T>*BinaryTree<T>:iCreat()T ch;cin>>ch;BinaryTreeNode<T> * root;if(ch='#')(root=NULL; else(root=new BinaryTreeNode<T>root->data=ch;root->LeftChild=this->iCreat();root->RightChild=this->iCreat(); return root;template<class T>void Bina

34、ryTree<T>:Creat()(this->root = iCreat();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>

35、: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(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t) (if(t)(PostOrder(Vis

36、it,t->LeftChild);PostOrder(Visit,t->RightChild);Visit(t);)template<class T>void BinaryTree<T>:swap(BinaryTreeNode<T> *t)(BinaryTreeNode<T> *temp;if(!t) return;else(temp=t->LeftChild;t->LeftChild=t->RightChild;t->RightChild=temp;swap(t->LeftChild);swap(t-&

37、gt;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>int BinaryTree<T&

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

39、oid main()(cout<<"输入二叉树:"<<endl;BinaryTree<char> Tree;Tree.Creat();/cout<<"前序遍历：”； Tree.PreOutput();cout<<”中序遍历：”； Tree.InOutput();cout<<"后序遍历：”；Tree.Postput();cout<<"二叉树的叶节点数目为："；cout<<Tree.leave()<<endl;Tree.swap()

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

41、叉链表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;RightChild=r;private:T data;BinaryTreeNode<T>*Left

42、Child,*RightChild; ;template<class T>class BinaryTree public: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)(BinaryTreeNod

43、e<T>*u);/某一层结点时把下一层结点记忆在队列(尾)中，然后在访问在队头的结点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+; ) BinaryTre

44、eNode<T>*t=new BinaryTreeNode<T>(VLR0);/ 根结点为 t t->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

45、(BinaryTreeNode<T>* t) if(t->LeftChild|t->RightChild)左或又子树不为空 if(t->LeftChild) cout<<t->LeftChild->data; else cout<<"#" if(t->RightChild) cout<<t->RightChild->data; else cout<<"#" ) ) ); template<class T> void BinaryTree

46、<T>:LevelOrder(void (BinaryTree<T>:*Visit)(BinaryTreeNode<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);/ 根节点出队

47、(this->*Visit)(p);/访问根结点if(p->LeftChild!=NULL) Q.EnQueue(p->LeftChild);/ 左子女进队 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 Node friend LinkedQu

48、eue<T> private: T data; Node<T>*link; ; template<class T> class LinkedQueue public: LinkedQueue()/ 构造函数 front=rear=0;/建立空队列 LinkedQueue();/ 析构函数bool IsEmpty()const return (front)?false:true);LinkedQueue<T>&EnQueue(const T &x);/往队尾队列中插入元素 LinkedQueue<T>&DeQue

49、ue(T&x);/从队头删除元素private: Node<T>*front; Node<T>*rear; )； 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>:EnQueu

50、e(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>&LinkedQueue<T>:DeQueue( T&x)/队头结点删去 Node<T>*p=front;/ 暂存队头

51、结点 x=front->data; front=front->link;/队头修改delete p; return*this; ) #endif #include "stdafx.h" #include"binarytree.h"#include <iostream.h>void main()(BinaryTree<char> Tree;/char 类型的int n;cout<<"二叉树中元素个数：”；cin>>n;char *L=new charn;char *R=new charn

52、;cout<<"前序序列为："；int i=0,j=0;while(i<n)(cin>>Li;i+;cout<<"中序序列为：”；while(j<n)(cin>>Rj;j+;Tree.root=Tree.createBinaryTree(L,R,n);cout<<"层次遍历：”；Tree.LevelOutPut();deleteL;deleteR;实习题目5.最优二叉树1)基本要求：对 Huffman树的方法进行扩充，实现如下功能：键盘输入一个字符串，统计每个字符出现的频率；2)输出

53、每个字符的Huffman编码3)计算并输出 WPL提高要求：改键盘输入为读文件(任何类型)/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/

54、树结点的类定义(/friend class HuffmanTree;public:int arrkey;Type data;/结点数据HuffmanTreeNode <Type> *leftChild, *rightChild, *parent;template <class Type>class HuffmanCodeNode(/friend class HuffmanTree;public:HuffmanTreeNode <Type> *dataptr;int bitMaxN;int start;template <class Type>cl

55、ass HuffmanTree(/friend class HuffmanTreeNode;/friend class HuffmanCodeNode;public:HuffmanTree();HuffmanTree(Type weight, int n);HuffmanCode();/ 求 huffman 编码protected:HuffmanTreeNode <Type> *hfTree;HuffmanCodeNode <Type> *hfCode;int currentSize;void MergeTree(HuffmanTreeNode <Type>

56、 &bt1, HuffmanTreeNode<Type>&bt2, HuffmanTreeNode <Type> *pt)/合并二叉树pt->leftChild = &bt1;pt->rightChild = &bt2;pt->data = bt1.data + bt2.data;pt->parent = NULL;bt1.parent = pt; bt2.parent = pt;template <class Type>HuffmanTree <Type> : HuffmanTree(Ty

57、pe weight, int n)/n个权值为 W1.HuffmanTreeNode <Type> *firstchild, *secondchild, *parent;HuffmanTreeNode <Type> *TNode;if(n > MaxN) (cout<<"Error!"<<endl;exit(-1);currentSize = n;hfCode = new HuffmanCodeNode <Type> n;TNode = new HuffmanTreeNode <Type> n;f

58、or(int i = 0;i < n;i+)/森林各颗树初始化(hfCodei.dataptr = &TNodei;TNodei.data = weighti;TNodei.arrkey = i;TNodei.parent = TNodei.leftChild = TNodei.rightChild = NULL; MinHeap <HuffmanTreeNode <Type> > hp(TNode,n);for(i = 0;i < n-1;i+) (parent = new HuffmanTreeNode <Type>firstchil

59、d = hp.RemoveMin();secondchild = hp.RemoveMin();MergeTree(*firstchild, *secondchild, parent);hp.Insert(*parent);hfTree = parent;template <class Type>HuffmanTree <Type> 二 HuffmanCode()(HuffmanCodeNode <Type> *cd = new HuffmanCodeNode<Type>HuffmanTreeNode <Type> *child, *

60、parent;for(int i=0;i < currentSize;i+) (cd->start = currentSize -1;child = hfCodei.dataptr;parent = child->parent;while(parent != NULL) (if(parent->leftChild = child)/向左标记为0cd->bitcd->start = 0;elsecd->bitcd->start = 1; /向右标记为0 child = parent;parent = parent->parent;cd->

61、;start-;)for(int k=0;k < currentSize;k+)(hfCodei.bitk = cd->bitk;hfCodei.start = cd->start+1;)cout<<endl<<"输出："<<endl;for(i=0;i<currentSize;i+)cout<<hfCodei.dataptr->data<<":"for(int j=hfCodei.start;j<currentSize;j+)cout<<hfCodei.bitj;cout<<endl;)#endif/minheap.h#ifndef MINHEAP_H#define MINHEAP_Htemplate <class Type>class MinHeap/friend class Type;public:MinHeap(int maxSize);MinHeap(Type a, int n);/ 构造函数MinHe