啰嗦几句
我本来想说的是 Unix 系统 C 标准库所提供的一些算法和数据结构 API, 但毕竟带有 iOS 标题可能更加吸引眼球一些. 其实我说的也没有错, 因为 iOS 毕竟是从 Unix 衍生出来的系统, 所以说标题所述也算是正确的. 下面将要介绍的几类 API, 有些可以在 POSIX 平台中支持, 有些则只能在 FreeBSD 中支持, 有些则只有在 iOS 系统中单独支持.
iOS 系统中的 C 标准库中主要提供了线性查找, 二分查找, 双向链表, 快速排序, 堆排序, 归并排序, 并行排序, 基数排序, 二叉排序树, 哈希表, KV 数据库等众多的 API. 这些 API 基本覆盖了在应用中的常见数据结构和算法的需求.
那既然 Foundation 和 CoreFoundation 库中都提供了众多的基于 OC 语言的算法和数据结构为什么还要使用这些函数呢? 原因就是性能和兼容性.
线性查找
功能: 遍历数组, 查找满足条件的记录.
头文件:#include
平台: 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
平台: 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);
- }
来源: http://www.tuicool.com/articles/IJNrQnm