|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
|
Опции темы | Поиск в этой теме | Опции просмотра |
#1
|
|||
|
|||
Односвязный список
В неупорядоченном списке удалить те элементы, для которых выполняется условие: значение элемента меньше значения следующего за ним элемента.
Пример: 4->1->5->4->3->7 Итог: 4->5->4->7 |
#2
|
|||
|
|||
Ну, как то так:
Код:
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
|
|||
|
|||
Вот, пришел домой, накидал еще немного кода и проверил - работает:
Код:
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. |