Некоторые примеры представления данных
Рассмотрим основные способы представления данных. Прежде всего отметим, что структурированные данные относятся прежде всего к таким языкам как Паскаль, Модула-2, Си. Именно необходимость описания структур данных была одной из причин создания языка Паскаль. Структурированная переменная в нем представлялась как единая переменная, состоящая из многих элементов или компонент. Усовершенствования языка Паскаль, прежде всего в описании типов данных, привели к созданию нового языка Модулы-2, в последствии этот опыт распространился на язык Си и многие другие. Отметим еще и то, что такие языки как Бейсик, также были усовершенствованы в части описания данных. Так была создана новая версия языка именуемая QUIK BASIC, в которой были предусмотрен пользовательский тип данных (или записи). Дальнейшее усовершенствование языка привело к созданию более мощной версии VISUAL BASIC, где вопросы описания типов данных были еще более усовершенствованы по сравнению с версией QUIK BASIC.
|
Рис. 2.5. Динамические структуры данных. Они могут сокращаться и даже перестраиваться под управлением алгоритмической части программы. Такие структуры составляются из узлов (как правило, записей), содержащих указатели на другие узлы (закрашены). Указатель который не на что не указывает, снабжается значением nil. Простейшей структурой является связанный список, каждый узел которого содержит один указатель на следующий узел. Любой список можно преобразовать в кольцо, сделав так, чтобы последний элемент указывал на первый. В бинарном дереве каждый узел имеет два указателя, которые дают адреса левого и правого подузлов.
Вследствие того, что в качестве основного изучаемого алгоритмического языка был изучен язык Бейсик, а в качестве дополнительного Паскаль, приводимые примеры будут на этих языках. Однако подробнее мы остановимся на Бейсике.
На рис.2.5 приведены примеры организации данных типа список, кольцо, и дерево.
В языке QUIK BASIC организация данных, такая как запись может быть представлена из набора простых данных (числовых и символьных).
Например, введем табельный номер работника, его фамилию и тарифную ставку. Затем присвоим некоторой переменной пользовательский тип данных с помощью оператора DIM и введем значения каждого элемента записи.
REM Определим пользовательский тип данных RECORD
REM с помощью оператора TYPE
TYPE RECORD
TabNamer AS INTEGER
Family AS STRING*15
Stavka AS DOUBLE
END TYPE
REM Присвоим переменной RABOTNIC пользовательский тип данных
DIM RABOTNIC AS RECORD
REM Последовательно вводим значение каждого элемента записи
INPUT "Введите табельный номер"; RABOTNIC.TabNamer
INPUT "Введите фамилию"; RABOTNIC.Family
INPUT "Введите тарифную ставку"; RABOTNIC.Stavka
Пользовательский данных занимает в памяти столько байт, сколько занимают в сумме каждый из составляющий его элементов. Для нашего примера запись RABOTNIC включает целое слово (2 байта), строку фиксированной длины (15 байт) и число удвоенной точности (8 байт). Следовательно, она имеет 25 байт.
В языке Бейсик используются массивы данных и пользовательский тип данных может быть использован для элементов массива. Например, используем для предыдущего примера не переменную RABOTNIC, а массив RABOTNIC из 10 элементов.
REM Определим пользовательский тип данных RECORD
REM с помощью оператора TYPE
TYPE RECORD
TabNamer AS INTEGER
Family AS STRING*15
Stavka AS DOUBLE
END TYPE
REM Присвоим массиву RABOTNIC пользовательский тип данных
DIM RABOTNIC(10) AS RECORD
REM Последовательно вводим значение каждого элемента записи
FOR I=1 TO 10
INPUT "Введите табельный номер"; RABOTNIC(I).TabNamer
INPUT "Введите фамилию"; RABOTNIC(I).Family
INPUT "Введите тарифную ставку"; RABOTNIC(I).Stavka
NEXT I
Как мы видим, эти две программы отличаются в части описания элементов массива, как пользовательский тип и в части ввода данных.
Попробуем теперь образовать такие структуры данных как кольцо и список. В качестве примера введем переменную n состоящую из 7 дней недели. Для того, чтобы показать как реализуется кольцо пройдем цикл из 14 элементов.
CLS
TYPE treenode
d AS STRING * 15
y AS INTEGER
END TYPE
DIM n(7) AS treenode
n(1).d = "понедельник"
n(1).y = 2
n(2).d = "вторник"
n(2).y = 3
n(3).d = "среда"
n(3).y = 4
n(4).d = "четверг"
n(4).y = 5
n(5).d = "пятница"
n(5).y = 6
n(6).d = "суббота"
n(6).y = 7
n(7).d = "воскресенье"
n(7).y = 1
i = 1
FOR f = 1 TO 14
PRINT n(i).d
i = n(i).y
NEXT f
Как мы видим, каждая переменная состоит из двух частей: первая часть - несет информацию о дне недели, а вторая указатель на следующий день. Последний день недели "воскресенью" имеет указатель 1, что указывает на первый день недели. Таким образом, мы образовали такой тип данных как кольцо. Напечатав, последовательно четырнадцать элементов этого типа данных в соответствии с их указателями мы увидим как "работает" такой тип данных. Такое представление является во много искусственным, и в таких языках как Паскаль, Модула-2 есть специальные операторы предусматривающие такие типы данных, как стек, очередь, кольцо и т.п. Но данный пример позволяет понять механизм работы таких типов данных.
Еще одним примером проиллюстрируем "работу" такого типа данных, как связанный список. Для него характерно не только информация о элементах, но и информация о связях между ними. Очевидно, что описание таких элементов с помощью простых массивов очень трудоемка, так как при изменении порядка или исключении какого-либо элемента массива перестановка элементов требует значительное время. Поэтому применение связанного списка, в котором храниться не только информация о элементах массива но и о связях между ними значительно сократит время и трудоемкость на такие изменения списка как удаление элементов, или внесение новых элементов.
Рассмотрим например массив размерности N, в котором содержаться некие лексико-графические имена студентов посещающих данные лекции. Спустя некоторое время некий студент перестает посещать лекции, а другой студент начинает их посещать вновь. Задача состоит в том чтобы получить новый список слушателей, например в алфавитном порядке.
Эта задача может быть представлена на рис. 2.6, где на рис. 2.6а представлен список студентов посещающий курс лекций. Из него удаляется студент Иванов и Егоров, а добавляется студент Семенов и мы хотим получить список, представленный на рис.2.6б.
|
| Афонин | |
| Васин | |
| Ерофеев | |
| Михайлов | |
| Петров | |
| добавить | Семенов |
| Харитонов | |
return false">ссылка скрыта
а б
Рис. 2.6. Список студентов посещающих курс лекций: а - вначале, б - в конце
На рис.2.7 массив студентов преобразован в записи, где в столбце 1 также содержаться фамилии студентов, (но как следует из 7б теперь уже не требуется чтобы эти фамилии были упорядочены по алфавиту) а в столбце 2 содержится информация связей или указателей, значениями которых являются номера строк массива (номера строк указаны перед фамилиями студентов), содержащих фамилию следующего студента (в алфавитном порядке) в текущем списке. Звездочкой отмечены указатели значения которых изменились.
|
| Афонин | |||
| Васин | 4* | ||
| удалить | Егоров | ||
| Ерофеев | 6* | ||
| удалить | Иванов | ||
| Михайлов | |||
| Петров | 9* | ||
| Харитонов | |||
| добавить | Семенов |
а б
Рис.2.7 Переорганизация связанного списка
Как видно из рисунка уже необходимости располагать сами фамилии по алфавиту достаточно расположить указатели в нужном порядке. Удаление фамилии из списка и включение новых студентов достигается за счет изменения указателей, а сами данные просто добавляются в конец списка.
Ниже представлена программа написанная на языке Бейсик в котором реализован список из семи студентов А, В, Е, И, М, П, С. Указатели ссылаются на следующего студента в алфавитном порядке. Список студентов содержится в массиве N. Фамилия указывается в первой половине записи N(I).D, а указатель во второй половине N(I).Y. Далее в программе удаляется фамилия студента из списка оператором и указатели модифицируются соответствующим образом. Подпрограмма NSPS выводит список на экран в алфавитном порядке.
CLS
DIM ff AS STRING * 15
TYPE treenode
d AS STRING * 15
y AS INTEGER
END TYPE
DIM n(7) AS treenode
n(1).d = "А"
n(1).y = 2
n(2).d = "В"
n(2).y = 3
n(3).d = "Е"
n(3).y = 4
n(4).d = "И"
n(4).y = 5
n(5).d = "М"
n(5).y = 6
n(6).d = "П"
n(6).y = 7
n(7).d = "С"
n(7).y = 0
start = 1
GOSUB NSPS
INPUT "введите наименование исключения ", ff
FOR i = 1 TO 7
IF ff$ = n(i).d THEN
IF n(i).y > 2 OR n(i).y = 0 THEN
n(i - 1).y = n(i).y
n(i).y = -1
ELSE
start = n(i).y
n(i).y = -1
END IF
END IF
NEXT i
GOSUB NSPS
END
NSPS:
i = start
FOR f = 1 TO 14
PRINT n(i).d
i = n(i).y
NEXT f
RETURN