📄 subject_66936.htm
字号:
<p>
序号：66936 发表者：ctq 发表日期：2003-12-27 20:36:20
<br>主题：请教算法 关于折半查找。
<br>内容：用折半查找确定记录所在块的分块查找算法<BR>我只找到了这个算法<BR>大虾帮帮忙看看对不对<BR>typedef struct {<BR> int maxkey;<BR> int firstloc;<BR> } Index; <BR>typedef struct {<BR> int *elem;<BR> int length;<BR> Index idx[MAXBLOCK]; <BR> int blknum; <BR> } IdxSqList; <BR>int Search_IdxSeq(IdxSqList L,int key)<BR>{<BR> if(key>L.idx[L.blknum].maxkey) return ERROR; <BR> low=1;high=L.blknum;<BR> found=0;<BR> while(low<=high&&!found) <BR> {<BR> mid=(low+high)/2;<BR> if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey)<BR> found=1;<BR> else if(key>L.idx[mid].maxkey)<BR> low=mid+1;<BR> else high=mid-1;<BR> }<BR> i=L.idx[mid].firstloc; <BR> j=i+blksize-1; <BR> temp=L.elem[i-1]; <BR> L.elem[i-1]=key; <BR> for(k=j;L.elem[k]!=key;k--); <BR> L.elem[i-1]=temp; <BR> if(k<i) return ERROR; <BR> return k;<BR>}//Search_IdxSeq
<br><a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p>
<hr size=1>
<blockquote><p>
回复者：黑羽 回复日期：2003-12-27 20:57:54
<br>内容：不完善，当key不在数组里，你是怎么解决的啊？<BR>
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：ctq 回复日期：2003-12-27 21:14:27
<br>内容：如果这样呢？<BR><BR><BR>typedef struct {<BR>int maxkey;<BR>int firstloc;<BR>} Index; <BR>typedef struct {<BR>int *elem;<BR>int length;<BR>Index idx[MAXBLOCK]; <BR>int blknum; <BR>} IdxSqList; <BR>int Search_IdxSeq(IdxSqList L,int key<BR>{<BR>if(key>L.idx[L.blknum].maxkey&&key<L.idx[1].maxkey) return ERROR; <BR>low=1;high=L.blknum;<BR>found=0;<BR>while(low<=high&&!found) <BR>{<BR>mid=(low+high)/2;<BR>if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey)<BR>found=1;<BR>else if(key>L.idx[mid].maxkey)<BR>low=mid+1;<BR>else high=mid-1;<BR>}<BR>i=L.idx[mid].firstloc; <BR>j=i+blksize-1; <BR>if(key==L.elem[i]) return i;<BR>temp=L.elem[i]; <BR>L.elem[i]=key; <BR>for(k=j;L.elem[k]!=key;k--); <BR>L.elem[i]=temp; <BR>if(k==i) return ERROR; <BR>return k;
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：黑羽 回复日期：2003-12-27 21:36:47
<br>内容：运行后，输入的key恰好不在L.idx[n].maxkey中,循环结束：found=0,mid=1,<BR>那么i=L.idx[mid].firstloc之后的就失去意义了，blksize也没定义.
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：ctq 回复日期：2003-12-27 21:45:37
<br>内容：这样啊<BR>能不能把正确的贴出来啊<BR>不止算法，连带源程序一起贴出来吧
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：黑羽 回复日期：2003-12-27 22:42:56
<br>内容：//记得书写代码要有缩进<BR>#define MAXBLOCK 100<BR>typedef struct {<BR> int maxkey;<BR> int firstloc;<BR> } Index; <BR>typedef struct {<BR> int *elem;<BR> int length;<BR> Index idx[MAXBLOCK]; <BR> int blknum; <BR> } IdxSqList; <BR>int Search_IdxSeq(IdxSqList L,int key)<BR>{ <BR> int i,low=1,high=MAXBLOCK,found=0;<BR> if(key>L.idx[L.blknum].maxkey) return ERROR; <BR> while(low<=high&&!found) <BR> {<BR> mid=(low+high)/2;<BR> if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey)<BR> found = 1;<BR> else if(key>L.idx[mid].maxkey)<BR> low=mid+1;<BR> else high=mid-1;<BR> }<BR> if(!found) return -1; //未找到。<BR> //以下我不明白你想干什么？<BR> i=L.idx[mid].firstloc; <BR> j=i+blksize-1; <BR> temp=L.elem[i-1]; <BR> L.elem[i-1]=key; <BR> for(k=j;L.elem[k]!=key;k--); <BR> L.elem[i-1]=temp; <BR> if(k<i) return ERROR; <BR> //？？？？？？<BR> return k;<BR>}//Search_IdxSeq
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：ctq 回复日期：2003-12-27 22:54:54
<br>内容：拜托啦<BR>连主程序一起贴出来吧<BR><BR>这几天我都被这个搞得烦死啦
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
<font color=red>答案被接受</font><br>回复者：黑羽 回复日期：2003-12-27 23:29:10
<br>内容：//这是简化程序，很容易懂自己根据你的题目改，太晚了，我下了，有什么88<BR>#typedef struct KeyType{<BR> int key;<BR>};<BR>#typedef struct Table {<BR> keytype key;<BR>}table; <BR><BR>int BinSearch(table R[],keytype k)<BR>{<BR> int low,mid,high;<BR> while(low<=high)<BR> {<BR> mid=[(low+high)/2];<BR> if(k==R[mid].key) return mid;<BR> if(k<R[mid].key) high=mid-1;<BR> else low=mid+1;<BR> {<BR> return (-1);<BR>}
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：ctq 回复日期：2003-12-27 23:54:16
<br>内容：谢谢啦<BR>但是可不可以把MAIN函数那部分也贴出来啊<BR>
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -