4.1 指令系统 指令的基本格式 按地址码数目 零地址指令 \(OP\) 不需要操作数，入空操作、停机、关中断等指令 堆栈计算机，两个操作数隐含存放在栈顶和次栈顶，计算结果压回栈顶 一地址指令 \(OP\) \(A_1\) 只需要单操作数，如加 \(1\) 、减 \(1\) 、取反、求补等 指令含义：\(OP(A_1)\rightarrow A_1\) ，完成一条指令需要 3 次访存，取值 \(\rightarrow\) 读 \(A_1\)\(\rightarrow\) 写 \(A_1\) 需要两个操作数，但其中一个操作数隐含在某个寄存器（如隐含在 \(ACC\)） 指令含义：\((ACC)OP(A_1)\rightarrow ACC\) ，完成一条需要 2 次访存：取值 \(\rightarrow\) 读 \(A_1\) 注：\(A_1\) 指某个主存地址，\((A_1)\) 表示 \(A_1\) 所指向的地址中的内容 二地址指令 \(OP\) \(A_1\) \(A_2\) 常用于需要两个操作数的算术运算、逻辑运算相关指令 ...

3.1 存储器概述 存储器的分类 按存取方式分类： 随机存取存储器（RAM）：读写任何一个存储单元所需时间都相同，与存储单元所在的物理位置无关。 顺序存取存储器（SAM）：读写一个存储单元所需时间取决于存储单元所在的物理位置。 直接存取存储器（DAM）：既有随机存取特性，也有顺序存取特性。先直接选取信息所在区域，然后按顺序方式存取。 相联存取存储器（CAM）：可以按照内容检索到存储位置进行读写，“快表” 就是一种相联存储器。 串行访问存储器：读写某个存储单元所需时间与存储单元的物理位置有关。 按信息的可更改性分类 读写存储器（Read/Write Memory）：即可读、也可写（如：磁盘、内存、Cache） 只读存储器（Read Only Memory）：只能读，通常不能写，但某些类型支持特定条件下的重写（如：实体音乐专辑通常采用 CD‑ROM，实体电影采用蓝光光碟，BIOS 通常写在 ROM 中） 按信息的可保存性分类 断电后，存储信息消失的存储器 ——易失性存储器（主存、Cache） 断电后，存储信息依然保持的存储 ...

《Narcissu》视觉小说简评 《Narcissu》 又名 《水仙》 序言 我们当时很年轻， 有地图， 有一辆银色的酷派， …以及抢来的处方药。 我们能到日本的任何一个地方， 但却迷茫内疚、痛苦不堪， 我们早已没有未来… 曾经， 在嗅到死亡的风中， 我们诉说着爱， 日夜有所希冀， 只听见， 凄冷的回声与空旷的山林。 如今， 这个晴朗的日子， 淡路岛的水仙满地， 清澈的水波摇荡着我们的倒影， 淋着960公里外的雨滴， 我们想要再次爱着自己。 既是厄科（Echo）， 亦是纳西索斯（Narcissus）。 此时， 也许有人在为工作而奔波、疲惫， 有人在青春中烦恼、嬉戏。 只有我知道的是： 那个相互簇拥的冬日， 她成了水仙花的一朵… （游戏简介） … on that blindingly bright day … … on that very day of winter … This is a story of disease and suffering; of med ...

8.1 排序的基本概念 排序（sort），就是重新排列表中元素，使得表中的元素满足按关键字有序的过程 具有稳定性：关键字相同的元素在排序之后相对位置不变 不能说稳定的排序比无稳定的排序好 内部排序：数据都在内存中 外部排序：数据太多，无法全部放入内存，还要关注如何使读/写磁盘次数更少 8.2 插入排序 插入排序：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。 直接插入排序 1234567891011121314151617181920212223242526// 直接插入排序void InsertSort(int A[],int n){ int i,j,temp; for(int i=1;i<n;i++){ if(A[i]<A[i-1]){ temp=A[i]; for(int j=i-1;j>=0&&A[j]>temp;--j){ ...

7.1 查找的基本概念 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找 查找表（查找结构）：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）构成 关键字：数据元素中唯一标识该元素的某个数据项，使用基于关键字的查找，查找结果应该是一样的 评价指标 查找长度：需要对比关键字的次数 平均查找长度（ASL）：查找过程中进行关键字的比较次数的平均值 ASL一般分为查找成功和查找失败的情况 7.2 顺序查找和折半查找 顺序查找 按着下标顺序依次往后找。 可加入“哨兵”，数组第 \(0\) 个位置是哨兵，从后往前查找，显然，如果查找失败，则返回下标 \(0\) 。 时间复杂度 \(O(n)\) 折半查找（二分查找） 仅适用于有序的顺序表 例如，\([l,r]\) 区间有序（升序），那么用 \(mid\) 指针指向中间 \(mid=(l+r)/2\) ，如果 \(mid<k\) ，则搜索 \([l,mid-1]\) 的区间，也就是 \(r=mid-1\) ；如果相等，就返回下标；否则，搜索 \( ...

6.1 图的基本概念 图 \(G\) 由顶点集 \(V\) 和边集 \(E\) 组成，记为 \(G=(V,E)\) 。其中，\(V(G)\) 表示图 \(G\) 中顶点的有限非空集。 存疑，这也许是考研标准，但一般空图也是图 用 \(|V|\) 表示图中 \(G\) 中点的数量。 ，用 \(|E|\) 表示图中 \(G\) 中边的数量。 无向图中的极大连通子图称为连通分量 极大连通子图：子图是连通的，而且不存在包含它的连通子图，也就是边和点尽可能多的。 有向图中的极大强连通子图成为有向图的强连通分量 连通图的生成树是包含图中全部顶点的一个极小连通子图 极小连通子图：子图是连通的，而且在相同顶点集，不存在边比它的少连通子图，也就是边尽可能少，但点要尽可能多。 无向完全图：无向图中任意两个顶点之间都存在边 有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧 边数很少的图称为稀疏图，反之称为稠密图 没有绝对的界限，一般来说 \(|E| < |V|\log|V|\) 时，可以将 \(G\) 视为稀疏 ...

参考资料： 2027王道数据结构 树基础 - OI Wiki 5.1 树的基本概念 考研中及王道书的树默认为有根树，下面的树均按此定义，为方便考研，所有树的定义名称按王道书来。 会有拓展的补充。 定义 树时 \(n (n\geq 0)\) 个结点的有限集。\(n=0\) 的树称为空树。非空树需满足 有且仅有一个根结点 当 \(n>1\) 时，其余结点可分为 \(m\) 个互不相交的有限集 \(T_1,T_2,\cdots,T_m\) ，其中每个集合本身又是一棵树，称为根的子树。 显然，树的定义是递归的，树是一种典型的递归数据结构。 有关树的定义 森林 (forest) ：每个连通分量（连通块）都是树的图。按照定义，一棵树也是森林。 生成树 (spanning tree) ：一个连通无向图的生成子图，同时要求是树。也即在图的边集中选择 \(n-1\) 条，将所有顶点连通。 双亲（父结点）：向上一层的与之连接的节点，即到根节点的路径上的第二个节点，显然根节点无父亲。 祖先：到根节点路径上的所有结点 ...

4.1 串的定义和实现 串的定义 串，即**字符串（String）**是由零个或多个字符组成的有限序列。一般记为 S=‘a1a2…. an’ 其中，S是串名，单引号括起来的字符序列是串的值。 \(n=0\) 的串，称为空串（用 \(\emptyset\) 表示） 串中的连续子序列被称作该串的子串，而该串就是该字串的主串。子串在主串中的位置，用以其第一个字符在主串中的对应位置表示。 串的存储结构 1.定长顺序存储表示 12345#define MAXLEN 255typedef struct{ char ch[MAXLEN]; int length;}SString; 2.堆分配存储表示 1234typedef struct{ char *ch; int length;}HString; 在 \(C\) 语言中，存在一个称为堆 的自由存储区。可通过调用 malloc 为新生成的串动态分配一块大小等于串长的连续存储空间。分配成功则返回起始地址的指针，否则返回NULL。 3.块链存储 ...

3.1 栈 **栈（stack）**是仅允许在一端进行插入（入栈）和删除（出栈）操作的线性表。 栈顶（Top）: 允许进行插入或删除的一端。 栈底（Bottom）: 固定不变，不允许增删的一端。 空栈：不含任何元素的栈。 栈的基本操作 InitStack(&S) 初始化一个空栈 StackEmpty(S) 判断栈是否为空。 Push(&S,x) 入栈，栈未满就压入 \(x\) Pop(&S,&x): 出栈，非空就弹出栈顶，取出 \(x\) GetTop(S,&x)：读栈顶 DestroyStack(&S): 销毁栈 \(n\) 个不同元素进栈，出栈元素不同排列的个数为 \(\frac{1}{n+1}C_{2n}^n\) ，该公式为卡特兰数。 栈的顺序存储结构 采用顺序存储的栈称为顺序栈，用 \(top\) 指向栈顶元素 12345#define MaxSize 50typedef struct{ Elemtype data[MaxSize]; int top; ...