数据结构笔记——线性表

好好学习，天天向上

本文已收录至我的Github仓库DayDayUP：github.com/RobodLee/DayDayUP，欢迎Star

⭐⭐⭐⭐⭐转载请注明出处！⭐⭐⭐⭐⭐

链接：https://blog.csdn.net/weixin_43461520/article/details/123783563

⭐⭐⭐⭐⭐转载请注明出处！⭐⭐⭐⭐⭐

数据结构三要素——逻辑结构、数据的运算、存储结构（物理结构），存储结构不同，运算的实现方式不同。

线性表指的是逻辑结构，可以采用顺序存储的顺序表或者链式存储的链表实现。

2.1 线性表的定义和基本操作 2.1.1 线性表的定义

线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，当n = 0时线性表是一个空表。除第一个元素（表头元素）外，每个元素都有且仅有一个直接前驱；除最后一个元素（表尾元素）外，每个元素有且仅有一个直接后继。

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

2.1.2 线性表的基本操作

• InitList(&L)：初始化表。构造一个空的线性表。
• Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
• LocateElem(L , e)：按值查找操作。在表L中查找具有给定关键字值的元素。
• GetElem(L , i)：按位查找操作。获取表 L 中第i 个位置的元素的值。
• ListInsert(&L , i , e)：插入操作。在表L中的第 i 个位置上插入指定元素e。
• ListDelete(&L , i , &e)：删除操作。删除表L中第 i 个位置的元素，并用e返回删除元素的值。
• PrintList(L)：输出操作。按前后顺序输出线性表 L 的所有元素值。
• Empty(L)：判空操作。若 L 为空表，则返回 true，否则返回 false。
• DestroyList(&L)：销毁操作。销毁线性表，并释放线性表 L所占用的内存空间。

2.2 线性表的顺序表示

线性表的顺序存储又称顺序表，用一组地址连续的存储单元依次存储线性表中的数据元素。表中元素的逻辑顺序与其物理顺序相同。

2.2.1 插入

ListInsert(&L , i , e)：插入操作。在表L中的第i个位置上插入指定元素e。

typedef struct {
    int data[MaxSize];  //用静态数组存放元素
    int length;         //长度
} SqList;

//在第i个位置插入元素e，下标为i-1
bool ListInsert(SqList &sqList, int i, int e) {
    //检查i的范围是否合理
    if (i < 1 || i > sqList.length + 1) {
        return false;
    }
    //检查数组是否已满
    if (sqList.length >= MaxSize) {
        return false;
    }
    //将第i个元素及之后的元素后移
    for (int j = sqList.length; j > i; j--) {
        sqList.data[j] = sqList.data[j - 1];
    }
    sqList.data[i - 1] = e;
    sqList.length++;
    return true;
}

2.2.2 删除

ListDelete(&L , i , &e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

typedef struct {
    int data[MaxSize];  //用静态数组存放元素
    int length;         //长度
} SqList;

//删除第i个元素，并将其赋值给给e，删除元素的下标为i-1
bool ListDelete(SqList &sqList, int i, int &e) {
    //检查i的范围是否合理
    if (i < 1 || i > sqList.length) {
        return false;
    }
    e = sqList.data[i - 1];
    //将第i个位置后的元素前移
    for (int j = i; j < sqList.length; j++) {
        sqList.data[j - 1] = sqList.data[j];
    }
    sqList.length--;
    return true;
}

2.2.3 查找

• 按位查找

GetElem(L , i)：按位查找操作。获取表L中第i个位置的元素的值。

typedef struct {
    ElemType data[MaxSize];  //用静态数组存放元素
    int length;         //长度
} SqList;

//和访问普通数组的方法一样，返回第i个元素
ElemType GetElem(SqList sqList, int i) {
    return sqList.data[i - 1];
}

• 按值查找

LocateElem(L , e)：按值查找操作。在表L中查找具有给定关键字值的元素。

typedef struct {
    ElemType data[MaxSize];  //用静态数组存放元素
    int length;         //长度
} SqList;

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SqList sqList, ElemType e) {
    for (int i = 0; i < sqList.length; ++i) {
        if (sqList.data[i] == e) {
            return i + 1;   //数组下标为i的元素值等于e，返回其位序i+1
        }
    }
    return 0;
}

2.3 线性表的链式表示 2.3.1 单链表

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

定义

• 不带头节点

#define ElemType int

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

//初始化一个不带头结点的空的单链表
bool InitList(LinkList &linkList) {
    linkList = nullptr;    //空表，暂时还没有任何节点
    return true;
}

int main() {
    LinkList linkList;
    InitList(linkList);
    return 0;
}

单链表的第一个节点直接指向数据节点。写代码更麻烦，对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑，对空表和非空表的处理需要用不同的代码逻辑。

空表判断：L == NULL

• 带头节点

#include <cstdlib>
#define ElemType int

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

//初始化一个带头结点的空的单链表
bool InitList(LinkList &linkList) {
    linkList = (LinkList) malloc(sizeof(LNode));
    if (linkList == nullptr) {
        return false;   //内存不足，分配失败
    }
    linkList->next = nullptr;   //头结点之后暂时还没有节点
    return true;
}

头结点不存储数据，即头结点的数据域data为空。

空表判断：L→next == NULL，写代码更方便。

插入

• 按位序插入（带头结点）

ListInsert(&L, i , e)：插入操作。在表L中的第i个位置上插入指定元素e。

#include <cstdlib>
#include <iostream>

using namespace std;
#define ElemType int

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

//向第i个位置插入元素e，也就是在第i-1个元素后插入e
bool ListInsert(LinkList &linkList, int i, ElemType e) {
    if (i < 1) {
        return false;   //检查i是否合法
    }
    LNode *p = linkList;    //临时节点，指向当前扫描到的节点
    int index = 0;//表示p当前指向第几个节点，初始为第0个节点也就是头结点
    while (p != nullptr && index < i - 1) { //移动p，使其指向第i-1个节点
        p = p->next;
        index++;
    }
    if (p == nullptr) {
        return false;
    }
    //在第i-1个节点后插入新节点
    auto *t = new LNode;
    t->data = e;
    t->next = p->next;
    p->next = t;
    return true;
}

平均时间复杂度：O(n)

• 按位序插入（不带头结点）

ListInsert(&L, i , e)：插入操作。在表L中的第i个位置上插入指定元素e。

#include <iostream>

using namespace std;
#define ElemType int

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

//初始化一个不带头结点的空的单链表
bool InitList(LinkList &linkList) {
    linkList = nullptr;    //空表，暂时还没有任何节点
    return true;
}

//向第i个位置插入元素e，也就是在第i-1个元素后插入e
bool ListInsert(LinkList &linkList, int i, ElemType e) {
    if (i == 1) {   //当插入的节点位置是第一个时，创建一个新节点放在linkList的前面
        auto *s = new LNode;
        s->data = e;
        s->next = linkList;
        linkList = s;
        return true;
    }
    if (i < 1) {
        return true;    //检查位序是否合法
    }
    LNode *p = linkList;
    int index = 1;//当前指向第几个节点，初始指向第1个节点
    while (p != nullptr && index < i - 1) {
        p = p->next;
        index++;
    }
    if (p == nullptr) {
        return false;
    }
    auto *s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

相较于带头结点的方式而言，当插入的节点为第一个节点时，需要额外进行处理。

平均时间复杂度：O(n)

• 指定节点的后插操作

InsertNextNode(LNode *p , ElemType e)：在p节点后插入一个新节点

#include <iostream>

using namespace std;
#define ElemType int

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

//指定节点的后插操作
bool InsertNextNode(LNode *p, ElemType e) {
    if (p == nullptr) {
        return false;   //检查p是否为空
    }
    auto *s = new LNode;
    if (s == nullptr) {
        return false;   //内存不足时可能分配失败
    }
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

没有需要循环的地方，直接在指定节点后插入一个新的节点，时间复杂度为O(1)。

• 指定节点的前插操作

bool InsertPriorNode(LNode *p, ElemType e)：在p节点前插入一个新节点

#include <iostream>

using namespace std;
#define ElemType int

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

//指定节点的后插操作
bool InsertPriorNode(LNode *p, ElemType e) {
    if (p == nullptr) {
        return false;   //检查p是否为空
    }
    auto *s = new LNode;
    s->next = p->next;
    p->next = s;            //新节点s连接到p之后
    s->data = p->data;      //将p中元素复制到s中
    p->data = e;            //p中元素覆盖为e
    return true;
}

本来应该是在p节点之前插入s节点，现在在p节点之后插入s，然后将p的data与s中的data交换，相当于实现了在p节点之前插入s，由于是直接插入，没有循环遍历，所以时间复杂度为O(1)。

删除

• 按位序删除（带头结点）

bool ListDelete(LinkList &linkList , int i , ElemType &e)：删除第i个节点

#include <iostream>

using namespace std;
#define ElemType int

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

//删除第i个节点，并将删除节点的data赋值给e
bool ListDelete(LinkList &linkList, int i, ElemType &e) {
    if (i < 1) {
        return false;   //检查i是否合法
    }
    LNode *p = linkList;    //使p指向被扫描到的节点，初始指向头结点
    int index = 0;          //表示p当前指向第几个节点
    while (p != nullptr && index < i - 1) {     //使p指向第i-1个节点
        p = p->next;
        index++;
    }
    if (p == nullptr || p->next == nullptr) {   //检查p是否合法，检查第i个节点是否存在
        return false;
    }
    LNode *q = p->next;   //q指向待删除节点
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

由于需要循环遍历到待删除节点的前一个节点，所以时间复杂度为O(n)。

• 指定节点的删除

bool DeleteNode(LNode *p)：删除节点p

#include <iostream>

using namespace std;
#define ElemType int

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

//删除节点p
bool DeleteNode(LNode *p) {
    if (p == nullptr) {
        return false;
    }
    LNode *s=p->next;
    //代码有bug，如果p是最后一个节点，只能循环遍历到p的前驱节点，然后将p删除，但是时间复杂度就会变成O(n)
    p->data=s->data;
    p->next=s->next;
    return true;
}

本来是删除节点p，现在将p的后继节点q的data值赋值给p，然后将q删除，间接实现的删除p，时间复杂度为O(1)，如果采用循环遍历的方式找到p的前驱节点，时间复杂度就会变成O(n)。

查找

• 按位查找

GetElem(L , i)：按位查找操作。获取表L中第i个位置的元素的值。

#include <iostream>

using namespace std;
#define ElemType int

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

//按位查找操作。获取表L中第i个位置的元素的值。
LNode *GetElem(LinkList &linkList, int i) {
    if (i < 1) {
        return nullptr; //检查i值是否合法
    }
    LNode *p = linkList;    //指向当前扫描到的节点
    int index = 0;          //表示p当前指向第几个节点
    while (p != nullptr && index < i) { //使p指向第i个节点
        p = p->next;
        index++;
    }
    return p;   //如果p是null，则返回的是null
}

循环遍历到指定位序的节点，所以平均时间复杂度为O(n)。

• 按值查找

LocateElem(L , e)：按值查找操作。在表L中查找具有给定关键字值的元素。

#include <iostream>

using namespace std;
#define ElemType int

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

//按值查找操作。在表L中查找具有给定关键字值的元素。
LNode *LocateElem(LinkList &linkList, ElemType e) {
    LNode *p = linkList->next;
    while (p != nullptr && p->data != e) {
        p = p->next;
    }
    return p;   //如果p存在则返回p，反之返回null
}

如果找到相应的节点则返回相应的节点，反之返回null。

由于是遍历查找，平均时间复杂度是O(n)。

建立

• 尾插法

LinkList List_TailInsert(LinkList &L)：尾插法建立单链表

#include <iostream>

using namespace std;
#define ElemType int

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

LinkList List_TailInsert(LinkList &linkList) {
    linkList = new LNode;   //建立头结点
    linkList->next = nullptr;
    LNode *s;   //临时节点
    LNode *r;   //尾指针
    r = linkList;
    ElemType data;
    cin >> data;
    while (data != 9999) {  //循环输入数据
        s = new LNode;      //建立一个新节点，将数据赋值给新节点的data，然后将新节点插在尾指针后
        s->data = data;
        r->next = s;
        r = s;
        r->next = nullptr;
        cin >> data;
    }
    return linkList;
}

尾指针r始终指向最后一个节点，循环输入数据，如果不为9999则表示链表还未结束，将输入的data 赋值给新节点的data域，然后将新节点插入到尾指针之后，再将尾指针指向新的节点。

由于是线性插入，所以时间复杂度是O(n)。

• 头插法

LinkList List_HeadInsert(LinkList &L)：逆向建立链表，每次都在头节点之后插入新的节点

#include <iostream>

using namespace std;
#define ElemType int

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

LinkList List_HeadInsert(LinkList &linkList) {
    linkList = new LNode;
    linkList->next = nullptr;       //初始化为空链表
    LNode *s;  //临时节点
    LNode *h;   //头结点
    h = linkList;
    ElemType data;
    cin >> data;
    while (data != 9999) {
        s = new LNode;
        s->data = data;
        s->next = h->next;
        h->next = s;
        cin >> data;
    }
    return linkList;
}

每次都在头结点之后插入新的节点，链表的顺序与输入数据的顺序相反，时间复杂度为O(n)。

一个重要的应用就是链表的逆置，需要翻转一个链表时，可以遍历旧的链表，然后使用头插法将依次将数据插入到头结点之后。

2.3.2 双链表

#include <iostream>

using namespace std;
#define ElemType int

typedef struct DNode {
    ElemType data;
    DNode *prior, *next;
} DNode, *LinkList;

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

//删除p节点的后继节点
bool DeleteNextNode(DNode *p) {
    if (p == nullptr) {
        return false;
    }
    DNode *q = p->next;
    if (q->next != nullptr) {
        q->next->prior = p;
    }
    p->next = q->next;
    return true;
}

双链表节点中有两个指针prior和next，分别指向其前驱节点和后继节点。

2.3.3 循环链表

• 循环单链表

在循环单链表中，表尾结点的next指针指向头节点。 从一个节点出发，可以找到其它任意一个节点。

#include <iostream>

using namespace std;
#define ElemType int

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

//初始化一个循环单链表
bool InitList(LinkList &linkList) {
    linkList = new LNode;
    if (linkList == nullptr) {
        return false;
    }
    linkList->next = linkList;    //头结点的下一个节点指向自身，表示为空链表
    return true;
}

//判断循环单链表是否为空
bool Empty(LinkList linkList) {
    //如果头结点的下一个节点指向自身，表示为空的链表
    return linkList->next == linkList;
}

//判断节点p是否为循环单链表的表尾结点
bool isTail(LinkList linkList, LNode *p) {
    //如果p的下一个节点是头结点，则表示p是表尾结点
    return p->next == linkList;
}

• 循环双链表

表头结点的 prior 指向表尾结点，表尾结点的 next 指向头结点。

#include <iostream>

using namespace std;
#define ElemType int

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

//初始化一个循环单链表
bool InitList(DLinkList &dLinkList) {
    dLinkList = new DNode;
    if (dLinkList == nullptr) { //内存不足，分配失败
        return false;
    }
    dLinkList->prior = dLinkList;   //头结点的 prior 指向自身
    dLinkList->next = dLinkList;    //头结点的 next 指向自身
    return true;
}

//判断循环单链表是否为空
bool Empty(DLinkList dLinkList) {
    //如果头结点的下一个节点指向自身，表示为空的链表
    return dLinkList->next == dLinkList;
}

//判断节点p是否为循环单链表的表尾结点
bool isTail(DLinkList dLinkList, DNode *p) {
    //如果p的下一个节点是头结点，则表示p是表尾结点
    return p->next == dLinkList;
}

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

//删除p节点的后继节点q
bool DeleteNextDNode(DNode *p) {
    if (p == nullptr) {
        return false;
    }
    DNode *q = p->next;
    p->next = q->next;
    q->next->prior = p;
    free(q);
    return true;
}

码字不易，可以的话，给我来个点赞，收藏，关注

如果你喜欢我的文章，欢迎关注微信公众号 『 R o b o d 』

如果你喜欢我的文章，欢迎关注微信公众号 『 R o b o d 』

本文已收录至我的Github仓库DayDayUP：github.com/RobodLee/DayDayUP，欢迎Star

⭐⭐⭐⭐⭐转载请注明出处！⭐⭐⭐⭐⭐

链接：https://blog.csdn.net/weixin_43461520/article/details/123783563

⭐⭐⭐⭐⭐转载请注明出处！⭐⭐⭐⭐⭐