1. 1. 线性表
    1. 1.1. 链表
    2. 1.2. 栈
    3. 1.3. 队列
      1. 1.3.1. 循环队列
      2. 1.3.2. 队列应用
      3. 1.3.3. 优先队列
    4. 1.4. 字符串匹配
      1. 1.4.1. KMP
  2. 2. 树
  3. 3. 图
    1. 3.1. 最短路

Data Structure

线性表

链表

链表中对于指针的使用,修改的是其所指向的值的更改,更改后要移动指针

//waiting找到好的题目再更

栈

  • 求合法出栈序列(卡特兰数)
    设序列长度为n
    则合法序列中 进栈次数为n,出栈次数为n
    但是在C(n,2n)中还应该使得出栈操作前栈不为空，即当前出栈次数<=入栈次数
    设出栈为-1，入栈为+1
    通过映射不合法序列使得序列变为n-1个-1,n+1个+1

映射规则为当前前缀和为-1时,将当前位置起的数字一一取反

序列① -1 -1 1 1
序列② 1 -1 1 1

那么合法序列则为

C(n,2n)-C(n-1,2n)=C(n,2n)/(n+1)
  • 中序表达式转为后序表达式
    遇到字母直接输出
    入栈条件：遇到运算符若栈为空或栈顶运算符优先级小于当前运算符
    出栈条件：若当前运算符优先级小于栈顶则栈顶出栈直到满足入栈条件
    若遇见括号’(‘则直接入栈,当遇到’)‘时将’(‘到’)'之间的符号依次出栈(包括括号)

将四则运算(中序)式子转为后序,在计算时对于括号嵌套能较好处理

在中序转为后序时,符号的优先级判断: 乘除号优先级最高则直接入栈,加减号则需要将栈排空或在遇到'('时再入栈 这里的'('相当于一个新的栈底（因为要将括号内式子先计算） 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std;

stack<char>ope;
stack<double>val;//数值类型
void PostOrder(char s[], char t[]) {
	int j = 0, len = strlen(s);
	for (int i = 0; i<len; i++) {
		if (s[i] >= '0'&&s[i] <= '9') {
			while (s[i] >= '0'&&s[i] <= '9') {
				t[j++] = s[i++];
			}
			i -= 1;
			t[j++] = '#';
		}
		else if (s[i] == '(') {
			ope.push(s[i]);
		}
		else if (s[i] == ')') {
			char k = ope.top();
			while (k != '(') {
				t[j++] = k;
				ope.pop();
				k = ope.top();
			}
			ope.pop();
		}
		else if (s[i] == '+' || s[i] == '-') {
			while (!ope.empty() && ope.top() != '(') {//此时已经对优先级进行比较
				t[j++] = ope.top();
				ope.pop();
			}
			if (s[i] == '+')ope.push('+');
			else ope.push('-');
		}
		else if (s[i] == '*')ope.push('*');
		else if (s[i] == '/')ope.push('/');
	}

	while (!ope.empty()) {
		t[j++] = ope.top();
		ope.pop();
	}
	t[j] = '\0';
}
void get_num(char t[], int& i) {
	double num = 0;
	while (t[i] >= '0'&&t[i] <= '9') {
		num *= 10;
		num += t[i] - '0';
		i++;
	}
	i -= 1;
	val.push(num);
}
void cal(char t[], int &i) {
	double num1 = val.top();
	val.pop();

	double num2 = val.top();
	val.pop();

	if (t[i] == '+') {
		num2 += num1;
	}
	else if (t[i] == '-') {
		num2 -= num1;
	}
	else if (t[i] == '*') {
		num2 *= num1;
	}
	else if (t[i] == '/') {
		num2 /= num1;
	}
	val.push(num2);
}

void result(char t[]) {
	int len = strlen(t);
	for (int i = 0; i<len; i++) {
		if (t[i] >= '0'&&t[i] <= '9') {
			get_num(t, i);
		}
		else if (t[i] == '#')continue;
		else {
			cal(t, i);
		}
	}
}
int main() {
	char s[100] = "9+(3-2*(11-5/10)*2)+3+10/2";
	char t[100];
	PostOrder(s, t);
	cout << "后缀： " << t << endl;// 9#3#2#3#5#-2#**-3#*+10#2#/+   '#'用来间隔数字 
	result(t);
	cout << val.top();
	val.pop();
	return 0;
}

队列

循环队列

插入时（rear+1）%LEN
删除时（front+1）%LEN
循环队列的插入和删除都是+1
计算长度当前LEN:(rear-front+LEN)%LEN

队列应用

对于队列简易的封装以及对于模板类简单的使用

/*  左上角开始向右下搜索
aaaaaaaaaa
aaaaaaaaaa
aa########
aaaaaaaaaa
aaaaaaaa*a
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
*/


#include<iostream>
#include<cstdio>
#define n 10 

using namespace std;

int vis[n][n] = { 0 };
char map[n][n];

template<typename ElemType>
struct queue {
	int capacity;
	int head;
	int tail;
	ElemType* items;

	queue(int c = 100) {
		capacity = c;
		head = 0;
		tail = 0;
		items = new ElemType[c];
	}
	void push(ElemType elem) {
		items[tail] = elem;
		tail++;
	}
	bool empty() {
		if (!tail)return true;
		return false;
	}
	void  pop() {
		for (int i = head; i<tail; i++)
			items[i] = items[i + 1];
		tail--;
	}
	ElemType front() {
		return items[head];
	}
};


struct node {
	int x, y;
	int cnt = 0;
};
queue<node> q;

int func(node b) {
	int xx[4] = { 0,1 };
	int yy[4] = { 1,0 };
	int flag = 0;
	node a;

	q.push(b);

	while (!q.empty() && !flag) {
		a = q.front();
		q.pop();
		int x1, y1;
		for (int i = 0; i < 2; i++) {
			x1 = a.x + xx[i], y1 = a.y + yy[i];
			if (map[x1][y1] == '*') {
				a.cnt++;
				flag = 1;
				break;
			}
			if (!vis[x1][y1] && x1<10 && y1<10 && map[x1][y1] != '#') {
				vis[x1][y1] = 1;
				q.push(node{ x1,y1,a.cnt + 1 });
			}
		}
	}
	if (flag)
		return a.cnt;
	else return -1;
}


int main() {
	memset(map, 'a', sizeof(map));
	map[4][8] = { '*' };
	for (int i = 2; i < 3; i++) {
		for (int j = 2; j < 10; j++)
			map[i][j] = '#';
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << map[i][j];
			
		}
		cout << endl;
	}
	node b;
	b.x = b.y = b.cnt = 0;
	int cnt = func(b);
	if (cnt == -1)cout << "没有联通路径";
	else cout << "存在路径长度为 num:" << cnt << endl;
	return 0;
}
优先队列

//waiting

字符串匹配

KMP

KMP的匹配规则与暴力不同之处：
在匹配错误时暴力会直接返回到起始处的后一位字符在进行匹配
kmp则可以避免不必要的"重蹈覆辙"

其中next数组就是kmp的核心,简要理解为最长相同前后缀 子串

字符串 a b c a b
next数组 -1 0 0 1 2

其中next[0]取-1用以区别头结点和其他节点,避免计数错误

#include<cstdio>
#include<iostream>
#include<cstring>

#define maxn 100010 

using namespace std;

//注意题目数据类型，不一定是字符串！！！ 
void cal_next(char*str,int nex[]) {           //算出str的前缀和后缀相同的长度 存入next中 
	nex[0] = -1;
	int i = 0, j = -1;

	while (i < strlen(p))
	{
		if (j == -1 || p[i] == p[j])
		{
			++i;
			++j;
			nex[i] = j;
		}	
		else
			j = nex[j];
	}

}

void kmp(char*str, char*ptr){
	int next[maxn];
	cal_next(ptr,next);
		int slen = strlen(str);
		int plen = strlen(ptr);
		int k = -1;
		int mark = 0;
		for (int q = 0; q < slen; q++) {
			while (k > -1 && ptr[k + 1] != str[q]) 
				k = next[k];       //字符串当前位置不相同且有相同匹配的时候，回溯 
			
			if (ptr[k + 1]==str[q]) 
				k++;     //相同则继续比较 
			if (k== plen - 1) {
				printf("%d\n", q - k + 1);     // 位置的输出，从1开始 
				  k=next[k];    //得出匹配字符串，位置回到含有相同前缀的点开始比较 
			}
		}
		//  输出子串的next 
		for (int i = 0; i <strlen(ptr); i++) 
			printf("%d ", next[i] + 1);
		printf("\n");	
}

int main() {
	char a[maxn],b[maxn];
	gets_s(a);
	gets_s(b);
	kmp(a,b);
	return 0;
	}

树

*由前序序列和中序序列求后序
①由先序可知第一个字母为跟节点，
②再看其在中序中的位置，以当前字母为中心，左边则为左子树所含字母，右边则为右子树所含字母
③重复上述操作直到结束（先序可确定父节点）
例题


//waiting

图

最短路

void minPath(ALGraph G, int start, int dis[], int path[][100]) {
	int i, j, mindist, k, t;
	Road *now;

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			path[i][j] = -1;
		}
	}

	for (i = 0; i <G.vexnum; i++) {    //初始化最短路径数组dis,和标记此顶点是否已经找到最短路径的path[i][0],等于0表示没有找到,等于1表示找到.
		dis[i] = INT_MAX;
		path[i][0] = 0;
	}
	now = G.vertices[start].firstarc;//起点的邻接表
	while (now) {                                  //保存起点到和其相邻点的路径.
		dis[now->spotId] = now->cost;
		path[now->spotId][1] = start;
		path[now->spotId][2] = now->spotId;
		path[now->spotId][3] = -1;
		now = now->nextarc;
	}

	path[start][0] = 1;               //源点标记为为1，此顶点以后不会再用到
	cout << endl;
	for (int i = 0; i < G.vexnum; i++) {
		for (int j = 0; j < G.vexnum; j++) {
			cout << path[i][j] << " ";
		}
		cout << endl;
	}
	cout << "path [] []" << endl;
	for (i = 1; i <G.vexnum; i++) {                //选择最最短的路径
		mindist = INT_MAX;//从已选集合中选择未选集合 相邻的最短路径
		for (j = 0; j < G.vexnum; j++) {
			if (!path[j][0] && dis[j] < mindist) { //所选集合点到当前点的
				k = j;								
				mindist = dis[j];
			}
		}
		if (mindist == INT_MAX) {         //如果没有找到最短的路径，则说明从此源点不能到任何其他顶点，直接返回.
			return;
		}
		path[k][0] = 1;                  //标记找到最小路径的顶点，此顶点以后不会再用到.
		now = G.vertices[k].firstarc; // 假设将所选点的邻接表中的点加入集合
		while (now) {
			if (!path[now->spotId][0] && dis[now->spotId] > dis[k] + now->cost) {//当前点选择后路径小于之前的（松弛操作）

				dis[now->spotId] = dis[k] + now->cost;//更新
				t = 1;
				while (path[k][t] != -1)      //记录最新的路径
				{

					path[now->spotId][t] = path[k][t];//将已选点集合的最短路径复制到最新的点的path中
					t++;
				}

				path[now->spotId][t] = now->spotId; //记录终点
				path[now->spotId][t + 1] = -1;                       //path[i][t+1]之前的都是最短路径所要经过的顶点，从t+1这里停止,作为最后输出路径的判断条件
			}
			now = now->nextarc;
		}
	}
}
Site construction by John Doe usinghexo blog framework.
Home