线性表

线性表是最常用且最简单的一种数据结构，线性表就是n个数据元素的有限序列，线性表的特点是：

存在唯一一个第一个的数据元素。
存在唯一一个最后一个的数据元素。
除第一个元素外，每个元素都有一个前驱。
除最后一个元素外，每个元素都有一个后继。

线性表分为静态表，和动态链表，静态表中数据在内存中依次存放地址相邻，动态链表中每个元素都包含一个指向下一个元素的地址，彼此地址不相邻。

静态表

静态表也称为线性表的顺序表示，是用一组地址连续的存储单元依次存储数据元素，数组就是一个静态表，静态表的优势是地址连续，可以做到随机存取元素i，只要根据其下标就可以，缺点是每当你想要在其中插入或删除元素i时，必须移动（表长-i）个元素，极大的浪费时间。静态表的操作参考数组就好，这里不进行过多的介绍。

链表

链表也称为线性表的链式存储，它不要求逻辑上相邻的元素在地址上也相邻，因此它没有顺序存储结构所具有的弱点，但也失去了可随即存储的优点。

线性链表

链表的结构特点是用一组任意的存储单元存储线性表数据元素，保证数据元素在逻辑上相邻，但不保证在物理地址上相邻，其中元素中包含两个部分，一部分是数据域，存储数据，另一部分称为指针域，存储所指向的下一个存储单元地址。

线性链表存储结构

typedef int ElementType;        //    定义数据类型,可根据需要进行其他类型定义
//    链表节点的定义
typedef struct ListNode {
    ElementType  Element;        //    数据域，存放数据
    struct ListNode *Next;        //    指向下一个链表节点
}Node, *PNode;

先进行数据类型的定义，方便日后修改，这里先设置为int整形，之后用结构体来表示存储结构，因为结构体可以存储多种数据类型的数据。结构体中包含了Element数据，Next指向结构体本身的指针，给存储结构起了名字叫做Node，结构指针的名字叫做PNode。

创建链表

往往我们在创建链表的时候，会创建一个头结点，头节点的数据域可以不存放数据，也可以存储一些链表的信息，例如长度等附加信息，头结点的指针域存储指向第一个结点的指针，起到一个哨兵的作用。下面放上创建链表的代码：

PNode CreateList(void) {
    int len ;    //    用于定义链表长度
    int val ;    //    用于存放节点数值
    PNode PHead = (PNode)malloc(sizeof(Node));    //    创建分配一个头节点内存空间
//头节点相当于链表的哨兵，不存放数据，指向首节点（第一个节点）
    if (PHead == NULL)    //    判断是否分配成功
    {
        printf("空间分配失败 \n");
        exit(-1);
    }

    PNode PTail = PHead;    //    链表的末尾节点，初始指向头节点
    PTail->Next = NULL;    //    最后一个节点指针置为空
    printf("请输入节点个数：");
    scanf("%d", &len);        //    输入节点个数
    for (int i = 0; i < len; i++) {
        PNode pNew = (PNode)malloc(sizeof(Node));    //    分配一个新节点
        if (pNew == NULL) {
            printf("分配新节点失败\n");
            exit(-1);
        }
        printf("请输入第 %d 个节点的数据：", i + 1);
        scanf("%d", &val);    //    输入链表节点的数据

        pNew->Element = val;    //    把数据赋值给节点数据域
        PTail->Next = pNew;    //    末尾节点指针指向下一个新节点
        pNew->Next = NULL;        //    新节点指针指向为空
        PTail = pNew;    //    将新节点复制给末尾节点
    }
    printf("创建链表成功\n");
    return PHead;    //    返回头节点
}

创建链表，返回一个头结点，首先创建一个头结点并对其分配内存空间，如果内存分配失败，则失败分配失败。之后创建一个末尾结点，其指针域指向头结点（并不是*Next指向头结点而是PTail指针本身指向头结点），把末尾结点的Next指针指向NULL也就是指向空。然后初始化链表，创建一个新结点，并为其分配内存空间，之后把输入的数据传给新结点，末尾结点的指针指向新节点，新节点的指针指向NULL，末尾指针指向新节点。

打印链表，逆序打印链表

因为链表的结构原因，访问链表只能从头结点开始依次访问，这里通过打印链表来体现访问链表：

//打印链表
void TraverseList(PNode List) {
    PNode P = List->Next;    //    首节点赋值给临时节点P
    printf("遍历链表的值为：");
    if (P == NULL)
        printf("链表为空");
    while (P != NULL)        //当临时节点P不为尾节点时，输出当前节点值
    {
        printf("%d ", P->Element);
        P = P->Next;
    }
    printf("\n");
}
//逆序打印链表
void TraverseListF(PNode List){
    PNode  Q;
    PNode  P = List->Next;      //首结点赋值给临时节点P
    printf("逆序遍历链表的值为：");
    while(P->Next){
        Q = P->Next;
        P->Next = Q->Next;
        Q->Next = List->Next;
        List->Next = Q;
    }
    TraverseList(List);
}

顺序打印链表，创建一个临时节点，把首结点赋值个临时节点，设置循环判断边界为临时结点的指针不指向NULL，输出链表的数据域，新节点指向新节点的下一个节点。逆序打印链表操作基本同顺序打印链表，但需要设置两个节点，先把首结点赋值给临时节点p，p指向首节点，q节点指向p节点的下一个节点，q节点的指针指向首结点。实现逆序链表。

链表的插入

链表的基本操作，链表的插入：

//算法2.8 单链表实现插入
void ListInsert(PNode L, int i,int e) {
    int j = 0;
    PNode p = L;    //    定义节点p指向头节点
    //    寻找i节点的前驱结点
    while (p &&j < i - 1)
    {
        p = p->Next;
        ++j;
    }
    PNode s = (PNode)malloc(sizeof(Node));    //    分配一个临时节点用来存储要插入的数据
    if (s == NULL)
    {
        printf("内存分配失败！");
        exit(-1);
    }
    //    插入节点
    s->Element = e;
    s->Next = p->Next;
    p->Next = s;
}

寻找节点的前驱结点，分配一个临时节点存储插入的数据，临时节点先指向前驱结点的指针所指向的节点，前驱结点的指针指向临时节点。

删除结点

void ListDelet(PNode L,int i){
    int j = 0;
    PNode p = L;
    while(p != NULL&& j < i - 1){
        p = p->Next;
        ++j;
    }
    PNode q = p->Next; //定义q为要删除的结点
    p->Next = q->Next;
    free(q);        //回收内存
    q = NULL;       //回收野指针
}

建立一个新的结点p指向首结点，寻找删除节点的前驱结点，再建立一个新的结点q指向前驱结点的后继，使p结点的指针指向q结点的后继，之后释放结点q。还可以p->Next = p->Next->Next,但是缺点是被删除的结点无法被释放，会造成浪费。

合并链表

把链表a和b合并到a：

//算法2.11 合并链表La，Lb 到La
void MergeList_L(PNode La,PNode Lb){
    while(La->Next != NULL){    //链表La，Lb合并到 La
        La = La->Next;
    }
    La->Next = Lb->Next;        //链表La末尾指针指向头结点指针所指向位置，就是Lb的第一个节点
    free(Lb);       //回收内存
    Lb = NULL;      //回收野指针
}

遍历链表找到链表a的结尾节点，使结点的指针指向链表b首结点的指针，就是指向链表b的头结点。

双向链表

遍历单链表的时候只能从头结点开始遍历，如果在每个数据元素再加入一个前驱指针，可以从后遍历链表，叫做双向链表。

创建双向链表

//创建双向链表
DuNode CreativeDuList(){
    int len ;    //    用于定义链表长度
    int val ;    //    用于存放节点数值
    DuNode DHead = (DuNode)malloc(sizeof(DNode));    //    创建分配一个头节点内存空间
//头节点相当于链表的哨兵，不存放数据，指向首节点（第一个节点）
    DHead->prior = NULL;    //头节点前驱为Null
    if (DHead == NULL)    //    判断是否分配成功
    {
        printf("空间分配失败 \n");
        exit(-1);
    }
    DuNode DTail = DHead;    //    链表的末尾节点，初始指向头节点
    DTail->Next = NULL;    //    最后一个节点next指针置为空
    DTail->prior = NULL;    //      最后一个节点prior指针为空
    printf("请输入节点个数：");
    scanf("%d", &len);        //    输入节点个数
    for (int i = 0; i < len; i++) {

        DuNode dNew = (DuNode)malloc(sizeof(DNode));    //    分配一个新节点
        if (dNew == NULL) {
            printf("分配新节点失败\n");
            exit(-1);
        }
        printf("请输入第 %d 个节点的数据：", i + 1);
        scanf("%d", &val);    //    输入链表节点的数据

        dNew->Element = val;    //    把数据赋值给节点数据域
        DTail->Next = dNew;    //    末尾节点指针指向下一个新节点
        dNew->Next = NULL;        //    新节点next指针指向为空
        dNew->prior = DTail;        //新节点prior指针指向尾结点
        DTail = dNew;    //    将新节点复制给末尾节点
    }
    printf("创建链表成功\n");
    return DHead;    //    返回头节点
}

创建双向链表操作如同单链表的操作，只是在初始化的时候把前驱指针指向尾节点就好了。

遍历双向链表

操作同单链表：

//  遍历双向链表
void TraverseDlist(DuNode List) {
    DuNode P = List->Next;    //    首节点赋值给临时节点P
    printf("遍历链表的值为：");
    if (P == NULL)
        printf("链表为空");
    while (P != NULL)        //当临时节点P不为尾节点时，输出当前节点值
    {
        printf("%d ", P->Element);
        P = P->Next;
    }
    printf("\n");
}

插入新结点

//算法 2.18 双向链表插入元素
void ListDinsert(DuNode L, int i,int e){
    int j = 0;
    DuNode p = L;   //定义结点p指向头节点
    while(j < i && p != NULL){        //找到插入节点的后继
        p = p->Next;
        j++;
    }
    DuNode s = (DuNode)malloc(sizeof(DNode));       //分配一块内存给新节点
    s->Element = e;     //赋值给新节点
    s->prior = p->prior;    //新节点的prior指向第i位置的prior
    p->prior->Next = s; //第i位置prior的next指针指向新节点
    s->Next = p;    //新节点next指向第i节点
    p->prior = s;   //第i节prior指向新节点
}

定义结点p指向头节点，再定义个新的结点并分配存储空间，并给新结点赋值，新节点的前继指针指向插入节点的前驱，插入结点的前驱指针所指向的后继指向新节点，最后把新节点的Next指向第i节点，插入指针的前驱结点指向新结点。

删除结点

只需更改删除节点的后继的前驱指针指向删除节点的前驱，删除节点的前驱的后继指针指向删除节点的后继指针。

//算法2.19 双向链表删除元素
void ListDdelet(DuNode L,int i){
    int j = 0;
    DuNode p = L;
    while(p != NULL&& j < i - 1){
        p = p->Next;
        ++j;
    }
    p->Next->prior = p->prior;  //后一节点的prior为被删除节点的prior
    p->prior->Next = p->Next;   //前一节点的next为被删除节点的next
    free(p);        //回收内存
    p = NULL;       //回收野指针
}

最后附上完整的代码

//
// Created by kingLower on 2018/10/23.
//
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

typedef int ElementType;        //    定义数据类型,可根据需要进行其他类型定义
//    链表节点的定义
typedef struct ListNode {
    ElementType  Element;        //    数据域，存放数据
    struct ListNode *Next;        //    指向下一个链表节点
}Node, *PNode;

//算法2.10    链表创建函数定义从表头到表尾逆向建立单链表
PNode CreateList(void) {
    int len ;    //    用于定义链表长度
    int val ;    //    用于存放节点数值
    PNode PHead = (PNode)malloc(sizeof(Node));    //    创建分配一个头节点内存空间
//头节点相当于链表的哨兵，不存放数据，指向首节点（第一个节点）
    if (PHead == NULL)    //    判断是否分配成功
    {
        printf("空间分配失败 \n");
        exit(-1);
    }

    PNode PTail = PHead;    //    链表的末尾节点，初始指向头节点
    PTail->Next = NULL;    //    最后一个节点指针置为空
    printf("请输入节点个数：");
    scanf("%d", &len);        //    输入节点个数
    for (int i = 0; i < len; i++) {
        PNode pNew = (PNode)malloc(sizeof(Node));    //    分配一个新节点
        if (pNew == NULL) {
            printf("分配新节点失败\n");
            exit(-1);
        }
        printf("请输入第 %d 个节点的数据：", i + 1);
        scanf("%d", &val);    //    输入链表节点的数据

        pNew->Element = val;    //    把数据赋值给节点数据域
        PTail->Next = pNew;    //    末尾节点指针指向下一个新节点
        pNew->Next = NULL;        //    新节点指针指向为空
        PTail = pNew;    //    将新节点复制给末尾节点
    }
    printf("创建链表成功\n");
    return PHead;    //    返回头节点
}

//打印链表
void TraverseList(PNode List) {
    PNode P = List->Next;    //    首节点赋值给临时节点P
    printf("遍历链表的值为：");
    if (P == NULL)
        printf("链表为空");
    while (P != NULL)        //当临时节点P不为尾节点时，输出当前节点值
    {
        printf("%d ", P->Element);
        P = P->Next;
    }
    printf("\n");
}
//逆序打印链表
void TraverseListF(PNode List){
    PNode  Q;
    PNode  P = List->Next;      //首结点赋值给临时节点P
    printf("逆序遍历链表的值为：");
    while(P->Next){
        Q = P->Next;
        P->Next = Q->Next;
        Q->Next = List->Next;
        List->Next = Q;
    }
    TraverseList(List);
}

//算法2.8 单链表实现插入
void ListInsert(PNode L, int i,int e) {
    int j = 0;
    PNode p = L;    //    定义节点p指向头节点
    //    寻找i节点的前驱结点
    while (p &&j < i - 1)
    {
        p = p->Next;
        ++j;
    }
    PNode s = (PNode)malloc(sizeof(Node));    //    分配一个临时节点用来存储要插入的数据
    if (s == NULL)
    {
        printf("内存分配失败！");
        exit(-1);
    }
    //    插入节点
    s->Element = e;
    s->Next = p->Next;
    p->Next = s;
}

//算法2.9 删除结点
void ListDelet(PNode L,int i){
    int j = 0;
    PNode p = L;
    while(p != NULL&& j < i - 1){
        p = p->Next;
        ++j;
    }
    PNode q = p->Next; //定义q为要删除的结点
    p->Next = q->Next;
    free(q);        //回收内存
    q = NULL;       //回收野指针
}

//算法2.11 合并链表La，Lb 到La
void MergeList_L(PNode La,PNode Lb){
    while(La->Next != NULL){    //链表La，Lb合并到 La
        La = La->Next;
    }
    La->Next = Lb->Next;        //链表La末尾指针指向头结点指针所指向位置，就是Lb的第一个节点
    free(Lb);       //回收内存
    Lb = NULL;      //回收野指针
}
// 双向链表
typedef struct DuNode {
    ElementType  Element;        //    数据域，存放数据
    struct DuNode *Next;        //    指向下一个链表节点
    struct DuNode *prior;        //    指向上一个链表节点
}DNode, *DuNode;

//创建双向链表
DuNode CreativeDuList(){
    int len ;    //    用于定义链表长度
    int val ;    //    用于存放节点数值
    DuNode DHead = (DuNode)malloc(sizeof(DNode));    //    创建分配一个头节点内存空间
//头节点相当于链表的哨兵，不存放数据，指向首节点（第一个节点）
    DHead->prior = NULL;    //头节点前驱为Null
    if (DHead == NULL)    //    判断是否分配成功
    {
        printf("空间分配失败 \n");
        exit(-1);
    }
    DuNode DTail = DHead;    //    链表的末尾节点，初始指向头节点
    DTail->Next = NULL;    //    最后一个节点next指针置为空
    DTail->prior = NULL;    //      最后一个节点prior指针为空
    printf("请输入节点个数：");
    scanf("%d", &len);        //    输入节点个数
    for (int i = 0; i < len; i++) {

        DuNode dNew = (DuNode)malloc(sizeof(DNode));    //    分配一个新节点
        if (dNew == NULL) {
            printf("分配新节点失败\n");
            exit(-1);
        }
        printf("请输入第 %d 个节点的数据：", i + 1);
        scanf("%d", &val);    //    输入链表节点的数据

        dNew->Element = val;    //    把数据赋值给节点数据域
        DTail->Next = dNew;    //    末尾节点指针指向下一个新节点
        dNew->Next = NULL;        //    新节点next指针指向为空
        dNew->prior = DTail;        //新节点prior指针指向尾结点
        DTail = dNew;    //    将新节点复制给末尾节点
    }
    printf("创建链表成功\n");
    return DHead;    //    返回头节点
}
//  遍历双向链表
void TraverseDlist(DuNode List) {
    DuNode P = List->Next;    //    首节点赋值给临时节点P
    printf("遍历链表的值为：");
    if (P == NULL)
        printf("链表为空");
    while (P != NULL)        //当临时节点P不为尾节点时，输出当前节点值
    {
        printf("%d ", P->Element);
        P = P->Next;
    }
    printf("\n");
}

//算法 2.18 双向链表插入元素
void ListDinsert(DuNode L, int i,int e){
    int j = 0;
    DuNode p = L;   //定义结点p指向头节点
    while(j < i && p != NULL){        //找到插入节点的后继
        p = p->Next;
        j++;
    }
    DuNode s = (DuNode)malloc(sizeof(DNode));       //分配一块内存给新节点
    s->Element = e;     //赋值给新节点
    s->prior = p->prior;    //新节点的prior指向第i位置的prior
    p->prior->Next = s; //第i位置prior的next指针指向新节点
    s->Next = p;    //新节点next指向第i节点
    p->prior = s;   //第i节prior指向新节点
}
//算法2.19 双向链表删除元素
void ListDdelet(DuNode L,int i){
    int j = 0;
    DuNode p = L;
    while(p != NULL&& j < i - 1){
        p = p->Next;
        ++j;
    }
    p->Next->prior = p->prior;  //后一节点的prior为被删除节点的prior
    p->prior->Next = p->Next;   //前一节点的next为被删除节点的next
    free(p);        //回收内存
    p = NULL;       //回收野指针
}
//    主函数
int main() {
    PNode List = CreateList();    //创建一个指针，使其指向新创建的链表的头指针
    ListInsert(List,3,5);   //在第1个位置前加入结点值为5
    TraverseListF(List);     //打印链表
//    PNode List2 = CreateList();    //创建一个指针，使其指向新创建的链表的头指针
//    MergeList_L(List,List2);
//    TraverseList(List);     //打印链表
//    ListDelet(List,3); //删除结点
//    TraverseList(List);     //打印链表
//    DuNode DList = CreativeDuList(); //创建双向链表
//    ListDinsert(DList,2,5);
//    TraverseDlist(DList);   //打印双向链表
//    ListDdelet(DList,3);
//    TraverseDlist(DList);   //打印双向链表
    return 0;
}

循环链表

循环链表是另一种形式的链式存储结构，表中最后一个节点的指针指向头结点，整个链表形成一个环。优点在于从表中任意一个节点出发可以遍历整个链表，循环链表的基本操作一致，差别在于算法的循环条件不是Next->NULL而是，Next->头结点。

线性表

静态表链表双向链表

线性表

静态表

链表

线性链表

线性链表存储结构

创建链表

打印链表，逆序打印链表

链表的插入

删除结点

合并链表

双向链表

创建双向链表

遍历双向链表

插入新结点

删除结点

循环链表

CATALOG

FEATURED TAGS

FRIENDS