Лекция 10. Динамические структуры данных (Электронные лекции)
Описание файла
Файл "Лекция 10. Динамические структуры данных" внутри архива находится в папке "Электронные лекции". PDF-файл из архива "Электронные лекции", который расположен в категории "". Всё это находится в предмете "алгоритмы и алгоритмические языки" из 1 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Лекции по курсу “Алгоритмы и алгоритмические языки”, 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.