程序设计基础第10章.ppt

1、数据结构的基本数据结构的基本概念和术语概念和术语10.110.2线性结构线性结构10.3树型结构树型结构图型结构图型结构10.410.5检索检索10.6排序排序10.1.1 10.1.1 数据结构概念数据结构概念 数据结构就是来研究程序设计中计算机操作的对象以及它们之间的关系和运算。数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。结点也叫数据元素，它是组成数据的基本单位。在程序中通常把结点作为一个整体进行考虑和处理。一般情况下，一个

2、结点中含有若干个字段（也叫数据项）。字段是构成数据的最小单位。10.1.2 10.1.2 数据结构的逻辑结构与存储结构数据结构的逻辑结构与存储结构 1.1.数据结构的逻辑结构数据结构的逻辑结构 数据元素之间的逻辑关系称为数据的逻辑结构。数据的逻辑结构只是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。按照数据元素之间的逻辑关系，又分为两大类：1 1）线性结构）线性结构 线性结构是数据元素之间存在着“一对一”的线性关系的数据结构，如图所示。线性表、栈、队列、串都是线性结构。10.1.2 10.1.2 数据结构的逻辑结构与存储结构数据结构的逻辑结构与存储结构 2 2）非线性结构）非线性结

3、构 非线性结构是数据元素之间存在着“一对多”或“多对一”的线性关系的数据结构，如图所示。树和图都是非线性结构。10.1.2 10.1.2 数据结构的逻辑结构与存储结构数据结构的逻辑结构与存储结构 2.2.数据结构的存储结构数据结构的存储结构 数据在计算机中的存储表示称为数据的存储结构。数据的存储结构是逻辑结构在计算机存储器中的映像，是依赖于计算机的。既然数据的逻辑结构分成了线性结构和非线性结构两种，相应地，其在存储器中的映像就有两种不同的表示方式：顺序映像和非顺序映像。由此得到两种不同的存储结构：10.1.2 10.1.2 数据结构的逻辑结构与存储结构数据结构的逻辑结构与存储结构 1 1）顺序

4、存储结构）顺序存储结构 顺序存储结构是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。链式存储结构不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。链式存储结构通常借助于程序设计语言中的指针类型来实现。2 2）链式存储结构）链式存储结构10.2.1 10.2.1 线性表线性表 线性表是最基本、最简单、最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑

5、结构简单，便于实现和操作。1.1.定义定义 线性表是一个含有n（n0）个结点的有限序列。当n=0时，称之为空表；当n=1，线性表仅有一个结点，此结点既是开始结点又是终端结点；当n1时，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。10.2.1 10.2.1 线性表线性表 ABDC集合中必存在集合中必存在唯一的一个唯一的一个“最后元素最后元素”除第一个元素除第一个元素之外，均有唯之外，均有唯一的前驱一的前驱集合中必存在集合中必存在唯一的一个唯一的一个“第一元素第一元素”除最后一个元除最后一个

6、元素之外，均有素之外，均有唯一的后继唯一的后继10.2.1 10.2.1 线性表线性表 2.2.线性表的基本操作线性表的基本操作123456GetElem（L,i）：）：取表中元素。取表中元素。InitList（L）：）：初始化表。初始化表。Length（L）：）：求表长。求表长。PriorElem（L,x,pre_x）：）：取元素取元素x x的直接的直接前驱。前驱。NextElem（L,x,next_x）：）：取元素取元素x x的直接后继。的直接后继。LocateElem（L,x）：）：定位。返回元素定位。返回元素x x在在线性表线性表L L中的位置。中的位置。10.2.1 10.2.1 线

7、性表线性表 7 8 9ListInsert（L,i,x）：）：插入元素。插入元素。ListDelete（L,i）：）：删除元素。删除元素。PrintList（L）：）：输出线性表。输出线性表。10.2.1 10.2.1 线性表线性表 3.3.线性表的顺序存储线性表的顺序存储 线性表的顺序存储是指用一组连续的存储单元依次存储线性表中的每个数据元素。用这种存储形式存储的线性表又称为顺序表。在程序设计中，往往用一维数组来做顺序表的存储。10.2.1 10.2.1 线性表线性表 存储地址存储地址内存单元内存单元.da1d+La2d+2La3.d+(i-1)Lai.d+(n-1)Lan.相邻两个数据元素

8、的存储位置计算公式为：LOC(ai+1)=LOC(ai)+L 线性表中任意一个数据元素的存储位置的计算公式为：LOC(ai+1)=LOC(a1)+(i-1)*L10.2.1 10.2.1 线性表线性表 （1）数据元素的存储位置反映了线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；（2）利用上述给出的数学公式，可以快速地计算出任何一个数据元素的存储地址，这在访问线性表中的任一数据元素所花费的时间开销是相同的，适宜于静态查找。这种存取元素的方法称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。10.2.1 10.2.1 线性表线性表 缺点缺点：采用顺序

9、存储方式的线性表需要程序预先定义线性表结构，占用固定的内存空间。如果要进行插入数据元素和删除数据元素的操作时，则需移动大量结点。4.4.线性表的链式存储线性表的链式存储 前面提到过，顺序表的存储空间大小需要在程序设计时预选设置一固定值，这就导致在表中的数据元素个数发生动态变化时会出现表满的情况发生。为了能够避免这种现象，引入了用链式存储方式存储线性表的方法，这样存储形式的线性表称之为链表。链表有单链表、双链表和循环链表之分。10.2.1 10.2.1 线性表线性表 单链表采用一个结点存放一个数据元素，每个结点除了包括存放数据元素值的数据域(data)外，还包括指向下一个元素的存储位置的指针域（

10、next），最后一个结点的指针域为空 NULL(图示中用表示)。单链表的结点结构如下所示：datanext 以线性表(bat，cat，fat，hat，jat，lat，mat)为例，来看一下以单链表形式存储的图示：batcatfatmathead 和顺序表相比，用单链表的存储形式更适合于表中元素频繁变动的线性表。10.2.2 10.2.2 栈栈 栈（Stack）是一种特殊的表，这种表只在表的一端进行插入和删除操作。允许插入和删除数据元素的这一端称为栈顶；而另一固定的一端称为栈底。不含任何元素的栈称为空栈。对栈中元素的操作是按照“后进先出”的原则进行的，即后进栈的元素先处理，所以栈又称为后进先出(

11、Last In First Out)表，简称为LIFO表。10.2.2 10.2.2 栈栈 anan-1a2a1栈顶栈顶栈底栈底进栈进栈出栈出栈10.2.2 10.2.2 栈栈 12345置空栈 initStack(s)：设置一个空栈S。进栈 push(S,x)：将元素x进到栈S中。gettop(S,x)：将栈s的栈顶元素赋给x，栈指针递减。判断栈空stackempty(s)：若栈为空，返回1，否则返回0。pop(s,x)：将栈s的栈顶元素赋给x，栈指针递减。10.2.2 10.2.2 栈栈 栈用顺序表存储，分配一块连续的内存区域存放栈中元素，并用一个变量指向当前的栈顶。假设栈的元素个数最大不

12、超过整数MaxSize,所有的元素都具有同一数据类型 ElemType，则可用下列方式来定义栈类型stack：Typedef struct Elemtype eMAXSIZE;Int top;Stack;10.2.3 10.2.3 队列队列 队列是一种特殊的线性表，对这种线性表，删除操作只在表头(称为队头)进行，插入操作只在表尾(称为队尾)进行。队列的修改是按先进先出的原则进行的，所以队列又称为先进先出(First In First Out)表，简称 FIFO 表。1.1.队列的数学性质队列的数学性质 假设队列为 a1,a2,.,an，那么a1就是队头元素，an为队尾元素。队列中的元素是按 a

13、1,a2,.,an 的顺序进入的，退出队列也只能按照这个次序依次退出。也就是说，只有在a1离开队列之后，a2才 能退出队列，只有在 a1,a2,.,an-1 都离开队列之后，an 才能退出队列。10.2.3 10.2.3 队列队列 入队入队出队出队a1 a2 a3 an-1 an队头队头队尾队尾 队列的示意图队列的示意图10.2.3 10.2.3 队列队列 2.2.队列的基本运算队列的基本运算 1initQueue(q)初始化：初始化：初始化一个新的队列。初始化一个新的队列。2empty(q)队列非空判断：队列非空判断：若队列若队列 q 不空，则返不空，则返回回 TRUE；否则，返回；否则，返

14、回 FALSE。3append(q,x)入队列：入队列：在队列在队列 q 的尾部插入元的尾部插入元素素 x，使元素，使元素 x 成为新的队尾。若队列满，则成为新的队尾。若队列满，则返回返回 FALSE；否则，返回否则，返回 TRUE。10.2.3 10.2.3 队列队列 6length(qlength(q)求队列长度：求队列长度：返回队列的长度。返回队列的长度。5getHead(q)取队头元素：取队头元素：若队列若队列 q 不空，则返不空，则返回队头元素；否则返回空元素回队头元素；否则返回空元素 NULL。4delete(s)出队列：出队列：若队列若队列 q 不空，则返回队头不空，则返回队头元

15、素，并从队头删除该元素，队头指针指向原元素，并从队头删除该元素，队头指针指向原队头的后继元素；否则，返回空元素队头的后继元素；否则，返回空元素 NULL。10.2.3 10.2.3 队列队列 3.3.队列的顺序存储结构队列的顺序存储结构 队列的顺序存储结构可以简称为顺序队列，也就是利用一组地址连续的存储单元依次存放队列中的数据元素。一般情况下，我们使用一维数组来作为队列的顺序存储空间，另外再设立两个指示器：一个为指向队头元素位置的指示器front，另一个为指向队尾的元素位置的指示器rear。C语言中，数组的下标是从0开始的，因此为了算法设计的方便，在此我们约定：初始化队列时，空队列时令fron

16、t=rear=-1，当插入新的数据元素时，尾指示器rear加1，而当队头元素出队列时，队头指示器front加1。另外还约定，在非空队列中，头指示器front总是指向队列中实际队头元素的前面一个位置，而尾指示器rear总是指向队尾元素。10.2.3 10.2.3 队列队列 4.4.队列的链式存储结构队列的链式存储结构 用链表表示的队列简称为链队列，在一个链队列中需设定两个指针(头指针和尾指针)分别指向队列的头和尾。为了操作的方便，和线性链表一样，我们也给链队列添加一个头结点，并设定头指针指向头结点。因此，空队列的判定条件就成为头指针和尾指针都指向头结点。10.2.4 10.2.4 串串 串又称字

17、符串，是一种特殊的线性表，其每个结点仅由一个字符组成。1.1.串的基本概念串的基本概念 串（String）是由0个或多个字符组成的有限序列，一般表示为：S=“a1a2an”。其中：S是串名，双引号括起的字符序列是串值；ai 可以是字母、数字或其它字符；n 为串的长度。10.2.4 10.2.4 串串 2.2.串的基本操作串的基本操作计算机中对串的操作主要包含以下几种：计算机中对串的操作主要包含以下几种：创建串 creat（S）求串长度 length（S）复制串 copy（S1，S2）连接串 concat（S1，S2）求子串 subs（S，i，j）比较串 compare（S1，S2）插入一个子串

18、 insert（S1，i，S2）删除一个子串 delete（S1，i，j）求子串在主串中的位置 index（S1，S2）10.2.4 10.2.4 串串 3.3.串的储存结构串的储存结构 串是一种特殊的线性表，因此串的存储结构表示也有两种方法：静态存储采用顺序存储结构，动态存储采用的是链式存储和堆存储结构。1 1）串的静态存储结构）串的静态存储结构 类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。由于一个字符只占1个字节，而现在大多数计算机的存储器地址是采用的字编址，一个字（即一个存储单元）占多个字节。因此顺序存储结构方式有两种：10.2.4 10.2.4 串串 （1）

19、紧缩格式：即一个紧缩格式：即一个字节存储一个字符。字节存储一个字符。（2 2）非紧缩格式：这种非紧缩格式：这种方式是以一个存储单元方式是以一个存储单元为单位，每个存储单元为单位，每个存储单元仅存放一个字符。仅存放一个字符。2 2）串的动态存储结构）串的动态存储结构 串的动态存储方式采用链式存储结构和堆存储结构两种形式：10.2.4 10.2.4 串串 (2)(2)堆存储结构堆存储结构(1)(1)链式存储结构链式存储结构 串的链式存储结构中每个结点包含字符域和结点链接指针域，字符域用于存放字符，指针域用于存放指向下一个结点的指针，因此，串可用单链表表示。堆存储结构的特点是，仍以一组空间足够大的、

20、地址连续的存储单元存放串值字符序 列，但它们的存储 空间是在程序执行过程中动态分配的。10.3.1 10.3.1 树的基本概念与术语树的基本概念与术语 树（Tree）是 n(n0)个结点的有限集合T，当 n=0时，集合T为空，此时树为空树；当 n0 时，集合T非空，此时树为非空树，它满足如下两个条件：（1）有且仅有一个特定的称为根（Root）的结点；（2）其余的结点可分为 m(m0)个互不相交的子集T1，T2，Tm，其中每个子集本身又是一棵树，并称其为根的子树（Subtree）。树的具体定义树的具体定义：10.3.1 10.3.1 树的基本概念与术语树的基本概念与术语 用来表示树的方法最直观的

21、就是树形表示法用来表示树的方法最直观的就是树形表示法10.3.1 10.3.1 树的基本概念与术语树的基本概念与术语 度（度（Degree）：）：一个结点拥有的子树数称为该结点的度。树的度：树的度：一棵树的度是指该树中结点的最大度数。叶子叶子（Leaf）和分支结点：和分支结点：度为零的结点称为叶子或终端结点。度不为零的结点称为分支结点或非终端结点。除根结点之外的分支结点统称为内部结点，根结点又称为开始结点。双亲双亲（Parents）和孩子和孩子（Child）：树中某个结点的子树之根称为该结点的孩子或儿子，相应地，该结点称为孩子的双亲或父亲。10.3.1 10.3.1 树的基本概念与术语树的基本

22、概念与术语 兄弟兄弟（Sibling）和堂兄弟：和堂兄弟：同一个双亲的孩子称为兄弟。双亲在同一层的结点互为堂兄弟。路径路径（Path）：）：若树中存在一个结点序列k1，k2，kj，使得 kj 是 ki+1 的双亲（1ij），则称该结点序列是从 ki 到 kj 的一条路径或道路。若一个结点序列是路径，则在树的树形图表示中，该结点序列“自上而下”地通过路径上的每条边。祖先（祖先（AncestorAncestor）和子孙（）和子孙（DescendantDescendant）：）：一个结点的祖先是指从树的根到该结点所经分枝上的所有结点（包括根结点）。一个结点的子树的所有结点都称为该结点的子孙。结点的层

23、数（结点的层数（LevelLevel）：）：是从根起算，设根的层数为1，其余结点的层数等于其双亲结点的层数加1。10.3.1 10.3.1 树的基本概念与术语树的基本概念与术语 树的高度树的高度（Height）：树中结点的最大层数称为树的高度或深度（Depth）。有序树有序树（Ordered Tree）和无序树和无序树（Unordered Tree）：若将树中每个结点的各子树看成是从左到右有次序的（即不能互换），则称该树为有序树；否则称为无序树。森林森林（Forest）：是 m(m0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林；反之，给一个森林加上一个结点，使原森林的各棵树

24、成为所加结点的子树，便得到一棵树。10.3.2 10.3.2 二叉树二叉树 二叉树（Binary Tree）是n(n0)个节点的有限集，它或为空树，或由一个根节点和两棵互不相交的左右子树组成。由此可以看出，二叉树的定义也是递归的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：10.3.2 10.3.2 二叉树二叉树l只有右子树只有右子树l只有左子树只有左子树l只有一个根只有一个根结点的二叉树结点的二叉树l完全二叉树完全二叉树l空二叉树空二叉树形态形态10.3.2 10.3.2 二叉树二叉树1 1 完全二叉树只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉

25、树。2 2 满二叉树除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树。10.3.2 10.3.2 二叉树二叉树10.3.2 10.3.2 二叉树二叉树(1)在二叉树中，第i层的结点总数不超过2*i-1（i1）；(2)深度为h的二叉树最多有2h-1个结点(h1)，最少有h个结点；(3)对于任意一棵二叉树，如果其叶结点数为n0，而度数为2的结点 总数为n1，则n0=n1+1；(4)具有n个结点的完全二叉树的深度为int（log2n）+1；10.3.2 10.3.2 二叉树二叉树(5)有n个结点的完全二叉树各结点如果用顺序方式存储，则结 点之间有如下关系：若i为结点编号，则如果i1，则

26、其父结点的编号为i/2；如果2*in，则其左儿子（即左子树的根结点）的编号为 2*i；若2*in，则无左儿子；如果2*i+1n，则其右儿子的结点编号为2*i+1；若 2*i+1n，则无右儿子。(6)给定n个节点，能构成 h(n)种不同的二叉树。其中，h(n)为卡 特兰数的第n项。h(n)=C(n,2*n)/(n+1)二叉树的存储结构主要有两种形式：二叉树的存储结构主要有两种形式：顺序存储方式顺序存储方式 顺序存储方式比较适合完全二叉树，而一般的二叉树也按这种形式来存储，这将造成存储空间的浪费。链表存储方式链表存储方式 对于二叉树，常用链表的形式存储，二叉链表存储结构中每个结点的链结构为：10.

27、3.2 10.3.2 二叉树二叉树10.3.2 10.3.2 二叉树二叉树10.3.2 10.3.2 二叉树二叉树2）ROOT（BT）ROOT（x）求根函数3）PARENT（BT,x）求双亲函数4 4）LCHILD（BT,x）和和 RCHILD（BT,x）求孩子结求孩子结点函数点函数5）LSIBLING（BT,x）和 RSIBING（BT,x）求兄弟函数6）CRT_BT（x,LBT,RBT）建树操作7）INS_LCHILD（BT,y,x）和INS_RCHILD（BT,x）插入子树操作8）DEL_LCHILD（BT,x）和DEL-RCHILD（BT,x）删除子树操作9）TRAVERSE（BT）遍

28、历操作10）CLEAR（BT）清除结构操作。将二叉树 BT置为空树10.3.2 10.3.2 二叉树二叉树Product（1 1）先序遍历）先序遍历先访问根结点，再按先序遍历左子树，最后按先序遍历右先访问根结点，再按先序遍历左子树，最后按先序遍历右子树。子树。Product（2 2）中序遍历）中序遍历先按中序遍历左子树，再访问根结点，最后按中序遍历右先按中序遍历左子树，再访问根结点，最后按中序遍历右子树。子树。Product（3 3）后序遍历）后序遍历先按后序遍历左子树，再按后序遍历右子树，最后访问根先按后序遍历左子树，再按后序遍历右子树，最后访问根结点。结点。10.3.3 10.3.3 哈夫

29、曼树哈夫曼树1.1.基本术语基本术语1 1）路径和路径长度）路径和路径长度 路径长度：从一个结点到另一个结点所经过的分支数，它等于路径上的结点数减1。2 2）结点的权和带权路径长度结点的权和带权路径长度 在实际应用中，往往将树中的结点赋上一个有着某种意义的数值，该数值即为结点的权。结点的带权路径长度定义为：从根结点到该结点之间的路径长度乘以该结点上的权。3 3）树的带权路径长度树的带权路径长度 树的带权路径长度定义为树中所有叶子结点的带权路径长度之和，通常表示为：10.3.3 10.3.3 哈夫曼树哈夫曼树2.2.哈夫曼树的定义及构造方法哈夫曼树的定义及构造方法 哈夫曼树又称最优二叉树，是一种

30、带权路径长度最短的二叉树。（2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。（1）根据给定的 n 个权值w1,w2,w3,.,wi,.,wn构成n棵二叉树的初始集合F=T1,T2,T3,.,Ti,.,Tn，其中每棵二叉树Ti中只有一个权值为 wi的根结点，它的左右子树均为空。（3）从F中删除这两棵树，并把这棵新的二叉树加入到集合F中。（4）重复（2）和（3）两步，直 到集合F中只有一棵二叉树为止。该树即为一棵最优二叉树，即哈夫曼树。10.4.1 10.4.1 图的基本概念与术语图的基本概念与术语 图G是由结点的有穷集合V和

31、边的有穷集合E组成的，记为G=(V，E)。通常，也将图G的顶点集和边集分别记为 V(G)和 E(G)。图中的结点一般称之为顶点。按照边是有向的还是无向的，图又分为有向图和无向图两种。10.4.2 10.4.2 图的存储结构图的存储结构1.1.图的邻接矩阵表示法图的邻接矩阵表示法 图G的邻接矩阵是表示G中顶点vi和顶点vj之间相邻关系的矩阵。若顶点vi和顶点vj相邻，则矩阵元素ai,j=1，否则为0。假设图G有n个顶点，则其邻接矩阵A是如下定义的n阶方阵：构造出一个图G的邻接矩阵后，就可以借助邻接矩阵很容易判断出两个顶点是否相邻，并计算出各顶点的度。另外由邻接矩阵的定义可以得知，无向图G的邻接矩

32、阵A是对称的。10.4.2 10.4.2 图的存储结构图的存储结构2.2.图的邻接表表示法图的邻接表表示法 邻接表是一种顺序存储与链接存储相结合的存储方法。对于图G中的某一个顶点vi，用一个单链表来记录与其相邻的所有顶点，称之为边表，刚好对应于邻接矩阵的一行，然后用一个顺序表来存储顶点vi（i=1，2，n）的数据以及指向vi的边表的指针。vi的边表中每个结点有两个域：顶点域vex和指针域link，其中vex存放vi的各邻接点的序号，link指向vi的下一个邻接点结点。其结点结构如下：10.4.2 10.4.2 图的存储结构图的存储结构 顺序表中的结点又称为表头结点，由两个域组成：数据域 dat

33、a 和指针域 link，其中 data 存放顶点vi的顶点序号或有关信息，link 指向顶点vi的边表中第一个结点。其结点结构如下：10.4.3 10.4.3 图的遍历图的遍历 给出一个图G和其中任一个结点v0，从v0出发系统地访问G中所有结点，每一个结点被访问一次，这就叫图的遍历。遍历图的结果是按访问顺序将结点排成一个线性序列。通常有两种遍历方法：深度优先搜索和广度优先搜索。它们对无向图和有向图都适用。1.1.深度优先搜索深度优先搜索 深度优先搜索类似于树的前序遍历，是树的前序遍历的推广。2.2.广度优先搜索广度优先搜索 广度优先搜索类似于树的按层次遍历的过程。二叉树的遍历：二叉树的遍历：1

34、0.5.1 10.5.1 检索的基本概念检索的基本概念 检索（或查找）的定义：给定一个关键字K值，在含有若干结点的序列中找到它。检索是对某一同类型元素集合构成的检索表做某种操作，因此它不是数据结构，而是与数据结构相关的运算问题。检索的一般含意有：检索的一般含意有：1111 查询特定的元素是否在检索表中。检索一个元素的各种信息（属性）如果特定的元素不在检索表中则插入此元素到表内。检索到特定的元素后从表中删除此元素。10.5.2 10.5.2 线性表的检索线性表的检索1.1.顺序检索顺序检索（Sequential Search）顺序检索是最简单的一种检索方法。其基本思想是：从表的一端开始顺序扫描线

35、性表，依次将扫描到的结点与给定值K相比较，若当前扫描到的结点与K相等，则查找成功；若扫描结束后，仍未找到等于K的结点，则查找失败。顺序检索方法适用于线性表的顺序结构和链式存储结构。10.5.2 10.5.2 线性表的检索线性表的检索2.2.折半检索折半检索（Binary Search）折半检索又称二分检索，是一种效率较高的检索方法。折半检索要求线性表是有序表，即表中结点按关键字有序，并且采用顺序存储结构。其基本思想是在已排好序的检索表中每次取它的中点关键字值比较，形成两个前后子表，如检索成功则退出，否则根据结果判别下一次检索在哪个子表中进行，重复分割该子表直至找到要检索的元素或子表长度为零。1

36、0.5.3 10.5.3 树表的检索树表的检索1.1.二叉排序树的定义二叉排序树的定义 线性表的两种检索方法比较适合静态检索，不适合要进行插入或删除操作的动态检索，为此，引入了几种特殊的树或二叉树作为表的一种组织形式，统称为树表。二叉排序树（Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：若左子树不空，则左子树上所有结点的值均小于它的根结点的值；1左、右子树也分别为二叉排序树。3 32若右子树不空，则右子树上所有结点的值均大于它的根结点的值；10.5.3 10.5.3 树表的检索树表的检索 由上图我们可以看出按照中序遍历该树所得到的中序序列5，10，13，16，2

37、0，24，33，38，64是递增有序的。由此得出二叉排序树的一个重要性质，那就是按照中序遍历该树所得到的中序序列是一个按递增有序的序列。10.5.3 10.5.3 树表的检索树表的检索2.2.二叉排序树的静态检索二叉排序树的静态检索 对二叉排序树的静态检索过程描述如下：若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归查左子树。若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功。10.5.3 10.5.3 树表的检索树表的检索2.2.二叉排序树的动态检索二叉排序树的动态检索void InsertBST(t，key)/在二叉排序树中插入查找关键字在二叉排序树中

38、插入查找关键字keyif(t=NULL)t=new BiTree;t-lchild=t-rchild=NULL;t-data=key;return;if(keydata)InsertBST(t-lchild,key);else InsertBST(t-rchild,key);void CreateBiTree(tree,d,n）/n个数据在数组个数据在数组d中中，tree为二叉排序树根为二叉排序树根 tree=NULL;for(i=0;idata=x)b=DelNode(b);else if(b-data x)b-lchild=DeleteBST(b-lchild,x);b-rchild=De

39、leteBST(b-rchild,x);return b;10.5.4 10.5.4 Hash（哈希）检索技术（哈希）检索技术 Hash 检索技术又称为散列检索技术，Hash 检索技术的基本思想是通过确定一个与关键字K有关的函数，把每个关键字值映射到一个表中的某个位置，在该位置上可以存储记录或记录的关键字，从而实现在检索时根据记录的关键字值直接访问记录。这个用来把关键字值K映射到表中某个位置的函数称为哈希函数或散列函数，通常用h(K)来表示。相应地，把用来存放记录的表称为哈希表或散列表，把 h(K)的值称为哈希地址或散列地址。哈希表的存储形式一般为数组。10.5.4 10.5.4 Hash（哈

40、希）检索技术（哈希）检索技术1.1.哈希函数哈希函数（1 1）直接定址法）直接定址法 直接定址法是以关键字值本身或关键字值加上某个数值常量c作为哈希地址的方法。即：h(K)=K+c 除留余数法是用关键字K除以某个不大于哈希表长度M的数P所得余数作为哈希地址的方法。即：h(K)=K%P 平方取中法是对关键字值取平方，然后取出结果的中间几位数做哈希地址，来构造哈希表的方法。（2 2）除留余数法除留余数法（3 3）除留余数法除留余数法10.5.4 10.5.4 Hash（哈希）检索技术（哈希）检索技术 数字分析法是先对关键字中的数字位进行分析，然后从中提取分布均匀的若干位或它们的组合作为哈希地址的方

41、法。折叠法是首先将关键字分割成位数相同的几部分（最后一部分的位数可能会少一些），然后取这几部分的叠加和（舍去最高位进位）作为哈希地址的方法。（5 5）折叠法折叠法 随机数法是通过选择一个随机函数，取关键字的随机函数值为它的哈希地址的方法。即：H(K)=random(K)（6 6）随机数法随机数法（4 4）数字分析法数字分析法10.5.4 10.5.4 Hash（哈希）检索技术（哈希）检索技术2.2.解决冲突的办法解决冲突的办法开放定址法开放定址法 是将哈希表中的空单元向解决冲突开放的一种方法。线性探查法线性探查法平方探查法平方探查法随机探查法随机探查法再哈希法再哈希法链地址法链地址法 链地址法

42、是将哈希表中发生冲突的同义词用单链表链接起来的一种解决冲突的方法。10.5.4 10.5.4 Hash（哈希）检索技术（哈希）检索技术3.3.哈希表的查找哈希表的查找 给定关键字 K，从哈希表中查找K的过程为，根据哈希函数求得基位置 h（K），若哈希表中此位置没有记录，则查找不成功；否则将该位置记录的关键字值与 K 比较，若和K相等，则查找成功；否则根据使用的冲突解决方法找下一个位置，直到哈希表中某一个位置为空或者表中记录的关键字值等于给定值 K。10.6.1 10.6.1 排序的基本概念排序的基本概念 排序的具体定义：设有排序的具体定义：设有n n个元素序列个元素序列R1，R2，.，Rn，其

43、相应的关键字其相应的关键字序列序列是是K1，K2，.，Kn，需确定需确定1 1，2，n的一种排列的一种排列p1，p2，pn，使其相应使其相应的关键字满足如下非递减（或非递增）的关键字满足如下非递减（或非递增）关系：关系：Kp1Kp2Kp3，.，Kpn 即序列按即序列按Rp1，Rp2，Rp3，.，Rpn成关键字有序序列，这种操作的过程称为成关键字有序序列，这种操作的过程称为排序。排序。直接插入排序是一种最简单的排序方直接插入排序是一种最简单的排序方法。其基本思想是每次从无序表中取出第法。其基本思想是每次从无序表中取出第一个元素，把它插入到有序表的合适位置，一个元素，把它插入到有序表的合适位置，使

44、有序表仍然有序。第一趟比较前两个数使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中；然后把第二个数按大小插入到有序表中；第二趟把第三个数据与前两个数从后向前第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了依次进行下去，进行了(n-1)趟扫描以后就趟扫描以后就完成了整个排序过程。完成了整个排序过程。10.6.2 10.6.2 直接插入直接插入排序法排序法10.6.2 10.6.2 直接插入直接插入排序法排序法10.6.3 10.6.3 交换交换排序法排序法 交换排序的基本思想是：两两比较待

45、交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录相反时即进行交换，直到没有反序的记录为止。应用交换排序基本思想的主要排序为止。应用交换排序基本思想的主要排序方法有：方法有：冒泡排序和快速排序。冒泡排序和快速排序。10.6.3 10.6.3 交换交换排序法排序法10.6.4 10.6.4 选择选择排序法排序法 选择排序选择排序（selection sort）每次寻找待排序元每次寻找待排序元素中最小的排序码，并与其最终排序位置上的元素中最小的排序码，并与其最终排序位置上的元素一次交换到位，避免冒泡排序算法有

46、元素在交素一次交换到位，避免冒泡排序算法有元素在交换过程中不断变位的问题，比如，首先选择换过程中不断变位的问题，比如，首先选择n n个元个元素的最小排序码，将其与排序数组素的最小排序码，将其与排序数组00位置的元素位置的元素交换，然后是选择剩余交换，然后是选择剩余n-1n-1个元素的最小排序码，个元素的最小排序码，将其与排序数组将其与排序数组11位置上的元素交换，即，第位置上的元素交换，即，第i i次排序过程是选择剩余次排序过程是选择剩余n-in-i个元素的最小排序码，个元素的最小排序码，并与排序数组并与排序数组ii位置的元素交换，它的特点是位置的元素交换，它的特点是n n个元素排序最多只有个元素排序最多只有n-1n-1次交换。次交换。10.6.4 10.6.4 选择选择排序法排序法