专业课知识复习

2019-07-05

算法

图

数据结构

二叉树的定义

数据库

三个范式 link

第一范式(1NF)

1NF是对属性的原子性，要求属性具有原子性，不可再分解；

表：字段1、字段2(字段2.1、字段2.2)、字段3 ……

如学生（学号，姓名，性别，出生年月日），如果认为最后一列还可以再分成（出生年，出生月，出生日），它就不是一范式了，否则就是.

第二范式(2NF)

2NF是对记录的惟一性，要求记录有惟一标识，即实体的惟一性，即不存在部分依赖；

非主属性完全依赖于主关键字

表：学号、课程号、姓名、学分;

这个表明显说明了两个事务:学生信息, 课程信息;由于非主键字段必须依赖主键，这里学分依赖课程号，姓名依赖与学号，所以不符合二范式。

正确做法: 学生：Student(学号, 姓名)；课程：Course(课程号, 学分)；选课关系：StudentCourse(学号, 课程号, 成绩)。

不满足第二范式可能存在的问题：

数据冗余:，每条记录都含有相同信息；
删除异常：删除所有学生成绩，就把课程信息全删除了；
插入异常：学生未选课，无法记录进数据库；
更新异常：调整课程学分，所有行都调整。

第三范式(3NF)

3NF是对字段的冗余性，要求任何字段不能由其他字段派生出来，它要求字段没有冗余，即不存在传递依赖；

表: 学号, 姓名, 年龄, 学院名称, 学院电话

因为存在依赖传递: (学号) → (学生)→(所在学院) → (学院电话)

可能会存在问题：

数据冗余:有重复值;
更新异常：有重复的冗余信息，修改时需要同时修改多条记录，否则会出现数据不一致的情况 .

正确做法：

学生：(学号, 姓名, 年龄, 所在学院) 学院：(学院, 电话)

范式化设计和反范式化设计的优缺点

范式化

优点: 可以尽量减小数据冗余, 更新操作快,表体积更小缺点: 查询需要对多个表进行关联,导致性能降低; 更难进行索引优化

反范式化

优点: 减少表的关联; 更好的进行索引优化缺点: 存在数据库冗余及数据维护异常; 对数据的修改需要更多成本

C语言

文件操作

FILE *fopen(const char *filename, const char *mode);

fprintf函数是否会覆盖所有，取决于fopen时是采用什么方式

fopen(file , "r") ; 读方式打开，写会报错！
fopen(file , "w") ; 写方式打开，整个文件会被直接重新写，以前文件的数据全丢失。
fopen( file , "a" ); 追加方式打开，写入数据时，是追加到文件尾，不会影响原文件中的数据
fopen( file ,"r+");
"r+" "a+" "w+" 等方式打开为读写模式，这时，写数据前，要先定位文件指针，如果想改动文件中的内容，则写入的数据长度与要覆盖的数据长度要一致才可以，不然会造成数据覆盖或数据完整性错误！

int fclose(FILE *fp)

若成功执行了关闭操作，放回值为0；非0，表示关闭时有错误

int fgetc(FILE *fp);

从分配读一个字符，将位置指针指向下一个字符
若读成功，则返回该字符

若读到文件尾或者读取错误，则返回EOF

#include <stdio.h>
#include <stdlib.h>

int main() {
    FILE *fp;
    int ch;
    if ((fp = fopen("demo.txt", "r")) == NULL) {
        printf("Failure to open demo.txt! \n");
        exit(0);
    }

    while ((ch = fgetc(fp)) != EOF) {
        putchar(ch);
    }
    fclose(fp);
    return 0;
}

int fputc(int c, FILE *fp);

向fp输出字符c
若写入错误，则返回EOF,否则返回c

feof()

函数 feof() 检查是否能达到文件尾，返回非0值，否则返回0值

按块读写数据

size_t fread(void *buffer, size_t size, size_t count, FILE *stream)

从fp所指文件中读取数据块存到 buffer 指向的内存

buffer 是存储数据块的内存首地址，如数组的地址

num = fread(a, sizeof char, n, fp); //n个块，每个块占1字节

size_t fwrite(const void *buffer, size_t size, size_t count, FILE *stream)

将buffer指向的内存中的数据块写入fp所指的文件
返回值：实际写入数据块个数，应等于count,除非出现写入错误

位运算

1、补码

在总结按位运算前，有必要先介绍下补码的知识，我们知道当将一个十进制正整数转换为二进制数的时候，只需要通过除2取余的方法即可，但是怎么将一个十进制的负整数转换为二进制数呢？其实，负数是以补码的形式表示：先按正数转换，然后取反加1。

要将十进制的-10用二进制表示，先将10用二进制表示：
0000 0000 0000 1010
取反：
1111 1111 1111 0101
加1：
1111 1111 1111 0110
所以，-10的二进制表示就是：1111 1111 1111 0110`

2、按位与(&)

参加运算的两个数，换算为二进制(0、1)后，进行与运算。只有当相应位上的数都是1时，该位才取1，否则该位为0。

将10与-10进行按位与(&)运算：
0000 0000 0000 1010
1111 1111 1111 0110
-----------------------
0000 0000 0000 0010
所以：10 & -10 = 0000 0000 0000 0010`

3、按位或(|)

参加运算的两个数，换算为二进制(0、1)后，进行或运算。只要相应位上存在1，那么该位就取1，均不为1，即为0。

将10与-10进行按位或(|)运算：
0000 0000 0000 1010
1111 1111 1111 0110
-----------------------
1111 1111 1111 1110
所以：10 | -10 = 1111 1111 1111 1110`

4、按位异或(^)

参加运算的两个数，换算为二进制(0、1)后，进行异或运算。只有当相应位上的数字不相同时，该为才取1，若相同，即为0。

将10与-10进行按位异或(^)运算：
0000 0000 0000 1010
1111 1111 1111 0110
-----------------------
1111 1111 1111 1100
所以：10 ^ -10 = 1111 1111 1111 1100`

可以看出，任何数与0异或，结果都是其本身。利用异或还可以实现一个很好的交换算法，用于交换两个数，算法如下：

a = a ^ b;
b = b ^ a;
a = a ^ b;

5、取反(~)

参加运算的两个数，换算为二进制(0、1)后，进行取反运算。每个位上都取相反值，1变成0，0变成1。

对10进行取反(~)运算：
0000 0000 0000 1010
---------------------
1111 1111 1111 0101
所以：~10 = 1111 1111 1111 0101

转义字符

所有的ASCII码都可以用“\”加数字（一般是8进制数字）来表示。而C中定义了一些字母前加"\"来表示常见的那些不能显示的ASCII字符，如\0,\t,\n等，就称为转义字符，因为后面的字符，都不是它本来的ASCII字符意思了。
32～126(共95个)是字符(32是空格），其中48～57为0到9十个阿拉伯数字。
65～90为26个大写英文字母，97～122号为26个小写英文字母

static

注意：静态局部变量，在函数里定义，就只能在这个函数里使用，同一个文档中的其他函数也是用不了的。

#include <stdio.h>
#include <iostream>
using namespace std;

int a = 5;
void f() {
    static int a = 10;
    a++;
    cout << "static:" << a << endl;
}

int main() {
    cout << a << endl;
    f();
    f();
    f();
    cout << a << endl;
}

//------------------输出：
5
static:11
static:12
static:13
5