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

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

2. Операции над абстрактным списком:

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

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

List
items
createList()
destroyList()
isEmpty()
getLengh()
insert()
remove()
retrieve()

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

11.

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

12.

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

13.

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

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

19.

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++;
current=current->next;
}//end while
}//end of insert

21.

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)
{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)
{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 в случае
связных списков выполняются за
конечное число шагов для списков
любой длины.

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

30.

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;

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((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 ()

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 ((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, за
исключением случая, когда список
пуст

41. Кольцевые списки

Head