数据结构

• 内存空间划分

  • 一个进程启动后，会生成4G的内存空间

  • 0~3G是用户空间(应用层) 3~4G是内核空间(底层)

    • 0~3G

    • 3~4G

  • 所有的进程都会共享3G~4G的内核空间， 但是每个进程会独立拥有0~3G的用户空间。

  • 栈区

    • 存放数据特点

      • 栈区存放数据的申请空间的先后顺序：从大到小

      • 先进后出，后进先出（电梯）（未优化前）

        • int a； -> &a = 0x01 int b； -> &b = 0x00

  • 堆区

    • 存放数据特点

      • 先进先出，后进后出（排队）

      • 栈区存放数据的申请空间的先后顺序：从小到大

        • int a； -> &a = 0x00 int b； -> &b = 0x01

• 动态内存分配和回收

  • malloc

    • 格式

      • void *malloc(size_t size)

        • 使用时需强转为其他基本数据类型

        • size为需要申请空间的字节大小， 以字节为单位，可以借助sizeof()

      • int *p = (int *)malloc(sizeof(int) * n)

        • 在堆区获取n个4字节大小的空间，并将首地址赋值给p

  • free

    • 格式

      • void free(void *p)

        • p为获取内存的起始地址

      • free(int *p)

        • 释放p为首地址的堆区内存

  • 野指针

    • 未初始化或已经释放的，并没有置空的指针。

      • 定义指针，未初始化就直接使用

      • 使用指针申请了堆区空间，而堆区空间已经释放，指针没有重新指向，成为野指针

      • 使用指针指向数组，可以通过指针遍历数组里的元素，如果越界访问成为野指针。

• 传址，传值，值返回，址返回

  • 左值

    • 可以放在等号左边和右边，有地址空间 比如：变量，堆区空间

  • 右值

    • 只能放在等号的右边，没有地址空间， 比如：常量、临时值、表达式结果

  • 传值

    • 将变量或者数据作为函数的实参传递给形参，形参的改变，一定不影响实参，因为只是将实参的数据复制一份给形参。根本原因：存储地址不同

  • 传址

    • 将变量或者数据的地址作为函数的实参传递给形参，形参的改变，可能会影响实参，具体看代码

      • (*p)++

        • 对地址p存储的值进行自增

          • 改变主函数的实参

      • *p++

        • 取值后对地址自增

  • 返值

    • 一个函数返回一个数据（值返回），返回结果为常量，只能为右值

  • 返址

    • 一个函数返回一个数据的地址(地址返回) 返回的数据生命周期够长，返回结果就可以为左值

• const

  • 该变量不可被改变，只读变量，常变量

  • const 修饰的全局变量，在静态区的.ro段，const修饰局部变量，存在栈区。

  • const修饰的变量，一定要初始化。

    • 因为cosnt修饰的值不可变，故而不能对其进行赋值操作

  • const修饰整型

    • int a = 10;

    • const int b = 20; // == int const b = 20;

    • 不可使用未被const修饰的指针指向常量

      • 否则会报错

  • const 和指针

    • 如果想保存常变量地址的话，就需要对指针加以限制

    • int * const p;

      • 表示指针的指向不可变，指向里的值可变。

    • int const *p;

      • 表示指针指向里的值不可变，指向可变。

    • int const * const p;

      • 都不可变

• typedef

  • 概念

    • 将数据类型重新起个名字，目的是将代码简化

  • 格式

    • typedef 数据类型 新名

    • typedef int * P

      • 将数据类型int * 重定义为P

      • P p; == int *p;

  • 已有数据类型

    • 用已有类型定义变量

      • int a; //定义一个整型变量

      • int *ptr; //定义一个整型指针

      • int arr[5]; //定义一个数组

      • int *p[5]; //定义一个指针数组

      • int (*p2)[3]; //定义一个数组指针

      • int (*fun)(int,int); //定义一个函数指针

      • int **ptr2; //定义一个二级指针

    • 提取类型

      • int

        • 整型

      • int *

        • 整型指针

      • int [5]

        • 整型数组

      • int *[5]

        • 整型指针数组

      • int (*)[5]

        • 整型数组指针

      • int (*)()

        • 函数指针

      • int **

        • 二级指针

    • 用已有类型重定义

      • typedef int A

      • typedef int *A

      • typedef int A[]

      • typedef int *A[]

      • typedef int (*A)[]

      • typedef int **A

• define

  • 概念

    • 是一种预处理指令，用来定义常量、函数、循环等。

    • 宏就是个常量，宏只做替换，不做计算，不做正确性的检查。

      • 不运算直接原样传过去

    • 在C语言中，宏的定义和输出不用格式符%s,而是直接使用宏本身作为标识符，主要原因，在预处理就是做个简单的替换，而不是在运行时执行函数调用。

  • 格式

    • #define 宏名 宏体

      • 将宏体定义为宏名

    • #define N10

      • 预处理时将程序中的宏名N替换为宏体10

  • 带参宏

    • #define max(x,y) x>y?x:y

      • int a = max(++x,y)

  • 条件编译

    • 判断宏是否成立

      • #if 条件 printf(); #else printf(); #endif

    • 判断宏是否存在

      • #ifdef 宏名 printf(); #else printf(); #endif

      • #ifndef 宏名 printf(); #else printf(); #endif

• struct

  • 概念

    • 结构体是一种用户自定义的数据类型，用于存储相同或者不同的数据的构造数据类型

  • 格式

    • struct + 结构名 ｛ 数据类型 成员1； 数据类型 成员2； ··· 数据类型 成员n； ｝；

      • 给结构体中的成员赋值

        • s1.name = “张三”；

          • 数组只能在初始化时整体赋值

          • 其他情况需要使用strcpy（s2.name, "李四"） 或gets（）

      • 间接初始化和赋值

        • 先定义结构体类型，然后在主函数内进行初始化或赋值

          • struct student s1；

      • 直接初始化和赋值

        • 在定义结构体类型的同时，将变量直接放在结构体类型后面进行定义

          • 直接初始化，可以省略结构名， 省略后不可在结构体外定义结构体变量

          • 若省略结构名，将只能使用已有的结构体变量，

      • 初始化

        • 按顺序初始化

          • struct student s1 = ｛“jack”，1001，21｝；

          • 数据和结构体内的数据类型一一对应

        • 不按顺序初始化

          • struct studen s2= ｛.id = 1002, .age = 22, .name = "Tom"｝

            • 通过引出结构体内部的成员进行赋值操作，

    • 注意事项

      • struct 定义结构体的关键字

      • ｛｝不可省略

      • 结构名要符合命名规则，可以省略

      • 成员的数据类型可以是基本类型也可以是构造数据类型

      • 结构体中的成员个数任意，根据代码进行设计

      • 结构体的声明可以放在任意位置，但是一般放在头文件中

      • 定义结构体类型时不占用空间，使用结构体变量时需要申请空间

  • 结构体数组

    • 数组

      • 一次性定义多个数据类型相同的变量

    • 一次性定义多个类型相同的结构体变量

      • 间接初始化结构体数组

      • 直接初始化结构体数组

  • 结构体指针

    • 结构体指针，用来存储结构体变量的地址

    • 子主题 2

  • 嵌套结构体

    • c语言不支持在一个结构体里嵌套另一个结构体 ，只有编译器优化后才可

    • 嵌套的结构体需要一层一层访问

      • T1.s2.a

  • 结构体的大小

    • 结构体的大小满足字节对齐的原则

      • 可以提高处理效率

      • 保证每一次都能取出完整的数据

    • 字节对齐规则

      • 结构体的每一个成员变量的存储位置（相对于结构体中第一个成员的偏移量），必须对齐在其整数倍上

      • 结构体整体的大小，必须是最大对齐成员对齐量的整数倍

      • 成员对齐量=成员本身的大小>操作系统的对齐量？操作系统的对齐量：成员本身的大小 (操作系统的对齐量：32位默认4Byte对齐，64位默认8Byte对齐)

  • 带位域的结构体对齐

• 共用体/联合体

  • union

    • 格式

      • union 共用体名 ｛ 数据类型 成员1； 数据类型 成员2； ··· 数据类型 成员n； ｝；

    • 特点

      • 一个成员发生修改，另一个成员也跟着修改

    • 取值赋值初始化和结构体类似

    • 共用体大小仍然满足对齐规则

      • 若全成员全为基本类型数据类型 那么共用体就和基本数据类型中最大的成员的大小一致

      • 若共用体中有构造类型的成员，那么共用体的大小需要满足，是共用体中最大基本类型成员的整数倍

• 枚举

  • 基本数据类型

    • 枚举项的值为整型常量，之间用空格隔开

    • 未初始化则从零开始，间隔为1

  • 格式

    • enum 枚举名 ｛ 枚举项1， 枚举项2， ··· 枚举项n ｝；

      • 枚举项可以直接拿来用，不需要有枚举变量

      • 枚举项默认有值，第一个枚举项从零开始，依次递增1

      • 若中间某个项赋值了，则后面的枚举项值从这个数开始依次递增1

      • 枚举变量也可直接给变量（包括枚举变量）赋值，相当于一个常量

      • 枚举变量也可使用常量赋值，但是会失去枚举的意义，建议枚举变量直接使用枚举项赋值

  • 枚举项的使用

    • 可以直接当成变量使用，也可使用枚举项给枚举变量赋值，但枚举项不可在枚举外赋值

  • 应用场景

    • 作为函数的参数传递

    • 枚举常和switch ·· case 语句联合使用