【数据结构】链表

#include 
#include 

typedef int ElementType;
typedef struct Node *PtrToNode;
typedef PtrTonode Position;
typedef PtrTonode List;
typedef struct Node
{
    int Element;
    Position next;
}Node;



List InitList(List L);//链表初始化
List MakeEmpty(List L);//清空链表
int IsEmpty(List L);//判断链表是否为空 ，是 return true，否 return false，
int IsLast(List L,Position p);//判断p指向的地址是否为最后一个元素 ，是 return true，否 return false，
int ListLength(List L);//返回链表长度
Position Find(List L, ElementType X);//返回元素X位置上的指针
Position FindPrevious(List L, ElementType X);//返回元素X前一个位置的指针
void visit(List L);//遍历链表
void Insert(List L, ElementType X,Position p);//在指针p指向的地址插入一个元素X
void Delete(List L, ElementType X);//删除链表中的元素X
Position Header(List L);//返回表头指针
Position First(List L);//返回第一个节点指针
Position Advance(Position p);//返回下一个指针p的下一个结点指针
ElementType Retrieve(Position p);//取指针指向的元素值

List InitList(List L)
{
    L = (PtrToNode)malloc(sizeof(Node));
    if (L == NULL)
    {
        exit(0);
    }
    L->Element = 0; //L->Element 记录链表长度
    L->next = NULL;
    return L;
}

List MakeEmpty(List L)
{
    Position p,q;
    p = L->next;
    L->Element = 0;
    while(p)
    {
        q = p->next;
        free(p);
        p = q;
    }
}

int IsEmpty(List L)
{
    return L->next == NULL;
}

int IsLast(List L,Position p)
{
    return p->next == NULL;
}

int ListLength(List L)
{
    printf("链表长度 = %dn", L->Element);
    return L->Element;
}


Position Find(List L, ElementType X)
{
    Position p;
    p = L;
    while (p->next && p->Element != X)
    {
        p = p->next;
    }
    return p;
}

Position FindPrevious(List L, ElementType X) //return 0 if not found 
{
    Position p;
    p = L;
    while (p->next && p->next->Element != X)
    {
        p = p->next;
    }
    return p;
}

void visit(List L)
{
    PtrTonode p;
    p = L->next;
    while (p)
    {
        printf("%d", p->Element);
        p = p->next;
    }
    printf("n");
}

void Insert(List L, ElementType X,Position p)
{
    Position temp = (PtrToNode)malloc(sizeof(Node));
    if (temp==NULL)
        exit(0);
    temp->Element = X;
    temp->next = p->next;
    p->next = temp;
    L->Element++;
}

void Delete(List L, ElementType X)
{
    Position p,q; //仅使用指针不需要开辟地址空间（会造成内存浪费），加入使用时需要malloc开辟新地址

    p = FindPrevious(L, X);
    if(!IsLast(L,p))
    {
        L->Element--;
        q = p->next;
        p->next = p->next->next;
        free(q);
    }
}

void DeleteList(List L)
{
    Position p,q; //仅使用指针不需要开辟地址空间（会造成内存浪费），加入使用时需要malloc开辟新地址

    p = L->next;
    L->Element = 0;
    L->next = NULL;
    while(p)
    {
        q = p->next;
        free(p);
        p = q;
    }
}

Position Header(List L)
{
    return L;
}

Position First(List L)
{
    if (L->next != NULL)
        return L->next;
}

Position Advance(Position p)
{
   if (p!= NULL)
        return p->next;
}

ElementType Retrieve(Position p)
{
    if (p!= NULL)
        return p->Element;
}

int main()
{
    int i;
    List L = NULL;
    Position p;
    L = MakeEmpty(L);//要加上“L =” 
    printf("CREATED AN EMPTY linkLISTn");
    printf("%dn", IsEmpty(L));
    
    p = L;
    for (i = 1; i < 10;i++)
    {
        Insert(L, i, p);
    }
    visit(L);
    p = Find(L, 2);
    printf("%dn", p->Element);
    p = FindPrevious(L, 10);
    printf("%dn", p->Element);
    Delete(L, 1);
    visit(L);
    DeleteList(L);
    MakeEmpty(L);
    visit(L);

    return 0;
}