Быстрый поиск

Реферат: Линейные списки. Стек. Дек. Очередь

Uk := nil; Указателям присваиваем nil.

q := nil;

AddToList (X, Uk); Добавляем элемент Х в список.

q := Uk; Формируем указатель на начало списка.

for i := 1 to 9 do Добавляем оставшиеся элементы в список.

begin

X := Random(101);

AddToList (X, q);

end;

ListBegin := Uk; Определяем указатель списка.

end;

Уничтожение списка

procedure DestroyList (PointerBegin: List); Процедура уничтожения списка

(PointerBegin – указатель на начало списка).

begin

while PointerBegin <> nil do Если указатель не nil, то

begin

q := PointerBegin;

PointerBegin := PointerBegin ^.Next; Ссылка на следующий.

if q <> nil then Dispose(q); Уничтожение.

end;

Добавление элемента в список

procedure AddToList(X: Integer; var PointerEndList: List);

Добавить элемент в конец списка

(PointerEndList - указатель на последний элеменBЀ списка)

begin

if PointerEndList = nil then

Если первый элемент еще не существует или список пуст, то

begin

New(PointerEndList); Создаем новую переменную

PointerEndList ^.Info := X; Инф. Части присваиваем элем. Х

PointerEndList ^.Next := nil; Ссылке на следующий - nil

end

else иначе добавляем в список

begin

New(PointerEndList ^.Next); Создаем новую ссылку

PointerEndList := PointerEndList ^.Next;

Указателю присвоить ссылку на след. элемент

PointerEndList ^.Info := X;

PointerEndList ^.Next := nil;

end;

Удаление элемента из списка.

procedure DeleteFromList(Position: Integer);

Удаляет элемент под номером Position

begin

q := ListBegin; Присваивается ссылка на первый элемент

if q <> nil then Если список не пуст, то

begin

if Position = 0 then Если позиция = 0, то удаляем первый элемент

begin

ListBegin := q^. Next;

if q <> nil then Dispose(q);

end

else

begin

i := 0;

while (i < Position - 1) and (q <> nil) do

Ищем элемент после которого нужно удалить

begin

q := q^. Next;

Inc(i);

end;

r := q^. Next;

if r <> nil then Если удаляемый элемент существует, то удаляем его

begin

q^. Next := r^. Next;

if r <> nil then Dispose(r);

end

end;

end

end;

Глава 2. Разработка факультативного курса «Динамические типы данных»

2.1 Методические рекомендации по введению факультативного курса в школе

В системе школьных факультативов необходимо изучение информатики с большей полнотой. Это требует в свою очередь особенно тщательного отбора материала который может быть хорошо усвоен учащимися за ограниченное количество часов.

Разработанный нами факультатив рассчитан на 14 часов.

Задачи факультатива:

1) Ввести понятие линейного списка, однонаправленного и двунаправленного списка, циклического списка, стека, дека и очереди;

2) Сформировать познавательный интерес у учащихся к информатике;

3) Развить у учащихся творческие способности.

Цель первого урока – дать учащимся на качественном уровне необходимый подготовительный материал, который включает в себя:

1) Определение линейного списка.

2) Операции со списками.

3) Виды списков.

4) Связанное распределение.

5) Динамические переменные.

На 2 – 6 уроках учащиеся знакомятся со списками более глубже. Седьмой урок итоговый. Учащимся предлагается тестовая программа, в которой они отвечают на вопросы и оценивают результаты полученных знаний. В целом же факультатив рассчитан на семь двух часовых занятий.

Общая структура факультатива такова:

№ урока	Тема	Кол-во часов
№1.	Списки	2
№2.	Однонаправленный и двунаправленный список	2
№3.	Циклический список	2
№4.	Очередь	2
№5.	Стек	2
№6.	Дек	2
№7.	Тест	2

Конспекты уроков

Тема: «Очередь»

Цели:

1. Раскрыть понятие линейного списка «Очередь».

2. Научиться использовать «Очередь» на практике при решении задач.

3. Сформировать у учащихся познавательный интерес к информатике.

№	Этап урока	Время (мин.)
1.	Организационный момент	2
2.	Подготовка к лабораторной работе	10
3.	Выполнение лабораторной работы	20
4.	Закрепление	8

Лабораторная работа №4 по теме «Очередь».

1. Нажмите кнопку "Теория" для очереди.

Внимательно изучите теоретический материал.

2. Нажмите кнопку "Обновить" для формирования списков.

Кнопки "<< и >>" служат для перемещения курсора по очереди.

а) Переместитесь вправо до 3 элемента;

б) Переместитесь влево (см. коментарии);

Кнопка "Добавить" служит для добавления элемента в очередь.

а) Добавьте 1, 4, 5-м элементами число 99;

б) Добавьте последним число 999;

Кнопка "Удалить" служит для удаления элемента из очереди.

Удалите 1, 2, 3 элементы;

3. На листе формата А4, опишите ход проделанной работы.

Ответьте на поставленные вопросы:

1) Как удаляется и добавляется элементы в очереди?

2) В чем различие и сходство очереди и однонаправленного списка?

3) Что называется головой и хвостом очереди?

4) Как располагаются элементы в очереди?

________________________________________________________________

Задачи для самостоятельного решения:

1) Пусть уже построена очередь Q, содержащая целые числа. Вычислить сумму и произведение элементов, находящихся в очереди.

2) Пусть уже построена очередь Q, содержащая целые числа. Сформировать новую очередь P, состоящую из элементов очереди Q, кратных числу 3.

3) Пусть уже построена очередь Q, содержащая целые числа. Вычислить количество простых чисел, находящихся в очереди.

Учитель	Ученик	ПК	Тетрадь
2 этап - Подготовка к лабораторной работе
Запускаем демонстрационную программу. Нажмите кнопку теория. Перед вами появилось окно с теоретическим материалом. Внимательно ознакомьтесь с новым материалом. Обратите внимание на примеры создания очереди и получения элемента из очереди. Провести аналогию между очередью и однонаправленным списком.	Знакомится с новым материалом.	Теоретический материал по теме «очередь».	Определение «очереди». Порядок расположения данных. Примеры создания очереди и получения элемента из очереди.
3 этап - Выполнение лабораторной работы
Открываем лабораторную работу №4. Внимательно читаем задание и начинаем выполнять.	Выполняет лабораторную работу.	Лабораторная работа №4.
После выполнения заданий ответьте на поставленные вопросы.	Отвечает на вопросы.		Ответы на вопросы.
Попробуйте выполнить практические задания.	Решает задачи.	Delphi или Pascal.	Листинг задачи.
4 этап - Закрепление лабораторной работы
Итак, давайте подведем итоги сегодняшней работы.
Что называется очередью?	Очередь — линейный список, в котором все включения производятся на одном конце списка, а все исключения на другом конце.
Как располагаются данные в очереди?	Очередь — тип данных, при котором новые данные располагаются следом за существующим в порядке поступления;
Какие данные в очереди обрабатываются первыми?	Данные поступившие первыми обрабатываются первыми.
Что такое «голова», «хвост» очереди?	Элемент, добавляемый в очередь, оказывается в её хвосте. Элемент, удаляемый из очереди, находится в её голове.
В чем схожи очередь и однонаправленный список?	Очередь, по сути, однонаправленный список, только добавление и исключение элементов происходит на концах списка.