第5章 数据结构与算法.ppt

第第5 5章章 数据结构与算法数据结构与算法计算机科学概论•理解数据结构的概念，理解数据结构的逻辑和存储结构；理解数据结构的概念，理解数据结构的逻辑和存储结构；•理解算法的概念和算法的基本特性，了解算法复杂度的度理解算法的概念和算法的基本特性，了解算法复杂度的度量方法；量方法；•理解线性数据结构，理解顺序存储和链式存储的存储方法；理解线性数据结构，理解顺序存储和链式存储的存储方法；•描述栈和队列、串和数组这几个线性数据结构的概念；描述栈和队列、串和数组这几个线性数据结构的概念；•了解非线性的数据结构，了解树、二叉树以及图的概念和了解非线性的数据结构，了解树、二叉树以及图的概念和数据结构；数据结构；•理解排序的概念，描述插入、选择、气泡和快速排序的算理解排序的概念，描述插入、选择、气泡和快速排序的算法；法；•理解查找的概念，描述顺序查找和折半查找的算法，并能理解查找的概念，描述顺序查找和折半查找的算法，并能够比较它们够比较它们•理解递归的概念，能够在实践中了解递归的应用理解递归的概念，能够在实践中了解递归的应用 教 学 目目 的的1 23学学 习习 内内 容容数据结构数据结构概述概述 线性结构线性结构 非线性结非线性结构构 基本算法基本算法 递归递归45学学 习习 重重 点点•数据结构的基本概念数据结构的基本概念•算算法法的的描描述述、、流流程程图图的的使使用用以以及及算算法法的的复复杂杂度度的的衡量衡量•顺序存储和链式存储的方法顺序存储和链式存储的方法•栈、队列、串和数组的概念和用法栈、队列、串和数组的概念和用法•二叉树数据结构二叉树数据结构•查询、排序和递归算法查询、排序和递归算法第一节第一节 数据结构概述数据结构概述1 数据结构概述数据结构概述1.1《《数据结构数据结构》》研究的对象研究的对象(1) 对所加工的对象进行逻辑组织(2) 如何把加工对象存储到计算机中去(3) 数据运算F数据结构正是讨论非数值类问题的对象描述、信息组织方法及其相应的操作 [例例5-1] 设有一个号码薄，有设有一个号码薄，有N个人的姓名和号码。

要求设计个人的姓名和号码要求设计一个程序，按人名查找号码，若不存在则给出不存在的信息一个程序，按人名查找号码，若不存在则给出不存在的信息1 数据结构概述数据结构概述1.2 数据结构相关概念数据结构相关概念1.1.基本概念和术语基本概念和术语数据元素、结点、数据项、关键字或主关键字、数据元素、结点、数据项、关键字或主关键字、 次关键字、次关键字、数据对象、数据结构数据对象、数据结构 2.2.数据结构数据结构 特性相同的数据元素构成的集合中，如果在数据元素特性相同的数据元素构成的集合中，如果在数据元素之间存在一种或多种特定的关系，则称之为数据结构之间存在一种或多种特定的关系，则称之为数据结构 Data-Structure=(D,R) 其中，其中，D D是数据元素的有限集，是数据元素的有限集，R R是是D D上关系的有限集上关系的有限集1 数据结构概述数据结构概述3 3. .四类基本的四类基本的数据结构数据结构•集合结构集合结构在集合结构中，数据元素间的关系是在集合结构中，数据元素间的关系是“属于属于同一个集合同一个集合”。

集合是元素关系极为松散的一种结构，集合是元素关系极为松散的一种结构，各元素间没有直接的关联各元素间没有直接的关联•线性结构线性结构该结构的数据元素之间存在着一对一的关系该结构的数据元素之间存在着一对一的关系•树型结构树型结构该结构的数据元素之间存在着一对多的关系该结构的数据元素之间存在着一对多的关系•图形结构图形结构该结构的数据元素之间存在着多对多的关系，该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构图形结构也称作网状结构 1 数据结构概述数据结构概述[ [例例5-2] 5-2] 线性数据结构线性数据结构=(D,S)=(D,S) D={1,2,3,4,5,6,7,8,9,10} D={1,2,3,4,5,6,7,8,9,10} S={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>,<6,7>,<7,8>, S={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>,<6,7>,<7,8>, <8,9>,<9,10>} <8,9>,<9,10>}1 数据结构概述数据结构概述[例例5-3] 图形数据结构图形数据结构=(D,R)D={1, 2, 3, 4, 5, 6, 7, 8, 9}R={<1,2>,<1,3>,<2,4>,<2,5>,<2,6>,<2,8>,<3,2>,<3,4>, <4,5>,<5,7>,<6,7>,<6,9>,<7,9>,<8,9>}1 数据结构概述数据结构概述 [ [例例5-4] 5-4] 树形结构树形结构 = =（（D,RD,R））D={a, b, c, d, e, f, g, h, i, j, k, l}D={a, b, c, d, e, f, g, h, i, j, k, l}R={,,,,,,,,,,,,,,,,, ,}c,j>, ,}1 数据结构概述数据结构概述1.3 数据结构的分类数据结构的分类1 1、、按数据结构的性质划分按数据结构的性质划分 数据的逻辑结构数据的逻辑结构——数据元素之间的逻辑关系数据元素之间的逻辑关系 （（设计算法设计算法—— 数学模型数学模型）） 数据的物理结构数据的物理结构——数据结构在计算机中的映像数据结构在计算机中的映像 （（存储结构，算法的实现存储结构，算法的实现））2 2、、按数据结构的操作来划分按数据结构的操作来划分 静态结构静态结构——经过操作后，数据的结构特征保持不变（如数组）。

经过操作后，数据的结构特征保持不变（如数组） 半静态结构半静态结构——经过操作后，数据的结构特性只允许很小变迁经过操作后，数据的结构特性只允许很小变迁（如栈、队列）如栈、队列） 动态结构动态结构——经过操作后，数据的结构特性变化比较灵活，可随经过操作后，数据的结构特性变化比较灵活，可随机地重新组织结构（如指针）机地重新组织结构（如指针）1 数据结构概述数据结构概述1.3 数据结构的分类数据结构的分类3 3、、按数据结构在计算机内的存储方式来划分按数据结构在计算机内的存储方式来划分 顺序存储结构顺序存储结构——借助元素在存储器的相对位置来表示数据元素之间借助元素在存储器的相对位置来表示数据元素之间的逻辑关系的逻辑关系 链式存储结构链式存储结构——借助指示元素存储地址的指针表示数据元素之间的借助指示元素存储地址的指针表示数据元素之间的逻辑关系逻辑关系 索引存储索引存储结构结构——在存储结点的同时，还建立附加在存储结点的同时，还建立附加 的索引表，索引表的索引表，索引表中的每一项称为索引项，形式为：关键字，地址。

中的每一项称为索引项，形式为：关键字，地址 散列存储散列存储结构结构——根据结点的关键字直接计算出该结点的存储地址根据结点的关键字直接计算出该结点的存储地址说明：说明：四种存储方法可结合起来对数据结构进行存储映像四种存储方法可结合起来对数据结构进行存储映像1 数据结构概述数据结构概述1.4 算法及其描述和算法分析算法及其描述和算法分析1、算法的概念及特征、算法的概念及特征 算法算法: 对问题求解的描述，为解决问题给出的一个确定的、有限长对问题求解的描述，为解决问题给出的一个确定的、有限长的操作序列的操作序列 算法具有以下五个重要的特征：算法具有以下五个重要的特征： 1）有穷性：有穷性：一个算法必须保证执行有限步之后结束一个算法必须保证执行有限步之后结束 2）确切性：确切性：算法的每一步骤必须有确切的定义算法的每一步骤必须有确切的定义 3）输入：输入：一个算法有一个算法有0个或多个输入，以刻画运算对象的初始情况，个或多个输入，以刻画运算对象的初始情况，所谓所谓0个输入是指算法本身定除了初始条件。

个输入是指算法本身定除了初始条件 4）输出：输出：一个算法有一个或多个输出，以反映对输入数据加工后一个算法有一个或多个输出，以反映对输入数据加工后的结果没有输出的算法没有实际意义没有输出的算法没有实际意义 5）可行性：可行性：算法原则上能够精确地运行，而且人们用笔和纸做有算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成限次运算后即可完成1 数据结构概述数据结构概述1.4 算法及其描述和算法分析算法及其描述和算法分析2 2、、、、算法的描述算法的描述: 1）流程图）流程图 2）伪代码）伪代码——类程序设计语言类程序设计语言 3 3、、、、算法的基本结构算法的基本结构 :1）顺序结构）顺序结构 2）分支结构）分支结构 3）循环结构）循环结构1 数据结构概述数据结构概述1 数据结构概述数据结构概述 算法基本结构示意图算法基本结构示意图1.4 算法及其描述和算法分析算法及其描述和算法分析 4 4、、、、算法效率衡量方法与准则算法效率衡量方法与准则 :时间复杂度：时间复杂度：指算法从开始执行到处理结束所需要的指算法从开始执行到处理结束所需要的总时间。

总时间 T（（n））= O（（f(n)））空间复杂度：空间复杂度：指算法从开始执行到处理结束所需的存指算法从开始执行到处理结束所需的存储量空间的总和储量空间的总和 S（（n））= O（（g(n)））1 数据结构概述数据结构概述1.4 算法及其描述和算法分析算法及其描述和算法分析 5 5、、、、算法与数据结构的关系算法与数据结构的关系:•计算机科学家沃斯（计算机科学家沃斯（N.Wirth））提出的提出的:“算法算法+数据结构数据结构=程序程序” 揭示了程序设计的本质：对实际问题选择一种好的数据结构，揭示了程序设计的本质：对实际问题选择一种好的数据结构，加上设计一个好的算法，而好的算法很大程度上取决于描述加上设计一个好的算法，而好的算法很大程度上取决于描述实际问题的数据结构算法与数据结构是互相依赖、互相联实际问题的数据结构算法与数据结构是互相依赖、互相联系的•一个算法总是建立在一定数据结构上的；反之，算法不确定，一个算法总是建立在一定数据结构上的；反之，算法不确定，就无法决定如何构造数据。

就无法决定如何构造数据1 数据结构概述数据结构概述第二节第二节 线性结构线性结构2.1 线性表线性表 1.1.线性表的定义线性表的定义 线性表线性表是是n(n>=0)个数据元素的个数据元素的有限序列有限序列，表中各个，表中各个元素具有相同元素具有相同的的属性，表中相邻元素间存在属性，表中相邻元素间存在“序偶序偶”关关系 记做：记做：(a1,a2,…….ai-1,ai,ai+1,…,an-1,an ) 其中，其中，ai-1称为称为ai 的的直接前驱元素直接前驱元素，，ai+1是是ai的的直接后直接后继元素继元素 线性表的长度：线性表的长度：表中的元素个数表中的元素个数 n 位序：位序：i称元素称元素ai性表中的位序性表中的位序2 线性结构线性结构2.1 线性表线性表 2 2. .线性表的线性表的顺序表示和实现顺序表示和实现 线性表的顺序存储是指在内存中用地址连续的一块存线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为的线性表称其为顺序表顺序表。

2 线性结构线性结构2.1 线性表线性表 2 2. .线性表的线性表的顺序表示和实现顺序表示和实现 顺序表顺序表——线性表的顺序存储表示线性表的顺序存储表示 Const LIST_INIT_SIZE=100; (C++规范规范) Const LISTINCREMENT=10; #define LIST_INIT_SIZE 100 (C规范规范) Typedef Struct {Elemtype * elem;Int length;Intlistsize;Int incrementsize; }SqList;2 线性结构线性结构2 线性结构线性结构2.1 线性表线性表3 3. . 线性表的线性表的链式表示和实现链式表示和实现 链表链表是通过一组任意的存储单元来存储线性表中的数是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间的关系，对每个数据据元素的，为建立起数据元素之间的关系，对每个数据元素元素ai，除了存放数据元素的自身的信息，除了存放数据元素的自身的信息ai之外，还需要之外，还需要和和ai一起存放其后继一起存放其后继ai+1所在的存贮单元的地址，这两部所在的存贮单元的地址，这两部分信息组成一个分信息组成一个“节点节点”。

2 线性结构线性结构2.1 线性表线性表 3.3.线性表的链式表示和实现线性表的链式表示和实现 单链表单链表——线性表的链式存储表示线性表的链式存储表示 F 数据域（数据域（data）和指针域（）和指针域（next）） F 存储表示存储表示typedef struct Lnode{ElemTypedata;Struct Lnode*next;}Lnode, *LinkList; 2 线性结构线性结构2 线性结构线性结构2.1 线性表线性表 3 3. .线性表的线性表的链式表示和实现链式表示和实现 双向链双向链表表（循环链表）（循环链表）——线性表的线性表的链式链式存储表示存储表示 概念：两个指针，分别指向前驱概念：两个指针，分别指向前驱元素元素和后继和后继元素元素 typedef struct DuLnode{ ElemTypedata; Struct DuLnode*prior; Struct DuLnode*next; }DuLnode, *DuLinkList; 2 线性结构线性结构2.2 栈和队列栈和队列1.1.栈的定义栈的定义 栈（栈（Stack））是限定只能在表得一端进行插入和删除是限定只能在表得一端进行插入和删除操作得线性表，又称限定性线性表结构。

操作得线性表，又称限定性线性表结构2.2.栈的结构特点和操作栈的结构特点和操作 Ø栈顶栈顶( (Top) )、、栈底栈底( (Bottom),),先入后出先入后出(LIFO) Ø栈的基本操作栈的基本操作 InitStack（&S） GetTop(S,&e) DestroyStack(&S) Push(&S, e) ClearStack(&S) Pop(&S,&e) StackEmpty（S） StackTraverse(S) StackLength（S）2 线性结构线性结构堆栈结构示意图堆栈结构示意图2 线性结构线性结构2.2 栈和队列栈和队列3.3.队列的定义队列的定义 队列（队列（Queue）是限定只能在表得一端进行插入在）是限定只能在表得一端进行插入在表的另一端进行删除操作的线性表表的另一端进行删除操作的线性表4.4.队列的结构特点和操作队列的结构特点和操作 Ø队列头队列头(front)、、队列尾队列尾(rear)，，先入先出先入先出(FIFO)Ø队列的基本操作队列的基本操作 InitQueue(&Q) GetHead(Q,&e) DestroyStack(&S) EnQueue(&Q,e) ClearQueue(&Q) Dequeue(&Q,&e) QueueEmpty(Q) QueueTraverse(Q) QueueLength(Q)2 线性结构线性结构2.3 串和数组串和数组1.1.串串的定义和表示方法的定义和表示方法•串定义串定义 串（即字符串）串（即字符串）是一种特殊的线性表，它的数据元素是一种特殊的线性表，它的数据元素仅由一个字符组成仅由一个字符组成 字符串字符串，由零个或多个字符组成的有限序列。

由零个或多个字符组成的有限序列 S S＝＝““a a0 0a a1 1.....a.....an-1n-1””串的长度串的长度：：n n空串空串：：n=0n=0，，Null StringNull String子串与主串子串与主串，子串的位置（从，子串的位置（从0 0开始）开始）串的比较串的比较：最大相等前缀子序列：最大相等前缀子序列2 线性结构线性结构2.3 串和数组串和数组1.1.串串的定义和表示方法的定义和表示方法•串的表示方法串的表示方法 定长顺序存储表示定长顺序存储表示 两种表示方法：两种表示方法： 1)1)下标为下标为0 0的数组存放长度的数组存放长度 ( (pascalpascal) ) typedef unsigned char SString[MAXSTLEN+1] ; 2) 2)在串值后面加在串值后面加‘‘\0\0’’结束结束 (C(C语言语言) ) 堆分配存储表示堆分配存储表示 串变量的存储空间是在程序执行过程中动态分配的，串变量的存储空间是在程序执行过程中动态分配的，程序中出现的所有串变量可用的存储空间是一个共享空程序中出现的所有串变量可用的存储空间是一个共享空间，称为间，称为“堆堆”。

2 线性结构线性结构2.3 串和数组串和数组2.2.数组数组的定义和操作的定义和操作•数组定义数组定义 数组是一个具有固定格式和数量的数据有序集，每一数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识数组可以看作线个数据元素有唯一的一组下标来标识数组可以看作线性表的推广数组作为一种数据结构其特点是结构中的性表的推广数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据元素本身可以是具有某种结构的数据，但属于同一数据类型•二维数组定义二维数组定义 其数据元素是一维数组的线形表其数据元素是一维数组的线形表•N N维数组定义维数组定义 其数据元素是其数据元素是N N－－1 1维数组的线形表维数组的线形表2 线性结构线性结构2.3 串和数组串和数组2.2.数组数组的定义和操作的定义和操作•数组的操作数组的操作initarray(&A,n,bound1,bound2...boundn) ——初始化初始化Destroyarray(&A) —— 删除数组删除数组value(A,&e,index1,index2......indexn) —— 赋值赋值assign(&A,e,index1,index2......indexn) —— 分配数组分配数组2 线性结构线性结构2.3 串和数组串和数组3.3.数组数组的存储方式和表示的存储方式和表示•数组元素的两种存储方式数组元素的两种存储方式行主序存储行主序存储列主序存储列主序存储•数组中元素在内存映象中的关系数组中元素在内存映象中的关系:二维数组二维数组A[m][n]LOC[i,j]=LOC[0,0]+(i*n+j)*L三维数组三维数组B[p][m][n]LOC[i,j,k]=LOC[0,0,0]+(i*m*n+j*n+k)*L2 线性结构线性结构第三节第三节 非线性结构非线性结构3.1 树树 1.1.树的定义与结构特点树的定义与结构特点 •树的定义树的定义 n(nn(n>=0)>=0)个数据元素（结点）的有限集个数据元素（结点）的有限集D D，若，若D为为空集，空集，则为则为空树空树。

否则：否则： 在在D D中存在唯一的称为中存在唯一的称为根根的数据元素；的数据元素； 当当n>1时时，，其余结点可分为其余结点可分为m（（m>0））个互不相交的有个互不相交的有限子集限子集T1，，T2，，......，，Tm，，其中每个子集本身又是一其中每个子集本身又是一颗树，并成为根的颗树，并成为根的子树 3 非线性结构非线性结构3.1 树树1.1.树的定义与结构特点树的定义与结构特点 •树的结构特点树的结构特点 树具有下面两个特点：树具有下面两个特点： (1) 树的根节点没有前驱节点，除根节点之外的所有节点有树的根节点没有前驱节点，除根节点之外的所有节点有且只有一个前驱节点且只有一个前驱节点 (2) 树中所有节点可以有零个或多个后继节点树中所有节点可以有零个或多个后继节点 3 非线性结构非线性结构3 非线性结构非线性结构典型的树结构典型的树结构3.1 树树 2 2. .二叉树二叉树 •二叉树的定义二叉树的定义 二叉树（二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一）是个有限元素的集合，该集合或者为空、或者由一个称为根个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。

成 3 非线性结构非线性结构二叉树的五种基本形态二叉树的五种基本形态  2.2.2.2.二叉树二叉树 •满二叉树和完全二叉树满二叉树和完全二叉树 满二叉树（满二叉树（full binary treefull binary tree）：所有结点度为）：所有结点度为2 2，叶子结点在同，叶子结点在同一层次 完全二叉树（完全二叉树（complete binary treecomplete binary tree）：）：一棵深度为一棵深度为k k的有的有n n个节个节点的二叉树，对树中的节点按从上至下、从左到右的顺序进行编号，点的二叉树，对树中的节点按从上至下、从左到右的顺序进行编号，如果编号为如果编号为i i（（1≤i≤n1≤i≤n）的节点与满二叉树中编号为）的节点与满二叉树中编号为i i的节点在二叉树的节点在二叉树中的位置相同，则这棵二叉树称为完全二叉树中的位置相同，则这棵二叉树称为完全二叉树 3 非线性结构非线性结构3.1 树树 3.3. 树的运算树的运算 树树的的运运算算主主要要是是插插入入节节点点、、删删除除节节点点和和遍遍历历等等几几种种。

插插入入节节点点、、删删除除节节点点运运算算改改变变树树的的结结构构，，但但要要求求在在改改变变结结构构的的同同时时，，保保持持树树的的特特性性不不变变，，对对于于二二叉叉树树，，插插入入和和删删除除操操作作后后的的树树仍仍然然是是一一棵棵二二叉叉树树这这两两个个操操作作过过于于复复杂杂，，在在专专业业书书籍籍中中介绍，在此不做详细讨论介绍，在此不做详细讨论 3 非线性结构非线性结构3.1 树树 3.3. 树的运算树的运算•树的基本运算操作：树的基本运算操作： InitTree（（&T）） DestroyTree（（&T）） CreateTree(&T,definition) TreeEmpty(T) TreeDepth(T) Parent(T, e) LeftChild（（T，，e）） Rightsibling(T,e) InsertChild（（&T,&p,i,C）） DeleteChild（（&T,&p,i）） Traverse（（T）） 3 非线性结构非线性结构3.2 图图 1.1.图的定义与相关概念图的定义与相关概念 •图的定义图的定义 图是由一组图是由一组节点（节点（vertexvertex））的有穷集的有穷集V(G)V(G)和和一组和和一组顶点顶点间的连线间的连线(arc)(arc)的集合的集合E(G)E(G)组成的一种抽象数据结构。

记做：组成的一种抽象数据结构记做：G G＝＝(V(V，，E)E)V V是数据结构中的数据元素，是数据结构中的数据元素，E E是集合上的关系是集合上的关系 3 非线性结构非线性结构3.2 图图 1.1.图的定义与相关概念图的定义与相关概念 •图的相关概念图的相关概念•弧弧(arc)(arc)、弧头（终点）、弧尾（起点）：、弧头（终点）、弧尾（起点）：< >表示从表示从v v到到w w的弧的弧 •有向图有向图(digraph) (digraph) 、无向图、无向图( (undigraphundigraph) ) 、边、边: : ( (v,wv,w) )代表代表< >和和< > •有向网、无向网：有向网、无向网：带权的有向图和无向图带权的有向图和无向图 •完全图（完全图（complete graphcomplete graph）：边）：边e e为为n(n-1)/2n(n-1)/2•有向完全图：弧有向完全图：弧e e为为n(n-1)n(n-1) 3 非线性结构非线性结构3 非线性结构非线性结构3.2 图图 2 2. .图图的的运算运算 •图的基本运算图的基本运算 添加顶点添加顶点——将一个新顶点插入到图中将一个新顶点插入到图中 添加边添加边——连接一个顶点和一个目标顶点连接一个顶点和一个目标顶点 删除顶点删除顶点——从一个图里移除一个顶点，同时删除连接顶点的边。

从一个图里移除一个顶点，同时删除连接顶点的边 查找顶点查找顶点——通过遍历图来查找特定的顶点通过遍历图来查找特定的顶点 图的遍历图的遍历——指从图中的任一顶点出发，对图中的所有顶点访问一次且指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次只访问一次 说明：图的遍历是图的一种基本操作，图的许多其他操作都是建立在遍说明：图的遍历是图的一种基本操作，图的许多其他操作都是建立在遍历操作的基础之上历操作的基础之上3 非线性结构非线性结构第四节第四节 基本算法基本算法4.1 排序排序 1.1.排序排序的定义的定义与相关概念与相关概念 •排序：排序：将一组杂乱无章的数据排列成一个按关键字有序的序列将一组杂乱无章的数据排列成一个按关键字有序的序列 •数据表数据表(datalist): 它是待排序数据对象的有限集合它是待排序数据对象的有限集合•关关键键字字(key): 通通常常数数据据对对象象有有多多个个属属性性域域，，即即多多个个数数据据成成员员组组成成，，其其中中有有一一个个属属性性域域可可用用来来区区分分对对象象，，作作为为排排序序依依据据。

该该域域即即为为关关键键字字每每个个数数据据表表用用哪哪个个属属性性域域作作为为关关键键字字，，要要视视具具体体的的应应用用需需要要而而定定即即使使是是同同一一个个表表，，在在解解决决不不同同问问题题的的场场合合也也可可能能取取不不同同的域做关键字的域做关键字4 基本算法基本算法4.1 排序排序 1.1.排序排序的定义的定义与相关概念与相关概念 •主关键字主关键字: 如果在数据表中各个对象的关键字互不相同，这种关如果在数据表中各个对象的关键字互不相同，这种关键字即主关键字按照主关键字进行排序，排序的结果是唯一的键字即主关键字按照主关键字进行排序，排序的结果是唯一的•次关键字次关键字: 数据表中有些对象的关键字可能相同，这种关键字称数据表中有些对象的关键字可能相同，这种关键字称为次关键字按照次关键字进行排序，排序的结果可能不唯一为次关键字按照次关键字进行排序，排序的结果可能不唯一•排序算法的稳定性排序算法的稳定性: 如果在对象序列中有两个对象如果在对象序列中有两个对象r[i]和和r[j]，它们，它们的关键字的关键字 k[i] == k[j]，且在排序之前，对象，且在排序之前，对象r[i]排在排在r[j]前面。

如前面如果在排序之后，对象果在排序之后，对象r[i]仍在对象仍在对象r[j]的前面，则称这个排序方法的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的是稳定的，否则称这个排序方法是不稳定的4 基本算法基本算法4.1 排序排序 2.衡量排序方法的标准衡量排序方法的标准•排序时所需要的平均比较次数排序时所需要的平均比较次数•排序时所需要的平均移动排序时所需要的平均移动•排序时所需要的平均辅助存储空间排序时所需要的平均辅助存储空间4 基本算法基本算法4.1 排序排序 3.插入排序插入排序 插入排序插入排序插入排序插入排序 (Insert Sorting)(Insert Sorting)的基本方法是：每步将一个的基本方法是：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止一组对象的适当位置上，直到对象全部插入为止•直接插入排序：直接插入排序：当插入第当插入第i (i   1) 个对象时，前面的个对象时，前面的V[0], V[1], …, v[i-1]已经排好序。

这时，用已经排好序这时，用v[i]的关键字与的关键字与v[i-1], v[i-2], …的关键字顺序进行的关键字顺序进行比较，找到插入位置即将比较，找到插入位置即将v[i]插入，原来位置上之后的所有对象依次向后插入，原来位置上之后的所有对象依次向后顺移•折半插入排序：折半插入排序：设在顺序表中有一设在顺序表中有一 个对象序列个对象序列 V[0], V[1], …, v[n- -1]其中，中，v[0], V[1], …, v[i- -1] 是已经排好序的对象在插入是已经排好序的对象在插入 v[i] 时，利用折半时，利用折半搜索法寻找搜索法寻找 v[i] 的插入位置的插入位置4 基本算法基本算法直直接接插插入入排排序序21212525494925*25*161608080 1 2 3 4 50 1 2 3 4 5 temp212125494925*25*161608082525i = 10 1 2 3 4 5 temp212125254925*25*161608084949i = 24 基本算法基本算法21212525494925*161608080 1 2 3 4 50 1 2 3 4 5 temp21212525494925*25*160808i = 40 1 2 3 4 5 temp21212525494925*25*161608i = 5i = 325*25*1616080821212525494925*25*161608080 1 2 3 4 5完成4 基本算法基本算法直直接接插插入入排排序序4.1 排序排序 4.选择排序选择排序 选择排序选择排序(Selection Sort)的基本方法是：的基本方法是：每一趟每一趟 (例如例如第第 i 趟，趟，i = 1, …, n-1) 在后面的在后面的 n-i+1 个待排序对象中选出关个待排序对象中选出关键字最小的对象键字最小的对象, 作为有序对象序列的第作为有序对象序列的第 i 个对象。

待到第个对象待到第 n-1 趟作完，待排序对象只剩下趟作完，待排序对象只剩下1个，就不用再选了个，就不用再选了•简单选简单选择排序择排序 (Simple Selection Sort) ：：i从从1开始，直到开始，直到n-1，进行，进行n-1趟趟排序，第排序，第i 趟的排序过程为：趟的排序过程为： 在一组对象在一组对象r[i]～～r[n] (i=1,2,…,n-1)中选择中选择具有最小关键字的对象；并和第具有最小关键字的对象；并和第 i 个对象进行交换个对象进行交换•与直接插入排序相比，选择排序由于是有选择地选取记录，在插入有序序与直接插入排序相比，选择排序由于是有选择地选取记录，在插入有序序列时，需要进行的记录移动操作较少，但其总的时间复杂度也是列时，需要进行的记录移动操作较少，但其总的时间复杂度也是O(n2) 4 基本算法基本算法4.1 排序排序 5.气泡排序气泡排序 气泡排序气泡排序 (Bubble Sort)的基本方法是：的基本方法是：设待排序对象序设待排序对象序列中的对象个数为列中的对象个数为 n最多作 n- -1 趟趟排序在第排序。

在第 i 趟中顺次两趟中顺次两两两比较比较r[j-1].Key和和r[j].Key，，j = i, i+1, , n-i-1如果发生逆序，如果发生逆序，则交换则交换r[j-1]和和r[j]4 基本算法基本算法气泡排序典型算法：气泡排序典型算法：• void BubbleSort(SqList &L) { int i, j, tag; j = L.length-1; do{ tag=1; for(i=1; i<=j; i++) if( L.r[i+1].key< L.r[i].key ) { L.r[0]= L.r[i+1]; L.r[i+1]= L.r[i]; L.r[i]= L.r[0]; tag=0; } if( !tag ) j--; } while( !tag &&j ); return;} 4 基本算法基本算法4.1 排序排序 6.快速排序快速排序 快速排序快速排序 (Quick Sort)的基本方法是：的基本方法是：任取待排序对象序列中任取待排序对象序列中的某个对象的某个对象 (例如取第一个对象例如取第一个对象) 作为作为枢轴枢轴(pivot)，按照该对象，按照该对象的关键字大小，将整个对象序列划分为的关键字大小，将整个对象序列划分为左右两个子序列左右两个子序列：： 左侧子序列中所有对象的关键字都小于或等于枢轴对象的关键左侧子序列中所有对象的关键字都小于或等于枢轴对象的关键字字 右侧子序列中所有对象的关键字都大于枢轴对象的关键字右侧子序列中所有对象的关键字都大于枢轴对象的关键字•枢轴对象枢轴对象则排在这两个子序列中间则排在这两个子序列中间(这也是该对象最终应安放的位这也是该对象最终应安放的位置置)。

•然后分别对这两个子序列重复施行上述方法，直到所有的对象都然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止排在相应位置上为止4 基本算法基本算法4.1 排序排序 6.快速排序快速排序 算法描述：算法描述：4 基本算法基本算法QuickSort ( List ) { if ( List的长度大于的长度大于1) {将序列将序列List划分为两个子序列划分为两个子序列 LeftList 和和 Right List; QuickSort ( LeftList );QuickSort ( RightList ); 将两个子序列将两个子序列 LeftList 和和 RightList 合并为一个序列合并为一个序列List; }}注意：注意：快速排序是一种不稳定的排序方法对于快速排序是一种不稳定的排序方法对于 n 较大的平均情况而言，快速较大的平均情况而言，快速排序是排序是“快速快速”的，但是当的，但是当 n 很小时，这种排序方法往往比其它简单排序方法很小时，这种排序方法往往比其它简单排序方法还要慢。

还要慢4.2 查找查找 1.1.查找的定义与相关概念查找的定义与相关概念 •查找的定义查找的定义 查找：查找： 根据给定的某个值，在查找表中确定一个关键字等于根据给定的某个值，在查找表中确定一个关键字等于给定值的数据元素若找到表示查找成功，返回该元素给定值的数据元素若找到表示查找成功，返回该元素详细信息或在查找表中的位置；负责返回详细信息或在查找表中的位置；负责返回NULLNULL 4 基本算法基本算法4.2 查找查找 1.1.查找的定义与相关概念查找的定义与相关概念 •查找的相关概念查找的相关概念•查找表：查找表： 由同一类元素或记录构成的集合对数据元素间的关系未作限定由同一类元素或记录构成的集合对数据元素间的关系未作限定•对查找表的操作有：对查找表的操作有： 查找某个查找某个““特定特定””的元素是否在表中的元素是否在表中 查找某个查找某个““特点特点””的元素的各种属性的元素的各种属性 在查找表中插入一个元素在查找表中插入一个元素 在查找表中删除一个元素在查找表中删除一个元素•静态查找表、动态查找表静态查找表、动态查找表•关键字关键字 数据元素中的某个数据项值。

可以表示一个数据元素，如可以唯一数据元素中的某个数据项值可以表示一个数据元素，如可以唯一表示，则为主关键字（表示，则为主关键字（primary keyprimary key）4 基本算法基本算法4.2 查找查找 1.1.查找的定义与相关概念查找的定义与相关概念 •查找的相关概念查找的相关概念•查找的结果通常有两种可能：查找的结果通常有两种可能：查找成功查找成功，即找到满足条件的数据对象即找到满足条件的数据对象查找不成功查找不成功，或查找失败作为结果，报告一些信息，如，或查找失败作为结果，报告一些信息，如 失败标志、失败位置等失败标志、失败位置等 4 基本算法基本算法4.2 查找查找2.2. 查找算法的效率衡量查找算法的效率衡量•衡衡量量一一个个查查找找算算法法的的时时间间效效率率的的标标准准是是：：在在查查找找过过程程中中关关键键字字的的平平均均比比较较次次数数或或平平均均读读写写磁磁盘盘次次数数(只只适适合合于于外外部部查查找找)，，这这个个标标准准也也称称为为平平均均查查找找长长度度ASL(Average Search Length)，，通通常常它它是是查查找结构中对象总数找结构中对象总数 n 或文件结构中物理块总数或文件结构中物理块总数 n 的函数的函数。

•另另外外衡衡量量一一个个查查找找算算法法还还要要考考虑虑算算法法所所需需要要的的存存储储量量和和算算法法的的复复杂性等问题杂性等问题•在在静静态态查查找找表表中中，，数数据据对对象象存存放放于于数数组组中中，，利利用用数数组组元元素素的的下下标标作作为为数数据据对对象象的的存存放放地地址址查查找找算算法法根根据据给给定定值值x，，在在数数组组中中进进行行查查找找直直到到找找到到x在在数数组组中中的的存存放放位位置置或或可可确确定定在在数数组组中中找找不不到到x为止4 基本算法基本算法4.2 查找查找3.3.顺序查找顺序查找 • •所谓所谓顺序查找顺序查找，又称，又称线性查找线性查找，主要用于在，主要用于性结构线性结构中进中进 行查找• •存储结构：存储结构： typedeftypedef structstruct{ { ElemTypeElemType * *elemelem; // ; // 元素数据结构元素数据结构 intint length; // length; // 查找表长度查找表长度 } } SSTableSSTable; ;• •查查找找过过程程：：从从表表中中最最后后一一个个元元素素开开始始，，顺顺序序用用各各元元素素的的关关键键字字与与给给定定值值x x进进行行比比较较，，若若找找到到与与其其值值相相等等的的元元素素，，则则查查找找成成功功，，给给出出该该元元素素在在表表中中的的位位置置；；否否则则，，若若直直到到第第一一个个记录仍未找到关键字与记录仍未找到关键字与x x相等的对象，则查找失败。

相等的对象，则查找失败 4 基本算法基本算法4.2 查找查找 3.3.顺序查找顺序查找 算法描述：算法描述： Search_Seq(SSTable ST, KeyType key){ //顺序查找的算法，顺序查找的算法，0号元素为监视哨号元素为监视哨 int i；； ST.elem[0].key=key; for (i=ST.length; !EQ(ST.elem[i].key,key);--i); return i; } } 4 基本算法基本算法4 基本算法基本算法4.2 查找查找3.3.顺序查找顺序查找 顺序查找的平均查找长度：顺序查找的平均查找长度： 设查找设查找第第 i i 个个元素的概率为元素的概率为 pipi，查找到，查找到第第 i i 个个元元素所需素所需比较次数比较次数为为 cici，则查找成功的平均查找长度，则查找成功的平均查找长度: : 在顺序查找情形，在顺序查找情形，ci = n-i +1, i = 1, , n，，因此因此4.2 查找查找4.4.折半查找折半查找•折折半半查查找找：：先先求求位位于于查查找找区区间间正正中中的的对对象象的的下下标标mid，，用用其其关关键键字字与给定值与给定值x比较比较: Element[mid].getKey( ) = x，，查找成功；查找成功； Element[mid].getKey( ) > x，，把把查查找找区区间间缩缩小小到到表表的的前前半半部部分分，，再继续进行对分查找；再继续进行对分查找； Element[mid].getKey( ) < x，，把把查查找找区区间间缩缩小小到到表表的的后后半半部部分分，，再继续进行对分查找。

再继续进行对分查找•每每比比较较一一次次，，查查找找区区间间缩缩小小一一半半如如果果查查找找区区间间已已缩缩小小到到一一个个对对象，仍未找到想要查找的对象，则查找失败象，仍未找到想要查找的对象，则查找失败4 基本算法基本算法折半查找算法过程：折半查找算法过程：（（1））mid= (low+high)/2」」 （（2））比较比较 ST.elem[mid].key = = key? 如果如果 ST.elem[mid].key = = key，则，则查找成功，查找成功， 返回返回mid值值 如果如果 ST.elem[mid].key > key，，则置则置high=mid-1 如果如果 ST.elem[mid].key < key，，则置则置low=mid+1 （（3））重重复复计计算算mid 以以及及比比较较ST.elem[mid].key与与 key，，当当low>high 时，表明查找不成功，查找结束时，表明查找不成功，查找结束4 基本算法基本算法 查找成功的例子查找成功的例子 查找失败的例子查找失败的例子4 基本算法基本算法第五节第五节 递归递归5.1 递归递归 1.1.递归的定义递归的定义•递归递归：：递归是指算法在过程中调用自身作为子算法的一种设递归是指算法在过程中调用自身作为子算法的一种设计方法。

计方法•递归是设计和描述算法的一种有力的工具，它在复杂算法的递归是设计和描述算法的一种有力的工具，它在复杂算法的描述中被经常采用能采用递归描述的算法通常具有如下特描述中被经常采用能采用递归描述的算法通常具有如下特征：征： 为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解 5 递归递归5.1 递归递归 2.2.递归解决的问题递归解决的问题•递归算法一般用于解决三类问题：递归算法一般用于解决三类问题： (1) (1) 数据的定义是按递归定义的数据的定义是按递归定义的 (例如例如FibonacciFibonacci函数函数) ) (2) (2) 问题解法按递归算法实现问题解法按递归算法实现 (例如回溯例如回溯) ) (3) (3) 数据的结构形式是按递归定义的数据的结构形式是按递归定义的 (例如树的遍历，例如树的遍历，图的搜索等图的搜索等) )5 递归递归5.1 递归递归 3 3. .递归算法的优点和缺陷递归算法的优点和缺陷•递归算法的优势：递归算法的优势： (1) 对于按递归定义的数据集合处理效率很高。

对于按递归定义的数据集合处理效率很高 (2) 易于将复杂的问题简单化，便于理解易于将复杂的问题简单化，便于理解 (3) 对于特殊的数据结构，例如二叉树、图等具有良好的处理能力对于特殊的数据结构，例如二叉树、图等具有良好的处理能力•递归算法的缺陷：递归算法的缺陷： 递递归归引引起起一一系系列列的的函函数数调调用用，，并并且且可可能能会会有有一一系系列列的的重重复复计计算算，，递递归归算算法法的的执执行行效效率率相相对对较较低低在在递递归归调调用用的的过过程程当当中中系系统统为为每每一一层层的的返返回回点、局部量等开辟了栈来存储递归次数过多容易造成栈溢出等点、局部量等开辟了栈来存储递归次数过多容易造成栈溢出等5 递归递归•数据是计算机化的信息，是计算机可以直接处理的最基本的对象计数据是计算机化的信息，是计算机可以直接处理的最基本的对象计算机中的各种应用，都是对数据进行加工处理的过程要使程序高效算机中的各种应用，都是对数据进行加工处理的过程要使程序高效率地运行，必须根据数据的特性及数据间的相互关系设计出高质量的率地运行，必须根据数据的特性及数据间的相互关系设计出高质量的数据结构；数据结构；•数据结构通常有：集合结构、线性结构和非线性结构（树和图）。

数据结构通常有：集合结构、线性结构和非线性结构（树和图）•结构中定义的结构中定义的“关系关系”描述的是数据元素之间的逻辑关系，因此称为描述的是数据元素之间的逻辑关系，因此称为数据的逻辑结构数据结构在计算机中的表示（又称映像）称为数据数据的逻辑结构数据结构在计算机中的表示（又称映像）称为数据的物理结构，或称存储结构的物理结构，或称存储结构•数据结构主要研究数据的各种逻辑结构和存储结构，以及对数据的各数据结构主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作因此，主要有三个方面的内容：数据的逻辑结构；数据的物种操作因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）通常，算法的设计取决于数理存储结构；对数据的操作（或算法）通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构据的逻辑结构，算法的实现取决于数据的物理存储结构•对特定问题求解步骤的一组规格化描述就是算法，也是计算机解题的对特定问题求解步骤的一组规格化描述就是算法，也是计算机解题的过程算法与数据结构是相辅相成的算法必须具备：正确性、可读过程算法与数据结构是相辅相成的算法必须具备：正确性、可读性、稳健性和高效性。

算法的描述通常使用流程图或伪代码性、稳健性和高效性算法的描述通常使用流程图或伪代码•线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，现实中的许多事物的关系都是非线性的的联系，现实中的许多事物的关系都是非线性的本章小结本章小结•线性表是最简单、最基本、也是最常用的一种线性结构，有顺序存储线性表是最简单、最基本、也是最常用的一种线性结构，有顺序存储和链式存储两种存储方法和链式存储两种存储方法•栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同其特点在于运算受到了限制：栈按性表相同其特点在于运算受到了限制：栈按“后进先出后进先出”的规则进的规则进行操作，队按行操作，队按“先进先出先进先出”的规则进行操作的规则进行操作•树、二叉树和图是非线性结构的基本数据表示方法；树、二叉树和图是非线性结构的基本数据表示方法；•排序运算的概念和基本实现算法排序是常用运用之一，其实现算法排序运算的概念和基本实现算法排序是常用运用之一，其实现算法有多种比较简单的有直接插入排序、简单选择排序、气泡排序等几有多种。

比较简单的有直接插入排序、简单选择排序、气泡排序等几种，其中快速排序是性能较好的排序算法；种，其中快速排序是性能较好的排序算法；•查找运算根据查找列表的结构，有顺序查找和折半查找等多种算法查找运算根据查找列表的结构，有顺序查找和折半查找等多种算法顺序查找效率较低，但对查找列表没有要求，适用于列表较小的场合；顺序查找效率较低，但对查找列表没有要求，适用于列表较小的场合；折半查找效率较高，但需要列表是有序表；折半查找效率较高，但需要列表是有序表；•递归是算法中调用自身的一种算法设计技术递归的运行效率低，但递归是算法中调用自身的一种算法设计技术递归的运行效率低，但运用递归方式编写的算法结构简单，便于理解在实际程序实现时，运用递归方式编写的算法结构简单，便于理解在实际程序实现时，应将递归算法用非递归形式实现以提高程序的运行效率应将递归算法用非递归形式实现以提高程序的运行效率本章小结本章小结。