Разработка программ с использованием динамической памяти
32 ВВЕДЕНИЕНа сегодняшний день всё большее количество людей сталкивается с компьютером, прогресс неумолимо движет нас вперёд. В данное время это обусловлено большими информационными потоками, и необходимо обеспечивать эту отрасль специалистами информационных технологий. Одно из наиболее мощных свойств языка программирования - указатели. Указатели - одна из наиболее трудных для освоения возможностей С. Указатели предоставляют программам возможность моделировать передачу по ссылке и создавать и манипулировать динамическими структурами данных, т.е. структурами данных, которые могут нарастать и сокращаться, например, такими как связные списки, очереди, стеки и деревья. Переменные-указатели содержат в качестве своих значений адреса памяти. Обычно переменная содержит определенное значение. С другой стороны, указатель содержит адрес переменной, которая содержит определенное значение. В этом смысле имя переменной отсылает к значению прямо, а указатель - косвенно. Ссылка на значение посредством указателя называется косвенной адресацией. Указатель - это переменная, содержащая адрес в памяти компьютера. Если удастся осознать смысл этого простого предложения, то это и все, что необходимо знать об указателях. Указатель - это переменная, которая содержит адрес оперативной памяти. Чтобы лучше понять указатели, рассмотрим устройство оперативной памяти компьютера. Оперативная память разделена на последовательно пронумерованные ячейки. Каждая переменная размещается в одной или нескольких последовательно расположенных отдельных ячейках памяти, адрес первой из них называется адресом переменной. Каждая ячейка в оперативной памяти занимает 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). Рисунок 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-ой очереди и выделяет под него память. void proga() - эта функция содержит в себе все выше перечисленные, поэтому она создает первые элементы 1-ой и 2-ой очередей и добавляет в них новые элементы. Также эта функция выводит на экран полученные очереди, то есть выводит на экран все элементы двух очередей, после чего функция производит сравнение: входит ли 1-я очередь во 2-ю, и выводит результат на экран. 3. ИСПОЛЬЗОВАНИЕ ДИНАМИЧЕСКИХ СТРУКТУР ПРИ РАБОТЕ С ГРАФАМИ3.1. Способы представления графовДля представления графа можно использовать матрицу смежности, матрицу инцидентности либо представить его списком дуг. Основные способы представления (задания) графов: 1) перечисление множеств V (вершин) и E (ребер), задающих граф. G = (V, E); 2) матричные способы описания; Пусть G = (V, E), |V| = p, а |E| = q, тогда: a) матрица смежности - квадратная матрица , где b) матрица инцидентности - прямоугольная матрица . 3) список дуг: Пример: задан граф G = (V, E), где V = {v1, v2, v3, v4}, E = {v1v2, v2,v3, v1v3, v1v4, v3,v4} = {e1, e2, e3, e4, e5}. Рисунок 3.1. v2 v1v3v4Рисунок 3.1. - Пример построения графаВ данной программе граф представлен списком дуг, в котором каждая вершина содержит информацию о смежном ей ребре, а каждое ребро содержит информацию о тех вершинах, которые ей смежные. Этот способ более экономичен в плане использования памяти. head: NULLРисунок 3.2. - Пример связности ребер графа3.2. Операции над графамиПри связанном хранении каждая вершина графа представляет собой структуру graf, состоящую из двух элементов: v1,v2 - предназначены для хранения вершин графа, next - для указателя на структуру, содержащую следующую вершину графа. На первые элементы графа указывает указатель head. Для всех операций над графом используется описание: typedef struct graf{ int v1,v2; struct graf* next; } Graf; Graf *g, *head, *temp; Для реализации операций могут использоваться следующие фрагменты программ: 1) определить первый элемент в линейном списке (рисунок 3.1): printf("v1="); scanf("%d",&head->v1); head->next=0; NULL head NULLРисунок 3.3- Создание первого элемента в графе2) вставить дополнительный элемент после указанного узла (рисунок 3.2): printf("v="); scanf("%d",&g->v1); g->next=head; head=g; …. . head NULLРисунок 3.4- Вставка дополнительного элемента3) печать всех элементов списка: printf("Ребра графа: \n"); g=head; i=0; while(g! =NULL) {i++; printf("РЕБРО%d: v1=%d v2=%d\n", i,g->v1,g->v2); g=g->next; }
Страницы: 1, 2
|