↑
C/C++数据结构（未完结） - we1c0me t0 PurgationDevil 810g
C/C++

C/C++数据结构（未完结）

Posted by PurgationDevil Blog on April 13, 2026

C/C++数据结构

线性表（C语言）

顺序表

什么是顺序表？

通俗理解： 顺序表就像一排连续的车位，每个车位都有编号（0,1,2,3…），你可以把车（数据）停进去。

特点：

  • 车位是连续的，挨在一起的
  • 知道编号就能直接找到那个车位（比如我说”第3个车位”，你直接走过去）
  • 但是车位总数是固定的（比如最多停100辆车）

头文件和宏定义

1
2
3
4

#include <stdio.h>   // 标准输入输出库，用于printf等函数
#include <stdlib.h>  // 标准库，虽然这个程序没用到，但通常保留

#define MAXSIZE 100  // 定义顺序表的最大容量为100
  • #include：预处理指令，意思是”包含某个头文件”
  • <stdio.h>：Standard Input Output Header，提供输入输出功能
  • #define：定义常量，MAXSIZE就代表100，以后想改容量只改这里就行

结构体定义

1
2
3
4

typedef struct {
    int data[MAXSIZE];  // 车位数组，每个车位能停一个整数
    int length;         // 当前停了多少辆车
} SeqList;
  • typedef：类型定义关键字
  • struct：结构体，可以把多个变量打包成一个新类型
  • SeqList：新类型的名字，以后可以用SeqList L来定义变量
  • data[MAXSIZE]：整型数组，真正存储数据的地方
  • length：记录当前有多少个元素，初始为0

内存示意图：

SeqList L:
┌────────────────────────────────────────────┐
│ data[0] | data[1] | data[2] | ... | data[99] │  ← 100个车位
├────────────────────────────────────────────┤
│ length = 3  （当前停了3辆车）                 │
└────────────────────────────────────────────┘

实际数据：
data[0]=10, data[1]=20, data[2]=30, 后面都是空的

初始化函数

1
2
3
4

void initSeqList(SeqList *L) {
    L->length = 0;
    printf("顺序表初始化成功！\n");
}
  • void：函数没有返回值
  • initSeqList：函数名，Initialize Sequence List的缩写
  • SeqList *L：参数是指针类型，*表示这是一个地址
  • L->length：箭头运算符，通过指针访问结构体成员
  • 为什么要用指针？因为要在函数内部修改L的值，必须传地址

通俗理解：就像买了个100格子的收纳盒，现在一个东西都没放，所以长度是0。

为什么用指针？ 因为要在函数内部修改 length 的值，必须传地址。就像你要让别人帮你打扫你家，你得给他你家钥匙（地址）。

辅助判断函数

判断是否为空
1
2
3

int isEmpty(SeqList *L) {
    return L->length == 0;
}
  • int：返回整型，1表示真（空），0表示假（非空）
  • L->length == 0：比较运算符，相等返回1，不等返回0
判断是否已满
1
2
3

int isFull(SeqList *L) {
    return L->length == MAXSIZE;
}
  • 长度等于最大容量100时，说明满了，不能再加元素。
获取长度
1
2
3

int getLength(SeqList *L) {
    return L->length;
}
  • 返回长度值。

查找函数

按位置查找（位置从1开始）
1
2
3
4
5
6
7

int getElem(SeqList *L, int pos) {
    if (pos < 1 || pos > L->length) {
        printf("查找位置无效！\n");
        return -1;
    }
    return L->data[pos - 1];
}
  • pos：位置，比如第3个元素，pos=3
  • if (pos < 1 || pos > L->length)：检查位置是否合法
    • pos < 1：位置不能小于1
    • pos > L->length：位置不能超过实际长度
  • return -1：位置无效时返回-1作为错误标志
  • return L->data[pos - 1]：数组下标从0开始，所以要减1

图示：

位置:  第1个   第2个  第3个  第4个
       ↓      ↓      ↓      ↓
data: [10] , [20] , [30] , [40]
下标:   0      1      2      3

要找第3个元素：pos=3, 实际访问data[2]=30

边界检查：

  • pos < 1：不能找第0个或负数位置
  • pos > L->length：不能找超出实际数量的位置（比如只有3辆车，不能找第5辆）
按值查找
1
2
3
4
5
6
7
8

int locateElem(SeqList *L, int value) {
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] == value) {
            return i + 1;  // 返回位置（从1开始）
        }
    }
    return 0;  // 未找到返回0
}
  • value：要查找的值
  • for循环：遍历整个数组
  • if (L->data[i] == value)：找到匹配的值
  • return i + 1：返回位置（+1是因为位置从1开始）
  • return 0：循环结束都没找到，返回0

举例：找20

data[0]=10 → 10==20? 否
data[1]=20 → 20==20? 是 → 返回 1+1=2，表示第2个位置

插入函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void insertElem(SeqList *L, int pos, int value) {
    // 检查1：插入位置是否有效（1到length+1之间）
    if (pos < 1 || pos > L->length + 1) {
        printf("插入位置无效！\n");
        return;
    }
    
    // 检查2：顺序表是否已满
    if (isFull(L)) {
        printf("顺序表已满，无法插入！\n");
        return;
    }
    
    // 移动元素（从后往前移）
    for (int i = L->length; i >= pos; i--) {
        L->data[i] = L->data[i - 1];
    }
    
    // 插入新元素
    L->data[pos - 1] = value;
    L->length++;
    
    printf("成功在位置%d插入元素%d\n", pos, value);
}

第1步：检查位置合法性

  • pos > L->length + 1：比如当前有5个元素，可以在第6个位置插入（末尾），但不能在第7个位置

第2步：检查是否已满

  • 如果满了就报错，不能再插

第3步：移动元素（最关键的一步）

例子：原数据 [10, 20, 30, 40, 50]，length=5
要在pos=3插入25

移动前：
下标:  0    1    2    3    4
data: 10   20   30   40   50

移动过程（从后往前）：
i=5: data[5]=data[4]=50
i=4: data[4]=data[3]=40  
i=3: data[3]=data[2]=30

移动后：
下标:  0    1    2    3    4    5
data: 10   20   30   30   40   50
[2]这个位置空了
           
然后：data[2]=25（因为pos=3，下标=pos-1=2）

最终：[10, 20, 25, 30, 40, 50]

为什么从后往前移动？

  • 如果从前往后移动，前面的数据会覆盖后面的数据
  • 就像排队插队，后面的人要一个一个往后退

末尾添加

1
2
3

void appendElem(SeqList *L, int value) {
    insertElem(L, L->length + 1, value);
}
  • 直接在最后一个位置后面插入
  • 比如当前长度是5，就在第6个位置插入
  • 这样新元素就在末尾了

删除函数

按位置删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void deleteByPos(SeqList *L, int pos) {
    if (pos < 1 || pos > L->length) {
        printf("删除位置无效！\n");
        return;
    }
    
    int deletedValue = L->data[pos - 1];
    
    // 移动元素（从前往后移）
    for (int i = pos; i < L->length; i++) {
        L->data[i - 1] = L->data[i];
    }
    
    L->length--;
    printf("成功删除位置%d的元素%d\n", pos, deletedValue);
}

图解：

原数据：[10, 20, 30, 40, 50]，删除pos=3的元素

删除前：
下标:  0    1    2    3    4
data: 10   20   30   40   50
要删除[3]

移动过程（从前往后）：
i=3: data[2]=data[3]=40
i=4: data[3]=data[4]=50

移动后：
下标:  0    1    2    3    4
data: 10   20   40   50   50
                      ↑ 最后这个还留着，但length减1了

length从5变成4，所以实际数据是：[10, 20, 40, 50]
最后一个50不会被访问到
按值删除（只删第一个）
1
2
3
4
5
6
7
8

void deleteByValue(SeqList *L, int value) {
    int pos = locateElem(L, value);  // 先找位置
    if (pos != 0) {
        deleteByPos(L, pos);  // 找到就删除
    } else {
        printf("未找到值为%d的元素\n", value);
    }
}
  • 先查找，再删除，组合使用已有函数。
删除所有匹配的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void deleteAllByValue(SeqList *L, int value) {
    int count = 0;
    int i = 0;
    while (i < L->length) {
        if (L->data[i] == value) {
            // 移动后续元素
            for (int j = i; j < L->length - 1; j++) {
                L->data[j] = L->data[j + 1];
            }
            L->length--;
            count++;
            // 注意：这里i不增加，因为新的元素移到了当前位置
        } else {
            i++;
        }
    }
    
    if (count > 0) {
        printf("成功删除%d个值为%d的元素\n", count, value);
    } else {
        printf("未找到值为%d的元素\n", value);
    }
}

例子：数据 [38, 25, 38, 42]，删除所有38

i=0: data[0]=38 → 删除
     删除后：[25, 38, 42]，length=3
     i保持0，检查新的data[0]=25

i=0: data[0]=25 → 不是38，i++，i=1

i=1: data[1]=38 → 删除
     删除后：[25, 42]，length=2
     i保持1，但length=2，循环结束

总共删除2个38

打印函数

1
2
3
4
5
6
7
8
9
10
11
12

void printSeqList(SeqList *L) {
    if (isEmpty(L)) {
        printf("顺序表为空\n");
        return;
    }
    
    printf("顺序表内容：");
    for (int i = 0; i < L->length; i++) {
        printf("%d ", L->data[i]);
    }
    printf("(长度：%d，最大容量：%d)\n", L->length, MAXSIZE);
}
  • 先判断是否为空
  • 用循环遍历前length个元素（不是MAXSIZE个）
  • 打印所有元素、长度、容量

主函数演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int main() {
    SeqList list;  // 定义顺序表变量（在栈上分配内存）
    
    // 1. 初始化
    initSeqList(&list);  // &取地址，传指针
    
    // 2. 创建
    int arr[] = {12, 25, 38, 42, 56, 38, 79, 38};
    int n = sizeof(arr) / sizeof(arr[0]);  // 计算数组长度
    createSeqList(&list, arr, n);
    
    // 3. 插入
    insertElem(&list, 3, 30);  // 在第3个位置插30
    
    // 4. 打印
    printSeqList(&list);
    
    return 0;  // 程序正常结束
}
  • &list：取地址，传递给需要修改list的函数
  • sizeof(arr)/sizeof(arr[0])：计算数组元素个数的标准写法

单链表

什么是链表？

通俗理解： 链表就像寻宝游戏，每个宝藏（结点）都藏着一个线索（指针），告诉你下一个宝藏在哪里。宝藏可以放在任何地方（不连续的内存），通过线索串起来。

特点：

  • 不连续：每个结点可以放在内存的任何位置
  • 通过指针连接：每个结点知道下一个结点在哪
  • 动态：需要多少就创建多少，不会浪费空间

结构体定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

// 结点结构体
typedef struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域
} Node;

// 链表结构体
typedef struct {
    Node* head;   // 头指针，指向头结点（头结点不存数据）
    int length;   // 链表长度（不包含头结点）
} LinkedList;

内存示意图：

LinkedList L:
┌─────────┬──────┐
│ head ───┼──┐   │  head里存的是第一个结点的地址
│ length=3│  │   │
└─────────┴──┼───┘
             ↓
         ┌────┬────┐  ┌────┬────┐  ┌────┬────┐
         │ 10 │  ●─┼─→│ 20 │  ●─┼─→│ 30 │NULL│
         └────┴────┘  └────┴────┘  └────┴────┘
          结点1        结点2        结点3
          
● 表示地址（指针）
NULL 表示空，最后一个结点指向NULL

初始化函数

1
2
3
4
5
6
7

void initLinkedList(LinkedList* L) {
    // 创建头结点（不存数据）
    L->head = (Node*)malloc(sizeof(Node));
    L->head->next = NULL;  // 头结点的next指向NULL
    L->length = 0;
    printf("链表初始化成功（带头结点）！\n");
}
  • 初始化时一定要创建头结点
  • 头结点的 data 不用（可以随便放个值，或者不管它）
  • 头结点的 next = NULL，表示后面还没有数据结点
  • length = 0，因为还没有数据结点

辅助函数

1
2
3
4
5
6
7

int isEmpty(LinkedList* L) {
    return L->head->next == NULL;
}// 判断是否为空

int getLength(LinkedList* L) {
    return L->length;
}// 获取长度

和顺序表一样，不多解释。

创建结点函数

1
2
3
4
5
6
7

// 创建一个新结点，并赋值
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));  // 分配内存
    newNode->data = value;                            // 存入数据
    newNode->next = NULL;                         // 指针先指向NULL
    return newNode;                               // 返回新结点的地址
}
  • 这个函数专门负责”生产”新结点
  • 传入一个整数 a，创建一个结点，把 a 放进去
  • 新结点的 next 先指向 NULL（还没连接）
  • 返回这个新结点的地址（指针）
  • 其他函数要用新结点时，直接调用这个函数就行了

尾插法

1
2
3
4
5
6
7
8
9
10
11
12

void appendElem(LinkedList* L, int value) {
    Node* newNode = createNode(value);  // 直接调用创建结点函数
    
    // 找到最后一个结点（从头结点开始找）
    Node* p = L->head;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = newNode;
    L->length++;
    printf("成功在末尾添加元素%d\n", value);
}

图解：

原链表：head→[头]→[10]→[20]→[30]→NULL

添加40：

步骤1：创建新结点 [40]→NULL

步骤2：找最后一个结点
p=head，指向[10]
p->next不是NULL，p=p->next，指向[20]
p->next不是NULL，p=p->next，指向[30]
p->next是NULL，停止，p就是最后一个结点

步骤3：连接
p->next = newNode → [30]→[40]

步骤4：结果
head→[头]→[10]→[20]→[30]→[40]→NULL

为什么要遍历到末尾？

  • 因为没有记录尾指针，只能从头开始找
  • 就像寻宝，要从头开始一个一个找，直到找到最后一个

头插法

1
2
3
4
5
6
7

void prependElem(LinkedList* L, int value) {
    Node* newNode = createNode(value);  // 直接调用创建结点函数
    newNode->next = L->head->next;      // 新结点指向原来的第一个数据结点
    L->head->next = newNode;            // 头结点指向新结点
    L->length++;
    printf("成功在头部添加元素%d\n", value);
}

图解：

插入前：head→[头]→[10]→[20]→NULL

插入5：
步骤1：newNode->next = head->next → [5]→[10]
步骤2：head->next = newNode → [头]→[5]

结果：head→[头]→[5]→[10]→[20]→NULL

头插法的特点：

  • 不需要遍历，速度很快（O(1)）
  • 新元素总是在最前面

按位置插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void insertElem(LinkedList* L, int pos, int value) {
    if (pos < 1 || pos > L->length + 1) {
        printf("插入位置无效！\n");
        return;
    }
    
    Node* newNode = createNode(value);  // 直接调用创建结点函数
    
    // 找到第pos-1个结点（从头结点开始找）
    Node* p = L->head;
    for (int i = 1; i < pos; i++) {
        p = p->next;
    }
    // 此时p就是要插入位置的前一个结点
    newNode->next = p->next;
    p->next = newNode;
    L->length++;
    printf("成功在位置%d插入元素%d\n", pos, value);
}

图解（在位置3插入25）：

插入前：head→[头]→[10]→[20]→[30]→[40]→NULL

找到前驱（pos=3，找第2个结点）：
p = [20]

步骤：
newNode->next = p->next → [25]→[30]
p->next = newNode → [20]→[25]

结果：head→[头]→[10]→[20]→[25]→[30]→[40]→NULL

按位置删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void deleteByPos(LinkedList* L, int pos) {
    if (pos < 1 || pos > L->length) {
        printf("删除位置无效！\n");
        return;
    }
    
    // 找到第pos-1个结点（从头结点开始找）
    Node* p = L->head;
    for (int i = 1; i < pos; i++) {
        p = p->next;
    }
    
    Node* temp = p->next;  // 要删除的结点
    p->next = temp->next;
    
    int deletedValue = temp->data;
    free(temp);  // 释放内存
    L->length--;
    printf("成功删除位置%d的元素%d\n", pos, deletedValue);
}

图解（删除位置3）：

删除前：head→[头]→[10]→[20]→[25]→[30]→NULL

找到前驱（pos=3，找第2个结点）：
p = [20]

temp = p->next → temp指向[25]
p->next = temp->next → [20]→[30]
free(temp) 释放[25]

结果：head→[头]→[10]→[20]→[30]→NULL

按值删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void deleteByValue(LinkedList* L, int value) {
    if (isEmpty(L)) {
        printf("链表为空\n");
        return;
    }
    
    Node* p = L->head;      // 从头结点开始
    Node* q = p->next;       // 第一个数据结点
    
    while (q != NULL && q->data != value) {
        p = q;
        q = q->next;
    }
    
    if (q == NULL) {
        printf("未找到值为%d的元素\n", value);
        return;
    }
    
    p->next = q->next;
    free(p);
    L->length--;
    printf("成功删除值为%d的元素\n", value);
}
  • 删除时需要让前一个结点跳过被删结点，指向被删结点的下一个

图解（删除20）：

查找过程：
prev=NULL, p=[10] → 10≠20，继续
prev=[10], p=[20] → 20==20，找到

删除：
prev不为NULL，所以 prev->next = p->next
[10]→[30]

结果：head→[头]→[10]→[30]→[40]→NULL

按位置查找

1
2
3
4
5
6
7
8
9
10
11
12

int getElem(LinkedList* L, int pos) {
    if (pos < 1 || pos > L->length) {
        printf("查找位置无效！\n");
        return -1;
    }
    
    Node* p = L->head;   // 第一个数据结点
    for (int i = 1; i < pos; i++) {
        p = p->next;
    }
    return p->data;
}
  • 从head开始，走 pos-1 步
  • 比如找第3个：走2步，从第1个到第2个到第3个

按值查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int locateElem(LinkedList* L, int value) {
    Node* p = L->head;
    int pos = 1;
    
    while (p != NULL && p->data != value) {
        p = p->next;
        pos++;
    }
    
    if (p == NULL) {
        return 0;
    }
    return pos;
}
  • 一个一个找，同时记录位置
  • 找到了返回位置
  • 走到头都没找到返回0

打印链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void printLinkedList(LinkedList* L) {
    if (isEmpty(L)) {
        printf("链表为空\n");
        return;
    }
    
    printf("链表内容：");
    Node* p = L->head->next;
    while (p != NULL) {
        printf("%d -> ", p->data);
        p = p->next;
    }
    printf("NULL\n");
    printf("链表长度：%d\n", L->length);
}
  • 从head开始，一个一个往后走
  • 打印每个结点的数据
  • 用 -> 表示指向关系

清空链表

1
2
3
4
5
6

void destroyLinkedList(LinkedList* L) {
    clearLinkedList(L);     // 先清空数据结点
    free(L->head);          // 释放头结点
    L->head = NULL;
    printf("链表已销毁\n");
}

为什么必须释放内存？

  • 链表的内存是动态分配的（malloc）
  • 不用时要还给系统，否则会造成”内存泄漏”

栈和队列（C语言）

什么是栈？

通俗理解： 栈就像一摞盘子，你只能：

  • 把新盘子放在最上面（压栈，Push）
  • 从最上面拿走盘子（出栈，Pop）

特点：后进先出（LIFO：Last In First Out）

顺序栈

结构体定义

1
2
3
4
5
6
7
8
9
10

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

#define MAXSIZE 100  // 栈的最大容量

// 顺序栈结构体
typedef struct {
    int data[MAXSIZE];  // 存储数据的数组
    int top;            // 栈顶指针（指向栈顶元素的位置）
} SeqStack;
  • data[MAXSIZE]：和顺序表一样，数组存放数据
  • top：栈顶指针，表示当前栈顶元素在数组中的下标
  • 约定：top = -1 表示空栈
空栈：top = -1
┌────┬────┬────┬────┬────┐
│    │    │    │    │    │
└────┴────┴────┴────┴────┘
 ↑
 top=-1，没有元素

压入10、20、30后：
top = 2
┌────┬────┬────┬────┬────┐
│ 10 │ 20 │ 30 │    │    │
└────┴────┴────┴────┴────┘
  ↑    ↑    ↑
  0    1    2 ← top指向这里

初始化栈

1
2
3
4

void initStack(SeqStack* S) {
    S->top = -1;  // 栈顶指针设为-1，表示空栈
    printf("顺序栈初始化成功！\n");
}

为什么 top = -1？

  • 数组下标从0开始
  • -1 表示”没有元素”，是个无效下标
  • 压入第一个元素时，top 变成 0

判断栈空/栈满

1
2
3
4
5
6
7
8
9

// 判断栈是否为空
int isEmpty(SeqStack* S) {
    return S->top == -1;
}

// 判断栈是否已满
int isFull(SeqStack* S) {
    return S->top == MAXSIZE - 1;  // 因为下标从0开始，最大是99
}

获取栈顶元素（不弹出）

1
2
3
4
5
6
7
8

// 获取栈顶元素（只看不拿）
int getTop(SeqStack* S) {
    if (isEmpty(S)) {
        printf("栈为空，无法获取栈顶元素！\n");
        return -1;
    }
    return S->data[S->top];
}

压栈（Push）

1
2
3
4
5
6
7
8
9
10
11

// 压栈：把元素放入栈顶
void push(SeqStack* S, int value) {
    if (isFull(S)) {
        printf("栈已满，无法压入%d！\n", value);
        return;
    }
    
    S->top++;                // 栈顶指针上移
    S->data[S->top] = value; // 放入元素
    printf("成功压入：%d\n", value);
}

图解：

压入10前：top=-1（空栈）
压入10：top变成0，data[0]=10

压入20前：top=0
压入20：top变成1，data[1]=20

压入30前：top=1
压入30：top变成2，data[2]=30

最终：
data[0]=10, data[1]=20, data[2]=30, top=2

出栈（Pop）

1
2
3
4
5
6
7
8
9
10
11
12

// 出栈：弹出栈顶元素并返回
int pop(SeqStack* S) {
    if (isEmpty(S)) {
        printf("栈为空，无法出栈！\n");
        return -1;
    }
    
    int value = S->data[S->top];  // 取出栈顶元素
    S->top--;                      // 栈顶指针下移
    printf("成功弹出：%d\n", value);
    return value;
}

图解：

当前：data[0]=10, data[1]=20, data[2]=30, top=2

弹出：value = data[2]=30, top变成1
现在：data[0]=10, data[1]=20, top=1（30还在数组里，但访问不到了）

再弹出：value = data[1]=20, top变成0

打印栈（从栈底到栈顶）

1
2
3
4
5
6
7
8
9
10
11
12
13

// 打印栈（从底到顶）
void printStack(SeqStack* S) {
    if (isEmpty(S)) {
        printf("栈为空\n");
        return;
    }
    
    printf("栈内容（从底到顶）：");
    for (int i = 0; i <= S->top; i++) {
        printf("%d ", S->data[i]);
    }
    printf("(栈顶)\n");
}

链表栈

结构体定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

// 结点结构体
typedef struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域
} Node;

// 栈结构体
typedef struct {
    Node* top;   // 栈顶指针
    int size;    // 栈的大小
} LinkedStack;

图示：

栈顶(top) → [30] → [20] → [10] → NULL
             ↑
          最新加入的

初始化

1
2
3
4
5

void initStack(LinkedStack* s) {
    s->top = NULL;
    s->size = 0;
    printf("链表栈初始化成功！\n");
}

判断栈空

1
2
3

int isEmpty(LinkedStack* s) {
    return s->top == NULL;
}

创建新结点

1
2
3
4
5
6
7
8
9
10

Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

压栈（Push）

1
2
3
4
5
6
7
8
9

void push(LinkedStack* s, int value) {
    Node* newNode = createNode(value);
    
    newNode->next = s->top;  // 新结点指向当前栈顶
    s->top = newNode;        // 栈顶指向新结点
    s->size++;
    
    printf("成功压栈：%d\n", value);
}

图解：

压栈前：top → [20] → [10] → NULL

压入30：
步骤1：newNode→next = top → [30]→[20]
步骤2：top = newNode → top→[30]→[20]→[10]→NULL

出栈（Pop）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int pop(LinkedStack* s) {
    if (isEmpty(s)) {
        printf("栈为空，无法出栈！\n");
        return -1;
    }
    
    Node* temp = s->top;
    int value = temp->data;
    
    s->top = s->top->next;  // 栈顶下移
    free(temp);              // 释放原栈顶
    s->size--;
    
    printf("成功出栈：%d\n", value);
    return value;
}

图解：

出栈前：top → [30] → [20] → [10] → NULL

弹出30：
步骤1：temp = top（指向[30]）
步骤2：top = top->next（指向[20]）
步骤3：free(temp) 释放[30]

结果：top → [20] → [10] → NULL

查看栈顶元素

1
2
3
4
5
6
7

int getTop(LinkedStack* s) {
    if (isEmpty(s)) {
        printf("栈为空！\n");
        return -1;
    }
    return s->top->data;
}

获取栈的大小

1
2
3

int getSize(LinkedStack* s) {
    return s->size;
}

打印栈（从栈顶到栈底）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void printStack(LinkedStack* s) {
    if (isEmpty(s)) {
        printf("栈为空\n");
        return;
    }
    
    printf("栈内容（顶→底）：");
    Node* p = s->top;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("(栈底)\n");
    printf("栈大小：%d\n", s->size);
}

清空栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void clearStack(LinkedStack* s) {
    Node* p = s->top;
    Node* temp;
    
    while (p != NULL) {
        temp = p;
        p = p->next;
        free(temp);
    }
    
    s->top = NULL;
    s->size = 0;
    printf("栈已清空\n");
}

顺序循环队列

什么是队列？

通俗理解： 队列就像排队买票：

  • 新来的人站在队尾（入队）
  • 最前面的人先买到票离开（出队）

特点：先进先出（FIFO：First In First Out）

什么是循环队列？

用数组实现队列时，出队后前面的位置就空出来了，但无法重复使用，造成”假溢出”。

普通队列：
[10] [20] [30] [ ] [ ] 
 ↑                  ↑
队头                队尾

出队10后：
[ ] [20] [30] [ ] [ ]
 ↑                 ↑
队头               队尾

再入队40：
[ ] [20] [30] [40] [ ]
 ↑                  ↑
队头                队尾

现在队尾到末尾了，但前面还有空位不能用！这就是假溢出。

把数组想象成一个圆环，队尾到末尾后可以绕回开头，重复利用空间。

结构体定义

1
2
3
4
5
6
7
8
9
10
11

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

#define MAXSIZE 5  // 队列最大容量（实际只能存4个，因为要空一个位置判断满）

// 循环队列结构体
typedef struct {
    int data[MAXSIZE];  // 存储数据的数组
    int front;          // 队头指针（指向队头元素的位置）
    int rear;           // 队尾指针（指向队尾元素的下一个位置）
} CirQueue;
  • front：指向队头元素的位置
  • rear：指向队尾元素的下一个位置（空位置）
  • 队列空：front == rear
  • 队列满：(rear + 1) % MAXSIZE == front（留一个空位判断满）

为什么要留一个空位？ 如果不留空位，队列满时 front == rear 和队列空时一样，无法区分。

初始化队列

1
2
3
4
5

void initQueue(CirQueue* Q) {
    Q->front = 0;
    Q->rear = 0;
    printf("循环队列初始化成功！\n");
}
  • front = 0, rear = 0，表示队列为空
  • 注意：不是 -1，因为要用取模运算

判断队列空/满

1
2
3
4
5
6
7
8
9

// 判断队列是否为空
int isEmpty(CirQueue* Q) {
    return Q->front == Q->rear;
}

// 判断队列是否已满
int isFull(CirQueue* Q) {
    return (Q->rear + 1) % MAXSIZE == Q->front;
}

图解满队列（MAXSIZE=5）：

队列满时，rear后面刚好是front：
       front=0
        ↓
       [ ] [20] [30] [40] [50]
        ↑              ↑
       rear=4?        不对
       
实际满时：rear=4, front=0
(4+1)%5 = 0 == front，所以满
数据：[10] [20] [30] [40]，一个空位
      ↑               ↑
    front=0         rear=4

六、获取队列长度

1
2
3
4

// 获取队列长度
int getLength(CirQueue* Q) {
    return (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
}
  • 普通队列：rear - front
  • 循环队列：因为可能绕圈，所以 (rear - front + MAXSIZE) % MAXSIZE

举例：

情况1：rear=3, front=0，长度 = (3-0+5)%5 = 3
情况2：rear=2, front=4（绕圈了），长度 = (2-4+5)%5 = 3

七、入队（EnQueue）

1
2
3
4
5
6
7
8
9
10
11

// 入队：在队尾添加元素
void enQueue(CirQueue* Q, int value) {
    if (isFull(Q)) {
        printf("队列已满，无法入队%d！\n", value);
        return;
    }
    
    Q->data[Q->rear] = value;      // 在rear位置放入元素
    Q->rear = (Q->rear + 1) % MAXSIZE;  // rear后移一位（循环）
    printf("成功入队：%d\n", value);
}

图解：

初始空队列：front=0, rear=0
        ┌───┬───┬───┬───┬───┐
        │   │   │   │   │   │
        └───┴───┴───┴───┴───┘
          ↑
          f/r

入队10：data[0]=10, rear=1
        ┌───┬───┬───┬───┬───┐
        │10 │   │   │   │   │
        └───┴───┴───┴───┴───┘
          ↑   ↑
          f   r

入队20：data[1]=20, rear=2
        ┌───┬───┬───┬───┬───┐
        │10 │20 │   │   │   │
        └───┴───┴───┴───┴───┘
          ↑       ↑
          f       r

八、出队（DeQueue）

1
2
3
4
5
6
7
8
9
10
11
12

// 出队：从队头取出元素
int deQueue(CirQueue* Q) {
    if (isEmpty(Q)) {
        printf("队列为空，无法出队！\n");
        return -1;
    }
    
    int value = Q->data[Q->front];  // 取出队头元素
    Q->front = (Q->front + 1) % MAXSIZE;  // front后移一位（循环）
    printf("成功出队：%d\n", value);
    return value;
}

图解：

当前队列：front=0, rear=2
        ┌───┬───┬───┬───┬───┐
        │10 │20 │   │   │   │
        └───┴───┴───┴───┴───┘
          ↑       ↑
          f       r

出队：取出data[0]=10，front=1
        ┌───┬───┬───┬───┬───┐
        │10 │20 │   │   │   │
        └───┴───┴───┴───┴───┘
          ↑   ↑
          f   r

再出队：取出data[1]=20，front=2
        ┌───┬───┬───┬───┬───┐
        │10 │20 │   │   │   │
        └───┴───┴───┴───┴───┘
              ↑
              f/r（队列空）

获取队头元素（不弹出）

1
2
3
4
5
6
7

int getFront(CirQueue* Q) {
    if (isEmpty(Q)) {
        printf("队列为空！\n");
        return -1;
    }
    return Q->data[Q->front];
}

打印队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void printQueue(CirQueue* Q) {
    if (isEmpty(Q)) {
        printf("队列为空\n");
        return;
    }
    
    printf("队列内容（队头→队尾）：");
    int i = Q->front;
    while (i != Q->rear) {
        printf("%d ", Q->data[i]);
        i = (i + 1) % MAXSIZE;
    }
    printf("\n");
}

清空队列

1
2
3
4
5
6
7
8
9
10

void clearQueue(CirQueue* Q) {
    int i = Q->front;
    while (i != Q->rear) {
        Q->data[i] = 0;  // 数据清零
        i = (i + 1) % MAXSIZE;
    }
    Q->front = 0;
    Q->rear = 0;
    printf("队列已清空（数据已清零）\n");
}

链表循环队列

什么是链式循环队列？

通俗理解：

  • 用链表实现的队列，队尾的 next 指向队头，形成一个圆环
  • 和顺序循环队列不同：没有”假溢出”，不需要留空位
  • 可以无限添加（只要内存够）

图示：

普通链式队列（不循环）：
head → [10] → [20] → [30] → NULL
        ↑              ↑
      队头            队尾

链式循环队列：
        ┌─────────────────┐
        ↓                 │
head → [10] → [20] → [30] ┘
        ↑              ↑
      队头            队尾
      
最后一个结点的next指向第一个结点

结构体定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

// 结点结构体
typedef struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域
} Node;

// 链式循环队列结构体
typedef struct {
    Node* front;   // 队头指针（指向队头结点）
    Node* rear;    // 队尾指针（指向队尾结点）
    int length;    // 队列长度（元素个数）
} LinkedCircularQueue;

解释：

  • front：指向队头结点（第一个元素）
  • rear：指向队尾结点（最后一个元素）
  • length：记录元素个数
  • 空队列：front = NULL, rear = NULL, length = 0
  • 循环：rear->next = front

初始化

1
2
3
4
5
6
7

// 初始化队列
void initQueue(LinkedCircularQueue* Q) {
    Q->front = NULL;
    Q->rear = NULL;
    Q->length = 0;
    printf("链式循环队列初始化成功！\n");
}

图解：

初始化后：
front = NULL
rear = NULL
没有结点

判断空/满

1
2
3
4
5
6
7
8
9
10

// 判断是否为空
int isEmpty(LinkedCircularQueue* Q) {
    return Q->length == 0;
    // 或者 return Q->front == NULL;
}

// 链式队列没有"满"的概念（除非内存不够）
int isFull(LinkedCircularQueue* Q) {
    return 0;  // 永远不满
}

创建新结点

1
2
3
4
5
6
7
8
9
10
11

// 创建新结点
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

入队（EnQueue）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// 入队：在队尾添加元素
void enQueue(LinkedCircularQueue* Q, int value) {
    Node* newNode = createNode(value);
    
    if (isEmpty(Q)) {
        // 空队列：新结点既是头也是尾
        Q->front = newNode;
        Q->rear = newNode;
        newNode->next = newNode;  // 指向自己，形成循环
    } else {
        // 非空队列：新结点插在队尾后面
        newNode->next = Q->front;   // 新结点指向队头
        Q->rear->next = newNode;    // 原队尾指向新结点
        Q->rear = newNode;          // 更新队尾
    }
    
    Q->length++;
    printf("成功入队：%d\n", value);
}

图解：

第1步：入队10（空队列）
newNode = [10]
front → [10] ← rear
         ↑  │
         └──┘ (next指向自己)

第2步：入队20
创建 [20]
newNode->next = front → [20]→[10]
rear->next = newNode → [10]→[20]
rear = newNode → rear指向[20]

结果：
front → [10] → [20] ← rear
         ↑      │
         └──────┘ (20的next指向10)

第3步：入队30
front → [10] → [20] → [30] ← rear
         ↑              │
         └──────────────┘ (30的next指向10)

出队（DeQueue）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 出队：从队头取出元素
int deQueue(LinkedCircularQueue* Q) {
    if (isEmpty(Q)) {
        printf("队列为空，无法出队！\n");
        return -1;
    }
    
    Node* temp = Q->front;
    int value = temp->data;
    
    if (Q->length == 1) {
        // 只有一个结点：删除后队列变空
        Q->front = NULL;
        Q->rear = NULL;
    } else {
        // 多个结点：队头后移
        Q->front = Q->front->next;   // 新队头
        Q->rear->next = Q->front;    // 队尾指向新队头（保持循环）
    }
    
    free(temp);
    Q->length--;
    printf("成功出队：%d\n", value);
    return value;
}

图解：

出队前（3个结点）：
front → [10] → [20] → [30] ← rear
         ↑              │
         └──────────────┘

删除10：
temp = [10]
Q->front = [20]
Q->rear->next = [20]（让[30]的next指向[20]）

出队后：
front → [20] → [30] ← rear
         ↑      │
         └──────┘

获取队头元素

1
2
3
4
5
6
7
8

// 获取队头元素（不弹出）
int getFront(LinkedCircularQueue* Q) {
    if (isEmpty(Q)) {
        printf("队列为空！\n");
        return -1;
    }
    return Q->front->data;
}

获取队列长度

1
2
3
4

// 获取队列长度
int getLength(LinkedCircularQueue* Q) {
    return Q->length;
}

打印队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 打印队列（从队头到队尾）
void printQueue(LinkedCircularQueue* Q) {
    if (isEmpty(Q)) {
        printf("队列为空\n");
        return;
    }
    
    printf("队列内容（队头→队尾）：");
    Node* p = Q->front;
    for (int i = 0; i < Q->length; i++) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("(循环回到队头)\n");
    printf("队头：%d，队尾：%d，长度：%d\n", 
           Q->front->data, Q->rear->data, Q->length);
}

注意：不能直接用 while (p != Q->front) 判断结束，因为循环队列永远走不完。要用 length 控制。

销毁队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// 销毁队列（释放所有结点）
void destroyQueue(LinkedCircularQueue* Q) {
    if (isEmpty(Q)) {
        printf("队列已空\n");
        return;
    }
    
    Node* p = Q->front;
    Node* temp;
    
    for (int i = 0; i < Q->length; i++) {
        temp = p;
        p = p->next;
        free(temp);
    }
    
    Q->front = NULL;
    Q->rear = NULL;
    Q->length = 0;
    printf("队列已销毁\n");
}

线性表（STL）

STL是什么？

STL = Standard Template Library（标准模板库），是C++自带的一套”现成的工具”，里面有很多常用的数据结构，比如：

  • vector：动态数组（类似顺序表）
  • list：双向链表（类似链表）

优点：不用自己写，直接用，代码更简单、更安全。

vector（顺序表/动态数组）

头文件

1

#include <vector>

常用操作

操作 代码 说明
定义 vector<int> v; 创建一个空的整型vector
末尾添加 v.push_back(10); 在末尾加元素
插入 v.insert(v.begin()+2, 25); 在第3个位置插入25
删除 v.erase(v.begin()+1); 删除第2个元素
按位置访问 int x = v[2]; 获取第3个元素
获取长度 int len = v.size(); 当前元素个数
判断空 v.empty(); 空返回true
清空 v.clear(); 删除所有元素
遍历 for(int x : v) cout << x << " "; 打印所有元素

list（双向链表）

头文件

1

#include <list>

常用操作

操作 代码 说明
定义 list<int> L; 创建一个空的整型链表
末尾添加 L.push_back(10); 尾插法
头部添加 L.push_front(5); 头插法
末尾删除 L.pop_back(); 删除最后一个
头部删除 L.pop_front(); 删除第一个
插入 L.insert(it, 25); 在迭代器位置插入
删除 L.erase(it); 删除迭代器位置的元素
获取长度 int len = L.size(); 当前元素个数
判断空 L.empty(); 空返回true
清空 L.clear(); 删除所有元素
遍历 for(int x : L) cout << x << " "; 打印所有元素

vector vs list 对比

操作 vector list
随机访问（下标） ✅ v[3] ❌ 不支持
头部插入/删除 ❌ 慢 ✅ push_front/pop_front
尾部插入/删除 ✅ push_back/pop_back ✅ push_back/pop_back
中间插入/删除 ❌ 慢（O(n)） ✅ 快（O(1)）
内存 连续 不连续

栈和队列（STL）

stack（栈）

头文件

1

#include <stack>

特点

  • 后进先出（LIFO）
  • 只能从顶部操作

常用操作

操作 代码 说明
定义 stack<int> s; 创建一个空栈
压栈 s.push(10); 放入元素
出栈 s.pop(); 移除顶部元素（不返回）
查看栈顶 s.top(); 返回顶部元素
判断空 s.empty(); 空返回true
获取大小 s.size(); 返回元素个数

queue（队列）

头文件

1

#include <queue>

特点

  • 先进先出（FIFO）
  • 队尾入队，队头出队

常用操作

操作 代码 说明
定义 queue<int> q; 创建一个空队列
入队 q.push(10); 队尾添加元素
出队 q.pop(); 移除队头元素（不返回）
查看队头 q.front(); 返回队头元素
查看队尾 q.back(); 返回队尾元素
判断空 q.empty(); 空返回true
获取大小 q.size(); 返回元素个数

注意事项

1. pop() 不返回值

1
2
3
4
5
6

// 错误写法
int x = s.pop();  // ❌ 编译错误

// 正确写法
int x = s.top();  // 先获取
s.pop();          // 再删除

2. 使用前要判空

1
2
3

if (!s.empty()) {
    cout << s.top() << endl;
}

3. 遍历方式

stack 和 queue 没有迭代器，不能这样遍历：

1
2
3
4
5
6
7
8

// ❌ 错误
for (auto it = s.begin(); it != s.end(); it++) 

// ✅ 正确：只能边pop边遍历
while (!s.empty()) {
    cout << s.top() << " ";
    s.pop();
}
CATALOG
    FRIENDS