double arrow

Лабораторная работа № 5


(4 часа)

Динамические структуры данных - односвязные и двусвязные списковые структуры

Цель работы:

Изучение организации списковых структур и построение реальных структур данных на базе списков.

Домашнее задание:

1. Освоить организацию адресного типа (указатели) в Object Pascal и построение динамического списка.

2. Изучить алгоритмы. Позволяющие работать со списковыми структурами различной организации:

а) линейный и кольцевой стек;

б) линейная и кольцевая очередь;

в) дек.

Порядок выполнения работы

1. Открыть проект Delphi Stuctures.

2. На главной форме в главное меню проекта добавить пункт «Лабораторная работа №5», при выборе которого должно появляться окно модуля «DinamicStuct». Для этого модуль DinamicStuct с формой добавить в проект.

3. Установить на форму модуля DinamicStuct компоненты, обеспечивающие ввод исходных данных и вывод результатов работы программы в соответствии с вашим вариантом задания (табл. 5.1), а также управляющую кнопку для запуска программного кода при нажатии на кнопку (событие onClic) в работающей программе. Для ввода и вывода в этих задачах использовать компоненты класса Tmemo.

4. В обработчике события onClic управляющей кнопки написать программный код, моделирующий работу структуры данных динамического характера, соответствующей заданию вашего варианта.

5. отладить приложение на тестовых примерах и продемонстрировать работу смоделированной структуры данных преподавателю.

6. Составить отчет о выполненной лабораторной работе, в который должны войти:

а) задание, в соответствии с вариантом;

б) блок-схема решения задачи;

в) программа решения задачи;

г) распечатка формы с демонстрацией работы смоделированной структуры данных.

7. Защитить работу преподавателю.


Таблица 5.1

№ вар. Содержание задания
1. Организовать программно линейный односвязный список следующей структуры:
 
 

Опишите в программе запись, в поле bukv которой заносится буква. Порождая записи, поместить их в стек, а затем «вытолкнуть» их из списка, получив буквы в порядке, обратном исходному. Проверьте работу примера для исходного набора букв:
const A: array [1 .. 9] of char =(‘A’, ’P’, ‘Y’, ‘T’, ‘K’, ‘Y’, ’P’, ‘T’, ‘C’).

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

3. Программно организазать очередь в виде однонаправленого списка из элементов типа rec: Type ptr =^ rec; rec = record key : integer; s : ptr; end; var t : rec; Заполняются ссылки на первое ипоследнее звенья списка.
 
 

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

4. Многочлен P(х) = anxn + an-1xn-1 +… + a1x + a0 с целыми коэффициентами можно представить в виде списка, элементы которого расположены по убыванию степеней одночленов: Описать на Object Pascal тип данных, соответствующий такому представлению многочленов, и определить следующие функции и процедуры для работы с этими списками-многочленами: а) логическую функцию Equal(p,q), проверяющую на равенство многочлены p и q; б) функцию Value(p,x), вычисляющую значение p в точке x; в) процедуру Dif(p,q), которая строит многочлен p-производную многочлена q; г) процедуру Addit(p,q,r), которая строит многочлен p-сумму многочленов q и r.
5. Кольцевым списком называется однонаправленный список, в последнем звене которого вместо Nil указывается ссылка на первое звено:
 
 

Пусть L - кольцевой список с элементами типа Type prt =^ rec

rec = record;

key : integer;

s : ptr;

end;

а E - величина типа rec.

Описать и отладить:

а) процедуру, которая строит кольцевой список L и выводит в компонент класса TstringGrid таблицу:

t1 t2 … tn-1 tn

t2 t3 … tn t1

t3 t4 … t1 t2

-- - - - - - - - - -

tn t1 … tn-2 tn-1

б) процедуру, которая строит кольцевой список L и функцию, которая удаляет из непустого списка L последний элемент.

в) процедуру, которая строит кольцевой список L и функцию, которая добавляет в конец списка L новый элемент.

Контрольные вопросы

1 Определения типизированного и обобщенного указателя.

2 Что такое линейный цепной список, и алгоритмы основных операций при работе с ним.

3 Принцип работы кольцевого списка.

4 Организация стека на базе линейного и кольцевого списка.

5 Организация очереди на базе линейного и кольцевого списка.



Сейчас читают про: