xhj的博客

计算机网络系统结构和协议 体系结构：研究系统中各个组成成分及其关系的一门学科。 计算机网络体系结构：定义和描述一组用于计算机及其通信设施之间互连的标准和规范的集合，遵循这组规范可以很方便的实现计算机间的通信。 开放系统互连基本参考模式（OSI/RM）的设计原理 分解：将整个系统划分为若干易于实现和控制的子模块，并通过对各模块的功能、交换的数据结构和时序进行约定，协调模块之间的动作，保证系统设计的合理性和互操作性。同时可以根据各子模块的依赖关系，使用结构化的设计和实现方法，采用具有层次结构的模型与之对应。 抽象：标准的提出应当独立于实现的具体环境， OSI/RM 的确立采用了三级抽象技术。 提出 OSI/RM：建立计算机网络在概念和功能上的框架，包括确定 OSI 的层次模型，以及公共术语、属性和子模块的功能等。 提出 OSI 服务定义：在 OSI/RM 的基础上，定义各个子模块可提供的服务，即确定各个子模块的外观特性。 定义 OSI 协议规范：定义一组为确保子模块服务的提供而应遵循的规则。 子模块（层）划分的原则： 各子模块具有...

绪论O记号 问题：随着问题规模的增长，计算成本是如何变化的？考虑的是计算成本的增长趋势 分析：在问题规模足够大的情况下，计算成本如何变化： 需要执行的基本操作次数T(n) 需要占用的存储单元数量S(n)，一般不考虑空间占用 对于T(n)转为O(f(n)) 常系数可以忽略，低次项可以忽略 O复杂度计算基于悲观的角度 判断代码的复杂度 常数复杂度O(1)：不含转向（循环、调用、递归等），部分特例虽然含有循环、调用、递归等，但是需要考虑到实际情况才能确定。 对数复杂度O(log n)：高效，复杂度无限接近常数 多项式复杂度O(n^c)：界定为多项式的最高次项 线性复杂度O(n) 指数复杂度O(c^n)：计算成本高 1234567void func(int n){ // n是正整数 int i = 1; while(i<=n)i*=2;}// 被嵌套的深层语句是i*=2；频率由i<=n决定，显然时间复杂度为O(log n) 冒泡排序 观察： 有序序列中，任意一对相邻元素顺序 / 无序序列中，存在一对相邻元素逆序 ...

线性表线性表 定义：由n个数据元素组成的有限序列；原则上数据类型可以不一致，但存储类型可能会做出一定的限制 特性: 除第一个元素外,其他元素只有一个直接前驱;除了最后一个元素,其他元素只有一个直接后继. 表示方式:顺序存储方式/链表存储方式 顺序表 定义:将线性表中的元素相继存放在一个连续的存储空间中,可以利用一维数组描述数据结构 特性:所有元素的逻辑先后顺序和物理存放顺序一致 123456789101112131415161718192021const MAX_SIZE = 100// SQListA 顺序表的静态存储表示type SQListA struct{ data [MAX_SIZE]int64 length int}// SQListB 顺序表的动态存储表示type SQListB struct{ data *int64 length int}// Init_SQ 初始化顺序表func Init_SQ(list *SQListA) bool{ list.d...

树与二叉树树 定义：树是n个结点的有限集合，在任何一个非空的树中 有且只有一个根节点 子女：结点的子树非空，结点子树的根即为结点的子女 双亲：结点有子女，该结点是子女的双亲 兄弟：某一结点的所有子女，互为兄弟 度：结点的子女个数 分支结点：非终端结点 叶：终端结点 祖先：沿着双亲的路径返回均为祖先 子孙：下属所有结点 结点的层次：规定根节点在第一层，子女依次加1 深度：层次的最大值 树的高度：根节点的高度->所有子女高度+1 有序树：树的结点的各棵子树是从左到右有顺序的 无序树：无序，各棵子树之间的次序可以呼唤 森林：m棵互不相交的树组成 二叉树 二叉树中不存在度大于2的结点 满二叉树 完全二叉树：k层二叉树除了第k层有从有向左的连续缺失的结点 二叉树的顺序表示 按照满二叉树的顺序，有数则填，无数则留空 极端情况下，资源利用率特别低 二叉树的链式表示 二叉链表 三叉链表 二叉树遍历 前序遍历（VLR）【-+a*b-cd/ef】 中序遍历（LVR）【a+b*c-d-e/f】 后序遍历（LRV）【abcd-*+ef/-】 ...

栈与队列栈Stack 栈：只允许在一段插入和删除的线性表（LIFO） 栈是操作受限的单向链表，只能在头部和尾部有操作 队列Queue 队列：先进先出的线性表（FIFO），只允许一端插入，另一端删除 循环队列：为了避免空间浪费引入。需要注意的是，插入的时候要注意要预判队首和队尾是否相连。

查找平均查找长度1ASL = 1/2 ASL_success + 1/2\*ASL_failed = 3/4\*(n+1) 有序表的查找 折半查找（Binary Search， 二分查找） 高效率的查找方案，前提条件是查找表中的记录有序 二分查找的路径会得到一个二叉树，称为判定树。n个结点的判定深度是log2n+1。 分块查找（Blocking Search，索引顺序查找） 将查找表分为几块，块间有序，块内无序 在查找表的基础上附加一个索引表，索引表按关键字有序查找方法的比较 查找方法 顺序查找 二分查找 索引查找 ASL 最大 最小 中等 表结构 有序表、无序表 有序表 分块有序表 存储结构 顺序存储结构线性链表 顺序存储结构 顺序存储结构线性链表 二叉搜索树 具有以下特性的二叉树或空树 每个结点都有一个作为搜索依据的关键字，所有结点的关键字互不相同 左子树上的所有结点的关键字都小于根节点关键字 右子树上的所有结点的关键字都大于根节点关键字 左右子树也是二叉搜索树 特性： 左子树<根结点<右子树 如果对一棵二叉搜索...

文件管理文件系统基础文件是具有符号名，由字节序列构成的数据项集合（文件系统的基本数据单位，文件名是文件的标识符号） 文件系统的功能 分配文件磁盘空间：管理文件块（位置和顺序）、管理空闲空间（位置）、分配算法（策略） 管理文件集合：定位（文件及其内容）、命名（通过名字找到文件）、文件系统结构（文件组织方式） 数据可靠和安全：安全（多层次保护数据安全）、可靠（持久保存、避免被破坏） 文件的属性：名称、类型、位置、大小、保护、创建者、时间、最近创建时间 文件头：文件系统元数据中的文件信息 文件的逻辑结构 文件大小 大多数文件很小：需要对小文件提供很好的支持，块空间不能太大 有的文件特别大：必须支持大文件，大文件的访问需要高效 文件分配（如何表示分配给一个文件数据块的位置和顺序） 分配类型：连续分配、链式分配、索引分配 考虑指标：存储效率（连续分配的外部碎片）、读写性能（链式和索引分配访问速度） 顺序文件：文件头指定起始块和长度（文件读取的性能好，搞笑顺序和随机访问；有碎片和文件增长无法实现的问题） 链式文件：文件以数据块链表方式存储，文件头包含了第一块和最后一块的指针（修改...

数组与广义表一维数组 数组是相同类型的数据元素的集合，而一维数组的每个数组元素是一个序对，由index和value组成 一维数组一般会被看成向量vector，二维数组一般被看成向量组 多维数组特殊矩阵的压缩存储 特殊矩阵是指非零元素和零元素的分布有一定规律的矩阵 特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵,为了节省存储空间,对可以不存储的元素,如零元素或者对称元素,不再存储 对称矩阵 沿着主对角线只需要一半的空间 三对角矩阵 沿着主对角线形成一个列表 稀疏矩阵 如果矩阵中很多数量是0，只需要存储对应的坐标和value的值即可 在稀疏矩阵的三元组表中，非零矩阵元素按照行存放，行号相同的时候，按照列号递增存放 十字链表 对于稀疏矩阵，当非0元素的个数和位置在操作过程中变化较大时（如相加），采用练市存储结构比较方便 广义表 列表里面的元素自定义，也可以是一个类型，可以类比Python中的list Samples： A()：深度1，长度0 B(6,2)：深度1，长度2 C(‘a’,(5,2))：深度2，长度2 D(B, C)：深度3，长度2 F(4, F)：深度...

数据通信原理通信系统的基本组成通信三要素： 信源：信息的发送者，是发出各种信息（文字、图片或者数据）的信息源 信宿：信息的接受者 载体：传送信息的媒体（信道） 噪声的存在对通信产生不利影响 通信系统的基本组成 变换器：将信源发出的信息变为载体上看传输的格式 反变换器：将载体上传输的信息变换成信宿可识别格式 信道：信息可以单向传输的途径 按传输类型分类： 有线信道 无线信道 按传输方式分类： 模拟信道 数字信道 信道带宽：信道可以不失真地传输信号的频率范围 信道容量：信道在单位时间内可以传输的最大信号量 数据传输速率（bps）：信道在单位时间内可以传输的最大比特数。 差错率、误码率：出错/总数、与传输距离成正比 由于噪声的影响和信道带宽的限制，信号可能发生失真 调制/解调：利用模拟信道支持数据信息传输的技术 调制：将数据信息变换成适合于模拟信道上传输的电磁波信号（数字->模拟） 解调：将从模拟信道上收取的载波信号还原成数据信息（模拟->数字） 调制解调器：具有调制、解调功能的通信设备 调制方法 调制依据：模拟信号的三...

操作系统概述操作系统的概念、特征、功能以及提供的服务 概念 控制程序（防止不当使用、为用户提供服务） 一个系统软件 控制程序执行过程 防止错误或者计算机的不当操作 执行用户程序 为用户程序提供各种服务，方便用户使用计算机 资源管理器（连接软件硬件，管理资源被高效利用，解决冲突确保公平） 应用程序和硬件之间的中间层 管理各种计算机软硬资源 提供访问计算机软硬资源的高效手段 解决资源访问冲突，确保资源公平使用 特征 并发 计算机系统中存在多个运行的程序，需要OS进行管理和调度 共享 程序运行过程中，宏观上并行执行，微观上互斥共享软硬件资源 虚拟 利用多道程序设计技术（交替运行程序），让计算机的每个用户专门有一个用户为它访问的感观 异步 程序的执行不是一贯到底而是走走停停，向前推进的速度不可知，只要运行环境相同，操作系统应当保证每次返回的数值相同 功能 进程管理（处理机管理功能） 进程控制、进程同步、进程通信、调度 内存管理（存储器管理功能） 内存分配、内存保护、地...