数据结构

InsectMk2023-03-172023-04-06

数据结构

引入

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

线性表

顺序结构

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

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

#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，做了个菜单，自我感觉良好

#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";
}

运行效果

单链表

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

LinkList.h

#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

#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";
}

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

顺序栈

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

MyMath.h

#pragma once

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

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

SeqStack.h

#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

#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

#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;
}

运行效果

队列

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

CirQueue.h

#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

#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;
	}
}

运行截图

模式匹配

字符串特有的功能

BF

暴力算法

Main.cpp

#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;
}

运行截图

KMP

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

Main.cpp

#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;
}

运行截图

扩展

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