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




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

Методические указания к выполнению работы



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

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

Список – это линейная динамическая структура данных, элементы которой связаны указателями. Каждый элемент списка состоит из двух частей:

INF

UKZ


В ^ INF содержится информация, представляемая одним полем или группой полей, среди которых одно является ключевым. В более сложных случаях в INF может содержаться ссылка на участок памяти, где хранится информация, или на другой список.

Поле ^ UKZ содержит указатель (ссылку) на элемент списка, следующий за данным элементом в логической последовательности, то есть UKZ содержит адрес следующего элемента.

Различают следующие виды списков:

  • односвязные (однонаправленные): каждый элемент содержит указатель на следующий элемент списка (рис.3);

  • двусвязные (двунаправленные): в каждом элементе имеются указатели как на следующий, так и на предыдущий элементы того же списка (рис.4);

  • кольцевые: в последнем элементе списка содержится указатель на первый элемент (рис.5).




Элементы списка – динамические переменные (ДП). Они создаются (то есть им выделяется память) во время выполнения программы, следуя потребностям решаемой задачи. ДП можно так же “уничтожать “ во время выполнения программы (отведенная ранее под переменные память освобождается).

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

Доступ к элементам списка осуществляется через указатель списка.

В приведенных на рисунках списках P, P1, P2, P3 - указатели списков. P, P1, P3 – содержат адреса первых элементов списков, P2 содержит адрес последнего элемента двусвязного списка. Значение UKZ, изображенное косой чертой, является признаком конца списка (пустой указатель).
Связное представление облегчает операции включения и исключения элементов из списка. Также значительно проще выполнить объединение двух списков или разделение списка на два по сравнению с выполнением таких же операций над массивами или таблицами. Это осуществляется простой заменой значений указателей и не требует перемещения данных в памяти.

Списки являются линейными динамическими структурами, так как все элементы списка находятся на одном уровне.

В современных системах программирования реализована возможность динамического распределения памяти. Например, в системе ТурбоПаскаль имеется специальная программа, которая управляет динамически распределяемой областью памяти ("кучей").
В Паскале работа с ДП осуществляется с помощью ссылочных переменных (переменных типа "указатель"):
TYPE

U = ^ZAP;

ZAP = RECORD

INF : integer;

UKZ : U;

END;

VAR

PSP, P : U;
Здесь ^ U – имя ссылочного типа (тип – указатель).

Запись U=^ZAP показывает, что тип – указатель U связан с переменной типа ZAP, определяющей структуру элемента списка. Для простоты в элементе списка представлено только одно информационное поле- INF. Элементы списка будут располагаться в динамической памяти.
Переменные ^ PSP, P – указатели; они связаны с типом ZAP (и только с этим типом). Если необходимы указатели на различные типы данных, то должны быть определены несколько указателей.

Для выделения памяти под динамические переменные используется системная процедура ^ NEW(P). При выполнении этой процедуры под переменную типа ZAP выделяется участок памяти, и его адрес присваивается указателю P (то есть в Р засылается адрес первого байта выделенной памяти).
Обращение к полям записи, адресуемой с помощью указателя ^ Р, осуществляется посредством точечной нотации:

P^.INF – обращение к полю INF;

P^.UKZ – обращение к полю UKZ.
Первый элемент списка можно создать следующей последовательностью операторов:

NEW (PSP);

- выделяется память под переменную типа ZAP, и ее адрес присваивается переменной PSP.
R
EADLN(PSP^.INF); PSP^.UKZ:=Nil;

Здесь ^ PSP – указатель списка.
Системная константа Nil определяет пустой указатель, что означает отсутствие ссылки на другой элемент. Если в поле UKZ не будут занесены некоторый указатель или Nil, то будем иметь неопределенный указатель, использование которого приводит к непредсказуемым последствиям.

Так как переменные-указатели содержат адреса, то для них допустимы только операции сравнения (“=” и “<>”) и оператор присваивания.

При исключении элемента из списка нужно вернуть занимаемую им память в "кучу" с тем, чтобы она снова могла быть использована (например, для создания нового элемента, включаемого в список).

При выполнении системной процедуры DISPOSE(P) область памяти, адресуемая указателем P, освобождается и возвращается в "кучу". При этом указатель P не должен иметь значение Nil или быть неопределенным.
Над списками определены следующие основные операции:

- включение элемента в список,

- поиск элемента по заданному ключу,

- исключение элемента из списка.
Следует помнить, что при выполнении операций над списками не должно происходить физическое перемещение элементов в памяти: должны изменяться только связи между ними.
На рис. 6 приведена процедура создания неупорядоченного списка (процедура связывания элементов в "цепочку" по мере их поступления).
Формальный параметр процедуры:

PSP – указатель списка (выходной параметр).
Рассмотрим пример выполнения процедуры Create_List. Для чисел 5, 3, 4, 2 должен получиться следующий список:



Procedure Create_List (Var PSP:U);

Var Q, {указатель предыдущего элемента списка}

P : U; { указатель текущего элемента списка }

Ch : Char;

Begin

New(Q);

WriteLn('Введите информационное поле элемента');
ReadLn (Q^.Inf);

PSP:=Q; {PSP указатель списка (адрес первого элемента)}

WriteLn('Продолжить ввод? y/n');

Ch:=ReadKey;

While Ch in ['y','Y',’н’,’Н’] do

Begin

New(P);

WriteLn('Введите информационное поле элемента');

ReadLn(P^.Inf);

Q^.Ukz:=P;

Q:=P;

WriteLn('Продолжить ввод? y/n');

Ch:=ReadKey;

End;

Q^.Ukz:=Nil

End;
Рисунок 6   Процедура создания неупорядоченного списка

Э
тапы выполнения процедуры:

New(Q);
ReadLn (Q^.Inf);

PSP:=Q;

Ch:=ReadKey; {Ch='y'}





Первый шаг цикла:

New(P);

ReadLn(P^.Inf);

Q^.Ukz:=P;

Q:=P;

Ch:=ReadKey; {Ch='y'}
Второй шаг цикла:

New(P);

ReadLn(P^.Inf);

Q^.Ukz:=P;

Q:=P;

C
h:=ReadKey; {Ch='y'}

Третий шаг цикла:

New(P);

ReadLn(P^.Inf);

Q^.Ukz:=P;

Q:=P;

C
h:=ReadKey; {Ch<>'y’ – выход из цикла}

Q^.Ukz:=Nil;
Алгоритм построения неупорядоченного списка очень прост. Однако, при поиске записи по заданному ключу нужно рассматривать в таком списке все элементы подряд и, возможно, до конца списка. Чтобы операция поиска была эффективной, следует создавать упорядоченный список - список, в котором элементы упорядочены по возрастанию значений ключевого поля.

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

Psp^.ukz^.inf – к информационной части, содержащей число 3;

Psp^.ukz^.ukz – к полю-указателю, содержащему адрес третьего элемента;

Psp^.ukz^.ukz^.inf – к информационной части третьего элемента списка,

содержащего число 4.

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

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

^ PSP – указатель списка;

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

Procedure VKLSP(Var PSP,VKL : U);

Var P,Q : U;

Begin

If PSP=nil Then

Begin

PSP:=VKL;

exit

End;

If VKL^.Inf<=PSP^.Inf Then

{ включение перед первым элементом }

Begin

VKL^.Ukz:=PSP;

PSP:=VKL;

Exit

^ End;

{общий случай}

P:=PSP;

While (VKL^.Inf>P^.Inf) And (P^.Ukz<>Nil) Do

Begin

Q:=P; { Q- указатель предыдущего элемента списка }

P:=P^.Ukz; { P- указатель текущего элемента списка }

End;

If VKL^.Inf<=P^.Inf Then

{ включение в середину списка }

Begin

VKL^.Ukz:=Q^.Ukz;

Q^.Ukz:=VKL

End

Else { включение в конец списка }

P^.Ukz:=VKL

End;

Рисунок 7  Процедура включения элемента в упорядоченный список

Например, исходное состояние списка:



(PSP содержит адрес первого элемента списка).

В
ключаемый элемент:

Результат включения:




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

PSP – указатель списка;

KL – заданный ключ;

PR–признак: если элемент с заданным ключом отсутствует, то PR=0.

Например, исходное состояние списка:
Заданный ключ KL=5

Результат исключения:




Особый случай: исключение первого элемента списка (указатель списка должен поменять значение).
Procedure ISKL( Var PSP:U; Var PR: integer;KL: integer);

Var P, Q: U;

Begin

PR:=0;

If PSP=nil Then

Begin

Writeln ( ‘Список пуст! ‘);

Readkey;

Exit;

End;

PR:=1;

If PSP^.Inf=KL Then

{ исключаемый элемент-первый }

Begin

Q:=PSP;

PSP:=PSP^.Ukz;

Dispose(Q);

Exit;

End;

{общий случай}

P:=PSP;

While (KL>P^.Inf) and (P^.Ukz<>Nil) do

Begin

Q:=P;

P:=P^.Ukz;

End;

If P^.Inf=KL Then

Begin

Q^.Ukz:=P^.Ukz;

Dispose(P);

End

Else { в списке нет элемента с заданным ключом }
PR:=0;

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

Похожие:

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

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

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

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

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

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

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

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

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

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

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


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