数据结构向：《大话数据结构》ch3 线性表_if (i<1 || i>l->length)

3.2 线性表的定义

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

需要注意：线性表是一个序列，即元素之间是有顺序的；线性表是有限的。

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

ai若将线性表记为(a1, ..., ai-1, ai, ai+1, ..., an)，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接先驱元素，ai+！是ai的直接后继元素。当i=1，2，...，n-1时，ai有且仅有一个直接后继，当i=2，3，...，n时，ai有且仅有一个直接前驱。所以线性表元素的个数n（n大于等于0）定义为线性表的长度，当n=0时，称为空表。

在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

线性表要求数据类型相同。

 

3.3线性表的抽象数据类型

线性表的一些操作：创建和初始化(InitList(*L))；线性表重置为空表(ListEmpty(L))；将线性表清空(ClearList(*L))；根据位序得到数据元素(GetElem(L, i, *e)将线性表L中的第i个位置元素返回给e)；查找某个元素是否存在(LocateElem(L, e))；获得线性模型长度(ListLength(L))；插入数据(ListInsert(*L, i, e)在线性表中的第i个位置插入新元素e)和删除数据(ListDelete(*L, i, *e)删除线性表L中第i个位置元素，并用e返回其值)

 

3.4 线性表的顺序存储结构

3.4.1 顺序存储定义

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

3.4.2 顺序存储方式

既然线性表的每个数据元素的类型都相同，所以可以用C语言（其他语言也相同）的一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

#define MAXSIZE 20

typedef int ElemType;

typedef struct

{

    ElemType data [MAXSIZE];

    int length;

}SqList;

因此描述顺序存储结构需要三个属性：

a)存储空间的其实位置：数组data，它的存储位置就是存储空间的存储位置。

b)线性表的最大存储容量：数组长度MaxSize

c)线性表的当前长度：length

 

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

数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。在任意时刻，线性表的长度应该小于等于数组的长度。

 

3.4.4 地址计算方法

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

假设占用的是c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系(LOC表示获得存储位置的函数)。LOC(ai+1) = LOC(ai) + c，所以对于第i个数据元素ai的存储位置可以由a1推算得出：LOC(ai) = LOC(a1) + (i-1)*c，用图示表示如下：

通过这个共识，可以随时酸楚线性表中任何位置的地址，不管是第一个还是最后一个，都是相同的时间。那么对每个线性表位置的存入或取出数据，对于计算机来说时间都相同，即为一个常数，因此用时间复杂度的概念来说，它的存取时间性能为O(1)。我们通常把具有这一特点的存储结构称为随机存取结构。

 

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

3.5.1 获得元素操作

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

typedef int Status;

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

{

    if (L.length == 0 || i <1 || i>L.length)

    return ERROR;

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

    return OK;

} 

 

3.5.2 插入操作

如果插入位置不合理，抛出异常；如果线性表航渡大于等于数组长度，则抛出异常或动态增加容量；从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；将要插入元素填入位置i处；表长加1。代码如下：

Status LinstInsert(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 删除操作

删除算法的思路：如果删除位置不合理，抛出异常；取出删除元素；从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；表长减1。实现代码如下：

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=1;k<L->length;k++)

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

}

 

    L->length--;

    return OK;

}

线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)；而插入或删除时，时间复杂度都是O(n)。这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。

 

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

优点：无须为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速地存取表中任意位置的元素

缺点：插入和删除操作需要移动大量元素；当线性表长度变化较大时，难以确定存储空间的容量；造成存储空间的“碎片”

 

3.6 线性表的链式存储结构

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

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

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。以前在顺序结构中，每个数据元素只需要存数据元素信息就可以了。现在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。

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

n个结点（ai的存储映像）链结成一个链表，记为线性表(a1, a2, ..., an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将星星表的数据元素按其逻辑次序链接在一起。

链表中第一个结点的存储位置叫做头指针，我们规定，线性链表的最后一个结点指针为“空”（常用NULL或“^”符号表示）

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

 

3.6.3 头指针与头结点的异同

头指针：头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针；头指针具有标识作用，所以常用头指针冠以链表的名字；无论链表是否为空，头指针均不为空，头指针是链表的必要元素

头结点：头结点是为了操作的同意和方便而设立的，当在第一元素的结点之前，其数据一般无意义（也可存放链表的长度）；有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了；头结点不应是链表必须要素。

 

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

带有头结点的单链表，如下图所示：

空链表如下图所示：

单链表中，我们在C语言中可用结构指针来描述。

typedef struct Node

 

{

    ElemType data;

    struct Node *next;

}Node;

typedef struct Node *LinkList;

从以上结构定义中，可以知道，结点由存放数据元素的数据域和存放后继结点地址的指针域组成。假设p是指向线性表第i个元素的指针，则该结点ai的数据域，我们可以用p->data来表示，p->data的值是一个数据元素，结点ai的指针域可以用p->next来表示，p->next的值是一个指针。p->next指向第i+1个元素，即指向ai+1的指针。即，若p->data=ai,那么p->next->data = ai+1，如图所示：

 

3.7 单链表的读取

对于单链表事先获取第i个元素的数据的操作GetElem，在算法上，相对要麻烦一些。获取链表第i个数据的算法思路：

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

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

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

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

实现代码算法如下：

Status ListInsert(StaticLinkList L, int i. ElemType e)
{
    int j, k, l;
    k = MAX_SIZE - 1; /*注意k首先是最后一个元素的下标*/
    if (i < 1 || i > ListLength(L))
        return ERROR;
    j = Malloc_SSL(L); /*获取空闲元素的下标*/
    if (j)
    {
        L[j].data = e; /*将数据赋值给此分量的data*/
        for (l = 1; l <= i-1; l++) /*找到第i个元素之前的元素*/
            k = L[k].cur;
        L[j].cur = L[k].cur; /*把第i个元素之前的cur赋值给新元素的cur*/
        L[k].cur = j; /*把新元素的下标赋值给第i个元素之前元素的cur*//*这两步是插入的标准做法*/
        return OK;
       
    }
    return ERROR;

}

 

 

3.12.2 静态链表的删除操作

Status ListDelete(StaticLinkList L, int i)

{
    int j, k
    if (i < 1 || i > ListLength(L))
        return ERROR;
    k = MAX_SIZE - 1; /*k = 999*/
    for (j = 1; j <= i - 1; j++) /*因为i=1，因此此时for循环不进行*/
        k = L[k].cur;
    j = L[k].cur; # j = L[999].cur = 1
    L[k].cur = L[j].cur; /*L[999].cur = L[1].cur = 2告诉计算机现在“甲”已经走了，“乙”才是第一个元素8
    Free_SSL(L, j);
    return OK;
}


void Free_SSL(StaticLinkList space, int k)
{
    space[k].cur = sapce[0].cur; /*把第一个元素cur值赋给要删除的分量cur*/
    space[0].cur = k; /*把要删除的分量下标赋值给第一个元素的cur*/
}


意思是，“甲”现在要走了，这个位置就没人了，未来要是有新人来呢，就优先考虑这个位置，所以原来的第一个空位分量就被降级了，我们把8给了“甲”所在下标为1的分量的cur，也就是space[1].cur = sapce[0].cur = 8，而space[0].cur = 1，其实就是让这个删除的位置称为第一个优先空位，把它存入第一个元素的cur中。

 

静态链表也有相应的其他操作的实现。比如ListLength，看以下代码：
int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIEZE - 1].cur;
    while (i)
    {
        i = L[i].cur;
        j++;
    }
    return j;

}

 

3.12.3 静态链表优缺点
优点：在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的哈杜和删除操作需要移动大量元素的缺点
缺点：没有解决连续存储分配带来的表长难以确定的问题；失去了顺序存储结构随机存取的特性

 

总的来说，静态链表是为了给没有指针的高级语言设计的一种实现单链表能力的方法。

 

3.13 循环链表
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表(circular linked list)
循环链表恶疾觉了一个很麻烦的问题，即如何从当中一个结点出发，访问到链表的全部结点。

为了使得空链表与非空链表一致，通常都设置一个头结点，当然，循环链表并非一定要有有结点。下面两幅图展示了空循环链表与非空循环循环链表的示意图：

循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否为空，现在则是p->next不等于头结点，则循环未结束。
在单链表中，有了头结点之后，访问第一个结点的时间为O(1)，但是访问最后一个结点却需要O(n)的时间。
要是我们想要使得访问最后一个结点的时间也变为O(1)，该怎么办呢？

此时我们需要改造一下这个循环链表，不用头指针，而是使用指向终端结点的尾指针来循环链表。此时查找开始结点和终端结点都变得很方便了。

从上图可以看出，终端结点用尾指针rear指示，此时我们查找终端结点的时间为O(1),而开始结点，其实就是rear->next->next，时间复杂度也是O(1)。

举个例子，如果我们想要把两个循环链表合并成一个表时，尾指针的存在就变得非常有意义了。例如，我们要合并下面两个循环链表，它们的尾指针分别为rear A和rear B

要想合并它们，只需进行如下操作即可。

 

p = rearA->next; /*保存A表的头结点*/

rearA->next = rearB->next->next; /*将本来指向B表的第一个结点(不是头结点)赋值给rearA->next*/

rearB->next = p; /*将原来A表的头结点赋值给rearB->next*/

free(p); /*释放p*/

在单链表中，有了next指针，可以使得我们查询下一结点的时间复杂度为O(1)。可是如果我们要查找的是上一结点的话，那么最坏的时间复杂度就是O(n)，因为我们每次都要从头开始遍历查找。
此时，就引出了双向链表。双向链表是在单链表的每个结点中，再设置一个指向前驱结点的指针。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。


typedef struct DulNode
{
    ElemType data;
    struct DulNode *prior; /*直接前驱指针*/
    struct DulNode *next; /*直接后继指针*/
}DulNode, *DuLinkList;
 

双向链表当然也可以是循环表。

对于链表中的某一个结点p，它的后继的前驱和它前驱的后继都是它本身，即:
p->next->prior = p = p->prior->next
由于双向链表是由单链表中扩展出来的，因此两者的许多操作都是相似的。比如，ListLength、GetElem以及LocateElem，这些操作都只设计一个方向的指针，另一指针多了也并没有提供什么额外的帮助。
双向链表相比单向链表多了可以反向遍历查找数据这一优点，它的代价是在插入和删除时，需要更改两个指针变量。

 

进行插入操作时，需要注意的是顺序。假设存储元素e的结点为s，要实现将结点s插入到结点p和p->next之间需要以下几步：

s->prior = p; /*把p赋值给s的前驱*/
s->next = p->next; /*把p->next赋值给s的后继*/
p->next->prior = s; /*把s赋值给p->next的前驱*/

p->next = s; /*把s赋值给p的后继*/

当理解了插入操作时，删除操作就比较简单了。

进行删除操作时，只需要下面两个步骤：

p->prior->next = p->next /*把p->next赋值给p->prior的后继*/
p->next->prior = p->prior /*把p->prior赋值给p->next的前驱*/

free(p) /*释放结点*/

双向链表一句话，就是用空间来换时间。