Функции обработки строк. смотреть 26.

Указатели. Объявление указателей.

Указатель (пойнтер, англ. pointer) — переменная, диапазон значений которой состоит из адресов ячеек памяти и специального значения — нулевого адреса. Значение нулевого адреса не является реальным адресом и используется только для обозначения того, что указатель в данный момент не может использоваться для обращения ни к какой ячейке памяти.

Пример указателей на языке Си:

int n = 6, /* Объявление переменной n типа int и присваивание ей значения 6 */

*pn = malloc(sizeofint); /* и указателя pn и выделение под него памяти. */

*pn = 5; /* Разыменование указателя и присваивание значения 5. */

n = *pn; /* Присвоить n то значение (5), на которое указывает pn. */

free(pn); /* Освободить занятую память. */

pn = n; /* Действие обратное разыменованию. Присваивает указателю */

/* pn адрес переменной n. Далее указатель будет ссылаться на n. */

n = 7; /* *pn тоже стало равно 7 */

29.

Операции над указателями.

— получить адрес переменной

* — коственная адресация; выдает значение

записанное по адресу на который ссылается

указатель

30.

В отличие от простых типов данных, данные структурированного типа характеризуются множественностью образующих этот тип элементов, т.е. переменная или константа структурированного типа всегда имеет несколько компонентов. Каждый компонент, в свою очередь, может принадлежать структурированному типу, т.е. возможна вложенность типов.

Подразделяются на: регулярный тип (массивы); комбинированный тип (записи); файловый тип (файлы); множественный тип (множества); строковый тип (строки); объектный тип (объекты).

31.

32. Структуры. Определение структур.

Структура — это совокупность переменных, объединенных под одним именем. С помощью структур удобно размещать в смежных полях связанные между собой элементы информации. Объявление структур создает шаблон, который можно использовать для создания ее объектов, то есть экземпляров этой структуры. Переменные, из которых состоит структура, называются членами. Члены структуры еще называют элементами или полями.

В структуре обязательно должен быть указан хотя бы один компонент. Определение структур имеет следующий вид: тип-данных описатель; где тип-данных указывает тип структуры для объектов, определяемых в описателях. В простейшей форме описатели представляют собой идентификаторы или массивы.

struct { double x,y; } s1, s2, sm[9];struct { int year; char moth, day; } date1, date2;

Объявление переменных типа структура

struct { double x,y; } s1, s2, sm[9]; struct { int year; char moth, day; } date1, date2;

Переменные s1, s2 определяются как структуры, каждая из которых состоит из двух компонент х и у. Переменнаяsm определяется как массив из девяти структур. Каждая из двух переменных date1, date2 состоит из трех компонентов year, moth, day.

Динамическая структура

ожно выделить следующие основные классы динамических объектов:

упорядоченные совокупности характеризуются тем, что для них значим физический порядок встраивания элементов. Пример — массивы;

неупорядоченные совокупности или коллекции — физический порядок объектов в представлении данных незначим, встраивание объектов в коллекцию произвольно. Примеры — хэши, одно?идвусвязныесписки, деревья; последовательности — физический порядок объектов в представлении данных незначим, но значим порядок вставки/удаления, которые выполняются только в определенных точках последовательности. Примеры — стеки, очереди.

Существуют 2 основных возможности для организации динамических структур:

библиотеки функций classlib;

организация динамических наборов структур, связанных указателями на структурные типы.

Списки.

Линейный список

В простейшем случае каждый узел содержит всего одну ссылку. Для определенности будемсчитать, что решается задача частотного анализа текста – определения всех слов, встречающихся в тексте и их количества. В этом случае область данных элемента включает строку (длиной

не более 40 символов) и целое число.

Каждый элемент содержит также ссылку на следующийза ним элемент. У последнего в списке

элемента поле ссылки содержит NULL. Чтобы не потерять список, мы должны где-то (в пере-

менной) хранить адрес его первого узла – он называется «головой» списка. В программе надо

объявить два новых типа данных – узел списка Nodeи указатель на него PNode. Узел пред-

ставляет собой структуру, которая содержит три поля — строку, целое число и указатель на та-

кой же узел. Правилами языка Си допускается объявление

Создание списка

Функция create(s) создает и возвращает в качестве результата список из

символов параметра-строки s.

Однонаправленные списки

Однонаправленный линейный список — это список, который имеет указатель на начало списка, при этом каждый список имеет указатель на следующий список, а последний список принимает указатель NULL, что говорит о том, что он последний.Однонаправленный кольцевой список — это список, который имеет указатель на начало списка, при этом каждый список имеет указатель на следующий список, а последний список имеет указатель на начало списка. Динамическое выделение памяти необходимо для того, чтобы память выделялась только тогда, когда нам надо, и при необходимости освобождалась. Динамическая память в си выделяется функцией new. Освобождение памяти происходит оператором delete.

Пример файловой системы (их атрибуты: имя, расширение, дата создания, размер, атрибуты). Список имеет следующий вид:structFDat{ //структура данных charName[20]; //имяchar r[4]; // расширениеchar d[10]; // дата intsize; // размерcharattr[4]; // атрибут FDat *Next; //указатель на следующую структуру

};

Двунапревленные списки.

Двунаправленный список обрабатывается аналогично однонаправленному.Выделим типовые операции:добавление звена в начало списка;удаление звена из начала списка;добавление звена в произвольное место списка, отличное от начала (например, после звена, указатель на которое задан);удаление звена из произвольного места списка, отличного от начала (например, после звена, указатель на которое задан);проверка, пуст ли список;очисткасписка;печатьсписка;формирование списка.

Циклические списки

Это тоже самое что и связанный список, только последник элемент указывает на первый и получается циклический список.

свя?зныйспи?сок — структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.[1] Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями

Стек

Стек (англ. stack — стопка) — структура данных, в которой доступ к элементам организован по принципу LIFO (англ. lastin — firstout, «последним пришёл — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.

Функция push(); вводит данные в стек, а pop(); удаляет данные из стека, при этом заботится о том, что, если стек пуст, выводит сообщение Стек пуст.

Для подсчета элементов в массиве используется счетчик count. Скрипт очень простой. Кому интересно смотрите исходники:

Очередь.

О?чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, FirstIn — FirstOut). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.

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

Программная реализация очереди возможна двумя способами:

статически с помощью массива

динамически с помощью механизма указателей

Дэк

Двусвязная очередь (жарг. дэк, дек от англ. deque — doubleendedqueue; двухсторонняя очередь, двусвязный список, очередь с двумя концами) — структура данных, в которой элементы можно добавлять и удалять как в начало, так и в конец.

Деком (англ. deque – аббревиатура от double-endedqueue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека:

push_front

Добавить (положить) в начало дека новый элемент

push_back

Добавить (положить) в конец дека новый элемент

pop_front

Извлечь из дека первый элемент

pop_back

Извлечь из дека последний элемент

front

Узнать значение первого элемента (не удаляя его)

back

Узнать значение последнего элемента (не удаляя его)

size

Узнать количество элементов в деке

clear

Очистить дек (удалить из него все элементы)

Бинарное дерево

Двои?чноеде?рево — древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.Для практических целей обычно используют два подвида бинарных деревьев — двоичное дерево поиска и двоичная куча.

Уроки C++ с нуля / Урок #11 — Символы и строки


Похожие статьи.

Понравилась статья? Поделиться с друзьями: