05-structures2 (1238879)

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

Текст из файла

СТРУКТУРЫ ДАННЫХСписки. Понятие абстрактной структуры данных. Хеш-таблицы ипоисковые деревьяК. Владимиров, Intel, 2019mail-to: konstantin.vladimirov@gmail.comИдея односвязного списка•Идея односвязного списка довольно проста: каждый узел содержитуказатель на следующийstruct node_t {struct node_t *next;int contents;};•Узлы такого рода динамических структур данных обычно выделяются в кучеstruct node_t *top = calloc(1, sizeof(struct node_t));top->next = calloc(1, sizeof(struct node_t));•Это бывает удобно изобразить картинкойИдея односвязного списка•Идея односвязного списка довольно проста: каждый узел содержитуказатель на следующийstruct node_t {struct node_t *next; int contents; };•Картинку можно несколько конкретизировать, учтя значения полей,выставленные на предыдущем слайдеИдея односвязного списка•Идея односвязного списка довольно проста: каждый узел содержитуказатель на следующийstruct node_t {struct node_t *next; int contents; };•Динамические структуры данных крайне полезны•По традиции мы начнём их изучение со списков (хотя они как раз сами посебе не слишком полезны, зато очень просты)Problem AL: работа со списками•Ваша задача: написать две функции•Построить односвязный список из файлового ввода, такой, что все чётныечисла идут в начале, а все нечётные в концеstruct node_t *read_list(FILE *inp);•Файл представляет собой просто целые числа разделённые через пробел1 65 78 2 34•Удалить односвязный список, получив указатель на первый элементvoid delete_list(struct node_t *top);Снова динамическое программирование•Любая часть оптимальной траектории является оптимальной траекторией•Пусть дана сумма 11.

Как оптимально разменять её номиналами 4, 3 и 1?12345678910111211222233? − 1 + 1• Здесь = ൞ − 2 + 1 − 3 + 1•В общем случае нужно разменять сумму номиналами 1 , 2 , … , •Последовательное заполнение таблицы требует ∗ времениОбсуждение•Мы хотели бы разменять сумму номиналами 1 , 2 , … , •Сколько для этого нам потребуется памяти?Обсуждение•Мы хотели бы разменять сумму номиналами 1 , 2 , … , •Сколько для этого нам потребуется памяти?•Неправильный ответ: •Правильный ответ: •Основная идея: циклический список78910112233?Обсуждение•Мы хотели бы разменять сумму номиналами 1 , 2 , … , •Сколько для этого нам потребуется памяти?•Неправильный ответ: •Правильный ответ: •Основная идея: циклический список891011122333?Интерфейс циклического списка•Основная структура ничем не отличается от обычного односвязного спискаstruct list_t {struct list_t *next;int data;};•Основные операции (файл cl-impl)// добавить элемент после указанногоstruct list_t *cl_push(struct list_t *pre, int d);// удалить элемент после указанногоstruct list_t *cl_pop(struct list_t *pre);Problem CL – циклический размен•Входной файл содержит сумму для размена, количество номиналов и всеноминалы размена•Ваша задача считав его со стандартного ввода вывести на стандартный выводправильное количество использованных монет•Пример.

Входные данные:11 3 1 3 4•Выход:3•Сумма для размена может быть очень большой, используйте циклический буферОбсуждение•Тот факт, что циклический список мало чем отличается от обычного должен, впринципе, вас насторожитьОбсуждение•Тот факт, что циклический список мало чем отличается от обычного должен, впринципе, вас насторожитьЗадача: есть ли петля?•Вам на вход приходит связный списокstruct list_t {struct list_t *next;int data;};int somefunc(struct list_t *top);•Возможно в нём есть петля. Возможно он кончается на нулевой указатель. Какэто определить?Алгоритм Флойда•Начинают два указателя: заяц и черепаха•Заяц за каждый ход продвигается вперёд на дваэлемента, а черепаха на один•Если они встретились, значит петля естьАлгоритм Брента•Начинают два указателя: заяц и черепаха•Заяц за каждый ход продвигается вперёд наединицу и несёт с собой телепорт•Как только он прошёл очередную степень двойки,он телепортирует туда черепаху•Если они встретились, значит петля естьProblem HL – петля в связном списке•Вам на вход приходит какой-то список, заданный всё той же структуройstruct list_t {struct list_t *next;int data;};•Вы должны написать функцию, которая определяет есть ли в нём петляint list_is_a_loop(struct list_t *top) {// TODO: ваш код здесь}•Вернуть 0 (нет) или 1 (есть).

Используйте любой из двух описанных методовProblem HL2 – длина петли•Вам на вход приходит какой-то список, заданный всё той же структуройstruct list_t {struct list_t *next;int data;};•Вы должны написать функцию, которая определяет длину петли если онаесть и возвращает 0, если её нетint loop_len(struct list_t *top);•Попробуйте адаптировать один из ранее приведённых алгоритмов для этого•Разумное решение не будет использовать много дополнительной памятиProblem RG: период генератора•Вам дан генератор +1 = , при этом вы не знаете функцию •Генерируемые числа выглядят случайными.

Вам нужно написать функцию,которая ищет длину цикла в генераторе, начиная с 0 = 0typedef int (*generator_t)(int);unsigned cycle_len(generator_t gen) {// TODO: ваш код здесь}•Например при = + 2 % 5, 0 = 0 генерируется последовательность0, 2, 4, 1, 3, 0, 2, ... и длина цикла равна 5•Заметьте, вовсе не факт, что 0 встретится ещё раз (генератор может бытьсмещённым). Но для любого j > i, = означает циклОбсуждение•Представьте, что у вас стоит задача развернуть односвязный список, несодержащий петли•Как вы представляете себе её решение?Алгоритм RFL – рекурсивный разворот•Основная идея в том, что reverse(x:xs) = reverse(xs):xstruct list_t * reverse(struct list_t *top) {struct list_t *xs;if (NULL == top) return NULL;if (NULL == top->next) return top;xs = reverse(top->next);top->next->next = top; // единственное тонкое местоtop->next = NULL;return xs;}•Алгоритм сравнительно прост и красив. Увы достаточно длинный списокпереполнит стекProblem LR – развернуть итеративно•Это ещё одна обычная проблема вида рекурсия-в-итерацию•Ваша задача написать функцию разворота односвязного списка, котораябудет работать за (1) по памятиstruct list_t *reverse(struct list_t *top);•Заметьте, что алгоритм RFL тратит () памяти на стек вызововОбсуждение•Что если в вашем входном односвязном списке всё же появится петля?•Попробуйте прогнать вашу процедуру переворота на зацикленном списке ипосмотрите результат•Интересный вопрос: что же делать?Обсуждение•Что если в вашем входном односвязном списке всё же появится петля?•Попробуйте прогнать вашу процедуру переворота на зацикленном списке ипосмотрите результат•Интересный вопрос: что же делать?•Плохой вариант: при каждом вызове переворота искать петлю.

Этопрактически удваивает время на переворот•Хороший вариант несколько менее очевиден. И он называется инкапсуляцияСписок как структура данных•Представьте, что список вынесен в модуль как в encap-sll.h / encap-sll.c•Внешний интерфейс выглядит примерно такstruct list_t; // объявление списка, детали спрятаныstruct list_t *list_create(int d);struct list_t *list_push(struct list_t * pre, int d);struct list_t *list_pop(struct list_t * pre);•Такой список в принципе не может случайно зациклиться, так как вся работа сним осуществляется только функциями его открытого интерфейса•И каждая из этих функций поддерживает инварианты своего типа данныхСтруктуры данных•Список не единственная структура данных. Самые известные это:•••••Динамические массивыЛинейные и циклические спискиХеш-таблицыПоисковые деревьяОбсуждение: чем отличаются друг от друга структуры данных?Структуры данных•Список не единственная структура данных.

Самые известные это:••••Динамические массивыЛинейные и циклические спискиХеш-таблицыПоисковые деревья•Обсуждение: чем отличаются друг от друга структуры данных?•Неправильный ответ: реализацией. Реализация у них спрятана и считается неслишком важной. Операции с каждым типом происходят только через егоинтерфейс•Правильный ответ: алгоритмической сложностью функций открытогоинтерфейсаПример: телефонная книга••У вас есть список друзей и список их номеров в международном формате (до 15цифр)44-7911-975-72-83Bob44-7911-486-92-83Camilla8-800-555-31-35Daniel8-800-765-91-35Вам нужно выбрать структуру данных, которая позволяла бы:•••AliceБыстро добавить человека и его номерНайти имя человека по номеру телефонаПросто хранить массив строк, индексированный номерами телефонов затратноОбсуждение•Можно выбрать сортированный по номеру массив•••Преимущества: быстрый поиск ()Недостатки: медленная вставка ()Можно выбрать список••Преимущества: быстрая вставка (1)Недостатки: медленный поиск ()•Конечно лучше всего было бы сделать прямую адресацию по номерамтелефонов, тогда и поиск и вставка были бы (1)•Можем ли мы отобразить все номера телефонов на разумный диапазон,скажем 0 ÷ 999?Хеширование•Самый простой способ это взять три последние цифры номера•Запишем это как функцию ℎ = % (где это мощность отображения, вданном случае = 1000).

Мощность определяет количество бакетов•Тогда имеем массив из 1000 списков...135Daniel (88007659135)Camilla(88005553135)Alice(4479119757283)Bob (4479114869283)...283...•Уже сейчас видно, что если повезёт и коллизий не будет, то поиск (1) ивставка (1). Увы сейчас хеш-функция ℎ довольно плохаУниверсальные семейства функций•Случайно выбранная функция из такого семейства гарантированно будет всреднем не хуже, чем любая другая для этого класса•Везде далее это мощность хеша, это простое число, большее •Для целых чисел это семействоℎ, = + % % , при этом ≠ 0Для строк это семействоℎ с1 … с = ℎ•σ=1 с − % где ℎ это произвольно выбранная ℎ,Иногда параметры действительно выбирают случайно и меняют с каждымзапуском программыРеализация хеш-функций•Если что-то считается миллионы раз за выполнение программы, его реализациилучше быть как можно более оптимальной•Пусть это количество бит в машинном слове (обычно 16 или 32) и мощность = 2 , < •Тогда неплохая хеш-функция для целых реализуется какunsigned hashint(unsigned a, unsigned b, unsigned x) {return (a*x + b) >> (w – M);}•Заметьте, здесь (a*x + b) уже вычисляется по модулю 232 без явного деления•Аналогично выкручиваются со строками (см.

)Problem XC: подсчёт коллизий•Ваша задача: имея произвольную функцию хеширования строки ипроизвольную последовательность строк, подсчитать количество коллизийtypedef int (*get_hash_t)(const char *s);int ncollisions(char **strs, get_hash_t f) {// TODO: your code here}•Эта функция впоследствии может быть использована для оценки качествахеш-функций над строкамиХеш-таблица как структура данных•Как структура данных, хеш-таблица тоже инкапсулируется в отдельном модуле•Интерфейс может выглядеть как:struct hashmap_t; // объявление таблицы, детали спрятаныstruct hashmap_t *hashmap_create(unsigned m);int hashmap_add(struct hashmap_t *h, unsigned key,const char *value);const char *hashmap_find(struct hashmap_t *h, unsigned key);void hashmap_destroy(struct hashmap_t *h);•Разумеется реальный интерфейс может быть гораздо богаче и интереснееДомашняя работа HWH – словарь•На стандартном вводе название текстового файла, лежащего по рабочемупути программы и список слов•На стандартном выводе список частот встретившихся слов•Например пусть text.txt содержит стишок отсюда:https://en.wikipedia.org/wiki/This_Is_the_House_That_Jack_Built> echo "text.txt farmer horse Jack" > test.stdin> ./a.out < test.stdin1 2 12•Поскольку слово farmer встретилось 1 раз и так далее•Постарайтесь использовать хеш-таблицы для упрощения подсчётаСнова о поиске подстроки в строке•Можем ли мы использовать хеширование для эффективного поискаподстроки?ABABACABACABAABACABCACBCA•Вычислим хеш ℎ = ℎ •Здесь функция ℎ это упрощённая универсальная функция для строкℎ с1 … с = σ=1 с − % •Первые шесть символов строки в которой мы ищем дают ℎ •Можем ли мы легко перейти от него к ℎ ?AAЦиклические свойства хеш-функции•Ещё раз посмотрим на формулу ℎ с1 … с = σ=1 с − % •ℎ с2 … с+1 =•Интуитивно: мы убираем первый символ, сдвигаем строку умножением идобавляем последний•Можно предварительно подсчитать = −1 % •Сигнатура для функции обновленияℎ с1 … с − с1 −1 ∗ + с+1 % unsigned update_hash(unsigned hash, unsigned n, char cf, char cl);•Напишите эту функциюОбсуждение•AЦиклические свойства хеш-функций наталкивают на идёю «циклическогохеша», который обновляется с каждым новым продвижением подстрокиBABACAABACABABACABCACBC•Вместо () имеем () потому что обновление хеша происходит законстантное время•Это называется алгоритмом Рабина-КарпаAAAАлгоритм RK – поиск подстроки•Проверяет наличие подстроки needle в строке haystack// assume strlen(needle) much lesser then strlen(haystack)int rabin_karp(const char *needle, const char *haystack) {unsigned n, target, cur, count = 0, left = 0, right = strlen(needle);target = get_hash(needle, needle + right);cur = get_hash(haystack, haystack + right);n = pow_mod(R, right - 1, Q); // алгоритм POWMwhile(target != cur && haystack[right] != 0) {cur = update_hash(cur, n, haystack[left], haystack[right]);left += 1; right += 1;}return (target == cur) ? left : 0;}Problem KС: коллизии Рабина-Карпа•В алгоритме RK никак не обработан случай коллизии хеш-функции, когдахеши совпали, а строка найдена неверно•Ваша задача доработать с учётом коллизий функциюint rabin_karp(const char *needle, const char *haystack);•Выберите в качестве хеш-функции нечто не слишком совершенное, напримерℎ с1 … с = ෍ с 10−=1•Проверьте как работает поиск с коллизиями% 31Обсуждение: алгоритм Рабина-Карпа•Несколько проигрывает КМП для поиска точного совпадения•Зависит от выбора хеш-функции•Но находит своё применение если нужно не слишком точное совпадение•Как бы вы модифицировали алгоритм RK чтобы он искал подстроку без учётарегистра и при этом игнорировал запятые?Обсуждение•Главный недостаток хеш-таблиц (и шире хеш-функций как идеи) это стираниеинформации о естественном порядке объектов•Например если нужно индексировать города расстоянием от Москвы, тосложить их в хеш-таблицу по этому расстоянию легко.

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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