未完待续==
一、数据结构与算法
1. 排序
排序
- 插入排序
N-1趟排序组成。从P=1到P=N-1趟，插入排序保证从位置0到位置P上的元素为已排序状态。
反着比较，若比当前元素大依次向后移位，否则插入。
void InsertSort(int *a, int n)
{
int temp;
for(int i=1; i<n; i++)
{
temp = a[i]; //即将新插入的值
for (int j=i; j>0 && a[j-1]>temp; j--)
a[j] = a[j-1]; //元素依次向后移动
a[j] = temp; //插入空挡
}
}
- 选择排序
每次选择最小的元素，交换到相应位置。
void SelectSort(int *a, int n)
{
for(int i=0; i<n; i++)
{
int min = i; //先赋值每趟的开始位置为最小
for (int j=i+1; j<n; j++)
{
if(a[j]<a[min])
min = j; //时刻更新最小位置
}
if(i!=min)
swap(a[i], a[min]);
}
}
- 冒泡排序
void BubbleSort(int *a, int n)
{
for (int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
if(a[i]>a[j])
swap(a[i], a[j]);
}
}
}
- 归并排序
分治思想。
合并两个已排序的表。两个输入数组A和B，一个输出数组C，三个计数器Aptr， Bptr， Cptr， A[Aptr]和B[Bptr]中较小者放入C的下一个位置。当其中一个表没有剩余时，将其余元素全部拷贝到C中。 - 堆排序
- 快速排序
//partition函数
int partition(int *a, int left, int right)
{
int temp = a[left]; //为方便起见，最左边元素为枢纽。其实是不科学的
while(left<right)
{
while(left<right && a[right]>temp)
-- right; //若右侧元素比枢纽元素值大，则继续向左查找
a[left] = a[right]; //一旦查找到比枢纽元素小的值，则交换到左边（枢纽）位置
while(left<right && a[left]<=temp)
++ left;
a[right] = a[left];
}
a[left] = temp; //将枢纽插入空位
return left； //返回枢纽位置
}
//quicksort函数
void QuickSort(int *a, int left, int right)
{
int pivot;
if(left>=right) return;
pivot = partition(a, left, right);
QuickSort(a, left, pivot-1);
QuickSort(a, pivot+1, right);
}
2. 二分查找
//不使用递归
int binarySearch(int arry[], int len, int value)
{
if(arry==NULL||len<=0)
return -1;
int start=0;
int end=len-1;
while(start<=end)
{
int mid=start+(end-start)/2;
if(arry[mid]==value)
return mid;
else if(value<arry[mid])
end=mid-1;
else
start=mid+1;
}
return -1;
}
//不要传参，传引用调用，减少垃圾。
int binarySearchRecursion(int arry[], int value, int start, int end)
{
if(start>end)
return -1;
int mid=start+(end-start)/2;
if(arry[mid]==value)
return mid;
else if(value<arry[mid])
return binarySearchRecursion(arry,value,start,mid-1);
else
return binarySearchRecursion(arry,value,mid+1,end);
}
二、操作系统
- 进程和线程的区别
- 一个进程至少有一个主线程。线程是进程内的一个执行单元，也是进程内的可调度实体。
- 进程是资源分配的基本单位，线程是CPU调度和分派的基本单位。
- 进程有自己独立的地址空间，线程共享进程的地址空间，没有单独的地址空间，线程可以有自己的寄存器和堆栈。
- 线程更加灵活，进程更加稳定。一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，需要用多线程。
- 进程的状态
进程的三种状态及转换
运行状态，阻塞状态，就绪状态。
进程状态转换图
创建和退出不是进程的状态。阻塞和就绪的区别：阻塞是等待除CPU以外的资源，而就绪等待的是CPU资源。
- 进程三种状态间的转换
一个进程在运行期间，不断地从一种状态转换到另一种状态，它可以多次处于就绪状态和执行状态，也可以多次处于阻塞状态。
(1) 就绪→执行处于就绪状态的进程，当进程调度程序为之分配了处理机后，该进程便由就绪状态转变成执行状态。
(2) 执行→就绪处于执行状态的进程在其执行过程中，因分配给它的一个时间片已用完而不得不让出处理机，于是进程从执行状态转变成就绪状态。
(3) 执行→阻塞正在执行的进程因等待某种事件发生而无法继续执行时，便从执行状态变成阻塞状态。
(4) 阻塞→就绪处于阻塞状态的进程，若其等待的事件已经发生，于是进程由阻塞状态转变为就绪状态。
- 进程通信的几种方式
linux系统下：
- 管道（pipe）：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
- 命名管道（named pipe）：命名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
- 信号量（semophore）：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
- 消息队列（message queue）：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
- 信号（signal）：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
- 共享内存（shared memory）：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。
- 套接字（socket）：套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。
线程同步几种方式。(一定要会写生产者、消费者问题，完全消化理解)
线程的实现方式。 (也就是用户线程与内核线程的区别)
- 内核线程：由操作系统内核创建和撤销。内核维护进程及线程的上下文信息以及线程切换。一个内核线程由于I/O操作而阻塞，不会影响其它线程的运行。Windows NT和2000/XP支持内核线程
- 用户线程：由应用进程利用线程库创建和管理，不以来于操作系统核心。不需要用户态/核心态切换，速度快。操作系统内核不知道多线程的存在，因此一个线程阻塞将使得整个进程（包括它的所有线程）阻塞。由于这里的处理器时间片分配是以进程为基本单位，所以每个线程执行的时间相对减少。
- 死锁
是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。
- 产生原因：
资源竞争引起进程死锁。
进程推进顺序不当。 - 导致死锁四个必要条件：
简洁版：
互斥条件 : 任一时刻只允许一个进程使用资源。
非剥夺条件: 进程已经占用的资源, 不会被强制剥夺。
占用并请求条件: 进程占有部分资源 , 申请更多的资源 , 且不会释放已经占有的资源。
循环等待 : 请求资源的进程形成了循环。
复杂版：
1、互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
2、请求和保持：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
3、不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
4、环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。 - 处理死锁的四个方式：
1、撤消陷于死锁的全部进程；
2、逐个撤消陷于死锁的进程，直到死锁不存在；
3、从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失；
4、从另外一些进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态。 - 预防死锁的方法、避免死锁的方法：
采用资源静态分配，破坏“部分分配”条件；
允许进程剥夺使用其他进程占用的资源，破坏“不可剥夺”条件；
采用资源有序分配法，破坏“环路”条件；
互斥条件无法破坏。
c++基础知识
C++面试题——基础概念篇
C++面试出现频率最高的30道题目（一）
C++面试出现频率最高的30道题目（二）
C++面试出现频率最高的30道题目（三）
- static
- 隐藏。未加static前缀的全局变量和函数都具有全局可见性；使用static在不同文件中定义同名函数和同名变量，不必担心命名冲突。
- 保持变量内容持久。全局变量和static变量存储在静态存储区，存储在静态存储区的变量会在程序刚开始运行就完成初始化，也是唯一一次初始化。
- 默认初始化为0。（全局变量也是）。
- const
修饰的内容不可改变，包括const数据成员，const参数，const返回值，const成员函数。被修饰的东西会被强制保护，可以预防意外变动，提高程序的健壮性。 - 宏#define和const关键字的区别
- const是有数据类型的常量，而宏常量没有，编译器可以对前者进行静态类型安全检查，而后者只是字符串替换，没有类型安全检查，在字符替换时可能会发生意想不到的错误。
- 有些编译器可以对const常量进行调试，不能进行宏调试。
- const无法代替宏作为卫哨来防止文件的重复包含。
- C++中引用和指针的区别
引用是对象的别名， 操作引用就是操作这个对象， 必须在创建的同时有效得初始化（引用一个有效的对象， 不可为NULL）， 初始化完毕就再也不可改变， 引用具有指针的效率， 又具有变量使用的方便性和直观性， 在语言层面上引用和对象的用法一样， 在二进制层面上引用一般都是通过指针来实现的， 只是编译器帮我们完成了转换。 之所以使用引用是为了用适当的工具做恰如其分的事， 体现了最小特权原则。 - C与C++的内存分配方式
- 静态存储区域分配。内存在程序编译时就已经分配好，这块内存在程序的整个运行期间都存在，如全局变量，static变量。
- 在栈上创建。在执行函数时，函数内部局部变量的存储单元可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。
- 从堆上分配（动态内存分配）。程序在运行的时候用malloc或new申请任意多少的内存，程序员负责在何时用free或delete释放内存。动态内存的生存期自己决定，使用非常灵活。
- 面向对象程序设计的优点
开发时间短， 效率高， 可靠性高。面向对象编程的编码具有高可重用性，可以在应用程序中大量采用成熟的类库（如STL），从而虽短了开发时间，软件易于维护和升级。
数据库
https://www.zhihu.com/question/19552975/answer/123523074
数据库基础知识复习
