[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