Курсовая работа "Структуры и алгоритмы обработки данных" вариант 11 студент группы п 64 Ивантеева А. В - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1страница 2
Похожие работы
Название работы Кол-во страниц Размер
Программа дисциплины «Алгоритмы и структуры данных» 3 260.07kb.
Лабораторная работа №2 По курсу «Структуры и алгоритмы обработки... 1 70.56kb.
1. Каждая контрольная работа включает 5 вариантов. Студент должен... 5 683.6kb.
Курсовая работа «Выдающиеся креаторы XX века: анализ рекламных концепций»... 1 460.82kb.
Курсовая работа по дисциплине «Устройство и эксплуатация пути» студент... 2 452.85kb.
Курсовая работа на тему: «Развитие рекламной индустрии Японии в послевоенный... 1 371.82kb.
Учебно-методический комплекс по дисциплине "структуры и алгоритмы... 1 266.6kb.
Контрольная работа содержит четыре варианта для выполнения математической... 1 38.07kb.
Эмпирическое исследование или инновационная работа в области практической... 1 160.24kb.
Курсовая работа «Защищенное хранилище данных» 1 47.59kb.
Программа элективного курса по информатике для учащихся 9 класса... 1 228.24kb.
Н. И. Дробышевский, А. Е. Киселёв, В. Ф. Стрижов, А. С. Филиппов... 1 358.42kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

Курсовая работа "Структуры и алгоритмы обработки данных" вариант 11 студент группы - страница №1/2

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

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


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

КУРСОВАЯ РАБОТА

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

ВАРИАНТ 11

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

Ивантеева А.В.

Проверил: доцент кафедры ПМиК Курапова Е.В.

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


СОДЕРЖАНИЕ

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

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

2.1. Метод сортировки

2.2. Двоичный поиск

2.3. Дерево и поиск по дереву

2.4. Метод кодирования

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

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

4.1. Основные переменные и структуры

4.2. Описание подпрограмм

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

6. РЕЗУЛЬТАТЫ

7. ВЫВОДЫ


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

Хранящуюся в файле базу данных загрузить в оперативную память компьютера и построить индексный массив, упорядочивающий данные по дате рождения, используя метод прямого слияния (Merge Sort) в качестве метода сортировки.

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

Из записей очереди построить двоичное Б - дерево поиска по дням рождения, и предусмотреть возможность поиска в дереве по запросу.

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

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

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

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

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

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

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

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

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

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

130

начальник_отдела______



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

по дате рождения, К = год рождения.

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

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

2.1. Метод сортировки

Метод прямого слияния

В основе метода прямого слияния лежит операция слияния серий. р-серией называется упорядоченная последовательность из р элементов.

Пусть имеются две упорядоченные серии a и b длины q и r соответственно. Необходимо получить упорядоченную последовательность с, которая состоит из элементов серий a и b. Сначала сравниваем первые элементы последовательностей a и b. Минимальный элемент перемещаем в последовательность с. Повторяем действия до тех пор, пока одна из последовательностей a и b не станет пустой, оставшиеся элементы из другой последовательности переносим в последовательность с. В результате получим (q+r)-серию.

Для алгоритма слияния серий с длинами q и r необходимое количество сравнений и перемещений оценивается следующим образом

min(q, r) ≤ C ≤ q+r-1, M=q+r

Пусть длина списка S равна степени двойки, т.е. 2k, для некоторого натурального k. Разобьем последовательность S на два списка a и b, записывая поочередно элементы S в списки а и b. Сливаем списки a и b с образованием двойных серий, то есть одиночные элементы сливаются в упорядоченные пары, которые записываются попеременно в очереди c0 и c1. Переписываем очередь c0 в список a, очередь c1 – в список b. Вновь сливаем a и b с образованием серий длины 4 и т. д. На каждом итерации размер серий увеличивается вдвое. Сортировка заканчивается, когда длина серии превысит общее количество элементов в обоих списках. Если длина списка S не является степенью двойки, то некоторые серии в процессе сортировки могут быть короче.

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

Дополнительные n перемещений происходят во время начального расщепления исходного списка. Асимптотические оценки для М и С имеют следующий вид



Метод обеспечивает устойчивую сортировку. При реализации для массивов, метод требует наличия второго вспомогательного массива, равного по размеру исходному массиву. При реализации со списками дополнительной памяти не требуется.


2.2. Двоичный поиск

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

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

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

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

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

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

2.3. Дерево и поиск по дереву



Двоичное Б-дерево

Двоичное Б-дерево состоит из вершин (страниц) с одним или двумя элементами. Следовательно, каждая страница содержит две или три ссылки на поддеревья. На рисунке показаны примеры страниц Б – дерева при m = 1.



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



Таким образом, страницы Б-дерева теряют свою целостность и элементы списков начинают играть роль вершин в двоичном дереве. Однако остается необходимость делать различия между ссылками на потомков (вертикальными) и ссылками на одном уровне (горизонтальными), а также следить, чтобы все листья были на одном уровне.

Очевидно, двоичные Б-деревья представляют собой альтернативу АВЛ-деревьям. При этом поиск в двоичном Б-дереве происходит как в обычном двоичном дереве.

Высота двоичного Б-дерева



.

Если рассматривать двоичное Б-дерево как обычное двоичное дерево, то его высота может увеличиться вдвое, т.е. . Для сравнения, в АВЛ-дереве даже в самом плохом случае h<1.44 log n. Поэтому сложность поиска в двоичном Б-дереве и в АВЛ-дереве одинакова по порядку величины.

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

Метод Хаффмена

Алгоритм построения оптимального кода Хаффмена



  1. Упорядочим символы исходного алфавита А={a1,…,an} по убыванию их вероятностей p1≥p2≥…≥pn.

  2. Если А={a1,a2}, то a1→0, a2→1.

  3. Если А={a1,…,aj,…,an} и известны коды j → bj >, j = 1,…,n ,то для {a1,…aj’ ,aj’’…,an}, p(aj)=p(aj’)+ p(aj’’), aj’ → bj0, aj’’ →bj1.

Пусть дан алфавит A={a1, a2, a3, a4, a5, a6} с вероятностями p1=0.36, p2=0.18, p3=0.18, p4=0.12, p5=0.09, p6=0.07. Будем складывать две наименьшие вероятности и включать суммарную вероятность на соответствующее место в упорядоченном списке вероятностей до тех пор, пока в списке не останется два символа. Тогда закодируем эти два символа 0 и 1. Далее кодовые слова достраиваются, как показано на рисунке:

Таблица кода Хаффмена



Посчитаем среднюю длину, построенного кода Хаффмена

Lср(P) = 1.0*36 + 3*0.18 + 3*0.18 + 3*0.12 + 4*0.09 + 4*0.07 = 2.44,

при этом энтропия данного источника равна

H = -(0.36*log0.36 + 2*0.18*log0.18 +0.12*log0.12+ 0.09*log0.09 + 0.07*log0.07) = 2.37

Код Хаффмена обычно строится и хранится в виде двоичного дерева, в листьях которого находятся символы алфавита, а на «ветвях» – 0 или 1. Тогда уникальным кодом символа является путь от корня дерева к этому символу, по которому все 0 и 1 собираются в одну уникальную последовательность.




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

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


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

Для организации интерфейса использовалась процедура void menu(), которая обеспечивает корректное и незатруднительное использование программы и предоставляет возможность многократного выбора различных вариантов обработки базы данных, в зависимости от задач пользователя. Визуальное представление пунктов меню вынесено в отдельную процедуру void info().


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

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

За вывод элементов считанной базы данных отвечает процедура void ViewBase Она предоставляет возможность постраничного просмотра базы данных(по 4 элемента на странице), смена страниц осуществляется нажатием управляющих стрелок «вверх» и «вниз» на клавиатуре. Есть возможность прервать просмотр в любой момент времени нажатием клавиши «Esc».
3. Вспомогательные функции и процедуры для сортировки данных

При сортировке базы данных потребовалось реализовать дополнительную процедуру void InvertDate для преобразования даты рождения в формат, соответствующий условию упорядочивания(«дд-мм-гг» в «гг-мм-дд»), а также определить операцию сравнения двух строк(не используя стандартные процедуры среды) для последующего применения в алгоритме сортировки. Данную функция выполняет процедура char compare, которая поэлементно сравнивает две строки и при первом различии возвращает результат.


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

Для того чтобы без проблем многократно осуществлять поиск элементов, соответствующих разным ключам, требуется каждый раз создавать новую очередь, и чтобы постоянно не выделять память(которая, как известно, не безгранична) процедура void FreeQueue – очищает , ту что была распределена при предыдущем вызове функции построения очереди - void MakeQueue. Новая очередь же, строится непосредственно после выполнения поиска. При его реализации была использована вторая версия двоичного поиска, так как в результате ее выполнения возвращается номер самого левого из найденных элементов, благодаря чему легко найти и вывести остальные элементы, лишь просмотрев оставшуюся правую часть массива.


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

Также как и для очереди, при неоднократном построении дерева требуется освобождать память, эту функцию выполняет процедура void FreeTree. Для вывода дерева на экран используется процедура void PrintTree, представляющая собой обход дерева слева – направо.

Аналогичная процедура void PrintSearch выполняет вывод результатов поиска в дереве.
6. Кодирование данных

При побуквенном кодировании существует необходимость знать вероятности встречаемости символов. Для их подсчета создана процедура void Probabilities(), в которой помимо вычисления значений вероятностей производится их вывод и и вывод алфавита кодируемого текста в сортированном по вероятностям и несортированном виде. Для сортировки массива вероятностей использовалась процедура сортировки методом Хоара, так как обладает сравнительно небольшой трудоемкостью и применима непосредственно для сортировки массивов.

И, наконец, для вычисления характеристик полученного кода разработана процедура void parametrs, где вычисляются основные параметры(средняя длина кодового слова и энтропия), а также производится оценка их соотношения.


Подробное описание основных и вспомогательных функций и процедур, алгоритмы их работы и параметры приведены далее в разделе «ОПИСАНИЕ ПРОГРАММЫ»

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

4.1. Основные переменные и структуры



***

struct Firma{

char Sotrudnik[32];

unsigned short int Nomer;

char Dolgnost[22];

char DataR[8];

};

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


***

struct qel{

struct qel *next;

struct Firma *data;

};

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



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

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

struct queueS {

qel *head;

qel *tail;

};

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



qel *headголова очереди;

qel *tailхвост очереди.
***

struct queue {

int index;

struct queue *next;

}

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



int index – индекс элемента в базе данных;

struct queue *next – указатель на следующий элемент.
***

struct derevo{

int x;

int balance;

struct derevo *left;

struct derevo *right;

}

Структура, представляющая двоичное Б – дерево. Где int x - индекс элемента из базы данных, а не сам элемент.



int balance – баланс в вершине(больше 0 если правое поддерево на 1 выше левого, меньше 0, если выше левое и равно 0 при равных высотах левого и правого поддеревьев);

struct derevo *left, struct derevo *right – указатели на левое и правое поддеревья.
***

int index[MAX+1];

Индексный массив на 3999+1 элементов.



***

struct Firma *el[MAX];

Указатель на массив структур «Предприятие».


***

float P[256] – массив вероятностей встречаемости символов;

P1[256] – копия массива P[] для подсчета характеристик сжатия после кодирования.
***

int maxpowerколичество различных символов в базе данных;

long amountобщее количество символов(используется для подсчета вероятностей);

4.2. Описание подпрограмм



Процедуры, вывода меню:

1. void menu();

2. void info();

Реализуют меню, info – отвечает только за визуальное представление, menu – непосредственно за функциональное.



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

3. struct qel * LoadMem();

4. void ViewBase(struct Firma **el,int iN);
LoadMem – считывание базы из файла и представление ее элементов в форме вышеперечисленных структур, возвращает указатель на массив записей «Предприятие».

ViewBase - просмотр базы. struct Firma **el – указатель на первый элемент, iN – общее количество записей в базе.

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

5. void InvertDate(char aData[],int n);

6. char compare(char aData[],char bData[],int n);

7. int Devide(qel* &s, qel* &a, qel* &b);

8. void Merging(qel* &a, qel* &b, queueS &c, int q, int r);

9. qel* MergeSort(qel* s);
InvertDate – вспомогательная процедура для преобразования даты (представленной в виде символьного массива char aData[], размерностью n) в формат соответствующий условию упорядочивания(«дд-мм-гг» в «гг-мм-дд»).

Compare – определение операции сравнения двух массивов: char aData[],char bData[] размерностью n. Возвращает 1 в случае, если a > b и 2, если ab.

Devide, Merging, MergeSort – реализация сортировки.

Devide – разделение последовательности s на два списка a и b, возвращает количество элементов в списке s.

Merging – слияние q – серии из списка a c r – серией списка b, запись результата в очередь c.

MergeSort – инициализация очередей, сама процедура сортировки элементов последовательности s, возвращает голову(head) первой из двух инициализированных очередей.

Функции и процедуры для поиска в отсортированной базе данных:

10. int BinSearch(struct Firma **x,int N,int *pointers,char *value);

11. void FreeQueue(queue *p);

12. void MakeQueue(char *n,struct queue *pq,int *index,int pos);

13. void PrintQueue(struct queue *p);
BinSearch – процедура двоичного поиска (версия 2), struct Firma **x – указатель на массив записей, в котором осуществляется поиск, N – количество записей(изначально - правая граница поиска), pointers – указатель на индексный массив, через который происходит обращение к элементам, value – ключ поиска. Возвращает позицию найденного элемента и -1, в случае его отсутствия.

FreeQueue – освобождение памяти для очереди p, если, например, она уже создавалась.

MakeQueue – построение очереди из результатов поиска. n – самый левый из найденных элементов, pq – голова очереди, index – указатель на индексный массив, pos – позиция, в которой был найден нужный элемент, от нее просматриваем массив только вправо.

PrintQueue – вывод очереди p (struct queue *pуказатель на первый элемент очереди) на экран.

Процедуры и функции построения двоичного Б-дерева:

14. void FreeTree(derevo *p);

15. void CreateDBD(int D, struct Firma **base, struct derevo **p,int *index);

16. void PrintTree(struct Firma **x,struct derevo *p,int *index);

17. struct derevo *SearchInTree(char key[],struct Firma **x,struct derevo *p);

18. void PrintSearch(char key[],struct Firma **x,struct derevo *p);
FreeTree – освобождение памяти для построения дерева, чтобы не возникало проблем, в случае если до этого дерево уже создавалось (derevo *p – указатель на корень дерева).

CreateDBD – непосредственно построение, D – данные, помещаемые в вершину (индекс элемента), base – указатель на массив структур (обращение к нему происходит при сравнении элементов через индексный массив), p – указатель на корень дерева, index - указатель на индексный массив.

PrintTree обход дерева с корнем derevo *p, используемый для вывода на экран отсортированных по дате рождения(дата рождения как строка) элементов базы данных(struct Firma **x – указатель на массив структур «Предприятие»), в соответствии с индексным массивом – index (int *index – указатель на него), элементы которого хранятся в вершинах дерева p.

SearchInTreeпоиск в дереве с корнем derevo *p элементов, соответствующих ключу char key[], struct Firma **x – указатель на массив структур, к которому обращаемся при поиске, используя вершины дерева p в качестве индексов. Возвращает адрес вершины, в которой хранится индекс найденного элемента и NULL, в случае его отсутствия.

PrintSearch – вывод на экран результатов поиска (обход поддерева, начиная с вершины с адресом struct derevo *p, в которой был найден первый элемент, соответствующий ключу поиска, до того, пока не закончатся все элементы удовлетворяющие заданному условию), параметр struct derevo *p обычно изначально принимает значение, возвращаемое предыдущей функцией). Остальные параметры такие же, как и в вышеописанной процедуре.

Процедуры и функции кодирования базы данных:

19. void Probabilities();

20. void quick(float *x,int n);

22. void quicksort(float *x,int left, int right);

23. void huffman(int n);

24. int Up(int n,float q1);

25. void Down(int n,int j);

26. void parametrs(int K,float *P);
Probabilities – процедура определения вероятностей встречаемости символов. Символы считываются из файла, описанного макроопределением #define default "D:\\base2.dat"

quick основной вызов процедуры сортировки массива, представленного указателем float *x, размерностью n.

quicksort – сортировка вероятностей встречаемости символов методом Хоара. float *x – указатель на сортируемый массив, int left, int right – левая и правая границы сортируемого фрагмента.

Huffman – составление матрицы кодовых слов для алфавита мощностью int n – количеством различных символов в кодируемом тексте.

Up – процедура поиска подходящей позиции для суммы вероятностей двух последних символов, ее вставка и сдвиг остальных элементов. int n – нижняя граница поиска, float q1 – вставляемая сумма.

Downпроцедура формирования кодовых слов. int n – количество строк в матрице кодовых слов, равное количеству различных символов, int j – номер строки, которая, на данном этапе, будет являться часть нового кодового слова.

Parametersподсчет характеристик сжатия базы данных (средней длины кодового слова, энтропии и коэффициента сжатия). int K – общее количество закодированных символов, float *P – указатель на массив вероятностей.

Основная программа

int main() – в основной программе вызывается только меню.
5. ТЕКСТ ПРОГРАММЫ

/*----------------------------------------------------------------------------*/

/* Course work SAOD ® */

/* Ivanteeva A.V. IVT P-64 */

/* N 11 B C S D E */

/* 2 3 3 2 1 */

/*----------------------------------------------------------------------------*/

#include

#include

#include

#include

#include

#include

#include

/*----------------------------------------------------------------------------*/

/* constantes */

/*----------------------------------------------------------------------------*/

#define MAX 3999

#define Base_name "D:\\base2.dat"

#define default "D:\\base2.dat"

/*----------------------------------------------------------------------------*/

/* variables */

/*----------------------------------------------------------------------------*/

int index[MAX+1];

int VR = 0, HR = 0;

/*----------------------------------------------------------------------------*/

struct Firma{

char Sotrudnik[32];

unsigned short int Nomer;

char Dolgnost[22];

char DataR[8];

};

/*----------------------------------------------------------------------------*/



struct qel{

struct qel *next;

struct Firma *data;

};

/*----------------------------------------------------------------------------*/



struct queueS {

qel *head;

qel *tail;

};

/*----------------------------------------------------------------------------*/



struct queue {

int index;

struct queue *next;

} *headq=NULL,*tailq,*spis;

/*----------------------------------------------------------------------------*/

struct derevo{

int x;

int balance;



struct derevo *left;

struct derevo *right;

} *Dbd, *q;

struct Firma *el[MAX];

/*----------------------------------------------------------------------------*/

FILE *fin;

float P[256],P1[256];

int p_to_s[256];

int s_to_p[256];

int maxpower; long amount; int i,j,k;

/*----------------------------------------------------------------------------*/

float q1;

unsigned char C[256][30],L[256];

unsigned char S[30],l;

/*----------------------------------------------------------------------------*/

/* prototypus&functions */

/*----------------------------------------------------------------------------*/

/* 1 */ void menu();

/* 2 */ void info();

/*---------------------------------------------------------------------*/

/* 3 */ struct qel * LoadMem();

/* 4 */ void ViewBase(struct Firma **el,int iN);

/*---------------------------------------------------------------------*/

/* 5 */ void InvertDate(char aData[],int n);

/* 6 */ char compare(char aData[],char bData[],int n);

/* 7 */ int Devide(qel* &s, qel* &a, qel* &b);

/* 8 */ void Merging(qel* &a, qel* &b, queueS &c, int q, int r);

/* 9 */ qel* MergeSort(qel* s);

/*---------------------------------------------------------------------*/

/* 10 */ int BinSearch(struct Firma **x,int N,int *pointers,char *value);

/* 11 */ void FreeQueue(queue *p);

/* 12 */ void MakeQueue(char *n,struct queue *pq,int *index,int pos);

/* 13 */ void PrintQueue(struct queue *p);

/*---------------------------------------------------------------------*/

/* 14 */ void FreeTree(derevo *p);

/* 15 */ void CreateDBD(int D,struct Firma **base, struct derevo **p,int *index);

/* 16 */ void PrintTree(struct Firma **x,struct derevo *p,int *index);

/* 17 */ struct derevo *SearchInTree(char key[],struct Firma **x,struct derevo *p);

/* 18 */ void PrintSearch(char key[],struct Firma **x,struct derevo *p);

/*---------------------------------------------------------------------*/

/* 19 */ void Probabilities();

/* 20 */ void quick(float *x,int n);

/* 22 */ void quicksort(float *x,int left, int right);

/* 23 */ void huffman(int n);

/* 24 */ int Up(int n,float q1);

/* 25 */ void Down(int n,int j);

/* 26 */ void parametrs(int K,float *P);

/*----------------------------------------------------------------------------*/

/* 1 - 2 */

/*----------------------------------------------------------------------------*/



void menu(){

int i;


char ch;

struct qel *head,*tail,*p;



head=LoadMem();

printf("\n Press any key to back to menu...");

getch();

for (i=0;i<=MAX;i++) index[i]=i;

i=0;

for (p=head;p!=NULL;p=p->next) el[index[i++]]=p->data;



while (1){

system("cls");



info();

ch=getch();

switch (ch){

case '1':

system("cls");

i=0;


qel *q;

for (p=MergeSort(head);p!=NULL;p=p->next){

el[index[i++]]=p->data;

}

printf("\n Base was sorted");



printf("\n Press any key to back to menu...");

getch();


break;

case '2':

system("cls");

printf("\n BASE \n");



ViewBase(el,i);

printf("\n THE END OF BASE \n");

printf("\n Press any key to back to menu...");

getch();


break;

case '3':

system("cls");

printf("\n Enter key of search (format 'yy'): ");

char x[2];

int y;


scanf("%s",x);
следующая страница >>