INTERVIEW 1

数据对齐存储

在32位系统中：int占4Bytes，short占2Bytes，char占1Byte，加起来应该是7Bytes，但是下面这段代码输出却是8。

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <cstdio>

using namespace std;

struct Node {
    int x;
    short y;
    char c;
};

int main()
{
    printf("%d\n", sizeof(Node));

    return 0;
}

计算机对于基本类型数据在内存中的存/储位置有些限制，即内存对齐。 处理器取数据一般不按照单个字节，而是双字节、四字节等进行，假设这种存取粒度为4Bytes，也就是说处理器只能从首地址为4的倍数的地址读取数据。如果没有对齐存储，取数据会很麻烦，可能需要两次读取并且剔除掉无用的字节。 每个编译器都有默认的对齐模数，那么有效对齐值=min{对齐模数，结构体中最长数据类型长度}。 规则1：第一个成员offset为0，其后成员的offset=min{有效对齐值，该类型字节数}； 规则2：结构体总大小必须为有效对齐值的整数倍，否则编译器会自动填充。 再看前面的例子，int占0_{3，short占4}5，char占6，总长度为7，不是4的整数倍，所以地址7是填充字节，共8Bytes。

栈 & 堆（不是数据结构中的栈和堆）

1. 内存栈区 编译器自动进行分配和释放，存放局部变量、函数的参数等。 Windows下栈向低地址扩展，大小只有几MB，如果开一个很大的局部数组，就会提示stack overflow。
2. 内存堆区 malloc或者new返回的内存区域，使用完需要用户free或delete，否则容易内存泄漏。如果程序员不释放，那么结束时由操作系统回收。 堆向高地址扩展，由于系统采用空闲链表存储空闲内存，所以是不连续的。系统在收到内存申请的请求后，会由低地址向高地址遍历空闲链表，找到第一个满足的空闲块，删除该结点，并将该块的首地址返回。如果分配的空间大于申请的，会将剩余部分重新链接回空闲链表。

   //在Heap中开辟10Bytes，同时在Stack中压入p，p的值为10Bytes的首地址
   char* p = new char[10];

3. 常数区 存放字符串常量等，程序结束由系统回收。
4. 静态区 存放全局变量或者静态变量，初始化的和没有初始化的分别存放在不同的区域，程序结束后由系统释放。
5. 代码区 存放程序代码。 ## 其它 排序复杂度、人工智能概念、模型的建立等。