03-pointers2 (1238873), страница 2

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

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

Мы уже пользовались им раньшеdouble d = 49.0;int i = (int) d; // теперь i == 49char c = (char) i; // теперь c == '1'•Точно так же можно приводить указателиchar *pc = (char *) &i; // теперь pc указывает на первый байт i•Будьте осторожны с приведением указателей. Правила строгого алиасинга (strictaliasing rules) требуют чтобы в программе одновременно не существовалоуказателей двух разных типов на одну и ту же локацию в памяти•Из этих правил есть два исключения.

Тип char* и тип void*Концепция void и void pointer•Ключевое слово void в языке C используется сразу для нескольких вещей•Отсутствия аргументов или результата у функцииvoid bar(void);•Указателя на неопределённую памятьvoid *pv = (void *) &i;•Такой указатель не может быть разыменован, с ним также не работаетадресная арифметика•Всё что с ним можно сделать осмысленного это привести к типизированномууказателю или передать в функциюОбсуждение•Сортировать целые числа это весело и интересно, но что делать, если хочетсясортировать произвольные объекты?•Для этого можно использовать void* и размер объекта в памяти•Для того, чтобы сравнивать такие объекты, можно передавать указатель нафункцию-компараторtypedef int (*cmp_t)(void const * lhs, void const * rhs);•Свою функцию компаратор можно написать для своих типов и передать вобобщённую функцию сортировкиКомпаратор для целых чисел•Обобщённый компараторint int_less(void const * lhs, void const * rhs) {int const * lhsi = (int const *) lhs;int const * rhsi = (int const *) rhs;return (*lhsi < *rhsi);}•Он работает так, что int_less(&a, &b) возвращает то же самое, что исравнение (a < b)int a = 2, b = 3;assert(int_less(&a, &b) == 1);Алгоритм CB – общий бинарный поискtypedef int (*cmp_t)(void const * lhs, void const * rhs);void *cbsearch(void const * key, void const * base, int num, int size, cmp_t cmp) {char const * pivot;int result;while (num > 0) {pivot = (char const *) base + (num / 2) * size;result = cmp(key, (void const *) pivot);if (result == 0)return (void *) pivot;// TODO: допишите здесь обобщённый бинарный поиск}return NULL;}Problem CSE – обобщение alg SE•Для одного шага сортировки выбором теперь понадобится чуть большепараметровtypedef int (*cmp_t)(void const * key, void const * elt);// eltsize – размер элемента// numelts – количество элементов// nsorted – позиция последнего отсортированногоint selstep(void const * arr, int eltsize, int numelts,int nsorted, cmp_t cmp) {// напишите тут код}•Ваша задача реализовать этот шаг.

Обратите особое внимание на swapProblem CM – обобщение слияния•Можно даже замахнуться на сортировку объектов разных размеров•Предположим, что у вас есть реализованный кем-то компаратор типа xcmp_t// сравнивает два объекта разных длинtypedef int (*xcmp_t)(void const * lhs, int lsz,void const * rhs, int rsz);•Ваша задача реализовать любую эффективную сортировку (проще всегослияние) с набором последовательных в памяти элементов разного размера// nelts количество элементов и их размеров, mem общая памятьvoid xmsort(void * mem, int * sizes, int nelts, xcmp_t cmp);•Вы можете попробовать разные алгоритмы сортировки, например быструю,но это может быть неожиданно сложноДомашнее задание HWS – Timsort•Многие современные алгоритмы для лучшей производительностикомбинируют слияние и вставки•Прочитайте статью https://en.wikipedia.org/wiki/Timsort•Реализуйте обобщённый (для произвольных типов) описанный там алгоритм,используя применённый на этом семинаре подход с void*Многомерные массивы•Два принципиально разных типа двумерных массивов:•Непрерывный двумерный массивint twodim[10][10] = {{0, 1}, {2, 3}};twodim[2][3] = 100; // *(&twodim[0][0] + 2*10 + 3) = 100;•Массив указателейint *twodim[3] = { malloc(40), malloc(40), malloc(40) };twodim[2][3] = 100; // *(*(twodim[0] + 2) + 3) = 100;•Ситуацию усложняет то, что обращения к arr[x][y] выглядят в кодеодинаковоУказатели на массивы•Подобно указателям на функции, существуют указатели на массивыint *arrptrs[10]; // array of 10 pointers to intint (*ptrarr)[10]; // pointer to array of 10 ints•Основная разница проявляется при инкрементеint arr[10][10] = {{0, 1}, {2, 3}};arrptrs[0] = &arr[0][0]; arrptrs[0] += 1; // +4ptrarr = &arr[0]; ptrarr += 1; // +40•Указатель на массив имеет применение когда мы хотим передатьнепрерывный массив в функциюProblem PX – матрицы в степень•Используйте идею из алгоритма POWM (cм.

также ℎ 4.6.3 )•Напишите функцию для возведения в любую степень матриц NxN заданных какуказатели на массивыvoid//////}•powNxN (unsigned (*n)[N], unsigned x) {TODO: ваш код здесьвы можете предполагать NxN матрицунеобходимо модифицировать n, возведя её в степень xОцените асимптотическую сложность этого алгоритмаЧтение сложных типов в языке C•Основные конструкции: массив указатель и функцияchar * const * (* next)(int * const);•Читается так: начинаем от имени переменной "next это"•Читаем "указатель" и выходим из скобок•Читаем "на функцию, принимающую неизменяемый указатель на int"•Читаем "и возвращающую указатель на неизменяемый указатель на char"•Соединяем: next это указатель на функцию, принимающую неизменяемыйуказатель на int и возвращающую указатель на неизменяемый указатель наchar•Подробнее см.

[]Немного тренировки•Прочитайте следующие определенияchar *(*carr[10])(int **);void (*signal(int, void (*)(int)) ) (int);unsigned (*search)(const (int *)[2], unsigned[][4]);•Разумеется умение читать такие объявления не означает что ими надозлоупотреблятьВаш друг typedef•Вместоvoid (*signal(int, void (*)(int)) ) (int);•Удобно записатьtypedef void (*ptr_to_func) (int);ptr_to_func signal(int, ptr_to_func);•Это делает тип читаемым и очевидным•Теперь запутанные правила typedef получают объяснение: они устроены так,чтобы typedef для типа точно соответствовал c-decl для его использованияЛитература•С11 ISO/IEC, "Information technology – Programminglanguages – C", ISO/IEC 9899:2011•& Brian W.

Kernighan, Dennis Ritchie – The Cprogramming language, 1988• Peter van der Linden – Expert C Programming:Deep C Secrets , 1994• Thomas H. Cormen – Introduction toAlgorithms, 2009• Donald E. Knuth – The Art of ComputerProgramming, 2011.

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

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