|
|
(не показано 8 промежуточных версий 3 участников) |
Строка 1: |
Строка 1: |
− | [[Категория:Конспекты]] | + | [[Категория:Основы программирования]] |
− | == АТД — Абстрактные Типы Данных == | + | == АТД — Абстрактные Типы Данных. Классы как реализация АТД == |
| === Что мы знаем о классах === | | === Что мы знаем о классах === |
| # Класс — это составной тип данных | | # Класс — это составной тип данных |
Строка 26: |
Строка 26: |
| Более того, реализацию в классе принято ''скрывать'' от клиента специальными конструкциями. <br /> | | Более того, реализацию в классе принято ''скрывать'' от клиента специальными конструкциями. <br /> |
| Этот принцип называется '''''принципом сокрытия реализации''''' (или '''''защитой доступа'''''). | | Этот принцип называется '''''принципом сокрытия реализации''''' (или '''''защитой доступа'''''). |
− |
| |
− | Кроме того, с классами тесно связано понятие ''инкапсуляции'':
| |
− | :'''Инкапсуляция''' — хранение в классе одновременно данных и методов (класс представляет собой «капсулу»). <br />Инкапсуляция тесно связана с защитой данных: лишь некоторые члены в этой «капсуле» являются открытыми.
| |
| | | |
| А теперь рассмотрим пример абстрактного типа данных — стек. | | А теперь рассмотрим пример абстрактного типа данных — стек. |
Строка 427: |
Строка 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>
| |
− | | |
− | === Класс Динамический массив ===
| |
− | ''<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>
| |
− | | |
− | ''<u>Пример 2</u>.'' <br />
| |
− | Наполнить список целых случайными элементами. <br />
| |
− | Удалить все элементы с четными номерами (нумерация с единицы).
| |
− | <source lang="Delphi">
| |
− | uses LinkedListUnit;
| |
− | | |
− | const
| |
− | MAX_RAN = 200;
| |
− |
| |
− | /// Возвращает список из n случайных целых чисел
| |
− | /// в диапазоне [-MAX_RAN, MAX_RAN]
| |
− | function CreateRandomLinkedList(n: integer): LinkedList<integer>;
| |
− | begin
| |
− | result := new LinkedList<integer>;
| |
− | for var i := 1 to n do
| |
− | result.AddLast(Random(-MAX_RAN, MAX_RAN));
| |
− | end;
| |
− | | |
− | /// Удаляет из списка list все элементы с четными номерами
| |
− | /// (элементы нумеруются с 1цы)
| |
− | procedure RemoveEvenNumbers(list: LinkedList<integer>);
| |
− | begin
| |
− | var cur := list.First;
| |
− | var i := 1;
| |
− | while cur <> nil do
| |
− | begin
| |
− | if (i mod 2 = 0) then
| |
− | list.Remove(cur);
| |
− | cur := cur.Next;
| |
− | i += 1;
| |
− | end;
| |
− | end;
| |
− | | |
− | begin
| |
− | var l := CreateRandomLinkedList(15);
| |
− | l.Println;
| |
− |
| |
− | RemoveEvenNumbers(l);
| |
− | writeln('Список после удаления элементов с четными номерами:');
| |
− | l.Println;
| |
− | end.
| |
− | </source>
| |
− | | |
− | == Стандартные контейнерные классы библиотеки .NET и пространство имен System.Collections.Generic ==
| |
− | В пространстве имен '''System.Collections.Generic''' находятся все основные стандартные ''контейнерные'' классы библиотеки '''.NET''':
| |
− | * ''<tt>Stack<T></tt>''
| |
− | * ''<tt>Queue<T></tt>''
| |
− | | |
− | * ''<tt>List<T></tt>'' — динамический массив
| |
− | | |
− | * ''<tt>LinkedList<T></tt>'' — класс двусвязного линейного списка
| |
− | * ''<tt>LinkedListNode<T></tt>''
| |
− | | |
− | * ''<tt>Dictionary<Key, Value></tt>'' — ассоциативный массив на базе ''хэш-таблицы'' (самые быстрые поиск и добавление, ключи не сортированы, неэкономичный по памяти)
| |
− | * ''<tt>SortedDictionary<Key, Value></tt>'' — ассоциативный массив на базе ''БДП''
| |
− | * ''<tt>SortedList<Key, Value></tt>'' — ассоциативный массив на базе ''динамического массива''
| |
− | | |
− | === Интерфейсы стандартных контейнерных классов .NET ===
| |
− | '''<tt>Stack<T></tt>'''
| |
− | <source lang="Pascal"> Push(x: T);
| |
− | Pop: T;
| |
− | Peek: T;
| |
− | Clear;
| |
− | ToString: string;
| |
− | property Count: integer;</source>
| |
− | | |
− | '''<tt>Queue<T></tt>'''
| |
− | <source lang="Pascal"> Enqueue(x: T);
| |
− | Dequeue: T;
| |
− | Peek: T;
| |
− | Clear;
| |
− | ToString: string;
| |
− | property Count: integer;</source>
| |
− | | |
− | '''<tt>List<T></tt>'''
| |
− | <source lang="Pascal"> Add(x: T);
| |
− | Clear;
| |
− | Contains(x: T): boolean;
| |
− | IndexOf(x: T): integer;
| |
− | Insert(ind: integer; x: T);
| |
− | LastIndexOf(x: T): integer;
| |
− | Remove(x: T): boolean;
| |
− | RemoveAt(ind: integer);
| |
− | RemoveRange(ind,count: integer);
| |
− | Reverse();
| |
− | Reverse(from,count: integer);
| |
− | Sort();
| |
− | ToString: string;
| |
− | property Count: integer;
| |
− | property Capacity: integer;
| |
− | property Item[ind: integer]: T;
| |
− | Find(function(x: T): boolean): T;
| |
− | FindIndex(function(x: T): boolean): integer;
| |
− | FindAll(function(x: T): boolean): List<T>;
| |
− | ForEach(procedure (x: T));
| |
− | RemoveAll(function(x: T): boolean);
| |
− | TrueForAll(function(x: T): boolean): boolean;</source>
| |
− | | |
− | '''<tt>LinkedListNode<T></tt>'''
| |
− | <source lang="Pascal"> property Next: LinkedListNode<T> read
| |
− | property Prev: LinkedListNode<T> read
| |
− | property Value: T read write
| |
− | </source>
| |
− | | |
− | '''<tt>LinkedList<T></tt>'''
| |
− | <source lang="Pascal"> AddFirst(x: T);
| |
− | AddLast(x: T);
| |
− | AddAfter(n: LinkedListNode<T>; x: T);
| |
− | AddBefore(n: LinkedListNode<T>; x: T);
| |
− | Clear;
| |
− | Contains(x: T): boolean;
| |
− | Find(x: T): LinkedListNode<T>;
| |
− | FindLast(x: T): LinkedListNode<T>;
| |
− | Remove(LinkedListNode<T>);
| |
− | RemoveFirst;
| |
− | RemoveLast;
| |
− | ToString: string;
| |
− | property Count: integer;
| |
− | property First: LinkedListNode<T>;
| |
− | property Last: LinkedListNode<T>;
| |
− | </source>
| |
− | | |
− | '''<tt>Dictionary<Key, Value>, SortedDictionary<Key, Value>, SortedList<Key, Value></tt>'''
| |
− | <source lang="Pascal"> Add(k: Key; v: Value);
| |
− | Clear;
| |
− | ContainsKey(k: Key): boolean;
| |
− | ContainsValue(v: Value): boolean;
| |
− | Remove(k: Key): boolean;
| |
− | TryGetValue(k: Key; var v: Value): boolean;
| |
− | ToString: string;
| |
− | property Count: integer;
| |
− | property Item[k: Key]: Value;
| |
− | </source>
| |
− | | |
− | === Примеры использования ===
| |
− | ''<u>Пример 1</u>.'' '''''Foreach по контейнерам.'''''
| |
− | <source lang="Delphi">
| |
− | uses System.Collections.Generic;
| |
− | | |
− | begin
| |
− | // Стек
| |
− | var s := new Stack<integer>;
| |
− | s.Push(1);
| |
− | s.Push(3);
| |
− | s.Push(5);
| |
− |
| |
− | foreach i: integer in s do
| |
− | write(i, ' ');
| |
− | writeln();
| |
− |
| |
− | // Очередь
| |
− | var q := new Queue<integer>;
| |
− | q.Enqueue(1);
| |
− | q.Enqueue(3);
| |
− | q.Enqueue(5);
| |
− |
| |
− | foreach i: integer in q do
| |
− | write(i, ' ');
| |
− | writeln();
| |
− |
| |
− | // Динамический массив
| |
− | var l := new List<integer>;
| |
− | l.Add(1);
| |
− | l.Add(3);
| |
− | l.Add(5);
| |
− |
| |
− | foreach i: integer in l do
| |
− | write(i, ' ');
| |
− | writeln();
| |
− |
| |
− | // Ассоциативный массив
| |
− | var m := new SortedDictionary<string, integer>;
| |
− | m['Крокодил'] := 3;
| |
− | m.Add('Бегемот', 2);
| |
− |
| |
− | {В отличие от «нашего» ассоциативного массива, в .NET:
| |
− | если ключа в ассоциативном массиве нет, то геттер
| |
− | для индексного свойства сгенерирует исключение,
| |
− | а сеттер добавит соответствующую пару.
| |
− | Поэтому строка:
| |
− | m['Обезьяна'] := m['Кашалот'] + 1;
| |
− | вызовет исключение.
| |
− | Чтобы этого не случилось, выполним проверку:}
| |
− |
| |
− | if m.ContainsKey('Кашалот') then
| |
− | m['Обезьяна'] := m['Кашалот'] + 1;
| |
− |
| |
− | foreach k: KeyValuePair<string, integer> in m do
| |
− | writeln(k.Key, ' ', k.Value);
| |
− | end.
| |
− | </source>
| |
− | | |
− | ''<u>Пример 2</u>.'' '''''Частотный словарь слов в файле.'''''
| |
− | <source lang="Delphi">
| |
− | uses System.Collections.Generic, System;
| |
− | | |
− | var
| |
− | // частотный словарь
| |
− | m := new SortedDictionary<string, integer>;
| |
− | f: TextFile;
| |
− | | |
− | begin
| |
− | Assign(f, 'a.txt');
| |
− | Reset(f);
| |
− |
| |
− | try
| |
− | while not Eof(f) do
| |
− | begin
| |
− | var s: string;
| |
− | readln(f, s);
| |
− |
| |
− | // разделители слов в тексте
| |
− | var delims: array of char := (' ', '.', ',', ':', ';', '!', '?', '-', '"', '(', ')');
| |
− | // слова строки s
| |
− | var words: array of string := s.Split(
| |
− | delims,
| |
− | // не включает в массив слов пустые
| |
− | StringSplitOptions.RemoveEmptyEntries);
| |
− |
| |
− | foreach w: string in words do
| |
− | if m.ContainsKey(w) then
| |
− | m[w] := m[w] + 1
| |
− | else
| |
− | m.Add(w, 1);
| |
− | end;
| |
− | finally
| |
− | Close(f);
| |
− | end;
| |
− |
| |
− | foreach k: KeyValuePair<string, integer> in m do
| |
− | writeln(k.Key, ' ', k.Value);
| |
− | end.
| |
− | </source>
| |
− | | |
− | ''<u>Пример 3</u>.'' <br />
| |
− | Дан массив чисел. <br />
| |
− | Вывести все четные в прямом порядке, а все нечетные в обратном.
| |
− | <source lang="Delphi">
| |
− | uses System.Collections.Generic;
| |
− | | |
− | function Even(x: integer): boolean;
| |
− | begin
| |
− | result := (x mod 2 = 0);
| |
− | end;
| |
− | | |
− | begin
| |
− | var l := new List<integer>;
| |
− | l.Add(3);
| |
− | l.Add(4);
| |
− | l.Add(5);
| |
− | l.Add(6);
| |
− |
| |
− | var evenElems: List<integer> := l.FindAll(Even);
| |
− |
| |
− | l.RemoveAll(Even);
| |
− | l.Reverse;
| |
− |
| |
− | foreach i: integer in evenElems do
| |
− | write(i, ' ');
| |
− | writeln();
| |
− | foreach i: integer in l do
| |
− | write(i, ' ');
| |
− | end.
| |
− | </source>
| |
− | | |
− | Функция <tt>l.'''FindAll'''(predicate: function(x: T): boolean)</tt> возвращает список, состоящий из элементов списка <tt>l</tt> типа <tt>T</tt>, удовлетворяющих условию <tt>predicate</tt>. <br />
| |
− | Процедура <tt>l.'''RemoveAll'''(predicate: function(x: T): boolean)</tt> удаляет элементы списка <tt>l</tt> типа <tt>T</tt>, удовлетворяющие условию <tt>predicate</tt>.
| |
− | | |
− | ''<u>Пример 4</u>.'' '''''Многоступенчатая фильтрация.'''''
| |
− | <source lang="Delphi">
| |
− | function Less7(x: integer): boolean;
| |
− | begin
| |
− | result := (x < 7);
| |
− | end;
| |
− | | |
− | l := l.FindAll(Even).FindAll(Less7);
| |
− | </source>
| |
− | | |
− | ''<u>Пример 5</u>.'' '''''Использование процедурных переменных, хранящих ссылки на методы объектов класса.''''' <br />
| |
− | Что делать, если, например, нужно фильтровать элементы по значению, которое определяется во время выполнения программы?
| |
− | | |
− | Использовать функцию
| |
− | <source lang="Delphi">function Less(x, maxValue: integer): boolean;</source>
| |
− | мы не можем, т.к. предикат функции <tt>FindAll</tt> должен быть типа
| |
− | <source lang="Delphi">type CompType = function(x: integer): boolean;</source>
| |
− | | |
− | Может быть сделать ''глобальную''(!) переменную, с которой и сравнивать <tt>x</tt> в функции <tt>Less</tt>, меняя её значение? <br />
| |
− | Нет, это очень плохое решение!
| |
− | | |
− | Есть другое решение. <br />
| |
− | Опишем класс, полем которого будет значение, с которым нужно сравнивать <tt>x</tt>, а методом — собственно функция сравнения:
| |
− | <source lang="Delphi">
| |
− | type
| |
− | Selector = class
| |
− | a: integer := 7;
| |
− |
| |
− | function Less(x: integer): boolean;
| |
− | begin
| |
− | result := (x < a);
| |
− | end;
| |
− | end;
| |
− | | |
− | CompType = function(x: integer): boolean;
| |
− | | |
− | var
| |
− | c: CompType;
| |
− | | |
− | ...
| |
− | | |
− | var s := new Selector;
| |
− | c := s.Less;
| |
− | | |
− | writeln(c(5));
| |
− | </source>
| |
− | | |
− | '''Правило.''' Процедурным переменным можно присваивать не только внешние подпрограммы, но и методы классов с соответствующими переменными. <br />
| |
− | Поскольку важно, какой объект вызывает метод этого класса, то присваивание осуществляется в виде:
| |
− | <имя объекта>.<имя метода>
| |
− | При этом, в процедурной переменной <tt>c</tt> по существу запоминаются два значения: ''объект'', вызывающий метод, и ''ссылка на метод'', вызывающийся объектом.
| |
− | | |
− | '''Примечание.''' Код
| |
− | <source lang="Delphi">writeln(c(5));</source>
| |
− | компилятор заменит на
| |
− | <source lang="Delphi">writeln(s.Less(5));</source>
| |
− | | |
− | Используем теперь эту возможность для фильтрации:
| |
− | <source lang="Delphi">
| |
− | var l := new List<integer>;
| |
− | // наполнение l
| |
− | s.a := 9;
| |
− | var ll := l.FindAll(s.Less);
| |
− | </source>
| |
− | | |
− | Списки .NET, итерация по списку, понятие итератора
| |
− | | |
− | Перегрузка операций
| |
До сих пор мы сталкивались с конкретными типами данных, которые характеризуются:
А теперь рассмотрим пример абстрактного типа данных — стек.
Мы уже знакомы со стеком. Хорошими примерами могут служить программный стек, колода карт или магазин автомата.
Т.о. стек следует представлять как стопку объектов, положенных один на другой. В каждый момент можно:
Причем, если предмет последним положили на вершину стопки, то он будет снят первым - отсюда и название LIFO.
Описывать стек будем в виде класса.
В результате работы этого алгоритма на стеке останется единственное число, являющееся значением выражения.
Запрограммируем этот алгоритм.
Пусть класс Stack определен в модуле Collections.
Код клиентской программы:
При таком способе разделения обязанностей обычно используется следующий сценарий: