Файл: Алгоритмы сортировки данных (Структура и типы данных).pdf

ВУЗ: Не указан

Категория: Курсовая работа

Дисциплина: Не указана

Добавлен: 26.05.2023

Просмотров: 88

Скачиваний: 3

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Символьный тип данных – это совокупность символов, используемых в том или ином компьютере. Переменная данного типа принимает значение одного из этих символов, занимает в памяти компьютера 1 байт. Слово Char определяет величину данного типа. Существует несколько способов записать символьную переменную (или константу):

  1. как одиночный символ, заключенный в апострофы: ‘W’, ‘V’, ‘п’;
  2. указав код символа, значение которого должно находиться в диапазоне от 0 до 255.
  3. при помощи конструкции ^K, где K – код управляющего символа. Значение K должно быть на 64 больше кода соответствующего управляющего символа.

К величинам символьного типа данных применимы операции отношения и следующие функции:

Succ(x) — возвращает следующий символ;

Pred(x) — возвращает предыдущий символ;

Ord(x) — возвращает значение кода символа;

Chr(x) — возвращает значение символа по его коду;

UpCase(x) — переводит литеры из интервала ‘a’..’z’ в верхний регистр.

Строковый тип

Строка в Паскале представляет собой последовательность символов заключенных в апострофы, и обозначается словом String. Число символов (длина строки) должно не превышать 255. Если длину строки не указывать, то она автоматически определиться в 255 символов. Общий вид объявления строковой переменной выглядит так:

Var <имя_переменной>: string[<длина строки>];

Каждый символ в строке имеет свой индекс (номер). Индекс первого байта – 0, но в нем храниться не первый символ, а длина всей строки, из чего следует, что переменная этого типа будет занимать на 1 байт больше числа переменных в ней. Номер первого символа – 1, например, если мы имеем строку S=‘stroka’, то S[1]=s;. В одном из следующих уроков строковый тип данных будет рассмотрен подробнее.

Перечисляемый тип данных

Перечислимый тип представляет собой упорядоченный тип данных, определяемый программистом, т.е. программист перечисляет все значения, которые может принимать переменная этого типа. Значения являются неповторяющимися, количество которых не может быть больше 256.

Перечисляемый тип данных представляет собой некоторое ограниченное количество идентификаторов. Эти идентификаторы заключаются в круглые скобки, и отделяются друг от друга запятыми.

Пример:

Type Day=(Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday);

Var A: Day;

Переменная A может принимать лишь значения определенные в разделе Type. Также можно объявить переменную перечисляемого типа в разделе Var:


Var A: (Monday, Tuesday);

К данному типу применимы операции отношения, при этом заранее определенно, что Monday<Tuesday<Wednesday т. д. Также можно применять функции succ, pred, ord, процедуры inc и dec, и использовать операцию присваивания: A:=Tuesday;

Интервальный тип данных

Один из способов образования новых типов из уже существующих - ограничение допустимого диапазона значений некоторого стандартного скалярного типа или рамок описанного перечислимого типа. Определяется заданием минимального и максимального значений диапазона. При этом изменяется диапазон допустимых значений по отношению к базовому типу, но представление в памяти полностью соответствует базовому типу. 

Когда необходимо задать какой то диапазон значений, то в таких ситуациях применяется интервальный тип данных. Для объявления используется конструкция m..n, где m – минимальное (начальное) значение, а n – максимально (конечное); здесь m и n являются константами, которые могут быть целого, символьного, перечисляемого или логического типа. Описываться величины интервального типа могут как в разделе типов, так и в разделе описания переменных.

Общий вид:

TYPE  <имя_типа> = <мин. значение>..<макс. значение>;

Пример:

TYPE Cards = 1..36;

Битовые типы

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

Указатели

Тип указателя представляет собой адрес ячейки памяти. При программировании на низком уровне - в машинных кодах, на языке Ассемблера и на языке C, который специально ориентирован на системных программистов, работа с адресами составляет значительную часть программных кодов. 

1.3 Структуры данных

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


Статические структуры в языках программирования связаны со структурированными типами. Структурированные типы в языках программирования являются теми средствами интеграции, которые позволяют строить структуры данных сколь угодно большой сложности. К таким типам относятся: массивы, записи (в некоторых языках - структуры) и множества (этот тип реализован не во всех языках). 

Векторы

Вектор (одномерный массив) - структура данных с фиксированным числом элементов одного и того же типа. Каждый элемент вектора имеет уникальный в рамках заданного вектора номер и имя. 

Массивы

Логическая структура.

Массив - такая структура данных, которая характеризуется: фиксированным набором элементов одного и того же типа; каждый элемент имеет уникальный набор значений индексов; количество индексов определяют мерность массива (два индекса - двумерный массив); обращение к элементу массива выполняется по имени массива и значениям индексов для данного элемента. 

Физическая структура - это размещение элементов массива в памяти ЭВМ. 

Многомерные массивы хранятся в непрерывной области памяти. Размер слота определяется базовым типом элемента массива. Количество элементов массива и размер слота определяют размер памяти для хранения массива. Принцип распределения элементов массива в памяти определен языком программирования.

Специальные массивы. На практике встречаются массивы, которые в силу определенных причин могут записываться в память не полностью, а частично. Это особенно актуально для массивов настолько больших размеров, что для их хранения в полном объёме памяти может быть недостаточно. К таким массивам относятся симметричные и разреженные массивы

Симметричные массивы. Двумерный массив, в котором количество строк равно количеству столбцов называется квадратной матрицей. Квадратная матрица, у которой элементы, расположенные симметрично относительно главной диагонали, попарно равны друг другу, называется симметричной. 

 Разреженные массивы. Разреженный массив - массив, большинство элементов которого равны между собой. 

Множества

Логическая структура: Множество - такая структура, которая представляет собой набор неповторяющихся данных одного и того же типа. Множество может принимать все значения базового типа. Базовый тип не должен превышать 256 возможных значений. Поэтому базовым типом множества могут быть byte, char и производные от них типы. 


^ Физическая структура: Множество в памяти хранится как массив битов, в котором каждый бит указывает является ли элемент принадлежащим объявленному множеству или нет. Т.о. максимальное число элементов множества 256, а данные типа множество могут занимать не более 32-ух байт.

^ Числовые множества. Стандартный числовой тип, который может быть базовым для формирования множества - тип byte. 

Символьные множества. Символьные множества хранятся в памяти также как и числовые множества. Разница лишь в том, что хранятся не числа, а коды ASCII символов. 

^ Множество из элементов перечислимого типа. Множество, базовым типом которого есть перечислимый тип, хранится также, как множество, базовым типом которого является тип byte. 

^ Множество от интервального типа. Множество, базовым типом которого есть интервальный тип, хранится также, как множество, базовым типом которого является тип byte. 

Записи

Запись - конечное упорядоченное множество полей, характеризующихся различным типом данных. Полями записи могут быть интегрированные структуры данных - векторы, массивы, другие записи. 

Таблицы

Таблица - сложная интегрированная структура. С физической точки зрения таблица представляет собой вектор, элементами которого являются записи. Логической особенностью таблиц является то, что доступ к элементам таблицы производится не по номеру (индексу), а по ключу - по значению одного из свойств объекта, описываемого записью-элементом таблицы. Ключ - это свойство, идентифицирующее данную запись во множестве однотипных записей. Ключ может включаться в состав записи и быть одним из её полей, но может и не включаться, а вычисляться по положению записи. Таблица может иметь один или несколько ключей. Иногда различают таблицы с фиксированной и с переменной длиной записи.  ^

Полустатические структуры данных характеризуются следующими признаками: они имеют переменную длину и простые процедуры её изменения; изменение длины структуры происходит в определенных пределах, не превышая какого-то максимального значения. Если полустатическую структуру рассматривать на логическом уровне, то можно сказать, что это последовательность данных, связанная отношениями линейного списка. Физическое представление полустатических структур данных в памяти это обычно последовательность слотов в памяти, где каждый следующий элемент расположен в памяти в следующем слоте (т.е. вектор). 


Стеки

Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Основные операции над стеком - включение нового и исключение элемента из стека. Полезными могут быть также вспомогательные операции: определение текущего числа элементов в стеке и очистка стека. 

Очереди FIFO

Очередью FIFO (First In First Out - "первым пришел - первым вышел") называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (конец), а исключение - с другой стороны (начало). Основные операции над очередью - включение, исключение, определение размера, очистка, неразрушающее чтение. 

Деки

Дек - особый вид очереди. Дек (от англ. deq - double ended queue, т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Операции над деком: включение элемента справа, слева; исключение элемента справа, слева; определение размера; очистка. 

Строки

Строка - это линейно упорядоченная последовательность символов, принадлежащих конечному множеству символов, называемому алфавитом. Говоря о строках, обычно имеют в виду текстовые строки - строки, состоящие из символов, входящих в алфавит какого-либо выбранного языка, цифр, знаков препинания и других служебных символов. Базовыми операциями над строками являются: определение длины строки; присваивание строк; конкатенация (сцепление) строк; выделение подстроки; поиск вхождения. 

Связные линейные списки.

Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным. Если ограничения на длину списка не допускаются, то список представляется в памяти в виде связной структуры. Линейные связные списки являются простейшими динамическими структурами данных. 
Но, обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения в противоположную сторону. Такую возможность обеспечивает двухсвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Для удобства обработки списка добавляют еще один особый элемент - указатель конца списка.5