首页 > 代码库 > 排序,查找,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);}
							


3、关于scanf中读取字符串特殊用法:

这个总是忘记,或者模糊,这里做个笔记。

scanf("%20[^\n]",&a);读字符串20个字节到\n 就结束;
sscanf(in,"%[^]]",deal);将in中的字符串 按照"%[^]]" 规则提取到 deal中;