1 基本命令

查看：
show databases；
show tables；

创建：
create database basename charset utf8；

删除：
drop database basename；

建表语句:
create table stu(
snum int,
sname varchar(10)
)engine myisam charset utf8;

1 排序的基本概念

1.1 排序的定义

排序：重新排列表中元素，使表中元素满足按关键字递增或递减的过程
算法的稳定性：关键字相同的不同元素排序前后前后相对顺序不变，称该算法是稳定的
内部排序：排序期间元素全存放在内存的排序
外部排序：排序期间元素需要在内外存之间移动的排序

2 插入排序

2.1 直接插入排序

排序思想：序列分为有序部分和无序部分，每次排序将无序部分的一个元素加入有序部分进行排序，重复上述步骤直到全部排序完成。

1
2
3
4
5
6
7
8
9

void InsertSort(Elemtype A[],int n){
    int i,j;
    for(i=2;i<=n;i++){            //依次将A[2]到A[n]插入到已排序序列
        A[0]=A[i];              //A[0]为哨兵
        for(j=i-1;A[j].key>A[i].key&&;j--)   //若前驱元素大于A[i】，将其后移一位
            A[j+1]=A[j];
        A[j+1]==A[0];                 //插入A[i]
    }
}

算法时间复杂度：O(n²);
算法空间复杂度：O(1)；
稳定性：稳定

2.2 折半插入排序

算法思想：利用折半查找在有序序列中查找目标元素的插入位置，再一次性移动元素后插入目标元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void InsertSort(Elemtype A[],int n){
    it i,j,low,mid,high;
    for(i=2;i<=n;i++){              //依次将A[2]到A[n]插入到已排序序列
        A[0]=A[i];                  //A[0]存储待排序元素
        low=1;
        high=i-1;
        while(low<=high){           //查找插入位置
            mid=(low+high)/2;
            if(A[mid].key>A[0].key)
                high=mid-1;
            else low=mid+1;
        }
        for(j=i-1;j>-high+1;j--)    //移动元素
            A[j+1]=A[j];

        A[high+1]=A[0]              //插入元素
    }
    //为什么插入位置是A[high+1]
    //可以这样理解：【特例】当源序列有序时，元素插入位置为原来位置，即A[high+1]
}

2.3 希尔排序

算法思想：直接插入排序中，排序元素取的步长为1，即比较时是A[i]和A[i+1]进行比较；而希尔排序中取得步长为di(di取值：1= < di <=(n/2)),每一轮排序后将步长减小，直到di=1这一轮排序完成则全部排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void ShellSort(Elemtype A[],int n){
    int di=n/2;
    for(di;di>=1;di=di/2){              //每轮排序后步长减半
        int i;
        for(i=di+1;i<=n;i++){          //从A[i+di]开始进行直接插入排序
            A[0]=A[i];
            if(A[i]<A[i-di]){          //判断已排序的最后元素大于欲排序元素，再排序，否则不予排序
                int j;
                for(j=i-di;j>0;j--){    //后移
                    A[j+di]=A[j];
                }
                A[j+di]=A[0];          //插入
            }
        }
    }
}

最坏时间复杂度：O(n²);
稳定性：不稳定

3 交换排序

根据序列中两个元素关键字的比较结果决定是否交换两个元素的位置的排序称为交换排序

3.1 冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12

void BubbleSort(Elemtype A[],int n){
    for(int i=0;i<n-1;i++){             //从小到大排序
        bool flag=false;                //本轮排序是否交换的标志位
        for(int j=n-1;j>i;j--){         //从尾部开始检测是否交换
            if(A[j-1]>A[j])
                swap(A[j-1],A[j]);
                flag=true;
        }
        if(flag==false)             //若本轮未发生交换，说明排序已完成，直接返回
            return;
    }
}

时间复杂度：O(n²)
稳定性：由于A[i]=A[j]时不会发送交换，所以为稳定排序。

3.2 快速排序

算法思想：取待排序列中一元素pivot作为基准，经过一趟快速排序确定pivot的最终位置，并划分出大于等于pivot的部分和小于等于pivot的部分；再对每个子序列重复上述过程，直到每一部分只含一个或0个元素，则排序完成。
一趟快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13

int Partition(Elemtype A[],int low,int high){
    Elemtype pivot = A[low];
    while(low<hight){
        while(low<high&&A[high]>pivot)
            high--;
        A[low]=A[high];
        while(low<high&&A[low]<pivot)
            low++;
        A[high]=A[low];
    }
    A[low]=pivot;
    return low;
}

快排

1
2
3
4
5
6
7

void QuickSOrt(Elemtype A[],int low,int high){
    if(low<high){
        int partition=Partition(A,low,high);
        QuickSOrt(A,low,partition-1);
        QuickSOrt(A,partition+1,high);
    }
}

空间复杂度：快排算法为递归算法，需要借助递归工作栈；其空间复杂度为栈的深度，其平均值为O(log₂n)。
时间复杂度：O(n²)

4 选择排序

选择排序算法思想：每趟排序选择未排序元素中关键字最小的元素，将其加入到已排序序列的末尾。

4.1 简单选择排序

1
2
3
4
5
6
7
8
9

void SelectSort(Elemtype A[],int n){
    for(int i=0;i<n-1;i++){
        min=i;
        for(int j=i+1;j<=n-1;j++){
            if(min>A[j]) min=j;
        }
        if(A[min]!=A[i]) swap(A[min],A[i]); 
    }
}

时间复杂度：O(n²)
稳定性：交换元素期间会打乱原来含有相同关键字的元素的顺序，不稳定。

4.2 堆排序

堆排序是一种树形选择排序方式，序列L[1]到L[n]经过堆排序后的结构符合完全二叉树的顺序存储结构。
其严格定义为：n个关键字序列L[1…n]称为堆，当且仅当：
1.L[i]<=L[2i] && L[i]<=L[2i+1] (小顶堆) 或
2.L[i]>=L[2i] && L[i]>=L[2i+1] （大顶堆）。
堆排序算法思想：

1. 对待排序序列生成器层序遍历树。
2. 从结点⌊n/2⌋ 开始，若左右子结点的最大值大于根结点，将根结点与之交换，再对该根结点以下的子结点进行递归操作。
3. 对结点序号小于⌊n/2⌋的结点从大到小依次进行步骤1和2的操作，直到第一个结点也完成上述操作。
   建堆算法：

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

   void BuildMaxHeap(Elemtype A[],int len){ for(int i=len/2;i>0;i--) AdjustDown(A,i,len); } void AdjustDown(Elemtype A[],int k ,int len){ if(k<=len/2){ // A[0]=A[k];//将父结点存储在A[0]中，注意原序列序号是从1开始，0序号元素不存储元素信息，故可以对其进行再次利用 for(int i=2*k;i<=len;i*=2){ //i代表子结点下标 if(i<len&&A[i]<A[i+1]) //选出子结点中值比较大的的结点 i=i+1; if(A[k]>A[i]) break; //如果子结点值比父节点小，则说明该趟排序完成 else{ A[k]=A[i]; //用子结点代替父结点 k=i； //修改k值，继续向子结点进行操作 } } A[k]=A[0]; //父结点的最终存放位置 } }

堆排序算法：

1
2
3
4
5
6
7

void HeapSort(Elemtype A[],int len){
    BuildMaxHeap;       //建大顶堆
    for(int i=len;i>1;i--){     //从大到小进行len-1趟排序
        Swap(A[len,A[1]]);      //交换堆顶元素和堆顶元素
        AdjustDown(A,1,i-1)   //对剩余元素进行调整使其成堆
    }
}

堆排序算法性能：
空间复杂度：O(1)
时间复杂度：O(nlog₂n)
稳定性：不稳定

5 归并排序和基数排序

5.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

Elemtype *B=(Elemtype *)malloc(sizeof(Elemtype)*(n+1))
void Merge(Elemtype A[],int low,int mid,int high){
    //表A[low...mid]和A[mid+1...high]分别有序，将它们合并为一个表
    for(int i=low;i<=high;i++){         //将A复制给B
        B[i]=A[i];
    }
    int i,j;
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){ //将两分表中值小的复制到A中，下标后移
        if(B[i]<=B[j])
            A[k]=B[i++];
        else
            A[k]=B[j++];
    }
    while(i<=mid) A[k++]=B[i++];       //加入剩余元素
    while(j<=high) A[k++]=B[j++];
}

void MergeSort(Elemtype A[],int low,int high){
    if(low<high){
        int mid=(low+high)/2;
        MergeSort(A,low,mid);
        MergeSort(A,mid+1;high);
        Merge(A,low,mid,high);
    }
    //递归边界为low=high，此时将不进行操作
}

时间复杂度：O(nlog₂n)
稳定性：稳定

5.2 基数排序

　　基数排序是基于关键字各位的大小进行排序的，基数排序分为最高位（MASD）优先和排序和最低位优先(LSD)排序。
　　排序步骤（以LSD为例）：第一趟排序时只考虑最低位，第二趟排序时只考虑次低位，以此进行n轮排序直到首位也完成排序则基数排序完成。在每趟排序时不进行比较，而是将其放入到已知的容器中，之后再将元素直接按照所在容器的顺序首尾相连，得到一趟排序的结果。，
　　时间复杂度：每趟排序时有n个元素要进行入队列（队列数目为r）的操作，之后需要连接这r个队列，操作次数为(n+r);设元素共有d位，则需要进行d趟排序，故时间复杂度为O(d*(n+r))。
　　空间复杂度：需要r个队列，故为O(r)。

6 各种内部排序算法的比较

1 查找的基本概念

1. 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找
2. 查找表：用于查找的数据集合称为查找表
3. 静态查找表：如果一个查找表的操作不涉及修改或删除称为静态查找表
4. 动态查找表：需要动态删除或插入的查找表称为动态查找表
5. 关键字：数据元素中唯一标识该元素的数据项的值称为关键字
6. 平均查找长度：所有查找过程进行关键字比较次数的平均值

2 顺序查找和折半查找

2.1 顺序查找

1. 一般线性表的顺序查找
   思想：在线性表一头设置哨兵，从另外一头开始逐个检测关键字是否满足查找条件

   1 2 3 4 5 6 7 8 9

   typedef struct{ //查找表的数据结构 ElemType *elemm; int TableLen; }SSTable; int Search_Seq(SSTable ST,ElemType key){ ST.elem[0]=key; //哨兵 for(i=ST.TableLen;ST.elem[i]!=key;i--) ; //从后往前找，找不到直接跳过 return i; //若i为0表示查找失败 }

查找成功的平均查找长度：(n+1)/2;
查找不成功时的平均查找长度：n+1；

2.2 折半查找

折半查找又称为二分查找，仅适用于有序的顺序表。
算法思想：将key与表中间元素比较，若相对查找 成功；若不等，则依据大小关系往前半部分或后半部分查找；如此重复。

1
2
3
4
5
6
7
8
9
10
11
12
13

int Binary_Search(SeqList L,ElemType key){
    int low=0;high=L.TableLen-1;mid;
    while(low<=high){
        mid=(low+high)/2;
        if(L.elem[mid]==key)        //找到则返回
            return mid;
        else if(L.elem[mid]>key)    //往前找
            high=mid-1;
        else                        //往后找
            low=mid+1;
    }
    return -1;                      //找不到返回-1
}

时间复杂度：O(log₂n);

分块查找

分块查找基本思想：将查找表分成若干子块，块间有序而块内元素无序。建立索引表，索引表的内容是：各块的最大关键字和该块的第一个元素地址的映射关系。
查找步骤：先用顺序查找或折半查找确定块，再在块内查找。

3 B树和B+树

3.1 B树及其基本操作

B树又称为多路平衡查找树，m阶B树或为空树或满足以下特性：

• 树中每个结点至多有m-1个结点，m棵子树；
• 若根结点不是终端结点，则至少有两棵子树
• 根结点以外的非叶结点至少有⌈m/2⌉棵子树，⌈m/2⌉-1个关键字
• 所有非叶结点由：关键字个数、关键字和指向子树根结点的指针组成
• 所有叶结点出现在同一层且不带任何信息(即NULL)

1. B树的高度
   log_m(n+1)<=h<=log_⌈m/2⌉((n+1)/2)+1;
2. B 树的查找
   查找步骤：1.在B树中找结点；2.在结点中找关键字
3. B树的插入
   插入需要修改B树结构使符合B树定义(涉及结点的分裂)
4. B树的删除
   删除操作需要修改B树的结构使其符合B树定义(涉及结点的合并)

3.2 B+树基本概念

m阶B+树满足：

• 每个分支结点至多有m棵子树
• 非叶的根结点至少有两棵子树，其它分支结点至少有⌈m/2⌉棵子树
• 结点的关键字数目和子树数目相等
• 所有叶结点包含全部关键字和指向记录的指针
• 所有分支结点只包含它的各子结点中关键字的最大值和指向子结点的指针

4 散列表(Hash)

4.1 散列表的基本概念

散列函数：把查找表中的关键字映射到该关键字对应的地址的函数称为散列函数，记为Hash(key)=Addr。
冲突：散列函数中把两个或以上的关键字映射到同一地址。
散列表：存储关键字和存储地址的直接映射关系。

4.2 散列函数的构造方法

1. 直接定址法
   H(key)=a*key+b
   
2. 除留余数法
   H(key)=key%p
   
3. 数字分析法
4. 平法取中法
5. 折叠法

4.3 冲突处理方法

1. 开发定址法
   
   Hi=(H(key)+di)%m
   
   其中m为散列表表长，di为增量序列。
   di通常有四种取法：
   线性探测法 ：di=1,2,3…,m-1
   平法探测法 ： di=1²,-1²,2²,-2²,…,k²,-k²
   再散列法：di=Hash₂(key)
   伪随机序列法：di为伪随机序列
2. 拉链法
   将所有冲突的关键字存储在一个线性链表中

4.4 散列查找及性能分析

散列表的查找效率取决于：散列函数、冲突处理方法和填装因子。
填装因子：填装因子=(表中记录数)/(散列表长度)

1 图的基本概念

1.1 图的定义

图G由顶点集V和边集E组成，记为G=(V,E)，V非空。

1. 有向图
   若E是有向边(弧)的有限集合时，图G为有向图，从顶点v到顶点w的弧记为\
2. 无向图
   若E是 无向边的有限集合，则图G为无向图，v和w之间的边记为(u,w)。
3. 简单图
   简单图满足：不存在重复边；不存在顶点到自身的边。
4. 多重图
   与简单图相对。
5. 完全图
   任意两点之间都存在边的无向图称为无向完全图；任意两个顶点之间都存在两条方向相反的弧的有向图称为有向完全图。
6. 子图
   一个图的子图其边和顶点包含于原图中。
7. 连通、连通图和连通分量
   顶点v和w之间有路径存在，则称v和w是连通的；图中任意两个顶点均连通的图称为连通图；极大连通子图称为连通分量。
8. 强连通图和强连通分量
   有向图中，从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的；
   任意一对顶点都是强连通的图称为强连通图；
   图的极大强连通子图称为图的强连通分量。
9. 生成树和生成森林
   连通图的生成树是包含全部顶点的一个极小连通子图(边数最小)；
   非连通图的生成森林是连通分量的生成树的集合。
10. 顶点的度、入度和出度
    无向图中顶点的度是以该顶点为端点的边的数目；
    有向图中顶点的入度是以该顶点为弧尾的弧的数目；
    有向图中顶点的出度是以该顶点为弧头的弧的数目。
11. 边的权和网
    边上的数值称为边的权值；边上带权值的图称为网(带权图)。
12. 路径、路径长度和回路
    顶点u到w的路径是指从u到w所经过的顶点序列，路径上的边的数目称为路径长度，首尾顶点相同的路径称为回路。
13. 简单路径、简单回路
    顶点不重复的路径称为简单路径，顶点不重复的回路称为简单回路。
14. 距离
    从顶点u到顶点w的最短路径若存在，则该路径的长度称为从u到w的距离。
15. 有向树
    有一个顶点的入度为0，其余顶点入度均为1的有向图称为有向树。

二叉排序树

1. 二叉排序树的定义
   二叉排序树(BST)也称为二叉查找树。非空二叉排序树满足：
   • 若左子树非空，则左子树上所有结点关键字值均小于根结点的关键字值。
   • 若右子树非空，则右子树所有结点关键字值均大于根结点的关键字值。
   • 左右子树本身也是一颗二叉排序树。
     对二叉排序树进行中序遍历可以得到一个递增序列。
2. 二叉排序树的查找
   设欲查找值为K,将K与根结点的关键字值比较，若相对则查找成功，若其值大于K则在根结点的左子树中查找，若其值小于K则在根结点的右子树中查找。

   1 2 3 4 5 6 7 8

   BSTNode *BST_Serach(BiTree T,ElemType key){ while(T&&key!=T->data){ if(key>T->data) T=T->rchild; else T=T->lchild; } return T; }

1 树的基本概念

1.1树的定义

树是N(N>=0)个结点的有限集合，N=0时，称为空树。任意一棵非空树满足：

1. 有且仅有一个特定的称为根的结点。
2. 当N>1时，其余结点可分为m个互不相交的有限集合，其中每个集合本身又是一棵树，并且称为根结点的子树。

树具有以下特点：

1. 树的根结点没有前驱结点，除根以外的结点有且仅有一个前驱结点。
2. 树中结点可以有零个或多个后结点。

1.2基本术语

1. 结点关系：
   • 祖先结点
   • 子孙结点
   • 双亲结点
   • 孩子结点
   • 兄弟结点
2. 度：
   • 结点的度：一个结点的子结点个数
   • 树的度：Max{结点的度}
   • 分支结点：度大于0的结点
   • 叶子节点：度为0的结点
3. 结点属性：
   • 结点的深度：从根结点开始自顶向下逐层累加
   • 结点的高度：从叶子结点开始自底向上逐层累加
   • 树的高度：树中结点的最大层数
4. 路径：
   • 路径：路径由两个结点之间所经过的结点序列构成
   • 路径长度：路径所经过的边的个数
5. 森林：树的集合
   阅读全文 »

1 栈

1.1 栈的基本概念

1. 栈的定义
   栈(Stack)：只允许在一端进行插入和删除的线性表
   栈顶(Top)：允许进行插入和删除的一端
   栈底(Button):栈底不允许插入和删除
   空栈：不含任何元素的栈
2. 栈的基本操作
   InitStack(&S)
   StackEmpty(S)
   Push(&S,x)
   Pop(&S,&x)
   GetTop(S,&x)
   ClearStack(&S)
   阅读全文 »

1 线性表的定义和基本操作

1.1 线性表的定义

线性表是具有相同数据类型的n(n≧0)个数据元素的有限序列。在线性表中，除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。
线性表特点：

• 表中元素个数有限
• 表中元素具有逻辑顺序性
• 每个元素都是数据元素
• 元素的数据类型相同
• 表中元素具有抽象性

1.2 线性表的基本操作

InitList(&L)
Length(L)
LocateElem(L,e)
GetElem(L,i)
ListInsert(&L,i,e)
ListDelect(&L,i,&e)
PrintList(L)
Empty(L)
DestoryList(&L)

数据结构的基本概念

一 基本结构和概念

1. 数据
   数据是信息的载体，是描述客观事物属性的数、字符和所有能输入到计算机并被计算机程序识别和处理的符号的集合。
2. 数据元素
   数据元素是数据的基本单位，一个数据元素由若干个数据项组成，数据项是构成数据元素的最小单位。
3. 数据对象
   数据对象是具有相同性质的数据元素的聚合。。

4. 数据类型
   数据类型是一组值的集合和定义在此集合上一组操作的总称。

   • 原子类型：其值不可再分的数据类型
   • 结构类型：其值可以再分解为若干分量的数据类型
   • 抽象数据类型：抽象数据组织和与之相关的操作

5. 抽象数据类型(ADT)
   抽象数据类型是一个数学模型和定义在该模型上的一组操作。
   抽象数据组成：

    * 数据对象
    * 数据关系
    * 基本操作集
   

6. 数据结构
   结构是指数据之间的相互关系。
   数据结构是指相互之间存在特定关系的数据元素的集合。
   数据结构构成：

    * 逻辑结构
    * 存储结构
    * 数据的运算
   

2 数据结构的三要素

1. 数据的逻辑结构
   逻辑结构是指数据之间的逻辑关系。

   数据逻辑结构分类：

   • 线性结构：
     • 一般线性表
     • 受限线性表：
       • 栈和队列
       • 数组
     • 线性表推广：
       • 广义表
   • 非线性结构：
     • 集合
     • 树形结构
     • 图状结构

2. 数据的存储结构
   数据的存储结构是指数据结构在计算机中的表示(映像)，也称为物理结构。
   　　
   数据存储结构分类：

   • 顺序存储:逻辑上相邻的元素存储在物理位置也相邻的存储单元
   • 链接存储：借助指示元素地址的指针表示元素之间的关系，只能实现顺序存取
   • 索引存储：建立索引表，索引表中每一项称为索引项(存储关键字和物理地址的映射关系)
   • 散列存储：根据元素的关键字直接计算出该元素的物理地址，也称为Hash存储
3. 数据的运算
   包括数据的定义和实现。

算法和算法评价

一 算法的基本概念

算法是对特定问题求解步骤的一种描述。算法有五个重要特征。

1. 有穷性：一个算法在执行有穷步后结束，且每一步在有穷时间内完成
2. 确定性：相同输入只能得出相同结构
3. 可行性：算法操作可通过基本运算执行有限次来实现
4. 输入：一个算法有零个或多个输入
5. 输出：一个算法有一个或多个输出

算法目标：

1. 正确性
2. 可读性
3. 健壮性
4. 效率和低存储需求

算法效率的度量

1. 时间复杂度
   一个语句的频度指该语句在算法中被重复执行的次数，算法中所有语句的频度之和为T(n)，T(n)与算法中的基本运算的频率f(n)同数量级。
   算法的时间复杂度记为：
   

   
   T(n)=O(f(n))
   
   常见时间复杂度比较：
   O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

2. 空间复杂度
   算法的空间复杂度指算法所耗费的存储空间。
   算法的就地工作是指算法所需存储空间为常量。即空间复杂度为O(1)

网络应用模型

1 客户/服务器(C/S)模型

CS模型中客户是服务请求方，服务器是服务提供方，其工作流程是：

- 服务器处于接收请求的状态
- 客服机发出服务请求，等待接收结果
- 服务器收到请求后分析请求并处理，将结果发送给客户机

C/S模型特点：

- 网络中主机地位不平等，服务器拥有更高权限，可以对客户机进行限制
- 客户机之间不直接通信
- 可扩展性不佳，服务器支持的客户机数量有限

2 P2P模型

在P2P模型中，任意一对计算机称为对等方(Peer)，直接相互通信，每个结点即作为服务器也作为客户机。

P2P模型的优点：

- 减轻服务器计算压力，消除对某个服务器的完全依赖
- 多个客户机之间直接共享文档
- 可扩展性好
- 网络健壮性强

DNS系统

DNS系统用于将域名转换为IP地址

1 层次域名空间

域名可以发分为顶级域名、二级域名、三级域名等，其中最高级别的域名写在最右边。

2 域名服务器

1. 根域名服务器
   根域名服务器是最高层次的域名服务器，若本地域名服务器无法解析某域名，就会向根域名服务器求助，根域名服务器确定本地服务器要找哪一个顶级域名服务器进行查询。
2. 顶级域名服务器
   顶级域名服务器管理该顶级域名下的所有二级域名，收到NDS请求后它可能直接给出结果或给出下一跳地址。
3. 授权域名服务器(权限域名服务器)
   每一个主机都必须在授权域名服务器登记，授权域名服务器总能将其管辖的主机名转换为主机的IP地址。
4. 本地域名服务器
   主机的DNS域名请求首先发送给本地域名服务器

3 域名解析过程

域名解析是把域名映射为IP地址(正向解析)或把IP地址映射为域名(反向解析)的过程，DNS请求以UDP数据报的形式发送。
域名解析有两种方式：

- 递归查询：对根域名负载过大，集合不使用，类似于深度遍历
- 递归和迭代相结合的查询：迭代查询类似于层次遍历

递归与迭代相结合的查询方式：

- 主机向本地域名服务器的查询采用递归查询
- 本地域名服务器向根域名服务器的查询采用迭代查询

文件传输协议FTP

1 FTP的工作原理

FTP是使用最广泛的文件传输协议，FTP屏蔽了计算机系统的异构细节，适合于异构网络中的计算机之间传送文件，FTP采用C/S模型，并使用TCP的可靠传输服务。
FTP提供以下服务：

- 不同主机系统之间的文件传输
- 以用户权限管理的方式提供用户对远程FTP服务器上文件的管理能力
- 以匿名FTP的方式提供公用文件共享的能力

FTP的工作步骤：

- 打开服务器21端口
- 等待客户进程发起连接请求
- 启动从属进程处理客户机请求，客户进程请求处理完毕则从属进程终止
- 回到等待状态，继续接收其他客户进程请求

2 控制连接与数据连接

FTP在工作时使用两个并行的FTP连接：控制连接(21端口)和数据连接(22端口)

1. 控制连接
   控制连接用来传输控制信息，如连接请求和传送请求

2. 数据连接
   数据连接用来连接客户端和服务端的数据传送进程

电子邮件

1 电子邮件系统的组成结构

电子邮件是一种异步通信方式，发件人将邮件发送到收件人的邮件服务器，收件人可随时上网使用自己的邮件服务器进行读取。
电子邮件组成：

• 用户代理UA：用户与电子邮件系统的接口，通常是一个程序，如Foxmail
• 邮件服务器：发送和接收邮件
• 邮件发送协议：用于UA向邮件服务器发送邮件或邮件服务器之间发送邮件，常用SMTP
• 邮件读取协议：用于用户代理从邮件服务器读取邮件，常用POP3

邮件收发过程：

• 1 发件人用UA撰写邮件，UA用SMTP协议将邮件传送给发送方邮件服务器
• 2 发送方邮件服务器将邮件放入邮件缓冲队列
• 3 发送方的邮件服务器的STMP进程发现邮件缓存有待发送邮件，向收件方邮件服务器的STMP进程发起建立TCP连接
• 4 TCP连接建立后，STMP客户进程向远程STMP服务器进程发送邮件
• 5 接收方的邮件服务器中的STMP服务器进程收到邮件，将邮件放入收件人邮箱中
• 6 收件人调用UA，使用POP3协议读取接收方邮件服务器的邮件

2 电子邮件格式和MIME

1. 电子邮件格式

   首部:

   From:abc@gmail.com
   To:xyz@gmail.com
   Subject:HelloWorld

   主体:

   the content of this email

1. MIME(多用途网际邮件扩充)
   MIME定义传送非ASCII码的规则，用于解决SMTP只能传送ASCII码的问题。

STMP协议

STMP(简单邮件传输协议)是一种提供可靠有效的电子邮件传输的协议，STMP用TCP连接，使用25端口号。 　　
STMP通信过程：

1. 连接建立
   发送方的邮件发送到发送方的邮件服务器的邮件缓存后，STMP客户端就每隔一定的时间对邮件缓存进程扫描，如发现有邮件，就使用STMP的25端口与接收方邮件服务器的SMTP服务器建立TCP连接.
2. 邮件传送
   连接建立后，开始传送邮件
3. 连接释放
   邮件发送完毕后，SMTP客户发送QUIT命令，若返回信息是‘221’则表示对方SMTP同意释放TCP连接，邮件传送过程结束。

POP3协议

POP(邮局协议)是一个简单的邮件读取协议，POP3是它的第三版。POP3采用‘拉’(Pull)的通信方式，当用户读取邮件时，UA向邮件服务器发出请求，‘拉’取用户邮箱中的邮件。
POP3也使用C/S的工作方式，在传输层使用TCP，端口是110。

万维网WWW

1 万维网概念与组成结构

万维网内核部分构成：

• 统一资源定位符URL
• 超文本传输协议HTTP
• 超文本标记语言HTML

万维网工作流程：

• Web用户使用浏览器指定URL与Web服务器建立连接，并发送浏览请求
• Web服务器将URL转换为文件路径，并返回信息给Web浏览器
• 通信完成，关闭连接

2 超文本传输协议HTTP

HTTP协议规定在服务器和浏览器之间的请求和响应的格式和规则，是万维网进行可靠文件交换的重要基础。

HTTP的操作过程(以访问菜鸟教程为例)

1. 浏览器分析URL(http://www.runoob.com/html/html-intro.html)
2. 浏览器向DNS请求解析www.runoob.com
3. 域名DNS解析百度服务器的IP地址
4. 浏览器与该服务器建立TCP连接(端口号80)
5. 浏览器发送HTTP请求：GET /html/html-intro.html
6. 服务器通过HTTP响应把文件html-intro.html发送给浏览器
7. TCP连接释放
8. 浏览器将文件html-intro.html进行释放，并把Web页面显示给用户

HTTP协议的特点

1. HTTP协议是无状态协议，服务器不会记得曾经访问过的用户，通常采用Cookie来跟踪用户活动。
2. HTTP采用TCP作为运输层协议，但HTTP协议本身是无连接的，双方在交换HTTP报文之前不需要建立连接，
3. HTTP的非持久连接中，对每一个网页元素都需要建立一个TCP连接。
4. HTTP的持久连接中(HTTP/1.1支持)中，同一客户与服务器只需建立一个TCP连接
5. 持久连接分为流水线方式和非流水线方式，非流水线方式中，客户在收到一个响应前不能再发送下一个请求；流水线方式中，客户可以连续发送请求。

HTTP的报文结构
HTTP报文分为请求报文和响应报文

请求报文：

- 请求行：包含方法、URL和HTTP版本
- 首部行：
- 实体主体：通常不用

响应报文：

- 状态行：包含版本、状态码和短语
- 首部行：
- 实体主体：可能没有

HTTP请求报文中的常见方法：

小结