当前位置：文档之家 › 华清远见 数据结构

华清远见 数据结构

  • 格式：ppt
  • 大小：915.00 KB
  • 文档页数：1

下载文档原格式

  / 1

合集下载

数据结构(C语言版清华大学出版社)-章课后部分答案

数据结构(C语言版清华大学出版社)-章课后部分答案

第八章选择题1. C2.A3.B4.C5.D6.B7.B8.A9.D 10.D 11.C 12.C填空题1.n、n+12. 43.8.25( 折半查找所在块 )4.左子树、右子树5.266.顺序、(n+1)/2、O(log2n)7.m-1、[m/2]-18.直接定址应用题1.进行折半查找时，判定树是唯一的，折半查找过程是走了一条从根节点到末端节点的路径，所以其最大查找长度为判定树深度[log2n]+1.其平均查找长度约为[log2n+1]-1.在二叉排序树上查找时，其最大查找长度也是与二叉树的深度相关，但是含有n个节点的二叉排序树不是唯一的，当对n个元素的有序序列构造一棵二叉排序树时，得到的二叉排序树的深度也为n，在该二叉树上查找就演变成顺序查找，此时的最大查找长度为n；在随机情况下二叉排序树的平均查找长度为1+4log2n。

因此就查找效率而言，二分查找的效率优于二叉排序树查找，但是二叉排序树便于插入和删除，在该方面性能更优。

3. 评价哈希函数优劣的因素有：能否将关键字均匀的映射到哈希表中，有无好的处理冲突的方法，哈希函数的计算是否简单等。

冲突的概念：若两个不同的关键字Ki和Kj，其对应的哈希地址Hash(Ki) =Hash(Kj)，则称为地址冲突，称Ki和K,j为同义词。

（1）开放定址法（2）重哈希法（3）链接地址法4.（1）构造的二叉排序树，如图（2）中序遍历结果如下：10 12 15 20 24 28 30 35 46 50 55 68（4）平均查找长度如下：ASLsucc = （1x1+2x2+3x3+4x3+5x3）/12 = 41/128.哈希地址如下：H(35) = 35%11 = 2H(67) = 67%11 = 1H(42) = 42%11 = 9H(21) = 21%11 = 10H(29) = 29%11 = 7H(86) = 86%11 = 9H(95) = 95%11 = 7H(47) = 47%11 = 3H(50) = 50%11 = 6H(36) = 36%11 = 3H(91) = 91%11 = 3第九章选择题1. D2.C3.B4.D5.C6.B7.A8.A9.D 10.D填空题1.插入排序、交换排序、选择排序、归并排序2.移动（或者交换）3.归并排序、快速排序、堆排序4.保存当前要插入的记录，可以省去在查找插入位置时的对是否出界的判断5.O(n)、O(log2n)6.直接插入排序或者改进了的冒泡排序、快速排序7.Log2n、n8.完全二叉树、n/29.1510.{12 38 25 35 50 74 63 90}应用题11.（1）Shell排序(步长为5 3 1)每趟的排序结果初始序列为100 87 52 61 27 170 37 45 61 118 14 88 32步长为5的排序14 37 32 61 27 100 87 45 61 118 170 88 52步长为3的排序结果14 27 32 52 37 61 61 45 88 87 170 100 118步长为1的排序结果14 27 32 37 45 52 61 61 87 88 100 118最后结果14 27 32 37 45 52 61 61 87 88 100 118 170（2）快速排序每趟的排序结果如图初始序列100 87 52 61 27 170 37 45 61 118 14 88 32第一趟排序[32 87 52 61 27 88 37 45 61 14]100[118 170]第二趟排序[14 27]32[61 52 88 37 45 61 87]100 118[170]第三趟排序14[27]32[45 52 37]61[88 61 87]100 118[170]第四趟排序14[27]32[37]45[52]61[87 61]88 100 118[170]第五趟排序14[27]32[37]45[52]61[87 61]88 100 118[170]最后结果14[27]32[37]45[52]61[61]87 88 100 118[170]（3）二路归并排序每趟的排序结果初始序列[100][87][52][61][27][170][37][45][61][118][14][88][32]第一趟归并[87 100][52 61][27 170][37 45][61 118][14 88][32]第二趟归并[52 61 87 100][27 37 45 170][14 61 88 118][32]第三趟归并排序[27 37 45 52 61 87 100 170][14 32 61 88 118]第四趟归并排序[14 27 32 37 45 52 61 61 87 88 100 118 170]最后结果14 27 32 37 45 52 61 61 87 88 100 118 17012.采用快速排序时，第一趟排序过程中的数据移动如图：算法设计题1.分析：为讨论方便，待排序记录的定义为（后面各算法都采用此定义）：#define MAXSIZE 100 /* 顺序表的最大长度，假定顺序表的长度为100 */ typedef int KeyType; /* 假定关键字类型为整数类型 */typedef struct {KeyType key; /* 关键字项 */OtherType other; /* 其他项 */}DataType; /* 数据元素类型 */typedef struct {DataType R[MAXSIZE+1]; /* R[0]闲置或者充当哨站 */int length; /* 顺序表长度 */}sqList; /* 顺序表类型 */设n个整数存储在R[1..n]中，因为前n-2个元素有序，若采用直接插入算法，共要比较和移动n-2次，如果最后两个元素做一个批处理，那么比较次数和移动次数将大大减小。

数据结构知识点整理(清华大学出版社)

数据结构知识点整理(清华大学出版社)
链式存储结构：关系采取链式映像表示，即借助附加信息指针显式表示元素间的关系，对应一个链表。优点是更有效利用空间、插入或者删除结点快，但要顺序访问各元素。
5.度量指标：算法运行时间主要取决于基本操作的执行次数(频度)，执行次数通常随问题规模扩大而增加，增加越快意味着算法随问题规模的扩大，运行时间增长的也快，从而该种算法效果较差；增长越慢算法越好，故可用基本操作的频度随问题规模的增长率反映算法的效率。
{//在顺序表L的第i个位置前插入元素e,i的合法值为1..L.length+1
if(i<1||i>L.length+1) return ERROR;//插入不合法
if(L.length>=L.listsize)
{//表满，增加存储容量
ElemType*newbase=(ElemType*)realloc
#define LISTINCREMENT 10 //…
typedef ***** ElemType;
typedef struct{
ElemType *elem; //存储空间基址
int length; //…
int listsize; //……
}SqList；
SqList La,Lb,Lc;
Status InitList_Sq(SqList &L)
return(OK);
}//InitList_Sq
void ListDelete(SqList &L,int i,ElemType &e)
{//在顺序表L中删除第ｉ个元素，用ｅ返回其值．
//i的合法值是[1，ListLength(L)]
if(i<1||i>L.length) retuΒιβλιοθήκη n ERROR;//删除位置不合理

简单介绍UCOS_华清远见

简单介绍UCOS_华清远见

简单介绍UCOSUCOS在我们学习嵌入式过程中，经常会遇到的，有很多人对UCOS还是有点陌生，写这篇文章主要就是给大家简单介绍一下UCOS，希望看完对你们有帮助。

UCOSII 是一个可以基于 ROM 运行的、可裁减的、抢占式、实时多任务内核，具有高度可移植性，特别适合于微处理器和控制器，是和很多商业操作系统性能相当的实时操作系统(RTOS)。

为了提供最好的移植性能， UCOSII 最大程度上使用 ANSI C 语言进行开发，并且已经移植到近 40 多种处理器体系上，涵盖了从 8 位到 64 位各种 CPU(包括 DSP)。

UCOSII 是专门为计算机的嵌入式应用设计的，绝大部分代码是用 C 语言编写的。

CPU 硬件相关部分是用汇编语言编写的、总量约 200 行的汇编语言部分被压缩到最低限度，为的是便于移植到任何一种其它的 CPU 上。

用户只要有标准的 ANSI 的 C 交叉编译器，有汇编器、连接器等软件工具，就可以将 UCOSII 嵌人到开发的产品中。

UCOSII 具有执行效率高、占用空间小、实时性能优良和可扩展性强等特点，最小内核可编译至 2KB 。

UCOS主要有：任务管理：建立任务OSTaskCreat()/OSTaskCreatExt();任务堆栈OS_STK()堆栈检验OSTaskStkChk()删除任务OSTaskDel()请求删除任务OSTaskDelReq()改变任务的优先级OSTaskChangePrio()挂起任务OSTaskSuspend()恢复任务OSTaskResume()获得任务的信息OSTaskQuery()时间管理：任务延迟函数OSTimeDly()按时，分，秒延时函数OSRimeDLyHMSM()恢复延时的任务OSTimeDlyResume()系统时间OSTimeGet()和OSTimeSet()内存管理：Typedefstruct{void *osmemaddr ;指向内存分区起始地址的指针。

【VIP专享】linux内核链表解析 初学者如何理解内核链表_华清远见

【VIP专享】linux内核链表解析 初学者如何理解内核链表_华清远见

linux内核链表解析初学者如何理解内核链表linux内核链表对于大多数的初学者来讲，都是挺难的一部分，不容易搞懂。

本篇文章就由华清远见为大家解析linux内核链表，初学者应该如何理解内核链表呢?请往下看!在Linux内核中使用了大量的链表结构来组织数据，包括设备列表以及各种功能模块中的数据组织。

这些链表大多采用在[include/linux/list.h]实现的一个相当精彩的链表数据结构。

很多linux下的源代码都会使用这个头文件，它里面定义了一个结构,以及定义了和其相关的一组函数，本文详细分析了3.14 内核中链表结构的实现，并通过实例对链表操作接口进行了测试。

一、链表数据结构简介链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。

链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。

链表有很多种不同的类型：单向链表，双向链表以及循环链表。

链表可以在多种编程语言中实现。

像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。

程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。

通常链表数据结构至少应包含两个域：数据域和指针域，数据域用于存储数据，指针域用于建立与下一个节点的联系。

按照指针域的组织以及各个节点之间的联系形式，链表又可以分为单链表、双链表、循环链表等多种类型，下面分别给出这几类常见链表类型的示意图：1. 单链表图1 单链表单链表是最简单的一类链表，它的特点是仅有一个指针域指向后继节点(next)，因此，对单链表的遍历只能从头至尾(通常是NULL空指针)顺序进行。

华清远见毕业实习报告

华清远见毕业实习报告

华清远见毕业实习报告一、实习背景及目的随着科技的飞速发展，人工智能、大数据、云计算等新兴技术日益融入各行各业，软件开发和IT技术应用已成为现代社会的重要支柱。

为了适应这一趋势，提高自己的实际工作能力，我选择了华清远见这家知名的IT培训机构进行毕业实习。

本次实习的主要目的是将所学知识与实际工作相结合，提升自己的专业技能，为未来的职业生涯打下坚实基础。

二、实习内容及收获实习期间，我参加了华清远见提供的Java软件工程师培训课程。

通过这次实习，我深入了解了Java编程语言的特点、应用场景和开发工具，掌握了许多实用的编程技巧和方法。

在项目实践中，我参与了多个实际项目的开发，学会了如何分析需求、设计系统架构、编写代码、调试程序和优化性能。

1. 掌握Java编程语言通过实习，我全面学习了Java编程语言的基本语法、数据结构、面向对象编程、异常处理、文件操作、多线程等知识。

同时，我还学会了使用Eclipse、IntelliJ IDEA等集成开发环境，提高了编程效率。

2. 学会数据库设计与应用在实习过程中，我了解了数据库的基本概念、原理和常见数据库管理系统，如MySQL、Oracle等。

通过实际操作，我掌握了数据库的设计、创建、查询、更新和管理方法，为后续项目开发奠定了基础。

3. 掌握前端技术实习期间，我学习了HTML、CSS、JavaScript等前端技术，并学会了使用HTML5、CSS3、Bootstrap等前端框架。

这使我能够独立完成前端页面的设计与开发，提高用户体验。

4. 项目实践经验在实习项目中，我参与了多个实际项目的开发，锻炼了自己的团队协作能力和沟通技巧。

通过实际操作，我学会了项目需求分析、系统设计、编码实现、测试和部署等完整流程。

同时，我还掌握了项目管理工具，如Jira、Confluence等。

5. 软件测试与部署实习过程中，我了解了软件测试的基本概念、方法和策略，学会了使用自动化测试工具，如Selenium、JUnit等。

华清远见培训代码

华清远见培训代码

华清远见培训代码1. 简介华清远见（Huawei Clarity Vision）是华为公司旗下的一项培训计划，旨在提升员工个人技能、团队协作和领导力，并帮助员工实现个人与公司发展的双赢。

2. 培训目的华清远见培训代码的主要目的是为了促进员工职业生涯的发展和提高团队的协作效率。

通过培训，员工能够不断提升技能、扩展知识领域，并具备更好的领导力，以适应公司在竞争激烈的市场中的发展需求。

3. 培训内容华清远见培训代码主要包括以下几个方面的内容：3.1 技能培训技能培训是华清远见培训的核心内容之一。

通过培训，员工可以学习到与岗位相关的专业知识和技能，提高自己的工作效率和质量。

培训内容包括但不限于：•项目管理：学习如何合理规划和管理项目，包括项目目标、进度安排、资源调配等。

•创新思维：培养员工的创新意识和创造力，鼓励尝试新的解决方案和方法。

•市场营销：学习市场调研、品牌定位、推广策略等，提高产品的市场竞争力。

3.2 团队协作团队协作是华清远见培训的另一个重要内容。

培训将注重培养员工的团队意识和协作能力，使员工能够更好地与他人合作，共同完成任务。

培训内容包括但不限于：•沟通技巧：学习有效沟通的方法和技巧，包括言语、非言语的沟通方式，以及如何处理冲突等。

•团队建设：了解团队成员的特点和优劣势，激发团队成员的潜力，提高团队的凝聚力和执行力。

•项目协作：学习如何在团队中合作完成项目，包括任务分配、进度控制、风险管理等。

3.3 领导力发展领导力发展是华清远见培训代码的重要部分。

通过培训，员工可以提升自己的领导能力，成为团队中的核心人物。

培训内容包括但不限于：•自我管理：了解自己的优势和劣势，发展个人能力和潜力，并能够合理规划个人职业发展路径。

•影响力与说服力：学习如何在团队中影响他人、说服他人，推动团队的发展和目标的实现。

•创造性领导：培养员工的创新意识和领导力，鼓励员工提出新的观点和创新方案，推动公司发展。

4. 培训效果华清远见培训代码注重实践和应用，通过培训提升员工的能力，并使其能够在实际工作中运用所学知识和技能。

网络编程(华清远见内部培训资料)



UPD头
21
2.

TCP/IP网络编程
预备知识 系统调用 TCP编程/UDP编程 API 网络封包格式和IP，TCP头 TCP握手过程 I/O模型和服务器模型 网络调试和协议分析—wireshark和tcpdump 使用




C类地址

前3个字节是网络地址，最后1个字节是主机地址。第1字节的前3位固定为 110 192.0.0.1 – 223.255.255.255

D类地址（组播地址）

不分网络地址和主机地址，第1字节的前4位固定为1110 224.0.0.1 – 239.255.255.255

嵌入式嵌入式linuxlinux网络编程网络编程主要内容internet与tcpip协议internet历史osi模型与tcpip协议体系结构tcpip协议tcp和udp协议tcpip网络编程预备知识io模型和服务器模型网络调试和协议分析wireshark和tcpdump使用wwwfarsightcomcnunix域套接字wwwfarsightcomcntcp和udp协议wwwfarsightcomcninternet的历史1958年美国总统艾森豪威尔向美国国会提出建立darpadefenseadvancedresearchprojectagency即国防部高级研究计划署简称arpa1968年6月darpa提出资源共享计算机网络resourcesharingcomputernetworks目的在于让darpa的所有电脑互连起来这个网络就叫做arpanet即阿帕网是interne的最早雏形wwwfarsightcomcnlinux为用户提供了完善的强大的网络功能在internet中为了使硬件和软件有差异的计算机之间联网彼此之间数据兼容需要建立一种大家共同都必须遵守的标准这样才能让不同的电脑按照一定的规则数据交互和资源共享这种标准就是网络协议

嵌入式系统培训班课程安排_华清远见

嵌入式系统培训班课程安排在参加嵌入式培训之前，很多学员都会现在网上了解各大嵌入式系统培训班的课程安排是什么样的，只要了解了嵌入式系统培训班课程安排，才能选择出哪个机构是最适合自己的。

下面分享来自华清远见嵌入式培训课程安排。

1.嵌入式C语言：C语言是嵌入式领域中最重要也是最主要的编程语言，通过大量编程实例重点来理解C语言的基础编程以及高级编程知识。

2.Linux基础：Linux操作系统的概念、安装方法，都可以详细了解下Linux下的目录结构、基本命令、编辑器VI、编译器GCC，调试器GDB和 Make 项目管理工具。

3.Linux系统编程：主要是重点学习标准I/O库，Linux多任务编程中的多进程和多线程，以及进程间通信，同步与互斥对共享资源访问控制等重点知识，主要提升对Linux应用开发的理解和代码调试的能力。

4.Linux网络编程：计算机网络在嵌入式Linux系统应用开发过程中使用非常广泛，通过Linux网络发展、TCP/IP协议、socket编程、TCP网络编程、UDP网络编程、Web编程开发等方面入手，全面了解Linux 网络应用程序开发。

5.数据结构域算法：数据结构及算法在嵌入式底层驱动、通信协议、及各种引擎开发中会得到大量应用，对其掌握的好坏直接影响程序的效率、简洁及健壮性。

6.C++、QT：C++是Linux应用开发的主要语言之一，在这一阶段最重要的是掌握面向对象编程的基本思想以及C++的重要内容。

7.Cortex A8 、Linux 平台开发，通过基于ARM Cortex-A8处理s5pv210了解芯片手册的基本阅读技巧，掌握s5pv210系统资源、时钟控制器、电源管理、异常中断控制器、nand flash控制器等模块，为底层平台搭建做好准备。

8.驱动开发：驱动程序设计是嵌入式Linux开发工作中重要的一部分，也是比较困难的一部分。

本阶段的学习要熟悉Linux的内核机制、驱动程序与用户级应用程序的接口，掌握系统对设备的并发操作。

详细分析Qt中moc文件_华清远见

详细分析Qt中moc文件一直想写一片详细分析Qt中moc文件的文章，今天终于是完成了。

迫不及待的分享给大家，希望大家可以赏个脸，认真的看完，希望对大家的学习也有帮助。

请看下面的分析Qt中moc文件的详细内容。

Qt 不是使用“标准的”C++语言编写，而是对其进行了一定程度的扩展。

我们可以从Qt增加的关键字看出来：signals、slots或emit。

但是使用gcc编译时，编译器并不认识这些非标准c++的关键字，那么就需要Qt自己将扩展的关键字处理成标准的C++代码。

Qt在编译之前会分析源文件，当发现包含了Q_OBJECT 宏，则会生成另外一个标准的C++源文件，这个源文件中包含了 Q_OBJECT 宏的实现代码，这个源文件名字是将原文件名前面加上 moc_ 构成，这个新的文件同样将进入编译系统，最终被链接到二进制代码中去，此时，Qt将自己增加的扩展转换成了标准的C++文件，moc 全称是 Meta-Object Compiler，也就是“元对象编译器”。

这就是moc文件的由来。

下面我们来分析一下Moc文件：一示例代码如下：#includeclass CTestMoc : public QObject{Q_OBJECTpublic:CTestMoc(){}~CTestMoc(){}signals:void Test1();void Test2(int iTemp);private slots:void OnTest1();void OnTest2(int iTemp);};二 Q_OBJECT宏#define Q_OBJECT \public: \Q_OBJECT_CHECK \static const QMetaObject staticMetaObject; \virtual const QMetaObject *metaObject() const; \virtual void *qt_metacast(const char *); \QT_TR_FUNCTIONS \virtual int qt_metacall(QMetaObject::Call, int, void **); \private: \Q_DECL_HIDDEN_STATIC_METACALL static void qt_static_metacall(QObject *, QMetaObject::Call, int, void **); \struct QPrivateSignal {};此宏在QObjectdefs.h头文件中定义1 Q_OBJECT_CHECK 定义如下：#define Q_OBJECT_CHECK \template inline void qt_check_for_QOBJECT_macro(const ThisObject &_q_argument) const \{ int i = qYouForgotTheQ_OBJECT_Macro(this, &_q_argument); i = i + 1; }宏展开最终会调用qYouForgotTheQ_OBJECT_Macro这个内联函数。

简单介绍ELF_华清远见

简单介绍ELF简单介绍下ELF，在计算机科学中，ELF是一种用于二进制文件、可执行文件、目标代码、共享库和核心转储格式文件。

是UNIX系统实验室(USL)作为应用程序二进制接口(Application Binary Interface，ABI)而开发和发布的，也是Linux的主要可执行文件格式。

1999年，被86open项目选为x86架构上的类Unix 操作系统的二进制文件标准格式，用来取代COFF。

因其可扩展性与灵活性，也可应用在其它处理器、计算机系统架构的操作系统上。

下面我们来看看华清远见是如何介绍ELF的，拿好笔记本哦~ELF(Executable and linking format)是一种二进制格式，在一些linux或Unix中作为默认的可执行格式。

ELF有三种主要的文件类型1、可执行文件：包含代码和数据。

可以执行的文件。

如下：$gcc test.c –o test$file testtest: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), for GNU/Linux 2.6.9, dynamically linked (uses shared libs), for GNU/Linux 2.6.9, not stripped2、可重定位文件：就是我们说的目标文件，没有连接之前的。

如下：$gcc –c test.c$file test.otest.o: ELF 32-bit LSB relocatable, Intel 80386, version 1 (SYSV), not stripped3、共享0bject文件：就是共享库，这些文件中的数据和代码在连接的时候和运行时动态加载。

如下：$file /lib/libc-2.5.so/lib/libc-2.5.so: ELF 32-bit LSB shared object, Intel 80386, version 1 (SYSV), for GNU/Linux 2.6.9, not strippedELF文件格式为：ELF header(ELF头部)Program header table(程序头表)Segment1(段1)Segment2(段2)………Sengmentn(段n)Setion header table(节头表，可选每个段由若干个节组成，节头表对每个节的信息有相关的描述，对可执行程序而言节头表是可选的。

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

→∞
时, ASL=O(log2(n+1))，大大优于O(n)。 ， 。
3 分块查找算法及分析 分块查找(Blocking Search)，又称索引顺序查找（Indexed Sequential Search），是顺序查找方法的一种改进，目的也是为了提高查找效率。 1．分块 ． 设记录表长为n，将表的n个记录分成b= n / s 个块，每块s个记录（最后 一块记录数可以少于s个），即：
算法思路 对给定值k，逐步确定待查记录所在区间，每次将搜索空间减少一半(折 半)，直到查找成功或失败为止。 设两个指针(或游标)low、high，分别指向当前待查找表的上界(表头)和 下界(表尾)。对于表(R1 R2……Rn)，初始时low=l、high=n，令： mid= (low + high) / 2 指向当前待查找表中间的那个记录。下面举例说明折半查找的过程。 例1 设记录表的key序列如下: 序号： 1 2 3 4 5 6 7 8 9 10 11 12 (n=12) 03 12 18 20 32 55 60 68 80 86 90 100
i =1 i =1
2
故ASL=O(n)。而查找失败时，查找次数等于n+l，同样为O(n)。 对查找算法，若ASL=O(n)，则效率是最低的，意味着查找某记录几 乎要扫描整个表，当表长n很大时，会令人无法忍受。下面关于查找的 一些讨论，大多都是围绕降低算法的ASL量级而展开的。 2 折半查找算法及分析 当记录的key按关系≤或≥有序时，即： 可采用折半或二分法查找 R1.key≤R2.key≤……≤Rn.key (升序) (Binary Search)。 或 R1.key≥R2.key≥……≥Rn.key (降序)
学号 姓名 性别 年龄 ……
其中，“学号”、“姓名”、“性别”、“年龄”等都是记录的数 据项。若某个数据项的值能标识(或识别)一个或一组记录，称其为关键字 关键字 (key)。若一个key能唯一标识一个记录，称此key为主key。如“学号”的值 给定就唯一对应一个学生，不可能多个学生的学号相同，故“学号”在学 生记录里可作为主key。若一个key能标识一组记录，称此key为次key。如 “年龄”值为20时，可能有若干同学的年龄为20岁，故“年龄”可作次key。 下面主要讨论对主key的查找。
查找
“查找”（Searching）及“排序”(Sorting)是建立在数据结构上的两个重 要运算。查找(或检索)是在给定信息集上寻找特定信息元素的过程。据统计， 一些计算机、特别是商用计算机，其CPU处理时间约25%～75%花费在查找 或排序上。所以对查找和排序问题的处理，有时直接影响到计算机的工作 效率。 一、概 述 待查找的数据单位(或数据元素)称为记录。记录由若干数据项(或 属性)组成，如学生记录:
且表分块有序，即第i（1≤i≤b-1）块所有记录的key小于第i+1块中记录的key， 但块内记录可以无序。 2．建立索引 ． 每块对应一索引项：
kmax
link
其中kmax为该块内记录的最大key；link为该块第一记录的序号（或指针）。
分块查找 例2 设表长n=19，取s=5，b= 19 / 5 = 4，分块索引结构 如图所示。 3．算法思路 分块索引查找分两步进行： ． (1)由索引表确定待查找记录所在的块； (2)在块内顺序查找。
90 100
mid low
mid low mid high high high mid
(1 + 12) / 2 =6。因k>r.data[6].key=55，若85存在，一定落在“55” 1mid=
的右半区间。令：low=mid+1。 (10+12)/2 (10 + 10) / 2 =11。因k<r.data[11].key=90，若85存在，一定落在“90” 3mid= 的左半区间。令：high=mid-1。 (10 + 10) / 2 =10。因k<r.data[10].key=86，若85存在，一定落在“86” 4mid= 的左半区间。令：high=mid-1。此时，下界1ow=10，而上界high=9，表 明搜索空间不存在，故查找失败，返回0。
2mid=(7 + 12) / 2 =9。因k>r.data[9].key=80，若85存在，一定落在“80”
的右半区间。令： low=mid+1 。
折半查找 算法描述 int Binsearch(sqlist r,keytype k) //对有序表r折半查找的算法// { int low,high,mid; low=1;high=r.len; //上下界初值// while(low<=high) //表空间存在时// { mid=(low+high)/2; //求当前mid// if (k==r.data[mid].key) return(mid); //查找成功，返回mid// if (k<r.data[mid].key) high=mid-1; //调整上界，向左部查找// else low=mid+1; } //调整下界，向右部查找// return(0); } //low>high，查找失败// 算法分析 查找次数 对例1中记录表的查找过程 ……………. ……... 1×20 可得到如图所示的一棵判定树： 6
1.查找定义 查找定义 设记录表L=(R1 R2……Rn)，其中Ri(l≤i≤n)为记录，对给定的某个值k， 在表L中确定key=k的记录的过程，称为查找。若表L中存在一个记录Ri 的key=k，记为Ri.key=k，则查找成功，返回该记录在表L中的序号i(或 Ri 的地址)，否则(查找失败)返回0(或空地址Null)。 2．查找方法 ． 查找方法很多，有顺序查找、折半查找、分块查找、树表查找及Hash 表查找等等。查找算法的优劣将影响到计算机的使用效率，应根据应用 场合选择相应的查找算法。 3．平均查找长度 ． 评价一个算法优劣的量度，一是时间复杂度T(n)，n为问题的体积， 此时为表长；二是空间复杂度D(n)；三是算法的结构等其他特性。 对查找算法，主要分析其T(n)。查找过程是key的比较过程，时间主 要耗费在各记录的key与给定k值的比较上。比较次数越多，算法效率越 差（即T(n)量级越高），故用“比较次数”刻画算法的T(n)。另外，显 然不能以查找某个记录的时间来作为T(n)，一般以“平均查找长度”来 衡量T(n)。 平均查找长度ASL（Average Search Length）：对给定k，查找表L中 n 记录比较次数的期望值(或平均值)，即： ASL = ∑ Pi C i
n
……… ….. h×2h-1
h 1 h i −1 i −1 0 1 2 h −2 h−1 ASL= ∑Pi Ci = ∑i ⋅ 2 令S= ∑i ⋅ 2 = 1⋅ 2 + 2 ⋅ 2 + 3⋅ 2 +……+ (h −1)2 + h ⋅ 2 n i=1 i =1 i =1 1 2 3 2S= 1 ⋅ 2 + 2 ⋅ 2 + 3 ⋅ 2 + …… + (h − 1)2 h −1 + h ⋅ 2 h
顺序查找 算法分析 设Ci(1≤i≤n)为查找第i记录的key比较次数(或查找次数)： 若r.data[n].key=k， Cn=1； 若r.data[n-1].key=k， Cn-1=2； …… 若r.data[i].key=k， Ci=n-i+1； …… 若r.data[1].key=k， n C1=n n n +1 1 所以，ASL= ∑ Pi C i = n ∑ (n − i + 1) =
半区间。令：low=mid+1。
3mid= (4 + 5) / 2 =4。因k=r.data[4].key=20，查找成功, 返回mid=4。
折半查找 再看查找失败的情况，设要查找k=85的记录。 序号： 1 2 3 4 5 6 7 8 03 low 12 18 20 32 55 60 68 9 80 10 86 11 12 (n=12)
S=2S-S= h ⋅ 2h − (20 + 21 + 22 +… + 2h−1 ) = h ⋅ 2h − (2h −1) = (n + 1) log 2 (n + 1) − n … 故ASL= n
1 n
(( n + 1) log 2 ( n + 1) − n ) =
n +1 n
log 2 ( n + 1) − 1
i =1 Pi为查找Ri的概率。等概率情况下Pi=1/n；Ci为查找Ri时key的比较次数(或查找次数)。
二、顺序表的查找 所谓顺序表(Sequential Table)，是将表中记录(R1 R2……Rn)按其序号 存储于一维数组空间，如图所示。其特点是相邻记录的物理位置也是相 邻的。 R1 记录Ri的类型描述如下： R2 typedef struct … { keytype key; //记录key// … …… //记录其他项// Rn }Retype; 其中，类型keytype是泛指，即keytype可以是int、float、char或其他的结 构类型等等。为讨论问题方便，一般取key为整型。 顺序表类型描述如下: #define maxn 1024; //表最大长度// typedef struct { Retype data[maxn]; //顺序表空间// int len; //当前表长，表空时len=0// }sqlist; 若说明：sqlist r，则（r.data[1]，……，r.data[r.len]）为记录表(R1……Rn)， Ri.key为r.data[i].key, r.data[0]称为监视哨，为算法设计方便所设。
low high mid low high mid 现查找k=20的记录。 mid 1mid= (1 + 12) / 2 =6。因k<r.data[6].key=55，若20存在，一定落在“55”的左 半区间(搜索空间折半)。令：high=mid-1。