Форум: "Основная";
Текущий архив: 2004.04.11;
Скачать: [xml.tar.bz2];

Вниз

Очень нужна помощь! Двусвязные списки...(Pascal)   Найти похожие ветки 

← →
Alexis ©   (2004-03-23 14:20) [0]


program Lists;//списки
uses
Crt;
type
double_list = ^elem;
elem = record
        info:integer;
   next, prev:double_list;
end;

procedure CreateList(var newlist:double_list);
var
 list:double_list;
 n:Word;
 i:integer;
begin
 newlist := nil;
 n := 1;
 write(" Enter ",n," element : ");
 readln(i);
 while i <> 0 do
  begin
   new(list);
   if newlist = nil then
    begin
     list^.info := i;
     list^.next := nil;
     list^.prev := nil;
    end
   else
    begin
     list^.info := i;
     list^.next := newlist;
     list^.prev := nil;
     newlist^.prev := list;
    end;
   newlist := list;
   n := n+1;
   write(" Enter ",n," element : ");
   readln(i);
  end;
//  dispose(list);
end; //конец подпрограммы

procedure PrintList(for_print : double_list);
 var item:double_list;
begin
 item := for_print;
 textcolor(red);
 writeln("printing list...");
 textcolor(black);
 while item <> nil do
  begin
   write(item^.info, " -> ");
   item := item^.next;
  end;
 write("/");
 writeln;
end;

procedure CompressList(long : double_list; var short : double_list);
 var
  p:double_list;
begin
 short := long;
 short := short^.next;

//ошибка здесь-при удалении из списка
  while short^.next <> nil do //чтобы не рассматривать последний элемент
   begin
    if short^.info = short^.next^.info then
     begin
      short^.prev^.next := short^.next^.next;
      short^.next^.prev := short^.prev^.prev;
      short^.next := nil;
      short^.prev := nil;
      dispose(short);
      //=====
{      if short^.next^.next = nil then //если следующий с nil"ом
       begin
        short^.next := nil;
   short^.prev := short^.next^.prev;
  end
      else
       begin
   p := short^.next^.next^.next;
   p^.prev := short^.prev;
  end;
}
     
   end;

 while short^.prev <> nil do short := short^.prev;
end;

var
 newlist, compressedlist:double_list;
begin
repeat
clrscr;
textcolor(red);
writeln("Программа создает двухсторонний список чисел "INTEGER" типа и удаляет повторяющиеся элементы.");
writeln("========================================");
textcolor(black);
new(newlist);
CreateList(newlist);
PrintList(newlist);
CompressList(newlist, compressedlist);
PrintList(compressedlist);
dispose(newlist);
writeln("<ESC> - leave program,");
writeln("another key - continue.");
until ord(readkey) = 27;
end.


Очень нужна помощь! Есть ли у кого пример удаления элемента из двухстороннего списка?
Все остальные процедуры кроме CompressList работают хорошо.
OS Linux, FPC 1.0.10

---

← →
Yermek   (2004-03-23 14:38) [1]

Доооолго я вчитывался в твой текст :)
ладно это была лирика, попробуй, для пробы (так сказать для теста) использовать обыкновенный массив, кстати скажи на что именно жалуется компилятор, в смысле что выдает.

---

← →
PVOzerski ©   (2004-03-23 14:56) [2]

Все-таки разбирать исходники целиком приведенной программы - задача не из приятных. Давайте уж по сути.

А по сути вот что. Мы должны удалить элемент из списка. При этом возможны 3 различные ситуации
1) Удаляется начальный элемент списка. Тогда поле prev у него должно быть nil. Но главное то, что этот элемент - ключевой при любом обращении к списку, от него "танцуем" при переборе всех элементов списка. Я бы, если это не единственный элемент в списке, вообще удалял не его, а последующий элемент, значения прочих полей которого переприсваивил бы этому. Хотя, конечно, можно и удалить именно его, но тогда не забываем обновить значения и для дополнительных переменных-указателей, если такие имеются.
2) Удаляется конечный элемент списка. Здесь ситуация зависит от того, контролируем ли мы "хвост" списка для доступа, или же добираемся до него только с "головы". Соответственно, решение может быть как в случае (1) или как в общем случае.
3) Общий случай: элемент не в начале и не в конце списка. Тогда если удаляемый элемент - elem, то
if elem^.next<>nil then
elem^.next^.prev:=elem^.prev;
if elem^.prev<>nil then
elem^.prev^.next:=elem^.next;
...<после освобождения динамически выделенных полей, если такие есть>dispose(elem);

---

← →
MBo ©   (2004-03-23 15:03) [3]

Для исключения многообразия случаев удобно фиктивные элементы вводить в начале и конце.

---

← →
Alexis ©   (2004-03-23 15:25) [4]

2Yermek-компилятор ни на что не жалуется, компилируется без ошибок, а во время выполнения вылетает Runtime Error.Кстати я конкретно спрашивал про списки(обыкновенный массив в задании применять нельзя).

2PVOzerski-
1) Удаляется начальный элемент списка. Тогда поле prev у него должно быть nil. Но главное то, что этот элемент - ключевой при любом обращении к списку, от него "танцуем" при переборе всех элементов списка. Я бы, если это не единственный элемент в списке, вообще удалял не его, а последующий элемент, значения прочих полей которого переприсваивил бы этому. Хотя, конечно, можно и удалить именно его, но тогда не забываем обновить значения и для дополнительных переменных-указателей, если такие имеются.

Я тоже так думаю-если встретятся два одинаковых элемента, то удалять следующий, и в таком случае проверять есть ли после следующего еще один, чтобы связать первый и третий, т.е.

...-X-Y-Z-
если X и Y одинаковы, то смотрим есть ли после Y какой либо Z или нет и если есть, то связываем X и Z(Y удаляем).
Предложите свой вариант, а то мне после 3-х часов усилий уже страшно на код смотреть:)

---

← →
Vuk ©   (2004-03-23 15:43) [5]

куски из собственной реализации двусвязных списков

   TCLNode = class( TObject )
   protected
     FData     : pointer;
     FNextNode : TCLNode;
     FPrevNode : TCLNode;
   public
     property    Data : pointer read FData write FData;
     property    Next : TCLNode read FNextNode write FNextNode;
     property    Prev : TCLNode read FPrevNode write FPrevNode;
   end;

   TCLList = class
   protected
     FFirst : TCLNode; //первый элемент списка
     FLast  : TCLNode; //последний элемент списка
   public
     {удаление элемента}
     procedure   DeleteNode( Node : TCLNode );    
     {вставка нового елемента перед указанным, node = nil
      для вставки в конец списка}
     procedure   InsertNode( Node, NewNode  : TCLNode );
   end;

procedure  TCLList.InsertNode( Node, NewNode  : TCLNode );
begin
 if NewNode = nil then
   exit;
 if Node = nil then begin
   //put node at end of list
   NewNode.Prev := FLast;
   if FFirst = nil then begin
      FFirst := NewNode;
      FLast := NewNode;
   end
   else begin
      FLast.Next := NewNode;
      FLast := NewNode;
   end;
 end
 else begin
   NewNode.Next := Node;
   NewNode.Prev := Node.Prev;
   if Node.Prev <> nil then
     Node.Prev.Next := NewNode;
   Node.Prev := NewNode;
   if Node = FFirst then
     FFirst := NewNode;
 end;

end;

procedure TCLList.DeleteNode( Node : TCLNode );
begin
 if Node = nil then
    exit;
 with Node do begin
   if Next <> nil then
      Next.Prev := Prev;
   if Prev <> nil then
      Prev.Next := next;
 end;
 if Node = FFirst then
   FFirst := Node.Next;
 if Node = FLast then
   Flast := Node.Prev;

 Node.Next := nil;
 Node.Prev := nil;

end;



---

← →
Alexis ©   (2004-03-23 15:49) [6]

2Vuk-спасибо большое!
На Free Pascal Compiler(Линуксовый аналог TurboPascal) скомпилируется?

---

← →
Vuk ©   (2004-03-23 15:51) [7]

to Alexis:
>а Free Pascal Compiler(Линуксовый аналог TurboPascal)
>скомпилируется?
Не знаю, не пробовал. :o) По идее здесь нет ничего особенного, связанного с компилятором. Просто работа с указателями.

---

← →
Fay ©   (2004-03-23 15:52) [8]

Free Pascal для линуха - линуховый аналог виндового Free Pascal.

---

← →
Alexis ©   (2004-03-25 12:46) [9]

Vsem ogromnoe spasibo, izmenil-rabotaet.Vot kod:


procedure CompressList(long : double_list; var short : double_list);
 var
  s:double_list;
begin
 short := long;
 if short = nil then exit;
 if short^.next = nil then exit; //only 1 element
 while short^.next <> nil do
  begin
   s := short^.next;
   if short^.info = s^.info then
    begin
     if s^.next <> nil then
      s^.next^.prev := s^.prev;
     if s^.prev <> nil then
      s^.prev^.next := s^.next;
     s^.next := nil;
     s^.prev := nil;
     dispose(s);
    end
   else
    short := short^.next;
  end;

 while short^.prev <> nil do
  short := short^.prev;
end;


Kakie budut zamecanija po povodu optimizacii, racionalnosti algoritma udalenija?

---

← →
PVOzerski ©   (2004-03-25 12:56) [10]

>На Free Pascal Compiler(Линуксовый аналог TurboPascal) скомпилируется?
Если с классами и т.п., добавь {$mode Delphi} или компилируй с ключом -Sd. Альтернатива - {$mode objfpc} или ключ -S2, но могут быть проблемы с синтаксисом.
Код, приведенный в [9], должен скомпилироваться без проблем. Вообще, FPC хорошо справляется со связными списками (а вот StonyBrook, например, делает какую-то такую оптимизацию, что иногда начинаются глюки).

---

← →
Alexis ©   (2004-03-25 15:54) [11]

> Код, приведенный в [9], должен скомпилироваться без проблем

Так ведь я и пишу, что работает:)
Может какие замечания по поводу оптимальности?

Кстати, раз уж зашла речь об FPC, то не знаете ли, PVOzerski, как пользоватся в нем модулем Graph(версия FPC 1.0.10).
Я включаю модуль(uses Graph), а при компиляции выдается:

/usr/bin/ld -lvga not found.
Linking not done.

Может какой-то ключ при компиляции надо указывать?

---

Страницы: 1 вся ветка

Форум: "Основная";
Текущий архив: 2004.04.11;
Скачать: [xml.tar.bz2];

Наверх

Память: 0.49 MB
Время: 0.04 c