分块查找课程设计讲解.docx

分块查找课程设计讲解.docx

《分块查找课程设计讲解.docx》由会员分享，可在线阅读，更多相关《分块查找课程设计讲解.docx（14页珍藏版）》请在冰点文库上搜索。

分块查找课程设计讲解

1实践的目的与要求

1.1实践目的

采用分块查找的方法查找指定的关键码

1.2课程设计要求

1）可以循环查找，可以选择退出；

2）分别采用顺序存储和链式存储完成分块查找，其中在顺序存储结果下，索引表的查找采用二分查找；

3）分别用函数完成索引表查找和块中查找；

4）每一个函数要有必要的注释，在课程设计论文中有流程图。

2分块查找概述

2.1分块查找简介

分块查找是折半查找和顺序查找的一种改进方法，折半查找虽然具有很好的性能，但其前提条件时线性表顺序存储而且按照关键码排序，这一前提条件在结点树很大且表元素动态变化时是难以满足的。

而顺序查找可以解决表元素动态变化的要求，但查找效率很低。

如果既要保持对线性表的查找具有较快的速度，又要能够满足表元素动态变化的要求，则可采用分块查找的方法。

分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。

当节点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。

分块查找由于只要求索引表是有序的，对块内节点没有排序要求，因此特别适合于节点动态变化的情况。

当增加或减少节以及节点的关键码改变时，只需将该节点调整到所在的块即可。

在空间复杂性上，分块查找的主要代价是增加了一个辅助数组。

需要注意的是，当节点变化很频繁时，可能会导致块与块之间的节点数相差很大，没写快具有很多节点，而另一些块则可能只有很少节点，这将会导致查找效率的下降。

2.2基本思想

1）分块查找要求把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。

假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的i，第i块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。

2）建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，显然这个辅助数组是按关键码值费递减排序的。

3）查找时，首先在索引表中进行查找，确定要找的节点所在的块。

由于索引表是排序的，因此，对索引表的查找可以采用顺序查找或折半查找。

然后，在相应的块中采用顺序查找，即可找到对应的节点。

2.3分块查找的优点

在线性表中插入或删除一个元素时，只要找到相应的块，然后在该块内进行插入或删除即可。

由于块内元素个数相对较少，而且是任意存放的，所以插入或删除比较容易，不需要移动大量的元素。

由于分块查找的过程是分两步进行的，所以在查找表中查找一个待查找记录的ASL为：

ASLbs=ASLb+ASLw

其中：

ASLb是在索引表中查找记录所在块的平均查找长度；ASLw是在块中查找待查找记录的平均查找长度。

假设将长度为n的查找表均匀地分为b块，每块含有s个记录，即「n/s」，再假设查找表中查找每一个记录的概率相等，则查找索引表的概率为1/b，在块中查找待查找记录的概率为1/s。

1）若采用顺序查找确定待查找记录所在块，那么，分块查找的平均查找长度为：

ASLbs=ASLb+ASLw=

所以分块查找的平均查找长度不仅与查找表的n有关，而且和每一块中的记录个数s有关。

所以在给定了长度为n的查找表的前提下，每块中的记录个数d是可变的。

容易证明，当s=

时，ASLbs=

+1，值最小。

2）若采用折半查找确定待查找记录所在块，那么，分块查找的平均查找长度为：

ASLbs=ASLb+ASLw=log2（b+1）+

=log2（

+1）+

由此可见，分块查找的效率是介于顺序查找和折半查找之间的。

它比顺序查找的执行速度更要快，比折半查找的执行速度要慢。

3分块查找的步骤

3.1方法描述

在查找表中的18个记录分成三个子表（R1，R2，…，R6）,（R7，R8，..,R12）,（R13，R14，…,R18），每个子表为一块。

首先用待查给定值K在索引表查找，然后再已确定的块中进行顺序查找，当查找表示有序表时，在块中也可用二分查找。

3.2假设

假设，如图3.1中，如果给定值K=36，则先用K和索引表各关键字进行比较，因为22

又如当K=26时，则仍在第二个字表中查找，自第7个记录起按记录顺序查找至第12个记录，每个记录的关键字和K比较都不想等，则查找失败。

引索表

关键字值

22

48

86

块起始地址

1

7

13

22

11

12

8

10

20

30

42

44

36

25

48

60

55

74

49

86

55

查找表

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

第一子表快

第二子表块

第三子表块

图3.1分块查找表结构示意图

4流程图

5编码

函数流程：

structsearchtable

//索引表结构体

创建索引表（程序开始）—>

输入关键字数据—>

自动生成索引表—>

赋值并输出索引表—>

循环寻找下一个反之跳出循环—>

找到元素反之越界找不到元素（程序结束）

#include

#include

#include

inttable[]={22,11,12,8,10,20,30,42,44,36,25,48,60,55,74,49,86,55};//list_1.h

{

intstelem;

//关键字数据

intlocation;

//关键字位置

}

6测试结果及运行结果

如图6.1，运行程序后的界面，按待查找的线性表给定的数字，任意输出其中数字和Enter键进入下一页面，或者退出。

图6.1分块查找的运行界面

图6.2待查给定值查询结果

如图6.2，测试输入给定值“36“页面正常显示，程序自动显示出给定值所在位置及其比较次数，以继续对页面进行操作，继续测试代码，逻辑。

图6.3查找失败的显示框

如图6.3，测试输入“26”页面正常显示，显示查找失败，说明逻辑设计正确。

可以继续对页面进行操作，继续测试代码，逻辑。

图6.4继续给待查给定值查询结果

如图6.4，测试输入“44”页面正常显示，程序自动显示出给定值所在位置及其比较次数，说明逻辑设计正确。

还可以继续对页面进行操作并继续对其测试代码，逻辑。

调试阶段最重要的还是耐性和细心。

要有足够的耐性去对待令人烦躁的错误，一步步细心的调试，就会查出错误的所在。

我们进行调试、测试是为了让我们的代码、程序更加健壮，质量更高。

所以，我们不要畏惧报错，这是个学习进步的过程。

我们应在错误中，认识到自己的不足与薄弱的知识点，提高自己的编写代码能力和改正错误的能力。

7总结

经过这次课程设计，得到的收获还是特别多的。

它不仅让我了解到做代码的整个流程，还让我在这个过程中学到了，很多过去不知道的东西，以及课本上所没有讲述的东西，同时也让我深刻的认识到我对知识的理解以及掌握程度还是极其有限的。

通过这次课程设计，让我了解到以下几点：

1、能力有待提高。

2、态度不太端正。

3、知识欠缺，课下尽可能地进行知识积累

4、整体意识不足，努力培养自身的整体意识

个人的力量是薄弱的，我学会了咨询别人，不再胆怯，不再保守。

   在过程中和同学相互讨论，询问老师，不断进步。

也许，我们可以说，编一个程仅仅是开始，调试和运行相比之下更难。

实践中收获的远比想象的多。

看到自己完成了所要求的任务，有一种无法用言语来形容的欣慰之感，这也是无法从学习书本知识中得到的。

8系统开发所用到的技术

操作系统：

Windows7以上的操作系统

开发软件:

Devc++

技术：

功能模块（函数）；结构；查找；文件保存及读取。

模块与函数:

功能模块：

求解较小问题的算法与程序称作“功能模块”，各功能模块可以先单独设计，然后将求解所有的子问题的模块组合成求解原问题的程序。

将一个大问题分解成多个解决小问题的模块的设计思想。

由功能模块组成程序的结构：

主控模块和模块组成。

模块还可细分。

自顶向下，逐步分解的设计思想

函数：

完成相对独立功能和程序。

模块独立：

功能独立的子功能模块之间的关系简单，使用独立变量，模块规模适当：

分解模块要注意层次：

（1）对问题抽象化

（2）设计时细化

设计原则：

高内聚，低耦合

查找是生活中经常用到的一个操作，如在英汉字典中查找某个英文单词的中文解释；在新华字典中查找某个汉字的读音、含义；在对数表、平方根表中查找某个数的对数、平方根；邮递员送信件要按收件人的地址确定位置等。

可以说查找是为了得到某个信息而常进行的工作。

查找在计算机科学中定义为：

在一些（有序的/无序的）数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找。

也就是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素。

参考文献

[1]刘觉夫,王更生等编著.C++程序设计.北京：

北京邮电大学出版社,2003.

[2]李素若,陈万华,游明坤编著.北京：

中国水利水电出版社，2014.

[3]谭浩强.C++面向对象程序设计.北京：

清华大学出版社，2006.

[4]刘玉英,张怡芳等.C++实验指导与课程设计.人民邮电出版社,2007.

附录全部代码

#include

#include

#include

inttable[]={22,11,12,8,10,20,30,42,44,36,25,48,60,55,74,49,86,55};

//书本8.2分块查找表结构示意图

structsearchtable

//索引表结构体

{

intstelem;

//关键字数据

intlocation;

//关键字位置

};

intmain（）

{

cout<<"待查找的线性表为"<

inti;

for（i=0;i<18;i++）{

cout<

cout<

cout<<"正在生成静态查找表..."<

//自动生成索引表

searchtablestable[3];

//索引表分为3个部分，表示分为3块

stable[0].location=1;

//第一个子表序列由位置1开始

stable[1].location=7;

//第二个子表序列由位置7开始

stable[2].location=13;

//第三个子表序列由位置13开始

intmax=table[0];

//将第一个元素值赋给max

for（intj=0;j<6;j++）

{

if（table[j]>max）

max=table[j];

}

stable[0].stelem=max;

//用循环使第一个子表的最大关键字的值赋给索引表第一个元素值

max=table[6];

//将第七个元素的值赋给max

for（j=6;j<12;j++）

{

if（table[j]>max）

max=table[j];

}

stable[1].stelem=max;

//用循环使第二个子表的最大关键字的值赋给索引表第二个元素值

max=table[12];

//将第十三个元素的值赋给max

for（j=12;j<18;j++）

{

if（table[j]>max）

max=table[j];

}

stable[2].stelem=max;

//利用循环将第三个子表的最大关键字的值赋给索引表第三个元素值

for（j=0;j<3;j++）

{

cout<

}

//输出索引表

cout<

while

（1）

{

inta;

printf（"Inputanumberyouwanttosearch:

"）;

cin>>a;

//接受输入的值赋给a

intcount=0;

//计数器清零

//在素引表中先查找

for（inti=0;i<3;i++）

if（a>stable[i].stelem）

//如果输入的值比索引表最大关键字的值大

{

continue;

//寻找下一个索引表最大关键字的值并与输入的值相比较并且计数器加1

}

elsebreak;

//反之，跳出循环

count+=i+1;

intaddr=6*i;

//开始计算输入元素的位置

for（j=0;j<6;j++）

//通过循环查找元素

{

count++;

//计数器加一

if（a==table[addr++]）

//找到元素

{

cout<

"<

cout<<"比较的次数为：

"<

break;

}

}

if（6==j）

//越界找不到元素

cout<<"查找失败！

"<

}

return0;

}