Xinhecuican's Blog

简单来说UML就是结构图，表示对象与类，类与类之间的联系。 UML主要包含以下框图： 用例图 从用户角度描述系统功能，简单来说就是用户让系统干什么（也可以说是系统的输入） 类框图 表示类与类之间的联系 状态转换图 这是针对有不同状态的类。类如开关的开和关就是状态的转换 时序图和协作图 时序图是在时间维度上描述用户的输入和类的使用。协作图则用箭头表示而不是通过时间轴表示 用例图用例图的要素有 用户 画成一个人型 用例 系统的某一个功能，大多数时候就是某一个函数，用椭圆表示 关系，用箭头表示 也可以用用例文档补充描述。 前置条件，什么时候才可以输入 主事件流，也就是这个用例干了什么事 其它事件流， 比如错误了该干什么事 后置条件 用例必须为真条件（个人理解是什么时候可以输出） 类框图类框图是表示类与类之间的关系（静态）。这个意思就是这个关系使不变的，做了一个就要去做另一个。 要素： 用一个方框表示类，方框的上面是类名，下面是函数名。用箭头表示方框之间关系。 时序图与协作图时序图有两个要素， 垂直上表示时间，水平上表示发送消息的过程。（用函数名和箭头表示） 协作图就用一个个箭头 ...

cpu运算可以简化成两大块，运算单元和寄存器。大致过程是先从寄存器中取值然后放入运算单元中运算完成之后又放入寄存器中。大致过程可分为六个部分 fetch(取指），读入指令 decode(译码),解码然后把寄存器中的值放到运算单元中 execute(执行), 进行计算 memory(访存),把结果放到内存中 write back（写回），把结果放到寄存器中 PC（更新PC） 这六个部分和把数据放到寄存器所用的总时间就是执行一条指令所需要的时间。cpu中有一个时钟，时钟以特定的周期进行高电压和低电压的变换。每一个周期内cpu执行一条指令，这个周期就是时钟周期。 但是这样速度不够快，因为cpu同一时间内只有一部分在工作，其他的都处于待机状态，所以可以用一种办法把其他部分利用起来。 之前我们之所以不能连续送入多条指令的原因是如果牵一条指令还未执行完成后一条指令便开始执行很可能导致电路出现问题（先这样理解吧）。如果我们在中间插入寄存器的话便不存在这个问题了。 例如：| 算术单元 | 寄存器 || 300ps | 20ps || 算术单元1 | 寄存器1 | 算术单元2 | 寄存器2 ...

顺序表就是将元素放入一个连续的内存空间里，它的优点是可以快速访问，缺点是插入和删除操作时间复杂度高 建立#include<iostream>#define datasize 100using namespace std;struct node{ int* p;//存储空间的基址 int length;//现在有的元素数量}; 初始化void init(node& a){ a.p=new int[datasize]; if(a.p==NULL) { cout<<"储存分配失败"<<endl; delete [] a.p; } a.length=0;} 初始化有两点要注意的地方，第一点是用了传引用，第二点是动态分配内存，这就表示如果使用完了要delete 查找int find(node& a,int x){ for(int i=0;i<a.length;i++)  ...

静态链表（链式前向星）是表示图的另外一种方法 前向星前向星也称为邻接数组 例 总共有这几条边(1, 2)(2, 4)(3, 4)(1, 3)(4, 3)(3, 2)(1, 4)现在将这些边按从小到大排序，变成(1, 2) --|(1, 3) --| => len[1] = 3(1, 4) --|(2, 4)(3, 2) => head[3] = 5(3, 4)(4, 3)然后再将数据填入三个数组中，分别是es[] 这个数组是用来记录每条边的终点的，而因为前面已经排好了序，起点很容易知道head[] 记录以i为起点的边在数组中的第一个位置len[] 记录以i为起点的边有多少 Array 1 2 3 4 5 6 7 es 2 3 4 4 2 4 3 head 1 4 5 7 len 3 1 2 1 head[2]=4表示2为起点的第一条边在es中的位置为4 通过这几个函数我们就能很清楚的知道点与边的关系 例如，我们想知道起点为1的所有边，我们只需要知道len[1]和head[1],这样我们知道起点为1的边有三个且从es[1]开始 但是前向星要排 ...

队列基础队列是一种线性结构，有队头（front）队尾（rear）两个指针，每次拉进来一个元素会让队尾加一，而每次删除一个元素会让队头加一，这是一种先进先出的结构。 队列特殊情况判断 空队列 front=rear 满队列 rear-front=N（N指的是开的数组的大小） POP 从队头删元素 push 拉元素到队尾struct duilie{ int a[N]; int front ,rear; void restart() { front=rear=0; } bool empty() { return (rear-front)==0?true:false; } bool full() { return rear-front==N-1?true:false; } int top() { return a[front]; } bool push(int k ...

之前写搜狗在线测试题目的时候，曾经想遍历一个set遍历。当时是这样写的。 set::iterator b = a.begin()+1 后来发现程序报错。究其原因是，set迭代器不支持加减数操作。查看了一下维基百科，下面是有关说明。 1.所有迭代器都应该实现自增算符：iter++,++iter 2.Bidirectional迭代器：是在前向迭代器的基础上，多了单步向后遍历的能力。也就是—iter,iter—。 3.Random Access迭代器：在双向迭代器基础上，具有直接访问各数据元素的能力。随机迭代器增加了“迭代器算术运算”： iter+=i 迭代器递增i位 iter-=i 迭代器递减i位 iter+i 加i位后的迭代器 iter-i 减i位后的迭代器 iter[i] 加i位后的迭代器的解引用 iter<iter1 如果迭代器iter的位置在iter1前，返回true，否则返回false iter<=iter1 如果iter的位置在iter1的前面或同一位置时返回true，否则返回false iter>iter1 如果迭代器iter的位置在iter1后，返回tru ...

用户空间用户空间是用户可以使用的空间，与之对应的是内核空间，这是系统所使用的空间。用户空间的大小有2的48次方，远远超出了内存的大小。 用户空间主要分为四个区域： 栈，栈位于用户空间的最高处，从高处向低处生长。linux系统中栈空间大小是8MB 堆， 用于存放一些动态分配的数据 数据， 用来存放全局变量，静态变量，字符串常量 代码， 存放指令和共享库 在Linux中，对于大小小于某一阈值的数据，在堆中分配时是从低地址向高地址生长。反之，从高地址向低地址生长 缓冲区溢出常见原因： 申请了一个数组但是访问时越界。 我们可以把数组叫做缓冲区，超出边界就是缓冲区溢出。 常见表现，对于输入的字符串没有进行长度检查直接赋值。如果缓冲区分配在栈中，就有可能造成栈中数据的破坏。如果造成了返回地址的破坏，可能直接导致程序的崩溃。这种错误叫做 segmentation fault 这里便可以被黑客利用，先故意把返回地址破坏了并且让返回地址到他自己写的程序上，这样retq时就可以调用自己写的程序。这种方法叫做注入。一般注入的数据有三部分，第一部分是恶意的指令。第二部分是占位数据，这部分数据没什么含义，只 ...

结构体的构成首先位于结构体中的元素在计算机也是对应存储的。而结构体的名字其实就可以看成是第一个变量的首地址。 例如：struct node{ int val; char c; int a[2];}在内存中是这样的| val | c | a[0] | a[1]p p+4 p+5 p+9 而变量在内存中的位置于定义时的位置是对应的 字节对齐首先说明什么事字节对齐。它指的是变量在内存中的首地址是变量的长度的整数倍。 例如定义一个int型变量，那么这个变量首地址尽量要是4的整数倍。也就是地址最后两位一定为零，如果是long型，地址最后三位一定为零 为什么要字节对齐？ 字节对齐可以加快访问数据的效率。原因是64位处理器数据总线是64位的，一次传过来8个字节的数据，所以如果我们是按8的整倍数进行存放，那么一定可以一次性取完，但是如果不是8的整倍数，例如int型首地址是6，那么就不可以一次性取完，要两次来取。而如果我们放在4这个位置，那么一定可以一次性取完。 此外例如首地址是2，这样也可以一次性取完，但是这样会造成空间浪费，因为现在不能再存int型了 ...

普通的二叉树中空节点数量很多，例如一个有2n条分支的二叉树，其中节点数只有n-1个，空节点有n+1个，因此就要想办法把这些没用到的节点利用起来。 可以用原来的空节点去存放指针，指向其他节点，这中指针叫做线索。 记ptr指向二叉链表中的一个结点，以下是建立线索的规则： （1）如果ptr->lchild为空，则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱； （2）如果ptr->rchild为空，则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继； 显然，在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要一个区分标志的。因此，我们在每个结点再增设两个标志域ltag和rtag，注意ltag和rtag只是区分0或1数字的布尔型变量，其占用内存空间要小于像lchild和rchild的指针变量。结点结构如下所示。 ltag = 0 表示指向左孩子，= 1 表示指向前驱 /* 二叉树的二叉线索存储结构定义*/typedef enum{Link, Thread}PointerTag; //Lin ...

lowbit函数lowbit函数指的是将元素与元素的补码按位与，即a&-a，这个值返回的是从右数第一个1开始的值 例如 6&-6， 6二进制位为110，所以6的lowbit函数值为10，即十进制下的二 ll lowbit(ll num) { return num&-num; } 树状数组首先我们可以把一整个数组分为若干小部分，然后让这几个小部分叠加就可以得到数组总的和。例如，我想求a[91],我可以先求c[88],发现c[88]管理2个数，再找c[86]，这样一直进行下去就可以了。 c又是什么呢？例如c[6]，它的lowbit函数为2，因此它管理两位数，所以c[6]=a[5]+a[6] 奇数位的c[i]只有他自己，而偶数位c[i]为2的k次方 单点修改void add(int x, int k) { while (x <= n) { //不能越界 c[x] = c[x] + k; x = x + lowbit(x); }} 这个函数是把a[x]加上k，小于x的c不用修改 ...