100，则整个线性表扫描完毕，仍未找到与100相等的元素，表示线性表中没有要查找的元素。
在下列两种情况下也只能采用顺序查找：
①如果线性表为无序表（表中的排列是无序的），则不管是顺序存储结构还是链式存储结构，只能用顺序查找；
②即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
1.7.2 二分法查找
二分法查找，也称拆半查找，是一种高效的查找方法。能使用二分法查找的线性表必须满足用顺序存储结构和线性表是有序表两个条件。
“有序”是特指元素按非递减排列，即从小到大排列，但允许相邻元素相等。下一节排序中，有序的含义也是如此。
对于长度为n的有序线性表，利用二分法查找元素X的过程如下： 步骤1：将X与线性表的中间项比较； 步骤2：如果X的值与中间项的值相等，则查找成功，结束查找； 步骤3：如果X小于中间项的值，则在线性表的前半部分以二分法继续查找；
步骤4：如果X大于中间项的值，则在线性表的后半部分以二分法继续查找。
例如，长度为8的线性表关键码序列为：[6，13，27，30，38，46，47，70]，被查元素为38，首先将与线性表的中间项比较，即与第4个数据元素30相比较，38大于中间项30的值，则在线性表[38，46，47，70]中继续查找；接着与中间项比较，即与第2个元素46相比较，38小于46，则在线性表[38]中继续查找，最后一次比较相等，查找成功。
顺序查找法每一次比较，只将查找范围减少1，而二分法查找，每比较一次，可将查找范围减少为原来的一半，效率大大提高。
对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较logn次，而顺序查找需要比较n次。
2§1.8 排序
排序：将一个无序序列整理成按值非递减顺序排列的有序序列。排序可以在不同的存储结构上实现，在本节所介绍的排序方法中，其排序的对象一般认为是顺序存储的线性表，在程序设计语言中就是一维数组。
1. 交换类排序法（借助数据元素之间的互相交换进行排序）
（1）冒泡排序法（通过相邻数据元素的交换逐步将线性表变成有序）
首先，从表头开始往后扫描线性表，逐次比较相邻两个元素的大
小，若前面的元素大于后面的元素，则将它们互换，不断地将两个相邻元素中的大者往后移动，最后最大者到了线性表的最后。
然后，从后到前扫描剩下的线性表，逐次比较相邻两个元素的大小，若后面的元素小于前面的元素，则将它们互换，不断地将两个相邻元素中的小者往前移动，最后最小者到了线性表的最前面。
对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时已经排好序。在最坏的情况下，冒泡排序需要比较次数为n(n-1)/2。 （2）快速排序法
任取待排序序列中的某个元素作为基准（一般取第一个元素），通过一次排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。
在快速排序过程中，随着对各个子表不断进行分割，划分出的子表会越来越多，但一次有只能对一个子表进行再分割处理，需要将暂时不分割的子表记忆起来，这就要用一个栈来实现 2. 插入类排序法
①.简单插入排序法：将无序序列中的各元素依次插入到已经有序的线性表中。最坏情况需要n(n-1)/2次比较；
②.希尔排序法：将整个无序序列分割成若干小的子序列分别进行插入排序，最坏情况需要O(n1.5)次比较。
3. 选择类排序法
①.简单选择排序法：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置），然后对剩下的子表采用同样的方法，直到子表为空为止。最坏情况需要n(n-1)/2次比较；
② 堆排序法
点)元素必为序列的n个元素中的最大项。
堆排序法对于规模较小的线性表并不适合，但对于较大规模的线性表来说是很有效的，最坏情况需要O(nlogn)次比较。
2相比以上几种（除希尔排序法外），堆排序法的时间复杂度最小。
第一章完
第2章 程序设计基础
§2.1 程序设计的方法与风格
程序设计是一门技术，需要相应的理论、技术、方法和工具来支持，就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计阶段。除此之外，程序设计风格也很重要，它会深刻的影响软件的质量和可维护性，因此，程序设计风格对保证程序的质量很重要??
一般来讲，程序设计风格是指编写程序时所表现的特点、习惯和逻辑思路。程序就设计风格总体而言应该强调简单和清晰，程序必须是可以理解的可以认为，著名的“清晰第一，效率第二”的论点已成为当今主导的程序设计风格。
养成良好的程序设计风格，主要考虑下述因素： （1）源程序文档化
①.符号名的命名：符号名的命名应具有一定的实际含义，以便于对程序功能的理解；
②.程序注释：在源程序中添加正确的注释可帮助人们理解程序。程序注释可分为序言性注释和功能性注释。语句结构清晰第一、效率第二；
③.视觉组织：通过在程序中添加一些空格、空行和缩进等，使人们在视觉上对程序的结构一目了然。 （2）数据说明的方法
为使程序中的数据说明易于理解和维护，可采用下列数据说明的风格，见表2-1。
（3）语句的结构程序
语句的结构程序应该简单易懂，语句构造应该简单直接。 （4）输入和输出
在设计和编程时应考虑如下原则:
Ⅰ.对所有的输入数据都要检验数据的合法性； Ⅱ.检查输入项的各种重要组合的合理性；
Ⅲ.输入数据时，应允许使用自由格式；应允许缺省值； Ⅳ.输入一批数据时，最好使用输入结束标志； Ⅴ.在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入放入请求，同时在数据输入过程中和输入结束时，应当在屏幕上给出状态信息；
Ⅵ.当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性，给所有的输出加注释，并设计输出报表格式， §2.2 结构化程序设计 1. 结构化程序设计的原则
结构化程序设计方法引入了工程思想和结构化思想，使大型软件的开发和编程得到了极大的改善。结构化程序设计方法的主要原则为：自顶向下、逐步求精、模块化和限制使用goto语句。
①.自顶向上：先考虑整体，再考虑细节；先考虑全局目标，再考虑局部目标；
②.逐步求精：对复杂问题应设计一些子目标作为过渡，逐步细化；
③.模块化：把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。
④.限制使用goto语句：在程序开发过程中要限制使用goto语句。
2. 结构化程序的基本结构
结构化程序的基本结构有三种类型：顺序结构、选择结构和循环结构。