Карта сайта Kansoftware
НОВОСТИУСЛУГИРЕШЕНИЯКОНТАКТЫ
KANSoftWare

Сортировка связанного списка

Delphi , Базы данных , Сортировка и Фильтр

Сортировка связанного списка

Автор: Peter Below


program noname;

type
  PData = ^TData;
  TData = record
    next: PData;
    Name: string[40];
    { ...другие поля данных }
  end;

var
  root: PData; { это указатель на первую запись в связанном списке }

procedure InsertRecord(var root: PData; pItem: PData);
(* вставляем запись, на которую указывает pItem в список начиная
с root и с требуемым порядком сортировки *)
var
  pWalk, pLast: PData;
begin
  if root = nil then
  begin
    (* новый список все еще пуст, просто делаем запись,
    чтобы добавить root к новому списку *)
    root := pItem;
    root^.next := nil
  end { If }
  else
  begin
    (* проходимся по списку и сравниваем каждую запись с одной
    включаемой. Нам необходимо помнить последнюю запись,
    которую мы проверили, причина этого станет ясна немного позже. *)
    pWalk := root;
    pLast := nil;

    (* условие в следующем цикле While определяет порядок сортировки!
    Это идеальное место для передачи вызова функции сравнения,
    которой вы передаете дополнительный параметр InsertRecord для
    осуществления общей сортировки, например:

    While CompareItems( pWalk, pItem ) < 0 Do Begin
    where
    Procedure InsertRecord( Var list: PData; CompareItems: TCompareItems );
    and
    Type TCompareItems = Function( p1,p2:PData ): Integer;
    and a sample compare function:
    Function CompareName( p1,p2:PData ): Integer;
    Begin
    If p1^.Name < p2^.Name Then
    CompareName := -1
    Else
    If p1^.Name > p2^.Name Then
    CompareName := 1
    Else
    CompareName := 0;
    End;
    *)
    while pWalk^.Name < pItem^.Name do
      if pWalk^.next = nil then
      begin
        (* мы обнаружили конец списка, поэтому добавляем
        новую запись и выходим из процедуры *)
        pWalk^.next := pItem;
        pItem^.next := nil;
        Exit;
      end { If }
      else
      begin
        (* следующая запись, пожалуйста, но помните,
        что одну мы только что проверили! *)
        pLast := pWalk;

        (* если мы заканчиваем в этом месте, то значит мы нашли
        в списке запись, которая >= одной включенной. Поэтому
        вставьте ее перед записью, на которую в настоящий момент
        указывает pWalk, которая расположена после pLast. *)
        if pLast = nil then
        begin
          (* Упс, мы вывалились из цикла While на самой первой итерации!
          Новая запись должна располагаться в верхней части списка,
          поэтому она становится новым корнем (root)! *)
          pItem^.next := root;
          root := pItem;
        end { If }
        else
        begin
          (* вставляем pItem между pLast и pWalk *)
          pItem^.next := pWalk;
          pLast^.next := pItem;
        end; { Else }
        (* мы сделали это! *)
      end; { Else }
  end; { InsertRecord }

procedure SortbyName(var list: PData);
var

  newtree, temp, stump: PData;
begin { SortByName }

  (* немедленно выходим, если сортировать нечего *)
  if list = nil then
    Exit;
  (* в
  newtree := Nil;

  (********
  Сортируем, просто беря записи из оригинального списка и вставляя их
  в новый, по пути "перехватывая" для определения правильной позиции в
  новом дереве. Stump используется для компенсации различий списков.
  temp используется для указания на запись, перемещаемую из одного
  списка в другой.
  ********)
  stump := list;
  while stump <> nil do
  begin
    (* временная ссылка на перемещаемую запись *)
    temp := stump;
    (* "отключаем" ее от списка *)
    stump := stump^.next;
    (* вставляем ее в новый список *)
    InsertRecord(newtree, temp);
  end; { While }

  (* теперь помещаем начало нового, сортированного
  дерева в начало старого списка *)
  list := newtree;
end; { SortByName }
begin

  New(root);
  root^.Name := 'BETA';
  New(root^.next);
  root^.next^.Name := 'ALPHA';
  New(root^.next^.next);
  root^.next^.next^.Name := 'Torture';

  WriteLn(root^.name);
  WriteLn(root^.next^.name);
  WriteLn(root^.next^.next^.name);
end.

Программа на языке Pascal, демонстрирующая сортировку связного списка по имени с помощью процедуры InsertRecord и функции SortByName.

Определения типов Программа определяет рекордный тип TData с двумя полями: next (указатель на другой рекорд TData) и Name (строковое поле).

Переменные Программа объявляет переменную root типа PData, которая является указателем на первый элемент в связном списке.

Процедура InsertRecord Эта процедура вставляет новый рекорд в связный список, сохраняя отсортированный порядок. Она принимает два параметра: var root (голова связного списка) и pItem (новый рекорд для вставки).

Процедура работает, итерируясь по связному списку, сравнивая каждый элемент с новым рекордом с помощью функции сравнения (CompareItems). Когда она находит правильное положение для нового рекорда, она вставляет его в список.

Функция SortByName Эта функция сортирует связный список в порядке возрастания по полю Name каждого рекорда. Она использует процедуру InsertRecord для вставки каждого элемента из оригинального списка в новый отсортированный список.

Функция работает, итерируясь по оригинальному списку, вставляя каждый элемент в новый список с помощью InsertRecord, и обновляет голову нового списка с каждой вставкой.

Главная программа Основная программа создает связный список из трех элементов, сортирует его с помощью SortByName и выводит наименования элементов в отсортированном порядке.

Предложения по улучшению кода Вот несколько предложений для улучшения кода: 1. Использование более эффективного алгоритма сортировки: Текущая реализация использует InsertRecord для вставки каждого элемента в новый список, что имеет время сложности O(n^2). Более эффективный алгоритм сортировки,such as MergeSort or QuickSort, could be used instead. 2. Улучшение обработки ошибок: Программа не обрабатывает ошибки хорошо. Например, если связный список пуст при попытке его отсортировать, программа будет крашиться. Механизмы обработки ошибок должны быть добавлены для обработки таких случаев. 3. Использование более описательных имен переменных: Некоторые имена переменных слишком длинны и описательны, но другие (например, stump и temp) могли бы быть переименованы для лучшей читаемости.

В целом, код хорошо структурирован и легко понятен, но есть место для улучшения в отношении эффективности и обработки ошибок.

Сортировка связанного списка описывается в статье, где рассматривается пример программирования на языке Pascal для сортировки записей в связанном списке по алфавитному порядку.


Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS




Материалы статей собраны из открытых источников, владелец сайта не претендует на авторство. Там где авторство установить не удалось, материал подаётся без имени автора. В случае если Вы считаете, что Ваши права нарушены, пожалуйста, свяжитесь с владельцем сайта.


:: Главная :: Сортировка и Фильтр ::


реклама


©KANSoftWare (разработка программного обеспечения, создание программ, создание интерактивных сайтов), 2007
Top.Mail.Ru

Время компиляции файла: 2024-11-30 11:42:55
2024-12-10 23:10:24/0.0052540302276611/0