Связныесписки. Понятиеконтейнера, определениеиклассификация связных списков. Преимущества связных списков перед массивами.

Контейнер в информатике: Программный объект, содержащий в себе тем или иным образом набор значений (объектов) одного или различных типов, и позволяющий обращаться к этим значениям.
• Массив • Многомерный массив • Список • Стек • Очередь • И т.д.

Свя́зныйспи́сок: Структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующие и/или предыдущие узлы. По количеству связей списки разделяют на односвязные и двусвязные.

Преимущества перед массивом - Гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Пример двусвязного списка:

Structbooks

{

Intnomer;

string name;

string author;

intpage;

intcost;

books* next; //Указатель на следующий

books* back; //Указатель на предыдущий

};

Примеродносвязногосписка:

Structbooks

{

Intnomer;

string name;

string author;

int page;

intcost;

books* next; //Указатель на следующий

};

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

Добавление элемента в конец списка:

struct books

{

//…
books* next;

};
books* end(books* book) //Поискконцасписка

{

while (book->next!= NULL) //покаестьэлементы

book = book->next; //переходим к следующему элементу

return book;

}
int _tmain(int argc, _TCHAR* argv[])

{
books* start = NULL;//Указатель на первый элемент

books* current = NULL;//Указатель на текущий элемент

if (start == NULL)

{

current = new books;

start = current;

current->next = NULL;

}

else

{

current = end(start);

current->next = new books;

current = current->next;

current->next = NULL;

}
//…
return 0;

}

Добавление элемента в начало списка:

//…
books* tmp = NULL; //Указатель на временный элемент

if (start == NULL)

{//… }

else

{

tmp = new books;

tmp->next = start;

start = tmp;

}
//…
return 0;

}

Добавлениеэлементавпроизвольнуюпозициюсписка:

books* add_rand(books* leftbook, books* newbook) // leftbook - Послекотороговставляем

{ // newbook - Новыйэлемент

if (leftbook!= NULL)

{

newbook->next = leftbook->next;

leftbook->next = newbook;

}

returnnewbook;

}

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

Время выполнения операции вставки элемента в произвольную позицию массива и время удаления элемента из произвольной позиции линейно зависит от количества элементов массива. O(n).

Время выполнения операции вставки элемента в произвольную позицию списка и время удаления элемента из произвольной позиции постоянно (т.е. не зависит от количества элементов списка). O(1)

Связныесписки. Удаление элемента из списка. Сравнение с удалением из массива. Примеры.

books* poisk(books* start, intid) // функция поиска элемента списка по номеру

{

while (start!= NULL)

{

if (start->nomer == id)

return start;

start = start->next;

}

return NULL;

}

//...

current = poisk(start, id);

tmp = current;

if (tmp == start) //еслипервый

start = current->next;

elseif (tmp->next == NULL) //еслипоследний

{

current = start;

while (current->next->nomer!= id)

current = current->next;

current->next = NULL;

}

else //не первый и не последний

{

current = start;

while (current->next->nomer!= id)

current = current->next;

current->next = tmp->next;

}

deletetmp;

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

Время выполнения операции вставки элемента в произвольную позицию массива и время удаления элемента из произвольной позиции линейно зависит от количества элементов массива. O(n).

Время выполнения операции вставки элемента в произвольную позицию списка и время удаления элемента из произвольной позиции постоянно (т.е. не зависит от количества элементов списка). O(1)

Связные списки. Обход списка. Сортировка списка. Примеры.

Обход с первого элемента:

books* end(books* start)

{

while (start->next!= NULL) //пока есть элементы

start = start->next; //переходим к следующему элементу

returnstart;

}

Сортировка:

structbooks

{

intnomer;

string name;

string author;

int page;

int cost;

books* next;

};

//...

do

{

sortOK = false;

current = start;

while (current->next!= NULL)

{

if (current->name > current->next->name)

{

swap(current->name, current->next->name);

swap(current->author, current->next->author);

swap(current->page, current->next->page);

swap(current->cost, current->next->cost);

 

sortOK = true;

}

current = current->next;

}

} while (sortOK);