第三章 线性表

3.1 开场白

        用小朋友排队的方式说明线性表

3.2 线性表的定义

        线性表（List）：零个或多个数据元素的有限序列。

        这里需要强调几个关键的地方：

        首先，它是一个序列，也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。

        然后，线性表强调是有限的，小朋友编辑人数是有限的，元素个数当然也是有限的。事实上，在计算机中处理的对象都是有限的，那种无限的数列，只存在于数学的概念中。

        如果用数学语言来定义。如下：

        若将线性表记为（a1,.....ai-1,ai,ai+1,...an）,则表中ai-1领先于ai，ai领先于ai+1，成ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2,...n-1时，ai有且仅有一个后继，当i=2,3...，n时，ai有且仅有一个直接前驱。如图3-2-1所示。

        所以线性表元素的个数n(n>=0)定义为线性表的长度，当n=0时，称为空表。

        在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是左后一个数据元素，ai是第i个数据元素,称i 为数据元素ai在线性表中的维序。

3.3线性表的抽象数据类型

    ADT 线性表（List）

    Data

        线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素都有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素都有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

    Operation

        InitList(*L):初始化操作。建立一个空的线性表L

        ListEmpty(L)： 若线性表为空，返回true，否则返回false

        ClearList(*L):将线性表清空。

        GetElem(L,i,*e):将线性表L中的第i个位置元素值返回给e。

        LocateElem(L,e)：在线性表L中查找与给定值e相等的元素，如果查找查灯光，返回该元素在表中序号表示成功；否则返回0表示失败。

        ListInsert(*L,i,e)：在线性表L中的第i个位置插入新元素e.

        ListDelete(*L,i,*e);删除线性表L中第i个位置元素，并用e返回其值。

        ListLength(L)返回线性表L的元素个数。

    endADT

        上述的操作时最基本的，对于实际问题中涉及的关于线性表的更复杂操作，完全可以用浙西基本操作的组合实现。

        比如，实现两个线性表集合A和B的并集操作。即要使得集合A=AUB。说白了就是把 存在集合B中单不存在A中的数据元素插入到A中即可。

        仔细分析一下这个操作，发现我们只要忙集合B中的每个元素，判断当前元素是否存在A中，若不存在，则插入到A中即可。思路应该是很容 易想到的。

void union(List *La, List Lb)

{

    int La_Len, Lb_len, i;

    ElemType e;

    La_len = ListLength(La);

    Lb_len = ListLenth(Lb);

    for(i = 1; i <= Lb_len; i++)

    {

        GetElem(Lb, i, e);

        if (!LocateElem(La,e, equal))

            ListInsert(La, ++La_len, e);    

    }

}

3.4 线性表的顺序存储结构

3.4.1 顺序存储定义

        线性表的顺序存储结构：指的是用一段地址连续的存储单元一次存储线性表的数据元素。

        线性表（a1,a2,...,an)的顺序存储十一图如下：

3.4.2 顺序存储方式

        线性表的属性存储结构，说白了，就是在内存中找一块地方通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素一次存放在这块空地中。

        C语言中用一维数组来实现顺序存储结构。

        随着数据的插入或删除，线性表的长度不够或者有空余了，应当怎么办？

        线性表的顺序存储的结构代码

#define MAXSIZE 20

typedef int ElemType;

typedef struct

{

    ElemType data[MAXSIZE];

    int length

}SqList;

这里我们发现，描述属性存储结构需要三个属性：

        存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。

        线性表的最大存储容量：数长度MaxSize.

        线性表的当前长度：length。

3.4.3 数据长度与线性表长度区别

        数组的长度和线性表的长度需要区分一下。

        数组的长度是存放线性表的存储空间的长度，存储分配后这个量是一般不变的。

        在任意时刻，线性表的长度应该小于等于数的长度。

3.4.4 地址计算方法

        存储器中没有出场单元都有自己的编号，这个编号称为地址。

        由于是连续的空间，存取时间复杂度为O(1)。我们通常把具有这一特点的存储结构称为随机存取结构。

3.5 顺序存储结构的插入与删除

3.5.1 获得元素操作

        C语言直接用下标存取

3.5.2 插入操作

        插入算法的思路：

        如果插入的位置不合理，抛出异常

        如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；

        从左后一个元素开始向前遍历到第i个位置，分别将他们都向后移动一个位置；

        将要插入元素填入位置i处；

        表长加1

        实现代码：

Status ListInsert(SqList *L, int i, ElemType e)

{

    int k;

    if (L->length == MAXSIZE)

        return ERROR;

    if (i < 1 || i>L->length+1)

        return ERROR;

    if (i <= L->length)

    {

        for (k=L->length-1; k>=i-1; k--)

            L->data[k+1] = L->data[k];

    }

    L->data[i-1] = e;

    L->length++;

    return OK;

}

3.5.3 删除操作

        删除算法思路：

        如果删除位置不合理，抛出异常

        取出删除元素；

        从删除元素位置开始办理到最后一个元素位置，分别将他们都向前移动一个位置；

        表长减一

        实现代码：

Status ListDelete(SqList *L, int i, ElemType *e)

{

    int k;

    if (L->length == 0)

        return ERROR;

    if (i < 1 || i > L->Length)

        return ERROR;

    *e = L->data[i-1];

    if (i < L->length)

    {

        for (k = i; k<L->length;k++)

        {

            L->data[k-1] = L->data[k];

        }

    }

}

        最后情况的时间复杂度是O(n)。

        线性表的属性存储结构，在存读数据时，不管是哪个位置，时间复杂度都是O(1)；而砸插入，删除数据时，时间复杂度都是O(n)。这说明他比较适合元素个数不太变化，而更多是存取数据的应用。当然他的优缺点不止这些。

3.5.4 线性表顺序存储结构的优缺点

优点：

        无须为表示表中元素之间的逻辑关系而增加二外的存储空间

        可以快速地存储表中任意位置的元素

缺点：

        插入和删除操作需要移动大量元素

        当线性表长度变化较大时难以确定存储空间的容量

        造成存储空间的碎片

3.6 线性表的链式存储结构

3.6.1 顺序存储结构不足的解决办法

        顺序存储结构，插入删除时需要移动大量的元素，耗费时间。

3.6.2 线性表链式存储结构定义

        为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素a1来说，除了存储器本身的信息之外还需存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这部分信息做成数据元素ai的存储映像，称为节点（Node）。

        n个节点（ai的存储映像）链接成一个链表，即为线性表（a1,a2,...,an）的链式存储结构，因为次链表的每个节点中只包含一个指针域，所以叫做单链表。

        链表第一个节点的存储位置叫做头指针，线性链表的最后一个节点指针为空。通常用NULL来表示。

        有时，我们为了更加方便地对链表进行操作，会在链表的第一个节点钱附加一个节点，称为头结点。头结点的数据域可以不存储任何信息。也可以存储线性表的长度等附加信息，头结点的指针域存储指向第一个节点的指针。

3.6.3 头指针与头结点的异同

头指针：

        头指针是指链表指向第一个节点的指针，若链表有头结点，则是指向头结点的指针

        头指针具有标识左右，所以常用头指针冠以链表的名字

        五乱链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点：

        头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，器数据域一般无意义（也可存放链表的长度）

        有了头结点，对在艺元素结点钱插入结点和删除第一节点器操作与其他结点的操作就统一了

        头结点不一定是链表必须要素。

3.6.4 线性表连式存储结构代码描述

        若线性表为空表，则头结点的指针域空。

        没有头结点的单链表

        带有头结点的单链表

        带有头结点的空链表

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

typedef struct Node

{

    ElemType data; struct Node *next;

} Node;

typedef struct Node *LinkList;

        结点由存放数据元素的数据域存放后继结点地址的指针域组成。

3.7 单链表的读取

        单链表的获取第i个元素到底在哪里比较麻烦，算法思路如下：

                1.声明一个节点p指向链表第一个结点，初始化j从1开始；

                2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1；

                3.若到链表末尾p为空，则说明第i个元素不存在；

                4.否则查找成功，返回结点p的数据

实现代码如下：

/* 初始条件：顺序线性表L已存在，l<=i<=ListLength(L) */

/* 操作结果：用 e 返回L中第i个数据元素的值 */

Status GetElem(LinkList L, int i, ElemType *e)

{

    int j;

    LinkList p;

    p = L->next;

    j = 1;

    while(p && j < i)

    {

        p = p->next;

        ++j;

    }

    if (!p || j > i)

    {

        return ERROR;

    }

    *e = p->data;

    return OK;

}

        这个算法的存取时间复杂度是O(n)，比顺序存储结构慢多了。

        但插入删除会快很多。

3.8 单链表的插入与删除

3.8.1 单链表的插入

        存储元素e的结点为s，要实现结点p，p->next和s之间逻辑关系的变化，只需要将结点s插入到结点p和p->next之间即可。

s->next = p->next;

p->next = s;

运行后：

两句能否互换呢？不能。

头结点和尾结点的操作时相同的。

单链表第i个数据插入结点的算法思路：

1.声明一个节点p指向链表第一个结点，初始化j从1开始；

2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1;

3.若到链表末尾p为空,则说明第i个元素不存在；

4.否则查找成功，在系统中生成一个空结点s;

5.将数据元素e赋值给s->data;

6.单链表的插入标准语句s->next=p->next; p->next=s;

7.返回成功。

实现代码算法如下：

/* 初始条件：顺序线性表L已存在，1<=i<=ListLength(L) */

/* 操作结果：在L中第i个位置之前插入新的数据元素e,L的长度加1 */

Status ListInsert(LinkList *L, int i, Elemtype e)

{

    int j;

    LinkList p,s;

    p = *L;

    j = l;

    while(p && j < i)

    {

        p = p->next;

        ++j;

    }

    if (!p || j > i)

        return ERROR;

    s = (LinkList)malloc(sizeof(Node));

    s->data = e;

    s->next = p->next;

    p->next = s;

    return OK;

}

3.8.2单链表的删除

p->next = q->next;

单链表第i个数据删除解密的算法思路：

1.声明一个结点p指向链表的第一个结点，初始化j从1开始；

2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1

3.若到链表末尾p为空，则说明第i个元素不存在；

4.否则查找成功，将欲删除的结点p->next赋值给q;

5.单链表的删除标准语句p->next=q->next;

6.将q结点中的数据赋值给e，作为返回。

7.释放q结点；

8.返回成功。

实现代码算法如下：

/* 初始条件：顺序线性表L已经存在，l<=i<=ListLength(L) */

/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */

Status ListDelete(LinkList *L, int i, ElemType *s)

{

    int j;

    LinkList p, q;

    p = *L;

    j = l;

    while(p->next && j < i)

    {

        p = p->next;

        ++j;

    }

    if (!(p->next) || j>i)

        return ERROR;

    q = p->next;

    p->next = p->next;

    *e = q->data;

    free(q);

    return OK;

}

对于插入或删除数据越频繁的操作，单链表的效率优势就越明显。

3.9 单链表的整表创建

单链表整表创建的算法思路：

1.声明一节点p和计数器变量i;

2.初始化一空链表L;

3.让L的头结点的指针指向NULL，即建立一个带头结点的单链表

4.循环：

生成一新节点赋值给p;

随机生成一数字赋值给p的数据域p->data;

将p插入到头结点与前一新结点之间。

实现代码算法如下：

/* 随机产生n个元素的值，建立带表头结点的单链线性表L(头插法) */

void CreateListHead(LinkList *L, int n)

{

    LinkList p;

    int i;

    srand(time(0));

    *L = (LinkList)malloc(sizeof(Node));

    (*L)->next = NULL;

    for (i = 0; i < n; i++)

    {

        p = (LinkList)malloc(sizeof(Node));

        p->data = rand()%100 +1;

        p->next = (*L)->next;

        (*L)->next = p;

    }

}

这段算法代码里，我们其实用的是插队的办法，就是始终让新结点在第一的位置。我也可以把这种算法简称为肉茶法，如图:

/* 随机产生n个元素的值，建立带表头结点的单链线性表L(尾插法) */

void CreateListTail(LinkList *L, int n)

{

    LinkList p,r;

    int i;

    srand(time(0));

    *L = (LinkList)malloc(sizeof(Node));

    r = *L;

    for (i=0; i<n;i++)

    {

        data = rand()%100+1;

        r->next = p;

        r = p;

    }

    r->next = NULL;

}

3.10 单链表的整表删除

单链表整表删除的算法思路：

1.声明一个结点p和q;

2.将第一个结点赋值给p;

3.循环：

将下一结点赋值给q;

释放p

将q赋值给p;

实现代码算法如下：

Status ClearList(LinkList *L)

{

    LinkList p,q;

    p=(*L)->next;

    while(p)

    {

        q = p->next;

        free(p);

        p = q;

    }

    (*L)->next = NULL;

    return OK;

}

3.11 单链表结构与顺序存储结构的优缺点

存储范培方式：

        顺序存储结构用一段连续的存储单元依次存储线性表的数据元素

        单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

时间性能：

        查找

        顺序存储结构O(1)

        单链表O(n)

        插入和删除

        属性存储结构序需要平均移动表长一半的元素时间为O(n)

        单链表在找出某位置的指针后，插入和删除时间仅为O(1)

空间性能

        顺序存储结构需要预分配存储空间，分大了，浪费，分校了易发生上溢

        单链表不需要预先分配存储空间，只有有旧可以分配，元素个数不受限制

经验性结论：

        若线性表需要频繁查找，很少进行插入和删除操作，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。比如说游戏开发中对于用户注册的个人信息，除了注册时插入数据外，绝大多数情况都是读取，所以应该考虑用顺序存储结构。而游戏中玩家的武器或装备类比，随着玩家的游戏过程，可能随时增加或删除，此时再用顺序存储就不太合适了，单链表结构就可以大展拳脚。当然这只是简单的类比，是显示中的软件开发，需要考虑的问题会复杂很多。

        当线性表中的元素个数变化较大或者根本不知道有多大是，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事前知道线性表的大致长度，不如一年12个月，一周就是星期一至星期日七天，这种用数学存储结构效率会搞很多。

3.12 静态链表

        用数组描述的链表叫做静态链表

        不能直接操作内存的高级语言使用数组描述链表的方法。

        静态链表的优缺点

优点：

        在插入和删除操作时要需要修改游标，不需要移动元素，从而改进了属性存储结构中的插入删除操作需要移动大量元素的缺点。

缺点：

        没有解决连续存储分配带来的表长难以确定的问题

        失去了顺序存储结构随机存取的特性。

3.13循环链表

        将单链表中终端结点的指针端由控制住改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表（circular linked list）

        从刚才的例子，可以总结出，循环链表解决了一个很慢发的问题。如何从当中一个结点触发，访问到链表的全部结点。

带有头结点的空循环链表：

        非空循环链表:

        判断循环链表是否遍历需要判断p->next是否等于头结点。

        非循环链表只要判断p->next是否为空

        如果记住末尾的结点，不记录头结点，则访问头结点和尾结点都只需要O(1)的时间复杂度。

        拼接链表也会很简单。

3.14 双向链表

        双向链表是在单链表的每个节点中，再设置一个指向前驱结点的指针域。

/* 双向链表的存储结构 */

typedef struct DulNode

{

    ElemType data;

    struct DulNode *prior;

    struct DulNode *next;

}DulNode, *DulinkList;

双链表也可以有循环表。

3.15 总结回顾