[SOLVED] algorithm lish.c

lish.c
include list.h
include stdlib.h
include fatal.h

Place in the interface file
struct Node

ElementType Element;
PositionNext;
;

List
MakeEmpty List L

if L ! NULL
DeleteList L ;
L Listmalloc sizeof struct Node;
if LNULL
FatalError Out of memory! ;
LNextNULL;
return L;

START: fig38.txt
Return true if L is empty

int
IsEmpty List L

return LNextNULL;

END

START: fig39.txt
Return true if P is the last position in list L
Parameter L is unused in this implementation

int IsLast Position P, List L

return PNextNULL;

END

START: fig310.txt
Return Position of X in L; NULL if not found

Position
Find ElementType X, List L

Position P;

1PLNext;
2while P ! NULLPElement ! X
3PPNext;

4return P;

END

START: fig311.txt
Delete from a list
Cell pointed to by PNext is wiped out
Assume that the position is legal
Assume use of a header node

void
Delete ElementType X, List L

Position P, TmpCell;

PFindPrevious X, L ;

if !IsLast P, L Assumption of header use
X is found; delete it
TmpCellPNext;
PNextTmpCellNext; Bypass deleted cell
free TmpCell ;

END

START: fig312.txt
If X is not found, then Next field of returned value is NULL
Assumes a header

Position
FindPrevious ElementType X, List L

Position P;

1PL;
2while PNext ! NULLPNextElement ! X
3PPNext;

4return P;

END

START: fig313.txt
Insert after legal position P
Header implementation assumed
Parameter L is unused in this implementation

void
Insert ElementType X, List L, Position P

Position TmpCell;

1TmpCellPositionmalloc sizeof struct Node;
2if TmpCellNULL
3FatalError Out of space!!! ;

4TmpCellElementX;
5TmpCellNextPNext;
6PNextTmpCell;

END

if 0
START: fig314.txt
Incorrect DeleteList algorithm

void
DeleteList List L

Position P;

1PLNext; Header assumed
2LNextNULL;
3while P ! NULL

4free P ;
5PPNext;

END
endif

START: fig315.txt
Correct DeleteList algorithm

void
DeleteList List L

Position P, Tmp;

1PLNext; Header assumed
2LNextNULL;
3while P ! NULL

4TmpPNext;
5free P ;
6PTmp;

END

Position
Header List L

return L;

Position
First List L

return LNext;

Position
Advance Position P

return PNext;

ElementType
Retrieve Position P

return PElement;