Лекция 10. Динамические структуры данных (1107985)
Текст из файла
Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.Лекция 10 Динамические структуры данных10.1. Динамическое распределение памяти.10.1.1. Выделение памяти с помощью функции malloc(). Память выделяется во времявыполнения программы.Функция void *malloc(size_t size) выделяет область памяти размеромsize байтов и возвращает указатель на выделенную область памяти. Еслипамять не выделена (например, в системе не осталось свободной памятитребуемого размера) возвращаемый указатель имеет значение null.Замечание. Как уже отмечалось, тип size_t, который определяется какбеззнаковый целочисленный тип результатов операции sizeof.
Посколькуsizeof выдает длину типа в байтах, в качестве size можно использоватьрезультат операции sizeof (Раздел 7.17 Стандарта Си99).Тривиальные примеры:(1) Выделение непрерывного участка памяти объемом 1000 байтов:char *p;p = malloc(1000);(2) Выделение памяти для 50 целых:int *p;p = malloc(50 * sizeof(int));Функция void free(void *p) возвращает системе выделенный ранееучасток памяти с указателем p.Важное замечание: Аргументом функции free() обязательно должен бытьуказатель p на участок памяти, выделенной ранее функцией malloc().
Вызовфункции free() с неправильным указателем (в частности, с указателем null)приводит к разрушению системы распределения памяти.10.1.2. Пример. Динамическое выделение памяти для массива байтов (строки):#include <stdio.h>#include <stdlib.h>#include <string.h>int main() {char *s;register int t;s = malloc(80);if (!s) {printf ("требуемая память не выделена.
\n");return 1 /* исключительная ситуация */}gets(s); /* ввод строки *//* посимвольный вывод строки на экран */for(t = strlen(s) - 1; t>=0; t--) putchar(s[tmp]);free(s);return 0;}(с) Кафедра системного программирования ф-та ВМК МГУ, 20101Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.10.1.3. Пример. Динамическое выделение памяти для двухмерного целочисленногомассива (матрицы):#include <stdio.h>#include <stdlib.h>int pwr(int a, int b)int main() {int (*p)[6];/* (*p), т. к. у []приоритет выше,* чем * у *register int i, j;p = malloc(24 * sizeof(int));if (!s) {printf ("требуемая память не выделена. \n");exit(1)}for (j = 1; j < 7; j++)for (i = 1; i < 5; i++)p[i – 1][j – 1] = pwr(j, i);for (j = 1; j < 7; j++) {for (i = 1; i < 5; i++)printf("%10d "; p[i – 1][j – 1]);printf("\n");}return(0);}int pwr(int a, int b){int t = 1;for (; b; b--) t *= a ;return t;}10.2.
Другие функции динамического распределения памяти из библиотеки stdlib.10.2.1. Помимо функции void *malloc(size_t size) и функции voidfree(void *p) библиотека stdlib (заголовочный файл <stdlib.h>)содержит еще две функции динамического распределения памяти: функциюvoid*realloc(void*p,size_tsize) и функцию void*calloc(size_t num, size_t size).10.2.2. Функция void *realloc(void *p, size_t size) согласно стандарту Си99сначала выполняет free(*p), а потом malloc(size), возвращая новоезначение указателя.
При этом значения первых size байтов новой и старойобластей совпадают.10.2.3. Функция void *calloc(size_t num, size_t size) работает аналогичнофункции malloc(size1), где size1 = num * size (т.е. выделяет память,достаточную для размещения массива, содержащего num объектов размера size).10.3. Динамические структуры данных.10.3.1. Очередь.(с) Кафедра системного программирования ф-та ВМК МГУ, 20102Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.10.3.1.1. Очередь (queue) – это линейный список информации, работа с которойпроисходит по принципу FIFO.
Для списка можно использоватьстатический массив (количество элементов = наибольшей допустимойдлине очереди MAX).10.3.1.2. Работа с очередью осуществляется с помощью двух функций:qstore() – поместить элемент в конец очереди;qretrieve() – удалить элемент из начала очереди;и двух глобальных переменных:spos (индекс первого свободного элемента очереди: его значение <=MAX) и rpos (индекс очередного элемента, подлежащего удалению: «ктопервый?»)10.3.1.3. Тексты функций п°.10.3.1.2.sposНачальноесостояниеrpossposqstore('A')Arpossposqstore('B')ABrpossposqretrieve()Brpos#define MAX67int *queue[MAX];int spos = 0, rpos = 0;void qstore(int *q) {if(spos == MAX) {printf("Очередь переполнена \n");return;}queue[spos] = q;spos++;(с) Кафедра системного программирования ф-та ВМК МГУ, 20103Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.}int *qretrieve() {if(rpos == spos) {printf("Очередь пуста \n");return '\0';}rpos++;return queue[rpos - 1];}10.3.1.4.
Улучшение – «циклическая» очередь. Чтобы не терять начало массива,#define MAX67int *queue[MAX];int spose = 0, rpose = 0;void qstore(int *q) {if(spos + 1 == rpos || (spos + 1 == MAX & !rpos) {printf("Очередь переполнена \n");return;}queue[spos] = q;spos++;if(spos == MAX) spos = 0;}int *qretrieve() {if(rpos == MAX) rpos = 0;if(rpos == spos) {printf("Очередь пуста \n");return '\0';}rpos++;return queue[rpos - 1];}Зацикленная очередь переполняется, когда spos находится непосредственноперед rpos, так как в этом случае запись приведет к rpos == spos, т.е.
кпустой очереди.10.3.2. Стек.10.3.2.1. Стек (stack) – это линейный список информации, работа с которойпроисходит по принципу LIFO.10.3.2.2. Работа со стеком, организованном на базе массива stack[MAX],осуществляется с помощью двух функций:push() – затолкать элемент в стек;pop() – вытолкнуть элемент из стека;и глобальной переменной tos (top of stack). По сравнению с п°.10.3.1. почтиничего нового.(с) Кафедра системного программирования ф-та ВМК МГУ, 20104Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.10.3.2.3 Организация стека на базе динамической памяти.
Помимо указателя tosпотребуется еще один указатель (bottom of stack). В случае массива длиныMAX роль bos играет конец массива.10.3.2.4. Тексты функцийint *st; // указатель стекаint *tos;int *bos;void push (int i) {if(st > bos) {printf("Переполнение стека\n");return;}*st = i;st=++;}int pop(void) {st--;if(st < tos) {printf("Стек пуст\n");return 0;}return *st;}Перед использованием этих функций стек необходимо инициализировать,т.е. выполнить операторы:st = malloc (m); tos = st; bos = st + m;10.3.2.5.
В случае переполнения стека можно не только известить об этомпользователя, но и увеличить стек с помощью операторов:*realloc(st, m + n); bos += n;10.3.3. Применение стека: перевод арифметического выражения в обратную польскуюзапись.(с) Кафедра системного программирования ф-та ВМК МГУ, 20105.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
