Лабораторная работа №16. Линейные списки
ЦЕЛЬ РАБОТЫ: Изучить программирование линейных списков – добавление элементов в любое место линейного списка, удаление любого элемента списка, просмотр списка, работу с упорядоченными списками и т.д.
ПОДГОТОВКА К РАБОТЕ:
Рассмотреть способы организации списков - однонаправленные, двунаправленные, кольцевые ит.д.
Изучить методы добавления элементов в начало, конец и в любое место списка.
ЗАДАНИЕ: Написать приложение для формирования упорядоченного линейного списка. Экранная форма приложения приведена на рисунке 16.1.
Компоненты приложения приведены в таблице 16.1.
Таблица 16.1 Компоненты приложения для работы с упорядоченным списком
Компонент |
Класс |
Описание |
Edit1 |
TEdit |
Окно ввода добавляемого/удаляемого элемента |
Memo1 |
TMemo |
Окно вывода сформированного списка |
Button1 |
TButton |
Командная кнопка «Добавить» |
Button2 |
TButton |
Командная кнопка «Удалить» |
Button2 |
TButton |
Командная кнопка «Вывод списка» |
Последовательность действий:
В блоке Type после объявления класса формы создайте структуру «список» и указатель на структуру «список»:
pt=^elem;
elem=Record
data:integer;
next:pt;
end;
В области глобальных переменных объявите указатели на начало и конец списка:
var
Form1: TForm1;
first,last:pt;
………………………………..
В блоке implementation опишите вспомогательную функцию добавления элемента в начало списка:
procedure Ins_Begin(el:Integer);
Var New_first:pt;
Begin
New(New_first); New_first^.next:=first; New_first^.data:=el;
first:=New_first;
end;
В блоке implementation опишите вспомогательную функцию добавления элемента в конец списка:
procedure Ins_End(el:Integer);
Var t:pt;
Begin
New(t); t^.data:=el; t^.next:=nil;
last^.next:=t; last:=t;
end;
В блоке implementation опишите вспомогательную функцию добавления элемента в середину списка:
procedure Ins_med(el:Integer);
Var t,new_m,dt:pt;
Begin
New(new_m); t:=first;
While el>t^.data do
begin
dt:=t; t:=t^.next;
end;
new_m^.next:=t; new_m^.data:=el; dt^.next:=new_m;
end;
Для события OnActivate формы напишите программный код для инициализации указателей на начало и конец списка:
procedure TForm1.FormActivate(Sender: TObject);
begin
first:=nil; last:=nil;
end;
Для события OnClick кнопки Button1 напишите следующий программный код:
procedure TForm1.Button1Click(Sender: TObject);
var el:Integer;
begin
el:=StrToInt(Edit1.Text);
// если список пуст
If first=nil then
begin
Ins_Begin(el); last:=first;
end
else
If el<first^.data then Ins_Begin(el)
else If el>last^.data then Ins_end(el)
else Ins_med(el);
end;
Для события OnClick кнопки Button2 напишите следующий программный код:
procedure TForm1.Button2Click(Sender: TObject);
var
t,x,dx:pt;
el:Integer;
begin
el:=StrToInt(Edit1.Text);
// Переменная цикла
t:=first;
// Пока список не просмотрен
While t<>nil do
// Есть совпадение
If t^.data=el then
// Удаляем первый элемент из списка
if t=first then
begin
// запоминаем адрес удаляемого элемента
x:=first;
// изменяем значение указателя на первый элемент списка
first:=first^.next;
// Освобождаем динамическую память
Dispose(x);
// Переменная цикла изменила свое значение
t:=first;
end
else
begin
// запоминаем адрес удаляемого элемента
x:=t;
t:=t^.next;
// удаление элемента не должно нарушать структуру списка
dx^.next:=t;
Dispose(x);
end
else
begin
// Переход к следующему элементу списка
// Адрес текущего элемента запоминается в переменной dx
dx:=t;
t:=t^.next;
end;
end;
Для события OnClick кнопки Button3 напишите следующий программный код:
procedure TForm1.Button3Click(Sender: TObject);
Var p:pt;
begin
Memo1.Clear;
p:=first;
While p<>nil do
begin
memo1.Lines.add(IntToStr(p^.data));
p:=p^.next;
end;
end;
Проверьте работу приложения.
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ:
Составить процедуру нахождения среднего арифметического элементов непустого списка L. Используя данную процедуру, найти максимальное среднее арифметическое в списках К, М, N.
Построить список L, упорядочив его по возрастанию, из двух неупорядоченных списков L1 и L2.
КОНТРОЛЬНЫЕ ВОПРОСЫ
Сравните функциональные возможности стеков, очередей и списков
Опишите алгоритм формирования упорядоченного списка.