Работа с двунаправленными списками

[Sparky]

Добрый вечер. Помогите пожалуйста. Необходимо реализовать следующие процедуры:
1.функция проверки существования списка
2.процедура всавки элементов в конец списка
3.процедура печати списка от первого
4.процедура печати списка от последнего
5.процедура удаления списка
6.получение указателя по индексу
7.получение указателя по значению
8.получение значения следующего за текущим
9.процедура удаления элементов по значению
10.процедура обмена элементов
11.сортировка пузырьком
12.быстрая сортировка

Часть из них я написала вот что у меня получилось


Проблемы с реализацией сортировок и процеруры обмена элементов и удалением элементов по значению. Помогите пожалуйста

[Sparky]

вот мой код:

program spisok;
type PList=^TList;

  TList=record
    inf:integer;
    prior:Plist;
    next:Plist
  end;

  ListCont=object first,last:PList;
    constructor Init;
    function Empty:boolean; //функция проверки существования списка
    procedure Insert(x:integer); //процедура всавки элементов в конец списка
    procedure Print_forward(start:PList); //процедура печати списка от первого
    procedure Print_back(start:PList);  //процедура печати списка от последнего
    procedure Remove(var start:PList);  //процедура удаления списка
    function GetById(i:integer):PList;  //получение указателя по индексу
    function GetByValue(x:integer):PList; //получение указателя по значению
    function GetNextByValue(P:Plist):Plist;   //получение значения следующего за текущим
    procedure RemoveAll(var start:PList;x:integer); //процедура удаления элементов по значению
    procedure Swap(i,j:integer);  //процедура обмена элементов
    procedure BubbleSort; //сортировка пузырьком
    procedure QuickSort;    //быстрая сортировка
  end;

constructor ListCont.Init;  //инициализация списка
begin
  first:=nil; last:=nil;
end;

function ListCont.Empty:boolean;  //процедура проверки наличия списка
begin
  Empty:=(last=nil) and (first=nil);
end;

procedure ListCont.QuickSort;    //быстрая сортировка
begin

end;

procedure ListCont.BubbleSort;   //пузырьковая сортировка
begin

end;

procedure ListCont.Insert(x:integer); //процедура всавки элементов в конец списка(информационная часть)
var
  p:PList;
begin
  new(p);
  p^.inf:=x;
  p^.next:=nil;
  if Empty then
  begin
    first:=p;
    first^.prior:=nil;
  end
  else
  begin
    last^.next:=p;
    p^.prior:=last;
  end;
  last:=p;
end;

procedure ListCont.Remove(var start:PList);  //процедура удаления списка
var
  q:Plist;
begin
  if start=nil then writeln('List not init')
  else
  begin
    while start<>nil do
    begin
      q:=start;
      start:=start^.next;
      dispose(q);
    end;
  end;
end;

procedure ListCont.Print_forward(start:PList); //процедра печати элементов с первого(начало)
begin
 if start=nil then writeln('List not init')
 else
 begin
 while (start<>nil) do
  begin
   write(start^.inf,' ');
   start:=start^.next;
  end;
 end;
end;

procedure ListCont.Print_back(start:PList); //процедра печати элементов с последнего(начало)
begin
  if start=nil then writeln('List not init')
  else
  begin
    while (start<>nil) do
    begin
      write(start^.inf,' ');
      start:=start^.prior;
    end;
  end;
end;


function ListCont.GetById(i:integer):PList;  //получение указателя по индексу(индекс)
var
  p:PList;
  j:integer;
begin
  p:=first;
  j:=1;
  while ((p<>nil) and (j<>i)) do
  begin
    p:=p^.next;
    inc(j);
  end;
  if p=nil then GetById:=nil
  else if j=i then GetById:=p;
end;

function ListCont.GetByValue(x:integer):PList; //получение указателя по значению(инофрмационное поле)
var
  p:PList;
begin
  p:=first;
  while ((p<>nil) and (p^.inf<>x)) do
  begin
    p:=p^.next;
  end;
  if p=nil then GetByValue:=nil
  else if p^.inf=x then GetByValue:=p;
end;

procedure ListCont.RemoveAll(var start:PList;x:integer);  //процедру удления элементов по значению(информационное поле)
begin

end;

procedure ListCont.Swap(i,j:integer);  //процедура обмена элементов
var
  p,q,t:PList;
begin
  p:=ListCont.GetById(i);
  q:=ListCont.GetById(j);
  if ((p<>nil) and (q<>nil)) then
  begin
    new(t);
    t^.inf:=p^.inf;
    t^.next:=p^.next;
    t^.prior:=p^.prior;


    p^.inf:=q^.inf;
    p^.next:=q^.next;
    p^.prior:=q^.prior;

    q^.inf:=t^.inf;
    q^.next:=t^.next;
    q^.prior:=t^.prior;
  end;
end;


function ListCont.GetNextByValue(P:Plist):Plist;   //получение значения следующего за текущим
begin

end;

[Sparky]

var
  List:ListCont;  //список
  temp_o,temp_t,count,i:integer;
  temp_list:PList;

begin

  List.Init;  //создание списка

{===============================================================================
                                вставка элементов в список и вывод
===============================================================================}
  writeln('output list forward');
  List.Print_forward(List.first);
  writeln('output list back');
  List.Print_back(List.last);

  writeln('enter count element');
  readln(count);

  for i:=1 to count do
  begin
    randomize;
    temp_o:=random(10);
    List.Insert(temp_o);
  end;

  writeln('output list forward');
  List.Print_forward(List.first);
  writeln;
  writeln('output list back');
  List.Print_back(List.last);
  writeln;

{===============================================================================
                                поиск элементов
===============================================================================}
{  writeln('enter index');
  readln(temp);
  temp_list:=List.GetById(temp);
  //вывести как-то результат
  if temp_list=nil then writeln('no index')
  else writeln(temp_list^.inf);

  writeln('enter data');
  readln(temp);
  temp_list:=List.GetByValue(temp);
  //вывести как-то результат
  if temp_list=nil then writeln('no data')
  else writeln(temp_list^.inf); }

{===============================================================================
                                удаление элементов и всего списка
===============================================================================}
 { writeln('enter data');
  readln(temp);
  List.RemoveAll(List.first,temp);
  writeln('output list forward');
  List.Print_forward(List.first);
{  writeln('delete list');
  List.Remove(List.first);

  writeln('output list forward');
  List.Print_forward(List.first);
  writeln;
  writeln('output list back');
  List.Print_back(List.last);
  writeln;      }

{===============================================================================
                                замена элементов
===============================================================================}
  writeln('enter elements');
  readln(temp_o,temp_t);

  List.Swap(temp_o,temp_t);

  writeln('output list forward');
  List.Print_forward(List.first);

{===============================================================================
                сортировки
===============================================================================}
  writeln('buble');
  List.BubbleSort;
  writeln('output list forward');
  List.Print_forward(List.first);
  writeln;

  writeln('QuickSort');
  List.QuickSort;
  writeln('output list forward');
  List.Print_forward(List.first);
  writeln;

  readln;
end.

[eoln]

1) Обмен. Тут менять ОДНО из двух: либо адреса, либо информацию. При смене адресов надо учитывать соседние элементы, поэтому быстрее будет изменить информационную часть (благо не мегабайты ворочить)

  if ((p<>nil) and (q<>nil)) then
  begin
    new(t);
    t^.inf:=p^.inf;
    //t^.next:=p^.next;
    //t^.prior:=p^.prior;

    p^.inf:=q^.inf;
    //p^.next:=q^.next;
    //p^.prior:=q^.prior;

    q^.inf:=t^.inf;
    //q^.next:=t^.next;
    //q^.prior:=t^.prior;
  end;

2) Удаление по значению

procedure ListCont.RemoveAll(x:integer); //изменяем вид вызова процедуры (убираем параметр start) {в описании класса тоже убрать надобны параметр stast}
var
  p, q:PList;
begin
  p:=first;
  while (p<>nil) do
  begin
    if p^.inf = x then begin //нашли нужные значения
      if p = first then begin //если удаляем первый элемент
        first := p^.next; //то редактируем указатель начала
        first^.prior := nil;
      end else
      if p^.next = nil then p^.prior^.next := nil else//если последний, то редактируем предпоследний
      begin //если где-то в середине
        p^.prior^.next := p^.next;//редактируем
        p^.next^.prior := p^.prior//соседнии элементы
      end;
      q := p; //указатель на удаляемый элемент
      p := p^.next;
      dispose(q);//удаляем
      continue
    end;
    p:=p^.next;
  end
end;

Соответственно в программу добавляем вызов

write('ydalenie elementov po znach = ');
  readln(i);
  List.RemoveAll(i);
  writeln('output list forward');
  List.Print_forward(List.first);
  writeln;

3) На счёт сортировок голова уже не думает (8 марта всё-таки )) ). Вобщем двойной цикл там надо - google или wikipedia в помощь. Буду жив завтра, обязательно отпишуся...

P.S. На будущее, кроме указателя на первый элемент, используй также указатель на последний элемент списка - это облегчает работу с динамическими списками (используйте "паразитное" дополнение лишнего элемента в 4 байта). Код вцелом разумен и практически оптимизирован. Ах да, не передавай массивы в параметрах - сделай их глобальными чтоли или передавай тока начальные и конечные адреса.

[Stilet]

Насчет списков, вот когда-то кому-то писал пример:

program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
 TDataTipe=integer;
 PTItem=^TItem;
 TItem=Record
  Data:TDataTipe;
  Prev,Next:PTItem;
 end;
var
 First,CurItem:PTItem;

//Добавляем в список**********************
  Function Ins(PrevItem:PTItem;AData:TDataTipe):PTItem;
  begin
    new(result);
    result^.Data:=AData;
    Result^.Prev:=PrevItem;
    Result^.Next:=nil;
      if PrevItem<>nil then begin
        if (PrevItem^.Next<>nil) then
         PrevItem^.Next^.Prev:=Result;
        PrevItem^.Next:=Result;
      end;
  end;

// Наполняем   **************************
 function fill:boolean;
 var i:integer;
 begin
   First:=ins(nil,0);
   CurItem:=First;
   for i:=1 to 10 do begin
     CurItem:=ins(CurItem,(20+random(100)));
   end;
 end;

// Выводим ******************************
 function outt:boolean;
 var i:integer;
 begin
   CurItem:=First;
   while CurItem<>nil do begin
     write(curitem^.data:5);
     CurItem:=CurItem^.Next;
   end;
 end;

// Сортируем ***************************
 Function Sort:boolean;
 var q:PTItem;s:TDataTipe;
 begin
  q:=First;
  while q<>nil do begin
   CurItem:=q;
   while CurItem<>nil do begin
    if CurItem^.Data<q^.Data then begin
      s:=CurItem^.Data;
      CurItem^.Data:=q^.Data;
      q^.Data:=s;
    end;
    CurItem:=CurItem^.Next;
   end;
   q:=q^.Next;
  end;
 end;


begin
   fill;
   outt;
   writeln;
   Sort;
   outt;
   Readln;
  { TODO -oUser -cConsole Main : Insert code here }
end.

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

[Sparky]

спасибо, сортировка пузырьком?

[Stilet]

сортировка пузырьком?

Ага. Шампанскими пузырьками в честь последнего праздника