基本数据结构修改

基本数据结构修改第1页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算22.1数据结构的基本概念2.1.1两个例子2.1.2什么是数据结构2.1.3数据结构的图形表示2.1.4线性数据结构与非线性数据结构第2页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算3数据结构三个方面的问题：(1)数据的逻辑结构(2)数据的存储结构(3)对各种数据结构进行的运算目的：提高数据处理的效率提高数据处理的速度尽量节省计算机存储空间第3页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算42.1.1两个例子

计算机已广泛应用于数据处理。实际问题中的各数据元素之间总是相互关联的。所谓数据处理，是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，以包括对数据元素进行分析。第4页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算5重要的是知道数据集合中各数据元素之间存在什么关系，为了提高处理效率，应如何组织它们，即如何表示所需要处理的数据元素。第5页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算6例2.1无序表的顺序查找35167885432933215446

有序表的对分查找16212933354346547885数据元素在表中的排列顺序对查找效率是有很大影响第6页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算7无序表的顺序查找从第一个元素开始，逐个将表中的元素与被查数进行比较，直到表中的某个元素与被查数相等（即查找成功）或者表中所有元素都与被查数进行了比较且都不相等（即查找失败）为止。最少次数：被查元素刚好是表中第一个元素时。只需比较一次。最多次数：被查元素刚好是表中最后一个元素时或表中不存在被查元素。在这种情况下顺序查找是很费时间的。第7页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算8有序表中的二分查找将被查数与表中的中间这个元素进行比较：若相等，则表示查找成功，查找过程结束；若被查数大于表中的中间这个元素，则表示如果被查数在表中，只能在表的后半部，此时可以舍弃表中的前半部保留后半部；若被查数小于表中的中间元素，则表示如果被查数在表中，只能在表的前半部此时可以舍弃后半部而保留前半部。然后对剩下部分再按照上述方法进行查找，这个过程一直做到在某次的比较中相等（查找成功）或剩下的部分已空（查找失败）为止。第8页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算9在有序表的对分查找中，不论查找的是什么数，也不论要查找的数在表中有没有，都不需要与表中所有元素进行比较，并且只需要与表中很少的元素进行比较。但需要指出的是，对分查找只适用于有序表，而对于无序表是无法进行对分查找的。第9页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算10结论：在对数据进行处理时，可以根据所做的运算不同，将数据组织成不同的形式，以便于做该种运算，从而提高数据处理的效率。第10页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算112.1.2什么是数据结构

数据结构是指相互有关联的数据元素集合。

现实世界中客观存在的一切个体都可以是数据元素。第11页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算12描述一年四季的季节名

春，夏，秋，冬可以作为季节的数据元素；表示数值的各个数

18，11，35，23，16，…

可以作为数值的数据元素；表示家庭成员的各成员名

父亲，儿子，女儿可以作为家庭成员的数据元素。第12页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算13

前后件关系是数据元素之间的一个基本关系，但前后件关系所表示的实际意义是随具体对象的不同而不同。一般来说，数据元素之间的任何关系都可以用前后件关系来描述。例如：“春”是“夏”的前件，“夏”是“春”的后件。

“父亲”是“儿子”，“女儿”的前件，“儿子”，“女儿”是“父亲”的后续。第13页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算141.数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。第14页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算15数据的逻辑结构有两个要素：数据元素的集合D；反映D中各数据元素之间的前后件关系R。

数据结构可以表示成

B＝（D，R）其中B表示数据结构。第15页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算16为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。设a与b是D中的两个数据，则二元组（a，b）表示a是b的前件，b是a的后件。例如

B＝（D，R）

D＝{春，夏，秋，冬}R＝{(春，夏)，(夏，秋)，(秋，冬)}第16页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算17家庭成员数据结构

B＝（D，R）

D＝{父亲，儿子，女儿}R＝{(父亲，儿子），(父亲，女儿）}n维向量X＝（x1，x2，…，xn）也是一种数据结构。即

X＝（D，R）

D＝{x1，x2，…，xn}R＝{(x1，x2)，(x2，x3)，…，(xn－1，xn)}第17页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算18m×n的矩阵是一个数据结构。即

A＝（D，R）

D＝{A1，A2，…，Am}R＝{(A1，A2)，(A2，A3)，…，(Ai，Ai＋1)，…，(Am－1，Am)}其中Ai=（ai1，ai2，…，ain），i＝1，2，…，m

Ai＝（Di，Ri）

Di＝{ai1，ai2，…，ain}Ri＝{(ai1，ai2)，(ai2，ai3)，…，(aij，ai，j＋1)，…，(ai，n－1，ain)}第18页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算192.数据的存储结构（数据的物理结构）

数据的物理结构在计算机存储空间中的存放形式。常用的存储结构有：顺序、链接、索引等存储结构。采用不同的存储结构，其数据处理的效率是不同的。第19页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算202.1.3数据结构的图形表示数据集合D中的每一个数据元素用中间标有元素值的方框表示（数据结点，结点）用一条有向线段从前件结点指向后件结点。第20页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算21一年四季数据结构的图形表示第21页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算22家庭成员间辈份关系数据结的图形表示第22页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算23DS1=(D1,R1)D1={a,b,c,d,e}R1={(a,b),(b,c),(c,d),(d,e),(e,a),(a,c),(a,d),(b,e),(c,e)}daebcDS1是个无向图第23页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算24DS2=(D2,R2)D2={a,b,c,d,e}R2={〈a,b〉,〈b,c〉,〈c,d〉,〈d,e〉,〈e,a〉,〈a,c〉,〈a,d〉,〈b,e〉,〈c,e〉}daebcDS2是一个有向图第24页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算25DS2=(D2,R2)D2={a1,a2,a3,…,ak}R2={<ai,ai+1>|{}}这说明这个关系R2任何两递增下标的数据元素都有相邻关系，如图所示a1a2a3……ak数组的数据结构第25页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算26

用图形表示数据结构B＝（D，R）D＝{di|1≤i≤7}＝{d1，d2，d3，d4，d5，d6，d7}R＝{(d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5)}第26页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算27数据结构的相关概念在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点（也称为叶子结点）；除了根结点与终端结点外的其他结点一般称为内部结点。数据结构中的相关运算：插入运算、删除运算。这两个运算是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。在一个数据结构中元素结点和数据元素之间的关系都可能是动态变化的。第27页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算282.1.4线性数据结构与非线性数据结构线性表的逻辑结构是n个数据元素的有限序列(a1,a2,a3,……,an)其中n表示了线性表的长度（n>=0）.n=0的表称为空表。线性结构：数据元素呈线性关系。隐含有序。

（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。线性结构又称线性表。第28页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算29特别说明

在一个线性结构中插入或删除任何一个结点后还应该是线性结构。如果一个数据结构满足上述两个条件，但当在此数据结构中插入或删除任何一个结点后就不满足这两个条件了，则该数据结构不能称为线性结构。第29页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算30不是线性结构的数据结构特例

第30页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算31如果一个数据结构不是线性结构，则称之为非线性结构第31页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算322.2线性表及其顺序存储结构2.2.1线性表及其运算2.2.2栈及其应用2.2.3队列及其应用第32页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算332.2.1线性表及其运算1.什么是线性表(LinearList)线性表是最简单最常用的一种数据结构。线性表是由一组数据元素构成。例如：n维向量(x1，x2，…，xn)是一个长度为n的线性表，其中的每一个分量就是一个数据元素。英文小写字母表(a，b，c，…，z)是一个长度为26的线性表一年中的四个季节(春，夏，秋，冬)是一个长度为4的线性表矩阵是一个比较复杂的线性表第33页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算34学生情况登记表是一个复杂的线性表,由若干数据项组成的数据元素称为记录(record)由多个记录构成的线性表又称为文件(file)第34页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算35线性表是由n(n≥0)个数据元素a1，a2，…，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为

(a1，a2，…，ai，…，an)

其中ai(i＝1，2，…，n)是属于数据对象的元素，通常也称其为线性表中的一个结点。线性表的逻辑结构第35页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算36非空线性表结构特征：

(1)有且只有一个根结点a1，它无前件；

(2)有且只有一个终端结点an，它无后件；

(3)除根结点与终端结点外，其它所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n＝0时，称为空表。第36页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算372.线性表的顺序存储结构线性表的顺序存储结构基本特点：(1)线性表中所有元素所占的存储空间是连续的；(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。线性表中第i个元素ai在计算机存储空间中的存储地址为

ADR(ai)＝ADR(a1)＋(i－1)k第37页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算38长度为n的线性表(a1，a2，…，ai，…，an)顺序存储结构第38页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算39整型一维数组存放长度为8的线性表(29,18,56,63,35,24,31,47)第39页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算40建立空线性表的顺序存储空间（即初始化线性表的顺序存储空间）

#include"stdlib.h"voidinitsl(v，m，n)ET*v；intm，*n；

{v＝malloc(m*sizeof(ET))；*n＝0；

return；

}释放线性表的顺序存储空间

free(v)；第40页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算41线性表顺序存储结构下的主要运算：(1)在线性表的指定位置处加入一个新的元素（即线性表的插入）；(2)在线性表中删除指定的元素（即线性表的删除）；(3)在线性表中查找某个（或某些）特定的元素（即线性表的查找）；(4)对线性表中的元素进行整序（即线性表的排序）；(5)按要求将一个线性表分解成多个线性表（即线性表的分解）；(6)按要求将多个线性表合并成一个线性表（即线性表的合并）；(7)复制一个线性表（即线性表的复制）；(8)逆转一个线性表（即线性表的逆转）等。第41页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算423.线性表在顺序存储下的插入运算第42页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算43第43页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算44线性表在顺序存储下的插入算法输入：线性表的存储空间V(1：m)；线性表的长度n（n≤m）；插入的位置i（i表示在第i个元素之前插入）；插入的新元素b。输出：插入后的线性表存储空间V(1：m)及线性表的长度n。

第44页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算45PROCEDUREINSL(V，m，n，i，b)1.IF(n＝m)THEN{OVERFLOW；RETURN}2.IF(i＞n)THENi＝n＋13.IF(i＜1)THENi＝14.FORj＝nTOiBY－1DOV(j＋1)＝V(j)5.V(i)＝b6.n＝n＋17.RETURN第45页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算46

voidinsl(v，m，n，i，b)ETv[]，b；intm，n，i；

{if(n＝＝m){printf("overflow\n")；return；}if(i＞n)i＝n＋1；在最后一个元素

if(i＜1)i＝1；在第一个元素之前

for(j＝n；j＜＝i；j――)v[j]＝v[j－1]；

v[i－1]＝b；

n＝n＋1；

return；

}第46页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算474.线性表在顺序存储下的删除运算第47页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算48第48页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算49线性表在顺序存储下的删除算法输入：线性表的存储空间V(1：m)；线性表的长度n（n≤m）；删除的位置i（表示删除第i个元素）。输出：删除后的线性表存储空间V(1：m)及线性表的长度n。

第49页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算50PROCEDUREDESL(V，m，n，i)1.IF(n＝0)THEN{UNDERFLOW；RETURN}2.IF(i＜1)or(i＞n)THEN{“Notthiselementinthelist”；RETURN}3.FORj＝iTOn－1DOV(j)＝V(j＋1)4.n＝n－15.RETURN第50页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算51

voiddesl(v，m，n，i)ETv[]；intm，n，i；

{if(n＝＝0){printf("underflow\n")；return；}if((i＜1)||(i＞n)){printf("Notthiselementinthelist\n")；

return；

}for(j＝i；j＜＝n－1；j＋＋)v[j－1]＝v[j]；

n＝n－1；

return；

}第51页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算521.什么是栈栈（stack）是一种特殊的线性表。对它的操作只能是“后进先出”（LIFO），也是使用最为广泛的数据结构之一。因为它的运算次序受到严格的规定，故又称为限定性数据结构。为了认识栈这种数据结构，首先介绍一个例子。2.2.2栈及其应用第52页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算53主程序与子程序之间的调用关系MAINSUB1SUB2SUB3SUB4

……

……

……

……

……CALLSUB1CALLSUB2CALLSUB3CALLSUB4……A：……B：……C：……D：……

……

……

……

……

……

……ENDRETURNRETURNRETURNRETURN第53页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算54由这个例子可以看出，在这种特殊的线性表中，其插入与删除运算都只能在线性表的一段进行。即在这种线性表的结构中，一端是封闭的，不允许插入和删除元素；另一端是开口的，允许插入与删除元素。在顺序存储结构下，对这种类型线性表的插入与删除运算是不需要移动表中其它数据元素的。这种线性表称为栈。第54页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算55栈(stack)是限定在一端进行插入与删除的线性表。栈顶:允许插入与删除的一端.栈底:不允许插入与删除的另一端。栈是按照“先进后出”

(FILO—FirstInLastOut)或“后进先出”

(LIFO—LastInFirstOut)的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。栈具有记忆作用。用指针top来指示栈顶的位置，用指针bottom指向栈底。往栈中插入一个元素称为入栈运算，从栈中删除一个元素(即删除栈顶元素)称为退栈运算。关于栈的几个基本概念第55页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算56第56页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算572.栈的顺序存储及其运算第57页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算58top＝0表示栈空；top＝m表示栈满。建立空栈的顺序存储空间（即初始化栈的顺序存储空间）

#include"stdlib.h"voidinit_stack(s，m，top)ETs；intm，*top；

{s＝malloc(m*sizeof(ET))；*top＝0；

return；

}释放栈的顺序存储空间时free(s)；第58页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算59(1)入栈运算

PROCEDUREPUSH(S，m，top，x)1.IF(top＝m)THEN{Stack－OVERFLOW；RETURN}2.top＝top＋13.S(top)＝x4.RETURN

voidpush(s，m，top，x)ETs[]，x；intm，*top；

{if(*top＝＝m){printf("Stack－overflow\n")；return；}*top＝*top＋1；s[*top]＝x；

return；

}第59页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算60(2)退栈运算PROCEDUREPOP(S，m，top，y)1.IF(top＝0)THEN{Stack－UNDERFLOW；RETURN}2.y＝S(top)3.top＝top－14.RETURNvoidpop(s，m，top，y)ETs[]，y；intm，*top；{if(*top＝＝0){printf("Stack－underflow\n")；return；}y＝s[*top]；*top＝*top－1；

return；}第60页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算61PROCEDURETOP(S，m，top，y)1.IF(top＝0)THEN{“Stackempty”；RETURN}2.y＝S(top)3.RETURN(3)读栈顶元素voidtop(s，m，top，y)ETs[]，y；intm，*top；{if(*top＝＝0){printf("Stackempty\n")；return；}y＝s[*top]；

return；}第61页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算623.表达式的计算运算符栈，用于在表达式处理过程中存放运算符。在开始时，运算符栈中先压入一个表达式结束符“；”。操作数栈，用于在表达式处理过程中存放操作数。第62页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算63从左到右依次读出表达式中的各个符号：若是操作数，则压入操作数栈，依次读下一个符号。若是运算符，则作进一步判断：第63页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算64①若读出运算符的优先级大于运算符栈栈顶运算符的优先级，则将读出的运算符压入运算符栈，并依次读下一个符号。②若读出的是表达式结束符“；”，且运算符栈栈顶的运算符也是表达式结束符“；”，则表达式处理结束，最后的计算结果在操作数栈的栈顶位置。③若读出运算符的优先级不大于运算符栈栈顶运算符的优先级，则从操作数栈连续退出两个操作数，并从运算符栈退出一个运算符，然后作相应的运算（运算符为刚从运算符栈退出的运算符，运算对象为刚从操作数栈退出的两个操作数），并将运算结果压入操作数栈。第64页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算65A＋B*C－D/E；第65页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算66A＋B*C－D/E；第66页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算67A＋B*C－D/E；第67页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算68A＋B*C－D/E；第68页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算694.递归依次打印输出自然数1到n的非递归算法PROCEDUREWRT(n)FORk＝1TOnDOOUTPUTkRETURN依次打印输出自然数1到n的递归算法PROCEDUREWRT(n)IF(n≠0)THEN{WRT(n)；OUTPUTn}RETURN第69页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算70

#include"stdio.h"wrt(intn){if(n!＝0){wrt(n－1)；printf("%d\n"，n)；}return；

}第70页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算712.2.3队列及其应用1.什么是队列队列(equeue)是指允许在一端进行插入、而在另一端进行删除的线性表。数据结构中的队列与生活中的“排队”极为相似，也是按“先来先解决”的原则行事的，并且既不允许“加塞”，也不允许“中途离队”。第71页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算72关于队列的几个基本概念允许插入的一端称为队尾，用尾指针(rear)指向队尾元素。允许删除的一端称为排头(也称队头)，用排头指针(front)指向排头元素的前一个位置。队列又称为“先进先出”

(FIFO—FirstInFirst

Out)或“后进后出”

(LILO—LastInLastOut)的线性表，体现了“先来先服务”的原则。往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。第72页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算73第73页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算742.循环队列及其运算第74页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算75第75页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算76队列空的条件为s＝0队列满的条件为(s＝1)且front＝rear第76页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算77建立循环队列顺序存储空间（即初始化循环队列顺序存储空间）#include"stdlib.h"voidinit_queue(q，m，front，rear，s)ET*q；intm，*front，*rear，s；{q＝malloc(m*sizeof(ET))；*front＝m；*rear＝m；s＝0；

return；}释放循环队列的顺序存储空间free(q)；第77页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算78入队voidaddcq(q，m，rear，front，s，x)ETq[]，x；intm，*rear，*front，s；{if((s＝＝1)&&(rear＝＝front)){printf("Queue－OVERFLOW\n")；return；}rear＝rear＋1；if(rear＝＝m＋1)rear＝1；q[rear]＝x；s＝1；return；}第78页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算79退队voiddelcq(q，m，rear，front，s，y)ETq[]，y；intm，*rear，*front，s；{if(s＝＝0){printf("Queue－UNDERFLOW\n")；return；}front＝front＋1；if(front＝＝m＋1)front＝1；y＝q[front]；if(front＝＝rear)s＝0；return；}第79页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算803.队列的应用

(1)给工人分配工作的模拟开辟一个队列结构的线性表。设置一个排头指针和一个队尾指针。初始时队列为空。每当有一个工人到调度员处报到时（包括新来的与完成任务后返回的），都将他加入到队尾；当需要一名工人去做某项工作时，就排头的工人去做该项工作。第80页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算81(2)输入输出缓冲区的结构第81页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算822.3线性链表及其运算2.3.1线性链表的基本概念2.3.2线性链表的基本运算2.3.3循环链表第82页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算832.3.1线性链表的基本概念1.线性链表线性表的链式存储结构称为线性链表。第83页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算84第84页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算85第85页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算86第86页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算87第87页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算88依次输出线性链表中的各结点值输入：线性链表的存储空间V(1：m)、NEXT(1：m)；线性链表的头指针HEAD。输出：依次输出线性链表中各结点的值。

PROCEDUREPRTLL(HEAD)j＝HEADWHILE(j≠0)DO{OUTPUTV(j)；j＝NEXT(j)}RETURN第88页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算89

structnode{charname[10]；/*数据域*/charsex；/*数据域*/structnode*next；/*指针域*/}VoidPRTLL(node*head){node*p;p=head;while(p!=null){printf(“name=%c”,p->name);printf(“sex=%c”,p->sex);p=p->next;}}第89页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算90#include"stdlib.h"#include"stdio.h"structnode/*定义结点类型*/{intd；

structnode*next；

}main(){intx；

structnode*head，*p，*q；

head＝NULL；/*置链表空*/q＝NULL；

scanf(“%d”，&x)；/*输入一个正整数*/第90页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算91while(x＞0)/*若输入值大于0*/{p＝(structnode*)malloc(sizeof(structnode))；/*申请一个结点*/p－>d＝x；p－>next＝NULL；/*置当前结点的数据域和指针域*/if(head＝＝NULL)head＝p；/*若链表空，则将头指针指向当前结点p*/elseq－>next＝p；/*将当前结点链接在最后*/q＝p；/*置当前结点为链表最后一个结点*/scanf("%d"，&x)；}}第91页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算92双向链表第92页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算932.带链的栈第93页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算94可利用栈及其运算第94页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算95#include"stdlib.h"structnode/*定义结点类型*/{ETd；/*数据元素类型*/structnode*next；

}；ETx；structnode*top；pushll(top，x){structnode*p；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝x；p－>next＝top；/*置新结点的数据域与指针域*/top＝p；/*改变栈顶指针*/return；}第95页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算96带链栈的退栈运算输入：带链栈的栈顶指针top。输出：退栈后的带链栈栈顶指针top；存放退出结点元素值的变量y。PROCEDUREPOPLL(top，y)y＝V(top)[取出栈顶元素值]p＝toptop=NEXT(p)[改变栈顶指针]DISPOSE(p)[被删除结点送回可利用栈]RETURN第96页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算97#include"stdlib.h"structnode/*定义结点类型*/{ETd；/*数据元素类型*/structnode*next；}；popll(top，y)ETy；structnode*top；{structnode*p；y＝top－>d；/*取出栈顶元素值*/p＝top；top＝p－>next；/*改变栈顶指针*/free(p)；return；/*释放被删除结点后返回*/}第97页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算983.带链的队列第98页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算99带链队列的入队运算输入：带链队列的队尾指针rear；入队的新元素x。输出：元素x入队后的带链队列队尾指针rear。

PROCEDUREADDLL(rear，x)NEW(p)[从可利用栈取得一个新结点p]V(p)＝x[置新结点的数据域]NEXT(p)＝0[置新结点的指针为空]NEXT(rear)＝p[最后一个结点的指针指向新结点]rear＝p[改变队尾指针]RETURN第99页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算100#include"stdlib.h"structnode/*定义结点类型*/{ETd；/*数据元素类型*/structnode*next；

}；addll(rear，x)ETx；structnode*rear；{structnode*p；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝x；p－>next＝NULL；/*置新结点的数据域与指针域*/rear－>next＝p；/*置最后一个结点的指针指向新结点*/rear＝p；/*改变队尾指针*/return；}第100页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算101带链队列的退队运算输入：带链队列的排头指针front。输出：退队后的带链队列排头指针front；存放退出结点值的变量y。

PROCEDUREDELLL(front，y)y=V(front)[取出排头元素值]p＝frontfront＝NEXT(front)[改变排头指针]DISPOSE(p)[释放删除的结点]RETURN第101页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算102#include"stdlib.h"structnode/*定义结点类型*/{ETd；/*数据元素类型*/structnode*next；

}；delll(front，y)ETy；structnode*front；{structnode*p；

y＝front－>d；/*取出排头元素值*/p＝front；

front＝p－>next；/*改变排头指针*/free(p)；/*释放被删除结点*/return；}第102页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算1032.3.2线性链表的基本运算(1)在线性链表中包含指定元素的结点之前插入一个新元素。(2)在线性链表中删除包含指定元素的结点。(3)将两个线性链表按要求合并成一个线性链表。(4)将一个线性链表按要求进行分解。(5)逆转线性链表。(6)复制线性链表。(7)线性链表的排序。(8)线性链表的查找。第103页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算1041.在线性链表中查找指定元素在非空线性链表中寻找包含元素x的前一个结点输入：非空线性链表头指针HEAD；被寻找元素x。输出：非空线性链表中包含元素x的前一个结点。PROCEDURELOOKST(HEAD，x，p)p＝HEADWHILE(NEXT(p)≠0)and(V(NEXT(p))≠x)DOp＝NEXT(p)RETURN第104页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算105structnode/*定义结点类型*/{ETd；/*数据元素类型*/structnode*next；

}；structnode*lookst(head，x)ETx；structnode*head；{structnode*p；

p＝head；

while((p－>next!＝NULL)&&(((p－>next)－>d)!＝x))p＝p－>next；

return(p)；}第105页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算1062.线性链表的插入在链式存储结构下的线性表中插入一个新元素。第106页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算107可利用栈与线性链表第107页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算108(1)从可利用栈取得一个结点，设该结点号为p。并置结点p的数据域为插入的元素值b，即V(p)＝b。(2)在线性链表中寻找包含元素x的前一个结点q。第108页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算109(3)将结点p插入到结点q之后：①使结点p指向包含元素x的结点，即

NEXT(p)＝NEXT(q)②使结点q的指针域内容改为指向结点p，即

NEXT(q)＝p第109页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算110线性链表的插入输入：线性链表的头指针HEAD；插入位置处的前一个结点值x；插入的新元素b。输出：插入后的线性链表。PROCEDUREINSLST(HEAD，x，b)1.NEW(p)2.V(p)＝b3.IF(HEAD＝0)THEN{HEAD＝p；NEXT(p)＝0；RETURN}4.IF(V(HEAD)＝x)THEN{NEXT(p)＝HEAD；HEAD＝p；RETURN}5.LOOKST(HEAD，x，q)6.NEXT(p)＝NEXT(q)；NEXT(q)＝p7.RETURN第110页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算111#include"stdlib.h"structnode/*定义结点类型*/{ETd；structnode*next；}；inslst(head，x，b)ETx，b；structnode*head；{structnode*p，*q；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝b；/*置结点的数据域*/if(head＝＝NULL)/*链表为空*/{head＝p；p－>next＝NULL；return；}if((head－>d)＝＝x)/*在第一个结点前插入*/{p－>next＝head；head＝p；return；}q＝lookst(head，x)；/*寻找包含元素x的前一个结点q*/p－>next＝q－>next；q－>next＝p；/*结点p插到结点q之后*/return；}第111页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算1123.线性链表的删除在链式存储结构下的线性表中删除包含指定元素的结点。第112页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算113可利用栈与线性链表第113页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算114(1)寻找包含元素x的前一个结点q。则包含元素x的结点序号p＝NEXT(q)。(2)将结点q后的结点p删除，即

NEXT(q)＝NEXT(p)。第114页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算115(3)将包含元素x的结点p送回可利用栈。第115页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算116线性链表的删除输入：线性链表的头指针HEAD；需删除的元素x。输出：删除后的线性链表。PROCEDUREDELST(HEAD，x)1.IF(HEAD＝0)THEN{“Thisisaemptylist!”；RETURN}2.IF(V(HEAD)＝x)THEN{p＝NEXT(HEAD)；DISPOSE(HEAD)；HEAD＝p；RETURN}3.LOOKST(HEAD，x，q)4.IF(NEXT(q)＝0)THEN{“Nothisnodeinthelist!”；RETURN}5.p＝NEXT(q)；NEXT(q)＝NEXT(p)6.DISPOSE(p)7.RETURN第116页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算117#include"stdlib.h"structnode/*定义结点类型*/{ETd；structnode*next；}；delst(head，x)ETx；structnode*head；{structnode*p，*q；

if(head＝＝NULL)/*链表为空*/{printf("Thisisaemptylist!\n")；return；}if((head－>d)＝＝x)/*删除第一个结点*/{p＝head－>next；free(head)；head＝p；return；}q＝lookst(head，x)；/*寻找包含元素x的前一个结点q*/if(q－>next＝＝NULL)/*链表中没有包含元素x的结点*/{printf("Nothisnodeinthelist!\n")；return；}p＝q－>next；q－>next＝p－>next；/*删除结点p*/free(p)；/*释放结点p*/return；}第117页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算1182.3.3循环链表与线性链表相比，循环链表具有以下特点：(1)在循环链表中增加了一个表头结点，其数据域为任意或根据需要来设置，指针域指向线性表第一个元素的结点。循环链表的头指针指向表头结点。(2)循环链表中最后一个结点的指针域不空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。第118页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算119(1)在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。(2)空表与非空表的运算统一。第119页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算120在头指针为HEAD的循环链表中寻找包含元素x的前一个结点输入：循环链表的头指针HEAD；被寻找的元素x。输出：循环链表中包含元素x的前一个结点p。PROCEDURELOOKCST(HEAD，x，p)p＝HEADWHILE(NEXT(p)≠HEAD)and(V(NEXT(p))≠x)DOp＝NEXT(p)RETURN第120页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算121#include"stdlib.h"structnode/*定义结点类型*/{ETd；structnode*next；}；structnode*lookcst(head，x)ETx；structnode*head；{structnode*p；

p＝head；

while((p－>next!＝head)&&(((p－>next)－>d)!＝x))p＝p－>next；

return(p)；}第121页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算122在头指针为HEAD的循环链表中包含元素x的结点前插入新元素b输入：循环链表的头指针HEAD；插入位置处的前一个结点值x；插入的新元素b。输出：插入后的循环链表。PROCEDUREINSCST(HEAD，x，b)NEW(p)[从可利用栈取得一个新结点p]V(p)＝b[置新结点p的数据域（插入的元素值b）]LOOKCST(HEAD，x，q)[寻找循环链表中包含元素x的前一个结点q]NEXT(p)＝NEXT(q)；NEXT(q)＝p[将新结点p插入到结点q之后]RETURN第122页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算123#include"stdlib.h"structnode/*定义结点类型*/{ETd；structnode*next；}；inscst(head，x，b)ETx，b；structnode*head；{structnode*p，*q；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝b；/*置结点的数据域*/q＝lookcst(head，x)；/*寻找包含元素x的前一个结点q*/p－>next＝q－>next；q－>next＝p；/*结点p插入到结点q后*/return；}第123页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算124在头指针为HEAD的循环链表中删除包含元素x的结点输入：循环链表的头指针HEAD；需删除的元素x。输出：删除后的循环链表。PROCEDUREDELCST(HEAD，x)LOOKCST(HEAD，x，q)[寻找包含元素x的前一个结点q]IF(NEXT(q)＝HEAD)THEN[循环链表中没有该结点]{“Nothisnodeinthelist!”；RETURN}p＝NEXT(q)；NEXT(q)＝NEXT(p)[删除结点q后的结点]DISPOSE(p)[将被删除的结点p送回可利用栈]RETURN第124页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算125#include"stdlib.h"structnode/*定义结点类型*/{ETd；structnode*next；}；delcst(head，x)ETx；structnode*head；{structnode*p，*q；

q＝lookcst(head，x)；/*寻找包含元素x的前一个结点q*/if(q－>next＝＝head)/*链表中没有包含元素x的结点*/{printf("Nothisnodeinthelist!\n")；return；}p＝q－>next；q－>next＝p－>next；/*删除结点p*/free(p)；/*释放结点p*/return；}第125页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算1262.4树与二叉树2.4.1树的基本概念2.4.2二叉树及其基本性质2.4.3二叉树的存储结构2.4.4二叉树的遍历第126页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算1272.4.1树的基本概念第127页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算128用图形表示树这种数据结构时，很像自然界中的树。只不过是一颗倒置的树。因此将这种数据结构用“树”来命名。在树的图形中总是认为在用直线连接起来的两端结点中，上端结点是前件下端结点是后件，所以省略了箭头。第128页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算129在现实世界中，能用树这种数据结构表示的例子很多！第129页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算130第130页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算131第131页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算132树中的几个基本术语父结点：在树中，每一个结点只有一个前件称为父结点。根：在树中，没有前件的结点只有一个，成为树的根结点。简称根。子结点：在树中，每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。度：在树中，一个结点所拥有的后件个数称为该结点的度。树的度：在树中，所有结点中的最大度。第132页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算133树的深度：树的最大层次。子树：在树中，以某结点的一个子结点为根构成的树。第133页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算134树是一种层次结构。一般按以下原则分层：（1）根结点在第1层（2）同一层上所有结点的所有子结点在下一层第134页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算135在计算机中，可以用树表示算术表达式。原则如下：（1）表达式中的每一个运算符在树中对应一个结点，称为运算符结点。（2）运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）。（3）运算对象中的单变量均为叶子结点第135页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算136a*(b＋c/d)＋e*h－g*f(s，t，x＋y)第136页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算137a*(b＋c/d)＋e*h－g*f(s，t，x＋y)第137页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算138树链表中的结点结构第138页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算1391.什么是二叉树（binarytree）

(1)非空二叉树只有一个根结点；

(2)每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。2.4.2二叉树及其基本性质第139页，共162页，2023年，2月20日，星期四第2章基本数据结构及其运算1402.二叉树的基本性质性质1在二叉树的第k层上，最多有2k－1(k≥1)个结点。性质2深度为m的二叉树最多有2m－1个结点。性质3在任意一棵二叉树中，度为0的结点即叶子结点总是比度为2的结点多一个。性质4具有n个结点的二叉树，其深度至少为

[log2n]＋1

其中[log2n]表示取log2n的整数部分。第140页，共162页，20