陈越《数据结构》第七讲 图(中)
Tree Traversals Again1086.Tree Traversals Again (25) Input Specification: Each input file contains one test case. For each case,the first line contains a positive integer N (<=30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow,each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack. Output Specification: For each test case,print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space,and there must be no extra space at the end of the line. Sample Input: 题目大意: #include <cstdio>
#include <stack>
using namespace std;
int preorder[35],inorder[35];
int n,preid = 0,inid = 0,cnt = 0;
int get(){
char s[10];
scanf("%s",s);
if (s[1] == 'o') return -1;
int a;
scanf("%d",&a);
return a;
}
void build(int preb,int pree,int inb,int ine){
if (preb > pree) return;
int root = preorder[preb];
int inroot = inb;
while (inorder[inroot] != root) ++inroot;
build(preb+1,preb+inroot-inb,inb,inroot-1);
build(preb+inroot-inb+1,pree,inroot+1,ine);
if (cnt++ != 0) putchar(' ');
printf("%d",root);
}
int main(){
scanf("%d",&n);
stack<int> st;
for (int i = 0; i < n*2; ++i){
int a = get();
if (a != -1){
st.push(a);
preorder[preid++] = a;
}else{
inorder[inid++] = st.top();
st.pop();
}
}
build(0,n-1,0,n-1);
return 0;
}
Complete Binary Search TreeA Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: The left subtree of a node contains only nodes with keys less than the node’s key. Now given a sequence of distinct non-negative integer keys,a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST. Input Specification: Each input file contains one test case. For each case,the first line contains a positive integer N (<=1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000. Output Specification: For each test case,print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space,and there must be no extra space at the end of the line.
#include <cstdio>
#include <cstdlib>
#include <math.h>
const int MaxNum = 1005;
int node[MaxNum];
int tree[MaxNum];
int cmp(const void *a,const void *b)
{/*以图2为基准*/
int *pa = (int *)a;
int *pb = (int *)b;
return *pa-*pb;
}
int GetLeftLength(int n)
{/*以图3为基准*/
int h,x,l;
/*转换成以2为底*/
h = log((double)(n + 1))/log (2.0);
x = n + 1 - pow(2.0,h);
if (x > pow(2.0,h - 1)) {
x = pow(2.0,h - 1);
}
l = pow(2.0,h - 1) - 1 + x;
return l;
}
void solve(int ALeft,int ARight,int TRoot)
{/*初始调用为solve(0,N-1,0)*/
/*以图1为基准*/
int n,L,LeftTRoot,RightTRoot;
n = ARight - ALeft + 1;
if(n==0) return; /*考虑完美二叉树的情况*/
L = GetLeftLength(n); /*计算出n个节点的树,其左子树有多少个节点*/
tree[TRoot] = node[ALeft + L];
LeftTRoot = TRoot * 2 + 1;
RightTRoot = LeftTRoot + 1;
solve(ALeft,ALeft + L -1,LeftTRoot);
solve(ALeft + L + 1,ARight,RightTRoot);
}
int main()
{
int i,n;
/*输入*/
scanf("%d",&n);
for(i=0;i<n;++i){
scanf("%d",&node[i]);
}
/*从大到小排序*/
qsort(node,n,sizeof(int),cmp);
/*排序成完全二叉树*/
solve(0,0);
/*输出*/
printf("%d",tree[0]);
for(i=1;i<n;++i){
printf(" %d",tree[i]);
}
printf("n");
system("pause");
return 0;
}
Huffman CodesPTA - Data Structures and Algorithms (English) - 5-9In 1953,David A. Huffman published his paper “A Method for the Construction of Minimum-Redundancy Codes”,and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes,I am encountering a big problem: the Huffman codes are NOT unique. For example,given a string
Input Specification: Each input file contains one test case. For each case,the first line gives an integer N
Output Specification: For each test case,print in each line either “
Note: The optimal solution is
Sample Input:
例1:最优编码不一定通过Huffman算法得到。给定4个字符及其出现频率:
例2:Huffman Codes的特点:
解法:解法转自:http://www.cnblogs.com/clevercong/p/4193370.html 2) 使用C++标准库中的优先队列:priority_queue,引入头文件 #include 。优先队列底层由堆实现,数据放入队列后,会自动按照“优先级”排好顺序。 #include <map>
#include <queue>
map<char,int> myMap;
priority_queue<int,vector<int>,greater<int> >pq; //小顶堆
for(int i=0; i<num; i++) // 输入结点的数据c[i]、权值f[i]
{
cin >> c[i] >> f[i];
myMap[c[i]] = f[i]; // 映射
pq.push(f[i]); // 向队列中添加元素
}
3) 计算
// 计算WPL的值
int myWpl = 0;
while(!pq.empty())
{
int myTop = pq.top();
pq.pop();
if(!pq.empty())
{
int myTop2 = pq.top();
pq.pop();
pq.push(myTop + myTop2);
int m = myTop + myTop2;
myWpl += m; //每次加m(子节点权值重复加入) 等效于 路径长度*权值
}
}
4) 测试数据需按编码排序,但标准库并没有为map制定sort函数,因此我们用vector装载pair类型,既可以模仿出map的功能,又可以用vector的排序函数。 #include <algorithm> // sort()
typedef pair<char,string> PAIR; // 用PAIR来代替pair<char,string> (编码类型:string)
// cmp():自定义按什么内容或大小顺序排序
// 这里是按编码的长度排序
int cmp(const PAIR& x,const PAIR& y)
{
return x.second.size() < y.second.size();
}
// vector + pair<,> 模仿 map
vector<PAIR> checkVec;
checkVec.push_back(make_pair(ch,s)); // 向vector中添加元素
sort(checkVec.begin(),checkVec.end(),cmp); // 按照编码的长度排序
5) 判断前缀问题:substr函数,取字符串中的一段并与当前编码进行比较。 bool flag = true; //已符合条件一:wpl最小
for(int i=0; i<num; i++)
{
string tmp = checkVec[i].second;
for(int j=i+1; j<num; j++)
{
if(checkVec[j].second.substr(0,tmp.size())==tmp)
flag = false;
}
}
完整代码: #include <iostream>
#include <algorithm> // 排序函数 sort()
#include <map>
#include <queue>
using namespace std;
typedef pair<char,string> PAIR; // + vector来模仿 map
int cmp(const PAIR& x,const PAIR& y) // 自定义让sort()按哪种方式排序
{
return x.second.size() < y.second.size();
}
int main()
{
int num;
cin >> num;
char *c = new char[num];
int *f = new int[num];
map<char,int> myMap; // 用来存节点数据及权值,并构成映射
// 使用优级队列
priority_queue<int,greater<int> >pq;
for(int i=0; i<num; i++) // 输入结点及出现次数(权值)
{
cin >> c[i] >> f[i];
myMap[c[i]] = f[i];
pq.push(f[i]); // 将权值压入优先队列
}
// 计算WPL的值
int myWpl = 0;
while(!pq.empty())
{
int myTop = pq.top();
pq.pop();
if(!pq.empty())
{
int myTop2 = pq.top();
pq.pop();
pq.push(myTop + myTop2);
int m = myTop + myTop2;
myWpl += m;
}
}
// 输入测试数据
int checkNum; // 测试数据的组数
cin >> checkNum;
for(int i=0; i<checkNum; i++)
{
int wpl = 0;
char ch;
string s;
// vector + PAIR 模仿 map,使其可排序
vector<PAIR> checkVec;
for(int j=0; j<num; j++)
{
cin >> ch >> s;
checkVec.push_back(make_pair(ch,s)); // 向vector中添加测试数据及其编码
wpl += s.size() * myMap[ch];
}
sort(checkVec.begin(),cmp); // 按照编码长度排序
if(wpl != myWpl)
{
cout << "No" << endl;
continue;
}
else
{
bool flag = true; // 表示已满足条件一:wpl最小(wpl==myWpl)
//条件二:编码的前缀不能是其他编码的前缀:substr()
for(int i=0; i<num; i++)
{
string tmp = checkVec[i].second;
for(int j=i+1; j<num; j++)
{
if(checkVec[j].second.substr(0,tmp.size())==tmp)
flag = false;
}
}
if(flag == true)
cout << "Yes" << endl;
else
cout << "No" << endl;
continue;
}
cout << "Yes" << endl;
}
return 0;
}
总结的程序 #include <iostream>
#include <string>
using namespace std;
struct Heap
{
int *data;
int size = 0;
};
struct cnode
{
int tag = 0;
cnode *left = nullptr;
cnode *right = nullptr;
};
Heap *Init_Heap(int n); //初始化小根堆(利用静态链表的逻辑结构);
void Insert_Heap(Heap *H,int x); //把元素依次插入小根堆;
int Delmin_Heap(Heap *H); //删除小根堆中的最小元素;
int Cal_Wpl(Heap *H); //计算huffman编码的wpl;
int wpl_prefix(int *sample,int n,int &re); //计算待测编码的wpl及判断是否为前缀编码;
/*思路:要判断是否,需要解决两个问题: 1)编码wpl等于huffman编码的wpl; 2)待测编码是前缀编码。 问题1: 首先要求出标准wpl。观察huffman树,我们发现其wpl是非叶子结点权值和。 于是,我们无需构造出huffman树来求权值(麻烦点),通过模拟树的构造过程, 理由小根堆的特点求出wpl; 而待测编码的wpl就是利用每个编码的字符串长度,乘以每个字符的权值得到; 问题2: 思路是构造一个二叉树出来,模拟huffman树。 1.让每个编码遍历树,结束时在当前结点设置标记为1; 2.如果遍历时,未结束时碰到了标记为1的结点,则不是前缀编码; 3.结束时,未碰到标记点(包括最后一个),是前缀编码。 */
int main()
{
int n,i,val;
char ch;
cin >> n;
int *sample = new int[n]; //每个字符权值存储在这里;
Heap *H = Init_Heap(n); //初始化小根堆(利用静态链表的逻辑结构);
for (i = 0; i < n; i++)
{
cin >> ch >> val;
sample[i] = val;
Insert_Heap(H,val); //把元素依次插入小根堆;
}
int best_wpl = Cal_Wpl(H); //计算huffman编码的wpl;
int m,wpl,re; //re是用来判断是否前缀编码,是为1,否为0;
cin >> m;
for (i = 0; i < m; i++)
{
wpl = wpl_prefix(sample,re); //计算待测编码的wpl及判断是否为前缀编码;
if (wpl == best_wpl && re == 1)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
delete sample;
return 0;
}
Heap *Init_Heap(int n)
{
Heap *H = new Heap;
H->data = new int[n + 1]; //堆的下标从1开始(为了操作方便);
H->data[0] = -1; //小根堆赋值最小值;
return H;
}
void Insert_Heap(Heap *H,int x) //把元素依次插入小根堆;
{
int i = ++(H->size);
for (; H->data[i / 2] > x; i /= 2) //从下往上过滤;
H->data[i] = H->data[i / 2];
H->data[i] = x;
return;
}
int Delmin_Heap(Heap *H) //删除小根堆中的最小元素;
{
int t = H->data[H->size--];
int min = H->data[1];
int pa,chi;
for (pa = 1; pa * 2 <= H->size; pa = chi) //从上往下过滤最小元素;
{
chi = pa * 2;
if (chi != H->size && H->data[chi + 1] < H->data[chi]) //找到子结点的最小下标;
chi++;
if (t < H->data[chi])
break;
else
H->data[pa] = H->data[chi];
}
H->data[pa] = t; //赋值最小元素
return min;
}
int Cal_Wpl(Heap *H) //计算huffman编码的wpl;
{
int sum = 0;
if (H->size > 1)
{
int i,t1,t2,t;
int m = H->size;
for (i = 1; i < m; i++)
{
t1 = Delmin_Heap(H); //模拟构造huffman树的过程,先取出两个最小值,相加,把和插入堆中;
t2 = Delmin_Heap(H);
t = t1 + t2;
Insert_Heap(H,t);
sum += t;
}
}
else
sum = H->data[0];
return sum;
}
int wpl_prefix(int *sample,int &re) //计算待测编码的wpl及判断是否为前缀编码;
{
int i,j,len,wpl = 0;
char ch;
string st;
cnode *phead = new cnode;
cnode *p = phead;
re = 1;
for (i = 0; i < n; i++)
{
cin >> ch >> st; //此处计算wpl;
len = st.length();
wpl += len*sample[i];
if (re != 0) //此处判断是否前缀编码;
{
for (j = 0; j < len; j++)
{
if (st[j] == '0') //0的话判断左边;
{
if (p->left == nullptr) //左边空,新建结点;
{
cnode *q = new cnode;
p->left = q;
}
else
{
if (p->tag == 1)
{
re = 0;
break;
}
}
p = p->left;
}
else if (st[j] == '1') //判断右边;
{
if (p->right == nullptr)
{
cnode *q = new cnode;
p->right = q;
}
else
{
if (p->tag == 1)
{
re = 0;
break;
}
}
p = p->right;
}
}
if (p->left == nullptr && p->right == nullptr)
re = 1;
else
re = 0;
if (p->tag == 0) //注意此处需要判断,最后结点标记不为1才能赋值(待测编码有可能有相同的);
p->tag = 1;
else
re = 0;
p = phead;
}
}
return wpl;
} (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |