Динамические структуры

Сентябрь 7, 2022

Главная
Алгебра
Динамические структуры

Содержание

2. Операции над абстрактным списком: Создать пустой список Уничтожить список Определить, пуст ли список Определить количество элементов
3. Диаграмма абстрактного списка
4. Операции над абстрактным Списком createList() - создает пустой список destroy() – уничтожает список isEmpty() – определяет
5. Операции над абстрактным Списком retrieve(index) – возвращает элемент, находящийся в списке на позиции index getlength() –
6. Реализация списков Необходимо определить тип элементов и понятия «позиция» элемента: typedef int TypeItem – тип элемента
7. Реализация списков посредством массивов При реализации с помощью массивов все элементы списка располагаются в смежных ячейках,
8. Реализация списков с помощью указателей В данном случае элементы списка не обязательно расположены в смежных ячейках,
9. Реализация связанных списков с помощью указателей информационная часть ссылочная часть – указатель на следующий элемент
10. Определение структуры List: struct Node { TypeItem Item;// элемент списка Node *Next; // указатель на следующий
11. Определение структуры List: struct List { int size ; //кол-во элементов списка ListNode *head; //указатель на
12. Определение структуры List: //Операции над списком: int isEmpty() const; int getLength() const; void insert(int index, Typeltem
14. Скачать презентацию

Слайд 2

Операции над абстрактным списком:
Создать пустой список
Уничтожить список
Определить, пуст ли список
Определить количество

элементов в списке
Вставить элемент в указанную позицию
Удалить элемент из указанной позиции
Посмотреть (извлечь) элемент из заданной позиции

Слайд 3

Диаграмма абстрактного списка

Слайд 4

Операции над абстрактным Списком
createList() - создает пустой список
destroy() – уничтожает

список
isEmpty() – определяет пуст ли список
insert(index, NewElement) - вставляет новый элемент NewElement в список на позицию index
remove(index) – удаляет элемент списка, находящийся в позиции index

Слайд 5

Операции над абстрактным Списком
retrieve(index) – возвращает элемент, находящийся в списке на

позиции index
getlength() – возвращает количество элементов в списке
Pos find(Element)- возвращает позицию элемента Element (Pos может быть как номером элемента, так и указателем на некоторый элемент)

Слайд 6

Реализация списков
Необходимо определить тип элементов и понятия «позиция» элемента:
typedef int TypeItem

– тип элемента может быть как простым, так и сложным
typedef int Pos – в данном случае позицией элемента будет его номер в списке

Слайд 7

Реализация списков посредством массивов
При реализации с помощью массивов все элементы списка

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

Слайд 8

Реализация списков с помощью указателей
В данном случае элементы списка не обязательно

расположены в смежных ячейках, для связывания элементов используются указатели.
Эта реализация освобождает нас с одной стороны от использования непрерывной области памяти
Нет необходимости перемещения элементов при вставке или удалении элемента в список.
Необходима дополнительная память для хранения указателей.

Слайд 9

Реализация связанных списков с помощью указателей
информационная часть
ссылочная часть – указатель на

следующий элемент

Слайд 10

Определение структуры List:
struct Node
{
TypeItem Item;// элемент списка
Node *Next; // указатель

на следующий элемент
}

Слайд 11

Определение структуры List:
struct List
{ int size ; //кол-во элементов списка
ListNode *head;

//указатель на связный список
ListNode *find(int index) const;//возвращает указатель на узел с номером index
void createList();
void destroyList();

Слайд 12

Определение структуры 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;
}; // Конец описания списка

Динамические структуры

Содержание

Операции над абстрактным списком:Создать пустой списокУничтожить списокОпределить, пуст ли списокОпределить количество

Диаграмма абстрактного списка

Операции над абстрактным СпискомcreateList() - создает пустой список destroy() – уничтожает

Операции над абстрактным Спискомretrieve(index) – возвращает элемент, находящийся в списке на

Реализация списковНеобходимо определить тип элементов и понятия «позиция» элемента: typedef int TypeItem

Реализация списков посредством массивовПри реализации с помощью массивов все элементы списка

Реализация списков с помощью указателейВ данном случае элементы списка не обязательно

Реализация связанных списков с помощью указателейинформационная частьссылочная часть – указатель на

Определение структуры List:struct Node{ TypeItem Item;// элемент списка Node *Next; // указатель

Определение структуры List: struct List{ int size ; //кол-во элементов списка ListNode *head;

Определение структуры List: //Операции над списком: int isEmpty() const; int getLength()

Похожие презентации