• 【数据结构】24王道考研笔记——线性表

    线性表

    目录

    定义和基本操作

    线性表的定义：线性表时具有相同数据类型的n（n>=0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。

    L=(a1,a2,a3…,an) a1为表头元素，an为表尾元素，除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素，每个元素有且仅有一个直接后继。

    特点：

    1. 元素个数有限
    2. 元素具有逻辑上的顺序性，表中元素有其先后次序
    3. 元素都是数据元素，每个元素都是单个元素
    4. 元素数据类型相同，占有相同大小的存储空间
    5. 元素具有抽象性

    线性表是一种逻辑结构，表示元素之间一对一的相邻关系，顺序表和链表是指存储结构。

    线性表基本操作：

    image.png

    总结：

    image.png

    顺序表

    线性表的顺序存储称为顺序表，使用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。i为ai在线性表中的位序，元素的逻辑顺序与其物理顺序相同。

    image.png

    线性表的顺序存储结构是一种随机存储的存储结构。

    顺序表的特点：

    1. 随机访问，可以在O（1）时间内找到第i个元素 data[i-1]
    2. 存储密度高，每个结点智存初数据元素
    3. 拓展容量不方便（即使采用动态分配，拓展长度时间复杂度仍较高）
    4. 插入、删除操作不方便，需要移动大量元素

    静态顺序表

    一维数组可以静态分配也可以动态分配，静态分配时，数组大小和空间事先固定，不可变。而动态顺序表则不需要为线性表一次性划分所有空间。

    结构体：

    #define MaxSize 50

typedef struct {
    int data[MaxSize];
    int length;
} SqList;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    初始化：

    //初始化
void InitList(SqList& L) {
    for (int i = 0; i < MaxSize; i++) {
        L.data[i] = 0;//将所有元素的初始值默认设置为0
        //这一步其实可以省略，但是省略之后，有可能受到内存中"脏数据"的影响
    }
    L.length = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    判空：

    //判断是否为空
bool Empty(SqList L) {
    return (L.length == 0);
}

    • 1
    • 2
    • 3
    • 4

    插入：

    //插入
bool ListInsert(SqList& L, int i, int e) {
    //判断插入的位置是否合法，
    if (i < 1 || i > L.length + 1)
        return false;
    //判断表是否存满了
    if (L.length >= MaxSize)
        return false;

    //后面的元素后移
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    删除：

    //删除
bool ListDelete(SqList& L, int i, int& e) {
    //判断i的位置是否合法
    if (i < 0 || i > L.length) {
        return false;
    }
    //取出将要被删除的数
    e = L.data[i - 1];
    //将其后的数据前移
    for (int j = i; j <= L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    //线性表长度减一
    L.length--;
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    查找：

    //查找
//按位查找
int GetElem(SqList L, int i) {
    //判断是否越界
    if (i < 0 || i > L.length)
        return -1;
    return L.data[i - 1];
}
//按值查找
int LocateElem(SqList L, int e) {
    //循环出查找
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e)
            return i + 1; //返回位序
    }
    return -1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    改值：

    //先查找后改值
//由此分为两种方式，先按位查找后改值；或先按值查找后改值
//先按值查找后改值
bool LocateChangeElem(SqList& L, int e, int em) {
    //按值查找得到位序
    int bitOrder = LocateElem(L, e);
    //改值
    if (bitOrder != -1) {
        L.data[bitOrder] = em;
        return true;
    }
    else {
        return false;
    }
}

//先按位序查找后改值
bool getChangeElem(SqList& L, int i, int em) {
    //给的位序,首先判断i是否合法
    if (i < 0 || i >= L.length)return false;

    //由于是用数组实现的方式，可以直接利用i查找
    L.data[i] = em;
    return true;

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    打印：

    //打印整个顺序表
void PrintSqList(SqList L) {
    //循环打印
    printf("开始打印顺序表\n");
    for (int i = 0; i < L.length; i++) {
        printf("Data[%d]==%d\n", i, L.data[i]);
    }
    printf("打印结束！\n");
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    动态顺序表

    一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储空间的目的。

    结构体：

    #define InitSize 100
typedef struct {
    int* data; //指示动态分配数组的指针
    int MaxSize;//顺序表的最大容量
    int length;//顺序表当前的长度
} SeqList;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    初始化：

    //初始化
bool InitList(SeqList& L) {
    //用 malloc 函数申请一片连续的存储空间
    L.data = (int*)malloc(InitSize * sizeof(int));
    if (L.data == NULL)
        return false;
    //(int *) 是指针的强制类型转换
    L.length = 0;
    L.MaxSize = InitSize;
    return true;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    判空：

    //判空
bool Empty(SeqList L) {
    return (L.length == 0);
}

    • 1
    • 2
    • 3
    • 4

    判满：

    //判满
bool Full(SeqList L) {
    return (L.length >= L.MaxSize);
}

    • 1
    • 2
    • 3
    • 4

    扩展空间：

    //扩展空间
void IncreaseSize(SeqList& L, int len) {
    int* p = L.data;
    L.data = (int*)malloc((InitSize + len) * sizeof(int));
    for (int i = 0; i < L.length; i++) {
        L.data[i] = p[i];
    }
    L.MaxSize = L.MaxSize + len;
    free(p);
    //malloc 函数用于申请内存空间；free 函数用于释放内存空间；
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    插入：

    //插入
bool ListInsert(SeqList& L, int i, int e) {
    //判断插入的位置是否合法，
    if (i < 1 || i > L.length + 1)
        return false;
    //判断表是否存满了
//    if (L.length>=L.MaxSize)
//        return fals;
    if (Full(L))
        return false;

    //后面的元素后移
    for (int j = L.length; j >= i; j--) {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    按位查找：

    //按位查找
int GetElem(SeqList L, int i) {
    //判断是否越界
    if (i < 0 || i > L.length)
        return -1;
    return L.data[i - 1];
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    按值查找：

    //按值查找
int LocateElem(SeqList L, int e) {
    //循环出查找
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e)
            return i + 1; //返回位序
    }
    return -1;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    删除：

    //删除
bool ListDelete(SeqList& L, int i, int& e) {
    //判断i的位置是否合法
    if (i < 0 || i > L.length) {
        return false;
    }
    //取出将要被删除的数
    e = L.data[i - 1];
    //将其后的数据前移
    for (int j = i; j <= L.length; j++) {
        L.data[j - 1] = L.data[j];
    }
    //线性表长度减一
    L.length--;
    return true;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    销毁：

    //销毁
//由于动态分配方式使用malloc申请的内存空间，故需要使用free函数手动释放空间！
void DestroySqList(SeqList& L) {
    free(L.data);
    L.data = NULL;
    L.length = 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    打印：

    //打印整个顺序表
void PrintSqList(SeqList L) {
    if (L.data == NULL || L.length == 0)
        printf("这是一个空表！");
    else {
        //循环打印
        printf("开始打印顺序表\n");
        for (int i = 0; i < L.length; i++) {
            printf("Data[%d]==%d\n", i, L.data[i]);
        }
        printf("打印结束！\n");
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    总结：

    image.png

    链表

    单链表

    线性表的链式存储称为单链表，它指通过一组任意的存储单元来存储线性表中的数据元素。每个链表结点存放元素自身的信息外，还需要存放一个指向其后继的指针。

    image.png

    结构体：

    //结构体
typedef struct LNode {
    int data;
    struct LNode* next;
} LNode, * LinkList;
//等价于
//struct LNode{
//    int data;
//    struct LNode *next;
//};
//
//typedef struct LNode LNode;
//typedef struct LNode *LinkList;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    LinkList强调为单链表 LNode*强调为结点，两者等价

    不带头结点：

    初始化：

    //初始化
bool InitList(LinkList& L) {
    L = NULL;//空表暂时没有任何数据
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5

    判空：

    //判断是否为空
bool Empty(LinkList L) {
    return (L == NULL);
}
//等价于
//bool Empty1(LinkList L){
//    if (L==NULL)
//        return true;
//    else
//        return false;
//}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    插入：

    //在指定位置插入元素
bool ListInsert(LinkList& L, int i, int e) {
    if (i < 1)return false;//判断位序i是否合法
    //不带头节点时，插入位置正好为表头时，得单独处理
    if (i = 1) {
        LNode* s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;
        return true;
    }
    LNode* p;//指针指向当前扫面到的节点
    int j = 0;//记录p指向的节点的位序
    p = L;//L指向头节点，从头开始
    while (p != NULL && j < i - 1) {
        //循环扫描
        p = p->next;
        j++;
    }
    if (p == NULL) //i值超过来表长，不合法
        return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    //下面的顺序不可交换
    s->next = p->next;
    p->next = s;
    return true;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    带头结点：

    初始化：

    //初试化(带有头节点)
bool InitList(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));//分配一个头节点
    if (L == NULL)
        return false;//头节点分配失败，可能是内存不足
    L->next = NULL;//头节点之后暂时没有节点，头节点也不存放数据
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    判空：

    //判空
bool Empty(LinkList L) {
    return (L->next == NULL);
}

    • 1
    • 2
    • 3
    • 4

    打印链表：

    void PrintList(LinkList L) {
    //循环打印整个链表
    LNode* p = L->next;//扫描指针
    int j = 0;
    if (p == NULL)printf("这是一个空表\n");
    while (p != NULL) {
        printf("LinkList[%d]=%d\n", j, p->data);
        p = p->next;
        j++;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    按位插入：

    image.png

    //按位插入
bool ListInsert(LinkList& L, int i, int e) {
    if (i < 1)return false;//判断位序i是否合法
    LNode* p;//指针指向当前扫面到的节点
    int j = 0;//记录p指向的节点的位序
    p = L;//L指向头节点，从头开始
    while (p != NULL && j < i - 1) {
        //循环扫描
        p = p->next;
        j++;
    }
    if (p == NULL) //i值超过来表长，不合法
        return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    //下面的顺序不可交换
    s->next = p->next;
    p->next = s; //将结点s连到p之后
    return true;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    后插操作：（包含于之前的插入操作之中）

    //指定节点的后插操作
bool InsertNextNode(LNode* p, int e) {
    if (p == NULL)
        return false;//判断指定节点是否存在
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL)return false;//分配内存失败
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    前插操作：由于难以获得前一个链表元素信息，所以先完成后插，再交换两者数据实现前插

    //指定节点的前插操作
//先完成后插，再交换数据以实现前插
bool InsertPriorNode(LNode* p, int e) {
    if (p == NULL)return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL)return false;
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    按指定位序删除并返回值：

    //按指定位序删除节点并返回其值
bool ListDelete(LinkList& L, int i, int& e) {
    if (i < 1)return false;
    LNode* p;
    int j = 0;
    p = L;
    while (p != NULL && j < i - 1) {
        p = p->next;
        j++;
    }
    LNode* q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    删除指定节点：若p为最后一个元素，则存在问题，只能通过从头结点开始顺序找到其前序节点的方法来进行删除。

    image.png

    //删除指定节点
bool DeleteNode(LNode* p) {
    if (p == NULL)
    {
        return false;
    }
    LNode* q = p->next;//令q指向*p的后续结点
    p->data = p->next->data;//和后续结点交换数据域
    p->next = q->next;//将*q结点从链中“断开”
    free(q);//释放后续结点的存储空间
    return true;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    按值查找：

    //按值查找
LNode* LocateElem(LinkList L, int e)
{
    LNode* p = L->next;//从第1个结点开始查找数据域为e的结点
    while (p != NULL && p->data != e)
    {
        p = p->next;
    }
    return p;//找到后返回该结点指针，否则返回NULL；
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    按位查找：

    //按位查找
LNode* GetElem(LinkList L, int i)
{
    if (i < 0)
    {
        return NULL;
    }
    LNode* p;//指针p指向当前扫描到的结点
    int j = 0;//当前p指向的是第几个结点
    p = L;//L指向头结点，头结点是第0个结点（不存数据）
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    return p;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    求表长：

    //求表长
int Lnegth(LinkList L)
{
    int len = 0;//统计表长
    LNode* p = L;
    while (p->next != NULL)
    {
        p = p->next;
        len++;
    }
    return len;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    尾插法建表：设置一个表尾指针，方便直接在队尾进行尾插操作

    //尾插法建立单链表（正向建立单链表）
LinkList List_TailInsert(LinkList& L)
{
    int x;
    L = (LinkList)malloc(sizeof(LNode));//建立头结点
    LNode* s, * r = L;//r为表尾指针，方便尾插
    scanf("%d", &x);//输入结点的值
    while (x != 9999)//输入9999表示结束
    {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;//r指向新的表尾结点，永远保持r指向最后一个结点，避免重复操作
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    头插法建立单链表(不断对头结点进行尾插操作）

    //头插法建立单链表(不断对头结点进行尾插操作）
LinkList List_HeadInsert(LinkList& L)//逆向建立单链表
{
    LNode* s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));//创建头结点
    L->next = NULL;//初始为空链表
    scanf("%d", &x);//输入结点的值
    while (x != 9999)//输入9999表示结束
    {
        s = (LNode*)malloc(sizeof(LNode));//创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;//将新结点插入表中，L为头指针
        scanf("%d", &x);
    }
    return L;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    双链表

    在单链表的基础上加入prior前驱指针，使得插入、删除操作的时间复杂度变为O（1）（可以很方便地找到前驱）

    image.png

    结构体：

    typedef struct DNode {
    int data;//数据域
    struct DNode* prior, * next;//前指针和后指针
} DNode, * DLinkList;

    • 1
    • 2
    • 3
    • 4

    初始化：

    //初始化
bool InitDLinkList(DLinkList& L) {
    L = (DNode*)malloc(sizeof(DNode));//分配一个头节点
    if (L == NULL)
        return false;
    L->prior == NULL;//头节点前后指针都指向空
    L->next == NULL;
    return true;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    判空：

    //判空
bool Empty(DLinkList L) {
    return (L->next == NULL);
}


    • 1
    • 2
    • 3
    • 4
    • 5

    后插：

    //指定节点的后插操作
bool InsertNextElem(DNode* p, DNode* s) {
    s->next = p->next;
    if (p->next != NULL)
    {
        p->next->prior = s;//防止出现p后面没有后继结点的情况
    }
    s->prior = p;
    p->next = s;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    删除p后继结点：

    //删除P节点的后继节点
bool DeleteNextNode(DNode* p) {
    if (p == NULL)return false;//p节点为空
    DNode* q = p->next;
    if (q == NULL)return false;//P节点没有后继
    p->next = q->next;
    if (q->next != NULL)//q不是最后一个节点
        q->next->prior = p;
    free(q);//手动释放内存空间
    return true;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    销毁整个表：

    //销毁整个表
bool DestroyList(DLinkList& L) {
    //循环删除并释放每个节点
    while (L->next != NULL)
        DeleteNextNode(L);
    free(L);//释放头节点
    L = NULL;//头指针指向NULL
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    循环链表

    循环链表的最后一个指针不是NULL而是改为指向头结点。

    循环单链表：

    结构体：

    typedef struct LNode {
    int data;
    struct LNode* next;
}LNode, * LinkList;


    • 1
    • 2
    • 3
    • 4
    • 5

    初始化：

    //初始化一个循环单链表
bool InitRLinkList(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));//分配一个头节点
    if (L == NULL)
        return false;//内存不足，分配失败；
    L->next = L;//头节点nex指向头节点，以此形成循环链表
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    判空：

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    判尾：

    //判断P是不是表尾指针
bool IsTail(LinkList L, LNode* p) {
    return (p->next == L);
}

    • 1
    • 2
    • 3
    • 4
    循环双链表：

    结构体：

    typedef struct DNode {
    int data;
    struct DNode* prior, * next;
}DNode, * DLinkList;

    • 1
    • 2
    • 3
    • 4

    初始化：

    //初始化
bool InitRDLinkList(DLinkList& L) {
    L = (DNode*)malloc(sizeof(DNode));//分配头节点
    if (L == NULL)return false;
    L->prior = L;
    L->next = L;//循环抱住自己
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    判尾：

    //判断节点p是不是循环双链表的表尾节点
bool iTail(DLinkList L, DNode* p) {
    return (p->next == L);
}

    • 1
    • 2
    • 3
    • 4

    插入：

    //在p节点之后插入s节点
bool InsertNextDNode(DNode* p, DNode* s) {
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
    return true;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    删除：

    //删除操作
bool DeleteNextDNode(DLinkList& L, DNode* p) {
    DNode* q = p->next;
    p->next = q->next;
    q->next->prior = p;
    free(q);
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    静态链表

    静态链表借助数组来描述线性表的线性存储结构，这里的指针next记录的是结点的相对地址（数组下标），又称游标，和顺序表一样，静态链表也要预先分配一块连续的内存空间。

    image.png

    静态链表以next==-1作为结束标志，插入、删除操作与动态链表的相同，只需要修改指针，而不需要移动元素。

    结构体：

    //第一种定义方法
struct Node0 {
    int data;//存储数据元素
    int next;//下一个元素的数组下标
};
typedef struct Node SLinkList[MaxSize];

//第二种定义方法
typedef struct Node {
    int data;
    int next;
}SLinkList[MaxSize];

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    优点：增删操作不需要大量移动元素

    缺点：不能随机存取，只能从头结点开始一次往后查找：容量固定不可变

    顺序表链表比较

    逻辑结构：

    都属于线性表，都是线性结构。

    采用顺序存储时，逻辑上相邻的元素，物理存储位置也相邻，采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，逻辑关系通过指针链接表示。

    存储结构：

    image.png

    基本操作：

    image.png

    image.png

    image.png

    image.png

    总结：

    image.png
    主要参考：王道考研课程
    后续会持续更新考研408部分的学习笔记，欢迎关注。
    github仓库（含所有相关源码）：408数据结构笔记

  • 相关阅读:
    Java(102)：ES7.14,RestHighLevelClient创建索引时报错 createis deprecated
    分析 SpringBoot 底层机制【Tomcat 启动分析 +Spring 容器初始化 +Tomcat 如何关联 Spring 容器 】
    WCH USB转多串口芯片相关型号
    【国外翻译】采访漫威视觉开发总监：AndyPark
    基于目录的ant任务
    就业季学好3d建模，找对才是赚到
    基于费舍尔判别分析的故障与诊断（lunwen+文献综述+翻译及原文+MATLAB程序）
    如何使用 NFTScan 的 TON API 实现 NFT 应用开发?
    Qt利用VCPKG和CMake和OpenCV和Tesseract实现中英文OCR
    应用实践 | 10 亿数据秒级关联，货拉拉基于 Apache Doris 的 OLAP 体系演进
  • 原文地址：https://blog.csdn.net/weixin_51630192/article/details/130912823