3、线性表

参考：《大话数据结构》程杰

Paste_Image.png

线性表（List）：零个或多个数据元素的有限序列，具有像线一样的性质的表。因为是序列，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都是有且只有一个前驱和后继。线性表强调是有限的。

3.1、抽象数据类型

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 La，集合B Lb的并集操作

void union(List *La, List Lb){
    int La_length, Lb_length, i;
    ElemType e; /*声明与List相同的数据元素e*/
    La_length ListLength(La)
    Lb_length ListLength(Lb)
    for(i=1; i<=Lb_length; i++){
        GetElem(Lb, i, e) /*取Lb中第i个数据元素赋给e*/
        if(!LocateElem(La, e, equal))
            ListInsert(La, ++La_length, e)/*插入*/
    }
}

3.2、顺序存储结构

3.3.1、定义

Paste_Image.png

线性表的顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素，如下所示：

内存中找位置，通过占位的形式，把一定内存空间占住，然后把相同数据类型的数据元素依次存放在这块空地中，如可以用一维数组实现顺序存储结构。
线性表的顺序存储的结构代码：

#define MAXSIZE 20  /*存储空间初始分配量*/
typedef int ElemType; /*ElemType根据实际情况*/
typedef struct{
    ElemType data[MAXSIZE]; /*数组存储数据元素*/
    int length;     /*线性表当前长度*/
}SqList;

顺序结存结构的三个属性：
1、存储空间的起始位置，2、线性表的最大存储容量，3、线性表的当前长度：length

数组长度与线性表长度区别：
数组长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。可以进行动态分配数组，但是会带来性能的损耗。
线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作，这个量是变化的。
任意时刻，线性表的长度应该小于等于数组的长度。

3.3.2、地址计算方法

数据元素的序号和存放它的数组下标之间存在对应关系，用数组存储顺序以为要分配固定长度的数组空间，由于线性表可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表长度。

Paste_Image.png

存储器中每个存储单元都有自己的编号，这个编号称为地址。LOC表示获得存储位置的函数，假设每个存储空间占用c个存储单元，基于以下公式可以推算出线性表中任意位置的地址。因此存取时间性能是O(1)。

Paste_Image.png Paste_Image.png

3.3.3、顺序存储结构的插入&删除

1、获得元素操作

实现线性表的GetElem操作，将线性表L中的第i个位置元素值返回，只要i在数组下标范围内，返回i-1下标对应的值即可，时间复杂度为O(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
}

2、插入操作

线性表顺序存储解耦，对于插入或删除，时间复杂度都是O(n)
如图：线性表顺序存储结构，在插入过程中的实现，插入的流程如下：
（1）如果插入位置不合理，抛异常；（2）如果线性表长度大于数组长度，则抛异常或动态增加容量；（3）从最后一个元素开始向前遍历i个位置，分别将它们向后移动一个位置；（4）插入元素填入位置i处；（5）线性表长度加长1。

Paste_Image.png

/*初始条件：顺序线性表L已存在 1<i<ListLength(L)*/
/*操作结果：在L中第i个位置插入元素e，L长度加1*/
Status ListInsert(SqList *L, int i, ElemType e){
    int k;
    if(L->length == MAXSIZE) /*顺序线性表已满*/
        return ERROR;
    if(i<1 || i > L->length+1) /*i不在范围内*/
        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、删除操作

顺序存储结构的线性表的删除元素过程，如下图所示，基本思想是：
（1）如果删除位置不合理，抛出异常；（2）取出删除元素；（3）从删除元素位置开始遍历到最后一个元素位置，分别把它们向前移动一个位置；（4）表长度减1.

Paste_Image.png

/*初始条件：顺序线性表L已存在 1<i<ListLength(L)*/
/*操作结果：删除L的第i个数据元素，用e返回其值，L的长度减1*/
Status ListDelete(SqList *L, int i, ElemType *e){
    int k;
    if(L->length==0)/*线性表为空*/
        return ERROR;
    if(i<1 || i > L->length+1) /*i不在范围内*/
        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];
    }
    L->length--;
    return OK;
}

3.3.4、线性表存储优缺点

优点：（1）无需为表中元素之间的逻辑关系增加额外的存储空间；（2）快速的存取表中任一位置的元素
缺点：（1）插入和删除操作需要移动大量元素；（2）当线性表长度变化大时，难以确定存储空间的容量；（3）造成存储空间的“碎片”

3.3、线性表的链式存储结构

3.3.1、定义

线性表的链式存储结构特点：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续，这些数据元素可以存在内存未被占用的任意位置。链式结构除了存储数据元素信息外，还存储它的后继元素的存储地址。存储数据元素信息的域称为数据域，存储直接后继位置的域称为指针域。
n个节点链结成一个链表，即为线性表（a1,a2,.....an）的链式存储结构，因为此链表的每个节点中只包含一个指针域，所以称为单链表。

Paste_Image.png

链表的第一个结点的存储位置叫头指针，之后的每个结点，指向后继指针，最后一个节点，指向NULL

Paste_Image.png

单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何数据信息

Paste_Image.png

头指针与头结点异同：

Paste_Image.png

3.3.2、线性表链式存储结构

1、线性表为空，头结点的指针域为“空”

Paste_Image.png

2、单链表图示

Paste_Image.png

3、带头头结点的单链表

Paste_Image.png

4、空链表

Paste_Image.png

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

/*线性表的单链表存储结构*/
typedef struct Node{
    ElemType data;
    struct Node *next;
} Node;
typedef struct Node *LinkList; /*定义LinkList*/

Paste_Image.png

3.3.3、单链表的读取

单链表中，由于第i个元素不知在哪，必须从头开始找，实现GetElem的思路：
（1）声明结点p指向链表第一个结点，初始化从j从1开始；（2）当j<i，遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；（3）若到链表末尾p为空，则说明i个元素不存在；（4）否则查找成功，返回结点p的元素
最坏的情况下时间复杂度：O(n)

/*初始条件：顺序线性表L已存在 1<i<ListLength(L)*/
/*操作结果：用e返回L中第i个数据元素的值*/
Status GetElem(LinkList L, int i, ElemType *e){
    int j;
    LinkList p; /*声明一结点p*/
    p = L->next; /*让p指向链表L的第一个结点*/
    j = 1; /*j为计数器*/
    while(p && j<i){/*p不为空或者计数器j还没有等于i，循环继续*/
        p = p->next;
        ++j;
    }
    if(!p || j>1)
        return ERROR;
    *e = p->data;
    return OK;
}

3.3.4、单链表的插入

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

Paste_Image.png Paste_Image.png

单链表第i个数据插入结点的算法思路：
（1）声明一结点p指向链表的第一个结点，初始化j从1开始；（2）当j<1时，遍历链表，让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 = 1;
    while(p && j < i){ /*寻找第i个结点*/
        p = p->next;
        ++j;
    }
    if(!p || j > i)
        return ERROR;
    s = (LinkList)malloc(sizeof(Node))/*生成新的结点*/
    s->data = e;
    s->next = p->next;
    s->next = s;
    return OK;
}

malloc用于生成一个新的节点，其类型与Node是一样的，在内存中找一个空位，准备用来存放e数据的s结点。

3.3.5、单链表的删除

实现单链表删除，就是将它的前继结点的指针绕过，指向它的后继结点即可。

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

Paste_Image.png

单链表第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结点；返回成功

/*初始条件：顺序线性表L已存在 1<i<ListLength(L)*/
/*操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1*/
Status ListDelete(LinkList *L, int i, ElemType *e){
    int j;
    LinkList p,q;
    p = *L;
    j = 1;
    while(p->next && j<i){/*遍历寻找第i个元素*/
        p = p->next;
        ++j;
    }
    if(!(p->next) || j>i)
        return ERROR; /*第i个元素不存在*/
    q = p->next;
    p->next = q->next;/*将q的后继赋值给p的后继*/
    *e = q->data;
    free(q); /*系统回收该结点，释放内存*/
    return OK;
}

3.3.6、单链表的整表创建

顺序存储结构的创建，是数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表不像顺序存储结构那么集中，它可以很散，是一种动态结构。单链表的创建过程时一个动态生成链表的过程，从“空表”初始状态，依次建立各元素结点，并逐个插入链表。
（1）声明一结点p和计数器变量i；（2）初始化一空链表L；（3）让L的头结点指向null，建立一个带头结点的单链表。
（4）循环：生成新的节点赋值p；随机生成数字赋值给p的数据域p->data；将p插入到头结点与前一新结点之间。

/*随机产生n个元素的值，建立带表头结点的单链表（头插法）*/
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;/*随机生成100内的数字*/
        p->next = (*L)->next;
        (*L) ->next = p;/*插入到表头*/
    }
}

思想：使用插队的方法，但始终让新结点在第一的位置，该方法称为头插法。

Paste_Image.png

将新结点插入到终端节点的后面，称为尾插法：

/*随机产生n个元素的值，建立带表头结点的单链表（尾插法）*/
void CreateListTail(LinkList *L, int n){
    LinkList p,r;
    int i;
    srand(time(0)); /*初始化随机数种子*/
    *L = (LinkList)malloc(sizeof(Node));
    r=*L; /*r为指向尾部的结点*/
    for(i=0; i<n; i++){
        p = (Node*)malloc(sizeof(Node));/*生成新结点*/
        p->data = rand()%100+1;/*随机生成100内的数字*/
        p->next = p;/*将表尾终端结点的指针指向新结点*/
        r = p;
    }
    r->next = NULL;
}

3.3.7、单链表的整表删除

删除单链表，就是在内存中将它释放，以便于留出空间给其他软件使用：
（1）声明一结点p和q；（2）将第一个结点赋值给p；（3）循环：将下一个结点赋值给q；释放p；将q赋值给p；

Status ClearList(LinkList *L){
    LinkList p,q;
    p=(*L)->next;  /*p指向第一个结点*/
    while(p){
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=NULL;
    return ok;
}

3.3.8、单链表结构与顺序存储结构优缺点

Paste_Image.png

3.4、静态链表

3.4.1、定义

在C语言中，指针能力非常容易地操作内存中的地址和数据，在Java中，虽不使用指针，但因为启用了对象引用机制，从某种角度也间接实现了指针的某些作用。
让数组的元素都是由两个数据域组成，data和cur，数组的每个下标都对应一个data和一个cur。数据域data用来存放数据元素，游标cur相当于单链表中next指针，存放该元素的后继在数组中的下标。这样用数组描述的链表称为静态链表。数据结构如下，通常会将数组建大一些，不至于溢出。

#define MAXSIZE 1000 /*假设链表最大长度是1000*/
typeof struct{
    ElemType data;
    int cur; /*游标Cursor，为0表示无指向*/
} Component,StaticLinkList[MAXSIZE]

对数组第一个和最后一个元素作为特殊元素处理，不存数据，通常把未使用的数组元素称为备用链表。

Paste_Image.png

/*将一维数组space各分量链成一备用链表*/
/*space[0].cur为头指标，"0"表示空指针*/
Status InitList(StaticLinkList space){
    int i;
    for(i=0; i<MAXSIZE-1; i++)
        space[i].cur = i+1;
    space[MAXSIZE-1].cur = 0;
    return OK;
}

3.4.2、插入操作

解决：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。在动态链表中分别借用malloc()和free()实现申请和释放，在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放问题，需要自己实现这两个函数。
将未被使用过或已经删除的游标链组成一个备用的链表，每当进行插入时，从备用链表中取得第一个结点作为待插入的新结点。

/*若备用链表非空，则返回分配的结点下标，否则返回0*/
int Molloc_SSL(StaticLinkList space){
    int i = space[0].cur;
    if(space[0].cur)
        space[0].cur = space[i].cur;
    return i;
}

Paste_Image.png

实现插入的代码如下：

Status ListInsert(StaticLinkList L, int i, ElemType e){
    int j,k,l;
    k = MAXSIZE -1;/*k首先是最后一个元素的下标*/
    if(i<1 || i > ListLength(L)+1)
        return ERROR;
    j = Molloc_SSL(L);/*获得空闲的分量下标*/
    if(j){
        L[j].data = e; /*数据赋值操作*/
        for(l=1; l<i-1; l++)
            k = L[k].cur;
        L[j].cur = L[k].cur;
        L[k].cur = j;
        return OK;
    }
    return ERROR;
}

3.4.3、删除操作

删除元素时，需要释放结点的函数free()，需要自己实现：

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

删除元素：

/*删除在L中第i个数据元素e*/
Status ListDelete(StaticLinkList L, int i){
    int j,k;
    if(i < 1 || i>ListLength(L))
        return ERROR;
    k = MAXSIZE-1;
    for(j=1; j <= i-1; j++)
        k = L[k].cur;
    j = L[k].cur;
    L[k].cur = L[j].cur;
    Free_SSL(L,j);
    return OK;
}

Paste_Image.png

3.4.4、静态链表优缺点

Paste_Image.png

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

3.5、循环链表

循环链表（circular linked list）：将单链表中终端结点的指针端由空指针改成指向头结点，使得整个单链表形成一个环，头尾相接。

Paste_Image.png

改造整个循环列表，不用头指针，而是用指向终端结点的尾指针表示循环链表。

Paste_Image.png

3.6、双向链表

双向链表（double linked list）：在单链表的每个结点中，再设置一个指向其前驱结点的指针域。其数据存储结构如下：

typeof struct DulNode{
    ElemType data;
    struct DulNode *prior /*前驱指针*/
    struct DulNode *next /*后驱指针*/
} DulNode, *DuLinkList;

Paste_Image.png