Методы сортировки. Динамические структуры данных. Анализ текстовых документов.
ВНИМАНИЕ!
Здесь приводится очень сокращённый текст курсовой работы. Если данная информация вас заинтересовала, то
вы можете по указанной ниже ссылке скачать бесплатно полную версию курсовой работы с исходными кодами.
Введение
Данная курсовая работа коротко рассматривает три темы: «Динамические структуры данных»,
«Методы сортировки» и «Анализ текстовых документов». По итогам изучения вышеупомянутых тем
будет разработана программа, на примере которой можно узнать об использовании этих методов
программирования на практике. Программа будет обрабатывать текстовый файл.
Локальные сети большинства предприятий построены таким образом, что доступ в Интернет
с компьютера, подключенного к сети, осуществляется через шлюз. В качестве шлюза обычно
выступает отдельный компьютер, который «подключен» к сети Интернет. Если это достаточно
мощный компьютер, то на него можно установить Windows, и все проблемы решены (если не считать
необходимость тратить деньги на лицензионную копию). Но, как правило, в качестве шлюза
используется достаточно старая и маломощная машина. В этом случае (да и не только в этом),
в качестве операционной системы шлюза лучше использовать Linux, FreeBSD и им подобные ОС.
Но за пользователями нужен контроль. Иначе вместо того, чтобы работать, сотрудники
будут просиживать целыми днями в Интернете. Для контроля за пользователями
существуют специальные программы. Наиболее распространенной для Unix-подобных
систем является программа SQUID. Хорошая программа, вот только информацию о
похождениях пользователей она записывает в лог-файлы, разбирать которые вручную –
занятие малоприятное. Лог-файл может содержать несколько миллионов строк, да и
строки эти непосвященному ничего не скажут. Данная курсовая работа описывает
программу, которая обрабатывает такой лог-файл и выдает отчет в виде таблицы.
Динамические структуры данных
Общие сведения
Использование динамических структур данных предоставляет программисту ряд дополнительных
возможностей. Во-первых, если потребность в каких-то данных отпала до окончания программы,
то занятую ими память можно освободить. Во-вторых, использование динамической памяти позволяет
создавать структуры данных переменного типа.
Второй случай как раз подходит для нашей программы. Delphi 7 предоставляет стандартный
тип данных – динамические массивы. Ими достаточно удобно пользоваться. Например, можно
обращаться к элементу массива по индексу, как и в обычном статическом массиве. Но
этот тип данных имеет один недостаток – количество элементов динамического массива
не может быть более 255. Для многих случаев этого достаточно. Но раз уж мы решили
изучить динамические структуры данных, то мы пойдем другим путем. В нашей программе
будет использоваться так называемый
односвязный список. Его описанием мы и ограничимся.
Но сначала поговорим об указателях и процедурах выделения и освобождения памяти.
Указатели
Практически в любом языке программирования высокого уровня есть ссылочный тип данных.
Переменные этого типа хранят адреса памяти (указатели), т.е. переменная ссылочного
типа указывает на адрес в памяти компьютера, где хранятся какие-либо данные. Указатели
могут быть типизированными и нетипизированными. Типизированный указатель содержит ссылку
на область памяти, где хранятся данные определенного типа (integer, real и т.п.).
Нетипизированные указатели содержат ссылку на область памяти, где могут храниться любые данные.
Сами указатели хранятся в статической области памяти, поэтому их нужно объявлять, как и другие
переменные.
Процедуры для работы с памятью
Одно из основных преимуществ использования указателей – это экономия статической памяти.
Вышеприведенные примеры имеют право на жизнь, но память они не экономят, т.к. работают со
статическими переменными. Здесь мы рассмотрим один из приемов работы с динамическими переменными.
Дальнейшее наше повествование будет только о языке Pascal. В Паскале есть несколько процедур и
функций для работы с памятью. Но мы рассмотрим только две из них, которые наиболее часто
применяются. Вот эти процедуры:
New(P) - Выделение памяти
Dispose(P) – Освобождение памяти
С помощью процедуры New выделяется блок памяти, размер которого зависит от типа указателя Р.
Адрес этого блока памяти записывается в указатель Р.
После того, как работа с памятью завершена, память нужно обязательно освободить.
Для этого используется процедура Dispose. Она освобождает блок памяти, на который
ссылается указатель Р. Процедура Dispose не изменяет значение указателя, и повторная
попытка освободить уже освобожденную память вызовет ошибку. Поэтому рекомендуется
поступать следующим образом:
Dispose(P);
P := NIL;
А теперь небольшой пример:
var s : ^string;
… … …
New(s); //Выделить память
s^ := ‘Это динамическая переменная, память под которую’;
s^ := ‘выделяется только во время выполнения программы’;
Dispose(s); //Освободить память
Теперь мы знаем достаточно, чтобы перейти к рассмотрению динамических структур данных.
Односвязный список
Указатели являются эффективным средством построения динамических структур данных.
Статические структуры данных, такие как массивы, весьма удобны в работе, но имеют
один существенный недостаток – они имеют фиксированное количество элементов.
И если мы не знаем заранее, сколько элементов будет хранить массив – 10 или 1000,
то нам придется объявлять массив на 1000 элементов «на всякий случай». А это
есть очень неэффективное использование памяти. Применение указателей решает эту проблему.
С их помощью можно создавать динамические структуры данных, такие как списки, деревья и графы.
Самым простым из этих структур является односвязный список. Его то мы и рассмотрим.
Список состоит из отдельных элементов. Каждый элемент имеет свой адрес. Каждый элемент –
это запись, которая содержит не менее двух полей. Первое поле содержит данные, а второе –
указатель на следующий элемент списка. Значение указателя последнего элемента должно быть NIL.
Чтобы создать список, сначала нужно объявить элемент. Например, так:
type TList = ^List;
List = record
Num : word; //Здесь будут храниться данные
Next : TList; //А здесь – адрес следующего элемента
end;
Ниже приведен пример программы на Паскале, где иллюстрируется работа со списками.
program Test_3_1;
{$M 1024, 0, 208} (* Стек, Минимальная КУЧА, Максимальная КУЧА *)
uses CRT;
const MaxNum = 25;
type TList = ^List;
List = record
Sim : char;
Next : TList;
end;
var Element : TList; {Адрес текущего элемента списка}
StartPtr : TList; {Адрес первого элемента списка}
i : byte;
{-------------------------------------------------------------------------
Создает новый элемент и записывает в него данные
-------------------------------------------------------------------------}
procedure NewElement(st : char);
var A : TList;
begin
A := Element; {Получить адрес текущего элемента}
New(Element); {Выделить память для нового элемента}
if StartPtr = NIL then StartPtr := Element; {Получить адрес 1-го элемента}
if A <> NIL then A^.Next := Element; {Записать адрес текущего элемента}
{в поле Next предыдущего}
Element^.Sim := st; {Записать данные в элемент}
Element^.Next := NIL {Пока это последний элемент списка}
end;
{-------------------------------------------------------------------------
Очищает выделенную память
-------------------------------------------------------------------------}
procedure ClearMemory(SA : TList);
var A : TList;
begin
while SA <> NIL do
begin
A := SA^.Next; {Получить адрес следующего элемента}
Dispose(SA); {Освободить память от текущего элемента}
SA := A {Установить указатель на следующий элемент}
end
end;
{-------------------------------------------------------------------------
ОСНОВНАЯ ПРОГРАММА
-------------------------------------------------------------------------}
begin
clrscr; writeln;
writeln(' Размер КУЧИ перед выполнением программы : ', MemAvail, ^J,^M);
Element := NIL; {Пока в нашем списке}
StartPtr := NIL; {нет ни одного элемента}
for i := 0 to MaxNum do NewElement(chr(i+65)); {Заполнить список}
Element := StartPtr; {Получить адрес первого элемента списка}
while Element <> NIL do {Вывести список на экран}
begin
write(' ', Element^.Sim); {Вывести текущий элемент списка}
Element := Element^.Next {Установить указатель на следующий элемент}
end;
ClearMemory(StartPtr); {Очистить память}
writeln;
writeln(^J,^M,' Размер КУЧИ после выполнения программы : ', MemAvail);
ReadKey
end.
Если в теле программы закомментировать процедуру ClearMemory, то мы увидим, как важно
ВСЕГДА освобождать память.
Методы сортировки
Общие сведения
На практике довольно часто приходится сортировать данные по различным признакам:
по алфавиту, по типу и т.д. Числовые значения обычно сортируются по убыванию или
по возрастанию. Существует несколько алгоритмов сортировки, но, чтобы наша курсовая
работа не раздулась до неприличных размеров, мы рассмотрим только один.
Это
метод пузырька или
пузырьковый метод - один из самых простых методов
(но и один из самых медленных).
Метод пузырька
Идея: производится последовательное упорядочивание смежных пар элементов массива:
Х1 и Х2, Х2 и Х3, … ,ХN-1 и ХN. В итоге максимальное значение переместится в XN.
Затем ту же процедуру повторяют до ХN-1 и т.д., вплоть до цепочки из двух элементов
Х1 и Х2. Такой алгоритм будет иметь структуру двух вложенных циклов с внутренним
циклом – переменной сокращающейся длины. Аналогично можно добиться сортировки по убыванию.
Здесь мы не будем приводить примеры, дабы не загромождать этот материал лишними исходными кодами.
Пример сортировки по убыванию будет подробно рассмотрен при описании программы.
