Сравним производительность различных операций для списков с массивами. Основное преимущество массивов – возможность обратиться к произвольному элементу по его индексу. Для списка подобная операция потребует просмотра всех предшествующих элементов. Однако добавление в начало и середину массива, а также удаление из начала и середины требует сдвига всех элементов массива, расположенных после вставляемого (удаляемого). Для списка же производительность операций добавления и удаления не зависит ни от длины списка, ни от места вставки. Сортировка вставками в списке имеет такую же производительность, что и простые виды сортировок для массивов (например, пузырьковая сортировка или сортировка выбором).
Таким образом, если в задаче требуется структура с частыми операциями вставки и удаления в середине, следует предпочесть список, если же важнее быстрый доступ по индексу – следует выбрать массив. При выборе структуры следует также учитывать, что для организации односвязного списка на каждый элемент требуется одно поле связи, занимающее 4 байта (для массива подобные накладные расходы отсутствуют). С другой стороны, список может динамически расширяться во время работы программы, в то время как под массив отводится фиксированное количество элементов, которое необходимо указать на этапе компиляции.
Двусвязные линейные списки
Двусвязный линейный список состоит из элементов, каждый из которых хранит адреса следующего и предыдущего. Для удобства работы со списком поддерживаются указатели first и last на первый и последний элемент соответственно:
В структуру Node добавляется указатель prev на предыдующий элемент списка:
type
PNode=^Node;
Node=record
data: integer;
prev,next: PNode;
end;
Вспомогательная функция NewNode при этом изменяется очевидным образом:
function NewNode(data: integer; prev, next: PNode): PNode;
begin
New(Result);
Result^.data:=data;
Result^.next:=next;
Result^.prev:=prev;
end;
Рассмотрим основные операции с двусвязным списком, реализация которых отличается от односвязного. После выполнения каждой операции first и last должны по-прежнему оставаться указателями на начало и конец списка, а если список пуст, то получать нулевое значение.
1. Инициализация.
При инициализации список пуст:
first:=nil;
last:=nil;
2. Добавление элемента со значением x в начало.
Осуществляется аналогично добавлению в односвязный список. Если список был пустым, то last также должен указывать на добавленный элемент.
first:=NewNode(x,nil,first);
if last=nil then last:=first;
3. Добавление элемента со значением x в конец.
Симметрично добавлению в начало:
last:=NewNode(x,last,nil);
if first=nil then first:=last;
4. Вставка элемента со значением x перед текущим.
Пусть указатель p хранит адрес текущего элемента.
Создадим новый элемент, поле next которого указывает на текущий, поле prev – на предыдущий. При этом поле prev текущего элемента и поле next предыдущего должны указывать на вставляемый. Если же предыдущего элемента нет, то осуществляется вставка в начало, и требуется скорректировать указатель на первый элемент:
t:=NewNode(x,p^.prev,p);
p^.prev:=t;
if p^.prev<>nil then
p^.prev^.next:=t
else first:=t;
Аналогично производится вставка после текущего элемента.
5. Удаление текущего элемента.
Пусть указатель p хранит адрес текущего элемента.
Перед освобождением памяти под текущий элемент следует перенаправить указатель next у предыдущего элемента на следующий, а у следующего указатель prev –на предыдущий. Если же следующего элемента нет, то необходимо удалить последний элемент и скорректировать переменную last. Аналогично если предыдущего элемента нет, то удаляется первый, и необходимо скорректировать first.
if p^.prev<>nil then
p^.prev^.next:=p^.next
else first:=p^.next;
if p^.next<>nil then
p^.next^.prev:=p^.prev
else last:=p^.prev;
Dispose(p);
Заметим, что если удаляется единственный элемент, то указатели first и last получают значение nil, т.е. список становится пустым.
В заключение приведем пример, иллюстрирующий высокую эффективность списков в некоторых задачах.
Пример. Объединение списков.
Имеется два списка, заданные указателями на начало и конец.
Требуется добавить содержимое второго списка в конец первого, очистив при этом второй список.
Для решения указанной задачи достаточно выполнить всего пять операторов присваивания:
last1^.next:=first2;
first2^.prev:=last1;
last1:=last2;
first2:=nil;
last2:=nil;
Заметим, что решение аналогичной задачи для массива требует использования цикла с числом итераций, равным размеру добавляемого массива.
Задание 1
Составить процедуры ввода и печати двунаправленного списка, опробовать их работу.
Задание 2
Составить нерекурсивную функцию для:
2.1. Подсчета числа элементов в списке
2.2. Нахождения суммы элементов списка
2.3. Нахождения максимума в непустом списке
2.4. Нахождения минимума в непустом списке
2.5. Поиска данного числа среди элементов списка (логическая функция)
2.6. Нахождения произведения ненулевых элементов списка
Задание 3
Составить аналогичную предыдущей рекурсивную функцию.
Задание 4
Выполнить одно из следующих заданий:
4.1. Составить процедуру добавления элемента в упорядоченный список с сохранением свойства упорядоченности списка. Проверить работу процедуры, а затем с ее использованием составить программу упорядочивания списка.
4.2. Составить процедуру смены местами двух последовательных элементов списка (аргументы – указатели на начало, конец списка и на первый из меняемых элементов, результат – указатели на начало и конец нового списка). Опробовать работу процедуры, а затем с ее помощью упорядочить данный список методом «пузырька».
Задание 5
Решить одну из следующих задач:
5.1. Составить процедуру слияния двух упорядоченных списков в один и с ее помощью организовать быструю сортировку списка.
5.2. Реализовать процедуру выбора водящего с помощью детской считалочки по кругу с выбыванием (после выбывшего счет начинается заново со следующего по кругу, а последний оставшийся и есть водящий).
5.3. Восстановить список, если есть список всех пар следующих друг за другом элементов, например по данным (4,13),(5,7),(7,3),(13,5),(67,4) должен быть получен исходный список (67,4,13,5,7,3).
Задание 6
Имеется указатель на первый элемент однонаправленного списка. Последний элемент списка указывает на nil. Описать алгоритм, (аккуратно, но не доводя до программы), с помощью которого можно установить корректность списка или наличие в нем циклов.
Лабораторная работа №12
Работа с графикой
Цель: приобрести навыки работы с графическими возможностями среды программирования.
Теоретические сведения
Дополнительные ресурсы:
http://www.slideshare.net/yak-ella/pascal-abc
http://samlib.ru/w/waleri_l_w/grafikawpascalabc.shtml
Изображения в паскале можно создавать с помощью модуля GraphABC, он подключается после Uses.
Начнем с рассмотрения системы координат в паскале
Операторы используемые в графике:
SetWindowHeight(h); - Устанавливает высоту графического окна
SetWindowWidth(w); - Устанавливает ширину графического окна
ClearWindow; - очищает графическое окно белым цветом.
ClearWindow(color); - очищает графическое окно указанным цветом.
SetPixel(x,y,color); - Закрашивает один пиксел с координатами (x,y) цветом color
LineTo(x,y); - рисует отрезок от текущего положения пера до точки (x,y); координаты пера при этом также становятся равными (x,y).
Line(x1,y1,x2,y2); - рисует отрезок с началом в точке (x1,y1) и концом в точке (x2,y2).
SetPenColor(color); - устанавливает цвет пера, задаваемый параметром color.
Некоторые из цветов:
| clBlack – черный clPurple – фиолетовый clWhite – белый clMaroon – темно-красный clRed – красный clNavy – темно-синий clGreen – зеленый clBrown – коричневый clBlue – синий clSkyBlue – голубой clYellow – желтый clCream – кремовый | clAqua – бирюзовый clOlive – оливковый clFuchsia – сиреневый clTeal – сине-зеленый clGray – темно-серый clLime – ярко-зеленый clMoneyGreen – цвет зеленых денег clLtGray – светло-серый clDkGray – темно-серый clMedGray – серый clSilver – серебряный |
Цвет также можно задать с помощью палитры RGB для это за место color пишется rgb(r,g,b): где r,b,g - числа от 0 до 255
SetPenWidth(n); - устанавливает ширину (толщину) пера, равную n пикселям.
Rectangle(x1,y1,x2,y2); - рисует прямоугольник, заданный координатами противоположных вершин (x1,y1) и (x2,y2).
FloodFill(x,y,color); - заливает область одного цвета цветом color, начиная с точки (x,y).
SetBrushColor(color); - устанавливает цвет кисти, заливка кистью распространяется на замкнутый контур, описание которого следует за процедурой установки цвета кисти.
Circle(x,y,r); - рисует окружность с центром в точке (x,y) и радиусом r.
Ellipse(x1,y1,x2,y2); - рисует эллипс, заданный своим описанным прямоугольником с координатами противоположных вершин (x1,y1) и (x2,y2).
SetFontName(‘name’);- устанавливает наименование шрифта.
SetFontColor(color); - устанавливает цвет шрифта.
SetFontSize(sz); - устанавливает размер шрифта в пунктах.
SetFontStyle(fs); - устанавливает стиль шрифта.
Стиль шрифта:
fsNormal – обычный;
fsBold – жирный;
fsItalic – наклонный;
fsBoldItalic – жирный наклонный;
fsUnderline – подчеркнутый;
fsBoldUnderline – жирный подчеркнутый;
fsItalicUnderline – наклонный подчеркнутый;
fsBoldItalicUnderline – жирный наклонный подчеркнутый.
Пример: нарисовать
Программа:
Program Seventh;
uses GraphABC;
Begin
Line (200,200,400,200); LineTO (300,140); lineTO (200,200);
FloodFill (300,170,clblue);
Line (200,200,400,200); LineTo (300,260); LineTo (200,200);
FloodFill (300,230,cllime);
circle (160,200,40);
FloodFill (160,200,clred);
circle (440,200,40);
FloodFill (440,200,clyellow);
End.
На экране вы увидите:
Задание 1.
Построить график функции. Реализовать координатную сетку, оси координат, и линию графика функции y = f(x).
а) График рисуется по точкам (приращение координаты ∆x = 1).
б) График функции рисуется в виде ломаной линии. Прорисовать в виде отдельных отрезков, приращение координаты (∆x = 5).
| № варианта | f(x) |
| 1 | sin(x) + 2*x |
| 2 | cos(x) |
| 3 | tg(x) |
| 4 | 2x2 + 3x - 5 |
| 5 | 4x3 – 5x - 2 |
| 6 | 2 * log2x |
| 7 | ex – 5*x |
| 8 | 5*x – 6*x2 |
| 9 | 4*x3 – sin(x) |
| 10 | 2* sin(x) + 3*cos(s) |
Задание 2.
Прорисовать изображение:
| № варианта | f(x) |
| 1 | автомобиль |
| 2 | самолёт |
| 3 | арбуз |
| 4 | дом |
| 5 | дерево |
| 6 | шляпа |
| 7 | телефон |
| 8 | книга |
| 9 | очки |
| 10 | карандаш |
На форме должно быть изображение и крупная цветная надпись с названием изображения.
Задание 3.
Реализовать программу, которая прорисовывает на форме сетку ( 10 х 10 ячеек).
Программа открывает файл в котором содержится значение цвета для каждой ячейки. В соответствие с файлом ячейки сетки на форме заполняются нужными цветами. В файле для отображения цветов используются символы:
R – красный;
G – зелёный;
B – голубой.
Например:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | ||||||||||
| 2 | ||||||||||
| 3 | ||||||||||
| 4 | ||||||||||
| 5 | ||||||||||
| 6 | ||||||||||
| 7 | ||||||||||
| 8 | ||||||||||
| 9 | ||||||||||
| 10 |
Файл содержит:
RRRRRRRRRR
RRRRRRRRRG
RRRRRRRRGG
RRRRRRRGGG
RRRRRRGGGG
RRRRRGGGBB
RRRRGGGBBB
RRRGGGBBBB
RRGGGBBBBB
RGGGBBBBBB
Лабораторная работа №13
Работа с графикой, анимация
Цель: закрепить навыки работы с графическими функциями, приобрести опыт реализации динамических графических изображений.
Теоретические сведения
Рисование шара
| uses GraphABC; var I,X,Y,D: integer; begin X:=20; Y:=30; D:=100; ClearWindow; SetBrushColor(clGreen); Ellipse(X+I,Y,X+I+D,Y+D); end. |
Движение шара
uses GraphABC;
var I,X,Y,D : integer;
begin
X:=20; Y:=30; D:=100;
for i:=1 to 500 do
begin
ClearWindow;
SetBrushColor(clGreen);
Ellipse(X+I,Y,X+I+D,Y+D);
Sleep(1);
end;
end.
При работе данного примера возможно мерцание движущегося изображения. Для устранения этого эффекта используются следующие функции:
LockDrawing – блокирует вывод в графическое окно, осуществляя рисование только во внеэкранном буфере.
Redraw – перерисовывает окна вывода при заблокированном выводе в графическое окно.
Дата: 2019-02-02, просмотров: 820.
