Представление и обработка данных в виде одно- и двусвязных списков

Представление и обработка данных в виде символьных цепочек

Символьные цепочки с точки зрения физической организации представляют собой обыкновенные массивы типа CHAR. Особенность этого типа данных состоит в том, что символьный массив в подавляющем большинстве случаев является осмысленным текстом, а значит, имеет логическую структуру: разделен на слова, предложения, строки и абзацы. Поэтому алгоритмы обработки символьных цепочек почти всегда включают в себя поиск специальных символов-разделителей, разде­ление текста на логические единицы (слова, предложения, строки) и выполнение операций (подсчет, сортировка, поиск и замена) над этими единицами.

Структура данных, в которой объекты расположены в линейном порядке, на­зывается связным списком. Однако в отличие от массива, в котором этот порядок определяется индексами, порядок в связном списке определяется указателями на объекты.

Элемент (узел) связного списка, помимо полей с данными, имеет поле next, в ко­тором содержится указатель на следующий элемент списка. Если это последний элемент списка, поле next принимает нулевое значение. Помимо своих элементов, каждый список содержит указатель head на первый элемент списка. Если этот ука­затель равен 0, значит, список пуст. Поскольку этот указатель относится к списку в целом и не содержит в себе данных, на рис. 14.18, на котором схематически по­казан односвязный список, указатель не заключен в прямоугольник.

Односвязный список отличается тем, что пройти по нему можно только в одном направлении — от начала в конец списка. Это оказывается достаточно неудобно, по­этому гораздо большее распространение получили двусвязные списки (рис. 14.19), отличающиеся тем, что их узлы содержат по два указателя — на следующий (next) и на

Рис. 2. Односвязный список

предыдущий (prev) элементы списка. Помимо указателя head на первый элемент списка, может существовать также указатель tail на последний элемент списка.

Рис. 3. Двусвязный список

Частный случай двусвязного списка — замкнутый (кольцевой) список, указа­тель next последнего элемента которого указывает на первый элемент, а указатель prev первого элемента — на последний элемент списка. Главная особенность списка — быстрое выполнение операций вставки и уда­ления в произвольном месте списка. Эти операции требуют модификации ука­зателей максимум у трех узлов: узла, над которым выполняется операция, и двух окружающих узлов. Схематично эти операции и изменения значений указателей показаны на рис. 14.20.

Рис. 4. Вставка и удаление в двусвязных списках

Дата добавления: 2014-01-03