話說(shuō)C是面向內(nèi)存的編程語(yǔ)言。數(shù)據(jù)要能存得進(jìn)去，取得出來(lái)，且要考慮效率。不管是順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)，其尋址方式總是很重要。順序存儲(chǔ)是連續(xù)存儲(chǔ)。同質(zhì)結(jié)構(gòu)的數(shù)組通過(guò)其索引表示位置偏移，異質(zhì)結(jié)構(gòu)的結(jié)構(gòu)體通過(guò)其成員名（字段名）的類型大小及對(duì)齊方式來(lái)計(jì)算字節(jié)偏移。鏈?zhǔn)酱鎯?chǔ)通過(guò)一個(gè)額外的指針（地址）作為數(shù)據(jù)成員來(lái)指示其相鄰節(jié)點(diǎn)的地址信息。
1 數(shù)組以數(shù)組名和索引提供對(duì)數(shù)據(jù)元素的引用
數(shù)組是對(duì)同質(zhì)元素的連續(xù)存儲(chǔ)，是許多結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。
int i = 0;
int j = 0;
int a[12] = {0};
a[i] = 1; //a[i]相當(dāng)于a+i，編譯器維護(hù)a的元素的類型信息，偏移i個(gè)元素長(zhǎng)度
int b[3][5] = {0};
b[i][j] = 1; //b[i][j] 相當(dāng)于*(*(b+i)+j)，編譯器維護(hù)b的元素及元素的類型信息，
// 偏移i個(gè)元素長(zhǎng)度，j個(gè)元素的元素的長(zhǎng)度
內(nèi)數(shù)組名與運(yùn)算符“&”、“sizeof”被編譯器解釋為整個(gè)數(shù)組，其它情況被解釋為指針（一個(gè)指向數(shù)組首元素的地址），這是為將數(shù)組名用做函數(shù)實(shí)參準(zhǔn)備的語(yǔ)法機(jī)制：
int arr[i][j][k][……];
int (*arp)[j][k][……] = arr; //利用arp做形參，便可以傳遞arr做實(shí)參
// 函數(shù)體內(nèi)對(duì)指針參數(shù)的解引用便是對(duì)指針指向?qū)ο蟮牟僮?void foo(int (*arp)[j][k][……], int i)// 便可在函數(shù)體內(nèi)用做左值或右值
{
*(*(*(*(arp+i)+j)+k)+……); //注意arp的類型是int[j][k][……],arp+i時(shí)便可以獲得正常的偏移
}
C語(yǔ)言對(duì)于數(shù)組引用不進(jìn)行任何邊界檢查。
對(duì)于局部數(shù)組，函數(shù)的局部變量和狀態(tài)信息（例如保存的寄存器值和返回地址）都存放在棧中。這兩種情況結(jié)合到一起就能導(dǎo)致嚴(yán)重的棧錯(cuò)誤，對(duì)越界的數(shù)組元素的寫操作會(huì)破壞存儲(chǔ)在棧中的狀態(tài)信息（向低地址區(qū)溢出）。當(dāng)程序使用這個(gè)被破壞的狀態(tài)，試圖重新加載寄存器或執(zhí)行ret指令時(shí)，就會(huì)出現(xiàn)很嚴(yán)重的錯(cuò)誤。
一種特別常見(jiàn)的狀態(tài)破壞稱為緩沖區(qū)溢出（buffer overflow）。
對(duì)于全局?jǐn)?shù)組，其溢出操作同樣有不可預(yù)見(jiàn)的后果。
2 結(jié)構(gòu)體利用結(jié)構(gòu)體變量名和成員對(duì)象名提供地址偏移來(lái)訪問(wèn)元素
C語(yǔ)言的struct聲明創(chuàng)建一個(gè)數(shù)據(jù)類型，將可能不同類型的對(duì)象聚合到一個(gè)對(duì)象中。用名字來(lái)引用結(jié)構(gòu)的各個(gè)組成部分。類似于數(shù)組的實(shí)現(xiàn)，結(jié)構(gòu)的所有組成部分都存放在內(nèi)存中一段連續(xù)的區(qū)域內(nèi)，而指向結(jié)構(gòu)的指針就是結(jié)構(gòu)第一個(gè)字節(jié)的地址。編譯器維護(hù)關(guān)于每個(gè)結(jié)構(gòu)類型的信息，指示每個(gè)字段（fileld）的字節(jié)偏移。以這些偏移作為內(nèi)存引用指令中的位移，從而產(chǎn)生對(duì)結(jié)構(gòu)元素的引用。
void foo()
{
struct Stru{
char ch; // ch要對(duì)齊到s，否則s需要兩次讀取
short s; // s要對(duì)齊到i，否則i需要兩次讀取
int i; // i要對(duì)齊到d，否則i需要兩次讀取
double d;
}; // 結(jié)構(gòu)體整體也要對(duì)齊到一個(gè)字長(zhǎng)
Stru stru;
printf("%dn",sizeof(stru)); // 16
printf("%dn",int(&stru.i)-int(&stru)); // 4
}
結(jié)構(gòu)體偏移時(shí)會(huì)考慮內(nèi)存對(duì)齊，以實(shí)現(xiàn)更好的引用效率（避免更多次的引用，因?yàn)镃PU會(huì)一次讀取一個(gè)字長(zhǎng)長(zhǎng)度的數(shù)據(jù)（sizeof(int)或sizeofof(void*)）。
如果將更大的數(shù)據(jù)類型靠前放則可以減少對(duì)后續(xù)元素讀取的影響，從而節(jié)省內(nèi)存空間：
代碼示例：
void foo()
{
struct S4{
char c; // c要對(duì)齊到i，否則i需要兩次讀取
int i; // i要對(duì)齊到d，否則i需要兩次讀取
char d;
}s4; // 結(jié)構(gòu)體整體也要對(duì)齊到一個(gè)字長(zhǎng)
printf("%dn",sizeof(s4)); // 12
printf("%dn",int(&s4.i)-int(&s4)); // 4
struct S5{
int i;
char c;
char d;
}s5; // 結(jié)構(gòu)體整體也要對(duì)齊到一個(gè)字長(zhǎng)
printf("%dn",sizeof(s5)); // 8
printf("%dn",int(&s5.c)-int(&s5)); // 4
}
3 switch可以被編譯器實(shí)現(xiàn)對(duì)case語(yǔ)句的直接跳轉(zhuǎn)
編譯器比你想象的要聰明，不但要做翻譯，還要做優(yōu)化。例如，你寫的switch語(yǔ)句可能會(huì)被優(yōu)化為 jump table，還會(huì)消除無(wú)用的語(yǔ)句(Dead code elimination)等，匯編代碼有時(shí)候不僅僅是C代碼的直譯，也就是說(shuō)，編譯器可以執(zhí)行不同程度的優(yōu)化。
switch語(yǔ)句可以根據(jù)一個(gè)整數(shù)索引值進(jìn)行多重分支。通過(guò)使用跳轉(zhuǎn)表（jump table）可以實(shí)現(xiàn)較高的效率。跳轉(zhuǎn)表是一個(gè)數(shù)組，表項(xiàng) i 是一個(gè)代碼段的地址，這個(gè)代碼段實(shí)現(xiàn)當(dāng)開(kāi)關(guān)索引值等于 i 時(shí)程序應(yīng)該采取的動(dòng)作。程序代碼用開(kāi)關(guān)索引值來(lái)執(zhí)行一個(gè)跳轉(zhuǎn)表內(nèi)的數(shù)組引用，確定跳轉(zhuǎn)指令的目標(biāo)。和使用一組很長(zhǎng)的if else語(yǔ)句相比，使用跳轉(zhuǎn)表的優(yōu)點(diǎn)是執(zhí)行開(kāi)關(guān)語(yǔ)句的時(shí)間與開(kāi)關(guān)情況的數(shù)量無(wú)關(guān)。編譯器根據(jù)開(kāi)關(guān)情況的數(shù)量和開(kāi)關(guān)情況值的稀疏程度來(lái)翻譯開(kāi)關(guān)語(yǔ)句。當(dāng)開(kāi)關(guān)情況數(shù)量比較多（如4個(gè)以上），并且值的范圍跨度比較小時(shí)，就會(huì)使用跳轉(zhuǎn)表。
看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) // 判斷某月天數(shù)的函數(shù)
{
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) // 判斷某月天數(shù)的函數(shù)
{
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表的最好情況可以實(shí)現(xiàn)到數(shù)據(jù)的直接映射
哈希表是維護(hù)字典的一種非常實(shí)用的方法。他們利用了這樣一個(gè)事實(shí)，即一旦有了索引(index)，在數(shù)組中查找一個(gè)元素需要常數(shù)時(shí)間。散列函數(shù)是一種將鍵（key）映射到整數(shù)的數(shù)學(xué)函數(shù)。我們將使用散列函數(shù)的值作為數(shù)組的索引（將元素的鍵值映射為下標(biāo)），并將元素存儲(chǔ)在該位置。
使用這樣一種稱為散列(hash)的策略可以非常有效地實(shí)現(xiàn)映射(map)，在這種策略中，鍵(key)被轉(zhuǎn)換為一個(gè)整數(shù)，該整數(shù)決定了實(shí)現(xiàn)(implementation)應(yīng)該在哪里查找結(jié)果。
hasing算法的一個(gè)常見(jiàn)實(shí)現(xiàn)是分配一個(gè)動(dòng)態(tài)的bucket數(shù)組，每個(gè)bucket都包含一個(gè)指向該bucket的鍵的鏈表。只要條目數(shù)與存儲(chǔ)桶數(shù)的比率不超過(guò)0.7左右，get和put方法的平均運(yùn)行時(shí)間為O(1)。
下標(biāo)與地址相關(guān)，讓關(guān)鍵字也讓地址相關(guān)，這就是hash，但key與下標(biāo)或索引相比，包含的信息更多。
常用的hash函數(shù)種類：
4.1 除留余數(shù)法
最簡(jiǎn)單的哈希算法是將數(shù)據(jù)除以某一個(gè)常數(shù)后取余數(shù)來(lái)當(dāng)索引。
h(key) = key mod b
// 哈希法的存儲(chǔ)與查找，核心在于如何將數(shù)據(jù)的存儲(chǔ)位置映射為數(shù)組的下標(biāo)
#if 0
#include <IOStream>
using namespace std;
/*
下面這段代碼是典型的用空間換時(shí)間的算法，數(shù)據(jù)與存儲(chǔ)其所占空間的下標(biāo)完全相同。
下面這段代碼不具有任何的實(shí)用性，但充分說(shuō)明了這種思路。
*/
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<<"在數(shù)組中找到." <<endl;
else
cout<<"沒(méi)有此數(shù)據(jù)!"<<endl;
return 0;
}
int search(int d[], int key)
{
return d[key];
}
void store(int d[], int n)
{
d[n]=n;
}
#else
//下面是采用哈希法存儲(chǔ)數(shù)據(jù)并實(shí)現(xiàn)查找的示例。
//實(shí)現(xiàn)哈希函數(shù)用“除法取余法”，解決沖突為“開(kāi)放地址法”。
#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; //哈希表長(zhǎng)度
int hashTable[hashLength]={0};
int m, n;
//創(chuàng)建hash
for (int i = 0; i < 6; i++)
{
cout<<"請(qǐng)輸入第"<<i<<"個(gè)值（共6個(gè)）：";
cin>>n;
insertHash(hashTable, hashLength, n);
}
cout<<"請(qǐng)輸入需要查找的值：";
cin>>m;
int result = searchHash(hashTable,hashLength, m);
if (result != -1)
cout<<"已經(jīng)在數(shù)組中找到，位置為：" << result<<endl;
else
cout<<"沒(méi)有此原始"<<endl;
getchar();
return 0;
}
int searchHash(int h[], int len, int key)
{
int hashAddress = key % len; // 哈希函數(shù)
// 指定hashAdrress對(duì)應(yīng)值存在但不是關(guān)鍵值，則用開(kāi)放尋址法解決
while (h[hashAddress] != 0 && h[hashAddress] != key)
{
hashAddress = (++hashAddress) % len;
}
// 查找到了開(kāi)放單元，表示查找失敗
if (h[hashAddress] == 0)
return -1;
return hashAddress;
}
void insertHash(int h[], int len, int data) // 數(shù)據(jù)插入Hash表
{
int hashAddress = data % len; // 哈希函數(shù)
// 如果key存在，則說(shuō)明已經(jīng)被別人占用，此時(shí)必須解決沖突
while (h[hashAddress] != 0)
{
// 用開(kāi)放尋址法找到
hashAddress = (++hashAddress) % len;
}
// 將data存入字典中
h[hashAddress] = data;
}
#endif
4.2 平方取中法
先計(jì)算數(shù)據(jù)的平方，然后取中間的某段數(shù)字做為索引。
4.3 折疊法
將數(shù)據(jù)轉(zhuǎn)換成一串?dāng)?shù)字后，先將這串?dāng)?shù)字拆成幾個(gè)部分，然后把它們加起來(lái)。
STL中的set的底層為什么用紅黑樹，而不是哈希表？
集合的常見(jiàn)運(yùn)算有并、交、差等，這些運(yùn)算在數(shù)據(jù)有序時(shí)對(duì)應(yīng)算法的時(shí)間復(fù)雜度會(huì)大大降低，紅黑樹恰好是有序結(jié)構(gòu)，而哈希表不是。
5 共用體只是一種字節(jié)共享（或特殊的類型泛化或類型強(qiáng)制轉(zhuǎn)換）
聯(lián)合能夠規(guī)避C語(yǔ)言的類型系統(tǒng)，允許以多種類型來(lái)引用對(duì)象，用不同的字段來(lái)引用相同的內(nèi)存塊。與結(jié)構(gòu)體不同的是，其成員不存在位移，兩個(gè)字段的使用是互斥的，一個(gè)共用體總的大小等于它最大字段的大小。
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碼，請(qǐng)輸入一個(gè)漢字：");
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 位域可以實(shí)現(xiàn)比字節(jié)長(zhǎng)度顆粒度更小的偏移
要將一個(gè)浮點(diǎn)數(shù)的二進(jìn)制存儲(chǔ)用16進(jìn)制的符號(hào)表示出來(lái)，使用字節(jié)的顆粒還是太大，因?yàn)橐粋€(gè)16進(jìn)制是4個(gè)二進(jìn)制位，半個(gè)字節(jié)長(zhǎng)度，可以使用位域：
#include <stdio.h>
#include <string>
using namespace std;
string double2hex(double db)
{
union { //用于將浮點(diǎn)數(shù)的二進(jìn)制位解析為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 索引表以空間換時(shí)間縮小搜索范圍提高搜索效率
將大范圍的數(shù)據(jù)建立索引，通過(guò)查找索引來(lái)確定數(shù)據(jù)的位置是一個(gè)提高查找效率的策略。
給數(shù)據(jù)建立索引也是利用數(shù)據(jù)在文件中的偏移量。
#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; //高考學(xué)生信息
typedef struct
{
int NO;
long offset; //數(shù)據(jù)在文件中的偏移量
} StudentIndex; //高考學(xué)生索引
void createIndex();
void writeIndex(StudentIndex *si, int n);
int main()
{
createIndex();
return 0;
}
/*
功能：創(chuàng)建索引
*/
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)); //讀入實(shí)際人數(shù)
//讀入數(shù)據(jù)，建立未排序的索引表
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; //記錄對(duì)應(yīng)學(xué)號(hào)學(xué)生數(shù)據(jù)的偏移量
}
//關(guān)閉數(shù)據(jù)文件
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;
}
//將建好的索引表通過(guò)文件存儲(chǔ)
writeIndex(studentsIndex, stuNum);
return;
}
/*
功能：將索引寫入文件
參數(shù)：si - 索引表起始地址；n - 考生人數(shù)，索引記錄條數(shù)
*/
void writeIndex(StudentIndex *si, int n)
{
//打開(kāi)文件
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; //索引用作文本文件時(shí)
indexFile.write((char*)&si[i], sizeof(StudentIndex)); //索引用二進(jìn)制文件時(shí)
}
//關(guān)閉文件
indexFile.close();
return;
}
－End－
