《数据结构》课件-项目八 查找

用查找实现手机通讯录项目概述在实际的工作生活中，查找操作无处不在。例如，在通信录中查找某个人的电话号码，在英汉字典中查找某个单词的中文解释，在图书馆里根据书名查找某一本书，这些都是查找的具体应用。查找操作如今可以通过计算机软件完成，在百度搜索引擎中查找想要的信息，在电子商务网站中查找想要的商品，在教务管理系统中查找学生的成绩，几乎各种信息管理系统，各种行业应用软件，都具有查找的功能。因此查找操作己经成为应用程序的重要组成部分。查找问题就是在给定的集合中找寻一个给定的值，有许多查找算法可供选择，其中既包括直截了当的顺序查找，也包括效率极高但应用受限的折半查找，还有将原集合用另一种形式表示以方便查找的算法，但没有一种算法在任何情况下都是最优的，如何根据实际的应用选择一种好的查找算法是一项不同寻常的挑战。项目目标序号能力目标知识要点1理解查找的基础知识查找的基本概念、查找的分类、平均查找长度2理解查找算法的基本思想静态查找：顺序查找、折半查找、分块查找动态查找：二叉排序树查找、哈希表查找3能用Java实现查找算法用Java语言实现顺序查找、折半查找、分块查找、二叉排序树查找、哈希表查找4能基于实际应用选择合适的查找算法使用查找实现手机通讯录项目情境-编程实现手机通讯录管理

1．情境描述

手机通讯录是手机最基本的功能之一，它是一种能够保存大量联系人信息的电子列表，联系人信息包括了姓名、电话、工作单位等，可以对联系人的信息进行增删改查操作，为方便查询，还可以对联系人进行分组，如亲人、朋友、同事等。打电话和接电话一般都先执行了查找运算。打电话时，通常先到通讯录中按姓名搜索联系人的号码，找到该号码后拨号，没有找到时才会输入号码拨打；接电话时，系统也会先到通讯录中查找该号码对应的联系人信息，有则显示的是姓名，无则显示的是号码，接话人以此来判断是否是陌生的来电。接听后还可将陌生人的电话保存到通讯中，接电话的流程如图所示。2．基本要求假设某手机通讯录中保存了表中的电话信息，现以该组电话为测试数据，编程实现如下功能：（1）来电时，查看电话号码是否在通讯中，有则显示姓名，无则显示电话号码。（2）如电话号码不在通讯录中，可保存该电话号码。（3）可删除电话通讯录中电话信息。任务一

分析手机通讯录中数据的逻辑结构学习目标熟悉查找的基本概念熟悉查找表的分类12熟悉查找的技术3

为实现手机通讯录功能，需要抽象手机通讯录问题，建立问题的抽象数据类型。一是确定数据对象的逻辑结构，找出构成数据对象的数据元素之间的关系。二是确定为求解问题需要对数据对象进行的操作或运算。最后将数据的逻辑结构及其在该结构上的运算进行封装得到抽象数据类型。任务描述步骤一：分析数据的逻辑结构任务实施手机通讯录的逻辑结构在手机通讯录问题中，电话信息数据表构成了问题要处理的数据对象，数据表由若干条联系人信息组成，每一条信息为一个数据元素，每个数据元素由姓名、号码两个数据项组成。数据表中第一个联系人信息可视为开始结点，它的前面无数据元素；最后一个联系人信息视为终止节点，它的后面无数据元素；其他联系人信息则各有一个也只有一个前趋和和一个后继.因此通讯录信息表的数据结构为线性表。步骤二：分析数据的查找运算任务实施查找的基本概念（1）查找的定义查找是指在一组给定的数据元素中寻找关键字等于某个给定值的数据元素。若存在这样的数据元素，则查找成功，返回数据元素的信息或数据元素的位置；否则查找不成功，返回的结果可以给出一个“空”值，或位置值为“-1”如查找号码为12320的号码是什么服务热线查r查找的基本概念（2）关键字、主关键字、次关键字关键字是数据元素中某个数据项的值，又称为键值，用它可以标识一个数据元素，也可以标识一个数据元素的某个数据项。主关键字是可以唯一地标识一个数据元素的关键字。对于那些可以标识多个数据元素的关键字，称为次关键字。表中的姓名和号码都可以作为主关键查r查找的基本概念（3）查找表是一种以同一类型的数据元素构成的集合为逻辑结构，以查找为核心运算的数据结构。从逻辑上来说，查找基于的数据结构是集合，集合中的记录之间没有本质关系。但为了获得较高的查找性能，通常将查找集合组织成表、树等结构若干个电话记录表构建了查找集合，根据查找的方式，可以将该集合组织成线性表、树等结构查r查找的技术对应不同的数据结构，有线性表、树表、哈希表三种查找技术。线性表查找是指进行查找运行的查找表所采用的存储结构是线性表的存储结构，在其上所进行的查找为线性表的查找。在线性表查找技术中，对数据元素的查找又有顺序查找、折半查找和分块查找。树表查找是指进行查找运行的查找表所采用的存储结构是树的存储结构，在其上所进行的查找为树表的查找。在树表查找技术中，对数据元素的查找又有平衡二叉树、B树、二叉排序树查找。哈希表查找是指进行查找运行的查找表所采用的存储结构是哈希散列存储结构，在其上所进行的查找为哈希表查找。查找的分类查找表按照操作方式可以分为两大类：静态查找表和动态查找表。静态查找表：只做查找操作的查找表。主要操作有查询某个“特定的”数据元素是否在查找表中。代表有顺序查找、二分查找、分块查找。动态查找表：在查找的同时对表做插入、删除或修改操作。代表有平衡二叉树、B树、二叉排序树、散列表。平衡二叉树B树二叉排序树散列表...顺序查找二分查找分块查找查找的分类静态查找表动态查找步骤三：定义抽象数据类型任务实施定义抽象数据类型ADTContactList数据对象：D={ai|0≤i≤n-1,n≥0,ai为联系人信息}数据关系：R={<ai,ai+1>|ai,ai+1∈D,i=0,...,n-2基本操作：publicEselectByNumber();//按号码查找联系人信息public

voidaddcontacts();//添加联系人信息public

voiddeletecontacts();//删除联系人信息步骤四：创建一个手机通讯录类任务实施创建一个手机通讯录类定义了一个名为Contacts的类，它代表了一个联系人对象。以下是对这段代码功能的详细分析：属性定义：Stringname;：定义了联系人的名称，但注意这个属性在类的构造方法中没有强制要求初始化。intphone;：定义了联系人的电话号码，是类的核心属性之一。构造方法：publicContacts(intphone)：接受一个参数（电话号码），并用于初始化phone属性。如果通过这个构造方法创建Contacts对象，那么name属性将保持为null。publicContacts(Stringname,intphone)：这是一个更完整的构造方法，它接受两个参数（名称和电话号码），并分别用于初始化name和phone属性。toString方法：@OverridepublicStringtoString()：重写了Object类的toString方法，以便在将Contacts对象转换为字符串时，能够返回包含名称和电话号码的格式化字符串。这对于调试和打印联系人信息非常有用。compareTo方法：@OverridepublicintcompareTo(Contactso)：实现了Comparable<Contacts>接口的compareTo方法，允许Contacts对象相互比较。比较是基于phone属性的值进行的。如果两个Contacts对象的phone属性值相同，则返回0；如果当前对象的phone属性值大于参数对象的phone属性值，则返回1；否则，返回-1。这种比较方式确保了基于电话号码的排序是稳定的（即相同的电话号码会保持它们原有的相对顺序）。public

classContactsimplementsComparable<Contacts>{ Stringname;//联系人名称

int

phone;//联系人电话

publicContacts(int

phone){

this.phone=phone; }

publicContacts(Stringname,int

phone){

this.phone=phone;

this.name=name; }

@Override

publicStringtoString(){

return

"["+name+","+phone+"]"; }

@Override

public

intcompareTo(Contactso){

if(phone==o.phone)

return0;

else

if(phone>o.phone)

return1;

else

return-1;

}}public

classContactsList{ Contacts[]cList;

publicContactsList(Contacts[]clist){

this.clist=cList; }}创建一个类ContactsList，声明一个为Contacts类型的数组变量cList，用于表示通讯录。并创建一个构造函数，用于初始化变量clist。在数据的海洋中，查找算法如同灯塔，指引我们迅速定位目标。它以高效的姿态，穿越有序与无序的迷宫，带来光明与希望，让信息的检索变得轻而易举，彰显科技的力量与智慧的光辉。任务二

用顺序查找技术查找联系人信息学习目标理解顺序查找的基本思想能用Java语言实现顺序查找的算法12

在理解顺序查找基本思想的基础上，将姓名和电话号码作为关键字，用顺序查找技术查找手机通讯录中联系人的信息。任务描述步骤一：理解顺序查找的基本思想任务实施顺序查找是最简单的查询方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到结点关键字与给定值Key相比较。若当前扫描到的结点关键字与Key相等，查找成功，返回该结点的索引下标；若扫描结束后，仍未找到关键字等于Key的结点，则查找失败,返回-1。基本思想图(a)用顺序存储结构存储手机通讯录图(b)用顺序查找查找电话为10086的联系人图(a)所示的顺序表中的每个元素为一个联系人的信息，由号码和姓名组成。图(b)记录了在顺序表中查找电话10086是什么电话的过程，比较4次后找到关键字10086所在的下标位置为3。查找12316电话号码时，比较9次后到顺序表的最后一个元素，仍没有找到该电话，则返回-1。步骤二：实现顺序查找算法任务实施算法实现在ContactList中，编写顺序查找算法seqSearchByPhone，查找的关键字为电话phone的联系人在通讯录中的位置。参数intphone：这是方法的参数，表示要查找的电话号码。方法体-方法首先通过一个for循环遍历整个联系人列表（cList），该列表是一个Contacts类型的数组。在每次循环中，使用if语句检查当前遍历到的联系人的电话号码（cList[i].phone）是否与要查找的电话号码（phone）相等。返回值-如果找到了匹配的电话号码，则立即通过returni;语句返回当前联系人在数组中的索引（i）。-如果遍历完整个数组都没有找到匹配的电话号码，则执行return-1;表示未找到具有指定电话号码的联系人。/*顺序查找*/

public

intseqSearchByPhone(int

phone){

for(int

i=0;i<cList.length;i++)

if(phone==cList[i].phone)

return

i;

return-1;}步骤三：测试顺序查找算法任务实施算法应用public

classTestContactsList{

public

static

voidmain(String[]args){Contacts[]data={

newContacts("铁路服务热线",12306),

newContacts("公共卫生健康热线",12320),

newContacts("旅游服务热线",12301),

newContacts("中国移动客服热线",10086),

newContacts("中国电信服务热线",10000),

newContacts("中国联通服务热线",10010),

newContacts("中国银行服务热线",95566),

newContacts("建设银行服务热线",95533),

newContacts("工商银行服务热线",95588)

};

int

findphone=10086;//指定要查找的电话号码

ContactsListcList=newContactsList(data);

if(cList.seqSearchByPhone(findphone)!=-1)System.out.println("查找号码："+findphone+

"的信息为:"+data[cList.seqSearchByPhone(findphone)]);

else System.out.println("不存在号码："+findphone);}}创建类TestContactsList，在类中调用顺序查找算法seqSearchByPhone，查找关键字10086的电话信息。定义并初始化联系人数组：首先，定义了一个Contacts类型的数组data，并使用多个Contacts对象的实例来初始化这个数组。每个Contacts对象都包含了一个联系人名称和一个电话号码。指定要查找的电话号码：然后，定义了一个整型变量findphone并将其值设置为10086，这是要在联系人列表中查找的电话号码。创建ContactsList对象：接着，创建了一个ContactsList类的实例cList，并将前面定义的联系人数组data作为参数传递给ContactsList的构造方法。这样，cList对象就包含了整个联系人列表。查找电话号码：通过调用cList对象的seqSearchByPhone方法，并传入要查找的电话号码findphone，该方法会返回一个整数。这个整数是匹配电话号码在联系人数组中的索引。如果电话号码不存在于数组中，该方法会返回-1。处理结果：-如果返回的索引不是-1（即找到了匹配的电话号码），则通过索引从data数组中检索出对应的Contacts对象，并将其信息（这里直接使用了Contacts对象的toString方法）打印出来。-如果返回的索引是-1（即没有找到匹配的电话号码），则打印出一条消息表示该电话号码不存在。步骤四：分析顺序查找算法性能任务实施平均查找长度的概念

在查找的过程中，一次查找的长度是指需要比较的关键字的次数，而平均查找长度则是所有查找过程中进行关键字比较的次数的平均值。

平均查找长度ASL(AverageSearchLength)定义为：

其中：

①n是结点的个数；

②pi是查找第i个结点的概率。若不特别声明，认为每个结点的查找概率相等，

即：pl=p2…=pn=1/n

③ci是找到第i个结点所需进行的比较次数。平均查找长度通常用来作为衡量一个查找算法效率优劣的标准。顺序查找的性能

假设顺序表中每个记录的查找概率相同，即pi=1/n(1≤i≤n)，查找表中第i个记录所需进行比较的次数Ci=i，则顺序查找算法查找成功时的平均查找长度为：

在等概率情况下，成功的平均查找长度为：(n+…+2+1)/n=(n+1)/2

即查找成功时的平均比较次数约为表长的一半。

在查找失败时，算法的平均查找长度为ASLsq=虽然顺序查找的效率不高，但在下列两种情况下只能采用顺序查找：

（1）如果顺序表为无序表，那么只能用顺序查找。（2）采用链式存储结构的线性表，只能采用顺序查找。在数据的海洋中，顺序查找如同一盏明灯，照亮前行的道路。它不畏艰难，逐个审视每个元素，直到找到目标。这种坚持和耐心，正是我们在面对挑战时所需要的。顺序查找教会我们，只要不放弃，成功终将到来。任务三

用二分查找技术查找联系人信息学习目标理解二分查找的基本思想能实现二分查找的算法12

在理解二分查找基本思想的基础上，将电话号码作为关键字，用二分查找技术查找手机通讯录中联系人的信息。任务描述步骤一：理解二分查找算法任务实施二分查找查找又称折半查找，是一种效率较高的查找方法。二分查找要求线性表是有序表，即表中结点按关键字有序排列，并且要用顺序表作为表的存储结构。基本思想设线性表存储在数组data中,各记录的关键字满足下列条件：data[0].key≤data[1].key≤…data[n-1].key设置三个变量low，high和mid，它们分别指向表的当前待查范围的下界、上界和中间位置。初始时，low=0，high=n-1，设待查数据元素的关键字为key。（1）令mid=(low+high)/2（2）比较key与data[mid].key值的大小，具体情况如下：

data[mid].key=key，则查找成功，结束查找；

data[mid].key<key，表明关键字为key的记录可能位于记录data[mid]的右边，修改查找范围，令下界指示变量low=mid+1，上界指示变量high的值保持不变；

data[mid].key>key，表明关键字为key的记录可能位于记录data[mid]的左边，修改查找范围，令上界指示变量high=mid-1，下界指示变量low的值保持不变。（3）比较当前变量low与high的值，若low≤high，重复步骤(1)和(2)步，若low>high，表明整个查找完毕，线性表中不存在关键字为key的记录，查找失败，返回-1。第1次查找：low=0,high=8,因此mid=(0+8)/2=4，在这个位置上的号码为12306，将12306与10086比较，说明10086只可能排在mid的左边，所以令high=mid-1=3；第2次查找：low=0,high=3因此mid=(0+3)/2=1，在这个位置上的数字为10010，将10010与10086比较，说明10086只可能排在mid的右边，所以令low=mid+1=2；第3次查找：low=2,high=3,因此mid=(2+3)/2=2，在这个位置上的数字为10086，查找成功，返回下标2。查找的电话号码为10086的联系人在通讯录中的位置。步骤二：实现二分查找算法任务实施算法实现在ContactList中，编写二分查找算法binSearchByPhone，查找关键字为电话phone的联系人在通讯录中的位置。排序：首先，调用Arrays.sort(cList);对数组cList进行排序。然而，Arrays.sort方法需要传入一个实现了Comparable接口的数组或者一个比较器（Comparator）。Contacts类实现了Comparable接口，并且compareTo方法基于phone字段比较了两个Contacts对象。二分查找：

（1）初始化：定义搜索的初始范围-low设置为数组的起始索引0。-high设置为数组的结束索引cList.length-1。（2）循环条件：

满足条件high>=low进行遍历-计算中间索引：mid=(low+high)/2，这将当前搜索范围分成两半，并尝试在中间点找到目标值。（3）比较和调整范围：-比较cList[mid].phone与要查找的电话号码phone。

-如果它们相等，说明找到了目标，返回mid。-如果cList[mid].phone小于phone，则说明目标在mid的右侧，将low更新为mid+1以缩小搜索范围到右半部分。-如果cList[mid].phone大于phone，则说明目标在mid的左侧，将high更新为mid-1以缩小搜索范围到左半部分。（4）重复：

-重复步骤3和4，直到找到目标值或搜索范围变得无效。返回值：如果找到了匹配的电话号码，在循环中己返回该电话号码在数组中的索引。如果遍历完整个可能的搜索范围都没有找到匹配的电话号码，则返回-1。/*二分查找*/

public

intbinSearchByPhone(int

phone){

//对数组元素进行排序

Arrays.sort(cList);

int

low=0,high=cList.length-1,mid;

while(high>=low){

mid=(low+high)/2;

if(phone==cList[mid].phone){

return

mid; }else

if(phone>cList[mid].phone)

low=mid+1;

else

high=mid-1;}

return-1;}步骤三：测试二分查找算法任务实施算法应用public

classTestContactsList{

public

static

voidmain(String[]args){Contacts[]data={

newContacts("铁路服务热线",12306),

newContacts("公共卫生健康热线",12320),

newContacts("旅游服务热线",12301),

newContacts("中国移动客服热线",10086),

newContacts("中国电信服务热线",10000),

newContacts("中国联通服务热线",10010),

newContacts("中国银行服务热线",95566),

newContacts("建设银行服务热线",95533),

newContacts("工商银行服务热线",95588)

};

int

findphone=10086;//指定要查找的电话号码

ContactsListcList=newContactsList(data);

if(cList.binSearchByPhone(findphone)!=-1)System.out.println("查找号码："+findphone+

"的信息为:"+data[cList.binSearchByPhone(findphone)]);

else System.out.println("不存在号码："+findphone);}}创建类TestContactsList，在类中调用二分查找算法binSearchByPhone，查找关键字10086的电话信息。定义并初始化联系人数组：首先，定义了一个Contacts类型的数组data，并使用多个Contacts对象的实例来初始化这个数组。每个Contacts对象都包含了一个联系人名称和一个电话号码。指定要查找的电话号码：然后，定义了一个整型变量findphone并将其值设置为10086，这是要在联系人列表中查找的电话号码。创建ContactsList对象：接着，创建了一个ContactsList类的实例cList，并将前面定义的联系人数组data作为参数传递给ContactsList的构造方法。这样，cList对象就包含了整个联系人列表。查找电话号码：通过调用cList对象的binSearchByPhone

方法，并传入要查找的电话号码findphone，该方法会返回一个整数。这个整数是匹配电话号码在联系人数组中的索引。如果电话号码不存在于数组中，该方法会返回-1。处理结果：-如果返回的索引不是-1（即找到了匹配的电话号码），则通过索引从data数组中检索出对应的Contacts对象，并将其信息（这里直接使用了Contacts对象的toString方法）打印出来。-如果返回的索引是-1（即没有找到匹配的电话号码），则打印出一条消息表示该电话号码不存在。步骤四：分析二分查找算法性能任务实施分析二分查找算法性能

二分查找过程通过可用一个二叉判定树来表示：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为二叉判定树二分查找通常可用一个二叉判定树表示。即若用查找区间二叉树的构造序列[low,high]的构造二叉判定树，那么二叉判定树二叉树的根结点的存储值为序列[low,high]的中间元素mid，而二叉树的其左子树构建序列为用查找区间[low,mid-1]的构建的二叉判定树，右子树用查找区间[mid+1,high]的构建的二叉判定树，依此类推。查找给定值key的过程，就是逐一自上而下遍历二叉树根结点的过程。从判定树上可见，查找10086的过程恰好是走了一条从根结点到结点②的路径，和给定值进行比较的关键字为该路径上的结点数或结点②在判定树上的层次数。类似地，找到有序表中任一记录的过程就是走了一条从根结点到该记录相应的结点的路径，和给定值进行比较的关键字个数恰为该结点在判定树上的层次数。因此二分查找成功时进行比较的关键字个数最多不超过树的深度。例如查找关键字10086的记录所走的路径为④→①→②，所作的比较次数为3。

假设有序表中记录的个数恰好为：n=20+21+…+2k-1=2k-1二叉判定树的深度为k=log2(n+1)的满二叉树。在树的第i层上总共有2i-1个记录结点，查找该层上的每个结点需要进行i次比较。因此当表中的每个记录的查找概率相等时，查找成功的平均查找长度为：ASLbins=在有序的数字森林中，二分查找如同智慧的猎人，每次选择中间的路径，迅速缩小搜寻范围。它以高效的姿态，将复杂问题简化，让数据的奥秘在对数时间里迎刃而解。任务四

用分块查找技术查找联系人信息学习目标理解分块查找的基本思想能实现分块查找的算法12能用分块查找解决实际的问题3

在理解分块查找算法基本思想的基础上，将电话号码作为关键字，用分块查找技术查找手机通讯录中联系人的信息。任务描述步骤一：理解分块查找的基本思想任务实施二分查找分块查找把顺序表分成若干块，每块包含的若干元素具有具同的特性，用一个关键字识别，各块的关键字互不相同。建立一个索引表保存块元素的索引信息，索引表中的每个元素含有各块的索引关键字及其第一个元素的地址。基本思想图中电话信息表分成三块：100开头的电话号码对应索引表中的关键字100，123开头的电话号码对应索引表中的关键字123，955开头的电话号码对应索引表中的关键字123，实际应用中，还可以分更多的块，如131、132、133、134、135、136、137、138、139等等，也可以按名称的首字母进行分块。查找的电话号码为10086的联系人在通讯录中的位置。在带索引表的顺序表中查找关键字等于key的记录时，需要按如下步骤进行:（1）首先查找索引表，确定待查记录所在块。索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点的位置。（2）在已确定的块中进行顺序查找。当块内的记录是任意排列的，只能用顺序查找。

例如，对于给定的关键字10086，首先截取前三位，分析是否为100，123、955开头，如果不是，没有为它建立分块索引，否则用二分查找法在索引表中查找对应关键字所在顺序表中的下标，索引表中100对应的块的起始位置为3，终止位置为起始位置加上块中元素数量减1。在顺序表中从下标位置3开始查找10086，比较1次后可以定位到其下标为3。步骤二：实现分块查找算法任务实施算法实现在ContactList中，编写分块查找算法blockSearchByPhone，查找的关键字为电话phone的联系人在通讯录中的位置。1、在类ContactList中创建一个内部类,表示索引表结点类型成员变量分析intblockBeginIndex：这个变量用于记录该块在数据结构中的起始下标。它的初始值被显式地设置为-1，这通常表示在构造函数被调用时，块的起始下标尚未确定或尚未分配。在实际应用中，这个值会在后续根据数据结构的组织和分配情况被更新。intblockKey：这个变量是块的关键字或标识符，用于唯一地表示或识别这个块。在构造函数中，这个变量被初始化为传入的参数值，这意味着每个BlockInfo实例都会根据其被创建时传入的blockKey值来唯一标识。intcount：这个变量记录了块中元素的数量。它被初始化为0，表示在创建BlockInfo实例时，块中还没有包含任何元素。随着数据的添加或分配到这个块中，这个值会被相应地更新。构造函数分析publicBlockInfo(intblockKey)这是一个公开的构造函数，它接受一个int类型的参数blockKey，用于初始化BlockInfo实例的blockKey成员变量。同时，构造函数还显式地将blockBeginIndex设置为-1，并将count设置为0，以反映初始状态下块的状态。通过这个构造函数，我们可以创建多个BlockInfo实例，每个实例都代表了一个具有唯一关键字（blockKey）的块，但初始时块的起始下标未知（blockBeginIndex为-1），且块中不包含任何元素（count为0）。//定义一个内部类，表示索引表结点类型static

classBlockInfo{

int

blockBeginIndex;//块的起始下标

int

blockKey;//块中关键字

int

count;//块中元素的数量

publicBlockInfo(int

blockKey){

this.blockBeginIndex=-1;

this.blockKey=blockKey;

this.count=0;}}算法实现2、在类ContactList中编写创建算法getIndexBlock,用于生成分块索引表初始化块数组：创建了一个BlockInfo数组blocks，其中包含三个BlockInfo实例，每个实例的blockKey分别被初始化为100、123和955。遍历cList数组：遍历cList数组中的每个元素。对于每个元素，它执行以下步骤：（1）提取前三位数字：从当前元素的phone属性中提取前三位数字。这是通过将phone转换为字符串，然后截取前三个字符，并再次将其转换回整数来实现的。（2）分组逻辑：使用switch语句根据提取的前三位数字将元素分配到相应的块中。如果前三位数字与某个BlockInfo实例的blockKey相匹配，则执行以下操作：-如果该块的blockBeginIndex尚未设置（即仍为-1），则将其设置为当前元素的索引i，表示这是该块中的第一个元素。-无论blockBeginIndex是否已更新，都将该块的count加一，以记录块中元素的数量。（3）跳过剩余代码：由于continue语句的存在，一旦元素被分配到某个块并更新了计数，switch语句中的剩余case将被跳过，不会执行任何进一步的操作。返回块数组：遍历完成后，方法返回填充了分组信息的blocks数组。此时，blocks数组中的每个BlockInfo实例都将包含有关其对应块的分组信息（即块中第一个元素的索引和块中元素的数量）publicBlockInfo[]getIndexBlock(){BlockInfo[]blocks={newBlockInfo(100),

newBlockInfo(123),newBlockInfo(955)};

for(int

i=0;i<cList.length;i++){

int

tmp=Integer.parseInt(Integer.toString(cList[i].phone).substring(0,3));

switch(tmp){

case100:

if(blocks[0].blockBeginIndex==-1)blocks[0].blockBeginIndex=i;

blocks[0].count++;

continue;

case123:

if(blocks[1].blockBeginIndex==-1)blocks[1].blockBeginIndex=i;

blocks[1].count++;

continue;

case955:

if(blocks[2].blockBeginIndex==-1)blocks[2].blockBeginIndex=i;

blocks[2].count++;

continue;

default:

continue;} }

return

blocks;}算法实现3、在类ContactList中编写二分查找算法binSearchByPhone,查找的关键字为电话phone确定电话号码所属的块：-首先，通过取电话号码phone的前三位数字作为key。-然后，遍历blocks数组，使用顺序查找来找到其blockKey与key相匹配的BlockInfo对象。-如果找到了匹配的BlockInfo对象，则记录其索引blockindex；如果没有找到，则blockindex保持为初始值-1。在指定块中搜索电话号码：-如果blockindex不等于-1（即找到了匹配的块），则在该块中进一步搜索电话号码。-使用blocks[blockindex].blockBeginIndex作为起始索引，并在该索引的基础上，结合块中的元素数量blocks[blockindex].count，来确定搜索的范围。-在这个范围内，顺序遍历cList数组，使用phone==cList[i].phone来检查当前元素是否是我们要找的电话号码。-如果找到了匹配的电话号码，则返回其在cList中的索引i。-如果在指定块中没有找到匹配的电话号码，或者blockindex为-1，则返回-1。public

intblockSearchByPhone(int

phone){

int

blockindex=-1;BlockInfo[]blocks=getIndexBlock();

int

key=Integer.parseInt(Integer.toString(

phone).substring(0,3));

//用顺序查找确定在哪一块

for(int

i=0;i<blocks.length;i++){

if(key==blocks[i].blockKey){

blockindex=i;

break;}}

//用顺序查找在指定块中查找元素

if(blockindex!=-1){

for(int

i=blocks[blockindex].blockBeginIndex;

i<blocks[blockindex].blockBeginIndex+blocks[blockindex].count;i++)

if(phone==cList[i].phone)

return

i;//找到，返回下标

}

return-1;}步骤三：测试分块查找算法任务实施算法应用public

classTestContactsList{

public

static

voidmain(String[]args){Contacts[]data={

newContacts("铁路服务热线",12306),

newContacts("公共卫生健康热线",12320),

newContacts("旅游服务热线",12301),

newContacts("中国移动客服热线",10086),

newContacts("中国电信服务热线",10000),

newContacts("中国联通服务热线",10010),

newContacts("中国银行服务热线",95566),

newContacts("建设银行服务热线",95533),

newContacts("工商银行服务热线",95588)

};

int

findphone=10086;//指定要查找的电话号码

ContactsListcList=newContactsList(data);

if(cList.blockSearchByPhone(findphone)!=-1)System.out.println("查找号码："+findphone+

"的信息为:"+data[cList.blockSearchByPhone(findphone)]);

else System.out.println("不存在号码："+findphone);}}创建类TestContactsList，在类中调用分块查找算法blocknSearchByPhone，查找关键字10086的电话信息。定义并初始化联系人数组：首先，定义了一个Contacts类型的数组data，并使用多个Contacts对象的实例来初始化这个数组。每个Contacts对象都包含了一个联系人名称和一个电话号码。指定要查找的电话号码：然后，定义了一个整型变量findphone并将其值设置为10086，这是要在联系人列表中查找的电话号码。创建ContactsList对象：接着，创建了一个ContactsList类的实例cList，并将前面定义的联系人数组data作为参数传递给ContactsList的构造方法。这样，cList对象就包含了整个联系人列表。查找电话号码：通过调用cList对象的blockSearchByPhone

方法，并传入要查找的电话号码findphone，该方法会返回一个整数。这个整数是匹配电话号码在联系人数组中的索引。如果电话号码不存在于数组中，该方法会返回-1。处理结果：-如果返回的索引不是-1（即找到了匹配的电话号码），则通过索引从data数组中检索出对应的Contacts对象，并将其信息（这里直接使用了Contacts对象的toString方法）打印出来。-如果返回的索引是-1（即没有找到匹配的电话号码），则打印出一条消息表示该电话号码不存在。步骤四：分析分块查找算法性能任务实施分析分块查找算法性能

分块查找的过程分为两部分,一部分是在索引表中确定待查记录所在块；另一部分是在块里寻找待查的记录。因此，分块查找法的平均查找长度是两部分平均查找长度的和，即假定长度为n的顺序表要分成b块，且每块的长度相等，那么有：块长s=n/b。若假定表中各记录的查找概率相等，仅考虑成功的查找，那么每块的查找概率为1/b，块内各记录的查找概率为1/s。当在索引表内对块的查找以及在块内对记录的查找都采用顺序查找时，有：由此可见，分块查找时的平均查找长度不但和表的长度有关，而且和块的长度也有关。当s=时，ASLblocks取得最小值，有分块查找，如同生活中的有序拼图，将复杂数据巧妙分割，每一块独立而有序，查找过程高效而精准。它教会我们在纷繁中寻找规律，以智慧和耐心，将数据的海洋化为有序的港湾。任务五

用归并排序实现商品按价格排序学习目标理解归并排序的思想能用Java语言实现归并排序12

对于大列表数据的排序,一个有效的排序算法是归并排序。类似于快速排序算法，其使用的是分治法来排序。归并排序的基本思想是将两个或两个以上的有序子序列“归并”为一个有序序列。在内部排序中，通常采用的是二路归并排序，即将两个位置相邻的有序子序列“归并”为一个有序序列。本任务使用归并排序方法完成电商网站商品列表按价格排序。任务描述步骤一：用二路归并排序实现商品按价格排序任务实施基本思想用归并排序完成电商网站商品列表按价格排序，10个商品的价格分别为：30,69,59,27,34,49,53,99,89,28图中二路归并排序过程如下所示：第1趟，将列表中的10个元素看成10个有序的子序列，每个子序列的长度为1，然后两两归并，得到5个长度为2的有序子序列。第2趟，将5个有序子序列两两归并，得到2个长度为4和1个长度为2的有序子序列。第3趟，将2个长度为4的有序子序列归并，得到1个长度为8和1个长度为2的有序子序列。第4趟，将长度为8有序子序列和长度为2的有序子序列归并，得到长度为10的一个有序子序列，归并排序结束。归并排序将有n个数据元素的原始序列看作n个有序子序列，每个子序的长度为1，然后从第一个子序列开始，把相邻的子序列两两合并后排序，得到n/2个长度为2或1的有序子序列（当子序列的个数为奇数时，最后一组合并得到的序列长度为1），把这一过程称为一次归并排序，对一次归并排序的n/2个子序列采用上述方法继续顺序成对归并排序，如此重复，当最后得到长度为n的一个子序列时，该子序列便是原始序列归并排序后的有序序列。算法实现对存储Product对象的数组r进行归并排序，代码按对象的属性price值对Product对象进行升序排序。通过两个方法：mergeSort和merge，共同实现了归并排序算法。mergeSort方法：这是归并排序的启动点。它初始化归并的“增量”k为1，并在一个循环中逐步增加k，每次翻倍，直到k大于或等于数组长度。在每次循环中，它调用merge方法来合并相邻的、长度为k的子序列。merge方法：这个方法负责合并两个已排序的子序列。然而，当前实现中的merge方法并没有直接使用其参数len来正确地控制合并过程。1.初始化变量：

-m：临时顺序表的起始位置，用于记录合并后数组的当前位置。

-l1和h1：分别表示第一个有序表的起始位置和结束位置。

-l2和h2：分别表示第二个有序表的起始位置和结束位置。

-i和j：分别用于遍历第一个和第二个有序表。2.创建临时数组：

-tmp：用于临时存储合并后的有序数组，其长度与原数组r相同。public

voidmergeSort(){

int

k=1;//归并增量

while(k<r.length){

merge(k);

k*=2;

}

}public

voidmerge(int

len){

int

m=0;//临时顺序表的起始位置

int

l1=0;//第1个有序表的起始位置

int

h1;//第1个有序表的结束位置

int

l2;//第2个有序表的起始位置

int

h2;//第2个有序表的结束位置

int

i=0;

int

j=0;

//临时表，用于临时将两个有序表合并为一个有序表

Product[]tmp=newProduct[r.length];…………}算法实现3.归并处理：

-使用while循环遍历两个有序表，每次循环处理两个有序表中的一部分元素。

-l1+len<r.length确保在处理过程中不会超出数组r的边界。

-l2和h2分别计算出第二个有序表的起始和结束位置。

-在while循环内部，通过比较两个有序表当前元素的price属性，决定将哪个元素放入临时数组tmp中。

-如果第一个有序表的元素较小，则将其放入tmp，并移动i指针。

-如果第二个有序表的元素较小，则将其放tmp，并移动j指针。

-当一个有序表的所有元素都处理完毕后，使用另一个while循环将剩余的元素直接复制到tmp中。4.更新起始位置：

-每次处理完两个有序表的一部分后，更新l1为当前处理完的第二个有序表的结束位置加一，以便下次循环处理下一个子数组。5.复制临时数组到原数组：

-最后，使用一个for循环将临时数组tmp`中的元素复制回原数组r，确保原数组r中的元素是有序的。

整个归并操作确保了数组r中的元素按照price属性从小到大排序。这个方法是归并排序算法的核心部分，通过递归地将数组分成更小的部分，然后合并这些部分以形成一个完全有序的数组。public

voidmerge(int

len){…………

while(l1+len<r.length){

l2=l1+len;//第2个有序表的起始位置

h1=l2-1;//第1个有序表的结束位置h2=(l2+len-1<r.length)?l2+len-1:r.length-1;

i=l1;

j=l2;while((i<=h1)&&(j<=h2)){

if(r[i].price<=r[j].price){

tmp[m++]=r[i++];}

else{

tmp[m++]=r[j++];}}

while(i<=h1){

tmp[m++]=r[i++];}

while(j<=h2){

tmp[m++]=r[j++];}

l1=h2+1;}

i=l1;

//原顺序表中还有记录没有排序完

while(i<r.length){

tmp[m++]=r[i++];}

//临时顺序表中的记录复制到原顺序表，使原顺序表中的记录有序

for(i=0;i<r.length;++i){

r[i]=tmp[i];}}算法实现public

classTestProductSort{

public

static

voidmain(String[]args){Product[]plist={newProduct("inphic","PB1P",20,30),

newProduct("logitech","M220",100,69),

newProduct("rapoo","M300G",20,59),

newProduct("inphic","PW1h",50,27),

newProduct("mi","Lite2",200,34),

newProduct("logitech","M187P",1,49),

newProduct("inphic","DR01",2,53),

newProduct("logitech","M330",100,99),

newProduct("dareu","EM915",50,89),

newProduct("inphic","PM6",100,28)};System.out.println("排序前的商品列表：");

for(int

i=0;i<plist.length;i++){System.out.println(plist[i]);}ProductSortpsort=newProductSort(plist);

psort.mergeSort();System.out.println("排序后的商品列表：");

for(int

i=0;i<plist.length;i++){System.out.println(plist[i]);}}}创建一个类TestProductSort，调用ProductSort类的归并排序法mergeSort()t实现商品列表按价格排序。创建商品列表：首先，创建了一个Product对象的数组plist，并初始化了10个商品对象，每个对象都被赋予了品牌名、型号、评论数和价格。打印排序前的商品列表：然后，通过一个循环遍历plist数组，并打印出每个商品对象的字符串表示（Product类重写了toString()方法以返回包含品牌名、型号、评数论和价格的字符串）。这样，用户可以看到排序前商品列表的顺序。排序商品列表：接着，创建了一个ProductSort类的实例psort，并将plist数组作为参数传递给它的构造函数。然后，调用psort的mergetSort()方法来对商品列表进行排序。打印排序后的商品列表：最后，再次通过一个循环遍历plist数组，并打印出每个商品对象的字符串表示。此时，由于已经调用了mergeSort()方法对商品列表进行了排序，所以打印出的商品列表将按照价格从低到高的顺序排列。步骤二：分析二路归并排序算法的时间复杂度任务实施二路归并排序算法的时间复杂度对于n个记录的顺序表，将这n个记录看作叶子结点，若将两两归并生成的子表看作它们的父结点，则归并过程对应于由叶子结点向根结点生成一棵二叉树的过程。所以，归并趟数约等于二叉树的高度减1，即log2n，每趟归并排序记录关键码比较的次数都约为n/2，记录移动的次数为2n（临时顺序表的记录复制到原顺序表中记录的移动次数为n）。因此，二路归并排序的时间复杂度为O(nlog2n)。归并排序如同心灵的净化，将杂乱无章的数据分解、重组，最终呈现出有序的美丽。每一次分割与合并，都是对问题的深刻理解与智慧的体现，让我们在数据的海洋中找到清晰的路径。任务六

用哈希查找技术查找联系人信息学习目标理解哈希查找的基本思想能实现哈希查找的算法12能用哈希查找算法管理通讯录3

在用线性查找的过程中需要依据关键字进行若干次的比较判断，确定数据集合中是否存在关键字等于某个给定关键字的记录以及该记录在数据表中的位置,查找的效率与比较的次数密切相关。在查找时需要不断进行比较的原因是建立数据表时，只考虑了各记录的关键字之间的相对大小，记录在表中的位置和其关键字无直接关系。如果在记录的存储位置及其关键字之间建立某种直接关系，那么在进行查找时，就无须比较或只做很少的比较就能直接由关键字找到相应的记录，哈希（Hash）表正是基于这种思想。本任务在理解哈希查找基本思想的基础上，将电话号码作为关键字，用哈希查找技术查找手机通讯录中联系人的信息。任务描述步骤一：理解哈希查找的基本思想任务实施哈希表的基本概念哈希的基本原理是将给定的键值转换为偏移地址来检索记录。键转换为地址是通过一种关系（公式）来完成的，这就是哈希（散列）函数。设置一个长度为m的表T，用一个函数将数据集合中n个记录的关键字尽可能唯一地转换成0~m-1范围内的数值，即对于集合中任意记录的关键字Ki，

有：0≤H(Ki)≤m-1(0≤i<n)函数H——散列函数或哈希（Hash）函数；H(K)——散列地址；若K1≠K2，但H(K1)=H(K2)这时我们称发生了冲突。K1和K2称为同义词。用哈希函数h将关键字映射到哈希表示意图如果要散列的键是3、4、8和10，，散列值分别为3、0、0、2，则产生冲突。哈希冲突：两个不同的关键字，由于哈希函数值相同，而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞，发生冲突的两个关键字称为该哈希函数的同义词(Synonym)。(a)无冲突假设散列函数是：h(k)=key%4对于键3、5、8和10使用该函数，散列值分别为3、1、0、2，没有发生冲突。(b)产生冲突尽管冲突现象是难免的，但还是希望能找到尽可能产生均匀映射的哈希函数，从而降低冲突的概率，另外当冲突发生时，还必须有相应的解决冲突的方法。因此，构造哈希函数和建立解决冲突的方法是建立哈希表的两大任务。哈希表的基本概念构造哈希函数将一组关键字(0100，0110，1010，1001，0111)平方后得：

(0010000，0012100，1020100，1002001，0012321)若取表长为1000，则可取中间的三位数作为散列地址集：(100，121，201，020，123)。intHash(intkey){//假设key是4位整数

key*=key；key/=100；//先求平方值，后去掉末尾的两位数

returnkey％1000；//取中间三位数作为散列地址返回

}平方取中法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为哈希函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。哈希函数代码如下所示：构造哈希函数有一组关键字(36475611，47566933，75669353，34547579，46483499)，哈希表的大小是43，则上述键的地址是：

36475611%43=147566933%43=3275669353%43=1734547579%43=3