数据结构笔记——线性表

好好学习，天天向上

本文已收录至我的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-1bool 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-1bool 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 inttypedef 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 inttypedef 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 inttypedef struct LNode {    ElemType data;    struct LNode *next;} LNode, *LinkList;//向第i个位置插入元素e，也就是在第i-1个元素后插入ebool 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 inttypedef struct LNode {    ElemType data;    struct LNode *next;} LNode, *LinkList;//初始化一个不带头结点的空的单链表bool InitList(LinkList &linkList) {    linkList = nullptr;    //空表，暂时还没有任何节点    return true;}//向第i个位置插入元素e，也就是在第i-1个元素后插入ebool 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 inttypedef 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 inttypedef 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 inttypedef struct LNode {    ElemType data;    struct LNode *next;} LNode, *LinkList;//删除第i个节点，并将删除节点的data赋值给ebool 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 inttypedef struct LNode {    ElemType data;    struct LNode *next;} LNode, *LinkList;//删除节点pbool 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 inttypedef 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 inttypedef 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 inttypedef 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 inttypedef 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 inttypedef struct DNode {    ElemType data;    DNode *prior, *next;} DNode, *LinkList;//p节点之后插入节点sbool 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 inttypedef 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 inttypedef 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节点的后继节点qbool 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

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