Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [Delphi] Кольцевой односвязный список


Автор: Killer79 18.4.2008, 00:56
Помогите пожалуйста с такой задачкой:
"Графическое моделирование операций в кольцевом односвязном списке"

Задается количество элементов кольцевого односвязного списка (КОС) - до 10-ти элементов. Прорисовывается логическая структура КОС с единственным информационным полем целого типа - полем ключа. Показываются неповторяющиеся значения ключей на логической структуре; эти значения генерируются программным датчиком из диапазона [1, 99].
Обеспечивается возможность выбора текущей операции: передвижение по списку с изменением текущего элемента, вставка, дополнение, удаление, сортировка. Процесс выполнения выбранной операции отображается на логической структуре КОС по шагам.

Автор: Killer79 23.4.2008, 19:31
Люди помогите плииззз.... в решении данной проблемы, а то сроки поджимают.

Автор: Killer79 4.5.2008, 12:54
Вот сел написал сам, но не могу разобраться с сортировкой, не хочет работать. Помогите пожалуйста!!!!


Код

// описание структуры кольцевого односвязного списка ///////////////////////////
type
  TList = ^List;

  List = record
    Str: integer;
    Next: TList; // следующий элемент списка
end;

var
  head: TList; // начало списка
  curr: TList;
  i: integer;

Procedure InsertRecord( Var head: TList; pItem: TList );
Var
  curr, pre, temp: TList;
Begin
      If head = Nil Then Begin
        head := pItem;
        head^.next := Nil
      End
      Else Begin
      curr := head;
      pre := Nil;
      end;
        While curr^.Str < pItem^.Str Do
          If curr^.next = Nil Then Begin
              curr^.next := pItem;
              pItem^.next := Nil;
              Exit;
          End
          Else Begin
            pre:= curr;
            If pre = Nil Then Begin
                pItem^.next := head;
                head := pItem;
            End
            Else Begin
              pItem^.next := pre;
              pre^.next := pItem;
            End;
          End;
        End;


// процедура скрытия картинок и label //////////////////////////////////////////
procedure TForm1.ImLabFal ;
begin
    Image1.Visible:=false;
    Image2.Visible:=false;
    Image3.Visible:=false;
    Image4.Visible:=false;
    Image5.Visible:=false;
    Image6.Visible:=false;
    Image7.Visible:=false;
    Image8.Visible:=false;
    Image9.Visible:=false;
    Image10.Visible:=false;
    Label1.Visible:=false;
    Label2.Visible:=false;
    Label3.Visible:=false;
    Label4.Visible:=false;
    Label5.Visible:=false;
    Label6.Visible:=false;
    Label7.Visible:=false;
    Label8.Visible:=false;
    Label9.Visible:=false;
    Label10.Visible:=false;
    i:=0;
    curr:=head;
    while curr<>NIL do begin
      i:=i+1;
    case i of
    1: Label1.Caption:=IntToStr(curr^.Str);
    2: Label2.Caption:=IntToStr(curr^.Str);
    3: Label3.Caption:=IntToStr(curr^.Str);
    4: Label4.Caption:=IntToStr(curr^.Str);
    5: Label5.Caption:=IntToStr(curr^.Str);
    6: Label6.Caption:=IntToStr(curr^.Str);
    7: Label7.Caption:=IntToStr(curr^.Str);
    8: Label8.Caption:=IntToStr(curr^.Str);
    9: Label9.Caption:=IntToStr(curr^.Str);
    10:Label10.Caption:=IntToStr(curr^.Str);
    end;
    curr:=curr^.Next;
    end;
end;

// функция создания элементов списка/////////////////////////////////////////
procedure TForm1.RecNSpisok;
var
  n:integer;  //  кол-во вставляемых элементов в список
  tr:bool;    // для проверки введены ли данные
begin
  randomize;
  try
    n:= StrToInt(Form2.Edit1.Text);
    tr:=true;
  except
    tr:=false;
  end;
  if (tr) then begin
    i:=0;
    while i<n do begin
      new(curr);
      curr^.Next:=head;
      head:=curr;
      curr.Str:=Random(99)+1;
      i:=i+1;
    case i of
    1: Label1.Caption:=IntToStr(curr.Str);
    2: Label2.Caption:=IntToStr(curr.Str);
    3: Label3.Caption:=IntToStr(curr.Str);
    4: Label4.Caption:=IntToStr(curr.Str);
    5: Label5.Caption:=IntToStr(curr.Str);
    6: Label6.Caption:=IntToStr(curr.Str);
    7: Label7.Caption:=IntToStr(curr.Str);
    8: Label8.Caption:=IntToStr(curr.Str);
    9: Label9.Caption:=IntToStr(curr.Str);
    10:Label10.Caption:=IntToStr(curr.Str);
    end;
    end;
    end;
end;

// функция добавления элемента в список/////////////////////////////////////////
procedure TForm1.RecSpisok;
begin
  ImLabFal;
  new(curr); // создание нового элемента списка
  curr^.Str:= StrToInt(Form3.Edit1.Text);
  curr^.Next:= head;
  head:= curr;
end;

// функция удаления элемента из списка//////////////////////////////////////////
procedure TForm1.DelSpisok;
var
  pre:TList; // предыдущий относительно curr
  n:integer; // элемент который необходимо удалить
begin
  if head = NIL then
    begin
      MessageDlg('Список пустой!', mtError, [mbOk],0);
      Exit;
    end;
  n:=StrToInt(Form4.Edit1.Text);
  curr:=head;
  i:=1;
  while i<n do begin
    pre:=curr;
    curr:=curr^.Next;
    i:=i+1;
  end;
    pre^.Next:=curr.Next;
    Dispose (curr);
    ImLabFal;
end;

// функция сортировки элементов списка//////////////////////////////////////////
procedure TForm1.SortSpisok;
var
  pre:  TList; // предыдущий относительно curr
  temp: TList; // временный элемент списка
begin
  if head=NIL then
    exit;
  curr:=head;
  while (curr<>NIL) do begin
    temp:=curr;
    curr:=curr^.Next;
    InsertRecord( pre, temp );
  end;
    head:=pre;
    ImLabFal;
end;

// процедура для формирования списка////////////////////////////////////////////
procedure TForm1.BitBtn3Click(Sender: TObject);
begin
  Form2.ShowModal;
end;

// процедура для вставки нового элемента////////////////////////////////////////
procedure TForm1.BitBtn4Click(Sender: TObject);
begin
  Form3.ShowModal;
end;

// процедура для удаления элемента из списка////////////////////////////////////
procedure TForm1.BitBtn5Click(Sender: TObject);
begin
  Form4.ShowModal;
end;

// процедура для вывода на экран элементов списка///////////////////////////////
procedure TForm1.BitBtn2Click(Sender: TObject);
begin
    ImLabFal;
  i:=0;
  curr:=head;
  if head=NIL then
    curr.Next:=NIL;
  while curr<>NIL do begin
    i:=i+1;
    curr:=curr^.Next;
    case i of
    1: Image1.Visible:=true;
    2: Image2.Visible:=true;
    3: Image3.Visible:=true;
    4: Image4.Visible:=true;
    5: Image5.Visible:=true;
    6: Image6.Visible:=true;
    7: Image7.Visible:=true;
    8: Image8.Visible:=true;
    9: Image9.Visible:=true;
    10:Image10.Visible:=true;
    end;
    case i of
    1: Label1.Visible:=true;
    2: Label2.Visible:=true;
    3: Label3.Visible:=true;
    4: Label4.Visible:=true;
    5: Label5.Visible:=true;
    6: Label6.Visible:=true;
    7: Label7.Visible:=true;
    8: Label8.Visible:=true;
    9: Label9.Visible:=true;
    10:Label10.Visible:=true;
    end;
  end;
end;

// кнопка сортировки списка ////////////////////////////////////////////////
procedure TForm1.BitBtn6Click(Sender: TObject);
begin
  SortSpisok;
end;

end.

Автор: Killer79 7.5.2008, 12:04
Такое ощущение что на форуме нету специалистов по Delphi, и не кому помочь.

Автор: Wedafl 12.5.2008, 13:45
1. Код организован очень неудобно, лучше весь список загнать в класс.
2. В таком случае проще всего использовать пузырьковую сортировку. Примеров в том числе и на паскале навалом, правда везде сортируется массив, но переделать под список несложно.

Будет выглядеть примерно так:
Код

procedure TForm1.SortSpisok;
var
  pre:  TList; // предыдущий относительно curr
  temp: TList; // временный элемент списка
  endSort: Boolean;
begin
  if Head = nil then
    Exit;
  curr := Head^.Next;
  pre := Head;
  endSort := False;
  while not endSort do
  begin
    endSort := True;
    while (curr <> Head) do
    begin
      if curr^.Str > curr^.next^.Str then //если следующий узел меньше то меняем узлы местами
      begin
        temp := curr^.next;
        pre^.Next := temp;
        curr^.Next := temp^.Next;
        temp^.Next := curr;
        pre := temp;
        endSort := False;
      end
      else
      begin
        pre := curr;
        curr := curr^.Next;
      end;
    end;
  end;
  ImLabFal;
end;

В голове должен оказаться самый большой элемент.

Автор: Killer79 13.5.2008, 19:54
Большое Спасибо за ответ, но я уже нашел другой алгоритм сортировки - cортировка выборкой.

Код

function Sort (head: TList) : TList;
var
  newh, max, pre, pmax, curr : TList;
begin
    newh:=nil;         { выходной список - пустой }
      while head<>nil do begin{ цикл, пока не опустеет входной список }
          max:=head;
          pre:=head; { нач.максимум - 1-й эл-т }
          curr:=head^.next;     { поиск максимума во входном списке }
            while curr<>nil do begin
                if curr^.Str>max^.Str then begin { запоминается адрес максимума и адрес предыдущего эл-та }
                  max:=curr;
                  pmax:=pre;
                end;
                pre:=curr;
                curr:=curr^.next; { движение по списку }
            end;        { исключение максимума из входного списка }
            if max=head then
              head:=head^.next
            else
              pmax^.next:=max^.next;{ вставка в начало выходного списка }
              max^.next:=newh;
              newh:=max;
      end;
      curr:= newh;
end;

Автор: Killer79 21.5.2008, 11:52
Объясните плиззз.... что тут нада делать.

СТАТИЧЕСКИЕ ДАННЫЕ И СТРУКТУРЫ

Назначение данного или структуры,  объем памяти для данного и структуры. Объем памяти для глобальных и локальных данных  каждой подпрограммы. Анализ размещения данных в памяти с указанием их адресов (для последовательных структур указать адреса начального и конечного элементов).


Код

// описание структуры кольцевого односвязного списка ///////////////////////////
type
  TList = ^List;

  List = record
    Str: integer;
    Next: TList; // следующий элемент списка
end;

var
  head: TList; // начало списка
  curr: TList;
  i: integer;

Procedure InsertRecord( Var head: TList; pItem: TList );
Var
  curr, pre, temp: TList;
Begin
      If head = Nil Then Begin
        head := pItem;
        head^.next := Nil
      End
      Else Begin
      curr := head;
      pre := Nil;
      end;
        While curr^.Str < pItem^.Str Do
          If curr^.next = Nil Then Begin
              curr^.next := pItem;
              pItem^.next := Nil;
              Exit;
          End
          Else Begin
            pre:= curr;
            If pre = Nil Then Begin
                pItem^.next := head;
                head := pItem;
            End
            Else Begin
              pItem^.next := pre;
              pre^.next := pItem;
            End;
          End;
        End;


// процедура скрытия картинок и label //////////////////////////////////////////
procedure TForm1.ImLabFal ;
begin
    Image1.Visible:=false;
    Image2.Visible:=false;
    Image3.Visible:=false;
    Image4.Visible:=false;
    Image5.Visible:=false;
    Image6.Visible:=false;
    Image7.Visible:=false;
    Image8.Visible:=false;
    Image9.Visible:=false;
    Image10.Visible:=false;
    Label1.Visible:=false;
    Label2.Visible:=false;
    Label3.Visible:=false;
    Label4.Visible:=false;
    Label5.Visible:=false;
    Label6.Visible:=false;
    Label7.Visible:=false;
    Label8.Visible:=false;
    Label9.Visible:=false;
    Label10.Visible:=false;
    i:=0;
    curr:=head;
    while curr<>NIL do begin
      i:=i+1;
    case i of
    1: Label1.Caption:=IntToStr(curr^.Str);
    2: Label2.Caption:=IntToStr(curr^.Str);
    3: Label3.Caption:=IntToStr(curr^.Str);
    4: Label4.Caption:=IntToStr(curr^.Str);
    5: Label5.Caption:=IntToStr(curr^.Str);
    6: Label6.Caption:=IntToStr(curr^.Str);
    7: Label7.Caption:=IntToStr(curr^.Str);
    8: Label8.Caption:=IntToStr(curr^.Str);
    9: Label9.Caption:=IntToStr(curr^.Str);
    10:Label10.Caption:=IntToStr(curr^.Str);
    end;
    curr:=curr^.Next;
    end;
end;

// функция создания элементов списка/////////////////////////////////////////
procedure TForm1.RecNSpisok;
var
  n:integer;  //  кол-во вставляемых элементов в список
  tr:bool;    // для проверки введены ли данные
begin
  randomize;
  try
    n:= StrToInt(Form2.Edit1.Text);
    tr:=true;
  except
    tr:=false;
  end;
  if (tr) then begin
    i:=0;
    while i<n do begin
      new(curr);
      curr^.Next:=head;
      head:=curr;
      curr.Str:=Random(99)+1;
      i:=i+1;
    case i of
    1: Label1.Caption:=IntToStr(curr.Str);
    2: Label2.Caption:=IntToStr(curr.Str);
    3: Label3.Caption:=IntToStr(curr.Str);
    4: Label4.Caption:=IntToStr(curr.Str);
    5: Label5.Caption:=IntToStr(curr.Str);
    6: Label6.Caption:=IntToStr(curr.Str);
    7: Label7.Caption:=IntToStr(curr.Str);
    8: Label8.Caption:=IntToStr(curr.Str);
    9: Label9.Caption:=IntToStr(curr.Str);
    10:Label10.Caption:=IntToStr(curr.Str);
    end;
    end;
    end;
end;

// функция добавления элемента в список/////////////////////////////////////////
procedure TForm1.RecSpisok;
begin
  ImLabFal;
  new(curr); // создание нового элемента списка
  curr^.Str:= StrToInt(Form3.Edit1.Text);
  curr^.Next:= head;
  head:= curr;
end;

// функция удаления элемента из списка//////////////////////////////////////////
procedure TForm1.DelSpisok;
var
  pre:TList; // предыдущий относительно curr
  n:integer; // элемент который необходимо удалить
begin
  if head = NIL then
    begin
      MessageDlg('Список пустой!', mtError, [mbOk],0);
      Exit;
    end;
  n:=StrToInt(Form4.Edit1.Text);
  curr:=head;
  i:=1;
  while i<n do begin
    pre:=curr;
    curr:=curr^.Next;
    i:=i+1;
  end;
    pre^.Next:=curr.Next;
    Dispose (curr);
    ImLabFal;
end;

// функция сортировки элементов списка//////////////////////////////////////////
procedure TForm1.SortSpisok;
var
  pre:  TList; // предыдущий относительно curr
  temp: TList; // временный элемент списка
begin
  if head=NIL then
    exit;
  curr:=head;
  while (curr<>NIL) do begin
    temp:=curr;
    curr:=curr^.Next;
    InsertRecord( pre, temp );
  end;
    head:=pre;
    ImLabFal;
end;

// процедура для формирования списка////////////////////////////////////////////
procedure TForm1.BitBtn3Click(Sender: TObject);
begin
  Form2.ShowModal;
end;

// процедура для вставки нового элемента////////////////////////////////////////
procedure TForm1.BitBtn4Click(Sender: TObject);
begin
  Form3.ShowModal;
end;

// процедура для удаления элемента из списка////////////////////////////////////
procedure TForm1.BitBtn5Click(Sender: TObject);
begin
  Form4.ShowModal;
end;

// процедура для вывода на экран элементов списка///////////////////////////////
procedure TForm1.BitBtn2Click(Sender: TObject);
begin
    ImLabFal;
  i:=0;
  curr:=head;
  if head=NIL then
    curr.Next:=NIL;
  while curr<>NIL do begin
    i:=i+1;
    curr:=curr^.Next;
    case i of
    1: Image1.Visible:=true;
    2: Image2.Visible:=true;
    3: Image3.Visible:=true;
    4: Image4.Visible:=true;
    5: Image5.Visible:=true;
    6: Image6.Visible:=true;
    7: Image7.Visible:=true;
    8: Image8.Visible:=true;
    9: Image9.Visible:=true;
    10:Image10.Visible:=true;
    end;
    case i of
    1: Label1.Visible:=true;
    2: Label2.Visible:=true;
    3: Label3.Visible:=true;
    4: Label4.Visible:=true;
    5: Label5.Visible:=true;
    6: Label6.Visible:=true;
    7: Label7.Visible:=true;
    8: Label8.Visible:=true;
    9: Label9.Visible:=true;
    10:Label10.Visible:=true;
    end;
  end;
end;

// кнопка сортировки списка ////////////////////////////////////////////////
procedure TForm1.BitBtn6Click(Sender: TObject);
begin
  SortSpisok;
end;

end.

Автор: Killer79 22.5.2008, 21:15
up

Автор: Wedafl 24.5.2008, 00:38
Не совсем понятно как вам надо делать задание, это будет что то вроде защиты перед сдачей проги или надо делать подробную записку к программе?  Вообще без привязке к конкретному курсу лекций, где будут даны все определения, задача выглядит очень расплывчатой.

Лично я могу проинтерпретировать "СТАТИЧЕСКИЕ ДАННЫЕ" только как глобальные переменные.

1. "Назначение данного или структуры" -- если вы уж смогли список сделать то наверное понимаете для чего нужны те или иные переменные и типы. 
2. "объем памяти для данного и структуры" что подразумевается тут я могу только догадываться, например  объем памяти (ОП) для данного это размер занимаемый в памяти самыми данными элемента структуры, в данном случае это Str: integer;, а ОП для элемента структуры это память для данного плюс память под служебные данные(указатели). Понятно что узнать обьем памяти мы можем только во время работы т.к он зависит от количества элементов.
Код

SizeOf(Head.Str); //ОП данных элемента
SizeOf(Head^); //ОП элемента 
 
3. "Объем памяти для глобальных и локальных данных  каждой подпрограммы" -- ИМХО Локальные данные это те данные которые не существовали до входа в подпрограмму и не будут существовать после выхода из нее, все остальные данные используемые подпрограммой можно считать глобальными.
4.  Адрес элемента у вас один это head, адреса я обычно вывожу так
Код

  Label.caption := IntToStr(Integer(Head));

Автор: Killer79 24.5.2008, 20:38
Цитата

СТАТИЧЕСКИЕ ДАННЫЕ И СТРУКТУРЫ

Назначение данного или структуры,  объем памяти для данного и структуры. Объем памяти для глобальных и локальных данных  каждой подпрограммы. Анализ размещения данных в памяти с указанием их адресов (для последовательных структур указать адреса начального и конечного элементов).


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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)