Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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





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

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

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

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

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

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

 

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

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

 

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

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

 

 





Дата добавления: 2014-01-03; Просмотров: 283; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.002 сек.