VPF::Двусвязный список - Форум программистов

Anark1

Дата 3.11.2008, 01:21 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 622
Регистрация: 15.12.2006
Где: RF -> Moscow

Репутация: нет
Всего: 11

Собственно сабж. Условия подзадачи такие : даны числа произвольной системы счисления (2-36), они хранятся в двусвязных списках. Реализуется вычитание одного из другого - алгоритм столбик. Также заведомо из одного можно вычесть другое.
Структура списка:

Код


type PList = ^TList;
     TList = record
           Prev : PList;
           Value : Byte;
           Next : PList;
           end;

Стоит заметить, что списки заполняются правильно (проверял дебаггом и выводом в обе стороны).
Но если что вот сам ввод:

Код


procedure PushToBack(var Head : PList;var Tail :PList; dec : byte);
var NewPtr : PList;
begin
New(NewPtr);
NewPtr^.Value:=dec;
if Head=nil then begin
                 Head:=NewPtr;
                 Tail:=NewPtr;
                 end
            else begin
                 Tail^.Next:=NewPtr;
                 NewPtr^.Prev:=Tail;
                 Tail:=NewPtr;
                 end;
end;

А теперь самое главное. Бьюсь головой об стену, не понимаю как такое в принципе возможно. Вот код процедуры вычитания

Код


procedure Subtract(var MainHead : PList;var MainTail:PList;Head,Tail : PList;
                        var Maincount:integer; count : integer; osn :byte);
var i,k,j : integer;
    Ptr1,Ptr2 : PList;
begin
Ptr1:=MainTail;
Ptr2:=Tail;                {vichitanie}
for i:=1 to count do
    begin
    if Ptr1^.Value>=Ptr2^.Value then
                               Ptr1^.Value:=Ptr1^.Value-Ptr2^.Value {esli mojno vichest' bez zaniyatiya edinici}
                               else begin
                               k:=0;
                               Ptr1^.Value:=Ptr1^.Value-Ptr2^.Value+osn; {inache zanimaem iz sled. razryada}
                               repeat
                               k:=k+1;
                               Ptr1:=Ptr1^.Prev;    {ishem pervii nenulevou elemnt dlya zaima}
                               until Ptr1^.Value<>0;
                               Ptr1^.Value:=Ptr1^.Value-1;  {zanimaem 1}
                               for j:=0 to k do
                               begin
                               Ptr1:=Ptr1^.Next;  {vozvrashaemsya}
                               if Ptr1^.Value=0 then Ptr1^.Value:=osn-1; {esli bili 0}
                               end;
                               end;
    Ptr1:=Ptr1^.Prev;          {<<<<<<<!!!!!>>>>>>>}
    Ptr2:=Ptr2^.Prev;
    end;
Ptr1:=Mainhead;
While Ptr1^.Value=0 do            {udalenie nulevih elementov v na4ale}
                    begin
                    Mainhead:=Ptr1^.Next;
                    Dispose(Ptr1);
                    Ptr1:=MainHead;
                    MainCount:=MainCount-1;
                    end;
end;

Все работает, если вычитание происходит без заема разряда. А вот если нужно выполнить например 123-45, то начинается проблема. В дебаггере это выглядит так : первый символ получается правильным, потом занимаем у следующего элемента, переходим назад, а когда опять возвращаемся к элементу у которого занимали, то там оказывается непонятно что. Строка 26, там где <<<!!!>>.
То есть грубо говоря, если Ptr^.Value=5, то после Ptr:=Ptr^.Next; Ptr:=Ptr^.Prev получаем Ptr^.Value<>5. Причем этот указатель изменяется самопроизвольно - я замечал, что он ни с того ни с сего меняет значение когда компилятор проходит строку 25. Более того, там оказывается какой-то мусор, значения вроде 139, хотя тип Byte и вообще непонятно как такое возможно. Что я уже только не попробовал. Ошибка какая-то глупая...
Очень прошу помощи, заранее благодарен

--------------------

Enjoy yourself, still you can...;)

volvo877

Дата 3.11.2008, 14:04 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116

Цитата(Anark1 @ 3.11.2008, 00:21

)

То есть грубо говоря, если Ptr^.Value=5, то после Ptr:=Ptr^.Next; Ptr:=Ptr^.Prev получаем Ptr^.Value<>5.

А все знаешь почему? Потому, что ты
1) некорректно заполняешь список (хоть и утверждаешь, что все в порядке)... Вот так будет корректно:

Код

procedure PushToBack(var Head : PList;var Tail :PList; dec : byte);
var NewPtr : PList;
begin
New(NewPtr);
NewPtr^.Value:=dec;
NewPtr^.next := nil; { <--- Чувствуешь разницу? }
NewPtr^.prev := nil;

if Head=nil then begin
                 Head:=NewPtr;
                 Tail:=NewPtr;
                 end
            else begin
                 Tail^.Next:=NewPtr;
                 NewPtr^.Prev:=Tail;
                 Tail:=NewPtr;
                 end;
end;

У тебя в Next последнего элемента и в Prev первого хранился мусор, а не nil-ы...

2) вот из первого вытекает как раз второе: если при

Код

                               for j:=0 to k do
                               begin
                               Ptr1:=Ptr1^.Next;  {vozvrashaemsya}
                               if Ptr1^.Value=0 then Ptr1^.Value:=osn-1; {esli bili 0}
                               end;

Ты вылетаешь (а ты вылетаешь-таки, проверь) за последний элемент списка, то раньше ты переходил по какому-то "левому" указателю в никуда, и из "ниоткуда" вообще непонятно куда возвращался, теперь у тебя в определенный момент Ptr1 будет равно nil, и вылетит ошибка "переход по нулевому указателю"... Кстати, мне почему-то кажется, что в том цикле, который я показал, J должно изменяться не от 0, а от 1 до K...

Anark1

Дата 3.11.2008, 16:16 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 622
Регистрация: 15.12.2006
Где: RF -> Moscow

Репутация: нет
Всего: 11

volvo877, именно так. Вчера через два часа после того как запостил, нашел ошибку. Но сил уже заходить на форум не было. Но все равно спасибо за внимание. smile

По поводу списка - это не обязательно, если есть счетчик count. Разве в целях аккуратности.

--------------------

Enjoy yourself, still you can...;)

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Object Pascal: кроссплатформенные технологии \| Следующая тема »