《数据结构》课程实习题

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 "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: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);// 判断链表是否为空// 求链表的长度// 查找第 k 个元素// 查找元素x// 删除第 k 个元素// 在第 k 个元素之后插入xvoid Output(ostream& 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& 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& 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，返回改变后的链表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>::Length() 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 < 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> *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)<<setfill('0')<< current->data << "";elseout<< current->data << "";i=1;j--;current=first;}}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(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=(current->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{n: ";cout<<" 请输入需要阶乘的数字cin>>n;Chain<long> a;a.Fac(n);cout<<n<<" 的阶乘为 :"<<endl;cout<<a;cout<<endl;cout<<" 是否进行计算:";cout<<endl;cin>>ch;}while(ch=='Y');return 0;}2:题目：表达式求值要求：实现关键栈的使用两位数以上、负数、小数点？实现方式控制台程序MFC 对话框#include "stdafx.h"#include <iostream>using namespace std;#include<assert.h>#include <cstdlib>#include <math.h>template<class T>class Stack{public:Stack(int sz=50);~Stack(){delete[]elements;}void Push(const T &x); //压入栈bool Pop(T&x);// 弹出栈T GetTop(void)const; // 取栈顶元素bool IsEmpty()const{return(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;elements=new T[MaxSize];// 创建栈的数组空间assert(elements!=NULL);//判断动态内存是否分配成功是否}template<class T>void Stack<T>::Push(const T&x){if(IsFull()==true){overflowProcess();}top++;elements[top]=x;}template<class T>bool Stack<T>::Pop(T&x){if(IsEmpty()==true){return false;}x=elements[top--];return true;}template<class T>T Stack<T>::GetTop(void)const//返回栈顶元素{if(IsEmpty()==true){cerr<<"栈为空 !"<<endl;exit(1);}return elements[top];}template<class T>void Stack<T>::overflowProcess() //溢出处理{T *newArray=new T[2*MaxSize]; // 扩充栈的空间for(int i=0;i<=top;i++){MaxSize=2*MaxSize;newArray[i]=elements[i];}delete[]elements;// 释放原来旧的空间}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(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){cerr<<"Divide by 0!"<<endl;Clear();}else{value=left/right;s.Push(value);}break;}cout<<"="<<s.GetTop()<<" ";}elseClear();}void Calculater::Run(){char ch;double newOperand;while(cin>>ch,ch!='#'){switch(ch){case '+':case'-':case'*':case'/'://是操作数，执行计算DoOperator(ch);break;default:// 其实也是一种case，只不过就是指“除了指定的几个case以外的其他情况”，不是操作符cin.putback(ch);// 字符放回输入流cin>>newOperand;// 重新读取操作数，一个操作数的第一个字符 AddOperand(newOperand);// 将操作数放入栈中}}}int main(){Calculater call;cout<<"输入计算表达式:";call.Run();return 0;}3.题目 :题目：二叉树基本算法的实现功能要求：键盘输入二叉树结点序列，创建一棵二叉树实现SwapTree 方法，以根结点为参数，交换每个结点的左子树和右子树（提示：前序递归）实现 Find 方法，查找值为 key 的结点，并输出该结点的所有祖先结点你可以选择：对BinaryTree 模板进行功能扩充；自己定义并实现二叉树类要求键盘输入二叉树结点序列结点序列可以是前序，也可以是层次空结点以 #表示//binarytree.h#ifndef BINARYTREE_H#define BINARYTREE_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;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)(BinaryTreeNode<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<<endl;}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>*iCreat();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),BinaryTreeNode<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 Height(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)const{if(!t) return 0;int hl=Height(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)const{if(!t) return0;int sl=Size(t->LeftChild);int sr=Size(t->RightChild);return (1+sl+sr);}template<class T>BinaryTreeNode<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 BinaryTree<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>::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(Visit,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->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>::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>void main(){cout<<"输入二叉树 :"<<endl;BinaryTree<char> Tree;Tree.Creat();//cout<<" 前序遍历 :";//Tree.PreOutput();cout<<"中序遍历 :";Tree.InOutput();cout<<"后序遍历 :";Tree.Postput();cout<<"二叉树的叶节点数目为:";cout<<Tree.leave()<<endl;Tree.swap();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>// 二叉树的二叉链表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>*LeftChild,*RightChild;};template<class T>class BinaryTree{public:BinaryTree()// 构造函数空树{root=0;}~BinaryTree(){}bool IsEmpty()const{return ((root)?false:true);}//void BinaryTree<T>::LevelOrder(void(* Visit)(BinaryTreeNode<T>*u));void LevelOrder(void(BinaryTree<T>::* Visit)(BinaryTreeNode<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(VLR[0]!=LVR[k])// 在中序前序结合找根{k++;}BinaryTreeNode<T>*t=new BinaryTreeNode<T>(VLR[0]);//根结点为tt->LeftChild=createBinaryTree(VLR+1,LVR,k);//从前序VLR+1 开始对中序0~k-1 左子序列的k 个元素递归建立左子树t->RightChild=createBinaryTree(VLR+k+1,LVR+k+1,n-k-1);//从前序V LR+k+1开始对中序k+1~n-1 左子序列的 n-k-1 个元素递归建立右子树return t;}BinaryTreeNode<T>*root;void Output(BinaryTreeNode<T>* t){if(t->LeftChild||t->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)(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);// 根节点出队(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 LinkedQueue<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>&DeQueue(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>::EnQueue(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;// 暂存队头结点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 char[n];char *R=new char[n];cout<<"前序序列为 :";int i=0,j=0;while(i<n){cin>>L[i];i++;}cout<<"中序序列为 :";while(j<n){cin>>R[j];j++;}Tree.root=Tree.createBinaryTree(L,R,n);cout<<"层次遍历 :";Tree.LevelOutPut();delete[]L;delete[]R;}实习题目 5.最优二叉树基本要求：对Huffman 树的方法进行扩充，实现如下功能：1）键盘输入一个字符串，统计每个字符出现的频率；2）输出每个字符的 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// 树结点的类定义{//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 bit[MaxN];int start;};template <class Type>class 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> &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(Type weight[], int n)//n个权值为W[1]....{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];for(int i = 0;i < n;i++)// 森林各颗树初始化{hfCode[i].dataptr = &TNode[i];TNode[i].data = weight[i];TNode[i].arrkey = i;TNode[i].parent = TNode[i].leftChild = TNode[i].rightChild = NULL;}MinHeap <HuffmanTreeNode <Type> > hp(TNode,n);for(i = 0;i < n-1;i++){parent = new HuffmanTreeNode <Type>;firstchild = 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, *parent;for(int i=0;i < currentSize;i++){cd->start = currentSize -1;child = hfCode[i].dataptr;parent = child->parent;while(parent != NULL){if(parent->leftChild == child)//向左标记为0cd->bit[cd->start] = 0;elsecd->bit[cd->start] = 1; // 向右标记为0child = parent;parent = parent->parent;cd->start--;}for(int k=0;k < currentSize;k++){hfCode[i].bit[k] = cd->bit[k];hfCode[i].start = cd->start+1;}}cout<<endl<<" 输出： "<<endl;for(i=0;i<currentSize;i++){cout<<hfCode[i].dataptr->data<<":";for(int j=hfCode[i].start;j<currentSize;j++)cout<<hfCode[i].bit[j];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);// 构造函数~MinHeap(){delete []heapArr;}//析构函数int Insert(Type &d);// 把数据元素插入最小堆中Type * RemoveMin();// 删除堆顶上最小元素private:Type * heapArr;// 存放堆中元素的数组Type * Arr;Type * saveNode[100];int saveNodeCount;int heapCurrentSize;// 堆中当前元素个数int heapMaxSize;// 最多元素个数void siftDown(int p);//从p下滑调整为最小堆void siftUp(int p);// 从 p 上滑调整为最小堆};template <class Type>MinHeap <Type> :: MinHeap(int maxSize)heapMaxSize = maxSize;heapArr = new Type [heapMaxSize];// 创建堆存储空间heapCurrentSize = 0;// 当前元素个数为0}template<class Type>MinHeap<Type>::MinHeap(Type a[],int n){heapMaxSize = n;heapArr = new Type[heapMaxSize];saveNodeCount=n;for(int j=0;j<n;j++){heapArr[j]=a[j];}Arr=a;heapCurrentSize=n;// 复制堆数组，建立当前大小int i=(heapCurrentSize-2)/ 2;// 找最初调整位置，即最后分支节点while(i>=0){siftDown(i);// 再向前换一个分支结点i--;}/*if (heapMaxSize%2==0){for(int k=0;k<n;k++){heapArr[k]=heapArr[k+1];}}*/}//?template <class Type>void MinHeap<Type>::siftDown(const int start)//堆下滑，从开始结点开始{int i=start,j;Type temp=heapArr[i];j=2*i+1;// 左子女位置while(j<=heapCurrentSize-1){if(j<=heapCurrentSize-1 && heapArr[j].data > heapArr[j+1].data) j++;if(temp.data <=heapArr[j].data) break;// else {heapArr[i]=heapArr[j];i=j;j=2*j+1;}//小不作调整小上移}heapArr[i]=temp;template<class Type>int MinHeap<Type>::Insert(Type&d){heapArr[heapCurrentSize]=d;heapArr[heapCurrentSize].arrkey=saveNodeCount;siftUp(heapCurrentSize);heapCurrentSize++;saveNode[saveNodeCount++]=&d;return 1;}template <class Type>void MinHeap<Type>::siftUp(int p){int j=p,i;Type temp = heapArr[j];i=(j-1)/ 2;while(j>0){if(heapArr[i].data<=temp.data)break;else{heapArr[j]=heapArr[i];j=i;i=(j-1)/ 2;}}heapArr[j]=temp;}template<class Type>Type * MinHeap<Type>::RemoveMin(){Type * temp=new HuffmanTreeNode<char>;(*temp)=heapArr[0];heapArr[0]= heapArr[heapCurrentSize-1];heapCurrentSize--;siftDown(0);if(temp->arrkey>-1 && temp->arrkey<heapMaxSize)return &Arr[temp->arrkey];else if(temp->arrkey>=heapMaxSize && temp->arrkey<100) return saveNode[temp->arrkey];}#endif#include "stdafx.h"#include "huffmantree.h"#include <iostream.h>int main(int argc, char* argv[]){char weight[MaxN];int n;cout<<" 字符个数 :";cin >> n;cout<<" 输入一串字符:";for(int i=0;i<n;i++)cin>>weight[i];HuffmanTree <char> a (weight,n);a.HuffmanCode();return 0;}实习题目 6.要求：自己设计图并编码进行存储，同时输出图的两种遍历方式的结果。

第六章习题1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。

3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k的结点，则该树中有多少个叶子结点并证明之。

4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。

5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？6．给出满足下列条件的所有二叉树：①前序和后序相同②中序和后序相同③前序和后序相同7． n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child 域有多少个？8．画出与下列已知序列对应的树Ｔ：树的先根次序访问序列为GFKDAIEBCHJ；树的后根次序访问序列为DIAEKFCJHBG。

9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10请为这8个字母设计哈夫曼编码。

10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因.11. 画出和下列树对应的二叉树：12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。

13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。

14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。

在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。

15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。

16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。

17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。

18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。

数据结构试题及答案一、选择题1. 下列哪项不是线性结构的特点？A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 至少有一个节点D. 每个节点最多有一个前驱和多个后继答案：D解析：线性结构的特点包括有且只有一个根节点、每个节点最多有一个前驱和一个后继、至少有一个节点。

选项D描述的是非线性结构的特点。

2. 在单链表中，增加一个头节点的作用是（）A. 便于首元节点的插入和删除操作B. 便于首元节点的访问C. 便于链表的操作D. 便于链表的删除答案：A解析：在单链表中，增加一个头节点可以使得首元节点的插入和删除操作更加方便，避免了首元节点特殊情况的处理。

3. 下面哪一个不是栈的基本运算？A. 入栈B. 出栈C. 初始化栈D. 求栈顶元素答案：C解析：栈的基本运算包括入栈、出栈、求栈顶元素和判断栈空。

初始化栈是创建栈的过程，不属于基本运算。

二、填空题4. 在顺序表中，元素之间的逻辑关系是由_______表示的。

答案：物理位置解析：顺序表中，元素之间的逻辑关系是通过物理位置来表示的。

每个元素在内存中占据连续的存储空间。

5. 设栈S的初始状态为空。

若元素序列为ABCDEF，当元素序列的进栈和退栈操作交叉进行时，下列序列中不可能出现在栈S中的是_______。

答案：BACF解析：当元素序列的进栈和退栈操作交叉进行时，栈中可能出现的序列有很多种，但BACF不可能是栈中出现的序列，因为元素C在元素F之前进栈，但F在C之前出栈，违反了栈的后进先出原则。

三、判断题6. 线性表是一种随机存取结构，因此可以随机访问表中的任一元素。

（）答案：正确解析：线性表是一种随机存取结构，支持随机访问表中的任一元素，时间复杂度为O(1)。

7. 在双向链表中，每个节点包含两个指针，一个指向前一个节点，另一个指向下一个节点。

（）答案：正确解析：双向链表中的每个节点确实包含两个指针，一个指向前一个节点，另一个指向下一个节点，便于从任意方向遍历链表。

第1章习题答案1. 填空题（1）在计算机中的存储映像（是逻辑结构在计算机中的实现或存储表示）数据元素的表示元素之间关系的表示数据元素。

（2）已经实现是一个概念分离分离（3）时、空效率指人对算法阅读理解的难易程度对于非法的输入数据，算法能给出相应的响应，而不是产生不可预料的后果。

（4）软硬件环境问题规模的（5）最坏（6）O（n4）O（n2）（7）时间复杂度（8）n 2)1(nn+O（n2）2. 判断题（1）×（2）×（3）√（4）√（5）√（6）√（7）×（8）×（9）×（10）×3. 简答题（1）略（见教材第3页的1.2数据结构的基本概念）（2）（a）n-1，O（n）（b）n-1 , O（n）（c）11* n+1, O（n）（n为初始值100）（d）⎣⎦n, O（n）（e）n , O（n）第2章习题及答案1、填空题（1）address+m*i（2）顺序顺序顺序链式存储链式存储（3）亦相邻不一定（4）n-i+1（5）0≤i≤la的长度-1≤j≤lb的长度-1 0≤k≤lc的长度-1（6）2)1(nn+插入的位置，节点数n（顺序表长度n）（7）其前驱O(n) O（1）（8）其前驱O(n) O（1）（9）p→next=p→next →next（10）head→next==Null head==Null head→next==head head==Null （11）head→next=head→next→next head=head→next（12）x=p→prior→data; p→prior→data=p→next→data; p→next→data=x; （13）p==head→prior(或p→next==head)2．判断题（1）×（2）√（3）×（4）×（5）×（6）×（7）√（8）×（9）×（10）×3．简答题(1)（2）在带头结点的单链表上，查找指针p所指结点的前驱。

数据结构实验实习题答案实验一线性表1. 设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有序。

分析：其实这个题在学C语言时就已经写过了，这里采用顺序表来存储数据。

主要就是考虑插入的位置是不是在最后一个，如果不在最后一个，那么就要移动数据了，算法很简单就不再说了，这里的数据都看成是整型的。

源程序：//1.1.c#include#includevoid Insert(int* p,int length,int n){//插入函数int i,j;int flag=0;if(n>=p[length-1]){//n比最大数还要大时p[length]=n;flag=1;}else{for(i=length-2;i>=0;i--){if(n>=p[i]){//插入nfor(j=length;j>=i+2;j--){p[j]=p[j-1];}p[i+1]=n;flag=1;break;}}}if(flag==0){//n为最小数时for(j=length;j>=1;j--){p[j]=p[j-1];}p[0]=n;}}int main(){int L[10]={1,3,6,8,9,10,15};//初始化一个非递减速有顺表int length=7;//初始化表长int i,x;printf("插入前的顺序表为：\n");for(i=0;i<length;i++){< p="">printf("%4d",L[i]);}printf("\n请输入要插入的整数：\n");scanf("%d",&x);Insert(L,length,x);//插入xprintf("插入%d后的顺序表为：\n",x);for(i=0;i<=length;i++){printf("%4d",L[i]);}printf("\n");system("pause");return 0;}2. 用单链表ha 存储多项式A（x ）=a0+a1x1+a2x2+…+anxn(其中aI为非零系数)，用单链表hb 存储多项式B（x ）=b0+b1x1+b2x2+…+bmxm(其中bj为非零系数)，要求计算C（x ）= A（x ）+B（x ），结果存到单链表hc中。

《数据结构》程序设计实习题目1.分别以顺序表和单链表作为存储结构，实现将线性表就地逆置的操作。

（所谓“就地逆置”是指辅助空间为O（1），即利用原表中的结点空间）。

2.写一程序将单链表中值重复的结点删除，使得表中各结点值均不相同。

3.已知一单链表中含有两类字符的数据元素（如：字母、数字），试编写程序将该单链表分成两个单链表，使得每个链表中只含有同一类的字符。

4.假设有两个按元素值递增有序的单链表A和B，试编写程序将A和B归并成一个按元素值递减有序的单链表。

5.利用线性结构（顺序表或链表）实现两个20位大整数的加法运算。

6.已知两个以顺序结构存储的线性表A和B，试编写程序实现从A表中删除包含在B表中的元素。

7.已知两个单链表A和B，试编写程序实现从A表中删除包含在B表中的元素。

8.已知两个以顺序结构存储的线性表A和B，试编写程序实现：将在B表中但不在A表中的元素插入到A表。

9.已知两个单链表A和B，试编写程序实现：将在B表中但不在A表中的元素插入到A表。

10.试编写程序，对任意输入的一个算术表达式，将式中的数字和运算符分成两类（一类是数字，一类是运算符），并按逆序输出。

（提示：利用栈来实现）11.利用栈结构，编写一个程序，对以逆波兰式表示的表达式求值。

12.编写程序，求得所有包含在串S中而不包含在串T中的字符（S中重复的字符只选一个）构成的新串R。

13.编写程序，求任意输入的串S中所含不同字符的总数和每种字符的个数。

14.一个文本串可用事先给定的字母映射表进行加密。

例如：设字母映射表为：a b c d e f g h i j k l m n o p q r s t u v w x y zn g z q t c o b m u h e l k p d a w x f y i v r s j则字符串“encrypt”被加密为“tkzwsdf”。

试写一程序将输入的文本串进行加密后输出。

15.假设两个10×10的稀疏矩阵A和B以三元组表的方式存储，试编写程序实现矩阵的相加运算，其结果存放在三元组表C中。

苏州大学数据结构课程10卷参考答案（共 5 页）院系专业 __________一、填空题（每题3分，共30分）1、7500；6252、10883、线性表；入栈；出栈4、n2+1 ； 2k-15、hdiebjkfca6、 227、深度优先；广度优先；10；从源点到汇点路径长度之和最长的路径8、299、1； 710、wpl=(2+5)*3+(7+9+13)*2=79 。

二、应用题（每题8分，共40分）因为队列的入队和出队在顺序队列的两端进行，可能造成队列空间未用完但队列指针已经越界，从而产生虚溢出。

（2分）解决虚溢出的方法是采用循环队列。

（2分）队空条件为：q.front=q.rear （2分）队满条件为：q.front=（q.rear+1）mod m （2分）2、(1)（4(2)（2分）(3)ASL=(1+1+2+1+2+1+1+3+1+3+1)/11=17/11 （2分）3、最小生成树：（4分）邻接矩阵：1 2 3 4 5 60 10 0 0 15 1210 0 5 6 0 70 5 0 6 0 00 6 6 0 0 815 0 0 10 0 1212 7 0 8 12 0（4分）4、（1（4分）（2）R1={4,5,6,7,8,9,16,18,20}。

（2分）（3）R2={5,6,4,9,8,18,20,16,7}。

（2分）三、算法设计题（每题10 分，共30分）1、假设用带头结点的单链表作为线性表的存储结构，编写在线性表中第i个元素前插入值为x的元素的算法。

deleteinsert(la,x) /*从表la中删除值为x的元素*/linklist *la；/*la分别为linklist类型的指针变量*/{linklist *p,*q;p=la;q=p->next; （3分）while (q!=null)if (q->data=x) {p->next=q->next ;dispose(q);q=p->next;} （4分）else {p=q;q=q->next;} （3分）2、int count(t,num)bitree *t;int num;{if (t) （2分）if ((t->lchild!=null) && (t->lchild==null)||(t->lchild==null) && (t->lchild!=null)) （2分）num=num+1;count(t->lchild,num); （2分）count(t->rchild,num); （2分）return(num); （2分）} /*count */3、#define INFINIY MAX_WEIGHTV oid converttu(AdjGraph *G1，ALGraph *G2)int{i,j;LinkNode *p;G2->vernum=G1->vernum;G2->e=G1->e; （3分）for (i=0;i< G1->vernum;i++){G2->adjlist[i].vexdata=G1->vexs[i]；G2->adjlist[i].first=null;}for (i=0;i< G1->vernum;i++)for (j=0;j< G1->vernum;j++)if (G1->adj[i][j]<INFINITY){p=(LinkNode *)malloc(sizeof(LinkNode)) （3分）p->weight=adj[i][j];p->adjvex=j;p->next=G2->adjlist[i].first;G2->adjlist[I].first=p;}return; （3分）}O(n2) （1分）。

【实验题】1．狐狸逮兔子围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必须找到我，我就藏身于这十个洞中，你先到１号洞找，第二次隔１个洞（即3号洞）找，第三次隔２个洞（即6号洞）找，以后如此类推，次数不限。

”但狐狸从早到晚进进出出了1000次，仍没有找到兔子。

问兔子究竟藏在哪个洞里？（提示：这实际上是一个反复查找线性表的过程。

）【数据描述】定义一个顺序表，用具有10个元素顺序表来表示这10个洞。

每个元素分别表示围着山顶的一个洞，下标为洞的编号。

#define LIST_INIT_SIZE 10 //线性表存储空间的初始分配量typedef struct {ElemType *elem; //存储空间基址int length; //当前长度int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位）}SqList;【算法描述】status InitList_Sq(SqList &L) {//构造一个线性表LL.elem=(ElemType )malloc(LIST_INIT_SIZE*sizeof(ElemType));If(!L.elem) return OVERFLOW; //存储分配失败L.length=0; //空表长度为0L.listsize=LIST_INIT_SIZE; //初始存储容量return OK;} //InitList_Sqstatus Rabbit(SqList &L){ //构造狐狸逮兔子函数int current=0; //定义一个当前洞口号的记数器，初始位置为第一个洞口for(i=0;i<LIST_INIT_SIZE;i++)L.elem[i]=1; //给每个洞作标记为1，表示狐狸未进之洞L.elem[LIST_INIT_SIZE-1]=L.elem[0]=0;//首先进入第一个洞，标记进过的洞为0。

数据结构与算法实践练习题目及解答以下是一些数据结构与算法的实践练题目及其解答。

1. 数组相关题目题目一给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的索引。

def twoSum(nums, target):nums_dict = {}for i in range(len(nums)):nums_dict[nums[i]] = i题目二给定一个整数数组 nums，将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

def moveZeroes(nums):count = 0for i in range(len(nums)):if nums[i] != 0:nums[count] = nums[i]count += 1while count < len(nums):nums[count] = 0count += 12. 链表相关题目题目三反转一个单链表。

class ListNode:def __init__(self, val=0, next=None): self.val = valself.next = nextdef reverseList(head):prev = Nonecurr = headwhile curr is not None:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prev题目四给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

def deleteDuplicates(head):curr = headwhile curr is not None and curr.next is not None:if curr.val == curr.next.val:curr.next = curr.next.nextelse:curr = curr.nextreturn head以上是一些数据结构与算法的实践练习题目及其解答。

重庆邮电学院软件学院《数据结构》实验参考资料<适用于软件学院13104级>重庆邮电学院软件学院实验中心目录一、课程编号 (2)二、课程类型 (2)三、本课程的地位、作用与任务 (2)四、课程基本要求 (2)五、实验安排 (2)1、数据结构实验机器与环境 (2)（一）计算机的硬件配置 (2)（二）计算机的软件配置 (2)2、VisualC++6.0开发C语言程序 (2)（一）进入C++工作环境 (2)（二）编译、运行C程序 (3)3、上机实验 (6)实验1：线性表操作 (6)实验2：单链表操作 (11)实验3：表达式计算 (17)实验4：二叉树操作 (24)实验5：二叉搜索树操作 (30)实验6：图的运算 (36)实验7：散列表操作 (43)实验8：外存文件的排序操作 (49)实验9：二叉搜索树与文件操作 (53)六、教材 (60)七、成绩考核办法 (60)数据结构（C语言版）实验一、课程编号130101（本科）二、课程类型课程类型：必修课。

适用专业：计算机系各专业实验学时：10学时三、本课程的地位、作用与任务《数据结构》在计算机科学中是一门综合性的专业基础课。

数据结构的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有密切的关系，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。

在计算机科学中，数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础，它的主要任务是讨论各种数据结构的逻辑结构，存储结构及有关操作的算法。

目的是使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。

另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。

从而为提高学生的实际分析问题和解决问题的编程能力打下基础。