软设知识点记录
以下是我个人考软件设计师的一些经验，本人一共考了两次软件设计师，第一次下午题查三分，第二次成绩还没出，虽然没什么悬念，这里分享一下我考软件设计师的一些经验分享
需要知识储备
C语言Java或C++数据结构没了考试结构
上午题 数据结构知识uml流程图设计模式软件开发模型杂七杂八 下午题 数据库（类似阅读理解，找不同）一到三题都是阅读理解，答案基本在文中都能找出来算法题设计模式题学习方法
学习方法有很多种，但是绝对不推荐买软官网卖的书
本人使用的方法
直接真题，哪题不懂搜哪题，记录笔记，归纳知识点，因为考点比较杂，记录到一定时间时要对笔记进行归总，哪些笔记属于同一个知识点，到时复习时又个联想记录方便，也有助于记忆
完善基础
C语言 最好先学个C，不想学C，想速成考证的，也不是不行，就算下午题第四题不写，一分不拿，光靠其他几题也是可能通过的，不过会增加之后的学习难度，和对数据结构知识理解的难度作为基础学习对于往后学习也有帮助C学习资源推荐MOOC中国大学，选个国家精品看就行，学到 结构类型、指针、链表差不多够用了中国大学MOOC 程序设计入门——C语言 翁恺 数据结构 大部分数据机构的课程都是使用C语言来讲解的，C有基础后，数据结构就是一种思想，虽然软件设计师考的比较浅，但是如果想进行往后的学习，敲一敲代码还是比较有必要的，整门课程学习数据结构资源推荐 MOOC ，数据结构 浙江大学的也是国家精品中国大学MOOC 数据结构 浙江大学 Java Java是下午题最好拿分的，只要五个空，拿满就15分，性价比最高的题目，第六题要结合设计模式一同理解作答，光靠找技巧不容易哪满分，找技巧得分应该不会超过9分，要拿满只要学完Java基础后多理解一个设计模式就行资源推荐MOOC Java核型技术初级看到38p差不多了设计模式，菜鸟教程，理解为主，从整体看，从结构看到细节，到数据流走向中国大学MOOC Java核心技术 浙江大学菜鸟教程 设计模式
使用51CTO小程序刷题，这个是比较实用的，直接刷题，哪题不懂，学哪题，还可以加入学习群一起学习，不理解的发到群上，虽然基本也没什么用，但是群上吹吹水放松一下还是很不错的
买课，针对考试的课程有很多，我买了51CTO的课，选一个便宜的，上午100的视频，下午99的视频，就算零基础，有充分的方法，少走弯路一次过软件设计师完全不是问题，不推荐买几千的课程，没必要
随便找的考证课程
我还记录了很多很多笔记在OneNote，都是个人自然语言描述有需要可以联系我
以下都是我考前复习的一些随笔
数据结构
挂在右子树上最小堆，哈夫曼树，霍夫曼树，最优二叉树提高编码效率图的遍历； DFS深度优先遍历BFS广度优先遍历杂项记录
计算执行时间，取指，分析，执行，100条 顺序方式，（取指+分析+执行）*100流水线方式（取指+分析+执行）*1+（分析+执行） * 99 系统总线 地址数据控制 系统初始化过程，按照自底向上可分为 片级初始化板级初始化系统级初始化 以软件初始化为主主要进行操作系统初始化 加载设备驱动建立内存加载初始化其他软件模块创建程序应用环境，将控制权交给应用程序 嵌入式操作系统 微型化可定制实时性可靠性易移植性动态规划：
01背包问题：
要求装尽价值尽可能多的物品，求最大价值在背包中和不在背包中，0和1 数据流图平衡：任何一个数据流子图必须与它上一层父图的某个加工对应，二者的输入数据流和输出数据流必须保持一致，此即父图与子图的平衡，父图与子图平衡中，数据流的数目和名称可以完全相同，也可以在数目上不相等，但是借助数据字典中数据流描述，确定父图中的数据流是由子图中几个数据流合并而成的，也即子图是对父图中加工和数据流进行分解结构化分析一般包括以下工具：
数据流图（Data Flow Diagram ）数据字典（Data Dictionary）结构化语言判定表判定🌲
用例之间的关系：
包含扩展泛化
命名冲突：
两个属性名相同，但是分别属于两个不同的关系模式，可以通过“关系名.属性名“区别。
活动图和状态图的区别：
活动图主要描述行为的动作
状态图主要描述行为的结果
第四题
01背包问题
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-boJlKirk-1604904857994)(…/…/…/Library/Application Support/typora-user-images/image-203018177.png)]
C是一个二维数组保存最优的装包方案
递归式
i=0 没有物品， T=0 背包容量为零的时候，价值为0T<w[i]，如果第i个物品的重量比背包容量大了，第 i 件物品无法装入背包，所以，当前的最大价值就是i-1个物品时的最大价值i>0 T>=w[i] 还有物品，并且 背包容量能装下第i个物品，装入物品时背包容量会减少， c[i-1] [ T-w[i] ] 当前物品是w[i]，装入后是T-w[i]对应的前 i-1 个物品的价值加上第i个物品的价值的总和对比c[i-1] [T] 不装这个物品的总和进行对比，选出最大值
c[ i ] [ j ] 表示i个物品在背包容量为 j 的情况下最优装包方案能获得的最大价值
采用大方法是，动态规划设计方法，动态规划和分治法大差别就是会保存中间结果
采用大是自底向上的方式，要求出第六个物品的最优解需要求出前五个物品的最优解
代码实现
#include<stdio.h>#include<math.h>#define N 6 #define maxT 1000int c[N][maxT]={0};//c[i][j]：表示前i个物品在背包容量为j的情况下最优装包方案所能获得的最大价值int Max_Value(int v[N],int w[N],int i,int j){int temp;if (c[i][j] != -1){//初始化时把值全部设置为了-1，如果不是-1，说明已经对这个值进行了更改，将保存的值返回，返回当前价值return c[i][j];}if (i == 0 || j == 0) {c[i][j] = 0;//没有物品 和 背包容量为 0 的时候，对应的第i件物品的，重量为j的物品，价值为0//当c[0][j]的值一定为0，//要考虑在前 i 件物品中拿取，就要考虑i-1件物品中拿取的最优情况 ，价值才有可能是最大的，前面拿取的都不是最大的，后面拿取的自然也不是最优的，都需要是最优的事，依次往前推，保证每次拿取的都是最优的，这是递归的思想，在求解 i 时，先求解 i-1，求解 i-1 时先求解 i-1-1 。。。。//当递推到 i 件时候，要考虑物品时拿还是不拿，如何收益才是最大的//拿的了和拿不了，j<w[i]是拿不了的//能拿的情况要考虑拿了之后收益是否更大，拿这件物品需要花费的w[i],除去这w[i]的子问题应该是c[i-1][j-w[i]]，j是会变化的，j是原来的可用空间，拿取之后克可用空间变少，j减去w[i]加上第i个物品的价值，对比不放入第i个物品的价值，选个最大的价值返回} else {//在程序实现时直接不用考虑放不进去的情况c[i][j] = Max_Value(v, w, i - 1, j);// if(__(2)__){if (j >= w[i]) {//可用空间大于物品重量// temp = __(3)__;temp = Max_Value(v, w, i - 1, j - w[i]) + v[i];//选择放还是不放 if (c[i][j] < temp) {//新加入的值比原有的价值大，进行更新// __(4)__;c[i][j] = temp;}}}return c[i][j];}int Memoized_Knapsack(int v[N], int w[N], int T) {/*** v[]:价值数组* w[]:重量数组* T: 背包容量* */// initialize arrayfor (int i = 0; i < N; i++) {for (int j = 0; j <= T; j++) {c[i][j] = -1;}}return Max_Value(v, w, N - 1, T);}int main() {int v[N] = {1, 6, 18, 22, 28};int w[N] = {1, 2, 5, 6, 7};int knapsack_capacity = 11;int max_value = Memoized_Knapsack(v, w, knapsack_capacity);printf("max_value: %d", max_value); // max_value: 40return 0;}
N皇后问题
n*n，如果是4 * 4 的棋盘上就要摆放4个皇后
queen[ i ] : i 表示为第几个皇后，value表示第 i 个皇后在第几列，一行只能有一个皇后，所以 i 代表第几个皇后
能成功放置就递归调用，移动到下一行根据纵向和斜向是否产生冲突判断是否要进行下一次行递归放置，当棋子数目达到，说明皇后图完成，可以进行输出
#include <stdio.h>#include "stdlib.h"#define n 4int queen[n+1];//如果定义成queen[n]是没有queen[4]的，所以要定义成n+1，queen[0]是不使用的void Show(){int i;printf("(");for (i=1;i<=n;i++) {printf("%d",queen[i]);}printf(")\n");}//place 放置 //是否能放置皇后，可以返回1，否则返回0int Place(int j){int i;for (i=1;i<j;i++) {//i表示行，for i 说明一行放置一个皇后，不会产生行的冲突，所以只要判断是否处于同一列或者同一斜线上//判定是否处于同一列，//判定是否处于同一条斜线,if (queen[i]==queen[j] || abs(queen[ j ] - queen[i]) == (j-i) ) {return 0;}}return 1;}void Nqueen(int j){int i;for(i = 1 ; i<= n;i++){//这里是皇后图的每一行，每一行都要放置一个皇后，从左到右的判断能否放置，就算找出了一组皇后图序列，i也会继续往后走，可能会找出其他可能的皇后图序列queen[j] = i;if(Place(j)){if(j==n){Show();//第一组序列是2413，输出时，queen的第一列停留在2的位置，说明第一列还没有走完，可以继续往下走，直至走到i==n时时完全尝试完了第一列放置皇后的所有可能，所以走到i=3的时候产生了第二组的皇后图序列}else{Nqueen(j+1);}}}}int main(int argc, char *argv[]) {Nqueen(1);return 0;}
(2413)(3142)
总结，递归的判断某个位置是否能放置，递归分段就是jn，到达这个分水岭就说明n*n的数组中成功放置了n个皇后，得出来一组n皇后序列，但是可能不止的出一组，在一列中尝试，尝试第二列，尝试第三列。。。最后jn，皇后序列输出，但是第一列的循环还没有结束，还能继续往下走，重复的尝试第一列第 i 个的放置，第二列，第三列，。。。最后的结束应该是 i == n ，第一列的最后一个位置也尝试完毕
核心思想就是不断设立新的基准，选出前面的最优解
第四题历年情况：
下：01背包问题、动态规划、自底向上、实例计算
上：四皇后图、回溯法、实例计算
下：最大字串对数、动态规划、复杂度、实例计算
上：钢条切割最大利益、动态规划、复杂度
模拟1:普通题目
哈密尔顿回路
走过的顶点应该是全部顶点数最后一个顶点应该与第一个顶点相连到达最后一个顶点，并且最后一个顶点与起始顶点是有路径的
下午题情况规划
第一题：
使用结构化语言进行描述，while、if、else，自然语言抽象描述数据流图平衡数据流组成，直接列出关系模式属性就行分解子加工第二题：
关系是否存在函数依赖对原有联系需要增加属性，是否要增加实体是否需要增加一个实体，将两个实体的联系单独形成关系模式，列出关系模式，列出该关系模式的主键，可以是组合组建增加弱实体，弱实体要使用双层方框全码概念 关系中只有一个候选码，并且这个候选码包括了全部的属性，称之为全码需要包括所有的属性，这里只有申请号是候选码，候选码没有包括全部属性，所以不是全码第三题：
推理类图，每推理出一项就标记出来，少打断思路类必要的属性，不仅是段落中的说明还要归纳文中整体的说明，根据联系状态，如1对多，一个治疗对应多个护士，但是治疗的段落中没有提及护士的编号，这是需要增加的基本事件流 主动语态：名词-动词-名词顾客登录系统、顾客浏览书籍信息 备选事件流 从基本路径的第一句开始不断问自己还可能发生别的事吗如果书籍库存量为0，顾客无法查询该书籍信息若购买数量超过库存量，提示库存不足 观察者模式添加需求新增一个被观察者对象群组B的主页，对于观察者，新增一个“加入群组B”的方法，加入之后，就可以接收被观察者群组B的主页变动所发送的通知第四题：
注意做题时间
采用的算法策略，动态规划、分治、回溯、
深度优先
第六题：
观察者设计模式（Observer）
一对多的依赖关系，当主题Subject状态发生改变是，所有依赖它的相关的对象，都会收到通知，自动跟新自己的状态，observer为观察者，Subject为主题Subject有一个观察者的对象列表，主题对象状态发生改变的时候，主题对象会调用列表中所有观察者对象的方法观察者对象实现Observer所以观察者对象都有update方法Attach和Detach增加和删除观察者对象Notify通知，通知列表中观察者对象进行更新关联关系 一种拥有关系，一个类知道另一个类的属性和方法 officeDoc是Subject的实现类，观察者对象数组应该存放在officeDoc类中，统一的调用实现了Observer接口的对象的update方法添加观察者要在观察者的构造函数调用被观察者的添加观察者方法添加，这是观察者和被观察者之间的关联关系策略设计模式（Strategy）
定义了一组算法，将每个算法都封装起来，并且使他们之间可以互换
比如出行的时候会选择不同的出行方式，每种都是一种策略
可以使用策略模式去解决这种问题，管理一组同类型的算法，并且这种算法完全互斥，任何时候，多个 策略中只有一个可以生效
看了两个例子，一个简单例子，一个在原有基础上进行了改进
基本思想就是Strategy规定ConcreteStrategy这些策略上实现规定，具体应该有哪些方法，自身可以实现方法但是主要是以一个抽象父类的角色进行简单的规定
ConcreteStrategy作为策略的具体实现，重写或覆盖Strategy的方法，
Context作为上下文角色，一个封装角色，承上启下的作用，屏蔽高层模块对策略，算法的直接访问，封装，将访问算法的方法封装起来，要使用算法，就要按照context给出的方法来进行访问
策略模式实现
public abstract class Strategy {//算法方法public abstract void algorithmInterface();//每个策略必须具有的方法和属性}
public class ConcreteStrategyA extends Strategy {@Overridepublic void algorithmInterface() {System.out.println("算法A实现");}}
具体的算法实现
public class Context {Strategy strategy;public Context(Strategy strategy) {this.strategy = strategy;}//上下文接口public void contextInterface() {strategy.algorithmInterface();}}
通过context的接口来连接使用Strategy中实现的算法
public class Client {public static void main(String[] args) {Context context;context = new Context(new ConcreteStrategyA());context.contextInterface();context = new Context(new ConcreteStrategyB());context.contextInterface();context = new Context(new ConcreteStrategyC());context.contextInterface();}}
改进思路
抽象Strategy类中定义了很多方法，但是实现类中并不一定想要实现，但是Strategy为抽象类，就必须要实现这个方法，所以在写实现类时可以通过写特殊的类来单独实现那个比较特殊的功能
public abstract class Duck {FlyBehavior flyBehavior;QuackBehavior quackBeahavior;public Duck(){//子类的构造函数中可以定义行为}//在本抽象类中已经自己实现了public void Quack(){// System.out.println("~~嘎嘎嘎~~");quackBeahavior.quack();}
public class GreenHeadDuck extends Duck {public GreenHeadDuck(){//行为轴展示具体的行为flyBehavior=new BadFlyBehavior();}
public class BadFlyBehavior implements FlyBehavior {@Overridepublic void fly() {System.out.println("---我不会飞---");}}
生成器模式（Builder）
以造车的例子举例
builder就是造车的规范，规范了车应该有轮子，框架，、、
ConcreteBuilder就可以看作不同品牌的车，规定了具体的实现，实现了builder的规范，通过getResult，返回实体
Director是一个指导类，任务就是你把你想创建的品牌车辆交给他，他按照步骤进行创建，然后返回创建好的对象，客户端通过访问Director来获取创建的实体
class Director {private Builder builder;director(Builder bld) {builder = bld;}void produceCar() {//这里对步骤进行控制builder.buildFrame();builder.buildWidget();builder.buildWheel();builder.buildEngine();}Car getCar() {builder.getCar();}}
public class Test {public static void main(String[] args) {Builder bld = new EconomicBuilder();//代表要创建ConcreteBuilder，告诉Director，Director就会按照ConcreteBuilder的要求进行创建Director director = new Director(bld);director.produceCar();Car car = director.getCar();}
桥接模式（Bridge）
将抽象部分与实现部分分离开，使他们可以独立变化
public abstract class Shape {Color color;public void setColor(Color color) {this.color = color;}public abstract void draw();}
public class Circle extends Shape{public void draw() {color.bepaint("正方形");}}
public class Client {public static void main(String[] args) {//白色Color white = new White();//正方形Shape square = new Square();//白色的正方形square.setColor(white);square.draw();//长方形Shape rectange = new Rectangle();rectange.setColor(white);rectange.draw();}}
装饰器模式Decorator
对已经存在的类进行装饰，以此来扩展一些功能
Component 为统一接口，是装饰类和被装饰类的基本类型
ConcreteComponent为具体实现类，是 被装饰类，本身是个具有一些功能的完整类
Decorator 装饰类，实现了Component，同时内部还维护了一个ConcreteComponent的实例，可以通过构造函数初始化
Decorator通常采用默认实现，他的存在仅仅是一个声明，主要产出装饰类的子类，子类才是富有装饰效果的装饰产品类
ConcreteDecorator是具体的装饰产品类，每一种装饰产品类都有特定的装饰效果，可以通过构造起声明装饰那种类型的ConcreteComponent，从而进行装饰
class Invoice {public void printInvoice(){System.out.println("content");}}//class Decorator extends Invoice{protected Invoice ticket;public Decorator(Invoice t){ticket = t;}public void printInvoice(){if(ticket != null){ticket.printInvoice();}}}//class HeadDecorator extends Decorator{public HeadDecorator(Invoice t){super(t);}public void printInvoice(){System.out.println("Head");super.printInvoice();}}//class FootDecorator extends Decorator{public FootDecorator (Invoice t){super(t);}public void printInvoice(){super.printInvoice();System.out.println("Foot");}}class Test{public static void main(String [] args){Invoice ticket;ticket = new HeadDecorator(new FootDecorator(new Invoice()));ticket.printInvoice();System.out.println("---------------------");ticket = new HeadDecorator(new FootDecorator(null));ticket.printInvoice();System.out.println("---------------------");ticket = new FootDecorator(new HeadDecorator(null));ticket.printInvoice();System.out.println("---------------------");ticket = new FootDecorator(new FootDecorator(new HeadDecorator(new Invoice())));ticket.printInvoice();//Head//content//Foot//---------------------//Head//Foot//---------------------//Head//Foot//---------------------//Head//content//Foot}}
动态的给对象增加一些额外的职责
解题思路 读题，想设计模式特性，观察者模式，当模版Subject发生改变时，模版调用观察者Observer的更新方法，进行更新，这题关键就是set，当设置Subject参数时就要让Subject中的观察者列表都进行更新 Subjectobserver.update(temperature, humidity,cleanness)notifyObserver()measurementChanged()ObserverenvData.registerObserver(this) 解题思路 ligthOnCommand中的ligth对象调用方法Ligth中的方法，将这样的关灯的操作作为一个对象，保存在RemoteControl对象的数组中，使用命令时在数组中找到对应元素调用执行命令方法 class Commandlight.on()light.off()onCommand[slot]offCommand[slot]onCommand[slot].execute()offCommand[slot].execute() 解题思路 装饰器模式，这题就是观察输出特点，什么时候使用super，super往上一层着 ticket.printInvoice()super.printInvoice()super.printInvoice()new HeadDecorator(new FootDecorator(t))new FootDecorator(new HeadDecorator(null)) 解题思路 Director指挥Builder构造具体的对象，Builder返回getResult返回对象 void buildPartA()Product getResult()product.setPartAproduct.setPartB(5) builder.builderPartA();builder.builderPartB();Product p =builder.getResult();
