这个链表是带有表头的单链表。实现链表的一些规范操作，初始化，插入，删除等。包括两个头文件list.h，fatal.h，库函数list.c，测试函数testlist.c。头文件放的都是函数声明，库函数list.c放的的函数的定义。

头文件list.h

typedef int ElementType;
#ifndef _List_H//如果没有编译过
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
#include<stdbool.h>
List MakeEmpty(List L);
void DeleteList(List L);
bool IsEmpty(List L);
bool 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);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
ElementType Retrieve(Position P);
void PrintList(const List L);
void PrintLots(List L, List P);
void SwapWithNext(Position BeforeP, List L);
List IntersectList(List L, List P);
List UnionList(Position L, Position P);
void ReverseList(List L);
#endif // !_List_H

头文件fatal.h

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

库函数list.c

//引用头文件
#include "list.h"
#include<stdlib.h>
#include "fatal.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;
}

//删除链表
void DeleteList(List L)
{
    Position P, Temp;
    P = L->Next;
    L->Next = NULL;
    while (P != NULL)
    {
        Temp = P->Next;
        free(P);
        P = Temp;
    }
}

//判断链表是否为空
bool IsEmpty(List L)
{
    return L->Next==NULL;
}
 
//判断当前指针P是否指向链表最后一个元素
bool 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;
}

//删除链表中的元素X，若返回NULL，说明在链表中没找到元素X
void Delete(ElementType X, List L)
{
    Position P, TempCell;
    P = FindPrevious(X, L);
    if (!IsLast(P, L))//当P不是尾针，说明找到了
    {
        TempCell = P->Next;
        P->Next = TempCell->Next;
        free(TempCell);
        TempCell = NULL;
    }

}


//如果返回的P指向最后一个元素，说明没有找到，1==IsLast(P,L)
Position FindPrevious(ElementType X, List L)
{
    Position P;
    P = L;
    while (P->Next != NULL&&P->Next->Element != X)
        P = P->Next;
    return P;
}

//插入元素X到位置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;
}

//获取链表头
Position Header(List L)
{
    return L;
}

//获取链表第一个元素的位置
Position First(List L)
{
    return L->Next;
}

//获取位置P的下一个位置
Position Advance(Position P)
{
    return P->Next;
}

//提取位置P处结构里面的值
ElementType Retrieve(Position P)
{
    return P->Element;
}

//打印链表
void PrintList(const List L)
{
    Position P=Header(L);
    if (IsEmpty(L))
        printf("Empty list\n");
    else
    {
        do
        {
            P = Advance(P);
            printf("%d ", Retrieve(P));
        } while (!IsLast(P, L));
        printf("\n");
    }
}


//打印链表L中那些由P所指定的位置上的元素。例如P=1，3，4，6，将L
//中的第1，第3，第4，第6个元素打印出来
void PrintLots(List L, List P)
{
    int count = 1;
    Position Lpos, Ppos;
    Lpos = First(L);
    Ppos = First(P);
    while (Lpos != NULL&&Ppos != NULL)
    {
        if ( Ppos->Element == count++)
        {
            printf("%d ", Ppos->Element);
            Ppos = Advance(Ppos);
        }
        Lpos = Advance(Lpos);
    }


}


//通过只调整指针来交换两个相邻的元素，BeforeP是要调换两个元素的前一个指针
void SwapWithNext(Position BeforeP, List L)
{
    Position P, AfterP;
    if (BeforeP != NULL)
    {
        P = Advance(BeforeP);
        if (P != NULL)
        {
            AfterP = Advance(P);
            if (AfterP != NULL)
            {
                P->Next = AfterP->Next;
                BeforeP->Next = AfterP;
                AfterP->Next = P;
            }
        }
    }
}

//求两个链表的交集
List IntersectList(List L1, List L2)
{
    List ResultList;
    Position L1Pos, L2Pos, ResultPos;
    ResultList = MakeEmpty(NULL);
    L1Pos = First(L1);
    L2Pos = First(L2);
    ResultPos = Header(ResultList);
    while (L1Pos!=NULL&&L2Pos!=NULL)
    {
        if (L1Pos->Element < L2Pos->Element)
            L1Pos = Advance(L1Pos);
        else if (L1Pos->Element > L2Pos->Element)
            L2Pos = Advance(L2Pos);
        else
        {
            Insert(L1Pos->Element, ResultList, ResultPos);
            ResultPos= Advance(ResultPos);
            L1Pos = Advance(L1Pos);
            L2Pos = Advance(L2Pos);
        }
    }
    return ResultList;
}

//求两个链表的并集
List UnionList(Position L1, Position L2)
{
    List ResultList;
    ElementType InsertElement;
    Position L1Pos, L2Pos, ResultPos;
    ResultList = MakeEmpty(NULL);
    L1Pos = First(L1);
    L2Pos = First(L2);
    ResultPos = Header(ResultList);
    while (L1Pos != NULL&&L2Pos != NULL)
    {
        if (L1Pos->Element < L2Pos->Element)
        {
            InsertElement = L1Pos->Element;
            L1Pos = Advance(L1Pos);
        }
        else if (L1Pos->Element > L2Pos->Element)
        {
            InsertElement = L2Pos->Element;
            L2Pos = Advance(L2Pos);
        }
        else
        {
            InsertElement = L1Pos->Element;
            L1Pos = Advance(L1Pos);
            L2Pos = Advance(L2Pos);
        }
        Insert(InsertElement, ResultList, ResultPos);
        ResultPos = Advance(ResultPos);
    }
    while (L1Pos != NULL)
    {
        Insert(L1Pos->Element, ResultList, ResultPos);
        ResultPos = Advance(ResultPos);
        L1Pos = Advance(L1Pos);
    }
    while (L2Pos != NULL)
    {
        Insert(L2Pos->Element, ResultList, ResultPos);
        ResultPos = Advance(ResultPos);
        L2Pos = Advance(L2Pos);
    }
    return ResultList;
}

//将链表以O(N)进行反转链表
void ReverseList(List L)
{
    if (IsEmpty(L)||L->Next->Next==NULL)//如果链表是空或者只有一个元素，则不排序
        return;
    Position CurrentPos, PreviousPos, NextPos;
    CurrentPos = L->Next;//当前指针
    PreviousPos = NULL;//上一个指针
    NextPos = L->Next->Next;//探测指针
    while (NextPos!=NULL)//探测指针指向链表尾部时，停止循环
    {
        CurrentPos->Next = PreviousPos;//当前指针指向指向上一个指针
        PreviousPos = CurrentPos;//将上一个指针后移
        CurrentPos = NextPos;//将当前指针后移
        NextPos = Advance(NextPos);//将探测指针后移，直到触到尾指针NULL
    }
    CurrentPos->Next = PreviousPos;//最后一个指针还没有链接前一个指针
    L->Next = CurrentPos;//将头结点链接原来尾节点
}

测试函数testlist.c

#include<stdlib.h>
#include "list.h"
main()
{
    List L,L1;
    Position P,P1;
    int i;
    L = MakeEmpty(NULL);
    P = Header(L);
    PrintList(L);

    L1 = MakeEmpty(NULL);
    P1 = Header(L1);
    PrintList(L1);


    for (i = 0; i < 50; i+=2)
    {
        Insert(i, L, P);
        //PrintList(L);
        P = Advance(P);
    }
    PrintList(L);
    printf("\n");
    for (i = 1; i < 100; i+=3)
    {
        Insert(i, L1, P1);
        //PrintList(L);
        P1 = Advance(P1);
    }
    PrintList(L1);
    printf("\n");
    ReverseList(L1);
    PrintList(IntersectList(L, L1));
    printf("\n");
    PrintList(UnionList(L, L1));
    //PrintLots(L, L1);

    //SwapWithNext(L, L);//换头两个元素

    //for (i = 0; i < 10; i += 2)
    //    Delete(i, L);
    //for (i = 0; i < 10; i++)
    //{
    //    if ((i % 2 == 0) == (Find(i, L) != NULL))
    //        printf("Find fails\n");
    //}
    //printf("Finished deletions\n");
    //PrintList(L);
    DeleteList(L);
    DeleteList(L1);
    return 0;
}