Введение
Линейный список – это последовательность из нуля или более элементов (узлов), главной особенностью которого является такое относительное расположение узлов, будто они образуют одну линию. Если в линейном списке n>0 элементов, то узел j[k] (0<k<n) следует непосредственно за j[k-1] и предшествует j[k+1]. В общем случае над линейными списками могут быть определены девять операций:
1. Доступ к узлу k для просмотра или модификации хранимых данных;
2. Вставка нового узла непосредственно перед или после узла k;
3. Удаление узла k;
4. Объединение линейных списков в новом списке;
5. Разбиение списка на линейные списки;
6. Копирование списка;
7. Нахождение количества узлов списка;
8. Сортировка узлов списка в некотором порядке, определяемом содержимым записанных в узле данных;
9. Поиск узла в соответствии со значением, связанным с содержимым записанных в узле данных.
Следует выделить особые случаи, когда обрабатывается первый или последний элемент списка, поскольку доступ к таким узлам организовать проще, чем к остальным.
Модуль GraphABC представляет собой простую графическую библиотеку и предназначен для создания несобытийных графических и анимационных программ в процедурном и частично в объектном стиле. Рисование осуществляется в специальном графическом окне, возможность рисования в нескольких окнах отсутствует. Кроме этого, в модуле GraphABC определены простейшие события мыши и клавиатуры, позволяющие создавать элементарные событийные приложения. Основная сфера использования модуля GraphABC – обучение.
Основная часть
Задача 1
Используйте линейные списки для хранения последовательности чисел. Опишите процедуру, которая удаляет:
а) из списка второй элемент, если такой есть;
б) из непустого списка последний элемент.
Используемые переменные
N – данные списка (количество элементов списка);
X – указатель на элемент списка;
L, p, s – списки;
i – счетчик цикла.
Алгоритм решения задачи
1. Создадим список – введем количество элементов и заполним список элементами;
2. Выводим полученный список на экран;
3. Вызываем процедуру, которая формирует новый список из исходного – в случае, если второй (следующий за первым) узел списка не пуст, он удаляется из списка;
4. Выводим новый список на экран;
5. Вызываем процедуру, которая формирует новый список из исходного – первый узел списка сохраняется в промежуточной переменной, узлы переданного списка просматриваются в цикле, и в случае, если достигнут последний элемент списка, он удаляется из него;
6. Выводим полученный список на экран.
Исходный код программы
{- описание типа списка -}
type
list = ^node;
node = record
info: integer;
next: list;
end;
{- описание переменных -}
var
s, l: list;
x, n, i: integer;
{ — процедура, которая из списка L удаляет последний элемент — }
procedure remove_last(var l: list);
var
p: list;
begin
if l^.next = nil then begin
dispose(l);
l := nil;
end
else begin
p := l;
while p^.next^.next <> nil do
p := p^.next;
dispose(p^.next);
p^.next := nil;
end;
end;
{ — процедура, которая из списка L удаляет второй элемент — }
procedure remove_second(var l: list);
var
p: list;
begin
if l^.next <> nil then
l^.next := l^.next^.next;
end;
{- процедура печати списка L -}
procedure out_list(l: list);
begin
while l <> nil do
begin
s := l^.next;
write(l^.info, ‘ ‘);
l := s;
end;
writeln;
end;
{- процедура освобождения памяти, выделенной для каждого из списков -}
procedure free_list(var l: list);
begin
while l <> nil do
begin
s := l^.next;
dispose(l);
l := s;
end;
end;
begin
{формируем список}
s := nil;
write(‘Введите количество элементов списка: ‘);
readln(n);
writeln(‘Введите элементы списка по одному: ‘);
for i := 1 to n do
begin
new(l);
l^.next := s;
readln(x);
l^.info := x;
s := l;
end;
{выводим список на экран}
writeln(‘Введенный список: ‘);
out_list(l);
{- формируем новый список и выводим его -}
remove_second(l);
writeln(‘Список после удаления второго элемента: ‘);
out_list(l);
remove_last(l);
writeln(‘Список после удаления последнего элемента: ‘);
out_list(l);
{- освобождаем память -}
free_list(l);
readln;
end.
Задача 2
Построить лемнискату — кривую, уравнение которой в полярных координатах
= a√2 cos(2), a > 0.
Используемые переменные
x, x0 – расположение графического объекта для представления элемента по оси абсцисс;
y, y0 – расположение графического объекта для представления элемента по оси ординат;
m – переменная для отрисовки координатной сетки;
a – коэффициент;
r – значение формулы;
f – величина угла;
s – строка с надписями;
i – счетчик цикла.
Алгоритм решения задачи
1.Инициируем модуль graph;
2.Устанавливаем начальные значения переменных;
3.В цикле рисуем линии и подписи координатной сетки;
4.Кладем f = 0.
5.Пока f не превосходит удвоенного числа пи, выполнить:
5.1Найти новое значение r для f в точке (x, y);
5.2Поставить r на форме;
5.3Увеличить f на величину шага.
Исходный код программы
uses graphABC;
var
x0, y0, i, x, y: integer;
r, a, m, f: real;
s: string;
begin
a := 2;
x0 := windowwidth div 2;
y0 := windowheight div 2;
m := (x0 — 50) / (a * sqrt(2));
line(0, y0, 2 * x0, y0);
line(x0, 0, x0, 2 * y0);
for i := 1 to 2 * (trunc(a * sqrt(2)) + 1) do
begin
line(x0 + round(i * m / 2), y0 — 3, x0 + round(i * m / 2), y0 + 3);
line(x0 — round(i * m / 2), y0 — 3, x0 — round(i * m / 2), y0 + 3);
line(x0 + 3, y0 — round(i * m / 2), x0 — 3, y0 — round(i * m / 2));
line(x0 + 3, y0 + round(i * m / 2), x0 — 3, y0 + round(i * m / 2));
str(i / 2:0:1, s);
textout(x0 + round(i * m / 2), y0 + 10, s);
textout(x0 — round(i * m / 2), y0 + 10, ‘-‘ + s);
textout(x0 — 20, y0 — round(i * m / 2), s);
textout(x0 — 25, y0 + round(i * m / 2), ‘-‘ + s);
end;
f := 0;
while f <= 2 * pi do begin if cos(2 * f) >= 0 then
begin
r := a * sqrt(2 * cos(2 * f));
x := x0 + round(r * cos(f) * m);
y := y0 — round(r * sin(f) * m);
setpixel(x, y, clRed);
end;
f := f + 0.001;
end;
end.
Блок-схемы
Рисунок 1. Блок-схема к задаче 1
Рисунок 2. Блок-схема к задаче 2
Тестирование программ
Рисунок 3. Результат работы программы для задания 1
Рисунок 4. Вид окна программы для задания 2 в процессе работы программы
Заключение
В ходе выполнения лабораторной работы были изучены базовые структуры данных, такие как линейные односвязные списки, и основные функции для работы со списками, а также изучен модуль GraphABC для создания программ в графическом режиме на языке программирования Pascal. Были выполнены две программы по каждой из этих тем, построены блок-схемы и описаны алгоритмы их решения.