Texcavator 的秘密基地

背景是有两个字符串 s1 和 s2， 要找到 s2 中的每个字符第一次出现在 s1 中的位置 方法一： int i = 0;for (int j = 0; j < s2.size(); j ++ ){ while (s1[i] != s2[j]) i ++ ; cout << i << '\n';} 方法二： int i = -1;for (int j = 0; j < s2.size(); j ++ ){ while (s1[++ i] != s2[j]) ; cout << i << '\n';} 它们的最大不同之处在于==如果s2中有两个连续的相同的字符，方法一会把这两个字符映射到s1中的同一个位置，方法二会把这两个字符映射到s1中的前后两个位置== 举个栗子 s1 = aaaaa s2 = aa 根据方法一，s2 的第一个 a 对应 s1 的第一个 a， s2 的第二个 a 也对应 s1 的第一个 a 根据方法二，s2 的第一个 a ...

一、基本定义与性质图由两个集合 V 和 E 组成，记为 G = （V，E）， V 是顶点集，E 是边集 有向图： 顶点对 有序，意为一条由点 x 指向点 y 的有向边。 和 是不同的两条边 在 中，x 是始点 / 弧尾，y 是终点 / 弧头 无向图： 顶点对(x, y) 无序，(x, y) 和 (y, x) 指的是同一条 基本术语n 表示顶点数，e 表示边数 子图： 有一个图的顶点全部都是另一个图的顶点，边也全都是另一个图的边，这个图叫做另一个图的子图 完全图 无向完全图： 有 n(n - 1) / 2 条边的无向图，说人话就是每两个顶点之间都有边 有向完全图： 有 n(n - 1) 条边的有向图，说人话就是从任何一个顶点都能到任何一个其他顶点 稀疏图和稠密图： 边少的就是稀疏图，边多的就是稠密图 网： 带权图 邻接点： 无向图中，(v, v’) 表示 v 与 v’ 互为邻接点，v 和 v’ 相邻接，边 (v, v’) 依附于顶点 v 和 v’，边 (v, v’) 和顶点 v v’ 相关联 度： 和顶点相关联的边的个数，记作TD(v) 入度： 有向图中从该点发出的边的 ...

一、栈栈就是后进先出的线性表。 表尾叫做==栈顶==，表头叫做==栈底== 1. 顺序存储（1） 结构体定义#define MAXSIZE 100typedef struct{ ElemType *base; // 栈底指针 ElemType *top; // 栈顶指针 int stacksize; // 栈大小}SqStack; base始终指向栈底，若base == NULL，则说明为空栈 top为栈顶指针，起初栈中没有元素时指向栈底，每添加一个元素，top也++，top始终指向最后一个元素的上一个位置（2） 初始化空栈Status InitStack(SqStack &S){ S.base = new ElemType[MAXSIZE]; // 分配内存 if (!S.base) exit(OVERFLOW); // 内存分配失败 S.top = S.base; // 栈中无元素，栈顶指针和栈底指针相等 S.stacksize = MAXSIZE; return OK;} （3） 入栈思路： 就是先判断栈是否满，没满就在栈顶插 ...

一学期没怎么听数构的大学生记录一下期末复（yu）习过程中一些容易遗漏的知识点QAQ Part1 数据结构 常见的四类基本数据结构有：线性结构、树形结构、集合结构和图形结构。[ 逻辑结构 ] 物理存储结构有：顺序存储结构、链式存储结构。 判断： 由于链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻，因此，它具有随机存取的优点。答案： 错，不能随机存取！！ 判断： 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。答案： 错，线性是对的 通常从四个方面评价算法的质量：正确性、易读性、强壮性、高效率Part2 线性表 顺序表中在第 i 位前添加元素，i 可以是1—length + 1 的任何数。 双向循环链表 指向前面一个结点的prior，指向后面一个结点的next，其他都与单链表类似。 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ A ）。 (A) q=p->next；p->data=q->data；p->next=q->next；free(q)； (B) q=p->next；q->da ...

从快吃中饭开始看题，一直到晚上七点半终于AC了！！！！！！！！！ 写篇题解记录一下这个激动人心的时刻 题目：[USACO11OPEN] Corn Maze S题面翻译奶牛们去一个 $N\times M$ 玉米迷宫，$2 \leq N \leq 300,2 \leq M \leq300$。 迷宫里有一些传送装置，可以将奶牛从一点到另一点进行瞬间转移。这些装置可以双向使用。 如果一头奶牛处在这个装置的起点或者终点，这头奶牛就必须使用这个装置。 玉米迷宫除了唯一的一个出口都被玉米包围。 迷宫中的每个元素都由以下项目中的一项组成： 玉米，# 表示，这些格子是不可以通过的。 草地，. 表示，可以简单的通过。 传送装置，每一对大写字母 $\tt{A}$ 到 $\tt{Z}$ 表示。 出口，= 表示。 起点， @ 表示 奶牛能在一格草地上可能存在的四个相邻的格子移动，花费 $1$ 个单位时间。从装置的一个结点到另一个结点不花时间。 题目描述This past fall, Farmer John took the cows to visit a corn maze. But this wasn’t ...