第九章查找-欢迎光临青岛科技大学信息科学技术学院

格式：docx
大小：64.87 KB
文档页数：7

下载文档原格式

基于嵌入式Linux下的USB3.0驱动程序开发方法研究

求。ＵＢ．信标准和协议的推出必将带动基于Ｓ３０通ＵＢ．口设备的大量生产。Ｓ３０接对于每一种ＵＢ．品Ｓ３０产在嵌入式应用中都必须开发其相应的设备驱动程序才可使该产品正常工作。因此，嵌入式系统工程师们对于
或者加载设备驱动时调用，其主要负责检测所需驱动的硬件设备是否存在或是否能正常工作。如果该设备正常，则对这个设备及其相关的驱动程序需要的软件状态进行初始化。驱动程序所提供的与设备的打开、释
１２Ｌｎｘ驱动．ｉｕ
驱动程序是Ｌｎｘ内核的重要组成部分，以看作ｉｕ可
是应用程序和物理设备之间的一个软件层，由设备驱动程序来完成操作系统与硬件设备之间的交互。对于嵌入式开发而言由于没有通用的驱动程序，因而驱动程序开发便成为嵌入式系统设计过程的一个重要环节。驱动程序包括配置初始化子程序和Ｉ／Ｏ请求子程序。配置初始化子程序在初始化时被调用一次，０请Ｉ／求子程序的调用通过系统调用或硬件中断信号来触
统和用户应用程序三部分。嵌入式Ｌｎｘ内核包含ｉｕ
个设备驱动程序后，用户可以动态地将该设备驱动
口函数为ｉｉｍｄｌ（和ｃｅｎｐｍｄｌ（。除此之外ｎｔｏｕｅ）ｌｕｏｕｅ）＿ａ
程序加载到内核中或从内核中卸载。加载和卸载的入
执行程序。
对于设备的每一种操作设备驱动程序中都包含其相应
的人口函数。字符型和块设备驱动程序中包括打开设
备函数ｏｅ（、ｐｎ）关闭设备函数ｃｓ（、ｌｅ）读数据函数ｒｄｏｅａ（、）写数据函数ｗｉ（和Ｉｒｅ）／ｔ０控制函数ｉｔ）ｏｌ等。ｃ（

C语言程序设计实验指导书【范本模板】

青岛科技大学信息科学技术学院C语言程序设计实验指导书目录实验1 C语言入门及选择结构 0实验1.1 Visual C++6。

0开发环境 0实验1.2 C程序快速入门 (7)实验1.3算术运算与赋值运算 (11)实验1。

4逻辑运算及if语句 (17)实验1.5 switch选择结构 (23)实验2循环结构及数组（共8学时） (27)实验2.1 循环结构（2学时） (27)循环结构程序设计补充 (32)实验2.2数组一：一维数组 (36)实验2。

3数组二：二维数组 (43)实验2.4数组三：字符数组 (45)实验3:函数与自定义数据类型 (49)实验3。

1函数一：函数的定义、调用和声明 (49)实验3。

2函数二：函数的参数传递2 (55)实验3。

3函数三:函数的嵌套和递归2 (57)实验3.4 自定义数据类型（2学时） (59)实验4：指针（共6学时） (61)实验4。

1指针一：指针的定义及运算 (61)实验4。

2指针二:指向数组的指针 (67)实验4.3指针三:用指针操作字符串2 (71)实验1 C 语言入门及选择结构实验1.1 Visual C++6.0开发环境一、实验目的1。

熟悉C 语言的系统环境,掌握在集成环境中编辑、编译、连接和运行C 语言程序的方法。

2. 掌握C 语言源程序的结构特点与书写规范. 二、实验学时数2学时三、实验步骤及任务（一） VC++6。

0集成环境（1）运行VC++6。

0a.双击桌面上的VC++6。

0快捷方式，运行VC++6。

0。

b 。

双击"C ：\Microsoft Visual Studio\Common\MSDev98\Bin\MSDEV 。

EXE"，运行VC++6.0. (2）认识VC++6。

0标题栏的左侧显示当前的文件名，右侧有最小化，最大化和关闭三个按钮。

菜单栏包含了开发环境中几乎所有的命令,其中一些常用的命令还被排列在工具栏中。

工具栏上的按钮提出和一些菜单命令相对应，提供了经常使用的命令的一种快捷方式。

LM-UNet:横向MLP用于增强U-Net的医学图像分割

LM-UNet：横向MLP用于增强U-Net的医学图像分割邱海韬;史操【期刊名称】《计算机系统应用》【年(卷),期】2024(33)5【摘要】卷积神经网络(CNN)作为医学图像分割领域中U-Net基线网络的重要组成部分,其主要作用是处理局部特征信息之间的关系.而Transformer是一种能够有效强化特征信息之间的远距离依赖关系的视觉模型.目前的研究表明,结合Transformer和CNN可以在一定程度上提高医学图像分割的准确性.但是,由于医学图像的标注数据较少,而且训练Transformer模型需要大量数据,这使得Transformer模型面临耗时长和参数量大的挑战.基于这些考虑,本文在UNeXt模型的基础上,结合多尺度混合MLP和CNN,提出了一种新型的基于混合MLP的医学图像分割模型——LM-UNet.这种模型能够有效地增强局部与全局信息之间的联系,并加强特征信息间的融合.在多个数据集上的实验表明,LM-UNet模型在皮肤数据集上的分割性能明显提升,平均Dice系数达到92.58%,平均IoU系数达到86.52%,分别比UNeXt模型提高了3%和3.5%.在软骨和乳腺数据集上的分割效果也有显著提升,平均Dice系数分别比UNeXt提高了2.5%和1.0%.因此,LM-UNet 模型不仅提高了医学图像分割的准确性,还增强了其泛化能力.【总页数】8页(P110-117)【作者】邱海韬;史操【作者单位】青岛科技大学信息科学技术学院【正文语种】中文【中图分类】TP3【相关文献】1.特征重加权U-Net超声图像分割的骨结构重建与增强现实显示2.用于肺部肿瘤图像分割的跨模态多编码混合注意力U-Net3.融合边缘增强注意力机制和U-Net 网络的医学图像分割4.基于U-Net网络的医学图像分割研究综述5.改进U-Net 的多级边缘增强医学图像分割网络因版权原因，仅展示原文概要，查看原文内容请购买。

关于若干倍图的关联邻点可区别边全染色

２１００年３月
天水师范学院学报
ＪｕｎｌｆｉｎｈｉｏｍａｉｅｓｔｏｒａａｓｕｒｌｏＴＮＵｎｖｒｉｙ
Ｍａ．２０ｒ，０１Ｖｏ＿０Ｎｏ２ｌ．３
第３０卷第２期
关于若干倍图的关联邻点可区别边全染色
全染色等都是十分困难的问题．至今文献甚少．此在
基础之上．一步提出了新染色概念．的关联邻点进图
㈣＝Ｉ１，ｎ，）｛＝，，ｎ１；｛ｉ， …，ｌ＝２Ｅ＝ｕＩ１ …，－｝＋ｉ２
记ｎ圈Ｃ为阶
杨晓亚，随义王三福．杨一，
（．１青岛科技大学信息科学技术学院，山东青岛２６６；．６０１２天水师范学院数学与统计学院，甘肃天水７１０）４０１
摘要：用关联邻点可区别边染色，出了路、、、、应给圈星扇轮及完全图倍图的关联邻点可区别边全染色数
（＝Ｉ１一凡ｉ，＝２｝
记ｎ１星５为＋阶
＝ｕｉ１一ｎ１ｕ｛ｌ｛－，｝ＵＵＵＩ２＝－小
（（ｉ１，ｎ，（ｎ｛ｏ，＝，，凡．．＝Ｉ， …，｝Ｃ）ｕｌ１ …，）Ｓ＝２Ｅ＝ｕｉ２
（），２ＶＹＷ∈ｅｃ， ≠ （）Ｕ “ ≠厂ｖ，）Ｉｗ）（Ｃｕ ≠ｃｖ，中ｃｕ＝厂Ｍ）（）ｖ∈ （）（其）（｛（）Ｕｌ）ｕ

青岛科技大学本科教学质量报告

强化内涵突出特色系统建设全面提高本科教学水平与人才培养质量——青岛科技大学2012年本科教学质量报告中国青岛二〇一二年十二月目录第一部分第一部分学校概况………………………………………………… （1）第二部分第二部分本科人才培养基本情况…………………………………（4） 2.1人才培养理念及人才培养理念及目标目标......................................................（4） 2.2本科专业设置...............................................................（4） 2.3 2012年本科生源质量 (6)第三部分师资与教学条件................................................（7） 3.1 师资数量师资数量与与结构.........................................................（7） 3.2 教学条件..................................................................（8）第四部分本科教学质量内涵建设与成效 (10)4.1 专业建设成效显著专业建设成效显著，，人才培养模式不断创新.....................（10） 4.2 大力推进大力推进师德教风建设师德教风建设 ...............................................（11） 4.3 构建了本科教学质量自我评估系统 ................................（12） 4.4 不断不断健全健全健全完善完善完善教学质量监教学质量监教学质量监控与保障体系控与保障体系............................（14） 4.5 重心下移重心下移，，丰富丰富完善完善完善二级学院本科教学考核二级学院本科教学考核.....................（15） 4.6 优质课程资源群收效显著优质课程资源群收效显著，教材建设教材建设教材建设取得突破取得突破..................（16） 4.7 体育课程建设成效突出体育课程建设成效突出，，高水平运动队成绩优异高水平运动队成绩优异 ............（17） 4.8 教学研究扎实开展教学研究扎实开展，，本科教学工程成绩显著 (17)第五部分本科教学效果 (19)5.1 课堂课堂、、实验实验、、实习教学效果优良 (19)5.2 各类学科竞赛屡创佳绩................................................（19） 5.3 毕业及就业情况毕业及就业情况好好 (20)第六部分办学特色 (22)6.1 学科特色 .............................................................（22） 6.2 人才培养人才培养特色特色 ........................................................（23） 6.3 政产学研政产学研合作特色合作特色.................................................. （23） 6.4 国际化国际化教育特色教育特色 (25)第七部分今后工作重点……………………………………… （27） 7.1 牢固树立以提高质量为核心的教育发展观牢固树立以提高质量为核心的教育发展观，，进一步强化教学工作进一步强化教学工作中心地位............................................................ （27） 7.2 进一步加强高水平师资队伍建设....................................（27） 7.3 坚持坚持走内涵发展走内涵发展走内涵发展、、特色发展之路特色发展之路，，创建省级特色名校 (27)第一部分学校概况青岛科技大学位于美丽的海滨城市青岛，是山东省重点建设的大学，是一所以工为主，理、工、文、经、管、医、法、艺等学科协调发展，以材料学、化学工程、应用化学、机械工程、自动化、信息与计算机为特色学科的多科性大学。

基于多层次的海洋生物分类

基于多层次的海洋生物分类
赵东;程远志
【期刊名称】《计算机系统应用》
【年(卷),期】2024(33)4
【摘要】本文提出了一种多层次海洋生物分类方法.海洋生物种类繁多,且同门类生物具有较强的类间相似性,而不同门类生物具有较大的差异.我们利用物种间的相似性,帮助网络学习生物先验知识,设计出了一种多层次分类方法.设计了C-MBConv 模块,并结合多层次分类方法改进了EfficientNetV2网络架构,改进后的网络架构称为CMEfficientNetV2.我们的实验表明CM-EfficientNetV2比原网络EfficientNetV2有着更高的准确率,在南麂列岛潮间带海洋生物数据集上准确率提高了1.5%,在CIFAR-100上准确率提高了2%.
【总页数】9页(P226-234)
【作者】赵东;程远志
【作者单位】青岛科技大学信息科学技术学院;哈尔滨工业大学计算机科学与技术学院
【正文语种】中文
【中图分类】TP3
【相关文献】
1.基于多层次分类策略的非特定人人脸表情分类识别
2.基于卷积神经网络的海洋生物图像分类方法研究
3.基于多层次特征的高分影像海岸带地物分类
因版权原因，仅展示原文概要，查看原文内容请购买。

青岛科技大学研究生院官网青岛科技大学研究生院：山东青岛科技大学2021考研调剂信息

青岛科技大学研究生院官网|青岛科技大学研究生院：山东青岛科
技大学2021考研调剂信息
专业代码
专业名称
085216
化学工程（专业学位）
085235
制药工程（专业学位）
085238
生物工程（专业学位）
085204
材料工程（专业学位）
085201
机械工程（专业学位）
085204
材料工程（专业学位）
085206
动力工程（专业学位）
085210
控制工程（专业学位）
085216
化学工程（专业学位）
085238
生物工程（专业学位）
085204
材料工程（专业学位）
085239
项目管理（专业学位）
125100
工商管理硕士（专业学位）
085224
安全工程（专业学位）
085211
计算机技术（专业学位）
085212
软件工程（专业学位）
感谢您的阅读，祝您生活愉快。

JM模型中UMHexagonS改进算法

JM模型中UMHexagonS改进算法
刘云;孟岩;孙芳
【期刊名称】《系统仿真学报》
【年(卷),期】2009(0)S1
【摘要】H.264是由ISO/IEC和ITU-T共同发布的较新的视频编解码标准,而JM
模型是JVT官方发布的H.264标准测试模型。

在H.264编码标准中,运动估计是最重要而最耗时的过程,对于多预测模式、多参考帧,更细化的运动矢量来说更是如此。

在JM模型中,可选的运动估计方法有三种,通过对JM10.2源码中的UMHexagonS算法进行分析,改进宏块中绝对误差和计算步骤,在保证视频序列信
噪比的前提下减少运动估计的耗时。

实验结果表明该方法对视频序列处理耗时平均减少达5%～15%,而信噪比衰减不超过0.3%。

【总页数】3页(P149-150)
【作者】刘云;孟岩;孙芳
【作者单位】青岛科技大学信息科学技术学院
【正文语种】中文
【中图分类】TN919.81
【相关文献】
1.H.264 JM模型中运动估计算法及改进方案
2.JM模型中UMHexagonS算法及
改进方案3.H.264JM模型中丢包算法的研究及改进4.H.264JM模型中UMHexagonS算法优化5.基于JM模型的UMHexagonS算法的改进
因版权原因，仅展示原文概要，查看原文内容请购买。

基于SOA集成框架的大型精密仪器共享平台的研究与设计

规范管理、合集成，动跨部门、综推单位的学术交流、
校已经建立了学院、实验室级别的大型精密仪器设
备的管理和服务网站，展大型仪器设备的网上信开息服务和预约服务。但是目前还存在如下的问题：（）１各学院、验室情况不同，的学院大型精密仪实有器较多，院比较重视仪器设备的管理，学自行开发设计了基于本学院所有实验室的大型精密仪器共享的信息系统；的实验室是国家重点或省级重点实验有室，以也自己开发了基于本实验室的共享系统平所
中图分类号：Ｐ９；４４Ｔ３３Ｇ３文献标识码：Ｂｄｉ１．９９ｊｉｎ１７ — ３５２１．３０４ｏ：０３６／．ｓ．６２４０．０２０．６ｓ
Ｒｅｅｒｈａｄｄｓｇｆｔｅｌｒｅｐｅｉｉｎｉｓｒｍｅｔｓａｃｎｅｉｎｏｈａｇｒｃｓｏｎｔｕｎ
王华东，曹磊
（１青岛科技大学信息科学技术学院；２．．青岛科技大学实验设备处，山东青岛２６６）６０１
摘要：构建一个合理的、功能完备的大型精密仪器共享平台是实现目前高校设备资源共享的关键。设计实
现了一个基于ＳＡ的系统集成框架，为大型精密仪器共享平台的开发建设提供了全面的解决方案。Ｏ关键词：ＳＡ；大型精密仪器；共享平台；资源共享Ｏ
１现状及分析
随着Ｉｔｎｔｎｅｅ网络技术的普及和发展，些高ｒ一

青岛各所大学12年录取分数

【青岛科技大学】2012年山东省录取情况一览表2012年省内录取分数情况一览表批次总计划数理科文科山东分数线青岛分数线我校录取最低分数我校录取最高分数山东分数线青岛分数线我校录取最低分数我校录取最高分数本科一批3016582582659573573616本科二批390501481562638504484548593本科二批（高密校区）140501481495634504484500567校企合作办学本科320501481496598504484中外合作办学本科385501481492638504484中外合作办学专科141180295499180398477专科高职批（高密校区）1079180251550180447543【青岛理工大学】2012年山东省录取情况（本科计划）专业科类学制学费标准2012年计划2011年计划2011年录取分数2010年录取分数2009年录取分数音乐表演（器乐）艺术四年6000109315361361音乐表演（声乐）艺术四年6000109302326310工业设计（文/理）艺术四年60005/1021477/399480/449376/404艺术设计（文/理）艺术四年600025/1540/20349/365406/339406/413绘画（文/理）艺术四年60005/515314/411399/373302/293服装设计与工程（文/理）艺术四年600016/418296/373324/377308/369会计学文史四年3740*53*40574601595财务管理文史四年3400*24*10571598595国际经济与贸易文史四年3740*89*85570601587国际商务文史四年3400*24*25570590595市场营销文史四年3400*2834570593595朝鲜语文史四年48002021539596582汉语言文学文史四年34002422520——英语文史四年48005054512597583日语文史四年48004755500597584社会工作文史四年34005351495596582广告学文史四年34005349494596582建筑学理工五年3960*62*63596605600土木工程理工四年3960*191*214591602598景观建筑设计理工四年3600*14*4590594592城市规划理工五年3960*28*27589598594工程造价理工四年3960*48*47587601598会计学理工四年3740*34*55586605585机械设计制造及其自动化理工四年3960*153*162586599599财务管理理工四年3600*15*26585603585经济学理工四年3600*27*28582596593材料科学与工程理工四年3960*21*25581593592电力工程与管理理工四年3600*30【山东科技大学】2012年山东省本科录取情况统计表省码省市科类计划录取一志愿征集志愿投档最高投档最低录取分数平均最低控制线3 7 山东省本一文科446 446 301 145 618 573 573 595.1 573理科4304 4504 4504 631 582 582 588.2 582 艺术艺设文40 40 40 543 407407/256432.35300/180广告学40 41 41 547 466 475 492 300工设文20 20 20 539 486 494 507.8 300工设理20 20 20 563 470 487509.75300 音乐学文30 28 28 476 308308/116名357.75300 音乐学理10 11 11 497 316316/20名405.6 300 本二文科180 181 181 575 508 522 542.5 484理科620 726 726 618 517 520 553.6 481 中外本科文科140 140 51 89 559 496 496 520.6 484理科340 340 121 219 594 495 495 531.6 481 软件外包理科120 104 42 62 593 496 496 541.6 481 金融外包文科80 80 80 577 496 500 521.6 484理科40 56 56 607 495 495 521 481 煤炭定向理科550 459 459 596 497 520 548.3 481 中外专科文科180 180 180 500 217 224 388.8 180理科120 120 120 500 237 241 403.8 180 本二（泰山科文科196 196 11 185 555 486 486 501 484理科344 344 62 282 586 486 486 504 481技学院）专科（泰山科技学院）文科412 319 230 89 494 189 189 358 180 理科838 760 606 154 517 183 183 384 180注：东营、烟台、威海、日照、莱芜、聊城执行省属线；淄博、枣庄、济宁、潍坊、泰安、临沂、德州、滨州、菏泽执行市属线。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第九章查找本章中介绍下列主要内容：静态查找表及查找算法：顺序查找、折半查找动态查找表及查找算法：二叉排序树哈希表及查找算法

第一节基本概念查找表用于查找的数据元素集合称为查找表。查找表由同一类型的数据元素（或记录）构成。静态查找表若只对查找表进行如下两种操作：（1）在查找表中查看某个特定的数据元素是否在查找表中，（2）检索某个特定元素的各种属性，则称这类查找表为静态查找表。静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。动态查找表若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元素，则称这类查找表为动态查找表。动态查找表在查找过程中查找表可能会发生变化。对动态查找表进行的查找操作称为动态查找。关键字是数据元素中的某个数据项。唯一能标识数据元素（或记录）的关键字，即每个元素的关键字值互不相同，我们称这种关键字为主关键字；若查找表中某些元素的关键字值相同，称这种关键字为次关键字。例如，银行帐户中的帐号是主关键字，而姓名是次关键字。查找在数据元素集合中查找满足某种条件的数据元素的过程称为查找。最简单且最常用的查找条件是 ”关键字值等于某个给定值”，在查找表搜索关键字等于给定值的数据元素（或记录）。若表中存在这样的记录，则称查找成功，此时的查找结果应给岀找到记录的全部信息或指示找到记录的存储位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可以给岀一个空记录或空指针。若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。查找表的存储结构查找表是一种非常灵活的数据结构，对于不同的存储结构，其查找方法不同。为了提高查找速度，有时会采用一些特殊的存储结构。本章将介绍以线性结构、树型结构及哈希表结构为存储结构的各种查找算法。查找算法的时间效率查找过程的主要操作是关键字的比较，所以通常以”平均比较次数”来衡量查找算法的时间效率。

第二节静态查找正如本章第一节所述：静态查找是指在静态查找表上进行的查找操作，在查找表中查找满足条件的数据元素的存储位置或各种属性。本节将讨论以线性结构表示的静态查找表及相应的查找算法。 1. 顺序查找 1.1顺序查找的基本思想顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。 1.2 顺序表的顺序查找下面是顺序表的类型定义： #define MAX_NUM 100 // 用于定义表的长度 typedef struct elemtype{ keytype key; anytype otherelem; }Se_List[MAX_NUM],Se_Elem; 假设在查找表中，数据元素个数为 n ( n下面我们给出顺序查找的完整算法。 int seq_search (Se_List a ， keytype k) {// 在顺序表中查找关键字值等于 k 的记录， // 若查找成功，返回该记录的位置下标序号，否则返回 0 i=1; while (i<=n && a[i].key != k) i++; if (i<=n) retrun i; else return 0; } 改进算法： int seq_search2 (Se_List a ， keytype k) { // 设置了监视哨的顺序表查找，查找关键字值等于指定值 k 的记录， // 若查找成功，返回记录存放位置的下标值，否则返回 0 i=n ; a[0].key=k ; while ( a[i].key != k) i--; return ( i ) ; } 1.3 链表的顺序查找链表的顺序查找是指将查找表作为线性表并以链式存储结构存储，用顺序查找方法查找与指定关键字值相等的记录。链表的类型定义如下所示： typedef struct linklist { keytype key; // 结点的关键字类型 anytype otherelem; // 结点的其他成分 struct linklist *next; // 指向链表结点的指针 }Link_Linklist,*Link; 将查找表中的数据元素用这种结构的结点表示，并以指向头结点的指针标识。对链表实现顺寻查找就是在有头结点的链式查找表中查找关键字值等于给定值的记录，若查找成功，返回指向相应结点的指针，否则返回空指针。 Link_Linklist *link_search (Link h , keytype k) {//link 为带头结点链表的头指针，查找关键字值等于 k 的记录， // 查找成功，返回指向找到的结点的指针，查找失败返回空指针 p=h->next; while ((p!=NULL) && (p->key!=k)) p=p->next;

return p; } 顺序查找算法简单，对表的结构无任何要求；但是执行效率较低，尤其当 n较大时，不宜采用这种查找方法。 2. 折半查找 2.1折半查找的基本思想折半查找要求查找表用顺序存储结构存放且各数据元素按关键字有序(升序或隆序)排列，也就是说折半查找只适用于对有序顺序表进行查找。折半查找的基本思想是：首先以整个查找表作为查找范围，用查找条件中给定值 k与中间位置结点的关键字比较，若相等，则查找成功，否则，根据比较结果缩小查找范围，如果 k的值小于关键字的值，根据查找表的有序性可知查找的数据元素只有可能在表的前半部分，即在左半部分子表中，所以继续对左子表进行折半查找；若k的值大于中间结点的关键字值，则可以判定查找的数据元素只有可能在表的后半部分，即在右半部分子表中，所以应该继续对右子表进行折半查找。每进行一次折半查找，要么查找成功，结束查找，要么将查找范围缩小一半，如此重复，直到查找成功或查找范围缩小为空即查找失败为止。 2.2折半查找过程示例

假设待查有序(升序)顺序表中数据元素的关键宁序列为也圾77忿47乱兄

2.3折半查找算法假设查找表存放在数组 a的a[1]~a[n]中，且升序，查找关键字值为 k。折半查找的主要步骤为： (1) 置初始查找范围：low=1，high=n;

(2) 求查找范围中间项： mid=(low+high)/2

(3) 将指定的关键字值 k与中间项a[mid].key 比较若相等，查找成功，找到的数据元素为此时 mid指向的位置；若小于，查找范围的低端数据元素指针 low不变，高端数据元素指针 high更新为mid-1;

若大于，查找范围的高端数据元素指针 high不变，低端数据元素指针 low更新为mid+1;

(4) 重复步骤(2)、( 3)直到查找成功或查找范围空(low>high )，即查找失败为止。 (5) 如果查找成功，返回找到元素的存放位置，即当前的中间项位置指针 mid;否则返回查找失败标志。折半查找的完整算法如下： int bin_search (Se_List a, keytype k) { low=1; high=n; // 置初始查找范围的低、高端指针 while (low<=high) { mid=(low+high)/2; // 计算中间项位置 if (k==a[mid].key) break; // 找到，结束循环 else if (k< a[mid].key) high=mid-1; // 给定值 k 小 else low=mid+1; // 给定值 k 大 }

if (low<=high) return mid ; // 查找成功 else return 0 ; // 查找失败 } 第三节动态查找 1•二叉排序树二叉排序树是一种常用的动态查找表，下面首先给岀它的非递归形式。二叉排序树是一棵二叉树，它或者为空，或者具有如下性质： (1) 任一非终端结点若有左孩子，则该结点的关键字值大于其左孩子结点的关键字值。 (2) 任一非终端结点若有右孩子，则该结点的关键字值小于其右孩子结点的关键字值。二叉排序树也可以用递归的形式定义，即二叉排序树是一棵树，它或者为空，或者具有如下性质： (1) 若它的左子树非空，则其左子树所有结点的关键字值均小于其根结点的关键字值。 (2) 若它的右子树非空，则其右子树所有结点的关键字值均大于其根结点的关键字值。 (3) 它的左右子树都是二叉排序树。例如，由关键字值序列(62,15,68,46,65,12,57,79,35 )构成的一棵二叉排序树如图 7-4所示

如果对上述二叉排序树进行中根遍历可以得到一个关键字有序序列( 12, 15, 35,46, 57,62,65,68,79 )，这是二叉排序树的一个重要特征，也正是由此将其称为 "二叉排序树"。 2•二叉排序树的查找二叉排序树的结构定义中可看到：一棵非空二叉排序树中根结点的关键字值大于其左子树上所有结点的关键字值，而小于其右子树上所有结点的关键字值，所以在二叉排序树中查找一个关键字值为 k的结点的基本思想是：用给定值k与根结点关键字值比较，如果k小于根结点的值，则要找的结点只可能在左子树中，所以继续在左子树中查找，否则将继续在右子树中查找，依此方法，查找下去，至直查找成功或查找失败为止。二叉排序树查找的过程描述如下： (1 )若二叉树为空树，则查找失败， (2) 将给定值k与根结点的关键字值比较，若相等，则查找成功， (3) 若根结点的关键字值小于给定值 k,则在左子树中继续搜索， (4) 否则，在右子树中继续查找。假定二叉排序树的链式存储结构的类型定义如下： typedef struct linklist { keytype key; anytype otherelem; struct linklist *lchild ； struct linklist *rchild;

}Bin_Sort_Tree_Linklist,*Bin_Sort_Tree ；二叉排序树查找过程的描述是一个递归过程，若用链式存储结构存储，其查找操作的递归算法如下所示：