数据结构-单链表(C描述)
2010-05-06 11:59:04 来源:WEB开发网实现假定带有头节点。
#include "list.h"
#include "fatal.h"
struct Node
{
ElementType Element;
Position Next;
};
List CreateList()
{
List L;
L = malloc(sizeof(struct Node));
if(L == NULL)
FatalError("Out of space!!!");
L->Next = NULL;
return L;
}
void DisposeList(List L)
{
MakeEmpty(L);
free(L);
}
List MakeEmpty(List L)
{
if(L == NULL)
Error("Must use CreateList first");
if(L->Next != NULL)
DeleteList(L);
return L;
}
/* Return true if L is empty */
int IsEmpty(List L)
{
return L->Next == NULL;
}
/* 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 P->Next == NULL;
}
/* Return Position of X in L; NULL if not found */
Position Find(ElementType X, List L)
{
Position P;
P = L->Next;
while(P != NULL && P->Element != X)
P = P->Next;
return P;
}
/* Delete from a list */
/* Cell pointed to by P->Next 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 = P->Next;
P->Next = TmpCell->Next; /* Bypass deleted cell */
free(TmpCell);
}
}
/* If X is not found, then Next field of returned value is NULL */
/* Assumes a header */
Position FindPrevious(ElementType X, List L)
{
Position P;
P = L;
while(P->Next != NULL && P->Next->Element != X)
P = P->Next;
return P;
}
/* 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;
TmpCell = malloc(sizeof(struct Node));
if(TmpCell == NULL)
FatalError("Out of space!!!");
TmpCell->Element = X;
TmpCell->Next = P->Next;
P->Next = TmpCell;
}
void DeleteList(List L)
{
Position P, Tmp;
P = L->Next; /* Header assumed */
L->Next = NULL;
while(P != NULL)
{
Tmp = P->Next;
free( P );
P = Tmp;
}
}
Position Header(List L)
{
return L;
}
Position First(List L)
{
return L->Next;
}
Position Advance(Position P)
{
return P->Next;
}
ElementType Retrieve(Position P)
{
return P->Element;
}
void SetAdvance(Position P, Position NextP)
{
P->Next = NextP;
}
赞助商链接