2. Логическая структура данных
Многосвязный нелинейный список может быть организован как иерархическая списковая структура (hierarchical structure), логическую организацию которой проиллюстрируем следующим примером.
Пусть на факультете высшего учебного заведения имеется 5 групп. Кроме того, каждая группа состоит из множества студентов, причем группы различаются количеством студентов. Для представления информации о группах и студентах можно предложить следующую информационную модель:
формируется список (назовем его Main-списком), элементы которого содержат информацию о группах: номер группы, число студентов, староста и т. д.,
каждый элемент Main-списка «дает начало» дополнительному списку (Sub-списку), состоящему из элементов, каждый из которых содержит информацию об отдельном студенте группы.
Очевидно, эта модель предполагает существование такого количества Sub-списков, которое равно числу групп. Каждый Sub-список как бы подчиняется Main-списку.
Для представления описанной модели в памяти можно использовать следующую структуру. Пусть указатель Faculty адресует начало главного цепного списка, каждый элемент которого, кроме информации о группах факультета, содержит два указателя Main и Sub. Указатель Main связывает элементы главного списка, а указатель Sub каждого элемента главного списка ссылается на начало другого списка, который содержит информацию о студентах соответствующей группы. Такая структура показана на рисунке 2.1.
Рисунок 2.1 - Логическая структура линейного односвязного списка
Как видно из рисунка 2.1, каждый список, адресуемый указателем Sub как бы «подчиняется» элементу главного списка; такой список, «ответвляющийся» от главного списка, называется подсписком (sublist). Очевидно, в каждом подсписке может располагаться произвольное число элементов, в общем случае не равное для всех подсписков.
Список, организованный указателем-связкой Main, образует верхний уровень иерархии, а списки, на начало которых указывают указатели Sub нижний уровень. Такой список называется двухуровневым связным списком.
3. Статические данные и структуры.
Таблица 3.1 - Глобальные переменные
Имя переменной |
Адрес в памяти |
Тип переменной |
Объем Памяти в байтах |
Назначение переменной |
Remuneration_Amount |
$BC2130 |
Byte |
1 |
Сумма вознаграждения |
zXD. Number |
$BC1F94 |
Byte |
1 |
Поля записи Хоздого-воров |
zXD.Date_of_conclusions |
$BC1F95 |
TString |
30 |
|
zXD. Date_of_terminations |
$BC1FB4 |
TString |
30 |
|
zXD. Subject_of_agreement |
$BC1FD3 |
TString |
30 |
|
zXD. Name_of_organization |
$BC1FF2 |
TString |
30 |
|
zXD. Sing_of_termination |
$BC2011 |
Byte |
1 |
|
zXD. Cost |
$BC2012 |
Word |
2 |
|
zWTK. Surname |
$BC2014 |
TString |
30 |
Поля записи Исполни-телей |
zWTK. Name |
$BC2033 |
TString |
30 |
|
zWTK. Patronymic_name |
$BC2052 |
TString |
30 |
|
zWTK. Of_birth |
$BC2072 |
Word |
2 |
|
zWTK. Code |
$BC2074 |
TString |
30 |
|
zWTK. Sign |
$BC2093 |
Byte |
2 |
|
zWTK. Remuneration_Amount |
$BC2094 |
Word |
2 |
|
zWTK. Home_Address |
$BC2096 |
TString |
30 |
|
zWTK. Branch_Number |
$BC20B5 |
String[4] |
4 |
|
zWTK. Accouting_count |
$BC20BA |
String[7] |
7 |
|
zBANK. Branch_Name |
$BC20C2 |
String[4] |
4 |
Поля записи Отделе-ния сбер-банка |
zBANK. City |
$BC20C7 |
TString |
30 |
|
zBANK. Address |
$BC20E6 |
TString |
30 |
|
zBANK. Name_of_branch |
$BC2105 |
TString |
30 |
|
zBANK. Bank_Code |
$BC2124 |
TString[3] |
3 |
Таблица 3.2 – Текущие переменные
Имя переменной |
Адрес в памяти |
Тип переменной |
Объем Памяти в байтах |
Назначение переменной |
first1 |
$BC2128 |
TFirstLevel |
4 |
Переменные указатели на первый уровень иерархической структуры |
cur1 |
$BC2512 |
TFirstLevel |
4 |
Переменные указатели на первый уровень иерархической структуры |
first2 |
$BC2125 |
TSecondLeval |
4 |
Переменные указатели на второй уровень иерархической структуры |
cur2 |
$BC2128 |
TSecondLeval |
4 |
Переменные указатели на второй уровень иерархической структуры |
cur1^.Remuneration_Amount |
$BC23A4 |
Word |
30 |
Информацион-ные поля для первого уровня иерархической структуры |
Cur^. Patronymic_name
|
|
TString |
30 |
|
cur1^.L |
$BC23C4 |
T TFirstLevel |
4 |
|
cur2.Branch_Number |
$BC2424 |
String[4] |
4 |
Указатель первый уровень иерархической структуры. |
cur2^.Surname |
$BC24B4 |
TString |
30 |
Указатели второй уровень иерархической структуры. |
cur2^.Name |
$BC2FF2 |
TString |
30 |
|
cur2^.Patronymic_Name |
$BC24A4 |
TString |
30 |
|
cur2^.Code |
$BC2421 |
TString |
30 |
|
cur2^.City |
$BA2424 |
TString |
30 |
|
cur1^.S |
$BC2454 |
T SecondLevel |
30 |
|
cur2^.Next |
$BA2424 |
TSecondLeval |
4 |
Указатель на следующее поле |
Таблица 3.3 - Локальные переменные
Имя переменной |
Адрес в памяти |
Тип переменной |
Объем Памяти в байтах |
Назначение переменной |
S |
$44579C |
TString |
30 |
Всп.переменная |
spt |
$44579D |
TSecondLeval |
1 |
Вспом. Указат. |
Count |
$68FBE4 |
Byte |
1 |
Счётчик |
sXD |
$68FBC0 |
TString |
30 |
Имя ф. ХD |
sWTK |
$68FBA1 |
TString |
30 |
Имя ф. WTK |
sBANK |
$68FB82 |
Byte |
30 |
Имя ф. BANK |
Len |
$68FBE0 |
Byte |
1 |
Длина строки |
CheckLos |
$68FBDF |
Boolean |
1 |
Проверка |
Cur |
$68F8A8 |
TFirstLeval |
4 |
Вспом. Указат. |
Remuneration_Amount |
$68FAD5 |
Word |
2 |
Сумма вознаграждения |
Surname |
$68FAD6 |
TString |
30 |
Фамилия |
Name |
$68FAD7 |
TString |
30 |
Имя |
Patronymic_Name |
$68FAD8 |
TString |
30 |
Отчество |
Code |
$68FAD9 |
TString |
30 |
Код ХД |
S |
$68FADA |
Word |
2 |
Всп.переменная |
City |
$68FAB58 |
TString |
30 |
Город в котором находится отделнение |
4. Алгоритм обработки структуры.
В этой курсовой работе рассматривается сортировка методом пузырька или пузырьковой сортировкой.
Проход метода начинается с конца сортируемого массива. Ключ последнего элемента a[HighIndex] сравнивается с ключом предпоследнего элемента a[HighIndex-1]. Если
a[HighIndex].Key < a[HighIndex-1].Key,
то сравниваемые элементы меняются местами друг с другом. Затем предпоследний элемент сравнивается с предыдущим, и если нужно, то происходит обмен и т. д. Следующий проход выполняется аналогичным образом. Сортировка завершается тогда, когда во время очередного прохода не произошло ни одного обмена.
Алгоритм пузырьковой сортировки иллюстрируется результатами выполнения проходов на тех же, что и ранее, ключах:
Рисунок 4.1 – Пример пузырьковой сортировки
По-шагово рассмотрим сортировка по 1-возрастанию