南的个人博客

遇事不决，但问春风

数据结构复习

发表于 更新于 分类于
数据结构部分代码的实现

王道书中错误地方

微信图片_20230524101557

线性表

顺序表

由于想省事，所以顺序表的数据都是固定的

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <algorithm>

using namespace std;


// 定义顺序表的初始长度
#define InitSize  100

// 定义顺序表的结构体
typedef struct
{
    int *data ; // 动态分配数组 ， 指针指向顺序表中的第一个元素
    int MaxSize; // 顺序表的最大容量
    int length; //顺序表的长度
} Sqlist;

// 初始化顺序表
void InitList(Sqlist &L){
    // 使用malloc函数动态分配数据空间
    L.data = (int *)malloc(sizeof(int)*InitSize);
    L.length = 0;
    L.MaxSize = InitSize;
}

// 插入顺序表元素    i表示在第几位插入  e 表示插入的数值
bool InsertList(Sqlist &L , int i , int e){
    // 判断i的范围
    if(i < 1 || i > L.length+1) 
        return false; 
    // 对顺序表的长度进行判断
    if(L.length >= L.MaxSize )
        return false;
    // 将第i位元素后面的树都向后移动一位
    for(int j = L.length - 1; j >= i ;j --){
        L.data[j] = L.data[j-1];
    }
    L.data[i-1] = e;
    L.length ++;
    return true;
}

// 删除顺序表的第i位操作
bool deleteList(Sqlist &L , int i){
    // 判断i的范围
    if(i < 1 || i > L.length) 
        return false; 
    
    for(int j = i - 1 ; j < L.length - 1;j ++){
        L.data[j] = L.data[j+1];
    }
    L.length --;
    return true;
}

// 按值查找
int locateElem(Sqlist L , int e){
    for(int i = 0;i < L.length ;i ++){
        if(L.data[i] ==  e){
            return i + 1;
        }
    }

    return -1; // 说明查找失败，没有这个数
}

// 按位查找
int locateIt(Sqlist L , int i){
    // 判断i的范围
    if(i < 1 || i > L.length) 
        return -2;  // i不在范围返回-2
    else return L.data[i-1];
    
    return -1; // 查找失败
}

//  显示菜单
void show(){
    cout << "请输入序号获取操作：" << endl;
    cout << "1 . 插入元素 "<<endl;
    cout << "2 . 删除元素 "<<endl;
    cout << "3 . 按值查找 "<<endl;
    cout << "4 . 按位查找 "<<endl;
    cout << "5 . 退出 "<<endl;
}

int main(){
    Sqlist L;
    InitList(L);
    show();
    int a ; 
    while(cin >> a){
        if(a == 5) return 0;
        else if(a == 1){
            bool l = InsertList(L,1,3);
            cout << l << endl;
        }
        else if(a == 2) {
            bool l = deleteList(L,1);
            cout << l << endl;
        }
        else if(a == 3){
            int h = locateElem(L,3);
            cout << h << endl;
        }
        else if(a == 4) {
            int h = locateIt(L,1);
            cout << h << endl;
        }
    }
    return 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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
#include <iostream>
#include <algorithm>

using namespace std;

typedef struct LNode //定义单链表的结构类型
{
    int data;  // 每个节点存放一个数据元素
    struct LNode *next;  // 指针指向下一个节点
}LNode, *LinkList;

// 初始化
bool InitList(LinkList &L){

    /**
     * 不带头节点
     * L = NULL;
     * return true;
    */

    L = (LNode *) malloc(sizeof(LNode)); // 分配一个头节点
    if(L == NULL)
        return false;  // 内存不足，分配失败
    L -> next = NULL;  //带有头结点的单链表
    return true;
}

//判断单链表是否为空
bool Empty(LinkList L){
    if(L -> next == NULL){
        return true;
    }else 
        return false;
}

//使用头插法建立单链表
LinkList List_headInsert(LinkList &L){
    int x;
    LNode *s ;
    L = (LNode *) malloc(sizeof(LNode));
    L -> next = NULL;  // 这个很重要，如果不对L进行重新赋值，容易造成冲突，报错 "Segmentation fault"
    cin >> x;
    while(x != 999)
    {
        s = (LNode *) malloc(sizeof(LNode)); // 重新对s进行建立节点
        s -> data = x;
        s -> next = L -> next;
        L -> next = s;
        cin >> x;
    }

    return L ;
}

// 使用尾插法建立单链表
LinkList List_TailInsert(LinkList &L){
    int x ;
    L = (LNode *)malloc(sizeof(LNode)); // 建立头节点
    LNode *s , *r = L; // r为表尾指针
    cin >> x;
    while(x != 999){
        s = (LNode *) malloc(sizeof(LNode)); // 重新对s进行建立节点
        s -> data = x;  // 将x赋给s节点
        r -> next = s; // 在表尾后插入一个元素
        r = s;         // 将r指针指向最后一个元素
        cin >> x;  // 接着输入x
    }

    r -> next = NULL;
    return L;
}

// 在第i个位置插入元素（带头节点）
bool ListInsert(LinkList &L, int i , int e){
    if(i < 1)
        return false;
    /**
     * 如果不带头节点需要对在第一个位置插入进行特殊处理
     * if(i == 1){
     *      LNode *s = (LNode *)malloc(sizeof(LNode));
     *      s -> data = x;
     *      s -> next = L;
     *      L  = s;
     *      return true;
     * }
    */
    LNode *p ; // 指针p指向当前扫描到的节点 等价于 LinkList p
    int j = 0; // 当前p指向的是第几个节点
    p = L; // p指向头节点
    while(p != NULL && j < i - 1){ // 找到第i-1个节点，并在其后面插入一个元素，
        p = p -> next;
        j ++;
    }
    if(p == NULL)
        return false;  // i值不合理

    LNode *s = (LNode *)malloc(sizeof(LNode)); // 分配一个节点
    if(s == NULL)
        return false;  // 分配内存失败

    s -> data = e;
    s -> next = p -> next ;
    p -> next = s;

    return true;
}

// 在p节点后插入元素
bool InsertNextNode(LNode *p , int e){
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s == NULL)
        return false;  // 分配内存失败
    s -> data = e;
    s -> next = p -> next;
    p -> next = s;

    return true;
}   

// 在p节点前插入元素
bool InsertPriorNode(LNode *p , int e){
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s == NULL)
        return false; // 分配内存失败

    /**
     * 如果遍历获得p的前驱节点时间复杂度是 O（n）
     * 但是我们可以先将s插入p的后面，然后交换s与p节点的值，即实现了前插操作
    */
    s -> next = p -> next;
    p -> next = s;
    s -> data = p -> data;
    p -> data = e;

    return true;
}

//  按位删除  第i位删除同时将其值赋给 元素e
bool deleteList(LinkList &L , int i , int &e){
    if(i < 1)
        return false; // i不合法
    LNode *p = L; //指针p指向当前扫描到的节点 等价于 LinkList p
    int j = 0 ;
    while(p != NULL && j < i - 1){
        p = p -> next;
        j ++;
    }

    if(p == NULL)
        return false;

    if(p -> next == NULL)
        return false;

    LNode * q = p -> next; // q节点指向要被删除的第i个节点
    p -> next = q -> next;
    e = q -> data;
    free(q); // 释放q
    
    return true;
}

// 指定节点的删除
bool deleteListNode(LNode *p ){
    if(p == NULL)
        return false;

    /**
     *  如果直接去寻找p的前驱，要从头开始遍历
     *  所以我们可以将p节点和p的后续节点进行调换
     *  然后删除p的后续节点 从而实现删除p节点的操作
    */
    LNode *q = p -> next; // q指向 p 的下一个节点
    p -> data = q -> data; // 将p的值替换为q的值
    p -> next = q -> next; // 将 q节点从链表中断开
    free(q);

    return true;
}

// 展示单链表中所有元素
void showNodes(LinkList L){
    LNode *p = L;
    while (p ->next != NULL)
    {
        p = p -> next;
        int t = p -> data;
        cout << t << " "<< endl;
    }
    
    cout << endl;
}
// 展示所有的单链表选项
void show(){
    cout << "请选择不同的操作："<< endl;
    cout << "1. 判断单链表是否为空"<<endl;
    cout << "2. 使用头插法建立单链表(输入999停止向链表注入数据)"<<endl;
    cout << "3. 使用尾插法建立单链表(输入999停止向链表注入数据)"<<endl;
    cout << "4. 在单链表第i个位置插入元素"<<endl;
    cout << "5. 在p节点后插入元素"<<endl;
    cout << "6. 在p节点前插入元素"<<endl;
    cout << "7. 删除单链表第i个位置的元素"<<endl;
    cout << "8. 删除节点p"<<endl;
    cout << "9. 展示单链表中的所有元素"<<endl;
    cout << "0. 退出" << endl;
}

// 调用上述所有方法
void useList(int u , LinkList &L ){
    if(u == 0){
        
    }else if( u == 1){
        bool flag = Empty(L);
        if(flag) cout << "链表为空";
        else cout << "链表不为空";
    }else if( u == 2){
        LinkList t = List_headInsert(L);
        cout << "链表内元素为："<<endl;
        showNodes(t);
    }else if(u == 3){
        LinkList t = List_TailInsert(L);
        cout << "链表内元素为："<< endl;
        showNodes(t);
    }else if(u == 4){
        int i, e;
        cout << "请输入要插入的位置以及元素数："<< endl;
        cin >> i >> e;
        bool flag = ListInsert(L,i,e);
        if(flag) cout << "插入成功"<< endl;
        else cout << "插入失败"<< endl;
    }else if(u == 7){
        int i ,e;
        cout << "请输入要删除元素的位置：" << endl;
        cin >> i;
        bool flag = deleteList(L,i,e);
        if(flag){
            cout << "删除成功,删除的元素为：" << e << endl; 
        }else cout << "删除失败" << endl;
    }else if(u == 9){
        showNodes(L);
    }

}
int main(){

    LinkList L;
    InitList(L);
    show();
    int u ;
    while(cin >> u){
        if( u == 0){
            return 0;
        }else useList(u,L);
    }
    system("pause");
    return 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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <algorithm>

using namespace std;

// 定义双链表结构体
typedef struct DNode{
    int data;
    struct DNode * next , * prior;
}DNode , *DLinkList;

// 初始化
bool InitDList(DLinkList &L){
    L = (DNode *) malloc (sizeof(DNode)); // 分配一个节点作为头节点

    if(L == NULL)
        return false;

    L -> next = NULL;
    L -> prior = NULL;  // 头结点的前驱节点永远为 NULL

    return true;
}

//  判断双链表是否为空
bool Empty(DLinkList L){
    if(L -> next == NULL) 
        return true;
    else 
        return false;
}

//  在p节点后插入s节点
bool InsertNextNode(DNode *p , DNode *s){
    s -> next = p -> next;
    s -> prior = p;
    if(p -> next != NULL)
        p -> next -> prior = s;
    p -> next = s;

    return true;
}

// 双链表的删除(删除p节点的后续节点)
bool DeleteNode(DNode *p){
    if(p == NULL)
        return false;

    DNode *q = p -> next;
    if(q == NULL) return false;  // p节点没有后继节点

    p -> next = q -> next ;
    if(q -> next != NULL){  // 如果q节点存在后继节点
        q -> next -> prior = p;
    }

    free(q);

    return true;
}

// 双链表的销毁操作
void DestroryList(DLinkList &L){
    while(L -> next != NULL)
        DeleteNode(L);
    
    free(L); // 释放头节点

    L = NULL ; // 头指针指向NULL
}

/*
    双链表的遍历操作：

    后向遍历
    while(p != NULL)
        p -> next;

    前向遍历
    while(p != NULL){
        p = p -> prior;
    }

    前向遍历（跳过头节点）
    while(p -> prior != NULL){
        p = p -> prior
    }

*/

int main(){


    return 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
#include <iostream>
#include <algorithm>

using namespace std;

// 定义循环单链表结构体 与 单链表结构体一样
typedef struct LNode{
    int data;
    struct LNode * next;
}LNode , * LinkList;

// 初始化
bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode)); // 分配一个头节点
    if(L == NULL) 
        return false;
    L -> next = L;  
    return true;
}

// 判断循环单链表是否为空
bool Empty(LinkList L){
    if(L -> next == L)
        return true;
    
    return false;
}

// 判断节点p是否为循环单链表的最后一个节点
bool isTail(LinkList L , LNode *p ){
    if(p -> next == L)
        return true;

    return false;
}



int main(){

    return 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
#include <iostream>
#include <algorithm>

using namespace std;

//  定义循环双链表的结构体
typedef struct DNode{
    int data;
    struct DNode * prior , * next;
}DNode , * DLinkList;

// 初始化
bool InitDList(DLinkList &L){
    L = (DNode *)malloc(sizeof(DNode));
    if(L == NULL)
        return false;
    
    L -> next = L;
    L -> prior = L;

    return true;
}

// 判空
bool Empty(DLinkList L){
    if(L -> next == L) return true;

    return false;
}

// 判断p节点是否为表尾节点
bool isTail(DLinkList L , DNode *p){
    if(p -> next == L)  
        return true;
    
    return false;
}

// 在p节点后插入s
bool InsertNextNode(DNode *p , DNode *s){

    /**
     * 相比于非循环双链表，少了对p是最后一个节点的判断
     * 相似的
     * 删除操作也不需要进行判断了
    */
    s ->  next = p -> next;
    s -> prior = p ;
    p -> next -> prior = s;
    p -> next = s;

    return true;
}

int main(){

    return 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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <algorithm>

using namespace std;

#define MaxSize 100

// 定义栈的结构体
typedef struct {
	int data[MaxSize];
	int top; // 栈顶指针
}SqStack;

// 初始化
void InitStack(SqStack& s) {
	s.top = -1;
}

// 判空
bool Empty(SqStack& s) {
	if (s.top == -1) return true;
	else return false;
}

// 进栈
bool Push(SqStack &s, int e) {
	if (s.top == MaxSize - 1) return false; // 栈满
	s.data[++ s.top] = e;
	return true;
}

// 出栈
bool Pop(SqStack &s, int &e) {
	if (s.top == -1) return false; // 栈空
	e = s.data[s.top --];
	return true;
}

// 读入栈顶元素
bool GetTop(SqStack s , int &e) {
	if (s.top == -1) return false;
	e = s.data[s.top];
	return true;
}

//展示各种操作
void show() {
	cout << "请输入操作序号" << endl;
	cout << "1. 判断栈是否为空" << endl;
	cout << "2. 进栈" << endl;
	cout << "3. 出栈" << endl;
	cout << "4. 读入栈顶元素" << endl;
	cout << "5. 退出" << endl;
}

// 各种方法的执行
void tete(int u ,SqStack &s) {
	if (u == 1) {
		bool flag = Empty(s);
		if (flag) cout << "栈为空" << endl;
		else cout << "栈不为空" << endl;
	}
	else if (u == 2) {
		cout << "请输入进栈元素" << endl;
		int x;
		cin >> x;
		bool flag = Push(s, x);
		if (flag) cout << "进栈成功" << endl;
		else cout << "进栈失败" << endl;
	}
	else if (u == 3) {
		int x;
		bool flag = Pop(s, x);
		if (flag) cout << "出栈成功，出栈元素为：" << x << endl;
		else cout << "出栈失败" << endl;
	}
	else if (u == 4) {
		int  x;
		bool flag = GetTop(s, x);
		if (flag) cout << "读入成功，栈顶元素为" << x << endl;
		else cout << "读入失败" << endl;
	}
}

int main() {
	SqStack s;
	InitStack(s);
	show();
	int u;
	while (cin >> u) {
		if (u == 5) return 0;
		else tete(u, s);
	}
	return 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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <algorithm>

using namespace std;

// 定义链栈
typedef struct LinkNode {
	int data;
	struct LinkNode* next;
}LNode, * LiStack;

// 初始化
bool InitStack(LiStack& S) {
	S = (LiStack)malloc(sizeof(LNode));
	if (S == NULL) return false; // 分配节点失败
	S->next = NULL;
	return true;
}

// 判空
bool Empty(LiStack S) {
	if (S->next == NULL) return true;
	return false;
}

// 进栈
bool Push(LiStack& S, int e) {
	LiStack L = (LiStack)malloc(sizeof(LNode));
	if (L == NULL) return false;
	L->data = e;

	L->next = S->next;
	S->next = L;

	return true;
}

// 出栈
bool Pop(LiStack& S, int& e) {
	LiStack q = S->next;

	if (q == NULL) return false; // 栈空
	e = q->data;
	S->next = q->next;
	free(q);
	return true;
}

// 读入栈顶元素
bool GetTop(LiStack S, int& e) {
	LiStack q = S->next;

	if (q == NULL) return false; // 栈空
	e = q->data;
	return true;
}

//展示各种操作
void show() {
	cout << "请输入操作序号" << endl;
	cout << "1. 判断栈是否为空" << endl;
	cout << "2. 进栈" << endl;
	cout << "3. 出栈" << endl;
	cout << "4. 读入栈顶元素" << endl;
	cout << "5. 退出" << endl;
}

// 各种方法的执行
void tete(int u, LiStack& s) {
	if (u == 1) {
		bool flag = Empty(s);
		if (flag) cout << "栈为空" << endl;
		else cout << "栈不为空" << endl;
	}
	else if (u == 2) {
		cout << "请输入进栈元素" << endl;
		int x;
		cin >> x;
		bool flag = Push(s, x);
		if (flag) cout << "进栈成功" << endl;
		else cout << "进栈失败" << endl;
	}
	else if (u == 3) {
		int x;
		bool flag = Pop(s, x);
		if (flag) cout << "出栈成功，出栈元素为：" << x << endl;
		else cout << "出栈失败" << endl;
	}
	else if (u == 4) {
		int  x;
		bool flag = GetTop(s, x);
		if (flag) cout << "读入成功，栈顶元素为" << x << endl;
		else cout << "读入失败" << endl;
	}
}

int main() {
	LiStack S;
	InitStack(S);
	show();
	int u;
	while (cin >> u) {
		if (u == 5) return 0;
		else tete(u, S);
	}

	return 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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>

using namespace std;

// 定义结构体最大存储空间
#define MaxSize 100

/**
 * 直接写的循环队列
*/

// 定义一个顺序队列的结构体
typedef struct{
    int data[MaxSize];
    int front , rear ; // 队头指向队头第一个元素，队尾指向队尾后面一个元素 即队满时 留出一个空位 作为队满的判断
} SqQueue;

// 初始化队列
void InitQueue(SqQueue &Q){
    Q.front = Q.rear = 0;
}

// 判空
bool Empty(SqQueue Q){
    if(Q.front == Q.rear ) return true;
    return false;
}

// 入队
bool EnQueue(SqQueue &Q , int e){
    if((Q.rear + 1) % MaxSize == Q.front) return false; // 如果队满则报错
    // 将值赋给队尾
    Q.data[Q.rear] = e;
    // 队尾向后移动一位
    Q.rear  = (Q.rear + 1) % MaxSize ; // 因为是循环队列，所以要模一个MaxSize

    return true;
}

// 出队
bool DeQueue(SqQueue &Q ,int &e){
    if(Q.rear == Q.front) return false; // 队空
    e = Q.data[Q.front];  
    Q.front = (Q.front + 1) % MaxSize;

    return true;
}

// 读取队头元素
bool GetHead(SqQueue Q, int &e){
    e = Q.data[Q.front];

    return true;
}

void show(){
    cout << "请输入操作" << endl;
    cout << "1. 判空" <<endl;
    cout << "2. 入队" <<endl;
    cout << "3. 出队" <<endl;
    cout << "4. 读取队头元素" <<endl;
    cout << "5. 退出" <<endl;
}

void tete(int u , SqQueue &Q){
    if(u == 1){
        if(Empty(Q)) cout << "队为空" << endl;
        else cout << "队不为空" << endl;
    }else if(u == 2){
        int x;
        cout << "请输入入队元素" << endl; 
        cin >> x;
        if(EnQueue(Q,x)) cout << "入队成功" << endl;
        else cout << "入队失败" << endl;
    }else if(u == 3){
        int x;
        if(DeQueue(Q,x)) cout << "出队成功，出队元素为：" << x << endl;
        else cout << "出队失败" << endl;
    }else if(u == 4){
        int x ;
        if(GetHead(Q,x)) cout << "读取成功，队头元素为：" << x << endl;
        else cout << "读取失败" << endl;
    }
}

int main(){

    SqQueue Q;
    InitQueue(Q);
    show();
    int u ;
    while(cin >> u){
        if(u == 5) return 0;
        else tete(u,Q);
    }

    return 0;
}

链队列

链队列的操作和顺序循环队列几乎一样，不在赘述

但是王道的数据结构书中代码定义链式队列结构体部分出错，无法直接使用，所以我做了一些改变， 将 *LinkQueue 改为 LinkQueue ，去掉了指针，即可成功。

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>

using namespace std;

// 定义链队列的结构体
typedef struct LinkNode{   // 链式队列节点
    int data;
    struct LinkNode * next;
}LinkNode;

typedef struct{    // 链式队列
    LinkNode * front , * rear ;  // 链式队列队头队尾指针  队头指针指向链头，负责出队， 队尾指针指向链尾，负责入队
}LinkQueue;

// 初始化
void InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode)); // 分配一个头节点
    Q.front -> next = NULL;  // 初始化队列为空
    // 当rear添加元素后，相应的front的next也会多一个元素,  同时 front 永远指向头节点，而不具体指向某一个含有数据的节点
}

// 判空
bool Empty(LinkQueue Q){
    if(Q.front == Q.rear) return true;
    return false;
}

// 入队
bool EnQueue(LinkQueue &Q , int e){
    LinkNode * s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = e;
    Q.rear->next = s;
    s->next = NULL;
    Q.rear = s;
    return true;
}

// 出队
bool DeQueue(LinkQueue &Q ,int &e){
    if(Q.front == Q.rear) return false;
    LinkNode *s;
    s = Q.front->next;
    e = s->data;
    Q.front->next = s->next;
    // 如果出队的是队列中的最后一个元素，则将rear指向头节点
    if(Q.rear == s){
        Q.rear = Q.front;
    }
    free(s);
    return true;
}

// 读取队头元素
bool GetHead(LinkQueue Q, int &e){
    if(Q.front == Q.rear) return false;
    LinkNode *s = Q.front->next;
    e = s->data;
    return true;
}

void show(){
    cout << "请输入操作" << endl;
    cout << "1. 判空" <<endl;
    cout << "2. 入队" <<endl;
    cout << "3. 出队" <<endl;
    cout << "4. 读取队头元素" <<endl;
    cout << "5. 退出" <<endl;
}

void tete(int u , LinkQueue &Q){
    if(u == 1){
        if(Empty(Q)) cout << "队为空" << endl;
        else cout << "队不为空" << endl;
    }else if(u == 2){
        int x;
        cout << "请输入入队元素" << endl; 
        cin >> x;
        if(EnQueue(Q,x)) cout << "入队成功" << endl;
        else cout << "入队失败" << endl;
    }else if(u == 3){
        int x;
        if(DeQueue(Q,x)) cout << "出队成功，出队元素为：" << x << endl;
        else cout << "出队失败" << endl;
    }else if(u == 4){
        int x ;
        if(GetHead(Q,x)) cout << "读取成功，队头元素为：" << x << endl;
        else cout << "读取失败" << endl;
    }
}

int main(){

    LinkQueue Q;
    InitQueue(Q);
    show();
    int u ;
    while(cin >> u){
        if(u == 5) return 0;
        else tete(u,Q);
    }

    return 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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>

using namespace std;

// 定义链队列的结构体
typedef struct LinkNode{   // 链式队列节点
    int data;
    struct LinkNode * next;
}LinkNode;


typedef struct LinkQueue {
    LinkNode * front , * rear; 
}LinkQueue , *LiQueue;


// 初始化
void InitQueue(LiQueue &Q){
    Q = (LinkQueue *)malloc (sizeof(LinkQueue)); //初始化链队列
    Q -> front = Q-> rear = (LinkNode *)malloc(sizeof(LinkNode)); // 分配一个头节点
    Q-> front -> next = NULL;  // 初始化队列为空，这里Q->rear 和Q->front 都一样，都是对同一个链进行操作，
    // 当rear添加元素后，相应的front的next也会多一个元素,  同时 front 永远指向头节点，而不具体指向某一个含有数据的节点
}

// 判空
bool Empty(LiQueue Q){
    if(Q -> front == Q -> rear) return true;
    return false;
}

// 入队
bool EnQueue(LiQueue &Q , int e){
    LinkNode * s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = e;
    Q -> rear->next = s;
    s->next = NULL;
    Q -> rear = s;
    return true;
}

// 出队
bool DeQueue(LiQueue &Q ,int &e){
    if(Q -> front == Q -> rear) return false;
    LinkNode *s;
    s = Q -> front->next;
    e = s->data;
    Q -> front->next = s->next;
    // 如果出队的是队列中的最后一个元素，则将rear指向头节点
    if(Q -> rear == s){
        Q -> rear = Q -> front;
    }
    free(s);
    return true;
}

// 读取队头元素
bool GetHead(LiQueue Q, int &e){
    if(Q -> front == Q -> rear) return false;
    LinkNode *s = Q -> front->next;
    e = s->data;
    return true;
}

void show(){
    cout << "请输入操作" << endl;
    cout << "1. 判空" <<endl;
    cout << "2. 入队" <<endl;
    cout << "3. 出队" <<endl;
    cout << "4. 读取队头元素" <<endl;
    cout << "5. 退出" <<endl;
}

void tete(int u , LiQueue &Q){
    if(u == 1){
        if(Empty(Q)) cout << "队为空" << endl;
        else cout << "队不为空" << endl;
    }else if(u == 2){
        int x;
        cout << "请输入入队元素" << endl; 
        cin >> x;
        if(EnQueue(Q,x)) cout << "入队成功" << endl;
        else cout << "入队失败" << endl;
    }else if(u == 3){
        int x;
        if(DeQueue(Q,x)) cout << "出队成功，出队元素为：" << x << endl;
        else cout << "出队失败" << endl;
    }else if(u == 4){
        int x ;
        if(GetHead(Q,x)) cout << "读取成功，队头元素为：" << x << endl;
        else cout << "读取失败" << endl;
    }
}

int main(){

    LiQueue Q;
    InitQueue(Q);
    show();
    int u ;
    while(cin >> u){
        if(u == 5) return 0;
        else tete(u,Q);
    }

    return 0;
}

串 KMP

还没有完全写好，还会补充 –2023.5.26

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

#define MaxSize 100

int ne[MaxSize]; // 定义next数组，用来存放kmp的next数组

// 定义一个结构体用于存储字符串及其长度，也可以直接定义两个char类型的变量
typedef struct {
	char ch[MaxSize];
	int length;
}SString;

// 暴力搜索 BF
int BF(SString S, SString T) {
	int i = 1, j = 1;
	while (i <= S.length && j <= T.length) {
		if (S.ch[i] == T.ch[j]) i++, j++;
		else j = 1, i - j + 2;
	}
	if (j > T.length) cout << i - T.length ; // +1 表示从第i个位置开始，即可匹配
	else return 0;
}

// 求next数组
void GetNext(SString T, int ne[]) {
	int i = 1, j = 0;
	ne[1] = 0;
	while (i < T.length) { //对比到倒数第二个数组结束
		if (j == 0 || T.ch[i] == T.ch[j]) {
			i++; j++;
		}
		else j = ne[j];
	}
}

// KMP匹配
int KMP(SString S, SString T,int ne[]) {
	int i = 1, j = 1;
	while (i <= S.length && j <= T.length) {
		if (j == 0 || S.ch[i] == T.ch[j]) {
			i++, j++;
		}
		else j = ne[j];// 模式串向右移动
	}
	if (j > T.length) return i - T.length;
	else return 0;
}

int main() {
	SString S, T;
    memset(ne,0,sizeof(ne));
	cin >> S.ch + 1>> T.ch + 1; // 从i= 1开始输入 
	S.length = strlen(S.ch) - 1;
	T.length = strlen(T.ch) - 1;
	return 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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
#include <iostream>
#include <queue>  //直接引入队列

using namespace std;

#define MaxSize 100 // 定义顺序栈的最大空间

bool flag = false ; // flag来判断输入的是否是根节点 false == 是  true == 不是
int values[] = {1, 2, 4, -1, -1, 5, -1, -1, 3, -1, -1}; // 手动创建一个二叉树
int val = 0; // 遍历values的指针

// 定义二叉链表
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild , *rchild ;
}BiTNode , *BiTree;

// 创建一个新的节点
BiTNode * CreateNode(int value){
    BiTNode * newNode = (BiTNode *)malloc(sizeof(BiTNode));
    if(newNode == NULL){
        cout << "分配内存失败" << endl;
        exit(0);
    }
    newNode->data = value;
    newNode->lchild = NULL;
    newNode->rchild = NULL;

    return newNode;
}

// 创建二叉树
BiTree CreateTree(){
    BiTNode * root = NULL;   // 创建一个新的节点
    int value;
    if(!flag){
        // cout << "请输入根节点的值（输入-1表示为空节点）" << endl;
        flag = true;
    }

    value = values[val ++];
    if (value == -1) {
        return NULL;
    }

    root = CreateNode(value); // 将value赋给root节点

    // 递归循环输入左右节点的值

    // cout << "请输入 " << value << " 的左节点（输入-1表示节点为空） " << endl;
    root->lchild = CreateTree();

    // cout << "请输入 " << value << " 的右节点（输入-1表示节点为空） " << endl;
    root->rchild = CreateTree();


    return root;
}


/**
 *  递归版本
*/

// 先序遍历
void PreOrder(BiTree T){
    if(T == NULL) return;
    cout << T->data << " ";
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}

// 中序遍历
void InOrder(BiTree T){
    if(T == NULL) return ;
    InOrder(T->lchild);
    cout << T->data << " ";
    InOrder(T->rchild);
}

// 后序遍历
void PostOrder(BiTree T){
    if(T == NULL ) return ;
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    cout << T->data << " ";
}

/**
 *  非递归版本 非递归需要用到栈  这里为了方便直接使用顺序栈 
*/

//  ================================== 栈的方法 ======================================

// 定义栈的结构体  
typedef struct {
	BiTree data[MaxSize];
	int top; // 栈顶指针
}SqStack;

// 初始化
void InitStack(SqStack& s) {
	s.top = -1;
}

// 判空
bool Empty(SqStack& s) {
	if (s.top == -1) return true;
	else return false;
}

// 进栈
bool Push(SqStack &s, BiTree e) {
	if (s.top == MaxSize - 1) return false; // 栈满
	s.data[++ s.top] = e;
	return true;
}

// 出栈
bool Pop(SqStack &s, BiTree &e) {
	if (s.top == -1) return false; // 栈空
	e = s.data[s.top --];
	return true;
}

// 读入栈顶元素
BiTree GetTop(SqStack s ) {
	if (s.top == -1) return NULL;
	return s.data[s.top];
}

//  ================================== 栈的方法结束 ======================================

SqStack S; // 提前申请一个栈，用作后续的使用

// 前序遍历
void RePreOrder(BiTree T){
    InitStack(S);
    BiTree P = T; // P 是遍历指针
    while(P || !Empty(S)){ // 如果 P 不为空 或者 栈不空 开始循环
        if(P){
            cout << P->data << " ";  // 先输出根节点的值
            Push(S,P);          // 入栈
            P = P->lchild;  // 接着访问 p的左节点
        }else {   // 出栈，并转向栈节点的右子树
            Pop(S,P);   // 栈顶元素出栈
            P = P->rchild;  // 向右子树走
        }
    }
}

// 中序遍历
void ReInOrder(BiTree T){
    InitStack(S);
    BiTree P = T;
    while(P || !Empty(S)){   // 当 P不为空 或者 栈不为空时候进入循环
        if(P){         // 左子树不为空
            Push(S,P);     // 入栈
            P = P->lchild;  // 进入左子树
        }else {   // 左孩子为空时候，进入右子树
            Pop(S,P); // 将栈顶节点出栈，即进入该节点的右孩子 ，此时p节点为最左侧节点
            cout << P->data << " " ; // 中序输出节点
            P = P->rchild; // 遍历右子树
        }
    }
}

// 后序遍历
/**
 * 后序遍历算法思想：
 *      1. 将遍历指针 P  指向根节点
 *      2. 创建一个辅助变量 prev，用于存储上一个被访问的节点 
 *      3. 进入循环（如果遍历指针 p 不为空 || 栈不为空） 
 *          1. 沿着当前节点的左子树，依次把左子树的左孩子都压入栈
 *          2. 取出栈顶元素 current （最后一个压入栈的节点，根据上一次的循环遍历，current节点没有左孩子），此时判断current是否有右孩子，或者右孩子是否被访问过
 *              如果 current 没有右孩子，或者右孩子已经被访问过 弹出 current ，将 prev 指针指向 current ，并输出 current 的值
 *              如果 current 存在右孩子并且没有被访问 ， 将遍历指针指向右孩子（P = current->rchild ），接着 第三步 的循环
 * 
 * 根据上述算法，可知，每次先输出最左边的节点（设为 left），然后判断left的父节点（设为father）的左孩子（设为right），如果right存在或者没有被访问
 *  则将right入栈，循环判断，然后输出。假设right为空，则输出father节点。即满足了 左右根 的后序遍历顺序
*/
void RePostOrder(BiTree T){
    InitStack(S); // 初始化栈
    BiTree P = T;  // p是遍历指针
    BiTNode * prev = NULL;
    while(P || !Empty(S)){ // 当 P不为空 或者 栈不为空时候进入循环
        while(P){   // 从根节点，沿着左子树开始，所有的左孩子压入栈
            Push(S,P); 
            P = P->lchild;
        }

        // 获取栈顶元素, 此时current的左孩子为空
        BiTNode * current = GetTop(S);

        // 判断右孩子是否为空或者被访问过
        if(current->rchild == NULL || current->rchild == prev){  // 如果右孩子为空或者被访问过
            Pop(S,current); // 将栈顶元素出栈，实际上 current 并没有改变
            cout << current->data << " "; // 输出current的值，此时左孩子和右孩子 为空，或者都被访问
            prev = current; // 将current设为上一个访问的值
        }else {  // 如果右孩子不为空且未访问过
            P = current->rchild; // p 节点指向右节点进行访问，重新进行遍历
        }

    }    
}

// 层序遍历，使用队列进行缓存 ,为了方便直接调用c++库里面的队列函数
void LevelOrder(BiTree T){
    queue<BiTree> Q; // 定义一个队列
    BiTNode * p = T; // p 是遍历指针
    Q.push(p); // 将根节点插入队列
    while(!Q.empty()){
        p = Q.front();
        Q.pop();
        cout << p->data << " ";

        if(p->lchild != NULL)
            Q.push(p->lchild);
        if(p->rchild != NULL)
            Q.push(p->rchild);

    }
}

int main(){

    BiTree T = CreateTree(); // 定义并创建一个二叉树

    cout << "递归方法的前序，中序，后序遍历二叉树" << endl;

    cout << "前序遍历: " ; 
    PreOrder(T);
    cout << endl;

    cout << "中序遍历：";
    InOrder(T);
    cout << endl;

    cout << "后序遍历：";
    PostOrder(T);
    cout << endl << endl;


    cout << "非递归方法的前序，中序，后序遍历二叉树" << endl;

    cout << "前序遍历: " ; 
    RePreOrder(T);
    cout << endl;

    cout << "中序遍历：";
    ReInOrder(T);
    cout << endl;

    cout << "后序遍历：";
    RePostOrder(T);
    cout << endl << endl;


    cout << "层序遍历: ";
    LevelOrder(T);
    cout << endl;

    return 0;
}

运行结果：

image-20230531185933832

二叉线索树

引入二叉线索树是为了加快查找结点的前驱和后继的速度

但是引入后，只有中序二叉线索树找前序和后继都很方便

但是 先序线索二叉树 找前驱 和 后序线索二叉树 找后继都比较麻烦 ，除非使用三叉链表，否则只能使用从根节点遍历的方法来寻找

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
#include <iostream>

using namespace std;
 
// 定义一个二叉链表，作为二叉线索树
typedef struct BiThrNode{
    int data;   // 存储的数据
    struct BiThrNode * lchild , * rchild; // 左右孩子的指针
    int LTag , RTag; // 左右标志，0 表示指向孩子， 1 表示指向前驱（LTag） 或 后继（RTag）
}BiThrNode , * BiThrTree;

// 初始化一个二叉链表

bool flag = false ; // flag来判断输入的是否是根节点 false == 是  true == 不是
int values[] = {1, 2, 4, -1, -1, 5, -1, -1, 3, -1, -1}; // 手动创建一个二叉树
int val = 0; // 遍历values的指针

// 创建一个新的节点
BiThrNode * CreateNode(int value){
    BiThrNode * newNode = (BiThrNode *)malloc(sizeof(BiThrNode));
    if(newNode == NULL){
        cout << "分配内存失败" << endl;
        exit(0);
    }
    newNode->data = value;
    newNode->lchild = NULL;
    newNode->rchild = NULL;
    newNode->LTag = 0; // 这里一定要初始化，不然会报错
    newNode->RTag = 0;
    return newNode;
}

// 创建二叉树
BiThrTree CreateTree(){
    BiThrNode * root = NULL;   // 创建一个新的节点
    int value;
    if(!flag){
        // cout << "请输入根节点的值（输入-1表示为空节点）" << endl;
        flag = true;
    }

    value = values[val ++];
    if (value == -1) {
        return NULL;
    }

    root = CreateNode(value); // 将value赋给root节点
    // cout << root->data << " ";
    // 递归循环输入左右节点的值

    // cout << "请输入 " << value << " 的左节点（输入-1表示节点为空） " << endl;
    root->lchild = CreateTree();

    // cout << "请输入 " << value << " 的右节点（输入-1表示节点为空） " << endl;
    root->rchild = CreateTree();


    return root;
}


// ======================================= 先序线索二叉树 ======================================



// 先序线索化
void PreThread(BiThrTree &q, BiThrTree & pre){
    if(q != NULL){
        if(q->lchild != NULL){  // 如果左孩子为空，将左孩子指针线索化 ,建立前驱线索
            q->lchild = pre;   // 左孩子指向前驱节点
            q->LTag = 1;    // 表示左孩子为线索
        }
        // 此时pre指向 q 的前驱结点，如果pre不为空，且pre结点的右孩子为空，则将pre的右孩子线索化，指向q
        if(pre != NULL && pre->rchild == NULL){  // 建立后继线索
            pre->rchild = q;
            pre->RTag = 1;
        }
        pre = q;
        if(q->LTag == 0) { // 如果q的左结点有孩子
            PreThread(q->lchild,pre); //递归遍历左孩子
        }
        PreThread(q->rchild,pre); // 递归遍历右孩子
    }
}

// 创建先序线索二叉树
void CreatePreThread(BiThrTree T){
    // 定义变量，用于表示当前访问结点的前驱
    BiThrNode * pre = NULL ;
    if(T != NULL){
        PreThread(T,pre);
        if(pre->rchild == NULL)
            pre->RTag = 1;
    }
}



// ======================================= 中序线索二叉树 ======================================




// 中序线索化
void InThread(BiThrTree &q, BiThrTree &pre){
    if(q != NULL){
        InThread(q->lchild , pre);   // 递归遍历左子树

        if(q->lchild == NULL){ // 如果左孩子为空，将左孩子指针线索化
            q->lchild = pre;   // 左孩子指向前驱节点
            q->LTag = 1;   // 表示左孩子为线索
        }
        // 此时pre指向 q 的前驱结点，如果pre不为空，且pre结点的右孩子为空，则将pre的右孩子线索化，指向q
        if(pre != NULL && pre->rchild == NULL){ 
            pre->rchild = q;
            pre->RTag = 1;
        }
        pre = q;  // 将当前结点标记为上一次访问过的结点

        InThread(q->rchild,pre); // 递归遍历右子树
    }

}

// 建立中序线索二叉树
void CreateInThread(BiThrTree T){
    // 定义变量，用于表示当前访问结点的前驱
    BiThrNode * pre = NULL ; 
    if(T != NULL ){
        InThread(T,pre);
        pre->rchild = NULL;  // 遍历处理完的最后一个结点，应为右子树的最后一个叶结点
        pre->RTag = 1;      // 没有右孩子
    }
}

// ================== 中序二叉树找后继 ========================

// 找到以 p 为根结点的线索树中，第一个被中序遍历的结点
BiThrNode *Firstnode(BiThrNode *p){
    // 中序遍历中，第一个被遍历的结点为 左子树中最左边的结点
    while(p->LTag == 0)
        p = p->lchild;

    return p;
}

// 找到 p 的后继结点
BiThrNode *Nextnode(BiThrNode *p){
    if(p->RTag == 0) return Firstnode(p->rchild); // 如果存在右结点，则找到右子树中的最左边结点，即为后继节点
    else return p->rchild;
}

// 对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
void InOrder(BiThrTree T){
    for(BiThrNode *p = Firstnode(T); p != NULL ; p = Nextnode(p)){
        cout << p->data <<" ";
    }
    cout << endl;
}

// =================== 中序二叉树找前驱 =================================

// 找到以 p 为根结点的线索树中，最后一个被中序遍历的结点
BiThrNode *Lastnode(BiThrNode *p){
    while(p->RTag == 0) p = p->rchild; // 树中最右边结点

    return p; 
}

// 找到 p 的前驱结点
BiThrNode *Priornode(BiThrNode *p){
    if(p->LTag == 0) return Lastnode(p->lchild);
    else return p->lchild; // 如果 LTag= 1 直接返回前驱节点
}

// 对中序二叉树进行逆向中序遍历
void RevInOrder(BiThrTree T){
    for(BiThrNode * p = Lastnode(T); p != NULL ; p = Priornode(p)){
        cout << p->data <<" ";
    }
    cout << endl;
}


// ======================================= 后序线索二叉树 ======================================



// 后序线索化
void PostThread(BiThrTree &q, BiThrTree & pre){
    if(q != NULL){
        PostThread(q->lchild,pre);
        PostThread(q->rchild,pre);  // 递归遍历左右子树
         if(q->lchild == NULL){ // 如果左孩子为空，将左孩子指针线索化
            q->lchild = pre;   // 左孩子指向前驱节点
            q->LTag = 1;   // 表示左孩子为线索
        }
        // 此时pre指向 q 的前驱结点，如果pre不为空，且pre结点的右孩子为空，则将pre的右孩子线索化，指向q
        if(pre != NULL && pre->rchild == NULL){ 
            pre->rchild = q;
            pre->RTag = 1;
        }
        pre = q;  // 将当前结点标记为上一次访问过的结点
    }

}

// 创建后序线索二叉树
void CreatePostThread(BiThrTree T){
    // 定义变量，用于表示当前访问结点的前驱
    BiThrNode * pre = NULL ; 
    if(T != NULL ){
        PostThread(T,pre);
        pre->rchild = NULL;  // 遍历处理完的最后一个结点，应为右子树的最后一个叶结点
        pre->RTag = 1;      // 没有右孩子
    }
}

//前序遍历(未线索化) 测试用
void IInOrder(BiThrTree T){
    if(T == NULL) return ;
    IInOrder(T->lchild);
    cout << T->data << " ";
    IInOrder(T->rchild);
}

int main(){
    BiThrTree T = CreateTree(); // 初始化一个二叉链表
    cout << "前序遍历(未线索化): " ; 
    IInOrder(T);
    cout << endl << endl;
    // 建立中序线索二叉树
    CreateInThread(T);
  
    cout << "正序输出中序二叉线索树: " ; 
    InOrder(T);
    cout << endl;

    cout << "逆序输出中序二叉线索树: " ; 
    RevInOrder(T);
    cout << endl;
}

程序运行结果：

image-20230531185904778

并查集

只优化了”并“的方法 （小树 + 到大树上），没有优化 查的部分

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
#include <iostream> 

using namespace std;

// 使用数组模拟并查集
#define Size 100
int UFSets[Size];

// 初始化，将所有结点赋值为-1，表示每个结点都是独立的一个集合
void Initial(int s[]){
    for(int i = 0;i < Size ;i ++) s[i] = -1;
}

// find 操作
int Find(int s[],int x){
    while(s[x] >= 0)
        x = s[x];

    return x;
}

// 并操作  首先找到根 ，然后进行并操作,让小树合并到大树上
void Union(int s[], int root1 ,int root2){
    if(root1 == root2) return ;

    // 如果root2 上结点数更少
    if(s[root1] > s[root2]){  // 根部 存放的是 当前集合一共有多少个结点的相反数，例如 有5个结点，存放的就是 -5
        s[root2] += s[root1];
        s[root1] = root2; 
    }else{
        s[root1] += s[root2];
        s[root2] = root1; 
    }
}

int main(){
    Initial(UFSets);
    cout << "输入1 判断" << endl;
    cout << "输入2 合并" << endl;
    cout << "输入其他字符 退出" << endl;
    int c;
    while(cin >> c){
        if(c == 1){
            cout << "请输入需要判断是否在一个集合的两个数：" << endl;
            int a ; 
            int b;
            cin >> a >> b;
            if(Find(UFSets,a) == Find(UFSets,b)) cout << "是同一个集合" << endl;
            else cout << "不是一个集合" << endl;
        }else if(c == 2){
            cout << "请输入想要合并的两个数的集合： " << endl;
            int a ;
            int b;
            cin >> a >> b;
            Union(UFSets,Find(UFSets,a), Find(UFSets,b));
        }else return 0;
    }
    

    return 0;
}

图

邻接矩阵

1
2
3
4
5
6
#define MaxVertexNum 100 
typedef struct {
    char Vex[MaxVertexNum];                         // 顶点表
    int Edge[MaxVertexNum][MaxVertexNum];           // 边表
    int vexnum,arcnum;                              // 图的当前顶点数和弧数
}MGraph;

邻接链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define MaxVertexNum 100 
typedef struct ArcNode{             // 边表结点
    int adjvex;                     // 该弧所指向的顶点的位置
    struct ArcNode *next;           // 指向下一条弧的指针
    // int info;                    // 网的边权值
}ArcNode;

typedef struct VNode{               // 顶点表结点
    char data;                      // 顶点信息
    ArcNode *first;                 // 指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];       

typedef struct{
    AdjList vertices;               // 邻接表
    int vexnum, arcnum;             // 图的顶点数和弧数
}AlGraph;

排序

注意：该所有排序都是数组下标从0开始，故代码与王道数据结构书上代码有所不同

插入排序

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
void InsertSort(int a[],int n){
    int j,temp;
    for(int i = 1;i < n;i ++){
        if(a[i] < a[i - 1]){
            temp = a[i];
            for(j = i -1 ;j >= 0 && a[j] > temp ;j --){
                a[j+1] = a[j];
            }
            a[j+1] = temp;
        }
    }
}

折半插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InsertHalfSort(int a[], int n){
    int i , j , temp , high , low , mid;
    for(i = 1;i < n ;i ++){
        temp = a[i];
        low = 0, high = i - 1;
        while(low <= high){
            mid = (low + high) / 2;
            if(a[mid] > temp) high = mid -1;
            else low = mid + 1;
        }
        for(j = i - 1  ;j >= high + 1; --j ){
            a[j+1] = a[j];
        }
        a[high+1] = temp; 
    }
}

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void ShellSort(int a[],int n){
    int dk, i , j,temp;
    for(dk = n/2; dk >= 1; dk /= 2){  // 设置增量变化
        for(i = dk; i < n;i ++){
            if(a[i] < a[i - dk]){  // 类比直接插入
                temp = a[i]; // temp暂存 a[i]
                for(j = i - dk ;j >= 0 && temp < a[j] ; j -= dk){ // 将记录依次向后移动
                    a[j + dk] =  a[j];
                }
                a[j + dk] = temp; // 插入
            }
        }
    }
    
}

交换排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
void BubbleSort(int a[],int n){
    
    for(int j = 0;j < n;j ++){
        bool flag = true;
        for(int i = n - 2;i >= j;i --){
            if(a[i] > a[i + 1]){
                 swap(a[i],a[i + 1]);
                 flag = false;  // 记录排序变化了
            }
        }
        if(flag == true) return ; //  如果一趟没有进行位置变化，表明排序完成
    }
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 一趟划分
int Partition(int a[] ,int low ,int high){
    int temp = a[low]; // 将第一个元素作为枢轴
    while(low < high){
        while(low < high && temp <= a[high]) high --; 
        a[low] = a[high];   // 将比枢轴小的数移动到左边

        while(low < high && temp > a[low]) low ++;
        a[high] = a[low];   // 将比枢轴小的数移动到右边
    }
    a[low] = temp ;   // 这里 low 也可用 high 替换，下面一行也是 ， 自己画个图手动推导一遍会更清晰一点
    return low;  // 返回存放枢轴的位置
}

void QuickSort(int a[],int low ,int high){
    if(low < high){
        int mid = Partition(a,low,high);
        QuickSort(a,low , mid -1);  // 一次对左右两边进行递归
        QuickSort(a,mid + 1 , high);
    }
    
}

选择排序

简单选择排序

1
2
3
4
5
6
7
8
void SelectSort(int a[],int n){
    for(int j = 0;j < n; j ++){
        int min = j; // 存储最小值
        for(int i = j + 1;i < n;i ++)
            if(a[min] > a[i]) min = i;
        if(min != j ) swap(a[min], a[j]);
    }
}

推排序

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
// 调整堆
void HeadAdjust(int a[],int k ,int len){
    // 将以k为跟的树进行调整
    int temp = a[k];  // 暂存
    for(int i = 2*k ; i < len ; i *= 2){
        if(i == 0) i ++; // 因为数组a[] 下标是从0 开始的，根节点的孩子节点为1 ，故加一个判断
        if(i < len - 1 && a[i] > a[i + 1]) i ++ ; // 找到左右结点中最小的一个
        if(temp <= a[i]) break;
        else {
            a[k] = a[i];
            k = i; // 修改 k 的值 ，继续往下进行遍历
        } 
    }
    a[k] = temp ; // 将被删选结点放入最终的位置
}

// 建立小根堆
void BuildMinHeap(int a[],int len){
    for(int i = len / 2 - 1 ; i >= 0;i --){  // 从最后一个非终端结点开始遍历
        HeadAdjust(a,i,len); // 进行调整
    }
}

// 从小到大进行输出
void HeapSort(int a[],int len){
    BubbleSort(a,len); // 先建立一个小根堆
    for(int i = len - 1;i >= 0;i --){
        cout << a[0] <<" "; // 输出最小的
        swap(a[i],a[0]);  // 将堆顶元素和堆底元素交换
        HeadAdjust(a,0,i-1);  // 调整，将剩余i-1个元素整理成堆
    }
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int b[21]; // 为归并排序划定一个辅助数组
void Merge(int a[],int low ,int mid ,int high){
    // 表中 low - mid 和 mid - high 各自有序
    int i,j,k;
    for(int i = low ;i <= high ;i ++)
        b[i] = a[i]; // 将a中所有元素复制到b中    
    
    for(i = low , j = mid + 1 , k = i; i <= mid && j <= high ; k ++){
        if(b[i] <= b[j]) a[k] = b[i ++];
        else a[k] = b[j ++];
    }
    while(i <= mid) a[k ++] = b[i ++]; //若跳出循环后，仍有剩下的元素，将其复制到数组中
    while(j <= high) a[k ++] = b[j ++];
}

void MergeSort(int a[] , int low ,int high){
    if(low < high){
        int mid = (low + high) /2;
        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
    }
}

基数排序

基数排序不做代码要求，故没有写。

所有排序运行完成程序

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
#include <iostream> 

using namespace std;

int a[] = {84,7,16,47,1,11,71,52,52,22,82,79,54,51,26,9,41,37,79,88,90}; // 二十一个数字，作为排序的数字，可以自行添加
// 排完序结果应为 1 7 9 11 16 22 26 37 41 47 51 52 52 54 71 79 79 82 84 88 
int len = 21;

// ======================================== 插入排序 ================================
// 直接插入排序
void InsertSort(int a[],int n){
    int j,temp;
    for(int i = 1;i < n;i ++){
        if(a[i] < a[i - 1]){
            temp = a[i];
            for(j = i -1 ;j >= 0 && a[j] > temp ;j --){
                a[j+1] = a[j];
            }
            a[j+1] = temp;
        }
    }
}

// 折半插入排序
void InsertHalfSort(int a[], int n){
    int i , j , temp , high , low , mid;
    for(i = 1;i < n ;i ++){
        temp = a[i];
        low = 0, high = i - 1;
        while(low <= high){
            mid = (low + high) / 2;
            if(a[mid] > temp) high = mid -1;
            else low = mid + 1;
        }
        for(j = i - 1  ;j >= high + 1; --j ){
            a[j+1] = a[j];
        }
        a[high+1] = temp; 
    }
}

// 希尔排序  类比直接插入排序
void ShellSort(int a[],int n){
    int dk, i , j,temp;
    for(dk = n/2; dk >= 1; dk /= 2){  // 设置增量变化
        for(i = dk; i < n;i ++){
            if(a[i] < a[i - dk]){  // 类比直接插入
                temp = a[i]; // temp暂存 a[i]
                for(j = i - dk ;j >= 0 && temp < a[j] ; j -= dk){ // 将记录依次向后移动
                    a[j + dk] =  a[j];
                }
                a[j + dk] = temp; // 插入
            }
        }
    }
    
}

// ======================================== 交换排序 ================================
// 交换
void swap(int &a,int &b){
    int temp = a ;
    a = b;
    b = temp;
}

// 冒泡排序
void BubbleSort(int a[],int n){
    
    for(int j = 0;j < n;j ++){
        bool flag = true;
        for(int i = n - 2;i >= j;i --){
            if(a[i] > a[i + 1]){
                 swap(a[i],a[i + 1]);
                 flag = false;  // 记录排序变化了
            }
        }
        if(flag == true) return ; //  如果一趟没有进行位置变化，表明排序完成
    }
}

// 快速排序

// 一趟划分
int Partition(int a[] ,int low ,int high){
    int temp = a[low]; // 将第一个元素作为枢轴
    while(low < high){
        while(low < high && temp <= a[high]) high --; 
        a[low] = a[high];   // 将比枢轴小的数移动到左边

        while(low < high && temp > a[low]) low ++;
        a[high] = a[low];   // 将比枢轴小的数移动到右边
    }
    a[low] = temp ;   // 这里 low 也可用 high 替换，下面一行也是 ， 自己画个图手动推导一遍会更清晰一点
    return low;  // 返回存放枢轴的位置
}

void QuickSort(int a[],int low ,int high){
    if(low < high){
        int mid = Partition(a,low,high);
        QuickSort(a,low , mid -1);  // 一次对左右两边进行递归
        QuickSort(a,mid + 1 , high);
    }
    
}


// ======================================== 选择排序 ================================

// 简单选择排序
void SelectSort(int a[],int n){
    for(int j = 0;j < n; j ++){
        int min = j; // 存储最小值
        for(int i = j + 1;i < n;i ++)
            if(a[min] > a[i]) min = i;
        if(min != j ) swap(a[min], a[j]);
    }
}

// 堆排序  书上是大根堆，我这里是小根堆

// 调整堆
void HeadAdjust(int a[],int k ,int len){
    // 将以k为跟的树进行调整
    int temp = a[k];  // 暂存
    for(int i = 2*k ; i < len ; i *= 2){
        if(i == 0) i ++; // 因为数组a[] 下标是从0 开始的，根节点的孩子节点为1 ，故加一个判断
        if(i < len - 1 && a[i] > a[i + 1]) i ++ ; // 找到左右结点中最小的一个
        if(temp <= a[i]) break;
        else {
            a[k] = a[i];
            k = i; // 修改 k 的值 ，继续往下进行遍历
        } 
    }
    a[k] = temp ; // 将被删选结点放入最终的位置
}

// 建立小根堆
void BuildMinHeap(int a[],int len){
    for(int i = len / 2 - 1 ; i >= 0;i --){  // 从最后一个非终端结点开始遍历
        HeadAdjust(a,i,len); // 进行调整
    }
}

// 从小到大进行输出
void HeapSort(int a[],int len){
    BubbleSort(a,len); // 先建立一个小根堆
    for(int i = len - 1;i >= 0;i --){
        cout << a[0] <<" "; // 输出最小的
        swap(a[i],a[0]);  // 将堆顶元素和堆底元素交换
        HeadAdjust(a,0,i-1);  // 调整，将剩余i-1个元素整理成堆
    }
}

// 归并排序
int b[21]; // 为归并排序划定一个辅助数组
void Merge(int a[],int low ,int mid ,int high){
    // 表中 low - mid 和 mid - high 各自有序
    int i,j,k;
    for(int i = low ;i <= high ;i ++)
        b[i] = a[i]; // 将a中所有元素复制到b中    
    
    for(i = low , j = mid + 1 , k = i; i <= mid && j <= high ; k ++){
        if(b[i] <= b[j]) a[k] = b[i ++];
        else a[k] = b[j ++];
    }
    while(i <= mid) a[k ++] = b[i ++]; //若跳出循环后，仍有剩下的元素，将其复制到数组中
    while(j <= high) a[k ++] = b[j ++];
}

void MergeSort(int a[] , int low ,int high){
    if(low < high){
        int mid = (low + high) /2;
        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
    }
}

void log(){
    for(int i = 0;i < len ;i ++) cout << a[i] << " " ;
}


int main(){
    int x ; 
    cout << "1. 直接插入排序" << endl;
    cout << "2. 折半插入排序" << endl;
    cout << "3. 希尔排序" << endl;
    cout << "4. 冒泡排序" << endl;
    cout << "5. 快速排序" << endl;
    cout << "6. 简单选择排序" << endl;
    cout << "7. 堆排序" << endl;
    cout << "8. 归并排序" << endl;
    
    while(cin >> x){
        if(x == 1){
            cout <<"直接插入排序： ";
            InsertSort(a,len);
            log();
            cout << endl << endl;
        }else if(x == 2){
            cout <<"折半插入排序： ";
            InsertHalfSort(a,len);
            log();
            cout << endl << endl;
        }else if(x == 3){
            cout <<"希尔排序： ";
            ShellSort(a,len);
            log();
            cout << endl << endl;
        }else if(x == 4){
            cout <<"冒泡排序： ";
            BubbleSort(a,len);
            log();
            cout << endl << endl;
        }else if(x == 5){
            cout <<"快速排序： ";
            QuickSort(a,0,len-1);
            log();
            cout << endl << endl;
        }else if(x == 6){
            cout <<"简单选择排序： ";
            SelectSort(a,len);
            log();
            cout << endl << endl;
        }else if(x == 7){
            cout <<"堆排序： ";
            HeapSort(a,len);
            cout << endl << endl;
        }else if(x == 8){
            cout <<"归并排序： ";
            MergeSort(a,0,len-1);
            log();
            cout << endl << endl;
        }
    }
    


    return 0;
}

结尾

图，查找 两个 目前不准备写，应该会等到暑假再写