<![CDATA[size : 3863
uploaded_on : Wed Oct 14 00:00:00 1998
modified_on : Wed Dec 8 14:03:17 1999
title : Sort linked list
org_filename : SortLinkedList.txt
author : Peter Below
authoremail :
description : An example on sorting linked lists
keywords :
tested : not tested yet
submitted_by : Mike Orriss
submitted_by_email : mjo@3kcc.co.uk
uploaded_by : nobody
modified_by : nobody
owner : nobody
lang : plain
file-type : text/plain
category : delphi-misc
__END_OF_HEADER__
Here is a sample:
program noname;
Type
PData = ^TData;
TData = Record
next: PData;
Name: String[ 40 ];
{ ...other data fields }
End;
Var
root: PData; { this is the pointer to the first record in the linked list }
Procedure InsertRecord( Var root: PData; pItem: PData );
(* insert the record pointed to by pItem into the list starting at root at the proper place required by sort order *)
Var
pWalk, pLast: PData;
Begin
If root = Nil Then Begin
(* new list is still empty, just make the record to add the root of the new list *)
root := pItem;
root^.next := Nil
End { If }
Else Begin
(* walk thru the list and compare each record with the one to insert. We need to remember the last record we checked, for reasons that will
become appearend later. *)
pWalk := root;
pLast := Nil;
(* the condition in the following While statement determines the sort order! This would be an ideal place to put in a call to a comparison
function you pass as additional parameter to InsertRecord, to make it a generic sort, e.g.
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
(* we found the end of the list, so append the new record there and exit this procedure *)
pWalk^.next := pItem;
pItem^.next := Nil;
Exit;
End { If }
Else Begin
(* next record, please, but remember the one we just checked! *)
pLast := pWalk;
(* if we end up here we found a record in the list that is >= the one to insert. So insert it before the record pWalk currently points at, which
is after pLast. *)
If pLast = Nil Then Begin
(* Oops, we fell out of the while loop on the very first round! The new record has to go to the top of the list, so it becomes the new root!
*)
pItem^.next := root;
root := pItem;
End { If }
Else Begin
(* insert pItem between pLast and pWalk *)
pItem^.next := pWalk;
pLast^.next := pItem;
End; { Else }
(* and we are done! *)
End; { Else }
End; { InsertRecord }
Procedure SortbyName( Var list: PData );
Var
newtree, temp, stump: PData;
Begin { SortByName }
(* exit immediately if there is nothing to sort *)
If list = Nil then Exit;
(* in
newtree := Nil;
(********
We sort simply by taking records off the original list and insert them
into a new one we hook to newtree at the right position. Stump is used
to hold the remainder of the list. temp is used to point at the record
we move from one list to the other.
********)
stump := list;
While stump <> Nil Do Begin
(* point temp at the record to move *)
temp := stump;
(* disconnect it from the list *)
stump := stump^.next;
(* insert it into the new list *)
InsertRecord( newtree, temp );
End; { While }
(* now put the start of the new, sorted tree into the old list start *)
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.
- Peter Below
]]>