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

В некоторых случаях возникает необходимость в качестве значения указателя принять «пустую» ссылку, которая не связывает с указателем никакого объекта. Такое значение в Паскале задается служебным словом 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 часов.

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

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, 4, 5, 6, 7