山东大学数据结构实验报告六.doc
文本预览下载声明
数据结构实验报告——实验六
?
实验题目：排序算法 学号： 201411130001日期：2015.12.11班级：计机14.1姓名：刘方铮 Email：liu191150932@163.com实验目的：堆和搜索树
任务要求：
?一、实验目的
1、掌握堆和搜索树的基本概念，插入、删除方法。
二、实验内容
创建最大堆类。最大堆的存储结构使用链表。
提供操作:堆的插入、堆的删除。堆的初始化。Huffman树的构造。二叉搜索树的构造。
接收键盘录入的一系列整数，输出其对应的最大堆、Huffman编码以及二叉搜索树。
堆排序。
软件环境：
Win7 操作系统
开发工具：visual C++ 6.0
实验代码：
#include iostream
#include string
#includecmath
#includequeue
using namespace std;
class BinaryTreeNode
{
public:
BinaryTreeNode(){ LeftChild=RightChild=0;}
BinaryTreeNode(const int e)
{
data=e;
LeftChild=RightChild=0;
}
BinaryTreeNode(const int e,BinaryTreeNode *l,BinaryTreeNode *r)
{
data=e;
LeftChild=l;
RightChild=r;
}
int data;
BinaryTreeNode *LeftChild,*RightChild;
};
void Travel(BinaryTreeNode* roots){
queueBinaryTreeNode * q;
while(roots){
coutroots-data ;
if(roots-LeftChild)q.push(roots-LeftChild);
if(roots-RightChild)q.push(roots-RightChild);
try{
roots=q.front();
q.pop ();
}
catch(...)
{return;}
}
}
void PrOrder(BinaryTreeNode* roots){
if(roots){
coutroots-data ;
PrOrder(roots-LeftChild);
PrOrder(roots-RightChild);}
}
void InOrder(BinaryTreeNode* roots){
if(roots){
InOrder(roots-LeftChild);
coutroots-data ;
InOrder(roots-RightChild);}
}
class MaxHeap {
public:
MaxHeap() {
root = 0;
state = 0;
}
void MakeHeap(int element, MaxHeap left, MaxHeap right);
int Max() {
if (!root)
return 0;
return root-data;
}
MaxHeap Insert(const int x);
MaxHeap DeleteMax(int x);
MaxHeap Initialize(int a[], int n);
void Deactivate(){heap=0;}
void HeapSort(int a[],int n);
BinaryTreeNode *root, *last,*p_last;
int state;
void ConditionOrder(BinaryTreeNode *u, int k, int i,BinaryTreeNode *temp);
void Adjust(BinaryTreeNode *u);
BinaryTreeNode* LocateLast(BinaryTreeNode *u,int k,int i);
private:
MaxHeap *heap;
};
void MaxHeap::MakeHeap(int element, MaxHeap left, MaxHeap right)
{
root = new BinaryTreeNode(element
显示全部