1
2
3
4
5

typedef struct{
    int * head; //定义一个名为head的长度不确定的数组，也叫“动态数组”
    int length; //记录当前顺序表的长度
    int size; //记录顺序表的存储容量
}Table;

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <stdio.h>
#include <stdlib.h>
#define Size 5 //对Size进行宏定义，表示顺序表的最大容量
typedef struct{
    int* head;
    int length;
    int size;
}Table;
void initTable(Table * t) {
    //构造一个空的顺序表，动态申请存储空间
    t->head = (int*)malloc(Size * sizeof(int));
    //如果申请失败，作出提示并直接退出程序
    if (!t->head)
    {
        printf("初始化失败");
        exit(0);
    }
    //空表的长度初始化为0
    t->length = 0;
    //空表的初始存储空间为Size
    t->size = Size;
}
//输出顺序表中元素的函数
void displayTable(Table t) {
    int i;
    for (i = 0; i < t.length; i++) {
        printf("%d ", t.head[i]);
    }
    printf("\n");
}
int main() {
    int i;
    Table t = { NULL,0,0 };
    initTable(&t);
    //向顺序表中添加{1,2,3,4,5}
    for (i = 1; i <= Size; i++) {
        t.head[i - 1] = i;
        t.length++;
    }
    printf("顺序表中存储的元素分别是：\n");
    displayTable(t);
    free(t.head);//释放申请的堆内存
    return 0;
}

1
2

顺序表中存储的元素分别是：
1 2 3 4 5 

1

phead->phead[1|p2]->p2[2|p3]->p3[3|p4]->p4[4|end]

1
2
3
4
5
6
7

//单链表节点定义
struct Node {
    int data;      // 数据域
    Node* next;    // 指针域
    Node(int x) : data(x), next(nullptr) {}   // 构造函数
};

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

//双链表的定义
template <class elemType>
struct Node {
    elemType data;
    Node *prior, *next;
    Node (const elemType &value,Node *p = NULL,Node *n = NULL){
        data = value;
        prior = p;
        next = n;
    }
    Node():next(NULL),prior(NULL){}
    ~Node(){}
};

1
2
3
4
5

//循环列表的定义
typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指向下一个结点
} Node;

1
2
3
4
5
6
7
8

//最基础的 依数组实现的顺序栈
#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];  // 存放元素
    int top;            // 栈顶指针（指向栈顶元素下标）
} Stack;

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

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

typedef struct {
    Node *top;   // 栈顶
    int length;  // 可选
} LinkStack;
//初始化
LinkStack s;
s.top = NULL;
s.length = 0;

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

#include <queue>
#include <iostream>

// 基本队列定义
std::queue<int> intQueue;           // 存储int类型的队列
std::queue<double> doubleQueue;     // 存储double类型的队列
std::queue<std::string> stringQueue; // 存储string类型的队列

// 自定义类型的队列
struct Person {
    std::string name;
    int age;
};

std::queue<Person> personQueue;

1
2
3
4
5
6
7
8
9
10
11

#include <cstring>
#include <iostream>

// 字符数组形式
char str1[] = "Hello";           // 自动计算长度，包含'\0'
char str2[6] = {'H', 'e', 'l', 'l', 'o', '\0'}; // 显式指定长度和结束符
char str3[] = {'H', 'i'};         // 不是字符串，没有'\0'

// 指针形式
char* str4 = "World";             // 指向常量字符串的指针
char* str5 = new char[10];        // 动态分配

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

//主串的每一个字符与子串的开头进行匹配，匹配成功则比较子串与主串的下一位是否匹配，匹配失败则比较子串与主串的下一位，很显然，我们可以使用两个指针来分别指向主串和子串的某个字符，来实现这样一种算法

//匹配成功，返回子串在主串中第一次出现的位置，匹配失败返回 -1，子串是空串返回 0

 int String::bfFind(const String &s, int pos) const {
     //主串和子串的指针，i主串，j子串
     int i, j;
     //主串比子串小，匹配失败，curLenght为串的长度
     if (curLength < s.curLenght)
         return -1;
     
     while (i < curLength && j < s.curLength) {
         //对应字符相等，指针后移
         if (data[i] == s.data[j])
             i+, j++;
         else {  //对应字符不相等
             i = i -j + 1;   //主串指针移动
             j = 0; //子串从头开始
         }
         //返回子串在主串的位置
         if (j >= s.curLength) 
             return (i - s.curLength);
         else return -1;    
     }
 }

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

求next数组算法实现
 void Stirng::getNext(const String &t, int *next) {
     int i = 0, j = -1;
     next[0] = -1;
     while (i < t.curLength - 1) {
         if ((j == -1) || t[i] == t[j]) {
             ++i, ++j;
             next[i] = j;
         }else{
             j = next[j];
         }
     }
 }

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

int String::kmpFind(const String &t, int pos) {
    //不允许申请大小为0的数组
    if (t,curLength == 0) return 0;
    //如果主串比子串小，匹配失败
    if(t.curLength < t.curLength) return -1;
    //主串指针i，子串指针j
    int i = 0, j = 0;
    int *next = new int[t.curLrngth];
    getNext(t,next);
    while (i < curLength && j < t,curLength) {
        if (j == -1 || data[i] == t.data[j])    //情况12
            i++, j++;
        else    //情况3
            j = next[j];
    }
    delete []next;
    if (j > t.curLength)
        return (i - t.curLength)
    else
        return -1;
}

1
2
3
4
5

    1
   / \
  2   3
 / \  / \
4  5  6  7 

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

(1)树(Tree)是由n(n≥0)个结点构成的有限集合T 若T=0 则称为空树; 否则 一个非空树需要满足以下两个条件
① 有且只有一个特定的 称为根(Root)的结点
② 除根节点以外的其他结点被分成m(m≥0)个互不相交的有限集合T1,T2,...,Tm,其中每个集合又是一棵树 这些树称为子树
(2)结点(Node)包含数据项及指向其他结点的分支
(3)结点的度表示结点所拥有的子树的数目
(4)叶结点 也叫终端结点 指度为0的结点 叶结点没有后续
(5)分支结点 也叫非终端结点 指度不为0的结点 也就是除叶结点以外的结点
(6)结点的层次 结点头上有n道杠就是n+1层的结点
(7)儿子 爸爸 兄弟 堂兄弟 祖先 子孙结点
儿子：一个节点的直接下级节点，该节点是其父节点。
爸爸：一个节点的直接上级节点，该节点是其子节点的父节点。
兄弟：拥有同一个父节点的两个或多个节点，它们之间互为兄弟。
堂兄弟：在同一层且父节点互为兄弟的两个节点，它们之间互为堂兄弟。
祖先：从根节点到当前节点路径上的所有节点，都称为该节点的祖先。
子孙结点：以某个节点为根的子树中所包含的所有节点，都称为该节点的子孙结点。
(8)树的高度/深度:树中结点的最大层次
(9)有序/无序树:一个树的次序是否重要/可否进行交换决定了其有序性
(10)森林:m(m≥0)个不相交的树的集合称为森林

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

        1  
       / \
      2   3
     / \  / \
    4  5  6  7

1. 前序遍历
规则：根 → 左 → 右
1. 从根 1 开始，访问 1  
2. 进入左子树 2（根为 2）  
   • 访问 2  
   • 进入左子树 4（根为 4）  
     ◦ 访问 4（无左右孩子，返回）  
   • 回到 2，进入右子树 5（根为 5）  
     ◦ 访问 5（无左右孩子，返回）  
3. 回到 1，进入右子树 3（根为 3）  
   • 访问 3  
   • 进入左子树 6（根为 6）  
     ◦ 访问 6（无左右孩子，返回）  
   • 回到 3，进入右子树 7（根为 7）  
     ◦ 访问 7（无左右孩子，返回）  
前序遍历结果：  
1 → 2 → 4 → 5 → 3 → 6 → 7

2. 中序遍历
规则：左 → 根 → 右
1. 从根 1 开始，先遍历左子树 2  
   • 对 2 先遍历它的左子树 4  
     ◦ 4 无左孩子，访问 4  
     ◦ 回到 2（根），访问 2  
     ◦ 遍历 2 的右子树 5  
       ◦ 5 无左孩子，访问 5  
2. 回到 1，访问 1  
3. 遍历 1 的右子树 3  
   • 对 3 先遍历它的左子树 6  
     ◦ 6 无左孩子，访问 6  
     ◦ 回到 3（根），访问 3  
     ◦ 遍历 3 的右子树 7  
       ◦ 7 无左孩子，访问 7  
中序遍历结果：  
4 → 2 → 5 → 1 → 6 → 3 → 7

3. 后序遍历
规则：左 → 右 → 根
1. 从根 1 开始，先遍历左子树 2  
   • 对 2 先遍历它的左子树 4  
     ◦ 4 无左右孩子，访问 4  
   • 遍历 2 的右子树 5  
     ◦ 5 无左右孩子，访问 5  
   • 回到 2，访问 2  
2. 回到 1，遍历右子树 3  
   • 对 3 先遍历它的左子树 6  
     ◦ 6 无左右孩子，访问 6  
   • 遍历 3 的右子树 7  
     ◦ 7 无左右孩子，访问 7  
   • 回到 3，访问 3  
3. 回到 1，访问 1  
后序遍历结果：  
4 → 5 → 2 → 6 → 7 → 3 → 1

4. 层次遍历
规则：按层从左到右
• 第 1 层：1  
• 第 2 层：2, 3  
• 第 3 层：4, 5, 6, 7  
层次遍历结果：  
1 → 2 → 3 → 4 → 5 → 6 → 7

最终答案：
• 前序：1, 2, 4, 5, 3, 6, 7  
• 中序：4, 2, 5, 1, 6, 3, 7  
• 后序：4, 5, 2, 6, 7, 3, 1  
• 层次：1, 2, 3, 4, 5, 6, 7

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

         (136)
        /     \
    (64)       (72)
   /    \      /    \
G29    (35)  F31    (41)
       /  \          /  \
    C17   H18      (18)  A23
                   /  \
                (9)    E9
               /   \
            D4      B5

1
2
3
4
5
6
7

        A
       / \
      B   C
     / \   \
    D   E   F
中序遍历后
D → B → E → A → C → F

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

struct

typedef

malloc

变量前面加上()

->next

insert

如何遍历创建出来的结构

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

// 定义结构体
struct Student {
    int id;
    string name;
    float score;
};

// 使用结构体
Student s1;           // 声明变量
s1.id = 1001;
s1.name = "张三";
s1.score = 95.5;

// 也可以在定义时初始化
Student s2 = {1002, "李四", 88.0};

1
2
3
4
5
6
7
8
9
10

// 定义结构体并同时声明变量
struct Student {
    int id;
    string name;
    float score;
} student1, student2;  // 这里声明了两个Student类型的变量

// 使用
student1.id = 1001;
student2.id = 1002;

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

// 为基本类型创建别名
typedef int Integer;
Integer age = 25;

// 为结构体创建别名
typedef struct Node {
    int data;
    Node* next;
} Node, *LinkList;  // Node是结构体类型，LinkList是指向Node的指针类型

// C++11之后更推荐使用using
using String = std::string;
String myStr = "Hello";