🗊Презентация Абстрактный тип данных. Список

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Абстрактный тип данных. Список, слайд №1Абстрактный тип данных. Список, слайд №2Абстрактный тип данных. Список, слайд №3Абстрактный тип данных. Список, слайд №4Абстрактный тип данных. Список, слайд №5Абстрактный тип данных. Список, слайд №6Абстрактный тип данных. Список, слайд №7Абстрактный тип данных. Список, слайд №8Абстрактный тип данных. Список, слайд №9Абстрактный тип данных. Список, слайд №10Абстрактный тип данных. Список, слайд №11Абстрактный тип данных. Список, слайд №12Абстрактный тип данных. Список, слайд №13Абстрактный тип данных. Список, слайд №14Абстрактный тип данных. Список, слайд №15Абстрактный тип данных. Список, слайд №16Абстрактный тип данных. Список, слайд №17Абстрактный тип данных. Список, слайд №18Абстрактный тип данных. Список, слайд №19Абстрактный тип данных. Список, слайд №20Абстрактный тип данных. Список, слайд №21Абстрактный тип данных. Список, слайд №22Абстрактный тип данных. Список, слайд №23Абстрактный тип данных. Список, слайд №24Абстрактный тип данных. Список, слайд №25Абстрактный тип данных. Список, слайд №26Абстрактный тип данных. Список, слайд №27Абстрактный тип данных. Список, слайд №28Абстрактный тип данных. Список, слайд №29Абстрактный тип данных. Список, слайд №30Абстрактный тип данных. Список, слайд №31Абстрактный тип данных. Список, слайд №32Абстрактный тип данных. Список, слайд №33Абстрактный тип данных. Список, слайд №34Абстрактный тип данных. Список, слайд №35Абстрактный тип данных. Список, слайд №36Абстрактный тип данных. Список, слайд №37Абстрактный тип данных. Список, слайд №38Абстрактный тип данных. Список, слайд №39Абстрактный тип данных. Список, слайд №40Абстрактный тип данных. Список, слайд №41
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Абстрактный тип данных. Список. Доклад-сообщение содержит 41 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


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

Слайд 2


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

Слайд 3


Диаграмма абстрактного списка
Описание слайда:
Диаграмма абстрактного списка

Слайд 4


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

Слайд 5


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

Слайд 6


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

Слайд 7


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

Слайд 8


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

Слайд 9


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

Слайд 10


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

Слайд 11


Абстрактный тип данных. Список, слайд №11
Описание слайда:

Слайд 12


Абстрактный тип данных. Список, слайд №12
Описание слайда:

Слайд 13


Абстрактный тип данных. Список, слайд №13
Описание слайда:

Слайд 14


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

Слайд 15


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

Слайд 16


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

Слайд 17


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

Слайд 18


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

Слайд 19


void Insert (TypeItem x, Pos n, list S) void Insert (TypeItem x, Pos n, list S) {list temp, current; current=S->Next;//первый элемент Pos i=1; while(current!=0)//пока список не пуст {if (i==n) {temp=new Node; temp->Next=current->Next; temp->Item=x; current->Next=temp; break;}
Описание слайда:
void Insert (TypeItem x, Pos n, list S) void Insert (TypeItem x, Pos n, list S) {list temp, current; current=S->Next;//первый элемент Pos i=1; while(current!=0)//пока список не пуст {if (i==n) {temp=new Node; temp->Next=current->Next; temp->Item=x; current->Next=temp; break;}

Слайд 20


i++; i++; current=current->next; }//end while }//end of insert
Описание слайда:
i++; i++; current=current->next; }//end while }//end of insert

Слайд 21


void Remove (Pos n, list S) void Remove (Pos n, list S) {list current=S->Next, temp; Pos i=1; while(current!=NULL && i<n) { current=current->next;i++;} if(i==n){ temp=current->next;//запоминаем //удаляемый элемент current->next=current->next->next; delete temp;//освобождаем память } }//end
Описание слайда:
void Remove (Pos n, list S) void Remove (Pos n, list S) {list current=S->Next, temp; Pos i=1; while(current!=NULL && i<n) { current=current->next;i++;} if(i==n){ temp=current->next;//запоминаем //удаляемый элемент current->next=current->next->next; delete temp;//освобождаем память } }//end

Слайд 22


Pos Find (TypeItem x, list S) Pos Find (TypeItem x, list S) {list current=S->Next; Pos i=1; if (S->Next==NULL) cout<<‘список пуст’; else { while(current->Next!=NULL) { if (current->Item==x) return (i); current=current->next;i++;} return (0);} }//end find
Описание слайда:
Pos Find (TypeItem x, list S) Pos Find (TypeItem x, list S) {list current=S->Next; Pos i=1; if (S->Next==NULL) cout<<‘список пуст’; else { while(current->Next!=NULL) { if (current->Item==x) return (i); current=current->next;i++;} return (0);} }//end find

Слайд 23


TypeItem Retriеve (Pos n, list S) TypeItem Retriеve (Pos n, list S) {list current=S->Next; Pos i=1; if (S->Next==NULL) cout<<‘список пуст’; else { while(current->Next!=NULL) { if (i==n) return (current->Item); current=current->next;i++;} return (0);} }//end
Описание слайда:
TypeItem Retriеve (Pos n, list S) TypeItem Retriеve (Pos n, list S) {list current=S->Next; Pos i=1; if (S->Next==NULL) cout<<‘список пуст’; else { while(current->Next!=NULL) { if (i==n) return (current->Item); current=current->next;i++;} return (0);} }//end

Слайд 24


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

Слайд 25


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

Слайд 26


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

Слайд 27


Двусвязные списки
Описание слайда:
Двусвязные списки

Слайд 28


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

Слайд 29


Реализация списков в виде класса class List { private: struct ListNode //узел списка {TypeItem item; //данные, хранящиеся в узле ListNode *next;//указатель на следующий узел } int size ; //кол-во элементов списка ListNode *head; //указатель на связный список ListNode *find(int index) const;//возвращает //указатель на узел с номером index
Описание слайда:
Реализация списков в виде класса class List { private: struct ListNode //узел списка {TypeItem item; //данные, хранящиеся в узле ListNode *next;//указатель на следующий узел } int size ; //кол-во элементов списка ListNode *head; //указатель на связный список ListNode *find(int index) const;//возвращает //указатель на узел с номером index

Слайд 30


Public: Public: //Конструкторы и деструкторы List(); List(const List& aList); ~List(); //Операции над списком: int isEmpty() const; int getLength() const; void insert(int index, TypeItem newItem); void remove(int index); void retrieve(int index, TypeItem& dataItem); } // Конец описания списка
Описание слайда:
Public: Public: //Конструкторы и деструкторы List(); List(const List& aList); ~List(); //Операции над списком: int isEmpty() const; int getLength() const; void insert(int index, TypeItem newItem); void remove(int index); void retrieve(int index, TypeItem& dataItem); } // Конец описания списка

Слайд 31


Конструкторы //конструктор по умолчанию List::List : size(0),head(NULL) { }; //конструктор копирования List::List(const List& aList) : size(aList.size) { if(aList.head==NULL) head=NULL; else { head= new ListNode; head->item=aList.head->item; ListNode *newPtr=head;
Описание слайда:
Конструкторы //конструктор по умолчанию List::List : size(0),head(NULL) { }; //конструктор копирования List::List(const List& aList) : size(aList.size) { if(aList.head==NULL) head=NULL; else { head= new ListNode; head->item=aList.head->item; ListNode *newPtr=head;

Слайд 32


Конструкторы for(ListNode *cur=alist.head->next; cur!=NULL; cur=cur->next); { newPtr->next=new ListNode; newPtr=newPtr->next; newPtr->item=cur->item); } // end for }// end if } // конец конструктора копирования
Описание слайда:
Конструкторы for(ListNode *cur=alist.head->next; cur!=NULL; cur=cur->next); { newPtr->next=new ListNode; newPtr=newPtr->next; newPtr->item=cur->item); } // end for }// end if } // конец конструктора копирования

Слайд 33


Деструктор List::~List() { while (!isEmpty()) remove(1); } // конец деструктора
Описание слайда:
Деструктор List::~List() { while (!isEmpty()) remove(1); } // конец деструктора

Слайд 34


Операции над списком int List::isEmpty() const { if(size) return (1); else return(0); } // конец функции isEmpty() int List::getLength() const { return(size); } // конец функции getLength()
Описание слайда:
Операции над списком int List::isEmpty() const { if(size) return (1); else return(0); } // конец функции isEmpty() int List::getLength() const { return(size); } // конец функции getLength()

Слайд 35


Операции над списком void List::remove(int index) { ListNode *cur; if((index<1)&&(index>getLength())) cout<<“ неверный индекс”; else { size--; if(index==1) //удаляем первый элемент {cur=head; head=head->next;}
Описание слайда:
Операции над списком void List::remove(int index) { ListNode *cur; if((index<1)&&(index>getLength())) cout<<“ неверный индекс”; else { size--; if(index==1) //удаляем первый элемент {cur=head; head=head->next;}

Слайд 36


Операции над списком Else { //находим узел, предшествующий удаляемому ListNode *prev=find(index-1); //удаляем узел с номером index cur=prev->next; prev->next=cur->next; } } // освобождаем память cur->next=NULL; delete cur; } // конец функции remove ()
Описание слайда:
Операции над списком Else { //находим узел, предшествующий удаляемому ListNode *prev=find(index-1); //удаляем узел с номером index cur=prev->next; prev->next=cur->next; } } // освобождаем память cur->next=NULL; delete cur; } // конец функции remove ()

Слайд 37


Операции над списком void List::retrieve(int index, TypeItem &dataItem) const { if ((index < 1) || (index > getLength()) cout<<“ неверный индекс”; else { // Вычислить указатель на узел, //а затем извлечь из него данные Listnode *cur = find(index); dataItem = cur->item; } } // Конец функции retrieve
Описание слайда:
Операции над списком void List::retrieve(int index, TypeItem &dataItem) const { if ((index < 1) || (index > getLength()) cout<<“ неверный индекс”; else { // Вычислить указатель на узел, //а затем извлечь из него данные Listnode *cur = find(index); dataItem = cur->item; } } // Конец функции retrieve

Слайд 38


Операции над списком List::ListNode *List::find(int index) const { if ((index<1)||(index>getLength())) return NULL; else // отсчет от начала списка { ListNode *cur =head; for (int i = 1; i < index; ++i) cur=cur->next; return cur; } // Конец оператора if } // Конец функции find
Описание слайда:
Операции над списком List::ListNode *List::find(int index) const { if ((index<1)||(index>getLength())) return NULL; else // отсчет от начала списка { ListNode *cur =head; for (int i = 1; i < index; ++i) cur=cur->next; return cur; } // Конец оператора if } // Конец функции find

Слайд 39


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

Слайд 40


Кольцевые списки В кольцевых списках вводят внешний указатель, который ссылается на «первый узел» «Последний узел» ссылается на первый узел В кольцевых списках ни один из узлов не содержит ссылку NULL, за исключением случая, когда список пуст
Описание слайда:
Кольцевые списки В кольцевых списках вводят внешний указатель, который ссылается на «первый узел» «Последний узел» ссылается на первый узел В кольцевых списках ни один из узлов не содержит ссылку NULL, за исключением случая, когда список пуст

Слайд 41


Кольцевые списки
Описание слайда:
Кольцевые списки

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию