Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19
Download 1.98 Mb.
|
Lekcii AiSD 2015
|
T.é. M B HéB6IMOMHéHH> y >oBHSBOMe dTO é while:
while(Cur != Start ... ) 107 Ведущее звено кольцевого 2-связного списка создаётся на- бором операторов: Link2 *L2 = new Link2; L2->next = L2; L2->prev = L2; Графически состояние списка после создания этого звена может быть представлено таким образом: Рис. 9.6 — Ведущее звено пустого двусвязного кольцевого списка 9.6. Многосвязные списки Многосвязные списки представляют собой динамические СТ]Э KT ]ЭЫ ДіІННЫХ, В OCHOB КОТО]ЭЫХ ПОПОЖ НЫ ОДНО- ИПИ ДВ - связные списки, в которых имеются дополнительные связи меж- ду звеньями. Чаще всего, такие связи проводятся между далеко отстоящими звеньями, например, обозначающими категории данных. Пример многосвязного списка показан на следующем рисунке. Рис. 9.7 — Многосвязный список Переход между звеньями АА и БА может выполнен по до- полнительной связи, в обход звеньев АБ и AB. Из-за такого ха- рактера перемещения эти списки иногда называют скпп- списками (skip — перепрыгивать). А при характере размещения данных, подобном показанному на этом рисунке, такие списки называют словарны ми (иногда просто словарями, но термин «словарь» может использоваться в теории структур данных в разных значениях). Возможны и другие варианты многосвязных 108
Вопросы и задания для самоконтроля Что представляют собой связные списки? К каким классификационным группам структур данных ОТНОСЯТСЯ СПИСКИ Какие существуют разновидности связных списков? В чем состоит отличие несвязного списка от массива? В чем состоит отличие связного списка от массива? В чем состоит отличие линейного списка от кольцевого? В чем заключаются недостатки односвязного списка? В чем состоит отличие односвязного списка от двусвяз- ного? Какие операции применяются для связных списков? В чем отличие считывания информации из списка от считывания из очереди или стека? Особенности операций вставки и удаления для связных СПИСКОВ. В чем отличие операции вставки в двусвязный список от вставки в односвязный список? В чем отличие операции удаления из двусвязного спи- ска от удаления из односвязного списка? В чем заключаются особенности работы с кольцевыми списками? Какой тип должно иметь звено связного списка? Поче- У’ Что обязательно должно содержать звено связного списка? В чем состоит отличие звена двусвязного списка от звена односвязного списка? В чем состоит отличие связного списка от стека, opгa- низованного в виде связного списка? Перечислите сходства и отличия списков и очередей. Перечислите достоинства и недостатки линейных од- В чем заключается поиск в списке? 109
Измените функцию поиска в односвязном списке так, чтобы не использовалась локальная переменная Success. Упростите функцию поиска в односвязном списке так, чтобы она находила только звено с искомыми данными, но не предыдущее звено. Упростите функцию поиска в односвязном списке так, чтобы она находила только предыдущее по отношению к иско- мому звено. Изобразите структуру линейного односвязного списка. Изобразите структуру линейного двусвязного списка. Перечислите достоинства и недостатки линейных дву- Изобразите возможные структуры двусвязных кольце- Объясните назначение выделенного заглавного звена в Download 1.98 Mb. Do'stlaringiz bilan baham: 
|