xhj的博客

线性表线性表 定义：由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进行管理和调度 共享 程序运行过程中，宏观上并行执行，微观上互斥共享软硬件资源 虚拟 利用多道程序设计技术（交替运行程序），让计算机的每个用户专门有一个用户为它访问的感观 异步 程序的执行不是一贯到底而是走走停停，向前推进的速度不可知，只要运行环境相同，操作系统应当保证每次返回的数值相同 功能 进程管理（处理机管理功能） 进程控制、进程同步、进程通信、调度 内存管理（存储器管理功能） 内存分配、内存保护、地...

图概念 图：由顶点集合和顶点间的关系集合组成的一种数据结构 有向图与无向图：在有向图中，顶点对(x,y)是有序的；无向图是无序的 完全图：在有n个顶点的图有n(n-1)/2条边，即为完全无向图；有n(n-1)条边，即为完全有向图 顶点的度：某一个顶点与其相关联的边的条数，有向图度是入度和出度之和 生成树：一个连通图的生成树是其极小连通子图，包括图中所有顶点，包含n-1条边 图的存储结构－邻接矩阵 在图的邻接矩阵表示中，有一个记录仪各个顶点信息的顶点表，还要一个表示各个顶点之间关系的邻接矩阵 网络的邻接矩阵 邻接表 邻接表是邻接矩阵的改进形式，需要把邻接矩阵的各行分别组织为一个单链表、 无向图的邻接表： 有向图的邻接表和逆邻接表： 网络邻接表： 图的遍历与连通性 DFS（深度优先搜索） BFS（广度优先搜索） 连通分量和生成树 极小连通子图（一棵生成树） 广度优先生成树、深度优先生成树 非连通无向图生成的生成树组将组成非连通图的森林 最小生成树（MST） 网络带权重的最小和的生成树 Prim算法：从顶点开始依次找最短边，然后相连 Kruskal算法...

内部排序概述 排序：将一组杂乱无章的数据按照一定规律顺次排列 数据表：待排序数据元素的有限集合 排序算法的稳定性：数据表中两个相同的值在经过算法排序后的相对位置是否改变 内排序：排序期间数据元素全部在内存中 外排序：数据太多，只能部分在内存中进行，需要不断进行内外存的数据转移 排序的时间开销：衡量算法好坏的标志，主要表现是数据比较次数和数据移动次数 总关键字比较次数：KCN 元素移动次数：RMN 内部排序 插入排序：每步将一个待排序的元素按照其关键字的大小，插入到前面已经排好序的一组元素的适当位置上面，直到全部元素插入完毕为止 直接插入排序：从unsorted的列表中找到最大的和sorted列表中最后一个元素交换 折半插入排序：利用折半查找算法，找到合适的位置层层递进插入（类似二叉查找树），实际复杂度取决于数据表的初始排列 2-路插入排序：复制一个新的数据表，遍历原数据表时判断与新数据表的关系选择插入位置 表插入排序：使用链表实现直接插入排序 希尔排序：(缩小增量排序)按照一个k的维度进行排序，开始时k值较大，子序列中元素较少，速度快；后来基本已完成排序，需要移动的元素减少...