第5章数据结构

1、2022-3-7大学计算机基础1第5章 数据结构l数据结构的基本概念数据结构的基本概念l线性表及其存储结构线性表及其存储结构l栈及其存储结构栈及其存储结构l队列及其存储结构队列及其存储结构l树和二叉树树和二叉树l查找查找l排序排序2022-3-7大学计算机基础2l数据数据(Data):是对信息的一种符号表示。在计算机科学中是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号是指所有能输入到计算机中并被计算机程序处理的符号的总称。的总称。l数据元素数据元素(Data Element):是数据的基本单位，在计算是数据的基本单位，在计算机程序中通常作为一个整体进行考

2、虑和处理。机程序中通常作为一个整体进行考虑和处理。l 一个数据元素可由若干个数据项组成。数据项是数据一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。的不可分割的最小单位。l数据对象数据对象(Data Object)：是性质相同的数据元素的集合。：是性质相同的数据元素的集合。是数据的一个子集。是数据的一个子集。l数据结构数据结构(Data Structure)：是相互之间具有一种或多：是相互之间具有一种或多种关联的数据元素的集合。种关联的数据元素的集合。5.1 数据结构的基本概念2022-3-7大学计算机基础3 数据结构的研究内容数据结构的研究内容 1） 数据的逻辑结构数据的

3、逻辑结构2） 数据的存储结构数据的存储结构3） 数据结构的运算数据结构的运算2022-3-7大学计算机基础41） 数据的逻辑结构数据的逻辑结构 数据的逻辑结构是用来描述数据元素在数据的逻辑结构是用来描述数据元素在逻辑上的关联关系的。它是数据的组织形式，逻辑上的关联关系的。它是数据的组织形式，与数据在计算机内的存储方式无关。与数据在计算机内的存储方式无关。 常用的数据的逻辑结构有：集合、线性常用的数据的逻辑结构有：集合、线性结构、树状结构、图状结构等。结构、树状结构、图状结构等。例如：有一个包含了例如：有一个包含了4个元素的数据集合个元素的数据集合小小学，初中，高中，大学学，初中，高中，大学。2

4、022-3-7大学计算机基础5 数据元素之间的前后位置关系称为数据元素之间的前后位置关系称为前后件关系，也称为直接前驱和直接后前后件关系，也称为直接前驱和直接后继关系。继关系。 所以，数据的逻辑结构描述了两个所以，数据的逻辑结构描述了两个方面的信息：方面的信息： 描述数据元素的信息；描述数据元素的信息； 描述数据元素之间的前后件关系的信息。描述数据元素之间的前后件关系的信息。2022-3-7大学计算机基础62） 数据的存储结构数据的存储结构 数据的逻辑结构在计算机存储器中数据的逻辑结构在计算机存储器中的存储方式就是数据的存储结构（也称的存储方式就是数据的存储结构（也称数据的物理结构）。数据的物

5、理结构）。 基本的存储结构有：顺序存储结构、基本的存储结构有：顺序存储结构、链式存储结构、索引存储结构、散列存链式存储结构、索引存储结构、散列存储结构。储结构。2022-3-7大学计算机基础73） 数据结构的运算数据结构的运算 数据结构的运算一般包括：插入、数据结构的运算一般包括：插入、删除、查找、分类、合并、分解、复制、删除、查找、分类、合并、分解、复制、修改等。修改等。2022-3-7大学计算机基础82. 数据结构的表示数据结构的表示1） 二元关系表示法二元关系表示法2） 图形表示法图形表示法2022-3-7大学计算机基础91） 二元关系表示法二元关系表示法形式：形式： B=（D,R） 其

6、中，其中， B表示数据结构，表示数据结构，D表示表示数据元素的集合，数据元素的集合，R表示各数据元素表示各数据元素之间前后件关系的集合。之间前后件关系的集合。 2022-3-7大学计算机基础10例例1：求学历程：求学历程 B=（D,R） D= 小学，初中，高中，大学小学，初中，高中，大学 R= （小学，初中），（初中，高中），（高中，（小学，初中），（初中，高中），（高中，大学）大学） 例例2：我国的行政区划分：我国的行政区划分 B=（D,R） D= 中国，省，自治区，直辖市，北京，天津，中国，省，自治区，直辖市，北京，天津，上海，重庆上海，重庆 R= （中国，省），（中国，自治区），（中国，

7、（中国，省），（中国，自治区），（中国，直辖市），（直辖市，北京），直辖市），（直辖市，北京）， （直辖市，天（直辖市，天津），津）， （直辖市，上海），（直辖市，上海）， （直辖市，重庆）（直辖市，重庆） 2022-3-7大学计算机基础112） 图形表示法图形表示法 每一个数据元素均表示为一个矩每一个数据元素均表示为一个矩形框，称为结点；每一个前后件关系形框，称为结点；每一个前后件关系表示为一个带箭头的有向线段，从前表示为一个带箭头的有向线段，从前件结点指向后件结点。件结点指向后件结点。2022-3-7大学计算机基础12例例1：求学历程：求学历程 例例2：我国的行政区划分：我国的行政区划分

8、小学初中高中大学中国直辖市重庆上海天津北京自治区省2022-3-7大学计算机基础133. 线性结构和非线性结构线性结构和非线性结构 如果一个数据结构中没有任何数据元如果一个数据结构中没有任何数据元素，则称该数据结构为空数据结构。对于素，则称该数据结构为空数据结构。对于一个非空的数据结构来说，如果满足以下一个非空的数据结构来说，如果满足以下三个条件：三个条件： 有且只有一个根结点；有且只有一个根结点； 每个结点最多有一个前件结点，也最多有每个结点最多有一个前件结点，也最多有一个后件结点；一个后件结点； 插入或删除任何一个结点后仍然同时满足插入或删除任何一个结点后仍然同时满足前两个条件。前两个条件

9、。则称这样的结构为线性结构，又称线性表，则称这样的结构为线性结构，又称线性表，否则为非线性结构。否则为非线性结构。2022-3-7大学计算机基础14l线性表的基本概念线性表的基本概念l线性表的顺序存储结构线性表的顺序存储结构l线性表的链式存储结构线性表的链式存储结构5.2 线性表及其存储结构2022-3-7大学计算机基础15 线性表的基本概念线性表的基本概念线性表(Linear List) ：由n(n0)个数据元素组成的有序序列。其中数据元素的个数n称为线性表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作： (a1，a2，an) 其中，ai(1in)是线性表中的一个数据元素，也称作

10、结点。例1、26个英文字母组成的字母表 （A，B，C、Z）例2、学生健康情况登记表如下：姓姓 名名学学 号号性性 别别年龄年龄 健康情况健康情况王小林王小林790631 男男 18 健康健康陈陈 红红790632 女女 20 一般一般刘建平刘建平790633 男男 21 健康健康张立立张立立790634 男男 17 神经衰弱神经衰弱 . . .2022-3-7大学计算机基础16 线性表是一种典型的线性结构。这线性表是一种典型的线性结构。这种结构在非空时具有以下特征：种结构在非空时具有以下特征： 有且只有一个根结点有且只有一个根结点a1，有且只有一个终端结点an ； 除根结点和终端结点外，其它中

11、间结点有且只有一个前件结点，也有且只有一个后件结点。2022-3-7大学计算机基础172. 线性表的顺序存储结构线性表的顺序存储结构1） 顺序表基本结构顺序表基本结构 顺序表就是按照线性表各结点的逻辑顺序表就是按照线性表各结点的逻辑次序把各点依次存放到一组连续的存储单次序把各点依次存放到一组连续的存储单元里。因此，在线性表的顺序存储结构中，元里。因此，在线性表的顺序存储结构中，前后相邻的两个数据元素在计算机的存储前后相邻的两个数据元素在计算机的存储空间中也是前后相邻的，且前后位置关系空间中也是前后相邻的，且前后位置关系跟逻辑关系一致。在程序设计语言中，一跟逻辑关系一致。在程序设计语言中，一般用

12、一维数组实现顺序表。般用一维数组实现顺序表。2022-3-7大学计算机基础18 对于顺序表，可以用公式计算对于顺序表，可以用公式计算出任一元素的存储位置。出任一元素的存储位置。 如果第一个数据元素存放位置为LOC(a i)，每个元素需占用 个存储单元，则线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置之间满足下列关系： LOC(a i+1)=LOC(a i)+ 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(i-1)*llla1a2aianLOC(a1)LOC(a1)+ lLOC(ai)=LOC(a1)+(i-1)*lLOC(an)=LOC(a1)+(

13、n-1)*l2022-3-7大学计算机基础192） 顺序表的运算顺序表的运算 顺序表的运算主要有：插入、删除、顺序表的运算主要有：插入、删除、查找、排序、分解、合并和逆转。排序和查找、排序、分解、合并和逆转。排序和查找将在后面介绍，这里介绍一下插入和查找将在后面介绍，这里介绍一下插入和删除运算。删除运算。2022-3-7大学计算机基础20u插入运算插入运算55557468923555573146892312345123456插入31插入前n=5插入后n=6注：平均情况下，顺序表的插入运算需要移动表中一半的元素。2022-3-7大学计算机基础21u删除运算删除运算5555746892355557

14、892312345123456删除46删除前n=5删除后n=4注：平均情况下，顺序表的删除运算需要移动表中一半的元素。2022-3-7大学计算机基础223. 线性表的链式存储结构线性表的链式存储结构1） 线性链表基本结构线性链表基本结构 线性链表是用任意的存储单元存储线线性链表是用任意的存储单元存储线性表的各个数据元素的。与顺序表不同，性表的各个数据元素的。与顺序表不同，这组存储单元可以是连续的存储空间，也这组存储单元可以是连续的存储空间，也可以是不连续的，甚至是零散的。因此，可以是不连续的，甚至是零散的。因此，对于线性链表来说，各数据元素的逻辑顺对于线性链表来说，各数据元素的逻辑顺序与存储顺

15、序未必一致。序与存储顺序未必一致。2022-3-7大学计算机基础23 为了表示存储线性表中数据元素及数为了表示存储线性表中数据元素及数据元素间的前后件关系，线性链表采用结据元素间的前后件关系，线性链表采用结点表示数据元素。每个结点有两个组成部点表示数据元素。每个结点有两个组成部分：数据域和指针域。其中，数据域中存分：数据域和指针域。其中，数据域中存储数据元素的信息，指针域中存储数据元储数据元素的信息，指针域中存储数据元素间的前后件关系的信息，一般用指针指素间的前后件关系的信息，一般用指针指示直接后继元素或直接前驱元素的存储位示直接后继元素或直接前驱元素的存储位置。置。 指向第一个结点的指针称为

16、头指针。指向第一个结点的指针称为头指针。 线性链表分为单链表、循环链表和双线性链表分为单链表、循环链表和双向链表。向链表。2022-3-7大学计算机基础242） 单链表及其运算单链表及其运算 单链表的每个结点有两个域：一个数单链表的每个结点有两个域：一个数据域和一个指针域。指针域中存储的是直据域和一个指针域。指针域中存储的是直接后继元素的存储位置。接后继元素的存储位置。V(i)Next(i)i存储序号 数据域 指针域2022-3-7大学计算机基础25例：线性表（例：线性表（A,B,C,D,E）的单链表存储结构。）的单链表存储结构。ABCDEhead单链表的逻辑结构D66A72C9ENULLB3

17、516head916356672单链表的存储结构2022-3-7大学计算机基础26 单链表的运算主要有：查找、插入和删单链表的运算主要有：查找、插入和删除运算。除运算。u查找运算查找运算 基本方法：从头指针指向的第一个结点基本方法：从头指针指向的第一个结点开始沿着指针链依次向后搜索，逐个检查每开始沿着指针链依次向后搜索，逐个检查每个结点的数据域是否是指定元素，若是则返个结点的数据域是否是指定元素，若是则返回该结点的地址，否则返回回该结点的地址，否则返回NULL。2022-3-7大学计算机基础27u插入运算插入运算 在单链表的第在单链表的第i个元素之后插入一个新元素个元素之后插入一个新元素x的基

18、本方法是：的基本方法是：u 在单链表中查找到要插入的位置；在单链表中查找到要插入的位置；u 生成一个新结点存储新元素生成一个新结点存储新元素x；u 将新结点插入到指定位置，更改相应元素指针域。将新结点插入到指定位置，更改相应元素指针域。a1ai-1aiana1ai-1aianx插入新元素x之前插入新元素x之后2022-3-7大学计算机基础28u删除运算删除运算 要删除单链表中第要删除单链表中第i个元素的基本方法是：个元素的基本方法是：u 在单链表中查找到要删除的元素；在单链表中查找到要删除的元素；u 更改相应元素的指针域，将第更改相应元素的指针域，将第i-1个结点的指针域不再指向个结点的指针域

19、不再指向原来的第原来的第i个结点，改为指向第个结点，改为指向第i+1个结点；个结点；u 将要删除的结点移除。将要删除的结点移除。a1ai-1aian删除元素ai之前ai+1a1ai-1aian删除元素ai之后ai+12022-3-7大学计算机基础293）循环链表）循环链表循环链表是一种首尾相接形似环状的链表。循环链表是一种首尾相接形似环状的链表。 a1 an .head 非空表 空表2022-3-7大学计算机基础304）双向链表）双向链表 双向链表的每个结点是由双向链表的每个结点是由3个域组成的，个域组成的，比单链表增加了一个指向前件结点的指针域。比单链表增加了一个指向前件结点的指针域。AAA

20、head注：循环链表和双向链表的插入运算、删除运算与单链表的这两种运算类似。2022-3-7大学计算机基础31l栈的基本概念栈的基本概念l栈的顺序存储结构栈的顺序存储结构l栈的链式存储结构栈的链式存储结构5.3 栈及其存储结构2022-3-7大学计算机基础321. 栈的基本概念栈的基本概念l 栈是一种特殊的线性表。栈是一种特殊的线性表。l 栈是指一端封闭，只允许在另栈是指一端封闭，只允许在另一端插入或删除元素的线性表。一端插入或删除元素的线性表。l 封闭的一端称为栈底，允许插封闭的一端称为栈底，允许插入或删除元素的一端称为栈顶。入或删除元素的一端称为栈顶。l 向栈中插入元素的过程称为入向栈中插

21、入元素的过程称为入栈运算或进栈运算；从栈中删栈运算或进栈运算；从栈中删除元素的过程称为出栈运算或除元素的过程称为出栈运算或退栈运算。退栈运算。a n a n-1a2a1栈顶top 栈底bottom出栈入栈2022-3-7大学计算机基础33l栈中没有任何元素称为空栈。栈中没有任何元素称为空栈。l对于非空栈，处于栈顶的元素称为栈顶元素，对于非空栈，处于栈顶的元素称为栈顶元素，处于栈底的元素称为栈底元素。处于栈底的元素称为栈底元素。l栈是栈是“先进后出先进后出”（first in last out, FILO）或或“后进先出后进先出”（last in first out, LIFO）表。）表。l栈具

22、有记忆功能。栈具有记忆功能。2022-3-7大学计算机基础342. 栈的顺序存储结构栈的顺序存储结构 栈的顺序存储结构也称为顺序栈，它是一种运算栈的顺序存储结构也称为顺序栈，它是一种运算受限的顺序表。受限的顺序表。 对顺序栈可以有对顺序栈可以有3种运算：种运算：CBAtopbottom54321EDCBAtopbottom54321DCBAtopbottom54321(a) 初始栈 (b) 元素D和E入栈后 (c)元素E出栈后 2022-3-7大学计算机基础35（1）入栈运算）入栈运算向栈中插入元素的过程称为入栈运算。向栈中插入元素的过程称为入栈运算。基本方法是：基本方法是：l将栈顶指针将栈顶

23、指针top向栈顶方向移动一个存储单元；向栈顶方向移动一个存储单元；l将要插入的元素插入到栈顶指针将要插入的元素插入到栈顶指针top指向的存储位指向的存储位置。置。说明：在执行入栈运算前，如果栈本身已经是满栈，说明：在执行入栈运算前，如果栈本身已经是满栈，即栈顶指针已经指向了栈存储空间的最后一个位即栈顶指针已经指向了栈存储空间的最后一个位置时，如果继续插入新元素，就会发生置时，如果继续插入新元素，就会发生“上溢上溢”错误。所以，要求在执行入栈运算前，必须先要错误。所以，要求在执行入栈运算前，必须先要判断栈内是否还有空间可以容纳新的元素插入。判断栈内是否还有空间可以容纳新的元素插入。2022-3-

24、7大学计算机基础36（2）出栈运算）出栈运算出栈运算是指从栈顶删除一个元素并把它的值赋给某出栈运算是指从栈顶删除一个元素并把它的值赋给某个变量。个变量。基本方法是：基本方法是：l将栈顶元素赋值给指定变量；将栈顶元素赋值给指定变量；l将栈顶指针将栈顶指针top向栈底方向移动一个存储单元。向栈底方向移动一个存储单元。说明：出栈时，原栈顶元素不必真正擦除，只需移动说明：出栈时，原栈顶元素不必真正擦除，只需移动栈顶指针即可，原栈顶元素在下次入栈运算之前栈顶指针即可，原栈顶元素在下次入栈运算之前仍然存在。在执行出栈运算前，如果栈是空栈，仍然存在。在执行出栈运算前，如果栈是空栈，即栈顶指针为即栈顶指针为0

25、时，已经没有元素可以删除，如果时，已经没有元素可以删除，如果还要执行出栈运算，则会发生还要执行出栈运算，则会发生“下溢下溢”错误。同错误。同样，也需要在执行出栈运算前，先检查栈顶指针样，也需要在执行出栈运算前，先检查栈顶指针所指的位置。所指的位置。2022-3-7大学计算机基础37（3）读栈顶元素）读栈顶元素读栈顶元素就是将栈顶元素的值赋给某个指定变量。读栈顶元素就是将栈顶元素的值赋给某个指定变量。说明：说明：l它与出栈运算的差异在于不用移动栈顶指针的位它与出栈运算的差异在于不用移动栈顶指针的位置，即不删除栈顶元素。置，即不删除栈顶元素。l当栈顶指针当栈顶指针top为为0时，无法读取栈顶元素。

26、时，无法读取栈顶元素。2022-3-7大学计算机基础383. 栈的链式存储结构栈的链式存储结构 栈的链式存储结构也称为链栈，它可以看作一种运算栈的链式存储结构也称为链栈，它可以看作一种运算受限的线性链表，插入和删除操作只允许在线性链表的一受限的线性链表，插入和删除操作只允许在线性链表的一端进行。端进行。top(a) 链栈的逻辑示意图 (b) 链栈的入栈运算 (c)链栈的出栈运算 DCBADCBAPtopDCBAPtop2022-3-7大学计算机基础39（1）入栈运算）入栈运算链栈的入栈运算就是向链栈中插入一个新的元素。链栈的入栈运算就是向链栈中插入一个新的元素。基本方法是：基本方法是：l先为新

27、元素分配一个结点；先为新元素分配一个结点；l结点的数据域存储新元素的值；结点的数据域存储新元素的值；l结点的指针域指向原栈顶元素；结点的指针域指向原栈顶元素；l改变栈顶指针，使之指向新元素的结点。改变栈顶指针，使之指向新元素的结点。2022-3-7大学计算机基础40（2）出栈运算）出栈运算链栈的出栈运算就是从链栈的栈顶处删除一个元素。链栈的出栈运算就是从链栈的栈顶处删除一个元素。基本方法是：基本方法是：l保存栈顶元素地址；保存栈顶元素地址；l读取栈顶元素，将其赋值给指定变量；读取栈顶元素，将其赋值给指定变量；l改变栈顶指针，使其指向原栈顶元素结点的后继改变栈顶指针，使其指向原栈顶元素结点的后继

28、结点；结点；l释放原栈顶元素空间。释放原栈顶元素空间。2022-3-7大学计算机基础41l队列的基本概念队列的基本概念l队列的顺序存储结构队列的顺序存储结构l队列的链式存储结构队列的链式存储结构5.4 队列及其存储结构2022-3-7大学计算机基础421. 队列的基本概念队列的基本概念l 队列也是一种运算受限的特殊队列也是一种运算受限的特殊线性表。线性表。l 队列只允许在表的一端插入元队列只允许在表的一端插入元素，在另一端删除元素。素，在另一端删除元素。l 允许插入元素的一端称为队尾，允许插入元素的一端称为队尾，允许删除元素的一端称为队头。允许删除元素的一端称为队头。l 向队列的队尾插入元素的

29、过程向队列的队尾插入元素的过程称为入队运算或进队运算；从称为入队运算或进队运算；从队列的队头删除元素的过程称队列的队头删除元素的过程称为出队运算或退队运算。为出队运算或退队运算。a 1 a 2an队头front 队尾rear出队入队2022-3-7大学计算机基础43l队列中没有任何元素时称为空队列。队列中没有任何元素时称为空队列。l对于长度不为对于长度不为0的非空队列，处于队头的元素的非空队列，处于队头的元素称为队头元素，处于队尾的元素称为队尾元素。称为队头元素，处于队尾的元素称为队尾元素。l队列是队列是“先进先出先进先出”（first in first out, FIFO）或或“后进后出后进

30、后出”（last in last out, LILO）表。）表。l队列中的元素的出队顺序与入队顺序完全相同。队列中的元素的出队顺序与入队顺序完全相同。2022-3-7大学计算机基础442. 队列的顺序存储结构队列的顺序存储结构 队列的顺序存储结构也称为顺序队列。队列的顺序存储结构也称为顺序队列。 一般顺序队列的运算有入队运算和出队运算两种。一般顺序队列的运算有入队运算和出队运算两种。CBArearfront54321DCBArearfront54321DCBrearfront54321(a) 初始队列 (b) 元素D入队后 (c)元素A出队后 2022-3-7大学计算机基础45（1）入队运算）

31、入队运算顺序队列的入队运算只涉及尾指针顺序队列的入队运算只涉及尾指针rear的变化。的变化。基本方法是：基本方法是：l将队尾指针将队尾指针rear向队尾方向移动一个存储单元；向队尾方向移动一个存储单元；l将要插入的元素插入队尾指针将要插入的元素插入队尾指针rear指向的存储位指向的存储位置。置。说明：入队运算时，如果队满或尾指针已经指向了队说明：入队运算时，如果队满或尾指针已经指向了队列存储空间的最后一个位置，若继续插入新元素，列存储空间的最后一个位置，若继续插入新元素，就会发生就会发生“上溢上溢”错误。错误。2022-3-7大学计算机基础46（2）出队运算）出队运算出队运算也只涉及头指针出队

32、运算也只涉及头指针front的改变。的改变。基本方法是：基本方法是：l将队头元素赋值给指定变量；将队头元素赋值给指定变量；l将头指针将头指针front向队尾方向移动一个存储单元。向队尾方向移动一个存储单元。说明：在执行出队运算时，如果队列是空队，继续删说明：在执行出队运算时，如果队列是空队，继续删除元素，则会发生除元素，则会发生“下溢下溢”错误。错误。 在实际应用中，由于顺序队列队头删除元素在实际应用中，由于顺序队列队头删除元素所在的空间常被闲置，造成资源的浪费，为解决所在的空间常被闲置，造成资源的浪费，为解决这个问题，一般顺序队列常采用循环队列的形式。这个问题，一般顺序队列常采用循环队列的形

33、式。2022-3-7大学计算机基础47循环队列循环队列l 循环队列就是将队列的首尾相连循环队列就是将队列的首尾相连构成一个逻辑上的环状空间，能构成一个逻辑上的环状空间，能够循环存储队列中的数据元素。够循环存储队列中的数据元素。l 循环队列中，依然是尾指针循环队列中，依然是尾指针rear指向队尾元素，头指针指向队尾元素，头指针front指向指向队头元素的前一个位置。队头元素的前一个位置。l 当循环队列空或满时，都有当循环队列空或满时，都有front= rear。为了区分队列空或。为了区分队列空或满的状态，增加了一个标志量满的状态，增加了一个标志量flag，所以当循环队列为空时，有所以当循环队列为

34、空时，有flag=0且且front= rear同时成立，当同时成立，当循环队列为满时，有循环队列为满时，有flag=1且且front= rear同时成立。同时成立。a 1 a 2an队头front 队尾rear2022-3-7大学计算机基础48（1）入队运算）入队运算循环队列的入队运算也是指在队尾加入一个新元素的过程。循环队列的入队运算也是指在队尾加入一个新元素的过程。基本方法是：基本方法是：l将队尾指针将队尾指针rear向队尾方向移动一个存储单元，有向队尾方向移动一个存储单元，有rear=(rear+1) mod n；l将要插入的元素插入队尾指针将要插入的元素插入队尾指针rear指向的存储位

35、置。指向的存储位置。说明：当说明：当flag=1且且front= rear时，说明循环队列是满队状态，时，说明循环队列是满队状态，如果进行入队运算，就会发生如果进行入队运算，就会发生“上溢上溢”错误。错误。CBArearfront54321DCBAErearfront54321rearfront54321(a) 初始队列 (b) 元素D和E入队后 (c)所有元素出队后 2022-3-7大学计算机基础49（2）出队运算）出队运算循环队列的出队运算也是指将队头元素删除的过程。循环队列的出队运算也是指将队头元素删除的过程。基本方法是：基本方法是：l将队头元素赋值给指定变量；将队头元素赋值给指定变量；

36、l将头指针将头指针front向队尾方向移动一个存储单元，有向队尾方向移动一个存储单元，有front=(front+1) mod n。说明：在执行出队运算时，如果说明：在执行出队运算时，如果flag=0且且front= rear时，说明循环队列是空对状态，如果继续删除元时，说明循环队列是空对状态，如果继续删除元素，就会发生素，就会发生“下溢下溢”错误。错误。2022-3-7大学计算机基础503. 队列的链式存储结构队列的链式存储结构 队列的链式存储结构也称为链队列，它也是一种运算队列的链式存储结构也称为链队列，它也是一种运算受限的线性链表，入队和出队操作必须在线性链表的不同受限的线性链表，入队和

37、出队操作必须在线性链表的不同端进行。端进行。rear(a) 链队列的逻辑示意图 (b) 链队列的入栈运算 (c)链队列的出栈运算 ABCDBCDPArearCDPrearfrontfrontfront2022-3-7大学计算机基础51（1）入队运算）入队运算链队的入队运算就是向链队中插入一个新的元素。链队的入队运算就是向链队中插入一个新的元素。基本方法是：基本方法是：l先为新元素分配一个结点；先为新元素分配一个结点；l结点的数据域存储新元素的值；结点的数据域存储新元素的值；l结点的指针域设置为空；结点的指针域设置为空；l尾结点的指针域指向新元素的结点；尾结点的指针域指向新元素的结点；l改变尾指

38、针，使之指向新元素的结点。改变尾指针，使之指向新元素的结点。2022-3-7大学计算机基础52（2）出队运算）出队运算链队的出队运算就是从链队的队头处删除一个元素。链队的出队运算就是从链队的队头处删除一个元素。基本方法是：基本方法是：l保存队头元素地址；保存队头元素地址；l读取队头元素，将其赋值给指定变量；读取队头元素，将其赋值给指定变量；l改变头结点的指针域，使其指向原队头元素结点改变头结点的指针域，使其指向原队头元素结点的后继结点；的后继结点；l释放原队头元素空间。释放原队头元素空间。2022-3-7大学计算机基础53l树的基本概念树的基本概念l二叉树的定义及性质二叉树的定义及性质l二叉树

39、的存储结构二叉树的存储结构l二叉树的遍历二叉树的遍历5.5 树和二叉树2022-3-7大学计算机基础54 树状结构是一种重要的非线性结构。它的形状类似于树状结构是一种重要的非线性结构。它的形状类似于现实中倒立的树，结点间呈现分支和层次关系，能够方现实中倒立的树，结点间呈现分支和层次关系，能够方便地描述数据之间一对多的联系。便地描述数据之间一对多的联系。 树结构树结构 （除了一个称为根的结点外）每个元素都有（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。且仅有一个直接前趋，有且仅有零个或多个直接后继。J JI IA AC CB BD DH HG GF FE

40、E石油大学石油大学计算系计算系数学专业数学专业数理系数理系外语系外语系物理专业物理专业1. 树的基本概念树的基本概念2022-3-7大学计算机基础55树形结构常用的术语树形结构常用的术语l根结点：最上层的没有前件结点的结点。根结点：最上层的没有前件结点的结点。l叶子结点：没有后件结点的结点。叶子结点：没有后件结点的结点。l内部结点：既有前件结点又有后件结点的结点。内部结点：既有前件结点又有后件结点的结点。l父结点：某一结点的前件结点称为该结点的父结点。父结点：某一结点的前件结点称为该结点的父结点。l子结点：某一结点的后件结点称为该结点的子结点。子结点：某一结点的后件结点称为该结点的子结点。l子

41、树：以某个结点的一个子结点为根的树称为该结点的子子树：以某个结点的一个子结点为根的树称为该结点的子树。树。l结点的度：某个结点连接的子结点的个数称为该结点的度。结点的度：某个结点连接的子结点的个数称为该结点的度。l树的度：一颗树包含的所有结点的度的最大值称为这棵树树的度：一颗树包含的所有结点的度的最大值称为这棵树的度。的度。l树的深度：树的最大层次数称为树的深度。树的深度：树的最大层次数称为树的深度。2022-3-7大学计算机基础562. 二叉树的定义及性质二叉树的定义及性质二叉树是一种重要的树状结构。二叉树是一种重要的树状结构。二叉树是二叉树是n(n 0)个结点的有限集合，具有两个特点：个结

42、点的有限集合，具有两个特点：l如果二叉树非空，则有且只有一个根结点；如果二叉树非空，则有且只有一个根结点；l每个结点最多有两个子结点，分别以这两个子结点作为每个结点最多有两个子结点，分别以这两个子结点作为根结点组成该结点的左子树和右子树。根结点组成该结点的左子树和右子树。二叉树的度最大为二叉树的度最大为2。 A A F F G G E E D D C C B B2022-3-7大学计算机基础57 A A F F G G E E D D C C B B(a) A A G G E E D D B B C C F F(b) (a)、(b)是不同的二叉树， (a)的左子树有四个结点，(b)的左子树有两

43、个结点，2022-3-7大学计算机基础58二叉树的二叉树的5种基本形态：种基本形态：（a） （b） （c） （d） （e）（a）空二叉树；（）空二叉树；（b）仅有根结点的二叉树）仅有根结点的二叉树 （c）右子树为空的二叉树；）右子树为空的二叉树； （d）左、右子数均为非空的二叉树）左、右子数均为非空的二叉树（e）左子树为空的二叉树）左子树为空的二叉树 2022-3-7大学计算机基础59 满二叉树满二叉树 满二叉树是指除了最后一层外，每一层的满二叉树是指除了最后一层外，每一层的结点都有两个子结点的二叉树。也就是说，在结点都有两个子结点的二叉树。也就是说，在满二叉树的任何一层上，结点的数目都达到最

44、满二叉树的任何一层上，结点的数目都达到最大值。大值。 A A G G F F E E D D C C B B A A C C B B深度为3的满二叉树深度为2的满二叉树2022-3-7大学计算机基础60 完全二叉树完全二叉树 完全二叉树是指除了最后一层外，每一层完全二叉树是指除了最后一层外，每一层的结点都有两个子结点，而在最后一层上，右的结点都有两个子结点，而在最后一层上，右边的若干结点缺失的二叉树。边的若干结点缺失的二叉树。 A A E E D D C C B B A A F F E E D D C C B B 完全二叉树是二叉树的特例 满二叉树又是完全二叉树的特例2022-3-7大学计算机

45、基础61二叉树的性质二叉树的性质l性质性质1 二叉树的第二叉树的第k层上最多有层上最多有2k-1(k 1)个结个结点。当二叉树为满二叉树时取得极限值。点。当二叉树为满二叉树时取得极限值。l性质性质2 深度为深度为m的二叉树最多有的二叉树最多有2m-1(m 1) 个个结点。结点。l性质性质3 二叉树中度为二叉树中度为0的结点数的结点数n0和度为和度为2的结的结点数点数n2满足满足n0=n2+1。l性质性质4 具有具有n个结点的二叉树，深度个结点的二叉树，深度h满足满足h log2n+1，当二叉树为完全二叉树时取得，当二叉树为完全二叉树时取得极限值极限值h=log2n+1，其中，其中log2n表示

46、取小于表示取小于等于等于log2n的最大整数。的最大整数。2022-3-7大学计算机基础62二叉树的性质二叉树的性质l性质性质5 具有具有n个结点的完全二叉树，如果从根个结点的完全二叉树，如果从根结点开始，按层序编号，则对任一编号为结点开始，按层序编号，则对任一编号为i(i=1,2,n)的结点，有的结点，有l若若i=1，则该结点为根结点；若，则该结点为根结点；若i1，则该结，则该结点的父结点的编号为点的父结点的编号为INT(i/2)。l若若2i n，则编号为，则编号为i的结点有左子结点，左子的结点有左子结点，左子结点的编号为结点的编号为2i，否则该结点是叶子结点。，否则该结点是叶子结点。l若若

47、2i+1 n，则编号为，则编号为i的结点有右子结点，右的结点有右子结点，右子结点的编号为子结点的编号为2i+1，否则该结点没有右子，否则该结点没有右子结点。结点。2022-3-7大学计算机基础633. 二叉树的存储结构二叉树的存储结构l二叉树通常有两种存储方式：顺序存储结构和二叉树通常有两种存储方式：顺序存储结构和链式存储结构，由于顺序存储结构局限性较大，链式存储结构，由于顺序存储结构局限性较大，而且空间浪费严重，所以一般采用的是链式存而且空间浪费严重，所以一般采用的是链式存储结构，也称二叉链表。储结构，也称二叉链表。l与线性表类似，二叉链表中的每个存储结点也与线性表类似，二叉链表中的每个存储

48、结点也是由数据域和指针域组成。是由数据域和指针域组成。L(i)V(i)R(i)存储序号 左指针域 数据域 右指针域i2022-3-7大学计算机基础64 A A F F E E D D C C B B D D A A B B C C E E F F t(a) 二叉树(b) 二叉链表的逻辑状态2022-3-7大学计算机基础654. 二叉树的遍历二叉树的遍历 二叉树的遍历是指沿某条路径不重复地访二叉树的遍历是指沿某条路径不重复地访问二叉树中的所有结点。这里的访问是指对结问二叉树中的所有结点。这里的访问是指对结点进行某种处理，如读、写、改等。点进行某种处理，如读、写、改等。 二叉树遍历过程中涉及访问根

49、结点、遍历二叉树遍历过程中涉及访问根结点、遍历左子树和遍历右子树左子树和遍历右子树3种操作。根据对结点访种操作。根据对结点访问先后的不同，可以将二叉树的遍历分为前序问先后的不同，可以将二叉树的遍历分为前序遍历、中序遍历和后序遍历遍历、中序遍历和后序遍历3种类型。种类型。2022-3-7大学计算机基础66 前序遍历（前序遍历（DLR） 前序遍历是一个递归过程，若二叉树为空，前序遍历是一个递归过程，若二叉树为空，则结束返回，对于非空的二叉树，其遍历规则结束返回，对于非空的二叉树，其遍历规则如下：则如下：l访问根结点；访问根结点；l前序遍历左子树；前序遍历左子树；l前序遍历右子树。前序遍历右子树。l

50、右图二叉树的前序遍历结果右图二叉树的前序遍历结果为：为：ABMWFIR A A W W I I M M F F B B R R2022-3-7大学计算机基础67 中序遍历（中序遍历（LDR） 中序遍历也是一个递归过程，若二叉树中序遍历也是一个递归过程，若二叉树为空，则结束返回，对于非空的二叉树，其为空，则结束返回，对于非空的二叉树，其遍历规则如下：遍历规则如下：l中序遍历左子树；中序遍历左子树；l访问根结点；访问根结点；l中序遍历右子树。中序遍历右子树。l右图二叉树的中序遍历结果右图二叉树的中序遍历结果l为：为：MBWAIRF A A W W I I M M F F B B R R2022-3

51、-7大学计算机基础68 后序遍历（后序遍历（LRD） 后序遍历也是一个递归过程，若二叉树后序遍历也是一个递归过程，若二叉树为空，则结束返回，对于非空的二叉树，其为空，则结束返回，对于非空的二叉树，其遍历规则如下：遍历规则如下：l后序遍历左子树；后序遍历左子树；l后序遍历右子树；后序遍历右子树；l访问根结点。访问根结点。l右图二叉树的中序遍历结果右图二叉树的中序遍历结果l为：为：MWBRIFA A A W W I I M M F F B B R R2022-3-7大学计算机基础69 查找就是指在某种数据结构中找到某个指查找就是指在某种数据结构中找到某个指定元素的过程。若从数据结构中找到了指定的定

52、元素的过程。若从数据结构中找到了指定的元素，则称查找成功，否则称为查找失败。元素，则称查找成功，否则称为查找失败。 通常，数据结构不同，采用的查找方法也通常，数据结构不同，采用的查找方法也不一样。由于查找的主要操作是元素的比较，不一样。由于查找的主要操作是元素的比较，所以通常把查找过程中元素的比较次数作为衡所以通常把查找过程中元素的比较次数作为衡量一个查找算法效率高低的标准。量一个查找算法效率高低的标准。l顺序查找顺序查找l二分查找二分查找5.6 查找2022-3-7大学计算机基础701. 顺序查找顺序查找l顺序查找是线性表的最简单的查找方法。顺序查找是线性表的最简单的查找方法。l顺序查找的基

53、本方法是：从线性表的一端开始顺序查找的基本方法是：从线性表的一端开始依次扫描每个元素，与指定元素进行比较，如依次扫描每个元素，与指定元素进行比较，如果相等，则查找成功，给出元素在表中的位置，果相等，则查找成功，给出元素在表中的位置，如果全部元素扫描完后，仍然没有找到与指定如果全部元素扫描完后，仍然没有找到与指定元素相等的，则查找失败。元素相等的，则查找失败。l优点：算法简单。缺点：查找效率比较低。优点：算法简单。缺点：查找效率比较低。l顺序查找长度为顺序查找长度为n的线性表，平均情况下要做的线性表，平均情况下要做(n+1)/2次比较次比较 ，最坏情况下要做，最坏情况下要做n次次比较。比较。l有

54、些情况只能采用顺序查找：线性表无序、线有些情况只能采用顺序查找：线性表无序、线性链表。性链表。1112ninin2022-3-7大学计算机基础711. 二分查找二分查找l二分查找又称折半查找，是一种比顺序表效率高的线二分查找又称折半查找，是一种比顺序表效率高的线性查找方法。要求线性表必须是有序的。性查找方法。要求线性表必须是有序的。l二分查找的基本方法是：首先将线性表的中间元素与二分查找的基本方法是：首先将线性表的中间元素与指定元素进行比较，如果相等，则查找成功，如果不指定元素进行比较，如果相等，则查找成功，如果不相等，需要进一步判断被查元素与中间元素的大小，相等，需要进一步判断被查元素与中间

55、元素的大小，如果被查元素大于中间元素，则要在元素值较大的子如果被查元素大于中间元素，则要在元素值较大的子表中继续使用二分法继续查找，如果被查元素小于中表中继续使用二分法继续查找，如果被查元素小于中间元素，则要在元素值较小的子表中继续使用二分法间元素，则要在元素值较小的子表中继续使用二分法继续查找，直到查找成功或查找失败。继续查找，直到查找成功或查找失败。l优点：算法简单。缺点：查找效率比较低。优点：算法简单。缺点：查找效率比较低。l用二分方法查找长度为用二分方法查找长度为n的有序线性表，最坏情况下比的有序线性表，最坏情况下比较次数为较次数为 log2n 次。次。2022-3-7大学计算机基础7

56、2例 L2=( 3,12,24,37,45,53,61,78,90,100 )L2=( 3,12,24,37,45,53,61,78,90,100 )，查找，查找 Key=24Key=24的记录的记录 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 1003 12 24 37 45 53 61 78 90 100lowlowmidmid highhigh 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 3 12 24 373 12 24 37 45 53 61 78 90

57、 100 45 53 61 78 90 100lowlowmidmid highhigh 24 24 45 45 继续在前半个表中用继续在前半个表中用二分查找法二分查找法查找查找 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 3 12 3 12 24 3724 37 45 53 61 78 90 100 45 53 61 78 90 100Low mid highLow mid high 24 24 12 12 继续在后半个表中用继续在后半个表中用二分查找法二分查找法查找查找查找成功2022-3-7大学计算机基础73l交换类排序交换类排序l插入类排序插入类

58、排序l选择类排序选择类排序5.7 排序2022-3-7大学计算机基础741. 交换类排序交换类排序 交换类排序的主要思想是：每次比交换类排序的主要思想是：每次比较待排序列的两个元素，如果这两个元较待排序列的两个元素，如果这两个元素的值的次序与排序要求的次序相反时，素的值的次序与排序要求的次序相反时，则交换两者的位置，直到整个序列全部则交换两者的位置，直到整个序列全部有序为止。有序为止。 常用的交换类排序是：常用的交换类排序是：l冒泡排序快速排序2022-3-7大学计算机基础75冒泡排序冒泡排序l冒泡排序的基本思想是：相邻的两个元素进行冒泡排序的基本思想是：相邻的两个元素进行比较，满足条件（与要

59、排序的顺序相反）就交比较，满足条件（与要排序的顺序相反）就交换。换。l一趟冒泡排序的结果是把最大（或最小）的放一趟冒泡排序的结果是把最大（或最小）的放到了最后，就像重的东西沉到了水底（或轻的到了最后，就像重的东西沉到了水底（或轻的东西浮到了水面）。东西浮到了水面）。l对剩下的元素作相同的操作，直到整个线性表对剩下的元素作相同的操作，直到整个线性表有序。对有序。对n个元素进行排序，冒泡的过程要个元素进行排序，冒泡的过程要n-1趟。趟。l最坏情况下，冒泡排序需要比较最坏情况下，冒泡排序需要比较n(n-1)/2次。次。2022-3-7大学计算机基础76例例 用起泡排序法对以下记录进行排序：用起泡排序

60、法对以下记录进行排序： 49、38、65、97、76、13、27、49分析： 49 38 65 97 76 13 27 49 38 49 65 97 76 13 27 49 38 49 65 97 76 13 27 49 38 49 65 97 76 13 27 49 38 49 65 76 97 13 27 49 38 49 65 76 13 97 27 49 38 49 65 76 13 27 9749 38 49 65 76 13 27 49 97 49 38 65 97 76 13 27 49一趟起泡排序一趟起泡排序初始初始状态状态最大者最大者沉底沉底下一趟下一趟只需排只需排的记录的记