lish.c
include list.h
include stdlib.h
include fatal.h
Place in the interface file
struct Node
ElementType Element;
Position Next;
;
List
MakeEmpty List L
if L ! NULL
DeleteList L ;
L List malloc sizeof struct Node ;
if L NULL
FatalError Out of memory! ;
LNext NULL;
return L;
START: fig38.txt
Return true if L is empty
int
IsEmpty List L
return LNext NULL;
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 PNext NULL;
END
START: fig310.txt
Return Position of X in L; NULL if not found
Position
Find ElementType X, List L
Position P;
1 P LNext;
2 while P ! NULL PElement ! X
3 P PNext;
4 return 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;
P FindPrevious X, L ;
if !IsLast P, L Assumption of header use
X is found; delete it
TmpCell PNext;
PNext TmpCellNext; 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;
1 P L;
2 while PNext ! NULL PNextElement ! X
3 P PNext;
4 return 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;
1 TmpCell Positionmalloc sizeof struct Node ;
2 if TmpCell NULL
3 FatalError Out of space!!! ;
4 TmpCellElement X;
5 TmpCellNext PNext;
6 PNext TmpCell;
END
if 0
START: fig314.txt
Incorrect DeleteList algorithm
void
DeleteList List L
Position P;
1 P LNext; Header assumed
2 LNext NULL;
3 while P ! NULL
4 free P ;
5 P PNext;
END
endif
START: fig315.txt
Correct DeleteList algorithm
void
DeleteList List L
Position P, Tmp;
1 P LNext; Header assumed
2 LNext NULL;
3 while P ! NULL
4 Tmp PNext;
5 free P ;
6 P Tmp;
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;