折半查找及其改进(算法与数据结构课程设计)

c语言折半查找法代码折半查找法，也称二分查找法，是一种高效的查找算法。

它的基本思想是将有序数组分成两部分，通过比较中间元素和目标元素的大小关系，来确定目标元素在哪一部分中，然后再在该部分中继续进行查找，直到找到目标元素或者确定目标元素不存在为止。

下面是C语言实现折半查找法的代码：```#include <stdio.h>int binarySearch(int arr[], int left, int right, int target) {while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}int main() {int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};int n = sizeof(arr) / sizeof(arr[0]);int target = 7;int index = binarySearch(arr, 0, n - 1, target);if (index == -1) {printf("目标元素不存在\n");} else {printf("目标元素在数组中的下标为：%d\n", index);}return 0;}```在上面的代码中，binarySearch函数接收四个参数：数组arr、左边界left、右边界right和目标元素target。

它通过while循环不断缩小查找范围，直到找到目标元素或者确定目标元素不存在为止。

其中，mid表示当前查找范围的中间位置，通过比较arr[mid]和target的大小关系来确定目标元素在哪一部分中。

数据结构-查找写在前⾯：这些内容是以考研的⾓度去学习和理解的，很多考试中需要⽤到的内容在实际应⽤中可能⽤不上，⽐如其中的计算问题，但是如果掌握这些东西会帮你更好的理解这些内容。

这篇关于查找的博客也只是⽤来记录以便于后续复习的，所以很多地⽅只是浅谈，并没有代码的实现如果有缘发现这篇⽂章想要深⼊了解或者因为作者表达能⼒差⽽看不懂以及有错的地⽅，欢迎留⾔指出来，我会尽快去完善的，期待有缘⼈内容多和杂，如果有机会我进⼀步进⾏梳理，将其重新梳理⼀⽚⽂章(会更注重于代码)本来只是想简单写⼀下的，但是不⼩⼼就get不到重点了本来打算等逐步完善和优化后再发出来的，但那样继续往前总感觉有所顾及，所以就先给这⼏天查找的复习暂时告⼀段落吧。

导学概览总体(⼀)概念查找：在数据集合中查找特定元素的过程查找表(查找结构)：同⼀类型数据元素构成的集合静态查找表:只涉及查找，不存在修改适⽤：顺序查找，折半查找，散列查找等动态查找表:动态插⼊和删除，对查找表进⾏修改适⽤：⼆叉排序树，散列查找等所有数据结构都可以看作是查找表，对于折半查找和顺序查找这些都属于查找算法关键字：数据元素中唯⼀标识该元素的某数据项的值主关键字：此关键字能唯⼀表⽰⼀个数据元素次关键字：此关键字⽤以识别若⼲记录(⼀对多)说明：在查找表中每个数据元素就相当于⼀条记录，包含有不同的数据项，例如拿学⽣为例，⼀个学⽣作为数据元素，那么学号，⾝⾼，姓名就是这个元素中的数据项，每个学⽣都有特定的学号，因此学号可以作为关键字。

(当然如果数据项包含⾝份证号，你⽤⾝份证号⾛位关键字也可以)0x01平均查找长度(重点注意：作为查找算法效率衡量的主要指标，那么查找算法的性能分析肯定是重点分析平均查找长度的，因此必须熟练掌握。

提⼀嘴，算法效率的度量前⾯学过时间和空间复杂度，但是算法效率的度量不是只取决于时间和空间复杂度，针对不同的算法还可能会有其他⼀些辅助度量，如查找算法中的平均查找长度。

《数据结构》课程教学大纲Data Structure执笔人：编写日期：一、课程基本信息1. 课程编号：2. 课程性质/类别：必修课/ 专业主干课3. 学时/学分：48 学时（另实验16学时）/ 4 学分4. 适用专业：计算机科学与技术、软件工程、网络工程、信息管理与信息系统等专业二、课程教学目标及学生应达到的能力数据结构课程是计算机相关专业的专业基础课、必修课程，主要介绍用计算机解决一系列问题特别是非数值信息处理问题时所用的各种组织数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。

通过本课程的学习，要求学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和编写质量高、风格好的应用程序的能力，培养学生分析问题、解决问题的能力，并为后续课程的学习打下良好的理论基础和实践基础。

三、课程教学内容与基本要求（一）绪论（3 学时）1．主要内容：（1）介绍什么是数据结构；（2）基本概念和术语: 数据、数据元素、数据对象，以及数据结构的定义、逻辑结构、物理结构（理解）数据类型、抽象数据类型；（3）抽象数据类型的表示与实现；（4）算法和算法分析: 算法的概念、算法设计的要求以及算法效率的度量。

2．基本要求（1）了解学习数据结构的重要性；（2）掌握数据结构的定义及相关概念和术语；（3）了解抽象数据类型的定义、表示与实现方法；（4）理解算法的概念、特点并掌握度量其效率的基本方法。

3．自学内容：类C语言的书写规范。

（二）线性表（6 学时）1．主要内容：（1）线性表的抽象数据类型定义和相关概念：数据项、记录、文件等；（2）线性表顺序存储表示和基本操作的实现；（3）线性表的链式存储表示和基本操作的实现；（4）稀疏多项式的抽象数据类型定义、表示和加法的实现。

2．基本要求（1）掌握线性表的定义和特点；（2）熟练掌握线性表的顺序存储表示和插入、删除、查找等实现算法；（3）熟练掌握单链表、循环链表、双向链表三种链表的表示，以及单链表的查找、插入、删除、创建等实现算法。

一、课程的性质、任务与基本要求（一）课程的性质、任务1．课程的性质《数据结构》是软件技术专业中一门重要的专业必修课程。

它与数学和计算机软件设计有十分密切的关系，是计算机软件专业的一门核心课程，是程序设计、操作系统、数据库等课程的基础。

同时，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。

当我们用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是《数据结构》课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。

因此，《数据结构》课程在计算机软件专业中具有重要的作用。

2．课程的任务①本课程实现专业培养目标中所承担的任务：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。

②本课程教学内容及教学环节等方面与相关课程的联系与分工：《数据结构》是计算机软件专业的一门核心课程，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。

③本课程相关的先修课及后续课：先修课：《Java语言程序设计基础》或《Python语言程序设计基础》；后续课：程序设计、项目开发、数据库等课程。

（二）基本要求具体要求学生通过各个教学环节达到以下目标：1 通过学习掌握各种数据结构的逻辑结构、物理结构以及在之上实施的算法2 提高程序设计能力和编程质量3 学会分析研究计算机加工的数据对象的特性，能选择适当的数据结构以及相应的算法4 通过本课程的学习，使学生的逻辑分析、抽象思维和程序设计的能力有所提高，培养学生具有优良的程序设计风格5 通过本课程的学习，为后续的软件课程打下良好基础二、主要教学内容及教学要求第一章绪论教学内容1.1 数据结构的概念1.2 算法的概念1.3 算法描述和算法分析概念介绍教学要求⑴领会数据、数据元素和数据项的概念及其相互间关系⑵清楚数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的运算及其实现⑶掌握“数据结构”的描述及算法的概念⑷掌握描述算法的方法⑸了解进行简单算法分析的方法第二章线性表教学内容2.1 线性表的基本概念和运算2.2 顺序表2.3 链表及其操作2.4 栈和队列教学要求⑴理解线性表的定义及其运算⑵理解顺序表定义、组织形式、结构特征和类型说明⑶掌握在顺序表上实现的插入、删除和查找的算法⑷掌握单链表和循环链表的结构特点及基本操⑸了解双向链表和双向循环链表的结构特点(6) 理解栈的定义、特征及在其上所定义的基本运算(7) 掌握在顺序和动态存储结构上栈基本运算的实现(8) 理解队列的定义、特征及在其上所定义的基本运算(9) 掌握在顺序和动态存储结构上队列基本运算的实现第三章串教学内容4.1 串的基本概念4.2 串的基本操作4.3 串的存储结构4.4 串操作应用举例教学要求⑴掌握串的基本概念、基本运算⑵了解串的存储方式⑶理解串的基本操作算法第四章数组和广义表教学内容4.1 多维数组4.2 特殊矩阵和压缩存储介绍4.3 稀疏矩阵介绍4.4 广义表介绍教学要求(1) 理解多维数组的逻辑结构和数组的顺序分配(2) 了解顺序存储结构上元素在存储区中地址的计算(3) 了解特殊矩阵和压缩存储、稀疏矩阵、广义表等概念第五章树教学内容5.1树的定义和基本术语5.2 二叉树5.3 遍历二叉树5.4 线索二叉树5.5树和森林5.6 哈夫曼树教学要求⑴深刻理解并掌握树的定义、术语⑵领会树的存储结构⑶深刻理解并掌握二叉树的定义、性质及其存储方法⑷掌握二叉树的存储方式、结点结构和类型定义⑸理解并掌握二叉树的三种遍历算法⑹能够运用二叉树的遍历方法解决简单的应用问题⑺了解线索二叉排的定义及构造方法⑻掌握二叉树与树、森林之间相互转换的方法⑼理解哈夫曼树并掌握哈夫曼算法第六章图教学内容6.1 图的定义和基本术语6.2 图的存储结构6.3 图的遍历6.4 生成树和最小生成树6.5拓扑排序6.6关键路径6.7 最短路径教学要求⑴理解图的定义、术语及其含义⑵掌握图存储结构⑶理解并掌握图的遍历方法⑷领会生成树和最小生成树的概念⑸掌握构造最小生成树的算法思想⑹领会拓扑序列和拓扑排序的概念⑺理解并掌握拓扑排序的算法思想⑻理解并掌握关键路径的算法思想⑼理解并掌握最短路径的算法思想第七章查找教学内容7.1 线性表查找7.2 顺序查找7.3折半查找7.4 索引查找7.5 二叉排序树7.6 哈希表查找教学要求⑴掌握查找操作的基本思想⑵理解查找表的基本概念及查找原理⑶掌握在顺序表、有序表、索引表、树表以及哈希表等结构上进行查找操作的方法和算法描述⑷掌握哈希表的组织以及解决冲突的方法⑸能够根据不同场合确定合适的查找方法第八章内部排序教学内容8.1 基本概念8.2 插入排序8.3 交换排序8.4 选择排序8.5 归并排序8.6 基数排序8.7 各种排序方法的比较及应用教学要求⑴理解排序基本概念及内部排序和外部排序、稳定排序和非稳定排序的区别⑵掌握直接插入排序的基本思想、基本步骤和算法⑶掌握希尔排序的基本思想、基本步骤和算法⑷掌握冒泡排序的基本思想、基本步骤和算法⑸掌握快速排序的基本思想、基本步骤和算法⑹掌握直接选择排序的基本思想、基本步骤和算法⑺掌握堆排序的基本思想、基本步骤和算法⑻理解两个有序文件合并的方法和算法⑼了解归并排序的基本思想、基本步骤和算法⑽了解基数排序的基本思想、基本步骤和算法⑾了解根据不同场合确定合适的排序方法。

《数据结构》教学大纲●教学课时：72●适用对象：计算机应用专业●先修课程：C语言程序设计、Visual Basic程序设计一、课程性质、目的课程性质：数据结构是计算机应用专业的主干课程之一，属于专业课。

本课程是学习提高程序设计、学习数据库技术、进行应用系统开发的基础。

课程目的：通过学习使学生了解客观数据及其联系，在计算机内部物理表示的特性及其存储结构，了解数据的逻辑结构与物理实现的区别；理解数据类型的概念；掌握线性表、栈与队列、树、二叉树、图等典型的数据结构，掌握典型内部排序算法和查找算法；通过对各种数据结构和算法的学习，能够为具体的问题选择适当的逻辑结构、存储结构及其相应的算法；为学习操作系统、数据库等后序课程打好基础。

本课程是学习《计算机操作系统》、《数据库系统术》、以及今后进行软件开发工作的必修课。

本课程共需72课时，其中54课时讲授，18课时上机，为实现。

上机所用计算机语言为C语言。

二、教学基本内容教学基本要求1. 知识要求了解：数据结构、数据类型、抽象数据类型概念；算法和算法分析概念；树的定义、表示；分类、查找的基本概念；内部排序算法的效率分析。

掌握：线性数据结构线性表、栈、队列、串的抽象类型描述方法和物理实现算法；二叉树的性质与存储，二叉树的遍历，树与二叉树的转换；最优二叉树；图的存储与遍历，拓扑排序；内部排序的算法与实现；折半查找与动态查找；Hash表；2.能力要求：简单应用：运用线性表结构解决实际问题，如高次多项式的存储，集合类型的实现；应用栈结构，如编制递归算法，解决汉诺塔问题；简单表达式的求解；拓扑排序。

熟练应用：应用数据结构知识描述实际问题。

第1章绪论1.1 数据结构分析示例1.2 数据结构的基本概念1.2.1 什么是数据结构(了解)1.2.2 数据结构的图形表示1.2.3线性数据结构与非线性数据结构1.3算法分析的考虑1.3.1 什么是算法1.3.2 算法的复杂性1.3.3 算法描述性语言第2章线性表及其顺序存储结构2.1线性表的定义（掌握）2.2 栈及其应用2.3 队列及其应用2.4 字符串基本操作第3章线性链表3.1 线性链表的基本概念3.1.1 线性表的顺序存储问题3.1.2 线性链表3.1.3 带链的栈3.1.4 带链的队列3.2 线性链表的基本操作3.2.1 在线性链表中查找指定的元素3.2.2 线性链表的插入3.3.3 线性链表的删除3.3 循环链表3.4 多项式的表示与运算第4章数组4.1数组的定义与数组的顺序存储结构4.2 规则矩阵的压缩4.3 一般稀疏矩阵的表示4.3.1 稀疏矩阵的三列二维数组表示4.3.2 十字链表第5章树和二叉树5.1树的基本概念（掌握）5.2二叉树及其基本性质（掌握）5.2.1什么是二叉树（掌握）5.2.1 二叉树的基本性质（掌握）5.2.3 满二叉树与完全二叉树5.3 二叉树的基本性质存储结构5.3.1二叉树链表（了解）5.3.2 二叉树的生成5.4 二叉树的遍历（掌握）5.5 穿线二叉树5.6 表达式的线性化5.7 最优二叉树及其应用5.7.1 什么是最优二叉树5.7.2 最优二叉树的构造5.7.3赫夫曼树及其应用（简单应用）第6章图6.1图的定义（掌握）6.2图的存储结构（掌握）6.3图的遍历6.3.1深度优先搜索（掌握）6.3.2广度优先搜索（掌握）6.4最短距离问题第7章查找技术7.1顺序查找（掌握）7.2折半查找（掌握）7.3分块查找7.4 二叉树排序查找7.5 多层索引树查找第8章 Hash 表技术8.1 Hash（哈希）表的基本概念什么是Hash表哈希函数的构造方法处理冲突的方法8.2 常用的几种哈希表（掌握）第9章排序技术9.1交换类排序9.1.1冒泡排序（掌握）9.1.2 快速排序9.2插入排序（掌握）简单插入排序希尔排序9.3选择类排序9.4 拓扑分类9.5 其他排序方法简介归并排序（了解）基数排序三.实践环节四.学时分配撰稿人：钱国梁审定人：温绍洁系主任：侯冬梅。

《数据结构》教学大纲Data Structure课程编号：J6110G0003课程性质：学科基础课程适用专业：计算机科学与技术、网络工程、数字媒体技术先行课：计算机科学导论、离散数学、高级语言程序设计；后续课：无。

学分数：5主讲教师：任燕、王命延、冯豫华、周石林、王玮立等一、课程的目的与任务数据结构是信息与计算科学专业中一门重要的专业基础课程。

当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。

因此，数据结构课程在计算机应用专业中具有举足轻重的作用。

本课程的目的是使学生掌握数据组织、存储和处理的常用方法，为以后进行软件开发和学习后续专业课程打下基础。

主要任务是讨论现实世界中数据的各种逻辑结构，在计算机中的存储结构以及进行各种非数值运算的算法。

本课程达到《认证通用标准》规定中关于“毕业要求”的第三款项（具有运用工程基础知识和本专业基本理论知识解决问题的能力，具有系统的工程实践学习经历；了解本专业的前沿发展现状和趋势）、第四款项（具备设计和实施工程实验的能力，并能够对实验结果进行分析）。

二、课程的基本要求通过本课程的学习，要求学生了解数据结构及其分类、数据结构与算法的密切关系；熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构；掌握设计算法的步骤和算法分析方法；掌握数据结构在排序、查找和路由选择等常用算法中的应用。

最后学生应达到知识技能两方面的目标：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。

三、课程教学内容第一章绪论基本要求:掌握数据结构的基本概念，抽象数据类型在软件设计中的意义，算法的概念和算法的时间复杂度分析，了解算法的描述和评价。