编程论坛 » 数据结构与算法 » 折半查找 、顺序查找 、 分块查找 的实现方法

chinahgcq 发表于 2007-7-6 13:57

折半查找 、顺序查找 、 分块查找 的实现方法

<P><FONT color=#ff0000>下面的链接是源代码，愿意看的点击下载，到C++ 里面运行就是<BR></FONT>[attach]23646[/attach]<BR><BR><BR>以下是源代码<BR>#include "iostream"<BR>#include "math.h"<BR>using namespace std;<BR>#define MAXSIZE 200<BR>typedef int KeyType;<BR>typedef int DataType;<BR>typedef struct <BR>{<BR>    KeyType key;<BR>    DataType data;<BR>}NodeType;<BR>typedef NodeType SeqList[MAXSIZE];</P>
<P><BR>void SeqSearch(SeqList S,int n,KeyType k)<BR>{<BR>    for(int i=0;i&lt;n&amp;&amp;S[i].key!=k;i++);<BR>    if(i&lt;n)<BR>    {<BR>        cout&lt;&lt;"该数在第 "&lt;&lt;i+1&lt;&lt;" 位"&lt;&lt;endl;<BR>        cout&lt;&lt;"顺序查找次数为"&lt;&lt;i&lt;&lt;endl;<BR>    }<BR>    else <BR>    {<BR>        cout&lt;&lt;"The number is not exist!SeqSearch has searched "&lt;&lt;i&lt;&lt;" times"&lt;&lt;endl;<BR>    }</P>
<P>}</P>
<P>void BinSearch(SeqList S,int n,KeyType k)<BR>{<BR>    int low=0,high=n-1,mid,num=0;<BR>    while(low&lt;=high)<BR>    {<BR>        mid=(low+high)/2;<BR>        num++;<BR>        if(S[mid].key==k)<BR>        {<BR>            cout&lt;&lt;"折半查找次数为 "&lt;&lt;num&lt;&lt;endl;<BR>            exit(0);<BR>        }<BR>            <BR>        else if(S[mid].key&lt;k)<BR>            low=mid+1;<BR>        else<BR>            high=mid-1;<BR>    }<BR>    cout&lt;&lt;"The number is not exist!BinSearch has searched "&lt;&lt;num&lt;&lt;" times"&lt;&lt;endl;<BR>}</P>
<P>void AreaSearch(SeqList S,int n,KeyType k)<BR>{<BR>    int length=sqrt(n);//分块的块长<BR>    bool check=false;//查到与否的标志<BR>    int b=n%length==0?0:1;<BR>    int num=n/length+b;//分的组数<BR>    for(int i=0;i&lt;num;i++)<BR>    {<BR>        int NUM=(i*num+num)&lt;=n?(i*num+num):n;<BR>        if(k&lt;S[NUM].key)<BR>        {<BR>           for(int j=i*num;j&lt;(NUM)&amp;&amp;k!=S[j].key;j++);<BR>           if(j&lt;(NUM))<BR>           {<BR>               cout&lt;&lt;"分块查找次数为 "&lt;&lt;(i+j-i*num+1)&lt;&lt;endl;<BR>               check=true;<BR>               break;<BR>           }<BR>           else<BR>           {<BR>               cout&lt;&lt;"The number is not exist!AreaSearch has searched "&lt;&lt;(i+j-i*num+1)&lt;&lt;" times"&lt;&lt;endl;<BR>               check=true;<BR>               break;<BR>           }<BR>        }<BR>        else if(k==S[NUM].key)<BR>        {<BR>            cout&lt;&lt;"分块查找次数为 "&lt;&lt;i+1&lt;&lt;endl;<BR>            check=true;<BR>            break;<BR>        }<BR>    }<BR>    if(!check)<BR>        cout&lt;&lt;"没有找到!分块查找次数为 "&lt;&lt;i+1&lt;&lt;endl;<BR>    <BR>    <BR>}</P>
<P>void Init(SeqList &amp;Q,int &amp;m,int &amp;n)<BR>{<BR>    <BR>    while(m&gt;MAXSIZE||m&lt;0)<BR>    {<BR>        cout&lt;&lt;"请输入数组的长度(不要超过"&lt;&lt;MAXSIZE&lt;&lt;")：";<BR>        cin&gt;&gt;m;<BR>    }<BR>    cout&lt;&lt;endl;<BR>    for(unsigned i=0;i&lt;m;i++)<BR>    {<BR>        Q[i].key=i;<BR>        cout&lt;&lt;Q[i].key&lt;&lt;" ";<BR>        if((i+1)%10==0)<BR>            cout&lt;&lt;endl;<BR>    }<BR>    cout&lt;&lt;endl&lt;&lt;"请输要查找的数据:";<BR>    cin&gt;&gt;n;</P>
<P><BR>}<BR>void main()<BR>{<BR>    SeqList Q;<BR>    int n;//number you want to find<BR>    int m;//length of array<BR>    Init(Q,m,n);<BR>    SeqSearch(Q,m,n);<BR>    AreaSearch(Q,m,n);<BR>    BinSearch(Q,m,n);<BR>    <BR>}</P>

vfdff 发表于 2008-6-12 00:58

有长度限制 不是很爽
应该长度动态可以变 才比较好

vfdff 发表于 2008-6-12 01:00

不知道您使用什么编译
我现在修改了 能在 cfree下

查看完整版本: 折半查找 、顺序查找 、 分块查找 的实现方法