数据结构——线性表学习篇(二)

前言

循环链表

在某些情况下，若在循环链表中设立尾指针而不设头指针(a)，可使一些操作简化，类如，将两个线性表合并成一个表时，

仅需将第一个表的尾指针指向第二个表的第一个结点，第二个表的尾指针指向第一个表的头指针，然后释放第二个表的头结点。

当线性表以(a）的循环链表作存储结构时，这个操作仅需改变两个指针的值就可以了

主要语句：

p=B->next->next;
B-next=A-next;
A->next=p;

判别单向循环链表为空的条件：P!=L或p->next!=L

时间复杂度O(1)

双向链表

在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱，上图中的a可以使用下面代码描述

typedef struct DuLNode
{
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
 } DuLNode,*DuLinkList;

和单链的循环链表类似，双向链表也算可以有循环链表的，上图中的c，链表中有两个环，b中只有一个表头结点的空表

注意： d->next->prior=d->prior-next=d;

双向链表的插入

双向链表第b个结点之前插入一个新的结点

Status ListInsert_DuL(DuLinkList &L,int i,ElemType e) {
    //在带头结点的双向链表L中第i个位置之前插入元素e
    if(!(p=GetElem_DuL(L,i)))//在L中确定第i个元素的位置指针p
        return ERROR; //p为NULL时，第i个元素不存在
    s=new DuLNode;   //生成新的结点*s
    s->data=e;   //将结点*s数据域置为e
    s->prior=p->prior; //图中的1
    p->prior->next=s;  //图中的2
    s->next=p;//图中的3
    p-prior=s;   //图中的4
    return OK;
}

双向链表的删除

Status ListInsert_DuL(DuLinkList &L,int i) {
    //删除带头结点的双向链表L中第i个位置
    if(!(p=GetElem_DuL(L,i)))//在L中确定第i个元素的位置指针p
        return ERROR; //p为NULL时，第i个元素不存在
    p->prior->next=p->next;   //图中的1 
    p->next-prior=p->prior;   //图中的2 
    delete p; //释放被删除结点的空间 
    return OK;
}

顺序表和链表的比较

1、顺序表

顺序表的优点：

(1) 方法简单，各种高级语言中都有数组，容易实现。

(2) 不用为表示结点间的逻辑关系而增加额外的存储开销。

(3) 顺序表具有按元素序号随机访问的特点。

顺序表的缺点：

(1) 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。

(2) 需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。

2、链表

链表的优点：

(1) 在链表中做插入删除操作时，不会影响前面和后面的节点，因此对n较大的链表效率高。

(2) 不需要预先分配足够大的存储空间，避免造成空间闲置或溢出的情况。

链表的缺点：

(1) 需要进行指针操作，方法复杂。

(2) 需要为表示结点间的逻辑关系（指针变量）而增加额外的存储开销。

(3) 只能通过遍历找到某个节点，不能使用下标直接定位节点。

3、选择合适的数据结构

１．基于存储的考虑

顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对＂MAXSIZE＂要有合适的设定，过大造成浪费，

过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低

（存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比，显然链式存储结构的存储密度是小于１的）。

２．基于运算的考虑

在顺序表中按序号访问 ai 的时间性能时O(1)，而链表中按序号访问的时间性能O(n)，所以如果经常做的运算是按序号访问数据元素，

显然顺序表优于链表；而在顺序表中做插入、删除时平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；

在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。

３．基于环境的考虑

顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。

链式有序表的合并

1：将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个

链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。

[题目分析]

合并后的新表使用头指针 Lc 指向，pa 和 pb 分别是链表 La 和 Lb 的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，

当两个链表 La 和 Lb 均为到达表尾结点时，依次摘取其中较小者重新链接在 Lc 表的最后。如果两个表中的元素相等，只摘取 La表中的元素，

删除 Lb 表中的元素，这样确保合并后表中无重复的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在 Lc 表的最后。

[算法描述]

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) {
    //合并链表 La 和 Lb，合并后的新表使用头指针 Lc 指向
    pa=La->next;
    pb=Lb->next;
//pa 和 pb 分别是链表 La 和 Lb 的工作指针,初始化为相应链表的第一个结点
    Lc=pc=La; //用 La 的头结点作为 Lc 的头结点
    while(pa && pb) {
        if(pa->data<pb->data) {
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
//取较小者 La 中的元素，将 pa 链接在 pc 的后面，pa 指针后移
        else if(pa->data>pb->data) {
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
//取较小者 Lb 中的元素，将 pb 链接在 pc 的后面，pb 指针后移
        8
        else { //相等时取 La 中的元素，删除 Lb 中的元素
            pc->next=pa;
            pc=pa;
            pa=pa->next;
            q=pb->next;
            delete pb ;
            pb =q;
        }
    }
    pc->next=pa?pa:pb; //插入剩余段
    delete Lb; //释放 Lb 的头结点
}

2：将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。

[题目分析]

合并后的新表使用头指针 Lc 指向，pa 和 pb 分别是链表 La 和 Lb 的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，

当两个链表 La 和 Lb 均为到达表尾结点时，依次摘取其中较小者重新链接在 Lc 表的表头结点之后，如果两个表中的元素相等，

只摘取 La 表中的元素，保留 Lb 表中的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素依次摘取，链接在 Lc 表的表头结点之后。

[算法描述]

void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, ) {
    //合并链表 La 和 Lb，合并后的新表使用头指针 Lc 指向
    pa=La->next;
    pb=Lb->next;
//pa 和 pb 分别是链表 La 和 Lb 的工作指针,初始化为相应链表的第一个结点
    Lc=pc=La; //用 La 的头结点作为 Lc 的头结点
    Lc->next=NULL;
    while(pa||pb ) {
        //只要存在一个非空表，用 q 指向待摘取的元素
        if(!pa) {
            q=pb;
            pb=pb->next;
        }
//La 表为空，用 q 指向 pb，pb 指针后移
        else if(!pb) {
            q=pa;
            pa=pa->next;
        }
//Lb 表为空，用 q 指向 pa，pa 指针后移
        else if(pa->data<=pb->data) {
            q=pa;
            pa=pa->next;
        }
//取较小者（包括相等）La 中的元素，用 q 指向 pa，pa 指针后移
        else {
            q=pb;
            pb=pb->next;
        }
//取较小者 Lb 中的元素，用 q 指向 pb，pb 指针后移
        q->next = Lc->next;
        Lc->next = q;
//将 q 指向的结点插在 Lc 表的表头结点之后
    }
    delete Lb; //释放 Lb 的头结点
}

3：已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。请设计算法求出 A 与 B的交集，并存放于 A 链表中。

[题目分析]

只有同时出现在两集合中的元素才出现在结果表中,合并后的新表使用头指针 Lc 指向。pa 和 pb 分别是链表 La 和 Lb 的工作指针,

初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表 La 和 Lb 均为到达表尾结点时，如果两个表中相等的元素时，

摘取La 表中的元素，删除 Lb 表中的元素；如果其中一个表中的元素较小时，删除此表中较小的元素，此表的工作指针后移。

当链表 La 和 Lb 有一个到达表尾结点，为空时，依次删除另一个非空表中的所有元素。

[算法描述]

void Mix(LinkList& La, LinkList& Lb, LinkList& Lc) {
    pa=La->next;
    pb=Lb->next;
    pa 和 pb 分别是链表 La 和 Lb 的工作指针,初始化为相应链表的第一个结点
    Lc=pc=La; //用 La 的头结点作为 Lc 的头结点
    while(pa&&pb) {
        if(pa->data==pb->data)∥交集并入结果表中。 {
            pc->next=pa;
            pc=pa;
            pa=pa->next;
            u=pb;
            pb=pb->next;
            delete u;
        } else if(pa->data<pb->data) {
            u=pa;
            pa=pa->next;
            delete u;
        } else {
            u=pb;
            pb=pb->next;
            delete u;
        }
    }
    while(pa) {
        u=pa;
        pa=pa->next;
        delete u;
    }∥ 释放结点空间
    while(pb) {
        u=pb;
        pb=pb->next;
        delete u;
    }∥释放结点空间
    pc->next=null;
    ∥置链表尾标记。
    delete Lb; //释放 Lb 的头结点
}