Слайд 2
![Операции над абстрактным списком: Создать пустой список Уничтожить список Определить,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/225775/slide-1.jpg)
Операции над абстрактным списком:
Создать пустой список
Уничтожить список
Определить, пуст ли список
Определить количество
элементов в списке
Вставить элемент в указанную позицию
Удалить элемент из указанной позиции
Посмотреть (извлечь) элемент из заданной позиции
Слайд 3
![Диаграмма абстрактного списка](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/225775/slide-2.jpg)
Диаграмма абстрактного списка
Слайд 4
![Операции над абстрактным Списком createList() - создает пустой список destroy()](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/225775/slide-3.jpg)
Операции над абстрактным Списком
createList() - создает пустой список
destroy() – уничтожает
список
isEmpty() – определяет пуст ли список
insert(index, NewElement) - вставляет новый элемент NewElement в список на позицию index
remove(index) – удаляет элемент списка, находящийся в позиции index
Слайд 5
![Операции над абстрактным Списком retrieve(index) – возвращает элемент, находящийся в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/225775/slide-4.jpg)
Операции над абстрактным Списком
retrieve(index) – возвращает элемент, находящийся в списке на
позиции index
getlength() – возвращает количество элементов в списке
Pos find(Element)- возвращает позицию элемента Element
(Pos может быть как номером элемента, так и указателем на некоторый элемент)
Слайд 6
![Реализация списков Необходимо определить тип элементов и понятия «позиция» элемента:](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/225775/slide-5.jpg)
Реализация списков
Необходимо определить тип элементов и понятия «позиция» элемента:
typedef int TypeItem
– тип элемента может быть как простым, так и сложным
typedef int Pos – в данном случае позицией элемента будет его номер в списке
Слайд 7
![Реализация списков посредством массивов При реализации с помощью массивов все](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/225775/slide-6.jpg)
Реализация списков посредством массивов
При реализации с помощью массивов все элементы списка
располагаются в смежных ячейках, причем у каждого элемента определен номер.
Это позволяет легко просматривать список, вставлять и удалять элементы в начало и в конец списка.
Однако, вставка элемента в середину списка потребует от нас сдвинуть все остальные элементы, также как удаление
Слайд 8
![Реализация списков с помощью указателей В данном случае элементы списка](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/225775/slide-7.jpg)
Реализация списков с помощью указателей
В данном случае элементы списка не обязательно
расположены в смежных ячейках, для связывания элементов используются указатели.
Эта реализация освобождает нас с одной стороны от использования непрерывной области памяти
Нет необходимости перемещения элементов при вставке или удалении элемента в список.
Необходима дополнительная память для хранения указателей.
Слайд 9
![Реализация связанных списков с помощью указателей информационная часть ссылочная часть – указатель на следующий элемент](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/225775/slide-8.jpg)
Реализация связанных списков с помощью указателей
информационная часть
ссылочная часть – указатель на
следующий элемент
Слайд 10
![Определение структуры List: struct Node { TypeItem Item;// элемент списка](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/225775/slide-9.jpg)
Определение структуры List:
struct Node
{
TypeItem Item;// элемент списка
Node *Next; // указатель
на следующий элемент
}
Слайд 11
![Определение структуры List: struct List { int size ; //кол-во](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/225775/slide-10.jpg)
Определение структуры List:
struct List
{ int size ; //кол-во элементов списка
ListNode *head;
//указатель на связный список
ListNode *find(int index) const;//возвращает указатель на узел с номером index
void createList();
void destroyList();
Слайд 12
![Определение структуры List: //Операции над списком: int isEmpty() const; int](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/225775/slide-11.jpg)
Определение структуры List:
//Операции над списком:
int isEmpty() const;
int getLength()
const;
void insert(int index, Typeltem newItem);
void remove(int index);
void retrieve(int index,Typeltem& dataItem) const;
void show() const;
}; // Конец описания списка