Представление списка общего вида в виде односвязной реализ на языке Pascal.

Введение

Деятельность любого современного человека, так или иначе, связана с использованием персонального компьютера, основной задачей которого является обработка информации. Известно, что человек привык хранить информацию в систематизированном виде. В первую очередь причиной этого факта является упрощение процедур поиска и добавления новых данных. Для того, чтобы компьютер также мог работать со структурированными данными, ему необходимо заранее определить скелет этой структуры.
Структуры данных являются очень полезными компонентами в работе любых прикладных программ или даже вычислительных комплексов. Это объясняет тот факт, что для того, чтобы быть грамотным программистом, необходимо знать теорию структур данных, а также методы их представления на машинном и логическом уровнях. Кроме того, важно различать допустимые операции над структурами разного вида. Все эти знания необходимы для глубокого изучения и уяснения таких разделов, как автоматизированные системы управления, компиляторы языков программирования, операционные системы, а также системы программного имитационного моделирования, управления базами данных, искусственного интеллекта и т.д. Все эти области знаний сегодня имеют свое развитие в крупнейших мировых компаниях, позволяя программистам реализовывать свои возможности и свой потенциал [7].
Выбор конкретной структуры данных для решения поставленной задачи является одним из наиболее существенных этапов разработки программ. Правильность этого выбора определяет не только эффективность будущей программной разработки, но и трудоемкость процесса ее написания, а также времени исполнения программного кода. Это же справедливо и для алгоритмов обработки данных и их структур. Появление в составе современных языков программирования библиотек и классов структур данных, например, списков, векторов, деревьев различных видов, карт и т.п. не отменяет необходимости знания высококвалифицированными специалистами тонкостей использования этих структур данных и алгоритмов их обработки [14].
Все вышесказанное объясняет актуальность выбранной темы. В современном мире постоянно развивающихся информационных технологий очень важно быть в курсе последних событий. Использование структур данных позволяет облегчить процесс разработки приложений, а также упрощает понимание кода.
Объект исследования – структуры данных, используемые в языках программирования высокого уровня.
Предмет исследования – динамические структуры данных.
Цель работы – рассмотреть односвязный список и реализовать приложение, демонстрирующее работу с ними.
При написании работы в качестве опорных источников были использованы следующие: М.А. Кузниченко – «Динамические структуры данных» и С.А. Орлов – «Теория и практика языков программирования».


1. Основные понятия

В основе всякой программы положен алгоритм. Алгоритмом называется однозначная конечная система правил, которая четко определяет последовательность действий, приводящих к достижению поставленной цели за конечное число итераций [9].
Современные вычислительные устройства и персональные компьютеры способны не только считывать и выполнять различные алгоритмы, но и хранить при этом большие объемы информации, используемые в работе. Чаще всего эта информация является абстрактным представлением каких-либо явлений и предметов реального мира. Она представляет собой определенное множество данных, непосредственно относящихся к поставленной перед компьютером задаче [8].
Независимо от сложности и содержания данных в рамках компьютера они представляются в двоичной системе счисления. Эти данные представляются компьютеру в виде слабо структурированной последовательности битов, имеющей простейшую организацию. Человек не привык описывать объекты и явления реального мира в подобном виде, поэтому были созданы более сложные информационные блоки данных – структуры [5].
В общем случае под структурой данных понимается некоторое множество элементов данных и связей между ними. Понятие структур является очень обширным, охватывающим все существующие подходы к структуризации данных, поэтому в рамках каждой отдельно взятой задачи заостряется внимание на различные аспекты структур.
Кроме общего понятия «структура» также употребляется понятие физической структуры данных, отражающей способ представления данных в памяти компьютера. Другое название физической структуры данных – структура хранения.
Еще один вид структуры - абстрактная или логическая. С этой точки зрения структура рассматривается без учета ее физического представления в компьютере. В общем случае между описанными структурами имеется отличие, степень которого определяется непосредственно структурой данных и особенностями среды. Для преобразований из одних видов структур в другие были созданы специальные процедуры, основная задача которых -обеспечивать доступ к физическим структурам через логические, а также выполнение над ними различных операций.
Классификация структур данных приведена на рисунке 1 [11].


Рисунок 1 – Классификация структур данных

В зависимости от размещения и доступа к элементам выделяют следующие структуры:
внешние – хранятся на внешних запоминающих устройствах;
внутренние – располагаются в оперативной памяти компьютера [4].
Внутренние структуры данных делятся на элементарные и составные

. Элементарные структуры - такие структуры, которые не могут быть поделены на отдельные составляющие, большие, чем биты. С точки зрения физической структуры очень важным в этом определении является тот факт, что применимо к конкретной архитектуре вычислительной машины и конкретной системы программирования, размер элементарного данного определенного типа и его размещение в памяти всегда известны заранее. С логической же точки зрения элементарные данные представляются в виде неделимых единиц [13].
Составными структурами данных называются такие структуры, которые включают в свой состав другие структуры данных – элементарные или составные. Подобные структуры данных формируются программистом согласно поставленному заданию с помощью специальных средств интеграции данных, предоставляемых языками программирования.
Отличительной чертой составных структур данных является упорядоченность элементов. По этому признаку структуры делятся на линейные и нелинейные.
Характерным признаком любой структуры данных является изменчивость – свойство, отражающее переменное количество элементов и связей между составными частями структуры. По этому признаку принято выделять статические и динамические структуры данных [2].
В рамках программирования понятие структур данных неразрывно связано с понятием типа данных, определяющим:
структуру хранения (объем памяти, способы представления данных, методы доступа к ним);
множество допустимых значений элементов;
множество допустимых операций над элементами [6].
В языках программирования высокого уровня существует несколько способов выделения памяти под данные, используемые в программах. Их принято делить на две группы:
статические – память под переменные в таком случае выделяется на этапе компиляции программы и остается занятой на протяжении всего времени ее исполнения;
динамические – память под переменные выделяется во время выполнения программы [10].
Применение динамических данных дает программисту ряд преимуществ:
увеличение объема данных, которые могут быть обработаны в процессе выполнения программы;
возможность освобождения памяти, в которой хранятся уже не нужные данные;
создание и использование структур данных переменного размера.
Таким образом, в процессе исполнения программного кода при помощи вызова специальной процедуры программист может запросить у системы некоторый требуемый объем памяти, а после того, как эта память станет не нужна, возвратить ее обратно. Другими словами, динамическим управлением памятью называется выделение памяти непосредственно во время исполнения программы.
Достоинства использования динамического выделения памяти:
уменьшение объема памяти, требующегося для корректной работы программы;
отсутствие необходимости указания фиксированного размера для объявляемых динамических переменных;
некоторые алгоритмы являются более эффективными в случае их реализации с использованием динамических структур, например, вставка элемента в массив на определенную позицию.
Недостатки:
алгоритмы обработки динамических структур данных более сложны и трудны в процессе отладки в сравнении с аналогичными алгоритмами обработки статических данных;
применение динамических структур требует затрат на память, выделяемую под ссылки;
существуют алгоритмы, реализация которых более эффективна на статичных данных.
Классификация динамических данных приведена на рисунке 2 [18].


Рисунок 2 – Классификация динамических данных


2. Динамические односвязные списки данных

Связанные динамические структуры отличаются отсутствием физической смежности элементов структуры в памяти, а также непостоянством и непредсказуемостью размера (количества элементов) структуры в процессе ее обработки.
В силу того, что элементы динамических структур расположены в несмежных адресах памяти, адреса элементов этих структуры невозможно определить, опираясь на адреса начального или предыдущего элементов. Чтобы установить связь между элементами динамических структур применяются указатели. Именно поэтому такое представление данных называется связным [15].
Элемент связной структуры состоит из двух обязательных полей:
поле данных - хранит информационные данные и может состоять из нескольких полей;
поле связи - один или несколько указателей, которые соединяют текущий элемент структуры с соседними.
С точки зрения конечного пользователя связные структуры данных аналогичны несвязным, так как он видит лишь значения информационных полей.
Достоинства связанных динамических структур:
размер структуры ограничен только размером памяти системы;
в случае изменения логической последовательности элементов структуры нет необходимости перемещать данные в памяти;
большая гибкость структуры.
Недостатки:
дополнительные расходы памяти на поля связи;
менее эффективный с точки зрения времени доступ к элементам.
Второй недостаток является наиболее критичным, именно он ограничивает использование связного представления данных