Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

Вопросы и задания для самоконтроля

1. 
   Что представляет собой стек?
   
2. 
   На основе каких структур данных могут организовы- ваться стеки?
   
3. 
   Чем отличается стек на основе массива от стека на ос- нове связного списка?
   
4. 
   Чем отличается стек на основе связного списка от соб- ственно связного списка?
   
5. 
   К каким структурам данных относятся очереди и стеки?
   
6. 
   Перечислите основные отличия стека от очереди.
   
7. 
   Какой метод доступа используется при доступе к эле- ментам стека? В чем его особенности?
   
8. 
   Перечислите основные операции, применяемые при ра- боте со стеками. К каким позициям в стеке они могут применять- ся?
   
9. 
   Какой характер имеет операция считывания для стеков?
   
10. 
    Перечислите задачи, для решения которых применяют- ся стеки.
    
11. 
    Изобразите структуру звена динамического стека.
    
12. 
    Как определить наличие или отсутствие элементов в стеке?
    
13. 
    Как определить количество элементов в стеке?
    

89

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

Понятие « сппскп» включает в себя самые разные структуры данных. Это могут быть и массивы, в том числе массивы записей, и специальные динамические структуры данных, и даже деревья. Общим для них является то, что они содержат набор записей од- ного вида, ограниченный по размеру или неограниченный, упо- рядоченный или неупорядоченный. Данные, хранящиеся в этих записях, обычно лоспческп связаны между собой, например, фа- милии студентов одной группы и т.п. В тексте программы такая связь может выражаться в том, что все такие элементы хранятся в одном и том же массиве как непрерывном блоке памяти. Но кро- ме общего имени массива (и адреса его начала) между этими элементами никакой другой фнзнческой связи нет, и на физиче- cкi›я уровне подобные списки могут быть названы «несвязны - оп» (или, что то же самое, «несвязанны ми» ). Т.е. внутри них нет связей (их элементы не связаны друг с другом Qнзпческн).

Типичным примером физически несвязного списка является массив. В этой главе мы рассмотрим те самые «специальные ди- намические структуры данных», которые и получили название



Вспомним общие черты очередей и стеков: строгие правила доступа к данным;
— операции извлечения (считывания) данных являются раз- рушающими.
Связные списки свободны от этих ограничений. Они допус- кают гибкие методы доступа; извлечение (чтение) элемента из списка не приводит к удалению его из списка и потере данных. Для фактического удаления элемента из связного списка требует- ся специальная процедура.
Связные списки представляют собой динамические (факти- чески, линейные!) структуры данных (динамические цепочки звеньев ), в которых однотипные элементы (звенья) каким-либо образом связаны между собой, обычно на физическое уровне. Связь между элементами можно осуществить за счёт хранения в одном элементе адреса другого такого же элемента (того же ти- па). Т.е. каждый информационный элемент содержит внутри себя указатель на собственный тип. Учитывая, что кроме этого указа-

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

struct Linkl

int data; Link1* next;

Классификация связные списков. Ухо числу связей (н одно- временно, направлению) списки бывают односвязны ми (однона- правленными), двусвязными (двунаправленными) и эіпогосsлз-


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

• 
  просмотр (или прохождение) списка;
  

91

• 
  поиск данных в списке;
  
• 
  создание ведущего (заглавного) звена (при необходимо- сти);
  

сортировка списка;

• 
  обращение (реверсирование) списка, т.е. перестановка всех его звеньев в обратном порядке.
  

Рассмотрим основные из этих операций для каждого вида списка отдельно, вместе с особенностями этих видов списков.