链表---C实现（带头节点）

代码来自 数据结构与算法分析（C语言描述）, 非原创

头节点的作用

1. 使每个节点的操作都相同，不必单独为第一个节点写特殊的操作。
2. 空表和非空表的头指针都指向头节点，可以同样处理

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.h

#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED

typedef int ElementType;

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

List MakeEmpty(List L);		//创建一个空链表
int IsEmpty(List L);		//判断链表是否为空
Position Find(ElementType X, List L);		//查找第一个元素大小为X的节点地址
void Delete(ElementType X, List L);		//删除第一个元素大小为X的节点地址
Position FindPrevious(ElementType X, List L);		//查找元素大小为X的节点的前一个节点
void Insert(ElementType X, List L, Position P);		//在位置P插入一个元素值为X的新节点
void DeleteList(List L);		//销毁链表，包括头节点


#endif // LIST_H_INCLUDED

list.c

#include"list.h"
#include"fatal.h"
#include<stdlib.h>

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 memory!");
    L->Next = NULL;
    return L;
}

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

Position Find(ElementType X, List L){
    Position P;

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

    return P;
}

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

    P = FindPrevious(X, L);

    if(P->Next != NULL){
        TmpCell = P->Next;
        P->Next = TmpCell->Next;
        free(TmpCell);
    }
}

Position FindPrevious(ElementType X, List L){
    Position P;

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

    return P;
}

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 = L->Next;
    Position TmpCell;

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

void PrintList(List L){
    Position P = L;
    while(P->Next != NULL){
        printf("%d ",P->Next->Element);
        P = P->Next;
    }
    printf("\n");
}

int main(){
    //printf("------------1\n");
    List L = NULL;
    printf("---------------------测试MakeEmpty\n");
    L = MakeEmpty(L);
    printf("---------------------测试IsEmpty\n");
    printf("%d\n",IsEmpty(L));
    printf("---------------------测试Insert\n");
    Position P = L;
    for(int i = 0; i < 5; i ++){
        Insert(i, L, P);
        P = P->Next;
    }
    PrintList(L);
    printf("---------------------测试Find\n");
    Position p1 = Find(1,L);
    printf("%d\n",p1->Element);
    printf("---------------------测试FindPrevious\n");
    Position p2 = FindPrevious(1,L);
    printf("%d\n",p2->Element);
    printf("---------------------测试DeleteList\n");
    DeleteList(L);
    return 0;
}