吴紫航

存储器概述

• 存储元：一个二进制物理器件
• 存储单元：多个存储元组成，一般是一次存取的单位
• 存储体：若干存储单元

存储器分类

• 按作用/层次分类
  • 主存储器
    • 即内存，存放计算机运行期间的数据和程序
    • CPU可以直接进行访问，也可以和Cache和辅存交换数据
    • 容量较小，速度较快，价格较高
  • 辅助存储器
    • 即外存，存放暂时不用的数据和程序，或需要长期保存的信息。
    • CPU不能直接访问
    • 容量大，速度慢，成本低
  • 高速缓冲存储器
    • 即Cache，位于主存和CPU之间，存放正在执行的程序段和数据，加速CPU访问数据
    • CPU可以直接进行访问，可以和内存交换数据
    • 容量小，价格高，存取速度和CPU速度匹配
• 按存取方式分类
  • 随机存储器RAM
    • 存取时间和位置无关，可随机存取，使用方便
    • 常用于主存和缓冲存储器
    • 可分为静态RAM（SRAM），动态RAM（DRAM）
  • 只读存储器ROM
    • 只能随机读出，不能写入
    • 通常存放不变的程序、字库、常数，和RAM共同作为主存的一部分
  • 串行访问存储器
    • 顺序存取存储器SAM：只能按某种顺序存取，存取时间和位置有关，速度慢，如磁带
    • 直接存取存储器DAM：不是全局随机存取，也不是完全顺序存取，折中方案。先确定数据所在小区域，在区域内顺序查找，如磁盘、光盘（详见第7章笔记）
• 按存储介质分类
  • 磁表面存储器
    • 磁盘
    • 磁带
  • 磁芯存储器
  • 半导体存储器
    • MOS型存储器
    • 双极型存储器
  • 光存储器
    • 光盘
    • 比如CD-ROM是只读型光盘，串行访问存储器，不是只读存储器ROM
    • 详见第7章笔记
• 按信息的可保存性分类
  • 易失性存储器
    • 断电后存储信息就会消失
    • 如RAM
  • 非易失性存储器
    • 断电后存储信息不会消失
    • 如ROM、磁表面存储器、光存储器

存储器性能指标

数制与编码

进位计数制和数据间转换

计算机内部用二进制编码信息的原因

• 成本方面：二进制两种状态，用有两个稳定状态的物理器件表示，制造成本低。
• 功能方面：二进制的两种状态，对应逻辑值“真”和“假”，方便计算机实现逻辑运算、进行逻辑判断
• 实现方面：二进制编码和运算简单，通过逻辑门电路很容易实现

进位计数值

基本概念

• 机器语言：计算机能直接识别执行的语言，机器语言的程序由0、1代码序列组成
• 汇编语言：把机器指令表示为助记符，与机器语言指令一一对应
• 高级语言：接近自然语言，按约定符号和规则写程序
• 编译程序：把高级语言程序翻译成机器语言目标代码的系统软件
• 汇编程序：把汇编语言程序翻译成机器语言目标代码的系统软件
• 字长：运算器能并行参与运算的数据位数，取决于CPU内部寄存器的数据宽度
• 系列机：一个厂家生产的，具有相同的系统结构，但具有不同组成和实现的一系列不同型号机器
• 软件兼容：现有的软件在升级换代后的新机器上可以使用
• 虚拟机器：从使用者角度，计算机系统是硬件上的虚拟机器；虚拟机依靠软件存在，软件扩充了系统功能
• 二进制位：是数字计算机中信息最小的位
• 字节：8个二进制数是1个字节。计算机系统存储器按字节编址。
• 内存地址：给存储器每个位置编号，方便访问指定位置，该编号是内存地址

计算机系统层次结构

计算机系统的组成

• 硬件系统：有形的物理设备，计算机系统中实际物理装置的总称
• 软件系统：在硬件上运行的程序、相关数据、文档

排序基本概念

• 输入n个记录，根据记录的关键字大小，输出该序列的重排，使得关键字有序
• 稳定算法：关键字大小相等的两条记录，在输入和输出中的先后顺序不变
• 内部排序：排序期间元素全部存放在内存，大部分内部排序是基于比较来移动记录顺序
• 外部排序：排序期间元素无法全部同时存放在内存，需要不断地在内外存之间移动的排序

插入排序

直接插入排序

算法步骤

基本概念

• 查找：在数据结构中寻找满足条件的元素的过程。查找可能成功或失败
• 查找表：用于查找的数据结构，支持插入，删除，查询元素，不支持插入删除的是静态查找表，否则是动态查找表
• 关键字：标识元素的数据项的值
• 平均查找长度ASL:给定每个元素的查找概率，计算出所有查找过程的平均关键字比较次数

顺序查找和折半查找

顺序查找

• 一般线性表顺序查找：从一端开始，逐个搜索关键字是否满足条件
• 有序表顺序查找：因为有序，有些失败的情况不一定要扫完整个表
• 可以用顺序存储或链式存储
• 可以用二叉树表示查找过程，叶子结点表示失败的情况，方便计算ASL

图的基本概念

图的定义

• 图G由顶点集V和边集E构成，记为G=(V,E)
• V(G)表示G中的顶点的有限非空集，|V|为点数
• E(G)表示G中的边的有限集，|E|为边数
• 图不可以没有顶点，不能是空图，但可以没有边

基本概念

• 有向图：如果E是有向边（弧）的有限集合，则G是有向图，从v到w的弧是顶点的有序对<v,w>，v是弧尾，w是弧头（也称作v邻接到w）
• 无向图：如果E是无向边的有限集合，则G是无向图，边是顶点的无序对（v，w），w和v互为邻接点，边（v，w）依附于v和w两个点
• 简单图：没有重复边，没有顶点到自身的边，数据结构中只讨论简单图
• 完全图：任意两点之间都有一条边，一般是指无向图
• 有向完全图：任意两点之间都有一对方向相反的弧
• 子图：两个图G(V,E)和G'(V',E')，如果V'是V子集，E'是E子集，则G'是G子图
• 生成子图：V'=V的子图
• 点的连通：无向图两个顶点之间有路径则两个点是连通的
• 连通图：任意两点是连通的
• 连通分量：无向图（可以是非连通图）的极大连通子图（一个图的连通分量显然不一定唯一）
• 强连通：有向图两个顶点之间相互可达
• 强连通图：有向图任意两点之间强连通
• 强连通分量：有向图的极大强连通子图
• 生成树：连通图的生成树是包含图中全部顶点的极小连通子图
• 顶点的度、入度、出度：无向图顶点上依附的边数为度（记为TD）；有向图根据出边和入边进一步区分度为入度和出度（记为ID和OD）
• 无向图的顶点度之和是边数两倍
• 有向图顶点入度和 = 出度和 = 图边数 = 度数和的一半
• 带权图（网）：给图的边标上权值的图
• 稠密图、稀疏图：边数少的图为稀疏图，反之为稠密图。一般认为|E|<|V|log|V|时为稀疏图
• 路径：顶点到的路径指的是顶点序列，路径上边个数是路径长度，首位顶点相同的路径叫做回路或者环。n个顶点的图，如果边数大于n-1，则一定有环
• 简单路径：顶点不重复的路径
• 简单回路：除了首位顶点外，其他顶点不重复的回路
• 距离：两个顶点的最短路径长度，如果不存在路径则距离为无穷
• 有向树：一个顶点的入度为0，其余顶点的入度为1的有向图

树的基本概念

树的定义

• 树是n()个结点的有限集
• n=0为空树
• 有且只有一个称为根的结点
• n>1时，其余结点可分为m()个互不相交的有限集，每个集合也是树，称为根的子树。

树的特点

• 根没有前驱，其他点有且只有一个前驱
• 所有点都可以有零或任意多个后继
• n个点的树有n-1条边（数学归纳法易证）

串定义

• 字符串简称串
• 由零个或多个字符组成的有限序列，记为，
• 空串用空集表示
• 串中任意多个连续字符子序列称作子串，包含子串的叫主串
• 子串的位置指子串第一个字符在主串中的位置
• 两个串相等，指长度相等且对应位置字符相等
• 串的逻辑结构和线性表类似，但串的数据对象仅为字符，且串的操作对象一般是子串。

串的存储结构

• 定长顺序存储：一般利用定长数组实现
• 堆分配动态存储：利用malloc和free函数
• 块链存储：每个结点可以放一个字符，也可以放多个。例如结点大小可以是4，最后一个结点如果不满4个字符用#补齐。

串的模式匹配

栈

定义

• 只能在栈顶进行插入和删除的线性表
• 后进先出结构
• 重要的数学结论：n个不同的元素，进栈顺序已知，则出栈顺序不同的排列有

顺序存储

• 利用连续存储单元存放元素，同时附设一个栈顶指针top
• top可以表示栈顶元素的下标（非空情况从0开始），也可以表示栈顶元素的位序(数值上等于栈大小，非空情况从1开始)
• 前者空栈时，top为-1；后者空栈时top为0
• 前者进栈为，后者进栈为
• 前者出栈为，后者出栈为
• 共享栈
  • 将两个栈的栈底设置在一维数组的两端，栈顶向内延申共享空间。
  • 以top表示栈顶元素下标为例
    • 时1栈为空
    • 时2栈为空
    • 时栈满

线性表的定义

• 线性表是具有相同数据类型的n个()数据元素的有限序列
• 为表长
• 用命名，则表示为，注意从1开始
• 特点
  • 元素有限
  • 逻辑上有顺序性（注：这里指先后次序而不是物理的顺序存储）
  • 表中元素为数据元素，类型相同，存储空间大小相同
  • 不考虑存储结构，属于逻辑结构

线性表的顺序表示

定义

• 线性表的顺序存储称作顺序表
• 线性表位序从1开始，数组下标从0开始
• 特点：逻辑结构和物理结构相同（插入删除要移动大量元素），可随机存取、存储密度高