Работа с динамической памятью в С

ЛАБОРАТОРНАЯ РАБОТА №6

«Линейные однонаправленные списки»

Цель работы

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

Содержание работы

Для выполнения лабораторной работы необходимо:

· Изучить принципы работы с динамической памятью.

· Изучить способы проектирования линейных списков.

· Спроектировать и отладить программу решения поставленной задачи.

· Составить отчет.

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

Теоретические сведения

Работа с динамической памятью в С

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

В языке программирования C существует и другой способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Такие величины будем называть динамическими. Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью).

При этом способе память распределяется для информации из свободной области памяти по мере необходимости. Область свободной памяти лежит между вашей программой с ее постоянной областью памяти и стеком. Динамическое размещение удобно, когда неизвестно, сколько элементов данных будет обрабатываться. Предложенный ANSI стандарт определяет, что информация, необходимая системе динамического распределения, будет находиться в stdlib.h. Однако, С помещает также информацию заголовка распределения в alloc.h.

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

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

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

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

Распределение памяти представлено на рис.1.

Память системы

Высший адрес

Стековая область

Область свободной памяти для динамического размещения

Область глобальных переменных

Область программы

Работа с динамической памятью в С - student2.ru

Низший адрес

Рис 1. Распределение оперативной памяти для программ на С.

Рис.2.

При работе со списками на практике чаще всего приходится выполнять следующие операции:

- найти элемент с заданным свойством;

- определить первый элемент в линейном списке;

- вставить дополнительный элемент до или после указанного узла;

- исключить определенный элемент из списка;

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

Методы хранения линейных списков разделяются на методы последовательного и связанного хранения. При последовательном хранении элементы линейного списка размещаются в массиве фиксированного размера и длина списка указывается в переменной , т.е. в программе необходимо иметь объявления вида:

float d[100]; int l;

Размер массива 100 ограничивает максимальные размеры линейного списка.

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

typedef struct snd /* структура элемента хранения */

{ float val; /* элемент списка */

struct snd *n ; /* указатель на элемент хранения */

} DL;

DL *p; /* указатель текущего элемента */

DL *dl; /* указатель на начало списка */

Для выделения памяти под элементы хранения необходимо пользоваться функцией malloc(sizeof(DL)) или calloc(l,sizeof(DL)). Формирование списка в связанном хранении может осуществляется операторами:

p=malloc(sizeof(DL));

p->val=10; p->n=NULL;

dl=malloc(sizeof(DL));

dl->val=7; dl->n=p;

В последнем элементе хранения (конец списка) указатель на соседний элемент имеет значение NULL. Получаемый список изображен на рис.3.

Работа с динамической памятью в С - student2.ru

Рис.3.

Постановка задачи

1. Элемент списка должен представлять собой структуру, состоящую из двух полей: одно поле – это какая-либо простейшая информация, заданная типом int или char, если в задании не оговорен какой-либо другой тип. Второе поле будет содержать указатель на следующий элемент списка или будет содержать признак конца списка.

2. Элементы списка должны вводиться с клавиатуры и размещаться в динамической памяти. Должен быть предусмотрен признак конца формирования списка, который сообщается пользователю.

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

4. Затем выполнить действия над элементами списка, заданные в конкретном варианте.

5. Элементы списка для поиска, сравнения, вставки и т.д. в список вводить с клавиатуры.

6. После выполнения преобразования над списком вывести результат на монитор.

Пример решения задачи

Все операции, которые необходимо выполнить над списком, подробно описаны в разделе 3.4.

Пример объявления элемента списка и всех указателей, необходимых для работы со списком (текущий элемент, голова списка и следующий).

typedef struct nd

{ <type> val;

struct nd * next; } ND;

ND * head, * current, * next;

Приняты следующие обозначения в описании вариантов заданий.

Параметры L, L1 и L2 обозначают списки, а параметры Е, E1 и Е2 -- данные типа <type> val, к которым применимы операции присваивания и проверки на равенство.

На рис. 8 представлена схема двух списков: с заглавным звеном и без заглавного звена. Под заглавным звеном подразумевается наличие элемента списка, в котором нет поля со значением, а есть только поле, которое содержит ссылку на начало списка.

Работа с динамической памятью в С - student2.ru
Однонаправленный список без заглавного звена