Размещено на http://www.allbest.ru/

Федеральное агентство связи

Сибирский государственный университет телекоммуникаций и информатики

Кафедра прикладной математики и кибернетики

Курсовая работа

«Структуры и алгоритмы обработки данных»

Вариант 37

Выполнил: студент группы П-02

Федоренко Г.К.

Проверил: Нечта И.В.

Новосибирск 2012



1. ПОСТАНОВКА ЗАДАЧИ

Хранящуюся в файле базу данных загрузить в оперативную память компьютера и построить индексный массив, упорядочивающий данные по дням рождения и ФИО, используя метод Вилльямса-Флойда в качестве метода сортировки.

Предусмотреть возможность поиска по ключу в упорядоченной базе, в результате которого из записей с одинаковым ключом формируется очередь, содержимое очереди выводится на экран.

Из записей очереди построить дерево АВЛ по номеру отдела, и предусмотреть возможность поиска в дереве по запросу.

Закодировать файл базы данных статическим кодом Шеннона, предварительно оценив вероятности всех встречающихся в ней символов. Построенный код вывести на экран, упакованную базу данных записать в файл, вычислить коэффициент сжатия данных.

База данных "Пpедпpиятие"

Стpуктуpа записи:

ФИО сотpудника: текстовое поле 32 символа

фоpмат <Фамилия>_<Имя>_<Отчество>

Hомеp отдела: целое число

Должность: текстовое поле 22 символа

Дата pождения: текстовое поле 8 символов

фоpмат дд-мм-гг

Пpимеp записи из БД:

Петpов_Иван_Иванович____________ 130

начальник_отдела______ 15-03-46

Варианты условий упорядочения и ключи поиска (К):

по номеру отдела и ФИО, К = номер отдела.

Ключ в дереве - номер отдела (как строка).



2. ОСНОВНЫЕ ИДЕИ И ХАРАКТЕРИСТИКИ ПРИМЕНЯЕМЫХ

МЕТОДОВ

2.1 МЕТОД СОРТИРОВКИ

Пирамидальная сортировка

Пирамидальная сортировка основана на алгоритме построения пирамиды. Последовательность a_i, a_i+1,…,a_k называется (i,k)-пирамидой, если неравенство

a_j?min(a_2j, а_2j+1) (*)

выполняется для каждого j, j=i,…,k для которого хотя бы один из элементов a_2j, a_2j+1 существует.

Например, массив А является пирамидой, а массив В не является.

А=(а₂ , а₃ , а₄ , а₅ , а₆ а₇ , а₈ )=(3, 2, 6, 4, 5, 7)

В=(b₁, b₂, b₃, b₄, b₅, b₆, b₇)=(3, 2, 6, 4, 5, 7)

Свойства пирамиды

1. Если последовательность a_i, a_i+1,…,а_k-1, a_k является (i, k)-пирамидой, то последовательность a_i+1,…,a_k-1, полученная усечением элементов с обоих концов последовательности, является (i+1, k-1)пирамидой.

2. Если последовательность a₁…a_n - (1, n)-пирамида, то а₁ - минимальный элемент последовательности.

3. Если a₁, a₂…,a_n/2,a_n/2+1,…a_n-произвольная последовательность, то последовательность a_n/2+1,…,a_n является (n/2+1, n)-пирамидой.

Процесс построения пирамиды выглядит следующим образом. Дана последовательность a_s+1,…,a_k, которая является (s+1, k)-пирамидой. Добавим новый элемент х и поставим его на s-тую позицию в последовательности, т.е. пирамида всегда будет расширяться влево. Если выполняется (*), то полученная последовательность - (s, k)-пирамида. Иначе найдутся элементы a_2s+1,a_2s такие, что либо a_2s < a_s либо a_2s+1 < a_s.

Пусть имеет место первый случай, второй случай рассматривается аналогично. Поменяем местами элементы a_s и a_2s. В результате получим новую последовательность a_s',a_s+1,…, a_2s',…, a_k. Повторяем все действия для элемента a_2s' и т.д. пока не получим (s, k)-пирамиду.

Пирамидальная сортировка производится в два этапа. Сначала строится пирамида из элементов массива. По свойству (3) правая часть массива является (n/2+1, n)-пирамидой. Будем добавлять по одному элементу слева, расширяя пирамиду, пока в неё не войдут все элементы массива. Тогда по свойству (2) первый элемент последовательности - минимальный.

Произведём двустороннее усечение: уберём элементы a₁,a_n. По свойству (1) оставшаяся последовательность является (2, n-1)-пирамидой. Элемент a₁ поставим на последнее место, а элемент a_n добавим к пирамиде a₂,…,a_n-1 слева. Получим новую (1, n-1)-пирамиду. В ней первый элемент является минимальным. Поставим первый элемент пирамиды на позицию n-1, а элемент a_n-1 добавим к пирамиде a₂,…,a_n-1, и т.д. В результате получим обратно отсортированный массив.

Величины М и С в процессе построения (L, R)-пирамиды имеют следующие оценки M_пир?log (R/L)+2, C_пир?2 log (R/L)

Общее количество операций сравнений и пересылок для пирамидальной сортировки: C ? 2n log n+n+2, M ? n log n+6.5n-4. Таким образом, С=O(n log n), М=O(n log n) при n > ?.

Отметим некоторые свойства пирамидальной сортировки. Метод пирамидальной сортировки неустойчив и не зависит от исходной отсортированности массива



2.2 ДВОИЧНЫЙ ПОИСК

Алгоритм двоичного поиска в упорядоченном массиве сводится к следующему. Берём средний элемент отсортированного массива и сравниваем с ключом X. Возможны три варианта:

Выбранный элемент равен X. Поиск завершён.

Выбранный элемент меньше X. Продолжаем поиск в правой половине массива.

Выбранный элемент больше X. Продолжаем поиск в левой половине массива.

Из-за необходимости найти все элементы соответствующие заданному ключу поиска в курсовой работе использовалась вторая версия двоичного поиска, которая из необходимых элементов находит самый левый, в результате чего для поиска остальных требуется просматривать лишь оставшуюся правую часть массива.

Верхняя оценка трудоёмкости алгоритма двоичного поиска такова. На каждой итерации поиска необходимо два сравнение для первой версии, одно сравнение для второй версии. Количество итераций не больше, чем . Таким образом, трудоёмкость двоичного поиска в обоих случаях

2.3 АВЛ-Дерево

Дерево поиска называется сбалансированным по высоте, или АВЛ - деревом, если для каждой его вершины высоты левого и правого поддеревьев отличаются не более чем на 1.

АВЛ-дерево никогда не будет в среднем по высоте превышать ИСДП более, чем на 45% независимо от количества вершин:



log(n+1) ? h_АВЛ(n) < 1,44 log(n+2) - 0,328 при n.

Таким образом, лучший случай сбалансированного по высоте дерева - ИСДП, худший случай - плохое АВЛ - дерево. Плохое АВЛ - дерево это АВЛ-дерево, которое имеет наименьшее число вершин при фиксированной высоте. Рассмотрим процесс построения плохого АВЛ-дерева. Возьмём фиксированную высоту h и построим АВЛ - дерево с минимальным количеством вершин. Обозначим такое дерево через T_h. Ясно, что Т₀ - пустое дерево, Т₁ - дерево с одной вершиной. Для построения Т_h при h > 1 будем брать корень и два поддерева с минимальным количеством вершин.

Одно поддерево должно быть высотой h-1, а другое высотой h-2. Поскольку принцип их построения очень напоминает построение чисел Фибоначчи, то такие деревья называют деревьями Фибоначчи: T_h = < T_h-1, x, T_h-2 >. Число вершин в T_h определяется следующим образом:

n₀ = 0, n₁ = 1, n_h = n_h-1 + 1 + n_h-2

Повороты при балансировке

Рассмотрим, что может произойти при включении новой вершины в сбалансированное по высоте дерево. Пусть r - корень АВЛ-дерева, у которого имеется левое поддерево (Т_L) и правое поддерево (T_R). Если добавление новой вершины в левое поддерево приведет к увеличению его высоты на 1, то возможны три случая:

1) если h_L = h_R, то Т_L и T_R станут разной высоты, но баланс не будет нарушен;

2) если h_L < h_R, то Т_L и T_R станут равной высоты, т. е. баланс даже улучшится;

3) если h_L > h_R, то баланс нарушиться и дерево необходимо перестраивать.

Введём в каждую вершину дополнительный параметр Balance (показатель баланса), принимающий следующие значения:

-1, если левое поддерево на единицу выше правого;

0, если высоты обоих поддеревьев одинаковы;

1, если правое поддерево на единицу выше левого.

Если в какой-либо вершине баланс высот нарушается, то необходимо так перестроить имеющееся дерево, чтобы восстановить баланс в каждой вершине. Для восстановления баланса будем использовать процедуры поворотов АВЛ-дерева.

Добавление вершины в дерево

Добавление новой вершины в АВЛ-дерево происходит следующим образом. Вначале добавим новую вершину в дерево так же как в случайное дерево поиска (проход по пути поиска до нужного места). Затем, двигаясь назад по пути поиска от новой вершины к корню дерева, будем искать вершину, в которой нарушился баланс (т. е. высоты левого и правого поддеревьев стали отличаться более чем на 1). Если такая вершина найдена, то изменим структуру дерева для восстановления баланса с помощью процедур поворотов.

Поиск элемента с заданным ключом, включения нового элемента, удаления элемента - каждое из этих действий в АВЛ-дереве можно произвести в худшем случае за О(log n) операций.

Отличие между процедурами включения и удаления заключается в следующем. Включение может привести самое большое к одному повороту, исключение может потребовать поворот во всех вершинах вдоль пути поиска. Наихудшим случаем с точки зрения количества балансировок является удаление самой правой вершины у плохого АВЛ-дерева (дерева Фибоначчи). По экспериментальным оценкам на каждые два включения встречается один поворот, а при исключении поворот происходит в одном случае из пяти.



2.4 МЕТОД КОДИРОВАНИЯ

Код Шеннона

Код Шеннона позволяет построить почти оптимальный код с длинами кодовых слов . Тогда по теореме Шеннона из п. 5.1

.

Код Шеннона, удовлетворяющий этому соотношению, строится следующим образом:

1. Упорядочим символы исходного алфавита А={a₁,a₂,…,a_n} по убыванию их вероятностей: p₁?p₂?p₃?…?p_n.

2. Вычислим величины Q_i:, которые называются кумулятивные вероятности

Q₀=0, Q₁=p₁, Q₂=p₁+p₂, Q₃=p₁+p₂+p₃, … , Q_n=1.

3. Представим Q_i в двоичной системе счисления и возьмем в качестве кодового слова первые знаков после запятой .

Для вероятностей, представленных в виде десятичных дробей, удобно определить длину кодового слова L_i из соотношения

, .

Пример. Пусть дан алфавит A={a₁, a₂, a₃, a₄, a₅, a₆} с вероятностями p₁=0.36, p₂=0.18, p₃=0.18, p₄=0.12, p₅=0.09, p₆=0.07. Построенный код приведен в таблице 6.



Таблица 6 Код Шеннона

ai	Pi	Qi	Li	кодовое слово
a1 a2 a3 a4 a5 a6	1/22?0.36<1/2 1/23?0.18<1/22 1/23?0.18<1/22 1/24?0.12<1/23 1/24?0.09<1/23 1/24?0.07<1/23	0 0.36 0.54 0.72 0.84 0.93	2 3 3 4 4 4	00 010 100 1011 1101 1110

Построенный код является префиксным. Вычислим среднюю длину кодового слова и сравним ее с энтропией. Значение энтропии вычислено при построении кода Хаффмана в п. 5.2 (H = 2.37), сравним его со значением средней длины кодового слова кода Шеннона

L_ср= 0.36^.2+(0.18+0.18)^.3+(0.12+0.09+0.07)^.4=2.92< 2.37+1,

что полностью соответствует утверждению теоремы Шеннона.



3. ОСОБЕННОСТИ РЕАЛИЗАЦИИ АЛГОРИТМОВ

В ходе выполнения курсовой работы, помимо основных алгоритмов, потребовалось реализовать также несколько вспомогательных, необходимых для корректной работы программы.

1. Интерфейс программы

Для удобства работы было создано примитивное консольное меню, позволяющее быстро задействовать ту или иную процедуру. С условием того что пользователь знает правильный порядок выполнения процедур. Общая структура меню состоит из процедуры switch() внутри которой расположены все возможные варианты меню, которые вызывают те или иные функции.

2. Загрузка и вывод базы данных

Для загрузки базы данных разработана процедура void Read(), в которой производится считывание записей типа struct BD(«Предприятие»). Здесь же предусмотрена проверка на наличие файла, откуда выполняется считывание. Данная процедура вызывается независимо от желания пользователя, в то время как остальные он может выбрать посредствам меню. Здесь же создаётся индексный массив day.

За вывод элементов считанной базы данных отвечает процедура voidPrintMas().

3.Вспомогательные функции и процедуры для сортировки данных

Для сортировки данных используется процедура void heapsort(int N) и void pyramid(int N_,int L,int R). Доступ к записям базы данных осуществляется через индексный массив day, для сортировки по отделам и ФИО используется процедуры int SravnenieFIO(int p1,int q1) и int SravnenieNumberO(int p1,int q1)возвращающие 1, если p-я запись меньше q-й, и 0 - иначе. Здесь же используется процедура сравнения двух строк int Compare(char s1[],char s2[],int number) (т.к. не используются стандартные процедуры сравнения двух строк), возвращающая 1, если строка s1<s2, 0, если s1>s2 и 2, если s1=s2.

4.Особенности реализации бинарного поиска

Бинарный поиск по отсортированной базе осуществляется в процедуре void Search(), доступ к записям ведётся через индексный массив day, найденные записи заносятся в очередь struct spisok, которая очищается перед каждым следующим поиском. Для вывода на монитор найденных записей используется процедура void Print(spisok *p). При реализации бинарного поиска была использована его вторая версия, так как в результате ее выполнения возвращается номер самого левого из найденных элементов, благодаря чему легко найти и вывести остальные элементы, лишь просмотрев оставшуюся правую часть массива, пока не встретится запись, не удовлетворяющая ключу поиска.

5. Вспомогательные функции и процедуры для построения дереваАВЛ.

При построении дерева АВЛ мы используем функцию void avl(struct BD D, derevo *&p), которая создает АВЛ дерево на базе списка и добавляет в него вершины. Функция также вызывает процедуру сравнения с помощью которой и определяется общее положение ветвей. Также мы используем функцию int PrintTree(derevo *p) для чтения данных из дерева. Поиск по дереву выполняет процедура void searsh(int ms,derevo *&p).

6. Кодирование данных

Кодирование базы данных начинается с процедуры void ShennonCode (FILE *f, char file_in[], char file_out[]) которая одновременно считает вероятности встречающихся символов и общее их количество, а также заносит информацию в индексные массивы. После сортировки через дополнительную функцию сортировки MergeSort снова меняет информацию в индексах и выводит символы, их вероятности, длины кодовых слов и сами кодовые слова на монитор. Также вычисляются энтропия и средняя длина кодового слова.



4. ОПИСАНИЕ ПРОГРАММЫ

4.1 ОСНОВНЫЕ ПЕРЕМЕННЫЕ И СТРУКТУРЫ

struct BD { char FIO[32]; // фоpмат <Фамилия>_<Имя>_<Отчество>

int numberO;

char dolzhnost[32];

char dateB[8];

} mas[10];

Запись, используемая для работы с базой данных «Предприятие».

mas[N] - массив на N элементов.

//Структура (список), используемая при сортировке базы данных.

struct spisok { spisok *next;

BD data;

} *spis,*head,*end;

spisok *next - указатель на следующие элемент;

BD data - поле данных (адрес элемента в основном массиве структур «Предприятие»).

//AVL DEREVO

struct derevo { BD sotrudnik;

short int bal;

struct derevo *left;

struct derevo *right;

struct derevo *down;

} *q,*r,*root,*start,*dn;

Структура, представляющая дерево АВЛ.

root - указатель на корень дерева.

BD sotrudnik - поле данных (адрес элемента в основном массиве структур «Предприятие»).

struct derevo *left;truct derevo *right;

- указатели на левое и правое поддеревья.

struct code

{

struct code *next;

unsigned char c;

double p;

int number;

}; Структура, предназначенная для кодирования базы данных.

Int *day - индексный массив.

FILE *f,*f2 - указатели на файл базы данных и на файл с кодированной базой.

char key_search[8]; - ключ поиска в дереве.

int rost,bal; - переменные роста и баланса для функции построения АВЛ

float entr,srdl; - переменные Энтропии и Ср.Длины для кодирования

4.2 ОПИСАНИЕ ПОДПРОГРАММ

Процедуры начальной обработки базы данных:

1. void Read() - считывает базу данных и формирует индексный массив.

2. void PrintMas(void) - осуществляет просмотр базы данных.

Функции и процедуры сортировки:

3 void heapsort(int N_)

4 void pyramid(int N_,int L,int R) эти 2 функции - сортируют базу данных по отделам и ФИО.

L - левая граница массива, R - правая граница массива.

Int Sravnenie(int p,int q) - сравнение дат рождения.

P,q - номера сравниваемых строк.

void avl(struct BD D, derevo *&p) - построение АВЛ дерева и добавление вершин в него.

int PrintTree(derevo *p) чтение АВЛ дерева

void searsh(int ms,derevo *&p) ) - поиск в дереве по ключу.

int CompareDate(char s1[],char s2[]) - сравнение Фамилий

// Процедура расщепления для кодирования

void SplittingCode(struct code *HEAD, struct code *&a, struct code *&b)

//Процедура слияния для кодирования

void MergeCode (struct code *&a, struct code *&b, int q, int r, struct code *&c)

// Процедура сортировки методом прямого слияния для кодирования

void MergeSortCode(struct code *&HEAD,int N_)

// Процедура кодирования базы данных методом Шеннона

void ShennonCode (FILE *f, char file_in[], char file_out[])

//Сравнение по фио.

int SravnenieFIO(int p1,int q1)

//Добавление в из массива в список

void Addfrommas()



4. ТЕКСТ ПРОГРАММЫ

#include <cctype>

#include <math.h>

#include <clocale>

#include <iostream>

#include <windows.h>

#include <time.h>

#define N 10

#define n 10

using namespace std;

//Вариант 37

int *day;

unsigned long int number;

struct code

{

struct code *next;

unsigned char c;

double p;

int number;

};

int sc=0;

float entr,srdl;

int rost,bal;

char key_search[8];

FILE *f1,*f2;

//База данных "Пpедпpиятие"

struct BD { char FIO[32]; // фоpмат <Фамилия>_<Имя>_<Отчество>

int numberO;

char dolzhnost[32];

char dateB[8];

} mas[10];

//Структура (список), используемая при сортировке базы данных.

struct spisok { spisok *next;

BD data;

} *spis,*head,*end;

struct list

{

struct BD note;

struct list *next;

};

struct list *basehead,*keylist;

//AVL DEREVO

struct derevo { BD sotrudnik;

short int bal;

struct derevo *left;

struct derevo *right;

struct derevo *down;

} *q,*r,*root,*start,*dn;

//ДЛЯ ПОИСКА

//по номеpу отдела и ФИО, К = номеp отдела;

int Compare(char s1[],char s2[],int number)

{

int i=0;

do

{if (s1[i]<s2[i]) return 1;

else if (s1[i]>s2[i]) return 0;

else i++;

}

while (i<number);

return 2;

}

//Сравнение по номеру отдела и по фио.

int SravnenieFIO(int p1,int q1)

{ if (Compare(mas[p1].FIO,mas[q1].FIO,32)==1) return 1; // I<I+1

else if (Compare(mas[p1].FIO,mas[q1].FIO,32)==0) return 0; // I>I+1

}

int SravnenieNumberO(int p1,int q1)

{

if (mas[p1].numberO>mas[q1].numberO) return 0;// I>I+1

else if (mas[p1].numberO<mas[q1].numberO) return 1; // I<I+1

}

void bubble(int N_)

{

int i,j,x;

struct BD temp;

for (i=1;i<N_-1;i++) {

for (j=0;j<N_-i;j++) {

if (SravnenieNumberO(day[j],day[j+1])==1) { temp=mas[day[j]]; mas[day[j]]=mas[day[j+1]]; mas[day[j+1]]=temp; } }}

}

//Сортировка Пирамидальная

void pyramid(int N_,int L,int R)

{

int i,j,x;

x=day[L]; i=L;

printf("x=%d\ti=%d\tR=%d\n",x,i,R);

while (true) { j=2*i;

printf("j=%d\n",j);

if (j>R) { break;}//

if ((j<R)&& SravnenieNumberO(day[j+1],day[j])==1 ) { j++; }

if (SravnenieNumberO(x,day[j])==1) { break;} //

//mas[day[i]]=mas[day[j]]; i=j;

//day[i]=day[j]; i=j;

mas[i]=mas[j]; i=j;

}; //do

day[i]=x;

}

void heapsort(int N_)

{

int i,j,x,L,R=N_;

int z,g; z=g=0;

struct BD temp;

L=1;

L=(int)(N_)/2;

while(L>=0)

{ //построение пирамиды

pyramid(N_,L,N_-1);

L=L-1;

};//while

R=N_;

while (R>=1) { z++; printf("z=%d\n",z);

//temp=mas[day[1]]; mas[day[1]]=mas[day[R]]; mas[day[R]]=temp;

temp=mas[R]; mas[R]=mas[0]; mas[0]=temp;

// temp=mas[day[0]]; mas[day[0]]=mas[day[R]]; mas[day[R]]=temp;

R=R-1;

pyramid(N_,1,R);

g++; printf("g=%d\n",g);

}//while;

}

void Read() //Считывает базу данных,формирует индексный массив

{

int i;

f1=fopen("BASE2.DAT","rb");

day=(int*)realloc(day,N*sizeof(int));

//for (i=0;i<N;i++) free(mas[i]);

for (i=0;i<N;i++)

{

//mas[i]=(BD*)malloc(sizeof(BD));

fgets(mas[i].FIO,32,f1);

fgetc(f1);//отступ по символу

mas[i].numberO=fgetc(f1);

fgetc(f1);

fgets(mas[i].dolzhnost,22,f1);

fgetc(f1);

fgets(mas[i].dateB,8,f1);

fgetc(f1);

day[i]=i;

}

fclose(f1);

}

//void PrintMas(void) - осуществляет просмотр базы данных.

void PrintMas()

{ int i; char h;

//system("cls");

for (i=0;i<10;i++)

{ printf("%4.d].%s %d %s %s\n",i+1,mas[day[i]].FIO,mas[day[i]].numberO,mas[day[i]].dolzhnost,mas[day[i]].dateB);

if (kbhit()) { h=getch(); if (h==27) break; else getch(); }//FI

}//FOR

}

void Addfrommas()

{ int i; spisok *p;

head=NULL;

for(i=0;i<n;i++){

p=(spisok*)malloc(sizeof(spisok));

if(i==0) {p->next=NULL; head=p; end=p; } else {p->next=NULL; end->next=p; end=p;}

p->data=mas[day[i]];

//printf("\n%s\n",p->data.FIO);

}

}

void Print(spisok *p)

{

char h; int x=0;

do

{

printf("%s",p->data.FIO);

printf("%03d\t",p->data.numberO);

printf("%s\t",p->data.dolzhnost);

printf("%s\n",p->data.dateB);

x++;

//if (p->next==NULL) break;

p=p->next;

} while (p!=NULL );

}

void avl(struct BD D, derevo *&p)

{

if (p==NULL)

{

p=(derevo *)malloc(sizeof(derevo));

p->sotrudnik=D;

p->left=NULL; p->right=NULL; p->down=NULL;

p->bal=0;

rost=1;

}

else

{ if(SravnenieNumberO(D.numberO,(p->sotrudnik.numberO)==1)) {dn=p;

while(1) {if (dn->down==NULL) {

dn->down=(derevo*)malloc(sizeof(derevo));

dn->down->sotrudnik=D; dn->down->down=NULL; break;}

else dn=dn->down;}

rost=0;}

if(SravnenieNumberO(D.numberO,(p->sotrudnik.numberO)==0))

{

avl(D,p->left);

if (rost)

{

if(p->bal>0)

{p->bal=0; rost=0;}

else

if( p->bal == 0)

{p->bal=-1;

}

else

{

if (p->left->bal < 0)

{ q=p->left;

p->bal=0;

q->bal=0;

p->left=q->right;

q->right=p;

p=q; rost=0;

} /*ll*/

else

{ q=p->left;

r=q->right;

if(r->bal < 0) p->bal=1;

else p->bal=0;

if(r->bal > 0) q->bal=-1;

else q->bal=0;

r->bal=0;

q->right=r->left;

p->left=r->right;

r->left=q;

r->right=p;

p=r;

rost=0;

} /*lr*/

}

}

}

//-------добавление в правое поддерево------------

if(SravnenieNumberO(D.numberO,(p->sotrudnik.numberO)==0))

{

avl(D,p->right);

if (rost)

{

if(p->bal < 0)

{p->bal=0; rost=0;}

else

if(p->bal==0)

{p->bal=1;

}

else

{

if (p->right->bal > 0)

{ q=p->right;

p->bal=0;

q->bal=0;

p->right=q->left;

q->left=p;

p=q; rost=0;

} /*rr*/

else

{

q=p->right;

r=q->left;

if( r->bal <0) q->bal=-1;

else q->bal=0;

if( r->bal >0) p->bal=1;

else p->bal=0;

r->bal=0;

p->right=r->left;

q->left=r->right;

r->left=p;

r->right=q;

p=r;

rost=0;

} /*rl*/

}

}

}

}

}

int PrintTree(derevo *p)

{

if (p!=NULL)

{

PrintTree(p->left);

printf("%s\n%d\n%s\n%s\n-----------------------\n\n",p->sotrudnik.FIO,

p->sotrudnik.numberO,

p->sotrudnik.dolzhnost,

p->sotrudnik.dateB);

sc++;

dn=p; while(1)

{if (dn->down!=NULL)

{printf("%s\n%d\n%s\n%s\n-----------------------\n\n",dn->down->sotrudnik.FIO,dn->down->sotrudnik.numberO,

dn->down->sotrudnik.dolzhnost,dn->down->sotrudnik.dateB); sc++; dn=dn->down;}

else break; }

PrintTree(p->right);

} данные компьютер код

return 0;

}

int ravns(int ms, BD d2)

{ if(ms>d2.numberO) return 1;

if(ms<d2.numberO) return -1;

return 0;

}

void searsh(int ms,derevo *&p)

{ if(p==NULL) printf("\nNot found\n");

else {

if(ravns(ms,p->sotrudnik)==0){ printf("%s\n%d\n%s\n%s\n-----------------------\n\n",p->sotrudnik.FIO,p->sotrudnik.numberO,p->sotrudnik.dolzhnost,p->sotrudnik.dateB);

dn=p;

while(1)

{ if (dn->down!=NULL) {printf("%s\n%d\n%s\n%s\n-----------------------\n\n",dn->down->sotrudnik.FIO,dn->down->sotrudnik.numberO,

dn->down->sotrudnik.dolzhnost,dn->down->sotrudnik.dateB); dn=dn->down;}

else break;

}

}

if(ravns(ms,p->sotrudnik)>0) searsh(ms,p->right);

if(ravns(ms,p->sotrudnik)<0) searsh(ms,p->left);

}

}

spisok *spissearsh(int ms,spisok *p)

{spisok *rt,*rthead,*rttail;

int i=0 ;

while(p->next!=0)

{ rt=(spisok*)malloc(sizeof(spisok));

if(ravns(ms,p->data)==0)

{

if(i==0) {rt->next=NULL; rthead=rt; rttail=rt; i=1; } else {rt->next=NULL; rttail->next=rt; rttail=rt;}

rt->data=p->data; p=p->next;

}

else p=p->next;

}

return rthead;

}

//============================КОДИРОВАНИЕ

// Процедура записи данных из одного списка в другой

void moveLtQ (struct code *&l, struct code *&t){

t->next=l;

t=l;

l=l->next;

}

// Процедура расщепления для кодирования

void SplittingCode(struct code *HEAD, struct code *&a, struct code *&b)

{

struct code *k,*p;

a=HEAD;

b=HEAD->next;

k=a;

p=b;

while (p!=NULL)

{

k->next=p->next;

k=p;

p=p->next;

}

}

//Процедура слияния для кодирования

void MergeCode (struct code *&a, struct code *&b, int q, int r, struct code *&c)

{

while (q!=0 && r!=0)

{

if (a->p > b->p)

{

moveLtQ(a,c);

q--;

}

else

{

moveLtQ(b,c);

r--;

}

}

while (q>0)

{

moveLtQ(a,c);

q--;

}

while (r>0)

{

moveLtQ(b,c);

r--;

}

}

// Процедура сортировки методом прямого слияния для кодирования

void MergeSortCode(struct code *&HEAD,int N_)

{

struct code *a,*b,*ch[2],*ct[2];

int p,q,r,m,i;

SplittingCode(HEAD,a,b);

p=1;

while (p<N_)

{

ch[0]=ch[1]=NULL;

ct[0]=(code*)&ch[0];

ct[1]=(code*)&ch[1];

i=0;

m=N_;

while (m>0)

{

if (m>=p)

q=p;

else q=m;

m=m-q;

if (m>=p)

r=p;

else r=m;

m=m-r;

MergeCode(a, b, q, r, ct[i]);

i=1-i;

}

a=ch[0];

b=ch[1];

p*=2;

}

ct[0]->next=NULL;

HEAD=ch[0];

}

// Процедура кодирования базы данных методом Шеннона

void ShennonCode (FILE *f, char file_in[], char file_out[])

{

unsigned char *d, *dd, **C; //временные перменные для информации, двумерный массив

double H,LA,td,Q[257]; //H - энтропия, LA средняя длина, Q сумма вероятностей

int i,j,_N,lbit,lbyte,pbit,pbyte,cbit,lt,inds,L[256],INDX[256],INDXB[256]; //индексные массивы

//pbit pbyte - для записи побитовой

int l=sizeof(struct BD)*N; //l общее кол-во симаволов во всем файле

struct code *lst, *hlst, *p; //используемые списки для кодирповаия

f=fopen(file_in, "rb");

if (f==NULL)

{

printf("File not found.");

getch();

return;

}

d=(unsigned char*)malloc(l);//все символы в Д считывает

fread(d, 1, l, f);

fclose(f);

lst=(struct code*)malloc(sizeof(struct code)*256); //список в который последовательно по каждому возможному симвоу будет вноситься инфа

for (i=0; i<256; i++) //256 - всевозможные АСКИ символы

lst[i].number=0; //подсчет кол-ва используемых символов в файле

for (i=0; i<l; i++)

lst[d[i]].number++; //если такой символ встретился то он перемещается в нужную ячейку увеличивает параметр обращения к себе

_N=0;

for (i=0; i<256; i++)

{

if (lst[i].number)

_N++;

lst[i].next=(&(lst[i]))+1; //переходим в следующий эл-т списка

lst[i].p=(double)lst[i].number/l; //расчитываем вероятность

lst[i].c=i; //записываем символ

}

hlst=lst;

lst[255].next=NULL;

MergeSortCode(lst,256);

for (p=lst, i=0; i<_N; p=p->next, i++)

INDX[i]=p->c;

for (i=0; i<_N; i++)

INDXB[INDX[i]]=i; //заносим инфо в индексные массивы

Q[0]=0;

H=LA=0;

for (i=0; i<_N; i++)//по псевдокоду

{

Q[i+1]=Q[i]+hlst[INDX[i]].p;

td=-log(hlst[INDX[i]].p)/0.693147180559945309417;

L[i]=(int)ceil(td);

H=H+td*hlst[INDX[i]].p;

LA=LA+L[i]*hlst[INDX[i]].p;

}

C=(unsigned char**)malloc(sizeof(unsigned char*)*_N);

for (i=0; i<_N; i++)

{

C[i]=(unsigned char*)malloc(sizeof(unsigned char)*L[i]);

}

for (i=0; i<_N; i++)

{

for (j=0; j<L[i]; j++)

{

Q[i]*=2;

C[i][j]=(Q[i]);

if (Q[i]>=1)

Q[i]=Q[i]-1;

}

}

for (i=0; i<_N; i++)

{

printf("%c:(%3i):",hlst[INDX[i]].c,hlst[INDX[i]].c);

for (j=0; j<L[i]; j++)

{

printf("%i",C[i][j]);

}

printf("\n");

}

for (i=lbit=0; i<_N; i++)

lbit=lbit+hlst[INDX[i]].number*L[i]; //преставляем в нулях и единицах информацию

lbyte=lbit/8;

if (lbit%8)

lbyte++;

dd=(unsigned char*)malloc(lbyte);

for (i=0; i<lbyte; i++)

dd[i]=0;

for (i=pbit=0; i<l; i++)

{

inds=INDXB[d[i]];

lt=L[inds];

for (j=0; j<lt; j++,pbit++)

{

pbyte=pbit/8;

cbit=pbit%8;

dd[pbyte]|=C[inds][j]<<(7-cbit); //побитовый сдвиг

}

} //Разница м\у Энтрпией и сред.дл Степень Сжатия

printf ("Entropy=%f \nAverage Length=%f \nRedundancy=%f\nCompression ratio=%f\n",

H,LA,LA-H,(double)l/lbyte);

f=fopen(file_out, "wb");

if (f==NULL)

printf ("File not created");

else {

fwrite(dd, 1, lbyte, f);

fclose(f);

}

for (i=0; i<_N; i++)

free(C[i]);

free(C);

free(hlst);

free(d);

}

int main(void)

{ //setlocale(LC_ALL,"rus");

char c; int i; int nom; char zz;

FILE *Base;

while (c!='n') { system("cls");

printf("1 - Read base from file.\n");

printf("2 - On Bubble sort.\n");

printf("3 - On Heap sort.\n");

printf("4 - Read massiv\n");

printf("5 - Read Spisok\n");

printf("6 - Read AVL\n");

printf("7 - Add data in AVL tree\n");

printf("8 - Add data in Spisok\n");

printf("9 - Search\n");

printf("10 - Shennon Code\n");

printf("n - Exit\n");

scanf("%c",&c);

switch(c)

{ case '1': { system("cls"); Read(); printf("Information:\n"); PrintMas(); printf("OK!"); getch(); system("cls"); break; }

case '2': { system("cls"); bubble(n); printf("OK!"); getch(); system("cls"); break; }

case '3': { system("cls"); heapsort(10); printf("OK!");getch(); system("cls"); break; }

case '4': { system("cls"); PrintMas(); printf("OK!"); getch(); system("cls"); break; }

case '5': { system("cls"); Print(head); printf("OK!"); getch(); system("cls"); break; }

case '6': { system("cls"); PrintTree(root); printf("OK!");getch(); system("cls"); break; }

case '7': { system("cls"); root=NULL; for (i=0;i<n;i++){ avl(head->data,root); head=head->next;}

printf("OK!");getch(); system("cls"); break; }

case '8': { system("cls"); Addfrommas(); printf("OK!");getch(); system("cls"); break; }

case '9': { system("cls"); printf("Input number otdela.."); scanf("%d",&nom); searsh(nom,root); getch();

system("cls"); break; }

case '10': { system("cls"); ShennonCode (Base,

"BASE2.dat",

"OutBase.dat"); printf("\nOK"); getch();

system("cls"); break; }

} }

/*

//s1=s1->next;

// }

Read();

// PrintMas();

// heapsort(10);

bubble(10);

//system("cls");

// PrintMas();

Addfrommas();

// Print(head);

// struct spisok p1;

//p1=head;

// getch();

for (i=0;i<n;i++){ avl(head->data,root); head=head->next;}

// PrintTree(root);

while(nom!=) {

system("cls");

printf("Input number otdela.."); scanf("%d",&nom);

searsh(nom,root); getch(); system("cls"); printf("one more or quit? (quit - '0')"); getch(); scanf("%d",&nom);}

getch();

*/

return 0;

}

Размещено на Allbest.ru