多语言网站建设幻境,自我建设外贸网站,宠物网站建设策划方案,茶叶网页设计图片声明#xff1a;以下内容来源于网络资料的学习和整理 一、查找技术分类
1、静态查找表技术#xff08;顺序查找、二分查找、分块查找#xff09;
2、动态查找表技术#xff08;二叉查找树#xff09;
3、哈希表技术#xff08;哈希表技术#xff09; 二、查找技术说明…
声明以下内容来源于网络资料的学习和整理 一、查找技术分类
1、静态查找表技术顺序查找、二分查找、分块查找
2、动态查找表技术二叉查找树
3、哈希表技术哈希表技术 二、查找技术说明 衡量查找算法优劣的标准——平均搜索长度ASL其中Ci为查找第i个数需要进行比较的次数比如开始对比一个数组中的第i个数则前面已经对比了i-1个数字Pi表示查找第i个数的概率一般会平均即1/n。 A、静态查找表技术
1、顺序查找
1平均查找长度为(n1)/2即时间复杂度为O(n)。
2、二分查找
1必须是有序表而且只适用于顺序存储结构性能只有在均匀分布的时候才是最优的。
2查找长度每经过一次比较查找范围都要缩小一半因此最大查找长度为MSL[log2 n]1。当n足够大时可近似的表示为log2(n)即时间复杂度为O(log2(n))。
3二分查找要求查找表按关键字有序而排序是一种很费时的运算而且二分查找法要求表是顺序存储的为保持表的有序性在进行插入和删除操作时都必须移动大量记录。因此二分查找的高查找效率是以牺牲排序为代价的它特别适合于一经建立就很少移动、而又经常需要查找的线性表。
4代码示例
//k为待查找的数字R为数据集合函数返回k在R[]中的位置
int binsearch(int R[], int k)
{int low 0, high n-1;//R长度为nint mid;int find 0;while ((low high) (!find)){mid (low high) / 2; /*求区间中间位置*/if (k R[mid])find 1; /*查找到*/elseif (kR[mid])low mid 1; /*在后半区查找修改low*/elsehigh mid - 1; /*在前半区查找修改high*/}if (find)return (mid); /*查找成功返回找到的元素位置*/elsereturn (-1); /*查找失败返回-1*/
} 3、分块查找索引顺序查找
1分块查找要求把线性表分成若干块块与块之间必须有序即假如升序排列那么第一块的最大值必须小于第二块的最小值但是在每一块中记录的关键字不一定有序。假设这种排序是按关键字值递增排序的抽取各块中的最大关键字及该块的起始位置构成一个索引表按块的顺序存放在一个数组中显然这个数组是有序的。
2分块查找过程分两步进行
a、首先查找索引表确定待查记录所在块可用二分查找法或顺序查找法
b、在相应块子表中用顺序查找法查找记录。
3分块查找的效率介于顺序查找和折半查找之间对于数据量巨大的线性表它是一种较好的方法。在表中插入或删除一个记录时只要找到该记录所属的块就可以在该块内进行插入和删除运算插入和删除无需移动大量记录。分块查找的主要代价是需要增加一个辅助数组的存储空间和将初始表分块排序的运算。
4代码示例
struct idtable
{int key;//这里指的是该块的最大值int addr;//该快的最大值在数组中的位置
};
struct idtable ID[b]; /*b为块数*/int blksearch(int R[], struct idtable ID[], int k)
{int i;int low10, high1b-1;//low1、high1为索引表的区间下、上界int low2, high2;int mid; while (low1 high1){mid (low1 high1) / 2;if (k ID[mid].key)high1 mid - 1;elselow1 mid 1;}/*查找完毕low1存放找到的块号*/if (low1 b){low2 ID[low1].addr; /*low2为待查值所在的那个表的起始地址*/if (low1 b - 1)high2 N - 1; /*N为查找表的长度high2为块在表中的末地址*/elsehigh2 ID[low1 1].addr - 1;for (i low2; i high2; i) /*在块内顺序查找*/if (R[i].key k)return i;}else /*若low1b则k大于查找表R中的所有关键字*/return -1;B、动态查找表技术 C、哈希表技术
1、哈希表的定义 哈希表是通过关键字进行某种计算映射来确定该记录的存储位置的一种查找表。
2、冲突解决方法 不同的关键字根据哈希函数被映射到同一个存储地址这种现象被称为冲突。冲突是不可避免的因为关键字的取值集合远远大于表空间的地址集合我们只能尽量减少冲突的发生。在构造哈希函数时主要面临两个问题一是构造较好的哈希函数把关键字集合中元素尽可能均匀地分布到地址空间中去减少冲突的发生另一个就是找到解决冲突的方法。 解决冲突的方法中比较常用的是链地址法即为每一个哈希地址建立一个链表当冲突发生时将具有相同哈希地址的记录链接到同一链表中。
3、哈希算法的过程首先得建立哈希表一般都有从文件中读取吧其次才是查找。
4、完整代码示例 #includestdio.h
#includestdlib.hstruct keyNum
{int key;//关键字struct keyNum *next;
};struct keyNum* hash[100];
struct keyNum* insertHash(struct keyNum*, int m);//关键字插入链表
int searchHash(struct keyNum*, int m);//查找链表中是否存在值为m的整数
void print(struct keyNum*);//打印链表void main()
{printf(关键字列表请保存在data.txt文件中其中第一个值为关键字的个数\n其他值为具体的关键字各个关键字之间用空格隔开\n);int i, k, m, n, num, flag, l, j;FILE *pNULL;struct keyNum *head NULL;p fopen(C:\\Users\\Horrobo\\Desktop\\data.txt, r);if (p NULL){printf(cannot open file 2.txt);exit(0);}fscanf(p, %d, num);//data.txt第一个值为关键字的个数因此num读入的是关键字的个数这里默认num小于100的for (i 0; inum; i)//由于hash[]只有100个指针因此关键字映射后最多只能有100个不相同的。hash[i] NULL;for (i 0; inum; i){ //fscanf()遇到空格停止读取fscanf(p, %d, k);//获取关键字m k % (num 1);//计算得到关键字的哈希值hash[m] insertHash(hash[m], k);//将关键字k插入到哈希值为m的链表中}printf(-----------------------------------------------\n请选择要进行的操作\n1、打印采用链地址法得到的哈希表\n);printf(2、进行关键字查找\n3、退出\n------------------------------------------------\n);scanf(%d, flag);while ((flag 1) || (flag 2)){if (flag 1)//打印哈希表{printf(采用链地址法得到的哈希表为\n);for (i 0; inum 1; i){printf(第%d行, i);print(hash[i]);printf(\n);}}else //查找{printf(请输入要查找的整数值\n);scanf(%d, n);for (i 0; inum 1; i)//只是返回一个标志值后面再根据标志来执行操作这个流程值得参考哦{l searchHash(hash[i], n);if (l 1){j i;break;}}if (l 1)printf(整数值%d在哈希表中位置为链表%d\n, n, j);//只是找出位于第几链表而已。else printf(整数值%d不在哈希表中\n);}printf(-----------------------------------------------\n请选择要进行的操作\n1、打印采用链地址法得到的哈希表\n);printf(2、进行关键字查找\n3、退出\n------------------------------------------------\n);scanf(%d, flag);}
}struct keyNum * insertHash(struct keyNum*head, int m)
{struct keyNum *p0, *p1, *p2NULL, *temp;//这些都仅仅是结构体指针而不是结构体它所指向的内容才是结构体内容。就把它理解为类型 int*指针就好temp (struct keyNum*)malloc(sizeof(struct keyNum));temp-key m;p1 head;p0 temp;//要插入的节点值为m);if (head NULL)//1原来的链表为空插入到head后{head p0;p0-next NULL;}else//原来的链表不为空{while ((p0-keyp1-key) (p1-next ! NULL))//移动到适当位置 起码有两个节点了否则p1-next ! NULL这个就不满足了。因为P1head是第一个节点的指针{//判断语句从head开始查询链表p1-next ! NULLp1p1-next,看是否满足条件p0-keyp1-key p2 p1;p1 p1-next;}if (p0-key p1-key){if (head p1)head p0;//2插入到第一个节点之前else p2-next p0;//3,插入到p2指向的节点之后p0-next p1;}else//4,插入到结尾处{p1-next p0;p0-next NULL;}}return(head);
}int searchHash(struct keyNum*head, int m)//查找链表head中是否存在m
{int k 0;struct keyNum*p;p head;if (head ! NULL)do{if (p-key m) //存在m{k 1;break;}p p-next;} while (p ! NULL);return(k);//存在m值则返回1否则返回0
}void print(struct keyNum*head)//打印链表head
{struct keyNum*p;p head;if (head ! NULL){do{printf( - %d , p-key);p p-next;} while (p ! NULL);}elseprintf(null);
}/*
struct keyNum * insertHash(struct keyNum*head, int k)//
{struct keyNum *p (struct keyNum *)malloc(sizeof(struct keyNum));//1.首先开创一个结构体区间给里面的相应内容赋值p-key k;struct keyNum * temp NULL;if (head NULL)//2、判断是否是空指针如果是则将刚才创建的结构体区间作为头//具体的实现方法就是将传过来的空指针指向刚才创建的结构体空间yes{head p;p-next NULL;}else//如果不是则在原来的链条的尾巴上添加新的节点上面已经创建好的节点//具体的实现方法就是将head指针指向刚才所创建的结构体空间NOhead并不是指向尾巴节点的指针而是整个链条的首指针{head-next p;p-next NULL;}return head;
}
*/总结
1顺序查找的查找效率很低但是对于待查记录的存储结构没有任何要求既适用于顺序存储又适用于链式存储当待查表中的记录个数较少时采用顺序查找法较好。
2折半查找的平均查找长度较小查找速度快但它只能用于顺序存储不能用于链式存储且要求表中的记录是有序的。对于不常变动的有序表采用折半查找法是较为理想的。
3分块查找的平均查找长度介于顺序查找和折半查找之间跟顺序查找一样对记录的存储结构没什么要求既可以用于顺序存储也可用于链式存储要求表中元素是逐段有序的即块与块之间的记录按关键字有序。当待查表的数据量较大时分块查找的优越性更为突出。
4哈希法是一种直接计算地址的方法通过对关键字值进行某种运算来确定待查记录的存储地址。在查找过程中不需要进行比较因此其查找时间与表中记录的个数无关。当所选择的哈希函数能得到均匀的地址分布时其查找效率比前面的三种方法都要快。哈希法的查找效率取决于以下三个因素哈希函数、处理冲突的方法及装填因子。 P.s.线性表包括顺序存储表比如数组、链式存储表链表。
另外在编程的过程中也体会到了以下内容指向结构体的指针P或者head无论是通过赋值还是开创的空间的强制转换head-next,p-next都是p结构体内next。
