啰嗦幾句

我本來(lái)想說(shuō)的是Unix系統(tǒng)C標(biāo)準(zhǔn)庫(kù)所提供的一些算法和數(shù)據(jù)結(jié)構(gòu)API，但畢竟帶有iOS標(biāo)題可能更加吸引眼球一些。其實(shí)我說(shuō)的也沒(méi)有錯(cuò)，因?yàn)閕OS畢竟是從Unix衍生出來(lái)的系統(tǒng)，所以說(shuō)標(biāo)題所述也算是正確的。下面將要介紹的幾類API，有些可以在POSIX平臺(tái)中支持，有些則只能在FreeBSD中支持，有些則只有在iOS系統(tǒng)中單獨(dú)支持。

iOS系統(tǒng)中的C標(biāo)準(zhǔn)庫(kù)中主要提供了線性查找、二分查找、雙向鏈表、快速排序、堆排序、歸并排序、并行排序、基數(shù)排序、二叉排序樹(shù)、哈希表、KV數(shù)據(jù)庫(kù)、位串、內(nèi)存池、cache等眾多的API。這些API基本覆蓋了在應(yīng)用中的常見(jiàn)數(shù)據(jù)結(jié)構(gòu)和算法的需求。

那既然Foundation和CoreFoundation庫(kù)中都提供了眾多的基于OC語(yǔ)言的算法和數(shù)據(jù)結(jié)構(gòu)為什么還要使用這些函數(shù)呢？原因就是性能和兼容性。

??線性查找

功能：遍歷數(shù)組，查找滿足條件的記錄。
頭文件：#include <search.h>
平臺(tái)：POSIX
函數(shù)簽名：

//查找
void *lfind(const void *key, const void *base, size_t *nelp, size_t width, int (*compar)(const void *, const void *));
//查找并追加
void *lsearch(const void *key, void *base, size_t *nelp, size_t width, int (*compar)(const void *, const void *));

參數(shù)：
key: [in] 要查找的元素。
base:[in] 數(shù)組元素的首地址。
nelp: [in/out] 數(shù)組的元素個(gè)數(shù)指針。
width: [in] 數(shù)組中每個(gè)元素的尺寸。
compar: [in] 函數(shù)比較器，查找時(shí)會(huì)對(duì)數(shù)組中的每個(gè)元素進(jìn)行遍歷并和要查找的元素調(diào)用函數(shù)比較器來(lái)判斷是否匹配成功。函數(shù)比較器的格式如下：

/*
@key: 是要查找的元素，也是上面lfind和lsearch中傳入的第一個(gè)參數(shù)key。
@element: 元素在數(shù)組中的地址，這里需要注意的是這個(gè)參數(shù)不是元素本身，而是元素所在的數(shù)組中的偏移地址。
@return: 如果比較結(jié)果相等則返回0，否則返回非0
*/
 int compar(const void *key, const void *element);

return:[out] 如果數(shù)組中找到了對(duì)應(yīng)的元素，則返回元素在數(shù)組中的地址，如果沒(méi)有找到則lfind返回NULL。而lsearch則會(huì)將要查找的元素追加到數(shù)組后面，并返回元素在數(shù)組中的地址，同時(shí)更新nelp的值。

描述：
系統(tǒng)提供的lfind和lsearch函數(shù)都是用于線性查找，但是二者的區(qū)別是:

1. lsearch中的key必須和數(shù)組的元素是相同的數(shù)據(jù)類型，而lfind則沒(méi)有這個(gè)要求。
2. 因?yàn)閘search函數(shù)在查找不到時(shí)會(huì)將key的內(nèi)容拷貝(memcpy)到數(shù)組的尾部，因此lsearch除了具有查找外還有添加數(shù)組元素的能力，而且數(shù)組的容量應(yīng)該要大于nelp參數(shù)中所指定的數(shù)組的元素個(gè)數(shù)，否則就有可能產(chǎn)生異常。同時(shí)在函數(shù)返回后nelp中保存的將是最終數(shù)組中實(shí)際的元素個(gè)數(shù)，這也是為什么nelp要以指針的形式進(jìn)行傳遞。而lfind則只是查找并不會(huì)追加。

lsearch也有可能在查找添加失敗時(shí)返回NULL。

示例代碼:

typedef struct student
{
    int age;
    char *name;
} student_t;

//注意這里的key的類型可以不和數(shù)組元素類型相同，同時(shí)第二個(gè)參數(shù)是元素在數(shù)組中的指針而不是元素本身。
int lfindcompar(const char *key, const student_t *pstudent)
{
    return strcmp(key, pstudent->name);
}

//注意這里的key的類型必須要和數(shù)組元素類型相同，同時(shí)第二個(gè)參數(shù)是元素在數(shù)組中的指針而不是元素本身。
int lsearchcompar(const  student_t *key, const student_t *pstudent)
{
    return strcmp(key->name, pstudent->name);
}

void main()
{
    student_t students[10] = {{10, "Bob"}, {20, "Alex"}, {15, "Lucy"}, {19, "Ada"}, {25, "Max"}};
    size_t  count = 5;  // 實(shí)際的元素個(gè)數(shù)為5

    //lfind第一次查找沒(méi)有找到
    student_t *pstudent = lfind("Lily", students, &count, sizeof(student_t), &lfindcompar);
    NSAssert(pstudent == NULL, @"oops");  //沒(méi)有找到。

    
    student_t newstudent = {20, "Lily"};
    //lsearch中的key的類型必須要和數(shù)組元素類型保持一致，如果沒(méi)有找到就會(huì)添加到數(shù)組尾部，并且數(shù)量參數(shù)count會(huì)加1
    pstudent = lsearch(&newstudent, students, &count, sizeof(student_t), &lsearchcompar);
    NSAssert(pstudent != NULL && count == 6, @"oops");

    //再次通過(guò)lfind就查找成功了。
    pstudent = lfind("Lily", students, &count, sizeof(student_t), &lfindcompar);
    NSAssert(pstudent != NULL, @"oops");
}

??二分查找

功能：對(duì)有序數(shù)組進(jìn)行二分查找，并查找滿足條件的記錄，二分查找法的時(shí)間復(fù)雜度為logN。
頭文件：#include <stdlib.h>
平臺(tái)：POSIX
函數(shù)簽名：

void *bsearch(const void *key, const void *base, size_t nel, size_t width, int (*compar) (const void *, const void *));
//bsearch_b并不是POSIX標(biāo)準(zhǔn)中的函數(shù)，而是iOS對(duì)二分查找的block形式的擴(kuò)展
void *bsearch_b(const void *key, const void *base, size_t nel, size_t width, int (^compar) (const void *, const void *));

參數(shù)：
key: [in] 要查找的元素。
base:[in] 數(shù)組元素的首地址。
nel: [in] 數(shù)組的元素個(gè)數(shù)。
width: [in] 數(shù)組中每個(gè)元素的尺寸。
compar: [in] 函數(shù)比較器，查找時(shí)會(huì)對(duì)數(shù)組的某些元素和要查找的元素調(diào)用函數(shù)比較器來(lái)判斷是否匹配成功。函數(shù)比較器的格式如下

/*
@key: 是要查找的元素，也是上面bsearch和bsearch_b中傳入的第一個(gè)參數(shù)key。
@element: 元素在數(shù)組中的地址，這里需要注意的是這個(gè)參數(shù)不是元素本身，而是元素所在的數(shù)組中的偏移地址。
@return : 如果比較結(jié)果相等則返回0, 如果key小于element則返回小于0，如果key大于element則返回大于0
*/
 int compar(const void *key, const void *element);

return：如果找到則返回元素在數(shù)組中的指針，如果沒(méi)有找到則返回NULL。

描述：
函數(shù)要求數(shù)組必須是有序的，至于是升序還是降序則跟函數(shù)比較器的返回是相關(guān)的。默認(rèn)的情況是按升序進(jìn)行二分查找的。bsearch_b和bsearch的區(qū)別是前者是block的形式的比較器，而后者則是函數(shù)形式的比較器，block形式的比較器功能更加強(qiáng)大一些。

示例代碼:

int bsearchcompar(const int *key, const student_t *pstudent)
{
    return *key - pstudent->age;
}

void main()
{
   student_t students[5] = {{10, "Bob"}, {20, "Alex"}, {30, "Lucy"}, {40, "Ada"}, {50, "Max"}};

   int age = 30;  //查找的關(guān)鍵字
   student_t *pstudent = bsearch(&age, students, sizeof(students)/sizeof(student_t), sizeof(student_t), &bsearchcompar);
   NSAssert(pstudent != NULL && pstudent->age == 30);

}

下一篇：iOS標(biāo)準(zhǔn)庫(kù)中常用數(shù)據(jù)結(jié)構(gòu)和算法之鏈表

歡迎大家訪問(wèn)歐陽(yáng)大哥2013的github地址和簡(jiǎn)書(shū)地址