Динамическое распределение памяти

Раздел 7. Операции с памятью. Динамические структуры данных Динамическое распределение памяти. Функции malloc() и free(). Calloc (), memcpy (), memset (). Односвязный список Язык С++ поддерживает три основных типа выделения (или «распределения») памяти, с двумя из которых, мы уже знакомы: 1. Статическое выделение памяти выполняется для статических и глобальных переменных. Память выделяется один раз (при запуске программы) и сохраняется на протяжении работы всей программы. 2. Автоматическое выделение памяти выполняется для параметров функции и локальных переменных. Память выделяется при входе в блок, в котором находятся эти переменные, и удаляется при выходе из него. 3. Динамическое выделение памяти Динамическое выделение памяти— это способ запроса памяти из операционной системы запущенными программами по мере необходимости. Эта память не выделяется из ограниченной памяти стека программы, а выделяется из гораздо большего хранилища, управляемого операционной системой — кучи. На современных компьютерах размер кучи может составлять гигабайты памяти. Память, которую используют программы, состоит из нескольких частей — сегментов: Сегмент кода (или «текстовый сегмент»), где находится скомпилированная программа. Обычно доступен только для чтения. Сегмент bss (или «неинициализированный сегмент данных»), где хранятся глобальные и статические переменные, инициализированные нулем. Сегмент данных (или «сегмент инициализированных данных»), где хранятся инициализированные глобальные и статические переменные. Куча, откуда выделяются динамические переменные. Стек вызовов, где хранятся параметры функции, локальные переменные и другая информация, связанная с функциями. Сегмент кучи (или просто «куча») отслеживает память, используемую для динамического выделения. При удалении динамически выделенной переменной, память возвращается обратно в кучу и затем может быть переназначена (исходя из последующих запросов). Помните, что удаление указателя не удаляет переменную, а просто приводит к возврату памяти по этому адресу обратно в операционную систему. Куча имеет свои преимущества и недостатки: 1. Выделение памяти в куче сравнительно медленное. 2. Выделенная память остается выделенной до тех пор, пока не будет освобождена (остерегайтесь утечек памяти) или пока программа не завершит свое выполнение. 3. Доступ к динамически выделенной памяти осуществляется только через указатель. Разыменование указателя происходит медленнее, чем доступ к переменной напрямую. 4. Поскольку куча представляет собой большой резервуар памяти, то именно она используется для выделения больших массивов, структур или классов. Стек вызовов (или просто «стек») отслеживает все активные функции (те, которые были вызваны, но еще не завершены) от начала программы и до текущей точки выполнения, и обрабатывает выделение всех параметров функции и локальных переменных. Стек вызовов реализуется как структура данных «Стек». Поэтому, прежде чем мы поговорим о том, как работает стек вызовов, нам нужно понять, что такое стек как структура данных. Стек как структура данных Структура данных в программировании — это механизм организации данных для их эффективного использования. Нам известны несколько типов структур данных, например, массивы или структуры. Существует множество других структур данных, которые используются в программировании. Некоторые из них реализованы в Стандартной библиотеке C++, и стек как раз является одним из таковых. В компьютерном программировании стек представляет собой контейнер (как структуру данных), который содержит несколько переменных (подобно массиву). Однако, в то время как массив позволяет получить доступ и изменять элементы в любом порядке (так называемый «произвольный доступ»), стек более ограничен. В стеке можно: 1. Посмотреть на верхний элемент стека. 2. Вытянуть верхний элемент стека. 2. Добавить новый элемент поверх стека. Стек — это структура данных типа LIFO (англ. «Last In, First Out = «Последним пришел, первым ушел»). Последний элемент, который находится на вершине стека, первым и уйдет из него. Если положить новую тарелку поверх других тарелок, то именно эту тарелку вы первой и возьмете. По мере того, как элементы помещаются в стек — стек растет по мере того, как элементы удаляются из стека — стек уменьшается. Сегмент стека вызовов содержит память, используемую для стека вызовов. При запуске программы, функция main() помещается в стек вызовов операционной системой. Затем программа начинает свое выполнение. Когда программа встречает вызов функции, то эта функция помещается в стек вызовов. При завершении выполнения функции, она удаляется из стека вызовов. Таким образом, просматривая функции, добавленные в стек, мы можем видеть все функции, которые были вызваны до текущей точки выполнения. Давайте рассмотрим детально, как работает стек вызовов. Ниже приведена последовательность шагов, выполняемых при вызове функции: -- Программа сталкивается с вызовом функции. -- Создается фрейм стека, который помещается в стек. Он состоит из: 1. адреса инструкции, который находится за вызовом функции (так называемый «обратный адрес»). Так процессор запоминает, куда ему возвращаться после выполнения функции; 2. аргументов функции; 3. памяти для локальных переменных; 4. сохраненных копий всех регистров, модифицированных функцией, которые необходимо будет восстановить после того, как функция завершит свое выполнение. -- Процессор переходит к точке начала выполнения функции. -- Инструкции внутри функции начинают выполняться. После завершения функции, выполняются следующие шаги: -- Регистры восстанавливаются из стека вызовов. -- Фрейм стека вытягивается из стека. Освобождается память, которая была выделена для всех локальных переменных и аргументов. -- Обрабатывается возвращаемое значение. -- ЦП возобновляет выполнение кода (исходя из обратного адреса). Стек имеет ограниченный размер и, следовательно, может содержать только ограниченный объем информации. В операционной системе Windows размер стека по умолчанию составляет 1МБ. На некоторых Unix-системах этот размер может достигать и 8 МБ. Если программа пытается поместить в стек слишком много информации, то это приведет к переполнению стека. Переполнение стека (англ. «stack overflow») происходит, когда запрашиваемой памяти нет в наличии (вся память уже занята). Переполнение стека является результатом добавления слишком большого количества переменных в стек и/или создания слишком большого количества вложенных вызовов функций (например, когда функция A() вызывает функцию B(), которая вызывает функцию C(), а та, в свою очередь, вызывает функцию D() и т.д.). Переполнение стека обычно приводит к сбою в программе. Стек имеет свои преимущества и недостатки: 1. Выделение памяти в стеке происходит сравнительно быстро. 2. Память, выделенная в стеке, остается в области видимости до тех пор, пока находится в стеке. Она уничтожается при выходе из стека. 3. Вся память, выделенная в стеке, обрабатывается во время компиляции, следовательно, доступ к этой памяти осуществляется напрямую через переменные. 4. Поскольку размер стека является относительно небольшим, то не рекомендуется делать что-либо, что съест много памяти стека (например, передача по значению или создание локальных переменных больших массивов или других затратных структур данных). В памяти компьютера программа на Си организована следующим образом: - Сегмент данных (Data, bss-сегмент и куча) - Сегмент стека - Сегмент кода Структура программы на си. Data SEGMENT cостоит из статических и глобальных переменных, которые явно инициализируются значениями. Этот сегмент может быть далее разбит на ro-data (read only data) – сегмент данных только для чтения, и rw-data (read write data) – сегмент данных для чтения и записи. BSS-сегмент (block started by symbol) содержит неинициализированные глобальные переменные, или статические переменные без явной инициализации. Этот сегмент начинается непосредственно за data-сегментом. Обычно загрузчик программ инициализирует bss область при загрузке приложения нулями. За счёт этого и неинициализированные глобальные переменные, и статические переменные по умолчанию равны нулю. Куча (HEAP) – начинается за BSS сегментом и начиная оттуда, растёт соответственно с увеличением адреса. Этот участок используется для выделения на нём памяти с использованием функции malloc (и прочих) и для очисти с помощью функции free. Стек вызовов обычно растёт "навстречу" куче, то есть с увеличением стека адрес вершины стека уменьшается. Набор значений, которые кладутся на стек одной функцией, называются фреймом. После выхода из функции стек освобождается от фрейма. Один фрейм хранит как минимум одно значение - адрес возврата. Каждый раз, когда мы создаём локальные переменные, они располагаются на стеке. Как только мы выходим из функции, стек очищается и переменные исчезают. Вызов функций и передача параметров также происходит через стек. Сегмент кода, или текстовый сегмент, или просто текст программы, содержит исполняемые инструкции. У него фиксированный размер и обычно он используется только для чтения, если же в него можно писать, то архитектура поддерживает самомодификацию. Сегмент кода располагается после начала стека, поэтому в случае роста он [стек] не перекрывает сегмент кода. Итак, в языке Си принято следующее распределение памяти: СТЕК Верхние адреса СВОБОДНАЯ ПАМЯТЬ РАЗДЕЛ ГЛОБАЛЬНЫХ ПЕРЕМЕННЫХ И КОНСТАНТ КОД ПРОГРАММЫ Нижние адреса Для глобальных переменных отводится фиксированное место в памяти на все время работы программы. Локальные переменные хранятся в стеке. Между ними находится область памяти для динамического распределения (куча - Heap). Стек — это очень быстрое хранилище памяти, управляемое процессором. Но эти преимущества приводят к ограниченному размеру стека и специальному способу получения значений. Без стека невозможна рекурсия, так как при любом повторном входе в функцию требуется сохранение текущего состояния на вершине, причём при каждом выходе из функции, нужно быстро восстанавливать это состояние. Для того, чтобы избежать этих ограничений, можно пользоваться кучей — она позволяет создавать динамические и глобальные переменные — но управлять памятью должен либо сборщик мусора, либо сам программист, да и работает куча медленнее. Взаимодействовать с кучей нужно посредством ссылок, обычно называемых указателями — это переменные, чьи значения являются адресами других переменных. Создавая указатель, указываем на местоположение памяти в куче, что задаёт начальное значение переменной и говорит программе, где получить доступ к этому значению. Из-за динамической природы кучи ЦП не принимает участия в контроле над ней; в языках без сборщика мусора (C, C++) разработчику нужно вручную освобождать участки памяти, которые больше не нужны. Для использования функций динамического выделения памяти необходимо описать указатель, представляющий собой начальный адрес хранения элемента: int *p; // указатель на тип int Функции динамического выделения памяти находят в оперативной памяти непрерывный участок требуемой длины и возвращают начальный адрес этого участка. C/С++ содержит два оператора, выполняющих выделение и освобождение памяти более эффективно и более просто. Этими операторами являются new и delete. Их общая форма имеет вид: тип_данных *имя_указателя = new тип_данных; delete имя_указателя; Например: int *a = new int; delete a; Оператор new выделяет память для хранения значения типа тип_данных и возвращает ее адрес. С помощью new могут быть размещены любые типы данных. Оператор delete освобождает память, на которую указывает указатель имя_указателя. Функции динамического распределения памяти в языке С: void* malloc(РазмерМассиваВБайтах); Функция malloc( ) выделяет память, функция free( ) освобождает ее. Функция malloc( ) возвращает указатель типа void, значение функции надо преобразовать к указателю на соответствующий тип. При успешном выполнении функция возвращает указатель на первый байт свободной памяти размера size. Если достаточного количества памяти нет, возвращается значение 0. Чтобы определить количество байтов, необходимых для переменной, используют операцию sizeof( ). void* calloc(ЧислоЭлементов, РазмерЭлементаВБайтах);   calloc выделяет n объектов размером m и заполняет их нулями. Обычно она используется для выделения памяти под массивы. Для использования функций динамического распределения памяти необходимо подключение библиотек , .   Поскольку обе представленные функции в качестве возвращаемого значения имеют указатель на пустой тип void, требуется явное приведение типа возвращаемого значения. Память, динамически выделенная с использованием функций calloc(), malloc(), может быть освобождена с использованием функции: free(указатель); Пример использования этих функций: #define _CRT_SECURE_NO_WARNINGS #include #include #include #include int main() { int *p, i; p = (int*) malloc (100 * sizeof(int)); /* Выделение памяти для 100 целых чисел */ if (!p) { printf("Недостаточно памяти\n"); exit (1); } for (i = 0; i < 100; ++i) *(p + i) = i; /* Использование памяти */ for (i = 0; i < 100; ++i) printf ("%4d", *(p++)); free(p); /* Освобождение памяти */ p = NULL; _getch(); } Перед использованием указателя, возвращаемого malloc( ), необходимо убедиться, что памяти достаточно (указатель не нулевой). Функции динамического распределения памяти (продолжение): void *memcpy (void *dest, const void *source, size_t count) Функция memcpy() копирует count символов из массива, на который указывает source, в массив, на который указывает dest. Если массивы перекрываются, поведение memcpy() не определено. Функция memcpy() возвращает указатель на dest. #include #define SIZE 80 int main(void) { char buf1[SIZE], buf2[SIZE]; strcpy (buf1, "Какой-то текст..."); memcpy (buf2, buf1, SIZE); printf (buf2); return 0; } void *memset (void *buf, int ch, size_t count) Функция memset() копирует младший байт ch в первые count символов массива, на который указывает buf. Функция возвращает buf. Чаще всего memset() используется для присвоения начальных значений определенной области памяти. Следующий фрагмент программы присваивает начальные значения 0 первым ста байтам массива, на который указывает buf, затем записывает в первые 10 байт символ '*' и выводит на экран строку «**********»: memset (buf, '\0', 100); memset (buf, '*', 10) printf ((char *) buf); Динамические массивы. Динамический массив – массив переменной длины, память под который выделяется в процессе выполнения программы. При каждом запуске программы, можно определять массив с разным количеством элементов, после того как массив не используется, память можно освободить, затем опять выделить и т.д. Для этого необходимо выполнить следующие действия (первый способ) : 1. Описать указатель (например, переменную p) определенного типа. 2. Начиная с адреса, определенного указателем, с помощью функций calloc, malloc или операции new выделить участок памяти определенного размера. После этого p будет адресом первого элемента выделенного участка оперативной памяти (0-й элемент массива), p+1 будет адресовать – следующий элемент в выделенном участке памяти (1-й элемент динамического массива), …, p+i является адресом i-го элемента. Необходимо только следить, чтобы не выйти за границы выделенного участка памяти. К i-му элементу динамического массива p можно обратиться одним из двух способов: *(p+i) или p[i] 3. Когда участок памяти будет не нужен, его можно освободить с помощью функции free(), операции delete. Возможен также другой способ динамического выделения памяти под двумерный массив - с использованием массива указателей. Для этого необходимо: выделить блок оперативной памяти под массив указателей; выделить блоки оперативной памяти под одномерные массивы, представляющие собой строки искомой матрицы; записать адреса строк в массив указателей. Графически такой способ выделения памяти можно представить так. При таком способе выделения памяти компилятору явно указано количество строк и количество столбцов в массиве. #include #include #include #include #include int main (int argc, char* argv[]) { int **arr; //это указатель на указатель на int int i, j, n, m; srand (time (NULL)); //вводим n и m с клавиатуры printf ("Input number of rows: "); scanf_s ("%d", &n); printf ("\nInput number of cols: "); scanf_s("%d", &m); //выделяем память под массив указателей arr = (int**)calloc(n, sizeof(*arr)); //arr теперь указывает на массив указателей на int //выделяем память для каждой строки массива for (i = 0; i < n; ++i) arr[i] = (int*) calloc (m, sizeof(*arr[i])); //теперь можно получить доступ к каждому элементу двумерного массива: arr[i][j], где 0 <= i < n, 0 <= j < m printf ("\nDynamic matrix:\n\n"); for (i = 0; i < n; ++i) { for (j = 0; j < m; ++j) { arr[i][j] = rand () % 100 - 50; printf ("%3d ", arr[i][j]); } printf("\n\n"); } //после завершения работы с массивом, необходимо освободить всю выделенную память for (i = 0; i < n; ++i) { free(arr); arr = NULL; } _getch (); system("pause"); return 0; } ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ При программировании реальных задач очень часто программисты сталкиваются с проблемой организации гибкого подхода к объемам обрабатываемой информации, которая тесно взаимосвязана с задачей создания эффективных программ. Эта проблема состоит в том, что во многих задачах нельзя заранее предугадать точное количество данных, а, следовательно, и количество переменных для их хранения. Выходом в этой ситуации стало создание целого класса динамических структур данных, которые обладают всеми свойствами типов данных, но исходя из сложности их воплощения отдельно, они реализуются на базе уже существующих типов данных. Главной их отличительной особенностью является возможность быстрого и гибкого видоизменения в процессе работы программы. Наиболее удобной базой для их построения стали структуры. Оказалось, что возможность использования в составе структур указателей того же типа, что и сам структурный тип, связана с целым рядом новых свойств. На их основе строятся динамические структуры данных: списки, буферы, стеки, деревья. Прежде чем переходить к описанию структур, следует запомнить несколько простых определений: Потомок (следующий) — элемент (узел) структуры, идущий после текущего. В зависимости от вида динамической структуры у элемента может быть более одного потомка. Предок (предыдущий) — элемент структуры, идущий до текущего. Головной элемент (корень, голова -- Head) — первый элемент списка. Хвостовой элемент (последний, хвост -- Tail) — последний элемент списка. Структура данных Список Список — это линейная динамическая структура данных, у каждого элемента может быть только один предок и только один потомок и в которой каждый элемент (узел) хранит информацию, а также ссылку на следующий элемент. Последний элемент списка ссылается на NULL. По сути своей это очень похоже на обыкновенный массив, с той лишь разницей, что размер его не имеет ограничений. рис. 1. Списковая структура Основные свойства списка: · элемент списка доступен в программе через указатель. «Смысл» этого указателя отражает функциональное назначение элемента списка в программе: первый, последний, текущий, предыдущий, новый и т.п. . Между указателем и элементом списка имеется такая же взаимосвязь, как между индексом в массиве и элементом массива; · в программе список задается посредством заголовка – указателя на первый элемент списка; · порядок следования элементов определяется последовательностью связей между элементами. Изменение порядка следования элементов (вставка, удаление) осуществляются изменением переустановкой указателей на соседние элементы. · логический (порядковый) номер элемента списка также задается его естественной нумерацией в цепочке элементов; · список является структурой данных с последовательным доступом. Для получения n-го по счету элемента необходимо последовательно пройти по цепочке от элемента, на который имеется указатель (например, от заголовка); · список удобен для использования именно как динамическая структура данных: элементы списка обычно создаются как динамические переменные, а связи между ними устанавливаются программно (динамически); · список обладает свойством локальности изменений: при вставке/удалении элемента изменения касаются только текущего и его соседей. Вспомним массив: при вставке/удалении его элементов происходит физическое перемещение (сдвиг) всех элементов от текущего до конца. Списки также подразделяются на несколько типов. Односвязный (однонаправленный) список — элемент имеет указатель только на своего потомка. Односвязный список Двусвязный (двунаправленный) список — элемент имеет указатели и на потомка, и на родителя. Двусвязный список Замкнутый (кольцевой, циклический) список — головной и хвостовой элементы которого указывают друг на друга. Замкнутый список На базе простого однонаправленного списка могут быть построены такие структуры данных, как очередь (queue), стек (stack) и дерево. Очередь — это список, операции чтения и добавления элементов, в котором подвержены определенным правилам. При этом, при чтении элемента, он удаляется из очереди. Все операции проводятся по принципу «Первый пришел, первый вышел» (FIFO — first in, first out). Таким образом, для чтения в очереди доступна только голова, в то время как добавление проводится только в хвост. Стек — это структура данных, представляющая собой специализированным образом организованный список элементов. Доступ к элементам стека осуществляется по принципу LIFO (Last In First Out) — последним пришел, первым вышел. Односвязный список Пример: Рис. 1. Односвязный список из целых чисел Каждый узел однонаправленного (односвязного) линейного списка содержит одно поле указателя на следующий узел. Поле указателя последнего узла содержит нулевое значение (указывает на NULL). Узел можно представить в виде структуры: struct list { int field; // поле данных struct list *ptr; // указатель на следующий элемент }; Основные действия, производимые над элементами: Инициализация списка Добавление узла в список Удаление узла из списка Удаление корня списка Вывод элементов списка list *root; // объявим указатель на первый элемент(корень) Вначале список пустой: list *root=NULL; // Список пустой Инициализация списка Инициализация списка предназначена для создания корневого узла списка, у которого поле указателя на следующий элемент содержит нулевое значение. struct list * init (int a) // а- значение первого узла { struct list *lst; // выделение памяти под корень списка ls = (struct list*) malloc (sizeof (struct list)); lst->field = a; lst->ptr = NULL; // это последний узел списка return(lst); } Добавление узла в список Функция добавления узла в список принимает два аргумента: 1. Указатель на узел, после которого происходит добавление 2. Данные для добавляемого узла. Процедуру добавления узла можно отобразить следующей схемой: Добавление узла включает в себя следующие этапы: создание добавляемого узла и заполнение его поля данных; 1. переустановка указателя узла, предшествующего добавляемому, на добавляемый узел; 2. установка указателя добавляемого узла на следующий узел (тот, на который указывал предшествующий узел). 3. установка указателя добавляемого узла на следующий узел (тот, на который указывал предшествующий узел). Таким образом, функция добавления узла может иметь вид: struct list *addelem (list *lst, int number) { struct list *temp, *p; temp = (struct list*) malloc(sizeof(list)); p = lst->ptr; // сохранение указателя на следующий узел lst->ptr = temp; // предыдущий узел указывает на создаваемый temp->field = number; // сохранение поля данных добавляемого узла temp->ptr = p; // созданный узел указывает на следующий элемент return(temp); } Возвращаемым значением функции является адрес добавленного узла. Удаление узла В качестве аргументов функции удаления элемента передаются указатель на удаляемый узел, а также указатель на корень списка. Функция возвращает указатель на узел, следующий за удаляемым. Удаление узла может быть представлено следующей схемой: Удаление узла включает в себя следующие этапы: 1. установка указателя предыдущего узла на узел, следующий за удаляемым; 2. освобождение памяти удаляемого узла. struct list * deletelem(list *lst, list *root) {   struct list *temp;   temp = root;   while (temp->ptr != lst) // просматриваем список начиная с корня   { // пока не найдем узел, предшествующий lst     temp = temp->ptr;   }   temp->ptr = lst->ptr; // переставляем указатель   free(lst); // освобождаем память удаляемого узла   return(temp); } Удаление корня списка Функция удаления корня списка в качестве аргумента получает указатель на текущий корень списка. Возвращаемым значением будет новый корень списка — тот узел, на который указывает удаляемый корень. struct list * deletehead(list *root) {   struct list *temp;   temp = root->ptr;   free(root); // освобождение памяти текущего корня   return(temp); // новый корень списка } Вывод элементов списка В качестве аргумента в функцию вывода элементов передается указатель на корень списка. Функция осуществляет последовательный обход всех узлов с выводом их значений. void listprint (list *lst) { struct list *p; p = lst; do { printf ("%d ", p->field); // вывод значения элемента p p = p->ptr; // переход к следующему узлу } while (p != NULL); } Пример. Сформировать список, содержащий целые числа 3, 5, 1, 9. Решение. При работе с динамическими структурами данных можно рекомендовать следующий порядок действий. а) Прежде всего необходимо определить две структуры: 1. структура, содержащая характеристики данных, то есть все те поля с данными, которые необходимы для решения поставленной задачи (в нашем случае имеется всего одно поле целого типа). Назовём эту структуру Data; 2. структура, содержащая поле типа Data и поле — адрес последующего элемента next. Вторую структуру назовём List. Тексты этих структур необходимо расположить в начале программы (до main() и других функций). Вот возможная реализация структур: struct Data { int a; }; struct List { Data d; List *next; }; Такой подход позволит в дальнейшем изменять в широких пределах структуру с собственно данными, никак не затрагивая при этом основную структуру List. Итак, мы описали структурный тип, с помощью которого можно создать наш односвязный список. Графически создаваемый список можно изобразить так, как это показано на рисунке ниже: б) В программе (обычно в функции main()) определяем указатель на начало будущего списка: List *u = NULL; Пока список пуст, и указатель явно задан равным константе NULL. в) Выполняем первоначальное заполнение списка. Создадим первый элемент: u = new List; // Выделяем память под элемент списка u->d.a = 3; // Заполняем поля с данными — это всего одно поле u->next = NULL;// Указатель на следующий элемент пуст После включения первого элемента список можно изобразить так: Продолжим формирование списка, добавляя новые элементы в его конец. Для удобства заведём вспомогательную переменную-указатель, которая будет хранить адрес последнего элемента списка: List *x; x = u; // Сейчас последний элемент списка совпадает с его началом Таким образом, к области памяти можно обратиться через два указателя. Выделяем место в памяти для следующего элемента списка и перенаправляем указатель x на выделенную область памяти: x->next = new List; x = x->next; Затем определяем значение этого элемента списка: x->d.a = 5; x->next = NULL; Получилась такая схема: Этот процесс продолжаем до тех пор, пока не будет сформирован весь список. Действия со сформированным списком Сформировав начальный список, можно выполнять с ним различные действия. Рекомендуется каждую операцию со списком оформлять в виде отдельной функции. Такой подход заметно упрощает разработку программы и возможную её дальнейшую модификацию. Понятно, что и только что рассмотренное формирование начального списка также лучше записать в виде функции. 1. Просмотр списка — осуществляется последовательно, начиная с его начала. Указатель последовательно ссылается на первый, второй, и т.д. элементы списка до тех пор, пока весь список не будет пройден. Приведём пример реализации просмотра, например, для вывода списка на экран монитора: void Print (List *u) { List *p = u; cout << "Spisok:" << endl; while(p) { cout << p->d.a << endl; p = p->next; } } Обратиться к функции можно так: Print(u); Здесь и далее в примерах u — это указатель на начало (корень) списка. 2. Поиск первого вхождения в список элемента, соответствующего заданным требованиям: List * Find (List *u, Data &x) { List *p = u; while(p) { if(p->d.a == x.a) // условие для поиска return p; p = p->next; } return 0; } Возможный вызов функции: List * v = Find (u, x); где x — объект типа Data. 3. Добавление нового элемента в начало списка: void Add_Beg (List **u, Data &x) { List *t = new List; t->d.a = x.a; t->next = *u; *u = t; } Возможный вызов функции: Add_Beg(&u, x); , где x — объект типа Data. 4. Вставка нового элемента в произвольное место списка по какому-нибудь принципу, например, вставка в отсортированный по возрастанию список: void Insert (List **u, Data &x) { // вставка в список одного элемента перед элементом, // меньшим или равным данному x List *p = new List; p->d.a = x.a; if(*u == 0) // исходный список пуст - вставка в начало { p->next = 0; *u = p; return; } List *t = *u; if(t->d.a >= p->d.a) // исходный список не пуст - // вставка в начало { p->next = t; *u = p; return; } List *t1 = t->next; while(t1) { if(t->d.a < p->d.a && p->d.a <= t1->d.a) { // вставка в середину t->next = p; p->next = t1; return; } t = t1; t1 = t1->next; } t->next = p; // добавляем в конец списка p->next = 0; } Возможный вызов функции: Insert (&u, x); , где x — объект типа Data. Эта функция позволяет сразу формировать упорядоченный список. 5. Удаление элемента из линейного списка: void Delete (List **u, Data &x) { if(*u == 0) // исходный список пуст - удалять нечего! { return; } List *t = *u; if(t->d.a == x.a) // исходный список не пуст - // удаляется начало { *u = t->next; delete t; return; } List *t1 = t->next; while(t1) { if(t1->d.a == x.a) // исходный список не пуст - //удаляется не первый элемент { t->next = t1->next; delete t1; return; } t = t1; t1 = t1->next; } } Возможный вызов функции: Delete(&u, x); , где x — объект типа Data. 6. Удаление (очистка) всего списка Когда данные, хранящиеся в списке, становятся ненужными, можно очистить весь список, т.е. освободить память, которую занимали все элементы списка. Выполнять эту операцию желательно сразу после того, как список стал не нужен. Реализация этой операции может быть такой: void Clear(List **u) { // удаление (очистка) всего списка if(*u == 0) return; List *p = *u; List *t; //локальная while(p) { t = p; p = p->next; delete t; } *u = 0; } Возможный вызов функции: Clear(&u); Мы рассмотрели наиболее важные действия со списками. По аналогии с ними можно реализовать и другие действия, которые могут потребоваться для решения практических задач. Пример 1 работы со списком: #include #include #include typedef int tData; typedef struct sNode { tData value; struct sNode* next; } tNode; tNode* create_list (int N) //заполним односвязный список { tNode* p_begin = NULL; tNode* p = NULL; p_begin = (tNode*) malloc(sizeof(tNode)); p = p_begin; p->next = NULL; p->value = 0; for (int k = 1; k < N; k++) { p->next = (tNode*) malloc(sizeof(tNode)); p = p->next; //шагнуть вперед !!! //заполнить _новую_ структуру данных p->next = NULL; p->value = k; } return p_begin; } void print_list (tNode* p_begin) //распечатаем односвязный список { tNode* p = p_begin; while (p != NULL) { printf ("%d \t", p->value); //распечатать структуру данных p = p->next; //шагнуть вперед !!! } printf (" \n "); } void delete_list (tNode* p_begin) { tNode* p = p_begin; while (p != NULL) { tNode* tmp; tmp = p; p = p->next; //шагнуть вперед!!! free(tmp); //удалить память ячейки } } int main () { do { printf ("Список создан! \n"); tNode* p_begin = create_list (10); printf ("Список распечатан! \n"); print_list(p_begin); printf ("Список удален! \n"); delete_list(p_begin); printf (" \n "); system("pause"); } while (_getch () != 27); }