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

Содержание

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

Слайд 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

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

Типы, переменные, управляющие инструкции. Ссылочные типы и переменные. (Тема 2.3) 210
Компьютерные вирусы и антивирусные программы 249
BPWin моделдеу аспабы 439
Организация работы современной пресс-службы. Основные функции и направления работы 372
Алгоритмы. Свойства алгоритмов. Виды алгоритмов. Форма записи алгоритмов 263
Разработка системы прогнозирования изменения порога принятия решений в интеллектуальных системах управления 229

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

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

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

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

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

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

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