数据结构与算法分析
上一次修改时间：2016-07-27 17:39:19

C语言

  1. 原码表示法在数值前面增加了一个符号位(正数为0，负数为1)，原码不能直接参与运算，因为在计算负数的运算时可能会出错；例如数学上，1+(-1)=0，而在二进制中，00000001+10000001=10000010，换算成十进制为-2；原码的符号位不能直接参与运算，必须和其他位分开，但会增加硬件的开销和复杂性；

  2. 反码：正数的反码与其原码相同；负数的反码是对其原码逐位取反，但符号位除外。例如：原码10010= 反码11101 （10010，1为符号码，故为负）；

  3. 补码：正数的补码与其原码相同；负数的补码是在其反码的末位加1。在计算机系统中，数值一律用补码来表示和存储。原因在于，使用补码，可以将符号位和数值域统一处理；同时，加法和减法也可以统一处理。此外，补码与原码相互转换，其运算过程是相同的，不需要额外的硬件电路。

  4. 计算机的硬件结构中只有加法器，所以大部分的运算都必须最终转换为加法；32位系统中，模为2^32；在以12模的系统中，加8和减4效果是一样的，因此凡是减4运算，都可以用加8来代替。对“模”而言，8和4互为补数。实际上以12模的系统中，11和1，10和2，9和3，7和5，6和6都有这个特性。共同的特点是两者相加等于模。

  5. 负数的补码与原码的和为模；对一个数求补，逻辑过程是对这个数的所有的二进制位按位取反再加1。现实含义是求出这个数对应的负数形式。

  6. 数0的补码表示是唯一的。[+0]补=[+0]反=[+0]原=00000000，[ -0]补=11111111+1=00000000；

  7. 8位二进制小数，用原码或反码表示时，取值范围为[-127, +127], 而使用补码表示的范围为[-128, 127]。[1111 1111]为-127的原码，[1000 0000]规定为-128的原码；

  8. 因为机器使用补码, 所以对于编程中常用到的32位int类型, 可以表示范围是: [-231, 231-1] 因为第一位表示的是符号位.而使用补码表示时又可以多保存一个最小值；

  9. 带符号的整数中，除出符号位外的值为真值；

    计算举例：

    -7 - 11；-7的补码为[1111 1001],-11的补码为[1111 0101]，相加后为[1110 1110]，将相加后的补码再进行一次补码，即转换成原码，并去掉溢出的最位为[1001 0010]，即十进制的-18；

    19 -53；19的原码，补码为[0001 0011],-53的补码为[1100 1011],相加后为[1101 1110]，对应的原码为[1010 0010],即十进制的 -34；

    73 -51；73的原码、补码为[0100 1001],-51的补码为[1100 1101]，相加后并去掉溢出的最高位为[0001 0110]，即十进制的22；

    总结：用补码相加后的结果也是补码，相加的结果必须转换成原码；规则同补码，即正数的原码为补码本身，负数的原码为补码的补码；

  10. 堆内存和栈内存的区别

    1）内存分配的算法不一样；

    2）以压栈出栈的方式分配的内存就是栈内存；

    3）以堆排序方式分配的内存就是堆内存；

    4）程序中函数的调用是靠压栈出栈实现的；

  11. $a = new a();a对象存放在堆中，变量$a保存了a对象的内存地址；

  12. 内存的地址编号是从0开始的非负整数(如8G内存的地址为:0-----8G-1),cup操作内存时主要靠三根主线，1根为地址线，即要操作的内存地址，1根为控制线，即控制操作是读、写，1根为数据线，即cpu处理完的数据；在32位的cpu中，控制线是32位的，因此32位的cpu能访问的内存大小为2的32次方，即4G,再大的内存不能被访问;

  13. 编程语言如c中的变量必须初始化后才能使用，操作系统回收程序使用过的内存后不会清空内存，编程语言中的变量如不初始化再使用的话，有可以会取到上一个程序留下来的值；

  14. c中int占四个字节，double占八个字节；

  15. 类和结构体一样都属于数据类型，结构体定义时大括号后面一定要写一个分号，结构体属于一种复合数据类型，里面可以定义多个成员变量，但不能像类一样定义方法；

  16. 结构体定义示例

  17. # include <stdio.h>
# include <string.h>

struct student{
    int sid;
    char name[20];
    int age;
};

int main(void)
{
    struct student std1 = {1000, "piqiu",23 };
    struct student std2;
    std2.sid = 1001;
    //std2.name = "pikaqiu"; 结构体中不能这样给字符串赋值
    strcpy(std2.name, "pikaqiu");
    std2.age =  22;
    struct student * pst = &std2;
    char test[10] = "abc";

    printf("%d---%s---%d\n",std1.sid, std1.name, std1.age);
    printf("%d---%s---%d\n",std2.sid, std2.name, std2.age);
    printf("%s\n", test);

    pst->sid = 10002;
    strcpy(pst->name, "leiqiu");
    pst->age = 22;
    printf("%d---%s---%d\n",std2.sid, std2.name, std2.age );
}
  18. [pikaqiu@bogon c]$ gcc -o test1 test.c
[pikaqiu@bogon c]$ ./test1
1000---piqiu---23
1001---pikaqiu---22
abc
10002---leiqiu---22

  19. 如上例中，当指针变量调用结构体下的成员时需用->，如果结构体变量本身调用成员变量时需用.符号；

  20. 整数是以补码的形式转换为二进制代码存储在计算机中的，浮点数是以 ieee754 标准转换为二进制代码存储在计算机中的。字符的本质实际也是与整数的存储方式相同。

  21. 内存中存储的最小单位是字节，但是硬件控制的时候不能精确到位，只能精确到字节，是通过地址总线来控制的，而精确到位是通过软件来控制的，叫做位运算符来精确到位的。

  22. Ascll 码规定了 ch 是以那个值去保存，ascii 码不是一个值，而是一种规定，规定了不同的字符是以那个整数值去表示。

  23. printf函数用法

    QQ图片20160605150833.png

    QQ图片20160605150833.png

  24. printf函数打印结果时，必须用双引号，用单引号时会有语法错误；

  25. 定义变量为NULL时，必须大写，小写会被解析成函数；

  26. 双引号里面是字符串，单引号里面的代表字符；函数实参必须用双引号传递字符串，否则会报错；如：fopen("./001.txt","r");

  27. NULL的值就是'\0'，即十进制的0，而字符'0'的十进制值是48；

  28. 在C语言的宏中，"##"被称为 连接符（concatenator），它是一种预处理运算符， 用来把两个语言符号(Token)组合成单个语言符号。

  29. "#"是一种预处理运算符，它的功能是将其后面的宏参数进行 字符串化操作 ， 简单说就是在对它所引用的宏变量通过替换后在其左右各加上一个双引号， 用比较官方的话说就是将语言符号(Token)转化为字符串。

  30. 0x80000000为32位int的最大值；

  31. 1