首页 > 代码库 > 排序,查找,qsort和bsearch的简单总结,scanf字符串截取
排序,查找,qsort和bsearch的简单总结,scanf字符串截取
有一些时候,一些方便用户做的设计,往往会降低产品本身的安全性。
安全性与易用性,是一道产品设计者需要仔细思考的题。
==========================================================================================================
好了,切入正题。最近在练题,或者说刷题,发现自己不知道的东西还真不少,得好好补补啦~
首先就是c语言的两个,也是唯一的两个与排序搜索相关的函数,记得之前自己还很仔细的去背快速排序法了,原来c里面有的。
标准库里面为数不多的两个实用函数。
它们都在stalib.h头文件中。
1、函数名: qsort
功 能: 使用快速排序例程进行排序
用 法: void qsort(void *base, int nelem, int width, int (*fcmp)());
base是待排序的数组,nelem是数组元素的个数, width是元素的大小,一般sizeof, fcmp是比较的函数。
参考实用方法: typedef struct { int h,l,t; }NODE; int cmp(const void *q, const void *p) { return (*(NODE*)q).t - (*(NODE *)p).t;//从小到大排,q-p; 从大到小排p-q; 或者:返回值小于0保持现状,大于0交换 } 调用: qsort(bg, n, sizeof(NODE), cmp);
2、函数名: bsearch
功 能: 二分法搜索
用 法: void *bsearch(const void *key, const void *base, size_t *nelem,
size_t width, int(*fcmp)(const void *key, const *));
key是待搜索的关键字, base是待搜索的数组, nelem是数组元素个数, width是元素大小, fcmp是比较函数,它一般和排序的函数是对应的。
返回值是搜索到的元素的地址,没有找到的时候,为null。
这里要注意的是,fcmp中使用的比较类型是数组元素的类型,因此key也必须是对应的数组元素类型。
bsearch的具体用法我参考了源代码才发现。
minix系统中提供: void * bsearch(register const void *key, register const void *base, register size_t nmemb, register size_t size, int (*compar)(const void *, const void *)) { register const void *mid_point; register int cmp; while (nmemb > 0) { mid_point = (char *)base + size * (nmemb >> 1); if ((cmp = (*compar)(key, mid_point)) == 0) return (void *)mid_point; if (cmp >= 0) { base = (char *)mid_point + size; nmemb = (nmemb - 1) >> 1; } else nmemb >>= 1; } return (void *)NULL; } linux系统中提: void *bsearch(const void *key, const void *base, size_t num, size_t size, int (*cmp)(const void *key, const void *elt)) { size_t start = 0, end = num; int result; while (start < end) { size_t mid = start + (end - start) / 2; result = cmp(key, base + mid * size);//传进来的key就是比较的key if (result < 0) end = mid; else if (result > 0) start = mid + 1; else return (void *)base + mid * size; } return NULL; }
因此,参考的使用方法:
NODE *q,temp; in[strlen(in)-1] = '\0'; strcpy(temp.magic,in+1); q = (NODE *)bsearch(&temp,words, t, sizeof(NODE), cmp1);//传入temp的类型应该和 要搜索的数组的元素类型一致。 if( q== NULL) printf("what?\n"); else printf("%s\n",(*q).func);
int cmp1(const void *p, const void *q)<span style="white-space:pre"> </span>//qsort中使用的方法{<span style="white-space:pre"> </span>return strcmp( (*(NODE *)p).magic, (*(NODE *)q).magic);}
这个总是忘记,或者模糊,这里做个笔记。
scanf("%20[^\n]",&a);读字符串20个字节到\n 就结束;
sscanf(in,"%[^]]",deal);将in中的字符串 按照"%[^]]" 规则提取到 deal中;