数据结构

引入

对于程序员来说，数据结构是一门非常重要的科目，但是也是一门比较难以掌握的科目，这里记录了自己在大学课程中的一些实践代码，方便以后回来看看自己写的数据结构有多烂……

线性表

顺序结构

线性表的顺序存储，C++代码实现如下

SeqlList.h，如果一个类使用了模板的话，不能将实现与定义拆分成两个文件，这个问题我卡了很久很久~

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
#pragma once
#include <iostream>
using namespace std;

const int MaxSize = 200;			// 设置顺序表最多能存储的元素的数量

template <typename DataType = int>	// 相当于Java的泛型，在C++叫模板
class SeqList
{
public:
	SeqList();						// 无参构造，建立空的顺序表
	SeqList(DataType a[], int n);	// 有参构造，建立长度为n的顺序表
	~SeqList();						// 析构函数，就是在对象销毁时会被执行
	int Length();					// 获取线性表的长度
	DataType Get(int i);			// 按位查找，查找第i个元素
	int Locate(DataType x);			// 按值查找，查找值为x的元素
	void Insert(int i, DataType x);	// 插入操作，在第i个位置插入值为x的元素
	DataType Delete(int i);			// 删除操作，删除第i个元素
	int Empty();					// 判断线性表是否为空
	void PrintList();				// 遍历操作，按序号依次输出各元素
private:
	DataType data[MaxSize];			// 存放数据元素的数组
	int length;						// 线性表的长度
};

// 无参构造，建立空的顺序表
template <typename DataType>
SeqList<DataType>::SeqList() {
	this->length = 0;
};

// 有参构造，建立长度为n的顺序表
template <typename DataType>
SeqList<DataType>::SeqList(DataType a[], int n) {
	if (n > MaxSize) throw "参数非法";
	for (int i = 0; i < n; i++) {
		this->data[i] = a[i];
	}
	this->length = n;
}

// 析构函数，就是在对象销毁时会被执行
template <typename DataType>
SeqList<DataType>::~SeqList() {
	cout << "被销毁了" << endl;
}

// 获取线性表的长度
template <typename DataType>
int SeqList<DataType>::Length() {
	return this->length;
}

// 按位查找，查找第i个元素
template <typename DataType>
DataType SeqList<DataType>::Get(int i) {
	if (i < 1 || i > this->length) {
		throw "位置不存在";
	}
	return this->data[i - 1];
}

// 按值查找，查找值为x的元素
// 0：没找到
template <typename DataType>
int SeqList<DataType>::Locate(DataType x) {
	for (int i = 0; i < length; i++) {
		if (this->data[i] == x) {
			return i + 1;
		}
	}
	return 0;
}

// 插入操作，在第i个位置插入值为x的元素
template <typename DataType>
void SeqList<DataType>::Insert(int i, DataType x) {
	if (length >= MaxSize) throw "已满";
	if (i < 1 || i > length + 1) throw "位置错误";
	for (int j = length; j >= i - 1; j--) {
		this->data[j + 1] = this->data[j];
	}
	this->data[i - 1] = x;
	this->length++;
}

// 删除操作，删除第i个元素
template <typename DataType>
DataType SeqList<DataType>::Delete(int i) {
	if (i < 1 || i > length) throw "位置错误";

	DataType del = this->Get(i);

	for (int j = i-1; j < length - 1; j++) {
		this->data[j] = this->data[j + 1];
	}

	this->length--;

	return del;
}

// 判断线性表是否为空
template <typename DataType>
int SeqList<DataType>::Empty() {
	return this->length ? 0 : 1;
}

// 遍历操作，按序号依次输出各元素
template <typename DataType>
void SeqList<DataType>::PrintList() {
	if (this->Empty()) {
		cout << "{}" << endl;
		return;
	}

	int i = 0;

	cout << "{";
	for (; i < length - 1; i++) {
		cout << this->data[i] << ",";
	}
	cout << this->data[i] << "}" << endl;
}

Main.cpp，做了个菜单，自我感觉良好

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
#include <iostream>
#include "SeqList.h"

using namespace std;

// 菜单
template <typename DataType = int>
void Menu(int choose, SeqList<>* list);
// 清除控制台（未使用）
void Clear();

int main() {
	SeqList<> list;
	int choose = -1;

	while (choose) {
		cout << "--------------------------------" << endl;
		cout << "元素[" << list.Length() << "]个|最大容量[" << MaxSize << "]个|顺序表状态";
		list.PrintList();
		cout << "1、插入一个数字" << endl;
		cout << "2、指定位置插入一个数字" << endl;
		cout << "3、获取某个数的具体位置" << endl;
		cout << "4、获取一个具体位置的数" << endl;
		cout << "5、删除一个指定位置的数" << endl;
		cout << "0、退出演示" << endl;
		cout << "请输入对应服务编号：";
		cin >> choose;
		try {
			Menu(choose, &list);
		}
		catch (const char * e) {
			cout << "出错啦，错误消息：" << e << endl;
		}
		cout << endl << "--------------------------------" << endl;
	}
}

// 菜单
template <typename DataType = int>
void Menu(int choose, SeqList<>* list) {
	int in_1 = 0, in_2 = 0, temp_1 = 0;
	switch (choose) {
		// 插入一个数字
	case 1:
		cout << "请输入要插入的数字：";
		cin >> in_1;
		list->Insert(list->Length() + 1, in_1);
		break;
		// 指定位置插入一个数字
	case 2:
		cout << "请输入指定位置与要插入的数字：";
		cin >> in_1 >> in_2;
		list->Insert(in_1, in_2);
		break;
		// 获取某个数的具体位置
	case 3:
		cout << "请输入要查询的数：";
		cin >> in_1;
		temp_1 = list->Locate(in_1);
		if (temp_1) {
			cout << "所查数第一次出现的位置是：" << temp_1 << endl;
		}
		else {
			cout << "没有查到哦~" << endl;
		}
		break;
		// 获取一个具体位置的数
	case 4:
		cout << "请输入要查找的位置：";
		cin >> in_1;
		temp_1 = list->Get(in_1);
		cout << "所在位置的数是：" << temp_1 << endl;
		break;
		// 删除一个指定位置的数
	case 5:
		cout << "请输入要删除的位置：";
		cin >> in_1;
		list->Delete(in_1);
		break;
	case 0:
		cout << "感谢体验，再见~" << endl;
		break;
	default:
		cout << "输入有误" << endl;
	}
}

// 清除屏幕（未使用）
void Clear()
{
	cout << "\x1B[2J\x1B[H";
}

运行效果

image-20230317232746299

image-20230317232856469

image-20230317232916272

单链表

单链表有头插法和尾插法的说法，案例代码具体体现在链表的有参初始工作中

LinkList.h

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
#pragma once
#include <iostream>
using namespace std;

// 定义单链表的结点
template <typename DataType = int>
struct Node {
	DataType data;
	Node<DataType>* next;
};

template <typename DataType = int>	// 相当于Java的泛型，在C++叫模板
class LinkList
{
public:
	LinkList();						// 无参构造，建立空的顺序表
	LinkList(DataType a[], int n);	// 有参构造，建立长度为n的顺序表
	~LinkList();						// 析构函数，就是在对象销毁时会被执行
	int Length();					// 获取线性表的长度
	DataType Get(int i);			// 按位查找，查找第i个结点
	int Locate(DataType x);			// 按值查找，查找值为x的结点
	void Insert(int i, DataType x);	// 插入操作，在第i个位置插入值为x的结点
	DataType Delete(int i);			// 删除操作，删除第i个结点
	int Empty();					// 判断线性表是否为空
	void PrintList();				// 遍历操作，按序号依次输出各结点
private:
	Node<DataType>* header;			// 单链表的头结点
};

// 无参构造，建立只有头节点的单链表
template <typename DataType>
LinkList<DataType>::LinkList() {
	this->header = new Node<DataType>;
	this->header->next = nullptr;
}

// 有参构造，建立长度为n的顺序表，头插法
template <typename DataType>
LinkList<DataType>::LinkList(DataType a[], int n) {
	this->header = new Node<DataType>;
	this->header->next = nullptr;
	Node<DataType>* temp = nullptr;
	for (int i = 0; i < n; i++) {
		temp = this->header->next;
		this->header->next = new Node<DataType>;
		this->header->next->data = a[i];
		this->header->next->next = temp;
	}
}

//// 有参构造，建立长度为n的顺序表，尾插法
//template <typename DataType>
//LinkList<DataType>::LinkList(DataType a[], int n) {
//	this->header = new Node<DataType>;
//	Node<DataType>* temp = this->header;
//	for (int i = 0; i < n; i++) {
//		temp->next = new Node<DataType>;
//		temp->next->data = a[i];
//		temp = temp->next;
//	}
//	temp->next = nullptr;
//}

// 析构函数，就是在对象销毁时会被执行
template <typename DataType>
LinkList<DataType>::~LinkList() {
	cout << "被销毁了" << endl;
}

// 获取线性表的长度
template <typename DataType>
int LinkList<DataType>::Length() {
	int cnt = 0;
	Node<DataType>* temp = this->header;
	while (temp->next != nullptr) {
		temp = temp->next;
		cnt++;
	}
	return cnt;
}

// 按位查找，查找第i个结点
template <typename DataType>
DataType LinkList<DataType>::Get(int i) {
	if (i < 1 || i > this->Length()) {
		throw "位置不存在";
	}
	Node<DataType>* temp = this->header;
	for (int j = 0; j < i; j++) {
		temp = temp->next;
	}
	return temp->data;
}

// 按值查找，查找值为x的结点
// 0：没找到
template <typename DataType>
int LinkList<DataType>::Locate(DataType x) {
	Node<DataType>* temp = header;
	for (int i = 0; i < this->Length(); i++) {
		temp = temp->next;
		if (temp->data == x) {
			return i + 1;
		}
	}
	return 0;
}

// 插入操作，在第i个位置插入值为x的结点
template <typename DataType>
void LinkList<DataType>::Insert(int i, DataType x) {
	if (i < 1 || i > this->Length() + 1) throw "位置错误";

	Node<DataType>* temp = header, *new_node = new Node<DataType>;
	for (int j = 0; j < i - 1; j++) {
		temp = temp->next;
	}
	new_node->data = x;
	new_node->next = temp->next;
	temp->next = new_node;
}

// 删除操作，删除第i个结点
template <typename DataType>
DataType LinkList<DataType>::Delete(int i) {
	if (i < 1 || i > this->Length()) throw "位置错误";

	DataType del = this->Get(i);

	Node<DataType>* node = header, *temp = nullptr;
	for (int j = 0; j < i - 1; j++) {
		node = node->next;
	}
	temp = node->next;
	node->next = node->next->next;
	delete(temp);

	return del;
}

// 判断线性表是否为空
template <typename DataType>
int LinkList<DataType>::Empty() {
	if (this->header->next == nullptr) {
		return 1;
	}
	return 0;
}

// 遍历操作，按序号依次输出各结点
template <typename DataType>
void LinkList<DataType>::PrintList() {
	if (this->Empty()) {
		cout << "{}" << endl;
		return;
	}

	Node<DataType>* temp = header->next;

	cout << "{" << temp->data;
	while (temp->next != nullptr) {
		temp = temp->next;
		cout << "," << temp->data;
	}
	cout <<  "}" << endl;
}

Main.h

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
#include <iostream>
#include "LinkList.h"

using namespace std;

// 菜单
template <typename DataType = int>
void Menu(int choose, LinkList<>* list);
// 清除控制台（未使用）
void Clear();

int main() {
	int init[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
	LinkList<> list(init, 8);
	int choose = -1;

	while (choose) {
		cout << "--------------------------------" << endl;
		cout << "元素[" << list.Length() << "]个|单链表状态";
		list.PrintList();
		cout << "1、插入一个数字" << endl;
		cout << "2、指定位置插入一个数字" << endl;
		cout << "3、获取某个数的具体位置" << endl;
		cout << "4、获取一个具体位置的数" << endl;
		cout << "5、删除一个指定位置的数" << endl;
		cout << "0、退出演示" << endl;
		cout << "请输入对应服务编号：";
		cin >> choose;
		try {
			Menu(choose, &list);
		}
		catch (const char* e) {
			cout << "出错啦，错误消息：" << e << endl;
		}
		cout << endl << "--------------------------------" << endl;
	}
}

// 菜单
template <typename DataType = int>
void Menu(int choose, LinkList<>* list) {
	int in_1 = 0, in_2 = 0, temp_1 = 0;
	switch (choose) {
		// 插入一个数字
	case 1:
		cout << "请输入要插入的数字：";
		cin >> in_1;
		list->Insert(list->Length() + 1, in_1);
		break;
		// 指定位置插入一个数字
	case 2:
		cout << "请输入指定位置与要插入的数字：";
		cin >> in_1 >> in_2;
		list->Insert(in_1, in_2);
		break;
		// 获取某个数的具体位置
	case 3:
		cout << "请输入要查询的数：";
		cin >> in_1;
		temp_1 = list->Locate(in_1);
		if (temp_1) {
			cout << "所查数第一次出现的位置是：" << temp_1 << endl;
		}
		else {
			cout << "没有查到哦~" << endl;
		}
		break;
		// 获取一个具体位置的数
	case 4:
		cout << "请输入要查找的位置：";
		cin >> in_1;
		temp_1 = list->Get(in_1);
		cout << "所在位置的数是：" << temp_1 << endl;
		break;
		// 删除一个指定位置的数
	case 5:
		cout << "请输入要删除的位置：";
		cin >> in_1;
		list->Delete(in_1);
		break;
	case 0:
		cout << "感谢体验，再见~" << endl;
		break;
	default:
		cout << "输入有误" << endl;
	}
}

// 清除屏幕（未使用）
void Clear()
{
	cout << "\x1B[2J\x1B[H";
}

运行效果和顺序表差不多，就不过多展示了

image-20230318123337905

顺序栈

栈结构就是先入后出，后入先出，使用顺序栈实现四则运算

MyMath.h

1
2
3
4
5
6
7
#pragma once

// 判断运算符优先级
int Precedence(char op);

// 根据二元运算符运算
float Operate(float left, float right, char op);

SeqStack.h

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

using namespace std;

const int StackSize = 10;

template <typename DataType = int>
class SeqStack {
public:
	SeqStack();					// 构造函数
	~SeqStack();				// 析构函数
	void Push(DataType x);		// 入栈操作
	DataType Pop();				// 出栈操作
	DataType GetTop();			// 去栈顶元素
	int Empty();				// 判断栈是否为空
private:
	DataType data[StackSize];	// 存放栈元素的数组
	int top;					// 栈顶元素在数组中的下标
};

// 构造函数
template <typename DataType>
SeqStack<DataType>::SeqStack() {
	this->top = -1;	// 初始化栈顶元素下标
}

// 析构函数
template <typename DataType>
SeqStack<DataType>::~SeqStack() {

}

// 入栈
template <typename DataType>
void SeqStack<DataType>::Push(DataType x) {
	if (this->top == StackSize - 1) throw "栈溢出";
	this->data[++top] = x;
}

// 出栈
template <typename DataType>
DataType SeqStack<DataType>::Pop() {
	return this->data[this->top--];
}

// 取栈顶
template <typename DataType>
DataType SeqStack<DataType>::GetTop() {
	return this->data[this->top];
}

// 判断栈是否为空
template <typename DataType>
int SeqStack<DataType>::Empty() {
	return (this->top == -1) ? 1 : 0;
}

MyMath.cpp

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
#include "MyMath.h"

// 判断运算符优先级
int Precedence(char op) {
	switch (op) {
	case '(':
		return 0;
	case '#':
		return 1;
	case '=':
		return 1;
	case '+':
		return 2;
	case '-':
		return 2;
	case '*':
		return 3;
	case '/':
		return 3;
	case ')':
		return 4;
	default:
		throw "不支持的运算符";
	}
}

// 根据二元运算符运算
float Operate(float left, float right, char op) {
	switch (op) {
	case '+':
		return left + right;
	case '-':
		return left - right;
	case '*':
		return left * right;
	case '/':
		return left / right;
	default:
		throw "不支持的运算符";
	}
}

Main.cpp

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
#include "SeqStack.h"
#include "MyMath.h"
#include <string>

using namespace std;

int main() {
	string allOps = "#+-*/=()", userIn = "";	// 定义所有支持的运算符与用户输入
	SeqStack<float> nums;						// 用于存储运算数
	SeqStack<char> ops;						// 用于存储运算符
	char op = '\0';
	float num = 0, left = 0, right = 0;		// 用于存储程序会产生的数字
	ops.Push('#');							// 将结束符号压入栈中，方便优先级比较
	
	cout << "请输入你的表达式\n每次输入[运算数]or[运算符]" << endl;
	do {
		if (userIn != "=") {
			cout << "你的输入：";
			cin >> userIn;
		}

		// 判断左括号
		if (userIn == "(") {
			ops.Push('(');
			continue;
		}

		// 判断是否为运算符
		if (allOps.find(userIn) == string::npos) {
			// 不是运算符则为数字，转为数字并压入数字栈
			num = stof(userIn);	// 转为数字
			nums.Push(num);		// 将数字压入数字栈中
			continue;
		}

		// 判断右括号
		if (userIn == ")") {
			while ((op = ops.Pop()) != '(') {
				right = nums.Pop();
				left = nums.Pop();
				nums.Push(Operate(left, right, op));
			}
			continue;
		}

		// 判断运算符优先级
		if (Precedence(ops.GetTop()) >= Precedence(userIn[0])) {
			// 如果新运算的优先级比栈中低则先弹栈进行运算
			right = nums.Pop();
			left = nums.Pop();
			nums.Push(Operate(left, right, ops.Pop()));	// 将运算结果压入数字栈中
			// 将用户输入的运算符压入运算符栈中
			if (userIn != "=") {
				ops.Push(userIn[0]);
			}						
			continue;
		}

		// 如果新运算的优先级比栈中高则直接压入运算符栈
		if (userIn != "=") {
			ops.Push(userIn[0]);
		}
	} while (userIn != "=" || ops.GetTop() != '#');

	cout << "计算结果：" << nums.GetTop();

	return 0;
}

运行效果

image-20230406202708597

队列

先入先出，后入后出，这里使用循环队列完成了一个门诊看病的案例

CirQueue.h

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
#pragma once

const int QueueSize = 50;		// 设置循环队列的长度

template <typename DataType>
class CirQueue {
public:
	CirQueue();					// 构造函数
	~CirQueue();				// 析构函数
	void EnQueue(DataType x);	// 入队操作，将元素x入队
	DataType DeQueue();			// 出队操作
	DataType GetHead();			// 取队头元素
	int Empty();				// 判空
	int Size();					// 长度
private:
	DataType data[QueueSize];	// 数据
	int start, end, length;		// 队头和队尾以及长度
};

// 长度
template <typename DataType>
int CirQueue<DataType>::Size() {
	return length;
}

// 构造函数
template <typename DataType>
CirQueue<DataType>::CirQueue() {
	// 将头尾都指向最后一个位置
	this->start = QueueSize - 1;
	this->end = QueueSize - 1;
	this->length = 0;	// 长度为0
}

// 析构函数
template <typename DataType>
CirQueue<DataType>::~CirQueue() {

}

// 入队
template <typename DataType>
void CirQueue<DataType>::EnQueue(DataType x) {
	if ((this->end + 1) % QueueSize == this->start) throw "满";
	this->data[this->end = ((this->end + 1) % QueueSize)] = x;
	this->length++;
}

// 出队
template <typename DataType>
DataType CirQueue<DataType>::DeQueue() {
	this->length--;
	if (this->start == this->end) throw "空队";
	
	return this->data[this->start = (this->start + 1) % QueueSize];
}

// 取队头
template <typename DataType>
DataType CirQueue<DataType>::GetHead() {
	if (this->start == this->end) throw "空队";
	return this->data[(this->start + 1) % QueueSize];
}

// 判空
template <typename DataType>
int CirQueue<DataType>::Empty() {
	return length ? 0 : 1;
}

Main.cpp

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
#include "CirQueue.h"
#include <iostream>
#include <string>

using namespace std;

// 用于存储病人信息的结构体
struct Sick {
	string id;	// 编号
	string name;// 姓名
};

/*
	处理菜单选项，并返回进入门诊的人
	choice：选项
	sicks：排队的病人
	current：当前正在门诊的病人
	return：返回处理后正在门诊的病人
*/ 
Sick* choiceHandle(int choice, CirQueue<Sick*>* sicks, Sick* current);

int main() {
	int userIn = 0;
	CirQueue<Sick*>* sicks = new CirQueue<Sick*>;
	struct Sick* sick = nullptr;
	
	do {
		try {
			cout << "----------输入数字选择对应功能----------" << endl;
			if (sick == nullptr) {
				cout << "----------------诊室空闲----------------" << endl;
			}
			else {
				cout << "---编号[" + sick->id + "]|姓名[" + sick->name + "]正在门诊-----" << endl;
			}
			if (sicks->Size()) {
				cout << "---请编号[" + sicks->GetHead()->id + "]|姓名[" + sicks->GetHead()->name + "]做好准备-----" << endl;
			}
			cout << "---------当前还有[" << sicks->Size() << "]人正在排队----------" << endl;
			cout << "--------------1、录入病人---------------" << endl;
			cout << "--------------2、呼叫病人---------------" << endl;
			cout << "--------------0、退出系统---------------" << endl;
			cout << "请选择：";
			cin >> userIn;
			sick = choiceHandle(userIn, sicks, sick);
			cout << "----------------------------------------" << endl;
		}
		catch (const char* ex) {
			cout << "错误的操作" << endl;
			exit(-1);
		}
	} while (userIn);

	return 0;
}

/*
	处理菜单选项，并返回进入门诊的人
	choice：选项
	sicks：排队的病人
	current：当前正在门诊的病人
	return：返回处理后正在门诊的病人
*/
Sick* choiceHandle(int choice, CirQueue<Sick*>* sicks, Sick* current) {
	struct Sick* sick;
	switch (choice) {
	case 0:
		cout << "再见" << endl;
		return nullptr;
	case 1:
		cout << "请输入编号及姓名" << endl;
		sick = new Sick;
		cin >> sick->id >> sick->name;
		sicks->EnQueue(sick);
		return current;
	case 2:
		if (sicks->Size()) {
			sick = sicks->DeQueue();
		}
		else {
			cout << "无人等待" << endl;
			sick = nullptr;
		}
		return sick;
	default:
		cout << "不支持的选项" << endl;
		return current;
	}
}

运行截图

image-20230406203204850

image-20230406203226150

模式匹配

字符串特有的功能

BF

暴力算法

Main.cpp

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
#include <iostream>
#include <stdlib.h>

using namespace std;

/**
* 获取子串在主串中第一次出现的起始位置，不存在则返回0
* param s 主串
* param t 子串
* return 返回子串在主串中第一次出现的下标（从1起标），不存在则返回0
*/
int BF(char* s, char* t) {
    int start = 0;                              // 设置主串每次匹配的起始位置
    int i = 0, j = 0;                           // i记录主串某次匹配的位置变动，j记录子串匹配的位置变动
    /*
        当主串下标不为空时说明主串还没匹配完，
        当子串下标不为空时说明子串还没被匹配完过
        当上面两个条件同时满足才执行循环
    */
    while ((s[i] != '\0') && (t[j] != '\0')) {
        /*
            如果在某次匹配中，子串能与主串匹配上就一直往下匹配，
            直到主串到底，或者子串到底
            主串到底说明已经没法匹配了
            子串到底说明找到了子串在主串中的位置
        */
        if (s[i] == t[j]) {
            i++;
            j++;
        }
        /*
            如果某次匹配没有匹配上，就说明主串的这个位置匹配不上，
            匹配的主串起始位置就往下走一位，
            并将记录主串某次匹配的位置更新为主串新的匹配起始位置，
            记录子串匹配的位置初始化为子串的第一个字符位置
        */
        else {
            start++; 
            i = start; 
            j = 0; 
        }
    }

    /*
        当匹配完成后如果子串的下标匹配记录为\0，
        则说明子串匹配成功了，就返回最后这次匹配的主串起始位置+1（方法返回从1起标）。
        如果子串下标匹配记录不为\0，说明是主串的下标匹配记录为\0，
        表明主串已经匹配到最后一个字符了，也没有匹配到子串，就返回0，表示没有找到子串
    */
    if (t[j] == '\0') {
        return start + 1; 
    }
    else { 
        return 0;
    }

}

int main() {
    // 给两个字符指针分配内存，方便存字符串
    char *s = (char*) malloc(1024), * t = (char*)malloc(1024);

    // 输入
    cout << "请输入主串：";
    cin >> s;
    cout << "请输入子串：";
    cin >> t;

    if (int index = BF(s,t)) {
        cout << "子串第一次在主串中出现的下标是：" << index;
    }
    else {
        cout << "没有匹配到子串";
    }

    // 内存释放
    free(s);
    free(t);

	return 0;
}

运行截图

image-20230406203523753

KMP

对我来说很烧脑，我这里的实现有问题，但是能力只能先这样了

Main.cpp

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
#include <stdlib.h>
#include <iostream>

using namespace std;

// 用于装载数组
struct Arr {
	int* data;	// 数组指针
	int length;	// 数组长度
};
/*
	获取子串的next数组
	param t 子串的首地址
	return 返回next数组
*/
Arr* getNext(char* t);

/*
	通过KMP算法获取子串在主串中第一次出现的下标（从0起标），未找到返回-1
	param s 主串
	param t 子串
	return 子串在主串中第一次出现的下标（从0起标），未找到返回-1
*/
int KMP(char* s, char* t);

int main() {
	// 创建字符串接收变量
	char* s = (char*) malloc(1024);
	char* t = (char*)malloc(1024);

	// 终端输入
	cout << "请输入主串：";
	cin >> s;
	cout << "请输入子串：";
	cin >> t;

	// 输出结果
	int index = KMP(s, t);
	if (index == -1) {
		cout << "没有在主串中找到子串";
	}
	else {
		cout << "子串在主串中第一次出现的下标为：" << index;
	}
	
	// 释放内存
	free(s);
	free(t);

	return 0;
}

/*
	获取子串的next数组
	param t 子串的首地址
	return 返回next数组
*/
Arr* getNext(char* t) {
	Arr* next = new Arr{ nullptr,0 };

	// 计算数组长度
	while (t[next->length] != '\0') {
		next->length++;
	}

	// 给next数组分配空间
	next->data = (int*)malloc(sizeof(int) * (next->length));

	next->data[0] = 0;
	next->data[1] = 0;

	// 循环对应子串的每个字符下标
	for (int i = 2; i < next->length; i++) {
		int max = i - 1;	// 当前子串字符下标需要比对的前后缀的最长长度
		next->data[i] = 0;	// 假想没有前后缀
		// 根据前后缀最大长度，从最大前后缀一直比较到最小前后缀，找到下次对比子串的起始指针
		for (int j = max; j >= 1; j--) {
			int flag = true;
			// 比较前后缀
			for (int k = 0; k < j; k++) {
				// 依次比较前后缀，如果没配对就表示本次循环的前后缀长度不是最长的
				if (t[k] != t[max - j + k + 1]) {
					flag = false;
					break;
				}
			}
			// 如果flag为真，则写入偏移量，并结束找最大前后缀
			if (flag) {
				// 将最大前后缀长度赋值给next数组并退出
				next->data[i] = j;
				break;
			}
		}
	}

	return next;
}

/*
	通过KMP算法获取子串在主串中第一次出现的下标（从0起标），未找到返回-1
	param s 主串
	param t 子串
	return 子串在主串中第一次出现的下标（从0起标），未找到返回-1
*/
int KMP(char* s, char* t) {
	// 获取子串的next数组
	Arr* next = getNext(t);
	// 分别为主串的比较下标记录与子串的比较下标记录
	int start = 0, t_i = 0;

	// 当主串比较到完，或者子串比较完就终止循环
	// 子串比较完说明找到了子串的下标，主串比较完说明没有找到
	while (s[start] != '\0' && t[t_i] != '\0') {
		if (s[start] == t[t_i]) {
			t_i++;
		}
		else {
			t_i = next->data[t_i + 1];
		}
		start++;
	}

	// 子串比较完说明找到了子串的下标
	if (t[t_i] == '\0') {
		// 返回子串第一次出现的下标
		// 由于主串下标在比较时会往后走，所以返回时要减去子串的长度
		return start - next->length;
	}

	// 子串没有比较完说明没有在主串中找到子串，返回-1
	return -1;
}

运行截图

image-20230406203822526

扩展

  • 双向链表：一个结点包含前驱与后继的结点指针
  • 循环链表：
    • 单链表：尾结点的后继结点指针指向头结点
    • 双向链表：头结点的前驱结点指针指向尾结点，尾结点的后继结点指针指向头结点