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);

}

快速幂

快速幂算法,也称二分幂。 递归写法:

typedef long long ll;
ll binaryPow(ll a, ll b, ll m){
	if(b == 0) return 1;
	if(b & 1) return a * binaryPow(a, b - 1, m) % m;
	else{
		ll mul = binaryPow(a, b / 2, m);
		return mul * mul % m;
	}
}

迭代写法:

typedef long long ll;
ll binaryPow(ll a, ll b, ll m){
	ll res = 1, pow = a;
	while(b){
		if(b & 1)
			res = res * pow % m; //注意这两个地方的取余
		pow = pow * pow % m; 
		b >> 1;
	}
	return res;
}

双指针法

双指针算法作为编程中的一种思想,利用了数据有序性,有效减少了算法复杂度。比如在两数之和的题目,可达到O(n)O(n)复杂度,而非O(n2)O(n2)。在序列递增的数组中找两个数之和为aim。

  • 对于a[i]+a[j]==Ma[i]+a[j]==M, 结果成立;
  • 对于a[i]+a[j]<Ma[i]+a[j]<M,则有a[i−1]+a[j]<Ma[i−1]+a[j]<M成立,但是a[i+1]+a[j]a[i+1]+a[j]大小未知。尝试ii向上移动
  • 对于a[i]+a[j]>Ma[i]+a[j]>M,则有a[i]+a[j+1]>Ma[i]+a[j+1]>M成立,但是a[i]+a[j−1]a[i]+a[j−1]大小未知。尝试jj向上移动

上面的算法推导有一个不太严谨的地方:没有证明[0,i−1]和[j+1,n−1][0,i−1]和[j+1,n−1]之间的元素的任何搭配不成立。

诶好像可以用归纳法!

int aim, i = 0, j = n - 1;
while(i<j){
	int sum = arr[i] + arr[j];
	if(sum ==aim){
		pirntf("%d,%d\n", arr[i], arr[j]);
		i++; j--;
	}
	if(sum < aim){
		i++
	}else j--; 
}

其他例子,如两个数列合并的双指针例子。

最大公约数——欧几里得算法

欧几里得算法又称碾转相除法,其算法基于以下定理:

gcd(a,b)=gcd(b,agcd(a,b)=gcd(b,a

其中gcd(a, b)表示a除于b的余数。

int gcd(int a, int b){
    return b? gcd(b, a % b) : a;

}

素数

用素数性质简单判断

bool isPrime(int n){
    if(n <= 1) return false;
    int sqr = (int)sqrt(1.0 * n);
    for(int i = 2; i <= sqr; i++)
        if(n % i == 0) return false;
    return true;
}

打素数表

经典的埃氏筛法

const int maxn = 1e5;
int prime[maxn], pNum = 0;

void findPrime(){
    for(int i = 2; i < maxn; i++){
        if(prime[i] == 0){
            prime[pNum++] = i;
            for(int j = i * 2; j < maxn; j += i)
                prime[j] = 1;
            printf("%d\n", i);
        } 
    }

}

素数表的经典应用就是分解质因子,在有了素数表的情况下分解一个数字的因子的复杂度为O(n−−√)O(n)

中缀式计算

中缀表示式计算分为两个步骤,一是中缀转后缀,二是后缀表达式计算;

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

stack<char> stop; // 符号栈
map<char, int> opp; // 运算符 映射到优先级 the priority of operators
stack<double> stn;// 数字栈

string mid2Post(string s){
	string res;
	for(int i = 0; i < s.size(); i++){
		if(isdigit(s[i]) || s[i] == '.') res += s[i];
		else{
            if(s[i] == ' ') continue; //去空格
			if(s[i] == '(') stop.push(s[i]);
			else if(s[i] == ')'){
				while(stop.top() != '('){
					res += stop.top();
					stop.pop();
				}

				stop.pop();
			}else{
				int pro = opp[s[i]];
				//为运算符两旁数字插入空格,否则无法区分数字
				res += ' ';
				//pop出运算优先级高的运算操作符
				while( !stop.empty() && pro <= opp[stop.top()]){ //注意这里stack要有数据,
					res += stop.top();
					stop.pop();
				}
				stop.push(s[i]);
			}
		}
	}
    
	while(!stop.empty()){
		res += stop.top();
		stop.pop();
	}
	return res;
}

// 获取正数(可有小数点)
double getNum(string &str, int &pos){
	int k = pos, flag = 1;// flag = 1表计算正整数
	double inter = 0, fac = 0, pow10 = 10;
	while(isdigit(str[k]) || str[k] == '.'){
	 	if( str[k] == '.') flag = 0;  
		else if(flag == 1){	//计算正整数
			inter = inter * 10 + (double)(str[k] - '0'); //地址?
		}else{	// 计算小数
			fac += (double)(str[k]-'0') / pow10;
			pow10 *= 10;
		}
		k++;
	 	if(k >= str.size() ) break;
	}
	pos = k;
	return inter + fac;
}


//计算后缀表达式的值
double calPost(string pStr){
	if(pStr.size() == 0) return 0;
	for(int i = 0; i < pStr.size(); i++){
		if(isdigit(pStr[i])){ //对于数字
			double t = getNum(pStr, i);
			i--; //多加了一次i
			printf("%f\n", t);
			stn.push(t);			
		}else if(pStr[i] == '+' || pStr[i] == '-' ||
			pStr[i] == '*' || pStr[i] == '/') { // 对于运算符(不包括小数,理论上规范的格式中应该被数据包裹着)
			double op2 = stn.top(); stn.pop(); //注意压栈后 数据顺序是反的
             double op1 = stn.top(); stn.pop();
    		if(pStr[i] == '+') stn.push(op1 + op2);
    		else if(pStr[i] == '-') stn.push(op1 - op2);
    		else if(pStr[i] == '*') stn.push(op1 * op2);
    		else if(pStr[i] == '/') stn.push(op1 / op2); //不做非零判断了

		}
	}
	if( stn.size() != 1){
		printf("error! the size of stck of num isn't 1.\n");
		return -1;
	} 
	return stn.top();
}
int main(){
    //freopen("data.in", "r", stdin);
	string str;
	getline(cin, str);
    cout << str << endl;
	opp['+'] = opp['-'] = 1;
    opp['/'] = opp['*'] = 2;
	opp['('] = 0; //'(' 特殊处理
    string pStr = mid2Post(str);
    cout << pStr << endl;
    double calRes = calPost(pStr);
    printf("%.2lf\n", calRes);
}

细节上也可以再改动,比如在识别数字的时候就把它提取出来并用结构体的形式存储下来。

拓扑排序



/** This is Code of JJ

Problem      :拓扑排序
Source       :
Solution     :
AnyDetial    :

DateAndTime  :2.26
CostofTime   :

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

const int N = 1e3;

vector<int>adj[N];
int indegree[N],dvis[N];

int n,m;

vector<int>res;

bool topu()
{
    int sortnum = 0;
    queue<int>q;
    for(int i=0;i<n;i++)
    {
        if(indegree[i]==0)
            q.push(i);
    }
    while(!q.empty())
    {
        int u = q.front();
        cout<< u << endl;
        q.pop();

        for(int j=0;j<adj[u].size();j++)
        {
            int k = adj[u][j];
            indegree[k]--;
            if(indegree[k]==0)
            {
                q.push(k);
            }
        }
        sortnum++;
    }

    if(sortnum==n) return true;
    else return false;
}


//dfs 逆序输出拓扑排序
stack<int> s;
int vis[N];
void dfs(int u){
    vis[u] = 1;
    for(int i=0;i<adj[u].size();i++){
        int v = adj[u][i];
        if(!vis[v]){
            dfs(v);
        }
    }
    s.push(u);
    cout<<u<<endl;
}
int main()
{
    scanf("%d%d",&n,&m);

    int c1, c2, w;
    for(int j=0;j<m;j++)
    {
        scanf("%d%d",&c1,&c2);
        adj[c1].push_back(c2);
        indegree[c2] ++;

    }
    topu();
}
/*

5 5
0 1
1 3
3 4
0 2
2 4
*/w

最短路


#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
const int INF = 0x3ffffff;
const int MX = 500;
int n, m, l, cap, s, t;
int dis[MX], vis[MX], bvis[MX], edge[MX][MX], fushe[MX];
int bec = -1    , becfu = INF, allp;
double rate = 1;
vector<int> path[MX], bepath, nwpath;
int disjk(){
    fill(dis,dis + MX, INF);
    dis[s] = 0;
    for(int i = 0;i < n;i++){
        int u = -1, minv =  INF;
        for(int j = 0;j < n; j++){
            if(!vis[j] && dis[j] < minv){
                minv = dis[j];
                u  = j;
            }
        }
        if(u == -1 ) break;
        vis[u] = 1;
        for(int v = 0; v < n;v++){
            if( edge[u][v] != INF && !vis[v]){//! vis[v] == 0 必须成立, 根据Dijkstra算法不能放缩已经标记过的节点
                                            //! 但是之前已经放缩的节点是绝对不会再被放缩的。。因为无负权
//            if( edge[u][v] != INF ){//! vis[v] == 0 必须成立, 根据Dijkstra算法不能放缩已经标记过的节点
                if(!vis[v] && dis[v] > dis[u] + edge[u][v] ){
                    dis[v] = dis[u] + edge[u][v];
                    path[v].clear();
                    path[v].push_back(u);
                }else if( dis[v] ==  dis[u] + edge[u][v]){
                    path[v].push_back(u);
                }
//            }

        }
    }
}

int bfs(){
    queue<int> que, lay;
    que.push(s);
    lay.push(0);
    bvis[s] = 1;
    while(que.size()){
        int u = que.front(), layer = lay.front(); que.pop(), lay.pop();
        if(layer < l)
            fushe[u] += (int)(ceil(1.0 * fushe[u] * (l - layer) / l));
        for(int i = 0; i < n;i++)
            if(edge[u][i] != INF && !bvis[i]){//!
                que.push(i);
                bvis[i] = 1;
                lay.push( layer + 1);
            }
    }
}
int dfs(int u){
    nwpath.push_back(u);
    if(u == s){
        allp ++;
        int npc = 0, npfushe = 0;
        for(int i = 0;i < nwpath.size(); i++){
            npc += fushe[nwpath[i]];
            if(i < nwpath.size() / 2) npfushe += fushe[nwpath[i]];
        }
        npc = npc % cap;
        if(npc > bec || npc == bec && npfushe < becfu){ //! npc >= bec
            bepath = nwpath;
            bec = npc;
            becfu = npfushe;
        }
    }else{
        for(int i = 0;i < path[u].size(); i++)
            dfs(path[u][i]);
    }
    nwpath.pop_back();
}

 int main(){
    fill(edge[0], edge[0] + MX * MX , INF);//! init
    int c1, c2, tmp;
    cin >> n >> m >> l >> cap >> s >> t;
    for(int i = 0;i < n;i ++) cin >> fushe[i] ;
    for(int i = 0; i < m;i++){
        scanf("%d%d%d",&c1, &c2, &tmp);
        edge[c1][c2] = edge[c2][c1] = tmp;
    }
    bfs();
    disjk();
    dfs(t);
    if( !bvis[t]) printf("-1\n");
    else{
        printf("%d %d %d %d\n", allp, dis[t], bec, becfu);
        reverse(bepath.begin(), bepath.end());
//        if(bepath.size()) printf("%d", bepath[0]);//! runtime error
        for(int i = 0;i < bepath.size(); i++)
            if(i + 1 == bepath.size()) printf("%d", bepath[i]);
            else  printf("%d->", bepath[i]);
    }
    return 0;
}

关键路径

​ ```

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
const int mss = 1e3 + 100;
const int INF = 0x3fffffff;
int edge[mss][mss], n, m;
int ve[mss], vl[mss], e[mss][mss], l[mss][mss];
int ingree[mss], maxtime;
stack<int> stk;
vector<int> activity[mss], tempp;
int topu(){
    queue<int> que;
    for(int i = 1;i <= n;i++)
        if(ingree[i] == 0) que.push(i);
    while(que.size()){
        int u = que.front(); que.pop();
        stk.push(u);
        for(int i = 1; i <= n;i++){
            if(edge[u][i] != INF){
                ingree[i] --;
                if(ingree[i] == 0) que.push(i);
                ve[i] = max(ve[i], ve[u] + edge[u][i]);// 拓扑排序兵同时计算 每个节点的最早开始时间
//                cout << ve[u] << endl;
            }
        }
    }
    if(stk.size() == n) return true;
    else return false;
}
int critical_path(){
    //初始化汇点
    int maxv = 0;
    for(int i = 1;i <= n; i++)
        if( maxv < ve[i]) maxv =  ve[i];
    for(int i = 1;i <= n; i++)
        vl[i] = maxv;
    maxtime = maxv;
    //逆拓扑排序地计算每个节点的最晚开始时间
    while(stk.size()){
        int u = stk.top(); stk.pop();
        for(int i = 1;i <= n;i++){
            if(edge[u][i] != INF)
                vl[u] = min( vl[u], vl[i] - edge[u][i]);
        }
    }
    // 查找关键路径
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= n;j ++){
            if(edge[i][j] != INF){
                e[i][j] = ve[i];
                l[i][j] = vl[j] - edge[i][j];
                if(e[i][j] == l[i][j]){//插入path 以便查询所关键路径
                    activity[i].push_back(j);
                }
            }
        }
    }
    //排序以保证按序输出
    for(int i = 0;i <= n; i++){
        sort(activity[i].begin(), activity[i].end());
    }
}
int dfs(int u){//输出所有关键路径
    tempp.push_back(u);
//    cout << u << endl;
    if(activity[u].size() == 0){
        for(int i =0 ;i < tempp.size() ;i++){
            cout << tempp[i];
            if(i + 1 != tempp.size()) cout << "->";
            else cout << "\n";
        }
    }else {
        for(int i = 0;i < activity[u].size(); i++)
            dfs( activity[u][i]);
    }
    tempp.pop_back();
}
int main(){
    fill(edge[0], edge[0] + mss * mss, INF);
    int u, v, w;
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        cin >> u >> v >> w;
        edge[u][v] = w;
        ingree[v]++;
    }
    if(!topu()){
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    critical_path();
    int q;
    cin >> q;
    for(int i = 0;i < q;i++){
        cin >> u >> v;
        cout << e[u][v] << ' ' << l[u][v] << endl;
    }
    cout << maxtime << endl;
    for(int i = 1;i <= n;i++)
        if( activity[i].size() && ve[i] == 0) dfs(i); //一个关键路径的起点的后序存在节点的 且最早开始时间为0
}

字符串hash

滚动哈希:O(n+m)时间内完成字符串匹配;
实现:选取两个台适的互素数$b$和h(l<b<h),假设字符串 C=clc2c3…CmC=clc2c3…Cm,定义哈希函数:
$$
H(C)=(C_1b_{m−1}+C_2b_{m−2}+⋯+C_mb_0)
$$

其中b是基数。

可以得出O(n)的时间复杂度就可以计算得到一个串的Hash值。而由取余性质

$$
(A+B)
$$

以滚动计算hash值,可实现以复杂度O(1)O(1)计算每个母串的长度为nn子串的hash值。最后再O(n+m)时间内完成字符串匹配。在实现时,可以使用64位无符号整数计算哈希值,并取M等于264264,通过自然溢出省去求模运算。

typedef unsigned long long ull;
const ull b=100000007;//哈希的基数;
//C是否在S中出现
bool contain(string C,string S)
{
     int m = C.length(), n = S.length();
     if(m > n)  return false;
     //计算b的m次方
     ull t=1;
     for(int i = 0;i < m; i++)   t *= b;
 
     //计算C和S长度为m的前缀对应的哈希值
     ull Chash=0, Shash=0;
     for(int i = 0;i < m; i++)   Chash = Chash * b + C[i];
     for(int i = 0; i < m; i++)   Shash = Shash * b + S[i];
 
     //对S不断右移一位,更新哈希值并判断
     for(int i = 0; i + m < n; i++){
          if(Chash == Shash)  return true;//S从位置i开始长度为m的字符串子串等于C;
          Shash = Shash * b - S[i] * t + S[i+m];
      }
      return false;
}

LCA问题

LCA问题即最近公共祖先问题

常见解法有递归法,向上

DeepLearning 读书笔记

DeepLearning读书笔记(1)

数学符号

英语名词:

Identity matrix:单位矩阵

Moore–Penrose pseudo inverse:摩尔-彭若斯广义逆

Determinant:行列式

Partial derivative :偏微分

Gradient :梯度

Definate integral:定积分

Variance:方差

Covariance:协方差

Shannon entropy:香农熵

Kullback-Leibler divergence:KL散度

Composition of the funcitions:函数的组合

parametrize:参数化

softplus: 公式如下

log(1+ex)log(1+ex)

The empirical distribution:经验分布(往往有训练集定义的)

疑惑处:

  • (P14) jocabian matrix 和 The Hessian matrix.

绪论

人类作为的地球上最智能的灵长类动物,可以高效地处理许多非形式化任务——难以用数学公式描述的问题,而计算机与人类正好相反,擅长处于规则化问题。AI(artificial intelligence)拥有从数据或者世界中学习模式的能力,这称之为machine learning。

简单模型的学习能力极大的依赖于数据特征。对于复杂的特征工作,表示学习 (representation learning)可以从复杂的数据中学习到远远优于人类所做出的的特征表示,仅需要稍稍的人工干预。表示学习一个典型代表就是自动编码器(autoencoder)。学习特征或者设计特征的算法的目的就是为了分离出factors of variation——影响事物变化的因素,比如识别车任务中的车轮,识别语音中的讲话人的年龄、性别。

2021年1月15日 11:56:35

更新:这种书,做笔记是不可能的,写写书上更高效。

Tag和Categories的命名

Tag和Categories的命名

最近博客的博文多了起来,有时候如何命名Tag和分类成一个小小烦人的问题。
决定记录一下刚刚思考的结果:

  • 先写categories后写tag
    • 依据博文内容来源和主题,而不是目的分categoreis
    • categories的一个分类至少或者可能有多篇博客才可以开出
    • categories条目应尽量少,但是应该全
    • 应当能完全分类
  • Tag应包括博文的描述主题,可以从不同维度联系,以便快速查找
    • 比如刷题的一篇博文,写算法——二分,DFS,LCA等等
    • 尽量不要使用categorie分类高级条目,保持内容的不重叠
  • 其内容为缩写是全大写;单个单词或者词组的第一个字母大写;

博客内容书写

关于博客内容的书写

4月份搭建的静态博客近来水了不少文章,主要是个人笔记和编程联系。但是随着POST量的增加,我也逐渐反思博客的真正意义是什么?

Read more

Hexo建站

Hexo + Github Page 建站方案

终于开始了建站之旅,之前都是采用信息源(知乎+B站+RSS)->onenote笔记来记录知识点。随着时间的推移也发现更开源、令人兴奋的方法是写博客。一来是对自己要求提高了不少,写博客可不像自己随手摘的笔记, 要求严谨而逻辑清楚,二来便于分享知识和交往新胖友。

陆陆续续装了好久也踩了不少的坑,在今天2020.04.26写下这篇博文,记录博客的开端吧!

Read more