Представление различных структур данных

ВВЕДЕНИЕ

Структуры данных являются неотъемлемой частью любой программы или программного продукта. При разработке программы необходимо определить множество данных, описывающих конкретную задачу и составить алгоритм решения задачи. В зависимости от назначения программы данные могут иметь разный уровень сложности или организованности, начиная с простых типов, представляющих собой числа или символы, и заканчивая файлами и системами файлов достаточно сложной структуры. Изучение структур данных, правильный выбор их в зависимости от выполняемых операций, размера требуемой для структур памяти, частоты использования структур при выполнении программы позволяет повысить эффективность разрабатываемых программ, уменьшить время и стоимость программной разработки. Знание теории структур данных и методов представления данных на логическом и машинном уровнях необходимо для изучения таких разделов вычислительной техники, как опе-рационные системы, базы данных и компиляторы языков программирования.
Целью данной работы является рассмотрение представления различных структур данных.
В соответствии с поставленной целью будут решаться следующие задачи:
- машинное представление различных структур данных;
- математические модели структур данных.
 

Машинное представление полустатических структур данных. [2]
При представлении стека в статической памяти для стека выделяется память, как для вектора. В дескрипторе этого вектора кроме обычных для вектора параметров должен находиться также указатель стека - адрес вершины стека. Указатель стека может указывать либо на первый свободный элемент стека, либо на последний записанный в стек элемент. (Все равно, какой из этих двух вариантов выбрать, важно в последствии строго придерживаться его при обработке стека.)
При занесении элемента в стек элемент записывается на место, определяемое указателем стека, затем указатель модифицируется таким образом, чтобы он указывал на следующий свободный элемент (если указатель указывает на последний записанный элемент, то сначала модифицируется указатель, а затем производится запись элемента). Модификация указателя состоит в прибавлении к нему или в вычитании из него единицы (помните, что наш стек растет в сторону увеличения адресов.
Операция исключения элемента состоит в модификации указателя стека (в направлении, обратном модификации при включении) и выборке значения, на которое указывает указатель стека. После выборки слот, в котором размещался выбранный элемент, считается свободным.
Операция очистки стека сводится к записи в указатель стека начального значения - адреса начала выделенной области памяти.
Определение размера стека сводится к вычислению разности указателей: указателя стека и адреса начала области.
Программный модуль, представленный ниже, иллюстрирует операции над стеком, расширяющимся в сторону уменьшения адресов. Указатель стека всегда указывает на первый свободный элемент.
const SIZE = ...;
type data = ...;
{ Стек }
unit Stack;
Interface
const SIZE=...; { предельный размер стека }
type data = ...; { эл-ты могут иметь любой тип }
Procedure StackInit;
Procedure StackClr;
Function StackPush(a : data) : boolean;
Function StackPop(Var a : data) : boolean;
Function...

ЗАКЛЮЧЕНИЕ

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