数据结构复习课.ppt

《数据结构复习课.ppt》由会员分享，可在线阅读，更多相关《数据结构复习课.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构复习课数据结构复习课第一章第一章基本概念与算法基础基本概念与算法基础一、学习要求：一、学习要求：理解关于数据结构的名词术语；理解关于数据结构的名词术语；理解算法描述方式；理解算法描述方式；掌握算法时间复杂度和辅助空间的概念；掌握算法时间复杂度和辅助空间的概念；掌握时间复杂度的计算。掌握时间复杂度的计算。二、数据结构概念：二、数据结构概念：1、数据：数据是指能够输入到计算机中，并被计算机识别、数据：数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。和处理的符号的集合。2、数据结构：是存在一种或多种特定关系的数据元素间的、数据结构：是存在一种或多种特定关系的数据元素间的逻辑结构

2、和存储结构关系以及在其上的运算的集合。逻辑结构和存储结构关系以及在其上的运算的集合。3、数据结构的三个方面：数据的逻辑结构，数据的存贮结构和对数据所施、数据结构的三个方面：数据的逻辑结构，数据的存贮结构和对数据所施加的运算。这三个方面的关系为：加的运算。这三个方面的关系为：（1）数据的逻辑结构独立于计算机，是数据本身所固有的。）数据的逻辑结构独立于计算机，是数据本身所固有的。（2）存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。）存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。（3）运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，）运算是指所施加的一组操作总

3、称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。但运算的实现必依赖于存贮结构。4、从逻辑结构划分数据结构从逻辑结构划分数据结构数据结构从逻辑结构划分为：数据结构从逻辑结构划分为：（1）线性结构（线性表、栈、队列、字串，数组）线性结构（线性表、栈、队列、字串，数组）元元素素之之间间为为一一对对一一的的线线性性关关系系，第第一一个个元元素素无无直直接接前前驱驱，最最后后一一个个元元素素无无直接后继，其余元素都有一个直接前驱和直接后继。直接后继，其余元素都有一个直接前驱和直接后继。（2）非线性结构（树、堆、图（网络），）非线性结构（树、堆、图（网络），）元素之间为一对多或多对多的非线

4、性关系，每个元素有多个直接前驱或多元素之间为一对多或多对多的非线性关系，每个元素有多个直接前驱或多个直接后继。个直接后继。5 5 从存贮结构划分数据结构从存贮结构划分数据结构数据结构从存贮结构划分为：数据结构从存贮结构划分为：(1)(1)顺序存贮（向量存贮）顺序存贮（向量存贮）所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。存仍然相邻。(2)(2)链式存贮链式存贮所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址确定，

5、逻辑上相邻的元素存放到计算机内存后不一定是相邻的。确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。(3)(3)索引存贮索引存贮使使用用该该方方存存放放元元素素的的同同时时，还还建建立立附附加加的的索索引引表表，索索引引表表中中的的每每一一项项称称为为索索引引项项，索索引引项项的的一一般般形形式式是是：（关关键键字字，地地址址），其其中中的的关关键键字字是是能能唯唯一一标标识一个结点的那些数据项。识一个结点的那些数据项。(4)(4)散列存贮散列存贮通过构造散列函数，用函数的值来确定元素存放的地址。通过构造散列函数，用函数的值来确定元素存放的地址。6 6、抽抽象象数数据据类类型型：用用户户

6、在在数数据据类类型型基基础础上上自自己己定定义义和和实实现现的的数数据据类类型型。在在更高一级的抽象程度上实现了信息的隐藏和封装。更高一级的抽象程度上实现了信息的隐藏和封装。三、算法：三、算法：1、算法的概念算法的概念（algorithm）通通俗俗地地讲讲，算算法法就就是是一一种种解解题题的的方方法法。更更严严格格地地说说，算算法法是是由由若若干干条条指指令令组组成成的的有有穷穷序序列列，它它必必须须满满足足下下述述条条件件（也也称称为算法的五大特性）：为算法的五大特性）：（1）输输入入：具具有有0个个或或多多个个输输入入的的外外界界量量（算算法法开开始始前前的的初初始量）始量）（2）输输出出

7、：至至少少产产生生一一个个输输出出，它它们们是是算算法法执执行行完完后后的的结结果。果。（3有穷性：算法的执行步骤必须是有限的。有穷性：算法的执行步骤必须是有限的。（4)确定性：每条指令的含义都必须明确，无二义性。确定性：每条指令的含义都必须明确，无二义性。（5)有效性：每条指令必须是可执行的。有效性：每条指令必须是可执行的。2 2算法和程序的关系算法和程序的关系算法的含义与程序十分相似，但二者是有区别的。一个程序算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性（死循环），另外，程序中的指令必须是不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，而算法中的指

8、令则无此限制。一个算法若用机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。计算机语言来书写，则它就可以是一个程序。3、算法描述、算法描述（1 1）用流程图描述算法用流程图描述算法一一个个算算法法可可以以用用流流程程图图的的方方式式来来描描述述，输输入入输输出出、判判断断、处处理理分分别别用用不不同同的的框框图图表表示示，用用箭箭头头表表示示流流程程的的流流向向。这这是是一一种种描描述述算算法法的的较较好好方方法法，目目前前在在一一些些高高级级语语言言程程序序设设计计中中仍仍然采用。然采用。（2 2）用自然语言描述算法用自然语言描述算法用我们日常生活中

9、的自然语言（可以是中文形式，也可以是用我们日常生活中的自然语言（可以是中文形式，也可以是英形式）也可以描述算法。英形式）也可以描述算法。（3 3）用其它方式描述算法用其它方式描述算法我们还可以用数学语言或约定的符号语言来描述算法。我们还可以用数学语言或约定的符号语言来描述算法。（4 4）用用C+C+描述算法描述算法在在本本教教材材中中，我我们们将将采采用用C C或或类类C+C+来来描描述述算算法法。函数类型函数类型 函数名（形参及类型说明）函数名（形参及类型说明）函数语句部分函数语句部分return(return(表达式值表达式值)；4 4、算法分析、算法分析（1 1）时间复杂度时间复杂度一个

10、算法花费的时间与算法中语句的执行次数成正比例，一个一个算法花费的时间与算法中语句的执行次数成正比例，一个算法中的语句执行次数称为语句频度或时间频度。记为算法中的语句执行次数称为语句频度或时间频度。记为T(n)T(n)，n称为问题的规模，当称为问题的规模，当n不断变化时，时间频度不断变化时，时间频度T(n)也会不断变也会不断变化化。设设T(n)的一个辅助函数为的一个辅助函数为g(n),定义为当定义为当n大于等于某一足够大大于等于某一足够大的正整数的正整数n0时，存在两个正的常数时，存在两个正的常数A和和B（其中其中AB），），使得使得AT(n)/g(n)B均成立，则称均成立，则称g(n)是是T(

11、n)的同数量级函数。把的同数量级函数。把T(n)表示成数量级的形式为：表示成数量级的形式为：T(n)=(g(n),其中大写字母其中大写字母为英文为英文Order（即数量级）一词的第一个字母。即数量级）一词的第一个字母。在各种不同算法中，若算法中语句执行次数为一个常数，则在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度另外，在时间频度不相同时，时间复杂度有可能相同，如有可能相同，如T(n)=n2+3n+4与与T(n)=4n2+2n+1它们的频度不它们的频度不同，但时间复杂度相同，都为同，但时间复杂度相同，都为O(n2)。按

12、数量级递增排列，常见的时间按数量级递增排列，常见的时间复杂度有：复杂度有：常数阶常数阶O(1),对数阶对数阶O(log2n),线性阶线性阶O(n),线性对数阶线性对数阶O(nlog2n),平方阶平方阶O(n2)，立方阶立方阶O(n3),.，k次次方方阶阶O(nk),指指数数阶阶O(2n)。随随着着问问题题规规模模n的的不不断断增增大大，上上述时间复杂度不断增大，算法的执行效率越低。述时间复杂度不断增大，算法的执行效率越低。算法的时间复杂度应是数据元素最坏情况下取值的时间复杂算法的时间复杂度应是数据元素最坏情况下取值的时间复杂度或数据元素等概率取值情况下的平均（或称期望）时间复度或数据元素等概率

13、取值情况下的平均（或称期望）时间复杂度。杂度。（2）空间复杂度空间复杂度一个算法在执行时所占有的内存开销，称为空间频度，但我们一个算法在执行时所占有的内存开销，称为空间频度，但我们一般是讨论算法占用的辅助存储空间。一般是讨论算法占用的辅助存储空间。与时间复杂度类似，空间复杂度是指算法在计算机内执行时所与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但我们一般所讨论的是除正常占用内存占用的内存开销规模。但我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似。开销外的辅助存储单元规模。讨论方法与时间复杂度类似。例题分析：例题分析：1、数据结构

14、是研究数据的、数据结构是研究数据的_和和_，以及它，以及它们之间的相互关系，并对这种结构定义相应的们之间的相互关系，并对这种结构定义相应的_，设计出相应的设计出相应的_，而确保经过这些运算后所得到的，而确保经过这些运算后所得到的新结构是新结构是_结构类型。结构类型。2、选择某种问题的最佳数据结构的标准是什么？、选择某种问题的最佳数据结构的标准是什么？答：通常有两条标准：即算法所需的时间量和算法所需的存答：通常有两条标准：即算法所需的时间量和算法所需的存储空间量。所需的书简涉及以下几个因素储空间量。所需的书简涉及以下几个因素（1）程序运行时）程序运行时所需输入的数据总量；（所需输入的数据总量；（

15、2）对原程序进行编译所需的时间；）对原程序进行编译所需的时间；（3）计算机执行每条指令所需的时间；（）计算机执行每条指令所需的时间；（4）程序中的指令）程序中的指令重复执行的次数。重复执行的次数。3、按增长率由小到大的序列排列以下的各函数：、按增长率由小到大的序列排列以下的各函数：逻辑结构存储结构运算算法原来的解：各函数由小到大的顺序是：解：各函数由小到大的顺序是：4、计算给定算法的时间复杂度、计算给定算法的时间复杂度第二章第二章线性表线性表一、学习要求：一、学习要求：掌握线性表的逻辑结构、存储结构及描述方法；掌握线性表的逻辑结构、存储结构及描述方法；熟悉、掌握并写出顺序表和链表的插入、删除结

16、点的算法，熟悉、掌握并写出顺序表和链表的插入、删除结点的算法，分析时间复杂度。分析时间复杂度。二、线性表的概念：二、线性表的概念：1 1、定义：、定义：线性表（线性表（linear listlinear list）是是n n（n0n0）个数据元素个数据元素a a1 1，a a2 2，aan n组成的有限序列。其中组成的有限序列。其中n n 称为数据元素的个数或线性表的长称为数据元素的个数或线性表的长度，当度，当n=0n=0时称为空表，时称为空表，n0n0时称为非空表。时称为非空表。2 2、线性表的特征、线性表的特征从线性表的定义可以看出线性表的特征：从线性表的定义可以看出线性表的特征：（1）有

17、且仅有一个开始结点有且仅有一个开始结点(表头结点表头结点)a1，它没有直接前它没有直接前驱，只有一个直接后继驱，只有一个直接后继;（2）有且仅有一个终端结点有且仅有一个终端结点(表尾结点表尾结点)an，它没有直接后继，它没有直接后继，只有一个直接前驱只有一个直接前驱;（3）其它结点都有一个直接前驱和直接后继；其它结点都有一个直接前驱和直接后继；（4）元素之间为一对一的线性关系。）元素之间为一对一的线性关系。3、线性表的存储结构、线性表的存储结构（1）顺序表结构）顺序表结构（用数组存储）（用数组存储）线性表的顺序存储结构线性表的顺序存储结构,也称为顺序表。其存储方式为：在内存也称为顺序表。其存储

18、方式为：在内存中开辟一片连续存储空间，但该连续存储空间的大小要大于或中开辟一片连续存储空间，但该连续存储空间的大小要大于或等于顺序表的长度，然后让线性表中第一个元素存放在连续存等于顺序表的长度，然后让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推。类推。（2）线性表的链式存贮结构）线性表的链式存贮结构线性表的链式存贮结构，也称为链表。其存贮方式是：在内线性表的链式存贮结构，也称为链表。其存贮方式是：在内存中利用存贮单元存中利用存贮单元(可以不连续可以不连续)来存放元素值及它在内存的来存放元素值及它在

19、内存的地址，各个元素的存放顺序及位置都可以以任意顺序进行，地址，各个元素的存放顺序及位置都可以以任意顺序进行，原来相邻的元素存放到计算机内存后不一定相邻，从一个元原来相邻的元素存放到计算机内存后不一定相邻，从一个元素找下一个元素必须通过地址素找下一个元素必须通过地址(指针指针)才能实现。故不能像顺才能实现。故不能像顺序表一样可随机访问，而只能按顺序访问。常用的链表有序表一样可随机访问，而只能按顺序访问。常用的链表有单单链表链表、循环链表和双向链表等。、循环链表和双向链表等。线性链表中的结点结构为：线性链表中的结点结构为：其中其中data域用来存放结点本身信息，类型由具体问题而定，域用来存放结点

20、本身信息，类型由具体问题而定，next域用来存放下一个元素地址。域用来存放下一个元素地址。4、线性表的插入和删除运算、线性表的插入和删除运算(C+程序）程序）（1）在顺序存储结构下的插入和删除运算及时间复杂度）在顺序存储结构下的插入和删除运算及时间复杂度在等概率下平均移动元素的次数为：在等概率下平均移动元素的次数为：（2）在链式存储结构下的运算）在链式存储结构下的运算在单链表的插入和删除运算中，只需改变两个结点的指针域在单链表的插入和删除运算中，只需改变两个结点的指针域即可，不需移动结点。即可，不需移动结点。因此二者的时间复杂度都为因此二者的时间复杂度都为O(1).因此二者的时间复杂度都为因此

21、二者的时间复杂度都为O(n).(3)在线性表中查找某个元素的时间复杂度：在线性表中查找某个元素的时间复杂度：在顺序存储结构中为：在顺序存储结构中为：O(1);在链式存储结构中为：在链式存储结构中为：O(n).例题分析：例题分析：1、将两个各有、将两个各有n个元素的有序表归并成一个有序表。其最个元素的有序表归并成一个有序表。其最少的比较次数为（少的比较次数为（）。）。2、在有、在有n个元素的线性表中，可删除的元素有（个元素的线性表中，可删除的元素有（）个，）个，可插入元素的位置有（可插入元素的位置有（）个）个nnn+13、设、设A是一个线性表（是一个线性表（a1,a2,a3,.an)，采用顺序存

22、储结构，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在素个数为多少？若元素插在ai与与ai+1之间（之间（0=i=n-1)的概的概率为（率为（n-i)/(n(n+1)/2)，平均每插入一个元素所需要移动的平均每插入一个元素所需要移动的元素个数是多少？元素个数是多少？解：在等概率的前提下，平均每插入一个元素所需要移解：在等概率的前提下，平均每插入一个元素所需要移动的元素个数为：动的元素个数为：（0+1+2+.+n)/(n+1)=n/2;若元素插在若元素插在ai与与ai+1之间（之间（0=i=n-1)的

23、概率为的概率为（n-i)/(n(n+1)/2)，平均每插入一个元素所需要移动的元平均每插入一个元素所需要移动的元素个数是：素个数是：n-1(n-i)2/(n(n+1)/2)=(2n+1)/3i=0第三章第三章栈和队列（操作受限的线性表）栈和队列（操作受限的线性表）学习要求：学习要求：掌握栈和队列的逻辑定义、描述方法及其特性；掌握栈和队列的逻辑定义、描述方法及其特性；理解循环队列判空和判满的方法；理解循环队列判空和判满的方法；栈和队列基本运算的算法实现，以及栈在实现递归过程中栈和队列基本运算的算法实现，以及栈在实现递归过程中的作用。的作用。一、栈的定义和基本运算一、栈的定义和基本运算1、栈的定义

24、：后进先出表、栈的定义：后进先出表2、栈的基本运算、栈的基本运算（1）置空栈：）置空栈：s=NULL；（2）判栈空判栈空empty(s)：top=NULL;(3)入栈入栈push(s,x);(4)出栈出栈pop(s)(5)读栈顶元素读栈顶元素top(s).3、栈的存储结构、栈的存储结构（1）、顺序栈：即栈的顺序存储结构，是利用一组地址连）、顺序栈：即栈的顺序存储结构，是利用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设续的存储单元依次存储自栈顶到栈底的数据元素，同时附设top指针指示栈顶元素在顺序栈中的位置。指针指示栈顶元素在顺序栈中的位置。利用栈底位置相对不变的特性，两个顺序

25、栈可以共享一个一利用栈底位置相对不变的特性，两个顺序栈可以共享一个一维数据空间，以互补余缺。具体实现时可以将两个栈的栈底维数据空间，以互补余缺。具体实现时可以将两个栈的栈底分别设在空间的两端，让它们的栈顶各自向中间延伸。分别设在空间的两端，让它们的栈顶各自向中间延伸。（2）、链栈：可以克服顺序栈所带来的大量数据元素移动）、链栈：可以克服顺序栈所带来的大量数据元素移动的不足。链栈中头指针就是栈顶指针。的不足。链栈中头指针就是栈顶指针。4、栈的应用：表达式求值、括号匹配、递归调用，即将递、栈的应用：表达式求值、括号匹配、递归调用，即将递归过程转变为非递归过程。归过程转变为非递归过程。二、队列的定义

26、和基本运算二、队列的定义和基本运算1、定义：先进先出表、定义：先进先出表2、队列的基本运算：、队列的基本运算：（1）置队列空：）置队列空：Q=NULL；（2）入队入队QInsert(x);(3)出队出队QDelete();(4)读队头元素读队头元素QFront();(5)判队空：判队空：QueueEmpty():rear=front(6)判队满：顺序队列：判队满：顺序队列：rear-front=maxsize;顺序循环队列：顺序循环队列：(rear+1)%MaxQueueSize=front3、队列的存储结构：队列的存储结构：（1）顺序队列：设置两个）顺序队列：设置两个.指针：队头指针和队尾指

27、针。指针：队头指针和队尾指针。（2）链队列：增加一个头结点，令头指针指向头结点。）链队列：增加一个头结点，令头指针指向头结点。例题分析：例题分析：1、设有一个空栈，栈顶指针为、设有一个空栈，栈顶指针为1000H（十六进制），现有十六进制），现有输入序列为输入序列为1，2，3，4，5，PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列为（后，输出序列为（），栈顶指），栈顶指针是（针是（）。）。2、31003H2、一般情况下，将递归算法转换成等价的非递归算法应该、一般情况下，将递归算法转换成等价的非递归算法应该设置（设置（）。）。A、栈栈B、队列队列C、堆栈或队列堆栈或队

28、列D、数组数组A3、在解决计算机主机与打印机之间速度不匹配问题时通、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（缓冲区应该是一个（）结构。）结构。队列第四章第四章串、数组和广义表串、数组和广义表学习要求：学习要求：理解字符串的概念及存储方式；理解字符串的概念及存储方式；串的模式匹配算法；串的模式匹配算法；掌握数组的逻辑结构特征及存储方式；掌握数组的逻辑结构特征及存储方式；掌握特

29、殊矩阵的压缩存储方式及对应公式（下标变换公式）；掌握特殊矩阵的压缩存储方式及对应公式（下标变换公式）；掌握稀疏矩阵的三元组表示及转置算法的基本思想；掌握稀疏矩阵的三元组表示及转置算法的基本思想；掌握广义表的有关概念和存储方式；掌握广义表的有关概念和存储方式；掌握广义表的基本特征和运算规则（求表头元素、表尾等）。掌握广义表的基本特征和运算规则（求表头元素、表尾等）。一、串的概念和存储结构一、串的概念和存储结构1、串的定义：串、串的定义：串(string)是由零个或多个字符组成的有限是由零个或多个字符组成的有限序列，记作序列，记作s=“a1a2an”，其中其中s为串的名字，用成对的双为串的名字，用

30、成对的双引号括起来的字符序列为串的值，但两边的双引号不算串引号括起来的字符序列为串的值，但两边的双引号不算串值，不包含在串中。值，不包含在串中。2、串的几个基本概念：、串的几个基本概念：空串：不含任何字符的串称为空串，它的长度空串：不含任何字符的串称为空串，它的长度n=0，记为记为s=“”。空格串：由一个或多个空格所组成的串。空格虽然是一个空格串：由一个或多个空格所组成的串。空格虽然是一个空白符，但它确是一个字符，计算串长度时要将其计算在空白符，但它确是一个字符，计算串长度时要将其计算在内。内。子串：若一个串是另一个串中连续的一段，则这个串称为子串：若一个串是另一个串中连续的一段，则这个串称为

31、另一个串的子串，而另一个串相对于该串称为主串。另一个串的子串，而另一个串相对于该串称为主串。串串相等：两个串长度相等且对应位置上的字符也相同；相等：两个串长度相等且对应位置上的字符也相同；串比较：两个串比较大小是以字符的串比较：两个串比较大小是以字符的ASCII码值作为依据的，码值作为依据的，两个串从第一个位置上的字符开始比较，第一次出现字符大两个串从第一个位置上的字符开始比较，第一次出现字符大者所在的串为大；若一个串比较结束，则以串长者为大。者所在的串为大；若一个串比较结束，则以串长者为大。二、串的存储结构二、串的存储结构串的顺序存储结构：串的顺序存储结构：（1）串的非紧缩存储串的非紧缩存储

32、一个存储单元中只存储一个字符，和顺序表中一个元素占用一个存储单元中只存储一个字符，和顺序表中一个元素占用一个存储单元类似。一个存储单元类似。（2）串的紧缩存储串的紧缩存储根据各机器字的长度，尽可能将多个字符存放在一个字中。根据各机器字的长度，尽可能将多个字符存放在一个字中。三、串的模式匹配：1、Brute-Force算法，2、KMP算法。四、数组的性质和基本运算：1、数组的性质：（1）数据元素数目固定。一旦说明了一个数组结构，其元素不在有增减变化；（2）数据元素具有相同的类型；（3）数据元素的下标关系具有上下界的约束且下标有序。2、数组的两个基本运算：（1）给定一组下标，存取相应的数据元素；（

33、2）给定一组下标，修改相应的数据元素中某个数据项的值。注意：注意：数组不能进行整体的运算，只能对单个数组元素进行操作。五、数组的顺序存储结构：在数组的顺序存储结构中，数据元素的位置是其下标的线性函数。在多维数组中，有以行为主序和以列为主序存储两种方法。（地址计算公式）六、矩阵的压缩存储（对称矩阵、三角矩阵、对角矩阵）非零元下标与数组下标的对应关系。P107-108七、稀疏矩阵的存储结构：三元组和十字链表。八、广义表的概念及基本操作1、广义表的定义：由零个或多个单元素或子表所组成的有限序列。广义表与线性表的区别在于：线性表的成分都是结构上不可分的单元素，而广义表的成分可以是单元素，也可以是有结构

34、的表。广义表的长度是指广义表中元素的个数。广义表的深度是指广义表展开后所含的括号的层数。2、广义表的基本操作：（1）取表头；（2）取表尾。3、广义表的特点（1）广义表的元素可以是子表，而子表的元素还可以是子表；（2）广义表可为其它广义表所共享；（3）广义表可以是一个递归的表，即广义表也可以是其本身的一个广义表。九、广义表的存储结构：链式存储结构。十、广义表的应用：m元多项式的表示。例1：字符串S满足等式strcat(head(tail(s),head(tail(tail(s)=“dc”,其中head,tail的定义同广义表类似。例如：head(xyz)=x,tail(xyz)=yz,则S为（）

35、A:abcd B:acbd C:acdb D:adcb(中科院计算所1996年试题）例2：设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（）。A:2(n-1)B:n2 C:n2/2 D:n2/2+n/2-1(中科院计算所1997年试题）例5-1：一个nxn的对称矩阵，如果以行为主序存入内存，则其容量为多少？（西电1999年试题）解：若对该矩阵采用压缩存储，需要 n(n+1)/2个存储单元。若以非压缩的二维数组的形式存储，则需要n2个存储单元。例5-2：设有一上三角矩阵A(aij)nxn，将其上三角元素逐行存于数组B1m之中（m充分大），使

36、得Bk=aij且k=f1(i)+f2(j)+c。试推导出函数f1、f2和常数c（要求f1、f2中不含有常数项）。（中科院自动化所1999年试题）解：由前面内容分析可得k和i、j之间的关系为：(i-1)(2n-i+2)/2+(j-(i-1)ij所以当ij时，有：f1(i)=f2(j)=0,c=(n(n+1)/2)+1例例1：设设mxn阶阶稀稀疏疏矩矩阵阵A有有t个个非非零零元元素素，其其三三元元组组表表表表示示为为LTMA1.(t+1),1.3,试试问问：非非零零元元素素的的个个数数t达达到到什什么么程程度度时时采采用用LTMA表表示示A才才有有意意义义？（北北航航1998年试题）年试题）解：稀

37、疏矩阵A有t个非零元素，占用数组LTMA的存储单元个数为:3(t+1),而用二维数组存储时，占用mxn个存储单元。当当3(t+1)mn,即即t=3)的稀疏矩阵的稀疏矩阵A中，只有下标满足中，只有下标满足1in和和n-i=j=n-i+2的元素的元素Ai,j不等于零，若这些不等于零，若这些非零元素按以行优先的顺序存入首地址为非零元素按以行优先的顺序存入首地址为FIRST的一的一个连续的存储空间中，试写出任一非零元素个连续的存储空间中，试写出任一非零元素Ai,j的的存储地址公式（西电存储地址公式（西电1998年试题）年试题）解：依题意可知这个矩阵的第一行和第n行的元素均为零，对满足2=i=0)个有限

38、结点构成的集合。n=0的树称为空树(empty)；对n0的树T有：（1）有一个特殊的结点称为根结点(root),根结点没有前驱结点；（2）当n1时，除根结点外其他结点被分成m(m0)个互不相交的子集T1,T2,Tm。其中每个子集Ti(1=i=0）。性质性质2 若规定空树的深度为-1，则深度为k的二叉树最大结点数为2k+1-1（k=-1）。性质性质3 对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。性质性质4具有n个结点的完全二叉树深度k为不超过log2(n+1)-1 的最大整数。性质性质5如果将一棵有n个结点的完全二叉树从上到下，从左到右对结点编号0，1，

39、2，n，然后按此编号将该二叉树中各结点顺序地存放于一个一维数组中，对任意结点 i(0in)，则有如下结论成立：（1）若 i0，则序号为i的结点的双亲结点的序号为(i-1)/2(“/”表示整除），若i=0，则序号为i的结点为根结点，无双亲结点；（2）若2i+1=n,则序号为i的结点无左子女。即结点为叶结点；（3）若2i+2=n,则序号为i的结点无右子女。（4）若结点i序号为奇数且不等于1，则它的左兄弟为i-1；（5）若结点i序号为偶数且不等于n，它的右兄弟为i+1。满二叉树满二叉树 深度为k具有2k+1-1个结点的二叉树，称为满二叉树。从上面满二叉树定义可知，必须是二叉树的每一层上的结点数都达到

40、最大，否则就不是满二叉树。即满二叉树的每一个结点或者是一个分支结点，并恰有两个非空子结点；或者是叶结点。完全二叉树完全二叉树如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1 n的结点一一对应，则称这棵二叉树为完全二叉树。从完全二叉树定义可知，结点的排列顺序遵循从上到下、从左到右的规律。所谓从上到下，表示本层结点数达到最大后，才能放入下一层。从左到右，表示同一层结点必须按从左到右排列，若左边空一个位置时不能将结点放入右边。满二叉树定理1：非空满二叉树的叶结点数等于其分支结点数加1。二叉树定理2：一个非空二叉树空子树的数目等于其结点数目加1。五、二叉树的遍历：

41、中序遍历，先序遍历，后序遍历和层序遍历。1、中序遍历：中序遍历根结点的左子树；访问根结点；中序遍历根结点的右子树。2、前序遍历：访问根结点；前序遍历根结点的左子树；前序遍历根结点的右子树。3、后序遍历：后序遍历根结点的左子树；后序遍历根结点的右子树；访问根结点。4、层序遍历：从根结点到叶结点，从左子树到右子树的次序访问二叉树的结点。访问根结点；层序遍历根结点的左子树；层序遍历根结点的右子树。一个二叉树的遍历序列不能决定一棵二叉树，前序序列和中序序列、后序序列和中序序列可唯一确定一棵二叉树，而前序序列和后序序列则不能。六、二叉树的存储结构及二叉树类1、二叉树的顺序存储结构 将完全二叉树的结点按从

42、上到下和从左到右的次序存储在一组从0开始的连续的内存单元中，其结点之间的关系可按性质5的公式计算得到，这就是二叉树的顺序存储结构。2、二叉链存储结构每个结点分成三个域,数据域data,左子树指针域leftChild、右子树指针域rightChild。3、二叉树的三叉链表表示法三叉链是在二叉链的基础上再增加一个双亲结点指针域parent。4、二叉树结点类和二叉树类。5、遍历算法应用举例：由二叉树的前序序列（或后序序列）和中序序列建立该二叉树。七、树、森林和二叉树的转换1 1树转换成二叉树树转换成二叉树可以分为三步：连线、抹线、旋转。2森林转换成二叉树（1）将森林中每一棵树分别转换成二叉树；（2）

43、合并使第n棵树接入到第n-1棵的右边并成为它的右子树，第 n-1 棵二叉树接入到第n-2 棵的右边并成为它的右子树，第2棵二叉树接入到第1棵的右边并成为它的右子树，直到最后剩下一棵二叉树为止。3、二叉树还原成树或森林(1)右链断开将二叉树的根结点的右链及右链的右链等全部断开，得到若干棵无右子树的二叉树。（2）二叉树还原成树将（1）中得到的每一棵二叉树都还原成树（与树转换成二叉树的步骤刚好相反：先连接双亲结点与其所有孩子结点之间的连线，然后抹掉相邻兄弟结点之间的连线。）八、K叉树 K叉树的结点有K个子结点。因此K叉树的度最大为K.满K叉树和完全K叉树的定义和相应二叉树的定义一样。九、线索二叉树1

44、、线索的概念 在原来的二叉链表结点中，利用原有的空孩子指针来存放直接前驱和后继，这样的指针称为“线索”，加线索的过程称为线索化，加了线索的二叉树，称为线索二叉树，对应的二叉链表称为线索二叉链表。2、建立线索二叉树 二叉链表中每个结点有5个域，但其中只有2个指针，增加线索后的二叉链表结点结构可描述如下：3、访问线索二叉树即：如何在线索二叉树中查找结点的前驱和后继。（1 1）查找指定结点在中序线索二叉树中的直接后继；）查找指定结点在中序线索二叉树中的直接后继；若所找结点右标志rtag=1，则右孩子域指向中序后继，否则，中序后继应为遍历右子树时的第一个访问结点,即右子树中最左下的结点。（2 2）查找

45、指定结点在中序线索二叉树中的的直接）查找指定结点在中序线索二叉树中的的直接前驱前驱若所找结点左标志ltag=1，则左孩子域指向中序前驱，否则，中序前驱应为遍历左子树时的最后一个访问结点，即左子树中最右下的结点。(3)(3)查找指定点在前序线索二叉树中的直接后继查找指定点在前序线索二叉树中的直接后继前序后继的查找比较方便，若无右孩子，右链为后继，否则左孩子为后继。(4)(4)查找指定结点在后序线索二叉树中的直接前驱查找指定结点在后序线索二叉树中的直接前驱后序前驱的查找也比较方便，若左孩子为空，左链指前驱，若右孩子为空，左孩子指前驱，若左右孩子都不为空，则右孩子为前驱。4、线索二叉树上的遍历(1)

46、前序遍历线索二叉树算法；(2)中序遍历线索二叉树算法。十、堆1、堆的定义假设n个数据元素的关键码k0,k1,k2,.,kn-1,按完全二叉树的顺序存放在一个一维数组中，如果当2i+1n时有：ki=k2i+1(i=0,1,.,(n-1)/2);如果当2i+2n时有：ki=k2i+2(i=0,1,.,(n-1)/2);则这样的数据元素集合称为最小堆。如果当2i+1=k2i+1(i=0,1,.,(n-1)/2);如果当2i+2=k2i+2(i=0,1,.,(n-1)/2);则这样的数据元素集合称为最大堆。2、堆的性质（1）最小堆的根结点是堆中值最小的数据元素，最大堆的根结点是堆中值最大的数据元素，我

47、们都把它们称为堆顶元素。（2）对于最小堆，从根结点到每个叶结点的路径上，数据元素组成的序列都是非递减有序的。对于最大堆，从根结点到每个叶结点的路径上，数据元素组成的序列都是非递增有序的。3、堆的应用 堆的一个应用是优先队列：在多道程序设计中，将优先权最高的进程出列，分配CPU运行。堆的另一个应用是递增或递减排序。堆结构的重要价值在于：在所有能直接访问一个表中的最大或最小数据元素的算法中，堆结构是时间效率最高的一种。4、最小堆类十一、哈夫曼树1、哈夫曼树的定义哈夫曼树的定义 在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。2、哈夫曼

48、树的构造哈夫曼树的构造假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值 分 别 设 为 w1,w2,wn,则 哈 夫 曼 树 的 构 造 规 则 为：(1)将w1,w2,wn看成是有n 棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。3、哈夫曼编码、哈夫曼编码在哈夫曼树中，规定往左编码为0，往右编码为1，则得到叶子结点编码为从根结点到叶子结点中所

49、有路径中0和1的顺序排列。一、填空题一、填空题1、假定一棵树的广义表表示为、假定一棵树的广义表表示为A(B(E),C(F(H,I,J),G),D),则该则该树的度为树的度为，树的深度为，树的深度为，终端结点的个数为，终端结点的个数为。（空树的深度为。（空树的深度为0）2、设、设F是一个森林，是一个森林，B是由是由F转换得到的二叉树，转换得到的二叉树，F中有中有n个非个非终端结点，则终端结点，则B中右指针域为空的结点有中右指针域为空的结点有个。个。3、对于一个具有、对于一个具有n个结点的二叉树，当它为一棵个结点的二叉树，当它为一棵二叉树二叉树时具有最小高度，即为时具有最小高度，即为，当它为一棵，

50、当它为一棵二叉树时，二叉树时，具有最大高度，即为具有最大高度，即为。4、在一棵二叉排序树上按、在一棵二叉排序树上按遍历得到的结点序列是一个遍历得到的结点序列是一个有序序列。有序序列。5、由三个结点构成的二叉树，共有、由三个结点构成的二叉树，共有种不同的结构。种不同的结构。346n+1完全lb(n+1)-1单支n中序5二、选择题二、选择题1、假定在一棵二叉树中，双分支结点数为、假定在一棵二叉树中，双分支结点数为15。单分支结点数。单分支结点数为为30，则叶结点数为，则叶结点数为个。个。（A）15（B)16(C)17(D)472、在一棵具有在一棵具有k层的满三层的满三叉树中，结点总数为叉树中，结点