[cdev] Задача_6. гр 135
Grigoriy A. Sitkarev
sitkarev на komitex.ru
Вт Сен 28 00:40:30 MSK 2010
Лёша,
Большая просьба, поставь в редакторе TAB в 8 символов и посмотри что у
тебя происходит, всё вкривь и вкось, где-то пляшет, где-то убежало.
Где-то табуляция, где-то пробелы. Поправь пожалуйста, а то читать же
невозможно, честное слово.
Теперь замечания:
1.
В prioq_remove() есть условие:
if (q->used > 0 && idx != q->used)
внутри этого блока выполняется код если:
а) очередь не пуста, после удаления элемента;
б) если удалённый элемент не был последним элементом в куче (индексом).
Потому что если это так, то ничего с кучей делать не надо. У тебя
почему-то часть кода, включая prioq_heapify(), вне этого блока
находится. По смыслу, они должны быть внутри этого блока.
2.
У нас это будет часть библиотеки. Все не-public функции должны получить
модификатор static, чтобы они не засоряли пространство имён при
связывании. Так, например, prioq_heapify() должна стать static void.
3.
Не понятно, почему спустились определения макросов RIGHT_CHILD и
LEFT_CHILD вниз. По смыслу они должны быть в начале файла, чтобы
пользователь видел о чём речь пойдёт дальше, потому что основная
структура, с которой идут манипуляции, это двоичная куча.
4.
В prioq_remove() проверки в return_if_fail() указателя hp идут после
того как он уже был разыменован, выше по коду. Там мы получаем индекс в
hp->index. Надо быть немножко внимательнее, и не забывать что проверки у
нас идут сразу же после определений локальных переменных и конечно же до
попыток разыменования указателей, которые мы проверяем, и т.д.
5.
Пример с использованием CONTAINER_OF() и твой проверочный код, и вообще
всё, что не относится к API очереди, нужно вынести в отдельный файл
исходный. У нас же prioq.c это часть библиотеки должно быть или
отдельный объектный файл, так ведь?
6.
Пример с CONTAINER_OF() не совсем верно использован, хотя и работает.
Работает, потому что в структуре user_data поле prioq_head идёт первым и
указатель на user_data аналогичен указатель на prioq_head. Но смысл
CONTAINER_OF() был в том что мы можем поместить prioq_head в любом месте
объемлющей структуры а затем по указатель на prioq_head получить саму
структуру. Поэтому с примером ещё раз разберись, подумай, если не
получится или что-то не понятно будет, я напишу подробнее.
--
Г.А.
Алексей Петрунёв пишет:
> Я добавил условие в prioq_heapify, чтобы элемент не двигался если он
> больше своих потомков.
Подробная информация о списке рассылки cdev