[图解数据结构] 线性表

1.线性表的定义

若将线性表记为（a₁,...,a_i-1,a_i,a_i+1,...,a_n），则表中a_i-1领先于a_i，a_i领先于a_i+1，称a_i-1是a_i的直接前驱元素，a_i+1是a_i的直接后继元素。
线性表元素的个数n(n>=0)定义为线性表的长度，当n=0时，称为空表。
mark

2.线性表的顺序存储结构

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

线性表的顺序存储结构如图所示：

mark

2.1地址计算方法

用数组存储顺序表意味着要分配固定长度的数组空间，分配的数组空间大于等于当前线性表的长度，数据元素的序号和存放它的数组下标之间存在对应关系：

mark

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

每个数据元素都需要占用一定的存储单元空间的，假设占用的是c个存储单元，对于第i个数据元素a_i存储位置为（LOC表示获得存储位置的函数）：

LOC(a_i) = LOC(a₁) + (i-1)*c

mark

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

#define MAXSIZE 20 /*存储空间初始分配量*/
typedef int ElemType;

typedef struct 
{
    ElemType data[MAXSIZE]; /*数组存储数据元素*/
    int length;             /*线性表当前长度*/
}SqList;

描述线性表顺序存储的三个属性：

存储空间的起始位置：数组data,它的位置就是存储空间的存储位置。
线性表的最大存储容量：数组长度MAXSIZE。
线性表的当前长度：length。

2.3获得元素操作

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/*用e返回L中第i个数据元素的值*/
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.4插入操作

思路：

如果线性表长度大于等于数组长度，抛出异常
如果插入位置不合理，抛出异常
从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置
将要插入元素填入位置i
表长加1

/*在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;
}

插入前：

mark

插入后：

mark

2.5删除操作

思路：

如果为空表，抛出异常
如果删除位置不合理，抛出异常
从删除元素位置开始遍历到最后一个元素位置，分别将它们向前移动一个位置
表长减1

/*删除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)
    {
        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;
}

删除前：

mark

删除后：

mark

2.6优缺点

线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O（1）;而插入或删除时，时间复杂度都是O（n）。

优点：

无需为表示线性表中的逻辑关系而增加额外的存储空间
可以快速的存取线性表中任一位置的元素

缺点：

插入和删除操作需要移动大量的元素
难以确定线性表存储空间的容量
造成存储空间的“碎片”，浪费存储空间

3.线性表的链式存储结构

为了每个数据元素a_i与其后继数据元素a_i+1之间的逻辑关系，对数据元素a_i来说，除了存储本身的信息之外，还需要存储一个指示其后继元素的信息（即直接后继元素的存储位置）。
mark

3.1单链表

n个结点链结成一个链表，每个结点只包含一个指针域，叫做单链表。

线性链表中第一个结点的存储位置叫做头指针，整个链表的存取必须从头指针开始。线性链表的最后一个结点指针为“空”（通常用NULL或^表示）。

单链表存储示意图：

mark

空链表：

mark

3.1.1线性表链式存储的结构代码：

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

3.1.2单链表的读取

在单链表中读取第i个元素，我们无法一开始知道，必须从头开始找。

读取单链表中第i个数据的思路:

声明一指针p指向单链表第一个节点，初始化j=1
当j<i时，就遍历链表，让p的指针向后移动，不断的指向下一节点，j累加1
若到链表末尾p为空，则说明第i个节点不存在
否则查找成功，返回节点p的数据

代码实现：

#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;

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

动画模拟：

mark

3.1.3单链表的插入

假设存储元素e的节点为s,只需要将节点s插入到节点p和p->next之间即可。

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

也就是说让p的后继节点改成s的后继节点，再把节点s变成p的后继节点。

mark

注意：s->next = p->next;p->next = s;代码的顺序不能反。如果先p->next = s;,再s->next = p->next;，此时第一句会将p->next覆盖成s的地址了，那么s->next = p->next;实际上就等于s->next = s;。这样单链表将不再连续，插入操作就是失败的。对于单链表的表头和表尾的特殊情况，操作是相同的。

单链表第i个数据插入节点的思路：

声明一指针p指向单链表头结点，初始化j=1
当j<i时，就遍历链表，让p的指针向后移动，不断的指向下一节点，j累加1
若到链表末尾p为空，则说明第i个节点不存在
否则查找成功，生成一个空节点s作为插入节点
将数据元素e赋值给s->data
单链表插入的标准语句s->next = p->next;p->next = s;

代码实现：

#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;
typedef struct Node
{
    ElemType data;
    struct Node *next;
} Node;
typedef struct Node *LinkList;

/*初始条件：顺序线性表L已经存在，1<=i<=ListLength(L)*/
/*操作结果：在L中第i个节点位置之前插入新的数据元素e，L的长度加1*/
Status ListInsert(LinkList *L, int i, ElemType e)
{
    int j;
    LinkList p = *L;
    j = 1;

    while (p && j<i)    /*寻找第i-1个节点*/
    {
        p = p->next;
        ++j;
    }
    if (!p || j > i)
    {
        return ERROR;   /*第i个节点不存在*/
    }
    LinkList s = (LinkList)malloc(sizeof(Node));    /*生成新节点*/

    s->data = e;
    s->next = p->next; /*将p的后集节点赋值给s的后继*/
    p->next = s ;   /*将s赋值给p的后继*/
    return OK;
}

c语言的malloc标准函数，用于生成一个新的节点，实质就是在内存中分配内存用来存放节点。

测试代码：

int main()
{
    LinkList head = (LinkList)malloc(sizeof(Node)); /*头结点*/

    LinkList s1 = (LinkList)malloc(sizeof(Node));   /*第一个节点*/
    s1->data = 4;
    s1->next = NULL;

    head->next = s1;
    ListInsert(&head, 1, 2);     /*第1个节点前插入2*/
    ListInsert(&head, 2, 3);    /*第2个节点前插入3*/
    ListInsert(&head, 2, 7);    /*第1个节点前插入7*/
    ListInsert(&head, 3, 5);    /*第1个节点前插入5*/
}

运行结果：

mark

动画模拟：

mark

3.1.4单链表的删除

假设存储元素a_i的节点为q,要实现从单链表中将节点q删除的操作，其实是将它的前继节点的指针指向它的后继节点即可。

mark

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

单链表第i个数据删除节点的算法：

声明一指针p指向单链表头结点，初始化j=1
当j<i时，就遍历链表，让p的指针向后移动，不断的指向下一节点，j累加1
若到链表末尾p为空，则说明第i个节点不存在
否则查找成功，将欲删除的节点p->next赋值给q
将q节点中的数据赋值给e，作为返回
释放q节点

代码实现：

#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;
typedef struct Node
{
    ElemType data;
    struct Node *next;
} Node;
typedef struct Node *LinkList;

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

    free(q);        /*回收此节点，释放内存*/

    return OK;
}

c语言的free标准函数，作用是让系统回收一个节点，释放内存。

测试代码：

还是使用上面插入例子的单链表，然后删除单链表中的第3个节点：

int main()
{
    LinkList head = (LinkList)malloc(sizeof(Node)); /*头结点*/

    LinkList s1 = (LinkList)malloc(sizeof(Node));   /*第一个节点*/
    s1->data = 4;
    s1->next = NULL;

    head->next = s1;
    ListInsert(&head, 1, 2);     /*第1个节点前插入2*/
    ListInsert(&head, 2, 3);    /*第2个节点前插入3*/
    ListInsert(&head, 2, 7);    /*第1个节点前插入7*/
    ListInsert(&head, 3, 5);    /*第1个节点前插入5*/

    int e;
    ListDelete(&head, 3, &e);   /*删除第3个节点*/
}

运行结果：

mark

动画模拟：

mark

3.1.5单链表的整表创建

顺序存储结构的创建，其实就是一个数组的初始化；而单链表和顺序存储结构就不一样，它所占用的空间的大小和位置是不需要预先分配划定的。所以创建单链表的过程就是一个动态生成链表的过程，即从“空表”的初始状态起，依次建立各元素节点，并逐个插入链表。

单链表创建的思路:

声明一指针p和计数变量i
初始化一空链表L
让L的头结点的指针指向NULL，即建立一个带头结点的单链表
循环

生成一个新节点赋值给p
随机生成一数字赋值给p的数据域p->data
将p插入到头节点与前一新节点之间

头插法

代码实现：

/*头插法*/
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;     /*插入到表头*/
    }
}

测试代码：

int main()
{
    LinkList list;
    CreateListHead(&list, 5); /*创建一个有5个节点的单链表（不包含头结点）*/
}

运行结果：

mark

动画模拟：

mark

尾插法

代码实现：

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++)
    {
        p = (LinkList)malloc(sizeof(Node));
        p->data = rand() % 100 + 1;
        r->next = p;        /*将表尾终端节点的指针指向新节点*/
        r = p;  /*将当前的新节点定义为表尾终端节点*/
    }

    r->next = NULL;
}

注意L和r的关系，L是指整个单链表，而r是指向尾节点的变量，r会随着循环不断的变化节点，而L则是随着循环增长为一个多节点的链表。

测试代码：

int main()
{
    LinkList list;
    CreateListTail(&list, 5); /*创建一个有5个节点的单链表（不包含头结点）*/
}

运行结果：

mark

动画模拟：

mark

3.1.6单链表的整表删除

单链表整表删除的思路：

声明一节点p和q
将一个节点赋值给p
循环

将下一节点赋值给q
释放p
将q赋值给p

代码实现：

#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;
typedef struct Node
{
    ElemType data;
    struct Node *next;
} Node;
typedef struct Node *LinkList;

/*初始条件：顺序线性表L已经存在*/
/*操作结果：将L重置为空表*/
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;
}

测试代码：

int main()
{
    LinkList list;
    CreateListTail(&list, 5); /*用尾插法创建一个5个元素的单链表*/
    ClearList(&list);   /*清空单链表*/
}

运行结果：

mark

动画模拟：

mark

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

存储分配方式
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
单链表采用链式存储结构，用一组任意的存储单元存储线性表的元素
时间性能
查找
- 顺序存储结构O(1)
- 单链表O(n)
插入和删除
- 顺序存储结构O(n)
- 单链表O(1)
空间性能
顺序存储结构需要预先分配存储空间，分大了浪费空间，分小了容易造成内存溢出
单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

总结：若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构；若线性表频繁的进行插入和删除操作，或者线性表中的元素个数变化较大，或者根本不知道有多大时，宜采用单链表结构。

3.2循环链表

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

循环列表解决了一个很麻烦的问题：如何从一个节点出发，访问到链表的全部节点。

非空的循环列表：

mark

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

mark

其实循环列表和单链表的主要差异就在于循环的判断条件上，单链表是判断p->next是否为空，现在则是p->next不等于头结点，则循环未结束。

3.3双向链表

双向链表（double linked list）是在单链表的每个节点中，再设置一个指向其前驱节点的指针域。

3.3.1双向链表的读取

双向链表的读取其实和单链表的读取大同小异，只不过双向链表不用每一次都从头开始找节点，支持反向查找。

mark

3.3.2双向链表的插入

假设存储元素e的节点为s，要实现将节点s插入到节点p和p->next之间需要下面几步，如图所示：

mark

s->prior = p;           /*把p赋值给s的前驱,如图①*/
s->next = p->next;      /*将p的后继节点赋值给s的后继,如图②*/
p->next->prior = s;     /*将s赋值给p->next的前驱,如图③*/
p->next = s;            /*将s赋值给p的后继,如图④*/

操作顺序是先搞定s的前驱和后继，再搞定后节点的前驱，最后解决前节点的后继。顺序很重要，不能颠倒。

代码实现：

#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;
/*线性表的双向链表存储结构*/
typedef struct DulNode
{
    ElemType data;
    struct DulNode *prior;      /*直接前驱指针*/
    struct DulNode *next;       /*直接后继指针*/
} DulNode;
typedef struct DulNode *DulLinkList;

/*初始条件：顺序线性表L已经存在，1<=i<=ListLength(L)*/
/*操作结果：在L中第i个节点位置之前插入新的数据元素e，L的长度加1*/
Status DulListInsert(DulLinkList *L, int i, ElemType e)
{
    int j;
    DulLinkList p = *L;
    j = 1;

    while (p && j<i)    /*寻找第i-1个节点*/
    {
        p = p->next;
        ++j;
    }
    if (!p || j > i)
    {
        return ERROR;   /*第i个节点不存在*/
    }
    DulLinkList s = (DulLinkList)malloc(sizeof(DulNode));   /*生成新节点*/

    s->data = e;
    s->prior = p;               /*把p赋值给s的前驱*/
    s->next = p->next;      /*将p的后继节点赋值给s的后继*/
    p->next->prior = s;     /*将s赋值给p->next的前驱*/
    p->next = s;                    /*将s赋值给p的后继*/
    return OK;
}

测试代码：

int main()
{
    DulLinkList dulList;
    CreateDulListHead(&dulList, 5); /*初始化一个有5个节点的循环链表*/
    DulListInsert(&dulList, 3, 7);/*在循环链表第3个节点前插入数据7*/
}

运行结果：

mark

我们可以看出循环链表一个节点的前驱的后继或者后继的前驱都是它自己。

p->next->prior = p = p->prior->next

动画模拟：

mark

3.3.3双向链表的删除

如果插入操作理解了，那么删除操作就很简单了。

假设要删除节点p，需要下面两步，如图所示：

mark

p->prior->next = p->next;   /*将p->next赋值给p->prior的后继,如图①*/
p->next->prior = p->prior;  /*将p->prior赋值给p->next的前驱,如图②*/

代码实现：

#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;
/*线性表的双向链表存储结构*/
typedef struct DulNode
{
    ElemType data;
    struct DulNode *prior;      /*直接前驱指针*/
    struct DulNode *next;       /*直接后继指针*/
} DulNode;
typedef struct DulNode *DulLinkList;

/*初始条件：顺序线性表L已经存在，1<=i<=ListLength(L)*/
/*操作结果：删除L中第i个节点，并用e返回其值，L的长度减1*/
Status DulListDelete(DulLinkList *L, int i, ElemType *e)
{
    int j;
    DulLinkList p = *L;
    j = 1;
    while (p->next && j<i)  /*寻找第i-1个节点*/
    {
        p = p->next;
        ++j;
    }
    if (!(p->next) || j > i)
    {
        return ERROR;       /*第i个节点不存在*/
    }
    DulLinkList q = p->next;
    q->prior->next = q->next;       /*将q->next赋值给q->prior的后继*/
    q->next->prior = q->prior;  /*将q->prior赋值给q->next的前驱*/
    *e = q->data;   /*将q节点中的数据给e*/

    free(q);        /*回收此节点，释放内存*/

    return OK;
}

测试代码：

int main()
{
    DulLinkList dulList;
    ElemType e;
    CreateDulListHead(&dulList, 5); /*初始化一个有5个节点的循环链表*/
    DulListDelete(&dulList, 3, &e); /*删除循环链表第3个节点并赋值给e*/
}

运行结果：

mark

动画模拟：

mark

3.3.4双向循环链表

既然单链表可以有循环链表，那么双向链表当然也可以是循环链表。

双向链表的循环带头节点的空链表：

mark

双向链表的循环带头节点的非空链表：

mark

[图解数据结构] 线性表

[图解数据结构] 线性表

目录

1.线性表的定义

2.线性表的顺序存储结构

2.1地址计算方法

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

2.3获得元素操作

2.4插入操作

2.5删除操作

2.6优缺点

3.线性表的链式存储结构

3.1单链表

3.1.1线性表链式存储的结构代码：

3.1.2单链表的读取

3.1.3单链表的插入

3.1.4单链表的删除

3.1.5单链表的整表创建

头插法

尾插法

3.1.6单链表的整表删除

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

3.2循环链表

3.3双向链表

3.3.1双向链表的读取

3.3.2双向链表的插入

3.3.3双向链表的删除

3.3.4双向循环链表