|
Amaliy mashg‘ulot 6 Mavzu
|
| bet | 4/6 | | Sana | 23.05.2024 | | Hajmi | 441,98 Kb. | | #251388 |
Bog'liq 2-dedline uchun shablonAmaliy qism
Huffman algoritmiga ko'ra daraxt quring va uni web brouserda tasvirini ko’rsating
#include
#include
#include
using namespace std;
struct Node {
string value, code;
unsigned amount;
Node * left;
Node * right;
// taqqoslash vositasi
bool operator() (const Node& x, const Node& y) const {
return x.amount > y.amount;
}
// taqqoslovchi ob'ektni yaratish uchun standart konstruktor kerak
Node (const string& value = "", unsigned amount = 0, Node * left = 0, Node * right = 0) {
bu- > qiymat= qiymat; / / tugun belgisi ko'p
bu - >code=""; / / tugun bit kodi string vakillik
bu- > miqdori= miqdori; / / necha marta sarflandi
bu- > chap = chap; / / chap bola
bu - >o'ng = o'ng; / / o'ng bola
}
// olingan daraxtning DOT tavsifini yaratish
string to_str() {
ostringstream x;
if (left != 0 || right != 0) {//daraxt har ikkala bola ham bor yoki yo'q
x << "\t\"" << code << ": " << value << "[" << amount << "]\" -> \"" << left->code << ": " << left->value << "[" << left->amount << "]\";\n";
x << left->to_str();
x << "\t\"" << code << ": " << value << "[" << amount << "]\" -> \"" << right->code << ": " << right->value << "[" << right->amount << "]\";\n";
x << right->to_str();
} else {
x << "\t\"" << code << ": " << value << "[" << amount << "]\" [shape=box, style=filled, fillcolor=green];\n";
}
return x.str();
}
// daraxtlarni birlashtirish
Node * join (Node x) {
return new Node(x.value + value, x.amount + amount, new Node(x), this);
}
// kodni ishlab chiqarish bilan daraxt o'tish
void traversal_code(string code) {
this->code = code;
if (left != 0 || right != 0) {
left->traversal_code(code + "1");
right->traversal_code(code + "0");
}
}
// Huffman algoritmiga ko'ra daraxt quramiz
static Node * builder(priority_queue, Node> graph) {
while (graph.size() > 1) {
Node *n = new Node(graph.top());
graph.pop();
graph.push(*n->join(*new Node(graph.top())));
graph.pop();
}
return new Node(graph.top());
}
};
unsigned amounts[256]; / / belgilar bilan duch hisoblagich bir qator
int main() {
string s;
getline (std:: cin, s); / / bo'sh joylar bilan birga qatorni o'qing
for(auto i: s) amounts[i]++;
priority_queue, Node> graph;
for (int i = 'a'; i < = 'z'; i++) / / ustuvor bilan navbat yozish
if (amounts[i] > 0) graph.emplace(s=(char)i, amounts[i]);
Node *n = Node::builder(graph);
n->traversal_code("");
// grafning tavsifiga ko'ra tasvirlarni yaratish uchun Google xizmatiga havola yaratish
cout << "http://chart.apis.google.com/chart?cht=gv&chl=" << endl;
// olingan daraxtning DOT tavsifini chizish uchun yarating
cout << "Digraph G {\n" << n->to_str() << "}";
// Agar dasturning chiqishi brauzerning manzil satriga nusxa ko'chirilsa va joylashtirilsa, rasmni ko'rasiz.
|
| |
