Тема VI. Операции над строками и файлами в языке С / С ++

19
© С.Н. Бердышев

в языке С/С++
§1. Функции ввода и вывода
§2. Функции файлового ввода

и вывода
§3. Строки: операции с текстовыми файлами
§4. Операции со структурами и бинарными файлами
§5. Списки: операции с динамическими структурами данных; организация списков и их обработка
§5.1. Линейные списки
§5.2. Стеки
§5.3. Очереди
§5.4. Бинарные деревья

организация списков и их обработка
© С.Н. Бердышев
Тема

VI. Операции над строками и файлами в языке С/С++

 Определение

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

языке С/С++
 Наиболее часто используют следующие динамические

структуры, способные изменять размер во время
выполнения программы:

линейные списки;
стеки;
очереди;
бинарные деревья.

файлами в языке С/С++
 Определение


Линейным списком называется структура данных,

при которой логический порядок следования элементов задается с помощью указателей.

языке С/С++
 Варианты линейных списков:


Односвязный линейный список
Двусвязный линейный список
Односвязный линейный

кольцевой список

языке С/С++
Односвязный линейный список
 Определение


Односвязным (однонаправленным) линейным списком называют

список, в котором каждый элемент ссылается на следующий элемент.

языке С/С++
Двусвязный линейный список
 Определение


Двусвязным (двунаправленным) линейным списком называют

список, в котором каждый элемент ссылается на предыдущий и следующий элементы.

языке С/С++
Односвязный линейный кольцевой список
 Определение


Кольцевым списком называют список,

у которого первый и последний элементы связаны указателями.

языке С/С++
 Примечание:


Элементы любой динамической структуры данных представляют собой структуры.
Каждый

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

языке С/С++
Пример элемента односвязного списка :
struct node {
int

data1;
char data2[15];
...
node *next;
};

Пример элемента двусвязного списка :

struct node {
int data1;
char data2[15];
...
node *next;
node *prev;
};

языке С/С++
 Над списками можно выполнять следующие операции:


Начальное формирование списка

(создание 1-го элемента).
Добавление элемента в конец списка.
Чтение элемента с заданным ключом.
Вставка элемента в заданное место списка (до или после элемента с заданным ключом).
Удаление элемента с заданным ключом.
Упорядочивание списка по ключу.

языке С/С++
Примеры работы с линейными списками:
struct node {
int

data;
node *next;
node *prev; };

1. Формирование первого элемента

node *first(int d){
node *pv = new node; // - выделение памяти под элемент
pv->d = d; // - присваивание значения полю данных
pv->next = NULL; // - обнуление указателей на следующий
pv->prev = NULL; // и предыдущий элементы (их еще нет)
return pv; } // - передача в программу указателя на
// первый элемент списка

языке С/С++
Примеры работы с линейными списками:
2. Добавление в конец списка
void

append(node **pend, int d){
node *pv = new node; // - выделение памяти под элемент
pv->d = d; // - присваивание значения полю данных
pv->next = NULL; // - обнуление (следующего эл-та еще нет)
pv->prev = *pend; // - указывает конец списка
// (куда добавляется)
(*pend)->next = pv; // - в предыдущем эл-те устанавливаем
// указатель на добавляемый эл-т
*pend = pv; } // - обновление указателя на конец списка

3. Поиск элемента по ключу

node *find(node *const pbeg, int d){
node *pv = pbeg; // - указатель на первый эл-т списка
while(pv){
if(pv->d == d) break;// - если значение совпало, то выход
pv = pv->next; } // - выбор следующего эл-та списка
return pv; } // - передача в программу указателя на
// найденный элемент списка

языке С/С++
Примеры работы с линейными списками:
4. Вставка элемента

языке С/С++
Примеры работы с линейными списками:
4. Вставка элемента
node insert(node *const

pbeg, node **pend, int key, int d){
if(node *pkey = find(pbeg, key)){
node *pv = new node;
pv->d = d;
// 1 – установка связи нового эл-та с последующим:
pv->next = pkey->next;
// 2 – установка связи нового эл-та с предыдущим:
pv->prev = pkey;
// 3 – установка связи предыдущего эл-та с новым:
pkey->next = pv;
// 4 – установка связи последующего эл-та с новым:
(pv->next)->prev = pv;
return pv; }

 Примечание:

Пример описывает вставку нового элемента только в середину списка.

языке С/С++
Примеры работы с линейными списками:
5. Удаление элемента
bool remove(node **pbeg,

node **pend, int key){
if(node *pkey = find(pbeg, key)){// выдел. памяти под указ. на эл-т
if(pkey == *pbeg){ // если в начале списка
*pbeg = (*pbeg)->next;
(*pbeg)->prev = 0;}
else if (pkey == *pend){ // если в конце списка
*pend = (*pend)->prev;
(*pend)->next = 0;}
else { // если в середине списка
(pkey->prev)->next = pkey->next;
(pkey->next)->prev = pkey->prev;}
delete pkey; // освобождение памяти (удаление)
return true; } // выход : эл-т найден и удален
return false; } // выход : эл-т не найден

в языке С/С++
 Определение


Стек — это частный случай односвязного

(однонаправленного) списка, добавление элементов в который и выборка из которого выполняется с одного конца, называемого вершиной стека.

 Примечания:

При чтении элемента он исключается из стека.
Работает стек по принципу «последним вошел, первым вышел» (LIFO).
Другие операции со стеком не определены.

в языке С/С++
 Определение


Очередь — это частный случай односвязного

(однонаправленного) списка, добавление элементов в который выполняется в конец, а выборка производится из начала списка.

 Примечания:

При чтении элемента он исключается из очереди.
Работает очередь по принципу «первым вошел, первым вышел» (FIFO).
Другие операции с очередью не определены.

языке С/С++

файлами в языке С/С++
 Определение


Бинарное дерево — это динамическая

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

языке С/С++
 Примечания:


На каждый узел имеется ровно одна ссылка.
Узел, не

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

языке С/С++
Пример элемента бинарного дерева:
struct node {
int data;

node *left;
node *right;
};

Пример функции обхода дерева:

function tree_walk (дерево)
{
tree_walk (левое поддерево);
посещение корня;
tree_walk (правое поддерево);
}

языке С/С++

языке С/С++
 Примечания:


При обходе данного дерева по рекурсивному алгоритму «левое

дерево → корень → правое дерево» получим результат: 1, 6, 8, 10, 20, 21, 25, 30.
При обходе данного дерева по рекурсивному алгоритму «правое дерево → корень → левое дерево» получим результат: 30, 25, 21, 20, 10, 8, 6, 1.
С бинарными деревьями можно выполнять следующие операции:
Включение узла в дерево;
Поиск по дереву;
Обход дерева;
Удаление узла.