Linked List Unit for CheckBook Program
UNIT ChkList;
{ A Unit for ADT Linked List. A linked list is an ordered structure of nodes.
Each node has a pointer to a successor, or to NIL for the last node. The
implementation of a Linked List is via a record with two pointers, Head and
Current. Head points to the first node in the list, whereas Current points to
some node in the list that is then considered the current node. The operations
on a Linked List are described below. This unit uses pointers to implement the
ADT Linked List. }
INTERFACE
CONST
Len_Date = 12;
Len_ID = 12;
Len_Amount = 12;
Len_PayTo = 100;
Len_Comment = 100;
TYPE
Check = Record
ID: String[Len_ID];
Date: String[Len_Date];
Amount: String[Len_Amount];
PayTo : String;
Comment: String[Len_Comment];
end;
StdElement = Check;
NodePointer = ^Node;
Node = RECORD
Data : StdElement;
Next: NodePointer;
END;
CheckList = RECORD
Head : NodePointer;
Current: NodePointer;
nnodes : integer;
END;
PROCEDURE MakeEmptyList(var List: CheckList);
{ POST: head and current point to NIL }
PROCEDURE DestroyList(var List: CheckList);
{ POST: destroys all nodes in list and returns a valid empty list }
PROCEDURE FindFirst(VAR List: CheckList);
{ PRE: the list is not empty }
{ POST: the current pointer points to the first node }
PROCEDURE FindNext(VAR List: CheckList);
{ PRE: the list is not empty, and current does not point to the last node }
{ POST: current points to the next node after old current }
PROCEDURE Findith(VAR List: CheckList; i : integer);
{ PRE: the list is not empty }
{ POST: current points to the i-th element in the list, if possible }
PROCEDURE FindPayTo(VAR List: CheckList; Key: String; var Position: integer);
{ PRE: the list is not empty }
{ POST: current points to the element containing Key in PayTo field and }
{ Pos indicates the position of the element in the list. Otherwise }
{ Pos = -1 and current is unchanged }
PROCEDURE Retrieve(List: CheckList; var e: StdElement);
{ PRE: the list is not empty }
{ POST: e contains the data of the current node }
PROCEDURE Update(List: CheckList; e: StdElement);
{ PRE: the list is not empty }
{ POST: the current node contains the new data e }
PROCEDURE Insert(VAR List: CheckList; e: StdElement);
{ PRE: the list has not reached its maximum length }
{ POST: a new node with data e is inserted at the first position in the list and }
{ current points to that new node }
PROCEDURE Delete(VAR List: CheckList);
{ PRE: the list is not empty }
{ POST: the current node is deleted from the list and current points to the first node }
FUNCTION IsEmpty(List: CheckList): BOOLEAN;
{ POST: if the list is empty, returns true; otherwise, returns false }
FUNCTION IsFull(List: CheckList): BOOLEAN;
{ POST: if the list is full, returns true; otherwise, returns false }
FUNCTION IsLast(List: CheckList): BOOLEAN;
{ PRE: the list is not empty }
{ POST: if current points to the last node, returns true; otherwise, returns false }
FUNCTION ListLength(List: CHeckList): integer;
PROCEDURE WriteCheckToFile(aCheck: Check; var aFile: Text);
PROCEDURE ReadCheckFromFile(var aCheck: Check; var aFile: Text);
IMPLEMENTATION
{ ************************************************************* }
PROCEDURE FindFirst(VAR List: CheckList);
begin
with List do
current := head
end;
{ ************************************************************* }
PROCEDURE FindNext(VAR List: CheckList);
begin
with List do
current := current^.next;
end;
{ ************************************************************* }
PROCEDURE Findith(VAR List: CheckList; i: integer);
var
count : integer;
BEGIN
FindFirst(List);
for count := 1 to i-1 do
FindNext(List);
END;
{ ************************************************************* }
PROCEDURE FindPayTo(VAR List: CheckList; Key: String; var Position : integer);
var
p: NodePointer;
Success : boolean;
begin
Position := 1;
Success := false;
p := List.head;
while (p <> nil) and (not success) do
begin
if (Pos(Key,p^.data.PayTo) > 0) then
Success := true
else
begin
p := p^.next;
Inc(Position);
end;
end;
if Success then
List.current := p
else
Position := -1;
end;
{ ************************************************************* }
PROCEDURE Retrieve(List: CheckList; var e: StdElement);
begin
e := List.current^.data;
end;
{ ************************************************************* }
PROCEDURE Update(List: CheckList; e: StdElement);
begin
List.current^.data := e;
end;
{ ************************************************************* }
PROCEDURE Insert(VAR List: CheckList; e: StdElement);
var
P : NodePointer;
begin
New(P);
P^.data := e;
P^.next := List.head;
List.head := p;
List.current := p;
Inc(List.nnodes);
end;
{ ************************************************************* }
PROCEDURE Delete(VAR List: CheckList);
var
P : NodePointer;
begin
with List do
begin
Dec(nnodes);
if (current <> head) then
begin
p := head;
while (p^.next <> current) do
p := p^.next;
p^.next := current^.next;
end
else
head := head^.next;
dispose(current);
current := head;
end;
end;
{ ************************************************************* }
FUNCTION IsEmpty(List: CheckList): BOOLEAN;
begin
IsEmpty := (List.head = nil);
end;
{ ************************************************************* }
FUNCTION IsFull(List: CheckList): BOOLEAN;
var
P : NodePointer;
begin
IsFull:= (SizeOf(P^) > MemAvail);
end;
{ ************************************************************* }
FUNCTION IsLast(List: CheckList): BOOLEAN;
begin
IsLast := (List.current^.next = NIL);
end;
{ ************************************************************* }
FUNCTION ListLength(List: CHeckList): integer;
begin
ListLength := List.nnodes;
end;
{ ************************************************************* }
PROCEDURE MakeEmptyList(var List: CheckList);
begin
List.head := NIL;
List.current := NIL;
List.nnodes := 0;
end;
{ ************************************************************* }
PROCEDURE DestroyList(var List: CheckList);
var
p, q: NodePointer;
begin
p := List.Head;
q := List.Head;
while (q <> nil) do
begin
q := p^.next;
Dispose(p);
p := q;
end;
List.Head := nil;
List.Current := nil;
List.nnodes := 0;
end;
{ ************************************************************* }
PROCEDURE WriteCheckToFile(aCheck: Check; var aFile: Text);
begin
with aCheck do begin
Writeln(aFile, ID);
Writeln(aFile, Date);
Writeln(aFile, Amount);
Writeln(aFile, PayTo);
Writeln(aFile, Comment);
end;
end;
PROCEDURE ReadCheckFromFile(var aCheck: Check; var aFile: Text);
begin
with aCheck do begin
Readln(aFile, ID);
Readln(aFile, Date);
Readln(aFile, Amount);
Readln(aFile, PayTo);
Readln(aFile, Comment);
end;
end;
BEGIN
END.
(bgw)