Алгоритмический язык Паскаль
Очевидно, что простые переменные можно условно отнести к структуре прямого доступа, т.к. всегда можно выйти на значение переменной по ее имени.
Массивы фиксированного размера являются наиболее распространенными структурами данных. Большинство языков обеспечивают такие массивы в качестве основного встроенного типа структур данных.
Как правило, представление в памяти этих массивов и доступ к ним обеспечивается аппаратурой машин с помощью индексных регистров и операций индексирования.
В языках программирования массивы фиксированного размера представляются переменными с индексами, причем в зависимости от типа индексов различают массивы одномерные, двумерные и т.д. Одномерный массив иногда называют линейной таблицей или вектором. Логически вектор организован как последовательность элементов данных, к каждому из которых возможен индивидуальный доступ с помощью целого индекса, указывающего позицию элемента в последовательности.
Значения элементов вектора хранятся физически в памяти также в виде последовательности, т.е. структура вектора однозначно отображается на структуру памяти ЭВМ. При этом индекс элемента массива означает адрес ячейки памяти, содержащей значение этого элемента, относительно адреса ячейки памяти, хранящей значение первого элемента данного массива.
| Память | 101 | 102 | 103 | 104 | 105 | 106 | 107 |
| (ячейки) | | | | | | | |
| Вектор Х | X[1] | X[2] | X[3] | X[4] | X[5] | X[6] | X[7] |
Переменные с двумя и более индексами служат для описания многомерных массивов. Двумерный массив состоит из элементов, образующих прямоугольную таблицу. При отображении двумерного массива в память его элементы располагаются в виде последовательности (строка за строкой или столбец за столбцом).
|
|
[1,1] | [1,2] | [1,3] | [1,4] | Двумерный массив | ||||||||
| [2,1] | [2,2] | [2,3] | [2,4] | (матрица) | |||||||||
| [3,1] | [3,2] | [3,3] | [3,4] | ||||||||||
|
|
[4,1] | [4,2] | [4,3] | [4,4] | |||||||||
| Память | |||||||||||||
|
|
[1,1] | [1,2] | [1,3] | [1,4] | [2,1] | [2,2] | [2,3] | [2,4] | [3,1] | [3,2] | … | ||
Массив как структура данных характерен тем, что с помощью индексов обеспечивается прямой доступ к любому его элементу, поэтому операции выбора элемента массива или записи в массив сводятся к вычислению значений индексов.
Данные могут поступать либо с устройства ввода в неизвестном заранее количестве, либо генерироваться внутри программы непредсказуемым образом. Для представления таких данных и манипулирования ими допускаются линейные массивы, которые способны динамически расти и сокращаться во время работы программы. Для массивов переменной размерности существуют различные виды представлений, такие как очереди, стеки, деки, списки, таблицы, деревья.
Логическая организация этих массивов близка к логической организации массивов фиксированного размера, однако, здесь использовано другое представление в памяти и другие методы доступа. При организации массивов переменного размера учитывается, прежде всего, тот факт, что они (эти массивы) могут расти и сокращаться. Поэтому здесь используются так называемые связанные представления.
Если в массиве фиксированного размера главной операцией был доступ к элементу, то здесь уже в качестве основных операций фигурируют включение новых элементов и исключение существующих. Доступ к элементам массивов чаще всего относительный: найти элемент, следующий (или предыдущий) по отношению к данному, найти первый (последний) элемент и т.д.
Очереди - это структуры данных, организованные по принципу "первым пришел - первым ушел". Обработка элементов очереди ведется последовательно, причем элемент, который первым попал в очередь, первым обрабатывается и покидает ее. Добавление новых элементов производится в конец очереди.
Элементы, находящиеся в середине очереди, недоступны для обработки. Следовательно, доступными являются только два элемента:
первый ("голова") и последний ("хвост"). Над первым элементом выполняются операции чтения и обработки, над последним – операция записи в очередь. Для отображения очереди используются как последовательные, так и связанные представления.
Для последовательного представления можно использовать одномерный массив А[1], А[2],..., А[N], причем длина N этого массива выбирается с таким запасом, чтобы длина очереди не превышала N.
При отображении очереди на массив поступают так: первый элемент очереди хранят в первом элементе массива, а вновь поступающие записывают в следующие свободные элементы массива. После обработки первый элемент удаляется из очереди и на его место переписывается следующий за ним (второй) элемент. Это приводит к перемещению и всех следующих элементов очереди: на место второго будет переписан третий, на место третьего - четвертый и т.д. Этот способ не очень эффективен, хотя и отражает реальный процесс движения очереди.
На практике для отображения очереди применяют способ введения двух указателей (индексов), один из которых ссылается на элемент массива, хранящий "голову" очереди, а другой - на элемент массива, предназначенный для записи очередного элемента очереди ("хвост").
Пусть I - индекс элемента массива, хранящего "голову" очереди, а J - индекс первого свободного элемента массива, куда поступает новый элемент очереди ("хвост"). Тогда выборка очередного элемента очереди для обработки сводится к выполнению операций:
X:=А[I]; I:=I+1.
После этого индекс I указывает на следующий элемент очереди, т.е. "головой" ее становится следующий по порядку элемент. Запись нового элемента Y в очередь сводится к выполнению операций:
А[J]:=Y; J:=J+1.
Теперь индекс J снова указывает на первый свободный элемент массива.
Элементы очереди могут поступать и обрабатываться неравномерно, поэтому длина ее будет изменяться. В частности, возможен случай, когда очередь окажется пустой. Признаком этого может служить равенство I = J после чтения головного элемента очереди.
В процессе обработки очереди ее элементы будут смещаться к концу массива, т.к. J увеличивается после каждой записи в очередь. Поэтому возможен случай J > N после записи в очередь очередного элемента. При этом надо сместить очередь в начало массива, т.е. положить I = 1 и последовательно переписать все элементы очереди в элементы массива, начиная с А[1].
Чтобы избежать этой работы, можно замкнуть массив (очередь) по кольцу, т.е. элементом, следующим за последним элементом массива, считать его первый элемент:
|
|
I голова | . | . | . | хвост | J | ||||
| . | . | . | ||||||||
| A[1] | A[2] | A[3] | A[N-2] | A[N-1] | A[N] | |||||
|
|
||||||||||
При такой закольцовке просто определить переполнение очереди. Признаком этого факта является условие J = I, т.е. признак того, что "хвост" совпал с "головою" очереди.
Связанное представление очереди позволяет разбрасывать ее элементы по памяти. Здесь необходимо вместе с каждым элементом хранить указатель на местоположение следующего. Помимо этих двух указателей есть еще два дополнительных: указатели на начало и конец очереди. Последний служит для облегчения включения элементов в конец очереди.
|
|
|||
|
|
|||
|
|
|||
|
|
|||
|
|
|||
|
|
… | ||
|
|
|||
Стек - это структура данных, организованная по принципу "последним пришел - первым ушел". В стеке, в отличие от очереди, доступен только один элемент, называемый вершиной стека. При записи в стек очередной элемент заносится в его вершину, а остальные продвигаются вниз без изменения порядка. При выборке из стека удаляется элемент из его вершины, а все остальные сдвигаются вверх без изменения порядка, так что в вершину попадает элемент, поступивший в стек предпоследним. Пример для аналогии: стопка книг на столе, обойма (магазин) автомата.
Для стеков используют два представления - ПОСЛЕДОВАТЕЛЬНОЕ и СВЯЗАННОЕ.
ПОСЛЕДОВАТЕЛЬНОЕ представление требует резервирования блока памяти - одномерного массива А[1], А[2],..., А[N] - по тому же принципу, что и очередь. Величина N должна быть такой, чтобы стек мог расти до своего максимального размера без переполнения блока. Первый элемент блока - это указатель вершины стека, который можно задать с помощью индекса I. При записи в стек указатель вершины стека будет сдвигаться в сторону конца массива, при чтении из стека указатель вершины будет перемещаться в сторону начала массива. Значение I = 0 перед чтением из стека служит признаком его пустоты, а значение I = N перед записью в стек - признаком переполненности стека.
Представление стека в памяти:
| I - вершина | |||||||||||
|
|
|||||||||||
| . | . | . | |||||||||
| D[K] | D[K-1] | D[3] | D[2] | D[1] | |||||||
| указатель | |||||||||||
| вершины стека | |||||||||||
Связанное представление стека осуществляется путем введения указателя на местоположение следующего (предыдущего) элемента. Указатель на первый элемент стека должен находиться в указателе вершины. Включение и исключение элементов осуществляется, как показано на рисунке:
| СТЕК | D0 | СТЕК | ||||||||
|
|
D1 | D0 | ||||||||
|
|
новый элемент | |||||||||
| D2 | D1 | |||||||||
|
|
||||||||||
|
|
||||||||||
|
|
… | D2 | ||||||||
|
|
||||||||||
|
|
||||||||||
|
|
… | |||||||||
| СТЕК | СТЕК | Свободное | |||||||||
|
|
пространство | ||||||||||
|
|
D1 | D1 | |||||||||
|
|
|||||||||||
| D2 | D2 | ||||||||||
|
|
|||||||||||
|
|
|||||||||||
|
|
… | … | |||||||||
Стек удобен для вычисления значения арифметического выражения, представленного в обратной польской (бесскобочной) записи. Такие вычисления с помощью стека реализуются, например, во многих калькуляторах. Стек используют в обращениях к процедурам, а также при реализации рекурсий в Паскале.
Линейный массив переменного размера, в котором включение и исключение элементов может выполняться в произвольных точках, обычно называется списком (или связанным списком). Доступ к элементам списка, как правило, ограничивается первым и следующим (или иногда предыдущим) по отношению к данному. Следовательно, возможен доступ к любому элементу списка, но только путем "прокручивания" списка, начиная с первого элемента.
Поскольку вероятны произвольные включения и исключения элементов, то для списков используется только связанное представление, главным образом, две его формы:
1. Представление с одной связью: каждый элемент списка соединен со следующим; имеется указатель на первый элемент, который обычно находится в отдельной ячейке, называемой головой списка. Это представление идентично представлению очереди, рассмотренное нами ранее:
| Список | С1 | С2 | Сn | ||||||
|
|
… | Nil | |||||||
| 0-звено | 1-звено | 2-звено | n-звено | ||||||
| (голова) | |||||||||
2. Представление с двумя связями: каждый элемент списка соединен с последующим и предыдущим; в голове списка имеются указатели и на первый, и на последний элементы. Такие двусвязные списки принято называть деками.
СХЕМА ПРЕДСТАВЛЕНИЯ ДВУХСВЯЗНОГО СПИСКА
|
|
|||||
|
|
Список | С1 | |||
|
|
Ук. 1-го эл-та | ||||
|
|
Ук. 2-го эл-та | ||||
|
|
|||||
| С2 | |||||
|
|
|||||
|
|
|||||
|
|
|||||
|
|
… | ||||
|
|
|||||
|
|
… | ||||
| Сn-1 | |||||
|
|
|||||
|
|
|||||
|
|
|||||
| Cn | |||||
|
|
|||||
|
|
|||||
|
|
|||||
Связанное представление с одной связью имеет тот недостаток, что список можно просматривать только в одном направлении. Для движения в обе стороны нужны двусвязные списки (деки), однако они занимают много памяти (содержат две ссылки), поэтому их надо использовать, если движение в обе стороны очень необходимо.
Если последнее звено списка имеет ссылку на первое звено как на следующее, а первое звено ссылается на последнее как на предыдущее, то такой список оказывается замкнутым по кольцу и называется кольцевым.
Часто списки строят по иерархическому принципу. В этом случае его записи могут иметь внутреннюю структуру, организованную также по принципу списка (основной список оказывается состоящим из записей-подсписков). В этом случае приходят к многомерным массивам переменного размера.
Ниже следуют фрагменты программ на Паскале записи и чтения элементов в очереди и стеке.
13. СТРУКТУРЫ ПРЯМОГО ДОСТУПА. СПОСОБЫ СОРТИРОВКИ МАССИВА
Рассмотрим несколько способов упорядочивания одномерных массивов по возрастанию величин их элементов. Такая задача называется сортировкой массива.
При решении ее возможны два подхода: использование промежуточного (вспомогательного) массива и сортировка внутри самого массива.
Первый способ, хотя в какой-то степени и проще, неэффективен, т.к. требует увеличения памяти и лишних операций пересылки элементов из одного массива в другой. Поэтому рассмотрим способы сортировки внутри самого массива.
Выделяют 3 основных способа сортировки:
1. Прямое включение.
2. Прямой выбор.
3. Прямой обмен.
Каждый из перечисленных способов имеет свои достоинства и недостатки. Поэтому стараются эти способы улучшить (модернизировать), хотя в принципе все они находятся в рамках одного из указанных направлений.
13.1 Прямое включение
Суть этого способа такова: в массиве берется i-й элемент и включается (вставляется) на свое место между 1-м и i-м элементами. Эта идея может быть выражена в виде следующего цикла:
FOR I:=2 TO N DO
BEGIN X:=A[I];
<включить X на свое место между A[1] и A[I]> END.
Из указанного видно, что на каждом шаге i все элементы с 1-го до (I-1)-го уже упорядочены, следовательно, при I = N произойдет последняя сортировка и N-й элемент встанет на свое место. Алгоритм должен быть таким, что если I-й элемент стоит в ряду, т.е. не нарушает порядка, то никаких действий совершать не надо, а следует перейти к I+1-му элементу.
Например, рассмотрим сортировку следующего массива:
| -3 | 2 | 4 | 1 | 6 | 3 |
| 1 | 2 | 3 | 4 | 5 | 6 |
Здесь все элементы до четвертого уже упорядочены и сортировка должна произойти при I = 4. Суть метода состоит в том, что среди элементов с 1-го по 4-й ищется такой, который меньше четвертого, равного 1. В нашем случае этим элементом является первый, равный -3. В ходе поиска четвертый элемент 1 запоминается в специальной переменной X, а все элементы циклически сдвигаются на одну позицию вправо:
1-й шаг: 1<4? - да => сдвиг
| -3 | 2 | 4 | 4 | 6 | 3 |
2-й шаг: 1<2? - да => сдвиг
| -3 | 2 | 2 | 4 | 6 | 3 |
3-й шаг: 1<-3? - нет
| -3 | 1 | 2 | 4 | 6 | 3 |
На третьем шаге сдвига не происходит и после него запомненный элемент ставится на свое место, т.е. на место второго элемента ставится четвертый из исходного массива. Поиск и сдвиг идут по циклу WHILE, в котором в качестве условия берется сравнение X < А[I-1].
Продолжая наш пример, заметим, что на пятом шаге никаких действий происходить не будет, а на шестом элемент А[6]=3 должен пойти на четвертое место, сдвигая пятый элемент на шестое место, а четвертый элемент - на пятое место:
3<6? - да => сдвиг
| -3 | 1 | 2 | 4 | 6 | 6 |
3<4? - да => сдвиг
| -3 | 1 | 2 | 4 | 4 | 6 |
3<2? - нет=>
| -3 | 1 | 2 | 3 | 4 | 6 |
Прежде чем переходить к самой программе, заметим, что если I-й элемент должен передвинуться на 1-е место, то в нашем алгоритме для окончания процесса сдвига нужно иметь элемент слева от А[1] для сравнения (барьер). Таким элементом является А[0]. Отсюда заключаем, что в цикле FOR от 2 до N нужно для каждого шага I предусмотреть засылку в А[0] сортируемого элемента.
procedure PRVKLUCH (var MM:MAS);
var I,J,X: integer;
begin
¦ for I:= 2 to N do
¦ begin
¦ ¦ X:=MM[I]; MM[0]:=X; J:=I;
¦ ¦ while X < MM[J-1] do
¦ ¦ begin
¦ ¦ ¦ MM[J]:=MM[J-1]; J:=J-1;
¦ ¦ end;
¦ ¦ MM[J]:=X;
¦ end;
end.
Из этой процедуры видно, что выход из нее происходит тогда, когда (J-1)-й элемент становится меньше I-го элемента. Слева от I-го уже не может быть меньшего элемента, т.к. на каждом шаге все элементы до