Python数据结构与算法-实训指导书6-搜索算法 附参考答案

《《Python数据结构与算法》课程实训任务书实训6搜索算法【实训目的】通过对商品库存管理系统的开发，将所学的搜索算法知识应用于实际问题的解决中，使学生能够：理解和掌握如何根据不同的应用需求选择合适的数据结构（如哈希表和列表）和搜索算法（如线性搜索、二分查找、插值查找和斐波那契查找）。实践搜索算法的编程实现，加深对算法逻辑和性能特性的理解。通过性能测试和比较分析，学会如何评价不同搜索算法的效率和适用性。培养解决实际问题的能力，提升编程技能和算法应用的实践经验。【实训场地】××机房（××实训室）【实训条件】硬件设备：台式电脑，软件设备：Pycharm，word或wps【实训任务】实训任务：商品库存管理系统题目描述：你作为一名软件工程师，受雇于一家电商公司，负责开发一个商品库存管理系统，以帮助库存管理员和销售人员更有效地管理和查询商品库存信息。商品采用面对对象设计，具体定义如下：classProduct:def__init__(self,name,quantity):=name#商品名称self.quantity=quantity#库存量现有几种实现方案可供选择：使用哈希表作为数据结构实现商品库存管理。（1）实现一个哈希表类，包括哈希函数设计、冲突处理、插入、查找和删除等方法。然后利用哈希表作为数据结构实现商品库存管理系统，将商品信息存储在哈希表中，允许通过哈希表对商品进行增删改查。使用列表作为数据结构，并使用以下的搜索方式作为查询算法。（1）线性搜索：实现一个函数，接收目标商品名称作为输入，在商品列表中进行线性搜索，返回目标商品的库存量。如果未找到目标商品，则返回-1。（2）二分查找：实现一个函数，接收目标商品名称作为输入，在有序商品列表中进行二分查找，返回目标商品的库存量。如果未找到目标商品，则返回-1。（3）插值查找：实现一个函数，接收目标商品名称作为输入，在有序商品列表中进行插值查找，返回目标商品的库存量。如果未找到目标商品，则返回-1。（4）斐波那契查找：实现一个函数，接收目标商品名称作为输入，在有序商品列表中进行斐波那契查找，返回目标商品的库存量。如果未找到目标商品，则返回-1。上述提到的有序商品列表式基于商品名称（字符串）进行比较字典序差距的，比较算法参考实现如下：defget_string_difference(str1,str2):"""用于比较字符串str1和str2的字典序差距:paramstr1::paramstr2::return:字典序差距"""#找出两个字符串中较短的长度min_length=min(len(str1),len(str2))#遍历字符串，找到第一个不相等的字符位置foriinrange(min_length):ifstr1[i]!=str2[i]:returnord(str1[i])-ord(str2[i])#如果前面的字符都相等，那么返回长度差returnlen(str1)-len(str2)请你分别实现上述两种以分别以哈希表和列表作为数据结构的实现方案，并对比分析其中的优缺点。参考答案1（哈希表作为数据结构）：classInventoryManagementSystemByHashTable:def__init__(self,size):#初始化哈希表self.size=sizeself.table=[[]for_inrange(size)]defhash_func(self,key):#哈希函数returnsum(ord(char)forcharinkey)%self.sizedefinsert(self,key,value):#插入键值对到哈希表index=self.hash_func(key)self.table[index].append({"name":key,"quantity":value})defsearch(self,key):#在哈希表中搜索指定键的值index=self.hash_func(key)foriteminself.table[index]:ifitem["name"]==key:returnitem["quantity"]returnNonedefdelete(self,key):#从哈希表中删除指定键的值index=self.hash_func(key)fori,iteminenumerate(self.table[index]):ifitem["name"]==key:delself.table[index][i]returnif__name__=="__main__":#测试哈希表ht=InventoryManagementSystemByHashTable(10)products=[Product("apple",10),Product("banana",20),Product("grape",15),Product("orange",25),Product("pear",30)]forproductinproducts:ht.insert(,product)#查询操作result=ht.search("banana")ifresult:print("banana库存量：",result.quantity)参考答案2（列表作为数据结构）：classInventoryManagementSystem:def__init__(self):#初始化商品列表,按商品名称字典序升序ducts=[Product("apple",10),Product("banana",20),Product("grape",15),Product("orange",25),Product("pear",30)]deflinear_search(self,target):#线性搜索算法forproductinducts:if==target:#检查商品名称是否与目标相匹配returnproduct.quantity#返回商品库存量return-1#如果未找到目标商品，则返回-1defbinary_search(self,target):#二分查找算法low,high=0,len(ducts)-1#初始化查找范围whilelow<=high:mid=(low+high)//2#计算中间索引ifducts[mid].name==target:#如果目标商品在中间位置returnducts[mid].quantity#返回商品库存量elifducts[mid].name<target:#如果目标商品在右半部分low=mid+1#调整查找范围else:high=mid-1#否则在左半部分return-1#如果未找到目标商品，则返回-1definterpolation_search(self,target):#插值查找算法low,high=0,len(ducts)-1#初始化查找范围whilelow<=highandducts[low].name<=target<=ducts[high].name:#计算插值位置(基于字典序差距比例进行计算)mid=low+(high-low)*get_string_difference(target,ducts[low].name)//\get_string_difference(ducts[high].name,ducts[low].name)ifducts[mid].name==target:#如果目标商品在插值位置returnducts[mid].quantity#返回商品库存量elifducts[mid].name<target:#如果目标商品在右半部分low=mid+1#调整查找范围else:high=mid-1#否则在左半部分return-1#如果未找到目标商品，则返回-1deffibonacci_search(self,target):#斐波那契查找算法fib_m_minus_2,fib_m_minus_1=0,1#初始化斐波那契数列fib_m=fib_m_minus_1+fib_m_minus_2whilefib_m<len(ducts):fib_m_minus_2=fib_m_minus_1fib_m_minus_1=fib_mfib_m=fib_m_minus_1+fib_m_minus_2offset=-1#初始化偏移量whilefib_m>1:i=min(offset+fib_m_minus_2,len(ducts)-1)ifducts[i].name<target:#如果目标商品在右半部分fib_m,fib_m_minus_1=fib_m_minus_1,fib_m_minus_2#调整斐波那契数列fib_m_minus_2=fib_m-fib_m_minus_1#更新偏移量offset=ielifducts[i].name>target:#如果目标商品在左半部分fib_m=fib_m_minus_1#调整斐波那契数列fib_m_minus_1=fib_m_minus_2fib_m_minus_2=fib_m-fib_m_minus_1else:returnducts[i].quantity#目标商品与当前商品名称匹配，返回商品库存量iffib_m_minus_1andducts[offset+1].name==target:#如果目标商品在右边界处returnducts[offset+1].quantity#返回右边界return-1#如果未找到目标商品，则返回-1if__name__=="__main__":ims=InventoryManagementSystem()#测试搜索算法print("grape库存量：",ims.linear_search("grape"))print("banana库存量：",ims.binary_search("banana"))print("orange库存量：",erpolation_search("orange"))print("pear库存量：",ims.fibonacci_search("pear"))【实训注意】×××××（清晰列出本次实训操作的注意点，若有安全方面的注意点，务必重点列出）【拓展任务】拓展任务:算法优化比较研究任务描述：为了帮助大家深入理解搜索算法的原理和性能特点，期望通过比较不同搜索算法的性能，学