[数据结构与算法]数据结构与算法---基本概念及代码模板合集

零.时间复杂度分析

1.时间复杂度概念

什么是时间复杂度

时间复杂度是一个函数，它定性描述该算法的运行时间。

什么是大O

算法导论给出的解释：大O用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。

但是业内的一个默认规定，这里说的O代表的就是一般情况，而不是严格的上界。

面试中说道算法的时间复杂度是多少指的都是一般情况

为什么时间复杂度都是省略常数项系数？

因为大O就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度，这个数据量也就是常数项系数已经不起决定性作用的数据量。

所以我们说的时间复杂度都是省略常数项系数的，是因为一般情况下都是默认数据规模足够的大，基于这样的事实，给出的算法时间复杂的的一个排行如下所示：

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)立方阶 < O(2^n)指数阶

2.时间复杂度的化简

我们计算时间复杂度的时候往往是一个复杂的表达式，如下

O(2*n^2 + 10*n + 1000)

其实两步我们就可以化简完毕

①去掉常数项以及常数系数

O(n^2 + n)

②只保留最高项

O(n^2)

这样就是我们最后要的结果了。

3.常见排序算法时间复杂度分析

一.线性表

1.顺序表

// 顺序表C++.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include <iostream>
#include<stdio.h>
using namespace std;

typedef int ElemType;
#define OK 1
#define ERROR 0
//Status是状态码，标识着函数执行结果的状态，OK或者ERROR
typedef int Status;

class SqList {
private:
    int MaxSize;        //数组最大长度
    int size;            //当前实际长度（区别索引），所以size=0时为空表
    ElemType* list;          //指向数组的指针
public:
    SqList();
    ~SqList();

    int listSize();             //获取顺序表实际长度
    Status listInit(int n);     //初始化顺序表，输入n个数，并依次存入顺序表中从0开始的位置
    Status listInsert(int i, ElemType s); //插入一个元素到位置i
    Status multiInsert(int i, int n, ElemType* item); //实现在第i个位置，连续插入来自数组item的n个数据，即从位置i开始插入多个数据。
    Status multiDel(int i, int n);//实现从第i个位置开始，连续删除n个数据，即从位置i开始删除多个数据。
    Status listDel(int i);      //删除一个元素
    Status listGet(int i);      //获取一个元素
    SqList listCombine(SqList& a, SqList& b);//合并两个顺序表并且排序
    ElemType* getListArr();          //返回数组
    void listMove(int d, int n);    //顺序表循环移位函数
    void listSort();            //排序
    void ClearList();          //清空栈内元素
    void display();             //打印所有栈内元素，从索引0开始顺序打印
};
SqList::SqList() {    //初始化
    size = 0;
    MaxSize = 99;       //默认最大长度为99
    list = new int[MaxSize];
}
SqList::~SqList() {
    /*delete[]list;*/
}

int SqList::listSize() {
    return size;
}
Status SqList::listInit(int n) {
    for (int i = 0; i < n; i++)
    {
        cin >> list[i];
    }
    size = n;
    return OK;
}
Status SqList::listInsert(int i, ElemType s) {
    if ((i > 0) && (i <= (size + 1)))
    {
        for (int k = size; k >= i; k--)
        {
            list[k] = list[k - 1];
        }
        list[i - 1] = s;
        size++;
        display();
        return OK;
    }
    else {
        cout << "error" << endl;
        return ERROR;
    }

}
Status SqList::multiInsert(int i, int n, ElemType* item) {
    if ((i > 0) && (i <= (size + 1)))
    {
        for (int k = size; k >= i; k--)
        {
            list[k+n-1] = list[k - 1];
        }
        for (int k =i-1,flag=0; flag < n; k++,flag++)
        {
            list[k] = item[flag];
        }
        size+=n;
        return OK;
    }
    else {
        cout << "error" << endl;
        return ERROR;
    }

}
Status SqList::listDel(int i) {
    if ((i > 0) && (i <= (size)))
    {
        for (int k = i-1; k <size; k++)
        {
            list[k] = list[k + 1];
        }
        size--;
        display();
        return OK;
    }

    cout << "error" << endl;
    return ERROR;
}
Status SqList::multiDel(int i,int n) {
    if ((i > 0) && (i <= size))
    {
        size -= n;
        for (int k = i - 1; k < size; k++)
        {
            list[k] = list[k + n];
        }
        display();
        return OK;
    }

    cout << "error" << endl;
    return ERROR;
}
Status SqList::listGet(int i)
{
    if ((i > 0) && (i <= size)) {
        cout << list[i - 1] << endl;
        return OK;
    }
    cout << "error" << endl;
    return ERROR;
}
void SqList::ClearList() {
    size = 0;           //这里不需要释放空间，直接size置为0即可
}
void SqList::display() {
    if (size == 0)
        cout << "当前为空表！！！" << endl;
    else
    {
        //cout << "当前顺序表内元素有：";
        for (int i = 0; i < size ; i++)
        {
            cout << list[i] << " ";
        }
        cout << endl;
    }
}
//顺序表排序函数
void SqList::listSort()
{
    for (int i = 0; i < size - 1; i++)
    {
        for (int i = 0; i < size - 1; i++)
        {
            if (list[i] > list[i + 1])
            {
                int temp;
                temp = list[i];
                list[i] = list[i + 1];
                list[i + 1] = temp;
            }
        }
    }
}
ElemType* SqList::getListArr() {
    return list;
}
void SqList::listMove(int d, int n)
{
    int* temp = new int[size];
    if (d == 0)
    {
        for (int i = 0; i < size; i++)
        {
            temp[(size  - (n - i)) % size] = list[i];
        }
    }
    else if (d == 1)
    {
        for (int i = 0; i < size; i++)
        {
            temp[(size + (i + n)) % size] = list[i];
        }
    }
    list = temp;
}

SqList SqList::listCombine(SqList& a, SqList& b)
{
    SqList res1;
    res1.multiInsert(1, a.listSize(), a.getListArr());//这里的方法，第三个参数是list指针，会导致析构的时候重复释放list指针
    res1.multiInsert(2, b.listSize(), b.getListArr());//这里的方法，第三个参数是list指针，会导致析构的时候重复释放list指针
    res1.listSort();
    res1.display();
    return res1;
}

int main()
{

    SqList test1;
    int n1,a,b;
    cin >> n1;
    test1.listInit(n1);
    test1.display();
    cin >> a >> b;
    test1.listMove(a, b);
    test1.display();
    cin >> a >> b;
    test1.listMove(a, b);
    test1.display();
    return 0;
}

2.单链表

#include<stdio.h>
#include<iostream>
using namespace std;

typedef int ElemType;
#define OK 1
#define ERROR 0
//Status是状态码，标识着函数执行结果的状态，OK或者ERROR
typedef int Status;

//单链表结点类
class Node {
public:
	ElemType data;  //节点数据
	Node* next;		//指向下一节点指针

	Node() {		//构造函数初始化头节点
		next = NULL;
		data = 0;
	}
};

//单链表类
class LinkList {
public:
	Node* head;		//头结点指针
	int len;		//链表长度
	LinkList();		//构造函数
	~LinkList();	//析构函数


	Node* GetIndex(int i);						//获取第i个节点的前一个节点指针（用于交换节点
	Status Swap(int pa,int pb);					//交换两节点位置
	Status GetElem(int i);						//查找第i个元素并打印
	Status ListInsert(int i, ElemType e);		//在第i个节点之前插入新元素e，链表长度+1（将元素插入第i个节点）
	Status ListElemDelete(int i);				//删除第i个节点，链表长度-1
	void CreatListHead(ElemType e);				//头插法
	void CreatListTail(ElemType e);				//尾插法
	Status ClearList();							//删除链表，链表已经存在，将其置为空表
	void display();								//打印整个单链表	
	LinkList merge(LinkList& La, LinkList& Lb); //合并两个链表
	void sort();								//排序
};

LinkList::LinkList() {
	head = new Node;
	len = 0;
}
LinkList::~LinkList() {

}
void LinkList::sort() {
	for (int i = 1; i <= len; i++)
	{
		for (int k = i; k <= len; k++)
		{
			if (GetIndex(i+1)->data > GetIndex(k+1)->data)
			{
				Swap(i, k);
			}
		}
	}
}

LinkList LinkList::merge(LinkList& La, LinkList& Lb) {
	LinkList res;
	Node* p = La.head;
	for (int i = 1; i <= La.len; i++)
	{
		p = p->next;
		res.ListInsert(i, p->data);
	}
	p = Lb.head;
	for (int i = 1; i <= Lb.len; i++)
	{
		p = p->next;
		res.ListInsert(i, p->data);
	}
	res.sort();
	return res;
}
Node* LinkList::GetIndex(int i) {
	int j = 1;			//计数器
	Node* p;
	p = head;			//指向链表的第一个节点
	while (p && j < i)	//p不为空或者计数器不等于i时，循环继续
	{
		p = p->next;	//让p指向下一个节点
		++j;
	}
	if (!p || j > i || i == 0) {
		return NULL;
	}
	else return p;
}
Status LinkList::Swap(int pa, int pb) {
	if (pa < 1 || pb<1 || pa>len || pb>len)
		return ERROR;
	Node* p1 = GetIndex(pa);
	Node* p2 = GetIndex(pb);
	//交换前继
	Node* temp = p1->next;
	p1->next = p2->next;
	p2->next = temp;
	//交换后继
	temp = p1->next->next;
	p1->next->next = p2->next->next;
	p2->next->next = temp;
	return  OK;
}
Status LinkList::GetElem(int i) {
	int j = 0;			//计数器
	Node* p;
	p = head;			//指向链表的第一个节点
	while (p && j < i)	//p不为空或者计数器不等于i时，循环继续
	{
		p = p->next;	//让p指向下一个节点
		++j;
	}
	if (!p || j > i || i == 0) {
		cout << "error" ;
		return ERROR;
	}
	cout << p->data << " ";
	return OK;
}
Status LinkList::ListInsert(int i, ElemType e) {
	int j;
	j = 1;
	Node* p, * s;
	p = head;
	while (p->next != nullptr && j < i) {		//寻找第i个节点
		p = p->next;
		++j;
	}
	if (!p || j < i || i == 0) {
		cout << "error" << endl;
		return ERROR;
	}
	s = new Node;				//创建新节点
	s->data = e;
	s->next = p->next;			//插入新节点
	p->next = s;
	len++;
	return OK;
}
Status LinkList::ListElemDelete(int i) {
	int j;
	Node* p, * q;
	p = head;
	j = 1;
	while (p->next && j < i)		//寻找第i个节点的前一个节点
	{
		p = p->next;
		++j;
	}
	if (!(p->next) || j >i||i==0) {
		cout << "error" << endl;
		return ERROR;
	}
	q = p->next;				//从链表中删除该节点
	p->next = q->next;
	delete q;					//系统回收该节点，释放内存
	len--;
	return OK;
}
void LinkList::CreatListHead(ElemType e) {
	Node* p;
	p = new Node;				//创建新节点
	p->data = e;
	p->next = head->next;		//在头结点后面插入新节点
	head->next = p;
	len++;
}
void LinkList::CreatListTail(ElemType e) {
	Node* p, * node;
	p = new Node;
	p = head;
	node = new Node;
	int j = 0;
	while (p->next && j < len)		//寻找最后一个节点
	{
		p = p->next;
		++j;
	}

	node->data = e;
	node->next = NULL;
	p->next = node;
	len++;
}
Status LinkList::ClearList() {
	Node* p, * q;
	p = head->next;		 //p指向第一个节点
	while (p)			 //没到表尾就一直循环，并且释放节点内存
	{
		q = p->next;
		delete p;
		p = q;
	}
	head->next = NULL;	//头指针指针域设为空
	len = 0;
	return OK;
}
void LinkList::display() {
	for (int i = 0; i < len; i++)
	{
		GetElem(i + 1);
	}
	cout << endl;
}


int main() {
	LinkList test1,test2;
	int n;
	ElemType data;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> data;
		test1.ListInsert(i + 1, data);
	}
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> data;
		test2.ListInsert(i + 1, data);
	}
	LinkList res = test1.merge(test1, test2);
	res.display();
	return 0;
}

3.循环链表

#include<stdio.h>
#include<iostream>
using namespace std;

typedef int ElemType;
#define OK 1
#define ERROR 0
//Status是状态码，标识着函数执行结果的状态，OK或者ERROR
typedef int Status;

//单链表结点类
class Node {
public:
	ElemType data;  //节点数据
	Node* next;		//指向下一节点指针

	Node() {		//构造函数初始化头节点
		next = NULL;
		data = 0;
	}
};

//单链表类
class LinkList {
public:
	Node* head;		//头结点指针
	Node* rear;     //尾节点指针
	int len;		//链表长度

	LinkList();		//构造函数
	~LinkList();	//析构函数

	Status GetElem(int i);						//查找第i个元素并打印
	Status ListInsert(int i, ElemType e);		//在第i个节点之前插入新元素e，链表长度+1（将元素插入第i个节点）
	Node* GetElemIndex(int i);					//查找并返回第i个结点的指针
	Status ListElemDelete(int i);				//删除第i个节点，链表长度-1
	void display();								//打印整个单链表	

};
LinkList::LinkList() {
	head = new Node;
	rear = new Node;//??????这里要注意，不能直接赋值next和data，除非rear=head像这样直接赋值指针*************************************
	rear->next = head;							//尾节点next指向头结点
	rear->data = head->data;		//获取尾节点数据域

	len = 0;
}
LinkList::~LinkList() {

}

Node* LinkList::GetElemIndex(int i) {
	int j = 1;			//计数器
	Node* p;
	p = head->next;			//指向链表的第一个节点
	while (p != head && j < i)	//p不为头结点或者计数器小于i时，循环继续
	{
		p = p->next;	//让p指向下一个节点
		++j;
	}
	if (!p || j > i)
		return ERROR;	//第i个元素不存在
	return p;
}


Status LinkList::GetElem(int i) {
	int j = 1;			//计数器
	Node* p;
	p = head->next;			//指向链表的第一个节点
	while (p!=head && j < i)	//p不为头结点或者计数器不等于i时，循环继续
	{
		p = p->next;	//让p指向下一个节点
		++j;
	}
	if (!p || j > i)
		return ERROR;	//第i个元素不存在
	cout << p->data << endl;
	return OK;
}

Status LinkList::ListInsert(int i, ElemType e) {
	int j;
	j = 1;
	Node* p, * s;
	p = head;
	while (p->next != head && j < i) {		//寻找第i个节点
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR;
	s = new Node;				//创建新节点
	s->data = e;
	s->next = p->next;			//插入新节点
	p->next = s;
	len++;
	rear->data = GetElemIndex(len)->data;  //更新尾指针
	return OK;
}
Status LinkList::ListElemDelete(int i) {
	int j;
	Node* p, * q;
	p = head->next;
	j = 1;
	while (p->next != head && j < i-1)		//寻找第i个节点的前一个节点
	{
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR;
	q = p->next;				//从链表中删除该节点
	p->next = q->next;
	delete q;					//系统回收该节点，释放内存
	len--;
	rear->data = GetElemIndex(len)->data;  //更新尾指针
	return OK;
}
void LinkList::display() {
	for (int i = 0; i < len; i++)
	{
		int k = GetElem(i + 1);
		if (k == 0) {
			cout << "display Error!";
		}
	}
}

int main() {
	LinkList test;
	int n;
	ElemType data;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> data;
		test.ListInsert(i + 1, data);
	}
	//test.ListElemDelete(2);
	test.display();
	cout << "尾结点数据域： "<<test.rear->data << endl;
	cout << "头结点数据域： "<<test.rear->next->data << endl;
	cout << "第一个结点数据域： "<<test.rear->next->next->data << endl;
	return 0;
}

4.双向链表

#include<iostream>
using namespace std;
//双向链表结点类
class ListNode
{
public:
	ListNode* front;  //前一个结点的指针
	int data;  //结点数据
	ListNode* next;  //下一个结点的指针
	//构造函数
	ListNode()
	{
		front = this;
		next = this;
		data = NULL;
	}
};
//双向链表类
class LinkList
{
public:
	ListNode* head;  //头结点指针
	int len;  //双向链表长度
	LinkList();
	void LL_add(int x);  //在双向链表末尾添加一个结点
	ListNode* LL_index(int i);  //返回第i个结点
	void LL_insert(int i, int item);  //将item插入双向链表的第i个结点
	void LL_del(int i);  //删除双向链表中的第i个结点
	void LL_display();  //打印输出双向链表所有结点
	void disPlayFB(int i);//打印i的前驱后继
};
//构造函数
LinkList::LinkList()
{
	head = new ListNode();
	len = 0;
}
//在双向链表末尾添加一个结点
void LinkList::LL_add(int x)
{
	ListNode* l = new ListNode();
	l->data = x;
	l->next = head;
	if (head->next == head)
	{
		l->front = head;
		head->next = l;
		head->front = l;
	}
	else
	{
		l->front = LL_index(len);
		LL_index(len)->next = l;
		head->front = l;
	}
	len++;
}
//返回第i个结点
ListNode* LinkList::LL_index(int i)
{
	if ((i <= 0) || (i > len))
	{
		cout << "index_error" << endl;
	}
	else
	{
		ListNode* p;
		p = head;
		for (int k = 1; k <= i; k++)
		{
			p = p->next;
		}
		return p;
	}
}
//将item插入双向链表的第i个结点
void LinkList::LL_insert(int i, int item)
{
	i = i - 1;
	if (i == len)
	{
		LL_add(item);
	}
	else if (i == 1)
	{
		if (len == 0)
		{
			LL_add(item);
		}
		else
		{
			ListNode* l = new ListNode();
			l->data = item;
			l->front = head;
			l->next = LL_index(1);
			LL_index(1)->front = l;
			head->next = l;
			len++;
		}
	}
	else
	{
		ListNode* l = new ListNode();
		l->data = item;
		l->next = LL_index(i);
		LL_index(i)->front = l;
		LL_index(i - 1)->next = l;
		l->front = LL_index(i - 1);
		len++;
	}
}
//删除双向链表中的第i个结点
void LinkList::LL_del(int i)
{
	if ((i <= 0) || (i > len))
	{
		cout << "del_error" << endl;
	}
	else
	{
		if (i == 1)
		{
			if (len == 1)
			{
				head->next = head;
				head->front = head;
			}
			else
			{
				head->next = LL_index(2);
				LL_index(2)->front = head;
			}
		}
		else if (i == len)
		{
			LL_index(i - 1)->next = head;
			head->front = LL_index(i - 1);
		}
		else
		{
			LL_index(i - 1)->next = LL_index(i + 1);
			LL_index(i)->front = LL_index(i - 1);
		}
		len--;
	}
}
//打印输出双向链表所有结点
void LinkList::LL_display()
{
	ListNode* p;
	p = head;
	if (p->next == head)
	{
		cout << "-";
	}
	while (p->next != head)
	{
		p = p->next;
		cout << p->data;
	}
	cout << endl;
}
void LinkList::disPlayFB(int i) {
	ListNode* p;
	p = head;
	while (p->next != head)
	{
		p = p->next;
		if (p->data == i) {
			if (p->front->data)
				cout << p->front->data << " ";
			if (p->next != head)
				cout << p->next->data << endl;
		}
		
	}
}
int main() {
	LinkList test;
	int n, m;
	int temp1,temp2;
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		cin >> temp1;
		test.LL_insert(i,temp1);
	}
	while (m--)
	{
		cin >> temp2;
		test.disPlayFB(temp2);
	}
	
}

5.学生宿舍管理系统

#include <list>
#include <map>
#include<stdio.h>
#include<iostream>
using namespace std;

//学生房间类定义 
class student {

public:
	string name;
	int id;
	student(string na, int i) {
		name = na; id = i;
	}
};

int main() {
	//已用宿舍链表
	list <student> stu;
	//可用宿舍链表
	list <int> empty;

	//初始化迭代器 
	list<int>::iterator i;
	list<student>::iterator j;

	//哈希表，用于查看房间有没有被占用
	map<int, int> hash;

	//初始化
	int n, number;
	cin >> n;
	string name;
	for (int i = 0; i < n; i++) {
		cin >> name >> number;
		stu.push_back(student(name, number));
		hash[number]=1;  //填充value，表示房间占用
	}
	for (int i = 101; i <= 120; i++) {
		if (!hash[i]) {
			empty.push_back(i);
		}
	}

	//房间分配收回操作 
	int m;
	string sign;
	cin >> m;
	while (m--) {
		cin >> sign;
		//分配房间
		if (sign == "assign") {
			cin >> name;
			int tmp = empty.front();
			for (j = stu.begin(); j != stu.end(); ) {
				//找到第一个比拿取房间id大的房间或到达末尾，插入到已用宿舍表 
				if (j->id > tmp ) {
					stu.insert(j, 1, student(name, tmp));
					break;
				}
				if (++j == stu.end()) {
					stu.insert(j, 1, student(name, tmp));
					break;
				}
			}
			empty.pop_front();
		}

		//返回房间
		if (sign == "return") {
			cin >> number;
			for (j = stu.begin(); j != stu.end(); j++) {
				if (j->id == number) {
					stu.erase(j);
					empty.push_back(number);
					break;
				}
			}
		}

		//输出已使用房间 
		if (sign == "display_used") {
			for (j = stu.begin(); j != stu.end();) {
				cout << j->name << "(" << j->id << ")";
				if (++j != stu.end()) cout << "-";
			}
			cout << endl;
		}

		//输出未使用房间 
		if (sign == "display_free") {
			for (i = empty.begin(); i != empty.end();) {
				cout << *i;
				if (++i != empty.end()) cout << "-";
			}
		}
	}
	return 0;
}

6.多项式相加

#include<stdio.h>
#include<iostream>
using namespace std;
//创建每个项的节点类
class Node {
public:
	int coe;	//系数
	int index;	//指数
	Node* next;
	Node() {
		next = NULL;
		coe = -1;
		index = -1;
	}
	Node(int coe1,int index1) {
		coe = coe1;
		index = index1;
		next = NULL;
	}

};
class list
{
public:
	Node* head;		//头结点指针
	int len;
	list();

	void pushBack(int coe1, int index1);//尾插法
	void disPlay();
	void disPlayItem(int i);		//打印第i个节点
};

list::list() {
	head = new Node;
	len = 0;
}
void list::pushBack(int coe1,int index1) {
	Node* p, * node;
	p = new Node;
	p = head;
	node = new Node(coe1, index1);
	int j = 0;
	while (p->next && j < len)		//寻找最后一个节点
	{
		p = p->next;
		++j;
	}
	p->next = node;
	len++;
}
void list::disPlay() {

	for (int i = 1; i <= len; i++)
	{
		disPlayItem(i);
	}
}
void list::disPlayItem(int i) {
	int j = 0;			//计数器
	Node* p;
	p = head;			//指向链表的第一个节点
	while (p && j < i)	//p不为空或者计数器不等于i时，循环继续
	{
		p = p->next;	//让p指向下一个节点
		++j;
	}
	if (!p || j > i || i == 0) {
		cout << "error";
	}
	if (p->coe != 0) {
		if (p->coe > 0)
			cout << p->coe;
		else
			cout << "(" << p->coe << ")";
		if (p->index != 0)
		{
			if(p->index > 0)
				cout << "x^" << p->index;
			else
				cout << "x^" << "(" << p->index << ")";
		}
			
	}
	if (p->next)
		cout << " + ";
	else
		cout << endl;

}


//多项式相加
list add(list& L1, list& L2) {
	Node* p1 = L1.head->next;
	Node* p2 = L2.head->next;
	list res;
	while (p1 || p2) {
		if ( p1 && p2 && (p1->index == p2->index))
		{
			int resCoe = p1->coe + p2->coe;
			if(resCoe!=0)
				res.pushBack(resCoe, p1->index);
			p1 = p1->next;
			p2 = p2->next;
		}
		else if ( p1 && p2 && p1->index > p2->index  || !p1 )
		{
			res.pushBack(p2->coe, p2->index);
			p2 = p2->next;
		}
		else if (p1 && p2 && p1->index < p2->index|| !p2 )
		{
			res.pushBack(p1->coe, p1->index);
			p1 = p1->next;
		}

	}
	return res;
}	
int main() {
	int t;
	cin >> t;
	while (t--) {
		list L1, L2,res;
		int n;
		cin >> n;
		int coe, index;
		for (int i = 0; i < n; i++)
		{
			cin >> coe >> index;
			L1.pushBack(coe, index);
		}
		cin >> n;
		for (int i = 0; i < n; i++)
		{
			cin >> coe >> index;
			L2.pushBack(coe, index);
		}
		L1.disPlay();
		L2.disPlay();
		res = add(L1, L2);
		res.disPlay();	
	}

	return 0;
}

二.栈

1.顺序存储结构

// 栈(顺序存储结构)C++.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include <iostream>
#include<stdio.h>
using namespace std;

typedef int ElemType;
#define OK 1
#define ERROR 0
//Status是状态码，标识着函数执行结果的状态，OK或者ERROR
typedef int Status;

class SqStack {
private:
    int MaxSize;        //数组最大长度
    int top;            //栈顶指针,表示栈顶的索引，所以top=-1时为空表
    ElemType* list;          //指向数组的指针
public:
    SqStack();
    ~SqStack();
    Status Push(ElemType e);    //将元素e推进栈
    Status Pop(ElemType *e);    //栈顶元素出栈，且记录出栈元素
    Status Pop();               //栈顶元素出栈
    Status GetTop(ElemType* e); //获取栈顶元素
    void ClearStack();          //清空栈内元素
    void display();             //打印所有栈内元素，从索引0开始顺序打印
};
SqStack::SqStack() {    //初始化
    top = -1;
    MaxSize = 99;       //默认最大长度为99
    list = new int[MaxSize];
}
SqStack::~SqStack() {
    delete[]list;
}
Status SqStack::Push(ElemType e) {
    if (top == MaxSize - 1) //栈满
        return ERROR;
    top++;
    list[top] = e;
    return OK;
}
Status SqStack::Pop(ElemType *e) {
    if (top == -1)       //栈空
        return ERROR;
    *e = list[top];
    top--;
    return OK;

}
Status SqStack::Pop() {
    if (top == -1)       //栈空
        return ERROR;
    top--;
    return OK;

}
Status SqStack::GetTop(ElemType* e) {
    if (top == -1)
        return ERROR;
    *e = list[top];
    return OK;
}
void SqStack::ClearStack() {
    top = -1;           //这里不需要释放空间，直接top置为-1即可
}
void SqStack::display() {
    if (top == -1)
        cout << "当前为空栈！！！" << endl;
    else
    {
        cout << "当前栈内元素有：";
        for (int i = 0; i < top + 1; i++)
        {
            cout << list[i] << " ";
        }
        cout << endl;
    }  
}
int main()
{

    SqStack test;
    test.Push(1);
    test.display();
    test.Push(2);
    test.display();
    test.Push(3);
    test.display();
    test.Pop();
    test.display();
    ElemType *topElem;
    topElem = new ElemType;
    test.GetTop(topElem);
    cout << "栈顶元素为:" << *topElem << endl;
    test.ClearStack();
    test.display();
    return 0;
}

2.双向循环链式存储结构

// 栈(顺序存储结构)C++.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include <iostream>
#include<stdio.h>
using namespace std;

typedef int ElemType;
#define OK 1
#define ERROR 0
//Status是状态码，标识着函数执行结果的状态，OK或者ERROR
typedef int Status;

//单链表结点类
class Node {
public:
    ElemType data;  //节点数据
    Node* next;		//指向下一节点指针
    Node* front;	//指向上一节点指针
    Node() {		//构造函数初始化栈顶节点******单链表用头结点表示整个链表，现在不同，是用栈顶指针来表示整个链表（其实意思就是第一个位置是栈顶）
        next = NULL;
        front = NULL;
        data = 0;
    }
};
class LinkStack {
private:    
    Node* top;		         //栈顶节点指针
    Node* bottom;            //栈底节点指针
    int len;		         //链表长度
public:
    LinkStack();
    ~LinkStack();
    Status Push(ElemType e);    //将元素e推进栈
    Status Pop(ElemType* e);    //栈顶元素出栈，且记录出栈元素
    Status Pop();               //栈顶元素出栈
    Status StackEmpty();        //判断是否为空栈（1：是   0：不是）
    Status GetTop(ElemType* e); //获取栈顶元素
    Status ClearStack();        //清空栈内元素
    void display();             //打印所有栈内元素，从索引0开始顺序打印
};
LinkStack::LinkStack() {    //初始化
    top = new Node;
    len = 0;
}
LinkStack::~LinkStack() {
    Node* p, * q;
    p = top;		 //p指向第一个节点
    for (int i = 0; i < len; i++)
    {
        q = p->next;
        delete p;
        p = q;
    }
    len = 0;
}
Status LinkStack::StackEmpty() {
    if (len == 0)
        return 1;
    else
        return 0;
}
Status LinkStack::Push(ElemType e) {
    Node* temp;
    temp = new Node;
    temp->data = e;     
    temp->next = top;       //把当前第一个元素节点指针（栈顶指针）赋值在插入的新节点的后继
    top->front = temp;      //把插入的新节点赋值给原本栈顶节点的前继
    top = temp;             //将新节点赋值给栈顶指针
    if (len == 0) {         //len=0即推进第一个节点的时候才需要记录bottom（因为bottom不会变），这时top的前继节点还是top本身
        top->front = top;
        bottom = top;
    }
    else
        top->front = bottom;
    len++;
    return OK;
}
Status LinkStack::Pop(ElemType* e) {
    if (StackEmpty())       //栈空
        return ERROR;
    *e = top->data;
    Node* temp;
    temp = top;
    top->front->next = top->next;
    top->next->front = top->front;
    top = temp->next;
    delete temp;
    len--;
    return OK;

}
Status LinkStack::Pop() {
    if (StackEmpty())       //栈空
        return ERROR;
    Node* temp;
    temp = top;
    top->front->next = top->next;
    top->next->front = top->front;
    top = temp->next;
    delete temp;
    len--;
    return OK;

}
Status LinkStack::GetTop(ElemType* e) {
    if (StackEmpty())       //栈空
        return ERROR;
    *e = top->data;
    return OK;
}
Status LinkStack::ClearStack() {
    Node* p, * q;
    p = top->next;		 //p指向第二个节点
    for (int i = 0; i < len-1; i++)
    {
        q = p->next;
        delete p;
        p = q;
    }
    //top = NULL;	//栈顶指针域设为空(×)
    top->next = NULL;  //表示链表的指针不能置空或者delete，所以上一行代码是错误的，应该清空栈是回到一开始构造的状态，不是删除指针，否注栈就消失了
    top->front = NULL;

    len = 0;
    return OK;
}
void LinkStack::display() {
    Node *temp;
    if (StackEmpty())
        cout << "当前为空栈！！！" << endl;
    else
    {
        temp = top;
        cout << "当前栈内元素有：";
        for (int i = 0; i < len; i++)
        {   
            cout << temp->front->data << " ";
            temp = temp->front;
        }
        cout << endl;
    }
}
int main()
{

    LinkStack test;
    test.Push(1);
    test.display();
    test.Push(2);
    test.display();
    test.Push(3);
    test.display();
    test.Pop();
    test.display();
    ElemType* topElem;
    topElem = new ElemType;
    test.GetTop(topElem);
    cout << "栈顶元素为:" << *topElem << endl;
    test.ClearStack();
    test.display();
    test.Push(1);
    test.display();
    test.ClearStack();
    test.display();
    return 0;
}

3.STL类模板实现

stack类使用的参考代码

• 1、包含头文件：#include <stack>
• 2、创建一个堆栈对象s（注意stack是模板类）：stack s; //堆栈的数据类型是字符型
• 3、把一个字符ct压入堆栈： s.push(ct);
• 4、把栈顶元素弹出：s.pop();
• 5、获取栈顶元素，放入变量c2： c2 = s.top();
• 6、判断堆栈是否空： s.empty()，如果为空则函数返回true，如果不空则返回false
• 7、对堆栈进行操作时，一定要记得查看堆栈是否为空

#include<iostream>
#include<stack>
#include<string>
using namespace std;

int main() {
	stack<char> s;
	int t;
	string c;
	cin >> t;
	int len;
	while (t--)
	{
		cin >> c;
		len = c.size();
		for (int i = 0; i < len; i++)
		{
			if (c[i] == '#' && !s.empty())
				s.pop();
			else if(c[i] != '#')
				s.push(c[i]);
		}
			stack<char> ans;
			while (!s.empty())
			{
				ans.push(s.top());
				s.pop();
			}
			/*for (int i = 0; i < s.size(); i++)
			{
				ans.push(s.top());
				s.pop();
			}*/
			if (ans.empty())
				cout << "NULL";
			while (!ans.empty())
			{
				cout << ans.top();
				ans.pop();
			}
			//for (int i = 0; i < s.size(); i++)
			//{
			//	cout << ans.top();
			//	ans.pop();
			//}
			cout << endl;
		}

	return 0;
}

括号匹配

#include<iostream>
#include<stack>
#include<string>
using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--)
	{
		int temp=1;
		stack<char> s;
		string tt;
		cin >> tt;
		int len = tt.size();
		for (int i = 0; i < len; i++)
		{
			temp = 1;
			if (tt[i] == '(' || tt[i] == '[' || tt[i] == '{')
				s.push(tt[i]);
			else if (tt[i] == ')' ) {
				if (s.empty()) {
					temp = 0;
					cout << "error" << endl;
					break;
				}
				if(s.top() == '(')
					s.pop();
				else {
					temp = 0;
					cout << "error" << endl;
					break;
				}
				
			}
			else if (tt[i] == ']') {
				if (s.empty()) {
					temp = 0;
					cout << "error" << endl;
					break;
				}
				if (s.top() == '[')
					s.pop();
				else {
					temp = 0;
					cout << "error" << endl;
					break;
				}
					
			}
			else if (tt[i] == '}') {
				if (s.empty()) {
					temp = 0;
					cout << "error" << endl;
					break;
				}
				if (s.top() == '{')
					s.pop();
				else {
					temp = 0;
					cout << "error" << endl;
					break;
				}

			}

		}

		if(!s.empty()&&temp==1)
			cout << "error" << endl;
		else if (temp == 1&&s.empty())
			cout << "ok" << endl;
	}
	return 0;
}

迷宫求解

#include<iostream>
#include<stack>
using namespace std;
const int m = 999;
int Lu[m][m];
int n;
int path(int i, int j) {//判断四个方向中右上下左的顺序那个可行
    if (j + 1 < n && !Lu[i][j + 1])
        return 1;
    else if (i + 1 < n && !Lu[i + 1][j])
        return 2;
    else if (j - 1 >= 0 && !Lu[i][j - 1])
        return 3;
    else if (i - 1 >= 0 && !Lu[i - 1][j])
        return 4;
    return 0;
}
int main() {

    int t;
    int ii[] = { 0, 0, 1, 0, -1 };
    int jj[] = { 0, 1, 0, -1, 0 };
    cin >> t;
    while (t--) {

        cin >> n;

        stack<int> stx;
        stack<int> sty;


        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> Lu[i][j];


        int i = 0;
        int j = 0;
        if (Lu[0][0] == 0) {
            Lu[0][0] = 1;
            stx.push(0);
            sty.push(0);
            while (1) {
                int k = path(i, j);

                if (k) {
                    i += ii[k];
                    j += jj[k];
                    Lu[i][j] = 1;
                    stx.push(i);
                    sty.push(j);

                }
                else if (!stx.empty() && !sty.empty()) {//四个方向不可行则回退
                    i = stx.top();
                    j = sty.top();
                    if (!path(i, j)) {
                        stx.pop();
                        sty.pop();
                    }
                }

                if ((stx.empty() && sty.empty()) || (i == n - 1 && j == n - 1))
                    break;//全部pop掉或到达终点则退出循环
            }
        }



        if (stx.empty() && sty.empty())
        {
            cout << "no path" << endl;
        }
        else {
            int path[1000];
            int len = 0;
            int l = 0;

            while (!stx.empty() && !sty.empty()) {
                len += 2;//注意这里是i和j同时插入，所以要加2
                path[l++] = sty.top();
                path[l++] = stx.top();
                stx.pop();
                sty.pop();
            }

            int flag = 1;
            for (int i = len - 1; i >= 0;) {

                cout << '[' << path[i--] << ',' << path[i--] << ']' << "--";
                if ((flag++) % 4 == 0)
                    cout << endl;
            }
            cout << "END" << endl;
        }
    }
    return 0;
}

波兰式，逆波兰式

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZkdJEZI4-1656231405137)(数据结构/image-20220328000953008.png)]

• 注意字符char拼接成string的用法
• 傻逼OJ行末尾不能有空格

#include<iostream>
#include<stack>
#include<string>
using namespace std;
stack<char> c1;
stack<string> c2;
//逆波兰
void nP(string n) {
    int len;
    len = n.size();
    char  temp;
    for (int i = 0; i < len; i++)
    {
        if (isdigit(n[i])) {
            if ( i<(len-1)&&isdigit(n[i+1])) {
                cout << n[i] ;
            }
            else
                cout << n[i] << " ";
        }
        else if (n[i] == '+'|| n[i] == '-') {
            if (!c1.empty()&&c1.top() == '*' || !c1.empty() && c1.top() == '/') {
                while (!c1.empty()) {
                    cout << c1.top() << " ";
                    c1.pop();
                }
                c1.push(n[i]);
            }
            else 
                c1.push(n[i]);                
        }
        else if (n[i] == '*'||n[i]=='/'|| n[i] == '(') {
             c1.push(n[i]);
        }
        else if (n[i] == ')') {
            temp = c1.top();
            while (temp!='(')
            {
                cout << temp << " ";
                c1.pop();
                temp = c1.top();
            }
            c1.pop();
        }
    }
    while (!c1.empty()) {
        //sb OJ行末不能有空格
        char temp = c1.top();
        c1.pop();
        if (c1.empty())
            cout << temp;
        else
            cout << temp << " ";
    }
    cout << endl;
    cout << endl;
}
//波兰
void P(string n) {
    int len;
    len = n.size();
    char  temp;
    for (int i = len-1; i >=0; i--)
    {
        if (isdigit(n[i])) {
            if (i >0 && isdigit(n[i - 1])) {
                //字符char不能直接拼接,注意下用法
                string t = "";
                t += n[i - 1];
                t += n[i];
                c2.push(t);
            }
            else if (i < (len - 1) && isdigit(n[i + 1]) ){

            }
            else {
                string t = "";
                t += n[i];
                c2.push(t);
            }
            
        }
        else if (n[i] == '+' || n[i] == '-') {
            if (!c1.empty() && c1.top() == '*' || !c1.empty() && c1.top() == '/') {
                while (!c1.empty()) {
                    string t = "";
                    t += c1.top();
                    c2.push(t);
                    c1.pop();
                    if (!c1.empty() && c1.top() == '+' || !c1.empty() && c1.top() == '-')
                        break;
                }
                c1.push(n[i]);
            }
            else
                c1.push(n[i]);
        }
        else if (n[i] == '*' || n[i] == '/' || n[i] == ')') {
            c1.push(n[i]);
        }
        else if (n[i] == '(') {
            temp = c1.top();
            while (temp != ')')
            {
                string t = "";
                t += temp;
                c2.push(t);
                c1.pop();
                temp = c1.top();
            }
            c1.pop();
        }
    }
    while (!c1.empty()) {
        string t = "";
        t += c1.top();
        c2.push(t);
        c1.pop();
    }
    while (!c2.empty()) {
        //sb OJ行末不能有空格
        string temp = c2.top();
        c2.pop();
        if (c2.empty())
            cout << temp;
        else
            cout << temp <<" ";
    }
    cout << endl;

}
int main() {

    int t;
    cin >> t;
    string c;
    while (t--)
    {
        cin >> c;
        P(c);
        nP(c);
    }
    return 0;
}

队列+堆栈–数制转换

#include <iostream>
#include <iomanip>
#include <queue>
#include <stack>
using namespace std;

int main()
{
	double num;
	int k, t;
	cin >> t;
	while (t--)
	{
		cin >> num >> k;
		int zheng = num;			//整数 
		float xiao = num - zheng;	//小数
		stack<char> res1;
		queue<char> res2;

		while (zheng)
		{
			int res = zheng % k;
			zheng /= k;
			//处理16进制
			if (res >= 10) {
				res1.push(res + 'A' - 10);
			}
			else {
				res1.push(res + '0');
			}
		}
		int fix = 3;
		while (fix--)
		{
			xiao *= k;
			int zh = int(xiao);//整数部分
			//处理16进制
			if (xiao >= 10) {
				res2.push(zh + 'A' - 10);
			}
			else {
				res2.push(zh + '0');
			}
			xiao -= zh;
		}

		while (!res1.empty()) {
			cout << res1.top();
			res1.pop();
		}
		cout << ".";
		while (!res2.empty()) {
			cout << res2.front();
			res2.pop();
		}
		cout << endl;
	}

}

三.队列

1.循环顺序存储结构

// 队列(循环队列顺序存储结构)C++.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include <iostream>
#include<stdio.h>
using namespace std;

typedef int ElemType;
#define OK 1
#define ERROR 0
//Status是状态码，标识着函数执行结果的状态，OK或者ERROR
typedef int Status;

class SqQueue {
private:
    int MaxSize;        //数组最大长度
    int front;          //头指针
    int rear;           //尾指针，指向队尾元素的下一个位置
    ElemType* list;     //指向数组的指针
public:
    SqQueue();
    ~SqQueue();
    int QueueLength();              //返回队列的元素个数，也就是队列的长度
    Status EnQueue(ElemType e);     //若队列未满，则插入元素e为新的队尾元素
    Status Dequeue();               //若队列不空，则删除队头元素
    void ClearQueue();              //清空队列
    void display();
};
SqQueue::SqQueue() {    //初始化一个空队列
    front = 0;
    rear = 0;
    MaxSize = 99;       //默认最大长度为99
    list = new int[MaxSize];
}
SqQueue::~SqQueue() {
    delete[]list;
}
int SqQueue::QueueLength() {
    return (rear - front + MaxSize) % MaxSize;
}
Status SqQueue::EnQueue(ElemType e) {
    if ((rear + 1) % MaxSize == front)    //队列满没满的判断
        return ERROR;
    list[rear] = e;
    rear = (rear + 1) % MaxSize;
    return OK;
}
Status SqQueue::Dequeue() {
    if (front == rear)    //队列为空的判断
        return ERROR;
    front = (front + 1) % MaxSize;
    return OK;
}
void SqQueue::ClearQueue() {
    front = 0;
    rear = 0;
}
void SqQueue::display() {
    if (front == rear)
        cout << "当前为空队列！！！" << endl;
    else
    {
        cout << "当前队列内元素有（头---->尾）：";
        for (int i =front,j=0 ; j < QueueLength(); i++,j++)
        {
            cout << list[i%MaxSize] << " ";
        }
        cout << endl;
    }
}
int main()
{
    SqQueue test;
    test.display();
    test.EnQueue(2);
    test.display();
    test.EnQueue(3);
    test.display();
    test.EnQueue(4);
    test.display();
    test.Dequeue();
    test.display();
    test.ClearQueue();
    test.display();
    return 0;
}

2.链式存储结构

// 队列（链式存储结构）C++.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include <iostream>
#include<stdio.h>
using namespace std;

typedef int ElemType;
#define OK 1
#define ERROR 0
//Status是状态码，标识着函数执行结果的状态，OK或者ERROR
typedef int Status;

//单链表结点类
class Node {
public:
    ElemType data;  //节点数据
    Node* next;
    Node() {		
        next = NULL;
        data = 0;
    }
};
class LinkQueue {
private:
    Node* front;		     //队头节点指针     //front一直为空，这里还是头结点表示整个链表，第一个元素节点在链表的第二个节点
    Node* rear;              //队尾节点指针
    int len;		         //链表长度
public:
    LinkQueue();
    ~LinkQueue();
    Status EnQueue(ElemType e); //插入元素e为新的队尾元素
    Status DeQueue();           //若队列不空，则删除对头元素
    Status ClearQueue();        //清空队列内元素
    void display();             //打印所有队列内元素，（头----->尾)
};
LinkQueue::LinkQueue() {
    front = new Node;
    rear = front;         //重要!!!!  一开始初始化rear和front为同一个节点，表示空对列
    len = 0;
}
LinkQueue::~LinkQueue() {
    Node* p, * q;
    p = front;		 //p指向第一个节点
    for (int i = 0; i < len; i++)
    {
        q = p->next;
        delete p;
        p = q;
    }
    front->next = NULL;  //！！！
    rear = front;
    len = 0;
}
Status LinkQueue::EnQueue(ElemType e) {
    Node* temp = new Node;
    temp->data = e;
    temp->next = NULL;
    rear->next = temp;
    rear = temp;
    len++;
    return OK;
}
Status LinkQueue::DeQueue() {
    Node *p = new Node;
    if (front == rear)          //判断队列是否为空
        return ERROR;
    p = front->next;            //要删除的队头节点
    front->next = p->next;      //删除队头节点
    if (rear == p)    //如果队列只有一个元素，删除后，rear指向头结点front，表示空队列
        rear = front;
    delete p;
    len--;
    return OK;
}
Status LinkQueue::ClearQueue() {
    Node* p, * q;
    p = front->next;		 //p指向第二个节点
    for (int i = 0; i < len-1; i++)
    {
        q = p->next;
        delete p;
        p = q;
    }
    front->next=NULL;  //！！！
    rear = front;
    len = 0;
    return OK;
}
void LinkQueue::display() {
    Node* temp;
    if (rear == front)
        cout << "当前为空队列！！！" << endl;
    else
    {
        temp = front;
        cout << "当前对列内元素有：";
        for (int i = 0; i < len; i++)
        {
            cout << temp->next->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
}

int main() {
    LinkQueue test;
    test.EnQueue(1);
    test.EnQueue(2);
    test.EnQueue(3);
    test.display();

    test.DeQueue();
    test.display();

    test.ClearQueue();
    test.EnQueue(3);
    test.EnQueue(1);
    test.display();

    test.ClearQueue();
    test.display();

    //test.ClearQueue();
    //test.display();
    return 0;
}

3.STL类模板实现

队列queue的用法如下：

• 1.包含头文件：#include <queue>
• 2.定义一个整数队列对象：queue<int> myQe;
• 3.定义一个整数队列对象数组：queue myQA[10];
• 4.入队操作：myQe.push(itemp); //把整数itemp进入队列
• 5.出队操作：myQe.pop(); //把队头元素弹出队列，注意本操作不获取队头元素
• 6.获取队头元素： itemp = myQe.front(); // 把队头元素放入itemp中，注意本操作不弹出元素
• 7.判断队列是否为空：myQe.empty();//队列空则返回true，不空则返回false

4.组队列（哈希表，队列）

#include <iostream>
#include <iomanip>
#include <queue>
#include <stack>
#include<string>
#include <map>
using namespace std;

int main()
{
	int t;
	cin >> t;
	queue<int>*res=new queue<int>[t];
	queue<int> Res;
	map<int, int> group;


	for (int i = 1; i <= t; i++)
	{
		int j;
		cin >> j;
		while (j--) {
			int x;
			cin >> x;
			group[x] = i;//同组的value为组号
		}
	}
	string operation;
	cin >> operation;
	int temp = 0;
	while (operation!="STOP")
	{
		int num;
		
		if (operation == "ENQUEUE") {
			cin >> num;
			for (int i = 0; i < t; i++)
			{
				//如果队列为空，或者队列元素同组号
				if (res[i].empty() || group[res[i].front()] == group[num]) {
					res[i].push(num);
					break;
				}
			}
		}
		else if (operation == "DEQUEUE") {
			for (int i = 0+temp; i < t; i++)
			{
				if (!res[i].empty()) {
					cout << res[i].front() << " ";
					res[i].pop();
					break;
				}
				else {
					temp++;
				}

			}
		}
		cin >> operation;
	}
	return 0;
}

四.KMP算法及其优化

void getNext(string &T,int *next)
{
	int i = 0, j = -1;
	next[0] = -1;
	while (i < T.size() -1)
	{
		if (j == -1|| T[i] == T[j])
		{
			i++;
			j++;
			if (T[i] != T[j])
				next[i] = j;
    //优化点，防止T串为aaaab这种类型，需要一个一个往前翻，利用下面两行，可以直接找到最初等价位置
			else
				next[i] = next[j];
		}
		else
			j = next[j];
	}
 
}
int  KMP_method(string &S, string &T)//S为目标串，T为模式串
{
	int *next = new int[T.size()];
	getNext(T, next);
	int i = 0, j = 0;
	while (i < S.size() && j < T.size())
	{
 
		if (S[i] == T[j])
		{
			i++;
			j++;
 
		}
		else if (next[j] == -1)
			i++;
		else
			j = next[j];
	}
	if (next)
	{
		delete[]next;
		next = NULL;
	}
	return (j == T.size()) ? i -j : -1;
 
}

可重叠子串 (Ver. I)

#include <string.h>
#include <iostream>
using namespace std;

void getNext(string& T, int* next)
{
	int i = 0, j = -1;
	next[0] = -1;
	while (i < T.size() - 1)
	{
		if (j == -1 || T[i] == T[j])
		{
			i++;
			j++;
			if (T[i] != T[j])
				next[i] = j;
			//优化点，防止T串为aaaab这种类型，需要一个一个往前翻，利用下面两行，可以直接找到最初等价位置
			else
				next[i] = next[j];
		}
		else
			j = next[j];
	}


}
int  KMP_method(string& S, string& T)//S为目标串，T为模式串
{
	int cnt = 0;
	int* next = new int[T.size()];
	getNext(T, next);
	int i = 0, j = 0;
	while (i < S.size())//j < T.size()是搜索到的条件
	{

		if (j==-1||S[i] == T[j])
		{
			if (j == (T.size() - 1)) { //计算匹配次数
				i = i - j + 1;
				j = 0;
				cnt++;
			}
			else {
				i++;
				j++;
			}
		}
		else if (next[j] == -1) {
			i++;
			j = 0;  //从头判断
		}			
		else
			j = next[j];
	}
	if (next)
	{
		delete[]next;
		next = NULL;
	}
	///*return (j == T.size()) ? i - j : -1;*/
	return cnt;

}
int main()
{
	string str;
	string ms;
	int t;
	while (cin >> str)
	{
		cin >> t;
		while (t--)
		{
			cin >> ms;
			int res = KMP_method(str, ms);
			cout << ms << ":" << res << endl;
		}
	}
	return 0;
}