一、线性表的定义

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

• 相同特性：把同一类事务归类，方便批量处理。
• 有限：表中元素个数为n，n有限大，n可以为0。
• 序列：表中元素排成一列，体现了一对一的逻辑特性（每一个元素有则仅有一个前驱和一个后继）。

二、存储结构

2.1、顺序存储结构

顺序存储结构可以使用数组加length实现。

A	B	C	...	X	...
0	1	2	...	length-1	...	maxSize-1

int A[maxSize];
int length = 0;

2.2、链式存储结构

链式存储结构可以通过自引用类型实现。

（1）单链表

有头结点的单链表：

有头结点单链表.png

无头结点的单链表：

无头结点单链表.png

单链表的实现如下：

typedef struct DLNode {
    int data;
    struct DLNode* next;
    struct DLNode* prior;
} DLNode;

    // 以下是伪代码
    DLNode *L;
    L = (DLNode*)malloc(sizeof(DLNode));
    A->next = B;
    B->next = C;
    C->next = D;
    D->prior = C;
    C->prior = B;
    B->prior = A;

有头结点的单链表的头结点判空：

Head->next = NULL;  为真

无头结点的单链表的头结点判空：

Head == NULL;  为真

（2）双链表

有头结点的双链表：

有头结点双链表.png

无头结点的双链表：

无头结点双链表.png

双链表的实现如下：

typedef struct DLNode {
    int data;
    struct DLNode* next;
    struct DLNode* prior;
} DLNode;

//伪代码
    DLNode *L;
    L = (DLNode*)malloc(sizeof(DLNode));
    A->next = B;
    B->next = C;
    C->next = D;
    D->prior = C;
    C->prior = B;
    B->prior = A;

有头结点的双链表的头结点判空：

Head -> next == NULL;  为真

无头结点的双链表的头结点判空：

Head == NULL;  为真

（3）循环链表

有头结点的单双循环链表：

有头结点的单双循环链表.png

无头结点的单双循环链表：

无头结点的单双循环链表.png

有头结点的单双循环链表的头结点判空：

• 单循环链表：

Head -> next == Head;  为真

• 双循环链表：

Head -> next == Head;  为真

或

Head -> prior == Head;   为真

无头结点的单双循环链表的头结点判空：

Head == NULL;  为真

我的博客：http://www.coderlearning.cn/

我的简书

我的微信公众号.jpg