数据结构实习题目

.n n（n20）的阶乘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 #include stdafx.hn #include n #includen using namespace std;n template n class Chain;n template n class ChainNoden n friend Chain;n private:n T data;n ChainNode *link;n ;n templaten class Chainn n public: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& Delete(int k, T& x);/删除第k个元素n Chain& Insert(int k, const T& x);/在第k个元素之后插入xn void Output(ostream& out) const;/单链表的输出n Chain& Fac(long n);n /求大数阶乘n private:n ChainNode *first;/ 指向第一个节点n ;nn templaten Chain:Chain()n /删除所有的节点n ChainNode *next; n while (first) n n next = first-link;n delete first;n first = next;n n n templaten bool Chain:Find(int k, T& x) constn / 查找第k个元素，并赋值给xn if (k 1) return false;n ChainNode *current = first;n int index = 1; n while (index link;n index+;n n if (current)n n x = current-data;n return true;n n return false; n nn templaten int Chain:Search(const T& x) constn /查找元素x，返回该元素的下标n ChainNode *current = first;n int index = 1; n while (current & current-data != x) n n current = current-link;n index+;n n if (current) return index;n return 0;n nn templaten Chain& Chain:Delete(int k, T& x)n / 删除第k个元素，并赋值给x，返回改变后的链表n ChainNode *p = first;n if (k = 1) n first = first-link; n elsen n ChainNode *q = first;n for (int index = 1; index link;n p = q-link; n q-link = p-link;n n x = p-data;n delete p;n return *this;n n templaten int Chain:Length() const / 返回链表的长度n n ChainNode *current = first;n int len = 0;n while (current) n n len+;n current = current-link;n n return len;n n templaten Chain& Chain:Insert(int k, const T& x) /在第k个元素之后插入x，返回插入后的链表n n ChainNode *p = first;n for (int index = 1; index link;n ChainNode *y = new ChainNode;n y-data = 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 templaten void Chain:Output(ostream& out) const / 输出链表元素n n ChainNode *current;n int i=0,j=Length();n for (current = first; current;current = current-link)n n i+;n if(i=j&j=1)n n if(current-link)n out setw(3)setfill(0)data ;n else n outdata ;n i=1;n j-;n current=first;n n n outsetw(3)setfill(0)data ;n n template /重载运算符n ostream& operator(ostream& out, const Chain& x)n x.Output(out); return out;nn template n Chain& Chain:Fac(long n) /初始化n n n int i=0;n long j=n;n while(j999)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 *current;n for(;n2;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=(current-data*(n-1)+m)%1000;n if(!current-link&k0) /?n n while(k999)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 coutn;n Chain a;n a.Fac(n);n coutn的阶乘为:endl;n couta;n coutendl;n cout是否进行计算:;n coutch;n while(ch=Y);n return 0;n 2:题目：表达式求值v 要求：实现关键 栈的使用 两位数以上、负数、小数点？v 实现方式 控制台程序 MFC对话框#include stdafx.h#include using namespace std;#include#include #include templateclass Stackpublic:Stack(int sz=50);Stack()deleteelements;void Push(const T &x); /压入栈bool Pop(T&x);/弹出栈T GetTop(void)const;/取栈顶元素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();/栈溢出处理;templateStack:Stack(int sz)top=-1;MaxSize=sz;elements=new TMaxSize;/创建栈的数组空间assert(elements!=NULL);/判断动态内存是否分配成功是否templatevoid Stack:Push(const T&x)if(IsFull()=true)overflowProcess();top+;elementstop=x;templatebool Stack:Pop(T&x)if(IsEmpty()=true)return false;x=elementstop-;return true;templateT Stack:GetTop(void)const/返回栈顶元素if(IsEmpty()=true)cerr栈为空!endl;exit(1);return elementstop;templatevoid Stack:overflowProcess() /溢出处理T *newArray=new T2*MaxSize; /扩充栈的空间for(int i=0;i=top;i+)MaxSize=2*MaxSize;newArrayi=elementsi;deleteelements;/释放原来旧的空间class Calculater/计算的声明public:Calculater()void Run();/执行表达式计算void Clear();/清空处理private:Stacks;/声明double型的栈对象void AddOperand(double value);/把数值压入栈中bool GetOperand(double &left,double& right);/判断取操作数操作是否成功void DoOperator(char ch);/进行操作;void Calculater: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 Calculater: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(value);break;case/:if(right=0.0)cerrDivide by 0!endl;Clear();elsevalue=left/right;s.Push(value);break;cout=s.GetTop()ch,ch!=#)switch(ch) case +:case-:case*:case/:/是操作数，执行计算DoOperator(ch);break;default: /其实也是一种case，只不过就是指“除了指定的几个case以外的其他情况”，不是操作符cin.putback(ch);/字符放回输入流cinnewOperand;/重新读取操作数，一个操作数的第一个字符AddOperand(newOperand);/将操作数放入栈中int main()Calculater call;cout输入计算表达式:;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 BINARYTREE_H#includetemplateclass BinaryTreeNode/二叉树结点/friend BinaryTree;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;public:T data;BinaryTreeNode*LeftChild,*RightChild;templateclass BinaryTreefriend BinaryTreeNode;public:BinaryTree()root=0;BinaryTree()bool IsEmpty()constreturn (root)?false:true);void Creat();void PreOrder(void (*Visit)(BinaryTreeNode*u)/前序遍历 PreOrder(Visit,root);void InOrder(void (*Visit)(BinaryTreeNode*u)/中序遍历InOrder(Visit,root);void PostOrder(void (*Visit)(BinaryTreeNode*u)/后序遍历PostOrder(Visit,root);void LevelOrder(void(*Visit)(BinaryTreeNode*u)/层次遍历 PreOrder(Output,root); coutendl;void InOutput()/中序输出InOrder(Output,root); coutendl;void Postput()/后序输出 PostOrder(Output,root); coutendl;void LevelOutPut()/层次输出LevelOrder(Output);coutendl;int Height()const/计算树的高度return Height(root);int Size()const/计算树的大小return Size(root);BinaryTreeNode*iCreat();void swap()/交换左右节点swap(root);int leave()/计算叶子节点个数return leave(root);int noleave()/计算非叶子节点个数return noleave(root);private:BinaryTreeNode*root;void PreOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);void InOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);void PostOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);/void LevelOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);static void Output(BinaryTreeNode* t)/输出树的所有节点coutdata ;int Height(BinaryTreeNode*t)const;int Size(BinaryTreeNode*t)const; void swap(BinaryTreeNode*t);int leave(BinaryTreeNode*t);int noleave(BinaryTreeNode*t);templateint BinaryTree:Height(BinaryTreeNode*t)constif(!t) return 0;int hl=Height(t-LeftChild);int hr=Height(t-RightChild);if(hlhr) return +hl;else return +hr;templateint BinaryTree:Size(BinaryTreeNode*t)const if(!t) return 0; int sl=Size(t-LeftChild); int sr=Size(t-RightChild); return (1+sl+sr);templateBinaryTreeNode*BinaryTree:iCreat( ) T ch;cinch;BinaryTreeNode * root;if(ch=#) root=NULL;elseroot=new BinaryTreeNode;root-data=ch;root-LeftChild=this-iCreat();root-RightChild=this-iCreat();return root; templatevoid BinaryTree:Creat() this-root = iCreat();templatevoid BinaryTree:PreOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t)if(t) Visit(t);PreOrder(Visit,t-LeftChild);PreOrder(Visit,t-RightChild);template void BinaryTree:InOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t)if(t)InOrder(Visit,t-LeftChild);Visit(t);InOrder(Visit,t-RightChild);templatevoid BinaryTree:PostOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t)if(t)PostOrder(Visit,t-LeftChild);PostOrder(Visit,t-RightChild);Visit(t);templatevoid BinaryTree:swap(BinaryTreeNode *t)BinaryTreeNode *temp;if(!t) return;elsetemp=t-LeftChild;t-LeftChild=t-RightChild;t-RightChild=temp;swap(t-LeftChild);swap(t-RightChild);templateint BinaryTree:leave(BinaryTreeNode*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;templateint BinaryTree:noleave(BinaryTreeNode *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#includebinarytree.h#include void main() cout输入二叉树:endl;BinaryTree Tree;Tree.Creat();/cout前序遍历:;/Tree.PreOutput();cout中序遍历:;Tree.InOutput();cout后序遍历:;Tree.Postput();cout二叉树的叶节点数目为:;coutTree.leave()endl;Tree.swap();cout交换前序遍历:;/Tree.PreOutput();实习题目4.v 任务：输入一棵二叉树的前序遍历序列和中序遍历序列，重构这棵二叉树v 功能要求： 在题目三的基础之上，增加一个方法，重构这棵二叉树 要求以图示效果，层次输出这棵二叉树/bintree.h #ifndef BINTREE_H#define BINTREE_H#include#includequeue.htemplateclass BinaryTree;template/二叉树的二叉链表class BinaryTreeNodefriend BinaryTree;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*LeftChild,*RightChild;templateclass BinaryTreepublic:BinaryTree()/构造函数 空树root=0;BinaryTree()bool IsEmpty()constreturn (root)?false:true);/void BinaryTree:LevelOrder(void(* Visit)(BinaryTreeNode*u);void LevelOrder(void(BinaryTree:* Visit)(BinaryTreeNode*u);/层次访问,在访问某一层结点时把下一层结点记忆在队列（尾）中，然后在访问在队头的结点void LevelOutPut()if(!root)/空树return;coutdata;LevelOrder(Output);coutendl;BinaryTreeNode*createBinaryTree(T *VLR,T*LVR,int n)/构造二叉树前 中 n为元素个数if(n=0)return NULL;int k=0;while(VLR0!=LVRk)/在中序前序结合找根k+;BinaryTreeNode*t=new BinaryTreeNode(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*root;void Output(BinaryTreeNode* t)if(t-LeftChild|t-RightChild)/左或又子树不为空if(t-LeftChild)coutLeftChild-data;elsecoutRightChild)coutRightChild-data;elsecout#;templatevoid BinaryTree:LevelOrder(void (BinaryTree:*Visit)(BinaryTreeNode *u)/void BinaryTree:LevelOrder(void(* Visit)(BinaryTreeNode*u)LinkedQueueBinaryTreeNode*Q;BinaryTreeNode *p=root;Q.EnQueue(p);/根节点进队while(!Q.IsEmpty ()Q.DeQueue(p);/根节点出队(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/单链表的链式队列templateclass LinkedQueue;templateclass Nodefriend LinkedQueue;private:T data;Node*link;templateclass LinkedQueue public:LinkedQueue()/构造函数front=rear=0;/建立空队列LinkedQueue();/析构函数bool IsEmpty()constreturn (front)?false:true);LinkedQueue&EnQueue(const T &x);/往队尾队列中插入元素LinkedQueue&DeQueue(T&x);/从队头删除元素private:Node*front;Node*rear;templateLinkedQueue:LinkedQueue()/析构函数的实现Node*next;while(front)next=front-link;delete front;front=next;templateLinkedQueue&LinkedQueue:EnQueue(const T &x)Node*p=new Node;p-data=x;p-link=0; if (front) rear-link=p;/在列尾添加新的结点 else/队列为空，新结点成为第一个结点 front=p;rear=p;return *this;templateLinkedQueue&LinkedQueue:DeQueue( T&x)/队头结点删去Node*p=front;/暂存队头结点x=front-data;front=front-link;/队头修改delete p;return*this;#endif#include stdafx.h#includebinarytree.h#include void main()BinaryTree Tree;/char 类型的int n;coutn;char *L=new charn; char *R=new charn;cout前序序列为:;int i=0,j=0;while(iLi;i+;cout中序序列为:;while(jRj;j+;Tree.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 #include minheap.h#include /const int MaxN = 100;template class HuffmanTree;template class HuffmanTreeNode/树结点的类定义 /friend class HuffmanTree; public: int arrkey; Type data;/结点数据 Huf