Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Основная коллекция
Артикул: 787130.01.99
В учебно-методическом пособии рассмотрены основные структуры данных, использующиеся для хранения и обработки информации, приведены варианты заданий для лабораторных работ. Учебно-методическое пособие предназначено для студентов направления «Информатика и вычислительная техника» в рамках дисциплины «Организация ЭВМ и систем».
Смирнова, О. В. Структуры данных : учебно-методическое пособие / О. В. Смирнова, К. В. Смирнов. - Москва : РУТ (МИИТ), 2018. - 40 с. - Текст : электронный. - URL: https://znanium.com/catalog/product/1895308 (дата обращения: 28.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
Министерство транспорта Российской Федерации  

Федеральное государственное бюджетное  

образовательное учреждение высшего образования  

«Российский университет транспорта (МИИТ)» 

___________________________________________________ 

 

Институт пути, строительства и сооружений 

 
 

Кафедра 

«Системы автоматизированного проектирования» 

 
 
 

О. В. СМИРНОВА 

К.В. СМИРНОВ 

 
 
 
 

СТРУКТУРЫ ДАННЫХ 

 

Учебно-методическое пособие 

 
 
 
 
 

Москва – 2018

Министерство транспорта Российской Федерации 

Федеральное государственное бюджетное  

образовательное учреждение высшего образования  

«Российский университет транспорта (МИИТ)» 

___________________________________________________ 

 

Институт пути, строительства и сооружений 

 
 

Кафедра 

«Системы автоматизированного проектирования» 

 
 
 

О. В. СМИРНОВА 

К.В. СМИРНОВ 

 
 
 
 

СТРУКТУРЫ ДАННЫХ 

 

Учебно-методическое пособие 

для студентов направления «Информатика и вычислительная техника» 

 
 
 
 
 
 
 
 
 

Москва – 2018 

УДК  004 
С 50 
 

Смирнова О.В., Смирнов К.В. Структуры данных: 

Учебно-методическое пособие. – М.: РУТ (МИИТ), 2018.  – 40 с. 

 
В учебно-методическом пособии рассмотрены основные 

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

студентов 
направления 
«Информатика 
и 
вычислительная 

техника» в рамках дисциплины «Организация ЭВМ и систем».  

 
 
 
 
 
 
 

Рецензент: 
 

Доцент кафедры «Менеджмент качества» РУТ (МИИТ),  
кандидат физико-математических наук А.А. Рогов 

 

 
 
 
 
 
 

© РУТ (МИИТ), 2018 

 

Оглавление 

Введение .................................................................................. 4 

Стек........................................................................................... 5 

Очередь .................................................................................... 9 

Связанные списки ................................................................. 12 

Деревья ................................................................................... 20 

Список литературы ............................................................... 39 

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение 

Все структуры данных условно делятся на два класса – 

структуры последовательного и произвольного доступа. В 
первых структурах доступ возможен к одному или 
нескольким элементам. Обычно это элементы в начале или 
в конце структуры. Так, в случае очереди доступны лишь 
элементы в её начале и конце, в случае стека – элемент в 
его вершине. В структурах произвольного (прямого) 
доступа можно производить действия с любым элементом 
структуры, при этом не требуется переборов всех или 
части элементов. 

Реализации структур данных можно также разделить 

на два класса – непрерывные и ссылочные. В непрерывных 
реализациях элементы структуры данных располагаются 
последовательно друг за другом в некотором непрерывном 
отрезке массива, причём порядок их расположения в 
массиве 
соответствует 
их 
порядку 
в 
реализуемой 

структуре. В ссылочных реализациях элементы структуры 
данных хранятся в совершенно произвольном порядке. 
При этом вместе с каждым элементом хранятся ссылки на 
один или несколько «соседних» элементов. В качестве 
ссылок могут выступать либо индексы ячеек массива, либо 
адреса памяти. 

Ссылочные реализации имеют недостатки: 

1. для 
хранения ссылок требуется дополнительная 

память; 

2. для доступа к некоторому элементу необходимо 

пройти последовательно по цепочке других элементов. 
 
Но 
все 
недостатки 
ссылочных 
реализаций 

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

В учебно-методическом пособии рассматриваются 

принципы работы с простейшими структурами данных: 

стеками, очередями, списками и бинарными деревьями.  

 

Стек 

Стек – самая популярная и важная структура данных. 

Из стека можно удалить только тот элемент, который был 
добавлен в него последним. Стек работает по принципу 
«последним пришёл – первым ушёл» (last-in, first-out – 
сокращённо LIFO). Примером стека может служить стопка 
бумаг на столе или стопка тарелок. Тарелки берутся в 
порядке, обратном их добавлению. Доступна только 
тарелка на вершине стопки. 

В компьютерах стек используется для: 
• размещения локальных переменных; 
• размещения параметров процедуры или функции; 
• сохранения адреса возврата (по какому адресу надо 

вернуться из процедуры); 

• временного хранения данных. 
На стек выделяется ограниченная область памяти. При 

каждом вызове процедуры в стек добавляются новые 
элементы (параметры, локальные переменные, адрес 
возврата). Поэтому если вложенных вызовов будет много, 
стек переполнится. 

На рисунке 1 показано, как можно реализовать стек 

ёмкостью не более N элементов на базе массива S. 
Индексы ячеек массива изменяются от 0 до N-1. Индекс 
элемента наверху стека обозначим через переменную t, 
которая называется указателем стека.  

Удобно объединить в одной структуре сам массив и 

его размер. Объявим новый тип данных: стек на 10 
элементов-символов. 

const int MAXSIZE = 10; 
struct Stack { 
 
char data[MAXSIZE]; 

 
int size; }; 

 

а)
0
1
2
3
4
5
6

S
15
6
2
9

 

                                                t=3 
 

б)
0
1
2
3
4
5
6

S
15
6
2
9
17
3

 
                                                                             t=5 
 

в)
0
1
2
3
4
5
6

S
15
6
2
9
17
3

 
                                                              t=4 

Рисунок 1. Реализация стека на базе массива S. 

 

Светло-серые клетки заняты элементами стека.  

(а) – Стек содержит 4 элемента, верхний элемент – число 9.  
(б) – Тот же стек после выполнения операций Push для 
элементов 17 и 3.  
(в) – Стек после того, как операция Pop вернула значение 3 
(последний добавленный в стек элемент). Хотя число 3 
присутствует в массиве S, в стеке его уже нет; на вершине 
стека число 17. 
 

Для 
работы 
со 
стеком 
надо 
определить, 
как 

выполняются операции добавление элемента на вершину 
стека Push и удаление элемента с вершины стека Pop.  

Поскольку 
нумерация 
элементов 
массива 
data 

начинается с нуля, надо сначала записать новый элемент в 
S.data[S.size], а затем увеличить размер стека. В процедуре 
предусмотрена обработка ошибки «переполнение стека». В 
этом случае на экран будет выдано сообщение «Стек 
переполнен». Можно написать функцию Push, которая 
будет возвращать 1 в случае удачного добавления элемента 

и 0 в случае ошибки. 

void Push ( Stack &S, char x ) 
{ 
 
if ( S.size = = MAXSIZE )  

 
{ 

 
 printf ("Стек переполнен"); 

 
 return; 

 
} 

 
S.data[S.size] = x; 

 
S.size ++; 

} 
Обратите внимание, что стек S передаётся в процедуру 

по ссылке, то есть, фактически передаётся адрес этого 
стека в памяти. Поэтому все операции со стеком в 
процедуре выполняются непосредственно со стеком 
вызывающей программы. 

char Pop ( Stack &S ) 
{ 
 
if ( S.size = = 0 )  

 
{ 

 
 printf ("Стек пуст"); 

 
 return char(255); 

 
} 

 
S.size --; 

 
return S.data[S.size]; 

} 
Функция Pop возвращает символ, «считанный» с 

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

 
Задание 1. Ввести символьную строку, которая может 

содержать три вида скобок: (), [] и {}. Определить, верно 

ли расставлены скобки (символы между скобками не 
учитывать). Например, в строках ()[{}] и [{}([])] скобки 
расставлены верно, а в строках ([)] и ]]]((( - неверно. 

Решение: выполним решение задачи с помощью стека. 
Вначале стек пуст. Проходим всю строку от начала до 

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

В 
приведённой 
ниже 
программе 
используются 

написанные ранее объявление структуры Stack и операции 
Push и Pop. Открывающие и закрывающие скобки 
записаны в массивах br1 и br2. 
void main() 
{ 

char br1[3] = { '(', '[', '{' }; // открывающие скобки 
char br2[3] = { ')', ']', '}' }; // закрывающие скобки 
char s[80], upper; 
int i, k, flag; 
Stack S; // стек символов 
printf("Введите выражение со скобками> "); 
gets ( s ); 
S.size = 0; // сначала стек пуст 
flag = 1; 
for (i = 0; flag && (s[i] != '\0'); i ++) 
 
for ( k = 0; k < 3; k ++ ) // проверить 3 вида скобок 

 
{ 

 
if ( s[i] = = br1[k] )  // открывающая скобка 

 
 {  
Push ( S, s[i] );    break; 
} 

 
if ( s[i] = = br2[k] ) // закрывающая скобка 

 
{ upper = Pop ( S ); 

if ( upper != br1[k] ) 

 
  
 flag = 0; 

 
 break; 

 
} 

 
} 

if (flag && (S.size = = 0) ) 
 
printf("\nВыpажение пpавильное\n"); 

else printf("\nВыpажение непpавильное \n"); 

} 

В самом начале стек пуст и его размер равен нулю 

(S.size = 0). Переменная flag служит для того, чтобы выйти 
из внешнего цикла, когда обнаружена ошибка (и не 
рассматривать 
оставшуюся 
часть 
строки). 
Она 

устанавливается в нуль, если в стеке обнаружена скобка 
другого типа или стек оказался пуст. 

 

Очередь 

Очередь в программировании аналогична очереди в 

повседневной жизни. Она содержит элементы, как бы 
выстроенные друг за другом в цепочку. У очереди есть 
начало и конец. Элемент, добавляемый в очередь, 
оказывается в её конце, элемент, удаляемый из очереди, 
находится в её начале. Очередь работает по принципу 
«первым пришёл – первым ушёл» (first-in, first-out – 
сокращённо FIFO). 

Операцию добавления  элемента в очередь обозначим 

Inq, а операцию удаления элемента Deq. 

На рисунке 2 показано, как можно реализовать 

очередь, вмещающую не более N элементов, на базе 
массива Q. Индексы ячеек массива изменяются от 0 до 
N-1. Массив свернут в кольцо: за N-1 следует 0. Кроме 
массива реализация очереди содержит три простые 
переменные: индекс начала очереди h, индекс конца 
очереди t, число элементов очереди N.