想通过这个类来呈现双向链表的创建，插入，删除，但对delphi和数据结构不是很了解。希望达人能给出具体的代码，例如form1.button1.click()里面实现创建，等。
万分焦急，因为要交作业的说-_-
谢谢啦以下是类:
unit DoubleLinkedList;interfacetype
DListNode=class(TObject)
private
next,prev:DListNode;
public
data:string;
constructor create;
destructor destroy; override; end; DList=class(TObject)
private
fhead,ftail:DListNode;
fsize:integer;
function getsize:integer;
public
constructor create;
destructor destroy; override;
procedure append(p:DListNode);
procedure insertbefore(p,before:DListNode);
procedure remove(p:DListNode);
procedure delete(p:DListNode);
function next(p:DListNode):DListNode;
function prev(p:DListNode):DListNode;
published
property size:integer read getsize;
property head:DListNode read fhead;
property tail:DListNode read ftail;
end; DQueue=class(DList) //FIFO
public
constructor create;
destructor destroy; override;
procedure QueueIn(p:DListNode);
function QueueOut:DListNode;
end; DStack=class(DList)
public
constructor create;
destructor destroy; override;
procedure push(p:DListNode);
function pop:DListNode;
end;
implementationuses Sysutils;type EDoubleLinkedStuff=class(Exception);constructor DListNode.create;
begin
inherited create;
next:=nil; prev:=nil;
end;destructor DListNode.destroy;
begin
inherited destroy;
end;function DList.getsize:integer;
begin
result:=fsize;
end;constructor DList.create;
begin
inherited create; fhead:=nil; ftail:=nil; fsize:=0;
end;destructor DList.destroy;
var q:DListNode;
begin
while head <> nil do
begin
q:=fhead; fhead:=fhead.next; q.destroy;
end;
end;procedure DList.append(p:DListNode);
begin
if fhead=nil then begin
fhead:=p; ftail:=p;
end
else begin
p.prev:=ftail; ftail.next:=p; ftail:=p;
end;
inc(fsize);
end;procedure DList.insertbefore(p,before:DListNode);
begin
if head=nil then begin
fhead:=p; ftail:=p;
end
else begin
if before=head then begin
p.next:=head; head.prev:=p; fhead:=p;
end
else begin
p.next:=before; p.prev:=before.prev;
p.prev.next:=p; before.prev:=p;
end;
end;
inc(fsize);
end;procedure DList.remove(p:DListNode);
begin
if p=fhead then begin
fhead:=fhead.next;
if fhead=nil then ftail:=nil
else fhead.prev:=nil;
end
else begin
if p=ftail then begin
ftail:=ftail.prev;
if ftail=nil then fhead:=nil
else ftail.next:=nil;
end
else begin
p.prev.next:=p.next;
p.next.prev:=p.prev;
end;
end;
dec(fsize);
p.next:=nil; p.prev:=nil;
end;procedure DList.delete(p:DListNode);
begin
remove(p); p.destroy;
end;function DList.next(p:DListNode):DListNode;
begin
if p=nil then raise EDoubleLinkedStuff.create('next(DList) is nil');
result:=p.next;
end;function DList.prev(p:DListNode):DListNode;
begin
if p=nil then raise EDoubleLinkedStuff.create('prev(DList) is nil');
result:=p.prev;
end;constructor DQueue.create;
begin
inherited create;
end;destructor DQueue.destroy;
begin
inherited destroy;
end;procedure DQueue.QueueIn(p:DListNode);
begin
insertbefore(p,head);
end;function DQueue.QueueOut:DListNode;
begin
result:=tail;
if tail <> nil then remove(result);
end;constructor DStack.create;
begin
inherited create;
end;destructor DStack.destroy;
begin
inherited destroy;
end;procedure DStack.push(p:DListNode);
begin
append(p);
end;function DStack.pop:DListNode;
begin
result:=tail;
if tail <> nil then remove(tail);
end;end.
万分焦急，因为要交作业的说-_-
谢谢啦以下是类:
unit DoubleLinkedList;interfacetype
DListNode=class(TObject)
private
next,prev:DListNode;
public
data:string;
constructor create;
destructor destroy; override; end; DList=class(TObject)
private
fhead,ftail:DListNode;
fsize:integer;
function getsize:integer;
public
constructor create;
destructor destroy; override;
procedure append(p:DListNode);
procedure insertbefore(p,before:DListNode);
procedure remove(p:DListNode);
procedure delete(p:DListNode);
function next(p:DListNode):DListNode;
function prev(p:DListNode):DListNode;
published
property size:integer read getsize;
property head:DListNode read fhead;
property tail:DListNode read ftail;
end; DQueue=class(DList) //FIFO
public
constructor create;
destructor destroy; override;
procedure QueueIn(p:DListNode);
function QueueOut:DListNode;
end; DStack=class(DList)
public
constructor create;
destructor destroy; override;
procedure push(p:DListNode);
function pop:DListNode;
end;
implementationuses Sysutils;type EDoubleLinkedStuff=class(Exception);constructor DListNode.create;
begin
inherited create;
next:=nil; prev:=nil;
end;destructor DListNode.destroy;
begin
inherited destroy;
end;function DList.getsize:integer;
begin
result:=fsize;
end;constructor DList.create;
begin
inherited create; fhead:=nil; ftail:=nil; fsize:=0;
end;destructor DList.destroy;
var q:DListNode;
begin
while head <> nil do
begin
q:=fhead; fhead:=fhead.next; q.destroy;
end;
end;procedure DList.append(p:DListNode);
begin
if fhead=nil then begin
fhead:=p; ftail:=p;
end
else begin
p.prev:=ftail; ftail.next:=p; ftail:=p;
end;
inc(fsize);
end;procedure DList.insertbefore(p,before:DListNode);
begin
if head=nil then begin
fhead:=p; ftail:=p;
end
else begin
if before=head then begin
p.next:=head; head.prev:=p; fhead:=p;
end
else begin
p.next:=before; p.prev:=before.prev;
p.prev.next:=p; before.prev:=p;
end;
end;
inc(fsize);
end;procedure DList.remove(p:DListNode);
begin
if p=fhead then begin
fhead:=fhead.next;
if fhead=nil then ftail:=nil
else fhead.prev:=nil;
end
else begin
if p=ftail then begin
ftail:=ftail.prev;
if ftail=nil then fhead:=nil
else ftail.next:=nil;
end
else begin
p.prev.next:=p.next;
p.next.prev:=p.prev;
end;
end;
dec(fsize);
p.next:=nil; p.prev:=nil;
end;procedure DList.delete(p:DListNode);
begin
remove(p); p.destroy;
end;function DList.next(p:DListNode):DListNode;
begin
if p=nil then raise EDoubleLinkedStuff.create('next(DList) is nil');
result:=p.next;
end;function DList.prev(p:DListNode):DListNode;
begin
if p=nil then raise EDoubleLinkedStuff.create('prev(DList) is nil');
result:=p.prev;
end;constructor DQueue.create;
begin
inherited create;
end;destructor DQueue.destroy;
begin
inherited destroy;
end;procedure DQueue.QueueIn(p:DListNode);
begin
insertbefore(p,head);
end;function DQueue.QueueOut:DListNode;
begin
result:=tail;
if tail <> nil then remove(result);
end;constructor DStack.create;
begin
inherited create;
end;destructor DStack.destroy;
begin
inherited destroy;
end;procedure DStack.push(p:DListNode);
begin
append(p);
end;function DStack.pop:DListNode;
begin
result:=tail;
if tail <> nil then remove(tail);
end;end.
可以帮助你很容易完成这些任务至于怎么用，看帮助吧，讲起来太烦了。
SysUtils, Windows;type
TtdNodeManager = class
private
FNodeSize : cardinal;
FFreeList : pointer;
FNodesPerPage : cardinal;
FPageHead : pointer;
FPageSize : cardinal;
FName : TtdNameString;
protected
procedure nmAllocNewPage;
public
constructor Create(aNodeSize : cardinal);
destructor Destroy; override; function AllocNode : pointer;
function AllocNodeClear : pointer;
procedure FreeNode(aNode : pointer); property Name : TtdNameString
read FName write FName;
end; PdlNode = ^TdlNode; {a node with two links}
TdlNode = packed record
dlnNext : PdlNode;
dlnPrior : PdlNode;
dlnData : pointer;
end; TtdDoubleLinkList = class
private
FCount : longint;
FCursor : PdlNode;
FCursorIx: longint;
FDispose : TtdDisposeProc;
FHead : PdlNode;
FIsSorted: boolean;
FName : TtdNameString;
FTail : PdlNode;
protected
function dllGetItem(aIndex : longint) : pointer;
procedure dllSetItem(aIndex : longint; aItem : pointer); procedure dllError(aErrorCode : integer;
const aMethodName : TtdNameString);
class procedure dllGetNodeManager;
function dllMerge(aCompare : TtdCompareFunc;
aPriorNode1 : PdlNode; aCount1 : longint;
aPriorNode2 : PdlNode; aCount2 : longint)
: PdlNode;
function dllMergesort(aCompare : TtdCompareFunc;
aPriorNode : PdlNode;
aCount : longint) : PdlNode;
procedure dllPositionAtNth(aIndex : longint);
public
constructor Create(aDispose : TtdDisposeProc);
destructor Destroy; override; function Add(aItem : pointer) : longint;
procedure Clear;
procedure Delete(aIndex : longint);
procedure DeleteAtCursor;
function Examine : pointer;
function First : pointer;
function IndexOf(aItem : pointer) : longint;
procedure Insert(aIndex : longint; aItem : pointer);
procedure InsertAtCursor(aItem : pointer);
procedure InsertSorted(aItem : pointer;
aCompare : TtdCompareFunc);
function IsAfterLast : boolean;
function IsBeforeFirst : boolean;
function IsEmpty : boolean;
function Last : pointer;
function Locate(aItem : pointer;
aCompare : TtdCompareFunc) : longint;
procedure MoveAfterLast;
procedure MoveBeforeFirst;
procedure MoveNext;
procedure MovePrior;
procedure Remove(aItem : pointer); procedure InsertionSort(aCompare : TtdCompareFunc);
procedure Sort(aCompare : TtdCompareFunc); property Count : longint
read FCount;
property IsSorted : boolean
read FIsSorted;
property Items[aIndex : longint] : pointer
read dllGetItem write dllSetItem;
default;
property Name : TtdNameString
read FName write FName;
end;
implementationconst
UnitName = 'DoubleLinkedList';
PageSize = 1024;var
DLNodeManager : TtdNodeManager; {nodemanager for doublylinked lists}type
PGenericNode = ^TGenericNode;
TGenericNode = packed record
gnNext : PGenericNode;
gnData : record end;
end;{===TtdNodeManager===================================================}
constructor TtdNodeManager.Create(aNodeSize : cardinal);
begin
inherited Create;
{save the node size rounded to nearest 4 bytes}
if (aNodeSize <= sizeof(pointer)) then
aNodeSize := sizeof(pointer)
else
aNodeSize := ((aNodeSize + 3) shr 2) shl 2;
FNodeSize := aNodeSize;
{calculate the page size (default 1024 bytes) and the number of
nodes per page; if the default page size is not large enough for
two or more nodes, force a single node per page}
FNodesPerPage := (PageSize - sizeof(pointer)) div aNodeSize;
if (FNodesPerPage > 1) then
FPageSize := 1024
else begin
FNodesPerPage := 1;
FPagesize := aNodeSize + sizeof(pointer);
end;
end;
{--------}
destructor TtdNodeManager.Destroy;
var
Temp : pointer;
begin
{dispose of all the pages, if there are any}
while (FPageHead <> nil) do begin
Temp := PGenericNode(FPageHead)^.gnNext;
FreeMem(FPageHead, FPageSize);
FPageHead := Temp;
end;
inherited Destroy;
end;
{--------}
function TtdNodeManager.AllocNode : pointer;
begin
{if the free list is empty, allocate a new page; this'll fill the
free list}
if (FFreeList = nil) then
nmAllocNewPage;
{return the top of the free list}
Result := FFreeList;
FFreeList := PGenericNode(FFreeList)^.gnNext;
end;
{--------}
function TtdNodeManager.AllocNodeClear : pointer;
begin
{if the free list is empty, allocate a new page; this'll fill the
free list}
if (FFreeList = nil) then
nmAllocNewPage;
{return the top of the free list}
Result := FFreeList;
FFreeList := PGenericNode(FFreeList)^.gnNext;
FillChar(Result^, FNodeSize, 0);
end;
{--------}
procedure TtdNodeManager.FreeNode(aNode : pointer);
begin
{add the node (if non-nil) to the top of the free list}
if (aNode <> nil) then begin
PGenericNode(aNode)^.gnNext := FFreeList;
FFreeList := aNode;
end;
end;
{--------}procedure TtdNodeManager.nmAllocNewPage;
var
NewPage : PAnsiChar;
i : integer;
begin
{allocate a new page and add it to the front of the page list}
GetMem(NewPage, FPageSize);
PGenericNode(NewPage)^.gnNext := FPageHead;
FPageHead := NewPage;
{now split up the new page into nodes and push them all onto the
free list; note that the first 4 bytes of the page is a pointer to
the next page, so remember to skip over them}
inc(NewPage, sizeof(pointer));
for i := pred(FNodesPerPage) downto 0 do begin
FreeNode(NewPage);
inc(NewPage, FNodeSize);
end;
end;
{===TtdDoubleLinkList================================================}
constructor TtdDoubleLinkList.Create;
begin
inherited Create;
{save the dispose procedure}
FDispose := aDispose;
{get the node manager}
dllGetNodeManager;
{allocate a head and a tail node and link them together}
FHead := PdlNode(DLNodeManager.AllocNode);
FTail := PdlNode(DLNodeManager.AllocNode);
FHead^.dlnNext := FTail;
FHead^.dlnPrior := nil;
FHead^.dlnData := nil;
FTail^.dlnNext := nil;
FTail^.dlnPrior := FHead;
FTail^.dlnData := nil;
{set the cursor to the head node}
FCursor := FHead;
FCursorIx := -1;
FIsSorted := true;
end;
{--------}
destructor TtdDoubleLinkList.Destroy;
begin
if (Count <> 0) then
Clear;
DLNodeManager.FreeNode(FHead);
DLNodeManager.FreeNode(FTail);
inherited Destroy;
end;
{--------}
function TtdDoubleLinkList.Add(aItem : pointer) : longint;
begin
{move to the very end of the linked list}
FCursor := FTail;
FCursorIx := Count;
{return the index of the new node}
Result := Count;
{insert at the cursor}
InsertAtCursor(aItem);
FIsSorted := false;
end;
{--------}
procedure TtdDoubleLinkList.Clear;
var
Temp : PdlNode;
begin
{delete all the nodes, except the head and tail nodes; if we can
dispose of nodes, do so}
Temp := FHead^.dlnNext;
while (Temp <> FTail) do begin
FHead^.dlnNext := Temp^.dlnNext;
if Assigned(FDispose) then
FDispose(Temp^.dlnData);
DLNodeManager.FreeNode(Temp);
Temp := FHead^.dlnNext;
end;
{patch up the linked list}
FTail^.dlnPrior := FHead;
FCount := 0;
{set the cursor to the head of the list}
FCursor := FHead;
FCursorIx := -1;
FIsSorted := true;
end;
{--------}
procedure TtdDoubleLinkList.Delete(aIndex : longint);
begin
{position the cursor}
dllPositionAtNth(aIndex);
{delete the item at the cursor}
DeleteAtCursor;
end;
{--------}
procedure TtdDoubleLinkList.DeleteAtCursor;
var
Temp : PdlNode;
begin
{let Temp equal the node we are to delete}
Temp := FCursor;
if (Temp = FHead) or (Temp = FTail) then
dllError(tdeListCannotDelete, 'Delete');
{dispose of its contents}
if Assigned(FDispose) then
FDispose(Temp^.dlnData);
{unlink the node and free it; the cursor moves to the next node}
Temp^.dlnPrior^.dlnNext := Temp^.dlnNext;
Temp^.dlnNext^.dlnPrior := Temp^.dlnPrior;
FCursor := Temp^.dlnNext;
DLNodeManager.FreeNode(Temp);
dec(FCount);
if (Count <= 1) then
FIsSorted := true;
end;
{--------}
procedure TtdDoubleLinkList.dllError(aErrorCode : integer;
const aMethodName : TtdNameString);
begin
if (Name = '') then
Name := '-unnamed-';
raise EtdLinkListException.Create(
FmtLoadStr(aErrorCode,
[UnitName, ClassName, aMethodName, Name]));
end;
{--------}
function TtdDoubleLinkList.dllGetItem(aIndex : longint) : pointer;
begin
{position the cursor}
dllPositionAtNth(aIndex);
{return the data}
Result := FCursor^.dlnData;
end;
{--------}
class procedure TtdDoubleLinkList.dllGetNodeManager;
begin
{if the node manager hasn't been allocated yet, do so}
if (DLNodeManager = nil) then
DLNodeManager := TtdNodeManager.Create(sizeof(TdlNode));
end;
{--------}
function TtdDoubleLinkList.dllMerge(
aCompare : TtdCompareFunc;
aPriorNode1 : PdlNode; aCount1 : longint;
aPriorNode2 : PdlNode; aCount2 : longint) : PdlNode;
var
i : integer;
Node1 : PdlNode;
Node2 : PdlNode;
LastNode : PdlNode;
Temp : PdlNode;
begin
{note: when this method is called the linked list looks like this:
aPriorNode1 -> sublist1 -> sublist2 -> rest of list
with the last node of sublist1 being aPriorNode2. After the
merge, the list will look like this
aPriorNode1 -> merged sublists -> rest of list
and we'll return the last node in the merged sublist.}
LastNode := aPriorNode1;
{get the two top nodes}
Node1 := aPriorNode1^.dlnNext;
Node2 := aPriorNode2^.dlnNext;
{repeat until one of the lists empties}
while (aCount1 <> 0) and (aCount2 <> 0) do begin
if (aCompare(Node1^.dlnData, Node2^.dlnData) <= 0) then begin
LastNode := Node1;
Node1 := Node1^.dlnNext;
dec(aCount1);
end
else begin
Temp := Node2^.dlnNext;
Node2^.dlnNext := Node1;
LastNode^.dlnNext := Node2;
LastNode := Node2;
Node2 := Temp;
dec(aCount2);
end;
end;
{if it was the first list that emptied, link the last node up to the
remaining part of the second list, and walk it to get the very last
node}
if (aCount1 = 0) then begin
LastNode^.dlnNext := Node2;
for i := 0 to pred(aCount2) do
LastNode := LastNode^.dlnNext;
end
{if it was the second list that emptied, Node2 is the first node of
the remaining list; walk the remaining part of the first list and
link it up to Node2}
else begin
for i := 0 to pred(aCount1) do
LastNode := LastNode^.dlnNext;
LastNode^.dlnNext := Node2;
end;
{return the last node}
Result := LastNode;
end;
{--------}
function TtdDoubleLinkList.dllMergesort(aCompare : TtdCompareFunc;
aPriorNode : PdlNode;
aCount : longint)
: PdlNode;
var
Count2 : longint;
PriorNode2 : PdlNode;
{$IFDEF Windows}
DummyNode : PdlNode;
{$ENDIF}
begin
{easy case first: if there is only one item in the sublist, it must
be sorted, so return}
if (aCount = 1) then begin
Result := aPriorNode^.dlnNext;
Exit;
end;
{split the list into two parts}
Count2 := aCount div 2;
aCount := aCount - Count2;
{mergesort the first half: this'll return the head node for the
second half}
PriorNode2 := dllMergeSort(aCompare, aPriorNode, aCount);
{mergesort the second half}
{$IFDEF Windows}
DummyNode :=
{$ENDIF}
dllMergeSort(aCompare, PriorNode2, Count2);
{now merge the two halves, return the final node}
Result := dllMerge(aCompare, aPriorNode, aCount, PriorNode2, Count2);
end;
{--------}
procedure TtdDoubleLinkList.dllPositionAtNth(aIndex : longint);
var
WorkCursor : PdlNode;
WorkCursorIx : longint;
begin
{check for a valid index}
if (aIndex < 0) or (aIndex >= Count) then
dllError(tdeListInvalidIndex, 'dllPositionAtNth');
{use local varaibles for speed}
WorkCursor := FCursor;
WorkCursorIx := FCursorIx;
{take care of easy case}
if (aIndex = WorkCursorIx) then
Exit;
{the desired index is either before the current cursor or after it;
in either case the required index is either closer to the cursor or
closer to the relevant end; work out the shortest route}
if (aIndex < WorkCursorIx) then begin
if ((aIndex - 0) < (WorkCursorIx - aIndex)) then begin
{start at front and work forwards towards aIndex}
WorkCursor := FHead;
WorkCursorIx := -1;
end;
end
else {aIndex > FCursorIx} begin
if ((aIndex - WorkCursorIx) < (Count - aIndex)) then begin
{start at end and work back towards aIndex}
WorkCursor := FTail;
WorkCursorIx := Count;
end;
end;
{while the work cursor index is less than the index required,
advance the work cursor}
while (WorkCursorIx < aIndex) do begin
WorkCursor := WorkCursor^.dlnNext;
inc(WorkCursorIx);
end;
{while the work cursor index is greater than the index required,
move the work cursor backwards}
while (WorkCursorIx > aIndex) do begin
WorkCursor := WorkCursor^.dlnPrior;
dec(WorkCursorIx);
end;
{set the real cursor equal to the work cursor}
FCursor := WorkCursor;
FCursorIx := WorkCursorIx;
end;
{--------}
procedure TtdDoubleLinkList.dllSetItem(aIndex : longint;
aItem : pointer);
begin
{position the cursor}
dllPositionAtNth(aIndex);
{if we can dispose of the data about to be replaced, do so}
if Assigned(FDispose) and (aItem <> FCursor^.dlnData) then
FDispose(FCursor^.dlnData);
{replace the data}
FCursor^.dlnData := aItem;
FIsSorted := false;
end;
{--------}
function TtdDoubleLinkList.Examine : pointer;
begin
if (FCursor = nil) or (FCursor = FHead) then
dllError(tdeListCannotExamine, 'Examine');
{return the data part of the cursor}
Result := FCursor^.dlnData;
end;
{--------}
function TtdDoubleLinkList.First : pointer;
begin
{position the cursor}
dllPositionAtNth(0);
{return the data}
Result := FCursor^.dlnData;
end;
{--------}
function TtdDoubleLinkList.IndexOf(aItem : pointer) : longint;
var
WorkCursor : PdlNode;
WorkCursorIx : longint;
begin
{set the work cursor to the first node (if it exists)}
WorkCursor := FHead^.dlnNext;
WorkCursorIx := 0;
{walk the linked list looking for the item}
while (WorkCursor <> FTail) do begin
if (WorkCursor^.dlnData = aItem) then begin
{we found it; set the result; set the real cursor}
Result := WorkCursorIx;
FCursor := WorkCursor;
FCursorIx := WorkCursorIx;
Exit;
end;
{advance to the next node}
WorkCursor := WorkCursor^.dlnNext;
inc(WorkCursorIx);
end;
{didn't find it}
Result := -1;
end;
{--------}
procedure TtdDoubleLinkList.Insert(aIndex : longint; aItem : pointer);
begin
{position the cursor}
dllPositionAtNth(aIndex);
{insert the item at the cursor}
InsertAtCursor(aItem);
FIsSorted := false;
end;
{--------}
procedure TtdDoubleLinkList.InsertAtCursor(aItem : pointer);
var
NewNode : PdlNode;
begin
{if the cursor is at the head, rather than raise an exception, move
it forwards one node}
if (FCursor = FHead) then
MoveNext;
{allocate a new node and insert before the cursor}
NewNode := PdlNode(DLNodeManager.AllocNode);
NewNode^.dlnData := aItem;
NewNode^.dlnNext := FCursor;
NewNode^.dlnPrior := FCursor^.dlnPrior;
NewNode^.dlnPrior^.dlnNext := NewNode;
FCursor^.dlnPrior := NewNode;
FCursor := NewNode;
inc(FCount);
end;
{--------}
procedure TtdDoubleLinkList.InsertSorted(aItem : pointer;
aCompare : TtdCompareFunc);
begin
if not IsSorted then
dllError(tdeListIsNotSorted, 'InsertSorted');
if Locate(aItem, aCompare) = -1 then
InsertAtCursor(aItem);
end;
{--------}
function TtdDoubleLinkList.IsAfterLast : boolean;
begin
Result := FCursor = FTail;
end;
{--------}
function TtdDoubleLinkList.IsBeforeFirst : boolean;
begin
Result := FCursor = FHead;
end;
{--------}
function TtdDoubleLinkList.IsEmpty : boolean;
begin
Result := (Count = 0);
end;
{--------}
function TtdDoubleLinkList.Last : pointer;
begin
{position the cursor}
dllPositionAtNth(pred(Count));
{return the data}
Result := FCursor^.dlnData;
end;
{--------}
function TtdDoubleLinkList.Locate(aItem : pointer;
aCompare : TtdCompareFunc)
: longint;
var
BLCursor : PdlNode;
BLCursorIx : longint;
WorkCursor : PdlNode;
WorkCursorIx : longint;
ListCount : longint;
MidPoint : longint;
i : integer;
CompareResult: integer;
begin
{there are two different ways of doing this, depending on whether
the list is sorted or not; if sorted, we perform a binary search,
if not, we perform a sequential search}
{if sorted, do a binary search}
if IsSorted then begin
{prepare}
BLCursor := FHead;
BLCursorIx := -1;
ListCount := Count;
{while there are still nodes to check...}
while (ListCount <> 0) do begin
{calculate the midpoint; it will be at least 1}
MidPoint := (ListCount + 1) div 2;
{move that many nodes along}
WorkCursor := BLCursor;
WorkCursorIx := BLCursorIx;
for i := 1 to MidPoint do begin
WorkCursor := WorkCursor^.dlnNext;
inc(WorkCursorIx);
end;
{compare this node's data with the given item}
CompareResult := aCompare(WorkCursor^.dlnData, aItem);
{if the node's data is less than the item, shrink the list, and
try again from where we're at}
if (CompareResult < 0) then begin
dec(ListCount, MidPoint);
BLCursor := WorkCursor;
BLCursorIx := WorkCursorIx;
end
{if the node's data is greater than the item, shrink the list,
and try again}
else if (CompareResult > 0) then begin
ListCount := MidPoint - 1;
end
{otherwise we found it; set the real cursor}
else begin
FCursor := WorkCursor;
FCursorIx := WorkCursorIx;
Result := WorkCursorIx;
Exit;
end;
end;
{we didn't find it, but set the real cursor to where the item
should be inserted}
FCursor := BLCursor^.dlnNext;
FCursorIx := succ(BLCursorIx);
end
{otherwise do a sequential search}
else begin
{set the work cursor to the first node (if it exists)}
WorkCursor := FHead^.dlnNext;
WorkCursorIx := 0;
{walk the linked list looking for the item}
while (WorkCursor <> nil) do begin
if (aCompare(WorkCursor^.dlnData, aItem) = 0) then begin
{we found it; set the result; set the real cursor}
Result := WorkCursorIx;
FCursor := WorkCursor;
FCursorIx := WorkCursorIx;
Exit;
end;
{advance to the next node}
WorkCursor := WorkCursor^.dlnNext;
inc(WorkCursorIx);
end;
end;
{didn't find it}
Result := -1;
end;
{--------}
procedure TtdDoubleLinkList.MoveAfterLast;
begin
{set the cursor to the tail node}
FCursor := FTail;
FCursorIx := Count;
end;
{--------}
procedure TtdDoubleLinkList.MoveBeforeFirst;
begin
{set the cursor to the head node}
FCursor := FHead;
FCursorIx := -1;
end;
{--------}
procedure TtdDoubleLinkList.MoveNext;
begin
{advance the cursor to its own next pointer}
if (FCursor <> FTail) then begin
FCursor := FCursor^.dlnNext;
inc(FCursorIx);
end;
end;
{--------}
procedure TtdDoubleLinkList.MovePrior;
begin
{move the cursor back to its own previous pointer}
if (FCursor <> FHead) then begin
FCursor := FCursor^.dlnPrior;
dec(FCursorIx);
end;
end;
{--------}
procedure TtdDoubleLinkList.Remove(aItem : pointer);
begin
if (IndexOf(aItem) <> -1) then
DeleteAtCursor;
end;
{--------}
procedure TtdDoubleLinkList.InsertionSort(aCompare : TtdCompareFunc);
var
Walker : PdlNode;
Temp : PdlNode;
WalkerParent : PdlNode;
TempParent : PdlNode;
begin
{if there are zero (or one) items the list is already sorted}
if (Count <= 1) then begin
FIsSorted := true;
Exit;
end;
{perform an insertion sort from the second item onwards}
WalkerParent := FHead^.dlnNext;
Walker := WalkerParent^.dlnNext;
while (Walker <> FTail) do begin
{find where the walker item should be in the sorted list to its
left - we walk the sorted sublist making a note of the parent as
we go so that we can insert properly. Note that the loop below
will terminate in the worst case by the walker node itself - we
won't run off the end of the list}
TempParent := FHead;
Temp := TempParent^.dlnNext;
while (aCompare(Temp^.dlnData, Walker^.dlnData) < 0) do begin
TempParent := Temp;
Temp := TempParent^.dlnNext;
end;
{did we find the walker node? If so, move the walker's parent on
by one link}
if (Temp = Walker) then begin
WalkerParent := Walker;
end
{otherwise, move the walker node into the correct place in the
sorted sublist}
else begin
{disconnect the walker node}
WalkerParent^.dlnNext := Walker^.dlnNext;
{connect the walker node in the correct place}
Walker^.dlnNext := Temp;
TempParent^.dlnNext := Walker;
end;
{set the walker node}
Walker := WalkerParent^.dlnNext;
end;
{now patch up all of the previous links}
WalkerParent := FHead;
Walker := WalkerParent^.dlnNext;
while (WalkerParent <> FTail) do begin
Walker^.dlnPrior := WalkerParent;
WalkerParent := Walker;
Walker := WalkerParent^.dlnNext;
end;
MoveBeforeFirst;
FIsSorted := true;
end;
{--------}
procedure TtdDoubleLinkList.Sort(aCompare : TtdCompareFunc);
var
Dad, Walker : PdlNode;
begin
{perform a singly linked mergesort if there are more than one item
in the list; then patch up the prior links}
if (Count > 1) then begin
dllMergesort(aCompare, FHead, Count);
Dad := FHead;
Walker := FHead^.dlnNext;
while (Walker <> nil) do begin
Walker^.dlnPrior := Dad;
Dad := Walker;
Walker := Dad^.dlnNext;
end;
end;
MoveBeforeFirst;
FIsSorted := true;
end;
{====================================================================}
{===Interfaced routines==============================================}
function TDSLLSearch(aList : TtdSingleLinkList;
aItem : pointer;
aCompare : TtdCompareFunc) : boolean;
begin
with aList do begin
MoveBeforeFirst;
MoveNext;
while not IsAfterLast do begin
if (aCompare(Examine, aItem) = 0) then begin
Result := true;
Exit;
end;
MoveNext;
end;
end;
Result := false;
end;
{--------}
function TDSLLSortedSearch(aList : TtdSingleLinkList;
aItem : pointer;
aCompare : TtdCompareFunc) : boolean;
var
Compare : integer;
begin
with aList do begin
MoveBeforeFirst;
MoveNext;
while not IsAfterLast do begin
Compare := aCompare(Examine, aItem);
if (Compare >= 0) then begin
Result := (Compare = 0);
Exit;
end;
MoveNext;
end;
end;
Result := false;
end;
{--------}
function TDDLLSearch(aList : TtdSingleLinkList;
aItem : pointer;
aCompare : TtdCompareFunc) : boolean;
begin
with aList do begin
MoveBeforeFirst;
MoveNext;
while not IsAfterLast do begin
if (aCompare(Examine, aItem) = 0) then begin
Result := true;
Exit;
end;
MoveNext;
end;
end;
Result := false;
end;
{--------}
function TDDLLSortedSearch(aList : TtdSingleLinkList;
aItem : pointer;
aCompare : TtdCompareFunc) : boolean;
var
Compare : integer;
begin
with aList do begin
MoveBeforeFirst;
MoveNext;
while not IsAfterLast do begin
Compare := aCompare(Examine, aItem);
if (Compare >= 0) then begin
Result := (Compare = 0);
Exit;
end;
MoveNext;
end;
end;
Result := false;
end;
{====================================================================}
procedure FinalizeUnit; far;
begin
DLNodeManager.Free;
end;initialization
DLNodeManager := nil;finalization
FinalizeUnit;
end.
我知道，误导比什么也不说更可耻。我有自己在实际中应用的双链表。高效但是没有注释。不适合你交作业。所以我干脆把Julian Bucknall实现的节点管理器和双链表贴上来，你自己看吧。奉劝你不要直接拿去交作业，仔细看懂自己重写一份才对得起Julian 写的那些注释。
-----------------------------------------------------
PF，不太清楚那些错综复杂的陈年旧事，单从技术角度上来说，算是一名斗士！佩服！
TList = class(TObject)
private
FList: PPointerList;
FCount: Integer;
FCapacity: Integer;
protected
function Get(Index: Integer): Pointer;
procedure Grow; virtual;
procedure Put(Index: Integer; Item: Pointer);
procedure Notify(Ptr: Pointer; Action: TListNotification); virtual;
procedure SetCapacity(NewCapacity: Integer);
procedure SetCount(NewCount: Integer);
public
destructor Destroy; override;
function Add(Item: Pointer): Integer;
procedure Clear; virtual;
procedure Delete(Index: Integer);
class procedure Error(const Msg: string; Data: Integer); overload; virtual;
class procedure Error(Msg: PResStringRec; Data: Integer); overload;
procedure Exchange(Index1, Index2: Integer);
function Expand: TList;
function Extract(Item: Pointer): Pointer;
function First: Pointer;
function IndexOf(Item: Pointer): Integer;
procedure Insert(Index: Integer; Item: Pointer);
function Last: Pointer;
procedure Move(CurIndex, NewIndex: Integer);
function Remove(Item: Pointer): Integer;
procedure Pack;
procedure Sort(Compare: TListSortCompare);
procedure Assign(ListA: TList; AOperator: TListAssignOp = laCopy; ListB: TList = nil);
property Capacity: Integer read FCapacity write SetCapacity;
property Count: Integer read FCount write SetCount;
property Items[Index: Integer]: Pointer read Get write Put; default;
property List: PPointerList read FList;
end;
========================================================
function First: Pointer;
function Last: Pointer;
========================================================把这两个想成Prior跟next了:P
我也把它当作双向链表了
在此向楼主道歉，向RL表示感谢！
PPointerList = ^TPointerList;
TPointerList = array[0..MaxListSize - 1] of Pointer; TList = class(TObject)
private
FList: PPointerList;
FCount: Integer;
FCapacity: Integer;
....
end;
以TStringList作为例子，模拟实现双向链表的所有功能TStringList的Count是包含的数据个数
对于任何节点N，访问方法是Strings［N］
下一个节点N+1，是Strings［N+1］
上一个节点是N-1，String［N-1］如果N>=Count则，下一个为String［0］
如果N＝0则，下一个为String［Count-1］使用外部变量N保存当前节点位置就OK了当然继承TList就可以拓展这个参数了在N中插入节点，用Insert（N，Data）
删除就Delete（N）方法用Tlist，我可以实现链表的所有功能，这就OK了效果相同就可以了，至于如何做，没所谓的http://lysoft.7u7.net
建议楼主找本数据结构for C++看看。
leeon是认真。。还好我没在他面前说过话。。不然惨了。。
我用tstringlist模拟了双向链表^^作业已经上交了，希望老师不要p我。谢谢大家啊。
liuyang和RL