Очередь на основе односвязного кольцевого списка , примерно вот так получился список, не уверен что правильно

[kotmatroskin55]

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

unit L1_sp;
interface
uses crt,timer;
type
TElem=integer;
TFile=file of TElem;
Link=^ListElem;
ListElem=record
   Data:TElem;
   next:Link;
end;
L1_List=object
  private
    buf:Link;
    Temp:Link;
    //err_code:word;    
  public
    constructor CreateList;//создание списка
    constructor CopyList(var List:L1_List);//копирование
    destructor Destroy_List;//удаление с очисткой памяти
    procedure ClearList;//очистка текущуго списка
    function IsEmptyList:boolean;//пустой ли список
    procedure PutTempForvard;//вправо
    procedure InBegin;//в начало
    //function IsTempLast:boolean;
    procedure PutElem(var x:TElem);//вставка элемента за указатель
   // procedure GetElem(var x:TElem);//
    procedure LookElem(var x:TElem);//посмотреть элемент
    procedure ChangeElem(var x:TElem);//изменить элемент
    procedure DelElem(var x:TElem);//удалить элемент
    //procedure GetError;
   // procedure MaskError(eror:word);
   // procedure ClearMaskErr;
end;
implementation
//********************************
constructor L1_List.CreateList;//
  begin
    new(buf);
    buf^.next:=buf;
    temp:=buf;
 end;
//****************************************
Destructor L1_List.Destroy_List;//
   begin
     while temp<>NIL do
       begin
         buf:=temp;
         temp:=temp^.next;
         dispose(buf);
       end;
     dispose(temp);
    
   end;
//***************************************
procedure L1_List.InBegin;//в начало 
   begin
     Temp:=buf^.next;
   end;
//****************************************
procedure L1_List.PutElem(var x:TElem);//добавить элемент после указателя
var
 NewEl:Link;
   begin
     new(NewEl);
     NewEl^.data:=x;// записываем в него данные
     {Если список был пустой, то головой списка становится p}
     if buf^.next=NIL then
       begin
         NewEl^.next:= nil;
         Buf:=NewEl;
       end
     else
      begin
        NewEl^.next:=Temp^.next;{ в новом элементе делаем ссылку
на следующий элемент, который был до вставки}
        Temp^.next:=NewEl;{в текущем элементе делаем ссылку на новый}    
      end;
     buf:=Temp^.next;// текущим становится новый элемент
   end;
//********************************************
procedure L1_List.PutTempForvard;//двигаем указатель вправо
  begin
    if temp^.next<>NIL then
       temp:=temp^.next
    else
      begin
      end;
  end;    
//********************************************
procedure L1_List.DelElem(var x:TElem);    
  var
   p,p1:Link;//p1 - предыдущий элемент
   power:boolean;
    begin
      if buf^.next<>nil then p:=buf^.next
      else
        begin
        end;      
      while true do
        begin
          if p^.data = x then
             begin
               power:= true;
               break;
             end
          else
            if p^.next = nil then break;
          p1:= p;
          p:= p^.next;
        end;
      if power then
        begin
          if p = buf then // если удаляется первый элемент
            begin
              p:= buf^.next; // запоминаем ссылку на следующий элемент
              Dispose(buf); // удаляем первый элемент списка
              buf:= p; // головой списка становится p
            end
          else
            begin // если удаляется не первый элемент
              p1^.next:= p^.next; { в предыдущем элементе заменяем
              ссылку на следующий элемент после удаляемого }
              Dispose(p);
              temp:= p1; // текущим делаем предыдущий элемент
            end;
        end
      else
        begin
        end;
    end;    
//********************************************
constructor L1_List.CopyList(var List:L1_List);
  begin
 
  end;
//********************************************
procedure L1_List.ClearList;//очистить текущий список
  var
  tmp:Link;
    begin
      tmp:=temp^.next;
      while tmp <> NIL do
        begin
          buf:=tmp;
          tmp:=tmp^.next;
          Dispose(buf);
        end;
      Dispose(tmp);
    end;
//***********************************************
function L1_List.IsEmptyList:boolean;//пустой ли список
  begin
    if temp^.next = NIL then IsEmptyList:=false
    else IsEmptyList:=true;
  end;
procedure L1_List.ChangeElem(var x:TElem);//изменение элемента за указателем
  begin
    if temp^.next<>nil then temp^.data:=x;
  end;
procedure L1_List.LookElem(var x:TElem);//посмотреть элемент после указателя
  begin
    if temp^.next<>nil then
        begin
        end;
  end;
end.

[volvo877]

Насчет самого списка -реализации уже были в этом разделе, я выкладывал точно - посмотри.

А насчет очереди - зачем тебе 2 списка для каждой очереди? Нужно на каждую очередь один список, метод Put очереди будет добавлять элемент перед начальным (новый элемент будет указывать полем Next на начальный), метод Get - будет получать значение начального элемента списка (и удалять его). Вот тебе и очередь.

[kotmatroskin55]

попробовал написать тестирующую для списка - казалось бы - чего сложного то, но компилятор ругается на методы вот так:
"Error: Only static variables can be used in static methods or outside methods"
вот код тестирующей - там три строчки - засел на создании списка.
опять наверное какая-нибудь мелочь - подскажите пожалуйста

program L1_Test;
uses crt,L1_sp;
var
    x:TElem;
begin
L1_List.CreateList;
readln(x);
L1_List.PutElem(x);
readln;
end.

вот код модуля

unit L1_sp;
interface
uses crt;
type
TElem=integer;
TFile=file of TElem;
Link=^ListElem;
ListElem=record
   Data:TElem;
   next:Link;
end;
L1_List=object
  private
    head:Link;//голова
    Temp:Link;//указатель на следующий элемент
    //err_code:word;    
  public
    constructor CreateList;//создание списка
    constructor CopyList(var List:L1_List);//копирование
    destructor Destroy_List;//удаление с очисткой памяти
    procedure ClearList;//очистка текущуго списка
    function IsEmptyList:boolean;//пустой ли список
    procedure PutTempForvard;//вправо
    procedure InBegin;//в начало
    //function IsTempLast:boolean;
    procedure PutElem(var x:TElem);//вставка элемента за указатель
   // procedure GetElem(var x:TElem);//
    procedure LookElem(var x:TElem);//посмотреть элемент
    procedure ChangeElem(var x:TElem);//изменить элемент
    procedure DelElem(var x:TElem);//удалить элемент
    //procedure GetError;
   // procedure MaskError(eror:word);
   // procedure ClearMaskErr;
end;
implementation
//********************************
constructor L1_List.CreateList;//
  begin
    new(head);//выделяем память
    head^.next:=nil;//направляем указатель в nil
    temp:=head;
 end;
//****************************************
Destructor L1_List.Destroy_List;//
   begin
     while head<>NIL do//пока голова не укаывает в nil
       begin
         temp:=head;
         head:=head^.next;
         dispose(temp);
       end;
     dispose(head);    
   end;
//***************************************
procedure L1_List.InBegin;//в начало 
   begin
     Temp:=head^.next;
   end;
//****************************************
procedure L1_List.PutElem(var x:TElem);//добавить элемент после указателя
var
 NewEl:Link;
   begin
     new(NewEl);//выделяем память под новый элемент
     NewEl^.data:=x;// записываем в него данные
     {Если список был пустой, то головой списка становится p}
     if head^.next=NIL then
       begin
         NewEl^.next:= nil;
         head:=NewEl;
       end
     else
      begin
        NewEl^.next:=Temp^.next;{ в новом элементе делаем ссылку
на следующий элемент, который был до вставки}
        Temp^.next:=NewEl;{в текущем элементе делаем ссылку на новый}    
      end;
     head:=Temp^.next;// текущим становится новый элемент
   end;
//********************************************
procedure L1_List.PutTempForvard;//двигаем указатель вправо
  begin
    if temp^.next<>NIL then
       temp:=temp^.next
    else
      begin
      end;
  end;    
//********************************************
procedure L1_List.DelElem(var x:TElem);    
  var
   p,p1:Link;//p1 - предыдущий элемент
   power:boolean;
    begin
      if temp^.next<>nil then
          begin
            p:=temp^.next;
            power:=true;
          end
      else
        begin
        end;      
      while true do
        begin
          if p^.data = x then
             begin
               power:= true;
               break;
             end
          else
            if p^.next = nil then break;
          p1:= p;
          p:= p^.next;
        end;
      if power then
        begin
          if p = head then // если удаляется первый элемент
            begin
              p:= head^.next; // запоминаем ссылку на следующий элемент
              Dispose(head); // удаляем первый элемент списка
              head:= p; // головой списка становится p
            end
          else
            begin // если удаляется не первый элемент
              p1^.next:= p^.next; { в предыдущем элементе заменяем
              ссылку на следующий элемент после удаляемого }
              Dispose(p);
              temp:= p1; // текущим делаем предыдущий элемент
            end;
        end
      else
        begin
        end;
    end;    
//********************************************
constructor L1_List.CopyList(var List:L1_List);
  begin
 
  end;
//********************************************
procedure L1_List.ClearList;//очистить текущий список
  var
  tmp:Link;
    begin
      tmp:=temp^.next;
      while tmp <> NIL do
        begin
          head:=tmp;
          tmp:=tmp^.next;
          Dispose(head);
        end;
      Dispose(tmp);
    end;
//***********************************************
function L1_List.IsEmptyList:boolean;//пустой ли список
  begin
    if temp^.next = NIL then IsEmptyList:=false
    else IsEmptyList:=true;
  end;
procedure L1_List.ChangeElem(var x:TElem);//изменение элемента за указателем
  begin
    if temp^.next<>nil then temp^.data:=x
    else
      begin
      end;
  end;
procedure L1_List.LookElem(var x:TElem);//посмотреть элемент после указателя
  begin
    if temp^.next<>nil then
        begin
          x:=temp^.data;        
        end;
  end;
end.

Добавлено 04.06.12, 05:08
и еще забыл сказать, что список я решил делать обычный, а не кольцевой

[volvo877]

var
   x:TElem;
   lst : L1_List;
begin
   lst.CreateList; // Создавать надо ЭКЗЕМПЛЯР
   readln(x);
   lst.PutElem(x);
   readln;
end.

[kotmatroskin55]

все понял.от души.

Добавлено 04.06.12, 05:42
все это финиш..............................................................

[kotmatroskin55]

И еще вопросик: как лучше сделать реализацию очереди - написать объект - наследник L1_List?или проще будет отдельный модуль написать?

[volvo877]

Это смотря какое у тебя задание. Можно и наследника в этом же модуле сделать. Можно и наследника в отдельном модуле

[kotmatroskin55]

задание такое:
"Даны две очереди целых чисел, элементы которых упорядочены по неубыванию. Составить из их элементов третью очередь, упорядоченную по невозрастанию"
там был еще компилятор, но я не стал его брать - времени в обрез.

Добавлено 04.06.12, 06:21
Я так понимаю,для выполнения задания еще нужно будет добавить процедуру поиска элемента? А еще не решил как создавать исходные очереди - вручную - с проверкой неубывания, или пусть пользователь забивает ее как хочет, а потом самому сортировать обе очереди, и оттуда уже плясать. Что посоветуешь?

[volvo877]

Цитата kotmatroskin55 @ 04.06.12, 06:14

Я так понимаю,для выполнения задания еще нужно будет добавить процедуру поиска элемента?

Я так понимаю, ты не хочешь читать посты? Нет и не может быть для очереди никакого поиска элементов. Только 2 метода (не включая конструктора/деструктора) - Put и Get. Первый добавляет элемент в хвост очереди, второй - извлекает из головы. Всё. Про все остальные методы (типа поиска, сортировки, получения НЕ головного элемента) забудь. Их не существует.

Вот у тебя и задача: используя только методы Put/Get, крутись как хочешь, но из двух упорядоченных очередей (создавать сразу упорядоченную, либо упорядочивать, используя только эти 2 метода - дело твоё) создай третью, которая тоже упорядочена.

[kotmatroskin55]

написал процедуры для работы с очередью на основе односвязного списка.
вроде вот так как-то:

unit L1_sp;
interface
uses crt;
type
TElem=integer;
TFile=file of TElem;
Link=^ListElem;
ListElem=record
   Data:TElem;
   next:Link;
end;
TQueue = record // структура для реализации очереди
  first: Link; // указатель, указывает на первый элемент очереди
  last: Link; // указатель, указывает на последний элемент очереди
end;
L1_List=object
  private
    head:Link;//голова
    Temp:Link;//указатель на следующий элемент
    //err_code:word;    
  public
    constructor CreateList;//создание списка
    constructor CopyList(var List:L1_List);//копирование
    destructor Destroy_List;//удаление с очисткой памяти
    procedure ClearList;//очистка текущуго списка
    function IsEmptyList:boolean;//пустой ли список
    procedure PutTempForvard;//вправо
    procedure InBegin;//в начало
    //function IsTempLast:boolean;
    procedure PutElem(var x:TElem);//вставка элемента за указатель
    procedure GetElem(var x:TElem);//
    procedure LookElem(var x:TElem);//посмотреть элемент
    procedure ChangeElem(var x:TElem);//изменить элемент
    procedure DelElem(var x:TElem);//удалить элемент
    //procedure GetError;
   // procedure MaskError(eror:word);
   // procedure ClearMaskErr;
end;
Queue=object(L1_List)
  private
    Que:TQueue;
    eprst:boolean;
  public
  procedure Put_Que(var x: TElem);  //добавление элемента в очередь
  procedure Get_Que(var x:TElem);
  procedure Print_Que;
 end;  
//********************************
implementation
//********************************
constructor L1_List.CreateList;//
  begin
    new(head);//выделяем память
    head^.next:=nil;//направляем указатель в nil
    temp:=head;
 end;
//****************************************
Destructor L1_List.Destroy_List;//
   begin
     while head<>NIL do//пока голова не укаывает в nil
       begin
         temp:=head;
         head:=head^.next;
         dispose(temp);
       end;
     dispose(head);    
   end;
//***************************************
procedure L1_List.InBegin;//в начало 
   begin
     Temp:=head^.next;
   end;
//****************************************
procedure L1_List.PutElem(var x:TElem);//добавить элемент после указателя
var
 NewEl:Link;
   begin
     new(NewEl);//выделяем память под новый элемент
     NewEl^.data:=x;// записываем в него данные
     {Если список был пустой, то головой списка становится p}
     if head^.next=NIL then
       begin
         NewEl^.next:= nil;
         head:=NewEl;
       end
     else
      begin
        NewEl^.next:=Temp^.next;{ в новом элементе делаем ссылку
на следующий элемент, который был до вставки}
        Temp^.next:=NewEl;{в текущем элементе делаем ссылку на новый}    
      end;
     head:=Temp^.next;// текущим становится новый элемент
   end;
//********************************************
procedure L1_List.PutTempForvard;//двигаем указатель вправо
  begin
    if temp^.next<>NIL then
       temp:=temp^.next
    else
      begin
      end;
  end;    
//********************************************
procedure L1_List.DelElem(var x:TElem);    
  var
   p,p1:Link;//p1 - предыдущий элемент
   power:boolean;
    begin
      if temp^.next<>nil then
          begin
            p:=temp^.next;
            power:=true;
          end
      else
        begin
        end;      
      while true do
        begin
          if p^.data = x then
             begin
               power:= true;
               break;
             end
          else
            if p^.next = nil then break
            else
              begin
                p1:= p;
                p:= p^.next;
              end;
        end;
      if power then
        begin
          if p = head then // если удаляется первый элемент
            begin
              p:= head^.next; // запоминаем ссылку на следующий элемент
              Dispose(head); // удаляем первый элемент списка
              head:= p; // головой списка становится p
            end
          else
            begin // если удаляется не первый элемент
              p1^.next:= p^.next; { в предыдущем элементе заменяем
              ссылку на следующий элемент после удаляемого }
              Dispose(p);
              temp:= p1; // текущим делаем предыдущий элемент
            end;
        end
      else
        begin
        end;
    end;    
//********************************************
constructor L1_List.CopyList(var List:L1_List);
  begin
 
  end;
//********************************************
procedure L1_List.ClearList;//очистить текущий список
  var
  tmp:Link;
    begin
      tmp:=temp^.next;
      while tmp <> NIL do
        begin
          head:=tmp;
          tmp:=tmp^.next;
          Dispose(head);
        end;
      Dispose(tmp);
    end;
//***********************************************
function L1_List.IsEmptyList:boolean;//пустой ли список
  begin
    if temp^.next = NIL then IsEmptyList:=false
    else IsEmptyList:=true;
  end;
procedure L1_List.ChangeElem(var x:TElem);//изменение элемента за указателем
  begin
    if temp^.next<>nil then temp^.data:=x
    else
      begin
      end;
  end;
procedure L1_List.LookElem(var x:TElem);//посмотреть элемент после указателя
  begin
    if temp^.next<>nil then
        begin
          x:=temp^.data;        
        end;
  end;
procedure L1_List.GetElem(var x:TElem);    
  begin
    if temp^.next<>nil then
        begin
          x:=temp^.data;        
          dispose(temp);
        end
    else
      begin
      end;
  end;
procedure Queue.Put_Que(var x: TElem);  //добавление элемента в очередь
var
  pont:Link;//временный указатель
  begin
    if Que.last=nil then{Если очередь пуста, то указатели на первый и последний элемент будут совпадать}
      begin
        Que.last:= New(Link);
        Que.first:= Que.last; // Приравниваем указатели
        Que.last^.data:= x;//записываем данные
        Que.last^.next:= nil; // Следующий элемент пока пустой    
      end
    else
      begin
        pont:=New(Link);
        pont^.data:=x;
        pont^.next:=nil;
        Que.last^.next:=pont;//ссылка на следующий элемент
        Que.last:=pont;//сдвигаем указатель на последний элемент
      end;
  end;
procedure Queue.Get_Que(var x:TElem);//взять элемент из очереди
  var
    pont:Link;
    begin
      if Que.first=nil then
        begin
          eprst:=true;
        end
      else
        begin
          x:=Que.first^.data;//первывй элемент очереди
          pont:=Que.first;//запомним ссылку
          Que.first:=Que.first^.next;//переход на следующий элемент
          dispose(pont);
        end
    end;
procedure Queue.Print_Que;
  var
    pont:Link;
    begin
      pont:=Que.first;//берем первый элемент очереди,в цикле проходим все элементы очереди и печатаем их
      while pont<>nil do
        begin
          write(pont^.data,' ');
          pont:=pont^.next;
        end;
      writeln;
    end;
end.

Добавлено 05.06.12, 06:49
только теперь не могу сообразить с какого боку подойти к решению задачи. Получается для начала нужно создать две очереди, выделить память под третью, а затем с помощью методов Put и Get каким-то макаром заполнить третью. Вопрос: позволит ли мне паскаль хранить в памяти несколько очередей?

[Vesper]

Цитата kotmatroskin55 @ 05.06.12, 06:44

Вопрос: позволит ли мне паскаль хранить в памяти несколько очередей?

В динамической памяти может поместиться довольно много объектов для такой задачи. Считай, что позволит, и из этого пиши дальше. На всякий случай можешь посмотреть результат функции MemAvail до и во время выполнения программы, чтобы оценить максимальную длину очередей.

[kotmatroskin55]

и еще вопросик:как с помощью методов для списка создавать очередь, если они идут как бы сами по себе,т.е. от методов L1_List не особо зависят. чего-то я не совсем в теме-литературы море перекопал,но толку пока не очень.

[Vesper]

Если тебе позарез нужны методы L1_List, нужно использовать Que как объект, одним из элементов которого является список как структура данных. Тогда метод Put будет реализован через AddElem(хвост) и смещение хвоста, а Get (как из начала очереди) через удаление головы.

[volvo877]

Цитата kotmatroskin55 @ 05.06.12, 06:44

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

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

// Модуль:
// (недостающие методы реализуешь сам, они для решения текущей задачи не важны)
unit L;
 
interface
 
type
   TItem = Integer;
 
   Link = ^Node;
   Node =
   record
      data : TItem;
      next : Link;
   end;
 
   TList =
   object
   protected
      head, tail : Link;
 
   public
      constructor Create;
      destructor Destroy; virtual;
 
      procedure Append (X : TItem); // to the end
      procedure Insert (X : TItem); // to the beginning
      procedure InsertAfter (p : Link; X : TItem); // insert X after p^
 
      function Find (x : TItem) : Link;
      procedure RemoveAt (p : Link);
      function IsEmpty : boolean;
 
      procedure Print;
      // ...
 
   end;
 
   TQueue =
   object (TList)
      constructor Create;
      destructor Destroy; virtual;
 
      procedure Put (X : TItem);
      function Get : TItem;
   end;
 
implementation
 
constructor TList.Create;
begin
   head := nil;
   tail := nil;
end;
destructor TList.Destroy;
var p : Link;
begin
   while head <> nil do
   begin
      p := head;
      head := head^.next;
      dispose(p);
   end;
end;
 
procedure TList.Append (X : TItem); // to the end
var p : Link;
begin
   new(p);
   p^.next := nil;
   p^.data := X;
 
   if IsEmpty then
      head := p
   else
      tail^.next := p;
 
   tail := p;
end;
 
procedure TList.Insert (X : TItem); // to the beginning
var p : Link;
begin
   new(p);
   p^.next := head;
   p^.data := X;
 
   if IsEmpty then
      tail := p;
   head := p;
end;
procedure TList.InsertAfter (p : Link; X : TItem); // insert X after p^
begin
   //
end;
 
function TList.Find (x : TItem) : Link;
begin
   //
end;
function TList.IsEmpty : boolean;
begin
   IsEmpty := head = nil;
end;
 
procedure TList.RemoveAt (p : Link);
var pp : Link;
begin
   if p = head then
   begin
      pp := head;
      head := head^.next;
      dispose(pp);
      if head = nil then
         tail := nil;
   end
 
   else
   begin
      pp := head;
      while (pp^.next <> nil) and (pp^.next <> p) do
         pp := pp^.next;
      if Assigned (pp) then // found
      begin
         pp^.next := p^.next;
         dispose(p);
      end;
   end;
end;
 
procedure TList.Print;
var p : Link;
begin
   p := head;
   write('<');
   while p <> nil do
   begin
      write (p^.data:3);
      p := p^.next;
   end;
   writeln('>');
end;
 
constructor TQueue.Create;
begin
   inherited;
end;
destructor TQueue.Destroy;
begin
   inherited;
end;
 
procedure TQueue.Put (X : TItem);
begin
   Append (X);
end;
function TQueue.Get : TItem;
var T : Link;
begin
   if IsEmpty then WriteLn('<>')
   else
   begin
      Get := head^.data;
      RemoveAt (head);
   end;
end;
 
end.

// тестовая программа:
uses crt, L;
var
   i : Integer;
   x : TItem;
   q : TQueue;
   ls : tlist;
begin
   ls.Create;
   for i := 1 to 10 do
   begin
      ls.Insert(2 * i);
   end;
   ls.Print;
   ls.Destroy;
 
   q.Create;
   for i := 1 to 10 do
   begin
      q.Put(i);
   end;
 
   q.Print;
   writeln(q.Get);
   writeln(q.Get);
   writeln(q.Get);
 
   q.Print;
   q.Destroy;
   readln;
end.

[kotmatroskin55]

понял,благодарю. Кстати,мне сказали,что наследование использовать нельзя: "Вы еще до этого не доросли". Сейчас попробую разобраться.