Линейные списки. Стек. Дек. Очередь
Переменные ссылочного типа (указатели) вводятся в употребление обычным путем с помощью их описания в разделе переменных, а их тип, указывающий на тип создаваемых в программе соответствующих динамических величин, тоже определяется либо путем задания типа в описании переменных, либо путем указания имени ранее описанного типа.
Значением указателя является адрес ячейки, начиная с которой будет размещена в памяти соответствующая динамическая величина.
![]()
На этой схеме р. - имя указателя; звездочкой изображено значение указателя, а стрелка отражает тот факт, что значением указателя является адрес объекта (ссылка на объект), посредством которого объект и доступен в программе.
В
некоторых
случаях возникает
необходимость
в качестве
значения указателя
принять «пустую»
ссылку, которая
не связывает
с указателем
никакого объекта.
Такое значение
в Паскале задается
служебным
словом nil и принадлежит
любому ссылочному
типу. Результаты
выполнения
оператора
p:=nil можно изобразить
следующим
образом:
Процедура new(i) выполняет две функции:
1) резервирует место в памяти для размещения динамического объекта соответствующего типа с именем i;
2) указателю i присваивает адрес динамического объекта i.
Однако, узнать адрес динамической переменной с помощью процедуры writeln (i) нельзя.
Динамические объекты размещаются по типу стека в специальной области памяти — так называемой «куче» свободной от программ и статических переменных. Символ ^ после имени указателя означает, что речь идет не о значении ссылочной переменной, а о значении того динамического объекта, на который указывает эта ссылочная переменная.
Имя ссылочной переменной с последующим символом ^ называют «переменной с указателем». Именно она синтаксически выполняет роль динамической переменной и может быть использована в любых конструкциях языка, где допустимо использование переменных того типа, что и тип динамической переменной.
Если в процессе выполнения программы некоторый динамический объект р^, созданный в результате выполнения оператора new(p), становится ненужным, то его можно уничтожить (очистить выделенное ему место в памяти) с помощью стандартной процедуры dispose(p). В результате выполнения оператора вида dispose(p) динамический объект, на который указывает ссылочная переменная р, прекращает свое существование, занимаемое им место в памяти становится свободным, а значение указателя р становится неопределенным (но не равным nil).
Если до вызова процедуры dispose(p) имел пустое значение nil, то это приведет к «зависанию» программы.
Если же до вызова этой процедуры указатель р не был определен, то это может привести к выходу из строя операционной системы.
Значение одного указателя можно присвоить другому указателю того же типа. Можно также указатели одинакового типа сравнивать друг с другом, используя отношения «=» или «о».
Стандартные процедуры new и dispose позволяют динамически порождать программные объекты и уничтожать их, что дает возможность использовать память машины более эффективно.
Связанные списки данных. Несмотря на богатый набор типов данных в Паскале, он не исчерпывает всего практически необходимого для разработки многих классов программ. В частности, из разнообразных связанных структур данных в языке стандартизированы массивы и файлы, а кроме них могут потребоваться и схожие с ними, но иные структуры. Для них характерны, в частности, следующие признаки:
а) неопределенное заранее число элементов;
б) необходимость хранения в оперативной памяти.
Средство для реализации таких структур дает аппарат динамических переменных. Простейшей из обсуждаемых структур является однонаправленный список. Он строится подобно очереди на прием к врачу: пациенты сидят на любых свободных местах, но каждый из них знает, за кем он в очереди (т.е. данные размещаются на свободных местах в памяти, но каждый элемент содержит ссылку на предыдущий или следующий элемент). Поскольку количество пациентов заранее не очевидно, структура является динамической.
Другая подобная структура - стек. Его моделью может служить трубка с запаянным концом, в которую вкатывают шарики. При этом реализуется принцип «последним вошел - первым вышел». Возможное количество элементов в стеке не фиксировано.
Остановимся на примере стека и покажем его программную реализацию. Технически при этом следует решить ряд задач, из которых наиболее специфическими являются
а) связывание последующих компонентов стека;
б) смещение ссылок при каждом движении по стеку.
И![]()
з-за
необходимости
хранить не
только значение
каждого элемента,
но и соответствующую
ссылку на последующий
элемент, каждый
из элементов
будем хранить
в виде двухполевой
записи, в которой
первое поле
- значение
элемента, а
второе - ссылка
на следующий
элемент. Схематически
эту структуру
можно описать
следующим
образом
(элементу, который пришел первым, ссылаться не на что, о чем свидетельствует «пустая ссылка» nil).
Ниже приведены примеры создания и уничтожения списков, добавление и удаление элементов из списка на Delphi. Рассмотрены только для однонаправленного и двунаправленного списков для остальных даны примеры в демонстрационной программе.
Type
List = ^Spisok; - Однонаправленный
Spisok = record
Info: Integer; - Информационное поле
Next: List; - Ссылка на следующий элемент
end;
ListTwo = ^SpisokTwo; - Двунаправленный
SpisokTwo = record
Info: Integer; - Информационное поле
Next: ListTwo; - Ссылка на следующий элемент
Prev: ListTwo; - Ссылка на предыдущий элемент
end;
Создание списка
procedure CreateLists; - процедура создания списка
begin
X := Random(101); Определяем значение первого элемента
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;
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;
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 часов.
Задачи факультатива:
Ввести понятие линейного списка, однонаправленного и двунаправленного списка, циклического списка, стека, дека и очереди;
Сформировать познавательный интерес у учащихся к информатике;
Развить у учащихся творческие способности.
Цель первого урока – дать учащимся на качественном уровне необходимый подготовительный материал, который включает в себя:
Определение линейного списка.
Операции со списками.
Виды списков.
Связанное распределение.
Динамические переменные.
На 2 – 6 уроках учащиеся знакомятся со списками более глубже. Седьмой урок итоговый. Учащимся предлагается тестовая программа, в которой они отвечают на вопросы и оценивают результаты полученных знаний. В целом же факультатив рассчитан на семь двух часовых занятий.
Общая структура факультатива такова:
|
№ урока |
Тема |
Кол-во часов |
| №1. | Списки | 2 |
| №2. | Однонаправленный и двунаправленный список | 2 |
| №3. | Циклический список | 2 |
| №4. | Очередь | 2 |
| №5. | Стек | 2 |
| №6. | Дек | 2 |
| №7. | Тест | 2 |
Конспекты уроков
Тема: «Очередь»
Цели:
Раскрыть понятие линейного списка «Очередь».
Научиться использовать «Очередь» на практике при решении задач.
Сформировать у учащихся познавательный интерес к информатике.
| № |
Этап урока |
Время (мин.) |
| 1. | Организационный момент | 2 |
| 2. | Подготовка к лабораторной работе | 10 |
| 3. | Выполнение лабораторной работы | 20 |
| 4. | Закрепление | 8 |
Лабораторная работа №4 по теме «Очередь».
Нажмите кнопку "Теория" для очереди.
Внимательно изучите теоретический материал.
Нажмите кнопку "Обновить" для формирования списков.
Кнопки "<< и >>" служат для перемещения курсора по очереди.
а) Переместитесь вправо до 3 элемента;
б) Переместитесь влево (см. коментарии);
Кнопка "Добавить" служит для добавления элемента в очередь.
а) Добавьте 1, 4, 5-м элементами число 99;
б) Добавьте последним число 999;
Кнопка "Удалить" служит для удаления элемента из очереди.
Удалите 1, 2, 3 элементы;
На листе формата А4, опишите ход проделанной работы.
Ответьте на поставленные вопросы:
Как удаляется и добавляется элементы в очереди?
В чем различие и сходство очереди и однонаправленного списка?
Что называется головой и хвостом очереди?
Как располагаются элементы в очереди?
________________________________________________________________
Задачи для самостоятельного решения:
Пусть уже построена очередь Q, содержащая целые числа. Вычислить сумму и произведение элементов, находящихся в очереди.
Пусть уже построена очередь Q, содержащая целые числа. Сформировать новую очередь P, состоящую из элементов очереди Q, кратных числу 3.
Пусть уже построена очередь Q, содержащая целые числа. Вычислить количество простых чисел, находящихся в очереди.
|
Учитель |
Ученик |
ПК |
Тетрадь |
|
2 этап - Подготовка к лабораторной работе |
|||
| Запускаем демонстрационную программу. Нажмите кнопку теория. Перед вами появилось окно с теоретическим материалом. Внимательно ознакомьтесь с новым материалом. Обратите внимание на примеры создания очереди и получения элемента из очереди. Провести аналогию между очередью и однонаправленным списком. | Знакомится с новым материалом. | Теоретический материал по теме «очередь». |
Определение «очереди». Порядок расположения данных. Примеры создания очереди и получения элемента из очереди. |
|
3 этап - Выполнение лабораторной работы |
|||
|
Открываем лабораторную работу №4. Внимательно читаем задание и начинаем выполнять. |
Выполняет лабораторную работу. |
Лабораторная
работа |
|
| После выполнения заданий ответьте на поставленные вопросы. | Отвечает на вопросы. | Ответы на вопросы. | |
| Попробуйте выполнить практические задания. | Решает задачи. | Delphi или Pascal. | Листинг задачи. |
|
4 этап - Закрепление лабораторной работы |
|||
| Итак, давайте подведем итоги сегодняшней работы. | |||
| Что называется очередью? | Очередь — линейный список, в котором все включения производятся на одном конце списка, а все исключения на другом конце. | ||
| Как располагаются данные в очереди? | Очередь — тип данных, при котором новые данные располагаются следом за существующим в порядке поступления; | ||
| Какие данные в очереди обрабатываются первыми? | Данные поступившие первыми обрабатываются первыми. | ||
| Что такое «голова», «хвост» очереди? | Элемент, добавляемый в очередь, оказывается в её хвосте. Элемент, удаляемый из очереди, находится в её голове. | ||
| В чем схожи очередь и однонаправленный список? |
Очередь, по сути, однонаправленный список, только добавление и исключение элементов происходит на концах списка. |
||
Тема: «Стек»
Цели:
Раскрыть понятие линейного списка «Стек».
Научиться использовать «Стек» на практике при решении задач.
Сформировать у учащихся познавательный интерес к информатике.
| № |
Этап урока |
Время (мин.) |
| 1. | Организационный момент | 2 |
| 2. | Подготовка к лабораторной работе | 10 |
| 3. | Выполнение лабораторной работы | 20 |
| 4. | Закрепление | 8 |
Лабораторная работа №5 по теме «Стек».
Нажмите кнопку "Теория" для стека.
Внимательно изучите теоретический материал.
Нажмите кнопку "Обновить" для формирования списков.
Кнопки "<< и >>" служат для перемещения курсора в стеке.
а) Переместитесь вправо до 4 элемента;
б) Переместитесь влево (см. комментарии);
Кнопка "Добавить" служит для добавления элемента в стек.
Добавьте 1, 3, 5 элементами число 22;
Кнопка "Удалить" служит для удаления элемента из стека.
Удалите 1, 3, 5, последний элементы;
На листе формата А4, опишите ход проделанной работы.
Ответьте на поставленные вопросы:
Как удаляется и добавляется элементы в стек?
Приведи примеры стека на практике?
________________________________________________________________
Задачи для самостоятельного решения:
Предположим, что уже построен стек, элементами которого являются целые числа. Написать программу, которая находит сумму элементов, находящихся в стеке.
Предположим, что уже построен стек, элементами которого являются целые числа. Написать программу, которая добавляет в конец стека S элемент, находящийся в его вершине.
Предположим, что уже построен стек, элементами которого являются целые числа. Написать программу, которая удаляет из стека все элементы, кратные 4 (использовать для промежуточного хранения элементов стека однонаправленный список с заглавным звеном).
|
Учитель |
Ученик |
ПК |
Тетрадь |
|
2 этап - Подготовка к лабораторной работе |
|||
| Запускаем демонстрационную программу. Нажмите кнопку теория. Перед вами появилось окно с теоретическим материалом. Внимательно ознакомьтесь с новым материалом. Обратите внимание на примеры создания стека и получения элемента из стека. Провести аналогию между очередью и стеком. | Знакомится с новым материалом. | Теоретический материал по теме «стек». |
Определение «стека». Порядок расположения данных. Примеры создания стека и получения элемента из стека. |
|
3 этап - Выполнение лабораторной работы |
|||
|
Открываем лабораторную работу №5. Внимательно читаем задание и начинаем выполнять. |
Выполняет лабораторную работу. |
Лабораторная
работа |
|
| После выполнения заданий ответьте на поставленные вопросы. | Отвечает на вопросы. | Ответы на вопросы. | |
| Попробуйте выполнить практические задания. | Решает задачи. | Delphi или Pascal. | Листинг задачи. |
|
4 этап - Закрепление лабораторной работы |
|||
| Итак, давайте подведем итоги сегодняшней работы. | |||
| Что называется стеком? |
Стек — линейный список, в котором все включения и исключения делаются в одном конце списка. |
||
| Как располагаются данные в стеке? | Стек, организован таким образом, что последний вводимый в область памяти элемент размещается на вершине списка. | ||
| Различия между очередью и стеком? |
Из стека мы всегда исключаем «младший» элемент из имеющихся в списке, т. е. тот, который был включен позже других. Для очереди справедливо в точности противоположное правило: исключается всегда самый "старший" элемент; узлы покидают список в том порядке, в котором они в него вошли. |
||
Тема: «Тест»
Цели:
Закрепить полученные знания по пройденному курсу.
Выяснить результативность полученных знаний с помощью теста.
Сформировать у учащихся познавательный интерес к информатике.
| № |
Этап урока |
Время (мин.) |
| 1. | Организационный момент | 2 |
| 2. | Подготовка к тесту | 10 |
| 3. | Тест | 20 |
| 4. | Подведение итогов | 8 |
Лабораторная работа №7 по теме «Тест».
Повторите весь теоретический материал.
Поработайте с демонстрационной программой.
Запустите тест (сервистест или Ctrl + T).
Ответьте на поставленные вопросы теста.
Результаты теста сообщить преподавателю.
|
Учитель |
Ученик |
ПК |
Тетрадь |
|
2 этап - Подготовка к тесту |
|||
| Запускаем демонстрационную программу. Внимательно просмотрите теоретический материал по пройденному курсу. Обратите внимание: на определения списков, на то как добавляется и исключаются элементы из списков, на общее и различия списков. | Повторяет пройденный материал. | Теоретический материал по пройденному курсу. |
Определения списков. Включение и исключение элементов из списков. Общее и различия между списками. |
|
3 этап – Тест |
|||
|
Запускаем тест. (Меню: СервисТест). Перед вами появилось окно «Тест». В верхнем левом поле предлагается вопрос, ниже под полем предлагаются на выбор несколько вариантов ответов. Правой клавишей мыши щелкаете на правильный по вашему мнению ответ. После выбора ответа, кнопка «Далее» становится активной, нажимаете ее. После нажатия на кнопку «Далее», появится следующий вопрос. Продолжаете далее, пока не появится оценка за тест. |
Тестируется. |
Тест. | |
| Результат сообщите учителю. | Оценка за тест. | ||
| Если результат оказывается неудовлетворительный, ученику предлагается повторить пройденный материал, и проверить свои знания на следующем уроке. После проведения теста, вызов теста блокируется. | |||
|
4 этап – Подведение итогов |
|||
|
Итак, мы с вами изучили линейные списки. Подведем итоги. Вы ознакомились с такими списками как: однонаправленный и двунаправленный списки, стек, дек, очередь и циклический список. Вы узнали, что такое связанное распределение и динамические информационные структуры. Научились использовать полученные знания на практике при решении задач. При помощи теста оценили результаты полученных знаний. |
|||
| Если кого, что-то заинтересовало или кто-то полностью не усвоил пройденный материал, то он может подойти к учителю и получить интересующие его сведения. | |||
| Сообщаются оценки за тест, и за факультатив в общем. | |||
2.2 Разработка программного средства по теме «Динамические типы данных»
После загрузки демонстрационной программы перед вами появится вот такое окно.

Это главная форма демонстрационной программы. Для формирования списков нажмите кнопку «Обновить».

Теперь списки сформированы и готовы к работе. Списки содержат целые положительные числа. Указатели указывают на начало списка. С помощью кнопок «<<» «>>» можно перемещать указатель по списку. С помощью кнопки «Добавить» вы можете добавить элемент в список. При нажатии на кнопку «Добавить» всплывает окно «Добавление нового элемента», в котором вы указываете какой элемент хотите добавить и нажимаете кнопку «Ok».

При нажатии на кнопку «Удалить» удаляется элемент из списка. В однонаправленном, двунаправленном и циклическом списках удаляется тот элемент, на который указывает указатель. В очереди и стеке удаляется первый. При удалении элемента из дека появляется окно «Удаление элемента», в котором вам предлагается выбрать откуда удалять элемент из начала или с конца.
При нажатии на кнопку теория (для очереди) открывается окно «Очередь», котором изложена теория и даны примеры.

Аналогично для остальных списков.
Для более удобной работы с учащимися в программе предусмотрены лабораторные работы (Ctrl + L или Сервис Лабораторные работы). Если вы выберете все то откроется окно «Лабораторные работы», в котором даны сразу все работы и задания. Перед вами 4 лабораторная работа на список «Очередь».

Если вы будете выбирать каждую в отдельности то они будут отображаться в комментариях на главной форме.
Помощь можно вызвать (СправкаПомощь или F1).

После проведения всех лабораторных работ учащимся предлагается ответить на вопросы теста, за который они получают оценку. При запуске теста (СервисТест или Ctrl + T) открывается окно «Тест».

Сверху вопрос, ниже варианты ответов. После выбора ответа кнопка «Далее» становится активной, нажав на нее появляется следующий вопрос. После выполнения теста выдается оценка, если неудовлетворительная то открывается окно «Лабораторные работы».
Примечание: после того как тест запустился вызов теста становится неактивным т.е. второй раз учащийся запустить тест не сможет.
Закрыть программу можно нажатием на кнопку «Закрыть» или F10.
Заключение
В квалификационной работе мы попытались раскрыть более полно и наглядно понятие линейного списка, однонаправленного и двунаправленного списков, стека, дека и очереди. Сформировать и закрепить познавательный интерес к данной теме у учащихся. Выявлять и развивать творческие способности в использовании полученного навыка при программировании.
Главной целью нашей работы было знакомство с теоретическим материалом, касающийся информационных структур и разработка программного средства «Динамические типы данных».
Достижением этой цели и согласно поставленной гипотезы определялись следующие задачи:
Изучить литературу по теме динамические информационные структуры, педагогическую и методическую по теме исследования;
Проанализировать виды динамических информационных структур;
Разработать факультатив по теме исследования;
Разработать программный продукт по теме исследования.
Все поставленные цели и задачи реализованы в данной квалификационной работе. Изучено понятие линейного списка, всевозможные операции с этим списком, определяются основные термины и понятия. Кроме того, рассматривается более конкретно и полно каждый список в отдельности и показывается целесообразность использования списков в тех или иных случаях. Для каждого списка приводятся жизненные примеры для простоты восприятия. Дается понятие связанного распределения и кратко изучается понятие динамических информационной структуры, которая позволяют применить полученные знания при программировании. Также рассматривается преимущество и недостатки двух форм представления информации: связанное и последовательное. Далее следует методическая часть, в которой представлена расчасовка факультатива, его структура, и поставлены цели и задачи факультатива. Приводится для примера три конспекта уроков по теме «Очередь», «Стек» и «Тест». И последнее это руководство пользователя, в котором дается описания работы с демонстрационной программой.
Литература
Айен Синклер «Большой толковый словарь компьютерных терминов», М.: 1998 г.
Архангельский А. Я. «Программирование в Delphi 4», М.: 1999 г.
Архангельский А. Я. «Программирование в Delphi 5», М.: 2000 г.
Вирт Н. «Алгоритмы и структуры данных», Москва Изд. Мир,
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.Нужна помощь в написании работы?Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.