NoResponse's Blog

# Ch6 # 概念 G=(V,E)G = (V, E) G=(V,E) 图的顶点至少要有一个，边可以没有 顶点数：∣V∣|V|∣V∣ 边数：∣E∣|E|∣E∣ 有向图、无向图 简单图（不存在重复边、不存在到自身的边）、多重图 度、入度、出度 TD(v)=ID(v)+OD(v)TD(v) = ID(v) + OD(v) TD(v)=ID(v)+OD(v) 有向图所有顶点的入度和出度之和相等，且等于边数 路径、路径长度、回路 简单路径、简单回路（顶点不重复出现） 距离（从 u 到 v...

# Ch5 # 树 树的性质： nnn 个节点的树有n−1n-1n−1 条边 结点数nnn 等于所以结点的度数和 + 1 度为mmm 的树中第iii 层上之多有mi−1m^{i-1}mi−1 个结点 高度为hhh 的mmm 叉树中至多有(mh−1)/(m−1)(m^h-1)/(m-1)(mh−1)/(m−1) 个结点 度为mmm，具有nnn 个结点的树的最小高度hhh hmin⁡=⌈log⁡m((m−1)n+1)⌉h_{\min} = \left\lceil \log_m \left( (m - 1)n + 1 \right)...

# Ch4 # 模式匹配 i: 主串当前待比较的字符位置 j: 模式串当前待比较的字符位置 字符串模式匹配，在主串中找到与模式串相同的子串 # 暴力算法 遍历主串，从每个和第一个字符相同的位置开始，继续比较后继字符 时间复杂度：O(mn)O(mn)O(mn)（主串长度 n，模式串长度 m） # KMP...

# Ch3 # 栈 LIFO # 顺序栈的实现 定义12345#define MaxSize 50typedef struct{ ElemType data[MaxSize]; int top;}SqStack; 初始化123void InitStack(SqStack &S){ S.top = -1;} 判断空123456bool StackEmpty(SqStack S){ if(S.top == -1) return true; else return...

# Ch1 计算机系统自下而上可以大致分为硬件、操作系统、应用程序、用户 OS 管理各种硬件，为应用程序提供基础，充当计算机硬件与用户之间的中介，是计算机系统中最基本的系统软件 # 基本概念 # 操作系统的功能 管理计算机系统资源 处理机管理（进程 / 线程管理）、存储器管理、设备管理、文件管理，向用户提供接口 作为用户与硬件系统之间的接口 命令接口（联机控制方式和脱机控制方式） 联机命令接口也称为交互式命令接口，由一组键盘操作命令组成 脱机命令接口也称批处理命令接口，由一组作业控制命令组成 程序接口 由一组系统调用组成 实现了对计算机资源的补充 虚拟机 #...

# Ch1 绪论 数据 数据元素是数据的基本单位 数据对象 数据类型：原子类型、结构类型、抽象数据类型 数据结构：三要素包括逻辑结构、存储结构和数据的运算 逻辑结构：集合、线性结构、树形结构、图状或网状 存储结构：顺序存储、链式存储、索引存储、散列存储 数据的运算：定义针对逻辑结构，实现针对存储结构 算法的特性：又穷行、确定性、可行性、输入、输出 好的算法还应该考虑：正确性、可读性、健壮性、高效率和低存储量需求 复杂度：时间复杂度、空间复杂度

# Ch2 线性表 存储结构：顺序表（数组），链表 # 顺序表 逻辑顺序和物理顺序一致，都连续 按下标访问 O (1)，插入操作平均移动 n/2，删除操作平均移动 (n-1)/2 静态分配12345#define MaxSize 50typedef struct{ ElemType data[MaxSize]; int length;}SqList; 动态分配12345#define InitSize 100typedef struct{ ElemType *data; int MaxSize,...

Aggregate analysis a sequence of nnn operations takes worst-case time T(n)T(n)T(n) int total. In the worst-case, the average cost, or amortized cost, per operation is T(n)/nT(n)/nT(n)/n. example: stack with MultiPop(int k, Stack S) Accounting method When an operation’s amortized cost is...

# Ch7 输入 / 输出系统 # I/O 接口 inerrface，主机与外设之间的交接界面 # 功能 进行地址译码和设备选择 实现主机和外设的通信联络控制 解决时序、工作速度不同的问题 实现数据缓冲 信号格式的转换 电平转换、并 / 串或串 / 并转换、模 / 数或数 / 模转换 传送控制命令和状态信息 CPU 通过接口中的命令寄存器发出启动命令给外设，外设就绪是传回 Ready 状态信息通过接口中的状态寄存器反馈给 CPU # 基本结构 主机侧通过 I/O 总线与内存、CPU 相连。数据缓冲器用来暂存与 CPU...