古月轩    复制

链表概述

    链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。

单向链表

    单向链表的每个结点中除信息域以外还有一个指针域，用来指出其后续结点，单向链表的最后一个结点的指针域为空(NULL)。单向链表由头指针唯一确定，因此单向链表可以用头指针的名字来命名，例如头指针名为head的单向链表称为表head，头指针指向单向链表的第一个结点。在用C语言实现时，首先说明一个结构类型，在这个结构类型中包含一个(或多个)信息成员以及一个指针成员：

#define NULL 0

typedef int DATATYPE

typedef struct node

{DATATYPE info；

node *next;

}LINKLIST;

    链表结构中包含指针型的结构成员，类型为指向相同结构类型的指针。根据C语
言的语法要求，结构的成员不能是结构自身类型，即结构不能自己定义自己，因为这样将导致一个无穷的递归定义，但结构的成员可以是结构自身的指针类型，通过指针引用自身这种类型的结构。

    链表的每个结点是lINKIST结构类型的一个变量。例如定义了个链表的头指针head
和两个指向链表结点的指针p，q：

        LINKLIST *head,*P，*q;

    根据结构成员的引用方法，当p和q分别指向了链表的确定结点后，P->info和p->next分别是某个结点的信息分量和指针分量，LINKLIST结构的信息分量是整型，可以用常规的方法对这两个结点的信息分量分别赋值：

p-＞info＝20;
q-＞inFo＝30;

    指针分量是指向LINKLIST类型变量的指针，指针中将存储链表的下一个结点的存储首地址，在链表尾部的最后一个结点的指针域中，指针的值为空(NULL)。

head＝p; p-＞next＝q； q-＞next＝NULL;     经上列的赋值后，组成右图的一个链表。

    下面将以上述链表结点结构为例，给出单向链表的几种算法。

	建立单向链表     建立单向链表的算法写成为函数create()，该函数将顺序输人的一组数构造为一个首尾相接的单向链表，为将新结点放在当前链表的尾部，函数中定义了个尾指针tail，使其一直指向当前链表的尾结点。 例：建立单向链表的函数。 LINKLIST *create() {DATATYPE data;  LINKLIST *head, *tail,*node;  head＝new(LINKLIST)；  tail=head;  scanf("%d",&data);  while(data!=0);  {node=new(LINKLIST);   node->info=data;   tail->next=node;   tail=node;   scanf("%d",&data);  }  tail->next=NULL;  return head; }     在函数中首先为Head申请了—个所指向的结点，该结点称为链表的首结点。开始链表的头指针和尾指针都指向头结点(见上图)，以后每输入一个数则申请一个结点，将输入的数放到结点的信息域后，由语句tail->next＝node将该结点链接在链表的尾部。输入结束后，置链表最后一个结点的指针域为空，返回链表头指针。
	单向链表中插入结点     在单向链表中插入一个结点要引起插入位置前面结点的指针的变化、下图表示了向一个单向链表插人结点时指针的变化情况，虚线所示为变化后的指针。 例：在单向链表的p结点后面插入一个信息域的值为x的新结点。     void insert(LINKLIST*p, DATATYPE x)     {LINKLIST *newp＝new(LINKLIST);     newp-＞info＝x;     newp-＞next＝p-＞next;     p-＞next＝newp;     }     在插入一个结点时首先要由new(LINKLIST)向系统申请一个存储LINKLIST类型变量的空间，并将该空间的首地址赋给指向新结点的指针newp，在为该新结点的信息域赋值后，先要将该结点插入位置后面一个结点的指针赋给该结点的指针域，然后才能将指向该结点的指针赋给其前一个结点的指针域，这样来完成上图的插入过程。
	单向链表中删除结点     在单向链表中删除个结点同样要引起删除结点的前面结点的指针的变化，下图形象地表示了从单向链表中删除一个结点时指针的变化情况，虚线所示为变化后的指针。 例：删除单向链表结点*p后面结点。          void delete(LINKLIST *p)     {LINKKLIST *temp；      temp＝p-＞next；      p-＞next=P-＞next-＞next；      delet(temp)；     }     将指向被删除结点的指针保存在一个同类型的指针变量中，然后将其前一个结点的指针调整到指向该结点的后一个结点，最后将被删除的结点释放给系统。
	编历链表     由于链表是一个动态的数据结构，链表的各个结点由指针链接在起，访问链表元素时通过每个链表结点的指针逐个找到该结点的下一个结点，—直找到链表尾，链表的最后一个结点的指针为空。 例：编历链表函数。     void outputlist(LINKLIST *head)     LINKLIST *current＝head-＞next;     while(current！＝NULL)     {printf("%d\n",current->info);

　
   current=current->next;

     }

    return;

    }

双向链表

    每个结点中只包括一个指向下个结点的指针域，这种链表称为单向链表。如果要在单向链表一个指针所指的当前位置插入一个新结点，就必须从链表头指针开始逐个遍历直到当前指针所指结点的前一结点，修改这个结点的指针。双向链表的每个结点中包括两个指针域，分别指向该结点的前一个结点和后一个结点。在双向链表中由任何一个结点都很容易找到其前面的结点和后面的结点，而不需要在上述的插入(及删除)操作中由头结点开始寻找。定义双向链表的结点结构为

typedef struct node

{ DATATYPE info；

 node *priv, *next;

}DINKLIST；

    下面给出双向链表中插入删除一个结点的函数。操作过程见下图：

    例:将一个结点插入到双向链表指定结点之后。

insertafter(DINKLIST *current，DINKLIST *new)

{new->next=current->next;

new-＞priv＝current;

current-＞next-＞priv＝new ;

current-＞next-＞new;

}

    例:将一个结点插入到双向链表指定结点之前。

insertbefor(DINKLIST *current，DINKLIST *new)

{new-＞next＝current;

 new->priv=current->priv;　

 current-＞priv=current->priv ;

 current-＞priv=new;

}

    例:在双向链表中删除一个指定结点。

deleteelement(DINKLIST *current)

{current-＞next->priv=current->priv ;

 current-＞priv->next=current->next;

 delete(current);

}

循环链表

    单向链表的最后一个结点的指针域为空（NULL）。如果将这个指针里利用起来，以指向单向链表的第一个结点，就组成一个单向循环链表。如下图所示：

    对双向链表做类似的处理可构造一个双向循环链表。