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

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

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

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

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

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

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

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

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

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

Viod Insert(int n,TypeItem NewItem,List L)
{
if (L.last>=100) cout<<’Список полон’;
else
if (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

Viod Remove(int n, List L)
{
if (n>L.last || n<1)
cout<<‘Такой позиции нет’;
else
{L.last=L.last-1; for (i=n; i<=L.last; i++) L.Items[i]=L.Items[i+1];
}
} //end Remove

Pos Find(TypeItem x, List L)
{for (i=n; i<=L.last; i++)
if (L.Items[i]=x)
return(i);
return(L.last+1);//х не найден
} //end Remove

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

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

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

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

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

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;}

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

void 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

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

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

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

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

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

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

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

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

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);
} // Конец описания списка

Конструкторы
//конструктор по умолчанию
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;

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

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

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

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

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

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

Операции над списком
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

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

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