Представление стека в виде списка
В виде списка удобно хранить стек с элементами переменной длины или трудно предсказуемым количеством элементов. Вершина стека размещается в начале списка, где выполнять операции включения и исключения элемента проще, чем в конце (рис. 3.8).
Рис. 3.8. Стек в виде списка
Дек
Дек (deque - double-ended queue: двусторонняя очередь) - это упорядоченная последовательность элементов, в которой включение и исключение элемента могут выполняться в обоих концах (рис. 3.9). Дек является обобщением очереди и стека.
|
|
|
D[1]
|
D[2]
|
…
|
D[n]
|
|
|
| Включение и
исключение
элементов
|
|
|
|
|
|
|
|
| Включение и
исключение
элементов
|
Рис. 3.9. Дек
Назначение дека - переупорядочивание поступающих данных перед обработкой. Стек и дек часто сравнивают с железнодорожными разъездами для перестановки вагонов поезда. Возможности дека по перестановкам больше, чем у стека.
Операции с деком аналогичны операциям над очередью и стеком. Хранится дек, подобно очереди, в виде циклического вектора или списка с двумя указателями.
Строка
Строка - последовательность элементов, доступ к которым - только последовательным перебором в прямом или обратном направлении.
В дальнейшем рассматривается только наиболее распространенный пример строки - строка символов (текст). Символьная обработка (обработка текстовой информации) является важным разделом программирования. Сюда относятся: редактирование текста (поиск, удаление, вставка, замена и перемещение его частей, оформление строчек, абзацев, страниц, документов и др.); трансляция языков программирования, поиск информации в Интернет и т.п. В частности, ввод данных (в том числе числовых) с клавиатуры, а во многих случаях и из файлов, производится в форме текста, который затем преобразуется в другие формы представления.
Примеры символьной обработки даны в разделе 7.
Типовые операции над строками:
1. Объединение (сцепление, [кон]катенация) строк.
Пример: "Петер" + "бург" --> "Петербург"
2. Разделение строки на части (выделение подстроки).
3. Сравнение строк элемент за элементом.
4. Замена, перемещение, удаление и вставка части строки.
5. Поиск вхождений одной строки в другую и др.
Дата добавления: 2015-09-27 | Просмотры: 474 | Нарушение авторских прав
|