Chinaunix首页 | 论坛 | 博客
  • 博客访问: 754027
  • 博文数量: 231
  • 博客积分: 3217
  • 博客等级: 中校
  • 技术积分: 2053
  • 用 户 组: 普通用户
  • 注册时间: 2011-07-04 12:01
文章分类

全部博文(231)

文章存档

2015年(1)

2013年(10)

2012年(92)

2011年(128)

分类: C/C++

2012-09-26 16:54:55

查找分为静态查找和动态查找;
静态查找中顺序查找:

点击(此处)折叠或打开

  1. typedef float Keytype;
  2. typedef int Keytype;
  3. typedef char* Keytype;

  4. typedef struct{
  5.                Keytype key;
  6.                ...........
  7.      }Elemtype;

  8. #define EQ(a,b) ((a) == (b))
  9. #define LT(a,b) ((a) < (b))
  10. #define LQ(a,b) ((a) <= (b))

  11. #define EQ(a,b) (!strcmp((a),(b)))
  12. #define LT(a,b) (strcmp((a),(b))<0)
  13. #define LQ(a,b) (strcmp((a),(b))<=0)

  14. 静态查找表中顺序表查找法:
  15. typedef struct{
  16. Elemtype *elem;
  17. int length;
  18. }SStable;

  19. int search_seq(SStable ST,Keytype key)
  20. {
  21. ST.elem[0].key =key;//“哨兵”
  22. for(i=ST.length;!EQ(ST.elem[i].key,key);--i);//从后往前查找;
  23. return i;
  24. }
顺序查找法性能分析:ASL=0.75*(n+1)
有序表查询可以使用折半查找:先确定待查记录所在的范围(区间),然后逐步缩小范围知道找到或找不到该记录为止。

点击(此处)折叠或打开

  1. int search_ban(SStable ST,Keytype key)
  2. {
  3. low=1;high=ST.length;
  4. while(low<=high)
  5. {
  6. mid=(low+high)/2;
  7. if(key==ST.elem[mid].key) return mid;
  8. else if(ST.elem[mid].key <key ) low=mid+1;
  9. else
  10. high=mid-1
  11. }
  12. return 0;
  13. }
什么是好的哈希函数?
若对于关键字集合中任一个关键字,经哈希函数映像到地址集合中任何一个地址的概率是相等,则称此类哈希函数为均匀哈希函数。换句话说就是是关键字经过哈希函数得到一个“随机地址”,以便使一组关键字的哈希地址均匀分布在整个地址区间中,从而减少冲突。
 
 
 
 
 
阅读(658) | 评论(0) | 转发(0) |
0

上一篇:树的概念

下一篇:排序

给主人留下些什么吧!~~