树状数组

树状数组

A[i]数组进行前前缀和的维护的时更新成了一个大难题,树状数组提供O(logn)的复杂度更新速度。C[i]所能管理的A[i]数字如下图所示,如果查询7的前缀和,则需要计算C[7] + C[6] + C[4]

Read more

DNS污染

<转载自南通宵云网络>

更多详细内容

什么是DNS污染?

按照百度百科的解释就是:某些网络运营商为了某些目的,对DNS进行了某些操作,导致使用ISP的正常上网设置无法通过域名取得正确的IP地址。某些国家或地区为出于某些目的防止某网站被访问,而且其又掌握部分国际DNS根目录服务器或镜像,也可以利用此方法进行屏蔽。

和某些流氓运营商利用DNS劫持域名发些小广告不同,DNS污染则让域名直接无法访问了,非得修改DNS服务器不可。

怎么验证是否遭遇DNS污染?

1.点“开始”-“运行”-输入CMD,再输入 ipconfig /all ,在下“DNS SERVER”里找到你使用的DNS服务器地址。

2.再输入 nslookup http://idcbest.com(你的域名) 你的DNS服务器IP ,来查看是否能解析。

3.再输入 nslookup http://idcbest.com 8.8.8.8 使用Google的DNS服务器验证。

域名遭遇DNS污染怎么解决?

1.更换DNS解析服务器。一般来说,域名注册商家都是提供免费的DNS解析服务的,以我所实用的新之洲数据为例,就提供了许多免费的DNS解析服务,而且解析速度很快,比之前实用的什么万网之流要快得多,不可能全部被污染,所以更换两个DNS服务器即可。

2.使用第三方DNS解析服务。目前有很多第三方网站提供DNS解析服务,不少都是免费的,国内也有免费提供DNS解析服务的,使用第三方DNS服务可以部分解决问题,比如新之洲数据正在使用的DNSpod服务,就是国内还算比较稳定的DNS解析服务。

注意事项一:在换用第三方解析服务的时候,应该先到DNSPOD之类的解析服务商那里将域名解析,过几个小时再到新之洲数据之类的域名注册商那里去修改DNS服务器,这样可以避免博客出现因解析时间造成的空白期。

注意事项二:Godaddy目前本身域名就被DNS污染了,即使挂VPN也访问不了,只有更改自己电脑的DNS(比如改成google的8.8.8.8)才能访问。

3.搭建自己的DNS服务器。这样子最保险,当然也最是费时废财,有条件的朋友可以尝试。

http劫持

<转载自掘金>

深入理解Http请求、DNS劫持与解析。

背景

前段时间在处理iOS端的HTTPDNS相关SDK,在接入和测试环节发现大家对HTTP的整体请求流程包括HTTP劫持原理以及HTTPDNS的工作原理并不是太清楚,所以写下这边文章帮助大家深入web请求过程:如何发起请求,HTTP协议解析,DNS域名解析。

HTTP发起一个请求

Read more

CSAPP笔记12-并发编程

现代操作系统提供了三种方法进行并发编程——进程、I/O多路复用和线程。这章节提供了三种构造并发服务器的思路。

Read more

CSAPP笔记10-系统级I/O

输入输出是在主存和外部设备(磁盘驱动器、终端和网络)之间复制数据的过程。所有的语言都提供执行I/O的高级别工具,比如ASNI的C提供了Scanf和Printf。在Linux系统中,内核提供的系统级Unix I/O实现了较高级别的I/O函数。学习Unix I/O有助于我们理解系统I/O的运作原理,理清其他系统概念,甚至在不得已的情况使用Unix I/O编程。

Read more

CSAPP笔记-虚拟内存

CSAPP的虚拟内存章节的前半部分主要讲述虚拟内存的实现细节和运转原理,其后半部分主要学习Linux的虚拟内存管理。

Read more

CSAPP笔记7:链接

链接是将各种代码和数据片段手机并组合成为一个单一文件的过程。链接方式从编译时(compile time)的静态链接,到加载时的共享库的动态链接,发展到运行时的共享库的动态链接。

这章的内容比较严谨,对知识的连续性要求较高。最好细细品读,尽可能理解大部分内容,这对后续学习帮助较大。

Read more

CSAPP笔记5-程序优化

GCC为我们C++语言提供了优秀的自动优化方法,-O1,-O2,-Og可以配置不同优化程度。但是GCC的优化也有局限性,它小心翼翼地保护不能确定结果的代码,比如:下述代码中,如果p2指向了v的最后一个元素,其计算结果和p2指向一个int data = (*v)[(int)v.size() - 1]的结果完全不同。

Read more

数据结构知识点笔记

(有时候确实读黑书应该读原著,中文翻译著作时常有些令人琢磨不透的表达)

复杂度

O(f(N))O(f(N))表算法复杂度T(N)T(N)的函数上限,其ff增长率≥T(N)≥T(N)的增长率。

Ω(f(N))Ω(f(N))表算法复杂度T(N)T(N)的函数下限,其ff增长率≤T(N)≤T(N)的增长率。

Θ(f(N))Θ(f(N))表 ff的增长率等于TT的增长率。

o(f(N))o(f(N))表 ff的增长率>T>T的增长率。

表、栈和队列

表或者说线性表的特征在于一组有次序(非大小有序的有序,这里指前后次序的序)的元素。实现物理结构:

  • 链表
    • 带头结点的链表
    • 双链表
    • 循环链表
    • 多重表
  • 数组

栈是删除和插入都在同一端点处进行的表。物理实现同样有链表和数组。

经典题目:后缀表示式计算、中缀转后缀

队列是队尾插入,队头删除的表。物理实现:

  • 循环数组的队列

树实际上只有一个源节点的DAG。最常见的如二叉查找树(限制了子节点和节点的关系的二叉树)、AVL、哈夫曼树

算法:

  • 先序遍历、中序遍历、后序遍历
  • 二叉查找树的创建、插入、删除
  • AVL树的旋转(四种)、插入、删除(调整 )
  • 展开树(p92?)
  • m阶B树的性质
  • 哈夫曼树 (Haffman)

实现:

  • 儿子链表
  • 兄弟儿子表示法
  • 父亲表示法

经典题目:表达式树的创建

散列

散列是将关键字映射到不同的数组单元DS。三个要点:

  • 散列函数
  • 消除冲突
    • 分离链接法
    • 开放定址法
      • 线性探测法
      • 平方探测法
      • 双散列
      • 再散列是重新建表重新映射到新数组

优先队列是用堆实现的保持堆序性的完全二叉树。

算法:

  • 上浮、下滤、插入、删除;注意建堆的复杂度是O(N)O(N)。

其他数据结构(我的神啊p147?):

  • d-堆
  • 左式堆
  • 斜堆
  • 二项队列

排序

  • 插入排序
  • 希尔排序
  • 堆排序
  • 归并排序
  • 快速排序:枢纽元的一个有效选取办法就是三数中值,随机数代价高昂
  • 桶式排序
  • 外部排序: 順串的产生(优先队列 + 最小元素锚定),順串的合并(归并算法)

集合

并查集算法

图论

数据表示:邻接表、邻接矩阵、邻接多重表(无向图)、十字链表(有向图)
算法:

  • 拓扑排序

  • 最短路径

    • 无权图:遍历

    • 非负权图:Dijkstra(最小堆优化)

      Dijkstra复杂度:

      邻接矩阵实现:O(V2)O(V2)

      邻接表实现:O(V2+VE)O(V2+VE)

      堆优化实现:O(V∗log(V)+Elog(V))O(V∗log(V)+Elog(V))
      思考复杂度真是有趣

    • 负权值图:

  • 遍历:DFS,BFS

  • 网络流问题

  • 最小生成树:Prim,Kruskal

  • 非双连通性的无向图割点问题:DFS

    • 有向图?

NP问题

NP问题值非确定性多项式时间问题,如果可以在多项式时间内验证一个问题的所有“对”为正确,那么该问题就是NP问题。而NP-完全问题就是NP问题在的一个子集,所有NP问题都可以通过映射转化为NP-C问题,所以NP-C问题是最难的。(。。。。。。。)

AVL

老模板了

/** This is Code of JJ

Problem      :AVL tree
Source       :
Solution     :
AnyDetial    :

DateAndTime  :5,18
CostofTime   :17:07

**/
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

struct Node{
    int data, height;
    Node *lchild, *rchild;
    Node(int x)
    {
        data = x;
        height = 1;
        lchild = NULL;
        rchild = NULL;
    }
};
int getHeight(Node *root)
{
    if(!root) return 0;//! child node may be is NULL.
    else return root->height;
}
int getHeightFactor(Node *root)
{
    return getHeight(root->lchild) - getHeight(root->rchild);
}
void updateHeight(Node *root)
{
    root->height = max(getHeight(root->lchild),getHeight(root->rchild)) + 1;//!!! add 1
}

void search(Node *root, int x)
{
    if(!root) return;
    if(root->data==x)
    {
        printf("%d\n",x);
    }
    else if(root->data>x)
    {
        search(root->lchild,x);
    }
    else  search(root->rchild,x);
}

//! right rotate
void r_rotate(Node *&root)
{
    cout<<"R\n";
    Node* tmpr = root->lchild;
    root->lchild = tmpr->rchild;
    tmpr->rchild = root;
    updateHeight(root);//!!!update the height of tree
    updateHeight(tmpr);
    root = tmpr;
}
//! left rotate
void l_rotate(Node *&root)///!!! left rotating replace root with root's right child.
{
    cout<<"L\n";
    Node* tmpr = root->rchild;
    root->rchild = tmpr->lchild;
    tmpr->lchild = root;
    updateHeight(root);//!!!update the height of tree
    updateHeight(tmpr);
    root = tmpr;

}

void insert(Node *&root, int x)
{
    if(root==NULL)
    {
        root  = new Node(x);;
        return;
    }
    else if(root->data>x)
    {
        insert(root->lchild,x);
    }else{
        insert(root->rchild,x);
    }
    //!!you should update the weight after changing the number or the height of root and child;
    updateHeight(root);
    if(getHeightFactor(root)==2)
    {
        if(getHeightFactor(root->lchild)==1)
        {
            r_rotate(root);//!!! change the root
        }else if(getHeightFactor(root->lchild)==-1)
        {
            l_rotate(root->lchild);
            r_rotate(root);//!!! change the root
        }
    }
    else if(getHeightFactor(root)==-2)
    {
        if(getHeightFactor(root->rchild)==-1)
        {
            l_rotate(root);//!!! change the root
        }
        else if(getHeightFactor(root->rchild)==1)
        {
            r_rotate(root->rchild);
            l_rotate(root);//!!! change the root
        }
    }
}
 Node *create(int a[], int n)
 {
     Node * root = NULL;
     for(int i=0;i<n;i++)
     {
         insert(root,a[i]);
     }
     return root;
 }

 void preorder(Node *root)
 {
     if(!root) return;
     printf("%d ",root->data);
     preorder(root->lchild);
     preorder(root->rchild);
 }
 void pr(Node *root)
 {
     if(!root) return;
     printf("data: %3d   h:%d\n",root->data,root->height);
     pr(root->lchild);
     pr(root->rchild);
 }
int main()
{
    int a[10]={1,2,3,4,5,6,7,8,9,10};
    Node *root = create(a,10);
//    preorder(root);
    pr(root);

}

二叉查找树实现

二叉查找树的一个实现

尤其注意删除那一部分的逻辑!

/** This is Code of JJ

Problem      :
Source       :
Solution     :
AnyDetial    :
注意点:
1.递归边界是root为NULL
2.插入:
    查找失败--NULL--即为插入点
    利用插入创建时,第一个数据就是查找失败的点!
3.层序遍历:队列里存的是地址;
DateAndTime  :
CostofTime   :

**/

#include<iostream>
#include<queue>
#include<cstdio>
#include<stack>
using namespace std;

struct Node{
    int data,layer;
    Node *lchild,*rchild;
    Node()
    {
        lchild = NULL;
        rchild = NULL;
    }
    Node(int a)
    {
        data = a;
        lchild = NULL;
        rchild = NULL;
    }
}; //

Node* newnode(int a)//! create a node with new!
{
    return new Node(a);
}

//! find those nodes whose data is x and replace those data with x;
void search_node(Node* root, int key, int x)
{
    if(root==NULL) return;
    if(root->data==key) root->data = x;//! a -> data !
    search_node(root->rchild,key,x);
    search_node(root->lchild,key,x);
}

void insert(Node *&root, int x)
{
    if(root==NULL)//! The
    {
        root = newnode(x);
        return;
    }
    if(root->data>x)
    {
        insert(root->lchild,x);
    }else{
        insert(root->rchild,x);
    }
}

Node* create(int a[], int n)
{
    Node *root = NULL;//!the index begin with 0;
    for(int i=0;i<n;i++)
    {
        insert(root,a[i]);
    }
    return root;
}

void preorder(Node *root)
{
    if(root==NULL) return;!
    printf("%d ",root->data);
    preorder(root->lchild);
    preorder(root->rchild);
}
//!可用于递归赋值父节点信息和遍历输出根到所有节点的路径

Node *path[1000];
int pos = -1;
void preorder_withrint(Node *root)
{
    if(root==NULL) return;
    path[++pos] = root;
//    cout<<pos<<endl;
    for(int i=0;i<pos;i++)
        printf("%d ",path[i]->data);
    printf("%d\n",path[pos]->data);
//    printf("%d ",root->data);
    preorder_withrint(root->lchild);
    preorder_withrint(root->rchild);
    pos--;
}

void inorder(Node *root)
{
    if(root==NULL) return;
    inorder(root->lchild);
    printf("%d ",root->data);
    inorder(root->rchild);
}

//!错误代码 : 此代码无法识别已经某一节点右节点是否已经压入过栈,而陷入无限循环之中
void inoder_withrecursion(Node *root)
{
    cout<<"Worry Code!\n";
    Node *q;
    stack<Node*> s;
    s.push(root);
    while(!s.empty()){
        getchar()
        ;q = s.top();
        if(q->lchild)//!一个错误点
            s.push(q->lchild);
        else{
            printf("%d ",q->data);
            s.pop();
            if(q->rchild)
                s.push(q->rchild);
        }
    }
}
void postorder(Node *root)
{
    if(root==NULL) return;
    inorder(root->lchild);
    inorder(root->rchild);
    printf("%d ",root->data);
}
void layerorder(Node* root)
{
    if(root==NULL) return;
    queue<Node*>q;
    q.push(root);
    while(!q.empty())
    {
        Node *t = q.front();
        q.pop();
        printf("%d ",t->data);
        if(t->lchild!=NULL) q.push(t->lchild);
        if(t->rchild!=NULL) q.push(t->rchild);
    }

}
int layerorder_withlayer(Node* root)
{
    if(root==NULL) return 0 ;
    int Nol = 0,Non = 0,maxn = 0;
    queue<Node*>q;
    root -> layer = 1;
    q.push(root);
    while(!q.empty())
    {
        Node *t = q.front();
        if(t->layer!=Nol){
            Nol = t->layer;
            Non = 1;
            cout<<"?";
        }else
            Non ++;
        maxn = max(Non,maxn);
        q.pop();
        printf("%d %d\n",t->data,t->layer);
        if(t->lchild!=NULL) {
            t->lchild->layer = Nol + 1;
            q.push(t->lchild);
        }
        if(t->rchild!=NULL){
            t->rchild->layer = Nol + 1;
            q.push(t->rchild);
        }
    }
    return maxn;

}
//!前序遍历和中序遍历重建树
Node *create_in_pre( int inorder[], int inl, int inr, int preorder[], int prel, int prer)//! in[l,r], pre[l,r],
{
    if(inl>inr || prel>prer) return NULL;
    int pos_in = inl;
    for(;pos_in<=inr;pos_in++)
    {
        if(inorder[pos_in]==preorder[prel])// find the index of root
            break;
    }
    int numleft = pos_in - inl;// the number of left tree;
    Node *root = newnode(preorder[prel]);
    root->lchild = create_in_pre(inorder, inl, pos_in-1, preorder, prel+1, prel+numleft);
    root->rchild = create_in_pre(inorder, pos_in+1, inr, preorder, prel+numleft+1, prer);
    return root;
}

//!后序遍历和中序遍历重建树
Node *create_in_post(int in[],int inl, int inr, int post[], int postl, int postr)
{
    if(inl>inr) return NULL;
    Node *root = newnode(post[postr]);
    int pos = inl;
    for(;pos<inr;pos++)
    {
        if(in[pos]==root->data) break;
    }
    int k = pos - inl;
    root->lchild = create_in_post(in,inl,pos-1,post,postl,postl+k-1);
    root->rchild = create_in_post(in,pos+1,inr,post,postl+k,postr-1);
    return root;
}
int main()
{
    int a[1000] = {1,3,-2,5,7,-10,15,0} ,n = 8;
    Node *root = create(a,n);
//    preorder(root);
    cout<<endl;
    inorder(root);
    cout<<endl;
//    inoder_withrecursion(root);
    preorder_withrint(root);
    cout<<endl;
//    postorder(root);
//    cout<<endl;
//    layerorder(root);
//    cout<<endl<<"max of Layer\n"<< endl;
//    cout<<layerorder_withlayer(root);
//    cout<<endl;

//    int pre[10] = {1 ,-2 ,-10, 0, 3 ,5 ,7 ,15};
//    int in[10] = {-10, -2, 0, 1, 3, 5, 7, 15};
//    int post[10] = {-10 ,-2, 0, 3, 5, 7, 15 ,1};
//
//    Node *newroot1 = create_in_pre(in,0,7,pre,0,7);
//    Node *newroot2 = create_in_post(in,0,7,post,0,7);
//    cout<<"!recreate!\n";
//    inorder(newroot1);
//    cout<<endl;
//    inorder(newroot2);

}

堆算法和堆排序

堆排序

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
vector<int> a, b;
int n;
void adjustDown(vector<int> &arr, int x, int len){
    for(int p = 2 * x; p <= len; p *= 2){
        if(p < len  && arr[p] < arr[p+1]) p++;
        if(arr[x] > arr[p]) break;
        swap(arr[x], arr[p]);
        x = p;
    }
}
int main(){
    cin >> n;
    a.resize(n + 1);
    b.resize(n + 1);
    for(int i = 1;i <= n; i++) cin >> a[i];
    for(int i = 1;i <= n; i++) cin >> b[i];
    int p = 1, ch;
    while(p < n && b[p] <= b[p + 1]) p++;
    for(ch = p + 1; ch <= n && a[ch] == b[ch]; ch++);
    if(ch == n + 1){
        cout << "Insertion Sort\n";
        sort(a.begin() + 1, a.begin() + 2 + p);
    }else{
        cout << "Heap Sort\n";
        int k = n;
        while(k > 0 && b[k] > b[1]) k--;
        swap(b[1], b[k]);
        adjustDown(b, 1, k - 1);
        a = b;

    }
    for(int i = 1; i <= n; i++)
        if(i == n) printf("%d\n", a[i]);
        else  printf("%d ", a[i]);
}

完全堆排序

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 1e3;
int heap[MAXN] = {0,3,14,7,12,13,4,5,20};
int n = 8;
///! down
void downAdjust(int p,int len){
    for(int x = p * 2; x <= len; x += x){
        if(x < len && heap[x] < heap[x + 1]) x++;
        if(heap[x] < heap[p]) break;
        swap(heap[x], heap[p]);
        p = x;
    }
}
//    for(int i=1;i<=n/2;i++)
    //! 叶子的一个下标是 n/2向下取整+1
    //! 必须从底部开始调整,不然不能保持之前的子堆的有序性质
void buildHeap(){
    for(int i=n/2; i>=1; i--)
        downAdjust(i,n);
}
///!delete element
void deleteTop(){
    heap[1] = heap[n--];//! n--
    downAdjust(1,n);
}
///!!!up
void upAdjust(int p, int len){
    for(int x = p /2 ; x >= 1; x /= 2){
        if(heap[x] > heap[p]) break;
        swap(heap[x], heap[p]);
        p = x;
    }
}
void insert(int x)
{
    heap[++n] = x;
    upAdjust(n,n);
}
void show()
{
    for(int i=1; i<=n; i++)
        cout<<heap[i]<<" ";
    cout<<"\n";
}
///! head sort
void headSort(int n)
{
    buildHeap();
    for(int i=n; i>=2; i--)
    {
        swap(heap[1],heap[i]);
        downAdjust(1,i-1);//!! heap only have n-1 elements;
    }
}
int main()
{
    show();
    buildHeap();
    insert(25);
    show();
    headSort(n);
    show();
}

二叉树集合

(好像不怎么用心的样子呢)

/** This is Code of JJ

Problem      :
Source       :
Solution     :
AnyDetial    :
注意点:
1.递归边界是root为NULL
2.插入:
    查找失败--NULL--即为插入点
    利用插入创建时,第一个数据就是查找失败的点!
3.层序遍历:队列里存的是地址;
DateAndTime  :
CostofTime   :

**/

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;

struct Node{
    int data;
    Node *lchild,*rchild;
    Node()
    {
        lchild = NULL;
        rchild = NULL;
    }
    Node(int a)
    {
        data = a;
        lchild = NULL;
        rchild = NULL;
    }
}; //

Node* newnode(int a)//! create a node with new!
{
    return new Node(a);
}

//! find those nodes whose data is x and replace those data with x;
void search_node(Node* root, int key, int x)
{
    if(root==NULL) return;
    if(root->data==key) root->data = x;//! a -> data !
    search_node(root->rchild,key,x);
    search_node(root->lchild,key,x);
}

void insert(Node *&root, int x)
{
    if(root==NULL)//! The
    {
        root = newnode(x);
        return;
    }
    if(root->data>x)
    {
        insert(root->lchild,x);
    }else{
        insert(root->rchild,x);
    }
}

Node* create(int a[], int n)
{
    Node *root = NULL;//!the index begin with 0;
    for(int i=0;i<n;i++)
    {
        insert(root,a[i]);
    }
    return root;
}

void preorder(Node *root)
{
    if(root==NULL) return;!
    printf("%d ",root->data);
    preorder(root->lchild);
    preorder(root->rchild);
}
void inorder(Node *root)
{
    if(root==NULL) return;
    inorder(root->lchild);
    printf("%d ",root->data);
    inorder(root->rchild);
}
void postorder(Node *root)
{
    if(root==NULL) return;
    inorder(root->lchild);
    inorder(root->rchild);
    printf("%d ",root->data);
}
void layerorder(Node* root)
{
    if(root==NULL) return;
    queue<Node*>q;
    q.push(root);
    while(!q.empty())
    {
        Node *t = q.front();
        q.pop();
        printf("%d ",t->data);
        if(t->lchild!=NULL) q.push(t->lchild);
        if(t->rchild!=NULL) q.push(t->rchild);
    }

}
//!前序遍历和中序遍历重建树
Node *create_in_pre( int inorder[], int inl, int inr, int preorder[], int prel, int prer)//! in[l,r], pre[l,r],
{
    if(inl>inr || prel>prer) return NULL;
    int pos_in = inl;
    for(;pos_in<=inr;pos_in++)
    {
        if(inorder[pos_in]==preorder[prel])// find the index of root
            break;
    }
    int numleft = pos_in - inl;// the number of left tree;
    Node *root = newnode(preorder[prel]);
    root->lchild = create_in_pre(inorder, inl, pos_in-1, preorder, prel+1, prel+numleft);
    root->rchild = create_in_pre(inorder, pos_in+1, inr, preorder, prel+numleft+1, prer);
    return root;
}

//!后序遍历和中序遍历重建树
Node *create_in_post(int in[],int inl, int inr, int post[], int postl, int postr)
{
    if(inl>inr) return NULL;
    Node *root = newnode(post[postr]);
    int pos = inl;
    for(;pos<inr;pos++)
    {
        if(in[pos]==root->data) break;
    }
    int k = pos - inl;
    root->lchild = create_in_post(in,inl,pos-1,post,postl,postl+k-1);
    root->rchild = create_in_post(in,pos+1,inr,post,postl+k,postr-1);
    return root;
}
int main()
{
    int a[1000] = {1,3,-2,5,7,-10,15,0} ,n = 8;
    Node *root = create(a,n);
    preorder(root);
    cout<<endl;
    inorder(root);
    cout<<endl;
    postorder(root);
    cout<<endl;
    int pre[10] = {1 ,-2 ,-10, 0, 3 ,5 ,7 ,15};
    int in[10] = {-10, -2, 0, 1, 3, 5, 7, 15};
    int post[10] = {-10 ,-2, 0, 3, 5, 7, 15 ,1};

    Node *newroot1 = create_in_pre(in,0,7,pre,0,7);
    Node *newroot2 = create_in_post(in,0,7,post,0,7);
    cout<<"!recreate!\n";
    inorder(newroot1);
    cout<<endl;
    inorder(newroot2);

}

数据库管理复习梗概

参考书籍:《数据库系统教程》3Ed. 施伯乐

基本概念

概览

  • 数据库(DateBase,DB):长期存储在计算机内的数据集合

  • 数据库管理系统(DataBase Mangement System, DBMS):管理数据库的软件,其操作包括CRUD。

  • 数据库系统(DataBase System,DBS):由计算机软硬件和数据资源组成的计算机系统。

  • 实体联系(Entity Relationship,ER)模型:对实体和实体之间关系的抽象。

  • 概念模型:对用户需要的建模,往往建立出了ER模型。

  • 逻辑模型:表达了数据库整体逻辑的模型。最重要的是关系模型,对象模型,还包括层次模型、网状模型。

  • 逻辑独立性:应用程序与数据库的逻辑结构保持独立,即数据库的逻辑结构由DBMS即使变化了,应用程序也无需变化。

  • 物理独立性:应用程序与数据库的物理结构保持独立,即数据库在磁盘的保存格式有数据库管理系统设置,应用程序无需关注数据库的物理结构。

    两种独立性都是将数据在磁盘中的定义和存储格式独立分离出去,因而简化应用程序编程,减少了程序维护和修改。

    关系模型

  • 关系模型:简单理解为一个二维表格

  • 子模式:用户需要用到数据的描述(?)

    • 记录\元祖:表格中的一行数据
    • 关系\实例:元祖的集合
    • 字段\属性:表的一列的列本身
    • 元数:属性的个数
    • 基数:元祖个数
  • 关键码\key\键:字段或者字段的集合

    • 超键(super key):可以唯一标识元祖的键
    • 候选键(Candidate key):不含多余属性的超键
    • 主键(Primary key):用户选择的候选键
    • 外键(Foreign key):其他关系模型的主键
  • 完全性规则(*表示省略相同成分):

    • 实体:主键不可缺
    • 参照:外键指向的元祖不可空
    • 用户:用户可自己定义完整性
  • 关系代数

    • 并:两个关系模型的去重合并
    • 差:关系模型AB相减
    • 笛卡尔积:两个关系模型的全排列
    • 投影:选择一个关系模型若干列
    • 选择:选择一个关系模型的若干行
    • ————
    • 交:求两个关系模型的公共元祖
    • 连接:筛选出符合条件的两个模型的笛卡尔积
    • 自然连接:条件是公共字段相同的连接,并去除公共字段
    • 除法:A/B即尽可能 包含了所有B字段的且除了B字段A字段值相同的元祖集合。(简要的记忆为寻找公因数)
    • ————
    • 改名
    • 广义投影:允许投影中使用算术运算
    • 外连接:就是把自然连接过程中丢失的元祖加以填充空值(NULL)并加入自然连接的结果
    • 左(右)外连接:类似于外连接,就是把单单是左(右)边的模型丢弃掉的元祖加入
    • 半连接:自然连接后投影到一个关系模型(不残缺的那边)上

SQL语句

术语

  • 基本表:关系模式
    • 表的三种类型:
      • 基本表:实际存储在数据库中的表
      • 视图:若干表和其他视图组成的表的定义,在用户面前都是一样的
      • 导出表:查询导出的表
  • 存储文件:存储模式(文件存储的方式)
  • 视图:子模式
  • 行:元祖
  • 列:属性
  • SQL模式(schema):约束集合(可能有多个表)

操作

模式创建CREATE SCHEMA <模式名> AUTHORIZATION <用户名>

模式撤销DROP SCHEMA <模式名> [CASCADE | RESTRICT] ; CASCADE即级联式,撤销下属的模式中所有的基本表、视图、索引;RESTRICT即约束式,仅当模式不存在任何下属元素才允许撤销;(SCHEMA可以替换为DATABASE

添加自定义类型CREATE DOMAIN <YOUR_DOMAIN> CHAR(8)这里把CHAR(8)定义成了自定义的domain名,可直接使用

创建基本表

CREATE TABLE <基本表名>
	(
      --列表类型
      T#  CHAR(4) NOT NULL, --默认允许空值(与主键定义冗余)
	 TITLE CHAR(10), 
     -- 完整性约束
	 PRIMARY KEY(T#)    -- 定义主键
     FOREIGN KEY(C#) REFERENCES S(C#) --定义外键为C#,且对应S表的主键C#
    
	);

插入数据:

INSRET

修改基本表:

--增加表的列
ALTER TABLE <基本表名> ADD  <列名> <类型>
--删除表的列
ALTER TABLE <基本表名> DROP <列名> [CASCADE | RESTRICT ]
	-- CASCADE表明删除列的同时删除所有使用该列约束和视图
--修改列形状
ALTER TABLE <基本表名> MODIFY   <列名> <类型>

撤销基本表:

DROP TABLE <基本表名> [ CASCADE| RESTRICT] --同理

索引:??

数据查询:

--- 基本sql查询语句
SELECT 属性1,属性2.....属性n 
FROM 表1,表2......表N
WHERE 关系表达式

---sql语句之间可以使用UNION(并) \ INTERSECT(交) \ EXCEPT(差)


----嵌套查询,括号中的子查询优先进行
SELECT 属性1,属性2.....属性n 
FROM 表1,表2......表N
WHERE 关系表达式 IN (
	SQL查询语句
	)
	---嵌套查询的速度往往比笛卡尔积的运算速度快

待补充:更复杂的还有相关子查询(。。)、where使用的运算符,以及(P85~P101)


关系数据库的规范设计

基本概念

函数依赖(FD,Functional Dependency):当一个基本表中的属性集Y是属性集X的”函数值”(即X的值可以确定出唯一的Y),就说明了X->Y,或者说Y依赖于X,这个基本表存在函数依赖。

(函数蕴涵P120)

逻辑蕴涵:若函数依赖集合F中存在的FD X→YX→Y和Y→ZY→Z,存在X→ZX→Z成立,则可称为F逻辑蕴涵X→ZX→Z 。

闭包: 就是函数依赖集上FF所有函数依赖和逻辑蕴涵推出来的依赖关系的完整集合,即为F+F+ 闭包。

FD推理规则: A→BA→B

  • 自反性:AA自身能确定出自身的子集,这样推导出来的FD也称平凡的FD
  • 增广性:依赖两边可以同时增加变量
  • 传递性:可传递(逻辑蕴涵)
  • ————
  • 合并性:同时能推导出两个结果BCBC,就能推导出两个结果的和B,CB,C
  • 分解性:与合并性相反,是将结果BCBC拆分成两个B,CB,C
  • 伪传递性:传递过程中需要添加一个因素,X→Y,YZ→WX→Y,YZ→W 等价于XZ→WXZ→W
  • 复合型:两个FD可以两边组成成一个FD
  • ————
  • 可以使用FD的定义来定义超键和候选键

当函数依赖集的闭包相等时,函数依赖集等价。可定义最难小函数依赖集:

  • FD右边都是单属性;
  • 无冗余FD
  • FD的左边的属性集不是冗余的(子集无法代替集

求出R的最小依赖集算法

  1. 分解FD的右边属性集,并去重
  2. 消除左边冗余的FD
  3. 消除R中冗余FD

模式分解特性

无损分解:把数据库模式分解为多个模式,并将分解的模式全部自然连接发现多出了元祖(寄生元祖)(也就是有损分解,实际上是信息的丢失,信息论!不确定性越大,信息量越小)。反之如果元祖不多不少就是无损分解。

上述讨论中假设模式存在一个“范关系”rr,可以分解为多个子关系rkrk。

当然也存在不存在范关系的rr,在连接过程中某个riri子关系的元祖会被丢失掉,这个被称为破环范关系的悬挂元祖

依赖保持:就是分解的模式中的依赖的并与原模式的依赖等价。

无损分解的测试方法:略(p128)

保持函数依赖的分解:略(p129)

关系模式的范式

第一范式:关系模式的R的关系r的属性值都是不可分的单一的(反例“AB”)

第二范式:每个非主属性完全依赖于候选键(挺严格的)。不完全依赖也就是局部依赖意味着A→BA→B 这个条件存在BB依赖于AA的一个子集,(注意这个FD推理规则A1不一样)

主属性:关系模式中R的候选键中的属性

化解成第二范式的算法:将一个局部依赖X→YX→Y的属性XYXY提出来形成一个关系,同时在原有属性集UU形成一个新的关系U−YU−Y;重复上述动作直到没有局部依赖。

第三范式:每个非主属性都不传递依赖与候选键,即为第三范式

传递依赖就是:X→Y,Y→ZX→Y,Y→Z 且X不依赖与Y,Z不是Y的子集

BC范式: 每个主属性不都传递依赖于候选键,则为BC范式。(相比于第三范式排除了主属性对候选键的传递依赖)

分解方法:略(p134)


数据库设计和ER模式

数据库设计过程:

  1. 规划:调查、可行性分析等
  2. 需求分析:分析用户活动,系统范围,分数用户数据,数据流图;数据字典(描述数据)
  3. 概念设计:数据抽象设计局部概念模型和全局概念模型(比如ER)
  4. 逻辑设计:把上一步概念模型转化符合具体DBMS的逻辑模型,比如关系模型;设计外模型(api接口);评价模型;修正模型
  5. 物理设计:存储记录结构设计;确定存储位置;完全性和安全性考虑;

ER图

组成结构:

  • 实体:数据对象
  • 联系:实体之间的关系
    • 元数\度数(degree):联系所涉及的实体个数
    • 数值约束:
      • (x,y)表示该实体的联系的另一方的数量限制
      • N或者:表示对实体在联系中的映射数量关系
    • 参与约束:
      • 双直线:完全参数该联系
      • 单直线:部分参与该联系
  • 属性:实体的特征
    • 简单属性和复合属性:在于可不可分
    • 单值和多值属性:在于可不可同时取多个值
      • 替换:
        • 多值属性替换为一个新的实体类型
        • 用多个单值属性代替

ER转关系模型的算法:

  1. 实体直接转化为一个关系
  2. 关系的转化方法
    1. 一元关系直接转化属性
    2. 1:1关系转化为一个实体的外键和属性
    3. 1:N关系转化”N处”实体的外键和属性
    4. N:M关系转化为两个实体的主键和一个属性
    5. ————
    6. 三元关系可类比二元关系的转化方法(太无聊了不看了)

数据库存储结构

文件组织

定长存储:连接方法和顺序方法

不定长存储解决方案:

  • 字符串表示形式:分槽式页结构(定长的首部顺序排列并记录剩余数据的其实起始地址,不定长的二进制数据从低端生长)

  • 变长记录的定长表现形式:预留空间、固定块的溢出块相补充、定长块的连接形式(p187)

    (不想看了555)

CSAPP笔记2

程序结构和执行过程

本章主要讲解程序在机器级代码上的执行过程以及程序编译翻译过程。

信息存储

相比人类熟悉的代表了十指的十进制,二进制的稳定性、表达形态少、对硬件芯片的友好性是建造计算机的更优选择。典型的二进制应用就是记录数值,float-point encodingUnsigned encoding就是代表。

有趣的是,计算机的算术运算过程即使是对溢出运算也会满足结合律(associative)

数值组成的bit有限就造成了数据表达的有限,从而引出的计算溢出,甚至安全问题都是编程者需要考虑的。


虚拟空间(virtual memory)是计算机操作系统提供的虚拟空间,以C语言的指针举例,一个C pointer指向的一定是一个数据类型(int, float, or structure)的第一个字节的虚拟地址。C语言本身会组织类型信息(type information)以便获取指针指向的数据内容,但是在机器级的代码中所有的程序对象都是一样的bit。(p63)

C语言在早期计算机语言发展占据重要的位置,比如提供了内存分配器(memory allocator)——the malloc library function。C语言的编译可以对GCC(Gun Compiler Collection)添加参数以控制编译版本

  • gcc -std=c11 prog.c 指定了C11标准版本
  • -std=c99指定了C99版本
  • -ansi-std=c89指定了C90版本
  • -std=gnu11指定了GNU项目的开发的一个版本,包括了ISO C11的内容

C语言支持向后兼容(backward compliale,“后”就是指过去,而非口语所说的“以后”),那么C语言编译的32bit的程序也可以在64位机子上跑。但是64bit的程序不能在32位的机子上跑。

  • gcc -m32 prog.c 设置了编译的位数,同理-m64设置了64bits

C的指针有两个方面——值和类型,值指向了指针指向的内容的地址,类型指出了指向的地址的存放的信息的种类。

十六进制计数 (Hexadecimal Notation)

image-20200503124826544

image-20200503124826544

1000多页是时候考虑时间问题了,有更值得去做事情去干,暂时读的话还不读英文版了。

CSAPP笔记1

Programmer’s Perspective )–3th edition

考完了研究生,浪荡了许久,终于肯安下心来钻研提升内功,就从这本书开始吧,抄录两端话送给自己的激励!

读完了本书以后你将成为极少数的“牛人”,这些“牛人”知道事情是怎么运作的,也知道当事情出现故障是如何修复。你写的程序将能更好利用操作系统和系统软件提供的功能,对各种操作条件和运行时的参数都能正确操作,运行起来更快,并避免出现使得成型容易受到网络攻击的缺陷。同时你也要做好更深入探究的准备。研究像编译器,计算机体系结构,操作系统,嵌入式系统、网络互连和网络安全这样高级题目。——译者序

We cover data representations, mechine level representations of C programs, processor architecture, program optimizations, the memory hierarchy, exceptional control flow(exceptions, interrupts, processes, and Unix signals), virtual memory and memory management, system-level I/O, basic network programming, and concurrent programming. THes concepts are suppeorted by series of fun and hands-on lab assignments. —— CSAPP online.

正如书籍的题目,此书的编写者考虑到大多数人都不会编写一个OS或者制作一个CPU,那么从一个程序员的角度可以更具体而实用的理解类似于C语言是怎么编译成汇编语言,不同的设置是如何影响计算机性能的,代理是如何工作的计算机基础内容。此书着手于x86处理器机器和Linux类系统,并用C作为工具来实操,提供了多个Lab。

CHAPTER 1 The wonder of computer system

伟大的编译器

一个最基本的C源文件是由N个ASCII码组成的数据串,将以文件的形式存储在计算机磁盘中。而每个ASCII都有由8bit组成,或者说是一字节组成,容易忽视的是,文本每一行的末尾都有\n符号,其编码为10,或者是00001010

中文的注释计算机将怎么处理?猜测可能有文件保存读取编码方式有关。

在linux环境下每一个C源文件都会被编译驱动(compiler driver)所编译为machine-language instructions 组成的可执行程序。

image-20200503124858005

image-20200503124858005

Pre-processor:预处理器

Assembler:汇编器

Linker:链接器

gcc -o hello hello.c 运作四个步骤:Preprocessing phase将#include<stdio.h>的语句所标记的系统头文件stdio.h内容插入到程序文本中,并形成hello.i;Compilation phase:将hello.i翻译成assembly-language program(汇编程序);

汇编语言作用之处在于给多种高层次语句的不同编译器提供同一个低层次的输出语言。

Assembly phase: 汇编器将汇编程序hello.s翻译成机器及的二进制relocatable object program(可重定位程序)。

GCC是伟大的自由(free speach的自由)软件思想主导的运动GUN(GUN’s Not Unix, hh递归的)的产物,其功能强大,能够支持多种语言。同样的GUN产物还有GDB debugger,EMACS editor。

Linking phase:linker将预编译好的printf.o文件链接到可重定位文件hello.o形成了最终的可执行文件hello。

重视编译器的效率问题

作为现代工具的使用者,我们程序员无需重造一个编译器或者了解其中的构造,但是更有意义的是去了解如何编写代码才能让编译器翻译出更有效率的代码。书中提出了几个例子:if-else是否比switch更有效?forwhile哪个效率更高?pointer referenes 是否比数组下标更快?为什么简单的重新放置算数表达式参数(arithmetic expression)可以提高效率?

处理器读取和接触存储在内存中的指令

commmand-line interpreter ——shell 可以接受指令并运行,如果输入的指令一个word不是built-in shell command,那么shell就会默认该字符为可执行文文件并load和执行,如./hello将执行可执行文件hello,shell会等待程序结束(terminate),之后输出提示符(a prompt)。

系统硬件组织

image-20200503124915375

image-20200503124915375

一个Inter风格的硬件组织图

总线(Buses)

类似人体血管的贯通系统内部传输固定大小电子信息比特的管道(conduits),通常这个大小的值不固定。

I/O 设备(I/O Devices)

I/O设备是计算机系统负责接收发送给外部世界的设备,通过控制器(contrlllers)和适配器(adapter)连接到I/O总线。控制器和适配器的目的为了传输信息,但是控制器是由计算机原有的芯片控制的或者说是在母板(motherboard)上的电路印刷而成的,适配器是可以插入母板插槽的芯片卡。常见的外部设备有磁盘、显示器和鼠标键盘。

主存(Main Memory)

主存是系统在运行程序时的暂时存放数据和指令的空间。物理上,其一般有动态随机存储芯片(dynamic random access memory, DRAM)芯片组成。逻辑上说内存实际就是一个地址从零开始的线性字节数组。另外系统指令可由多个比特组成,数据项大小随数据类型不同而变化。

原句: In general, each of the machine instructions that constitute a program can consist of a variable number of bytes

处理器(Processor)

中央处理器(central processing unit)是计算机的心脏,负责解释(interpet)和执行(execute)从内存运送到CPU的IR(instrruction register)的指令。简单的说,CPU包括了其运算器部分(如ALU,寄存器等)和控制器部分(如PC,IR等等)。在CPU运行过程中,CPU解释PC指向的指令,根据指令执行操作并更新PC值。

简单来说,指令包括了Load、Store、Operate(数据运算)和Jump类。

运行hello程序

从硬件底层在理解一次刚刚的运行过程,在我们打入./hello命令指示,shell程序将键盘输入的字符通过寄存器和总线存储到内存中,当输入Enter1后shell开始执行shell程序。

有趣!

image-20200503124936718

image-20200503124936718

shell将原本存储在Disk中的代码和数据复制到内存中。系统借助了直接存储器存储器(direct memory access, DMA)而无需通过CPU传输数据直达主存。

image-20200503124954066

image-20200503124954066

最后,CPU运行hello程序,执行对应指令,并把数据hello,world\n复制到寄存器并打印到屏幕。

image-20200503125006147

image-20200503125006147

其中必然包括了中断技术。

高速缓存至关重要

从上文的例子看到程序运行过程中存在大量数据和指令移动,而现有的机械结构却造成了存储器速度和容量之间的取舍难题。往往速度快的存储器(比如寄存器)容量却很小,相反的容量大的存储器比如磁盘、光盘存储速度都很慢。为了解决这一难题,现在计算机配备了高速缓存(cache),甚至是多级高速缓存。其运用了局部性原理(locality)。这对程序性能有着重要影响。

locality:程序会倾向于使用局部区域的代码和数据

image-20200503125016708

image-20200503125016708

cache的加入让我们有一个更美妙的想法:存储器层次结构(memory hierarchy),这种结构从上到下,速度逐渐变慢,价格变低,同时容量上升。更有趣的是,上层可以视为相邻下层的缓存,相邻下层可以视为上层的存储,比如分布式系统中的本地磁盘就是远程存储系统的缓存。

操作系统管理硬件

hello程序运行中时,外部数据的输入和打印屏幕这些操作硬件的举动都不是源程序或者shell所做的,都是使用了操作系统所提供的接口。操作系统是计算机硬件和应用软件之间的管理层,一方面负责保护硬件不直接受到应用软件的操作,另一方面提供给所有应用软件统一且简单的接口。

image-20200503125027579

image-20200503125027579

操作系统通过几个抽象的功能来实现对计算机资源的管理,如下图。

确实抽象,Processes本身带着运行程序的位置信息、进程信息和源程序信息,也就是说Processes是对三者的管理。其他类似

image-20200503125035839

image-20200503125035839

进程(Processes)

即使是单核处理器(uniprocessor)计算机也可以同时(宏观)运行多个进程,操作系统在记录并控制了所有进程的上下文(content)。操作系统通过保存当前的进程上下文,并载入一个新进程的上下文可以实现进程切换。

image-20200503125045850

image-20200503125045850

一个正在运行的进程可以通过系统调用来调用操作系统的功能,比如读写磁盘,执行另一个程序创建新进程。

线程(Threads)

线程作为“轻量级”的进程,能快速访问同进程下的共享资源,占有更少的内存空间,运行效率更高,可以充分利用多核计算机的计算效能。

虚拟内存(Virutual Memory)

顾名思义,虚拟内存是操作系统在内存的基础上虚拟空间。对于软件来说虚拟内存唯一可以接触到的空间,物理内存对他们是透明的。

image-20200503125120329

image-20200503125120329

从低地址到高地址所存放的内容分别是:

  • 程序的代码和数据
  • 读写数据
  • 堆(heap):可以由进程通过程序malloca,new动态创建
  • 分享库(shared libraries):比如C++的math
  • 栈:在用户调用函数增长,返回函数时减小,
  • 内核虚拟内存:保留给内核程序的空间。用户应用程序无法读取这部分内容,也无法直接掉调用。

文件(Files)

至少在Unix I/O上,file系统将各式的外设输入输出设备、甚至网络建模成一个文件。统一的文件形式给系统操作员极大的方便。

linux: a complex, Posix-compliant version of the Unix operating system.

posix,Portable Operating System Interface X——可移植操作系统接口

网络:计算机与其他系统的沟通桥梁

讲的太粗略,不计

重要主题

This concludes our initial whirlwind tour of systems. An important idea to take away from this discussion is that a system is more than just hardware. It is a collection of intertwined hardware and systems software that must cooperate in order to achieve the ultimate goal of running application programs.

Amdahl’s Law

Amdahl’s Law假设简单系统的各个部件线性工作,提升一个部件的效率其实对整齐来说提升并不明显。

image-20200503125132267

image-20200503125132267

并发(Concurrency)和并行(Parallelism)

并发是对计算机同时运行多个事件的广义概念。并行是指???

在分时(time-sharing)操作系统上,所谓的并发仅仅只是一种模拟(simulated),通过不断的切换进程(在进程(Process-Level Concurrency)级别上 )让电脑同时相应多个用户的操作。而在线程级别(Threa-Level)上,即时在单核对一个单一的进程也有执行的多重控制流。

随着由多个有单独的操作系统内核管理的单个处理器组成的多核处理器(multiple processors)的到来,多核操作系统诞生了,随之而来的是超线程(hyperthreading)!

image-20200503125144846

image-20200503125144846

image-20200503125157325

image-20200503125157325

超线程(也称为sinultaneous multi-threading)是一种允许一个核同时执行的多个控制流,涉及了部分硬件的多分设计,比如PC(program countes),寄存器文件,而其余硬件只设一份,比如浮点数计算。可以说,在并发概念提出50年的铺垫后,多核处理器和超线程的出现才引爆了对多线程编程应用和并行的极大热情。(Eng. P55)

指令级并行通过多核处理的多核处理能力,以及现代流水线架构来实现。

单指令多数据(SIMD,single-instruction, multile-data)并行是通过特殊硬件允许一条指令同时进行多重操作。常常用于处理图像、声音等数据。

抽象(abstraction)的重要性

计算机最重要的两个概念——抽象和局部性原理

抽象在计算机领域无处不在,提供给调用者的统一的函数接口API(Application program inteface)是函数的抽象,文件本身就是输出输入设备和物理数据的抽象,虚拟内存是内存和文件的抽象,进程是指令和数据的抽象,而计算机本身也是一个运行在硬件上的虚拟机(可见开头图)

终于读完了一个综述,开心 :heart: :happy::happy::happy:~~于2020.04.27.10:17

CNAME和A记录

域名解析中A记录、CNAME记录的区别和联系

域名解析就是域名申请后做的到IP地址的转换过程。域名的解析工作由DNS服务器完成。

A (Address) 记录是用来指定主机名(或域名)对应的IP地址记录。用户可以将该域名下的网站服务器指向到自己的web server上。同时也可以设置您域名的二级域名。

CNAME记录即:别名记录。这种记录允许您将多个名字映射到另外一个域名。通常用于同时提供WWW和MAIL服务的计算机。例如,有一台计算机名为“host.mydomain.com”(A记录)。它同时提供WWW和MAIL服务,为了便于用户访问服务。可以为该计算机设置两个别名(CNAME):WWW和MAIL。这两个别名的全称就 “www.mydomain.com” 和“mail.mydomain.com”。实际上他们都指向“host.mydomain.com”。

两者的区别在于A记录就是把一个域名解析到一个IP地址(Address,特制数字IP地址),而CNAME记录就是把域名解析到另外一个域名。其功能是差不多,CNAME将几个主机名指向一个别名,其实跟指向IP地址是一样的,因为这个别名也要做一个A记录的。但是使用CNAME记录可以很方便地变更IP地址。如果一台服务器有100个网站,他们都做了别名,该台服务器变更IP时,只需要变更别名的A记录就可以了。

域名解析CNAME记录A记录对网站的影响不大。但是:CNAME有一个好处就是稳定,就好像一个IP与一个域名的区别

排序总结

交换类?

选择排序

不具有稳定性,复杂度稳定在O(n2)O(n2)。

存在不同元素大范围交换,所以不稳定。

int main(){
    // freopen("./data.in", "r", stdin);
    int c[6] = {5, 3, 2, 1, 7, 2}, n = 6;
    for(int i = 0; i < n; i++){
		int mp = i;
        for(int j = i + 1; j < n; j++){
            if(c[j] < c[mp]){
				mp = j;
			}
        }
        int temp = c[mp];
        c[mp] = c[i];
        c[i] = temp;
    }
    for(int i=0; i < n; i++){
        printf("%d ", c[i]);
    }
    printf("\n");
    return 0;
}

冒泡排序

具有稳定性,复杂度为O(n)O(n)到O(n2)O(n2)。

int main(){
    // freopen("./data.in", "r", stdin);
    int c[6] = {5, 3, 2, 1, 7, 2}, n = 6;
    for(int i=0; i < n-1; i++){
        int flag = 0;
        for(int j=0; j < n - 1 - i; j++){
            if(c[j] > c[j+1]){
                int temp = c[j];
                c[j] = c[j + 1];
                c[j + 1 ] = temp;
                flag = 1;
            }
        }
        if(!flag) break;
    }
    for(int i=0; i < n; i++){
        printf("%d ", c[i]);
    }
    printf("\n");
    return 0;
}

??

插入排序

具有稳定性,复杂度为O(n)O(n)到O(n2)O(n2)。

int main(){
    // freopen("./data.in", "r", stdin);
    int c[6] = {5, 3, 2, 1, 7, 2}, n = 6;
    for(int i = 1; i < n; i++){
        int j = i, t = c[j];
        while(j > 0 && t < c[j - 1]){
            c[j] = c[j - 1];
            j--;
        }
        c[j] = t;
    }
    for(int i=0; i < n; i++){
        printf("%d ", c[i]);
    }
    printf("\n");
    return 0;
}

归并排序

稳定,复杂度为O(nlgn)O(nlgn)。

int printArr(int A[], int r, int l){
    for(int i=r; i < l + 1; i++){
        printf("%d ", A[i]);
    }
    printf("\n");

}

const int maxn  = 100;
int merge(int arr[], int l1, int r1, int l2, int r2){
	int i = l1, j = l2, k = 0;
	int temp[maxn];
	while(i <= r1 && j <= r2){
		if(arr[i] < arr[j])
			temp[k++] = arr[i++]; 
		else if(arr[i] >= arr[j])
			temp[k++] = arr[j++];
	}
	while(i <= r1)
    	temp[k++] = arr[i++]; 
	while(j <= r2)
    	temp[k++] = arr[j++]; 
    for(int i = l1, k = 0; i <= r2; i++, k++) arr[i] = temp[k];
}

//递归写法
int mergeSort_re(int A[], int l, int r){
	if(l < r){
		int mid = (l + r) / 2;
		mergeSort_re(A, l, mid);
		mergeSort_re(A, mid + 1, r);
		merge(A, l, mid, mid + 1, r);
	}
}
// 迭代写法
int mergeSort_for(int A[], int l, int r){
	if(l < r){
		int n = r - l + 1;
		//step为组内元素个数
		for(int step = 1; step <= n; step *= 2){
			for(int i = 0; i < n; i += 2*step){
				//这么写行不行?测试一下A[5]
				// 事实证明这种写法很优美!
				merge(&A[l], i, i + step - 1, i + step, min(i + 2 * step - 1, n - 1));
			}
		    printArr(A, l, r);
        }
        
	}

}
int main(){
    // freopen("./data.in", "r", stdin);
    int c[10] = {5, 3, 2, 1, 7, 2, 10, 3, 5, -1}, n = 10;
    
    // mergeSort_re(c, 0, n - 1);
    mergeSort_for(c, 5, n - 1);
    
    printArr(c, 0, n - 1);
    return 0;
}

快速排序

不稳定,复杂度为O(nlgn)O(nlgn)到O(n2)O(n2),最广泛使用的排序算法。

//挖沙法 分割
int Partition(int A[], int l, int r){
	//三个数取最小值
    int minp = l;
    if(A[r] < A[minp]) minp = r;
    if(A[(r + l) / 2] < A[minp]) minp = (r + l) / 2;
    int temp = A[minp];
    A[minp] = A[l];
    A[l] = temp;
    int i = l, j = r;
    while(i < j){
        while(i < j && temp < A[j]) j--;
        A[i] = A[j];
        while(i < j && temp >= A[i]) i++;
        A[j] = A[i];
    }
    A[j] = temp;
    return j;
}
void quickSort(int A[], int l, int r){
    if(l >= r) return;
    int mid = partition(A, l, r);
        printArr(A, 0, 9);
        printf("%d\n", mid);
    quickSort(A, l, mid - 1); // 如果这里取mid - 1, 可能会导致mid为右侧最小值的情况时,无限partition!(没错,微妙的递归)
    quickSort(A, mid + 1, r);

}