Списки в Паскале

[silentkiller]

Всем привет. Дали в универе задачку на работу со списками, причём толком как это делается никто не объяснил. Очень надеюсь на Вашу помощь. Итак, исходные данные:
1) создать двухсвязный список из случ. чисел (через random, штук 20)
2) из элементов от 1-го по счёту до последнего отрицательного создать один замкнутый список (кольцо)
3) из остальных элементов создать второе кольцо
Заранее спасибо. Если не затруднит, то продублируйте код программы и на мыло alex17@tut.

[Serge_Bliznykov]

что-то все молчат...
а мне - лень полностью раскрывать тему...
ладно, для затравки кину идею (тип данных):

Код: Выделить всё

type
   pMyNumber=^MyNumber; 
   MyNumber =record 
      Value: integer;
      next :p MyNumber;  
      prev :p MyNumber;  
   end;  

дальше разберётесь?...

[silentkiller]

Это всё понятно. Я не знаю как создать двухсвязный список. По идее указатели next и prev должны указывать на одно и то же место, т.е. надо соединить начало и конец списка. Затем из этого списка выловить нужные значения и поместить в другой список (в цикле). Полученный список замкнуть таким же образом. Вроде так... Только как это на паскале записать я не догоняю

[Duncon]

Код: Выделить всё

next :p MyNumber;  
prev :p MyNumber;

[LAngel]

Структура линейного двухсвязного списка:

Элементы Prev и Next элемента списка указывают соответственно на предыдущий
и следующий элементы.

Код: Выделить всё

     +---------+        +---------+        +---------+
     | TMyType |<-+  +->| TMyType |<-+  +->| TMyType | 
     +---------+  |  |  +---------+  |  |  +---------+
     | Info    |  |  |  | Info    |  |  |  | Info    |
     +---------+  |  |  +---------+  |  |  +---------+
Nil<-| Prev    |  +--|--| Prev    |  +--|--| Prev    |
     +---------+     |  +---------+     |  +---------+
     | Next    |-----+  | Next    |-----+  | Next    |->Nil
     +---------+        +---------+        +---------+

[syntax=pascal]PMyType = ^TMyType;

TMyType = record
Info: Integer;
Prev: PMyType;
Next: PMyType;
end;[/syntax]


Добавление элемента, происходит либо в конец списка, либо в начало.
Для удобства хранят ссылку на первый элемент списка.

В кольцевом двухсвязном списке последний элемент указывает на первый, а
первый на последний.

[LAngel]

Вот, что я тут наваял на коленке )

[syntax=pascal]PMyType = ^TMyType;

TMyType = record
Info: Integer;
Prev: PMyType;
Next: PMyType;
end;

var
First: PMyType;
Cursor: PMyType;
LastNegItem: PMyItem;
i: Integer;
begin
new(First); // создадим первый элемент списка

First^.Info := Random(1000)-500;
First^.Next := nil;
First^.Prev := nil;

for i := 1 to 19 do // создаем остальные 19
begin
new(Cursor);
Cursor^.Info := Random(1000)-500;
Cursor^.Next := First;
Cursor^.Prev := nil;
First^.Prev := Cursor;
First := Cursor;
end;

// ищем первый последний отрицательный элемент
LastNegItem := nil;
Cursor := First;
while Cursor <> nil do
begin
if Cursor^.Info < 0 then LastNegItem := Cursor;
Cursor := Cursor.Next;
end;

if LastNegItem <> nil then
begin // элемент существует, можно продолжить
// найдем последний элемент:
Cursor := First;
while Cursor^.Next <> nil do Cursor := Cursor^.Next;
// Создадим сначала второе кольцо (из оставшихся элементов)
Cursor^.Next := LastNegItem^.Next^;
LastNegItem^.Next^.Prev := Cursor;
// теперь создадим первое кольцо
First^.Prev := LastNegItem;
LastNegItem^.Next := First;
WriteLn('задача выполнена');
// очистим память второго кольца
First := Cursor;
Cursor^.Prev^.Next := nil;
while First <> nil do
begin
Cursor := First^.Next;
Dispose(First);
First := Cursor;
end;
// очистим память первого кольца
First := LastNegItem;
LastNegItem^.Prev^.Next := nil;
while First <> nil do
begin
Cursor := First^.Next;
Dispose(First);
First := Cursor;
end;
end else begin
WriteLn('Отрицательных элементов нет в списке');
// очистим память
while First <> nil do
begin
Cursor := First^.Next;
Dispose(First);
First := Cursor;
end;
end;


end.
[/syntax]

[Serge_Bliznykov]

Потерянный Ангел, спасибо за помощь. Круто!!!

[silentkiller]

Огромное спасибо LAngel. Программка правда не работает, но помогла разобраться что и как. Ошибки поисправлял, добавил вывод всех трёх списков... Надеюсь прокатит
ps: иногда при запуске кидает invalid poiner operation на Dispose(first). Не в курсе, с чем это может быть связано? Из 5 запусков 3-4 нормальных, 1-2 с ошибкой...
pps: кто-нибудь вообще использует данные алгоритмы в реальной жизни? Ну или скажем деревья, графы? А то у меня ощущение, что это дают типа для галочки, чтобы знали (универ всё таки ).
Ещё раз спасибо всем за помощь!!!

[LAngel]

Ну я ж сказал, что писано на коленке, не оттещено.
Вот вам отдебаженый вариант:

[syntax="pascal"]program P1;
type
PMyType = ^TMyType;
TMyType = record
Info: Integer;
Prev: PMyType;
Next: PMyType;
end;

var
First: PMyType;
Cursor: PMyType;
LastNegItem: PMyType;
i: Integer;

begin
Randomize;
new(First); // создадим первый элемент списка
First^.Info := Random(1000)-500;
First^.Next := nil;
First^.Prev := nil;
for i := 1 to 19 do // создаем остальные 19
begin
new(Cursor);
Cursor^.Info := Random(1000)-500;
Cursor^.Next := First;
Cursor^.Prev := nil;
First^.Prev := Cursor;
First := Cursor;
end;

WriteLn('Элементы списка: ');
Cursor := First;
repeat
Write(Cursor^.Info, ' ');
Cursor := Cursor^.Next;
until Cursor = nil;
WriteLn('');

// ищем первый последний отрицательный элемент
LastNegItem := nil;
Cursor := First;
while Cursor <> nil do
begin
if Cursor^.Info < 0 then
LastNegItem := Cursor;
Cursor := Cursor.Next;
end;
if LastNegItem <> nil then
begin // элемент существует, можно продолжить
// найдем последний элемент:
Cursor := First;
while Cursor^.Next <> nil do Cursor := Cursor^.Next;
if Cursor = LastNegItem then
begin
WriteLn('за последним отрицательным элементов нет.');
// создадим одно кольцо
Cursor^.Next := First;
First^.Prev := Cursor;

WriteLn('Единственное кольцо: ');
First := LastNegItem^.Next;
repeat
Write(First^.Info, ' ');
First := First^.Next;
until First = LastNegItem^.Next;
WriteLn('');

// очистим память этого кольца
First := LastNegItem;
First.Prev^.Next := nil;
while First <> nil do
begin
Cursor := First^.Next;
Dispose(First);
First := Cursor;
end;
end else begin
// Создадим сначала второе кольцо (из оставшихся элементов)
Cursor^.Next := LastNegItem^.Next;
LastNegItem^.Next^.Prev := Cursor;
Cursor := Cursor^.Next;
// теперь создадим первое кольцо
First^.Prev := LastNegItem;
LastNegItem^.Next := First;
WriteLn('задача выполнена');

WriteLn('Первое кольцо: ');
First := LastNegItem^.Next;
repeat
Write(First^.Info, ' ');
First := First^.Next;
until First = LastNegItem^.Next;
WriteLn('');

WriteLn('Второе кольцо: ');
First := Cursor;
repeat
Write(First^.Info, ' ');
First := First^.Next;
until First = Cursor;
WriteLn('');

// очистим память второго кольца
First := Cursor;
Cursor^.Prev^.Next := nil;
while First <> nil do
begin
Cursor := First^.Next;
Dispose(First);
First := Cursor;
end;
// очистим память первого кольца
First := LastNegItem;
LastNegItem^.Prev^.Next := nil;
while First <> nil do
begin
Cursor := First^.Next;
Dispose(First);
First := Cursor;
end;
end;
end else begin
WriteLn('Отрицательных элементов нет в списке');
// очистим память
while First <> nil do
begin
Cursor := First^.Next;
Dispose(First);
First := Cursor;
end;
end;

end.[/syntax]

[silentkiller]

Ну что я могу сказать... МЕГАРЕСПЕКТ!!! Сразу видна рука мастера
Для меня ты настоящий ангел (реально спас). Спасибо!