Связныесписки. Понятиеконтейнера, определениеиклассификация связных списков. Преимущества связных списков перед массивами.
Контейнер в информатике: Программный объект, содержащий в себе тем или иным образом набор значений (объектов) одного или различных типов, и позволяющий обращаться к этим значениям.
• Массив • Многомерный массив • Список • Стек • Очередь • И т.д.
Свя́зныйспи́сок: Структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующие и/или предыдущие узлы. По количеству связей списки разделяют на односвязные и двусвязные.
Преимущества перед массивом - Гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
Пример двусвязного списка:
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);