罗湖网站建设公司网页广告调词平台
A. 【程序填空】赫夫曼编码
题目描述
给定n个叶子的权值，根据这些权值构造huffman树，并输出huffman编码
参考课本第6.6节的算法6.12，注意算法中数组访问是从位置1开始
赫夫曼构建中，默认左孩子权值不大于右孩子权值
如果遇到两个孩子权值相等，那么按输入顺序或生成顺序来排列。
例如有一个叶子权值是29，后来生成一个中间结点权值也是29，那么叶子为左孩子，中间结点为右孩子
例如有两个叶子权值都是4，那么按输入顺序，先输入权值的叶子是左孩子
请完成以下程序填空
输入
第1行输入n，表示有n个叶子
第2行输入n个权值，权值都是正整数
输出
输出n行，每行输出格式：权值-赫夫曼编码
请参考样例
输入：
8
5 29 7 8 14 23 3 11输出：
5-0001
29-10
7-1110
8-1111
14-110
23-01
3-0000
11-001代码：
#include <iostream>
#include <cstring>
#include <string>
#include <sstream>
using namespace std;const int maxW = 9999; //设定无穷大权值//Huffman树结点结构
class HuffNode { //哈夫曼树的结点结构
public:int weight; //权值int parent; //双亲下标int lchild; //左孩子下标int rchild; //右孩子下标
};//Huffman树结构
class HuffMan {
private:int len; //结点总数，等于lnum*2-1int lnum; //叶子数量HuffNode *HuffTree; //保存构建后的赫夫曼树信息void selectMin(int n, int &x1, int &x2);
//函数selectMin是从已生成的n个结点中(包含叶子)，选出未选的且权值最小的两个结点的下标
//两个下标结果保存在x1和x2中
//第一小权值的结点下标保存在x1，第二小权值的结点下标保存在x2
//如果不想用这个函数，就在类外定义中定义一个空函数体，避免语法错误string *HuffCode; //保存叶子的赫夫曼编码char ** HC; //保存叶子的赫夫曼编码
//如果不喜欢用string，可以用二维字符数组HC
//HuffCode和HC，两者只用一个保存赫夫曼编码就可以了 public:HuffMan(int n,int w[]); //输入叶子数量和叶子权重，初始化HuffTree和HuffCode（或HC）void buildTree(); //构建赫夫曼树，保存在HuffTree中void Coding(); //生成赫夫曼编码，保存在HuffCode或HC中void printCode(); //输出赫夫曼编码~HuffMan(); //回收空间
};//请完成Huffman树的剩下部分类定义
HuffMan ::~HuffMan() {delete[]HuffTree;delete[]HuffCode;len = 0; lnum = 0;
}void HuffMan::selectMin(int n, int& x1, int& x2) {int j;x1 = 0; x2 = 0;for (j = 1; j < n; j++) {if (HuffTree[j].parent == 0) {if (x1 == 0)x1 = j;else if (x2 == 0) x2 = j;if (HuffTree[j].weight < HuffTree[x1].weight) {x2 = x1; x1 = j;}else if (x2 != 0 && HuffTree[j].weight < HuffTree[x2].weight) x2 = j;}}
}HuffMan::HuffMan(int n, int w[]) {lnum = n;len = 2 * lnum - 1;HuffTree = new HuffNode[len + 1];HuffCode = new string[lnum + 1];//位置从1开始int i = 1;for (i = 1; i <= len; i++) {HuffTree[i].weight = 0;HuffTree[i].lchild = 0;HuffTree[i].rchild = 0;HuffTree[i].parent = 0;}for (i = 1; i <= lnum; i++)HuffTree[i].weight = w[i - 1];
}void HuffMan::buildTree() {int x1, x2;for (int i = lnum + 1; i <= len; i++) {selectMin(i, x1, x2);HuffTree[x1].parent = i;HuffTree[x2].parent = i;HuffTree[i].lchild = x1;HuffTree[i].rchild = x2;HuffTree[i].weight = HuffTree[x1].weight + HuffTree[x2].weight;}
}void HuffMan::Coding() {int i, j, c, f; // c,f是结点在数组中的下标for (i = 1; i <= lnum; i++) { // c,f是结点在数组中的下标for (c = i, f = HuffTree[i].parent; f != 0; c = f, f = HuffTree[f].parent) {if (c == HuffTree[f].lchild) HuffCode[i] = '0' + HuffCode[i];else HuffCode[i] = '1' + HuffCode[i];}}
}void HuffMan::printCode() {for (int i = 1; i <= lnum; i++)cout << HuffTree[i].weight << "-" << HuffCode[i] << endl;
}
//主函数如下
int main(void)
{ int n, wt[100];cin>>n;for(int i=0;i<n;i++)cin>>wt[i];HuffMan huff(n,wt);huff.buildTree();huff.Coding();huff.printCode();return 0;
}B. 【程序填空】赫夫曼解码
题目描述
在掌握赫夫曼树构建的基础上，实现赫夫曼解码
赫夫曼构建中，默认左孩子权值不大于右孩子权值
如果遇到两个孩子权值相等，那么按输入顺序或生成顺序来排列。
例如有一个叶子权值是29，后来生成一个中间结点权值也是29，那么叶子为左孩子，中间结点为右孩子
例如有两个叶子权值都是4，那么按输入顺序，先输入权值的叶子是左孩子
请完成以下程序填空
输入
第一行输入n，表示有n个叶子
第二行输入n个叶子权值，权值全是正整数
第三行输入n个叶子对应的字符，权值全是正整数
第四行输入k，表示要输入k个编码串
接着输入k个编码串
输出
输出k行，每行输出一个编码串的解码结果。
如果编码串非法，则对应的一行输出error，不输出已解码的字符
输入：
5
15 4 4 3 2
K G C M W
2
11011010000001
0000011100010输出：
KKCGWM
error代码：
#include <iostream>
#include <string>
using namespace std;const int maxW = 9999; //设定无穷大权值//Huffman树结点结构
class HuffNode { //哈夫曼树的结点结构
public:char letter;//结点对应的字符int weight; //权值int parent; //双亲下标int lchild; //左孩子下标int rchild; //右孩子下标
};//Huffman树结构
class HuffMan {
private:int len; //结点总数，等于lnum*2-1int lnum; //叶子数量HuffNode *HuffTree; //保存构建后的赫夫曼树信息void selectMin(int n, int &x1, int &x2);
//函数selectMin是从已生成的n个结点中(包含叶子)，选出未选的且权值最小的两个结点的下标
//两个下标结果保存在x1和x2中
//第一小权值的结点下标保存在x1，第二小权值的结点下标保存在x2
//如果不想用这个函数，就在类外定义中定义一个空函数体，避免语法错误public:HuffMan(int n,int w[], char c[]);
//构造函数HuffMan根据输入叶子数量、叶子权重、字符集合，初始化HuffTreevoid buildTree(); //构建赫夫曼树，保存在HuffTree中void Decoding(string cs);
//函数Decoding是根据参数编码串cs进行赫夫曼解码
//如果编码串cs有错，函数Decoding直接输出error，不输出已解码的字符~HuffMan(); //回收HuffTree空间
};
//以下完成Huffman类的定义填空
HuffMan::~HuffMan() {if (HuffTree) delete[]HuffTree;len = lnum = 0;
}void HuffMan::selectMin(int n,int &x1,int &x2) {x1 = x2 = 0;for (int i = 1; i <= n; i++) {if (HuffTree[i].parent == 0) {if (x1 == 0) x1 = i;else if (x2 == 0)x2 = i;if (HuffTree[i].weight < HuffTree[x1].weight) {x2 = x1; x1 = i;}else if (x2 != 0 && HuffTree[i].weight < HuffTree[x2].weight)x2 = i;}}
}HuffMan::HuffMan(int n,int w[],char c[]) {lnum = n;len = 2 * n - 1;HuffTree = new HuffNode[len + 1];for (int i = 1; i <= len; i++) {HuffTree[i].weight = 0;HuffTree[i].lchild = 0;HuffTree[i].rchild = 0;HuffTree[i].letter = 0;HuffTree[i].parent = 0;}for (int i = 1; i <= lnum; i++) {HuffTree[i].weight = w[i - 1];HuffTree[i].letter = c[i - 1];}
}
void HuffMan::buildTree() {int x1, x2;for (int i = lnum + 1; i <= len; i++) {selectMin(i - 1, x1, x2);HuffTree[x1].parent = i;HuffTree[x2].parent = i;HuffTree[i].lchild = x1;HuffTree[i].rchild = x2;HuffTree[i].weight = HuffTree[x1].weight + HuffTree[x2].weight;}
}void HuffMan::Decoding(string cs) {string decode;int k = len;for (int i = 0; i < cs.length(); i++) {if (cs[i] == '0') {if (HuffTree[k].lchild)k = HuffTree[k].lchild;else {cout << "error" << endl;return;}}else {if (HuffTree[k].rchild)k = HuffTree[k].rchild;else {cout << "error" << endl;return;}}if (HuffTree[k].lchild == 0 && HuffTree[k].rchild == 0) {decode += HuffTree[k].letter;k = len;}}if (k == len) cout << decode << endl;else cout << "error" << endl;
}
int main()
{ int i, n, wt[100];char ct[100];string cstr;cin>>n;for(i=0;i<n;i++)cin>>wt[i];for(i=0;i<n;i++)cin>>ct[i];HuffMan huff(n,wt, ct);huff.buildTree(); //构建赫夫曼树cin>>i;while (i--){ cin>>cstr;huff.Decoding(cstr); //赫夫曼解码}return 0;
}C. DS树--带权路径和
题目描述
计算一棵二叉树的带权路径总和，即求赫夫曼树的带权路径和。
已知一棵二叉树的叶子权值，该二叉树的带权案路径和APL等于叶子权值乘于根节点到叶子的分支数，然后求总和。如下图中，叶子都用大写字母表示，权值对应为：A-7，B-6，C-2，D-3
树的带权路径和 = 7*1 + 6*2 + 2*3 + 3*3 = 34
本题二叉树的创建参考前面的方法
输入
第一行输入一个整数t，表示有t个二叉树
第二行输入一棵二叉树的先序遍历结果，空树用字符‘0’表示，注意输入全是英文字母和0，其中大写字母表示叶子
第三行先输入n表示有n个叶子，接着输入n个数据表示n个叶子的权值，权值的顺序和前面输入的大写字母顺序对应
以此类推输入下一棵二叉树
输出
输出每一棵二叉树的带权路径和
输入：
2
xA00tB00zC00D00
4 7 6 2 3
ab0C00D00
2 10 20输出：
34
40#include <iostream>
#include <string>
using namespace std;
class BiTreeNode {
public:char data; //数据域BiTreeNode* leftChild, * rightChild; //左右子树指针BiTreeNode() :leftChild(NULL), rightChild(NULL) {}~BiTreeNode() {}
};class BiTree {
private:BiTreeNode* root; //根结点指针string sTree; //建树字符串int pos,sum=0; //标识建树字符串的当前字符位置int* arry;int j = 0;//路径数组下标int road[100];int high=0;BiTreeNode* CreateTree();//建树私有函数void PreOrder(BiTreeNode* t); //先序遍历实现void InOrder(BiTreeNode* t); //中序遍历实现void PostOrder(BiTreeNode* t); //后序遍历实现void findroad(BiTreeNode* t);
public:BiTree() :root(NULL) {};void Create(string vArray,int arr[],int n); //建树公有接口，参数是特定的先序遍历字符串void PreOrder(); //先序遍历公有接口void InOrder(); //中序遍历公有接口void PostOrder(); //后序遍历公有接口void findroad();void calculate();
};
//二叉树公有接口的实现
void BiTree::Create(string vArray,int arr[],int n)
{pos = 0;sTree.assign(vArray); //把参数保存到内部字符串root = CreateTree(); //建树成功后root指向根结点arry = new int[n];for (int i = 0; i < n; i++)arry[i] = arr[i];/*for (int i = 0; i < n; i++)cout << arry[i];*/
}
void BiTree::PreOrder()
{PreOrder(root);
}
void BiTree::InOrder()
{InOrder(root);
}
void BiTree::PostOrder()
{PostOrder(root);
}
void BiTree::findroad()
{findroad(root);
}
//请完成上述类内部的私有函数实现
BiTreeNode* BiTree::CreateTree()
{BiTreeNode* node;int l = sTree.length();if (sTree[pos] != '0'){node = new BiTreeNode;node->data = sTree[pos];pos++;node->leftChild = CreateTree();node->rightChild = CreateTree();}else{pos++;node = NULL;}return node;
}
void BiTree::PreOrder(BiTreeNode* t)
{if (t == NULL)return;cout << t->data;PreOrder(t->leftChild);PreOrder(t->rightChild);}
void BiTree::InOrder(BiTreeNode* t)
{if (t == NULL)return;InOrder(t->leftChild);cout << t->data;InOrder(t->rightChild);
}
void BiTree::PostOrder(BiTreeNode* t)
{if (t == NULL)return;PostOrder(t->leftChild);PostOrder(t->rightChild);cout << t->data;
}
void BiTree::findroad(BiTreeNode* t)
{if (t!=NULL){if (t->leftChild==NULL && t->rightChild==NULL){road[j] = high;j++;}else{if (t->leftChild != NULL){high++;findroad(t->leftChild);}if (t->rightChild != NULL){high++;findroad(t->rightChild);}}high--;}
}
void BiTree::calculate()
{/*cout << j << endl;*/for (int i = 0; i < j; i++){sum += arry[i] * road[i];}cout << sum << endl;
}//主函数
int main()
{int t;string vArray;cin >> t;while (t--){cin >> vArray;BiTree myTree;int n;cin >> n;int* a = new int[n];for (int i = 0; i < n; i++){cin >> a[i];}myTree.Create(vArray,a,n);myTree.findroad();myTree.calculate();/*myTree.PreOrder(); cout << endl;*//*myTree.InOrder(); cout << endl;myTree.PostOrder(); cout << endl;*/delete[]a;}return 0;
}D. DS树--二叉树之最大路径
题目描述
给定一颗二叉树的逻辑结构（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构
二叉树的每个结点都有一个权值，从根结点到每个叶子结点将形成一条路径，每条路径的权值等于路径上所有结点的权值和。编程求出二叉树的最大路径权值。如下图所示，共有4个叶子即有4条路径，
路径1权值=5 + 4 + 11 + 7 = 27路径2权值=5 + 4 + 11 + 2 = 22
路径3权值=5 + 8 + 13 = 26路径4权值=5 + 8 + 4 + 1 = 18
可计算出最大路径权值是27。
该树输入的先序遍历结果为ABCD00E000FG00H0I00，各结点权值为：
A-5，B-4，C-11，D-7，E-2，F-8，G-13，H-4，I-1
输入
第一行输入一个整数t，表示有t个测试数据
第二行输入一棵二叉树的先序遍历，每个结点用字母表示
第三行先输入n表示二叉树的结点数量，然后输入每个结点的权值，权值顺序与前面结点输入顺序对应
以此类推输入下一棵二叉树
输出
每行输出每棵二叉树的最大路径权值，如果最大路径权值有重复，只输出1个
输入：
2
AB0C00D00
4 5 3 2 6
ABCD00E000FG00H0I00
9 5 4 11 7 2 8 13 4 1输出：
11
27代码：
#include <iostream>
#include<queue>
using namespace std;class HTNode
{
private:char data;int weight;HTNode* lchild, * rchild;
public:HTNode() :weight(0), lchild(NULL), rchild(NULL) {}~HTNode() {}friend class HuffmanTree;
};class HuffmanTree
{
private:HTNode* root;int LeafNum;int Maxroad;queue<int> weights;
public:~HuffmanTree();void CreateTree();void CreateTree(HTNode*& p, int& i, int& j);void getRoad();void getRoad(HTNode* p, int Level);
};HuffmanTree::~HuffmanTree()
{delete root;}void HuffmanTree::CreateTree(HTNode*& p, int& i, int& j)
{char c;cin >> c;if (c == '0') { p = NULL;}else {p = new HTNode;p->data = c;CreateTree(p->lchild, i, j);CreateTree(p->rchild, i, j);}}void HuffmanTree::CreateTree()
{int i = 0;int j = 0;CreateTree(root, i, j);
}void HuffmanTree::getRoad(HTNode* t, int road)
{if (t){ t->weight = weights.front() + road;weights.pop();getRoad(t->lchild, t->weight);getRoad(t->rchild, t->weight);if (!t->lchild && !t->rchild)if (t->weight > Maxroad)Maxroad = t->weight;}}
void HuffmanTree::getRoad() {int n;cin >> n;Maxroad=0;while (n--){int e;cin >> e;weights.push(e);}getRoad(root, 0);cout << Maxroad<<endl ;}int main(void)
{int t;cin >> t;while (t--){HuffmanTree myTree;myTree.CreateTree();myTree.getRoad();}return 0;
}E. DS二叉树—二叉树镜面反转
题目描述
假设二叉树用二叉链表存储，用先序序列结果创建。输入二叉树的先序序列，请你先创建二叉树，并对树做个镜面反转，再输出反转后的二叉树的先序遍历、中序遍历、后序遍历和层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。
--程序要求--
程序中不允许使用STL库等第三方对象或函数实现本题的要求
输入
测试次数t
每组测试数据是一个二叉树的先序遍历序列，#表示空树
输出
对每棵二叉树，输出镜面反转后的先序、中序、后序和层次遍历序列。如果空树，输出四个NULL（后面不加空格，每个NULL独自一行，中间没有空行）。如下：
NULL
NULL
NULL
NULL
输入：
3
41#32###65##7##
AB#C##D##
AB##C##输出：
4 6 7 5 1 3 2
7 6 5 4 3 2 1
7 5 6 2 3 1 4
4 6 1 7 5 3 2
A D B C
D A C B
D C B A
A D B C
A C B
C A B
C B A
A C B 代码：
#include<iostream>
using namespace std;
class node {
public:char data;node* left, * right;node() { left = right = NULL; }~node(){}
};
class tree {node* root;int pos;string str;node* createtree();void preOrder(node* root);void inOrder(node* root);void postOrder(node* root);void levelOrder(node* root);void exchange(node* root);
public:void create(string s);void inOrder();void preOrder();void postOrder();void exchange();void levelOrder();
};
void tree::exchange() {if (root != NULL) {exchange(root);}
}
void tree::exchange(node* root) {if (root != NULL) {exchange(root->left);exchange(root->right);node* p = new node();p = root->left;root->left = root->right;root->right = p;}
}
void tree::create(string s) {pos = 0;str = s;root = createtree();
}
node* tree::createtree() {node* p = new node();char c = str[pos++];if (c == '#') p = NULL;else {p->data = c;p->left = createtree();p->right = createtree();}return p;
}
void tree::preOrder() {if (str[0] == '#') cout << "NULL";else preOrder(root);cout << endl;
}
void tree::preOrder(node* root) {if (root) {cout << root->data << ' ';preOrder(root->left);preOrder(root->right);}
}
void tree::inOrder() {if (str[0] == '#') cout << "NULL";else inOrder(root);cout << endl;
}
void tree::inOrder(node* root) {if (root) {inOrder(root->left);cout << root->data << ' ';inOrder(root->right);}
}
void tree::postOrder() {if (str[0] == '#') cout << "NULL";else postOrder(root);cout << endl;
}
void tree::postOrder(node* root) {if (root) {postOrder(root->left);postOrder(root->right);cout << root->data << ' ';}
}
void tree::levelOrder() {if (str[0] == '#') cout << "NULL";else levelOrder(root);cout << endl;
}
void tree::levelOrder(node* root) {//不给用STL，有点大病）node** que = new node*[100];for (int i = 0; i < 100; i++) que[i] = new node();int front = 0, rear = 0,temp=0;node* p = root;que[temp++] = p; rear++;while (1) {p = que[front];front++;cout << p->data << " ";if (p->left) {que[temp++] = p->left; rear++;}if (p->right) {que[temp++] = p->right; rear++;}if (front == rear) break;}
}
int main() {int t; cin >> t;string s;while (t--) {cin >> s;tree t;t.create(s);t.exchange();t.preOrder();t.inOrder();t.postOrder();t.levelOrder();}
}