C｜数据存储地址与字节偏移、数据索引
话说C是面向内存的编程语言。数据要能存得进去，取得出来，且要考虑效率。不管是顺序存储还是链式存储，其寻址方式总是很重要。顺序存储是连续存储。同质结构的数组通过其索引表示位置偏移，异质结构的结构体通过其成员名（字段名）的类型大小及对齐方式来计算字节偏移。链式存储通过一个额外的指针（地址）作为数据成员来指示其相邻节点的地址信息。
1 数组以数组名和索引提供对数据元素的引用
数组是对同质元素的连续存储，是许多结构数据结构的基础。
int i = 0;
int j = 0;
int a[12] = {0};
a[i] = 1; //a[i]相当于a+i，编译器维护a的元素的类型信息，偏移i个元素长度
int b[3][5] = {0};
b[i][j] = 1; //b[i][j] 相当于*(*(b+i)+j)，编译器维护b的元素及元素的类型信息，
// 偏移i个元素长度，j个元素的元素的长度
内数组名与运算符“&”、“sizeof”被编译器解释为整个数组，其它情况被解释为指针（一个指向数组首元素的地址），这是为将数组名用做函数实参准备的语法机制：
int arr[i][j][k][……];
int (*arp)[j][k][……] = arr; //利用arp做形参，便可以传递arr做实参
// 函数体内对指针参数的解引用便是对指针指向对象的操作
void foo(int (*arp)[j][k][……], int i)// 便可在函数体内用做左值或右值
{
*(*(*(*(arp+i)+j)+k)+……); //注意arp的类型是int[j][k][……],arp+i时便可以获得正常的偏移
}
C语言对于数组引用不进行任何边界检查。
对于局部数组，函数的局部变量和状态信息（例如保存的寄存器值和返回地址）都存放在栈中。这两种情况结合到一起就能导致严重的栈错误，对越界的数组元素的写操作会破坏存储在栈中的状态信息（向低地址区溢出）。当程序使用这个被破坏的状态，试图重新加载寄存器或执行ret指令时，就会出现很严重的错误。
一种特别常见的状态破坏称为缓冲区溢出（buffer overflow）。
对于全局数组，其溢出操作同样有不可预见的后果。
2 结构体利用结构体变量名和成员对象名提供地址偏移来访问元素
C语言的struct声明创建一个数据类型，将可能不同类型的对象聚合到一个对象中。用名字来引用结构的各个组成部分。类似于数组的实现，结构的所有组成部分都存放在内存中一段连续的区域内，而指向结构的指针就是结构第一个字节的地址。编译器维护关于每个结构类型的信息，指示每个字段（fileld）的字节偏移。以这些偏移作为内存引用指令中的位移，从而产生对结构元素的引用。
void foo()
{
struct Stru{
char ch; // ch要对齐到s，否则s需要两次读取
short s; // s要对齐到i，否则i需要两次读取
int i; // i要对齐到d，否则i需要两次读取
double d;
}; // 结构体整体也要对齐到一个字长
Stru stru;
printf("%dn",sizeof(stru)); // 16
printf("%dn",int(&stru.i)-int(&stru)); // 4
}
结构体偏移时会考虑内存对齐，以实现更好的引用效率（避免更多次的引用，因为CPU会一次读取一个字长长度的数据（sizeof(int)或sizeofof(void*)）。
如果将更大的数据类型靠前放则可以减少对后续元素读取的影响，从而节省内存空间：
代码示例：
void foo()
{
struct S4{
char c; // c要对齐到i，否则i需要两次读取
int i; // i要对齐到d，否则i需要两次读取
char d;
}s4; // 结构体整体也要对齐到一个字长
printf("%dn",sizeof(s4)); // 12
printf("%dn",int(&s4.i)-int(&s4)); // 4
struct S5{
int i;
char c;
char d;
}s5; // 结构体整体也要对齐到一个字长
printf("%dn",sizeof(s5)); // 8
printf("%dn",int(&s5.c)-int(&s5)); // 4
}
3 switch可以被编译器实现对case语句的直接跳转
编译器比你想象的要聪明，不但要做翻译，还要做优化。例如，你写的switch语句可能会被优化为 jump table，还会消除无用的语句(Dead code elimination)等，汇编代码有时候不仅仅是C代码的直译，也就是说，编译器可以执行不同程度的优化。
switch语句可以根据一个整数索引值进行多重分支。通过使用跳转表（jump table）可以实现较高的效率。跳转表是一个数组，表项 i 是一个代码段的地址，这个代码段实现当开关索引值等于 i 时程序应该采取的动作。程序代码用开关索引值来执行一个跳转表内的数组引用，确定跳转指令的目标。和使用一组很长的if else语句相比，使用跳转表的优点是执行开关语句的时间与开关情况的数量无关。编译器根据开关情况的数量和开关情况值的稀疏程度来翻译开关语句。当开关情况数量比较多（如4个以上），并且值的范围跨度比较小时，就会使用跳转表。
看if与switch的代码比较：
#include <stdio.h>
bool IsLeapYear(int y) // 判断是否为闰年
{
return((y%4==0&&y%100!=0)||y%400==0);
}
int DaysOfMonth(int month,int year) // 判断某月天数的函数
{
switch(month){
case 1:
case 3:
case 5:
case 7:
case 8:
case 10:
case 12:return 31;
case 4:
case 6:
case 9:
case 11:return 30;
case 2:if(IsLeapYear(year))
return 29;
else
return 28;
}
return 0;
}
int DaysOfMonth2(int month,int year) // 判断某月天数的函数
{
if(month==2)
{
if(IsLeapYear(year))
return 29;
else
return 28;
}
else if(month==4 || month == 6 || month == 9 || month == 11)
return 30;
else
return 31;
}
int main()
{
for(int i=0;i<12;i++)
printf("%d ",DaysOfMonth2(i+1,2021));
getchar();
return 0;
}
switch汇编：
9: switch(month){
004010C8 mov eax,dword ptr [ebp+8]
004010CB mov dword ptr [ebp-4],eax
004010CE mov ecx,dword ptr [ebp-4]
004010D1 sub ecx,1
004010D4 mov dword ptr [ebp-4],ecx
004010D7 cmp dword ptr [ebp-4],0Bh
004010DB ja $L538+23h (00401118)
004010DD mov edx,dword ptr [ebp-4]
004010E0 jmp dword ptr [edx*4+40112Bh]
10: case 1:
11: case 3:
12: case 5:
13: case 7:
14: case 8:
15: case 10:
16: case 12:return 31;
004010E7 mov eax,1Fh
004010EC jmp $L538+25h (0040111a)
17: case 4:
18: case 6:
19: case 9:
20: case 11:return 30;
004010EE mov eax,1Eh
004010F3 jmp $L538+25h (0040111a)
21: case 2:if(IsLeapYear(year))
004010F5 mov eax,dword ptr [ebp+0Ch]
004010F8 push eax
004010F9 call @ILT+5(IsLeapYear) (0040100a)
004010FE add esp,4
00401101 and eax,0FFh
00401106 test eax,eax
00401108 je $L538+1Ch (00401111)
22: return 29;
0040110A mov eax,1Dh
0040110F jmp $L538+25h (0040111a)
23: else
24: return 28;
00401111 mov eax,1Ch
00401116 jmp $L538+25h (0040111a)
25: }
26: return 0;
00401118 xor eax,eax
27: }
else if 汇编：
30: if(month==2)
004011A8 cmp dword ptr [ebp+8],2
004011AC jne DaysOfMonth2+41h (004011d1)
31: {
32: if(IsLeapYear(year))
004011AE mov eax,dword ptr [ebp+0Ch]
004011B1 push eax
004011B2 call @ILT+5(IsLeapYear) (0040100a)
004011B7 add esp,4
004011BA and eax,0FFh
004011BF test eax,eax
004011C1 je DaysOfMonth2+3Ah (004011ca)
33: return 29;
004011C3 mov eax,1Dh
004011C8 jmp DaysOfMonth2+65h (004011f5)
34: else
35: return 28;
004011CA mov eax,1Ch
004011CF jmp DaysOfMonth2+65h (004011f5)
36: }
37: else if(month==4 || month == 6 || month == 9 || month == 11)
004011D1 cmp dword ptr [ebp+8],4
004011D5 je DaysOfMonth2+59h (004011e9)
004011D7 cmp dword ptr [ebp+8],6
004011DB je DaysOfMonth2+59h (004011e9)
004011DD cmp dword ptr [ebp+8],9
004011E1 je DaysOfMonth2+59h (004011e9)
004011E3 cmp dword ptr [ebp+8],0Bh
004011E7 jne DaysOfMonth2+60h (004011f0)
38: return 30;
004011E9 mov eax,1Eh
004011EE jmp DaysOfMonth2+65h (004011f5)
39: else
40: return 31;
004011F0 mov eax,1Fh
41:
42: }
4 hash表的最好情况可以实现到数据的直接映射
哈希表是维护字典的一种非常实用的方法。他们利用了这样一个事实，即一旦有了索引(index)，在数组中查找一个元素需要常数时间。散列函数是一种将键（key）映射到整数的数学函数。我们将使用散列函数的值作为数组的索引（将元素的键值映射为下标），并将元素存储在该位置。
使用这样一种称为散列(hash)的策略可以非常有效地实现映射(map)，在这种策略中，键(key)被转换为一个整数，该整数决定了实现(implementation)应该在哪里查找结果。
hasing算法的一个常见实现是分配一个动态的bucket数组，每个bucket都包含一个指向该bucket的键的链表。只要条目数与存储桶数的比率不超过0.7左右，get和put方法的平均运行时间为O(1)。
下标与地址相关，让关键字也让地址相关，这就是hash，但key与下标或索引相比，包含的信息更多。
常用的hash函数种类：
4.1 除留余数法
最简单的哈希算法是将数据除以某一个常数后取余数来当索引。
h(key) = key mod b
// 哈希法的存储与查找，核心在于如何将数据的存储位置映射为数组的下标
#if 0
#include <IOStream>
using namespace std;
/*
下面这段代码是典型的用空间换时间的算法，数据与存储其所占空间的下标完全相同。
下面这段代码不具有任何的实用性，但充分说明了这种思路。
*/
int search(int h[], int key);
void store(int h[], int data);
int main()
{
int data[1000]={0};
int m, n;
for (int i = 0; i < 6; i++)
{
cin>>n;
store(data, n);
}
cin>>m;
int result = search(data, m);
if (result)
cout<<"在数组中找到." <<endl;
else
cout<<"没有此数据!"<<endl;
return 0;
}
int search(int d[], int key)
{
return d[key];
}
void store(int d[], int n)
{
d[n]=n;
}
#else
//下面是采用哈希法存储数据并实现查找的示例。
//实现哈希函数用“除法取余法”，解决冲突为“开放地址法”。
#include <iostream>
using namespace std;
int searchHash(int h[], int len, int key);
void insertHash(int h[], int len, int data);
int main()
{
const int hashLength = 13; //哈希表长度
int hashTable[hashLength]={0};
int m, n;
//创建hash
for (int i = 0; i < 6; i++)
{
cout<<"请输入第"<<i<<"个值（共6个）：";
cin>>n;
insertHash(hashTable, hashLength, n);
}
cout<<"请输入需要查找的值：";
cin>>m;
int result = searchHash(hashTable,hashLength, m);
if (result != -1)
cout<<"已经在数组中找到，位置为：" << result<<endl;
else
cout<<"没有此原始"<<endl;
getchar();
return 0;
}
int searchHash(int h[], int len, int key)
{
int hashAddress = key % len; // 哈希函数
// 指定hashAdrress对应值存在但不是关键值，则用开放寻址法解决
while (h[hashAddress] != 0 && h[hashAddress] != key)
{
hashAddress = (++hashAddress) % len;
}
// 查找到了开放单元，表示查找失败
if (h[hashAddress] == 0)
return -1;
return hashAddress;
}
void insertHash(int h[], int len, int data) // 数据插入Hash表
{
int hashAddress = data % len; // 哈希函数
// 如果key存在，则说明已经被别人占用，此时必须解决冲突
while (h[hashAddress] != 0)
{
// 用开放寻址法找到
hashAddress = (++hashAddress) % len;
}
// 将data存入字典中
h[hashAddress] = data;
}
#endif
4.2 平方取中法
先计算数据的平方，然后取中间的某段数字做为索引。
4.3 折叠法
将数据转换成一串数字后，先将这串数字拆成几个部分，然后把它们加起来。
STL中的set的底层为什么用红黑树，而不是哈希表？
集合的常见运算有并、交、差等，这些运算在数据有序时对应算法的时间复杂度会大大降低，红黑树恰好是有序结构，而哈希表不是。
5 共用体只是一种字节共享（或特殊的类型泛化或类型强制转换）
联合能够规避C语言的类型系统，允许以多种类型来引用对象，用不同的字段来引用相同的内存块。与结构体不同的是，其成员不存在位移，两个字段的使用是互斥的，一个共用体总的大小等于它最大字段的大小。
void cngb()
{
union{
struct {
unsigned int i:4;
unsigned int j:4;
unsigned int k:4;
unsigned int L:4;
unsigned int m:4;
unsigned int n:4;
};
char hanzi[3];
}hz;
fflush(stdin);
puts("查询gb2312码，请输入一个汉字：");
gets(hz.hanzi);
//strcpy(hz.hanzi,"中");
printf("%X%X%X%Xn",hz.j,hz.i,hz.L,hz.k);
//for(int i=0;i<2;i++)
//printf("%2Xn",hz.hanzi[i]);
}
6 位域可以实现比字节长度颗粒度更小的偏移
要将一个浮点数的二进制存储用16进制的符号表示出来，使用字节的颗粒还是太大，因为一个16进制是4个二进制位，半个字节长度，可以使用位域：
#include <stdio.h>
#include <string>
using namespace std;
string double2hex(double db)
{
union { //用于将浮点数的二进制位解析为int位输出
float input;
int output;
} data;
union {
struct {
unsigned j:4;
unsigned i:4;
}by;
char ch;
}un;
char *hexa = "0123456789ABCDEF";
int i=0;
int j=0;
char *ch = (char*)&db;
string hexd = "";
for(i=7;i>=0;i--)
{
un.ch = ch[i];
hexd += hexa[un.by.i];
hexd += hexa[un.by.j];
hexd += " ";
}
return hexd;
}
int main()
{
string str = double2hex(-15.525);
printf("%sn",str.c_str()); // C0 2F 0C CC CC CC CC CD
getchar();
return 0;
}
7 索引表以空间换时间缩小搜索范围提高搜索效率
将大范围的数据建立索引，通过查找索引来确定数据的位置是一个提高查找效率的策略。
给数据建立索引也是利用数据在文件中的偏移量。
#include <iostream> // 建立索引表并排序
#include <fstream>
#include <cstdlib>
using namespace std;
typedef struct
{
int NO;
char name[8];
int chinese;
int math;
int english;
int Comprehensive;
int total;
} Student; //高考学生信息
typedef struct
{
int NO;
long offset; //数据在文件中的偏移量
} StudentIndex; //高考学生索引
void createIndex();
void writeIndex(StudentIndex *si, int n);
int main()
{
createIndex();
return 0;
}
/*
功能：创建索引
*/
void createIndex()
{
int stuNum;
StudentIndex *studentsIndex; //索引表的起始地址
Student student;
ifstream binaryFile("binarydata.dat", ios::in|ios::binary);
if(!binaryFile)
{
cerr<<"cannot open binary file!"<<endl;
exit(1);
}
//建立索引
binaryFile.read((char*)&stuNum, sizeof(stuNum)); //读入实际人数
//读入数据，建立未排序的索引表
studentsIndex = new StudentIndex[stuNum];
int i, j;
long mOffset;
for(i=0; i<stuNum; ++i)
{
mOffset = binaryFile.tellg();
binaryFile.read((char*)&student, sizeof(Student));
studentsIndex[i].NO = student.NO;
studentsIndex[i].offset = mOffset; //记录对应学号学生数据的偏移量
}
//关闭数据文件
binaryFile.close();
//为索引表排序
StudentIndex temp; //用于交换的中间变量
for (i=0; i<stuNum-1; i++)
for(j=0; j<stuNum-i-1; j++)
if (studentsIndex[j].NO>studentsIndex[j+1].NO)
{
temp=studentsIndex[j];
studentsIndex[j]=studentsIndex[j+1];
studentsIndex[j+1]=temp;
}
//将建好的索引表通过文件存储
writeIndex(studentsIndex, stuNum);
return;
}
/*
功能：将索引写入文件
参数：si - 索引表起始地址；n - 考生人数，索引记录条数
*/
void writeIndex(StudentIndex *si, int n)
{
//打开文件
ofstream indexFile("binarydata.idx", ios::out|ios::binary);
if(!indexFile)
{
cerr<<"cannot open index file!"<<endl;
exit(1);
}
int i;
for(i=0; i<n; ++i)
{
//indexFile<<si[i].NO<<"t"<<si[i].offset<<endl; //索引用作文本文件时
indexFile.write((char*)&si[i], sizeof(StudentIndex)); //索引用二进制文件时
}
//关闭文件
indexFile.close();
return;
}
－End－
