Форум по Delphi программированию

Delphi Sources



Вернуться   Форум по Delphi программированию > Все о Delphi > [ "Начинающим" ]
Ник
Пароль
Регистрация <<         Правила форума         >> FAQ Пользователи Календарь Поиск Сообщения за сегодня Все разделы прочитаны

Ответ
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 22.10.2017, 17:08
doc98 doc98 вне форума
Прохожий
 
Регистрация: 22.10.2017
Сообщения: 1
Версия Delphi: Delphi 7
Репутация: 10
По умолчанию Односвязный список

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

Пример:
4->1->5->4->3->7
Итог:
4->5->4->7
Ответить с цитированием
  #2  
Старый 25.10.2017, 00:35
lmikle lmikle вне форума
Модератор
 
Регистрация: 17.04.2008
Сообщения: 8,004
Версия Delphi: 7, XE3, 10.2
Репутация: 49089
По умолчанию

Ну, как то так:
Код:
type
  PLinkedList = ^TLinkedList;
  TLinkedList = record
    Data : Integer;
    Next : PLinkedList;
  end;
  
function DeleteItemsLessThanNext(AList : PLinkedList) : PLinkedList;
var
  tmp : PLinedList;
begin
  Result := AList;
  If Result = Nil Then Exit; // List is empty
  While AList.Next <> Nil Do
    Begin
      If AList.Data < AList.Next.Data // if current is less than next - delete current
        Then
          Begin
            // As soon as we delete current item - we do not need to switch to next item
            If Result = AList 
              Then
                Begin
                  // Delete 1st item, just repoint pointer to the head
                  tmp := AList;
                  AList := AList.Next;
                  Result := AList;
                  Dispose(tmp);
                End
              Else
                Begin
                  // Delete current item that is not head of the list. Use the trick:
                  // instead of deleting current element - copy next then delete next
                  tmp := AList.Next;
                  AList.Data := AList.Next.Data;
                  AList.Next := AList.Next.Next;
                  Dispose(tmp);
                End;
          End
        Else
          AList := AList.Next; // current item is greater or equal to the next - just switch to next item
    End;
end;

Не проверял, но должно работать, если нигде не накосячил.

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

Последний раз редактировалось lmikle, 25.10.2017 в 00:37.
Ответить с цитированием
  #3  
Старый 25.10.2017, 05:04
lmikle lmikle вне форума
Модератор
 
Регистрация: 17.04.2008
Сообщения: 8,004
Версия Delphi: 7, XE3, 10.2
Репутация: 49089
По умолчанию

Вот, пришел домой, накидал еще немного кода и проверил - работает:
Код:
unit Unit2;

interface

uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;

type
  PLinkedList = ^TLinkedList;
  TLinkedList = record
    Data : Integer;
    Next : PLinkedList;
  end;

  TForm2 = class(TForm)
    Memo1: TMemo;
    Memo2: TMemo;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
    function DeleteItemsLessThanNext(AList : PLinkedList) : PLinkedList;
    procedure PrintList(AList : PLinkedList; AMemo : TMemo);
  end;

var
  Form2: TForm2;

implementation

{$R *.dfm}
procedure TForm2.PrintList(AList : PLinkedList; AMemo : TMemo);
begin
  AMemo.Lines.Clear;
  While AList <> Nil Do
    Begin
      AMemo.Lines.Add(InttoStr(AList.Data));
      AList := AList.Next;
    End;
end;

function TForm2.DeleteItemsLessThanNext(AList : PLinkedList) : PLinkedList;
var
  tmp : PLinkedList;
begin
  Result := AList;
  If Result = Nil Then Exit; // List is empty
  While AList.Next <> Nil Do
    Begin
      If AList.Data < AList.Next.Data // if current is less than next - delete current
        Then
          Begin
            // As soon as we delete current item - we do not need to switch to next item
            If Result = AList
              Then
                Begin
                  // Delete 1st item, just repoint pointer to the head
                  tmp := AList;
                  AList := AList.Next;
                  Result := AList;
                  Dispose(tmp);
                End
              Else
                Begin
                  // Delete current item that is not head of the list. Use the trick:
                  // instead of deleting current element - copy next then delete next
                  tmp := AList.Next;
                  AList.Data := AList.Next.Data;
                  AList.Next := AList.Next.Next;
                  Dispose(tmp);
                End;
          End
        Else
          AList := AList.Next; // current item is greater or equal to the next - just switch to next item
    End;
end;

// Test
procedure TForm2.Button1Click(Sender: TObject);
const
  A : Array [0..5] Of Integer = (4,1,5,4,3,7);
var
  tmp : PLinkedList;
  AList : PLinkedList;
  I : Integer;
begin
  // Create the list
  AList := Nil;
  For I := High(A) DownTo Low(A) Do
    Begin
      New(tmp);
      tmp.Data := A[i];
      tmp.Next := AList;
      AList := tmp;
    End;
  PrintList(AList,Memo1);

  // Run the job
  AList := DeleteItemsLessThanNext(AList);

  // Print result
  PrintList(AList,Memo2);
end;


end.
Ответить с цитированием
Ответ


Delphi Sources

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра
Комбинированный вид Комбинированный вид

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB-коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход


Часовой пояс GMT +3, время: 00:11.


 

Сайт

Форум

FAQ

RSS лента

Прочее

 

Copyright © Форум "Delphi Sources" by BrokenByte Software, 2004-2023

ВКонтакте   Facebook   Twitter