我所理解的链表

虽然使用数组可以很方便的查找每一个元素，但如果要插入或删除元素时，因为要移动大量的元素，所以需要一定的运行时间，而且代码也变的复杂。为了能够方便的删除和插入元素，我们一般不采用顺序存取结构，而采用链表存取。根据链表中结点的性质，我把它分为两种，一种是使用指针来指向它的后继（为简单起见，我暂时只讲一下单向链表，至于双向链表和循环链表，大家可以在单向链表的基础上做一定扩展即可），每一个结点的空间由系统动态分配，我们称之为动态链表；另一种是用游标（相当于指针）来指向它的后继，每一个结点的空间由程序建立的“模拟空间分配站”来分配，这个“模拟空间分配站”实际上是一个事先给定足够空间的结构数组，它为链表的结点分配空间，链表上释放的结点空间再返回给“模拟空间分配，

站”，由于这个“模拟空间分配站”的空间是由系统事先静态分配好空间的，所以称这种链表为静态链表。静态链表满足了那些不支持指针的高级语言（如BASIC和FORTRAN）需要链表的要求，它的使用方法和动态链表极为相似。

首先我们来了解动态链表。它的类型声明和基本操作如下表所示：

//-----------线性表的单链表存储结构-------------

typedef struct Node{

    ElemType data;

    struct Node *next;

} *LNode, *LinkList;

//----------线性表的单链表基本操作------------

LinkList InitList(void); //构造一个空的线性表

 

void DestroyList(LinkList *L);//初始条件：线性表L已存在。 操作结果：销毁线性表L。

 

LinkList MakeEmpty(LinkList L);//初始条件：线性表L已存在。 操作结果：将线性表L重置为空表。

 

int IsEmpty(LinkList L);//初始条件：线性表L已存在。 操作结果：判断线性表是否为空表。

 

int ListLength(LinkList L);//初始条件：线性表L已存在。 操作结果：返回线性表L结点的个数。

 

LNode IsLast(LinkList L); //初始条件：线性表L已存在。 操作结果：返回线性表L的最后一个结点（尾结点）。

LNode NewLNode(ElemType X);//构造一个数据域为X的新结点

 

LNode FindPrefious(ElemType X, LinkList L);//初始条件：线性表L已存在。 操作结果：在线性表L中寻找值为X的结点，若找到则返回该结点的前驱，否则返回NULL。

 

void ListDelete(LNode Pre);//初始条件：线性表L中结点P已找到。 操作结果：删除该结点。

 

void ListInsert(LNode Pre, LNode S);//初始条件：线性表L中结点P已找到，新结点S已构造。 操作结果：在该结点之前插入新结点X。

  ----------线性表的单链表基本操作的算法实现------------

//我给链表设置了一个头结点,虽然它的数据域毫无意义,但它作为一个指针却意义非凡!

//它的作用我们在下面的例程中可以领教

LinkList InitList(void) //构造一个空的线性表

{

    LNode Head;

         

    Head = (LNode)malloc(sizeof(struct Node)); //为链表的头结点分配空间

    if(!Head)

    {

        printf("Out of space!");

        return NULL;

    }

    Head->next = NULL;

    return Head;//返回头结点

}

 

void DestroyList(LinkList *L)//初始条件：线性表L已存在。 操作结果：销毁线性表L。

{

   LNode Head, P;

   

    if(*L)//若线性表L已存在

    {

        Head = *L;

        P = Head->next;

        while(!P)  //把链表中除头结点外的所有结点释放

        {

            free(Head);

            Head = P;

            P = Head->next;       

       }

        free(Head); //释放头结点

    }

}

     

LinkList MakeEmpty(LinkList L)//初始条件：线性表L已存在。 操作结果：将线性表L重置为空表。

{

   LNode Head, P;

 

    Head = *L;

    P = Head->next;

    while(!P)//把链表中除头结点外的所有结点释放

    {

        free(Head);

        Head = P;

        P = Head->next;    

    }

    return (Head); //返回头结点

}

 

int IsEmpty(LinkList L);//初始条件：线性表L已存在。 操作结果：判断线性表是否为空表。

{

    return L->next == NULL;

}

 

int ListLength(LinkList L)//初始条件：线性表L已存在。 操作结果：返回线性表L结点的个数。

{

    LNode P = L->next;

    int num = 0;

     

    while(P) //累积线性表L结点的个数

    {

        num++;

        P = P->next;

    }

   return num;  //返回线性表L结点的个数

}

 

//初始条件：线性表L已存在。 操作结果：返回线性表L的最后一个结点（尾结点）。

LNode IsLast(LinkList L)

{

    LNode P = L->next;

   

    if(P)

    {

        while(P->next) //遍历线性表L

            P = P->next;

    }

    return P;  //返回线性表L的最后一个结点，若为空表则返回NULL

}

 

LNode NewLNode(ElemType X)//构造一个数据域为X的新结点

{

    LNode S;

   

    S = (LNode)malloc(sizeof(struct Node))//为新结点分配空间

    if(!S)

    {

        printf("Out of space!");

        return NULL;

    }

    S->data = X;

    S->next = NULL;

    return S;//返回新结点

}

 

//线性表L已存在。 操作结果：在线性表L中寻找值为X的结点，若找到则返回该结点的前驱，否则返回NULL。

LNode FindPrefious(ElemType X, LinkList L)

{

    LNode P = L;

   

    while(P->next && P->next->data != X)//遍历链表寻找值为X的结点

        P = P->next;

    if(!P->next)  //如果找不到值为X的结点,返回NULL

        return NULL;

    else         //若找到则返回该结点的前驱P

        return P;   

}

                          

void ListDelete(LNode Pre)//初始条件：线性表L中结点P已找到。 操作结果：删除该结点。

{

    LNode P = Pre->next;

   

    Pre->next = P->next;

    free(P);

}

//初始条件：线性表L中结点P已找到，新结点S已构造。。操作结果：在该结点之前插入新结点X。

void ListInsert(LNode Pre, LNode S)

{

    S->next = Pre->next;

    Pre->next = S;

}

注意：为操作方便起见，在执行函数void ListDelete(LNode Pre, LinkList L)

和void ListInsert(LNode Pre, LNode X, LinkList L)时，通常把结点P的前驱Pre作为实参。而且这两个函数通常与函数LNode FindPrefious(ElemType X, LinkList L)一起使用，即先查找结点，再执行插入或删除操作。

以上操作为线性单链表的最基本的操作，其他操作可以是上述操作的组合。如，执行“在线性表L中寻找值为X的结点，并删除之”操作时，可先执行LNode FindPrefious(ElemType X, LinkList L)，再执行void ListDelete(LNode Pre)。 又如，执行“把一个值为X的新结点插入结点P之前”，可先执行LNode FindPrefious(ElemType X, LinkList L)，再执行LinkList NewLNode((ElemType X)，最后执行void ListInsert(LNode Pre, LNode S)。

我特意向大家推荐这种”坚持使用头结点“和“锁定前驱结点”的设计方法，这正是我和一般书本上有着不同理解的地方。有些书上的例程有时设置一个头结点，还有些根本就不使用头结点，也许是他们认为头结点占地方罢，但我认为为了更方便的编程实现我们的意图和更好的编程风格---主要指代码清晰易读，我再一次吐血推荐我的设计方法。因为这种设计方法就像一把万能钥匙---也许有些夸张了，呵呵！一般书上的例程在删除或插入结点时，要分别讨论链表头，链表中和链表尾三种不同的情况，采取不同的操作；而我上面所列的”删除“和”插入“操作可以全面搞定对链表中任意位置的结点（头结点除外）插入和删除功能。（除了”把新结点插入到链表尾“，但这可以组合执行LNode IsLast(LinkList L)和void ListInsert(LNode Pre, LNode S)）。

举一个实际的例子。已知集合A={1，2，3，4，5}，B={3，4，5，6，7，8，9，11}，求集合A和B的交集。

算法思路是先把集合A和B分别存入两个单向链表LA和LB中，以LA的结点P为研究对象，遍历LB，看是否有与其同值的结点，根据情况判断是否执行删除结点P的指令。最后得到的LA就是集合A和B的交集。

具体的实现如下所示，因为函数部分已经包含在“线性表的单链表基本操作的算法实现“中，所以不做重复，只把其他的部分列出来。程序经过测试，可以运行。

#include

#include

#include

 

typedef int ElemType;

typedef struct Node{

    ElemType data;

    struct Node *next;

} *LNode, *LinkList;

LinkList CreateList(ElemType a[], ElemType len);//用来构造一个链表

。。。//其他函数声明

int main(void)

{

   LNode LA, LB, Pre,Flag;

   ElemType X, A[5]={1,2,3,4,5}, B[8]={3,4,5,6,7,8,9,11};

   //把集合A和B分别存入两个单向链表LA和LB中

   LA = CreateList(A, 5);

   LB = CreateList(B, 8);

   //以LA的结点P为研究对象，遍历LB，看是否有与其同值的结点，根据情况判断是否执行删除结点P的指令

   Pre = LA;

   while(Pre->next)

   {

        X = Pre->next->data;

        Flag = FindPrefious(X, LB);

        if(!Flag)

            ListDelete(Pre);

        else

            Pre = Pre->next; 

    }

    //输出集合A和B的交集

    Pre = LA;

    printf("集合A和B的交集:\n");

      if(!Pre->next)

        printf("交集为空集!");

    else          

          while(Pre->next)

       {

            X = Pre->next->data;

            printf("%2d", X);

            Pre = Pre->next; 

        }

  

      system("pause");    

   return 0;

}

 

LinkList CreateList(ElemType a[], ElemType len)//用来构造一个链表

{

    LNode L, S;

    ElemType i;

     

    L = InitList(); //构造一个空的线性表

    for(i=0; i

    {

        S = NewLNode(a[i]); //构造一个数据域为a[i]的新结点

        ListInsert(L, S); //把新结点S插到头结点后面。

    }

    return L;

}