当前位置：首页 > article >正文

【数据结构与算法:二、线性表】

article 2025/1/7 16:25:47

线性表是数据结构中最基础、最常用的一种结构形式，其具有线性关系和顺序存储特点。以下从 线性表的定义和特点、线性表的类型定义、线性表的顺序表示和实现、线性表的链式表示和实现 以及 线性表的应用 五个方面介绍线性表。

一、线性表的定义和特点

1.1 线性表的定义

线性表是由 n(≥0) 个数据元素组成的有限序列，记为：

$L = (a_1, a_2, ..., a_n)$

数据元素： $a_i$ 是线性表中的元素， $i = 1, 2, ..., n$ 。
有限性：线性表中数据元素的个数是有限的。
线性关系：线性表中的数据元素之间存在线性顺序关系，即每个数据元素有且只有一个直接前驱和一个直接后继（首元素除外，只有后继；尾元素除外，只有前驱）。

1.2 线性表的特点

唯一性：表中元素按顺序排列，位置唯一。
动态性：可以动态增加或删除元素。
有序性：元素按逻辑顺序排列，与物理存储无关。

二、线性表的类型定义

线性表在实际应用中有以下几种常见的类型定义：

顺序表：
- 基于数组的顺序存储结构。
- 适合需要随机访问的情况。
链表：
- 基于指针的链式存储结构。
- 包括单链表、循环链表和双向链表。
- 适合需要频繁插入和删除的情况。

三、线性表的顺序表示和实现

3.1 顺序存储表示

定义：

顺序表是将线性表的元素按逻辑顺序存储在内存中连续的存储单元中。
每个元素占用一个存储单元，通过数组实现。

特点：

优点：支持随机访问，可以通过下标 $i$ 快速访问第 $i$ 个元素，时间复杂度为 $O (1)$ 。
缺点：插入和删除操作需要移动元素，时间复杂度为 $O (n)$ 。

顺序表的基本存储结构：

typedef struct {
    ElemType data[MAXSIZE];  // 存储数据元素的数组
    int length;             // 线性表当前长度
} SeqList;

3.2 顺序表中基本操作的实现

插入操作：
在顺序表第 $i$ 个位置插入一个元素。

bool ListInsert(SeqList *L, int i, ElemType e) {
    if (i < 1 || i > L->length + 1 || L->length >= MAXSIZE) {
        return false; // 插入位置非法或表满
    }
    for (int k = L->length - 1; k >= i - 1; k--) {
        L->data[k + 1] = L->data[k]; // 后移元素
    }
    L->data[i - 1] = e;
    L->length++;
    return true;
}

删除操作：
删除顺序表第 $i$ 个位置的元素。

bool ListDelete(SeqList *L, int i, ElemType *e) {
    if (i < 1 || i > L->length) {
        return false; // 删除位置非法
    }
    *e = L->data[i - 1]; // 保存被删除元素
    for (int k = i; k < L->length; k++) {
        L->data[k - 1] = L->data[k]; // 前移元素
    }
    L->length--;
    return true;
}

四、线性表的链式表示和实现

4.1 单链表的定义和表示

定义：

单链表由一系列节点组成，每个节点包含一个数据域和一个指针域，指针域指向下一个节点。
表头用头指针表示。

存储结构：

typedef struct Node {
    ElemType data;         // 数据域
    struct Node *next;     // 指针域，指向下一个节点
} Node, *LinkList;

4.2 单链表基本操作的实现

插入操作：
在链表第 $i$ 个位置插入元素 $e$ 。

bool ListInsert(LinkList *L, int i, ElemType e) {
    Node *p = *L; int j = 0;
    while (p && j < i - 1) { p = p->next; j++; } // 定位到第i-1个节点
    if (!p || j > i - 1) return false;           // 插入位置非法
    Node *s = (Node *)malloc(sizeof(Node));     // 生成新节点
    s->data = e; s->next = p->next;
    p->next = s;                                // 插入新节点
    return true;
}

删除操作：
删除链表第 $i$ 个位置的元素。

bool ListDelete(LinkList *L, int i, ElemType *e) {
    Node *p = *L; int j = 0;
    while (p->next && j < i - 1) { p = p->next; j++; } // 定位到第i-1个节点
    if (!p->next || j > i - 1) return false;           // 删除位置非法
    Node *q = p->next; *e = q->data;                  // 保存被删除元素
    p->next = q->next; free(q);                       // 删除节点
    return true;
}

4.3 循环链表和双向链表

循环链表：

尾节点的指针域指向头节点，形成一个循环。
优点：适用于需要循环访问的场景。

双向链表：

每个节点包含两个指针域，分别指向前驱节点和后继节点。
优点：支持从任意节点快速访问前驱和后继。

4.4 顺序表和链表的比较

空间性能比较：

顺序表需要预分配存储空间，可能导致内存浪费或不足。
链表按需分配存储空间，利用率更高。

时间性能比较：

顺序表随机访问快，但插入、删除需移动大量元素。
链表插入、删除操作效率高，但随机访问较慢。

五、线性表的应用

5.1 线性表的合并

将两个线性表 $L_1$ 和 $L_2$ 合并为一个线性表 $L$ ，实现如下：

void MergeList(SeqList *L1, SeqList *L2, SeqList *L) {
    int i = 0, j = 0, k = 0;
    while (i < L1->length && j < L2->length) {
        if (L1->data[i] <= L2->data[j]) L->data[k++] = L1->data[i++];
        else L->data[k++] = L2->data[j++];
    }
    while (i < L1->length) L->data[k++] = L1->data[i++];
    while (j < L2->length) L->data[k++] = L2->data[j++];
    L->length = k;
}