話說C是面向內(nèi)存的編程語言。數(shù)據(jù)要能存得進(jìn)去，取得出來，且要考慮效率。不管是順序存儲還是鏈?zhǔn)酱鎯?，其尋址方式總是很重要。順序存儲是連續(xù)存儲。同質(zhì)結(jié)構(gòu)的數(shù)組通過其索引表示位置偏移，異質(zhì)結(jié)構(gòu)的結(jié)構(gòu)體通過其成員名（字段名）的類型大小及對齊方式來計算字節(jié)偏移。鏈?zhǔn)酱鎯νㄟ^一個額外的指針（地址）作為數(shù)據(jù)成員來指示其相鄰節(jié)點的地址信息。

1 數(shù)組以數(shù)組名和索引提供對數(shù)據(jù)元素的引用

數(shù)組是對同質(zhì)元素的連續(xù)存儲，是許多結(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個元素長度
    int b[3][5] = {0};
    b[i][j] = 1; //b[i][j] 相當(dāng)于*(*(b+i)+j)，編譯器維護(hù)b的元素及元素的類型信息，
                  // 偏移i個元素長度，j個元素的元素的長度

內(nèi)數(shù)組名與運(yùn)算符“&”、“sizeof”被編譯器解釋為整個數(shù)組，其它情況被解釋為指針（一個指向數(shù)組首元素的地址），這是為將數(shù)組名用做函數(shù)實參準(zhǔn)備的語法機(jī)制：

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ù)組引用不進(jìn)行任何邊界檢查。

對于局部數(shù)組，函數(shù)的局部變量和狀態(tài)信息（例如保存的寄存器值和返回地址）都存放在棧中。這兩種情況結(jié)合到一起就能導(dǎo)致嚴(yán)重的棧錯誤，對越界的數(shù)組元素的寫操作會破壞存儲在棧中的狀態(tài)信息（向低地址區(qū)溢出）。當(dāng)程序使用這個被破壞的狀態(tài)，試圖重新加載寄存器或執(zhí)行ret指令時，就會出現(xiàn)很嚴(yán)重的錯誤。

一種特別常見的狀態(tài)破壞稱為緩沖區(qū)溢出（buffer overflow）。

對于全局?jǐn)?shù)組，其溢出操作同樣有不可預(yù)見的后果。

2 結(jié)構(gòu)體利用結(jié)構(gòu)體變量名和成員對象名提供地址偏移來訪問元素

C語言的struct聲明創(chuàng)建一個數(shù)據(jù)類型，將可能不同類型的對象聚合到一個對象中。用名字來引用結(jié)構(gòu)的各個組成部分。類似于數(shù)組的實現(xiàn)，結(jié)構(gòu)的所有組成部分都存放在內(nèi)存中一段連續(xù)的區(qū)域內(nèi)，而指向結(jié)構(gòu)的指針就是結(jié)構(gòu)第一個字節(jié)的地址。編譯器維護(hù)關(guān)于每個結(jié)構(gòu)類型的信息，指示每個字段（fileld）的字節(jié)偏移。以這些偏移作為內(nèi)存引用指令中的位移，從而產(chǎn)生對結(jié)構(gòu)元素的引用。

void foo()
{
    struct Stru{
        char ch;    // ch要對齊到s，否則s需要兩次讀取
        short s;    // s要對齊到i，否則i需要兩次讀取
        int i;      // i要對齊到d，否則i需要兩次讀取
        double d;
    };              // 結(jié)構(gòu)體整體也要對齊到一個字長
    Stru stru;
    printf("%dn",sizeof(stru)); // 16
    printf("%dn",int(&stru.i)-int(&stru)); // 4
}

結(jié)構(gòu)體偏移時會考慮內(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;           // 結(jié)構(gòu)體整體也要對齊到一個字長
    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)體整體也要對齊到一個字長
    printf("%dn",sizeof(s5)); // 8
    printf("%dn",int(&s5.c)-int(&s5)); // 4
}

3 switch可以被編譯器實現(xiàn)對case語句的直接跳轉(zhuǎn)

編譯器比你想象的要聰明，不但要做翻譯，還要做優(yōu)化。例如，你寫的switch語句可能會被優(yōu)化為 jump table，還會消除無用的語句(Dead code elimination)等，匯編代碼有時候不僅僅是C代碼的直譯，也就是說，編譯器可以執(zhí)行不同程度的優(yōu)化。

switch語句可以根據(jù)一個整數(shù)索引值進(jìn)行多重分支。通過使用跳轉(zhuǎn)表（jump table）可以實現(xiàn)較高的效率。跳轉(zhuǎn)表是一個數(shù)組，表項 i 是一個代碼段的地址，這個代碼段實現(xiàn)當(dāng)開關(guān)索引值等于 i 時程序應(yīng)該采取的動作。程序代碼用開關(guān)索引值來執(zhí)行一個跳轉(zhuǎn)表內(nèi)的數(shù)組引用，確定跳轉(zhuǎn)指令的目標(biāo)。和使用一組很長的if else語句相比，使用跳轉(zhuǎn)表的優(yōu)點是執(zhí)行開關(guān)語句的時間與開關(guān)情況的數(shù)量無關(guān)。編譯器根據(jù)開關(guān)情況的數(shù)量和開關(guān)情況值的稀疏程度來翻譯開關(guān)語句。當(dāng)開關(guān)情況數(shù)量比較多（如4個以上），并且值的范圍跨度比較小時，就會使用跳轉(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表的最好情況可以實現(xiàn)到數(shù)據(jù)的直接映射

哈希表是維護(hù)字典的一種非常實用的方法。他們利用了這樣一個事實，即一旦有了索引(index)，在數(shù)組中查找一個元素需要常數(shù)時間。散列函數(shù)是一種將鍵（key）映射到整數(shù)的數(shù)學(xué)函數(shù)。我們將使用散列函數(shù)的值作為數(shù)組的索引（將元素的鍵值映射為下標(biāo)），并將元素存儲在該位置。

使用這樣一種稱為散列(hash)的策略可以非常有效地實現(xiàn)映射(map)，在這種策略中，鍵(key)被轉(zhuǎn)換為一個整數(shù)，該整數(shù)決定了實現(xiàn)(implementation)應(yīng)該在哪里查找結(jié)果。

hasing算法的一個常見實現(xiàn)是分配一個動態(tài)的bucket數(shù)組，每個bucket都包含一個指向該bucket的鍵的鏈表。只要條目數(shù)與存儲桶數(shù)的比率不超過0.7左右，get和put方法的平均運(yùn)行時間為O(1)。

下標(biāo)與地址相關(guān)，讓關(guān)鍵字也讓地址相關(guān)，這就是hash，但key與下標(biāo)或索引相比，包含的信息更多。

常用的hash函數(shù)種類：

4.1 除留余數(shù)法

最簡單的哈希算法是將數(shù)據(jù)除以某一個常數(shù)后取余數(shù)來當(dāng)索引。

h(key) = key mod b

// 哈希法的存儲與查找，核心在于如何將數(shù)據(jù)的存儲位置映射為數(shù)組的下標(biāo)
#if 0

#include <IOStream>
using namespace std;

/*
下面這段代碼是典型的用空間換時間的算法，數(shù)據(jù)與存儲其所占空間的下標(biāo)完全相同。
下面這段代碼不具有任何的實用性，但充分說明了這種思路。
*/
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對應(yīng)值存在但不是關(guān)鍵值，則用開放尋址法解決
    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ù)轉(zhuǎn)換成一串?dāng)?shù)字后，先將這串?dāng)?shù)字拆成幾個部分，然后把它們加起來。

STL中的set的底層為什么用紅黑樹，而不是哈希表？

集合的常見運(yùn)算有并、交、差等，這些運(yùn)算在數(shù)據(jù)有序時對應(yīng)算法的時間復(fù)雜度會大大降低，紅黑樹恰好是有序結(jié)構(gòu)，而哈希表不是。

5 共用體只是一種字節(jié)共享（或特殊的類型泛化或類型強(qiáng)制轉(zhuǎn)換）

聯(lián)合能夠規(guī)避C語言的類型系統(tǒng)，允許以多種類型來引用對象，用不同的字段來引用相同的內(nèi)存塊。與結(jié)構(gòu)體不同的是，其成員不存在位移，兩個字段的使用是互斥的，一個共用體總的大小等于它最大字段的大小。

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ù)的二進(jìn)制存儲用16進(jìn)制的符號表示出來，使用字節(jié)的顆粒還是太大，因為一個16進(jìn)制是4個二進(jìn)制位，半個字節(jié)長度，可以使用位域：

#include <stdio.h>
#include <string>
using namespace std;

string double2hex(double db)
{
    union {         //用于將浮點數(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ù)據(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;          //高考學(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ù)據(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;      //記錄對應(yīng)學(xué)號學(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;
            }
                                                //將建好的索引表通過文件存儲
    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)); //索引用二進(jìn)制文件時  
    }
    //關(guān)閉文件
    indexFile.close();
    return;
}

－End－