跳至主要內容

3.线性表

CoderMast大约 8 分钟

3.线性表

线性表定义和操作

线性表

线性表是具有相同数据类型的n个数据元素的有限集序列,其中n为表长,当n=0时线性表是一个空表。若用L命名线性表,其一般表示为:L = ( a1 ,a2 ,...,ai ,ai+1 ,...,an )

线性表的基本操作:

  • 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所占用的内存空间。

顺序表

顺序表

线性表的顺序结构又称为顺序表,他是用一组地址连续的存储单元依次存储线性表中的数据元素,从而使得逻辑上相邻的两个元素在物理上也相邻。

线性表的顺序存储类型描述:

ElemType 是线性表的元素类型

#define MaxSize 50  // 定义线性表的最大容量
typedef struct{
    ElemType data[MaxSize]; // 顺序表的元素
    int length; // 顺序表当前的长度
}SqList;    // 顺序表的类型定义

顺序表的特点

  • 顺序表中元素的逻辑顺序和实际的物理顺序相同,所以插入和删除操作需要移动大量元素。
  • 顺序表中第一个元素存储在线性表的起始位置,第 i 个元素的存储位置后面紧接着存储的是第 i + 1 个元素,称 i 为元素 ai 在线性表中的位序。
  • 顺序表最重要的特点是支持随机访问,即通过首地址和元素需要可在 O(1) 时间内找到指定的元素。
  • 通常情况下使用数组来表述线性表的顺序存储结构。
  • 顺序表的存储密度高,每个结点只存储数据元素。

注意

线性表中元素的位序是从 1 开始的,而数组中元素的下标是从 0 开始的。

顺序表上基本操作的实现:

说明

这里实现了顺序表的插入、删除、按值查询、按序号查询操作的算法。

  • 插入操作

在顺序表 L 的第 i 个位置插入新元素 e 。若 i 的位置不合法,则返回 fasle,表示插入失败。否则将第 i 个元素及其后的所有元素依次往后移动一个位置,腾出一个空位置插入新元素 e,顺序表长度增加 1 ,插入成功,返回 true。

bool ListInsert(SqList &L, int i, ElemType e){
    // 判断 i 的范围是否合法
    if (i < 1 || i >= L.length){
        return false;
    }

    // 当存储空间已满时,则无法插入
    if (L.length >= MaxSize){
        return false;
    }

    // 将第 i 个元素及之后的元素后移
    for (int j = L.length; j >= i; j--){
        L.data[j] = L.data[j - 1];
    }

    // 在位置 i 处放入 e
    L.data[i - 1] = e;

    // 线性表长度加 1
    L.length ++;

    return true;
}

最好情况:在表头插入(即 i = n + 1),元素后移语句将不执行,时间复杂度为 O(1)

最坏情况:在表头插入(即 i = 1),元素后移语句将执行 n 次,时间复杂度为 O(n)

平均情况:假设 pip_i 是在第 i 个位置上插入的一个结点的概率,则在长度为 n 的线性表中插入一个结点时,所需要移动结点的平均次数为 i=1n+1pi(ni+1)=i=1n+11n+1(ni+1)=1n+1i=1n+1(ni+1)=1n+1n(n+1)2=n2\sum\limits _{i=1}^{n+1} p_i (n-i+1) = \sum\limits _{i = 1} ^{n+1} \frac {1} {n + 1} * (n - i + 1) = \frac {1} {n + 1} \sum\limits _{i = 1} ^{n+1} (n - i + 1) = \frac {1} {n + 1} \frac {n(n + 1)} {2} = \frac {n} {2} ,则平均时间复杂度为 O(n)

  • 删除操作

删除顺序表 L 中第 i 个位置的元素,用引用变量 e 返回。

bool ListDelete(SqList &L, int i, ElemType &e){
    // 判断 i 的位置是否合法
    if (i < 1 || i >= L.length){
        return false;
    }

    // 将被删除的元素赋值给 e
    e = L.data[i - 1];

    // 将第 i 个位置后的元素前移
    for (int j = i; j < L.length; j ++){
        L.data[j - 1] = L.data[j];
    }

    // 线性表长度 减1
    L.length --;

    return true;
}

最好情况:删除表尾元素,则无需移动元素,时复杂度为 O(1)

最坏情况:删除表头元素,则需要移动除表头元素以外的所有元素,时间复杂度为 O(n)

平均情况:假设 pip_i 是删除第 i 个位置结点的概率,则在长度为 n 的线性表中删除一个结点时,所需要移动结点的平均次数为 i=1npi(ni)=i=1n1n(ni)=1ni=1n(ni)=1nn(n1)2=n12\sum\limits _{i=1}^{n} p_i (n-i) = \sum\limits _{i = 1} ^{n} \frac {1} {n} * (n - i) = \frac {1} {n} \sum\limits _{i = 1} ^{n} (n - i) = \frac {1} {n} \frac {n(n - 1)} {2} = \frac {n - 1} {2} ,则平均时间复杂度为 O(n)

  • 按值查询

在顺序表 L 中查找第一个元素值等于 e 的元素,返回其位序。如果没有找到,则返回 0。

需要注意的是,位序是从 1 开始的,而索引是从 0 开始的。

int LocateElem(SqList &L, ElemeType e){
    int i;

    for (i = 0; i < L.length; i ++){
        if (L.data[i] == e){
            return i + 1;
        }
    }
    return 0;
}

最好情况:查找的元素就在第一个,则只需要比较一次,时间复杂度为 O(1)

最坏情况:查找的元素在最后一个,需要将所有的元素都进行对比,时间复杂度为 O(n)

平均情况:假设 pip_i 是在第 i 个位置上插入的一个结点的概率,则在长度为 n 的线性表中查找值为 e 的元素需要比较的平均次数为 i=1npii=i=1n1ni=1nn(n+1)2=n+12\sum\limits _{i=1}^n p_i * i = \sum\limits _{i = 1} ^n \frac {1} {n} * i = \frac {1} {n} \frac {n(n + 1)} {2} = \frac {n + 1} {2},则平均时间复杂度为 O(n)

  • 按序号查询

在顺序表 L 中查找位序为 i 个元素的值。

需要注意的是,位序是从 1 开始的,而索引是从 0 开始的。

int getByIndex(SqList &L,int i){
    if (i <= 0 || i > L.length){
        return -1;
    }

    return L.data[i - 1];
}

因为顺序表支持随机访问,所以这里通过位序或者索引进行查找的最好、最坏和平均复杂度都是 O(1) 。

单链表

单链表

线性表的链式存储成为单链表,他是通过一组任意的存储单元来存储线性表中的数据元素。通过节点中存储后续节点的指针来进行连接。

  • 单链表中节点类型的描述
typedef struct LNode{   // 定义单链表节点类型
    ElemeType data;     // 数据域
    struct LNode *next; // 指针域
}LNode, *LinkList;

单链表的特点

  • 可以存储大量数据,解决了顺序表需要大量连续存储单元的缺点
  • 存储数据域,还存储指针域,浪费了存储空间
  • 单链表元素离散的分布在存储空间中,是非随机存取的存储结构
  • 通常头指针来标示一个单链表,为了方便操作,在第一个实际节点之间附加一个头结点

单链表上基本操作的实现

  • 头插法建立单链表

该方法从一个空表开始,生成新结点,并将读取到的数据存放到新节点的数据域中,然后将新节点插入到当前链表的表头,即头结点之后。

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;
}

每个结点插入的时间为 O(1) ,则当单链表长为 n 时,总时间复杂度为 O(n)

  • 尾插法建立单链表

  • 按序号查找结点值

  • 按值查找表节点

  • 插入结点操作

  • 对某一节点进行前插操作

  • 删除节点操作

  • 求表长操作

int *GetListLen(LinkList L){
    int length = 0;
    for (Node i = L; i = L.next ; i != null){
        length ++;
    }
    return length;
}

双链表

  • 双链表

循环链表

  • 循环链表

静态链表

  • 静态链表

顺序表与链表的比较和选择