这是本节的多页打印视图。点击此处打印.

线性表

本章是后序内容的基础，可能会涉及到在选择题中的概念考察。除此外，需要能够手写代码实现基于数组或链表的相关操作。

1: 定义和基本操作
2: 顺序表示
3: 链式表示

学习思维导图：

# 线性表

## 线性表的基本概念

## 线性表的实现

- 顺序存储
- 链式存储

## 线性表的应用

1 - 定义和基本操作

线性表可分为顺序表和链表，本节讨论线性表的定义和操作。

线性表定义

线性表是L数据结构中的一种基本结构。它是零个或多个数据元素的有限序列。通常，线性表中的数据元素之间是有序的，它们之间存在着前驱和后继的关系。

$$L = (a_1, a_2, \cdots, a_i, a_{i+1}, \cdots, a_n)$$

特点：

个数有限
表中元素数据类型都相同，每个元素占有相同大小的存储空间
仅讨论元素间的逻辑关系，表中元素有先后顺序

操作

初始化 (InitList): 创建一个空的线性表。
插入 (Insert): 在线性表的指定位置插入一个新的元素。
删除 (Delete): 删除线性表中的指定位置的元素。
查找 (LocateElem): 根据给定的条件查找线性表中的元素。
获取元素 (GetElem): 获取线性表中指定位置的元素。
设置元素 (SetElem): 修改线性表中指定位置的元素的值。
长度 (Length): 返回线性表中的元素数量。
判空 (IsEmpty): 判断线性表是否为空。
清空 (ClearList): 清除线性表中的所有元素。
遍历 (Traverse): 对线性表中的每个元素执行某种操作。

2 - 顺序表示

需熟练掌握顺序表的定义，并且能够用手写代码实现顺序表上的各种操作。

顺序表定义

顺序表（Sequential List） 是一种常见的数据结构，用于存储一组元素，并按照它们在内存中的物理顺序来排列和访问这些元素。顺序表通常由一个数组或列表构成，其中每个元素都占据一个连续的内存位置，并且可以通过索引值来访问。

假设线性表 A 存储的其实位置为LOC(A)，每个元素占用的存储空间的大小为sizeof(Elem)，则 A 所对应的顺序存储结构为：

顺序表优点：
- 随机访问性强：顺序表支持通过索引直接访问元素，访问速度快，时间复杂度为O(1)。
- 空间使用连续：顺序表中的元素存储在连续的内存块中，这有助于提高缓存的局部性，从而提高访问速度。
- 操作简单：无需处理复杂的指针操作。
顺序表缺点：
- 固定大小或调整大小的开销：对于静态数组，大小是固定的，如果预分配的空间不足或过大，会导致内存浪费或数组溢出。动态数组可以重新分配大小，但这会增加时间和空间开销。
- 插入和删除的时间开销：如果要在顺序表的中间插入或删除元素，可能需要移动大量的元素，时间复杂度为O(n)。

操作

#define MAXSIZE 100
typedef struct {
    ElementType data[MAXSIZE];
    int length;
} SeqList;

void InitList(SeqList *L) {
    L->length = 0;
}

bool Insert(SeqList *L, int pos, ElementType e) {
    if (L->length == MAXSIZE || pos < 1 || pos > L->length + 1) {
        return false;
    }
    for (int i = L->length; i >= pos; i--) {
        L->data[i] = L->data[i - 1];
    }
    L->data[pos - 1] = e;
    L->length++;
    return true;
}

bool Delete(SeqList *L, int pos, ElementType *e) {
    if (pos < 1 || pos > L->length) {
        return false;
    }
    *e = L->data[pos - 1];
    for (int i = pos; i < L->length; i++) {
        L->data[i - 1] = L->data[i];
    }
    L->length--;
    return true;
}

int LocateElem(SeqList L, ElementType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1;  // 返回元素位置，而不是下标
        }
    }
    return 0;  // 未找到返回0
}

bool GetElem(SeqList L, int pos, ElementType *e) {
    if (pos < 1 || pos > L.length) {
        return false;
    }
    *e = L.data[pos - 1];
    return true;
}

bool IsEmpty(SeqList L) {
    return L.length == 0;
}

void ClearList(SeqList *L) {
    L->length = 0;
}

int Length(SeqList L) {
    return L.length;
}

3 - 链式表示

需熟练掌握链表的定义，并且能够用手写代码实现链表上的各种操作。

单链表定义

线性表的链式表示通常指的是使用链表来实现线性表。链表是由一系列节点组成的，每个节点都包含一个数据元素和一个指向下一个节点的指针。这种结构允许我们动态地插入和删除元素，而不需要移动其他元素。

单链表的优点：
- 动态分配存储空间：链表的节点是在需要时动态分配的，因此在使用过程中不需要提前分配固定大小的存储空间。这使得内存利用率更加高效，可以减少内存浪费。
- 插入和删除方便：只要知道了某个节点的位置，就可以在O(1)的时间复杂度内插入或删除该节点。而顺序表可能需要移动大量的元素。
- 无需预估数据大小：链表可以灵活地增长，而顺序表需要预先定义一个固定大小，或者使用动态数组实现，但重新分配和拷贝的开销可能会很大。
单链表的缺点：
- 空间开销较大：除了数据元素的存储外，每个节点还需要额外的空间存储一个指针，这增加了链表的存储开销。
- 随机访问较慢：链表不支持直接通过索引进行随机访问，必须从头部开始逐个遍历节点，直到找到所需的节点，所以访问链表中的元素需要O(n)的时间复杂度。
- 复杂的操作：链表需要处理更多的指针操作，容易出错。

为了方便链表的操作，常常在单链表中常常引入头结点，头结点中的指针为头指针，指向链表中的第一个结点，如果头指针指向NULL的话，则表示链表为空。

操作

// 链表定义
typedef struct Node {
    ElementType data;
    struct Node *next;
} Node;

typedef Node *LinkList;

// 初始化
LinkList InitList() {
    LinkList L = (Node *)malloc(sizeof(Node));  // 创建头结点
    if (L == NULL) exit(1);  // 内存分配失败
    L->next = NULL;  // 初始为空链表
    return L;
}

bool Insert(LinkList L, int pos, ElementType e) {
    Node *p = L;
    int i = 0;
    while (p && i < pos - 1) {  // 找到第pos-1个节点
        p = p->next;
        i++;
    }
    if (!p || i > pos - 1) return false;

    Node *s = (Node *)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

bool Delete(LinkList L, int pos, ElementType *e) {
    Node *p = L;
    int i = 0;
    while (p->next && i < pos - 1) {  // 找到第pos-1个节点
        p = p->next;
        i++;
    }
    if (!(p->next) || i > pos - 1) return false;

    Node *q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return true;
}

int LocateElem(LinkList L, ElementType e) {
    Node *p = L->next;
    int i = 1;
    while (p) {
        if (p->data == e) return i;
        p = p->next;
        i++;
    }
    return 0;  // 未找到返回0
}

bool GetElem(LinkList L, int pos, ElementType *e) {
    Node *p = L->next;
    int i = 1;
    while (p && i < pos) {
        p = p->next;
        i++;
    }
    if (!p || i > pos) return false;

    *e = p->data;
    return true;
}

bool IsEmpty(LinkList L) {
    return L->next == NULL;
}

void ClearList(LinkList L) {
    Node *p = L->next, *q;
    L->next = NULL;
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
}