Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Контрольные работы » Аналіз трудомісткості алгоритмів

Реферат Аналіз трудомісткості алгоритмів





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 ми приймемо кількість символів вихідного коду.

Можна помітити, що з усіх використовуваних функцій тільки дві функції використовують сам алгоритм Хаффмана і, тому, є в...


Назад | сторінка 4 з 7 | Наступна сторінка





Схожі реферати:

  • Реферат на тему: Якщо ви викликаєте швидку допомогу
  • Реферат на тему: Якщо ремонт виявився модернізацією
  • Реферат на тему: Якщо лікарняний невірно розрахований
  • Реферат на тему: Якщо ваш працівник затриманий чи засуджений
  • Реферат на тему: Як бути, якщо контрагент за договором - нерезидент?