Разработка программ с использованием динамической памяти (стр. 1 из 3)
ВВЕДЕНИЕ
На сегодняшний день всё большее количество людей сталкивается с компьютером, прогресс неумолимо движет нас вперёд. В данное время это обусловлено большими информационными потоками, и необходимо обеспечивать эту отрасль специалистами информационных технологий.
Одно из наиболее мощных свойств языка программирования – указатели. Указатели – одна из наиболее трудных для освоения возможностей С. Указатели предоставляют программам возможность моделировать передачу по ссылке и создавать и манипулировать динамическими структурами данных, т.е. структурами данных, которые могут нарастать и сокращаться, например, такими как связные списки, очереди, стеки и деревья.
Переменные-указатели содержат в качестве своих значений адреса памяти. Обычно переменная содержит определенное значение. С другой стороны, указатель содержит адрес переменной, которая содержит определенное значение. В этом смысле имя переменной отсылает к значению прямо, а указатель – косвенно. Ссылка на значение посредством указателя называется косвенной адресацией.
Указатель – это переменная, содержащая адрес в памяти компьютера. Если удастся осознать смысл этого простого предложения, то это и все, что необходимо знать об указателях. Указатель – это переменная, которая содержит адрес оперативной памяти.
Чтобы лучше понять указатели, рассмотрим устройство оперативной памяти компьютера. Оперативная память разделена на последовательно пронумерованные ячейки. Каждая переменная размещается в одной или нескольких последовательно расположенных отдельных ячейках памяти, адрес первой из них называется адресом переменной. Каждая ячейка в оперативной памяти занимает 1 байт или 8 бит.
1. ПОСТАНОВКА ЗАДАЧИ
Задание №1:
Описать функцию, которая меняет местами первый и предпоследний элемент непустой очереди.
Входные данные:
Запись{inf}: цел – элементы очереди;
Промежуточные данные:
kol: цел – счетчик(номера элементов очереди);
key: сим – клавиша события;
tmp: сим – временный массив символов;
Ограничения:
нет
Задание №2:
Определить количество изолированных вершин неориентированного графа, вывести их список. Сделать выбранную вершину неизолированной.
Входные данные:
Запись {v1, v2}: цел – 1-я и 2-я вершины одного ребра;
n: цел – общее количество вершин в графе.
Промежуточные данные:
i: цел – счетчик(номера элементов 1-ой очереди);
f: цел – счетчик(проверка на существование висячих вершин);
ch: сим – клавиша события;
s,s1: сим – строки, которые нужны для проверки введенных результатов;
v [10]: сим – показатель степени данной вершины.
Ограничения:
2<=n<=5;
1<=v1<=n;
1<=v2<=n;
v1<>v2.
Выходные данные:
Запись {v1, v2}: цел – граф после удаления одной из висячих вершин.
2. ОБРАБОТКА СПИСКОВ
2.1. Описание структуры списка
Линейный список - это конечная последовательность однотипных элементов (узлов), возможно, с повторениями. Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться. Линейный список F, состоящий из элементов D1,D2,...,Dn, записывают в виде последовательности значений заключенной в угловые скобки F=, или представляют графически (рисунок 2.1).
| D1 | | D2 | | D3 | | ... | | Dn |
Рисунок 2.1. - Изображение линейного списка
Например, F1=< 2,3,1>,F2=< 7,7,7,2,1,12 >, F3=< >. Длина списков F1, F2, F3 равна соответственно 3,6,0. В реальных языках программирования нет какой-либо структуры данных для представления линейного списка. Поэтому при работе с линейными списками важным является представление используемых в программе линейных списков таким образом, чтобы была обеспечена максимальная эффективность и по времени выполнения программы, и по объему требуемой памяти. Методы хранения линейных списков разделяются на методы последовательного и связанного хранения. При последовательном хранении элементы линейного списка размещаются в массиве d фиксированных размеров, например, 100, и длина списка указывается в переменной l, т.е. в программе необходимо иметь объявления вида
float d [100] ; int l;
Размер массива 100 ограничивает максимальные размеры линейного списка. Список F в массиве d формируется так:
d [0] =7; d [1] =10; l=2;
Полученный список хранится в памяти согласно схеме на рисунке 2.2.
| l: | 2 | ||||||
| d: | 7 | 10 | ... | ||||
| [0] | [1] | [2] | [3] | [98] | [99] | ||
| Рисунок 2.2. – Последовательное хранение линейного списка | |||||||
При связанном хранении в качестве элементов хранения используются структуры, связанные по одной из компонент в цепочку, на начало которой (первую структуру) указывает указатель 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. Получаемый список изображен на рисунке 2.3.
Рисунок 2.3. – Связное хранение линейного списка
2.2. Операции над элементами списка
При простом связанном хранении каждый элемент списка представляет собой структуру graf, состоящую из двух элементов: v - предназначен для хранения элемента списка, next - для указателя на структуру, содержащую следующий элемент списка. На первый элемент списка указывает указатель head. Для всех операций над списком используется описание:
typedef struct graf
{ int v;
struct graf* next;
} Graf;
Graf *g, *head, *teil;
Для реализации операций могут использоваться следующие фрагменты программ:
1) определить первый элемент в линейном списке (рисунок 2.4):
printf("v=");
scanf("%d",&head->v);
head->next=0;
teil->next=0;
teil=head;
 |
head: NULL
Рисунок 2.4. – Создание первого элемента в списке
2) вставить дополнительный элемент после указанного узла (рисунок 2.5):
printf("v=");
scanf("%d",&g->v);
teil->next=g;
teil=teil->next;head: NULL
Рисунок 2.5. – Вставка дополнительного элемента
3) печать всех элементов списка:
g=head;
i=0;
while(g! =NULL)
{
i++;
printf("Эллемент%d:%d\n", i,g->v1);
g=g->next;
}
2.3. Описание программной реализации
Данная программа реализована с помощью пяти функций, которые частично демонстрируют работу с такой структурой данных как очередь.
Очередь аналогична очереди людей в супермаркете: первый клиент в ней обслуживается первым, а другие клиенты занимают очередь с конца и ожидают, когда их обслужат. Узлы очереди удаляются только из головы очереди, а помещаются в очередь только в ее хвост. По этой причине, очередь – это структура данных типа "первым вошел – первым вышел" (first-in, first-out – FIFO). У очередей имеется множество применений в вычислительных системах. У большинства компьютеров имеется только один процессор, поэтому в один и тот же момент времени может быть обслужен только один пользователь. Запросы остальных пользователей помещаются в очередь. Каждый запрос постепенно продвигается в очереди вперед по мере того, как происходит обслуживание пользователей. Запрос в начале очереди является очередным кандидатом на обслуживание.
Первые четыре функции для формирования очереди похожи между собой: первые две из них: vvod1 и vvod2 нужны для созданий первых элементов двух очередей. Две остальные: dobavl1 и dobavl2, для добавления новых элементов в уже созданные нами очереди. Последняя функция: proga, содержит первые четыре и ряд новых возможностей, в который входят: возможность вывода на экран всех элементов очередей, а также возможность проверки на вхождение всех элементов первой очереди во вторую. Так как структуры можно сравнивать только поэлементно в данной функции в цикле каждый элемент сравнивается с отдельными элементами второй очереди, если элемент первой очереди встречается во второй, значит что этот элемент входит во вторую очередь. В конце расчетов на экран пользователю выводится соответствующее сообщение о том, есть ли вхождение одной очереди в другую или его нет.
2.3.1. Описание процедур и функций языка
void *malloc(size_t size) – данная функция используется для выделения памяти из кучи в байтах. Для таких информационных структур, таких как деревья и списки выделение памяти происходит таким же способом
void free(void *block) – данная функция очищает память, которая была выделена такими функциями как calloc, malloc или realloc.
2.3.2. Описание созданных функций для работы со списками
void vvod1() – данная функция создает первый элемент очереди под номером 1 и, используя стандартную функцию malloc, выделят определенное количество памяти под этот первый элемент;
void dobavl1() – функция в цикле, до нажатия клавиши Esc, каждый раз добавляет новый элемент 1-ой очереди и выделяет под него память.
void vvod2() – данная функция создает первый элемент очереди под номером 2 и, используя стандартную функцию malloc, выделят определенное количество памяти под этот первый элемент;
void dobavl2() – функция в цикле, до нажатия клавиши Esc, каждый раз добавляет новый элемент 2-ой очереди и выделяет под него память.