[cdev] Задача_6. гр 135
Grigoriy A. Sitkarev
sitkarev на komitex.ru
Пн Апр 5 22:25:40 MSK 2010
Лёша, в программе есть ошибки.
Функция prioq_get выглядит более чем странно.
1. Пользователь передаёт нам указатель на queue. Мы решили следовать
хорошему правилу - проверять указатели на NULL, чтобы отлавливать
возможные ошибки пользователя при программировании (забыл что высвободил
аргумент и он теперь NULL например). Нулевой указатель разыменовывать
нельзя, это ошибка и программа завершится аварийно.
Попробуй сделать вот так:
((struct prioq *)(NULL))->heap
и немедленно прилетит сигнал SIGSEGV и программа завершится.
Ты до того как проверяешь queue на NULL уже разыменовываешь этот
(потенциально нулевой) указатель ещё в определении локальных переменных:
struct prioq_head *
prioq_get(struct prioq*queue)
{
struct prioq_head* head = queue->heap[0];
struct user_data* ptr;
Это ошибка, так делать нельзя. Поэтому head ты можешь присваивать
значение только после того как проверил queue на NULL.
Далее, очень сложно сделано, Лёша, зачем? Ведь после того как ты
проверил queue на NULL, дальше этого делать не надо, тебе известно точно
что он уже не нулевой указатель. Поэтому такая конструкция избытона:
if ((queue != NULL) && (head != NULL))
Она не нужна.
2. Ты не корректно реализовал то что было в псевдокоде, посмотри ещё
раз. Обрати внимание, что прежде чем индексироваться в queue->heap мы
уменьшили used на 1. У тебя декремент идёт после! Поэтому программа
сваливается (в лучшем случае, потому что там в массиве указателей они
NULL) а в худшем будешь искать почему "не тот" элемент получили.
e = queue[0];
queue.used = queue.used - 1;
queue[0] = queue[queue.used];
prioq_heapify(queue);
Здесь сначала уменьшили used на 1 и потом индексируемся. Ведь последний
элемент имеет индекс queue.used-1, так?
queue->heap[0] = queue->heap[used]; <- лезем в чужую ячейку
queue->heap[0]->index = used;
queue->used--; <- и только теперь уменьшили
Кроме того, зачем ты освобождаешь там указатель с польз. данными?? Этого
делать не надо, потому что это пользователь только знает, надо их
освобождать или нет. Твоя очередь не размещала их в памяти, не ей и их
освобождать.
Ещё раз пересмотри пожалуйста алгоритм извлечения элемента из очереди.
Он же очень простой, но у тебя он катастрофически сложен!
Что-то с оформлением у нас безобразие, всё уплывает, читать тяжеловато,
если честно. Посмотри пожалуйста LKCS, внимательно прочитай и далее
придерживайся этого стиля при программировании на Си таких вещей, хотя
повторюсь что это не догма. И много предупреждений выдаёт gcc, надо
править всё.
3. Если тебе что-то не понятно, как работает на Си, задай вопросы.
Потому что просто писать что что тебя просят это копировать форму, но не
содержание, т.е. тебе будет понятно КАК но ЗАЧЕМ - нет. Надо это
исправить, потому что задача здесь именно понять ЗАЧЕМ.
--
Г.А.
Алексей Петрунёв пишет:
> Написал prioq_get, посмотрите.
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> cdev mailing list
> cdev на wiki.syktsu.ru
> http://wiki.syktsu.ru/cgi-bin/mailman/listinfo/cdev
Подробная информация о списке рассылки cdev