关系数据理论

发表于 2018-10-15 分类于学习笔记，数据库系统
本文字数： 1.1k 阅读时长 ≈ 1 分钟

【问题的提出】

之前已经介绍过关系数据库的基本概念、关系模型的三部分、关系数据库的标准语言 SQL，但有一个很基本的问题没有涉及：针对一个具体问题，应该如何构造一个适合它的数据库模式，即应该构造几个关系模式，每个关系由哪些属性组成等

这个问题确切来讲是关系数据库逻辑设计问题，由于关系模型有严格的数学理论基础，且可以向别的数据模型转换，因此，以关系模型为背景讨论这个问题，形成了数据库逻辑设计的一个有力工具，即关系数据库规范化理论

阅读全文 »

二叉树的遍历

发表于 2018-10-15 分类于 OI&ACM ，数据结构，树与二叉树
本文字数： 3.5k 阅读时长 ≈ 3 分钟

【概述】

树中最基本的操作是遍历，即从根结点出发，按照某种次序访问树中的所有结点，使得每个结点仅被访问一次

在二叉树中，有两种遍历方式，一种是基于树的递归特性的前/中/后序遍历，一种是基于树的层次特性的层次遍历

阅读全文 »

树的数据生成器

发表于 2018-10-13 分类于 OI&ACM ，数据结构，树与二叉树
本文字数： 1.1k 阅读时长 ≈ 1 分钟

为方便测试与树相关的算法而编写的树的随机数据生成器

树的结点为 1~10 个，边权为 1~100，各点编号随机化

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include <algorithm>
#include<ctime>
using namespace std;
#define N 50

struct Edge {
    int x, y;
    int dis;
} edge[N];
int n,edgeTot;
int tot, x[N], y[N], dis[N];
int id[N], father[N];
int Find(int x) { return father[x] == x ? x : Find(father[x]); }
int main() {
    srand(time(0));
    n = rand() % 10 + 1;
    
    printf("%d\n", n);
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            x[++tot] = i;
            y[tot] = j;
            dis[tot] = rand() % 100 + 1;
        }
    }
    for (int i = 1; i <= tot; ++i){
        id[i] = i;
        father[i] = i;
    }
 
    random_shuffle(id + 1, id + tot + 1);
 
    for (int i = 1; i <= tot; ++i) {
        int pos = id[i];
        int fx = Find(x[pos]);
        int fy = Find(y[pos]);
        if (fx == fy)
            continue;
        father[fy] = fx;
 
        edge[++edgeTot].x = x[pos];
        edge[edgeTot].y = y[pos];
        edge[edgeTot].dis = dis[pos];
        if (edgeTot == n - 1)
            break;
    }
 
    for ( int i = 1; i <= edgeTot; i++)
        printf("%d %d %d\n", edge[i].x, edge[i].y, edge[i].dis);
        
    system("pause");
    return 0;
}