Posted on | In

只谈一下单链表, 链表实在是太重要, 是前面两篇说算法博客的基础, 了解了其应用和衍生, 再去了解其本身就有动力了

存储结构

typedef struct Node
{
	DataType data;
	struct Node *next;
}Node, *Node_Ptr;
  • 链表中第一个结点的存储位置叫做头指针
  • 头指针和头结点不同，头结点即第一个结点，头指针是指向第一个结点的指针。链表中可以没有头结点，但不能没有头指针。
  • 如果链表有头结点，那么头指针就是指向头结点数据域的指针。
  • 单链表也可以没有头结点

头结点的优点:

  • 头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。
  • 有了头结点后，对在第一个元素结点前插入结点和删除第一个结点，其操作与对其它结点的操作统一了。

有头结点和无头结点的建立链表方法头插法

include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Link {
    int  elem;
    struct Link *next;
}link;
//无头结点链表的头插法实现函数
link * creatLink(int * arc, int length) {
    int i;
    //最初状态下，头指针 H 没有任何结点，所以，插入第一个元素，就相当于是创建结点 H
    link * H =(link*)malloc(sizeof(link));
    H->elem = arc[0];
    H->next = NULL;
    //如果采用头插法插入超过 1 个元素，则可添加到第一个结点 H 之前
    for (i = 1; i<length; i++) {
        link * a = (link*)malloc(sizeof(link));
        a->elem = arc[i];
        //插入元素时，首先将插入位置后的链表链接到新结点上
        a->next = H;
        //然后再链接头指针 H
        H = a;
    }
    return H;
}
//有头结点链表的头插法实现函数
link * HcreatLink(int * arc, int length) {
    int i;
    //创建头结点 H，其链表的头指针也是 H
    link * H = (link*)malloc(sizeof(link));
    H->elem = 0;
    H->next = NULL;
    //采用头插法创建链表
    for (i = 0; i<length; i++) {
        link * a = (link*)malloc(sizeof(link));
        a->elem = arc[i];
        //首先将插入位置之后的链表链接到新结点 a 上
        a->next = H->next;
        //将新结点 a 插入到头结点之后的位置
        H->next = a;
    }
    return H;
}
//链表的输出函数
void display(link *p) {
    while (p) {
        printf("%d ", p->elem);
        p = p->next;
    }
    printf("\n");
}
int main() {
    int a[3] = { 1,2,3 };
    //采用头插法创建无头结点链表
    link * H = creatLink(a, 3);
    display(H);
    //采用头插法创建有头结点链表
    link * head = HcreatLink(a, 3);
    display(head);
    //使用完毕后，释放即可
    free(H);
    free(head);
    return 0;
}

运行结果：

3 2 1
0 3 2 1

提示：没有 0 的为无头结点的头插法输出结果，有 0 的为有头结点的头插法的输出结果

. . .

Posted on | In

前言

使用SVN在管理代码的时候免不了进行代码的合并和还原，特别是当前版本的修改发现有重大问题的时候，还原是避免不了的，那么究竟应该怎样操作呢？

内容

使用SVN查看文件或目录的日志的时候，右键单击日志记录会弹出下面这个界面，今天我们来着重了解一下被红圈标记的三个选项——“Update item to this version”，“Revert to this version”，“Revert changes from this version”，这三个选项对于刚接触SVN的人确实不太好区分，一开始我也搞不懂，直到亲自试验一下才搞清楚这三个选项的用法。

在讲解这三个选项的作用之前，我们还是先来假定一个使用情景，假设我们的项目文件一共有8个版本，它版本号分别是1，2，3，4，5，6，7，8。

Update item to this version

这个选项的作用是将文件版本更新到对应所选的版本（当然内容也修改到了相应的版本）。如果我们是在版本4这里点击“Update item to this version”，表示5~8版本所作的修改全部作废，这个文件的历史回退到了版本4那个时代，但是需要注意的是，此时文件的版本是4，并不是最新的。我们知道SVN工具中如果文件不是最新版本就无法上传，所以说这个功能只是用来暂时还原一下版本，来查询某个问题的，不能将还原后的文件上传。这个特别是当你服务器启动不了了, 把版本退回一个可以启动版本的情况

Revert to this version

这个选项的作用是将文件的内容更新到对应的版本，版本号没有发生变化。如果我们是在版本4这里点击“Revert to this version”，表示5~8版本所作的修改全部被还原，此时svn里会有5-8被还原的文件改动可以提交, 此时文件和版本4的文件一模一样，但需要注意的是这项操作相当于我们把版本4这个文件拷贝了一份赋值给了当前目录下的文件，此时的文件版本还是8，并且是可以提交的，提交以后文件的版本变成了9，增加了一个新的版本，虽然这个版本和版本4的内容是一样的。

Revert changes from this version

这个选项的作用是将对应版本的修改还原，文件的版本号不发生变化，相当于在当前本版本上剔除某些版本所作的改变。如果我们是在版本4这里点击“Revert changes from this version”，表示版本4所作的修改被抹杀了，只剩下除版本4以外的7个修改了，但是此时文件是可以上传的，并且会生成新的版本9，只是版本9只包括除版本4以外的7次修改。这个选项是可以选择多个版本的，如果我们选择4,5,6,7这四个版本点击“Revert changes from this revision”，那么这几次修改都会被抹杀。如果我们选择5,6,7,8这四个版本点击“Revert changes from this revision”，表示取消这几个版本的修改，实际上和在版本4这里点击“Revert to this version”的作用是一样的。

Posted on | In

考察cpp的静态绑定



struct MMPA{
	int value() const { return this->v_; }
	int tvalue() const { return 1; }
public:
	int v_;
};

int main(int argc, char* argv[]){
	{
		const MMPA* p = nullptr;
// 		std::cout << p->v_ << std::endl;
		std::cout << p->tvalue() << std::endl;
		std::cout << p->value() << std::endl;
		getchar(); return 0;
	}
}

会打印什么?

答案以及分析

答案: 打印1之后崩溃

真正的原因是：

因为对于非虚成员函数，Ｃ++这门语言是静态绑定的。这也是Ｃ++语言和其它语言Java, Python的一个显著区别。以此下面的语句为例：somenull->foo();这语句的意图是：调用对象somenull的foo成员函数。如果这句话在Java或Python等动态绑定的语言之中，编译器生成的代码大概是：找到somenull的foo成员函数，调用它。

（注意，这里的找到是程序运行的时候才找的，这也是所谓动态绑定的含义：运行时才绑定这个函数名与其对应的实际代码。有些地方也称这种机制为迟绑定，晚绑定。）但是对于C++。为了保证程序的运行时效率，Ｃ++的设计者认为凡是编译时能确定的事情，就不要拖到运行时再查找了。

所以C++的编译器看到这句话会这么干：

  1. 查找somenull的类型，发现它有一个非虚的成员函数叫foo。（编译器干的）
  2. 找到了，在这里生成一个函数调用，直接调B::foo(somenull)。

所以到了运行时，由于foo()函数里面并没有任何需要解引用somenull指针的代码，所以真实情况下也不会引发segment fault。这里对成员函数的解析，和查找其对应的代码的工作都是在编译阶段完成而非运行时完成的，这就是所谓的静态绑定，也叫早绑定。正确理解C++的静态绑定可以理解一些特殊情况下C++的行为。

求最大公约数

求 a 和 b 的最大公约数
辗转相除法

int measure(int a, int b)
{
	int product = a * b;
	if (a == 0 || b == 0)
	{
		return -1;
	}
	if (a < b)
	{
		int temp = a;
		a = b;
		b = temp;
	}
	while (int mod = a % b)
	{
		a = b;
		b = mod;
	}
	//return b; // 最大公约数
	return product / b; // 记住这个公式： a*b=最小公倍数*最大公约数
}

棋盘/格子问题

在如下7*5的棋盘中，请计算从A移动到B一共有多少走法？要求每次只能向上或向右移动一格，并且不能经过P。(答案为492)

给定一个M*N的格子或棋盘，从左下角走到右上角的走法总数（每次只能向右或向上移动一个方格边长的距离）

运用动态规划来解答 :
我们可以把棋盘的左下角看做二维坐标的原点(0,0)，把棋盘的右上角看做二维坐标(M,N)(坐标系的单位长度为小方格的变长)
用f(i,j)表示移动到坐标f(i,j)的走法总数，其中0=<i,j<=n，设f(m,n)代表从坐标（0,0）到坐标（m,n）的移动方法，则
f(m,n)=f(m-1,n)+f(m,n-1).
于是状态f(i,j)的状态转移方程为： 

f(i,j)=f(i-1,j)+f(i,j-1)   if i,j>0
f(i,j)=f(i,j-1)            if i=0
f(i,j)=f(i-1,j)            if j=0

初始情况就为：f(0,0)=0, f(0,1)=1, f(1,0)=1，这个问题可以在时间O(n^2)，空间O(n^2)内求解，非递归解.

所以答案为 492 = 

SumWaysOfMoveOnChessBoard(7, 5) - SumWaysOfMoveOnChessBoard(3, 3) * SumWaysOfMoveOnChessBoard(7 - 3, 5 - 3)

递归解

int SumWaysOfMoveOnChessBoard_Recursion(int m, int n) 
{
    if (m == 0 && n == 0)
        return 0;
    if (m==0 || n==0)
        return 1;
    return SumWaysOfMoveOnChessBoard_Recursion(m, n - 1) + SumWaysOfMoveOnChessBoard_Recursion(m - 1, n);
}

非递归解

int SumWaysOfMoveOnChessBoard_NonRecursion_RawArray(int m, int n)
{
	if (m == 0 || n == 0)
		return 1;
	if (m == 0 && n == 0)
		return 0;

	int xSize = m + 1;
	int ySize = n + 1;

	int** arr = new int*[xSize];
	for (int i = 0; i < xSize; ++i)
		arr[i] = new int[ySize];

	arr[0][0] = 0;
	for (int i = 0; i < xSize; ++i) arr[i][0] = 1;
	for (int i = 0; i < ySize; ++i) arr[0][i] = 1;
	for (int i = 1; i < xSize; ++i)
		for (int j = 1; j < ySize; ++j)
			arr[i][j] = arr[i - 1][j] + arr[i][j - 1];

	for (int i = 0; i < xSize; ++i)
		delete[] arr[i];
	delete[] arr;

	return arr[m][n];
}

int SumWaysOfMoveOnChessBoard_NonRecursion_STL(int m, int n)
{
	if (m == 0 && n == 0)
		return 0;

	int xSize = m + 1;
	int ySize = n + 1;

	std::vector< vector<int> > ChessBoardArray(xSize, vector<int>(ySize));;
	ChessBoardArray[0][0] = 0;
	for (int i = 0; i < xSize; ++i) ChessBoardArray[i][0] = 1;
	for (int j = 0; j < ySize; ++j) ChessBoardArray[0][j] = 1;
	for (int i = 1; i < xSize; ++i)
		for (int j = 1; j < ySize; ++j)
			ChessBoardArray[i][j] = ChessBoardArray[i][j - 1] + ChessBoardArray[i - 1][j];

	return ChessBoardArray[m][n];
}

大数加法/乘法

大数加法思路 :
模拟小学列竖式

        9  8
+       2  1
-------------
    (1)(1)(9)

大数乘法思路 :

模拟乘法累加 - 改进
简单来说，方法二就是先不算任何的进位，也就是说，将每一位相乘，相加的结果保存到同一个位置，到最后才计算进位。

例如：计算98×21,步骤如下

        9  8
×       2  1
-------------
       (9)(8)   <---- 第1趟: 98×1的每一位结果 
   (18)(16)     <---- 第2趟: 98×2的每一位结果 
-------------
   (18)(25)(8)  <---- 这里就是相对位的和，还没有累加进位

这里唯一要注意的便是进位问题，我们可以先不考虑进位，当所有位对应相加，产生结果之后，再考虑。
从右向左依次累加，如果该位的数字大于10，那么我们用取余运算，在该位上只保留取余后的个位数，而将十位数进位（通过模运算得到）累加到高位便可，循环直到累加完毕。

void BigIntAddition(char* bigIntA, char* bigIntB)
{
	if (!bigIntA || !bigIntB)
		return;

	size_t strlenA = strlen(bigIntA);
	size_t strlenB = strlen(bigIntB);
	size_t biggerStrlen = strlenA > strlenB ? strlenA : strlenB;

	int* reversedA = new int[biggerStrlen];
	int* reversedB = new int[biggerStrlen];
	// 先将例子中的 1234 和 98765 逆序存储, 不够的补零, 方便计算
	for (size_t i = 0; i < biggerStrlen; ++i)
	{
		//cout << int(strlenA - 1 - i) << endl;
		reversedA[i] = (int(strlenA - 1 - i) >= 0) ? (bigIntA[strlenA - 1 - i] - '0') : 0;
		reversedB[i] = (int(strlenB - 1 - i) >= 0) ? (bigIntB[strlenB - 1 - i] - '0') : 0;
	}

	for (size_t i = 0; i < biggerStrlen; ++i)
		cout << reversedA[i];
	cout << endl; // --> 43210

	for (size_t i = 0; i < biggerStrlen; ++i)
		cout << reversedB[i];
	cout << endl; // --> 98765

	int* bigIntSum = new int[biggerStrlen + 1];
	int x = 0; // 进位
						 // 模拟小学的列竖式加法, 满10进1
	for (size_t i = 0; i < biggerStrlen; ++i)
	{
		bigIntSum[i] = reversedA[i] + reversedB[i] + x;
		x = bigIntSum[i] / 10;
		bigIntSum[i] %= 10;
	}
	size_t printLen = biggerStrlen;
	// 查看最后一个进位是否 > 0, 大于零则最高位为1
	if (x > 0)
	{
		bigIntSum[biggerStrlen] = x;
		printLen = biggerStrlen + 1;
	}
	for (size_t i = 0; i < printLen; ++i)
		cout << bigIntSum[printLen - 1 - i]; // --> 58023
	cout << endl;

	delete[] bigIntSum;
}

void BigIntMultiplication(char* bigIntA, char* bigIntB)
{
	if (!bigIntA || !bigIntB)
		return;

	int strlenA = static_cast<int>(strlen(bigIntA));
	int strlenB = static_cast<int>(strlen(bigIntB));
	cout << strlenA << ", " << strlenB << endl;
	int biggerStrlen = strlenA > strlenB ? strlenA : strlenB;

	int* reversedA = new int[biggerStrlen];
	int* reversedB = new int[biggerStrlen];
	// 先将例子中的 1234 和 98765 逆序存储, 不够的补零, 方便计算
	for (int i = 0; i < biggerStrlen; ++i)
	{
		reversedA[i] = (int(strlenA - 1 - i) >= 0) ? (bigIntA[strlenA - 1 - i] - '0') : 0;
		reversedB[i] = (int(strlenB - 1 - i) >= 0) ? (bigIntB[strlenB - 1 - i] - '0') : 0;
	}

	for (int i = 0; i < biggerStrlen; ++i)
		cout << reversedA[i];
	cout << endl; // --> 43210

	for (int i = 0; i < biggerStrlen; ++i)
		cout << reversedB[i];
	cout << endl; // --> 98765

	// 分配一个空间，用来存储运算的结果，num1长的数 * num2长的数，
	// 结果不会超过num1+num2长
	int* bigIntProduct = new int[strlenA + strlenB];
	// 比如防止下面执行 bigIntSum[i + j] += reversedA[i] * reversedB[j]; 这句的时候
	// i+j = 0 时 出错, 因为 bigIntSum[0] 为一个未初始化的值
	for (int i = 0; i < strlenA + strlenB; ++i)
		bigIntProduct[i] = 0;
	int carry = 0; // 进位

	// 先不考虑进位问题，根据竖式的乘法运算，
	// num1的第i位与num2的第j位相乘，结果应该存放在结果的第i+j位上
	for (int i = 0; i < strlenA; ++i)
		for (int j = 0; j < strlenB; ++j)
			bigIntProduct[i + j] += reversedA[i] * reversedB[j];

	for (int i = 0; i < strlenA + strlenB; ++i)
		cout << bigIntProduct[i] << ", "; // --> 3659707060341650
	cout << endl;

	//单独处理进位
	for (int i = 0; i < strlenA + strlenB - 1; ++i)
	{
		bigIntProduct[i] += carry;
		carry = bigIntProduct[i] / 10;
		bigIntProduct[i] %= 10;
	}

	for (int i = 0; i < strlenA + strlenB; ++i)
		cout << bigIntProduct[i] << ", "; // --> 626770070
	cout << endl;

	int printLen = strlenA + strlenB - 1;
	// 查看最后一个进位是否 > 0, 大于零则最高位为1
	if (carry > 0)
	{
		bigIntProduct[strlenA + strlenB - 1] = carry;
		printLen = strlenA + strlenB;
	}
	for (int i = 0; i < printLen; ++i)
		cout << bigIntProduct[printLen - 1 - i]; // --> 70077626
	cout << endl;
	delete[] bigIntProduct;
}

int main()
{
	char *bigIntA = "1234";
	char *bigIntB = "56789";
	BigIntAddition(bigIntA, bigIntB);
	BigIntMultiplication(bigIntA, bigIntB);
	return 0;
}

最长公共子串

问题：有两个字符串str和str2，求出两个字符串中最长公共子串长度。

比如：str=acbcbcef，str2=abcbced，则str和str2的最长公共子串为bcbce，最长公共子串长度为5。

算法思路：

1、把两个字符串分别以行和列组成一个二维矩阵。
2、比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。
3、通过查找出值为1的最长对角线就能找到最长公共子串。

针对于上面的两个字符串我们可以得到的二维矩阵如下：

从上图可以看到，str和str2共有5个公共子串，但最长的公共子串长度为5。

为了进一步优化算法的效率，我们可以再计算某个二维矩阵的值的时候顺便计算出来当前最长的公共子串的长度，
即某个二维矩阵元素的值由 item[i][j]=1 演变为 item[i][j]=1 +item[i-1][j-1] ，这样就避免了后续查找对角线长度的操作了。修改后的二维矩阵如下：

故状态转移方程

X[i] == Y[j]，dp[i][j] = dp[i-1][j-1] + 1
X[i] != Y[j]，dp[i][j] = 0

int LongestCommonSubstring(char* strA, char* strB)
{
	if (!strA || !strB)
		return -1;

	int maxLen = 0;

	int strlenA = static_cast<int>(strlen(strA));
	int strlenB = static_cast<int>(strlen(strB));

	int biggerStrlen = strlenA > strlenB ? (strlenA + 1) : (strlenB + 1);
	char * lcs = new char[biggerStrlen];
	int lcsMaxIndex = 0;

	int** temp = new int*[strlenA];
	for (int i = 0; i < strlenA; ++i)
		temp[i] = new int[strlenB];

	for (int i = 0; i < strlenA; ++i)
	{
		for (int j = 0; j < strlenB; ++j)
		{
			if (strA[i] == strB[j])
			{
				if (i > 0 && j > 0)
					temp[i][j] = temp[i - 1][j - 1] + 1;
				else
					temp[i][j] = 1;
			}
			else
			{
				temp[i][j] = 0;
			}
			if (temp[i][j] > maxLen)
			{
				maxLen = temp[i][j];
				lcsMaxIndex = i;
			}
		}
	}

	for (int i = 0;i < maxLen; ++i)
		*(lcs + maxLen - i - 1) = strA[lcsMaxIndex--];
	*(lcs+maxLen) = '\0';
	cout << lcs << endl;

	for (int i = 0; i < strlenA; ++i)
		delete[] temp[i];
	delete[] temp;

	delete[] lcs;

	return maxLen;
}

int main()
{
	cout << "maxLen = " <<
		LongestCommonSubstring("wwwadfabcdeasdf", "wwweoruqpeorqabcdezcvnz") << endl;
	return 0;
}

Posted on | In

队列和双端队列的比较

队列(queue)是一种是相对于栈的一种数据结构，它是先进先出(First In First Out)。
它只可以在尾部添加元素。

双端队列(deque double ended queue（双端队列）)是一种相对于队列的一种数据结构。它可以在尾部和头部插入、移除和获取。

三者成员函数的比较

通过他们各自的成员函数我们能一目了然的看出区别

栈的成员函数

  • stack<Type> s : 定义一个stack的变量
  • s.push(x) : 入栈，如例
  • s.pop() : 出栈，如例 . 注意，出栈操作只是删除栈顶元素，并不返回该元素。
  • s.top() : 访问栈顶，如例
  • s.empty() : 判断栈空，如例，当栈空时，返回true。
  • s.size() : 访问栈中的元素个数，如例

队列的成员函数

  • queue<Type> M : 定义一个queue的变量
  • M.empty() : 查看是否为空范例 是的话返回1，不是返回0;
  • M.push() : 从已有元素后面增加元素
  • M.size() : 输出现有元素的个数
  • M.front() : 显示第一个元素
  • M.back() : 显示最后一个元素
  • M.pop() : 清除第一个元素

双端队列的成员函数

  • deque<Type> c : 定义一个deque的变量
  • c.pop_back() : 删除最后一个数据。
  • c.pop_front() : 删除头部数据。
  • c.push_back(elem) : 在尾部加入一个数据。
  • c.push_front(elem) : 在头部插入一个数据。
  • c.clear() : 移除容器中所有数据。
  • c.front() : 传回地一个数据。
  • c.back() : 传回最后一个数据，不检查这个数据是否存在。
  • c.size() : 返回容器中实际数据的个数。
  • c.empty() : 判断容器是否为空。

Posted on | In

有了二叉树的基础, 我们继续学习二叉搜索树.

二叉搜索树的定义

二叉查找树(Binary Search Tree, 简称”BST”), 又名”二叉搜索树”或”二叉排序树”:
它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

. . .

Posted on | In

二叉树的二叉链式存储方案的代码表示：

typedef struct BinTreeNode
{
	BinTreeNode( char Data ) : data_( Data ), left_( nullptr ), right_( nullptr ) {}
	char data_;
	struct BinTreeNode *left_, *right_;
}btn, *btnp;

二叉树的遍历

. . .

Posted on | In

接着上一篇， 上一篇主要说了各种排序算法， 但对几个常用的数据结构还未提及，所以这一篇主要讲二叉树, 二叉树已经包括很多链表的知识了。所有代码都是测试过的, 可以直接撸.

二叉树

这里不举太多数字方面的东西， 我们直接看图， 直观感性的认识满二叉树和完全二叉树：

有一点性质需要牢记：具有n个结点的完全二叉树的最大高度为log2n+1

二叉树的二叉链式存储

二叉树的二叉链式存储方案的代码表示：

typedef struct BinaryTreeNode
{
	void *data;
	BinaryTreeNode *LeftNode;
	BinaryTreeNode *RightNode;
}BTN, *BTNP;

. . .

Posted on | In

面向对象的四大特征

  • 封装：
    封装是把过程和数据包围起来，对数据的访问只能通过已定义的界面，面向对象计算始于这个基本概念，即现实世界可以被描绘成一系列完全自治，封装的对象，这些对象通过一个受保护的接口访问其他对象

  • 继承：
    继承是一种联结类的层次模型，并且允许和鼓励类的重用，它提供了一种明确表达共性的方法，对象的一个新类可以从现在的类中派生，这个过程成为继承，新类继承了原始类的特性，新类成为原始类的派生类，而原始类称为新类的基类，派生类可以从他的基类那里继承方法和实例变量，并且类可以修改或增加新的方法使之更加适合特殊的需求

  • 抽象：
    抽象就是忽略一个主题中与当前目标无关的那些方面，以便充分的注意与当前目标有关的方面，抽象包括两个方面，一个是过程抽象，二是数据抽象

  • 多态性：
    多态性是指允许不同类的对象对同一消息作出响应，多态性包括参数化多态性和包含多态性，多态性语言具有灵活，抽象，行为共享，代码共享的优势，很好的解决了应用程序函数同名的问题

面向对象的五大原则

记忆口诀 : 替开依(“凯隐”, 一个英雄联盟英雄名字)接单

  • 单一职责原则（Single-Resposibility Principle）
    其核心思想为：一个类，最好只做一件事，只有一个引起它的变化。单一职责原则可以看做是低耦合、高内聚在面向对象原则上的引申，将职责定义为引起变化的原因，以提高内聚性来减少引起变化的原因。职责过多，可能引起它变化的原因就越多，这将导致职责依赖，相互之间就产生影响，从而大大损伤其内聚性和耦合度。通常意义下的单一职责，就是指只有一种单一功能，不要为类实现过多的功能点，以保证实体只有一个引起它变化的原因。
    专注，是一个人优良的品质；同样的，单一也是一个类的优良设计。交杂不清的职责将使得代码看起来特别别扭牵一发而动全身，有失美感和必然导致丑陋的系统错误风险。

  • 开放封闭原则（Open-Closed principle）
    其核心思想是：软件实体应该是可扩展的，而不可修改的。也就是，对扩展开放，对修改封闭的。开放封闭原则主要体现在两个方面1、对扩展开放，意味着有新的需求或变化时，可以对现有代码进行扩展，以适应新的情况。2、对修改封闭，意味着类一旦设计完成，就可以独立完成其工作，而不要对其进行任何尝试的修改。
    实现开开放封闭原则的核心思想就是对抽象编程，而不对具体编程，因为抽象相对稳定。让类依赖于固定的抽象，所以修改就是封闭的；而通过面向对象的继承和多态机制，又可以实现对抽象类的继承，通过覆写其方法来改变固有行为，实现新的拓展方法，所以就是开放的。
    “需求总是变化”没有不变的软件，所以就需要用封闭开放原则来封闭变化满足需求，同时还能保持软件内部的封装体系稳定，不被需求的变化影响。

  • 替换原则（Liskov-Substituion Principle）
    其核心思想是：子类必须能够替换其基类。这一思想体现为对继承机制的约束规范，只有子类能够替换基类时，才能保证系统在运行期内识别子类，这是保证继承复用的基础。在父类和子类的具体行为中，必须严格把握继承层次中的关系和特征，将基类替换为子类，程序的行为不会发生任何变化。同时，这一约束反过来则是不成立的，子类可以替换基类，但是基类不一定能替换子类。
    Liskov替换原则，主要着眼于对抽象和多态建立在继承的基础上，因此只有遵循了Liskov替换原则，才能保证继承复用是可靠地。实现的方法是面向接口编程：将公共部分抽象为基类接口或抽象类，通过Extract Abstract Class，在子类中通过覆写父类的方法实现新的方式支持同样的职责。
    Liskov替换原则是关于继承机制的设计原则，违反了Liskov替换原则就必然导致违反开放封闭原则。
    Liskov替换原则能够保证系统具有良好的拓展性，同时实现基于多态的抽象机制，能够减少代码冗余，避免运行期的类型判别。

  • 依赖倒置原则（Dependecy-Inversion Principle）
    其核心思想是：依赖于抽象。具体而言就是高层模块不依赖于底层模块，二者都同依赖于抽象；抽象不依赖于具体，具体依赖于抽象。
    我们知道，依赖一定会存在于类与类、模块与模块之间。当两个模块之间存在紧密的耦合关系时，最好的方法就是分离接口和实现：在依赖之间定义一个抽象的接口使得高层模块调用接口，而底层模块实现接口的定义，以此来有效控制耦合关系，达到依赖于抽象的设计目标。
    抽象的稳定性决定了系统的稳定性，因为抽象是不变的，依赖于抽象是面向对象设计的精髓，也是依赖倒置原则的核心。
    依赖于抽象是一个通用的原则，而某些时候依赖于细节则是在所难免的，必须权衡在抽象和具体之间的取舍，方法不是一层不变的。依赖于抽象，就是对接口编程，不要对实现编程。

  • 接口隔离原则（Interface-Segregation Principle）
    其核心思想是：使用多个小的专门的接口，而不要使用一个大的总接口。
    具体而言，接口隔离原则体现在：接口应该是内聚的，应该避免“胖”接口。一个类对另外一个类的依赖应该建立在最小的接口上，不要强迫依赖不用的方法，这是一种接口污染。
    接口有效地将细节和抽象隔离，体现了对抽象编程的一切好处，接口隔离强调接口的单一性。而胖接口存在明显的弊端，会导致实现的类型必须完全实现接口的所有方法、属性等；而某些时候，实现类型并非需要所有的接口定义，在设计上这是“浪费”，而且在实施上这会带来潜在的问题，对胖接口的修改将导致一连串的客户端程序需要修改，有时候这是一种灾难。在这种情况下，将胖接口分解为多个特点的定制化方法，使得客户端仅仅依赖于它们的实际调用的方法，从而解除了客户端不会依赖于它们不用的方法。
    分离的手段主要有以下两种：1、委托分离，通过增加一个新的类型来委托客户的请求，隔离客户和接口的直接依赖，但是会增加系统的开销。2、多重继承分离，通过接口多继承来实现客户的需求，这种方式是较好的。