Абстрактный тип данных. Список

Здесь вы можете просмотреть и скачать доклад по теме «Абстрактный тип данных. Список», размещенный в категории «Устройства и комплектующие», который поможет вам успешно провести свое мероприятие или подготовиться к занятию.

Информация о презентации

Абстрактный тип данных. Список
Раздел:Устройства и комплектующие
Слайдов:27
Слов:678
Символов:4779
Просмотров:39
Скачиваний:1
Загрузка:онлайн
Размер:81.50 kB
Тип:ppt / pptx для PowerPoint/Impress
Теги:#list, #элемент, #списк, #temp, #next, #реализац, #typeitem, #current, #указател, #celltype

Похожие презентации об устройстве и комплектующих

Готовые презентации об устройстве и комплектующих

Содержание слайда №1 (29 знаков, 4 слова)

Абстрактный тип данных список

Содержание слайда №2 (341 знак, 48 слов)

Операции над абстрактным Списком CreateList(List) - создает пустой список List DeleteList(List) – уничтожает список List IsEmpty(List) – определяет пуст ли список List Insert(index, NewElement, List) - вставляет новый элемент NewElement в список List на позицию index Remove(index, List) – удаляет элемент списка, находящийся в позиции index

Содержание слайда №3 (314 знаков, 43 слова)

Операции над абстрактным Списком TypeItem Retrive(index, List) – возвращает элемент, находящийся в позиции index Getlength(List) – возвращает количество элементов в списке List Pos Find(List, Element)- возвращает позицию элемента Element (Pos может быть как номером элемента, так и указателем на некоторый элемент)

Содержание слайда №4 (235 знаков, 35 слов)

Реализация списков Необходимо определить тип элементов и понятия «позиция» элемента: typedef int TypeItem – тип элемента может быть как простым, так и сложным typedef int Pos – в данном случае позицией элемента будет его номер в списке

Содержание слайда №5 (379 знаков, 53 слова)

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

Содержание слайда №6 (144 знака, 15 слов)

Реализация списков посредством массивов Определяем максимальное количество элементов: define max_list 100;// максимальное число элементов списка

Содержание слайда №7 (174 знака, 21 слово)

Реализация списков посредством массивов Описываем структуру List: Struct List { TypeItem Items [Max_ list]; //массив элементов списка int last; //индекс следующего элемента }

Содержание слайда №8 (77 знаков, 10 слов)

Реализация списков посредством массивов Void CreateList(List L) { L. last=0;}

Содержание слайда №12 (399 знаков, 50 слов)

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

Содержание слайда №13 (49 знаков, 6 слов)

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

Содержание слайда №14 (163 знака, 19 слов)

Определение структуры List: typedef struct celltype { TypeItem Item;// элемент списка celltype *Next; // указатель на следующий элемент } typedef celltype *list;//

Содержание слайда №15 (175 знаков, 25 слов)

Описания необходимых типов и переменных typedef int Pos;//позицией элемента будет его номер в списке typedef celltype *Pos;// позицией элемента будет указатель на этот элемент

Содержание слайда №16 (108 знаков, 17 слов)

Функции работы со списком Void CreateList(List S)//создание пустого списка { S=new celltype; S->next=NULL; }

Содержание слайда №17 (252 знака, 45 слов)

void Insert (TypeItem x, Pos n, list S) void Insert (TypeItem x, Pos n, list S) {list temp, current; temp=S; current=S->Next; Pos i=1; while(current! =0) {if (i==n) {temp=new celltype; temp->Next=current->Next; temp->Item=x; current->Next=temp; break;}

Содержание слайда №18 (62 знака, 10 слов)

i++; i++; current=current->next; }//end while }//end of insert

Содержание слайда №19 (215 знаков, 38 слов)

void Remove (Pos n, list S) void Remove (Pos n, list S) {list current=S->Next, temp; Pos i=1; while(current! =NULL && inext;i++;) if(i==n){ temp=current->next; current->next=current->next->next; delete temp;} }//end

Содержание слайда №20 (190 знаков, 34 слова)

Pos Find (TypeItem x, list S) Pos Find (TypeItem x, list S) {list temp; Pos i=1; if (S->Next==NULL) coutNext! =NULL) {if (temp->Item==x) return (i); temp=temp->next;i++;} return (0);} }//end

Содержание слайда №21 (196 знаков, 34 слова)

TypeItem Retrive (Pos n, list S) TypeItem Retrive (Pos n, list S) {list temp; Pos i=1; if (S->Next==NULL) coutNext! =NULL) {if (i==n) return (temp->Item); temp=temp->next;i++;} return (0);} }//end

Содержание слайда №22 (196 знаков, 34 слова)

TypeItem Retrive (Pos n, list S) TypeItem Retrive (Pos n, list S) {list temp; Pos i=1; if (S->Next==NULL) coutNext! =NULL) {if (i==n) return (temp->Item); temp=temp->next;i++;} return (0);} }//end

Содержание слайда №23 (354 знака, 47 слов)

Сравнение реализаций Реализация списков с помощью массивов требует указания максимального размера массива до начала выполнения программы Если длина списка заренее не известка, более рациональным способом будет реализация с помощью указателей. Процедуры INSERT и DELETE в случае связных списков выполняются за конечное число шагов для списков любой длины.

Содержание слайда №24 (345 знаков, 44 слова)

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

Содержание слайда №25 (149 знаков, 19 слов)

Двусвязные списки Используются в приложениях, где необходимо организовать эффективное перемещение по списку как прямом, так и в обратном направлениях

Содержание слайда №26 (17 знаков, 2 слова)

Двусвязные списки

Содержание слайда №27 (216 знаков, 25 слов)

Описание структуры списка typedef struct celltype { TypeItem Item;// элемент списка celltype *Next; // указатель на следующий элемент celltype *Previous; // указатель на предыдущий элемент } typedef celltype *list;//