|
|
| (не показаны 3 промежуточные версии этого же участника) |
| Строка 424: |
Строка 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.
Код клиентской программы:
При таком способе разделения обязанностей обычно используется следующий сценарий:
