nt = 0; _file < }
}
}
}
}
} _file.close (); _file.close ();
} main (int argc, char * argv [])
}
3. Алгоритм програми
Зіставимо алгоритм Хаффмана та код програми.
Крок 1.
У початковому тексті необхідно порахувати частоту появи кожного символу (інакше, вага). Функція Read () зчитує файл побайтово. У ній викликається функція Find_this_symbol () приймаюча лічений символ. Вона шукає його у векторі символів (symbol_vector) і збільшує параметр amount (вага або частота) на 1, або якщо не знаходить те додає цей елемент у вектор. p align="justify"> Крок 2.
Після обчислення частот ми створимо вузли бінарного дерева для кожного знака і додамо їх у чергу, використовуючи частоту в якості пріоритету. Для цього спочатку викликаємо функцію Create_Null_Nodes (), яка створює пусте несвязанное дерево використовую вектор символів. p align="justify"> Далі викликається функція Create_Tree (). У ній спочатку викликається функція Sort (), сортуюча елементи дерева (Tree_vector) відповідно з частотою символів (їх вагою), за зменшенням. Після цього викидається два елементи з мінімальною вагою з кінця вектора і замінюється новим елементом, вага якого дорівнює сумі ваг цих двох елементів. Також створюється зв'язок між двома В«синамиВ» і В«батькомВ». Цикл повторюється до тих пір, поки не залишиться один елемент - корінь. Таким чином будується дерево Хаффмана. p align="justify"> Крок 3.
Тепер, щоб отримати код для кожного символу, потрібно пройтися по дереву, і для кожного переходу додавати 0, якщо ми йдемо вліво, і 1 - якщо направо. Таким способом ми отримаємо код для кожного символу. Ця частина алгоритму виконується у функції Coding_Tree (). Це рекурсивна функція. Код накопичується у векторі code і якщо знайдений вузол без В«синівВ», то елементу присвоюється В«накопиченийВ» при обході код. Після цього останній символ з code викидається і функція рекурсивно повторюється. Таким чином, ми кодуємо дерево Хаффмана. p align="justify"> На цьому алгоритм кодування закінчується. Програма виводимо на екран закодований текст. Розкодування тексту, як згадувалося, не передбачено, але це нескладно зробити, якщо записати структуру vector Tree_vector в окремий файл і потім рахувати, тому що в ній зберігаються коди всіх елементів.
. Аналіз трудомісткості алгоритму
При знаходженні обчислювальної складності (аналізі трудомісткості) алгоритму за N ми приймемо кількість символів вихідного коду.
Можна помітити, що з усіх використовуваних функцій тільки дві функції використовують сам алгоритм Хаффмана і, тому, є в...
