计算机网络

1、计算机网络：计算机网络主要是由一些通用的、可编程的硬件互连而成的，而这些硬件并非专门用来实现某一特定目的（例如，传送数据或视频信号）。这些可编程的硬件能够用来传送多种不同类型的数据，并能支持广泛的和日益增长的应用。

2、网络分类：
广域网 WAN (Wide Area Network)：作用范围通常为几十到几千公里。
城域网 MAN (Metropolitan Area Network)：作用距离约为 5 ~ 50 公里。
局域网 LAN (Local Area Network) ：局限在较小的范围（如 1 公里左右）。
个人区域网 PAN (Personal Area Network) ：范围很小，大约在 10 米左右。

注意：若中央处理机之间的距离非常近（如仅1米的数量级甚至更小些），则一般就称之为多处理机系统，而不称它为计算机网络。

3、接入网：
接入网 AN (Access Network)，它又称为本地接入网或居民接入网。
接入网是一类比较特殊的计算机网络，用于将用户接入互联网。
接入网本身既不属于互联网的核心部分，也不属于互联网的边缘部分。
接入网是从某个用户端系统到互联网中的第一个路由器（也称为边缘路由器）之间的一种网络。

4、计算机网络体系结构
Image text

5、各层工作过程
Image text
1)OSI 参考模型把对等层次之间传送的数据单位称为该层的协议数据单元 PDU (Protocol Data Unit)。
2)协议是“水平的”，即协议是控制对等实体之间通信的规则。
3）服务是“垂直的”，即服务是由下层向上层通过层间接口提供的。

6、TCP/IP体系结构
Image text

物理层中继系统：转发器 (repeater)。
数据链路层中继系统：网桥 或 桥接器 (bridge)。
网络层中继系统：路由器 (router)。
网桥和路由器的混合物：桥路器 (brouter)。
网络层以上的中继系统：网关 (gateway)。

算法-递归

递归重点：

1、寻找相似性（可能需要主动构造）
2、参数设置（参数分配不相同，否则死循环）
3、出口设置
（每次调用的层次不同，注意返回的次序）

例子：取球问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package recursion;

public class GetBall {
//在n个球中，任意取m个（不放回），求有多少种取法
	static int count=0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int k=getBall(10,3);
		System.out.println(k);
	}
	
	public static int getBall(int n,int m) {
		//假设有一个球被标记，则规模变成
		//1、被标记的球已取到，则还剩n-1,还需取 m-1,即f(n-1,m-1) 
		//2、被标记球一定不取，则需从剩下的 n-1 中取 m,即f(n-1,m)

		if(n<m) return 0;
		if(n==m) return 1;
		if(m==0) return 1;
		
		return getBall(n-1,m-1)+getBall(n-1,m);
	}
}

用栈实现十进制转换为X进制

参考：https://www.cnblogs.com/lixiaolun/p/4645247.html

1、链栈的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package linkStack;

public class LinkStack {

	Node base;
	Node top;
	
	public void init() {
		base=new Node();
		top=new Node();
		
		base.data=null;
		base.next=null;
		
		top.data=null;
		top.next=base;
	}
	
	//入栈
	public void push(Object e) {
		Node node=new Node();
		node.data=e;
		
		//第一次入栈
		if(top.next==base) {
			node.next=base;
			top.next=node;
		}else {
			node.next=top.next;
			top.next=node;
		}
	}
	
	//出栈
	public void pop() {
		if(top.next==base)
        {
            System.out.println("栈中没有元素！");
        }else
        {
            System.out.println(top.next.data);
            top.next=top.next.next;
        }
	}
	
	public boolean isEmpty() {
		if(top.next==base) {
			return true;
		}
		
		return false;
	}
	
	public void printNode() {
		Node temp=top;
		while(temp.next!=base) {
			temp=temp.next;
			System.out.println(temp.data);
		}
	}
	
	class Node{
		Object data;
		Node next;
	}
}

2、进制转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package linkStack;

public class DToX {
//十进制转X进制
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		LinkStack stack=new LinkStack();
		stack.init();
		
		int d=16;//十进制数100
		int x=2;//转为二进制
		
		while(d!=0) {
			stack.push(d%x);
			d=d/x;
		}
		
		 while(!stack.isEmpty())
	        {
	            stack.pop();
	        }
	}

}

查找

一、线性表的查找

1、顺序查找 O(n)[^code]

1
2
3
4
5
6
int[] a;
int Search(int key){
	a[0]=key;//设置岗哨
	for(int i=a.length;a[i]!=key;i--){
	return i;
}

2、折半查找 O(log2(N))(下标从1开始)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int[] a;
int Search_Bin(int key){
	int low=0;
	int high=a.length
	int mid=(low+high)/2

	while(low<=high){//loe<=high
		if(key==mid)
			return mid;
		else if(key<mid){
			high=mid-1;
		}
		else
			low=mid+1;	
	}

	return 0;
}

3、分块查找

分块查找是折半查找和顺序查找的一种改进方法，分块查找由于只要求索引表是有序的，
对块内节点没有排序要求，因此特别适合于节点动态变化的情况。

二、树表的查找

1、二叉排序树

1）二叉排序树的查找 O(log2(N))

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Node root;
int Search(Tree T,int key){
	if(root==null || root.data==key){
		return 0;
	}

	if(key<root.data){
		Search(T.lchild,key);
		return;
	}else{
		Search(T.rchild,key);
		return;
	}
}

2）二叉排序树的插入 O(log2(N))

二叉排序树的插入 以查找为基础：查找失败则插入，查找成功则返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Node root;
int Insert(Tree T,int e){
	if(root==null){
		root=new Node();
		root.data=e;
		root.lchild=root.rchild=null;
	}

	if(e<root.data){
		Insert(T.lchild,e);
		return;
	}else{
		Insert(T.rchild,e);
		return;
	}
}

3)二叉排序树的创建 O(nlog2(N))

从空树开始，新建一个结点，查找后，再插入到合适位置

1
2
3
4
5
6
7
8
9
10
Tree T;
void CreateBST(){
	T=null;
	cin>>e;
	while(e!="*")//"*"结束符
	{
		Insert(T,e);
		cin>e;
	}
}

4)二叉排序树的删除 O(nlog2(N))

删除的过程也是查找的过程

2、平衡二叉树

三、哈希表的查找

时间复杂度为直接计算

树的相关知识点

一.

1.结点n=0，称为空树

二. 二叉树的性质（树的深度从1开始计数）

1、 第i层至多有2^（i-1）个结点

2、 深度为k的二叉树至多有（2^k）-1个结点

3、对任意二叉树的n个结点：叶子结点n0，度为1的结点n1，度为2的结点n2，分支总数B

* n=n0+n1+n2
  n=B+1
  B=n1+2n2
* n=n1+2n2+1
  • 综合上式有：n0=n2+1

4、满二叉树：深度为k且含有结点数为（2^k）-1的二叉树

5、完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中 编号从1至n一一对应时，称为完全二叉树

特点：
    1）叶子结点只可能在层次最大的两层出现
    2）对任一结点，若其右分支下的子孙最大层次为l，则其左分支下的子孙的最大层次必为l或l+1

####6、具有n个结点的完全二叉树的深度为log2（N）+1，log2（N）取下界

数据库总结

1、 where、having之间的区别和用法
聚合函数是比较where、having 的关键。

where、聚合函数、having 在from后面的执行顺序：

1
where>聚合函数(sum,min,max,avg,count)>having

注意事项 ：
1、where 后不能跟聚合函数，因为where执行顺序大于聚合函数。
2、where 子句的作用是在对查询结果进行分组前，将不符合where条件的行去掉，即在分组之前过滤数据，条件中不能包含聚组函数，
使用where条件显示特定的行。

3、having 子句的作用是筛选满足条件的组，即在分组之后过滤数据，条件中经常包含聚组函数，使用having 条件显示特定的组，也可以使用多个分组标准进行分组。

操作系统概述

1、计算机系统的组成
Image text

操作系统的地位：
紧贴系统硬件之上，所有其他软件之下
（是其他软件的共同环境）
Image text

2、操作系统的作用:
(1)OS是计算机硬件、软件资源的管理者
管理的对象：CPU、存储器、外部设备、信息（数
据和软件）；
– 管理的内容：
1、资源的当前状态（数量和使用情况）
2、资源的分配、回收和访问操作
3、相应管理策略（包括用户权限）

(2)OS是用户使用系统硬件、软件的接口。
系统命令（命令行、菜单式、命令脚本式）；
– 系统调用（形式上类似于过程调用，在应用编程
中使用API）；
– 图形用户接口GUI

（3）OS是扩展机(extended machine)/虚拟机(virtual machine)。
在裸机上添加：设备管理、文件管理、存储管理（包括内存和外存）、处理机管理（针对CPU）；
– 另外，为合理组织工作流程：作业管理、进程管理

– 通道：用于控制I/O设备与内存间的数据传输。启动后可
独立于CPU运行，实现CPU与I/O的并行。
• 通道有专用的I/O处理器，可与CPU并行工作
• 可实现 I/O联机处理
– 中断是指CPU在收到外部中断信号后，停止原来工作，转
去处理该中断事件，完毕后回到原来断点继续工作。
• 中断处理过程：中断请求，中断响应，中断点（暂停当前任务并
保存现场），中断处理例程，中断返回（恢复中断点的现场并继续原
有任务

3、通道和中断技术
通道：用于控制I/O设备与内存间的数据传输。启动后可
独立于CPU运行，实现CPU与I/O的并行。

中断是指CPU在收到外部中断信号后，停止原来工作，转
去处理该中断事件，完毕后回到原来断点继续工作。
• 中断处理过程：中断请求，中断响应，中断点（暂停当前任务并
保存现场），中断处理例程，中断返回（恢复中断点的现场并继续原
有任务

3.1、手工操作
计算机的工作特点
• 用户独占全机：不出现资源被其他用户占用，资源利
用率低；
• CPU等待用户：计算前，手工装入纸带或卡片；计算完
成后，手工卸取纸带或卡片；CPU利用率低；

3.2、单道批处理系统
联机批处理：输入输出设备和主机直接相连，串行工作
脱机批处理：利用卫星机完成输入输出功能。主机与卫星机可
并行工作。
– 卫星机：完成面向用户的输入输出（纸带或卡
片），中间结果暂存在磁带或磁盘上。
– 优点：同一批内各作业的自动依次更替，改善了
主机CPU和I/O设备的使用效率，提高了吞吐量。
– 缺点：磁带或磁盘需要人工装卸，作业需要人工
分类，监督程序易遭到用户程序的破坏（由人工干预
才可恢复）

3.3 多道批处理系统
多道批处理的运行特征
• 多道：内存中同时存放几个作业；
• 宏观上并行运行：都处于运行状态，但都未运行完；
• 微观上串行运行：各作业交替使用CPU；
在当前运行的作业需作I/O处理时，CPU转而执行
另一个作业。
优点：
• 资源利用率高：CPU和内存利用率较高；
• 作业吞吐量大：单位时间内完成的工作总量大；
– 缺点：
• 用户交互性差：整个作业完成后或中间出错时，
才与用户交互，不利于调试和修改；
• 作业平均周转时间长：短作业的周转时间显著
增长；

3.4 分 时 系 统
许多个联机用户同时使用一台计算机系统进行计算的操作
系统称分时操作系统
系统把中央处理器的时间划分成时间片 ，按时间片轮流
把处理机分配给联机作业
– “分时”的含义分时是指多个用户分享使用同一台计算机。
多个程序分时共享硬件和软件资源
– 人机交互性好：在调试和运行程序时由用户自己
操作。
– 共享主机：多个用户同时使用。
– 用户独立性：对每个用户而言好象独占主机

3.5 实 时 系 统
– 要求：响应时间短，在规定的时间之内（s, ms,
us）；系统可靠性高

3.6 通用操作系统
目前的操作系统，通常具有分时、实时和批处理
功能，又称作通用操作系统。

4、操作系统的分类
4.1 批处理操作系统
批处理系统中作业处理及状态：
Image text

单道和多道批处理的比较
Image text

– 多道程序系统和多重处理系统(multi-processing
system)的区别：
• 前者指多个程序同时在内存中交替运行
• 后者指多个处理器

多道批处理系统上的技术
– 作业调度：作业的现场保存和恢复－－上下文切换
– 资源共享：资源的竞争和同步－－互斥(exclusion)
和同步(synchronization)机制
– 内存使用：提高内存使用效率（为当前由CPU执行
的程序提供足够的内存）－－覆盖(overlay)，交换
(swap)和虚拟存储(virtual memory)
– 内存保护：系统存储区和各应用程序存储区不可冲
突－－存储保护

4.2 分时操作系统
– 多路性：多个用户同时工作。
– 独立性：各用户独立操作，互不干扰。
– 交互性：系统能及时对用户的操作进行响应，显
著提高调试和修改程序的效率：缩短了周转时间。
（对批处理的改进）

4.3 实时操作系统
– 实时操作系统主要用于过程控制、事务处理等有
实时要求的领域，其主要特征是实时性和可靠性

5、 操作系统的特征
5.1 并 发 ( c o n c u r r e n c y )
– 多个事件在同一时间段内发生。操作系统是一个并
发系统，各进程间的并发，系统与应用间的并发。操作
系统要完成这些并发过程的管理。并行(parallel)是指
在同一时刻发生。
– 在多道程序处理时，宏观上并发，微观上交替执行
（在单处理器情况下）。
– 程序的静态实体是可执行文件，而动态实体是进程
（或称作任务），并发指的是进程。

5.2 共 享 (sharing)
多个进程共享有限的计算机系统资源。操作系统要
对系统资源进行合理分配和使用。资源在一个时间段内
交替被多个进程所用。
– 互斥共享（如视频设备）：资源分配后到释放前，
不能被其他进程所用

5.3 虚 拟 (virtual)
– 一个物理实体映射为若干个对应的逻辑实体－－分
时或分空间。虚拟是操作系统管理系统资源的重要手段，
可提高资源利用率

5.4 异步性 ( asynchronism )
– 也称不确定性，指进程的执行顺序和执行时间的不
确定性；
– 进程的运行速度不可预知：分时系统中，多个进程
并发执行，程序是以走走停停的方式运行的。系统中的
每个程序何时执行，执行顺序，完成时间都是不确定的。

6、操作系统的功能
6.1 处 理 机 管 理
– 完成处理机资源的分配调度等功能。处理机调度的
单位可为进程或线程。
– 进程控制：创建、撤销、状态转换
– 进程同步：对并发执行的进程进行协调
– 进程通信：负责完成进程间的信息交换
– 进程调度：按一定算法进行处理机分配

6.2 存 储 管 理
– 内存分配：按一定的策略分配内存并负责回收
– 内存保护：保证进程间互不干扰、相互保密
– 地址变换：进程逻辑地址到内存物理地址的映射；
– 内存扩充：为允许大型作业或多个作业运行，借助
虚拟技术获得更大逻辑内存的效果；

6.3 设备管理
– 设备分配：为了使设备与主机并行工作，一定的分
配原则对设备进行分配，常采用缓冲技术和虚拟技术
– 设备传输控制：实现物理的输入/输出操作
– 设备独立性：用户向系统申请的设备和实际操作的
设备无关

6.4 文 件 管 理
– 文件存储空间管理：存储空间的分配和回收。
– 目录管理：解决信息检索问题。
– 文件操作管理：实现文件的操作，负责完成数据的
读写
– 文件保护：提供文件保护功能，防止文件遭到破坏

各个排序算法总结

参考：https://blog.csdn.net/hellozhxy/article/details/79911867

1、术语说明

1、稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
2、不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
3、内排序：所有排序操作都在内存中完成；
4、外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
5、时间复杂度： 一个算法执行所耗费的时间。
6、空间复杂度：运行完一个程序所需内存的大小。

2、算法总结

1、时间复杂度与空间复杂度比较
Image

图片名词解释：
n: 数据规模
k: “桶”的个数
In-place: 占用常数内存，不占用额外内存
Out-place: 占用额外内存

3、算法分类

Image

Tip：比较和非比较的区别
1、常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。

2、在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O（n²)

3、在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。

4、比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。

5、计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr之前有多少个元素，则唯一确定了arr在排序后数组中的位置。

6、非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。

7、非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

插入排序

1、插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

2、时间复杂度

最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

3、动态演示

Image text

4、算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package sort;

public class InsertionSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] a= {99,45,67,12,84,59,32};
		insertionSort(a);
		printArr(a);
	}
	
	public static void insertionSort(int [] a) {
		int cur;//记录即将插入的当前值
		for(int i=0;i<a.length-1;i++) {//比较a.length-1趟
			int index=i;//记录有序数组的最后一位坐标
			cur=a[i+1];
			
			while(index>=0 && cur<a[index]) {//当前值小于有序数组中的值时
				a[index+1]=a[index];//记录后移
				index--;
			}
			
			//当前值不小于前一个值时，把当前值赋给index+1
			a[index+1]=cur;
		}
	}
	
	public static void printArr(int [] a) {
		for(int i=0;i<a.length;i++) {
			System.out.print(a[i]+" ");
		}
	}
}

排序

一、插入排序

1、直接插入排序

时间复杂度：O(n^2)

1
2
3
4
5
6
7
int[] a;
void insertSort(){
	for(int i=2;i<L.length;i++){
		
	}
}
}