САОД кафедра ОСУ 1 Основные абстрактные типы данных Схема процесса создания программ для решения прикладных задач ВУ

САОД кафедра ОСУ 2 Основные абстрактные типы данных Определение1: Абстрактный тип данных (АТД) - некоторая математическая модель с совокупностью операторов, определенных в рамках этой модели. Например: множество целых чисел с операторами объединения, пересечения и разности множеств.

САОД кафедра ОСУ 3 Основные абстрактные типы данных Определение 2: Абстрактный тип данных (АТД) это тип данных (набор значений и совокупность операций для этих значений), доступ к которому осуществляется только через интерфейс.

САОД кафедра ОСУ 4 Основные абстрактные типы данных: списки В математике список представляет собой последовательность элементов определенного типа. Список представляется в виде последовательности элементов: a 1,a 2, a 3,…,a n все а i имеют один тип. Количество элементов п будем называть длиной списка. Если п 1, то a 1 называется первым элементом, а a n последним элементом списка. В случае n=0 имеем пустой список, который не содержит элементов.

САОД кафедра ОСУ 5 Основные абстрактные типы данных: списки Постулируем существование позиции, следующей за последним элементом списка. Функция END( L) будет возвращать позицию, следующую за позицией n в n-элементном списке L. Позиция END (L), рассматриваемая как расстояние от начала списка, может изменяться при увеличении или уменьшении списка

САОД кафедра ОСУ 6 Основные абстрактные типы данных: списки INSERT(x, р, L) Этот оператор вставляет объект х в позицию р в списке L, перемещая элементы от позиции р и далее в следующую, более высокую позицию. Если список L состоит из элементов a 1,a 2, a 3,…,a n то после выполнения этого оператора он будет иметь вид a 1,a 2, a 3,a p-1,x,a p …,a n Если р принимает значение END(L), то будем иметь a 1,a 2, a 3,…,a n,, х. Если в списке L нет позиции р, то результат выполнения этого оператора не определен.

САОД кафедра ОСУ 7 Основные абстрактные типы данных: списки LOCATE(x, L) Функция возвращает позицию объекта х в списке L. Если в списке объект х встречается несколько раз, то возвращается позиция первого от начала списка объекта х. Если объекта х нет в списке L, то возвращается END(L).

САОД кафедра ОСУ 8 Основные абстрактные типы данных: списки RETRIEVE(p, L) Эта функция возвращает элемент, который стоит в позиции р в списке L. Результат не определен, если р = END(L) или в списке L нет позиции р. Отметим, что элементы должны быть того типа, который в принципе может возвращать функция. Однако на практике мы всегда можем изменить эту функцию так, что она будет возвращать указатель на объект типа elementtype.

САОД кафедра ОСУ 9 Основные абстрактные типы данных: списки DELETE(p, L) Этот оператор удаляет элемент в позиции р списка L. если список L состоит из элементов a 1,a 2, a 3,…,a n то после выполнения этого оператора он будет иметь вид a 1,a 2, a 3,…a p-1, a p+1 …,a n Результат не определен, если в списке L нет позиции р или р = END(L).

САОД кафедра ОСУ 10 Основные абстрактные типы данных: списки NEXT(p, L) и PREVIOUS(p, L). Функции возвращают соответственно следующую и предыдущую позиции от позиции р в списке L. Если р последняя позиция в списке L, то NEXT(p, L) = END(L). Функция NEXT не определена, когда р = END(L). Функция PREVIOUS не определена, если р = 1. Обе функции не определены, если в списке L нет позиции р.

САОД кафедра ОСУ 11 Основные абстрактные типы данных: списки MAKENULL(L) Эта функция делает список L пустым и возвращает позицию END(L).

САОД кафедра ОСУ 12 Основные абстрактные типы данных: списки FIRST(L) Эта функция возвращает первую позицию в списке L. Если список пустой, то возвращается позиция END(L).

САОД кафедра ОСУ 13 Основные абстрактные типы данных: списки PRINTLIST(L) Печатает элементы списка L в порядке из расположения.

САОД кафедра ОСУ 14 Реализация списков Представление списка с помощью массива Первый элемент Второй элемент Последний элемент 1 2 список свободный last maxlenght

САОД кафедра ОСУ 15 Реализация списков Const maxl = 1000; Type List = record elements: array[1..maxl] of eltype; last: integer end; position = integer;

САОД кафедра ОСУ 16 Реализация списков Function EndL (var L:List) : position; begin EndL := L.last+1 end;

САОД кафедра ОСУ 17 procedure INSERTL (x: eltype; р: position; var L: LIST ); { вставляет элемент х в позицию р в списке L } var q : position; begin if L.last >= maxlength then Writeln (Список полон') else if (р > L.last + 1) or (р < 1) then Writeln ('Такой позиции не существует') else begin

САОД кафедра ОСУ 18 for q:= L.last downto p do {перемещение элементов на одну позицию к концу списка } L.elements[q+l]:= L.elements[q]; L.last:= L.last + 1; L.elements[p]:= x end end; { INSERT }

САОД кафедра ОСУ 19 procedure DELETEL ( p: position; var L: LIST ) ; {удаляет элемент в позиции р списка L } var q: position; begin if (p > L.last) or (p < 1) then Writeln ('Такой позиции не существует') else

САОД кафедра ОСУ 20 begin L.last:= L.last – 1; for q:= p to L.last do { перемещение элементов из позиций р+1, р+2,... на одну позицию к началу списка } L.elements[q] := L.elements [q+1] end end; { DELETE }

САОД кафедра ОСУ 21 function LOCATE ( x:eltype; L: LIST ): position; { возвращает позицию элемента x в списке L } var q: position; begin for q:= 1 to L.last do if L.elements[q] = x then begin Locate := q; Exit (LOCATE) end else Locate := L.last+1 {х не найден } end; { LOCATE }

САОД кафедра ОСУ 22 Коллекции Класс ArrayList – динамический массив объектов (ссылок). Расширяет класс AbstractList и реализует интерфейс List. Класс имеет конструкторы: ArrayList() ArrayList(Collection c) ArrayList(int capacity)

САОД кафедра ОСУ 23 Коллекции Плюсы: Быстрый доступ по индексу Быстрая вставка и удаление краевых элементов Минусы: Медленная вставка и удаление элементов

САОД кафедра ОСУ 24 Коллекции Методы класса ArrayList void add(int index, Object obj) – вставляет obj в позицию, указанную в index; void addAll(int index, Collection c) – вставляет в вызывающий список все элементы коллекции с, начиная с позиции index; Object get(int index) – возвращает элемент в виде объекта из позиции index; int indexOf(Object ob) – возвращает индекс указанного объекта; Object remove(int index) – удаляет объект из позиции index.

САОД кафедра ОСУ 25 Коллекции /* пример: работа со списком : DemoList1.java */ import java.util.*; public class DemoList1 { public static void main(String[] args) { List c = new ArrayList(); //Collection c = new ArrayList(); int i = 2, j = 5; c.add(new Integer(i)); c.add(new Boolean("True"));

САОД кафедра ОСУ 26 Коллекции c.add(" "); c.add(2, Integer.toString(j) + "X"); //добавить во 2 позицию 5 System.out.println(c); if (c.contains("5X")) c.remove(c.indexOf("5X")); System.out.println(c); } }

САОД кафедра ОСУ 27 Коллекции на консоль будет выведено: [2, true, 5X, ] [2, true, ]