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

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

 

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

 

Списки

 

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

В односвязном списке каждый элемент, кроме последнего, содержит ссылку на следующий элемент в списке, т.е. у каждого элемента есть два поля: имя и указатель (рис. 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)

 

Поделиться:

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