数据布局－单链表(C描写)

副标题#e#

list.h

typedef int ElementType;
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
List CreateList();
void DisposeList(List L);
List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
void Delete(ElementType X, List L);
Position FindPrevious(ElementType X, List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
void SetAdvance(Position P, Position NextP);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
ElementType Retrieve(Position P);
#endif // LIST_H_INCLUDED

fatal.h
#ifndef FATAL_H_INCLUDED
#define FATAL_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#define Error(Str)　　　　　　　　FatalError(Str)
#define FatalError(Str)　　 fprintf(stderr, "%s\n", Str), exit(1)
#endif // FATAL_H_INCLUDED

list.c

#p#副标题#e#

实现假定带有头节点。

#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;
}