- •1.Понятия указателя, стэка вызовов функций, потока выполнения программы
- •Void pthread_exit (void *value_ptr);
- •Int pthread_join (
- •Int pthread_kill (
- •Int pthread_detach (pthread_t thread);
- •Introsort — Сложность алгоритма: o(n log n), сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает log(n).
- •6.Динамически выделяемая память, динамические массивы (вставка, удаление элементов с концов и в середине).
- •Int main(int argc, char* argv[])
- •1. Односвязные списки
- •Var cur : sllptr; { адрес текущего элемента }
- •Var cur : sllptr; { адрес нового эл-та }
- •Var p1, p2 : sllptr; { указатели на эл-ты пары }
- •3.2. Реализация очереди на базе массива
- •4.2. Реализация стека на базе массива
1. Односвязные списки
Линейный список представляет собой набор элементов (узлов), соединенных в цепочку. Обычно элемент представляет собой запись, которая содержит поле - указатель на следующий элемент.
Первая запись называется "головой" списка. Обычно при работе со списками вводится указатель на голову списка (например first)
Последняя запись должна быть отмечена как последняя. Для этого в поле связи устанавливают специальное значение указателя(=0)(в Паскале - nil)
Использование списка удобно, когда приходится часто дополнять его записями, удалять из него записи, поддерживать упорядочение списка и т.д.
Основные операции со списками:
1) Получить доступ к i-ому узлу списка для чтения или изменения данных.
2) Включить новый узел непосредственно перед (или после) i-го узла
3) Исключить i-й узел
4) Отсортировать список по некоторым полям в узлах
5) Найти в списке узел с заданным значением в некотором поле
В отличии от массива доступ к i-ому узлусписка занимает неодинаковое время. Чем дальше узел от начала списка, тем дольше до него добираться.
Наоборот, включение и исключение элементов в середину списка, сохранение упорядоченности при включении - выполняются проще чем в массиве.
а) включение после ptr:
1) S^.next := ptr^.next;
2) ptr^.next := S;
порядок важен!
б)включить в начало списка
1) S^.next := head;
2) head := S;
(Работает и в случае пустого списка, когда head = nil)
в) Удаление после ptr
Логическое удаление
ptr^.next := (ptr^.next)^.next
При этом теряется доступ, но неиспользуемый объект занимает память, т.е образуется мусор.
Удаление с освобождением памяти
1) wsp := ptr^.next;
2) ptr^.next := wsp^.next;
3) dispose (wsp);
г) Поиск в списке. Найти узел с заданным значением поля info
ptr := head;
while (ptr<>nil and ptr^.info<>value) do ptr := ptr^.next;
if ptr=nil then writeln("искомого значения в списке нет");
2. Двусвязные списки
Двусвязный список мало чем не отличается от односвязного, но у него появляется еще одна компонента, в которой хранится адрес предыдущего элемента.
Ниже рассматриваются некоторые простые операции над линейными списками. Выполнение операций иллюстрируется в общем случае рисунками со схемами изменения связей и программными примерами.
На всех рисунках сплошными линиями показаны связи, имевшиеся до выполнения и сохранившиеся после выполнения операции. Пунктиром показаны связи, установленные при выполнении операции. Значком 'x' отмечены связи, разорванные при выполнении операции. Во всех операциях чрезвычайно важна последовательность коррекции указателей, которая обеспечивает корректное изменение списка, не затрагивающее другие элементы. При неправильном порядке коррекции легко потерять часть списка. Поэтому на рисунках рядом с устанавливаемыми связями в скобках показаны шаги, на которых эти связи устанавливаются.
В программных примерах подразумеваются определенными следующие типы данных:
любая структура информационной части списка:
type data = ...;
элемент односвязного списка (sll - single linked list):
type
sllptr = ^slltype; { указатель в односвязном списке }
slltype = record { элемент односвязного списка }
inf : data; { информационная часть }
next : sllptr; { указатель на следующий элемент }
end;
элемент двухсвязного списка (dll - double linked list):
type
dllptr = ^dlltype; { указатель в двухсвязном списке }
dlltype = record { элемент односвязного списка }
inf : data; { информационная часть }
next : sllptr; { указатель на следующий элемент (вперед) }
prev : sllptr; { указатель на предыдущий элемент (назад) }
end;
Перебор элементов списка
Эта операция, возможно, чаще других выполняется над линейными списками. При ее выполнении осуществляется последовательный доступ к элементам списка - ко всем до конца списка или до нахождения искомого элемента.
Алгоритм перебора для односвязного списка представляется программным примером 1.
{==== Программный пример 1 ====}
{ Перебор 1-связного списка }
Procedure LookSll(head : sllptr);
{ head - указатель на начало списка }