Методические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "




НазваниеМетодические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "
страница9/19
Дата публикации28.09.2013
Размер1.39 Mb.
ТипМетодические указания
vbibl.ru > Информатика > Методические указания
1   ...   5   6   7   8   9   10   11   12   ...   19
^


Рисунок 8   Процедура исключения элемента из упорядоченного


списка

Пример

Написать программу, выполняющую следующую операцию обработки односвязного списка: поменять местами первый и предпоследний элементы списка (программа приведена в приложении Б).
В общем случае для списка, состоящего из шести элементов,



результат обмена будет выглядеть так:

Особые случаи:

  1. если список пуст (Psp=nil), или состоит из одного элемента (Psp^.ukz=nil), или из двух элементов (Psp^.ukz^.ukz=nil), то поставленная задача не может быть выполнена;

2 если список состоит из трех элементов (Psp^.ukz^.ukz^.ukz=nil ), то

нужно поменять местами первый и второй элементы, то есть элементы, стоящие рядом.


Стек



Стек – линейная, динамически изменяющаяся структура данных, предназначенная для того, чтобы добавлять элементы ко множеству и удалять их из него. Стек может удлиняться, укорачиваться и на время становиться пустым.

Над стеком определены следующие операции:

  • занесение нового элемента;

  • выборка и удаление злемента.


Примечание: " выборка и удаление" – это одна операция.
Выборка элемента из стека и занесение в него нового элемента выполняются с одного и того же конца, называемого вершиной стека. Принцип выполнения - LIFO: ("последним пришел – первым обслуживаешься"). При работе со стеком понятие ключа записи не используется, имеет значение только порядок занесения элемента в структуру (поэтому операция поиска для стека не определена).

Стеки используются обычно не для представления исходных данных, а при реализации различных алгоритмов, например, при разработке компиляторов и ОС.
Современные системы программирования позволяют отобразить стек в динамически распределяемой области памяти.

Пусть, например, в стек последовательно поступают такие элементы: 5, 8, 3, 2. Получим следующее состояние стека:


Процедуры работы со стеком очень просты.
На рис. 9 приведена процедура ^ ZSTEK, реализующая занесение элемента в стек.

Формальные параметры процедуры:

PST – указатель на вершину стека (указатель стека);

VKL – указатель на включаемый элемент (элемент уже подготовлен).

Procedure ZSTEK (Var PST, VKL: U);

Begin

VKL^.Ukz:=PST;
PST:=VKL

End;
^

Рисунок 9   Процедура занесения элемента в стек



На рис. 10 приведена процедура VSTEK, реализующая выборку и удаление элемента из стека.
Формальные параметры процедуры:

^ PST – указатель стека;

ELEM – возвращает информационную часть удаляемого элемента (если стек пуст, то из процедуры возвращается ELEM =0 ).
Например, если перед удалением элемента состояние стека было таким:

т
о после удаления содержимое стека будет иметь вид:





(выполнилась выборка и удаление элемента 2).

Procedure VSTEK (Var PST: U; Var ELEM:integer);

Var P: U;

Begin

If PST<>nil Then

Begin

P:=PST;

ELEM:=PST^.Inf;

PST:=PST^.Ukz;

Dispose(P);

End

Else

ELEM:=0;

End;
1   ...   5   6   7   8   9   10   11   12   ...   19

Похожие:

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconФизика методические указания к лабораторным работам 10, 31
Козлов В. А., Курушин А. Д., Серов Е. А. Физика. Методические указания к лабораторным работам 10, 31 // Под общ ред доц. С. Г. Стоюхина....

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания и задания к лабораторным работам по курсам “
Дискретные структуры“, “Теория алгоритмов и вычислительных процессов“ (для студентов специальностей 050102 “Программное обеспечение...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным наборам предназначены для студентов,...
Металлургическая гидроаппаратура: Методические указания к лабораторным работам / Санкт-Петербургский государственный горный институт...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по дисциплине «Автоматизация...
Сапр простейшей структуры на основе расчета и анализа критериев эффективности с использованием имитационных моделей

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по курсу “
В прологе предусматриваются основные арифметические операции +, -, /, ×, mod, div. Чтобы заставить систему выполнить присваивание...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по дисциплине «Программирование»
Тема: Разработка классов, создание конструкторов и деструкторов. Использование статических членов класса

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconУчебное пособие к лабораторным работам
Автоматизированные информационно-управляющие системы: учебное пособие к лабораторным работам / Л. С. Казаринов, Т. А. Барбасова,...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconКонтрольные задания по курсу «Экономико-математическое моделирование»...
Контрольные задания по курсу «Экономико-математическое моделирование» и методические указания к их выполнению

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconКонтрольные задания по курсу «Экономико-математическое моделирование»...
Контрольные задания по курсу «Экономико-математическое моделирование» и методические указания к их выполнению

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания и контрольные задания к выполнению контрольных...
В методических указаниях приведены программа изучения курса, контрольные вопросы, контрольные задания и методические указания по...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница