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

Основные абстрактные типы данных

• Схема процесса создания программ для решения прикладных задач

Основные абстрактные типы данных

• Определение1:

• Абстрактный тип данных (АТД) -

• некоторая математическая модель с

• совокупностью операторов, определенных

• в рамках этой модели.

• Например: множество целых чисел с

• операторами объединения, пересечения и

• разности множеств.

Основные абстрактные типы данных

• Определение 2:

• Абстрактный тип данных (АТД) — это

• тип данных (набор значений и

• совокупность операций для этих значений),

• доступ к которому осуществляется только

• через интерфейс.

Основные абстрактные типы данных: списки

• В математике список представляет собой последовательность элементов определенного типа.

• Список представляется в виде последовательности элементов: a1 ,a2, a3,…,an все аi имеют один тип.

• Количество элементов п будем называть длиной списка. Если п  1, то a1 называется первым элементом, а an — последним элементом списка.

• В случае n=0 имеем пустой список, который не содержит элементов.

Основные абстрактные типы данных: списки

• Постулируем существование позиции, следующей за последним элементом списка.

• Функция END(L) будет возвращать позицию, следующую за позицией n в n-элементном списке L.

• Позиция END(L), рассматриваемая как расстояние от начала списка, может изменяться при увеличении или уменьшении списка

Основные абстрактные типы данных: списки

• INSERT(x, р, L)

• Этот оператор вставляет объект х в позицию р в списке L, перемещая элементы от позиции р и далее в следующую, более высокую позицию. Если список L состоит из элементов

• a1 ,a2, a3 ,…,an

• то после выполнения этого оператора он будет иметь вид a1 ,a2 , a3 ,ap-1,x,ap…,an

• Если р принимает значение END(L), то будем иметь a1 ,a2, a3,…,an,, х.

• Если в списке L нет позиции р, то результат выполнения этого оператора не определен.

Основные абстрактные типы данных: списки

• LOCATE(x, L)

• Функция возвращает позицию объекта х в списке L.

• Если в списке объект х встречается несколько раз, то возвращается позиция первого от начала списка объекта х.

• Если объекта х нет в списке L, то возвращается END(L).

Основные абстрактные типы данных: списки

• RETRIEVE(p, L)

• Эта функция возвращает элемент, который стоит в позиции р в списке L.

• Результат не определен, если р = END(L)

• или в списке L нет позиции р.

• Отметим, что элементы должны быть того типа, который в принципе может возвращать функция. Однако на практике мы всегда можем изменить эту функцию так, что она будет возвращать указатель на объект типа elementtype.

Основные абстрактные типы данных: списки

• DELETE(p, L)

• Этот оператор удаляет элемент в позиции р списка L.

• если список L состоит из элементов a1 ,a2, a3,…,an то после выполнения этого оператора он будет иметь вид

• a1 ,a2 , a3 ,…ap-1, ap+1…,an

• Результат не определен, если в списке L нет позиции р или р = END(L).

Основные абстрактные типы данных: списки

• NEXT(p, L) и PREVIOUS(p, L).

• Функции возвращают соответственно следующую и предыдущую позиции от позиции р в списке L. Если р — последняя позиция в списке L, то NEXT(p, L) = END(L).

• Функция NEXT не определена, когда р = END(L).

• Функция PREVIOUS не определена, если р = 1.

• Обе функции не определены, если в списке L нет позиции р.

Основные абстрактные типы данных: списки

• MAKENULL(L)

• Эта функция делает список L пустым и возвращает позицию END(L).

Основные абстрактные типы данных: списки

• FIRST(L)

• Эта функция возвращает первую позицию в списке L.

• Если список пустой, то возвращается позиция END(L).

Основные абстрактные типы данных: списки

• PRINTLIST(L)

• Печатает элементы списка L в порядке из расположения.

Реализация списков

• Представление списка с помощью массива

Реализация списков

• Const maxl = 1000;

• Type

• List = record

• elements: array[1..maxl] of eltype;

• last: integer

• end;

• position = integer;

Реализация списков

• Function EndL (var L:List) : position;

• begin

• EndL := L.last+1

• end;

• 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

• 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 }

• procedure DELETEL ( p: position; var L: LIST ) ;

• {удаляет элемент в позиции р списка L }

• var

• q: position;

• begin

• if (p > L.last) or (p < 1)

• then

• Writeln ('Такой позиции не существует')

• else

• 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 }

• 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 }

Коллекции

• Класс ArrayList – динамический массив объектов (ссылок).

• Расширяет класс AbstractList и реализует интерфейс List.

• Класс имеет конструкторы:

• ArrayList()

• ArrayList(Collection c)

• ArrayList(int capacity)

Коллекции

• Плюсы:

• Быстрый доступ по индексу

• Быстрая вставка и удаление краевых

• элементов

• Минусы:

• Медленная вставка и удаление

• элементов

Коллекции

• Методы класса 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.

Коллекции

• /* пример: работа со списком : 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"));

Коллекции

• 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);

• }

• }

Коллекции

• на консоль будет выведено:

• [2, true, 5X, ]

• [2, true, ]