[cdev] Задача_6. гр 135

[Grigoriy A. Sitkarev]

Лёш, посмотри как должны эти функции работать. Я вложил файл, чтобы не 
включать код в тело письма.

Тебе нужно добавить проверку во все public функции, как мы 
договаривались, и немного переделать prioq_add потому что у меня там ф-я 
prioq_resize() а у тебя её скорее всего нет.

Расскажи что у тебя не получилось с macros.h, я не могу понять. Ты его 
включил в файл? Он локально должен включаться, ты его положи в тот же 
каталог где и исходные файлы и впиши после всех заголовков:

#include "macros.h"

Там поправлена ошибка в prioq_heapify() а также переделан 
prioq_remove(). В prioq_heapify() теперь проверяется случай перед 
поиском наибольшего из потомков, не выходим ли мы за границу массива 
кучи при попытке обратиться к правому потомку. В prioq_remove() алгоритм 
приведён в порядок, сначала мы должны самый последний элемент, 
помещённый на место удалённого, двигать наверх, пока его родитель не 
станет больше или не будет достигнут корень кучи, потом мы его двигаем 
вниз, пока его потомки не станут меньше чем он сам. Таким образом 
поддерживается нужные свойства бинарной кучи в том числе и после изъятия 
любого элемента из неё. В этой функции идёт проверка на краевой случай, 
когда изъят последний элемент, тогда ничего двигать не надо.

Надо это всё ещё раз проверить, но важнее чтобы ты понял как это всё 
программируется и потом работает. Попробуй также написать пример с 
использованием концепции в container.c, через макрос CONTAINER_OF(), 
поищи в архиве рассылки, там было всё расписано. В любую структуру можно 
включить struct prioq_head и потом работать с ней как с элементом очереди.

--
Г.А.

Алексей Петрунёв пишет:
> В prioq_put  исправил строчку "i = queue->used++" на "i =
> queue->used". Ошибку с memset тоже исправил и prioq_get
> убрал(закоментил) queue->heap[used] = NULL. Хотя queue->heap[used] не
> должен участвовать в сортировке и нам уже он  не нужен, поэтому можем
> присвоить ему NULL. Неожиданно возник вопрос: В функции prioq_heapify
> условие "largest == queue->used" когда-нибудь выполняется? queue->used
> всегда больше последнего индекса в массиве, т.к. он с нуля начинается.


----------- следущая часть -----------
A non-text attachment was scrubbed...
Name: prioq.c
Type: text/x-csrc
Size: 1709 bytes
Desc: отсутствует
URL: <http://amplab.syktsu.ru/pipermail/cdev/attachments/20100926/e876482a/attachment.c>