Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Задания для самостоятельной работы

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

 

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

 

Списки

 

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

В односвязном списке каждый элемент, кроме последнего, содержит ссылку на следующий элемент в списке, т.е. у каждого элемента есть два поля: имя и указатель (рис. 6.1а). Структура списка (рис. 6.1б) содержит указатель на первый элемент (First), который является внешним.

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

 
 

Рассмотрим процедуры вставки элемента INS(NEL, FREE, POS) и удаления элемента DEL(POS) при работе с различными списками. Здесь NEL – новый элемент, FREE – индекс первой свободной ячейки, POS – позиция того элемента, после которого нужно вставить (удалить) элемент.

Пример 6.1. Задан список, состоящий из 6 элементов. Требуется выполнить следующее задание.

1. Записать список в виде двух массивов NAME и NEXT.

2. Вставить элемент А34 между А3 и А4; показать, как при этом изменяются массивы.

3. Удалить из исходного списка А5; показать, как при этом изменяются массивы.

Решение представлено в табл. 6.1 – 6.3, состоящих из трех основных столбцов: индекса, имени элемента – NAME и указателя на следующий элемент – NEXT.

По указателю FREE и по отмеченным жирным шрифтом элементам массивов NAME и NEXT можно наблюдать изменения, происходящие при внесении и удалении элемента. Отметим, что удаление элемента из списка не означает его физического уничтожения (показано в табл. 6.3 зачернением).  
Таблица 6.1

Индекс NAME NEXT
  ----  
  А1  
  А2  
  А3  
  А4  
  А5  
  А6  
7Free ---- ----

 

Таблица 6.2 Таблица 6.3

Индекс NAME NEXT   Индекс NAME NEXT
  ---     ---  
  A1     A1  
  A2     A2  
3 Pos A3     A3  
  A4   4 Pos A4  
  A5   5 Free    
  A6     А6  
  A34    
8 Free --- ---

 

Двусвязный список

В двусвязном списке присутствует система двойных указателей, поэтому в таблице добавляется столбец PREV (previous - предыдущий), указывающий на связи с предыдущим элементом.

 
 

Пример 6.2. Для двусвязного списка, состоящего из 6 элементов (рис. 5.2.), выполнить то же задание, что и в примере 6.1.

 

Таблица 6.4 Таблица 6.5

Индекс NAME NEXT PREV   Индекс NAME NEXT PREV  
 
  ----   ----   ----   ----  
 
 
  A1       A1      
 
 
  A2       A2      
 
  A3     3 Pos A3      
  A4       A4      
 
  А5       A5      
 
  A6       A6      
7 Free --- --- ---   A34      
  8 Free --- --- ---  

 

Таблица 6.6

Индекс NAME NEXT PREV
  ----   ----
  A1    
  A2    
  A3    
4 Pos A4    
5Free      
  A6    

 

Кольцевой список

Рассмотрим кольцевой список, в котором последний элемент имеет указатель на первый элемент.

 
 

Пример 6.3. Задан кольцевой список, состоящий из шести элементов (рис. 6.3.); выполнить то же задание, что и в примере 6.1.

 

Решение опять представим в виде таблиц с тремя столбцами: индекс, имя и указатель на следующий элемент.

 
 
Разница между содержимым таблицы обычного списка (пример 1, табл. 6.1) и содержимым таблицы кольцевого списка (табл. 6.7) в том, что в табл. 6.7 нет пустой строки, а в 6–й строке NEXT[6] =1, а не пусто. Содержимое табл. 6.8 и 6.9 аналогично содержимому табл. 6.2 и 6.3 для простого списка.  


Таблица 6.7

Индекс NAME NEXT
  А1  
  А2  
  А3  
  А4  
  А5  
  А6  
7 Free ---- ----

 

 

Стек

Рассмотрим работу со стеком. Стек представляется массивом, в таблице – это столбец NAME. Вершина стека определяется значением переменной ТОР. Ввод и вывод элемента производится на одном конце списка. При работе со стеком производятся следующие операции:

вставка - TOP:=TOP + 1; <ввод элемента>;

удаление – <удаление элемента>; ТОР:= ТОР – 1;

Пример 6.4. В стек (рис. 6.4) поступило 4 элемента el1, el2, el3, el4.

1. Записать представление такого стека в виде массива NAME.

2. Вставить элемент el5.

3. Удалить элемент el4 (из исходного массива).

 
 

Решение показано соответственно в табл. 6.8, 6.9, 6.10. Изменения можно наблюдать по указателю вершины стека – ТОР.
 

 

 

Рис. 6.4

Очередь

Рассмотрим работу с очередью. Здесь ввод производится в один конец очереди (начало очереди), а вывод – из другого (конец очереди). В таблице для очереди используются указатели: BACK – конец очереди, FORWARD – начало очереди.

Пример 6.5. Очередь в текущий момент состоит из 5 элементов (рис.6.5); первые 9 элементов отсутствуют.

 
 
1. Записать представление очереди в виде массива NAME. 2.Вставить элемент el6. 3.Удалить элемент el1 (из исходной очереди).  
 
 

 


Рис. 6.5

 

4. Задан стек. Произвести ввод и удаление элементов (табл. 6.15).

 

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

 

Таблица 6.11

Индекс NAME
--- ... ---
10 BACK 14 FORWARD EL1 EL2 EL3 EL4 EL5

 

Таблица 6.12

 

Индекс NAME
--- … ---
10 BACK 15 FORWARD EL1 EL2 EL3 EL4 EL5 EL6

 

Таблица 6.13

 

Индекс NAME
--- ... ---
11 BACK 14 FORWARD   EL2 EL3 EL4 EL5  

 

Задания для самостоятельной работы

В первых трёх заданиях список состоит из семи элементов; количество элементов стека определяется указателем TOP.

 
 
Во всех заданиях записать процедуры ВСТАВИТЬ и УДАЛИТЬ, исходя из фактических (конкретных) значений параметров процедуры. 1. Задан односвязный список. Вставить указанный элемент, а затем удалить указанный элемент (табл. 6.14). 2. Задан двусвязный список. Выполнить задания, аналогичные заданию 1. 3. Задан кольцевой список. Выполнить задания, аналогичные заданию 1. 4. Задан стек. Ввести и затем удалить указанный элемент (табл. 6.15).  


Таблица 6.14

Ins Del
  El34 El56 El23 El12 El45 El34 El7 El5 El6 El4 El2 El3

 

Таблица 6.15

 

K (TOP)
   

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...