首页 > 程序开发 > 软件开发 > C语言 >

一步一步写算法(之查找)

2011-10-21

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】 无论是数据库,还是普通的ERP系统,查找功能数据处理的一个基本功能。数据查找并不复杂,但是如何实现数据又快又好地查...

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】

无论是数据库,还是普通的ERP系统,查找功能数据处理的一个基本功能。数据查找并不复杂,但是如何实现数据又快又好地查找呢?前人在实践中积累的一些方法,值得我们好好学些一下。我们假定查找的数据唯一存在,数组中没有重复的数据存在。

(1) 普通的数据查找

设想有一个1M的数据,我们如何在里面找到我们想要的那个数据。此时数据本身没有特征,所以我们需要的那个数据可能出现在数组的各个位置,可能在数据的开头位置,也可能在数据的结束位置。这种性质要求我们必须对数据进行遍历之后才能获取到对应的数据。

view plaincopy to clipboardprint?int find(int array[], int length, int value)

{

if(NULL == array || 0 == length)

return -1;

for(int index = 0; index < length; index++){

if(value == array[index])

return index;

}

return -1;

}

int find(int array[], int length, int value)

{

if(NULL == array || 0 == length)

return -1;

for(int index = 0; index < length; index++){

if(value == array[index])

return index;

}

return -1;

}分析:

由于我们不清楚这个数据判断究竟需要多少次。但是,我们知道,这样一个数据查找最少需要1次,那么最多需要n次,平均下来可以看成是(1+n)/2,差不多是n的一半。我们把这种比较次数和n成正比的算法复杂度记为o(n)。

(2)上面的数据没有任何特征,这导致我们的数据排列地杂乱无章。试想一下,如果数据排列地非常整齐,那结果会是什么样的呢?就像在生活中,如果平时不注意收拾整齐,那么找东西的时候非常麻烦,效率很低;但是一旦东西放的位置固定下来,所有东西都归类放好,那么结果就不一样了,我们就会形成思维定势,这样查找东西的效率就会非常高。那么,对一个有序的数组,我们应该怎么查找呢?二分法就是最好的方法。

view plaincopy to clipboardprint?int binary_sort(int array[], int length, int value)

{

if(NULL == array || 0 == length)

return -1;

int start = 0;

int end = length -1;

while(start <= end){

int middle = start + ((end - start) >> 1);

if(value == array[middle])

return middle;

else if(value > array[middle]){

start = middle + 1;

}else{

end = middle -1;

}

}

return -1;

}

int binary_sort(int array[], int length, int value)

{

if(NULL == array || 0 == length)

return -1;

int start = 0;

int end = length -1;

while(start <= end){

int middle = start + ((end - start) >> 1);

if(value == array[middle])

return middle;

else if(value > array[middle]){

start = middle + 1;

}else{

end = middle -1;

}

}

return -1;

}分析:

上面我们说到普通的数据查找算法复杂度是o(n)。那么我们可以用上面一样的方法判断一下算法复杂度。这种方法最少是1次,那么最多需要多少次呢?我们发现最多需要log(n+1)/log(2)即可。大家可以找个例子自己算一下,比如说7个数据,我们发现最多3次;如果是15个数据呢,那么最多4次;以此类推,详细的论证方法可以在《算法导论》、《计算机编程艺术》中找到。明显,这种数据查找的效率要比前面的查找方法高很多。

(3) 上面的查找是建立在连续内存基础之上的,那么如果是指针类型的数据呢?怎么办呢?那么就需要引入排序二叉树了。排序二叉树的定义很简单:(1)非叶子节点至少一遍分支非NULL;(2)叶子节点左右分支都为NULL;(3)每一个节点记录一个数据,同时左分支的数据都小于右分支的数据。可以看看下面的定义:

view plaincopy to clipboardprint?typedef struct _NODE

{

int data;

struct _NODE* left;

struct _NODE* right;

}NODE;

typedef struct _NODE

{

int data;

struct _NODE* left;

struct _NODE* right;

}NODE; 那么查找呢,那就更简单了。

view plaincopy to clipboardprint?const NODE* find_data(const NODE* pNode, int data){

if(NULL == pNode)

return NULL;

if(data == pNode->data)

return pNode;

else if(data < pNode->data)

return find_data(pNode->left, data);

else

return find_data(pNode->right, data);

}

const NODE* find_data(const NODE* pNode, int data){

if(NULL == pNode)

return NULL;

if(data == pNode->data)

return pNode;

else if(data < pNode->data)

return find_data(pNode->left, data);

else

return find_data(pNode->right, data);

}

(4)同样,我们看到(2)、(3)都是建立在完全排序的基础之上,那么有没有建立在折中基础之上的查找呢?有,那就是哈希表。哈希表的定义如下:1)每个数据按照某种聚类运算归到某一大类,然后所有数据链成一个链表;2)所有链表的头指针形成一个指针数组。这种方法因为不需要完整排序,所以在处理中等规模数据的时候很有效。其中节点的定义如下:

view plaincopy to clipboardprint?typedef struct _LINK_NODE

{

int data;

struct _LINK_NODE* next;

}LINK_NODE;

typedef struct _LINK_NODE

{

int data;

struct _LINK_NODE* next;

}LINK_NODE;

那么hash表下面的数据怎么查找呢?

view plaincopy to clipboardprint?LINK_NODE* hash_find(LINK_NODE* array[], int mod, int data)

{

int index = data % mod;

if(NULL == array[index])

return NULL;

LINK_NODE* pLinkNode = array[index];

while(pLinkNode){

if(data == pLinkNode->data)

return pLinkNode;

pLinkNode = pLinkNode->next;

}

return pLinkNode;

}

LINK_NODE* hash_find(LINK_NODE* array[], int mod, int data)

{

int index = data % mod;

if(NULL == array[index])

return NULL;

LINK_NODE* pLinkNode = array[index];

while(pLinkNode){

if(data == pLinkNode->data)

return pLinkNode;

pLinkNode = pLinkNode->next;

}

return pLinkNode;

}分析:

hash表因为不需要排序,只进行简单的归类,在数据查找的时候特别方便。查找时间的大小取决于mod的大小。mod越小,那么hash查找就越接近于普通查找;那么hash越大呢,那么hash一次查找成功的概率就大大增加。

【预告: 下一篇博客介绍排序的内容】

相关文章
最新文章
热点推荐