上图参考文章
RIP 最大的跳数为15
为主机配置地址:DHCP
ICMP报文传输方式:放在IP数据报的数据字段中传送
CIDR技术的作用：是网络归并技术，把小的网络汇聚成大的超网，进而缓解了地址资源不足的问题
IP首部字段，与分片和重组有关的是：片偏移，标志，标识
普通IP首部长为20个字节，最长60字节
- 16位总长度（Total Length）： 标识IP数据报包的总长度，以字节为单位。利用首部长度字段和总长度字段，就可以知道IP数据报中数据内容的起始位置和长度。由于该字段长16bit，所以IP数据包最长可达2^16 -1 = 65535字节，当数据包被分片时，该字段的值也随着变化。
- 16位标识（Identification）： 用于标识IP数据报的唯一码，如果因为数据链路层帧数据段长度限制（也就是MTU，支持的最大传输单元为1500字节），一个过长的IP数据包需要被拆散进行分片发送，拆分出的每个分片的IP数据包标识都是一致的，当分片要进行重组的时候就是依据了这个标识。
- 3位标志（Flag）： 目前只有两种，即只有后2位有意义；最低位为MF（More Fragment），为1代表后面还有分片的数据包，MF=0代表当前数据包已是最后的数据包。第二位为DF（Don’t Fragment），DF=1代表不能分片，此时若这个包长度大于路由器的长度限制，则直接丢弃了，DF=0代表可以分片。
- 13位片偏移（Fragment Offset）： 代表某个分片在原始IP数据包中的相对位置。通过这个偏移量和16位标识将多个分片数据包进行还原成原IP数据包。
- 8位协议（Protocol）： 代表上层的传输协议类型，一般常见的1代表ICMP，6代表TCP，17代表UDP。
参考文章
- 单播
- 多播
- 广播
- 主机之间的一对多的通信
- 所有的主机都可以接收到广播消息(不管你是否需要)
- 广播禁止穿过路由器（只能做局域网通信）
- 只有UDP可以广播
- 广播地址 有效网络号+全是1的主机号
- 192.168.50.123 -----》 192.168.50.255
- 255.255.255.255 给所有的网段中的所有主机发送广播，也是只能做局域网通信
- 需要相同端口
转发分组过程中源mac和目的mac会变，考虑NAT涉及私有地址转换，源地址和目的地址改变。
spooling 设备与输入输出井之间数据传输是由系统实现的
spooling技术实现了将独占设备改造成共享设备的技术
一个管道可以实现双向的数据传输，同一个时刻最多有一个方向的传输，不能两个方向同时进行。
管道单独构成一种文件系统，并且只存在于内存中。类似于半双工信道的进程通信机制。
4个fork 之后有 2 4 = 16 2^4=16 24=16个进程，派生出 16 − 1 = 15 16-1=15 16−1=15个进程。
实时系统为了满足用户实时交互以及对重要时间的迅速反应，所以采取抢占式的优先数高者优先。
基于关键字之间比较的算法，无论用什么方法都至少需要进行log_2n!次比较
基于比较方法的n个数据的内部排序，最坏情况下时间复杂度能达到的最好下界是： O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)
堆排序辅助空间 O ( 1 ) O(1) O(1)，快速排序 O ( l o g n ) O(log_n) O(logn)，归并为 O ( n ) O(n) O(n)
时间复杂度题目本质就是代码执行次数
时间局部性：一条【指令】执行之后可能会被再次执行。
空间局部性：内存相邻的【数据】可能会被再次执行，所以存在cache中
链表
typedef int ElemType;
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;
头插法
带头节点
LinkList HeadInsert(LinkList& L,int n){LNode *s;int x=1;L = (LinkList)malloc(sizeof(LNode));//创建头结点L->next = NULL;//初始化为空链表while(x!=n){s = (LNode*)malloc(sizeof(LNode));//创建新结点s->data = x;s->next = L->next;//核心代码；L->next = s;//核心代码；x++;}return L;
}不带头节点
LinkList HeadInster(LinkList &L,int n){LNode *s;int x=1;L= (LinkList)malloc(sizeof(LNode));L->data=x++;L->next=NULL;while(x!=n){s=(LNode*) malloc(sizeof(LNode));s->data=x;s->next=L;L=s;x++;}return L;
}上面图片和代码参考
仔仔木
尾插法
带头节点的尾插法
LinkList TailInster(LinkList&L,int n){int x = 1;L = (LinkList)malloc(sizeof(LNode));LNode *s,*r = L;while(x!=n){s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;x++;}
}
逆置法
带头结点实现尾插法
LinkList TailInserter(LinkList &L,int n){int x=1;L=(LinkList)malloc(sizeof(LNode));LNode *s,*r=L;while(x!=n){s=(LNode*)malloc(sizeof(LNode));s->data=x;r->next=s;r=s;x++;}r->next=NULL;return L;
}
不带头结点实现尾插法
LinkList TailInserter(LinkList &L,int n){int x=1;L=(LinkList)malloc(sizeof(LNode));L->data=x++;LNode *s,*r=L;while(x!=n){s=(LNode*)malloc(sizeof(LNode));s->data=x;r->next=s;r=s;x++;}r->next=NULL;return L;
}
归并法
typedef struct node{
Elemtype data;
struct node* next;
}Lnode;Lnode* merge1(Linklist& LA, Linklist& LB) {Lnode* LC = (Lnode*)malloc(sizeof(Lnode));LC->next = NULL;Lnode *pa = LA->next, *pb = LB->next, *pc = LC;while (pa && pb) {if (pa->data < pb->data) {pc->next = pa;pa = pa->next;} else {pc->next = pb;pb = pb->next;}pc = pc->next;}if (pa)pc->next = pa;if (pb)pc->next = pb;return LC;
}//******************************************************
Lnode* merge2(Linklist& LA, Linklist& LB) {// merge two sorted Singly linked lists// LA, LB and the return one ( LC ) all have a head node// all the linklist are sorted not in the same way:// LA and LB are the same, but LC just the other way// we assume that LA and LB are sorted in an increasing order// KEY: insert in the frontLnode* LC = (Lnode*)malloc(sizeof(Lnode));LC->next = NULL;Lnode *pa = LA->next, *pb = LB->next, *temp = NULL;while (pa && pb) {if (pa->data < pb->data) {temp = pa->next;pa->next = LC->next;LC->next = pa;pa = temp;} else {temp = pb->next;pb->next = LC->next;LC->next = pb;pb = temp;}}// only one of the following "while" will be excutedwhile (pa) {temp = pa->next;pa->next = LC->next;LC->next = pa;pa = temp;}while (pb) {temp = pb->next;pb->next = LC->next;LC->next = pb;pb = temp;}return LC;
}参考代码
链接
双指针法
参考内容
链接
链表——双指针和双链表
- 两个指针从不同位置出发：一个从始端开始，另一个从末端开始(对撞指针)；相隔k个位置进行遍历
- 两个指针以不同速度移动：一个指针快一些，另一个指针慢一些。一个走一步，一个走两步
- 滑动窗口：有左右端点和长度，根据题目调整左右端点的位置进行滑动，也是一种特殊的双指针。
扁平化多级双向链表
题目
多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。
示例 1：
输入：head =[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
扁平化后的链表如下图：
给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。
- 遇到child就递归, 把next和child都传递过去, 因为指针会遍历到后面, 正好可以拼接next和child
- 递归返回之后要清掉child, 并且处理好prev指针
// 优化前
const flatten = (head, next) => {let curr = headwhile (curr && (curr.next || curr.child)) {if (curr.child) {curr.next = flatten(curr.child, curr.next)curr.child = nullcurr.next.prev = curr}curr = curr.next}if (next) {next.prev = currcurr.next = next}return head
}滑动窗口
例题
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。