ПРОГРАММИРОВАНИЕ/ ЯЗЫКИ ПРОГРАММИРОВАНИЯ Лекция 5 Структуры данных (весенний семестр 2012 г.) Доцент Кафедры вычислительных систем, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ»

Кардинальные числа типов данных 2 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Общим свойством структур данных, изученных к настоящему моменту: 1) скалярных переменных; 2) статических массивов; 3) структур; является то, что их кардинальное число (количество элементов) конечно. Представление таких структур в памяти компьютера является достаточно простым. Большинство усложненных структур : 1) последовательности; 2) деревья; 3) графы; характеризуются тем, что их кардинальные числа бесконечны.

Последовательность 3 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Последовательность с базовым типом T 0 это либо пустая последовательность, либо конкатенация последовательности (с базовым типом T 0 ) и значения типа T 0. Например, пусть базовый тип – char (символ), тогда: 1) S 1 = - пустая последовательность 2) S 2 = a, b, c = a, b & c = ( a & b) & c = (( &a ) & b) & c, где "&" – операция конкатенации (сцепления, склеивания). Если x = x 1, x 2, …, x n - непустая последовательность, то first(x) = x 1 обозначает ее первый элемент. Если x = x 1, x 2, …, x n - непустая последовательность, то rest(x) = x 2, …, x n обозначает последовательность без ее первой компоненты. Справедливо: x first(x) & rest(x). Кардинальное число последовательности не ограничено.

Динамическая память 4 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Инструменты работы с динамической памятью позволяют обеспечить изменение размера выделенной памяти с сохранением ее содержимого. Для этого используется функция realloc. Изменение размера динамически выделенной области может приводить к значительным накладным расходам Частое применение операции realloc нежелательно Динамическая память

Динамически-расширяемый массив 5 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Для уменьшения количества вызовов функции realloc может быть эффективно применена следующая стратегия: 1.Изначально выделяется некоторый начальный объем памяти X. 2.Если при добавлении очередного элемента текущего объема памяти не достаточно, то размер увеличивается в два раза: X = X*2. 3.Если при удалении очередного элемента количество использованной памяти X/4, то размер памяти сокращается в два раза: X = X/2.

Динамически-расширяемый массив 6 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Включение элементов в массив требует log 2 N вызовов функции realloc для увеличения размера памяти. При исключении элементов изменение размера происходит только если объем фактически занимаемой памяти в 4 раза меньше размера выделенной памяти.

Описание и инициализация динамически-расширяемого массива 7 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» struct darray { *ptr; // указатель на начало // динамической области unsigned int size; // размер области unsigned int used; // использовано элементов }; #define INIT_SIZE 16 int dinit(striuct darray *da) { da->size = INIT_SIZE; // начальный размер массива // Выделение памяти для хранения массива da->ptr = malloc(INIT_SIZE * sizeof( )); if( da->ptr == NULL ) return -1; da->used = 0; return 0; }

Изменение размера динамически-расширяемого массива 8 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» int dexpand(struct darray *ptr, int cnt) { if( da->used + cnt size){ // Памяти достаточно da->used += cnt; }else{ int k; for(k=1; da->used + cnt > k*da->size; k=k*2); // k – количество раз, в которое необходимо увеличить // размер массива. da->ptr = realloc(da->ptr,k*da->size*sizeof( )); if( da->ptr == NULL ) return -1; da->size *= k; } return 0; }

Получение размера, доступ к элементам и освобождение динамически-расширяемого массива 9 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» *dptr(struct darray *da) { return da->ptr; } int *dcount(struct darray *da) { return da->used; } void dfree(struct darray *da) { free(da->ptr); da->size = da->used = 0; }

Пример работы с динамически-расширяемым массивом 10 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» int main() { struct darray da; int i; dinit(&da); for(i=0;i

Недостатки динамически- расширяемых массивов 11 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 1.Необходимость вызова realloc, который характеризуется значительными накладными расходами (может приводить к копированию всей последовательности). 2.Вставка или удаление элементов массива требует перемещения существующих элементов. Это может приводить к перемещению больших объемов данных. Например, сдвига большей части элементов последовательности вправо при удалении.

Подходы к размещению элементов последовательности в памяти 12 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Произвольное размещение элементов в памяти позволяет: 1. Избавиться от необходимости перемещения элементов при их вставке/удалении в последовательность. 2. Позволяет выделять только необходимый объем памяти для хранения последовательности. 3. Обеспечивает выделение/освобождение небольших объемов динамической памяти (под каждый элемент в отдельности).

Технические особенности реализации последовательностей с произвольным размещением элементов 13 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 1. Необходим механизм обеспечения связи между элементами. В языке СИ для этого подходят указатели. Обеспечение связности является задачей программиста. 2. В отличие от массивов для доступа к произвольному элементу требуется произвести доступ к элементам расположенным перед ним в последовательности.

Описание и инициализация списка 14 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» struct list { val; // Информационное поле struct list *next; // Указатель на след. элемент } struct list *linit() { struct list *head = malloc(sizeof(struct list)); if( head == NULL ) return head; head->next = NULL; return head; } 0 0 head

Включение элемента в начало списка 15 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» int linsfirst(struct list *head, int elem) { struct list *tmp; tmp->next = malloc( sizeof(struct list)); if( tmp->next == NULL ) return -1; tmp->next = head->next; tmp->val = elem; head->next = tmp; return 0; } 0 head 10??? 2

Включение элемента в конец списка 16 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» int linslast(struct list *head, int elem) { struct list *tmp = head; for( ; tmp->next != NULL; tmp = tmp->next); tmp->next = malloc( sizeof(struct list)); if( tmp->next == NULL ) return -1; tmp = tmp->next; tmp->next = NULL; tmp->val = elem; return 0; } 0 head 10????120

1 Доступ к элементам списка 17 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» struct list *lfirst(struct list *head) { return head->next; } struct list *lnext(struct list *elem) { if( elem != NULL ) return elem->next; else return NULL; } 0 head 20 lfirstlnext

Пример работы со списками 18 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» int main() { struct list *head, *elem; int i; head = list_init(); if( head == NULL ){ return 0; } for(i=0;ival); } list_free(&da); return 0; }

Сериализация списков 19 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Бинарный файл

Восстановление списков из бинарных файлов 20 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» Бинарный файл head

Литература 21 © Кафедра вычислительных систем ГОУ ВПО «СибГУТИ» 1.Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ, М.:МЦНМО, 2002, 960 с. 2.Кнут, Д.Э. Искусство программирования. Том 1. Основные алгоритмы. – Вильямс, – (Серия: Искусство программирования). – ISBN