|
|
(не показано 27 промежуточных версий 5 участников) |
Строка 1: |
Строка 1: |
− | [[Категория:Конспекты]] | + | [[Категория:Основы программирования]] |
− | == АТД — Абстрактные Типы Данных == | + | == АТД — Абстрактные Типы Данных. Классы как реализация АТД == |
| === Что мы знаем о классах === | | === Что мы знаем о классах === |
| # Класс — это составной тип данных | | # Класс — это составной тип данных |
Строка 8: |
Строка 8: |
| # Можно создавать шаблоны классов, параметризованные одним или несколькими типами | | # Можно создавать шаблоны классов, параметризованные одним или несколькими типами |
| | | |
− | <small>Лекция 10</small>
| + | === Понятие абстрактного типа данных === |
− | | |
− | === Абстрактные типы данных === | |
| До сих пор мы сталкивались с конкретными типами данных, которые характеризуются: | | До сих пор мы сталкивались с конкретными типами данных, которые характеризуются: |
| * ''набором допустимых значений'' | | * ''набором допустимых значений'' |
Строка 29: |
Строка 27: |
| Этот принцип называется '''''принципом сокрытия реализации''''' (или '''''защитой доступа'''''). | | Этот принцип называется '''''принципом сокрытия реализации''''' (или '''''защитой доступа'''''). |
| | | |
− | Рассмотрим пример абстрактного типа данных — стек.
| + | А теперь рассмотрим пример абстрактного типа данных — стек. |
| | | |
| === АТД Стек === | | === АТД Стек === |
Строка 319: |
Строка 317: |
| end. | | end. |
| </source> | | </source> |
− |
| |
− | <small>Лекция 11</small>
| |
| | | |
| === АТД и класс Очередь === | | === АТД и класс Очередь === |
Строка 428: |
Строка 424: |
| </source> | | </source> |
| | | |
− | <xh4> Примеры использования АТД Queue </xh4>
| + | ====Примеры использования АТД Queue==== |
− | ''<u>Задача 1</u>.''
| |
− | :Вводятся натуральные числа, конец ввода - '''<tt>0</tt>'''
| |
− | :Вывести: количество четных, количество нечетных, все четные в прямом порядке, все нечетные — в обратном.
| |
− | Например, введены числа:
| |
− | '''1 2 5 7 4 6 9 0'''
| |
− | Должно быть выведено следующее:
| |
− | '''3''' ''// количество четных''
| |
− | '''4''' ''// количество нечетных''
| |
− | '''2 4 6''' ''// все четные в прямом порядке''
| |
− | '''3 7 5''' ''// все нечетные в обратном порядке''
| |
− | | |
− | <u>Решение:</u> <br />
| |
− | Эта задача имеет несколько решений, но, очевидно, самым удобным является использование изученных нами АТД — стека и очереди. <br />
| |
− | Очередь организована по принципу ''FIFO'', а значит подходит для вывода чисел в прямом порядке, в то время как для обратного вывода надо воспользоваться стеком, организованным по принципу ''LIFO''.
| |
− | | |
− | <source lang="Delphi">
| |
− | uses Collections;
| |
− | | |
− | var
| |
− | /// для хранения четных чисел
| |
− | q: Queue<integer>;
| |
− | /// для хранения нечетных чисел
| |
− | s: Stack<integer>;
| |
− |
| |
− | /// количество четных чисел
| |
− | cEven: integer;
| |
− | /// количество нечетных чисел
| |
− | cOdd: integer;
| |
− |
| |
− | begin
| |
− | q := new Queue<integer>;
| |
− | cEven := 0;
| |
− | s := new Stack<integer>;
| |
− | cOdd := 0;
| |
− |
| |
− | while True do
| |
− | begin
| |
− | var x: integer;
| |
− | read(x);
| |
− |
| |
− | if x = 0 then
| |
− | break;
| |
− | Assert(x > 0); // по условию задачи должны вводиться натуральные числа
| |
− |
| |
− | if Odd(x) then
| |
− | begin
| |
− | cOdd += 1;
| |
− | s.Push(x);
| |
− | end
| |
− | else // if x is even
| |
− | begin
| |
− | cEven += 1;
| |
− | q.Enqueue(x);
| |
− | end;
| |
− | end;
| |
− |
| |
− | writeln('Количество четных = ', cEven);
| |
− | writeln('Количество нечетных = ', cOdd);
| |
− | | |
− | write('Четные в прямом порядке: ');
| |
− | while not q.IsEmpty do
| |
− | write(q.Dequeue, ' ');
| |
− | writeln();
| |
− |
| |
− | write('Нечетные в обратном порядке: ');
| |
− | while not s.IsEmpty do
| |
− | write(s.Pop, ' ');
| |
− | end.
| |
− | </source>
| |
− | <br />
| |
− | ''<u>Задача 2</u>.'' Обслуживание клиентов в очереди (категория '''''использование АТД при моделировании'''''). <br />
| |
− | <u>Спецификация задачи:</u>
| |
− | Имеется очередь клиентов. <br />
| |
− | Первоначально она пуста. <br />
| |
− | В течение рабочего дня (7*60 минут) происходят следующие случайные события:
| |
− | * приход клиента;
| |
− | * обслуживание клиента в очереди;
| |
− | Время перед приходом нового клиента <tt>TimeBeforeNewClient</tt> и время обслуживания текущего клиента <tt>ServeTime</tt> генерируются случайно. <br />
| |
− | Будем считать, что функция RandomClient возвращает нового клиента.
| |
− | | |
− | <u>Решение:</u>
| |
− | <source lang="Delphi">
| |
− | uses Collections;
| |
− | | |
− | type
| |
− | /// Клиент
| |
− | Client = class
| |
− | /// Имя клиента
| |
− | name: string;
| |
− | /// Сумма денег
| |
− | money: integer;
| |
− |
| |
− | constructor (pName: string; pMoney: integer);
| |
− | begin
| |
− | name := pName;
| |
− | money := pMoney;
| |
− | end;
| |
− |
| |
− | procedure Println;
| |
− | begin
| |
− | write('Имя: ', name);
| |
− | writeln(' Наличные: ', money);
| |
− | end;
| |
− | end;
| |
− | | |
− | /// Возвращает случайного клиента
| |
− | function RandomClient: Client;
| |
− | begin
| |
− | case Random(3) of
| |
− | 0 : result := new Client('Иванов', Random(100, 1000));
| |
− | 1 : result := new Client('Петрова', Random(1, 1000000));
| |
− | 2 : result := new Client('Сидоров', Random(1000, 10000));
| |
− | end;
| |
− | end;
| |
− |
| |
− | const
| |
− | /// Количество часов рабочего дня
| |
− | WORKING_DAY = 7;
| |
− | /// Количество минут в часе
| |
− | MIN_IN_HOUR = 60;
| |
− |
| |
− | /// Минимальное время до прихода нового клиента
| |
− | MIN_BEFORE_NEW = 1;
| |
− | /// Максимальное время до прихода нового клиента
| |
− | MAX_BEFORE_NEW = 10;
| |
− | /// Минимальное время обслуживания клиента
| |
− | MIN_SERVE = 4;
| |
− | /// Максимальное время обслуживания клиента
| |
− | MAX_SERVE = 9;
| |
− |
| |
− | /// Выводит время в часах и минутах
| |
− | procedure PrintTime(cMinutes : integer);
| |
− | begin
| |
− | var hours := cMinutes div MIN_IN_HOUR;
| |
− | var minutes := cMinutes mod MIN_IN_HOUR;
| |
− |
| |
− | write(hours:2, ' : ', minutes:2);
| |
− | end;
| |
− | | |
− | var
| |
− | /// Очередь клиентов
| |
− | ClientQueue := new Queue<Client>;
| |
− |
| |
− | /// Время до обслуживания нового клиента
| |
− | TimeBeforeNewClient: integer;
| |
− | /// Врямя, требующееся на обслуживание клиента
| |
− | ServeTime: integer;
| |
− |
| |
− |
| |
− | begin
| |
− | TimeBeforeNewClient := 0;
| |
− | ServeTime := 0;
| |
− | | |
− | for var t := 1 to WORKING_DAY * MIN_IN_HOUR do
| |
− | begin
| |
− | if TimeBeforeNewClient = 0 then // пришел новый клиент
| |
− | begin
| |
− | var rCl := RandomClient;
| |
− | ClientQueue.Enqueue(rCl);
| |
− | TimeBeforeNewClient := Random(MIN_BEFORE_NEW, MAX_BEFORE_NEW);
| |
− |
| |
− | PrintTime(t); write(' Пришел: ');
| |
− | rCl.Println;
| |
− | end;
| |
− |
| |
− | if (ServeTime = 0) and not ClientQueue.IsEmpty then // подошло время обслуживать клиента
| |
− | begin
| |
− | var rCl := ClientQueue.Dequeue;
| |
− | ServeTime := Random(MIN_SERVE, MAX_SERVE);
| |
− |
| |
− | PrintTime(t); write(' Обслужен: ');
| |
− | rCl.Println;
| |
− | end;
| |
− |
| |
− | if TimeBeforeNewClient > 0 then
| |
− | TimeBeforeNewClient -= 1;
| |
− | if ServeTime > 0 then
| |
− | ServeTime -= 1;
| |
− | end;
| |
− | end.
| |
− | </source>
| |
− | | |
− | <small>Лекция 12</small>
| |
− | | |
− | === Класс Динамический массив ===
| |
− | ''<u>Задача</u>.''
| |
− | :* Реализовать АТД <tt>'''DynArray'''</tt>, который хранит данные одного типа, доступные по индексу;
| |
− | :* Индекс — единственный, целочисленный, нумеруется с нуля;
| |
− | :* В процессе работы программы объекты класса <tt>DynArray</tt> должны автоматически уметь менять размер памяти, отведенной под массив;
| |
− | | |
− | :Уже ясно, что этот АТД — не просто <tt>'''array of''' T</tt>. <br /> Назовем <tt>'''array of''' T</tt> '''''встроенным''' типом динамического массива''.
| |
− | | |
− | ''<u>Уточнение спецификации</u>.''
| |
− | :Будем строить класс '''динамический массив''' на базе встроенного динамического массива.
| |
− | | |
− | :Для автоматического изменения размера при выполнении программы обеспечим следующее поведение:
| |
− | :* под массив выделяется некоторая память размера <tt>Capacity</tt> (''емкость'')
| |
− | :* однако, данная память будет заполнена лишь на <tt>'''Count <= Capacity'''</tt> (*) элементов, где <tt>Count</tt> — количество элементов, ''размер'' массива.
| |
− | | |
− | :Как только, при некоторой операции, неравенство (*) перестает выполняться, то есть <tt>'''Count > Capacity'''</tt>, мы увеличим емкость <tt>Capacity</tt>, сделав её, например, <tt>'''Count * 2'''</tt>.
| |
− | | |
− | :При изменении размера массива все старые данные должны сохраняться.
| |
− | | |
− | :По возможности, необходимо обеспечивать, чтобы емкость массива была немного больше размера для дальнейших расширений.
| |
− | | |
− | <xh4> Реализация ДМ в виде шаблона класса </xh4>
| |
− | <source lang="Delphi">
| |
− | unit Collections;
| |
− |
| |
− | interface
| |
− |
| |
− | uses Nodes;
| |
− |
| |
− | type
| |
− | // Здесь описан шаблон класса Stack
| |
− |
| |
− | // Здесь описан шаблон класса Queue
| |
− | | |
− | const
| |
− | /// Минимальная емкость, устанавливаемая при создании массива
| |
− | MIN_CAP = 4;
| |
− | /// Коэффициент увеличения емкости массива при её нехватке
| |
− | INC_CAP_FACTOR = 2;
| |
− | | |
− | type
| |
− | /// Шаблон класса DynArray [Динамический массив с автоконтролем памяти]
| |
− | DynArray<DataType> = class
| |
− | private
| |
− | /// Встроенный динамический массив, содержащий данные
| |
− | data: array of DataType;
| |
− | /// Размер массива
| |
− | size: integer;
| |
− | /// Емкость массива
| |
− | cap: integer;
| |
− |
| |
− | public
| |
− | /// Создает массив размера pSize
| |
− | constructor Create(pSize: integer := 0);
| |
− |
| |
− | /// Выделяет новую память. Емкость увеличивается до newCap
| |
− | /// (Если newCap меньше текущей емкости, ничего не происходит)
| |
− | procedure Reserve(newCap: integer);
| |
− | /// Устанавливает размер массива равным newSize
| |
− | procedure Resize(newSize: integer);
| |
− |
| |
− | /// Добавляет элемент x в конец массива
| |
− | procedure Add(x: DataType);
| |
− | | |
− | /// Устанавливает элемент с индексом ind равным x
| |
− | procedure SetElem(ind: integer; x: DataType);
| |
− | /// Возвращает элемент массива с индексом ind
| |
− | function GetElem(ind: integer): DataType;
| |
− |
| |
− | /// Возвращает индекс первого элемента массива равного x
| |
− | /// или -1, если такого элемента нет
| |
− | function Find(x: DataType): integer;
| |
− |
| |
− | /// Вставляет в позицию pos элемент x
| |
− | procedure Insert(pos: integer; x: DataType);
| |
− | /// Удаляет элемент из позиции pos
| |
− | procedure Delete(pos: integer);
| |
− | end;
| |
− | | |
− | implementation
| |
− |
| |
− | // Здесь реализованы методы шаблона класса Stack
| |
− | | |
− | // Здесь реализованы методы шаблона класса Queue
| |
− |
| |
− | {Создает массив размера pSize}
| |
− | constructor DynArray<DataType>.Create(pSize: integer);
| |
− | begin
| |
− | size := pSize;
| |
− | cap := INC_CAP_FACTOR*pSize + MIN_CAP; // Устанавливаем емкость "с запасом"
| |
− | SetLength(data, cap);
| |
− | end;
| |
− | | |
− | {Выделяет новую память. Емкость увеличивается до newCap
| |
− | (Если newCap меньше текущей емкости, ничего не происходит)}
| |
− | procedure DynArray<DataType>.Reserve(newCap: integer);
| |
− | begin
| |
− | if newCap > cap then
| |
− | begin
| |
− | SetLength(data, newCap);
| |
− | cap := newCap;
| |
− | end;
| |
− | end;
| |
− | | |
− | {Устанавливает размер массива равным newSize}
| |
− | procedure DynArray<DataType>.Resize(newSize: integer);
| |
− | begin
| |
− | if newSize <= cap then
| |
− | size := newSize
| |
− | else
| |
− | begin
| |
− | Reserve(INC_CAP_FACTOR * newSize);
| |
− | for var i := size to newSize - 1 do // явным образом заполняем новые элементы
| |
− | data[i] := default(DataType);
| |
− | size := newSize;
| |
− | end;
| |
− | end;
| |
− | | |
− | {Добавляет элемент x в конец массива}
| |
− | procedure DynArray<DataType>.Add(x: DataType);
| |
− | begin
| |
− | Resize(size + 1);
| |
− | data[size-1] := x;
| |
− | end;
| |
− | | |
− | {Устанавливает элемент с индексом ind равным x}
| |
− | procedure DynArray<DataType>.SetElem(ind: integer; x: DataType);
| |
− | begin
| |
− | Assert((0 <= ind) and (ind <= size-1));
| |
− | data[ind] := x;
| |
− | end;
| |
− | | |
− | {Возвращает элемент массива с индексом ind}
| |
− | function DynArray<DataType>.GetElem(ind: integer): DataType;
| |
− | begin
| |
− | Assert((0 <= ind) and (ind <= size-1));
| |
− | result := data[ind];
| |
− | end;
| |
− | | |
− | {Возвращает индекс первого элемента массива равного x
| |
− | или -1, если такого элемента нет}
| |
− | function DynArray<DataType>.Find(x: DataType): integer;
| |
− | begin
| |
− | result := -1;
| |
− | for var i := 0 to size - 1 do
| |
− | if data[i] = x then
| |
− | begin
| |
− | result := i;
| |
− | exit;
| |
− | end;
| |
− | end;
| |
− | | |
− | {Вставляет в позицию pos элемент x}
| |
− | procedure DynArray<DataType>.Insert(pos: integer; x: DataType);
| |
− | begin
| |
− | Assert((0 <= pos) and (pos <= size-1));
| |
− | Resize(size + 1);
| |
− | for var i := size - 2 downto pos do
| |
− | data[i+1] := data[i];
| |
− | data[pos] := x;
| |
− | end;
| |
− | | |
− | {Удаляет элемент из позиции pos}
| |
− | procedure DynArray<DataType>.Delete(pos: integer);
| |
− | begin
| |
− | Assert((0 <= pos) and (pos <= size-1));
| |
− | for var i := pos to size - 2 do
| |
− | data[i] := data[i+1];
| |
− | Resize(size - 1);
| |
− | end;
| |
− | | |
− | | |
− | end.
| |
− | </source>
| |
− | | |
− | === Свойства класса ===
| |
− | Создадим объект-динамический массив:
| |
− | <source lang="delphi">
| |
− | var dyn := new DynArray<integer>(5);</source>
| |
− | | |
− | Что делать, если мы хотим увеличить его размер на единицу? <br />
| |
− | Мы можем сделать это только так:
| |
− | <source lang="delphi">
| |
− | dyn.Resize(6);</source>
| |
− | | |
− | '''''Как хотелось бы:''''' <br />
| |
− | <source lang="delphi">
| |
− | dyn.size := dyn.size + 1;</source>
| |
− | | |
− | Однако, мы не можем этого сделать, благодаря '''защите доступа'''. Иначе мы были бы не защищены, например, от присваивания размеру отрицательного(!) значения.
| |
− | | |
− | '''''Как мы сделаем:''''' <br />
| |
− | Станет возможно писать вот так:
| |
− | <source lang="delphi">
| |
− | dyn.Count := dyn.Count + 1;</source>
| |
− | При этом, такой код компилятор будет заменять на следующий:
| |
− | <source lang="delphi">
| |
− | dyn.Resize(dyn.size + 1);</source>
| |
− | | |
− | <tt>Count</tt> — это '''свойство класса''' ('''«интеллектуальное поле»'''). <br />
| |
− | В записи
| |
− | <source lang="delphi">
| |
− | dyn.Count := dyn.Count + 1;</source>
| |
− | справа к <tt>dyn.Count</tt> обеспечивается '''доступ на чтение''', а слева — '''доступ на запись'''. <br />
| |
− | Оба доступа могут быть реализованы специальными методами: метод доступа на ''запись'' называется '''Setter''', а метод доступа на ''чтение'' — '''Getter'''.
| |
− | | |
− | В роли метода доступа на запись для свойства <tt>Count</tt> выступает процедура <tt>Resize</tt>, меняющая значение приватного поля <tt>size</tt>. <br />
| |
− | Вместо метода доступа на чтение можно использовать непосредственно обращение к полю <tt>size</tt>.
| |
− | | |
− | <xh4> Как оформить свойство Count </xh4>
| |
− | В интерфейс класса нужно добавить:
| |
− | <source lang="Delphi">
| |
− | property Count: integer write Resize read size;</source>
| |
− | | |
− | '''Свойство''' — это конструкция языка, позволяющая использовать синтаксис, идентичный обращению к полю класса, но при попытке записи в это поле приводящая к вызову метода-setter'а, а при попытке чтения — getter'а.
| |
− | | |
− | Аналогично можем описать свойство «ёмкость»:
| |
− | <source lang="Delphi">
| |
− | property Capacity: integer read cap write Reserve;</source>
| |
− | | |
− | <xh4> Семантика </xh4>
| |
− | ''Первый вариант:''
| |
− | <source lang="Delphi">
| |
− | property A: PropType read aa write SetA</source>
| |
− | : <tt>aa</tt>: имя поля типа <tt>PropType</tt>
| |
− | : <tt>SetA</tt>: <tt>'''procedure''' SetA(x: PropType)</tt> (процедура с одним параметром типа <tt>PropType</tt>)
| |
− | | |
− | ''Второй вариант:''
| |
− | <source lang="Delphi">
| |
− | property A: PropType read GetA write SetA</source>
| |
− | : <tt>GetA</tt>: <tt>'''function''' GetA: PropType</tt> (функция без параметров, возвращающая значение типа <tt>PropType</tt>)
| |
− | : <tt>SetA</tt>: как и в первом случае, <tt>'''procedure''' SetA(x: PropType)</tt>
| |
− | | |
− | | |
− | '''Замечание.''' Свойства не обладают всеми возможностями полей:
| |
− | * их нельзя передавать как <tt>'''var'''</tt>-параметры;
| |
− | * их нельзя использовать в таких операциях, как <tt>'''+='''</tt>
| |
− | | |
− | === Индексные свойства классов ===
| |
− | Как же будет осуществляться доступ к элементам нашего динамического массива?
| |
− | | |
− | '''''Как хотелось бы:''''' <br />
| |
− | <source lang="Delphi">
| |
− | dyn[3] := dyn[2] + 1; // (1)</source>
| |
− | | |
− | '''''Как мы умеем:''''' <br />
| |
− | <source lang="Delphi">
| |
− | dyn.SetElem(3, dyn.GetElem(2) + 1); // (2)</source>
| |
− | | |
− | Нельзя ли сделать так, чтобы компилятор переводил запись (1) в (2)? <br />
| |
− | Можно.
| |
− | | |
− | '''''Как это сделать:''''' <br />
| |
− | <source lang="Delphi">
| |
− | property Elem[i: integer]: DataType read GetElem write SetElem;</source>
| |
− | | |
− | Теперь можно писать:
| |
− | <source lang="Delphi">
| |
− | dyn.Elem[3] := dyn.Elem[2] + 1;</source>
| |
− | | |
− | А для корректности записи (1) необходимо сделать данное '''индексное свойство''' свойством по умолчанию. Для этого нужно использовать ключевое слово '''<tt>default</tt>''':
| |
− | <source lang="Delphi">
| |
− | property Elem[i: integer]: DataType read GetElem write SetElem; default;</source>
| |
− | | |
− | <xh4> Семантика </xh4>
| |
− | <source lang="Delphi">
| |
− | property Elem[i: IndType]: PropType read GetElem write SetElem</source>
| |
− | : <tt>GetA</tt>: <tt>'''function''' GetElem(i : IndType): PropType</tt> <br />(функция с одним параметром, совпадающим по типу с индексом и возвращающая значение типа <tt>PropType</tt>)
| |
− | : <tt>SetA</tt>: <tt>'''procedure''' SetElem(i: IndType; x: PropType)</tt> <br />(процедура с первым параметром, совпадающим по типу с индексом, и вторым — типа <tt>PropType</tt>)
| |
− | | |
− | {{Hider
| |
− | |title = Реализация ДМ с учетом использования свойств
| |
− | |content =
| |
− | <source lang="Delphi">
| |
− | unit Collections;
| |
− |
| |
− | interface
| |
− |
| |
− | uses Nodes;
| |
− |
| |
− | type
| |
− | // Здесь описан шаблон класса Stack
| |
− |
| |
− | // Здесь описан шаблон класса Queue
| |
− | | |
− | const
| |
− | /// Минимальная емкость, устанавливаемая при создании массива
| |
− | MIN_CAP = 4;
| |
− | /// Коэффициент увеличения емкости массива при её нехватке
| |
− | INC_CAP_FACTOR = 2;
| |
− | | |
− | type
| |
− | /// Шаблон класса DynArray [Динамический массив с автоконтролем памяти]
| |
− | DynArray<DataType> = class
| |
− | private
| |
− | /// Встроенный динамический массив, содержащий данные
| |
− | data: array of DataType;
| |
− | /// Размер массива
| |
− | size: integer;
| |
− | /// Емкость массива
| |
− | cap: integer;
| |
− |
| |
− | /// Устанавливает элемент с индексом ind равным x
| |
− | procedure SetElem(ind: integer; x: DataType);
| |
− | /// Возвращает элемент массива с индексом ind
| |
− | function GetElem(ind: integer): DataType;
| |
− | | |
− | public
| |
− | /// Создает массив размера pSize
| |
− | constructor Create(pSize: integer := 0);
| |
− |
| |
− | /// Выделяет новую память. Емкость увеличивается до newCap
| |
− | /// (Если newCap меньше текущей емкости, ничего не происходит)
| |
− | procedure Reserve(newCap: integer);
| |
− | /// Устанавливает размер массива равным newSize
| |
− | procedure Resize(newSize: integer);
| |
− |
| |
− | /// Добавляет элемент x в конец массива
| |
− | procedure Add(x: DataType);
| |
− |
| |
− | /// Возвращает индекс первого элемента массива равного x
| |
− | /// или -1, если такого элемента нет
| |
− | function Find(x: DataType): integer;
| |
− |
| |
− | /// Вставляет в позицию pos элемент x
| |
− | procedure Insert(pos: integer; x: DataType);
| |
− | /// Удаляет элемент из позиции pos
| |
− | procedure Delete(pos: integer);
| |
− | | |
− | /// Количество элементов (размер) массива
| |
− | property Count: integer read size write Resize;
| |
− | /// Емкость массива (отведенная память)
| |
− | property Capacity: integer read cap write Reserve;
| |
− | /// Позволяет обращаться к элементам массива по индексу
| |
− | /// (например, apples[5])
| |
− | property Elem[index: integer]: DataType read GetElem write SetElem; default;
| |
− | end;
| |
− | | |
− | implementation
| |
− |
| |
− | // Здесь реализованы методы шаблона класса Stack
| |
− | | |
− | // Здесь реализованы методы шаблона класса Queue
| |
− |
| |
− | {Создает массив размера pSize}
| |
− | constructor DynArray<DataType>.Create(pSize: integer);
| |
− | begin
| |
− | size := pSize;
| |
− | cap := INC_CAP_FACTOR*pSize + MIN_CAP; // Устанавливаем емкость "с запасом"
| |
− | SetLength(data, cap);
| |
− | end;
| |
− | | |
− | {Выделяет новую память. Емкость увеличивается до newCap
| |
− | (Если newCap меньше текущей емкости, ничего не происходит)}
| |
− | procedure DynArray<DataType>.Reserve(newCap: integer);
| |
− | begin
| |
− | if newCap > cap then
| |
− | begin
| |
− | SetLength(data, newCap);
| |
− | cap := newCap;
| |
− | end;
| |
− | end;
| |
− | | |
− | {Устанавливает размер массива равным newSize}
| |
− | procedure DynArray<DataType>.Resize(newSize: integer);
| |
− | begin
| |
− | if newSize <= cap then
| |
− | size := newSize
| |
− | else
| |
− | begin
| |
− | Reserve(INC_CAP_FACTOR * newSize);
| |
− | for var i := size to newSize - 1 do // явным образом заполняем новые элементы
| |
− | data[i] := default(DataType);
| |
− | size := newSize;
| |
− | end;
| |
− | end;
| |
− | | |
− | {Добавляет элемент x в конец массива}
| |
− | procedure DynArray<DataType>.Add(x: DataType);
| |
− | begin
| |
− | Resize(size + 1);
| |
− | data[size-1] := x;
| |
− | end;
| |
− | | |
− | {Устанавливает элемент с индексом ind равным x}
| |
− | procedure DynArray<DataType>.SetElem(ind: integer; x: DataType);
| |
− | begin
| |
− | Assert((0 <= ind) and (ind <= size-1));
| |
− | data[ind] := x;
| |
− | end;
| |
− | | |
− | {Возвращает элемент массива с индексом ind}
| |
− | function DynArray<DataType>.GetElem(ind: integer): DataType;
| |
− | begin
| |
− | Assert((0 <= ind) and (ind <= size-1));
| |
− | result := data[ind];
| |
− | end;
| |
− | | |
− | {Возвращает индекс первого элемента массива равного x
| |
− | или -1, если такого элемента нет}
| |
− | function DynArray<DataType>.Find(x: DataType): integer;
| |
− | begin
| |
− | result := -1;
| |
− | for var i := 0 to size - 1 do
| |
− | if data[i] = x then
| |
− | begin
| |
− | result := i;
| |
− | exit;
| |
− | end;
| |
− | end;
| |
− | | |
− | {Вставляет в позицию pos элемент x}
| |
− | procedure DynArray<DataType>.Insert(pos: integer; x: DataType);
| |
− | begin
| |
− | Assert((0 <= pos) and (pos <= size-1));
| |
− | Resize(size + 1);
| |
− | for var i := size - 2 downto pos do
| |
− | data[i+1] := data[i];
| |
− | data[pos] := x;
| |
− | end;
| |
− | | |
− | {Удаляет элемент из позиции pos}
| |
− | procedure DynArray<DataType>.Delete(pos: integer);
| |
− | begin
| |
− | Assert((0 <= pos) and (pos <= size-1));
| |
− | for var i := pos to size - 2 do
| |
− | data[i] := data[i+1];
| |
− | Resize(size - 1);
| |
− | end;
| |
− | | |
− | | |
− | end.
| |
− | </source>}}
| |
− | | |
− | | |
− | <small>Лекция 13</small>
| |
− | | |
− | === Использование классов библиотеки .NET ===
| |
− | Классы ''.NET'' хранятся в специальных внешних ''.dll''.
| |
− | : '''<tt>mscorlib.dll</tt>''' — <br />библиотека в которой содержатся основные классы .NET; <br />подключается к PascalABC.NET автоматически.
| |
− | '''Замечание.''' В .NET все типы являются ''классами''.
| |
− | | |
− | Все классы в библиотеках .NET находятся внутри так называемых '''''пространств имен'''''. <br />
| |
− | Вспомним, что это такое:
| |
− | :'''Пространство имен''' — <br />область программы, в которой не может находиться двух объектов с одинаковыми именами (исключая имена перегруженных подпрограмм).
| |
− | В Pascal'е существует:
| |
− | * ''глобальное'' пространство имен
| |
− | * пространство имен, связанное с ''подпрограммой''
| |
− | * ''классом'' (или ''записью'')
| |
− | * ''модулем''
| |
− | | |
− | В библиотеках .NET дополнительно можно вводить '''''именованные пространства имен''''': <br />
| |
− | '''C#'''
| |
− | <source lang="csharp">
| |
− | namespace System
| |
− | {
| |
− | ...
| |
− | }
| |
− | </source>
| |
− | | |
− | В PascalABC.NET нельзя определять свои пространства имен, но можно пользоваться пространствами имен .NET. <br />
| |
− | Самым важным пространством имен .NET является '''<tt>System</tt>'''.
| |
− | | |
− | Для подключения пространств имен .NET к основной программе используется тот же синтаксис, что и для модулей:
| |
− | <source lang="Delphi">
| |
− | uses System;
| |
− | </source>
| |
− | После того, как пространство имен подключено, можно пользоваться всеми классами внутри этого пространства имен. <br />
| |
− | Например:
| |
− | <source lang="Delphi">
| |
− | uses System;
| |
− | | |
− | var t: DateTime; // класс DateTime определен определен внутри пространства имен System
| |
− | </source>
| |
− | Кроме этого, можно не подключать пространство имен явно, а использовать полное имя класса, предваряя его именем пространства имен:
| |
− | <source lang="Delphi">
| |
− | var t: System.DateTime;
| |
− | </source>
| |
− | | |
− | === Генерация собственных исключений ===
| |
− | '''Замечание.''' В большинстве языков программирования вызовы процедур <tt>Assert</tt> убираются из программного кода компилятором, если компилируется так называемая '''Release''' ('''релиз''') версия.
| |
− | Это делается для скорости выполнения. <br />
| |
− | Т.о. вызовы <tt>Assert</tt>'ов работают только в '''Debug'''-версии (т.е. версии для разработчиков). <br />
| |
− | Однако, и в релиз-версии продукта возможно возникновение ошибок, которые необходимо контролировать. Для этого генерируют собственные исключения.
| |
− | | |
− | Все генерируемые исключения, перехватываемые в блоке
| |
− | '''try'''
| |
− | ...
| |
− | '''except'''
| |
− | ...
| |
− | '''end;'''
| |
− | являются объектами класса '''<tt>System.Exception</tt>'''. <br />
| |
− | В нем находится конструктор, одна из версий которого имеет следующий вид:
| |
− | <source lang="Delphi">constructor(message: string);</source>
| |
− | | |
− | Для генерации собственного исключения используется оператор '''<tt>raise</tt>''':
| |
− | '''raise''' <переменная исключения: System.Exception>
| |
− | Например:
| |
− | <source lang="Delphi">
| |
− | raise new System.Exception('Выход за границы диапазона');
| |
− | </source>
| |
− | | |
− | | |
− | Уточним, как можно модифицировать метод <tt>SetElem</tt> класса [[Основы программирования — второй семестр 08-09; Михалкович С.С.; V часть#Класс Динамический массив|DynArray]]:
| |
− | <source lang="Delphi">
| |
− | ...
| |
− | uses System; // Чтобы писать Exception вместо System.Exception
| |
− | ...
| |
− | | |
− | procedure SetElem(ind: integer; x: DataType);
| |
− | begin
| |
− | if (ind < 0) or (i >= size) then
| |
− | raise new Exception(
| |
− | IntToStr(ind) + ': Выход за границы диапазона [0..' + IntToStr(size - 1) + ']');
| |
− | ...
| |
− | end;
| |
− | </source>
| |
− | | |
− | <xh4> Как обработать свое исключение </xh4>
| |
− | Когда мы генерируем свое исключение, создается переменная <tt>e</tt> — объект класса <tt>System.Exception</tt>. Её то и можно отлавливать в охранном блоке:
| |
− | <source lang="Delphi">
| |
− | try
| |
− | var d := new DynArray<integer<(10);
| |
− | d[10] := 666;
| |
− | except
| |
− | on e: Exception do
| |
− | writeln(e);
| |
− | end;
| |
− | </source>
| |
− | | |
− | === Класс Множество ===
| |
− | <xh4> Интерфейс </xh4>
| |
− | '''Add'''(x: DataType)
| |
− | Добавляет элемент x ко множеству, если его там еще нет
| |
− |
| |
− | '''Remove'''(x: DataType);
| |
− | Удаляет элемент x из множества, если он там есть
| |
− |
| |
− | '''Contains'''(x: DataType): boolean;
| |
− | Возвращает истину, если элемент x содержится во множестве
| |
− | <xh4> Реализация </xh4>
| |
− | Реализуем класс <tt>SimpleSet<DataType></tt> на базе класса <tt>DynArray<DataType></tt>.
| |
− | | |
− | '''Замечание.''' Мы впервые создаем один АТД на базе другого.
| |
− | <br />
| |
− | <source lang="Delphi">
| |
− | unit Collections;
| |
− |
| |
− | interface
| |
− |
| |
− | // Здесь описан шаблон класса Stack
| |
− | // Здесь описан шаблон класса Queue
| |
− | // Здесь описан шаблон класса DynArray
| |
− | | |
− | // ------------------------------------------- SIMPLE_SET -----------------------------------------
| |
− | type
| |
− | /// Шаблон класса SimpleSet [Простое множество]
| |
− | SimpleSet<DataType> = class
| |
− | private
| |
− | /// Элементы множества
| |
− | data := new DynArray<DataType>;
| |
− |
| |
− | public
| |
− | /// <summary>
| |
− | /// Добавляет элемент во множество, если его там еще нет
| |
− | /// </summary>
| |
− | /// <param name="x">Добавляемый элемент</param>
| |
− | procedure Add(x: DataType);
| |
− | /// <summary>
| |
− | /// Удаляет элемент из множества, если он там есть
| |
− | /// </summary>
| |
− | /// <param name="x">Удаляемый элемент</param>
| |
− | procedure Remove(x: DataType);
| |
− |
| |
− | /// <summary>
| |
− | /// Возвращает истину, если множество содержит элемент
| |
− | /// </summary>
| |
− | /// <param name="x">Искомый элемент</param>
| |
− | function Contains(x: DataType): boolean;
| |
− | end;
| |
− |
| |
− |
| |
− | implementation
| |
− | | |
− | // Здесь реализованы методы шаблона класса Stack
| |
− | // Здесь реализованы методы шаблона класса Queue
| |
− | // Здесь реализованы методы шаблона класса DynArray
| |
− |
| |
− | // ------------------------------------------- SIMPLE_SET -----------------------------------------
| |
− |
| |
− | {Добавляет элемент x во множество, если его там еще нет}
| |
− | procedure SimpleSet<DataType>.Add(x: DataType);
| |
− | begin
| |
− | if data.Find(x) = -1 then
| |
− | data.Add(x);
| |
− | end;
| |
− |
| |
− | {Удаляет элемент x из множества, если он там есть}
| |
− | procedure SimpleSet<DataType>.Remove(x: DataType);
| |
− | begin
| |
− | var xPos := data.Find(x);
| |
− | if xPos <> -1 then
| |
− | data.Remove(xPos);
| |
− | end;
| |
− |
| |
− | {Возвращает истину, если множество содержит элемент x}
| |
− | function SimpleSet<DataType>.Contains(x: DataType): boolean;
| |
− | begin
| |
− | result := (data.Find(x) <> -1);
| |
− | end;
| |
− |
| |
− | end.
| |
− | </source>
| |
− | | |
− | | |
− | Если класс для реализации своих методов вызывает методы объекта другого класса, который является полем этого внешнего класса, то такой вызов называется '''делегированием'''.
| |
− | | |
− | Объект класса <tt>SimpleSet<DataType></tt> '''''делегирует''''' выполнение действий своему подобъекту <tt>data</tt>, который и выполняет основные действия. <br />
| |
− | Внешний класс совершает лишь базовые проверки, и его код крайне компактен.
| |
− | | |
− | === АТД и класс Ассоциативный массив ===
| |
− | '''Ассоциативный массив''' — это массив, у которого в качестве индексов могут фигурировать объекты произвольного типа.
| |
− | | |
− | Будем считать, что ассоциативный массив уже реализован. Посмотрим, что с ним можно делать:
| |
− | <source lang="Delphi">
| |
− | uses Collections;
| |
− | | |
− | var Zoo: AssocArray<string, integer>;
| |
− | | |
− | begin
| |
− | Zoo := new AssocArray<string, integer>;
| |
− | | |
− | Zoo['бегемот'] := 2;
| |
− | Zoo['жираф'] := Zoo['жираф'] + 1;
| |
− | write(Zoo['крокодил']);
| |
− | end.
| |
− | </source>
| |
− | | |
− | Ассоциативные массивы реализуются в виде набора параметров
| |
− | (ключ, значение)
| |
− | | |
− | После выполнения нашей программы массив <tt>Zoo</tt> будет иметь вид:
| |
− | ('бегемот', 2)
| |
− | ('жираф', 1)
| |
− | ('крокодил', 0)
| |
− | | |
− | Будем реализовывать наш ассоциативный массив в виде двух динамических массивов — для ключей и для значений.
| |
− | <source lang="Delphi">
| |
− | unit Collections;
| |
− |
| |
− | interface
| |
− |
| |
− | // Здесь описан шаблон класса Stack
| |
− | // Здесь описан шаблон класса Queue
| |
− | // Здесь описан шаблон класса DynArray
| |
− | // Здесь описан шаблон класса SimpleSet
| |
− |
| |
− | // ------------------------------------------- ASSOC_ARRAY ----------------------------------------
| |
− | type
| |
− | /// Шаблон класса AssocArray [Ассоциативный массив]
| |
− | AssocArray<KeyType, ValueType> = class
| |
− | private
| |
− | /// Ключи
| |
− | keys: DynArray<KeyType> := new DynArray<KeyType>;
| |
− | /// Значения, соответствующие ключам
| |
− | values: DynArray<ValueType> := new DynArray<ValueType>;
| |
− |
| |
− | /// Устанавливает значение элемента с ключом key равным value
| |
− | procedure SetElem(key: KeyType; value: ValueType);
| |
− | /// Возвращает значение элемента с ключом key
| |
− | function GetElem(key: KeyType): ValueType;
| |
− |
| |
− | public
| |
− | // --------------------------------- Свойства --------------------------------
| |
− | /// Позволяет обращаться к элементам массива по ключу
| |
− | /// (Например, zoo['крокодил'])
| |
− | property Elem[key: KeyType]: ValueType read GetElem write SetElem; default;
| |
− | end;
| |
− |
| |
− | | |
− | implementation
| |
− |
| |
− | // Здесь реализованы методы шаблона класса Stack
| |
− | // Здесь реализованы методы шаблона класса Queue
| |
− | // Здесь реализованы методы шаблона класса DynArray
| |
− | // Здесь реализованы методы шаблона класса SimpleSet
| |
− | | |
− | // ------------------------------------------- ASSOC_ARRAY ----------------------------------------
| |
− |
| |
− | // ---------------------------- Доступ к элементам ---------------------------
| |
− | {Устанавливает значение элемента с ключом key равным value}
| |
− | procedure AssocArray<KeyType, ValueType>.SetElem(key: KeyType; value: ValueType);
| |
− | begin
| |
− | var ind := Keys.Find(key);
| |
− | if ind <> -1 then
| |
− | Values[ind] := value
| |
− | else
| |
− | begin
| |
− | Keys.Add(key);
| |
− | Values.Add(value);
| |
− | end;
| |
− | end;
| |
− |
| |
− | {Возвращает значение элемента с ключом key}
| |
− | function AssocArray<KeyType, ValueType>.GetElem(key: KeyType): ValueType;
| |
− | begin
| |
− | var ind := Keys.Find(key);
| |
− | if ind <> -1 then
| |
− | result := Values[ind]
| |
− | else
| |
− | begin
| |
− | Keys.Add(key);
| |
− | Values.Add(default(ValueType));
| |
− | result := default(ValueType);
| |
− | end;
| |
− | end;
| |
− | | |
− | end.
| |
− | </source>
| |
− | | |
− | === АТД и класс Список (Linked List) ===
| |
− | ''Структура данных'' '''двусвязный список''' обладает следующими важными преимуществами по сравнению с другими:
| |
− | * список занимает в памяти ровно столько места, каково количество его элементов;
| |
− | * операции вставки и удаления в начало(конец) и середину списка выполняются за время, ''не зависящее от длины списка'';
| |
− | Недостатки:
| |
− | * невозможность обращаться к элементу по индексу (отсутствие ''произвольного'' доступа, только ''последовательный'');
| |
− | | |
− | В задачах, где требуется перебрать элементы от первого до последнего, списки являются хорошим выбором. <br />
| |
− | В задачах, где есть вставка и удаление из середины, списки — незаменимый выбор.
| |
− | | |
− | <xh4> Проблемы при доступе к структуре данных «двусвязный список» </xh4>
| |
− | ''Поля <tt>Next</tt> и <tt>Prev</tt> легко изменить, «испортив» при этом список.''
| |
− | | |
− | '''Способ решения:''' <br />
| |
− | Сделать поля связи доступными только на чтение и разрешить их изменение только строго определенному набору подпрограмм (вставка, удаление). <br />
| |
− | Технически это осуществимо с помощью
| |
− | * классов
| |
− | * защиты доступа
| |
− | * свойств
| |
− | | |
− | '''Замечание.''' В Object Pascal ключевое слово '''<tt>private</tt>''' не распространяется на доступ внутри данного модуля. <br />
| |
− | Это значит, что внутри одного модуля каждый может обращаться к любым приватным полям.
| |
− | | |
− | '''Вывод.''' Связанные классы следует помещать в один модуль.
| |
− | | |
− | Именно так мы и поступим с классами LinkedListNode и LinkedList:
| |
− | <source lang="Delphi">
| |
− | unit LinkedListUnit;
| |
− |
| |
− | interface
| |
− |
| |
− | uses System; // для генерации исключений
| |
− |
| |
− | // ========================================= LinkedListNode =======================================
| |
− | type
| |
− | /// Узел с двумя полями связи
| |
− | LinkedListNode<DataType> = class
| |
− | private
| |
− | // ----------------------------------- Поля ----------------------------------
| |
− | /// Значение узла
| |
− | fData: DataType;
| |
− | /// Ссылка на предыдущий элемент
| |
− | fPrev: LinkedListNode<DataType>;
| |
− | /// Ссылка на следующий элемент
| |
− | fNext: LinkedListNode<DataType>;
| |
− |
| |
− | public
| |
− | // --------------------------------- Свойства --------------------------------
| |
− | /// Значение узла
| |
− | property Value: DataType read fData write fData;
| |
− | /// Ссылка на предыдущий элемент — только на чтение
| |
− | property Prev: LinkedListNode<DataType> read fPrev;
| |
− | /// Ссылка на следующий элемент — только на чтение
| |
− | property Next: LinkedListNode<DataType> read fNext;
| |
− |
| |
− | // ---------------------------- Стандартные методы ---------------------------
| |
− | /// <summary>
| |
− | /// Создает новый узел
| |
− | /// </summary>
| |
− | /// <param name="DataType">Значение узла</param>
| |
− | /// <param name="Prev">Ссылка на предыдущий элемент</param>
| |
− | /// <param name="Next">Ссылка на следующий элемент</param>
| |
− | constructor Create(Data: DataType; Prev, Next: LinkedListNode<DataType>);
| |
− | end;
| |
− |
| |
− |
| |
− | // =========================================== LinkedList =========================================
| |
− | type
| |
− | /// Двусвязный линейный список
| |
− | LinkedList<DataType> = class
| |
− | private
| |
− | /// Первый элемент (голова)
| |
− | fFirst: LinkedListNode<DataType> := nil;
| |
− | /// Последний элемент (хвост)
| |
− | fLast: LinkedListNode<DataType> := nil;
| |
− |
| |
− | public
| |
− | // --------------------------------- Свойства --------------------------------
| |
− | /// Первый элемент (голова) — только на чтение
| |
− | property First: LinkedListNode<DataType> read fFirst;
| |
− | /// Последний элемент (хвост) — только на чтение
| |
− | property Last: LinkedListNode<DataType> read fLast;
| |
− |
| |
− | // ---------------------------- Стандартные методы ---------------------------
| |
− | /// <summary>
| |
− | /// Добавляет элемент x в начало списка
| |
− | /// </summary>
| |
− | /// <param name="x">Добавляемый элемент</param>
| |
− | procedure AddFirst(x: DataType);
| |
− | /// <summary>
| |
− | /// Добавляет элемент x в конец списка
| |
− | /// </summary>
| |
− | /// <param name="x">Добавляемый элемент</param>
| |
− | procedure AddLast(x: DataType);
| |
− |
| |
− | /// Удаляет первый элемент списка
| |
− | procedure RemoveFirst();
| |
− | /// Удаляет последний элемент списка
| |
− | procedure RemoveLast();
| |
− |
| |
− | /// <summary>
| |
− | /// Добавляет элемент x перед node
| |
− | /// </summary>
| |
− | /// <param name="node">Ссылка на элемент, перед которым нужно добавить новый</param>
| |
− | /// <param name="x">Добавляемый элемент</param>
| |
− | procedure AddBefore(node: LinkedListNode<DataType>; x: DataType);
| |
− | /// <summary>
| |
− | /// Добавляет элемент x после node
| |
− | /// </summary>
| |
− | /// <param name="node">Ссылка на элемент, после которого нужно добавить новый</param>
| |
− | /// <param name="x">Добавляемый элемент</param>
| |
− | procedure AddAfter(node: LinkedListNode<DataType>; x: DataType);
| |
− |
| |
− | /// <summary>
| |
− | /// Удаляет элемент node
| |
− | /// </summary>
| |
− | /// <param name="node">Ссылка на элемент, который нужно удалить</param>
| |
− | procedure Remove(node: LinkedListNode<DataType>);
| |
− |
| |
− | // ---------------------------------- Вывод ----------------------------------
| |
− | /// Выводит содержимое списка на консоль
| |
− | procedure Println();
| |
− | /// Выводит содержимое списка на консоль в обратном порядке
| |
− | procedure ReversePrintln();
| |
− | end;
| |
− |
| |
− |
| |
− | implementation
| |
− |
| |
− | // ========================================= LinkedListNode =======================================
| |
− | {Создает новый узел}
| |
− | constructor LinkedListNode<DataType>.Create(Data: DataType; Prev, Next: LinkedListNode<DataType>);
| |
− | begin
| |
− | fData := Data;
| |
− | fPrev := Prev;
| |
− | fNext := Next;
| |
− | end;
| |
− |
| |
− |
| |
− | // =========================================== LinkedList =========================================
| |
− |
| |
− | // ---------------------------- Стандартные методы ---------------------------
| |
− | {Добавляет элемент x в начало списка}
| |
− | procedure LinkedList<DataType>.AddFirst(x: DataType);
| |
− | begin
| |
− | var val := new LinkedListNode<DataType>(x, nil, fFirst);
| |
− | if fFirst <> nil then
| |
− | fFirst.fPrev := val;
| |
− |
| |
− | fFirst := val;
| |
− | if fLast = nil then
| |
− | fLast := fFirst;
| |
− | end;
| |
− |
| |
− | {Добавляет элемент x в конец списка}
| |
− | procedure LinkedList<DataType>.AddLast(x: DataType);
| |
− | begin
| |
− | var val := new LinkedListNode<DataType>(x, fLast, nil);
| |
− | if fLast <> nil then
| |
− | fLast.fNext := val;
| |
− |
| |
− | fLast := val;
| |
− | if fFirst = nil then
| |
− | fFirst := fLast;
| |
− | end;
| |
− |
| |
− | {Удаляет первый элемент списка}
| |
− | procedure LinkedList<DataType>.RemoveFirst();
| |
− | begin
| |
− | if fFirst = nil then
| |
− | raise new Exception(
| |
− | 'Попытка удаления из пустого списка!');
| |
− |
| |
− | fFirst := fFirst.fNext;
| |
− | if fFirst = nil then
| |
− | fLast := nil
| |
− | else
| |
− | fFirst.fPrev := nil;
| |
− | end;
| |
− |
| |
− | {Удаляет последний элемент списка}
| |
− | procedure LinkedList<DataType>.RemoveLast();
| |
− | begin
| |
− | if fLast = nil then
| |
− | raise new Exception(
| |
− | 'Попытка удаления из пустого списка!');
| |
− |
| |
− | fLast := fLast.fPrev;
| |
− | if fLast = nil then
| |
− | fFirst := nil
| |
− | else
| |
− | fLast.fNext := nil;
| |
− | end;
| |
− |
| |
− | {Добавляет элемент x перед node}
| |
− | procedure LinkedList<DataType>.AddBefore(node: LinkedListNode<DataType>; x: DataType);
| |
− | begin
| |
− | if node = nil then
| |
− | raise new Exception(
| |
− | 'Аргумент node метода является нулевой ссылкой!');
| |
− |
| |
− | if node = fFirst then
| |
− | AddFirst(x)
| |
− | else
| |
− | begin
| |
− | var val := new LinkedListNode<DataType>(x, node.fPrev, node);
| |
− | node.fPrev.fNext := val;
| |
− | node.fPrev := val;
| |
− | end;
| |
− | end;
| |
− |
| |
− | {Добавляет элемент x после node}
| |
− | procedure LinkedList<DataType>.AddAfter(node: LinkedListNode<DataType>; x: DataType);
| |
− | begin
| |
− | if node = nil then
| |
− | raise new Exception(
| |
− | 'Аргумент node метода является нулевой ссылкой!');
| |
− |
| |
− | if node = fLast then
| |
− | AddLast(x)
| |
− | else
| |
− | begin
| |
− | var val := new LinkedListNode<DataType>(x, node, node.fNext);
| |
− | node.fNext.fPrev := val;
| |
− | node.fNext := val;
| |
− | end;
| |
− | end;
| |
− |
| |
− | {Удаляет элемент node}
| |
− | procedure LinkedList<DataType>.Remove(node: LinkedListNode<DataType>);
| |
− | begin
| |
− | if node = nil then
| |
− | raise new Exception(
| |
− | 'Аргумент node метода является нулевой ссылкой!');
| |
− |
| |
− | if node = fFirst then
| |
− | RemoveFirst
| |
− | else if node = fLast then
| |
− | RemoveLast
| |
− | else
| |
− | begin
| |
− | node.fPrev.fNext := node.fNext;
| |
− | node.fNext.fPrev := node.fPrev;
| |
− | end;
| |
− | end;
| |
− |
| |
− | // ---------------------------------- Вывод ----------------------------------
| |
− | {Выводит содержимое списка на консоль}
| |
− | procedure LinkedList<DataType>.Println();
| |
− | begin
| |
− | var cur := fFirst;
| |
− | while cur <> nil do
| |
− | begin
| |
− | write(cur.Value, ' ');
| |
− | cur := cur.Next;
| |
− | end;
| |
− | writeln();
| |
− | end;
| |
− |
| |
− | {Выводит содержимое списка на консоль в обратном порядке}
| |
− | procedure LinkedList<DataType>.ReversePrintln();
| |
− | begin
| |
− | var cur := fLast;
| |
− | while cur <> nil do
| |
− | begin
| |
− | write(cur.Value, ' ');
| |
− | cur :=cur.Prev;
| |
− | end;
| |
− | writeln();
| |
− | end;
| |
− |
| |
− | end.
| |
− | </source>
| |
− | | |
− | | |
− | ''<u>Пример 1</u>.'' Проход по списку.
| |
− | <source lang="Delphi">
| |
− | var l: LinkedList<integer> := new LinkedList<integer>;
| |
− | l.AddLast(1100);
| |
− | l.AddLast(1300);
| |
− |
| |
− | var node := l.First;
| |
− | while node <> nil do
| |
− | begin
| |
− | node.Value := node.Value * 2;
| |
− | node := node.Next;
| |
− | end;
| |
− | </source>
| |
− | | |
− | ===Основные контейнерные классы библиотеки .NET===
| |
− | | |
− | Списки .NET, итерация по списку, понятие итератора
| |
− | | |
− | Перегрузка операций
| |
До сих пор мы сталкивались с конкретными типами данных, которые характеризуются:
А теперь рассмотрим пример абстрактного типа данных — стек.
Мы уже знакомы со стеком. Хорошими примерами могут служить программный стек, колода карт или магазин автомата.
Т.о. стек следует представлять как стопку объектов, положенных один на другой. В каждый момент можно:
Причем, если предмет последним положили на вершину стопки, то он будет снят первым - отсюда и название LIFO.
Описывать стек будем в виде класса.
В результате работы этого алгоритма на стеке останется единственное число, являющееся значением выражения.
Запрограммируем этот алгоритм.
Пусть класс Stack определен в модуле Collections.
Код клиентской программы:
При таком способе разделения обязанностей обычно используется следующий сценарий: