大机二数据结构与算法

1、第二章数据结构与算法中 北 大 学 计 算 机 与 控 制 工 程 学 院School of Computer Science and Control Engineering . NUC 1 数据结构与算法 内容及要求掌握算法在解决实际问题中的重要性、算法的特征、算法的时间复杂度和空间复杂度了解线性数据结构，掌握队列和堆栈的逻辑结构及运算，掌握队列和堆栈的数据结构表示和基本应用了解非线性数据结构，掌握二叉树的定义与运算、二叉树的遍历 掌握基本的排序与查找算法，掌握算法的C+语言实现1-1数据结构与算法概述 众所周知，早期电子计算机的应用范围，几乎只局限于科学和工程的计算，其处理的对象是纯数值性

2、的信息，通常，人们把这类问题称为数值计算。近三十年来，电子计算机的发展异常迅猛，这不仅表现在计算机本身运算速度不断提高、信息存储量日益扩大、价格逐步下降，更重要的是计算机广泛地应用于情报检索、企业管理、系统工程等方面，已远远超出了科技计算的范围，而渗透到人类社会活动的一切领域。与此相应，计算机的处理对象也从简单的纯数值性信息发展到非数值性的和具有一定结构的信息。1、什么是数据结构计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型；然后设计一个解此数学模型的算法（Algorithm）；最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分

3、析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。什么是数据结构计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法 。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。数据结构的直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。2、基本概念和术语 数据数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并

4、被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。例如，一个个人书库管理程序所要处理的数据可能是一张如表1-1所示的表格。实例表1-1 个人书库管理程序数据实例结点结点结点也叫数据元素，它是组成数据的基本单位。在程序中通常把结点作为一个整体进行考虑和处理。例如，在表1-1所示的个人书库中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由10个结点构成。一般情况下，一个结点中含有若干个字段（也叫数据项）。例如，在表1-1所示的表格数据中，每个结点都有登录号、书号、书名、作者、出版社和价格等六个字段构成。字段是构成数据的最小单位。逻辑结构逻辑结构结点和结点之间

5、的逻辑关系称为数据的逻辑结构。在刚才的表格数据中，各结点之间在逻辑上有一种线性关系，它指出了10个结点在表中的排列顺序。存储结构存储结构数据在计算机中的存储表示称为数据的存储结构。在刚才所示的表格数据在计算机中可以有多种存储表示，例如，可以表示成数组，存放在内存中；也可以表示成文件，存放在磁盘上，等等。磁盘内存数据处理数据处理数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。在早期，计算机主要用于科学和工程计算，进入八十年代以后，计算机主要用于数据处理。据有关统计资料表明，现在计算机用于数据处理的时间比例达到80%以上，随着时间的推移和计算机应用的进一步普及，计

6、算机用于数据处理的时间比例必将进一步增大。数据结构数据结构（Data Structure）数据结构是研究数据元素（Data Element）之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。为了叙述上的方便和避免产生混淆，通常我们把数据的逻辑结构统称为数据结构，把数据的物理结构统称为存储结构（Storage Structure）。数据类型数据类型数据类型是指程序设计语言中各变量可取的数据种类数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密

7、切相关。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。算法算法 简单地说就是解决特定问题的方法（关于算法的严格定义，在此不作讨论）。特定的问题可以是数值的，也可以是非数值的。解决数值问题的算法叫做数值算法，科学和工程计算方面的算法都属于数值算法，如求解数值积分，求解线性方程组、求解代数方程、求解微分方程等。解决非数值问题的算法叫做非数值算法，数据处理方面的

8、算法都属于非数值算法。例如各种排序算法、查找算法、插入算法、删除算法、遍历算法等。数值算法和非数值算法并没有严格的区别。3、算法和算法的描述算法是执行特定计算的有穷过程：动态有穷：当执行一个算法时，不论是何种情况，在经过了有限步骤后，这个算法一定要终止；确定性：算法中的每条指令都必须是清楚的，指令无二义性；输入：具有0个或0个以上由外界提供的量；输出：产生1个或多个结果；可行性：每条指令都充分基本，原则上可由人仅用笔和纸在有限的时间内也能完成；注意：算法和程序是有区别的，即程序未必能满足动态有穷。我们只讨论满足动态有穷的程序。1)算法的描述 一个算法可以用自然语言、数字语言或约定的符号来描述，

9、也可以用计算机高级程序语言来描述，如Pascal语言、C语言或伪代码等。课程中，我们选用C+语言作为描述算法的工具。2)算法评价设计一个好的算法应考虑以下几个方面：正确性运行时间占用的存储空间简单性正确性“正确”的含义在通常的用法中有很大的差别，大体可分为以下四个层次： 程序不含语法错误； 程序对于几组输入数据能够得出满足规格说明要求的结果； 程序对于精心选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果； 程序对一切合法的输入数据都能产生满足规格说明要求的结果。 运行时间运行时间是指一个算法在计算机上运算所花费的时间。它大致等于计算机执行一种简单操作（如赋值操作、转向操作、

10、比较操作等等）所需要的时间与算法中进行简单操作次数的乘积。通常把算法中包含简单操作次数的多少叫做算法的时间复杂性，它是一个算法运行时间的相对量度。时间复杂性【例】计算f=1！+2！+3！+n！。void factorsum(n)int n； int i，j；int f，w； f=0； for (i=1;i=n;i+) w=1； for (j=1;j0，则除a0和an-1外，有且仅有一个直接前趋和一个直接后继数据元素，ai（0in-1）为线性表的第i个数据元素，它在数据元素ai-1之后，在ai+1之前。a0为线性表的第一个数据元素，而an-1是线性表的最后一个数据元素；若n=0，则为一个空表，表

11、示无数据元素。因此，线性表或者是一个空表（n=0），或者可以写成：（a0，a1，a2， ai-1，ai，ai+1，an-1）。抽象数据类型线性表的定义抽象数据类型线性表的定义如下：LinearList=(D,R)其中，D= ai| aiElemSet,i=0,1,2, ，n-1 n1R=| ai-1，aiD, i=0,1,2, ，n-1Elemset为某一数据对象集；n为线性表的长度。线性表的主要操作Initiate(L) 初始化：构造一个空的线性表L。Insert(L,i,x) 插入：在给定的线性表L中，在第i个元素之前插入数据元素x；线性表L长度加1。Delete(L,i) 删除：在给定的

12、线性表L中，删除第i个元素；线性表L的长度减1。Locate(L,x) 查找定位：对给定的值x，若线性表L中存在一个元素ai与之相等，则返回该元素在线性表中的位置的序号i，否则返回Null（空）。Length(L) 求长度：对给定的线性表L，返回线性表L的数据元素的个数。2、线性表的顺序存储结构线性表有两种基本的存储结构：顺序存储结构和链式存储结构。在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。在线性表的顺序存储结构中，其前后两个元素在存储空间中是紧邻的，且前驱元素一定存储在后继元素的前面。由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储

13、器中占用的空间大小相同，因此，要在该线性表中查找某一个元素是很方便的。线性表的顺序存储结构假设线性表中的第一个数据元素的存储地址为Loc(a0)，每一个数据元素占d字节，则线性表中第i个元素ai在计算机存储空间中的存储地址为：Loc(ai)= Loc(a0)+id在程序设计语言中，通常利用数组来表示线性表的顺序存储结构。这是因为数组具有如下特点：（1）数据中的元素间的地址是连续的；（2）数组中所有元素的数据类型是相同的。而这与线性表的顺序存储空间结构是类似的。示例若定义数组An= a0，a1，a2，an-1，假设每一个数组元素占用d个字节，则数组元素A0，A1，A2，An-1的地址分别为Loc

14、(A0)，Loc(A0)+d，Loc(A0)+2d，Loc(A0)+（n-1）d 。3、线性表类定义C+语言描述顺序存储结构下的线性表（顺序表）如下：typedef int ElemType; /数据元素的类型const int MAXSIZE=100; /数组的容量class SqList private: ElemType elemMAXSIZE; /数组 int length; /线性表长 public: SqList( void); /构造函数 SqList() ; /析构函数 void Creat() ; /创建一个线性表 void PrintOut(); /输出线性表 void I

15、nsert( int i, ElemType e); /插入函数 ElemType Delete(int i); /删除函数 ; /类定义结束 3、线性表类定义SqList:SqList() length=0; /构造函数，构造空表void SqList:Creat() /创建线性表函数 coutlength; coutn Input Data:n ; for(int k=0; kelemk; void SqList:PrintOut() /输出线性表函数 coutn length=length ; coutn PrintOut Data:n ; for(int k=0; klength;k+

16、) coutsetw(6)elemk; coutendl; 顺序表的插入操作在长度为length(0 length MAXSIZE-2)的顺序表的第i(0i length +1)个数据元素之前插入一个新的数据元素x时，需将最后一个即第length个至第i个元素（共length -i+1个元素）依次向后移动一个位置，空出第i个位置，然后把x插入到第i个存储位置，插入结束后顺序表的长度增加1。顺序表的插入操作 0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1 ai+1 i+2 ai+2 num anum 0 a0 1 a1 2 a2 i-1 ai-1 i x i+1 ai i+2a

17、i+1 numanum插入x顺序表的插入算法【算法2.1 顺序表的插入】void SqList:Insert( int i, ElemType e) int j; i-; /逻辑位置换算为C+数组下标值 if(ilength) cout “ i Error!”i; j-) elemj=elemj-1; /移动元素 elemi=e; /插入元素 length+; /线性表长加1 顺序表的删除操作 在长度为length(0 length MAXSIZE-1)的顺序表List，删除第i(0i length)个数据元素，需将第i+1至第length个数据元素的存储位置依次前移，并使顺序表的长度减1，若

18、i0或i length ，则无法删除，如图所示。 0 a0 1 a1 2 a2 i-1 ai-1 i ai+1 i+1 ai+2 num anum 0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1ai+1 numanum顺序表的删除算法 【算法2.2 顺序表的删除】ElemType SqList:Delete(int i) ElemType x; int j; i-; /转换成C+数组下标 if(ilength-1) cout i Error!endl; x=-1; /判断删除位置 else x=elemi; for(j=i; jno,p-score); p=p-next; w

19、hile(p!=NULL);执行结果：020910 87020915 79020921 92链表的顺序操作02091087&b02091579&c02092192Nullabc&aheadp=head;do printf(%-10s%dn, p-no,p-score); p=p-next; while(p!=NULL);for(p=head;p!=Null;p=p-next) printf(%-10s%dn, p-no,p-score);动态链表在程序执行过程中可从无到有的建立一个链表，即按使用开辟结点，输入各结点数据，并建立起前后的链接关系。从而避免了数组在使用前必须先定义固定的长度，以便在

20、内存中分配存贮空间，对于事前难以确定大小时，即需把数据空间定得足够大而浪费空间的弊端。单链表结点结构定义在C+语言中，实现线性表的链式存储结构的类型定义typedef int ElemType;struct NodeType /结点类型定义 ElemType data; NodeType *next; ;单链表类定义单链表类定义如下：class LinkList private: NodeType *Head; /链表头指针 public: LinkList(); /构造函数，初始化空链表 LinkList(); /析构函数 void Creat(); /创建一个非空链表 void Displ

21、ay(); /输出链表的数据元素 void Insert(int i,ElemType x); /插入 ElemType Delete(int i ); /删除第i个结点 ;/类定义结束单链表生成算法void LinkList: Creat() NodeType *p; p=new NodeType; /头结点,不是第一个结点。 p-next=NULL; Head=p; for(int i=1;idata=i;p-next=Head-next; /难点Head-next=p; /难点 单链表插入算法void LinkList:Insert(int i,ElemType x) NodeType

22、*p,*q,*s; int k=1; /计数器k，用于寻找i位置 q=Head; p=Head -next; while(knext; k+; if(k=i) s=new NodeType; s-data=x; s-next=p ; q-next=s; coutn 插入成功。 endl; else coutn i1或i太大，不存在。endl; coutnext; /q指向头指针，p指向第一个数据结点 while(knext; k+; if(p!=NULL) x=p-data; q-next=p-next; delete p; coutn 删除结点成功。endl; else coutn i1或i

23、太大，i不存在。endl; x=-1; return x; 链表特点链式存贮虽然比顺序存贮多占用一些指针空间，但存贮中的碎片可得到充分利用。删除后的结点也都会释放，等待重新使用；链式存取只能顺序存取，不能随机存取；对插入和删除操作，则利用链接存贮比较方便，无需移动元素。显然：各种存贮结构各有优缺点，使用中应根据实际应用需求选用适宜的存贮结构。1-4栈和队列从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称为操作受限的线性表。栈栈（stack）是一种只允许在一端进行

24、插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。栈的插入操作通常称为入栈或进栈(push)，而栈的删除操作则称为出栈或退栈(pop)。当栈中无数据元素时，称为空栈。根据栈的定义可知，栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。这种表是按照后进先出（LIFO，last in first out ）的原则组织数据的，因此，栈也被称为“后进先出”的线性表。栈的抽象数据类型ADT Stack 数据对象：D=ai |aiElemSet , i=1,2,n,n0 ; 数据关系：R= |

25、ai-1 ,aiD, i=2,3,n 约定an 端为栈顶，a1 端为栈底。 基本操作：初始化一个空栈； 判栈空，空栈返回True,否则返回False； 进栈，在栈顶插入一个元素； 出栈，在栈顶删除一个元素； 取栈顶元素值； 置栈为空状态； 求栈中数据元素的个数； 销毁栈； ADT Stack；栈的顺序存储结构 栈的顺序存储结构是利用一批地址连续的存储 单元依次存放自栈底到栈顶的数据元素，同时设指针top指向栈顶元素的位置。 采用顺序存储的方式存储的栈称之为顺序栈。 通常用一维数组来实现栈的顺序存储，将下标1设为栈底，这样空栈时栈顶指针top=0； 进栈时，栈顶指针top加，当top达到数组的最

26、大下标值时为栈满； 出栈时，栈顶指针top减。顺序栈类定义 typedef int ElemType; /数据元素的类型const int MAXSIZE=100; /数组的容量class SqStack private: ElemType elemMAXSIZE; int top; public: SqStack () top=0； /构造函数，初始化一个空栈 SqStack(); /析构函数 void SetEmpty() top=0； /置已有的栈为空栈 int IsEmpty() ; /判断栈是否为空 void Push( ElemType e); /进栈 ElemType Pop()

27、; /出栈 void PrintOut(); /输出栈中数据元素 ElemType GetPop(); /取栈顶元素数据 ;顺序栈类定义 void SqStack:PrintOut() /输出函数,不可改变top coutn PrintOut Data:n ; if(top=0)coutn 已是空栈！ /或用语句if(IsEmpty() cout=1;k-) coutsetw(6)elemk; coutendl; int SqStack:IsEmpty() /判断栈是否为空 if(top=0) return 1; else return 0; 顺序栈的进栈算法 假设要在栈顶插入数据元素e。首先

28、判断栈是否为满，栈不满才能执行进栈操作。在进栈时，先使栈顶指针top自加1，然后使数据元素e进栈。算法实现如下：void SqStack:Push( ElemType e) if(top=MAXSIZE-1) coutn栈满溢出endl; /判断栈是否为满 else top+; elemtop=e; /数据元素e进栈 顺序栈的出栈算法 假设要在栈顶删除数据元素e。首先判别栈是否为空，栈不空时才能出栈。出栈时先把栈顶元素值保存，然后栈顶指针top自减，最后返回删除的数据元素值。 ElemType SqStack:Pop() ElemType x; if(top=0) cout n 栈为空，不能进

29、行出栈操作endl; x=0; /表示未曾出栈 else x=elemtop; /出栈 top-; return x; 队列队列（queue）是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入的一端称为队尾（rear），只允许进行删除的一端称为队头(front)。队列的插入操作通常称为入队列或进队列，而队列的删除操作则称为出队列或退队列。当队列中无数据元素时，称为空队列。根据队列的定义可知，队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（FIFO，first in first ou

30、t ）的原则组织数据的，因此，队列也被称为“先进先出”表。队列的抽象数据类型 ADT Queue 数据对象：D=ai | aiElemSet , i=1,2,n, n0 ; 数据关系：R= |ai-1,aiD, i=2,3,n /约定a1端为队头，an端为队尾。 基本操作：初始化一个空队列； 判队空，空队返回True,否则返回False； 入队，在队尾插入一个元素； 出队，在队头删除一个元素； 取队头数据元素值； 置队列为空状态； 销毁队列； ADT Queue;队列顺序存储结构 队列的顺序存储常用一维数组来存储队列中的元素。为了指示队头和队尾的位置，需要设置队头front和队尾rear两个指

31、针，并约定：头指针front指向队列头元素的前一位置，尾指针rear指向队尾元素。 队列顺序存储结构 队列顺序存储结构 存在问题：“假溢出”解决方法： 采用平移元素方法 采用循环队列解决队列顺序存储结构循环队列 队列顺序存储结构循环队列循环队列判断队空条件是：rear=front循环队列判断队满条件是：(rear+1)%MAXSIZE=front进队操作如下：rear=(rear+1)% MAXSIZE; elemrear=x; 出队操作的如下：front=(front+1)% MAXSIZE; 循环队列类定义class SeQueue private: ElemType elemMAXSIZ

32、E; int front,rear; public: SeQueue() front=0; rear=0; /初始化空队列 SeQueue() ; int Empty(); void Display(); /输出队列 void AddQ(ElemType x); /进队 ElemType DelQ(); /出队 ElemType GetFront(); ; /循环队列类定义结束循环队列类定义int SeQueue:Empty() /判断循环队列是否为空 if(rear=front) return 1; else return 0; ElemType SeQueue:GetFront() /取队

33、首元素，不出队 ElemType x; if(front= rear) /判断队列是否为空 coutn Queu is Empty! endl; x=-1; else x= elem(front+1)%MAXSIZE; return x; 循环队列的进队算法 void SeQueue:AddQ(ElemType x) if(rear+1) % MAXSIZE=front) /判断是否满队 coutn Queu is Full! endl; else rear=(rear+1) % MAXSIZE; /尾指针加1 elemrear=x; /x进队列 循环队列的出队算法 ElemType SeQu

34、eue:DelQ () if(front=rear) /判断队列是否为空 coutn Queue is Empty! =0)个结点的有限集。在任意一棵非空树中：(1)有且仅有一个特定的称为根的结点；(2)当n1时,其余结点可分为m(m0)个互不相交的有限集T1,T2,.Tm，其中每一个集合本身又是一棵树，并且称为根的子树。树的基本概念 结点拥有的子树数称为结点的度。度为0的结点称为叶子或终端结点。度不为0的结点称为非终端结点或分支结点。树的基本概念 结点的层次 树中根结点的层次为1，根结点子树为第2层，以此类推。 树的度 树中所有结点度的最大值。 树的深度 树中所有结点层次的最大值。 有序树、

35、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。二叉树是由 n(n=0) 个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树,这是二叉树与树的最主要的差别。二叉树 满二叉树:一颗深度为k 且有2k -1个结点的二叉数称为满二叉树 完全二叉树：有一棵深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1n的结点位置一一对应时，则称这棵二叉树为完全二叉树。二叉树的 5 种形

36、式(a)空二叉树A (b)根和空的左右子树AB (c)根和左子树AB(d)根和右子树ACB (e)根和左右子树二叉树的性质 【性质1】 在二叉树的第i层上最多有2i-1个结点（i1）。 【性质2】 深度为K的二叉树最多有2K-1个结点（K1）。 【性质3】 对于任意一棵二叉树BT，如果度为0 的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。 【性质4】 具有n个结点的完全二叉树的深度为 log2n+1。其中，log2n 的结果是不大于log2n的最大整数。二叉树的性质【性质5】 对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i （1in）

37、，都有： （1）如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为 i/2。 （2）如果2in，则结点i没有左孩子；否则其左孩子结点的编号为2i。 （3）如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。遍历二叉树 二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。 所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。遍历二叉树的三种方法 先序1访问根结点2先序访问左子树3先序访问右子

38、树中序1中序访问左子树2中序访问根结点3中序访问右子树后序1后序访问左子树2后序访问右子树3访问根结点G HD E FB CA先序序列：ABDGCEFH中序序列：DGBAECHF后序序列：GDBEHFCA遍历二叉树的三种方法练习先序遍历结果：1,2,4,5,6,7,3 1-6查找与排序1.顺序查找 顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找

39、失败标志。查找 2 折半查找 折半查找要求查找表用顺序存储结构存放且各数据元素按关键字有序（升序或降序）排列，也就是说折半查找只适用于对有序顺序表进行查找。折半查找的基本思想 首先以整个查找表作为查找范围，用查找条件中给定值k与中间位置结点的关键字比较，若相等，则查找成功。 否则,如果k的值小于关键字的值，查找的数据元素只有可能在表的前半部分，继续对左子表进行折半查找；若k的值大于中间结点的关键字值，在右半部分子表中，所以应该继续对右子表进行折半查找。 每进行一次折半查找，要么查找成功，要么将查找范围缩小一半，重复，直到查找成功或查找范围缩小为空即查找失败为止。假设待查有序（升序）顺序表中数据

40、元素的关键字序列为（8,18,27,42,47,50,56, 68,95,120），用折半查找方法查找关键字值为27的数据元素。折半查找过程示例折半查找的完整算法int bin_search (Se_List a, keytype k) low=1; high=n; /置初始查找范围的低、高端指针 while (low=high) mid=(low+high)/2; /计算中间项位置 if (k=amid.key) break; /找到，结束循环 else if (k amid.key) high=mid-1;/给定值k小 else low=mid+1; /给定值k大 if (low=high

41、) return mid ; /查找成功 else return 0 ; /查找失败排序排序 是把一组无序的数据元素按照关键字值递增（或递减）的顺序重新排列。 1.直接插入排序首先将待排序记录序列中的第一个记录作为一个有序段，将记录序列中的第二个记录插入到上述有序段中形成由两个记录组成的有序段，再将记录序列中的第三个记录插入到这个有序段中，形成由三个记录组成的有序段，依此类推，每一趟都是将一个记录插入到前面的有序段中。1.直接插入排序假设当前欲处理第i个记录，则应该将这个记录插入到由前i-1个记录组成的有序段中，从而形成一个由i个记录组成的按关键字值排列的有序序列，直到所有记录都插入到有序段中

42、。一共需要经过n-1趟就可以将初始序列的n个记录重新排列成按关键字值大小排列的有序序列。直接插入排序例子例如:设待排序的记录共7个,关键码分别为8,3,2,5,9,1,6直接插入排序算法将第i个记录插入到由前面i-1个记录构成的有序段中主要有两个步骤： 将待插入记录ai 保存在a0中，即a0=ai; 搜索插入位置：j=i-1; /j最初指示i的前一个位置while (a0.key aj.key) aj+1=aj; /后移关键字值大于a0.key的记录 j=j-1; /将j指向前一个记录，为下次比较做准备aj+1=a0; /将a0放置在第j+1个位置上直接插入排序算法void insertsor

43、t (DataType a, int n) for (i=2; i=n; i+) /需要n-1趟 a0=ai; /将ai赋予监视哨 j=i-1; while (a0.keyaj+1），则将其交换，最终达到有序化。其处理过程为： （1）将整个待排序的记录序列划分成有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。 （2）对无序区从前向后依次将相邻记录的关键字进行比较，若逆序将其交换，从而使得关键字值小的记录向上“飘浮”（左移），关键字值大的记录好像石块，向下“堕落”（右移）。冒泡排序 每经过一趟冒泡排序，都使无序区中关键字值最大的记录进入有序区，对于由n个记录组成的记录序列，最多经

44、过n-1趟冒泡排序，就可以将这n个记录重新按关键字顺序排列。冒泡排序例子例如:设待排序文件的关键码为: 38,19,65,13,97,49,41,95,1,73冒泡排序算法void BubbleSort1 (DataType a,int n) for (i=n；i1；i-） for (j=1;ja j+1.key） temp=aj；aj=aj+1；aj+1=temp； 3.简单选择排序 简单选择排序的基本思想是：每一趟在n-i+1(i=1,2,3,.,n-1)个记录中选取关键字最小的记录作为有序序列中的第i个记录。它的具体实现过程为：简单选择排序的基本思想(1) 将整个记录序列划分为有序区域和

45、无序区域，有序区域位于最左端，无序区域位于右端，初始状态有序区域为空，无序区域含有待排序的所有n个记录。简单选择排序的基本思想 设置一个整型变量index，用于记录在一趟比较过程中关键字值最小的记录位置。 开始将它设定为无序区域的第一个位置，然后用它与无序区域中其他记录比较，若发现有比它的关键字还小的记录，就将index改为这个新的最小记录位置。 随后再用aindex.key 与后面的记录进行比较，随时修改index的值，一趟选择后index中保留的就是本趟关键字最小的记录位置。简单选择排序的基本思想(3) 将index位置的记录交换到无序区域的第一个位置，使得有序区域扩展了一个记录，而无序区

46、域减少了一个记录。 不断重复 (2)、(3)，直到无序区域剩下一个记录为止。此时所有的记录已经按关键字从小到大的顺序排列就位。选择排序例子例如:设待排序的记录共7个,关键码分别为8,3,2,5,9,1,6“第i 趟简单选择排序”的算法 (1)初始化：假设无序区域中的第一个记录为关键字值最小的元素，即将index=i; （2）搜索无序区域中关键字值最小的记录位置：for (j=i+1;j=n;j+)if (aj.keya.index.key) index=j; （3）将无序区域中关键字最小的记录与无序区域的第一个记录进行交换，使得有序区域由原来的i-1个记录扩展到i个记录。简单选择排序完整算法void selecsort ( DataType a, int n) for( i=1; in; i+) /对n个记录进行n-1趟的简单选择排序 index=i; /初始化第i趟简单选