- •Структуры данных и алгоритмы их обработки (Учебное пособие)
- •Москва 2007
- •1. Структуры данных и алгоритмы 6
- •1.2. Информация и ее представление
- •1.2.1. Природа информации
- •1.2.2. Хранение информации
- •1.2.3. Классификация структур данных
- •1.3. Операции над структурами данных
- •1.4. Порядок алгоритма
- •1.5. Структурность данных и технологии программирования
- •Контрольные вопросы
- •2. Простые структуры данных
- •2.1. Порядковые типы
- •2.2. Целочисленный тип
- •2.3. Символьный тип
- •2.4. Перечисляемый тип
- •2.5. Интервальный тип
- •2.6. Логический тип
- •2.7. Битовый тип
- •2.8. Вещественный тип
- •2.9. Указательный тип
- •Контрольные вопросы
- •3. Объектные типы данных
- •3.1. Объявление и реализация классов
- •Interface
- •Implementation
- •3.2. Директивы видимости
- •3.3. Свойства классов
- •3.4. Структурированная обработка ошибок
- •3.5. Применение объектов
- •Контрольные вопросы
- •4. Статические структуры данных
- •4.1. Векторы
- •4.2. Массивы
- •4.3. Множества
- •4.4. Записи
- •4.5. Таблицы
- •4.6. Операции над статическими структурами
- •4.6.1. Алгоритмы поиска
- •4.6.2. Алгоритмы сортировки
- •Самые медленные алгоритмы сортировки
- •Быстрые алгоритмы сортировки
- •Самые быстрые алгоритмы сортировки
- •Сортировка слиянием
- •Контрольные вопросы
- •5. Полустатические структуры данных
- •5.1. Стеки
- •5.1.1. Стеки в вычислительных системах
- •5.2. Очереди fifo
- •5.2.1. Очереди с приоритетами
- •5.2.2. Очереди в вычислительных системах
- •5.3. Деки
- •5.3.1. Деки в вычислительных системах
- •5.4. Строки
- •5.4.1. Операции над строками
- •5.4.2. Представление строк в памяти
- •3 A b d 8 p q r s t u V w
- •V w ptr nil
- •1 8 П р е д с т а в
- •2 7 ? Л е н и е ?
- •1 8 С т р о к и з
- •1 8 В е н ь я м и
- •1 8 С у п р а в л
- •1 8 Я е м о й д л
- •1 4 И н о й ? ? ? ? nil
- •6.2. Связные линейные списки
- •6.2.1. Машинное представление связных линейных списков
- •Inf next
- •Inf next
- •Inf nil
- •6.2.2. Реализация операций над связными линейными списками
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •6.2.3. Применение линейных списков
- •6.3. Нелинейные разветвленные списки
- •6.3.1. Основные понятия
- •6.3.2. Представление списковых структур в памяти
- •6.3.3. Операции обработки списков
- •6.4. Язык программирования lisp
- •6.5. Управление динамически выделяемой памятью
- •Контрольные вопросы
- •7. Нелинейные структуры данных
- •7.1. Графы и деревья
- •(B) (a) (b) (a)
- •V0 v1 v2 v5 v6 v3 v4 v7 v8 v9 v10 (v0) (v1) (v7) (v8) (v9) (v10) (v3) (v2) (v4) (v5) (v6)
- •7.3. Бинарные деревья
- •7.3.1. Представление бинарных деревьев
- •7.3.2. Прохождение бинарных деревьев
- •7.4. Алгоритмы на деревьях
- •7.4.1. Сортировка с прохождением бинарного дерева
- •7.4.2. Сортировка методом турнира с выбыванием
- •7.4.3. Применение бинарных деревьев для сжатия информации
- •7.4.4. Представление выражений с помощью деревьев
- •7.5. Представление сильноветвящихся деревьев
- •Контрольные вопросы
- •8. Методы ускорения доступа к данным
- •8.1. Хеширование данных
- •8.1.1. Функции хеширования
- •8.1.2. Оценка качества хеш-функции
- •8.1.3. Методы разрешения коллизий
- •8.1.4. Переполнение таблицы и рехеширование
- •8.2. Организация данных для поиска по вторичным ключам
- •8.2.1. Инвертированные индексы
- •8.2.2. Битовые карты
- •Контрольные вопросы
- •Листинги рабочих примеров
- •1. Создание и управление списковыми объектами
- •Interface
- •Implementation
- •Interface
- •Implementation
- •3. Моделирование работы стека
- •Interface
- •Implementation
- •Interface
- •Implementation
- •4. Создание и редактирование бинарных деревьев
- •5. Создание и редактирование сильноветвящихся деревьев
- •Задания для самостоятельной работы
- •Литература
- •144Кафедра Вычислительной Техники и Программирования Московского Государственного Открытого Университета
1. Создание и управление списковыми объектами
Модуль демонстрирует приемы работы со списковым классом, прототипами функций и динамической памятью.
unit common;
Interface
uses Classes, SysUtils;
type
{ Прототип функции сравнения }
TCompareFunc = function(aData1, aData2: Pointer): Integer;
{ Прототип процедуры сортировки }
TSortProc = procedure(aList: TList;
aFirst, aLast: Integer; aCompare: TCompareFunc);
function CompareLongWord(aData1, aData2: Pointer): Integer;
procedure InitList(Count: LongWord);
procedure DisposeList;
procedure PrintList;
procedure PrintItem(Index: LongWord);
procedure SaveList(FileName: string);
function OpenList(FileName: string; var Size: LongWord): Boolean;
var List: TList;
Implementation
{ Функция сравнения двух целых чисел, заданных своими указателями }
function CompareLongWord(aData1, aData2: Pointer): Integer;
begin
{ Значение первого элемента меньше значения второго }
if LongWord(aData1^) < LongWord(aData2^) then
Result:=-1 else
{ Значения элементов равны }
if LongWord(aData1^) = LongWord(aData2^) then
Result:=0 else
{ Значение первого элемента больше значения второго }
Result:=1;
end;
{ Инициализация массива случайными числами }
procedure InitList(Count: LongWord);
var
pw: ^LongWord;
i: LongWord;
begin
Randomize;
for i:=0 to Count-1 do
begin
New(pw);
pw^:=Random(1000);
List.Add(pw);
end;
end;
{ Вывод содержимого массива }
procedure PrintList;
var i: Integer;
begin
if List.Count > 0 then
for i:=0 to List.Count-1 do
WriteLn(IntToStr(i)+': '+IntToStr(LongWord(List.Items[i]^)));
end;
{ Вывод значения одного элемента массива, заданного своим порядковым номером }
procedure PrintItem(Index: LongWord);
begin
if List.Count > 0 then
WriteLn(IntToStr(Index)+': '+IntToStr(LongWord(List.Items[Index]^)));
end;
{ Освобождение всех элементов массива и самого массива }
procedure DisposeList;
var
pw: ^LongWord;
i: LongWord;
begin
if List.Count > 0 then
try
{ Освобождение памяти, на
которую указывают элементы массива }
for i:=0 to List.Count-1 do
begin
pw:=List.Items[i];
Dispose(pw);
end;
finally
{ Удаление объекта массива }
List.Free;
end;
end;
{ Сохранение содержимого массива в текстовом файле }
procedure SaveList(FileName: string);
var
TF: TextFile;
i: LongWord;
begin
AssignFile(TF, FileName);
try
ReWrite(TF);
for i:=0 to List.Count-1 do
Writeln(TF, LongWord(List.Items[i]^));
finally
CloseFile(TF);
end;
end;
{ Чтение содержимого выборки из текстового файла и инициализация массива }
function OpenList(FileName: string; var Size: LongWord): Boolean;
var
TF: TextFile;
pw: ^LongWord;
begin
Size:=0;
Result:=True;
try
AssignFile(TF, FileName);
try
Reset(TF);
repeat
New(pw);
Readln(TF, pw^);
List.Add(pw);
until Eof(TF);
finally
CloseFile(TF);
Size:=List.Count;
end;
except
Result:=False;
end;
end;
initialization
List:=TList.Create;
finalization
DisposeList;
end.
2. Алгоритмы поиска и сортировки
Модуль содержит реализации различных алгоритмов поиска по критерию отсортированных и неотсортированных объектов в списковом объекте класса TList. Все приведенные алгоритмы были рассмотрены в главе 4 и не требуют дополнительных пояснений.
unit srch;
interface
uses Classes, Common;
{ Алгоритмы поиска }
function LineNonSortedSearch(aList: TList;
aItem: Pointer; aCompare: TCompareFunc): Integer;
function LineSortedSearch(aList: TList;
aItem: Pointer; aCompare: TCompareFunc): Integer;
function BinarySearch(aList: TList;
aItem: Pointer; aCompare: TCompareFunc): Integer;
function BinaryRecurSearch(aList: TList;
aItem: Pointer; L,R: Integer; aCompare: TCompareFunc): Integer;
implementation
{ Линейный поиск в неотсортированном массиве }
function LineNonSortedSearch;
var i: Integer;
begin
Result:=-1;
for i:=0 to aList.Count-1 do
if aCompare(aList.List[i],aItem) = 0 then
begin
Result:=i;
Break;
end;
end;
{ Линейный поиск в отсортированном массивом }
function LineSortedSearch;
var i, CompareResult: Integer;
begin
Result:=-1;
{ Искать первый элемент, больший или равный искомому }
for i:=0 to aList.Count-1 do
begin
CompareResult:=aCompare(aList.List[i], aItem);
if CompareResult >= 0 then
begin
if CompareResult = 0 then
Result:=i else
Result:=-1;
Exit;
end;
end;
end;
{ Двоичный поиск }
function BinarySearch;
var L, R, M, CompareResult: Integer;
begin
{ Значения индексов первого и последнего элементов }
L:=0; R:=aList.Count-1;
while L <= R do
begin
{ Индекс среднего элемента }
M:=(L + R) div 2;
{ Сравнить значение среднего элемента с искомым }
CompareResult:=aCompare(aList.List[M], aItem);
{ Если значение среднего элемента меньше искомого -
переместить левый индекс на позицию до среднего индекса }
if CompareResult < 0 then
L:=M+1 else
{ Если значение среднего элемента больше искомого -
переместить правый индекс на позицию после среднего индекса }
if CompareResult > 0 then
R:=M-1 else
begin
Result:=M;
Exit;
end;
end;
Result:=-1;
end;
{ Рекурсивный алгоритм двоичного поиска }
function BinaryRecurSearch;
var i, CompareResult: Integer;
begin
{ Проверка ширины интервала }
if L > R then
Result:=-1 else
begin
i:=(L + R) div 2;
CompareResult:=aCompare(aList.List[i], aItem);
{ Ключ найден, возврат индекса }
if CompareResult = 0 then
Result:=i else
if CompareResult = -1 then
{ Поиск в правом подинтервале }
Result:=BinaryRecurSearch(aList,aItem,i+1,R,aCompare) else
{ Поиск в левом подинтервале }
Result:=BinaryRecurSearch(aList,aItem,L,i-1,aCompare);
end;
end;
end.
Модуль содержит реализации различных алгоритмов сортировки элементов в списковом объекте класса TList. Все приведенные алгоритмы были рассмотрены в главе 4 и не требуют дополнительных пояснений.
unit sort;