数据结构之线性表（链式表示）

在上篇博文中，我们介绍了线性表的顺序存储，本文将介绍其链式表示方式。
由于顺序表的插入、删除操作都需要移动大量的元素，这极大的影响了运行效率，所以引进了线性表的链式表示。链式存储线性表时，不需要使用地址连续的存储单元，对线性表的插入删除操作只需要修改指针，不需要移动元素。

我们将介绍4种链表形式：

单链表
双链表
循环链表
静态链表

单链表

线性表的链式存储又称单链表。它是通过一组任意的存储单元来存储线性表中的数据元素。对于每个链表结点，除了存放元素自身信息外（数据data），还需要存放一个指向其后继的指针（指针next）。

单链表中结点类型的描述如下：

typedef struct LNode{
    ElemType data;        //数据域
    struct LNode *next;   //指针域
}LNode,*LinkList;

注意：单链表是非随机存取的存储结构，查找某个特定结点时，需要从表头开始遍历，依次查找。
通常用头指针来标识一个单链表。为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等相关信息。头结点的指针域指向线性表的第一个元素结点。

头结点和头指针的区别：

不管带不带头结点，头指针始终指向链表的第一个结点
头结点是带头结点链表的第一个结点，结点内通常不存储信息

引入头结点的优点：

开始结点的位置被放在头结点的指针域中，链表的第一个位置上的操作和其他位置上的操作一致，无须进行特殊处理
无论链表是否为空，头指针都是指向头结点的非空指针（空表中头结点指针域为空），这样空表和非空表处理统一了

头插法建立单链表：O(n)
该方法从一个空表开始，生成新结点，将新结点插入到当前链表的表头，如下所示：

LinkList CreatList1(LinkList &L){
    LNode *s;int x;
    L=(LinkList)malloc(sizeof(LNode));    //创建头结点
    L->next=NULL;
    scanf("%d",&x);                       //输入值
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode));  //创建新结点
        s->data=x;
        s->next=L-next;
        L-next=s;                        //将新结点插入表L中
        scanf("%d",&x);
    }
    return L;
}

采用头插法建立单链表，读入数据的顺序与生成的链表中的元素顺序是相反的。

尾插法建立单链表：O(n)
将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，让它始终指向当前链表的尾结点。如下所示：

LinkList CreatList2(LinkList &L){
    int x;
    L=(LinkList)malloc(sizeof(LNode)); 
    LNode *s,*r=L;                           //r为表尾指针
    scanf("%d",&x); 
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode)); 
        s->data=x;
        r->next=s;
        r=s;                               //r指向新的表尾结点
        scanf("%d",&x);
    }
    r->next=NULL;                          //尾结点指针置空
    return L;
}

按序号查找结点值：O(n)
从链表第一个结点开始，顺着指针域next向下搜索，直到找到第i个结点为止，否则返回最后一个结点指针域为NULL。

LNode *GetElem(LinkList L,int i){
    int j=1;
    LNode *p=L->next;
    if(i==0)
        retuen L;
    if(i<1)                  //i无效，返回NULL
        return NLLL;
    while(p&&j<i){          //顺序查找
        p=p->next;
        j++;
    }
    return p;
}

按值查找结点：O(n)
从链表第一个结点开始，顺着指针域next向下搜索，若某结点的值等于给定值e，返回该结点的指针，否则返回NULL。

LNode *LocateElem(LinkList L,ElemType e){
    LNode *p=L->next;
    while(p!=NULL&&p->data!=e)
        p=p->next;
    return p;
}

插入结点： （后插，将s插在p后）复杂度为O(n)
将值为x的新结点s插入到单链表的第i个位置上。分为3步：

调用按序号查找算法GetElem(L,i-1),找到第i-1个结点，假设为p
让新插入结点s的指针域指向p的后继结点
最后让p结点的指针域指向新插入结点s
1
2
3
p=GetElem(L,i-1);
s->next=p->next;
p->next=s;

前插操作均可以转化为后插操作，只需要先找到待插入结点的前驱结点即可。时间主要耗费在查找前驱结点上。

插入结点： （前插，将s插在p前）
可以通过上面的后插方法，除此之外，下面介绍另外一种方法O(1)。

仍然将s插入p的后面

将p->data和s->data交换

s->next=p->next;    //修改指针域
p->next=s;
temp=p->data;       //交换数据域
p->data=s->data;
s->data=temp

删除结点操作：O(n)
将单链表的第i个结点删除。先查找表中的第i-1个结点，即被删结点（q）的前驱结点（p），再将其删除。

p=GetElem(L,i-1);
q=p->next;
p->next=q->next;
free(q);

要实现删除某一个给定结点，通常是找到其前驱结点，然后执行删除操作即可，这样的时间复杂度为O(n)，如上面所示。

删除结点操作：O(1)
其实，删除某一结点也可以通过删除它的后继结点实现。实质上就是将其后继结点的值赋予自身，然后删除后继结点，这样的时间复杂度为O(1)。

例如：删除给定结点p (q为p的后继结点)

q=p->next;
p->data=p->next->data; //和后继结点交换数据
p->next=q->next;      //将结点q从链中断开 
free(q);

双链表

单链表中结点只有一个指向其后继的指针，这使得单链表只能从头结点依次顺序的向后遍历。如果想要访问某个节点的前驱结点（插入、删除），只能从头遍历。访问前驱结点的时间复杂度为O(n),访问后继结点的时间复杂度为O(1)。

双链表的结点描述如下：

typedef struct DNode{
    ElemType data;              //数据域
    struct DNode *prior,*next;  //前驱后后继指针
}DNode,*DLinkList;

双链表仅仅在单链表的结点中增加了一个指向其前驱的prior指针，因此，双链表中执行按值查找和按位查找和单链表相同。但双链表在插入和删除操作上和单链表不同，这是因为链变的同时prior也要做出修改。双链表可以很快的找到其前驱结点，插入和删除的时间复杂度为O(1)。

插入操作（后插：将结点s插在p结点之后）

s->next=p->next;
p->next->prior=s;
s->prior=p;
p->next=s;

插入操作（前插：将结点q插在p结点之前）

p->prior->next=q;
q->next=p;
q->prior=p->prior;
p->prior=q;

删除操作：删除p的后继结点q

1
2
3

p->next=q->next;
q->next->prior=p;
free(q);

上面2节详细介绍了单链表和双链表的各种操作，接下来简要介绍一下循环链表和静态链表。

循环链表

循环单链表：
与单链表区别在于，表中最后一个结点的指针不是NULL，而是指向头结点。

判空条件：头结点的指针是否等于头指针。
任何一个位置上的插入、删除操作等价，无须判断是否为表尾。
可以从表中任意一个结点遍历整个链表。

循环双链表：

若结点p为尾结点，p->next=L
为空表时，头结点的prior和next都为L

静态链表

借助数组来描述线性表的链式存储结构，也有数据域和指针域
以next==-1作为结束标志
适合于不支持指针的高级语言（如Basic）

顺序表和链表的比较

存取方式

顺序表：可以顺序存取，也可以随机存取
链表：只能从表头顺序存取
逻辑和物理结构

顺序表：逻辑相邻的，物理存储也相邻
链表：逻辑相邻的，物理存储不一定相邻
查找、删除和插入操作

	按值查找	按号查找	插入删除
顺序表	无序 O(n)；有序O($log_2^n$)	O(1)	平均移动半个表长
链表	O(n)	平均O(n)	只需要修改相关结点指针域

空间分配

顺序表：静态（造成溢出）；动态（效率低）
链表：灵活、高效
选取情况

顺序表：线性表较稳定；按号访问为O(1)
链表：线性表长度、规模难以估计；需要频繁插入、删除操作时