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

end

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

begin

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

PointerEndList := PointerEndList ^.Next;

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

PointerEndList ^.Info := X;

PointerEndList ^.Next := nil;

end;

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 этап - Закрепление лабораторной работы |

|Итак, давайте подведем итоги| | | |

|сегодняшней работы. | | | |

|Что называется очередью? |Очередь — | | |

| |линейный список,| | |

| |в котором все | | |

| |включения | | |

| |производятся на | | |

| |одном конце | | |

| |списка, а все | | |

| |исключения на | | |

| |другом конце. | | |

|Как располагаются данные в |Очередь — тип | | |

|очереди? |данных, при | | |

| |котором новые | | |

| |данные | | |

| |располагаются | | |

| |следом за | | |

| |существующим в | | |

| |порядке | | |

| |поступления; | | |

|Какие данные в очереди |Данные | | |

|обрабатываются первыми? |поступившие | | |

| |первыми | | |

| |обрабатываются | | |

| |первыми. | | |

|Что такое «голова», «хвост» |Элемент, | | |

|очереди? |добавляемый в | | |

| |очередь, | | |

| |оказывается в её| | |

| |хвосте. Элемент,| | |

| |удаляемый из | | |

| |очереди, | | |

| |находится в её | | |

| |голове. | | |

|В чем схожи очередь и |Очередь, по | | |

|однонаправленный список? |сути, | | |

| |однонаправленный| | |

| |список, только | | |

| |добавление и | | |

| |исключение | | |

| |элементов | | |

| |происходит на | | |

| |концах списка. | | |

Тема: «Стек»

Цели:

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

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

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

|№ |Этап урока |Время (мин.) |

|1. |Организационный момент |2 |

|2. |Подготовка к лабораторной работе |10 |

|3. |Выполнение лабораторной работы |20 |

|4. |Закрепление |8 |

Лабораторная работа №5 по теме «Стек».

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

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

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

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

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

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

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

Добавьте 1, 3, 5 элементами число 22;

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

Удалите 1, 3, 5, последний элементы;

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

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

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

2) Приведи примеры стека на практике?

________________________________________________________________

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

1) Предположим, что уже построен стек, элементами которого являются целые

числа. Написать программу, которая находит сумму элементов, находящихся

в стеке.

2) Предположим, что уже построен стек, элементами которого являются целые

числа. Написать программу, которая добавляет в конец стека S элемент,

находящийся в его вершине.

3) Предположим, что уже построен стек, элементами которого являются целые

числа. Написать программу, которая удаляет из стека все элементы,

кратные 4 (использовать для промежуточного хранения элементов стека

однонаправленный список с заглавным звеном).

|Учитель |Ученик |ПК |Тетрадь |

|2 этап - Подготовка к лабораторной работе |

|Запускаем |Знакомится с |Теоретически|Определение |

|демонстрационную |новым |й материал |«стека». |

|программу. Нажмите |материалом. |по теме |Порядок |

|кнопку теория. Перед | |«стек». |расположения |

|вами появилось окно с | | |данных. |

|теоретическим | | |Примеры |

|материалом. Внимательно | | |создания стека |

|ознакомьтесь с новым | | |и получения |

|материалом. Обратите | | |элемента из |

|внимание на примеры | | |стека. |

|создания стека и | | | |

|получения элемента из | | | |

|стека. Провести аналогию| | | |

|между очередью и стеком.| | | |

|3 этап - Выполнение лабораторной работы |

|Открываем лабораторную |Выполняет |Лабораторная| |

|работу №5. |лабораторную |работа | |

|Внимательно читаем |работу. |№5. | |

|задание и начинаем | | | |

|выполнять. | | | |

|После выполнения заданий|Отвечает на | |Ответы на |

|ответьте на поставленные|вопросы. | |вопросы. |

|вопросы. | | | |

|Попробуйте выполнить |Решает задачи. |Delphi или |Листинг задачи.|

|практические задания. | |Pascal. | |

|4 этап - Закрепление лабораторной работы |

|Итак, давайте подведем | | | |

|итоги сегодняшней | | | |

|работы. | | | |

|Что называется стеком? |Стек — линейный| | |

| |список, в | | |

| |котором все | | |

| |включения и | | |

| |исключения | | |

| |делаются в | | |

| |одном конце | | |

| |списка. | | |

|Как располагаются данные|Стек, | | |

|в стеке? |организован | | |

| |таким образом, | | |

| |что последний | | |

| |вводимый в | | |

| |область памяти | | |

| |элемент | | |

| |размещается на | | |

| |вершине списка.| | |

|Различия между очередью |Из стека мы | | |

|и стеком? |всегда | | |

| |исключаем | | |

| |«младший» | | |

| |элемент из | | |

| |имеющихся в | | |

| |списке, т. е. | | |

| |тот, который | | |

| |был включен | | |

| |позже других. | | |

| |Для очереди | | |

| |справедливо в | | |

| |точности | | |

| |противоположное| | |

| |правило: | | |

| |исключается | | |

| |всегда самый | | |

| |"старший" | | |

| |элемент; узлы | | |

| |покидают список| | |

| |в том | | |

| |порядке, в | | |

| |котором они в | | |

| |него вошли. | | |

Тема: «Тест»

Цели:

1. Закрепить полученные знания по пройденному курсу.

2. Выяснить результативность полученных знаний с помощью теста.

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

|№ |Этап урока |Время (мин.) |

|1. |Организационный момент |2 |

|2. |Подготовка к тесту |10 |

|3. |Тест |20 |

Страницы: 1, 2, 3, 4, 5, 6, 7