数据结构（三）：线性表

一、线性表及其逻辑结构

1、线性表的定义

线性表是具有相同特性的数据元素的一个有限序列。

该序列中所含的元素个数叫做线性表的长度，用 n表示（n>=0）。当 n=0时，表示线性表是一个空表，即表中不包含任何数据元素。

线性表中的第一个元素叫做表头元素，最后一个元素叫做表尾元素。

线性表在位置上是有序的，即第 i个元素处在第 i-1个元素后面、第 i+1个元素前面，这种位置上的有序性就是线性关系，所以线性表是一个线性结构。

2、线性表的抽象数据类型描述

ADT List{
    //数据对象 括号内的 i是下标
    D = {a(i)|1=<i<=n, n>=0, a（i）属于 ElemType类型}
    //数据关系
    R = {<a(i), a(i+1)>, a(i+1)属于 D, i=1,···,n-1}
    //基本运算
    InitList(&L) //初始化线性表  该方法会将 L初始化为一个空的线性表
    DestroyList(&L) //销毁线性表  该方法会释放 L所占的储存空间
    ListEmpty(L) //确定线性表是否为空  若 L为空表则返回真，否则返回假
    DisPlayList(L) //输出线性表  按顺序输出线性表中各个节点的值
    GetElem(L, i, &e) //获取线性表中第 i个数据元素的值  并将该数据元素的值赋给 e（1=<i<=ListLength(L))
    LocateElem(L, e)  //返回 L中第一个和 e的值相等的数据元素的序号
    ListInsert(&L, i, e)  //在 L的第 i个元素之前插入 e，L的长度增加 1
    ListDelete(&L, i, &e)  //删除 L的第 i个元素并用 e返回其值
}

二、线性表的顺序存储结构

1、顺序表

线性表的顺序存储结构就是：把线性表中的数据元素按照其逻辑顺序一次存储到计算机存储器中指定存储位置的一块连续的存储空间中。这样，表头元素的存储位置就是指定存储空间的首地址，第 i个元素就紧挨着第 i+1个元素前面。

假设线性表中的数据元素为 ElemType，则每个数据元素所占的存储空间就是 sizeof(ElemType)，整个线性表占的存储空间就是 n*sizeof(ElemType)，其中 n是线性表的长度。

在 C/C++中数组中相邻的两个元素在内存中的位置也是相邻的，和顺序表的存储结构刚好一样，所以在 C/C++中我们可以使用数组来实现顺序表。

2、顺序表的基本算法实现

我们先定义顺序表和顺序表中的数据元素的类型：

#define INIT_LIST_LEN 50
#define INCREACEMENT_NUM 20
#define ERROR -1
#define OK 1
#define NULL_VALUE -51

typedef char ElemType;
typedef struct {
    ElemType *data;
    int length;
    int max_size;
}LinerList;

这里 ElemType是顺序表里的数据元素类型，LinerList是顺序表的类型。

在顺序表中，我们定义了一个 ElemType类型的数组指针 data，这个指针指向一块用来保存 ElemType类型数据的储存空间。

在使用中我们可以把 data直接看作一个 ElemType类型的数组，不过和数组不同的是 data的大小（相当于数组的长度）是可以动态改变的。

length就是顺序表当前的长度，max_size就是顺序表当前能够存储的最大元素数量。

当 length要大于 max_size时，我们会通过 realloc函数来为 data分配一块更大的内存（大小是原来的大小加上 INIT_LIST_LEN再乘以 sizeof(ElemType)）。

接下来我们来定义顺序表的基本运算：

void InitList(LinerList*& L) {
    L = (LinerList*)malloc(sizeof(LinerList));
    L->data = (ElemType*)malloc(INIT_LIST_LEN * sizeof(ElemType));
    L->max_size = INIT_LIST_LEN;
    L->length = 0;
}

void DestroyList(LinerList*& L) {
    free(L->data);
    free(L);
    L = NULL;
}

bool ListEmpty(LinerList L) {
    //当 L未初始化时 L.length小于 0
    //当 L初始化但为空时 L.length等于 0
    //两种情况都认为 L为空
    if (L->length <= 0) {
        return true;
    }
    else {
        return false;
    }
}

int ListLength(LinerList L) {
    //当 L未初始化时返回 -1
    if (L->length >= 0) {
        return L->length;
    }
    else{
        return ERROR;
    }
}

void DisplayList(LinerList L) {
    if (L->length < 0) {
        printf("This list is not inited.\n");
    }
    else if(L->length == 0){
        printf("This list is empty.\n");
    }
    else {
        for (int i = 1; i <= L->length; i++) {
            printf("ElmType %2d: %c\n", i, L->data[i]);
        }
    }
}

void GetElem(LinerList L, int i, ElemType* e) {
    if (i <= 0 || i > L.length) {
        printf("invalid integer i.\n");
    }
    else{
        *e = L.data[i];
    }
}

int LocateElem(LinerList L, ElemType e) {
    //包含对错误的处理
    for (int i = 1; i <= L.length; i++) {
        if (L.data[i] == e) {
            return i;
        }
    }
    return 0;
}

ListInsert：

int ListInsert(LinerList* L, int i, ElemType e) {
    if (L->length == L->max_size) {
        L->data = (ElemType*)realloc(L->data, (L->max_size + INCREACEMENT_NUM) * sizeof(ElemType));
        L->max_size += INCREACEMENT_NUM;
    }

    if (i > L->length + 1 || i <= 0) {
        return ERROR;
    }
    else {
        for (int k = L->length; k >= i; k--) {
            L->data[k + 1] = L->data[k];
        }
        L->data[i] = e;
        L->length++;
    }

    return OK;
}

在插入数据元素之前，我们要先检查顺序表长度是否已达到最大容量，如果顺序表已经达到最大长度，我们用 realloc重新分配一块更大的内存，并且顺序表的最大容量 max_size增加 INCREACEMENT_NUM（也就是 20）。

若顺序表还没达到最大容量，我们先对插入位置 i的有效性进行检查。

显然当 i小于或等于 0和 i大于顺序表长度加 1的时候是无效的。

当确定 i是有效的时候，我们才执行插入操作。

首先我们先把第 i个元素及其后面的所有元素向后移一个位置，然后再将数据元素 e插入到第 i个位置，并将顺序表的长度加 1.

ListDelete：

int ListDelete(LinerList* L, int i, ElemType* e) {
    if (i > L->length || i <= 0) {
        return ERROR;
    }
    else {
        *e = L->data[i];
        for (int k = i; k < L->length - 1; k++) {
            L->data[k] = L->data[k + 1];
        }
        L->data[L->length] = NULL_VALUE;
        L->length--;
    }
}

和插入数据元素时一样，我们在执行删除操作之前先检查 i的有效性，当 i的值有效时我们才进行下一步执行删除操作。

在删除目标数据元素之前，我们先将它的值赋给数据元素 e，然后再将其在顺序表中删除，并且顺序表的长度减 1。

在删除一个数据元素的时候，我们跟在该数据元素之后的所有数据元素向前移一个位置，然后将最后一个数据元素的值赋值为空值，最后将顺序表的长度减一。

测试：

int main() {
    LinerList* L = NULL;
    
    InitList(L);

    ElemType t;
    ElemType a = 'a';
    ElemType b = 'b';

    //检查顺序表是否为空
    if (ListEmpty(*L)) {
        printf("true\n");
    }
    else {
        printf("false\n");
    }

    //顺序表为空时删除
    ListDelete(L, 1, &t);
    //顺序表为空时输出顺序表
    DisplayList(*L);
    //顺序表为空时定位
    printf("the locate is %d\n", LocateElem(*L, b));
    //获取顺序表长度
    printf("list length: %d\n", ListLength(*L));

    for (int i = 0; i < 100; i++) {
        ListInsert(L, 1, a);
    }

    //检查顺序表是否为空
    if (ListEmpty(*L)) {
        printf("true\n");
    }
    else {
        printf("false\n");
    }


    //顺序表达到最大长度时插入
    ListInsert(L, 10, b);
    //顺序表达到最大长度时删除
    ListDelete(L, 1, &t);
    ListDelete(L, 1, &t);
    //给定过大的 i
    ListInsert(L, 100, a);
    ListInsert(L, 101, a);
    //顺序表不为空时定位
    printf("the locate is %d\n", LocateElem(*L, b));
    //获取顺序表长度
    printf("list length: %d\n", ListLength(*L));
    //输出顺序表
    DisplayList(*L);


    int c;
    scanf_s("%d", &c);
}

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

1、链表

在链式存储中，每个节点不仅包含有元素本省的信息（这称为数据域），还包含了元素之间的逻辑关系的信息，即前驱节点包含了后继节点的地址信息（这称为指针域），这样可以通过前驱节点指针域中的信息方便地找到后继节点地位置。

由于顺序表中每个数据元素最多只有一个前驱节点和一个后继节点，所以当采用链式存储时，一般在每个节点中只设置一个指针域，用来指向后继节点地位置，这样构成的链接表称为单向链接表，简称单链表。

另一种方法是，在每个节点中设置两个指针域，分别用来指向前驱节点和后继节点，这样构成的链表称为双链表。

在单链表中，由于每个节点只有一个指向后继节点的指针，所以当我们访问过一个节点后，只能接着访问它的后继节点，而无法访问它的前驱节点。在双链表中，由于每个节点既包含有指向前驱节点的指针，也包含了指向后继节点的指针，所以我们在访问过一个节点后，既可以依次访问它的前驱节点，也可以依次访问它的后继节点。

在线性表的链式存储中，为了方便插入和删除算法的实现，每个链表带有一个头节点，并通过头节点的指针唯一标识该链表。

在单链表中，每个节点应该包含存储元素的数据域和指向下一个节点的指针域，我们使用 C语言的结构体来定义单链表的节点类型：

typedef char ElemType;
typedef struct ListNode {
    ElemType data;
    ListNode* next;
} LinkList;

对于双链表。采用类似单链表的类型定义，不过和单链表不同的是，双链表有两个指针域。

typedef char ElemType;
typedef struct DListNode {
    ElemType data;
    DListNode* pre;
    DListNode* next;
} DLinkList;

2、单链表的基本运算实现

（1）头插法创建单链表

头插法创建链表的方法是：先创建一个头节点，然后将新节点插入到头节点的后面。注意这里的头节点只保存链表开始节点的地址，并不保数据，也就是说链表的第一个节点应该是头节点后面的第一个节点，头插法的算法实现如下：

void CreateLinkList(LinkList*& L, ElemType data[], int n) {
    L = (LinkList*)malloc(sizeof(LinkList));
    L->next = NULL;

    for (int i = 0; i < n; i++) {
        LinkList* p = (LinkList*)malloc(sizeof(LinkList));
        p->data = data[i];
        p->next = L->next;
        L->next = p;
    }
}

思考：

既然头节点不保存任何数据，能否另外再定义一个头节点类型来表示一个链表？

如：

typedef char ElemType;
typedef struct ListNode {
    ElemType data;
    ListNode* next;
} ListNode;
typedef struct {
    int length;
    ListNode *first_node
} LinkList;

这里 ElemType是要保存的数据类型，ListNode是链表的节点类型，LinkLIst是链表类型。

我们用 LInkList类型的变量来表示一个链表，它包含了一个指向链表开始节点的指针和表示链表长度的变量 length。

（2）尾插法创建单链表

头插法创建链表虽然简单，但是头插法创建的链表中的数据元素的顺序和原数组元素的顺序相反。如果希望两者的顺序一致，我们可以使用尾插法来创建链表。

尾插法建表时将数据元素添加到链表的尾部，所以我们需要一个指针来指向链表的尾部（这个指针指只在创建链表时使用）。

尾插法创建链表的算法如下：

void ECreateLinkList(LinkList*& L, ElemType data[], int n) {
    L = (LinkList*)malloc(sizeof(LinkList));
    L->next = NULL;

    LinkList* end = L; // end始终指向链表尾部

    for (int i = 0; i < n; i++) {
        LinkList* p = (LinkList*)malloc(sizeof(LinkList));
        p->data = data[i];
        end->next = p;
        end = p;
    }
    end->next = NULL;
}

销毁链表需要把每个节点的空间都释放：

void DestroyList(LinkList*& L){
    LinkList* p = L;
    LinkList* q = p->next;

    while(q != NULL) {
        free(p);
        p = q;
        q = p->next;
    }
    free(p);
}

（3）单链表的基本运算

void DestroyList(LinkList*& L){
    LinkList* p = L;
    LinkList* q = p->next;

    while(q != NULL) {
        free(p);
        p = q;
        q = p->next;
    }
    free(p);
}

bool ListEmpty(LinkList* L) {
    if (L->next == NULL) {
        return true;
    }
    else {
        return false;
    }
}

int ListLength(LinkList* L) {
    int i = 0;
    LinkList* t = L;

    while (t->next != NULL) {
        i++;
        t = t->next;
    }

    return i;
}

void DisplayList(LinkList* L) {
    if (L->next == NULL) {
        printf("list is empty.\n");
    }
    else {
        while (L->next != NULL) {
            L = L->next;
            printf("node data: %c\n", L->data);

        }
    }
}

void GetElem(LinkList* L, int i, ListNode*& e) {
    int count = 0;
    while (L->next != NULL && count < i) {
        L = L->next;
        count++;
    }

    if (count == i) {
        e = (ListNode*)malloc(sizeof(ListNode));
        e->data = L->data;
        e->next = L->next;
    }
    else {
        e = NULL;
    }
}

int LocateElem(LinkList* L, ListNode* e) {
    int i = 1;
    L = L->next;

    while (L != NULL && L->data != e->data) {
        L = L->next;
        i++;
    }

    if (L == NULL) {
        return 0;
    }
    else {
        return i;
    }
}

向链表中插入节点：

int ListInsert(LinkList* L, int i, ListNode* e) {
    int count = 0;
    while (count < i - 1 && L != NULL) {
        count++;
        L = L->next;
    }

    if (L == NULL || count == 0) {
        return 0;
    }
    else {
        LinkList* t = L->next;
        L->next = e;
        e->next = t;
        return 1;
    }
}

在向链表中插入节点时，我们先定位到第 i-1个节点。

如果第 i-1个节点存在，则 count=i-1，且 L不为空；如果第 i-1个节点不存在，则 L为空；如果输入的 i为非法值（比如负数），则 count为 0。

当第 i-1个节点存在时，直接将第 i-1个节点的 next指针指向要插入的节点，并将要插入的节点的 next指针指向第 i+1个节点（原来的第 i个节点）。

当第 i-1个节点不存在时，第 i个节点没有前驱节点，所以不能将节点插入到第 i个节点处。

删除链表中的节点：

int ListDelete(LinkList* L, int i, ListNode*& e) {
    int count = 0;
    while (count < i - 1 && L != NULL) {
        count++;
        L = L->next;
    }
    
    if (L != NULL && L->next != NULL && count != 0) {
        ListNode *t = L->next;
        e = (ListNode*)malloc(sizeof(ListNode));
        e->data = t->data;
        e->next = t->next;
        L->next = t->next;
        free(t);
        return 1;
    }
    else {
        e = NULL;
        return 0;
    }
}

和插入节点一样，在删除节点时我们也要先定位第 i-1个节点，不过和插入节点有一点不同的是，我们要先检查第 i个节点是否存在，只有当第 i个节点存在时我们才执行删除操作。

这里我们为什么要定位第 i-1个节点，而不是第 i个节点呢？

这是因为单链表只能单向访问，第 i个节点时无法访问第 i-1个节点的。所以如果我们定位到第 i个节点的话，就无法将第 i-1个节点指向后面一个节点了。

3、双链表的基本运算实现

双链表中有两个指针域，一个指向前驱节点、另一个指向后继节点。

typedef char ElemType;
typedef struct DListNode {
    ElemType data;
    DListNode* pre;
    DListNode* next;
} DLinkList;

和单链表类似，建立双链表也有两种方法：头插法和尾插法。

（1）头插法建立双链表

void CreateDoubleLinkList(DLinkList *&L, ElemType data[], int n) {
    L = (DLinkList*)malloc(sizeof(DLinkList));
    L->pre = NULL;
    L->next = NULL;

    for (int i = 0; i < n; i++) {
        DLinkList *t = (DLinkList*)malloc(sizeof(DLinkList));

        t->next = L->next;
        t->pre = L;
        t->data = data[i];

        L->next = t;

        if (t->next != NULL) {
            t->next->pre = t;
        }
    }
}

在头插法建立双链表的算法中，我们先为头节点分配存储空间并将头节点的两个指针域都赋值为 NULL。

在向双链表中插入节点时，我们总是将待插入的节点插入到头节点和开始节点之间。

插入节点时，我们先将待插入节点的 next指针指开始节点（也就是 L->next所指向的节点），再将待插入节点的 pre指针指向头节点，这时我们已经建立了待插入节点与头节点和开始节点之间的关系。

不过这时的关系还是单向的，我们还需要让头节点的 next指针指向待插入节点，这时头节点和待插入节点之间的双向关系就已经建立好了。

我们可以用同样的方法将待插入节点和其后继节点建立双向连接，不过在建立连接之前我们需要检查一下是否存在后继节点，存在后继节点才建立双向连接。

（2）尾插法建立双链表

void ECreateDoubleLinkList(DLinkList *&L, ElemType data[], int n) {
    L = (DLinkList*)malloc(sizeof(DLinkList));
    L->pre = NULL;
    L->next = NULL;

    //始终指向双链表尾部的指针
    DLinkList *end = L;

    for (int i = 0; i < n; i++) {
        DLinkList* t = (DLinkList*)malloc(sizeof(DLinkList));

        t->pre = end;
        t->data = data[i];

        end->next = t;

        end = t;
    }
    end->next = NULL;
}

最后一次修改于 2018年 9月 13日。

转载自：
数据结构教程（第二版）
李春葆 等 编著
清华大学出版社
ISBN：978-7-302-14229-4