链式表示

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

单链表定义

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

单链表的优点：
- 动态分配存储空间：链表的节点是在需要时动态分配的，因此在使用过程中不需要提前分配固定大小的存储空间。这使得内存利用率更加高效，可以减少内存浪费。
- 插入和删除方便：只要知道了某个节点的位置，就可以在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;
    }
}