Последовательности вкратце
Последовательность - бесконечная структура данных с последовательным доступом, все элементы последовательности имеют один и тот же базовый тип.
T: sequence of Tbase
Операции:
1)Взятие read
x=read() – берем текущий элемент данной последовательности;
2)Добавление (ограничение только по объему памяти)
write(x) – добавляем х в конец последовательности;
3)Переход в начало rewind ().
Обычно представляет собой однородную структуру, подобную массиву. Но существенная разница в том, что у массива число элементов зафиксировано в его определении, а у последовательности – нет. То есть оно может меняться во время выполнения программы. Хотя каждая последовательность в любой момент времени имеет конкретную конечную длину, мы должны считать мощность последовательного типа бесконечной, т.к. нет никаких ограничений на потенциальную длину последовательностей.
Прямое следствие переменной длины – невозможность отвести фиксированный объем памяти под переменные-последовательности. Поэтому память выделяется в ходе выполнения программы, в частности, когда последовательность растет. Таким образом, для работы с последовательностями необходима динамическая схема выделения памяти.
Основное правило работы с последовательностями: доступ к элементам осуществляется строго в порядке их следования, а порождается последовательность присоединением новых элементов к ее концу. Следствие – невозможность прямого доступа к элементам, за исключением того элемента, который доступен для просмотра в данный момент. Это и является главным отличием последовательностей от массивов.
Линейные списки
Линейный список – это множество элементов хранения с заданным отношением строгого порядка, определяющим следование элементов в множестве. Требование строгого порядка вызвано тем, что с каждым элементом линейного списка при хранении связан конкретный физический адрес.
Линейный список – либо пустой список, либо элемент, ссылающийся на линейный список.
Описание:
struct {
Tdata data; // поле данных какого-либо произвольного типа
struct ls *next; // ls – линейный список, next – указатель на ls (структуру л. с.)
} – ссылаемся на структуру, пока ее описание не закончено.
Операции:
1)Вставка
Имеется указатель на некий элемент p, нужно вставить элемент q:
после р (через присваивание – не требует сложных операций и памяти)
до р (используем случай а, а затем меняем местами
2)Удаление из списка
после p:
p.next=q.next; free(q); - перенаправляем указатель, освобождаем память.
до р
переписать информацию из p.next в q.next , удалить p.next, используя случай а.
Операции удаления/вставки занимают время О(1) и не зависят от длины линейного списка, имеют преимущества по сравнению.
Операции поиска и индексации (доступ к элементам) – O(n).
Пример применения списка – подсчет количества всех переменных в программе:
main()
{
int i;
for (i=0; i<N; i++) {}
}
Алгоритм:
вносим первую встретившуюся переменную в линейный список, увеличиваем ее счетчик,
в дальнейшем сверяем каждую прочитанную, есть ли такая в списке,
если нет, то добавляем ее в список и увеличиваем ее счетчик,
иначе увеличиваем счетчик уже имеющейся в списке переменной,
завершаем список.
Двунаправленный линейный список – первый указатель связывает данный элемент со следующим, а второй - с предыдущим. Интересным свойством такого списка является то, что для доступа к его элементам вовсе не обязательно хранить указатель на первый элемент. Достаточно иметь указатель на любой элемент списка. Первый элемент всегда можно найти по цепочке указателей на предыдущие элементы, а последний - по цепочке указателей на следующие. Но наличие указателя на заголовок списка в ряде случаев ускоряет работу со списком.
Циклические списки также как и линейные бывают однонаправленными и двунаправленными. Основное отличие циклического списка состоит в том, что в списке нет пустых указателей NULL.
Последний элемент списка содержит указатель, связывающий его с первым элементом. Для полного обхода такого списка достаточно иметь указатель только на текущий элемент.
В двунаправленном циклическом списке система указателей аналогична системе указателей двунаправленного линейного списка.