3.2.8 Cursor Implementation of Linked Lists
来源:百度文库 编辑:神马文学网 时间:2024/03/29 13:39:28
Many languages, such as BASIC and FORTRAN, do notsupportpointers.
The two importantitems present in a pointer implementation of linked lists are
1. The data is storedin a collection of structures. Each structure contains the data and apointerto the next structure.
2. A new structure canbe obtained from the system's global memory by a call to mallocandreleased by a call to free.
A value of 0 for next istheequivalent of a pointer.
********************************************************************
/* START: fig3_28.txt */
#ifndef _Cursor_H
#define _Cursor_H
typedef int PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
voidInitializeCursorSpace( void );
ListMakeEmpty( List L );
intIsEmpty( const List L );
intIsLast( const Position P, const List L );
Position Find( ElementType X, const List L );
voidDelete( ElementType X, List L );
Position FindPrevious( ElementType X, const List L );
voidInsert( ElementType X, List L, Position P );
voidDeleteList( List L );
Position Header( const List L );
Position First( const List L );
Position Advance( const Position P );
ElementType Retrieve( const Position P );
#endif /* _Cursor_H*/
/* END*/
********************************************************************
/*Place in the interface file */
struct Node
{
ElementType Element;
Position Next;
};
struct Node CursorSpace[ SpaceSize ];
********************************************************************
/* START: fig3_31.txt */
static Position
CursorAlloc( void )
{
Position P;
P = CursorSpace[ 0 ].Next;
CursorSpace[ 0 ].Next = CursorSpace[ P ].Next;
return P;
}
staticvoid
CursorFree( Position P )
{
CursorSpace[ P ].Next = CursorSpace[ 0 ].Next;
CursorSpace[0 ].Next = P;
}
/* END */
********************************************************************
If the value of L is 5 and thevalue of Mis 3, then L represents the list a,b,e, and M represents the list c,d,f.
********************************************************************
void
InitializeCursorSpace(void )
{
int i;
for( i = 0; i < SpaceSize; i++ )
CursorSpace[ i ].Next = i + 1;
CursorSpace[ SpaceSize - 1 ].Next = 0;
}
********************************************************************
List
MakeEmpty( List L )
{
if( L != NULL )
DeleteList( L );
L = CursorAlloc( );
if( L == 0 )
FatalError( "Out of memory!" );
CursorSpace[ L ].Next = 0;
return L;
}
********************************************************************
/* START: fig3_32.txt */
/*Return true if L is empty */
int
IsEmpty( List L )
{
return CursorSpace[ L ].Next == 0;
}
/* END */
********************************************************************
/* START: fig3_33.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 CursorSpace[ P ].Next == 0;
}
/* END*/
********************************************************************
/* START: fig3_34.txt */
/*Return Position of X in L; 0 if not found */
/*Uses a header node */
Position
Find( ElementType X, List L )
{
Position P;
/* 1*/ P= CursorSpace[L ].Next;
/* 2*/ while(P&& CursorSpace[ P ].Element != X )
/* 3*/ P = CursorSpace[ P ].Next;
/*4*/ returnP;
}
/* END */
********************************************************************
/* START: fig3_35.txt */
/*Delete from a list */
/*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 = CursorSpace[ P ].Next;
CursorSpace[ P ].Next = CursorSpace[ TmpCell ].Next;
CursorFree(TmpCell );
}
}
/* END */
********************************************************************
/*If X is not found, then Next field of returned value is 0 */
/*Assumes a header */
Position
FindPrevious( ElementType X, List L )
{
Position P;
/* 1*/ P= L;
/* 2*/ while(CursorSpace[P ].Next &&
CursorSpace[ CursorSpace[ P ].Next ].Element != X )
/*3*/ P = CursorSpace[ P ].Next;
/*4*/ returnP;
}
********************************************************************
/* START: fig3_36.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 =CursorAlloc( );
/* 2*/ if(TmpCell == 0)
/* 3*/ FatalError( "Out of space!!!" );
/* 4*/ CursorSpace[TmpCell].Element = X;
/* 5*/ CursorSpace[TmpCell].Next = CursorSpace[ P ].Next;
/* 6*/ CursorSpace[P].Next = TmpCell;
}
/* END */
********************************************************************