小张的博客

# 面向对象

# 概念

  • 对象：属性、方法、对象名。即静态特征、动态特征、名字

  • 消息：对象之间进行通信

  • 类：一组对象

    • 实体类：表示某一具体事物
    • 接口类：面向人的按钮等和面向系统的可调用方法类
    • 控制类：控制活动流

  • 三大原则

    • 封装：定义和实现分离，保证安全性、灵活性，对外只暴露很小的接口
    • 继承：已经存在的类（父类、一般类）作为基础，加入新的内容
    • 多态：不同对象收到同一消息产生不同结果
      • 包含多态：方法作用在父类上，一定可以作用在子类上
      • 参数多态：根据参数不同，调用不同方法
      • 强制多态：用父类定义子类的时候，强制把子类定义成父类
      • 过载多态：同一方法的参数类型不同、数量不同，返回值不同

  • 动态绑定：区别于静态绑定（编译之后即知道调用什么方法），直到运行时才能知道是什么方法，效率低但更灵活

  • 定义：面向对象=对象+分类+继承+通过消息的通信

# 面向对象的分析

按步骤：①认定对象 ②对象分组 ③描述对象间的作用（UML） ④确定对象的操作 ⑤定义对象的内部信息

# 面向对象的设计原则

  • 概述：原则实际上是顶层框架
  • 单一责任原则：对一个类，应该仅有一个引起其变化的原因
  • 开放-封闭原则：软件实体是可以扩展的，但应该是不可修改的
  • 里氏替换原则：父类出现的任何地方，子类都可以替换
  • 依赖倒置原则：细节依赖于抽象概念，抽象概念变细节就变；子类依赖于父类
  • 接口分离原则：将大接口拆分成小接口，不同的小接口通过继承和组合实现不同功能
  • 其他规则

# 面向对象的测试

  • 单元测试：分体测试，即测试属性和方法
  • 系统测试：在环境中的测试
  • 综合测试：随着开发一直需要不断测试，包含类内部的综合测试和类之间的综合测试

分为①算法层（单元测试） ②类层（模块测试 综合测试的类内） ③模板层（集成测试 即综合测试的类间测试） ④系统层（系统测试）

# UML

  • 基本概念：事物、关系、图

    • 结构事物（静态）、行为事物（动态）、分组事物、注释事物
    • 依赖关系、关联关系、泛化关系、实现关系、聚合关系、组合关系
    • 类图、对象图、用例图、序列图、通信图、状态图、活动图、构件图、部署图、包图

  • 事物：UML的名词

    • 结构事物image-20260507220728242

    • 行为事物：消息、状态机、活动

      image-20260507220809989

    • 分组事物：把一堆事物组成一个包（import xxx.xxx）

      image-20260507220902928

    • 注释事物：用来注释

      image-20260507220925547

  • 关系

    • 依赖关系：一个事物的变化影响另一个事物。

      image-20260507231432993

    • 关联关系：描述一组链，链是对象之间的链接（类似ER图）。

      image-20260507221433416

    • 泛化关系：特殊对象可以替换一般对象

      image-20260507221705220

    • 实现关系：一个对象执行的是保证另一个对象执行的契约，图中所示为接口和实现它们的类

      image-20260507221930563

    • 聚集关系：一个类由某些对象实例的组成，由部分指向整体，但是生命周期不同

      image-20260507224410100

    • 组合关系：一个类是另一个类的固定组成部分，生命周期相同（拆下来两者都完蛋）

      image-20260507225736991

  • 类图

    • 用例图：扩展关系（extend）、包含关系（包含与被包含）、泛化关系
    • 序列图：参与者、对象、激活期、生命线、消息
    • 状态图：状态机
    • 活动图：箭头＋方框
    • 对象图
    • 部署图
    • 通信图
    • 构件图
    • 包图

# 设计模式

# 概述

分析变与不变之处，把变化的部分隔离到结构的外部实现。

就是根据不同的类型进行总结分类，例如医疗里针对不同疾病的处理方法。（一共有23个）

# 创建型模式

不管系统的具体实现。例如只用一个接口与用户交流，把具体实现封装。

  • 单例模式：只有一个实例，只有一个访问点（单例类）

  • 工厂模式：new的时候可以new不同的对象，可以自定义实现哪个类

  • 原型模式：直接克隆，而不用new，直接拷贝

  • 生成器（建造者）模式：组成固定，但是生成不固定

    eg：某一类生成时传入参数不固定或为空，需要其它逻辑生成传入参数。某根据时间日期等等来计费的系统

  • 抽象工厂模式

# 结构型模式

# 数据结构

对数据结构的操作：创建、删除、查找、删除

# 时间复杂度

计算总步数

例如，则时间复杂度为，即线性时间。

出现于嵌套，出现于递归。

# 空间复杂度

描述算法运行临时占用的存储空间。

  • 常量空间
  • 线性空间
  • 二维空间
  • 递归空间

看变量定义数量。

# 线性结构

  • 线性表

    • 数组

      顺序存储：依次存储。优点：查找方便；缺点：插入和删除需要移动元素

    • 链表：有node，每个node都有前驱或后继。

      链式存储：用数据+指针方式。优点：插入和删除效率高；缺点：查找不方便（必然是一个循环）

  • 栈

    后进先出，操作的一端为栈顶。

    • 顺序存储
    • 链式存储

  • 队列

    先进先出，插入为队尾rear，删除为队头front。

    循环队列：节约资源

  • 数组、矩阵

# 非线性结构

  • 树（数据量大则用树比较多）

    一个结点的子树的个数成为该结点的度，度为0则为叶子结点

    • 二叉树

      度为零的结点数等于度为二的结点数加一。

      具有n个结点的完全二叉树的深度为。

      • 顺序存储：从1开始编，不是0。对于完全二叉树，若结点编号为i，左孩子编号为2i，右孩子编号为2i+1。缺点：不易存储，且非完全二叉树无法存储。
      • 链式存储：三叉或者二叉【根据根结点的遍历先后，分为先序遍历（先读根）、中序遍历（从下往上先读叶）、后序遍历】

    • 哈夫曼树

      特殊的二叉树：一群结点能组成的带权路径长度最小的二叉树。（每两部分构成一颗子树）

      • 构造方法：选出最小的两个结点构造二叉树，再把构造出的二叉树和剩下的结点里选出两个最小结点组成新的二叉树...以此类推。
      • 哈夫曼编码：把字符集设置权值，构造哈夫曼树

    • 树和森林

      • 树转二叉树：兄弟结点连接，保留长子，删去其它连接
      • 森林转二叉树：先把每棵树转二叉树，然后再连接这么多二叉树的根结点
      • 二叉树转树：结点X的左孩子若存在，则左孩子右边的所有兄弟结点都变成X的子结点
      • 二叉树转森林：根节点有右孩子才能转换为森林（类似上述逆）
      • 树的遍历：先根遍历（对应二叉树的先序遍历）、后根遍历（对应同一棵树对应二叉树的中序遍历，先读叶）

  • 图

    完全图：无向图有n个顶点，则有条边。

    度：关联的点数量（边数）；入度：该点为终点的有向边数；出度：该点为起点的有向边数。

    连通图：所有点都是连接的。

    有向树：有一个顶点入度为0，其他所有结点入度为1。

    • 顺序存储

      邻接矩阵：一个矩阵中某一行或者某一列表示一个顶点。

    • 链式存储

      邻接链表：为每一个顶点建立一个单链表，不要求顺序。

    • 图的遍历

      • 深度优先 ：栈

        空间复杂度：O(n)

        时间复杂度：O(n+边数e)

      • 广度优先：队列

        空间复杂度：O(n)

        时间复杂度：O(n+边数e)

    • 生成树：局域网内部用于路由选择

      • 普利姆算法：时间复杂度

        广度优先，先找权值最小的结点

      • 克鲁斯卡尔算法：时间复杂度

        直接找权值最小的边

    • 拓扑排序

      找入度为0，然后删掉该点以及与该点有关的所有边，后面以此类推。

    • 最短路径-迪杰斯特拉

# 算法

# 递归

时间复杂度O(n)、空间间复杂度O(n)

# 查找

  • 二分查找：查找序列构建为二叉树
  • 哈希表

# 排序

  • 冒泡排序
  • 快速排序
  • 希尔排序
  • 堆排序
  • 归并排序
image-20260513232454289

# 动态规划

  • 0-1背包
  • 最长公共子序列

# 贪心

  • 背包问题

# 回溯法

  • 0-1背包
  • n皇后

# 计算机组成原理

# 基本概念

1、五大组成部分：运算器、控制器、存储器、I/O设备

2、原码（二进制本身）、反码（正数为原码，负数为符号位不变其余取反）、补码（正数为原码，负数为反码加一）

3、浮点数表示

# 校验码

码距：不同数量

奇偶校验码：在编码中增加校验位，来使1的个数为奇数（奇校验）或偶数（偶校验）

海明码：数据有n位，校验有k位，则n和k满足关系：

CRC循环冗余校验：利用生成多项式，为n个数据位产生k个校验码。举例：根据多项式得到最高位次k=3、以及被除数，使用左移k位的值除以被除数（模2），最后得到余数即为CRC码

# 指令系统

  • CISC：复杂的，PC用

  • RISC：简化的，手机用，硬布线

image-20260513234328979

# 流水线

执行时间--吞吐率（执行时间）

执行时间--加速比（时间之比）

# 存储系统

  • 读写存储器（断电丢数据）

    • SRAM：缓存
    • DRAM：内存条
    image-20260513235151297

  • 只读存储器

    • ROM
    • ...

# 总线系统

image-20260513235307536

# 计算机性能评价

  • CPI：执行一条指令所需的时钟周期数
  • MIPS：每秒执行的指令条数（百万为单位）

# 操作系统

# 进程

  • 三态模型：

    就绪，阻塞，运行：运行若时间片到，则转就绪，若等待其它进程则转阻塞；阻塞满足条件则转就绪，就绪被调度则转运行

  • 互斥与同步

    互斥是二者有竞争抢占关系，同步是二者没有。

    • PV操作

      P减一，S>=0则继续执行

      V加一，S>0才执行，若S=0，则从阻塞态唤醒一个进程进入就绪队列

    • 死锁：两个以上进程互相都要对方已经占有的资源

# 存储管理

  • 分页存储
  • 分段存储
  • 段页存储
  • 页面置换算法

# 设备管理

  • 磁盘调度

    • 移臂调度

    • 旋转调度

# 计算机网络

# ipv4地址

image-20260514175454135

每个网段的首地址为网络地址

每个网段的尾地址为广播地址

# 交换机和路由器

一个交换机是一个广播域，一个路由器接口是一个广播域

# 应用层协议端口

Telnet TCP:23

DNS UDP:53

SMTP TCP:25

POP3 TCP:110

FTP TCP:21/20（21用于传输控制命令，20用于传输文件）

DHCP UDP:68/69（68用于服务端，69用于客户端）

# 网络安全

被动攻击：主动攻击前的准备；主动攻击：发动恶意流量

  • 恶意代码

    • 病毒
    • 网络蠕虫（Worm、Macro）
    • 特洛伊木马（Trojan）
    • 后门漏洞（Backdoor）

  • 加密算法

    • 对称加密

      DES

      3DES

      ASE

    • 非对称加密

      公钥加密，私钥打开，确保只有目标对象能收到打开

  • 哈希算法

    输入任意长度数据，输出固定长度

    MD5、SHA-1、SHA-2

  • 数字签名

    用户提出申请，在数字证书上配上私钥加密的签名，用公钥确认对象。常用格式：X.509

# 项目管理&法律法规

# PERT图

关键路径：起点到终点最长的路径叫关键路径。