表ADT

链表

#include<stdio.h>

#include<stdlib.h>

//链表的类型声明

struct Node;

typedef struct Node *PtrToNode;

typedef PtrToNode List;

typedef PtrToNode Position;

struct Node{

    int Element;

    Position Next;

};

//测试一个链表是否是空表的函数

int IsEmpty(List L){

    return L->Next == NULL;

}

//测试当前位置是否是链表的末尾的函数

int IsLast(Position P,List L){

    return P->Next == NULL;

}

//Find例程

Position Find(int X,List L){

    Position P;

    P = L->Next;

    while (P != NULL && P->Element != X) {

        P = P->Next;

    }

    return P;

}

//FindPrevious--为与Delete一起使用的Find例程，FindPrevious函数找出含有X的表元的前驱元P。

Position FindPrevious(int X,List L){

    Position P;

    P = L;

    while (P->Next != NULL && P->Next->Element != X) {

        P = P->Next;

    }

    return P;

}

//链表的删除例程，删除表L中的某个元素X。

void Delete(int X,List L){

    Position P,Tmpcell;

    P = FindPrevious(X, L);

    if(!IsLast(P, L)){

        Tmpcell = P->Next;

        P->Next = Tmpcell->Next;

    }

}

//链表的插入例程，将一个元素插入到由P所指示的位置之后

void Insert(int X,List L,Position P){

    Position TmpCell;

    TmpCell = malloc(sizeof(struct Node));

    if(TmpCell == NULL){

        printf("Out of space!!!\n");

    }

    TmpCell->Element = X;

    TmpCell->Next = P->Next;

    P->Next = TmpCell;

}

//删除表的正确方法

void DeleteList(List L){

    Position P,Tmp;

    P = L->Next;

    L->Next = NULL;

    while (P != NULL) {

        Tmp = P->Next;

        P = Tmp;

    }

}

int main(){

    return 0;

}

链表的游标实现

#include<stdio.h>

#include<stdlib.h>

#define SpaceSize 10

typedef int PtrToNode;

typedef PtrToNode List;

typedef PtrToNode Position;

struct Node{

    int Element;

    Position Next;

};

struct Node CursorSpace[SpaceSize];

//例程：CursorAlloc和CursorFree

static Position CursorAlloc(){

    Position P;

    P= CursorSpace[0].Next;

    return P;

}

static void CursorFree(Position P){

    CursorSpace[P].Next = CursorSpace[0].Next;

    CursorSpace[0].Next = P;

}

//测试一个链表是否为空的函数--游标实现

int IsEmpty(List L){

    return CursorSpace[L].Next == 0;

}

//测试P是否是链表的末尾的函数--游标实现

int IsLast(Position P,List L){

    return CursorSpace[P].Next == 0;

}

//例程Find--游标实现

Position Find(int X,List L){

    Position P;

    P = CursorSpace[L].Next;

    while (P && CursorSpace[P].Element != X) {

        P = CursorSpace[P].Next;

    }

    return P;

}

//对链表进行删除操作的例程Delete--游标实现

void Delete(int X,List L){

    Position P,Tmpcell;

    P = FindPrevious(X,L);

    if(!IsLast(P, L)){

        Tmpcell = CursorSpace[P].Next;

        CursorSpace[P].Next = CursorSpace[Tmpcell].Next;

        CursorFree(Tmpcell);

    }

}

//对链表进行插入操作的例程Insert--游标实现

void Insert(int X,List L,Position P){

    Position TmpCell;

    TmpCell = CursorAlloc();

    if(TmpCell == 0)

        printf("Out of space!!!");

    CursorSpace[TmpCell].Element = X;

    CursorSpace[TmpCell].Next = CursorSpace[P].Next;

    CursorSpace[P].Next = TmpCell;

}

int main(){

    return 0;

}