数据结构（线性表）

1线性表的定义与操作

1.1线性表的定义

线性表是一种基础的数据结构，其主要特点是：数据元素之间存在一种线性关系（一对一）。线性表的每一个数据元素都有一个唯一的前驱和后继，除了第一个元素没有前驱，最后一个元素没有后继

有限性：线性表中数据元素的个数是有限的。
序列性：数据元素之间存在着先后顺序，即线性表中的数据元素是有顺序的。
相同数据类型：线性表中的数据元素具有相同的数据类型。

线性表（Linear List）是由n个数据元素组成的有限序列，可以用以下形式表示：

顺序线性表：数据元素在内存中占据连续的存储空间。
链式线性表：数据元素在内存中不必连续，但每个元素都包含指向下一个元素的地址（指针）

1.2线性表的基本操作

初始化操作
- 功能：创建一个空的线性表，为后续的操作做好准备。
- 实现：通常分配一定的存储空间，并将线性表的长度设置为 0。
插入操作
- 功能：在指定位置插入一个新的数据元素。
- 实现：首先要判断插入位置是否合法，如果合法，则从插入位置开始，将后面的元素依次向后移动一位，然后在指定位置插入新元素，并更新线性表的长度。
- 例如，在线性表 [1, 2, 3] 中，在位置 2 插入元素 4，结果为 [1, 2, 4, 3]。
删除操作
- 功能：删除指定位置的数据元素。
- 实现：首先判断删除位置是否合法，如果合法，则将删除位置后面的元素依次向前移动一位，覆盖被删除的元素，并更新线性表的长度。
- 例如，在线性表 [1, 2, 3, 4] 中，删除位置 2 的元素，结果为 [1, 2, 4]。
查找操作
- 功能：在线性表中查找指定的数据元素，并返回其位置。
- 实现：从线性表的第一个元素开始，依次比较每个元素与目标元素是否相等，直到找到目标元素或遍历完整个线性表。
- 例如，在线性表 [1, 2, 3, 4] 中，查找元素 3，返回位置 2。
遍历操作
- 功能：依次访问线性表中的每个数据元素。
- 实现：使用循环从线性表的第一个元素开始，依次访问每个元素，直到遍历完整个线性表。
- 例如，对于线性表 [1, 2, 3, 4]，遍历输出为 “1 2 3 4”。
获取长度操作
- 功能：返回线性表中数据元素的个数。
- 实现：直接返回存储线性表长度的变量值。
判断空操作
- 功能：判断线性表是否为空。
- 实现：如果线性表的长度为 0，则为空，返回 true；否则返回 false。

2线性表的顺序存储

2.1顺序表的定义与初始化

一、顺序表的定义

顺序表，又称线性表的顺序存储结构，是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。在顺序表中，各个表项的逻辑顺序与其存放的物理顺序一致，即第i个表项存储于第i个物理位置（1≤i≤n）。

顺序表具有以下特点：

随机访问：可通过首地址和元素序号在单位时间O(1)内找到指定的元素。
存储密度高：因为每个结点存储空间只用来存储数据元素，没有额外的开销。
物理位置相邻：逻辑上相邻的元素在物理位置上也相邻，因此插入和删除元素需要移动大量元素，比较耗时。

二、顺序表的初始化

确定顺序表的存储结构
- 通常可以使用数组来实现顺序表。定义一个数组来存储数据元素，并记录顺序表的当前长度。
分配存储空间
- 根据实际需求确定数组的大小，并在内存中分配相应的空间。可以在程序运行时动态分配空间，也可以使用固定大小的数组。
设置初始状态
- 将顺序表的长度初始化为 0，表示当前没有数据元素。同时，可以将数组的所有元素初始化为特定的值，如 0 或 null。

以下是用 C 语言实现顺序表初始化的示例代码：

方式一：静态数组定义和初始化

这是最简单的定义和初始化方式，适用于固定大小的顺序表。

#include <stdio.h>

#define MAXSIZE 100  // 定义顺序表的最大容量
typedef int ElemType;  // 定义顺序表中元素的类型

typedef struct {
    ElemType data[MAXSIZE];  // 存储数据的静态数组
    int length;  // 当前表长
} SqList;  // 定义顺序表的结构体类型

// 初始化顺序表
void InitList(SqList *L) {
    L->length = 0;  // 初始化表长为0
}

int main() {
    SqList L;  // 声明一个顺序表变量
    InitList(&L);  // 初始化顺序表
    // ... 其他操作
    return 0;
}

方式二：动态数组定义和初始化

这种方式允许在运行时动态分配内存，适用于不确定顺序表大小的情况。

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;  // 定义顺序表中元素的类型

typedef struct {
    ElemType *data;  // 存储数据的动态数组
    int length;  // 当前表长
    int maxSize;  // 数组的最大容量
} SqList;  // 定义顺序表的结构体类型

// 初始化顺序表
void InitList(SqList *L, int maxSize) {
    L->data = (ElemType *)malloc(maxSize * sizeof(ElemType));  // 动态分配内存
    if (L->data == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    L->length = 0;  // 初始化表长为0
    L->maxSize = maxSize;  // 设置最大容量
}

// 释放顺序表的内存
void FreeList(SqList *L) {
    free(L->data);
    L->data = NULL;
    L->length = 0;
    L->maxSize = 0;
}

int main() {
    SqList L;  // 声明一个顺序表变量
    InitList(&L, 100);  // 初始化顺序表，最大容量为100
    // ... 其他操作
    FreeList(&L);  // 释放顺序表的内存
    return 0;
}

方式三：内存分配与初始化函数结合

这种方式将内存分配和初始化结合在一起，适用于需要初始化默认值的情况。

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;  // 定义顺序表中元素的类型

typedef struct {
    ElemType *data;  // 存储数据的动态数组
    int length;  // 当前表长
    int maxSize;  // 数组的最大容量
} SqList;  // 定义顺序表的结构体类型

// 初始化顺序表并分配内存
SqList* CreateList(int maxSize) {
    SqList *L = (SqList *)malloc(sizeof(SqList));  // 动态分配顺序表结构体内存
    if (L == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    L->data = (ElemType *)malloc(maxSize * sizeof(ElemType));  // 动态分配数组内存
    if (L->data == NULL) {
        printf("内存分配失败\n");
        free(L);
        exit(1);
    }
    L->length = 0;  // 初始化表长为0
    L->maxSize = maxSize;  // 设置最大容量
    return L;
}

// 释放顺序表的内存
void DestroyList(SqList *L) {
    free(L->data);
    free(L);
}

int main() {
    SqList *L = CreateList(100);  // 创建顺序表，最大容量为100
    // ... 其他操作
    DestroyList(L);  // 释放顺序表的内存
    return 0;
}

2.2顺序表的基本操作

1插入运算

插入运算的步骤

检查位置合法性：
- 确保插入位置 pos 在有效范围内，即 1 ≤ pos ≤ length + 1，其中 length 是顺序表的当前长度。
- 如果 pos 小于 1 或大于 length + 1，则插入位置非法，通常返回错误或抛出异常。
检查容量：
- 确保顺序表的容量（即数组的大小）足够容纳新元素。
- 如果当前容量不足，需要进行扩容操作（通常是分配一个更大的数组，并将原数组的内容复制到新数组中）。
插入元素：
- 从插入位置 pos 开始，将顺序表中该位置及其后的所有元素向后移动一个位置，以腾出空间插入新元素。
- 将新元素插入到 pos - 1 的位置（因为数组索引从 0 开始）。
更新长度：
- 将顺序表的长度 length 增加 1。

以下是一个简单的 c语言实现，展示了如何在顺序表中插入元素

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100  // 定义顺序表的最大容量
typedef int ElemType;  // 定义顺序表中元素的类型

typedef struct {
    ElemType data[MAXSIZE];  // 存储数据的数组
    int length;  // 当前表长
} SqList;  // 定义顺序表的结构体类型

// 初始化顺序表
void InitList(SqList *L) {
    L->length = 0;  // 初始化表长为0
}

// 插入元素到顺序表的指定位置
int InsertList(SqList *L, int pos, ElemType e) {
    if (L->length >= MAXSIZE) {
        printf("顺序表已满，无法插入元素 %d\n", e);
        return 0;  // 插入失败
    }
    if (pos < 1 || pos > L->length + 1) {
        printf("插入位置 %d 不合法\n", pos);
        return 0;  // 插入失败
    }
    // 从后向前移动元素，为新元素腾出位置
    for (int i = L->length; i >= pos; i--) {
        L->data[i] = L->data[i - 1];
    }
    L->data[pos - 1] = e;  // 插入新元素
    L->length++;  // 更新当前表长
    return 1;  // 插入成功
}

// 打印顺序表中的所有元素
void DisplayList(const SqList *L) {
    for (int i = 0; i < L->length; i++) {
        printf("%d ", L->data[i]);
    }
    printf("\n");
}

int main() {
    SqList L;  // 声明一个顺序表变量
    InitList(&L);  // 初始化顺序表

    // 插入1到10的数字到顺序表中
    for (int i = 1; i <= 10; i++) {
        InsertList(&L, i, i);
    }

    // 打印顺序表中的所有元素
    printf("顺序表中的元素：");
    DisplayList(&L);

    // 在位置3插入一个新元素 99
    if (InsertList(&L, 3, 99)) {
        printf("插入元素后的顺序表：");
        DisplayList(&L);
    }

    return 0;
}

2删除运算

删除运算的步骤

检查位置合法性：
- 确保删除位置 pos 在有效范围内，即 1 ≤ pos ≤ length，其中 length 是顺序表的当前长度。
- 如果 pos 小于 1 或大于 length，则删除位置非法，通常返回错误或抛出异常。
删除元素：
- 从删除位置 pos 开始，将顺序表中该位置之后的所有元素向前移动一个位置，以填补被删除元素留下的空位。
- 注意，不需要为被删除元素分配新的存储空间或进行其他特殊处理，因为顺序表的内存是连续的，只需调整后续元素的位置即可。
更新长度：
- 将顺序表的长度 length 减少 1。

// 删除顺序表中指定位置的元素
int deleteElem(SeqList *L, int pos) {
    if (L->length == 0) {
        return 0; // 顺序表为空，删除失败
    }
    if (pos < 1 || pos > L->length) {
        return 0; // 位置不合法，删除失败
    }
    for (int i = pos; i < L->length; i++) {
        L->data[i - 1] = L->data[i];
    }
    L->length--;
    return 1; // 删除成功
}

以下是一个完整的 C 代码示例，包括顺序表的定义、初始化、删除运算以及显示顺序表内容的功能。

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100  // 定义顺序表的最大容量
typedef int ElemType;  // 定义顺序表中元素的类型

typedef struct {
    ElemType data[MAXSIZE];  // 存储数据的数组
    int length;  // 当前表长
} SqList;  // 定义顺序表的结构体类型

// 初始化顺序表
void InitList(SqList *L) {
    L->length = 0;  // 初始化表长为0
}

// 插入元素到顺序表的指定位置
int InsertList(SqList *L, int pos, ElemType e) {
    if (L->length >= MAXSIZE) {
        printf("顺序表已满，无法插入元素 %d\n", e);
        return 0;  // 插入失败
    }
    if (pos < 1 || pos > L->length + 1) {
        printf("插入位置 %d 不合法\n", pos);
        return 0;  // 插入失败
    }
    // 从后向前移动元素，为新元素腾出位置
    for (int i = L->length; i >= pos; i--) {
        L->data[i] = L->data[i - 1];
    }
    L->data[pos - 1] = e;  // 插入新元素
    L->length++;  // 更新当前表长
    return 1;  // 插入成功
}

// 删除顺序表中指定位置的元素
int DeleteList(SqList *L, int pos, ElemType *e) {
    if (L->length == 0) {
        printf("顺序表为空，无法删除元素\n");
        return 0;  // 删除失败
    }
    if (pos < 1 || pos > L->length) {
        printf("删除位置 %d 不合法\n", pos);
        return 0;  // 删除失败
    }
    *e = L->data[pos - 1];  // 保存被删除的元素
    // 从前向后移动元素，覆盖被删除的元素
    for (int i = pos - 1; i < L->length - 1; i++) {
        L->data[i] = L->data[i + 1];
    }
    L->length--;  // 更新当前表长
    return 1;  // 删除成功
}

// 打印顺序表中的所有元素
void DisplayList(const SqList *L) {
    for (int i = 0; i < L->length; i++) {
        printf("%d ", L->data[i]);
    }
    printf("\n");
}

int main() {
    SqList L;  // 声明一个顺序表变量
    InitList(&L);  // 初始化顺序表

    // 插入1到10的数字到顺序表中
    for (int i = 1; i <= 10; i++) {
        InsertList(&L, i, i);
    }

    // 打印顺序表中的所有元素
    printf("顺序表中的元素：");
    DisplayList(&L);

    // 从顺序表中删除位置3的元素
    ElemType deletedElem;
    if (DeleteList(&L, 3, &deletedElem)) {
        printf("删除了元素 %d\n", deletedElem);
        printf("删除元素后的顺序表：");
        DisplayList(&L);
    }

    return 0;
}

3按值查找

按值查找的步骤

遍历顺序表：从顺序表的第一个元素开始，逐个检查每个元素的值是否等于指定的值。
记录位置：如果找到了与指定值相等的元素，则记录该元素的位置（索引）。注意，根据具体实现，位置可能是从0开始还是从1开始的索引。
返回结果：如果遍历完整个顺序表后找到了元素，则返回记录的位置；如果未找到，则返回一个表示失败的值。

// 按值查找元素在顺序表中的位置
int searchElem(SeqList *L, int elem) {
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] == elem) {
            return i + 1;
        }
    }
    return -1; // 未找到元素
}

以下是一个简单的 c语言实现，展示了如何在顺序表中找到具体元素

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100  // 定义顺序表的最大容量
typedef int ElemType;  // 定义顺序表中元素的类型

typedef struct {
    ElemType data[MAXSIZE];  // 存储数据的数组
    int length;  // 当前表长
} SqList;  // 定义顺序表的结构体类型

// 初始化顺序表
void InitList(SqList *L) {
    L->length = 0;  // 初始化表长为0
}

// 插入元素到顺序表的指定位置
int InsertList(SqList *L, int pos, ElemType e) {
    if (L->length >= MAXSIZE) {
        printf("顺序表已满，无法插入元素 %d\n", e);
        return 0;  // 插入失败
    }
    if (pos < 1 || pos > L->length + 1) {
        printf("插入位置 %d 不合法\n", pos);
        return 0;  // 插入失败
    }
    // 从后向前移动元素，为新元素腾出位置
    for (int i = L->length; i >= pos; i--) {
        L->data[i] = L->data[i - 1];
    }
    L->data[pos - 1] = e;  // 插入新元素
    L->length++;  // 更新当前表长
    return 1;  // 插入成功
}

// 按值查找顺序表中的元素
int LocateElem(const SqList *L, ElemType e) {
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] == e) {
            return i + 1;  // 返回元素位置（从1开始）
        }
    }
    return 0;  // 未找到元素
}

// 打印顺序表中的所有元素
void DisplayList(const SqList *L) {
    for (int i = 0; i < L->length; i++) {
        printf("%d ", L->data[i]);
    }
    printf("\n");
}

int main() {
    SqList L;  // 声明一个顺序表变量
    InitList(&L);  // 初始化顺序表

    // 插入1到10的数字到顺序表中
    for (int i = 1; i <= 10; i++) {
        InsertList(&L, i, i);
    }

    // 打印顺序表中的所有元素
    printf("顺序表中的元素：");
    DisplayList(&L);

    // 按值查找元素 5
    int pos = LocateElem(&L, 5);
    if (pos) {
        printf("元素 5 的位置是 %d\n", pos);
    } else {
        printf("未找到元素 5\n");
    }

    // 按值查找元素 20
    pos = LocateElem(&L, 20);
    if (pos) {
        printf("元素 20 的位置是 %d\n", pos);
    } else {
        printf("未找到元素 20\n");
    }

    return 0;
}

3线性表的链式存储

优点

动态大小：
- 链表不需要在创建时指定大小，它可以根据需要动态地增长和缩小。
高效插入和删除：
- 在链表中，插入和删除操作（特别是在已知节点位置的情况下）通常可以在O(1)时间复杂度内完成，因为只需要调整相邻节点的指针。
无需连续内存：
- 链表节点可以分散在内存中的任何位置，这有助于减少内存碎片问题。
灵活性：
- 链表可以通过各种方式（如双向链表、循环链表等）进行扩展，以满足不同的需求。

缺点

访问速度慢：
- 链表不支持随机访问，因此查找特定位置的元素需要从头节点开始顺序遍历，时间复杂度为O(n)。
额外空间开销：
- 每个链表节点都需要额外的空间来存储指针，这增加了内存的使用量。
内存管理复杂：
- 链表节点的动态分配和释放需要仔细管理，以避免内存泄漏和碎片化。
缓存性能较差：
- 由于链表节点在内存中通常不是连续存储的，因此可能无法充分利用CPU缓存，导致访问速度下降。

应用场景

链表适用于需要频繁进行插入和删除操作，但对随机访问要求不高的场景。
双向链表和循环链表等扩展形式可以用于需要双向遍历或循环遍历的场景。
在实现某些数据结构（如栈、队列、哈希表等）时，链表也可以作为底层存储结构。

3.1单向链表的结构

一、结构特点

节点组成：
- 单向链表由一系列节点（Node）组成，每个节点包含两个部分：数据域（Data）和指针域（Next）。
- 数据域用于存储节点的数据，可以是任意类型，由编程者自行指定。
- 指针域用于存储下一个节点的地址（或指针），指向链表中的下一个节点。
链接方向：
- 单向链表的链接方向是单向的，即只能从头节点开始，通过指针域依次访问后续节点。
头节点与头指针：
- 头节点是为了操作方便而设立的，通常放在第一个元素节点之前，其数据域一般无实际意义（但也可以用来存放链表长度等信息）。
- 头指针是指向链表头节点的指针，无论链表是否为空，头指针均不为空，是链表的必要元素。
无头与有头链表：
- 无头链表：不设立头节点，头指针直接指向第一个元素节点（如果存在）。
- 有头链表：设立头节点，头指针指向头节点，头节点的指针域指向第一个元素节点。

二单链表的定义与初始化

一、单链表的定义

typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode;

二、单链表的初始化

ListNode* initList() {
    // 创建一个空的头节点
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    head->data = 0; // 头节点的数据域可以存储一些特殊信息，这里初始化为 0
    head->next = NULL;
    return head;
}

以下是一个用C语言初始化单链表的示例（包含头节点）：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点
typedef int ElemType;  // 定义链表中元素的类型

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

// 初始化链表
LinkedList InitList() {
    LinkedList L = (LinkedList)malloc(sizeof(Node));  // 申请头节点空间
    if (!L) {
        printf("内存分配失败\n");
        exit(1);  // 内存分配失败，退出程序
    }
    L->next = NULL;  // 初始化头节点，指针域为空
    return L;  // 返回初始化后的链表
}

// 测试初始化链表
int main() {
    LinkedList L = InitList();  // 初始化链表
    if (L->next == NULL) {
        printf("链表初始化成功，头节点指向 NULL\n");
    }
    // 这里可以继续对链表进行插入、删除等操作
    free(L);  // 释放头节点的内存
    return 0;
}

3.2单链表的基本操作

1插入结点建立单链表

在单链表中插入节点是一个常见的操作，它允许我们在链表的特定位置添加一个新的节点。

在链表头部插入节点：新节点成为链表的新头节点。
在链表尾部插入节点：新节点成为链表的最后一个节点。
在链表中间插入节点：在指定位置插入新节点，新节点位于指定位置的节点之前。

单链表的定义

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点的类型
typedef int ElemType;  // 定义链表中元素的类型

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

初始化单链表

// 初始化链表
LinkedList InitList() {
    LinkedList L = (LinkedList)malloc(sizeof(Node));  // 申请头节点空间
    if (!L) {
        printf("内存分配失败\n");
        exit(1);  // 内存分配失败，退出程序
    }
    L->next = NULL;  // 初始化头节点，指针域为空
    return L;  // 返回初始化后的链表
}

在链表头部插入节点

// 在链表头部插入节点
void InsertHead(LinkedList L, ElemType e) {
    Node *s = (Node *)malloc(sizeof(Node));  // 申请新节点空间
    if (!s) {
        printf("内存分配失败\n");
        exit(1);  // 内存分配失败，退出程序
    }
    s->data = e;  // 新节点数据域赋值
    s->next = L->next;  // 新节点的指针域指向原头节点的下一个节点
    L->next = s;  // 头节点的指针域指向新节点
}

在链表尾部插入节点

// 在链表尾部插入节点
void InsertTail(LinkedList L, ElemType e) {
    Node *p = L;
    // 找到链表的最后一个节点
    while (p->next) {
        p = p->next;
    }
    Node *s = (Node *)malloc(sizeof(Node));  // 申请新节点空间
    if (!s) {
        printf("内存分配失败\n");
        exit(1);  // 内存分配失败，退出程序
    }
    s->data = e;  // 新节点数据域赋值
    s->next = NULL;  // 新节点的指针域指向NULL
    p->next = s;  // 原最后一个节点的指针域指向新节点
}

在指定位置插入节点

// 在链表的第pos个位置插入节点
int InsertAtPosition(LinkedList L, int pos, ElemType e) {
    Node *p = L;
    int i = 0;
    // 找到插入位置的前一个节点
    while (p && i < pos - 1) {
        p = p->next;
        i++;
    }
    if (!p || i > pos - 1) {
        printf("插入位置不合法\n");
        return 0;  // 插入失败
    }
    // 创建新节点
    Node *s = (Node *)malloc(sizeof(Node));
    if (!s) {
        printf("内存分配失败\n");
        exit(1);  // 内存分配失败，退出程序
    }
    s->data = e;  // 新节点数据域赋值
    s->next = p->next;  // 新节点的指针域指向插入位置的下一个节点
    p->next = s;  // 插入位置前一个节点的指针域指向新节点
    return 1;  // 插入成功
}

打印链表

// 打印链表中的所有元素
void DisplayList(LinkedList L) {
    Node *p = L->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

主函数

int main() {
    LinkedList L = InitList();  // 初始化链表

    // 在链表头部插入节点
    InsertHead(L, 1);
    InsertHead(L, 2);

    // 在链表尾部插入节点
    InsertTail(L, 3);
    InsertTail(L, 4);

    // 在指定位置插入节点
    InsertAtPosition(L, 3, 5);  // 在第3个位置插入元素5

    // 打印链表中的所有元素
    printf("链表中的元素：");
    DisplayList(L);

    return 0;
}

2有头节点的单链表

在有头节点的单链表中，链表包含一个额外的节点，称为头节点（或哑节点、哨兵节点）。头节点不存储实际的数据，而是作为链表的起点，其next指针指向链表的第一个实际数据节点。头节点的存在可以简化链表的操作，特别是在插入和删除节点时，因为它允许我们在链表头部进行这些操作而无需检查是否为空链表。

定义

在C语言中，有头节点的单链表可以通过定义一个结构体来表示链表节点，其中包含一个数据域和一个指向下一个节点的指针域。头节点也是这个结构体的一个实例，但其数据域通常不会被使用。

typedef struct Node {  
    int data; // 数据域，可以存储任意类型的数据，这里以int为例  
    struct Node* next; // 指针域，指向下一个节点  
} Node;

初始化

初始化有头节点的单链表时，需要为头节点分配内存，并将其next指针设置为NULL，表示链表当前为空。以下是一个初始化有头节点的单链表的函数示例：

Node* initLinkedList() {  
    Node* head = (Node*)malloc(sizeof(Node)); // 为头节点分配内存  
    if (head == NULL) {  
        // 内存分配失败，可以打印错误信息或进行其他错误处理  
        printf("内存分配失败\n");  
        return NULL; // 返回NULL表示初始化失败  
    }  
    head->next = NULL; // 初始化头节点的next指针为NULL，表示链表为空  
    return head; // 返回头节点的指针  
}

3求单链表的长度

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点的类型
typedef int ElemType;

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

// 初始化有头节点的单链表
LinkedList InitList() {
    LinkedList L = (LinkedList)malloc(sizeof(Node));  // 申请头节点空间
    if (!L) {
        printf("内存分配失败\n");
        exit(1);
    }
    L->next = NULL;  // 初始化头节点的下一个节点为空
    return L;
}

// 在链表尾部插入节点
void InsertTail(LinkedList L, ElemType e) {
    Node *p = L;
    while (p->next) {
        p = p->next;
    }
    Node *s = (Node *)malloc(sizeof(Node));  // 申请新节点空间
    if (!s) {
        printf("内存分配失败\n");
        exit(1);
    }
    s->data = e;      // 新节点数据域赋值
    s->next = NULL;   // 新节点的指针域指向NULL
    p->next = s;      // 原最后一个节点的指针域指向新节点
}

// 求链表的长度
int GetLength(LinkedList L) {
    int length = 0;               // 初始化长度为0
    Node *p = L->next;           // 从头节点的下一个节点开始遍历
    while (p) {
        length++;                 // 计数
        p = p->next;             // 移动到下一个节点
    }
    return length;               // 返回链表的长度
}

// 打印链表中的所有元素
void DisplayList(LinkedList L) {
    Node *p = L->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 主函数
int main() {
    LinkedList L = InitList();  // 初始化链表

    // 插入一些元素到链表中
    InsertTail(L, 10);
    InsertTail(L, 20);
    InsertTail(L, 30);
    InsertTail(L, 40);

    // 打印链表
    printf("链表中的元素：");
    DisplayList(L);

    // 求链表的长度
    int length = GetLength(L);
    printf("链表的长度是：%d\n", length);

    return 0;
}

4输出表中所有元素

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点的类型
typedef int ElemType;

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

// 初始化有头节点的单链表
LinkedList InitList() {
    LinkedList L = (LinkedList)malloc(sizeof(Node));  // 申请头节点空间
    if (!L) {
        printf("内存分配失败\n");
        exit(1);
    }
    L->next = NULL;  // 初始化头节点的下一个节点为空
    return L;
}

// 在链表尾部插入节点
void InsertTail(LinkedList L, ElemType e) {
    Node *p = L;
    while (p->next) {
        p = p->next;
    }
    Node *s = (Node *)malloc(sizeof(Node));  // 申请新节点空间
    if (!s) {
        printf("内存分配失败\n");
        exit(1);
    }
    s->data = e;      // 新节点数据域赋值
    s->next = NULL;   // 新节点的指针域指向NULL
    p->next = s;      // 原最后一个节点的指针域指向新节点
}

// 打印链表中的所有元素
void DisplayList(LinkedList L) {
    Node *p = L->next;  // 从头节点的下一个节点开始遍历
    while (p) {
        printf("%d ", p->data);  // 输出当前节点的数据域
        p = p->next;             // 移动到下一个节点
    }
    printf("\n");
}

// 主函数
int main() {
    LinkedList L = InitList();  // 初始化链表

    // 插入一些元素到链表中
    InsertTail(L, 10);
    InsertTail(L, 20);
    InsertTail(L, 30);
    InsertTail(L, 40);

    // 打印链表中的所有元素
    printf("链表中的元素：");
    DisplayList(L);

    return 0;
}

5删除指定元素

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点的类型
typedef int ElemType;

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

// 初始化有头节点的单链表
LinkedList InitList() {
    LinkedList L = (LinkedList)malloc(sizeof(Node));  // 申请头节点空间
    if (!L) {
        printf("内存分配失败\n");
        exit(1);
    }
    L->next = NULL;  // 初始化头节点的下一个节点为空
    return L;
}

// 在链表尾部插入节点
void InsertTail(LinkedList L, ElemType e) {
    Node *p = L;
    while (p->next) {
        p = p->next;
    }
    Node *s = (Node *)malloc(sizeof(Node));  // 申请新节点空间
    if (!s) {
        printf("内存分配失败\n");
        exit(1);
    }
    s->data = e;      // 新节点数据域赋值
    s->next = NULL;   // 新节点的指针域指向NULL
    p->next = s;      // 原最后一个节点的指针域指向新节点
}

// 删除链表中指定的元素
void DeleteElement(LinkedList L, ElemType e) {
    Node *p = L;  // p 指向头节点
    Node *q;      // q 用于指向要删除的节点

    // 遍历链表，找到目标元素的前一个节点
    while (p->next && p->next->data != e) {
        p = p->next;
    }

    // 如果找到了目标元素
    if (p->next) {
        q = p->next;           // q 指向要删除的节点
        p->next = q->next;     // 修改前一个节点的指针域，跳过目标节点
        free(q);               // 释放目标节点的内存空间
        printf("元素 %d 已删除\n", e);
    } else {
        printf("链表中不存在元素 %d\n", e);
    }
}

// 打印链表中的所有元素
void DisplayList(LinkedList L) {
    Node *p = L->next;  // 从头节点的下一个节点开始遍历
    while (p) {
        printf("%d ", p->data);  // 输出当前节点的数据域
        p = p->next;             // 移动到下一个节点
    }
    printf("\n");
}

// 主函数
int main() {
    LinkedList L = InitList();  // 初始化链表

    // 插入一些元素到链表中
    InsertTail(L, 10);
    InsertTail(L, 20);
    InsertTail(L, 30);
    InsertTail(L, 40);

    // 打印链表中的所有元素
    printf("删除前的链表：");
    DisplayList(L);

    // 删除指定元素
    DeleteElement(L, 30);

    // 打印删除后的链表
    printf("删除后的链表：");
    DisplayList(L);

    return 0;
}

6查找特定元素

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点的类型
typedef int ElemType;

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

// 初始化有头节点的单链表
LinkedList InitList() {
    LinkedList L = (LinkedList)malloc(sizeof(Node));  // 申请头节点空间
    if (!L) {
        printf("内存分配失败\n");
        exit(1);
    }
    L->next = NULL;  // 初始化头节点的下一个节点为空
    return L;
}

// 在链表尾部插入节点
void InsertTail(LinkedList L, ElemType e) {
    Node *p = L;
    while (p->next) {
        p = p->next;
    }
    Node *s = (Node *)malloc(sizeof(Node));  // 申请新节点空间
    if (!s) {
        printf("内存分配失败\n");
        exit(1);
    }
    s->data = e;      // 新节点数据域赋值
    s->next = NULL;   // 新节点的指针域指向NULL
    p->next = s;      // 原最后一个节点的指针域指向新节点
}

// 查找链表中指定的元素
int FindElement(LinkedList L, ElemType e) {
    Node *p = L->next;  // 从头节点的下一个节点开始遍历
    int index = 1;      // 记录元素的索引位置

    // 遍历链表，查找目标元素
    while (p) {
        if (p->data == e) {
            return index;  // 返回元素的索引位置
        }
        p = p->next;       // 移动到下一个节点
        index++;           // 索引位置加1
    }

    return -1;  // 如果未找到，返回-1
}

// 打印链表中的所有元素
void DisplayList(LinkedList L) {
    Node *p = L->next;  // 从头节点的下一个节点开始遍历
    while (p) {
        printf("%d ", p->data);  // 输出当前节点的数据域
        p = p->next;             // 移动到下一个节点
    }
    printf("\n");
}

// 主函数
int main() {
    LinkedList L = InitList();  // 初始化链表

    // 插入一些元素到链表中
    InsertTail(L, 10);
    InsertTail(L, 20);
    InsertTail(L, 30);
    InsertTail(L, 40);

    // 打印链表中的所有元素
    printf("链表中的元素：");
    DisplayList(L);

    // 查找指定元素
    ElemType target = 30;
    int index = FindElement(L, target);

    if (index != -1) {
        printf("元素 %d 在链表中的位置是 %d\n", target, index);
    } else {
        printf("链表中不存在元素 %d\n", target);
    }

    return 0;
}

3.3循环链表

循环链表是一种特殊的链表结构，其特点是链表中的最后一个节点指向头节点，形成一个闭环。这种结构使得链表的遍历可以从任何节点开始，并且在遍历到链表末尾时可以无缝地回到链表的开头。循环链表可以是单向的（每个节点只有一个指针指向下一个节点）或双向的（每个节点有两个指针，分别指向前一个节点和后一个节点）。

循环链表的特点

闭环结构：链表的最后一个节点指向头节点，形成一个闭环。
遍历灵活：可以从任何节点开始遍历，并且在遍历到链表末尾时可以回到链表的开头。
节省空间：相比于双向链表，单向循环链表只需要一个指针域，节省了空间。
应用场景：常用于需要循环操作的场景，如循环队列、约瑟夫环问题等。

循环链表的基本操作

1. 初始化循环链表

初始化一个空的循环链表，创建一个头节点，并使其指向自身。

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点的类型
typedef int ElemType;

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

// 初始化循环链表
CircularLinkedList InitCircularList() {
    CircularLinkedList L = (CircularLinkedList)malloc(sizeof(Node));  // 申请头节点空间
    if (!L) {
        printf("内存分配失败\n");
        exit(1);
    }
    L->next = L;  // 头节点的下一个节点指向自身，形成闭环
    return L;
}

2. 插入节点

在循环链表中插入节点，可以选择在链表的头部或尾部插入。

// 在链表尾部插入节点
void InsertTail(CircularLinkedList L, ElemType e) {
    Node *p = L;
    while (p->next != L) {  // 找到链表的最后一个节点
        p = p->next;
    }
    Node *s = (Node *)malloc(sizeof(Node));  // 申请新节点空间
    if (!s) {
        printf("内存分配失败\n");
        exit(1);
    }
    s->data = e;      // 新节点数据域赋值
    s->next = L;      // 新节点的指针域指向头节点
    p->next = s;      // 原最后一个节点的指针域指向新节点
}

3. 删除节点

删除循环链表中的指定节点。

// 删除链表中指定的元素
void DeleteElement(CircularLinkedList L, ElemType e) {
    Node *p = L;  // p 指向头节点
    Node *q;      // q 用于指向要删除的节点

    // 遍历链表，找到目标元素的前一个节点
    while (p->next != L && p->next->data != e) {
        p = p->next;
    }

    // 如果找到了目标元素
    if (p->next != L) {
        q = p->next;           // q 指向要删除的节点
        p->next = q->next;     // 修改前一个节点的指针域，跳过目标节点
        free(q);               // 释放目标节点的内存空间
        printf("元素 %d 已删除\n", e);
    } else {
        printf("链表中不存在元素 %d\n", e);
    }
}

4. 查找节点

查找循环链表中的指定元素。

// 查找链表中指定的元素
int FindElement(CircularLinkedList L, ElemType e) {
    Node *p = L->next;  // 从头节点的下一个节点开始遍历
    int index = 1;      // 记录元素的索引位置

    // 遍历链表，查找目标元素
    while (p != L) {
        if (p->data == e) {
            return index;  // 返回元素的索引位置
        }
        p = p->next;       // 移动到下一个节点
        index++;           // 索引位置加1
    }

    return -1;  // 如果未找到，返回-1
}

5. 打印链表

遍历并打印循环链表中的所有元素。

// 打印链表中的所有元素
void DisplayList(CircularLinkedList L) {
    Node *p = L->next;  // 从头节点的下一个节点开始遍历
    while (p != L) {
        printf("%d ", p->data);  // 输出当前节点的数据域
        p = p->next;             // 移动到下一个节点
    }
    printf("\n");
}

主函数示例

// 主函数
int main() {
    CircularLinkedList L = InitCircularList();  // 初始化循环链表

    // 插入一些元素到链表中
    InsertTail(L, 10);
    InsertTail(L, 20);
    InsertTail(L, 30);
    InsertTail(L, 40);

    // 打印链表中的所有元素
    printf("链表中的元素：");
    DisplayList(L);

    // 查找指定元素
    ElemType target = 30;
    int index = FindElement(L, target);

    if (index != -1) {
        printf("元素 %d 在链表中的位置是 %d\n", target, index);
    } else {
        printf("链表中不存在元素 %d\n", target);
    }

    // 删除指定元素
    DeleteElement(L, 30);

    // 打印删除后的链表
    printf("删除后的链表：");
    DisplayList(L);

    return 0;
}

3.4双向链表

双向链表是一种链表结构，与单向链表不同，双向链表中的每个节点除了包含数据域外，还包含两个指针，分别指向前一个节点和后一个节点。这种结构使得链表的操作更加灵活，但也增加了空间的开销。

双向链表的特点

双向遍历：可以从任何一个节点开始向前或向后遍历链表。
灵活性高：插入和删除操作更加方便，因为可以直接访问前一个节点和后一个节点。
空间开销大：每个节点包含两个指针，相比于单向链表，空间开销更大。
应用场景：适用于需要频繁插入和删除操作的场景，如文本编辑器中的撤销/重做功能。

双向链表的基本操作

1. 初始化双向链表

初始化一个空的双向链表，创建一个头节点，并使其前后指针都指向自身（如果链表为空）。

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点的类型
typedef int ElemType;

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

// 初始化双向链表
DoubleLinkedList InitDoubleList() {
    DoubleLinkedList L = (DoubleLinkedList)malloc(sizeof(Node));  // 申请头节点空间
    if (!L) {
        printf("内存分配失败\n");
        exit(1);
    }
    L->prev = L;  // 头节点的前指针指向自身
    L->next = L;  // 头节点的后指针指向自身
    return L;
}

2. 插入节点

在双向链表中插入节点，可以选择在链表的头部或尾部插入。

// 在链表尾部插入节点
void InsertTail(DoubleLinkedList L, ElemType e) {
    Node *p = L;
    while (p->next != L) {  // 找到链表的最后一个节点
        p = p->next;
    }
    Node *s = (Node *)malloc(sizeof(Node));  // 申请新节点空间
    if (!s) {
        printf("内存分配失败\n");
        exit(1);
    }
    s->data = e;      // 新节点数据域赋值
    s->next = L;      // 新节点的后指针指向头节点
    s->prev = p;      // 新节点的前指针指向原最后一个节点
    p->next = s;      // 原最后一个节点的后指针指向新节点
    L->prev = s;      // 头节点的前指针指向新节点
}

3. 删除节点

删除双向链表中的指定节点。

// 删除链表中指定的元素
void DeleteElement(DoubleLinkedList L, ElemType e) {
    Node *p = L->next;  // p 指向第一个节点

    // 遍历链表，找到目标元素
    while (p != L && p->data != e) {
        p = p->next;
    }

    // 如果找到了目标元素
    if (p != L) {
        p->prev->next = p->next;  // 修改前一个节点的后指针
        p->next->prev = p->prev;  // 修改后一个节点的前指针
        free(p);                  // 释放目标节点的内存空间
        printf("元素 %d 已删除\n", e);
    } else {
        printf("链表中不存在元素 %d\n", e);
    }
}

4. 查找节点

查找双向链表中的指定元素。

// 查找链表中指定的元素
int FindElement(DoubleLinkedList L, ElemType e) {
    Node *p = L->next;  // 从第一个节点开始遍历
    int index = 1;      // 记录元素的索引位置

    // 遍历链表，查找目标元素
    while (p != L) {
        if (p->data == e) {
            return index;  // 返回元素的索引位置
        }
        p = p->next;       // 移动到下一个节点
        index++;           // 索引位置加1
    }

    return -1;  // 如果未找到，返回-1
}

5. 打印链表

遍历并打印双向链表中的所有元素。

// 打印链表中的所有元素
void DisplayList(DoubleLinkedList L) {
    Node *p = L->next;  // 从第一个节点开始遍历
    while (p != L) {
        printf("%d ", p->data);  // 输出当前节点的数据域
        p = p->next;             // 移动到下一个节点
    }
    printf("\n");
}

主函数示例

// 主函数
int main() {
    DoubleLinkedList L = InitDoubleList();  // 初始化双向链表

    // 插入一些元素到链表中
    InsertTail(L, 10);
    InsertTail(L, 20);
    InsertTail(L, 30);
    InsertTail(L, 40);

    // 打印链表中的所有元素
    printf("链表中的元素：");
    DisplayList(L);

    // 查找指定元素
    ElemType target = 30;
    int index = FindElement(L, target);

    if (index != -1) {
        printf("元素 %d 在链表中的位置是 %d\n", target, index);
    } else {
        printf("链表中不存在元素 %d\n", target);
    }

    // 删除指定元素
    DeleteElement(L, 30);

    // 打印删除后的链表
    printf("删除后的链表：");
    DisplayList(L);

    return 0;
}