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