线性表

线性表是具有 相同数据类型 的 n 个数据元素的 有限序列 ，其中 n≥0 。

表示方式：$L = (a_1, a_2, a_3, ..., a_n)$

位序从 1 开始，即 $a_i$ 是第 i 个元素。

顺序表

定义

顺序表的特点：

• 表中元素的逻辑顺序和物理顺序是一致的；
• 顺序表中的元素可以随机存取，时间复杂度为 $O(1)$ ；
• 扩展容量不方便；
• 插入和删除操作需要移动大量元素，时间复杂度为 $O(n)$ 。

静态分配

#define MAX_SIZE 10         // 最大长度

typedef struct {
    Element data[MAX_SIZE]; // 数组存储数据元素
    int length;             // 当前长度
} SeqList;

缺点：长度固定，不易扩展。

动态分配

#define INIT_SIZE 10    // 初始长度

typedef struct {
    Element *data;      // 指针
    int length;         // 当前长度
    int maxSize;        // 最大长度
} DynSeqList;

// 初始化
void initList(DynSeqList &list) {
    list.data = (Element *)malloc(INIT_SIZE * sizeof(Element));
    list.length = 0;
    list.maxSize = INIT_SIZE;
}

// 扩容
void increaseSize(DynSeqList &list, int length) {
    Element *p = list.data;
    // 注意强制转换
    list.data = (Element *)malloc((list.maxSize + length) * sizeof(Element));
    for (int i = 0; i < list.length; i++) {
        list.data[i] = p[i];
    }
    list.maxSize += length;
    free(p);
}

插入

bool insert(SeqList &list, int i, Element e) {
    // 判断插入位置是否合法
    if (i < 1 || i > list.length + 1) return false;
    // 判断顺序表是否已满
    if (list.length >= list.maxSize) return false;
    // 从后往前移动元素
    for (int j = list.length; j >= i; j -= 1) {
        list.data[j] = list.data[j - 1];
    }
    list.data[i - 1] = e;
    list.length += 1;
    return true;
}

删除

bool remove(SeqList &list, int i, Element &e) {
    // 判断删除位置是否合法
    if (i < 1 || i > list.length) return false;
    e = list.data[i - 1];
    // 从前往后移动元素
    for (int j = i; j < list.length; j += 1) {
        list.data[j - 1] = list.data[j];
    }
    list.length -= 1;
    return true;
}

查找

// 根据位序查找元素
Element getElement(SeqList list, int i) {
    return list.data[i - 1];
}

// 根据元素值查找位序
int locateElement(SeqList list, Element e) {
    for (int i = 0; i < list.length; i += 1) {
        if (list.data[i] == e) return i + 1;
    }
    return 0;
}

链表

• 优点：不要求存储空间连续，可以动态分配，扩展容量方便。
• 缺点：不支持随机存取，只能顺序访问，时间复杂度为 O(n) 。

单链表

定义

typedef struct Node {
    Element data;
    struct Node *next;
} Node, *LinkList; // LinkList 为指向结点的指针

结点操作

获取指定位置的结点

Node *getElement(LinkList list, int i) {
    if (i == 0) return list; // 返回头结点
    if (i < 1) return NULL;
    Node *p = list;
    int j = 0;
    while (p != NULL && j < i) { // 找到第 i 个结点
        p = p->next;
        j += 1;
    }
    return p;
}

指定结点后插入

bool insertAfter(Node *p, Element e) {
    if (p == NULL) return false;
    Node *s = (Node *)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

指定节点前插入

bool insertBefore(Node *p, Element e) {
    if (p == NULL) return false;
    Node *s = (Node *)malloc(sizeof(Node));
    // 讲 p 的数据复制到 s
    s->data = p->data;
    s->next = p->next;
    // 将 e 赋值给 p
    p->data = e;
    p->next = s;
    return true;
}

指定结点删除

该函数存在问题：如果删除的是最后一个结点，那么 p->next 会变成野指针。

bool remove(Node *p, Element &e) {
    if (p == NULL) return false;
    Node *q = p->next; // q 代表第 i 个结点，即待删除结点
    p->data = q->data;
    p->next = q->next;
    e = q->data;
    free(q);
    return true;
}

带头结点的链表

初始化

bool initList(LinkList &list) {
    list = (LinkList)malloc(sizeof(Node));
    if (list == NULL) return false; // 内存分配失败
    list->next = NULL;
    return true;
}

尾插法：

ListList tailInsert(LinkList &list) {
    list = (LinkList)malloc(sizeof(Node));
    Node *r = list; // r 为尾指针
    for (int i = 0; i < n; i += 1) {
        Node *p = (Node *)malloc(sizeof(Node));
        scanf("%d", &p->data);
        r->next = p;
        r = p;
    }
    r->next = NULL;
    return list;
}

头插法：

ListList headInsert(LinkList &list) {
    list = (LinkList)malloc(sizeof(Node));
    list->next = NULL;
    for (int i = 0; i < n; i += 1) {
        Node *p = (Node *)malloc(sizeof(Node));
        scanf("%d", &p->data);
        p->next = list->next;
        list->next = p;
    }
    return list;
}

查找

Node *locateElement(LinkList list, Element e) {
    Node *p = list->next;
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p;
}

插入

// 这里的 & 是否可去？
bool insert(LinkList &list, int i, Element e) {
    if (i < 1) return false;
    Node *p = getElement(list, i - 1);
    return insertAfter(p, e);
}

不带头结点的链表

初始化

void initList(LinkList &list) {
    list = NULL;
}

插入

bool insert(LinkList &list, int i, Element e) {
    if (i < 1) return false;
    // 特殊情况：插入到表头
    if (i == 1) {
        Node *s = (Node *)malloc(sizeof(Node));
        s->data = e;
        s->next = list;
        list = s;
        return true;
    }
    // 正常插入（与带头结点插入方法一致）
    Node *p = list;
    int j = 1;
    while (p != NULL && j < i - 1) { // 找到第 i-1 个结点
        p = p->next;
        j += 1;
    }
    if (p == NULL) return false;
    Node *s = (Node *)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

删除

// 这里的 & 是否可去？
bool remove(LinkList &list, int i, Element &e) {
    if (i < 1) return false;
    Node *p = getElement(list, i - 1);
    if (p == NULL) return false;
    if (p->next == NULL) return false;
    Node *q = p->next; // q 代表第 i 个结点，即待删除结点
    p->next = q->next;
    e = q->data;
    free(q);
    return true;
}

双链表

定义及初始化

typedef struct DNode {
    Element data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

bool initList(DLinkList &list) {
    list = (DLinkList)malloc(sizeof(Node));
    if (list == NULL) return false; // 内存分配失败
    list->prior = NULL;
    list->next = NULL;
    return true;
}

结点操作

在指定结点后插入结点

bool insertAfter(DNode *p, DNode *s) {
    if (p == NULL || s == NULL) return false;
    s->next = p->next;
    if (p->next != NULL) p->next->prior = s;
    s->prior = p;
    p->next = s;
    return true;
}

删除指定结点的后继结点

bool removeAfter(DNode *p) {
    if (p == NULL) return false;
    DNode *q = p->next;
    if (q == NULL) return false; // p 的后继可能不存在
    p->next = q->next;
    if (q->next != NULL) q->next->prior = p;
    free(q);
    return true;
}

循环链表

循环链表的尾结点指向头结点，形成一个环。

可以将指针指向尾结点，此时下一个结点就是头结点。

定义及初始化

typedef struct Node {
    Element data;
    struct Node *next;
} Node, *CirLinkList;

bool initList(CirLinkList &list) {
    list = (LinkList)malloc(sizeof(Node));
    if (list == NULL) return false; // 内存分配失败
    list->next = list;
    return true;
}

属性

判断是否为空

bool isEmpty(CirLinkList list) {
    return list->next == list;
}

判断表尾

bool isTail(CirLinkList list, Node *p) {
    return p->next == list;
}

循环双链表

typedef struct DNode {
    Element data;
    struct DNode *prior, *next;
} DNode, *CirDLinkList;

初始化

bool initList(CirDLinkList &list) {
    list = (CirDLinkList)malloc(sizeof(DNode));
    if (list == NULL) return false; // 内存分配失败
    list->prior = list;
    list->next = list;
    return true;
}

静态链表

静态链表是用数组实现的链表，数组中的每个元素都是一个结点，结点中包含数据域和游标域。

游标域用来存放下一个结点的下标，即下一个结点在数组中的位置。用 -1 表示尾结点。

定义及初始化

typedef struct SNode {
    Element data;
    int cur; // 游标，为 0 时表示无指向
} SNode, SLinkList[MAX_SIZE];

顺序表 VS 链表

• 逻辑结构：都是线性结构。
• 存储结构：顺序表是连续存储，链表是非连续存储。
• 弹性：顺序表弹性差，链表弹性好。
• 查找：顺序表时间复杂度为 O(1)；链表时间复杂度为 O(n)。
• 插入/删除：顺序表时间复杂度为 O(n)；链表时间复杂度为 O(1) 或 O(n)。

十字链表法

十字链表法是一种用于表示稀疏矩阵的存储结构。

待补充