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

Содержание

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

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

Слайд 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Реализация списков посредством массивов
Определяем максимальное количество элементов:

define max_list 100;// максимальное число

элементов списка

Слайд 9Реализация списков посредством массивов
Описываем структуру List:

Struct List {
TypeItem Items [Max_

list]; //массив элементов списка
int last; //индекс следующего элемента
}

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

Слайд 11Viod Insert(int n,TypeItem NewItem,List L)
{
if (L.last>=100) cout

(n>L.last || n<1) cout<<‘Такой позиции нет’;
else
{for (i=L.Last; i>=n; i--) L.Items[i+1]=L.Items[i];
L.last=L.last+1;
L.Items[n]=NewItem; }

} //end Insert

Слайд 12Viod Remove(int n, List L)
{
if (n>L.last || n

else
{L.last=L.last-1;
for (i=n; i<=L.last; i++) L.Items[i]=L.Items[i+1];
}

} //end Remove

Слайд 13Pos Find(TypeItem x, List L)
{for (i=n; i

return(L.last+1);//х не найден
} //end Remove

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

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

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

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

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

// указатель на следующий элемент
}
typedef Node *list;//

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

в списке

typedef Node *Pos;// позицией элемента будет указатель на этот элемент


Слайд 18Функции работы со списком
Void CreateList(list S)//создание пустого списка
{ S=new Node;

S->next=NULL;
}

Слайд 19void 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++;
current=current->next;
}//end while


}//end of insert

Слайд 21void Remove (Pos n, list S)
{list current=S->Next, temp;
Pos i=1;
while(current!=NULL &&

i { current=current->next;i++;}
if(i==n){
temp=current->next;//запоминаем //удаляемый элемент
current->next=current->next->next;
delete temp;//освобождаем память
}
}//end

Слайд 22Pos Find (TypeItem x, list S)
{list current=S->Next;
Pos i=1;
if (S->Next==NULL) cout

{
while(current->Next!=NULL)
{ if (current->Item==x) return (i);
current=current->next;i++;}
return (0);}
}//end find

Слайд 23TypeItem Retriеve (Pos n, list S)
{list current=S->Next;
Pos i=1;
if (S->Next==NULL) cout

{
while(current->Next!=NULL)
{ if (i==n) return (current->Item);
current=current->next;i++;}
return (0);}
}//end

Слайд 24Сравнение реализаций
Реализация списков с помощью массивов требует указания максимального размера массива

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

Слайд 25Сравнение реализаций
Реализация списков с помощью массивов расточительна с точки зрения использования

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

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

как прямом, так и в обратном направлениях

Слайд 27Двусвязные списки
информационная часть
указатель на предыдущий элемент
указатель на следующий элемент

Слайд 28Описание структуры списка
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

Слайд 30Public:
//Конструкторы и деструкторы
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;

Слайд 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
} // конец

конструктора копирования

Слайд 33Деструктор
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()

Слайд 35Операции над списком
void List::remove(int index)
{
ListNode *cur;
if((indexgetLength()))
cout

//удаляем первый элемент
{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 ()

Слайд 37Операции над списком
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 ((indexgetLength()))
return NULL;
else //

отсчет от начала списка
{
ListNode *cur =head;
for (int i = 1; i < index; ++i)
cur=cur->next;
return cur;
} // Конец оператора if
} // Конец функции find

Слайд 39Разновидности связных списков
Кольцевые списки:
Каждый узел в кольцевом списке ссылается на своего

преемника
Весь список можно обойти, начиная с любого узла

Слайд 40Кольцевые списки
В кольцевых списках вводят внешний указатель, который ссылается на «первый

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

Слайд 41Кольцевые списки

Head

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

Тема 3.1. Архитектура компьютеров 554
Нотные редакторы 373
Операционная система Linux 423
Алгоритмы и основы языка программирования Тurbo Рascal 7.0. (Лекция 7.2) 457
Тест по информатике на тему "Текстовый процессор MS Word" 1396
Разработка программы управления шаговым двигателем при помощи Arduino через драйвер А4988 247

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.

Для правообладателей

Яндекс.Метрика