Линейные структуры данных
Анализ статистических структур данных (массивы, записи, множества). Цели описания типа данных и определения некоторых переменных, относящихся к статическим типам. Динамическая структура данных. Понятие однонаправленных и двунаправленных линейных списков.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 06.12.2016 |
| Размер файла | 457,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
15
Размещено на http://www.allbest.ru/
Лекция. Тема: "Линейные структуры данных"
План лекции
- 1. Статистические структуры данных
- 1.1 Массив
- 1.2 Строка
- 1.3 Запись
- 1.4 Множество
- 1.5 Таблица
- 2. Линейные списки
- 2.1 Линейный однонаправленный список
- 2.2 Линейный двунаправленный список
- 3. Стек. Очередь. Дек
- 3.1 Стек
- 3.2 Очередь
- 3.2.1 Дек
1. Статистические структуры данных
Рассмотрим статические структуры данных: массивы, записи, множества. Цель описания типа данных и определения некоторых переменных, относящихся к статическим типам, состоит в том, чтобы зафиксировать диапазон значений, присваиваемых этим переменным, и соответственно размер выделяемой для них памяти. Поэтому такие переменные и называются статическими.
1.1 Массив
Массив - это поименованная совокупность однотипных элементов, упорядоченных по индексам, определяющих положение элемента в массиве.
Следующее объявление задает имя для массива, тип для индекса и тип элементов массива:
имя: array [ТипИндекса] of ТипЭлемента;
Тип индекса, в общем случае, может быть любым порядковым, но некоторые языки программирования поддерживают в качестве индексов массивов только последовательности целых чисел.
Количество используемых индексов определяет размерность массива. Массив может быть одномерным (вектор), двумерным (матрица), трехмерным (куб) и т.д.:
var
Vector: array [1.100] of integer;
Matrix: array [1.100, 1.100] of integer;
Cube: array [1.100, 1.100, 1.100] of integer;
В Паскале определены такие операции над массивами в целом, как сравнение на равенство и неравенство массивов, а также операция присвоения для массивов с одинаковым типом индексов и одинаковым типом элементов. Доступ к массивам в этих операциях осуществляется через имя массива без указания индексов. В некоторых языках программирования определен более мощный перечень операции, где в качестве операндов выступают целые массивы, это так называемые векторные вычисления.
Можно также выполнять операции над отдельными элементами массива. Перечень таких операций определяется типом элементов. Доступ к отдельным элементам массива осуществляется через имя массива и индекс (индексы) элемента:
Cube [0,0,10]: = 25;
Matrix [10,30]: = Cube [0,0,10] + 1;
В памяти ЭВМ элементы массива обычно располагаются непрерывно, в соседних ячейках. Размер памяти, занимаемой массивом, есть суммарный размер элементов массива.
1.2 Строка
Строка - это последовательность символов (элементов символьного типа).
В Паскале количество символов в строке (длина строки) может динамически меняться от 0 до 255.
Рассмотрим пример описания строк:
var
TTxt: string;
TWrd: string [10];
Здесь описаны строка TTxt, максимальная длина которой 255 символов (по умолчанию) и строка TWrd, максимальная длина которой ограничена 10 символами. Каждый символ строки имеет свой индекс, принимающий значение от 1 до заданной длины строки. Следует обратить внимание, что существует элемент строки с индексом 0, который не доступен с использованием индекса, и содержит текущее количество символов в строке. Доступ к этому специфическому элементу можно получить только с помощью специальных функций языка.
Благодаря индексам, строки очень похожи на одномерные массивы символов, и доступ к отдельным элементам строки можно получать с использованием этих индексов, выполняя операции, определенные для символьного типа данных. Так же как и для массивов, определена операция присвоения строк в целом.
Однако есть ряд отличий. Операций сравнения строк больше, чем аналогичных операций для массивов: <, >, ?, ?, =, <>. Существует операция сцепления (конкатенации) строк "+".
В памяти ЭВМ символы строки располагаются непрерывно, в соседних ячейках. Размер памяти, занимаемой строкой, есть суммарный размер элементов массива (включая элемент, содержащий длину строки).
1.3 Запись
Запись - это агрегат, составляющие которого (поля) имеют имя и могут быть различного типа.
Рассмотрим пример простейшей записи:
type
TPerson = record
Name: string;
Address: string;
Index: longint;
end;
var
Person1: TPerson;
Запись описанного типа объединяет три поля. Первые два из них символьного типа, а третье - целочисленного.
В Паскале определена операция присваивания для записей в целом (записи должны быть одного типа). Доступ к записи осуществляется через ее имя.
Можно также выполнять операции над отдельным полем записи. Перечень таких операций определяется типом поля. Доступ к полям отдельной записи осуществляется через имя записи и имя поля:
Person1. Index: = 190000;
Person1. Name: = `Иванов';
Person1. Adress: = `Санкт-Петербург, ул.Б. Морская, д.67';
В памяти ЭВМ поля записи обычно располагаются непрерывно, в соседних ячейках. Размер памяти, занимаемой записью, есть суммарный размер полей, составляющих запись.
1.4 Множество
Наряду с массивами и записями существует еще один структурированный тип - множество. Этот тип используется не так часто, хотя его применение в некоторых случаях является вполне оправданным.
Множество - совокупность каких-либо однородных элементов, объединенных общим признаком и представляемых как единое целое.
линейная структура список статистическая
Тип множество соответствует математическому понятию множества в смысле операций, которые допускаются над структурами такого типа.
Множество допускает операции объединения множеств "+", пересечения множеств "*", разности множеств "-" и проверки элемента на принадлежность к множеству "in". Множества, так же как и массивы, объединяют однотипные элементы. Поэтому в описании множества обязательно должен быть указан тип его элементов:
var
RGB, YIQ, CMY: set of char;
Здесь приведено описание трех множеств, элементами которых являются символы. Кроме того, определены операции сравнения множеств: ?, ?, =, <>. В отличие от массивов и записей здесь отсутствует возможность обращения к отдельным элементам. Операции выполняются по отношению ко всей совокупности элементов множества:
CMY: = [`M', 'C', 'Y'];
RGB: = [`R', 'G', 'B'];
YIQ: = [`Y', 'Q', 'I'];
Writeln (`Пересечение цветовых систем RGB и CMY ', RGB*CMY);
Writeln (`Пересечение цветовых систем YIQ и CMY ', YIQ*CMY);
В Паскале в качестве типов элементов множества могут использоваться типы, максимальное количество значений которых не превышает 256. В памяти ЭВМ элементы множества обычно располагаются непрерывно, в соседних ячейках.
1.5 Таблица
Таблица представляет собой одномерный массив (вектор), элементами которого являются записи. Отдельная запись массива называется строкой таблицы. Чаще всего
используется простая запись, т.е. поля - элементарные данные. Совокупность одноименных полей всех строк называется столбцом, а конкретное поле отдельной строки - ячейкой:
type
TPerson = record
Name: string;
Address: string;
Index: longint;
end;
TTable = array [1.1000] of TPerson;
var
PersonList: TTable;
Характерной особенностью таблиц является то, что доступ к элементам таблицы производится не по индексу, а по ключу, т.е. по значению одного из полей записи.
Ключ таблицы (основной, первичный) - поле, значение которого может быть использовано для однозначной идентификации каждой записи таблицы. Ключ таблицы может быть составным - образовываться не одним, а несколькими полями данной таблицы.
Вторичный ключ - поле таблицы с несколькими ключами, не обеспечивающий (в отличие от первичного ключа) однозначной идентификации записей таблицы. В этот ключ могут входить все поля таблицы за исключением полей, составляющих первичный ключ.
Если последовательность записей упорядочена относительно какого-либо столбца (поля), то такая таблица называется упорядоченной, иначе - таблица неупорядоченная.
Основной операцией при работе с таблицами является операция доступа к записи по ключу. Она реализуется процедурой поиска. Получив доступ к конкретной записи (строке таблицы), с ней можно работать как с записью в целом, так и с отдельными полями (ячейками). Перечень операций над отдельной ячейкой определяется типом ячейки:
PersonList [1]. Index: = 190000;
PersonList [1]. Name: = `Иванов';
PersonList [1]. Adress: = `Санкт-Петербург, ул.Б. Морская, д.67';
В памяти ЭВМ ячейки таблицы обычно располагаются построчно, непрерывно, в соседних ячейках. Размер памяти, занимаемой таблицей, есть суммарный размер ячеек.
2. Линейные списки
Список - это структура данных, представляющая собой логически связанную последовательность элементов списка.
Иногда бывают ситуации, когда невозможно на этапе разработки алгоритма определить диапазон значений переменной. В этом случае применяют динамические структуры данных.
Динамическая структура данных - это структура данных, определяющие характеристики которой могут изменяться на протяжении ее существования.
Обеспечиваемая такими структурами способность к адаптации часто достигается меньшей эффективностью доступа к их элементам.
Динамические структуры данных отличаются от статических двумя основными свойствами:
1) в них нельзя обеспечить хранение в заголовке всей информации о структуре, поскольку каждый элемент должен содержать информацию, логически связывающую его с другими элементами структуры;
2) для них зачастую не удобно использовать единый массив смежных элементов памяти, поэтому необходимо предусматривать ту или иную схему динамического управления памятью.
Для обращения к динамическим данным применяют указатели.
Созданием динамических данных должна заниматься сама программа во время своего исполнения. В языке программирования Паскаль для этого существует специальная процедура:
New (Current);
После выполнения данной процедуры в оперативной памяти ЭВМ создается динамическая переменная, тип которой определяется типом указателя Current.
После использования динамического данного и при отсутствии необходимости его дальнейшего использования необходимо освободить оперативную память ЭВМ от этого данного с помощью соответствующей процедуры:
Dispose (Current);
Наиболее простой способ организовать структуру данных, состоящее из некоторого множества элементов - это организовать линейный список. При такой организации элементы некоторого типа образуют цепочку. Для связывания элементов в списке используют систему указателей, и в зависимости от их количества в элементах различают однонаправленные и двунаправленные линейные списки.
2.1 Линейный однонаправленный список
В этом списке любой элемент имеет один указатель, который указывает на следующий элемент в списке или является пустым указателем у последнего элемента (рис.1).
Рисунок 1 - Линейный однонаправленный список
Основные операции, осуществляемые с линейным однонаправленным списком:
вставка элемента;
просмотр;
поиск;
удаление элемента.
Следует обратить особое внимание на то, что при выполнении любых операций с линейным однонаправленным списком необходимо обеспечивать позиционирование какого-либо указателя на первый элемент. В противном случае часть или весь список будет недоступен.
Линейный однонаправленный список имеет только один указатель в элементах. Это позволяет минимизировать расход памяти на организацию такого списка. Одновременно, это позволяет осуществлять переходы между элементами только в одном направлении, что зачастую увеличивает время, затрачиваемое на обработку списка. Например, для перехода к предыдущему элементу необходимо осуществить просмотр списка с начала до элемента, указатель которого установлен на текущий элемент.
Для ускорения подобных операций целесообразно применять переходы между элементами списка в обоих направлениях. Это реализуется с помощью линейных двунаправленных списков.
2.2 Линейный двунаправленный список
В этом линейном списке любой элемент имеет два указателя, один из которых указывает на следующий элемент в списке или является пустым указателем у последнего элемента, а второй - на предыдущий элемент в списке или является пустым указателем у первого элемента (рис.2).
Рисунок 2 - Линейный двунаправленный список
Основные операции, осуществляемые с линейным двунаправленным списком те же, что и с однонаправленным линейным списком:
вставка элемента;
просмотр;
поиск;
удаление элемента.
Следует обратить внимание на то, что в отличие от однонаправленного списка здесь нет необходимости обеспечивать позиционирование какого-либо указателя именно на первый элемент списка, так как благодаря двум указателям в элементах можно получить доступ к любому элементу списка из любого другого элемента, осуществляя переходы в прямом или обратном направлении. Однако часто бывает полезно иметь указатель на заголовок списка.
3. Стек. Очередь. Дек
3.1 Стек
Стек - это структура данных, в которой новый элемент всегда записывается в ее начало (вершину) и очередной читаемый элемент также всегда выбирается из ее начала. Здесь используется принцип "последним пришел - первым вышел" (LIFO: Last Input - First Output).
Стек можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру - в виде линейного списка (рис.3).
При реализации стека в виде статического массива необходимо резервировать массив, длина которого равна максимально возможной глубине стека, что приводит к неэффективному использованию памяти. Однако работать с такой реализацией проще и быстрее. При такой реализации дно стека будет располагаться в первом элементе массива, а рост стека будет осуществляться в сторону увеличения индексов. Одновременно необходимо отдельно хранить значение индекса элемента массива, являющегося вершиной стека. Можно обойтись без отдельного хранения индекса, если в качестве вершины стека всегда использовать первый элемент массива, но в этом случае, при записи или чтении из стека, необходимо будет осуществлять сдвиг всех остальных элементов, что приводит к дополнительным затратам вычислительных ресурсов.
Рисунок 3 - Стек и его организация
Стек как динамическую структуру данных легко организовать на основе линейного списка. Поскольку работа всегда идет с заголовком стека, т.е. не требуется осуществлять просмотр элементов, удаление и вставку элементов в середину или конец списка, то достаточно использовать экономичный по памяти линейный однонаправленный список.
Для такого списка достаточно хранить указатель вершины стека, который указывает на первый элемент списка. Если стек пуст, то списка не существует и указатель принимает значение nil.
Поскольку стек, по своей сути, является структурой с изменяемым количеством элементов, то основное внимание уделим динамической реализации стека. Как уже говорилось выше, для такой реализации целесообразно использовать линейный однонаправленный список.
Описание элементов стека аналогично описанию элементов линейного однонаправленного списка, где DataType является типом элементов стека. Поэтому здесь приводить его не будем.
Основные операции, производимые со стеком:
записать (положить в стек);
прочитать (снять со стека);
очистить стек;
проверка пустоты стека.
3.2 Очередь
Очередь - это структура данных, представляющая собой последовательность элементов, образованная в порядке их поступления. Каждый новый элемент размещается в конце очереди; элемент, стоящий в начале очереди, выбирается из нее первым. Здесь используется принцип "первым пришел - первым вышел" (FIFO: First Input - First Output).
Очередь можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру - в виде линейного списка (рис.4).
При реализации очереди в виде статического массива необходимо резервировать массив, длина которого равна максимально возможной длине очереди, что приводит к неэффективному использованию памяти.
При такой реализации начало очереди будет располагаться в первом элементе массива, а рост очереди будет осуществляться в сторону увеличения индексов. Однако, поскольку добавление элементов происходит в один конец, а выборка - из другого конца очереди, то с течением времени будет происходить миграция элементов очереди из начала массива в сторону его конца. Это может привести к быстрому исчерпанию массива и невозможности добавлении новых элементов в очередь при наличии свободных мест в начале массива. Предотвратить это можно двумя способами:
после извлечения очередного элемента из начала очереди осуществлять сдвиг всей очереди на один элемент к началу массива. При этом необходимо отдельно хранить значение индекса элемента массива, являющегося концом очереди (начало очереди всегда в первом элементе массива);
представить массив в виде циклической структуры, где первый элемент массива следует за последним. Элементы очереди располагаются в "круге" элементов массива в последовательных позициях, конец очереди находится по часовой стрелке на некотором расстоянии от начала. При этом необходимо отдельно хранить значение индекса элемента массива, являющегося началом очереди, и значение индекса элемента массива, являющегося концом очереди. Когда происходит добавление в конец или извлечение из начала очереди, осуществляется смещение значений этих двух индексов по часовой стрелке.
С точки зрения экономии вычислительных ресурсов более предпочтителен второй способ. Однако здесь усложняется проверка на пустоту очереди и контроль переполнения очереди - индекс конца очереди не должен "набегать" на индекс начала.
Очередь как динамическую структуру данных легко организовать на основе линейного списка. Поскольку работа идет с обоими концами очереди, то предпочтительно будет использовать линейный двунаправленный список. Хотя, как уже говорилось при описании этого списка, для работы с ним достаточно иметь один указатель на любой элемент списка, здесь целесообразно хранить два указателя - один на начало списка (откуда извлекаем элементы) и один на конец списка (куда добавляем элементы). Если очередь пуста, то списка не существует и указатели принимают значение nil.
Рисунок 4 - Очередь и его организация
3.2.1 Дек
Дек - это структура данных, представляющая собой последовательность элементов, в которой можно добавлять и удалять в произвольном порядке элементы с двух сторон. Первый и последний элементы дека соответствуют входу и выходу дека.
Выделяют ограниченные деки:
дек с ограниченным входом - из конца дека можно только извлекать элементы;
дек с ограниченным выходом - в конец дека можно только добавлять элементы.
Данная структура является наиболее универсальной из рассмотренных выше линейных структур. Накладывая дополнительные ограничения на операции с началом и/или концом дека, можно осуществлять моделирование стека и очереди.
Дек также можно реализовывать как статическую структуру данных в виде одномерного массива, а можно как динамическую структуру - в виде линейного списка (рис.5).
Поскольку в деке, как и в очереди, осуществляется работа с обоими концами структуры, то целесообразно использовать те же подходы к организации дека, что применялись и для очереди.
Рисунок 5 - Дек и его организация
Контрольные вопросы.
1. Что относится к статистическим структурам данных
2. Понятие массива
3. Понятие строки
4. Понятие записи
5. Понятие множества
6. Понятие списка
7. Виды списков
8. Реализация линейного однонаправленного списка
9. Реализация линейного двунаправленного списка
10. Стек и его организация
11. Очередь и его организация
12. Дек и его организация
Размещено на Allbest.ru
...Подобные документы
Простые типы данных: порядковые, вещественные, дата-время. Стандартные процедуры и функции, применимые к целым типам. Кодировка символов в соответствии со стандартом ANSI. Структурированные типы: массивы; записи; множества. Указатели, динамическая память.
реферат [83,3 K], добавлен 01.12.2009Средства создания динамических структур данных. Формат описания ссылочного типа. Структура памяти во время выполнения программы. Линейные списки, стек, очередь. Организация списков в динамической памяти. Пример создания списка в обратном порядке.
лабораторная работа [788,2 K], добавлен 14.06.2009Проблемы с организацией данных. Определение и классификация динамических структур данных. Линейные односвязные, двухсвязные, кольцевые списки. Очередь, стеки. Описание основных типов данных и функции для работы с ними. Листинг программы, пример ее работы.
контрольная работа [290,6 K], добавлен 17.07.2012Линейные динамические структуры. Построение списочной структуры, состоящей из трехнаправленного и двух однонаправленных списков, связанных между собой. Дерево двоичного поиска для заданного множества целых чисел. Листинг программы на языках Си и Паскаль.
курсовая работа [451,1 K], добавлен 19.10.2013Способы ограждения пользователей от деталей фактического устройства данных. Список описателей переменных, указателей или массивов. Статические или динамические структуры данных. Доступ к различным элементам данных. Добавление и удаление элементов.
презентация [57,8 K], добавлен 14.10.2013Изучение применяемых в программировании и информатике структур данных, их спецификации и реализации, алгоритмов обработки данных и анализ этих алгоритмов. Программа определения среднего значения для увеличивающегося количества чисел заданного типа.
контрольная работа [16,0 K], добавлен 19.03.2015Рассмотрение общей характеристики данных. Исследование особенностей и назначения линейных, табличных и иерархических структур данных, анализ процесса их упорядочения. Рассмотрение основных режимов обработки данных. Описание алгоритма решения задачи.
реферат [27,4 K], добавлен 20.04.2019Особенности строковых типов данных и их обработка. Записи как совокупность поименованных компонентов различных типов, основные принципы работы с ними. Массивы - элементы и массивы структур. Понятие и свойства объединений. Файлы и работа с ними в языке СИ.
презентация [73,1 K], добавлен 09.12.2013Написание программы, исходя из конкретных данных. Создание двунаправленного линейного списка. Main - главная программа, содержащая меню. Занесение данных в память списка. Результирующий файл. Значения всех числовых данных из диапазона целого типа данных.
курсовая работа [2,3 M], добавлен 22.12.2010Разработка алгоритмов на динамических структурах данных. Описание структуры данных "стек". Процедуры добавления и удаления элемента, очистки памяти. Код распечатки содержимого всего стека. Инструкция пользователя, код программы, контрольный пример.
курсовая работа [22,9 K], добавлен 19.10.2010Решение задачи средствами прикладных программ. Разработка алгоритмов и структур данных. Реализация задачи определения статистических данных по успеваемости на факультете на языке программирования C#. Программа перевода чисел в различные системы счисления.
курсовая работа [519,9 K], добавлен 03.01.2015Сущность понятия "тип данных". Объектно-ориентированный стиль программирования. Простые типы данных в языке Паскаль: порядковые, вещественные, дата-время. Булевский (логический) тип. Синтаксис определения ограниченного типа. Регулярные типы (массивы).
реферат [24,1 K], добавлен 01.12.2009Изучение понятия баз данных - набора специальным образом организованных, хранящихся вместе данных, относящихся к определенному роду или кругу деятельности. СУБД – комплекс программных и языковых средств для создания, редактирования и ведения баз данных.
презентация [4,3 M], добавлен 21.02.2011Организация типов данных. Записи, оператор присоединения. Множества, операции над ними. Строки, стандартные процедуры и функции, работающие со строками. Совместимость типов. Явное и неявное преобразование типов. Многомерные массивы. Операции отношения.
презентация [30,8 K], добавлен 13.10.2013Разработка программы "Игроки КХЛ 2012-2013" на языке С++ с использованием классов списков структур для обработки данных. Описание глобальных переменных, разработанных функций. Главное меню программы. Чтение данных из файла, их просмотр и сохранение.
курсовая работа [2,2 M], добавлен 17.03.2016Рассмотрение правил записи, способов ввода и вывода, использования функций обработки символьных данных в Pascal. Описание алгоритмизации и программирования файловых структур данных, проектирования структуры файла. Ознакомление с работой данных массива.
курсовая работа [336,2 K], добавлен 27.06.2015Создание программы для обработки структуры данных. Возможность ввода и записи данных на персональном компьютере. Прикладное программирование на языке Turbo Pascal. Свободное редактирование записанных данных с помощью программы, написанной на Turbo Pascal.
лабораторная работа [11,4 K], добавлен 13.05.2011Общая характеристика данных. Список как простейшая линейная структура данных. Табличные структуры данных (матрицы). Принцип действия метода дихотомии. Основные режимы обработки данных. Расчет отчислений в фонды по каждому сотруднику с помощью MS Excel.
курсовая работа [1,6 M], добавлен 21.10.2009Определение понятия структур данных. Рассмотрение информации и ее представления в памяти. Особенности непозиционных и позиционных систем счисления. Классификация структур данных, операции над ними. Структурность данных и технология программирования.
презентация [359,3 K], добавлен 20.05.2015Создание базы данных, содержащей сведения о напильниках. Вывод данных об инструменте, номер насечки которых равен 2.Использование переменных типа "запись" при работе с базами данных. Решение задачи с использованием Microsoft Excel. Алгоритм программы.
курсовая работа [33,3 K], добавлен 08.03.2013
