Слайды лекций - 2014 (лектор - Белеванцев А. А.) (1107979), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Динамическое выделение памяти для строки:#include <stdio.h>#include <stdlib.h>#include <string.h>int main (void) {char *s;int t;s = (сhar *) malloc (80 * sizeof (char));if (!s) {fprintf (stderr, "требуемая память не выделена.\n");return 1; /* исключительная ситуация */}fgets (s, 80, stdin); s[strlen (s) – 1] = '\0';/* посимвольный вывод перевернутой строки на экран */for (t = strlen(s) - 1; t >= 0; t--)putchar (s[t]);free (s);return 0;}4Динамическое распределение памятиПример. Динамическое выделение памяти для двухмерногоцелочисленного массива (матрицы):#include#includelong pwrlong tfor (;return}<stdio.h><stdlib.h>(int a, int b) {= 1;b; b--) t *= a;t;int main (void) {long *p[6];int i, j;for (i = 0; i < 6; i++)if (!(p[i] = malloc (4 * sizeof (long)))) {printf ("требуемая память не выделена. \n");exit(1);}for (i = 1; i < 7; i++)for (j = 1; j < 5; j++)p[i – 1][j – 1] = pwr (i, j);for (i = 1; i < 7; i++) {for (j = 1; j < 5; j++)printf ("%10ld ", p[i – 1][j – 1]);printf ("\n");}/* Цикл с освобождением памяти */return 0;}5Динамическое распределение памятиПример.

Динамическое выделение памяти для двухмерногоцелочисленного массива (матрицы):#include <stdio.h>#include <stdlib.h>long pwrlong tfor (;t *=return}(int a, int b) {= 1;b; b--)a;t;int main (void) {long *p[6];int i, j;for (i = 0; i < 6; i++)if (!(p[i] = malloc (4 * sizeof (long)))) {printf ("требуемая память не выделена. \n");exit(1);}6Динамическое распределение памятиПример.

Динамическое выделение памяти для двухмерногоцелочисленного массива (матрицы):for (i = 1; i < 7; i++)for (j = 1; j < 5; j++)p[i – 1][j – 1] = pwr (i, j);for (i = 1; i < 7; i++) {for (j = 1; j < 5; j++)printf ("%10ld ", p[i – 1][j – 1]);printf ("\n");}for (i = 0; i < 6; i++)free (p[i]);return 0;}7VLA-массивыВ Си-89 размер массива обязан являться константой. Этонеудобно при передаче массивов (многомерных) в функции:/* можно передать int a[5]; int a[42]; ...

*/int asum1d (int a[], int n) {int s = 0;for (int i = 0; i < n; i++)s += a[i];return s;}/* можно передать только int a[???][5] */int asum2d (int a[][5], int n) {int s = 0;for (int i = 0; i < n; i++)for (int j = 0; j < 5; j++)s += a[i][j];return s;}8VLA-массивыВ Си-99 размер массива автоматического класса памятиможет задаваться во время выполнения программы:int foo (int n) {int a[n];<... Можно обрабатывать a[i]...>}/* можно передать int a[???][???] */int asum2d (int m, int n, int a[m][n]) {int s = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)s += a[i][j];return s;}Объявление функции asum2d:int asum2d (int m, int n, int a[m][n]);int asum2d (int, int, int [*][*]);9VLA-массивы и динамическое выделение памятиФункция asum2d может использоваться с VLA-массивами,но они всегда выделяются в автоматической памяти:int foo (int m, int n) {int a[m][n]; int s;<... Считаем a[i][j]...>s = asum2d (m, n, a);}Можно выделить VLA-массив в динамической памяти:int main (void) {int m, n;scanf ("%d%d", &m, &n);int (*pa)[n];pa = (int (*)[n]) malloc (m * n * sizeof (int));<...

Считаем pa[i][j]...>s = asum2d (m, n, pa);free (pa);10}Динамическое распределение памятиСостав функций динамического распределения памятибиблиотеки stdlib (заголовочный файл <stdlib.h>)voidvoidvoidvoid*malloc (size_t size);free (void *p);*realloc (void *p, size_t size);*calloc(size_t num, size_t size);Функцияvoid *realloc (void *p, size_t size)согласно стандарту Си99 сначала выполняет free (p),а потом p = malloc (size), возвращая новое значениеуказателя p.

При этом значения первых size байтов новой истарой областей совпадают.Функцияvoid *calloc (size_t num, size_t size)работает аналогично функции malloc (size1),где size1 = num * size (т.е. выделяет память для размещениямассива из num объектов размера size).Выделенная память инициализируется нулевыми значениями11Массив переменного размера в структуре (C99)Flexible array member – последнее поле структуры:struct polygon {int np; /* число вершин */struct point points[];}Варьирование размера переменного массива:int np; struct polygon *pp;scanf ("%d", &np);pp = malloc (sizeof (struct polygon)+ np * sizeof (struct point));pp->np = np;for (int i = 0; i < np; i++)scanf ("%d%d", &pp->points[i].x,12&pp->points[i].y);Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекция 131Схема компиляцииИсходная программаfile1.cfile3.cfile2.c1Препроцессор1Препроцессор1Препроцессор2Компилятор2Компилятор2Компиляторfile1.s3Ассемблерfile3.sfile2.s3file1.oАссемблерfile2.o43Ассемблерfile3.oКомпоновщикИсполняемый файл2ПрепроцессорПеред компиляцией выполняется этап препроцессирования.Это обработка программного модуля для получения егоокончательного текста, который отдается компилятору.Управление препроцессированием выполняется с помощьюдиректив препроцессора:#include <...> - системные библиотеки#include "..." – пользовательские файлы#define name(parameters) text#undef name#define MAX 128#define ABS(x) ((x) >= 0 ? (x) : -(x))x -> y – 7ABS(x) -> ((y – 7) >= 0 ? (y – 7) : -(y – 7))x -> a-- ?3Препроцессор и условная компиляцияПрепроцессор позволяет организовать условное включениефрагментов кода в программу#ifdef name / #endif – проверка определения имени#ifndef _STDIO_H#define _STDIO_H<...

текст файла ...>#endif4Препроцессор и условная компиляцияПрепроцессор позволяет организовать условное включениефрагментов кода в программу#if/#if defined/#elif/#else/#endif – общие проверкиусловий#if HOST_BITS_PER_INT >= 32typedef unsigned int gfc_char_t;#elif HOST_BITS_PER_LONG >= 32typedef unsigned long gfc_char_t;#elif defined(HAVE_LONG_LONG)&& (HOST_BITS_PER_LONGLONG >= 32)typedef unsigned long long gfc_char_t;#else#error "Cannot find an integer type with at least 32 bits"#endif5Препроцессор: операции # и ##Операция # позволяет получить строковое представлениеаргумента#define FAIL(op)do {fprintf (stderr, "Operation " #op "failed: ""at file %s, line %d\n", __FILE__,__LINE__);abort ();} while (0)\\\\\\int foo (int x, int y) {if (y == 0)FAIL (division);return x / y;}do { fprintf (stderr, "Operation " "division" "failed: " "at file%s, line %d\n", "fail.c", 13); abort (); } while (0);6Препроцессор: операции # и ##Операция ## позволяет объединить фактические аргументымакроса в одну строкуjava-opcodes.h:enum java_opcode {#define JAVAOP(NAME, CODE, KIND, TYPE, VALUE) \OPCODE_##NAME = CODE,#include "javaop.def"#undef JAVAOPLAST_AND_UNUSED_JAVA_OPCODE};javaop.def:JAVAOP (nop,0, STACK,POP,0)JAVAOP (aconst_null,1, PUSHC,PTR,0)JAVAOP (iconst_m1,2, PUSHC,INT,-1)<...>JAVAOP (ret_w,209, RET,RETURN, VAR_INDEX_2)JAVAOP (impdep1,254, IMPL,ANY,1)JAVAOP (impdep2,255, IMPL,ANY,2)7Препроцессор: операции # и ##Операция ## позволяет объединить фактические аргументымакроса в одну строкуgcc –E java-opcodes.h:enum java_opcode {OPCODE_nop = 0,OPCODE_aconst_null = 1,OPCODE_iconst_m1 = 2,OPCODE_iconst_0 = 3,<...>OPCODE_impdep2 = 255,LAST_AND_UNUSED_JAVA_OPCODE};8Компоновка и классы памятиКласс памяти Время жизниВидимость Компоновка ОпределенаaвтоматическийавтоматическоеблокнетВ блокерегистровыйавтоматическоеблокнетВ блоке какregisterстатическийстатическоефайлвнешняяВне функцийстатическийстатическоефайлвнутренняяВне функцийкак staticстатическийстатическоеблокнетВ блоке как staticКвалификатор extern: переменная определена и память под неевыделена в другом файлеКлассы памяти функций:статическая (объявлена с квалифатором static)внешняя (extern), по умолчаниювстраиваемая (inline, C99)Объявление внешних функций в заголовочных файлах:extern void *realloc (void *ptr, size_t size);9КомпоновщикОрганизовывает слияние нескольких объектныхфайлов в одну программуРазрешает неизвестные символы (внешниепеременные и функции)Глобальные переменные с одним именемполучают одну область памятиОшибки, если необходимых имен нетили есть несколько объектов с одним именемОпции для указания места поискаХорошим стилем программирования являетсяэкспорт лишь тех объектов, которые используютсяв других файлах (интерфейс модуля)Используйте квалификатор staticСборка исполняемого файла или библиотеки10(статической или динамической)Отладка программВсе программы содержат ошибки, отладка – это процесс поискаи удаления некоторых ошибокСуществуют другие методы обнаружения ошибок (тестирование,верификация, статические и динамические анализаторы кода),но их применение не гарантирует отсутствия ошибокДля отладки используют инструменты, позволяющие получитьинформацию о поведении программы на некоторых входныхданных, не изменяя ее поведенияПростейший метод: отладочная печатьstatic void debug_array (int *a, int n) {int *a; int n;fprintf (stderr, "Array (%d)", n);n = read_array (a);for (int i = 0; i < n; i++)debug_array (a, n);fprintf (stderr, "%d ", a[i]);fprintf (stderr, "\n");}Отладочная печать может контролироваться макросом (NDEBUG)11Отладка программ: отладчикиОтладчик – основной инструмент отладки программыОтладчик позволяетзапустить программу для заданных входных данныхостанавливать выполнение по достижении заданныхточек программы безусловно или при выполнениинекоторого условия на значения переменныхостанавливать выполнение, когда некоторая переменнаяизменяет свое значениевыполнить текущую строку исходного кода программыи снова остановить выполнениепосмотреть/изменить значения переменных, памятипосмотреть текущий стек вызововНеобходимое условие для отладки на уровне исходного кода:наличие в исполняемом файле программы отладочнойинформации (связи между командами процессора и строкамиисходного кода программы, связь между адресами и12переменными и т.д.)Отладка программ: отладчик gdbКомпиляция с отладочной информацией: gcc -gНекоторые команды gdbgdb <file> --args <args> – загрузить программу сзаданными параметрами командной строкиrun/continue – запустить/продолжить выполнениеbreak <function name/file:line number> –завести безусловную точку остановаcond <bp#> condition – задать условие остановкивыполнения для некоторой точки остановаwatch <variable/address> – задать точкунаблюдения (остановка выполнения при изменениизначения переменной или памяти по адресу)next/step – выполнить текущую строку исходного кодапрограммы без захода/с заходом в вызываемые функцииprint <var>/set <var> = expression – посмотреть/изменить текущие значения переменных, памятиbt – посмотреть текущий стек вызововСреда Code::Blocks поддерживает gdb в своем интерфейсе 13Отладка программ: примеры команд gdbУстановка точек остановаможно использовать '.' вместо '->'b fancy_abortb 7199b sel-sched.c:7199cond 2 insn.u.fld.rt_int == 112cond 3 x_rtl->emit.x_cur_insn_uid == 1396Просмотр и изменение значений переменныхp orig_ops.u.expr.history_of_changes.basep bb->indexset sched_verbose=5call debug_vinsn (0x4744540)Установка точек наблюденияwa can_issue_morewa ((basic_block) 0x7ffff58b5680)->preds.base.prefix.num14Курс «Алгоритмы и алгоритмические языки»1 семестр 2014/2015Лекция 141Динамические структуры данных.

Характеристики

Список файлов лекций