数据结构笔记——线性表

好好学习,天天向上

本文已收录至我的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;
}

双链表节点中有两个指针priornext,分别指向其前驱节点后继节点

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仓库DayDayUPgithub.com/RobodLee/DayDayUP,欢迎Star

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

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

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

 6 total views,  2 views today

页面下部广告