iOS标准库中常用数据结构和算法之查找

啰嗦几句

我本来想说的是Unix系统C标准库所提供的一些算法和数据结构API，但毕竟带有iOS标题可能更加吸引眼球一些。其实我说的也没有错，因为iOS毕竟是从Unix衍生出来的系统，所以说标题所述也算是正确的。下面将要介绍的几类API，有些可以在POSIX平台中支持，有些则只能在FreeBSD中支持，有些则只有在iOS系统中单独支持。

iOS系统中的C标准库中主要提供了线性查找、二分查找、双向链表、快速排序、堆排序、归并排序、并行排序、基数排序、二叉排序树、哈希表、KV数据库、位串、内存池、cache等众多的API。这些API基本覆盖了在应用中的常见数据结构和算法的需求。

那既然Foundation和CoreFoundation库中都提供了众多的基于OC语言的算法和数据结构为什么还要使用这些函数呢？原因就是性能和兼容性。

线性查找

功能：遍历数组，查找满足条件的记录。

头文件：#include <search.h>

平台：POSIX

函数签名：

//查找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 *));复制代码

参数：

key: [in] 要查找的元素。

base:[in] 数组元素的首地址。

nelp: [in/out] 数组的元素个数指针。

width: [in] 数组中每个元素的尺寸。

compar: [in] 函数比较器，查找时会对数组中的每个元素进行遍历并和要查找的元素调用函数比较器来判断是否匹配成功。函数比较器的格式如下：

/*@key: 是要查找的元素，也是上面lfind和lsearch中传入的第一个参数key。@element: 元素在数组中的地址，这里需要注意的是这个参数不是元素本身，而是元素所在的数组中的偏移地址。@return: 如果比较结果相等则返回0，否则返回非0*/ int compar(const void *key, const void *element);复制代码

return:[out] 如果数组中找到了对应的元素，则返回元素在数组中的地址，如果没有找到则lfind返回NULL。而lsearch则会将要查找的元素追加到数组后面，并返回元素在数组中的地址，同时更新nelp的值。

描述：

系统提供的lfind和lsearch函数都是用于线性查找，但是二者的区别是:

lsearch中的key必须和数组的元素是相同的数据类型，而lfind则没有这个要求。因为lsearch函数在查找不到时会将key的内容拷贝(memcpy)到数组的尾部，因此lsearch除了具有查找外还有添加数组元素的能力，而且数组的容量应该要大于nelp参数中所指定的数组的元素个数，否则就有可能产生异常。同时在函数返回后nelp中保存的将是最终数组中实际的元素个数，这也是为什么nelp要以指针的形式进行传递。而lfind则只是查找并不会追加。

lsearch也有可能在查找添加失败时返回NULL。

示例代码:

typedef struct student{ int age; char *name;} student_t;//注意这里的key的类型可以不和数组元素类型相同，同时第二个参数是元素在数组中的指针而不是元素本身。int lfindcompar(const char *key, const student_t *pstudent){ return strcmp(key, pstudent->name);}//注意这里的key的类型必须要和数组元素类型相同，同时第二个参数是元素在数组中的指针而不是元素本身。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; // 实际的元素个数为5 //lfind第一次查找没有找到 student_t *pstudent = lfind("Lily", students, &count, sizeof(student_t), &lfindcompar); NSAssert(pstudent == NULL, @"oops"); //没有找到。  student_t newstudent = {20, "Lily"}; //lsearch中的key的类型必须要和数组元素类型保持一致，如果没有找到就会添加到数组尾部，并且数量参数count会加1 pstudent = lsearch(&newstudent, students, &count, sizeof(student_t), &lsearchcompar); NSAssert(pstudent != NULL && count == 6, @"oops"); //再次通过lfind就查找成功了。 pstudent = lfind("Lily", students, &count, sizeof(student_t), &lfindcompar); NSAssert(pstudent != NULL, @"oops");}复制代码

二分查找

功能：对有序数组进行二分查找，并查找满足条件的记录，二分查找法的时间复杂度为logN。

头文件：#include <stdlib.h>

平台：POSIX

函数签名：

void *bsearch(const void *key, const void *base, size_t nel, size_t width, int (*compar) (const void *, const void *));//bsearch_b并不是POSIX标准中的函数，而是iOS对二分查找的block形式的扩展void *bsearch_b(const void *key, const void *base, size_t nel, size_t width, int (^compar) (const void *, const void *));复制代码

参数：

key: [in] 要查找的元素。

base:[in] 数组元素的首地址。

nel: [in] 数组的元素个数。

width: [in] 数组中每个元素的尺寸。

compar: [in] 函数比较器，查找时会对数组的某些元素和要查找的元素调用函数比较器来判断是否匹配成功。函数比较器的格式如下

/*@key: 是要查找的元素，也是上面bsearch和bsearch_b中传入的第一个参数key。@element: 元素在数组中的地址，这里需要注意的是这个参数不是元素本身，而是元素所在的数组中的偏移地址。@return : 如果比较结果相等则返回0, 如果key小于element则返回小于0，如果key大于element则返回大于0*/ int compar(const void *key, const void *element);复制代码

return：如果找到则返回元素在数组中的指针，如果没有找到则返回NULL。

描述：

函数要求数组必须是有序的，至于是升序还是降序则跟函数比较器的返回是相关的。默认的情况是按升序进行二分查找的。bsearch_b和bsearch的区别是前者是block的形式的比较器，而后者则是函数形式的比较器，block形式的比较器功能更加强大一些。

示例代码:

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; //查找的关键字 student_t *pstudent = bsearch(&age, students, sizeof(students)/sizeof(student_t), sizeof(student_t), &bsearchcompar); NSAssert(pstudent != NULL && pstudent->age == 30);}复制代码