单链表笔记

发表于 | 分类于

list.c

#include <stdio.h>;
#include <stdlib.h>;
#define FatalError(str) fprintf(stderr, "%s\n", str),exit(1);

typedef int ElementType;
#ifndef _list_H
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

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);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
ElementType Retrieve(Position P);

#endif

struct Node {
    ElementType Element;
    Position Next;
};

List MakeEmpty(List L)
{
    if (L != NULL){
        DeleteList(L);
    }
    L = malloc(sizeof(struct Node));
    if(L == NULL){
        FatalError("Out of space!!!");
    }
    L-&gt;Next = NULL;
    return L;
}

// 测试链表是否是空链表
int IsEmpty(List L)
{
    return L-&gt;Next == NULL;
}

// 检测当前位置是否是链表的末尾
int IsLast(Position P, List L)
{
    return P-&gt;Next == NULL;
}

// 查找链表中第一次出现X的位置
Position Find(ElementType X, List L)
{
    Position P;

    P = L-&gt;Next;
    while(P != NULL &amp;&amp; P-&gt;Element != X){
        P = P-&gt;Next;
    }

    return P;
}

Position FindPrevious(ElementType X, List L)
{
    Position P;
    P = L;
    while(P-&gt;Next != NULL &amp;&amp; P-&gt;Next-&gt;Element != X){
        P = P-&gt;Next;
    }
    return P;
}

void Delete(ElementType X, List L){
    Position P, TmpCell;

    P = FindPrevious(X, L);
    if(!IsLast(P, L)){
        TmpCell = P-&gt;Next;
        P-&gt;Next = TmpCell-&gt;Next;
        free(TmpCell);
    }
}

void Insert(ElementType X, List L, Position P)
{
    Position TmpCell;
    TmpCell = malloc(sizeof(struct Node));
    if(TmpCell == NULL){
        FatalError("Out of space!!!");
    }
    TmpCell-&gt;Element = X;
    TmpCell-&gt;Next = P-&gt;Next;
    P-&gt;Next = TmpCell;
}

void DeleteList(List L)
{
    Position P, TmpCell;

    P = L-&gt;Next;
    L-&gt;Next = NULL;
    while(P != NULL){
        TmpCell = P-&gt;Next;
        free(P);
        P = TmpCell;
    }
}

Position Header(List L)
{
    return L;
}

Position First(List L)
{
    return L-&gt;Next;
}

Position Advance(Position P)
{
    return P-&gt;Next;
}

ElementType Retrieve(Position P)
{
    return P-&gt;Element;
}

void PrintList(List L)
{
    Position P = Header(L);

    if(IsEmpty(L)){
        FatalError("Empty List\n");
    }else{
        do{
            P = Advance(P);
            printf("%d ", P-&gt;Element);
        }while(!IsLast(P, L));
    }
    printf("\n");
}
`</pre>

main.c

<pre class="line-numbers prism-highlight" data-start="1">`#include "list.c"

int main()
{
    List L;
    Position P;
    L = MakeEmpty(NULL);
    P = Header(L);
    Insert(1, L, P);
    PrintList(L);
    P = Advance(P);
    Insert(2, L, P);
    PrintList(L);
    Delete(1, L);
    PrintList(L);
    DeleteList(L);
    PrintList(L);
    return 0;
}