计算机网络
交换技术
电路交换
报文交换
分组交换
WAN广域网
LAN局域网
PAN个域网
MAN城域网
网络指标
比特 KB=1024B 1M=1024KB
速率:b/s ,bps
1 K bps=1000 bps
带宽 :单位时间最高数据传输速率b/s
吞吐量:单位时间某个端口的数据量
时延
发送时延=数据块长度b/带宽(b/s),传播时延=信道长度m/电磁波传播速率(m/s),处理时延构成
时延带宽积
时延带宽积=传播时延*带宽 面积**长度
往返时间RTT
发送分组开始到确认分组结束
利用率:信道利用率和网络利用率
丢包率
栈的应用
栈在括号匹配中的应用只包含括号的表达式({【】})是否对称匹配
算法基本原理
从头开始扫描表达式
遇到左括号【,(,{ 入栈
遇到右括号则弹出括号进行匹配,不匹配则配对失败
重复操作,直到扫描完整个表达式
如果最后栈不空则匹配失败
栈在后缀表达式中的应用后缀表达式是指两个操作数A和B在前,运输符+ - * / 在后,例如AB+表示A+B
中缀表达式转后缀表达式基本思路
遍历中缀表达式
遇到操作数,加入后缀表达式
遇到运算符,如果栈中存在比其优先级大或相等的运算符则将运算符弹出,直到遇到(结束,该元素加入后缀表达式;如果栈中运算符优先级均小于当前运算符,则当前运算符入栈
遇到(则入栈,遇到)则弹出栈中元素加入后缀表达式,直到遇到(
linux内核链表
linux内核链表链表linux中的链表将数据域与指针域进行分离。
通过list_head怎么访问其他成员变量?
这就要依靠container_of宏了。指针域相对于结构体首地址的偏移量是固定的
指针域地址-相当偏移地址=结构体首地址。偏移量求解的办法offset宏
123#define container_of(ptr,type,member) \ const typeof((type *)0->member) *_ptr=(ptr); \ (type *)((char *)_ptr-offset(type,member))
offset是内置的函数,也可以用上面的方法实现
1#define offset(type,member) (unsigned long)(&(type)(0)->member)
使用0地址作为结构体的起始地址,成员的地址就是相对与0号地址的偏移地址
链表头静态创建链表头1234struct Node Head{ .data=data; .list=List_Head_In ...
无题
双向循环链表双向循环链表能够访问前驱和后继,快速定位到尾节点,并在在尾部进行插入和删除,也能够找到任意节点前驱和后继,方便添加和删除元素。
双向链表的存储结构1234typedef struct DulNode{ ElemType data; struct DulNode *next,*prior;}DulNode,*DulLinkList;
一个双向链表结点由三部分组成,分别是前驱指针,数据域,后驱指针。DulNode表示节点,*DulLinkList表示链表的头指针。
链表初始化12345678910/*初始化链表*/Status InitList(LinkList &L){ L=(LinkList)malloc(sizeof(LNode)); if(L==NULL) return ERROR; L->next==L; L->prior=L; L->data=0; return OK;}
初始化过程中,将前驱指向L自身,L的后继也指向自身,形成闭环。
头插法和尾插 ...
内联汇编
内联汇编的基本结构1234asm asm-qualifiers ( AssemblerTemplate : OutputOperands [ : InputOperands [ : Clobbers ] ])
AssemblerTemplate 汇编程序模板OutputOperands 输出操作数InputOperands 输入操作数Clobbers
示例代码
1234567int src = 1;int dst; asm ("mov %1, %0\n\t" "add $1, %0" : "=r" (dst) : "r" (src));printf("%d\n", dst);
此段代码复制 src 到 dst ,并将 1 添加到 dst 。
可以将多个汇编程序指令放在一个 asm 字符串中,由系统汇编代码中通常使用的字符分隔。在大多数地方都有效的组合是换行符, ...
djikstra最短路径
1234567891011121314151617181920212223242526272829303132333435void dijkstra(int graph[][6],int len,int start){ int isshort[len];/*记录是否找到最短路径*/ int dis[len]; int path[len];/*recode pre node*/ for(int i=0;i<len;i++){ dis[i]=graph[start][i]; if(graph[start][i]!=INF) path[i]=start; else path[i]=-1; isshort[i]=0; } isshort[start]=1; for(int i=0;i<len;i++){ int min=INF; int minindex=-1; for(int j=0;j<len;j++){ if(isshort[j]!=1&&dis[j]<min){ ...
函数栈帧
程序的虚拟地址空间
在了解函数的栈帧之前,我们先了解一下虚拟地址空间的概念。操作系统给每个c语言程序实例分配了一块虚拟地址空间,营造了一种每个程序都独占则内存的假象。这块内存地址的分布如下。
栈区栈是一种先进后出的数据结构。在C程序的地址空间中,%esp寄存器指向栈顶,%ebp寄存器指向栈底。栈由高地址向低地址延申,入栈时esp向低地址处移动,出栈时esp向高地址处移动
函数的调用依赖于栈。调用函数,栈增加。函数返回,栈缩小。
函数调用1
调用函数的过程本质上是修改PC(程序计数器)的值,PC指向了下一条执行指令的地址
在调用函数前
参数从右往左依次入栈,
call指令将返回地址入栈,用于指明当函数返回时下一条执行语句
参数传递在32位的系统中,参数的传递是靠栈来进行的。
在X86-64架构中函数的参数是存储在寄存器中的,分别存储在di,si,dx,cx,r8,r9寄存器中。如果函数的参数大于6,超过的部分需要使用栈来进行传递
局部变量12345678long caller() { long argl = 534; long arg2 = 1057 ...
Kruskal
实现思路
将图中的边按从小到大的顺序排列
遍历边所在的数组
如果边的两个顶点不存在于同一集合,则将两点所在的集合合并,两点连通
否则跳过
模拟过程
按边从小到大排序,构建辅助数组
算法实现克鲁斯卡尔算法需要一个辅助数组,数据元素结构如下
12345typedef struct Edge{ int head; int tail; int weight;}Edge;
Edges数组需要根据边的长度weight从小到大进行排序,排序的算法如下
123456789101112131415161718/*快速排序*/void Sort(struct Edge edges[],int l,int r){ if (l >= r) return; int i=l-1; int j=r+1; int mid=edges[(l+r)/2].weight; while(i<j){ while(edges[++i].weight<mid); while(edges[-- ...
并查集
并查集并查集的数据结构
1int S[MAXSIZE];
查询元素所在的集合
1234567int Find(int sets[],int x){ int index=x; while(sets[index]!=-1){ index=sets[index]; } return index;}
合并两个集合
1234void Union(int sets[],int root1,int root2){ if(root1==root2) return; sets[root2]=root1;}
并查集和优化Union优化123456789101112131415161718/*将两个根节点所在的集合合并集合*/void UnionSets(int sets[],int root1,int root2){ if(root1==root2) return; if(sets[root1]>=sets[root2]){ s ...