线性表

线性结构的特点是：

1、存在唯一的一个被称作“第一个”的数据元素

2、存在唯一的一个被称作“最后一个”的数据元素

3、除第一个之外，集合中的每个元素均只有一个前驱4、除最后一个以外，集合中的每个数据元素均只有一个后继

顺序存储就是把线性表的元素依次存放在一组地址连续的存储单元中。
就像电影院的座位：每个座位有固定编号，相邻座位物理上也挨着。你可以通过座位号（下标）直接找到对应的人。

• 随机存取：想访问第 i 个元素，直接用 data[i-1]，时间复杂度 O(1)。

• 插入/删除麻烦：在中间插入一个元素，需要把后面的元素全部后移；删除同理。平均移动约一半元素，时间复杂度 O(n)。

• 空间固定：需要预先分配大小，容易浪费或不够用。

常见操作时间复杂度

• 按位查找：O(1)

• 插入/删除（平均）：O(n)

• 求表长：O(1)

顺序表示和实现

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct
{
    ElemType *elem;
    int length;
    int listsize;
} SqList;

int InitList_Sq(SqList *L)
{
    // 分配内存空间，大小为LIST_INIT_SIZE 乘以ElemType的大小   
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (L->elem == NULL)
    {
        return OVERFLOW; // 如果内存分配失败，返回溢出错误   
    }
    L->length = 0;                // 初始化顺序表的长度为0   
    L->listsize = LIST_INIT_SIZE; // 初始化顺序表的容量为LIST_INIT_SIZE   
    return OK;
}

顺序表的插入

int insert(SeqList *L, int pos, int elem) {
    if (pos < 1 || pos > L->length + 1) return 0; // 位置非法
    if (L->length >= MAXSIZE) return 0;           // 表满
    for (int i = L->length; i >= pos; i--)
        L->data[i] = L->data[i-1];                // 后移
    L->data[pos-1] = elem;
    L->length++;
    return 1;
}

int ListInsert_Sq(SqList *L, int i, ElemType e)
{ // 判断插入位置是否合法，i的值应该在1 到L.length+1 之间
    if (i < 1 || i > L->length + 1)
    {
        return ERROR;
    } // 如果顺序表已满，需要重新分配内存空间
    if (L->length >= L->listsize)
    {
        ElemType *newbase = (ElemType *)realloc(L->elem, (L->listsize + LISTINCREMENT) * sizeof(ElemType));
        if (!newbase)
        {
            exit(OVERFLOW); // 内存分配失败，退出程序
        } // 更新顺序表的基地址和容量
        L->elem = newbase;
        L->listsize += LISTINCREMENT;
    } // 找到插入位置的地址
    ElemType *q = &(L->elem[i - 1]); // 将插入位置之后的元素向后移动一位
    for (ElemType *p = &(L->elem[L->length - 1]); p >= q; --p)
    {
        *(p + 1) = *p;
    } // 将新元素插入到指定位置
    *q = e;
    ++L->length; // 更新顺序表的长度
    return OK;
}

顺序表的删除

int ListDelete_Sq(SqList *L, int i, ElemType *e)
{ // 判断删除位置是否合法，i的值应该在1 到L.length之间
    if (i < 1 || i > L->length)
    {
        return ERROR;
    } // 找到删除位置的地址
    ElemType *p = &(L->elem[i - 1]); // 将删除位置的元素赋值给e
    *e = *p;                         // 将删除位置之后的元素向前移动一位
    ElemType *q = L->elem + L->length - 1;
    for (++p; p <= q; ++p)
    {
        *(p - 1) = *p;
    } // 更新顺序表的长度
    --L->length;
    return OK;
}

顺序表的合并

void MergeList_Sq(SqList *La, SqList *Lb, SqList *Lc)
{   
    ElemType *pa, *pb, *pc;
    ElemType *pa_last, *pb_last; // 初始化指针 pa 和 pb，分别指向顺序表 La 和 Lb 的第一个元素
    pa = La->elem;
    pb = Lb->elem; // 初始化 Lc 的大小，并分配内存空间
    Lc->listsize = Lc->length = La->length + Lb->length;
    Lc->elem = (ElemType *)malloc(Lc->listsize * sizeof(ElemType));
    if (!Lc->elem)
    {
        exit(OVERFLOW); // 如果内存分配失败，退出程序
    }
    pc = Lc->elem; // 初始化指针 pc，指向顺序表 Lc 的第一个元素
    // 初始化指针pa_last和pb_last，分别指向顺序表 La 和 Lb的最后一个元素
    pa_last = La->elem + La->length - 1;
    pb_last = Lb->elem + Lb->length - 1;
    while (pa <= pa_last && pb <= pb_last)
    { // 合并两个顺序表，直到其中一个顺序表遍历完
        if (*pa <= *pb)
        {
            *pc++ = *pa++; // 将较小的元素放入 Lc
        }
        else
        {
            *pc++ = *pb++;
        }
    }
    while (pa <= pa_last)
    { // 如果pa没有到达最后一个元素，将剩余的元素插入到Lc中
        *pc++ = *pa++;
    }
    while (pb <= pb_last)
    { // 如果pb没有到达最后一个元素，将剩余的元素插入到Lc中
        *pc++ = *pb++;
    }
}

线性链表

一个节点包括两个域：

存储数据元素信息的域称为数据域；

存储直接后继存储位置的域称为指针域。

链式存储不用连续的内存，每个元素（节点）包含数据和指向下一个节点的指针。

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

• 动态内存：需要多少就申请多少，不会浪费。

• 插入/删除高效：只需修改指针，无需移动元素，时间复杂度 O(1)（已知位置）。

• 不支持随机存取：要访问第 i 个元素，必须从头开始一个一个找，时间复杂度 O(n)。

创建链表

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

void CreateList_L(LinkList *L, int n)
{
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    for (int i = n; i > 0; i--)
    {
        LNode *p = (LNode *)malloc(sizeof(LNode));
        scanf("%d", p->data);
        p->next = L->next;
        L->next = p;
    }
}

插入结点

int ListInsert_L(LinkList *L, int i, ElemType e)
{
    LinkList p = *L; // 用指针 p 指向头节点
    int j = 0;       // 遍历链表，直到找到第 i-1 个节点
    while (p && j < i - 1)
    {
        p = p->next;
        ++j;
    } // 如果遍历到链表末尾，说明i的值不合法，返回ERROR
    if (!p || j > i - 1)
    {
        return ERROR;
    } // 创建一个新节点 s，将新节点插入到第 i-1 个节点之后
    LinkList s = (LinkList)malloc(sizeof(LNode)); // 为新节点分配内存
    if (!s)
    {
        return ERROR; // 如果内存分配失败，返回ERROR
    }
    s->data = e;       // 将数据 e 插入到新节点中
    s->next = p->next; // 将新节点的 next 指向原来第 i 个节点
    p->next = s;       // 将第 i-1 个节点的 next 指向新节点
    return OK;         // 插入成功，返回 OK
}

查找结点

int GetElem_L(LinkList L, int i, ElemType *e)
{
    LinkList p = L->next; // 指针 p 指向链表的第一个元素
    int j = 1;            // 从头节点开始遍历链表，直到找到第 i 个节点或者遍历到链表末尾
    while (p && j < i)
    {
        p = p->next;
        ++j;
    } // 如果遍历到链表末尾，说明 i 的值不合法，返回 ERROR
    if (!p || j > i)
    {
        return ERROR;
    } // 将第 i 个节点的值赋值给 e
    *e = p->data;
    return OK;
}

删除结点

// 删除链表 L 中第 i 个元素，并将其值存入 e
int ListDelete_L(LinkList *L, int i, ElemType *e)
{
    LinkList p = *L; // 指针 p 指向头节点
    LinkList q;      // 用于保存要删除的节点
    int j = 0;       // 从头节点开始遍历链表，找到第 i-1 个节点
    while (p->next && j < i - 1)
    {
        p = p->next;
        ++j;
    } // 如果遍历到链表末尾，说明 i 的值不合法，返回 ERROR
    if (!(p->next) || j > i - 1)
    {
        return ERROR;
    } // 删除第 i 个节点，并将其值赋值给 e
    q = p->next;       // 保存要删除的节点
    p->next = q->next; // 将第 i-1 个节点的 next 指向第 i+1 个节点
    *e = q->data;      // 将被删除节点的值赋给 e
    free(q);           // 释放被删除节点的内存
    return OK;         // 删除成功，返回 OK
}

合并有序链表

void MergeList_L(LinkList *La, LinkList *Lb, LinkList *Lc)
{
    LinkList pa = (*La)->next; // 指向链表 La 的第一个节点
    LinkList pb = (*Lb)->next; // 指向链表 Lb 的第一个节点
    LinkList pc;               // 用于构建链表 Lc
    *Lc = pc = *La;            // 将 Lc 的头节点指向 La，并将 pc 也指向 La
    // 当 pa 和 pb 都不为 NULL 时，比较它们的值，将较小的节点插入到 Lc 中
    while (pa && pb)
    {
        if (pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    } // 如果 pa 不为 NULL，将剩余的节点插入到 Lc 中
    pc->next = pa ? pa : pb; // 释放链表 Lb 的头节点，避免内存泄漏
    free(*Lb);
}

应用场景

1.动态数据结构：当你需要一个可以动态调整大小的数据结构时，线性链表非常适合。与数组相比，链表可以方便地在运行时插入和删除元素，而无需预先定义大小。

2.频繁的插入和删除操作：在需要频繁进行插入和删除操作的场景中，链表的性能优于数组。例如，任务调度、操作系统中的进程管理等场景。

3.实现其他数据结构：链表常用于实现其他复杂数据结构，如栈、队列、哈希表等。这些数据结构的基本操作可以通过链表轻松实现。

4.处理不确定数量的数据：例如，处理用户输入的字符串或数据流时，链表能够灵活地扩展以适应不同的数据量。

5.实现图的邻接表：在图的表示中，链表常用作邻接表的实现，以存储图的边和节点的关系。

6.内存管理：链表在内存管理中也很有用，例如，空闲内存块的链表管理，可以有效地跟踪和分配内存。

项目	顺序表（数组）	链表
存储方式	连续内存	非连续，通过指针链接
空间分配	静态/动态数组，需预分配	动态按需分配
存取速度	随机存取 O(1)	顺序存取 O(n)
插入/删除	需移动元素 O(n)	只需改指针 O(1)（已知位置）
内存利用率	可能浪费（固定大小）	无浪费，但每个节点有指针开销
缓存友好性	好（连续内存）	差（节点分散）

双向链表

应用场景

浏览器的历史记录

在Web 浏览器中，双向链表被用于管理浏览器的前进和后退历史记录：

•前进与后退功能：双向链表允许用户在浏览器中轻松实现前进（next）和后退（previous）操作。当用户访问一个新页面时，当前页面会被添加到链表中，用户可以在链表中进行遍历，快速返回到之前的页面，或者前进到未来的页面。

双向导航菜单

在用户界面（UI）设计中，双向链表可以用来构建双向导航菜单：

•前进与后退功能：用户可以在多个菜单层级之间进行前后跳转，双向链表使得这种操作变得更加高效，尤其在用户需要频繁切换菜单时。

音乐播放器中的播放列表

在音乐播放器或视频播放器中，双向链表可以用来管理播放列表：

•播放列表的管理：双向链表允许用户在播放列表中前后跳转，用户可以选择跳到播放列表中的任意歌曲，并且支持播放列表的循环播放和顺序播放。

双向链表的构建

一个结点中有两个指针域，一个指向直接后继，另一个指向直接前驱。

typedef struct DuLNode
{
    ElemType data;
    struct DuLNode *prior, *next;
} DuLNode, *DuLinkList;

// 创建一个带头节点的空双向链表
DuLinkList CreateList_DuL()
{
    DuLinkList L = (DuLinkList)malloc(sizeof(DuLNode));
    if (L == NULL)
    {
        return NULL;
    }
    L->prior = L;
    L->next = L;
    return L;
}

节点插入

int ListInsert_DuL(DuLinkList *L, int i, ElemType e)
{
    DuLinkList p = GetElem_DulL(*L, i); // 获取第 i 个元素的指针
    if (p == NULL)
    {
        return ERROR;
    } // 创建一个新节点 s
    DuLinkList s = (DuLinkList)malloc(sizeof(DuLNode));
    if (s == NULL)
    {
        return ERROR; // 如果内存分配失败
    }
    s->data = e;
    s->prior = p->prior;
    s->next = p; // 修改前后节点的指针
    if (p->prior != NULL)
    {
        p->prior->next = s;
    }
    p->prior = s;
    return OK;
}

节点删除

int ListDelete_DulL(DuLinkList *L, ElemType *e, int i)
{
    DuLinkList p = GetElem_DulL(*L, i); // 获取第 i 个元素的指针
    if (p == NULL)
    {
        return ERROR;
    }
    // 将被删除元素的值赋给 e
    *e = p->data;
    // 更新双向链表的前后节点指针
    p->prior->next = p->next;
    if (p->next != NULL)
    {
        p->next->prior = p->prior;
    }
    free(p); // 释放被删除节点的内存
    return OK;
}