← 数据结构基础

线性表

数据结构-线性表

线性表(Linear List)是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用n表示,n ≥ 0。当n = 0时,表示线性表是一个空表。
设序列中第i个元素为ai(1 ≤ i ≤ n)(i表示逻辑序号)。线性表L可以表示为: L = (a1, a2, …ai, ai + 1, …, an) 其中a1为第一个元素,又称做表头元素a2为第二个元素,an为最后一个元素,又称做表尾元素。例如,以下的线性表: (1, 4, 3, 2, 8, 10)
1为表头元素,10为表尾元素。
线性表L中的元素是与位置有关的,即第i个元素ai处在第i − 1个元素ai − 1的后面和第i + 1个元素ai + 1的前面。这种位置上的有序性就是一种线性关系,所以线性表是一种线性结构

顺序表

顺序表是线性表的顺序存储结构,把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。
假定线性表的元素类型为ElemType,则每个元素所占用存储空间大小(即字节数)为sizeof(ElemType),整个线性表所占用存储空间的大小为:
n * sizeof(ElemType)    // n表示线性表的长度。

类型定义

#define ElemType int               // 元素类型#define MaxSize 10                 // 最大长度typedef struct{    ElemType data[MaxSize];        // data用于存放元素    int length;                    // 顺序表的实际元素个数} SqList;                          // 顺序表结构体类型
由于C/C++中数组的下标从0开始,线性表的第i个元素ai存放在顺序表的第i − 1个位置上。
ai在逻辑序列中的位置称为逻辑序号,而在顺序表中的位置称为物理序号(指数组下标)

基本运算

初始化顺序表

// 初始化顺序表void initList(SqList *&L){    L = (SqList *) malloc(sizeof(SqList));    L->length = 0;}

初始化非空顺序表

// 根据数组拷贝建立非空顺序表void createList(SqList *&L, ElemType a[], int n){    if (a == NULL || n < 0 || n >= MaxSize) return;    L = (SqList *) malloc(sizeof(SqList));    for (int i = 0; i < n; ++i)    {        L->data[i] = a[i];    }    L->length = n;}

销毁顺序表

// 销毁顺序表void destroyList(SqList *&L){    free(L);}

遍历顺序表

平均时间复杂度为O(n)。
// 打印顺序表void printList(SqList *L){    printf("[");    for (int i = 0; i < L->length; ++i)    {        if (i == L->length - 1) printf("%d", L->data[i]);        else printf("%d, ", L->data[i]);    }    printf("]");}

查找元素

平均时间复杂度为O(1)。
// 获取第i个元素, 将元素值存入e中bool getElem(SqList *L, int i, ElemType &e){    if (L == NULL || i < 1 || i > L->length) return false;    e = L->data[i - 1];    return true;}

按元素值查找

平均时间复杂度为O(n)。
// 按元素值查找, 返回逻辑序号int locateElem(SqList *L, ElemType e){    if (L == NULL) return 0;    int i = 0;    while (i < L->length && L->data[i] != e) i++;    if (i >= L->length) return 0; // 找不到就返回0    else return i + 1;}

插入元素

该运算在顺序表Lii是逻辑序号,1 ≤ i ≤ n + 1)个位置上插入新的元素e。如果i值不正确,则显示相应错误信息;否则将顺序表原来第i个元素及以后元素均后移一个位置,移动方向从右向左,如下图所示,腾出一个空位置插入新元素,最后顺序表长度增1。
// 在第i个位置上插入元素ebool insertElem(SqList *&L, ElemType e, int i){    if (L == NULL || i < 1 || i > L->length) return false;    i--; // 将逻辑序号转换成物理序号    for (int j = L->length; j > i; --j)    {        L->data[j] = L->data[j - 1];    }    L->data[i] = e;    L->length++;    return true;}
对于本算法来说,元素移动的次数不仅与表长L->length = n有关,而且与插入位置i有关:
  • i = n + 1时,移动次数为0。
  • i = 1时,移动次数为n,达到最大值。
删除算法最好的时间复杂度为O(1),最坏时间复杂度为O(n)。
平均情况分析:
在插入元素ai时,若为等概率情况,则$p_i = \frac{1}{n+1}$。
此时需要将aian的元素均后移一个位置,共移动n − i + 1个元素。
所以在长度为n的线性表中插入一个元素时所需移动元素的平均次数为: $$ \sum_{i=1}^{n+1} p_{i}(n-i+1)=\sum_{i=1}^{n+1} \frac{1}{n+1}(n-i+1)=\frac{n}{2} $$ 因此插入算法的平均时间复杂度为O(n)。

删除元素

该运算删除顺序表L的第ii是逻辑序号,1≤i≤n)个元素。如果i值不正确,则显示相应错误信息;否则将线性表第i个元素以后元素均向前移动一个位置,移动方向为从左向右,如下图所示,这样覆盖了原来的第i个元素,达到删除该元素的目的,最后顺序表长度减1。
// 删除第i个位置上的元素bool deleteElem(SqList *&L, int i){    if (L == NULL || i < 1 || i > L->length + 1) return false;    i--; // 将逻辑序号转换成物理序号    for (int j = i; j < L->length; ++j)    {        L->data[j] = L->data[j + 1]; // 元素前移    }    L->length--;    return true;}
对于本算法来说,元素移动的次数也与表长n和删除元素的位置i有关:
  • i = n时,移动次数为0。
  • i = 1时,移动次数为n − 1。
删除算法最好的时间复杂度为O(1),最坏时间复杂度为O(n)。
平均情况分析:
在删除元素ai时,若为等概率情况,则$p_i = \frac{1}{n}$。
此时需要将ai + 1an的元素均前移一个位置,共移动n − i个元素。
所以在长度为n的线性表中删除一个元素时所需移动元素的平均次数为: $$ \sum_{i=1}^{n} p_{i}(n-i)=\sum_{i=1}^{n} \frac{1}{n}(n-i)=\frac{n-1}{2} $$ 因此删除算法的平均时间复杂度为O(n)。

单链表

链表是线性表的链式存储结构,在每个结点中除包含有数据域外,还含有一个指针域,用以指向其后继结点,这样构成的链接表称为线性单向链接表,简称单链表

类型定义

在单链表中,假定每个结点的类型用LinkNode表示,它应包括存储元素的数据域,这里用data表示,其类型用通用类型标识符ElemType表示,还包括存储后继元素位置的指针域,这里用next表示。
typedef int ElemType;       // 数据类型typedef struct LNode        // 定义单链表节点类型{    ElemType data;          // 数据域    struct LNode *next;     // 指针域, 指向后继节点} LinkNode;                 // 单链表节点的类型

基本运算

初始化单链表

该运算建立一个空的单链表,即创建一个头结点
// 初始化单链表void initList(LinkNode *&L){    L = (LinkNode *) malloc(sizeof(LinkNode));    L->next = NULL; // 创建头结点}

初始化非空单链表

非空单链表可以通过一个含有n个数据的数组来建立单链表,常用方法有如下两种:

头插法

该方法从一个空表开始,依次读取数组a中的元素,生成新结点,将读取的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上(即头结点之后),直到结束为止。
// 利用头插法根据数组拷贝建立非空单链表void createListL(LinkNode *&L, ElemType a[], int n){    LinkNode *s;    L = (LinkNode *) malloc(sizeof(LinkNode)); // 创建头结点    L->next = NULL;                 // 其next域置为NULL    for (int i = 0; i < n; i++)     // 循环建立数据节点    {        s = (LinkNode *) malloc(sizeof(LinkNode));        s->data = a[i];             // 创建数据结点s        s->next = L->next;          // 将结点s插在原首结点之前, 头结点之后        L->next = s;    }}

尾插法

该方法从一个空表开始,依次读取数组a中的元素,生成新结点,将读取的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表尾后,直到结束为止。
为此,必须增加一个尾指针r,使其始终指向当前链表的尾结点。
// 利用尾插法根据数组拷贝建立非空单链表void createListR(LinkNode *&L, ElemType a[], int n){    LinkNode *s, *r;    L = (LinkNode *) malloc(sizeof(LinkNode));  // 创建头结点    r = L;                          // r始终指向尾结点, 开始时指向头结点    for (int i = 0; i < n; i++)     // 循环建立数据结点    {        s = (LinkNode *) malloc(sizeof(LinkNode));        s->data = a[i];             // 创建数据结点s        r->next = s;                // 将结点s插入到结点r之后        r = s;    }    r->next = NULL;                 // 尾结点next域置为NULL}

销毁单链表

释放单链表L占用的内存空间。即逐一释放全部结点的空间。平均时间复杂度为O(n)。
// 销毁单链表void destroyList(LinkNode *&L){    LinkNode *pre = L, *p = L->next;    // pre指向*p的前驱结点    while (p != NULL)                   // 扫描单链表L    {        free(pre);                      // 释放*pre结点        pre = p;                        // pre, p同步后移一个结点        p = pre->next;    }    free(pre); // 循环结束时, p为NULL, pre指向的是尾结点, 释放它}

判断是否为空表

// 判断是否为空表bool isEmpty(LinkNode *L){    return L->next == NULL; // 若单链表L没有数据结点, 则返回真, 否则返回假}

求单链表的长度

平均时间复杂度为O(n)。
// 求单链表的长度int getLength(LinkNode *L){    int n = 0;    LinkNode *p = L; // p指向头结点, n置为0(即头结点的序号为0)    while (p->next != NULL)    {        p = p->next;        n++;    }    return n;        // 循环结束, p指向尾结点, 序号n为单链表中数据结点的个数}

遍历单链表

平均时间复杂度为O(n)。
// 打印单链表void printList(LinkNode *L){    printf("[");    LinkNode *p = L->next;      // p指向开始结点    while (p != NULL)           // p不为NULL, 输出p结点的data域    {        printf("%d ", p->data);        p = p->next;            // p指向下一个结点    }    printf("]");}

查找元素

在单链表L中从头开始遍历到第i个结点,若存在第i个数据结点,则将其数据域的值赋给变量e。平均时间复杂度为O(n)。
// 获取第i个元素, 将元素值存入e中bool getElem(LinkNode *L, int i, ElemType &e){    if (i <= 0) return false;       // 保证逻辑序号大于0    LinkNode *p = L;                // p指向头结点    int j = 0;                      // j置为0(即头结点的序号为0)    while (j < i && p != NULL)      // 找第i个结点    {        p = p->next;        j++;    }    if (p == NULL) return false;    // 不存在第i个数据结点, 返回false    e = p->data;                    // 存在第i个数据结点, 返回true    return true;}

按元素值查找

在单链表L中从头开始找第1个值域与e相等的结点,若存在这样的结点,则返回逻辑序号,否则返回0。平均时间复杂度为O(n)。
// 按元素值查找, 返回逻辑序号int locateElem(LinkNode *L, ElemType e){    int i = 1;    LinkNode *p = L;    while (p != NULL && p->data != e)    {        p = p->next;        i++;    }    return p == NULL ? 0 : i;}

插入元素

先在单链表L中找到第i − 1个结点p,若存在这样的结点,将其值为e结点s的下一个结点指向第i个节点,并将结点s插入到p的后面。插入到表头的时间复杂度为O(1),插入到表尾的时间复杂度为O(n)。
// 在第i个位置上插入元素ebool insertElem(LinkNode *&L, int i, ElemType e){    if (i <= 0) return false;       // 保证逻辑序号大于0    int j = 0;    LinkNode *p = L, *s;            // p指向头结点, j置为0    while (j < i - 1 && p != NULL)  // 查找第i-1个结点    {        p = p->next;        j++;    }    if (p == NULL) return false;    // 未找到第i-1个结点, 返回false    // 找到第i-1个结点p, 创建新结点s    s = (LinkNode *) malloc(sizeof(LinkNode));    s->data = e;                    // 将新结点s其data域置为e    s->next = p->next;              // 将s之后的结点指向p之后的结点    p->next = s;                    // 将s插入到p之后, 完成新结点s的插入    return true;}

删除元素

先在单链表L中找到第i − 1个结点p,若存在这样的结点,且也存在后继结点,则删除该后继结点。删除指定位置结点的平均时间复杂度为O(n)。
// 删除第i个位置上的元素bool deleteElem(LinkNode *&L, int i, ElemType &e){    if (i <= 0) return false;       // 保证逻辑序号大于0    int j = 0;    LinkNode *p = L, *q;            // p指向头结点, j置为0    while (j < i - 1 && p != NULL)  // 查找第i-1个结点    {        p = p->next;        j++;    }    if (p == NULL) return false;    // 未找到第i-1个结点, 返回false    // 找到第i-1个结点p    q = p->next;                    // q指向第i个结点    if (q == NULL) return false;    // 若不存在第i个结点, 返回false    e = q->data;    // 将p指向的下一个结点替换成q的下一个结点, 从而删除q结点    p->next = q->next;    free(q);                        // 释放q结点    return true;                    // 成功删除第i个结点, 返回true}

Nobelium is built with ♥ and ⚛ Next.js. Proudly deployed on ▲Vercel.

© Ashinch 2021 桂ICP备18011166号-1