home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
RBBS in a Box Volume 1 #3.1
/
RBBSIABOX31.cdr
/
magn
/
ltut2.pas
< prev
next >
Wrap
Pascal/Delphi Source File
|
1990-09-29
|
32KB
|
775 lines
{
FUNCTIONS AND PROCEDURES
FOR CREATING AND ACCESSING
LINKED LISTS IN HEAPSPACE
GARRY J. VASS [72307,3311]
This file is a stand-alone TPascal program that attempts to provide
a step-by-step demo of the creation and management of a linked list
in heapspace. Comments, revisions, corrections, questions, and
suggestions should be passed on to my SIG at the POLICE STATION BSS
(201-866-7902).
INTRODUCTION
------------
Why bother with linked lists? Why not just stick everything in an
array and keep track it that way? Link lists are undoubtedly one
of the most arcane things Turbo has to offer; consider the problems
in learning linked lists:
1. The variables do not really have names in any
familar context;
2. Lists involve odd notation;
3. Lists reside in an unfamilar place, heapspace.
4. Lists need pointer variables, and those look
cumbersome.
5. Lists require odd procedures like GETMEM, NEW,
and MEMAVAIL.
6. The TURBO documentation on this subject seems
vague and inconsistent. It does not provide
an adequate conceptual foundation.
On the other hand, consider some of the advantages of lists:
1. The total data area available to your application
is limited only by the amount of RAM available
when your program starts. With arrays, your
application is limited by the size of the
data segment.
2. The sort time is reduced to that required for a
single pass of the data (no nested FOR constructs,
or bubble sorts, etc).
3. List members can be deleted much more easily than
array elements. Imagine trying to delete the
70th element of an array with 300 plus elements.
4. The device drivers, memory control blocks, etc.,
used by DOS are chained together using linked list-like
constructs and are easier to understand and process
in a linked list context.
So, on balance, lists have a useful place in any programmer's
bag of trick,s and, with an equitable foundation, they are actually
quite simple.
A pointer, for example, is roughly analogous to an array index. It
has a value in its own right, but actually refers to an address
(or offset) in memory of what is really needed. An array index,
however, contains only a part of what is needed to access the
data (we rely upon the compiler to fill in the segment and base
address of the array). A pointer variable contains a full
absolute address (segment and offset) in two words. A pointer
is declared in a way that seems to violate Turbo's syntax rules in
that a reference is made to something not yet declared. For example,
TYPE
LIST_POINTER = ^LISTREC;
(... more type declarations ...)
VAR
MYPOINTER : LIST_POINTER;
When the compiler reaches this statement, it trusts that something
called LISTREC will be defined in the next statement. The english
translation for this example is "Variables of type LIST_POINTER
will contain two word, segment/offset addresses corresponding
to the locations of variables of the type LISTREC. Variables
of the type LISTREC will not reside in the data segment like
static variables. Rather, they will reside in heapspace. MYPOINTER
is a variable that can contain any segment/offset address, but will
contain the address of a specific member of a list (of type LISTREC)."
To get the next element in an array, we usually just add one to the
index. To get the next element in a linked list, we need to know
its address. To accomplish this then, each member of a linked list
must have some address information, namely the address of the
next member. For this reason, a RECORD structure is frequently used
to define list members, such as:
TYPE
ANYSTRING = STRING[255];
LIST_POINTER = ^LISTREC;
LISTREC = RECORD
POINTER_TO_NEXT_MEMBER: LIST_POINTER;
MEMBER_DATA : ANYSTRING;
END;
VAR
MYPOINTER : LIST_POINTER;
ROOT : LIST_POINTER;
LIST : LISTREC;
This translates into, "each member of my linked list will occupy
260 bytes of memory:
POINTER_TO_NEXT_MEMBER 4 bytes
MEMBER_DATA
(Turbo's length byte) 1 byte
(String part) 255 bytes
Further, each member will reside in contiguous heapspace, and each
member will contain the address of the next member. The variable,
ROOT, will be used to hold the address of the first member added to
the list ('list entry point'). With the value of ROOT, the first
list member can be accessed. Once the first record is accessed, the
pointer to the next record can be obtained. When that record is
obtained, the pointer to the third record can be found, and so on".
ROOT, then, corresponds roughly to the first element of an array.
To learn the last element in an array, we frequently use a counter
in a context like "FOR I := 1 TO NAME_COUNT DO ...". In linked
lists, the last member is signified by all zeros in the
POINTER_TO_NEXT_MEMBER element. Turbo uses a pre-defined constant
called, "NIL" for this. Using the above example, compare these
constructs:
last element of array last member of a list
I := I + 1; MYPOINTER := MYPOINTER^.POINTER_TO_NEXT_MEMBER;
IF I = NAME_COUNT THEN IF MYPOINTER = NIL THEN
BEGIN BEGIN
(last element is reached) (last member is reached)
The translation for the statements on the right is "MYPOINTER is currently
pointing to a list member. Take the value of the POINTER_TO_NEXT_MEMBER element
from this record and put it in MYPOINTER. If this is NIL, then..."
With these concepts, we can now transverse a linked list in a line-by-line
analogy to array processing:
array logic linked list logic
I := 1; MYPOINTER := ROOT;
REPEAT REPEAT
WRITELN(NAMES[I]); WRITELN(MYPOINTER^.MEMBER_DATA);
I := SUCC(I); MYPOINTER := MYPOINTER^.POINTER TO NEXT MEMBER;
UNTIL I > NAME_COUNT; UNTIL MYPOINTER = NIL;
To add an element/member:
array logic linked list logic
NAME_COUNT := SUCC(NAME_COUNT); NEW(MYPOINTER);
NAMES[NAME_COUNT] := 'Mr. Kahn'; MYPOINTER^.MEMBER_DATA := 'Mr. Kahn';
MYPOINTER^.POINTER_TO_NEXT_MEMBER := NIL;
(logic for setting pointer
in previous record goes here).
Beyond these examples, the analogies tend to break down. The logic for
sorting an array tends to involve a physical rearrangement of the data
through an iterative process. A linked list is usually sorted as
it is created by reassigning the pointers. The upper bound of an
array is bound to a constant. The capacity of a list is tied to
available heapspace.
To maximize the value of this program, I suggest that it be run
in its native form (i.e., as you found it - which is hopefully
not altered) several times and observe the dynamics/interaction
of the generic routines. Then copy this program into your own
file and modify the list building routines to create various
situations, such as a stack/heap collisions, duplicate records,
multiple lists, different sort key types, and so on. It is also
important to note that several particularly elegant uses of
pointer variables that are not list related can be found on "GO BOR"
(try MAPMEM.PAS by TurboPower for a flagship example).
TREATMENT
---------
The linked list used here is composed of three elements. The first
is an index (or sort key). The values in this element determine
how the list is to be sorted. I have used an integer type here,
but this element can just as easily be redefined as a string type.
In addition to being the sort key for the list, the index element
is also used as a search argument in the lookup function. The
next element is the so-called "data part", which contains all the
relevant information associated with the index value. Naturally, this
element can also be redefined to meet specific applications. The last
element is a pointer variable that can hold one of two values:
1. the NIL value, a special value indicating that
this record is the last item in the list. NIL
is represented internally by four zero filled
bytes; or
2. a pointer to the location of the next item in the
list. These four bytes are represented internally
(as are all pointers) as:
- low order offset;
- high order offset;
- low order segment;
- high order segment;
It is IMPORTANT to note that the physical location
of a pointer or list member has NOTHING to do with
its sorted (or logical) location in the list.
Physical addresses are assigned at the next available
heapspace location in the order that you ask for them.
This means that the root record (or logical entry point)
of a list could be located at a higher physical address than
any of the other members in the same list.
Most of the procedures and functions given below deal with the
assignment of these pointers. Filling the index and data parts
is up to you. To build a list of names and ages
with age as the index, for example, the following code could be
used:
list.index_part := 28; (* age *)
list.data_part := 'Sally Maxwell';
add_member(list);
list.index_part := 27; (* age *)
list.data_part := 'Jane Robinson';
add_member(list);
etc, etc, etc....
The add_member procedure finds the appropriate place in the
list, plugs your record there, and figures out to modify the
pointers.
Once the list has been constucted, several things can be
done:
1. Look up a member of the list based upon the
the index value (procedure lookup_member).
2. Delete a member of the list based upon
the index value (procedure delete_member).
3. Process the entire list in sorted order
(procedure process_list).
4. Dispose of the entire list (procedure dispose_list).
When reading through linked list code, one encounters odd notation
such as the carat, ^. I use the following translations:
P^ That which is pointed to by P.
P^ := X That which is pointed to by P is X.
P^.A The A element of the record pointed
to by P.
P^ := P^.M^ P now points to same thing as the M pointer
element of the record being pointed to by P.
NEW(W) Create a new record in heapspace. Assignments
for the record elements to go in this area will
soon follow, and will be issued in the form...
W^.INDEX :=
W^.DATA :=
}
PROGRAM LINKED_LISTS;
CONST
FOREVER:BOOLEAN = FALSE; { FOR CREATING STACK/HEAP COLLISIONS }
TYPE
ANYSTRING = STRING[255];
LISTPTR = ^LISTREC;
LISTREC = RECORD
NEXT_POINTER : LISTPTR;
INDEX_PART : INTEGER;
DATA_PART : ANYSTRING;
END;
VAR
{ Define a global variable to hold the root address,
or entry point of the list. The concept of a root
variable means "this variable holds the logical
entry point into the list".}
ROOT: LISTPTR;
{ Define a global variable to enable the construction
of the list.}
LIST: LISTREC;
{ Extra pointer for general use }
TEMPTR:LISTPTR;
ANYINTEGER:INTEGER;
ANYCH:CHAR;
{--------------------- GENERAL SUPPORT ROUTINES ----------------------}
{ These routines are not of immediate interest and are included in compressed format.}
FUNCTION HEXBYTE(N:INTEGER):ANYSTRING;CONST H:ANYSTRING='0123456789ABCDEF';BEGIN HEXBYTE:=H[((LO(N)DIV 16)MOD 16)+1]+
H[(LO(N)MOD 16)+1];END;FUNCTION HEXWORD(N:INTEGER):ANYSTRING;BEGIN HEXWORD:=HEXBYTE(HI(N))+HEXBYTE(LO(N));END;
FUNCTION CONV(I:INTEGER):REAL;BEGIN CONV:=256.0*HI(I)+LO(I);END;PROCEDURE PAUSE;VAR CH:CHAR;BEGIN WRITELN;
WRITELN('-- PAUSING FOR KEYBOARD INPUT...');READ(KBD,CH);WRITELN;END;
{--------------------- END OF GENERAL SUPPORT ROUTINES ----------------}
{ Linked lists reside in heapspace, an area of unused memory
at the low end of the stack/data segment. The beginning of
available heapspace changes according to two factors:
1. how much is on the stack; and
2. how much heapspace has already been grabbed.
Our friends at Borland were thoughtful enough to provide
a pre-defined variable that points to the beginning of heapspace,
this variable is called, "HEAPPTR", and is configured with four bytes
just like the pointer layout described above. You can use the
VALUEOF(HeapPtr) function at various points in the program to
examine Turbo's behavior in setting and assigning this rather
ephermeral item. Unfortunately the standard variable, StackPtr,
as described in the documentation, is more elusive and not
compatable with VALUEOF.
When heapspace is requested (with the NEW procedure), the HEAPPTR
variable will be reset to the next available location in
memory so that it will always point to the beginning of
available heapspace. If enough heapspace is requested,
this variable will ultimately be equal to, or greater than
the stack pointer. This situation creates a run-time
"stack/heap collision" and the program dies. To avoid
this, the MEMAVAIL function should be used before the
NEW procedure to assure that enough heapspace is available.
}
{------------------- LINKED LIST SUPPORT ---------------------
These routines help show what is happening as the list is being
constructed. They are not needed for an application.
}
PROCEDURE SNAPMEM(X, Y:INTEGER); { PUTS AVAILABLE HEAPSPACE }
BEGIN { AT COLUMN X, ROW Y }
GOTOXY(X, Y);
CLREOL;
WRITELN('HEAP SPACE = ',CONV(MEMAVAIL)*16.0:8:0);
END;
FUNCTION VALUEOF(P:LISTPTR):ANYSTRING; { RETURNS A STRING IN }
{ SEGMENT:OFFSET FORMAT }
{ WHICH CONTAINS VALUE }
BEGIN { OF A POINTER VARIABLE }
VALUEOF := HEXBYTE(MEM[SEG(P):OFS(P) + 3]) +
HEXBYTE(MEM[SEG(P):OFS(P) + 2]) +':'+
HEXBYTE(MEM[SEG(P):OFS(P) + 1]) +
HEXBYTE(MEM[SEG(P):OFS(P) + 0]);
END;
PROCEDURE GIVESTATS; { REPORTS STATISTICS FOR DEMO PROGRAM }
BEGIN
WRITELN('HEAP SPACE NOW BEGINS AT ',VALUEOF(HEAPPTR),
' AND EXTENDS FOR ',CONV(MEMAVAIL) * 16.0:8:0,' BYTES');
PAUSE;
END;
PROCEDURE SNAP_MEMBER(POINTER:LISTPTR); { PRINTS THE LIST MEMBER }
BEGIN { BEING POINTED TO BY "POINTER"}
IF POINTER = NIL THEN
BEGIN
WRITELN('----------- EMPTY LIST -------------');
EXIT;
END;
WRITELN('--------------- LIST MEMBER INFORMATION ------------');
WRITELN('THE INDEX OF THIS RECORD IS ', POINTER^.INDEX_PART);
WRITELN('THE DATA IN THIS RECORD IS ', POINTER^.DATA_PART);
WRITELN('MEMORY LOCATION OF THIS RECORD IS ',VALUEOF(POINTER));
WRITELN('THIS RECORD IS POINTING TO A RECORD AT ',VALUEOF(POINTER^.NEXT_POINTER));
PAUSE;
END;
{--------------------- END OF LINKED LIST SUPPORT ---------------------}
{--------------------- GENERIC LINKED LIST ROUTINES --------------------}
{ When adding a member to a linked list, four situations can occur.
1. The list is empty/uninitialized.
2. The new record must be added to a place
before the existing root record.
3. The new record must be inserted somewhere
in the middle of the list.
4. The new record must be inserted
at the end of the list.
The add_member procedure below recognizes each of these four
situations and adjusts the list accordingly.
}
PROCEDURE ADD_MEMBER (TARGET:LISTREC); { ADDS THE TARGET RECORD TO }
VAR { LINKED LIST }
MOVING_POINTER : LISTPTR;
POINTER_TO_PRIOR_RECORD : LISTPTR;
BEGIN
{Assure that sufficient memory is available for the target member}
IF ((CONV(MEMAVAIL) * 16.0) < CONV(SIZEOF(TARGET))) THEN
BEGIN
WRITELN('---------- NO MORE MEMORY ---------------');
EXIT;
END;
WRITELN;
WRITELN('------------- ADDING A RECORD TO THE LIST ----------');
WRITELN;
WRITELN('INDEX VALUE IS ',TARGET.INDEX_PART,' DATA IS ',TARGET.DATA_PART);
{ Logic for adding the first record to a list }
IF ROOT = NIL THEN
BEGIN
{ Allocate some memory for the root pointer }
NEW(ROOT);
{ Assign NIL to the last record in the list }
TARGET.NEXT_POINTER := NIL;
{ Root points to the record in TARGET }
ROOT^ := TARGET;
WRITELN('THIS RECORD INITIALIZED THE LIST AT ',VALUEOF(ROOT));
GIVESTATS;
EXIT;
END;
{ Logic for adding a record "in front of" the current root }
IF (TARGET.INDEX_PART) <= (ROOT^.INDEX_PART) THEN
BEGIN
{ Set pointer in new record to point to the root }
TARGET.NEXT_POINTER := ROOT;
{ Allocate some memory for a new root pointer }
NEW(ROOT);
{ Root points to the record in TARGET }
ROOT^ := TARGET;
WRITELN('THIS RECORD BECAME THE NEW ROOT AT ',VALUEOF(ROOT));
WRITELN('THIS RECORD POINTS TO THE OLD ROOT AT ',VALUEOF(ROOT^.NEXT_POINTER));
GIVESTATS;
EXIT;
END;
{ Logic for adding a record to "the middle of" a list }
MOVING_POINTER := ROOT;
REPEAT
POINTER_TO_PRIOR_RECORD := MOVING_POINTER;
MOVING_POINTER := MOVING_POINTER^.NEXT_POINTER;
IF (MOVING_POINTER <> NIL) THEN
IF ((TARGET.INDEX_PART) <= (MOVING_POINTER^.INDEX_PART))
THEN
BEGIN
NEW(POINTER_TO_PRIOR_RECORD^.NEXT_POINTER);
TARGET.NEXT_POINTER := MOVING_POINTER;
POINTER_TO_PRIOR_RECORD^.NEXT_POINTER^ := TARGET;
WRITELN('THIS RECORD WAS INSERTED INTO THE MIDDLE OF THE LIST ',
'AT ',VALUEOF(POINTER_TO_PRIOR_RECORD^.NEXT_POINTER));
GIVESTATS;
EXIT;
END;
UNTIL MOVING_POINTER = NIL;
{APPEND TO END OF LIST }
NEW(MOVING_POINTER);
TARGET.NEXT_POINTER := NIL;
POINTER_TO_PRIOR_RECORD^.NEXT_POINTER := MOVING_POINTER;
MOVING_POINTER^ := TARGET;
WRITELN('THIS RECORD WAS ADDED TO THE END OF THE LIST AT ',VALUEOF(POINTER_TO_PRIOR_RECORD^.NEXT_POINTER));
GIVESTATS;
END;
FUNCTION LAST_MEMBER:LISTPTR; { RETURNS POINTER TO LAST LIST MEMBER }
VAR P:LISTPTR;
BEGIN
P := ROOT;
IF P = NIL THEN
BEGIN
LAST_MEMBER := NIL;
EXIT;
END;
REPEAT
IF P^.NEXT_POINTER <> NIL THEN P := P^.NEXT_POINTER;
UNTIL P^.NEXT_POINTER = NIL;
LAST_MEMBER := P;
END;
PROCEDURE ROTATE_LIST_LEFT; { ROTATES ENTIRE LIST LEFT, ROOT BECOMES }
VAR P1:LISTPTR; { TAIL, TAIL BECOMES PENULTIMATE, ETC. }
P2:LISTPTR;
TR:LISTPTR;
R1:LISTREC;
BEGIN
IF (ROOT = NIL) OR (ROOT^.NEXT_POINTER = NIL) THEN EXIT;
R1.DATA_PART := ROOT^.DATA_PART;
R1.INDEX_PART := ROOT^.INDEX_PART;
R1.NEXT_POINTER := NIL;
TR := ROOT^.NEXT_POINTER;
DISPOSE(ROOT);
ROOT := TR;
NEW (P1);
P1^ := R1;
P2 := LAST_MEMBER;
P2^.NEXT_POINTER := P1;
END;
PROCEDURE MAKE_NEW_HEAD(P:LISTPTR); { FIXES LIST SO THAT RECORD WITH POINTER }
BEGIN { "P" IS THE ROOT RECORD. ASSUMES "P" }
IF (ROOT = NIL) OR { EXISTS. }
(ROOT^.NEXT_POINTER = NIL) THEN EXIT;
REPEAT
ROTATE_LIST_LEFT;
UNTIL ROOT = P;
END;
FUNCTION LIST_COUNT:INTEGER; { RETURNS LIST MEMBER COUNT }
VAR
P:LISTPTR;
I:INTEGER;
BEGIN
IF ROOT = NIL THEN
BEGIN
LIST_COUNT := 0;
EXIT;
END;
I := 0;
P := ROOT;
REPEAT
I := SUCC(I);
P := P^.NEXT_POINTER;
UNTIL P = NIL;
LIST_COUNT := I;
END;
FUNCTION PENULTIMATE:LISTPTR; { RETURNS PENULTIMATE LIST MEMBER }
VAR { OR NIL IF NO PENULTIMATE }
P1:LISTPTR;
P2:LISTPTR;
BEGIN
IF ROOT = NIL THEN
BEGIN
PENULTIMATE := NIL;
EXIT;
END;
IF LIST_COUNT <= 2 THEN
BEGIN
PENULTIMATE := ROOT;
EXIT;
END;
P1 := ROOT;
P2 := ROOT^.NEXT_POINTER;
REPEAT
P1 := P2;
P2 := P2^.NEXT_POINTER;
UNTIL P2 = LAST_MEMBER;
PENULTIMATE := P1;
END;
PROCEDURE KILL_MEMBER(P:LISTPTR); { DELETES LIST MEMBER POINTED TO }
VAR P1:LISTPTR; { BY "P". EXITS IF THE LIST CONTAINS }
P2:LISTPTR; { LESS THAN TWO MEMBERS. }
BEGIN
IF ROOT = NIL THEN EXIT;
IF ROOT^.NEXT_POINTER = NIL THEN EXIT;
IF P = ROOT THEN
BEGIN
P1 := ROOT^.NEXT_POINTER;
DISPOSE(P);
ROOT := P1;
EXIT;
END;
IF P = LAST_MEMBER THEN
BEGIN
P1 := PENULTIMATE;
DISPOSE(P);
P1^.NEXT_POINTER := NIL;
EXIT;
END;
P1 := ROOT;
REPEAT
P2 := P1;
IF P1^.NEXT_POINTER <> NIL THEN P1 := P1^.NEXT_POINTER;
UNTIL (P1 = NIL) OR
(P1 = P);
IF P1 = NIL THEN EXIT;
P2^.NEXT_POINTER := P1^.NEXT_POINTER;
DISPOSE(P1);
END;
FUNCTION LOOKUP_MEMBER(IND:INTEGER):LISTPTR; { RETURNS THE POINTER }
VAR { CONTAINING THE RECORD }
MOVING_POINTER:LISTPTR; { WHOSE INDEX VALUE IS }
BEGIN { EQUAL TO "IND". IF NO }
MOVING_POINTER := ROOT; { RECORD EXISTS, RETURNS }
REPEAT { NIL. }
IF MOVING_POINTER^.INDEX_PART = IND THEN
BEGIN
LOOKUP_MEMBER := MOVING_POINTER;
EXIT;
END;
MOVING_POINTER := MOVING_POINTER^.NEXT_POINTER;
UNTIL MOVING_POINTER = NIL;
LOOKUP_MEMBER := NIL;
END;
{------------------ END OF GENERIC LIST PROCEDURES -------------}
{--------------- PRESENTATION PROCEDURES AND ENGINE ----------}
PROCEDURE PROCESS_LIST; { WALKS THROUGH THE LIST, }
{ FROM ROOT TO NIL. }
{ IMPORTANT NOTE ABOUT LIST PROCESSING!!!!
Once a list has been created you can still have a stack/heap
collision where the stack is the culprit! Remember that each
call to a function or procedure moves the stack downward
closer to your list. For this reason, extra care must be
taken to assure that the routines for list processing programs
are sufficiently "shallow" (not nested too deep, not overly
recursive, etc). }
VAR
MOVING_POINTER:LISTPTR;
BEGIN
CLRSCR;
{ }
{ YOUR LIST PROCESSING ROUTINES GO HERE }
{ }
IF ROOT = NIL THEN
BEGIN
WRITELN('-------------- EMPTY LIST -------------');
EXIT;
END;
WRITELN;
WRITELN(' ---------------- CURRENT LIST CONTENTS -------------- ');
WRITELN;
WRITELN('INDEX DATA LOCATION OF RECORD LOCATION OF NEXT');
WRITELN('VALUE VALUE IN MEMORY RECORD IN MEMORY');
WRITELN('----- -------------------- --------- ----------------');
MOVING_POINTER := ROOT;
REPEAT
{ LIST PROCESSING CODE GOES HERE }
WRITELN(MOVING_POINTER^.INDEX_PART:5,
MOVING_POINTER^.DATA_PART :20,
VALUEOF(MOVING_POINTER):20,
VALUEOF(MOVING_POINTER^.NEXT_POINTER):30);
MOVING_POINTER := MOVING_POINTER^.NEXT_POINTER;
UNTIL MOVING_POINTER = NIL;
WRITELN;
WRITELN('THE LIST COUNT IS ',LIST_COUNT);
IF ROOT = NIL THEN WRITELN('----- EMPTY LIST ----')
ELSE WRITELN('THE ROOT MEMBER IS ',ROOT^.DATA_PART);
MOVING_POINTER := PENULTIMATE;
IF MOVING_POINTER <> NIL
THEN WRITELN('THE PENULTIMATE MEMBER IS ',MOVING_POINTER^.DATA_PART)
ELSE WRITELN('THERE IS NO PENULTIMATE MEMBER');
MOVING_POINTER := LAST_MEMBER;
WRITELN('THE LAST MEMBER IS ',MOVING_POINTER^.DATA_PART);
PAUSE;
END;
PROCEDURE BUILD_A_LIST;
BEGIN
{ }
{ YOUR LIST BUILDING LOGIC GOES HERE }
{ }
LIST.INDEX_PART := 25; LIST.DATA_PART := 'George Wilson '; ADD_MEMBER(LIST); PROCESS_LIST;
LIST.INDEX_PART := 21; LIST.DATA_PART := 'Walter Thompson'; ADD_MEMBER(LIST); PROCESS_LIST;
LIST.INDEX_PART := 28; LIST.DATA_PART := 'James McCoy '; ADD_MEMBER(LIST); PROCESS_LIST;
LIST.INDEX_PART := 22; LIST.DATA_PART := 'Robert Henton '; ADD_MEMBER(LIST); PROCESS_LIST;
LIST.INDEX_PART := 31; LIST.DATA_PART := 'Dennis Campbell'; ADD_MEMBER(LIST); PROCESS_LIST;
LIST.INDEX_PART := 20; LIST.DATA_PART := 'Jack Farrell '; ADD_MEMBER(LIST); PROCESS_LIST;
LIST.INDEX_PART := 24; LIST.DATA_PART := 'Herbert Walker '; ADD_MEMBER(LIST); PROCESS_LIST;
END;
{----------------- BEGINNING OF MAINLINE ------------------------}
{------------------------ DEMO ----------------------------------}
BEGIN
CLRSCR;
WRITELN('PROGRAM IS LOADED AT ',HEXWORD(CSEG));
WRITELN('DATA SEGMENT IS AT ',HEXWORD(DSEG));
WRITELN('STACK SEGMENT IS AT ',HEXWORD(SSEG));
WRITELN('HEAP SPACE BEGINS AT ',VALUEOF(HEAPPTR),
' AND EXTENDS FOR ', CONV(MEMAVAIL) * 16.0:8:0,
' BYTES');
WRITELN('LINKED LIST RECORD SIZE IS ',SIZEOF(LIST),' BYTES');
PAUSE;
ROOT := NIL;
WRITELN('BEGIN BUILDING A LINKED LIST');
PAUSE;
BUILD_A_LIST;
REPEAT
WRITELN('DO YOU WANT TO ROTATE THE LIST (Y/N)?');
GOTOXY(50, WHEREY - 1);
READ(KBD,ANYCH);
IF UPCASE(ANYCH) = 'Y' THEN
BEGIN
ROTATE_LIST_LEFT;
PROCESS_LIST;
END;
UNTIL UPCASE(ANYCH) <> 'Y';
WRITELN;
WRITELN('NOW SEARCH FOR LIST MEMBERS');
PAUSE;
REPEAT
PROCESS_LIST;
WRITELN('PLEASE ENTER AN AGE TO SEARCH FOR (OR ZERO TO QUIT): ');
GOTOXY(55, WHEREY - 1);
READLN(ANYINTEGER);
IF ANYINTEGER <> 0 THEN
BEGIN
WRITELN;
TEMPTR := LOOKUP_MEMBER(ANYINTEGER);
IF TEMPTR = NIL THEN
BEGIN
WRITELN('NO ONE OF AGE ',ANYINTEGER);
PAUSE;
END
ELSE SNAP_MEMBER(TEMPTR);
END;
UNTIL ANYINTEGER = 0;
WRITELN('NOW DELETE LIST MEMBERS');
PAUSE;
REPEAT
PROCESS_LIST;
WRITELN('PLEASE ENTER AN AGE TO DELETE (OR ZERO TO QUIT): ');
GOTOXY(55, WHEREY - 1);
READLN(ANYINTEGER);
IF ANYINTEGER <> 0 THEN
BEGIN
WRITELN;
TEMPTR := LOOKUP_MEMBER(ANYINTEGER);
IF TEMPTR = NIL THEN
BEGIN
WRITELN('NO ONE OF AGE ',ANYINTEGER);
PAUSE;
END
ELSE KILL_MEMBER(LOOKUP_MEMBER(ANYINTEGER));
END;
UNTIL (ANYINTEGER = 0) OR (ROOT = NIL);
PROCESS_LIST;
END.
{----------------------- END OF MAINLINE ---------------------------}
APPLICATIONS:
With no effort at all, you can use these procedures to develop an improved
DOS sort filter. Consider the following list record:
LISTREC = RECORD
INDEX_PART : ANYSTRING; { Load this according }
{ to your specs }
DATA_PART : ANYSTRING; { Line from ASCII file }
NEXT_PART : POINTER;
END;
With the numerous directory procedures available at "GO BOR", you can
develop customized directory sort programs. A sort by file size, for
example, might have the following records:
DIRREC = RECORD
ATTRIBUTE : BYTE;
NAME : ANYSTRING;
EXTENSION : ANYSTRING;
DATE : DATEREC; { or whatever you want }
TIME : TIMEREC; { " " " " }
FST_CLUSTER : INTEGER;
END;
LISTREC = RECORD
INDEX_PART : REAL; { Holds file size }
DATA_PART : DIRREC;
NEXT_PART : POINTER;
END;
