1、第第1 1章章 绪论绪论2022年8月3日星期三课程简介课程简介 数据结构是计算机专业的一门专业基础课程，很数据结构是计算机专业的一门专业基础课程，很多后续课程都要用到本课程所涉及的知识。例如，程多后续课程都要用到本课程所涉及的知识。例如，程序设计、编译技术和操作系统等课程都要使用一些基序设计、编译技术和操作系统等课程都要使用一些基本的数据结构及其相关的算法；本课程讨论的其他一本的数据结构及其相关的算法；本课程讨论的其他一些数据结构，如广义表、集合以及图等也是很多应用些数据结构，如广义表、集合以及图等也是很多应用领域经常涉及的。本课程的目的是介绍一些最常用的领域经常涉及的。本课程的目的是介绍一
2、些最常用的数据结构，阐明数据结构内在的逻辑关系，讨论它们数据结构，阐明数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种数据结构，讨论在计算机中的存储表示，并结合各种数据结构，讨论其各种操作的实现算法。其各种操作的实现算法。2022年8月3日星期三本章概述本章概述 本章将概括地介绍一些基本概念和术语，包括数本章将概括地介绍一些基本概念和术语，包括数据和数据结构、数据的逻辑结构和存储结构、数据类据和数据结构、数据的逻辑结构和存储结构、数据类型、算法的概念及描述、算法的复杂度分析等。型、算法的概念及描述、算法的复杂度分析等。2022年8月3日星期三1.1 1.1 引言引言 计算机应用
3、广泛，加工处理的对象也在发展：计算机应用广泛，加工处理的对象也在发展：由纯粹的数值数据发展到字符、表格和图像等各由纯粹的数值数据发展到字符、表格和图像等各种具有一定结构的数据。种具有一定结构的数据。为了设计出一个为了设计出一个“好好”的程序，必须分析待处理的程序，必须分析待处理的对象的特性以及各对象之间存在的关系，这就是数的对象的特性以及各对象之间存在的关系，这就是数据结构这门学科形成和发展的背景。据结构这门学科形成和发展的背景。2022年8月3日星期三 用计算机解决一个具体问题时，一般需要经过用计算机解决一个具体问题时，一般需要经过以下几个步骤：以下几个步骤：首先分析实际问题并从中抽象出一个
4、适当的数首先分析实际问题并从中抽象出一个适当的数学模型，然后设计一个解决此数学模型的算法，最学模型，然后设计一个解决此数学模型的算法，最后编制出程序上机调试，直至得到最终的解答，其后编制出程序上机调试，直至得到最终的解答，其过程如图所示。过程如图所示。2022年8月3日星期三 寻求数学模型的实质是分析问题，从中提取操作寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间的关系，然后使用的对象，并找出这些操作对象之间的关系，然后使用数学模型加以描述。数学模型加以描述。数值计算问题的数学模型一般可用数学方程或数数值计算问题的数学模型一般可用数学方程或数学公式来描述，而更多的非数
5、值计算问题无法用数学学公式来描述，而更多的非数值计算问题无法用数学方程加以描述。下面给出几个例子。方程加以描述。下面给出几个例子。2022年8月3日星期三 【例【例1-11-1】某单位职工档案管理问题。为了简单，】某单位职工档案管理问题。为了简单，假定每个职工的档案只包括以下假定每个职工的档案只包括以下5 5项：职工号、姓名、项：职工号、姓名、性别、出生日期和职称。一般来说，档案管理人员很性别、出生日期和职称。一般来说，档案管理人员很可能将这些档案组织成表格形式，如表所示，表中的可能将这些档案组织成表格形式，如表所示，表中的每一行反映了一个职工的基本情况。每一行反映了一个职工的基本情况。202
6、2年8月3日星期三 本问题中的处理要求包括所有能用计算机完成的档本问题中的处理要求包括所有能用计算机完成的档案管理工作，至少应包含以下功能：案管理工作，至少应包含以下功能：(1)(1)查找，需要时在表格中找出某人的档案。查找，需要时在表格中找出某人的档案。(2)(2)读取，阅读通过查找找到的档案。读取，阅读通过查找找到的档案。(3)(3)插入，调入新职工时将该职工的档案加入表格中。插入，调入新职工时将该职工的档案加入表格中。(4)(4)删除，某职工调离时，从表格中撤销其档案。删除，某职工调离时，从表格中撤销其档案。(5)(5)更新，某职工情况变化（如晋升职称）时，修改档案更新，某职工情况变化（
7、如晋升职称）时，修改档案的有关内容。的有关内容。2022年8月3日星期三 上述每一项功能又可称为一个上述每一项功能又可称为一个“运算运算”。由此，。由此，从职工档案管理问题抽象出来的数学模型便包含职工从职工档案管理问题抽象出来的数学模型便包含职工档案表和对此表进行的各种运算。在这类管理问题的档案表和对此表进行的各种运算。在这类管理问题的数学模型中，计算机处理的对象之间通常存在着一种数学模型中，计算机处理的对象之间通常存在着一种最简单的线性关系，这类数学模型可称为线性的数据最简单的线性关系，这类数学模型可称为线性的数据结构。诸如此类的还有电话自动查号系统、排课系统、结构。诸如此类的还有电话自动查
8、号系统、排课系统、仓库库存管理系统等各种应用系统。仓库库存管理系统等各种应用系统。2022年8月3日星期三 【例【例1-21-2】UNIXUNIX操作系统中文件系统的系统结构图。操作系统中文件系统的系统结构图。UNIXUNIX操作系统中文件系统的底层是根目录，根目录下包含操作系统中文件系统的底层是根目录，根目录下包含binbin、liblib、useruser、etcetc等一级子目录，而等一级子目录，而binbin目录下又包含目录下又包含mathmath、dsds、swsw等二级子目录，等二级子目录，useruser目录下又包含目录下又包含yinyin、xiexie、tangtang等二级子
9、目录，等二级子目录，yinyin目录下有目录下有Linklist.cLinklist.c、Stack.cStack.c和和Tree.cTree.c等若干个文件，如图所示。等若干个文件，如图所示。2022年8月3日星期三 如果将这些目录和文件都画在一张图上，它们之间如果将这些目录和文件都画在一张图上，它们之间所呈现的是一种层次关系，从上到下按层进行展开形成所呈现的是一种层次关系，从上到下按层进行展开形成一棵倒长的一棵倒长的“树树”。“树根树根”是系统的根目录，其他目是系统的根目录，其他目录和文件是这棵树上的录和文件是这棵树上的“树叶树叶”，从根结点到某个叶子，从根结点到某个叶子结点经过的路径就是
10、当前文件的绝对路径。由此可见，结点经过的路径就是当前文件的绝对路径。由此可见，“树树”也可以是某些非数值计算问题的数学模型，它也也可以是某些非数值计算问题的数学模型，它也是一种数据结构。是一种数据结构。“树树”状结构的模型在生活中接触状结构的模型在生活中接触的也比较多，如国家行政区域规划、书籍目录等。的也比较多，如国家行政区域规划、书籍目录等。2022年8月3日星期三 【例【例1-31-3】比赛编排问题。有】比赛编排问题。有6 6支球队进行足球比赛，支球队进行足球比赛，分别用分别用V1V1、V2V2、V3V3、V4V4、V5V5、V6V6表示这表示这6 6支球队，它们支球队，它们之间的比赛情况
11、也可以用一个称为之间的比赛情况也可以用一个称为“图图”的数据结构来的数据结构来表示，图中的每个顶点表示一个球队，如果从顶点表示，图中的每个顶点表示一个球队，如果从顶点ViVi到到VjVj之间存在有向边之间存在有向边Vi，则表示球队，则表示球队ViVi战胜球队战胜球队VjVj，如如V1V1队战胜队战胜V2V2队，队，V2V2队战胜队战胜V3V3队，队，V3V3队战胜队战胜V5V5队等，这队等，这种胜负情况可以用图表示。种胜负情况可以用图表示。2022年8月3日星期三 由此可以看出，用点、点与点之间的线所构成的图由此可以看出，用点、点与点之间的线所构成的图也可以反映实际生产和生活中的某些特定对象之
12、间的特也可以反映实际生产和生活中的某些特定对象之间的特定关系。诸如此类有铁路交通图、教学编排图等。定关系。诸如此类有铁路交通图、教学编排图等。综合以上综合以上3 3个例子可见，描述非数值计算问题的数个例子可见，描述非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构及其运算。据结构及其运算。因此可以说，数据结构课程主要是研究非数值性程因此可以说，数据结构课程主要是研究非数值性程序设计中所出现的计算机操作对象以及它们之间的关系序设计中所出现的计算机操作对象以及它们之间的关系和运算等的学科。和运算等的学科。2022年8月3日星期三
13、 在美国，数据结构作为一门独立的课程开始于在美国，数据结构作为一门独立的课程开始于19681968年。当时，数据结构几乎和图论，特别是表、树的理年。当时，数据结构几乎和图论，特别是表、树的理论为同义语。论为同义语。数据结构在计算机学科中起着承上启下的作用，在数据结构在计算机学科中起着承上启下的作用，在计算机技术的各个领域也有着广泛的应用。计算机技术的各个领域也有着广泛的应用。学习数据结构的目的是了解计算机处理对象的特性，学习数据结构的目的是了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。并对它们进行处理。2
14、022年8月3日星期三1.2 1.2 基本术语基本术语 数据数据(data)(data)：数据是客观事物的符号表示，在计算：数据是客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。理的符号的总称。数据元素数据元素(data element)(data element)：数据元素是数据的基本：数据元素是数据的基本单位，在计算机程序中通常把它作为一个整体来处理。单位，在计算机程序中通常把它作为一个整体来处理。1.2.1 1.2.1 数据及相关概念数据及相关概念2022年8月3日星期三 例如，【例例如，【例1-2
15、1-2】中的文件系统的系统结构图的一】中的文件系统的系统结构图的一个目录，【例个目录，【例1-31-3】中的】中的“图图”的一个圆圈都被称为一个的一个圆圈都被称为一个数据元素。有时，一个数据元素又可以由若干个数据项数据元素。有时，一个数据元素又可以由若干个数据项(data item)(data item)组成。如表下所示学生成绩表中的一条记组成。如表下所示学生成绩表中的一条记录为一个数据元素，而记录中的学号、姓名、语文等都录为一个数据元素，而记录中的学号、姓名、语文等都分别为一个数据项。数据项是数据的不可分割的最小单分别为一个数据项。数据项是数据的不可分割的最小单位。数据元素也可以仅有一个数据
16、项。位。数据元素也可以仅有一个数据项。2022年8月3日星期三 数据对象数据对象(data object)(data object)：数据对象是性质相同：数据对象是性质相同的数据元素组成的集合，是数据的一个子集。数据元的数据元素组成的集合，是数据的一个子集。数据元素是数据对象的数据成员。素是数据对象的数据成员。例如，正整数的数据对象是集合例如，正整数的数据对象是集合N=1,2,3,4,N=1,2,3,4,，字母字符数据对象是集合字母字符数据对象是集合N=A,B,C,ZN=A,B,C,Z。数据结构数据结构(data structure)(data structure)：是相互之间存在一：是相互之
17、间存在一种或多种特定关系的数据元素的集合。数据结构包括种或多种特定关系的数据元素的集合。数据结构包括数据的逻辑结构和存储结构。数据的逻辑结构和存储结构。2022年8月3日星期三 逻辑结构的逻辑结构的4 4种形式种形式(1)(1)集合：数据元素间为松散的关系。在集合结构中各元集合：数据元素间为松散的关系。在集合结构中各元素之间，除了素之间，除了“同属于某一个数据对象同属于某一个数据对象”的关系外，再的关系外，再无其他的关系，如图无其他的关系，如图(a)(a)所示。所示。1.2.21.2.2 数据的逻辑结构数据的逻辑结构2022年8月3日星期三(2)(2)线性结构：数据元素间为严格的一对一关系，除
18、第线性结构：数据元素间为严格的一对一关系，除第一个元素外，其他元素只有一个前驱，除最后一个元一个元素外，其他元素只有一个前驱，除最后一个元素外，其他元素只有一个后继，如图素外，其他元素只有一个后继，如图(b)(b)所示。所示。(3)(3)树状结构：数据元素之间为严格的一对多的关系，树状结构：数据元素之间为严格的一对多的关系，即一个元素只有一个前驱，但可以有多个后继，如图即一个元素只有一个前驱，但可以有多个后继，如图(c)(c)所示。所示。(4)(4)图状结构：数据元素之间存在多对多的关系，也就图状结构：数据元素之间存在多对多的关系，也就是说元素间的逻辑关系可以是任意的。图状结构如图是说元素间的
19、逻辑关系可以是任意的。图状结构如图(d)(d)所示。所示。2022年8月3日星期三简单地说，数据结构就是带有结构的数据元素简单地说，数据结构就是带有结构的数据元素的集合。的集合。数据结构可以用二元组来进行数学意义上的形数据结构可以用二元组来进行数学意义上的形式定义：式定义：Data_StructureData_Structure=(D=(D，R)R)其中，其中，D D是数据元素的有限集，即数据对象；是数据元素的有限集，即数据对象；R R是是D D中所有数据元素之间的关系的有限集。中所有数据元素之间的关系的有限集。2022年8月3日星期三 【例【例1-41-4】为毕业设计小组设计一个数据结构。假
20、设每】为毕业设计小组设计一个数据结构。假设每个小组的关系是个小组的关系是1 1名教师指导名教师指导110110名学生，则数据结构的名学生，则数据结构的二元组表示如下：二元组表示如下：Group=(P,R)Group=(P,R)其中，其中，P=T,G1,Gn,1n10P=T,G1,Gn,1n10；R=T,GiR=|1in,1n10|1in,1n10。上述数据结构的定义是一种数学意义上的定义。上述数据结构的定义是一种数学意义上的定义。“数据结构数据结构”定义中的定义中的“关系关系”是指数据间的逻辑关系，是指数据间的逻辑关系，故也称数据结构为逻辑结构。故也称数据结构为逻辑结构。2022年8月3日星期
21、三 可将集合、树状结构、图状结构归纳为非线性结构。可将集合、树状结构、图状结构归纳为非线性结构。因此，数据的逻辑结构可分为两大类，即线性结构和非因此，数据的逻辑结构可分为两大类，即线性结构和非线性结构。线性结构。然而，讨论数据结构的目的是在计算机中实现对它然而，讨论数据结构的目的是在计算机中实现对它的操作，因此还需研究如何在计算机中表示它，即数据的操作，因此还需研究如何在计算机中表示它，即数据的存储结构，又称物理结构。的存储结构，又称物理结构。2022年8月3日星期三 数据的逻辑结构：指根据实际问题的需要而选择数据的逻辑结构：指根据实际问题的需要而选择设计，面向问题与计算机本身无关，是不依赖于
22、机器设计，面向问题与计算机本身无关，是不依赖于机器的。的。数据存储结构：指数据在计算机中的物理表示和数据存储结构：指数据在计算机中的物理表示和存储的方式。涉及数据元素及其关系在存储器中的物存储的方式。涉及数据元素及其关系在存储器中的物理位置、机器响应的速度等方面的因素，物理结构的理位置、机器响应的速度等方面的因素，物理结构的设计与计算机密切相关。设计与计算机密切相关。1.2.3 1.2.3 数据的存储结构数据的存储结构2022年8月3日星期三 计算机中存储信息的最小单位叫做位计算机中存储信息的最小单位叫做位(bit)(bit)，8 8位位可表示一个字节可表示一个字节(byte)(byte)，两
23、个字节称为一个字，两个字节称为一个字(word)(word)，字节、字或更多的二进制位可称为位串，这个位串称字节、字或更多的二进制位可称为位串，这个位串称为元素为元素(element)(element)或结点或结点(node)(node)。当数据元素由若干。当数据元素由若干个数据项组成时，则位串中对应于每个数据项的子位个数据项组成时，则位串中对应于每个数据项的子位串称为数据域串称为数据域(data field)(data field)。2022年8月3日星期三 线性表的逻辑结构是：除第一个元素外，其他线性表的逻辑结构是：除第一个元素外，其他元素只有一个前驱，除最后一个元素外，其他元素元素只有一
24、个前驱，除最后一个元素外，其他元素只有一个后继。只有一个后继。线性表在计算机中的表示和存储有两种方式：线性表在计算机中的表示和存储有两种方式：用连续的存储单元存储；用连续的存储单元存储；用分散的存储单元存储，并用指针将其连接。用分散的存储单元存储，并用指针将其连接。2022年8月3日星期三 数据元素之间的关系在计算机中有两种不同的存数据元素之间的关系在计算机中有两种不同的存储方法：储方法：顺序存储顺序存储 链式存储。链式存储。顺序存储：把数据元素依次存储在一组地址连续顺序存储：把数据元素依次存储在一组地址连续的存储单元中，元素间的逻辑关系由存储单元的位置的存储单元中，元素间的逻辑关系由存储单元
25、的位置直接体现直接体现，由此得到的存储表示称为顺序存储。，由此得到的存储表示称为顺序存储。2022年8月3日星期三顺序存储结构的特点是所有元素存放在一片连续顺序存储结构的特点是所有元素存放在一片连续的存储单元中，逻辑结构上相邻的元素存放到计算机的存储单元中，逻辑结构上相邻的元素存放到计算机内后仍然相邻，如图所示。内后仍然相邻，如图所示。2022年8月3日星期三 链式存储：将数据元素存储在一组任意的存储单链式存储：将数据元素存储在一组任意的存储单元中，而用附加的指针元中，而用附加的指针(pointer)(pointer)表示元素之间的逻表示元素之间的逻辑关系，由此得到的存储表示称为链式存储。辑关
26、系，由此得到的存储表示称为链式存储。存储结构的每个结点都由两部分组成：数据域和存储结构的每个结点都由两部分组成：数据域和指针域。其中指针域。其中,数据域存放元素本身的数据，指针域数据域存放元素本身的数据，指针域存放指针，如图所示。存放指针，如图所示。2022年8月3日星期三 链式存储结构的特点是所有元素可以存放在不连链式存储结构的特点是所有元素可以存放在不连续的存储单元中，元素之间的关系可以通过地址确定，续的存储单元中，元素之间的关系可以通过地址确定，逻辑结构上相邻的元素存放到计算机内后不一定是相逻辑结构上相邻的元素存放到计算机内后不一定是相邻的。邻的。数据的逻辑结构与存储结构是密不可分的两个
27、方数据的逻辑结构与存储结构是密不可分的两个方面，任何一种算法的设计都取决于选定的数据的逻辑面，任何一种算法的设计都取决于选定的数据的逻辑结构，而算法的实现则依赖于所采用的存储结构。结构，而算法的实现则依赖于所采用的存储结构。2022年8月3日星期三 1.1.数据类型数据类型 数据类型数据类型(data type)(data type)是一个值的集合和定义在是一个值的集合和定义在这个值集上的一组操作的总称。这个值集上的一组操作的总称。按按“值值”是否可分解，把数据类型分为两类：是否可分解，把数据类型分为两类：(1)(1)原子类型：每一对象仅由单值构成的类型，其原子类型：每一对象仅由单值构成的类型
28、，其值不可分解。值不可分解。(2)(2)结构类型：每一对象可由若干成分按某种结构结构类型：每一对象可由若干成分按某种结构构成，其值可分成若干成分构成，其值可分成若干成分(或称分量或称分量)。1.2.4 1.2.4 数据类型数据类型2022年8月3日星期三 某种意义上，数据结构可以看成一组具有相同结某种意义上，数据结构可以看成一组具有相同结构的值，而数据类型可以看成由一种数据结构和定义构的值，而数据类型可以看成由一种数据结构和定义在其上的一组操作组成。在其上的一组操作组成。2 2抽象数据类型抽象数据类型 抽象数据类型抽象数据类型(abstract data type(abstract data
29、type，ADTADT)是指一是指一个数学模型及定义在该模型上的一组操作。个数学模型及定义在该模型上的一组操作。抽象数据类型不仅包括数据类型的定义，而且为这抽象数据类型不仅包括数据类型的定义，而且为这个新类型指明了一个有效的操作集合。个新类型指明了一个有效的操作集合。2022年8月3日星期三 抽象强调数据类型的数学特性，而不管它们在不抽象强调数据类型的数学特性，而不管它们在不同处理器上的实现方法和细节。同处理器上的实现方法和细节。抽象数据类型和数据类型实质上是同一个概念。抽象数据类型和数据类型实质上是同一个概念。抽象数据类型的范畴更广。抽象数据类型的范畴更广。线性表是一个抽象数据类型。线性表是
30、一个抽象数据类型。把一个数据结构以及定义在其上的一组操作封装把一个数据结构以及定义在其上的一组操作封装起来，使之成为一个抽象数据类型，则可以提高它们起来，使之成为一个抽象数据类型，则可以提高它们的复用率。的复用率。2022年8月3日星期三 抽象数据类型一般可以由数据对象、数据关系及抽象数据类型一般可以由数据对象、数据关系及基本操作基本操作3 3个要素来定义。个要素来定义。抽象数据类型可用以下三元组表示：抽象数据类型可用以下三元组表示：ADT=(DADT=(D，S S，P)P)其中，其中，D D是数据对象，用数据元素的有限集合表是数据对象，用数据元素的有限集合表示；示；S S是是D D上的关系集
31、，用结点间序偶的集合表示；上的关系集，用结点间序偶的集合表示；P P是对是对D D的基本操作集。的基本操作集。2022年8月3日星期三 根据上述定义，可用以下格式定义抽象数据类型：根据上述定义，可用以下格式定义抽象数据类型：ADT ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：ADTADT抽象数据类型名抽象数据类型名2022年8月3日星期三 其中，数据对象和数据关系的定义用伪代码描述；其中，数据对象和数据关系的定义用伪代码描述；基本操作的定义格式为：基本操作的定义格式为：基本操作名（参数表）基本操作名（参数表）初始条件：初始条件：操作结果：操
32、作结果：基本操作有两种参数：基本操作有两种参数：赋值参数为操作提供输入值；赋值参数为操作提供输入值；引入参数以开始，除了提供输入值外，还可以返引入参数以开始，除了提供输入值外，还可以返回操作结果。回操作结果。2022年8月3日星期三 “初始条件初始条件”说明了操作之前数据结构和参数应满说明了操作之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回错误信息。足的条件，若不满足，则操作失败，并返回错误信息。“操作结果操作结果”说明了操作正常完成之后，数据结构说明了操作正常完成之后，数据结构的变化情况和应返回的结果。的变化情况和应返回的结果。2022年8月3日星期三 【例【例1-51-5】使
33、用三元组定义描述抽象数据类型栈。】使用三元组定义描述抽象数据类型栈。ADT StackADT Stack 数据对象：栈的数据对象是一个数据元素序列数据对象：栈的数据对象是一个数据元素序列a1,a2,an(n0),a1,a2,an(n0),其中，数据元素其中，数据元素aiai属于用户自定义属于用户自定义的数据类型。的数据类型。数据关系：栈是一种特殊的线性表，因此其数据数据关系：栈是一种特殊的线性表，因此其数据元素也是一一对应关系，并且约定元素也是一一对应关系，并且约定anan端为栈顶，端为栈顶，a1a1端为端为栈底。栈底。基本操作：基本操作：InitStack(&SInitStack(&S)初始
34、条件：栈初始条件：栈S S不存在。不存在。操作结果：构造一个空栈操作结果：构造一个空栈S S。2022年8月3日星期三DestoryStack(&SDestoryStack(&S)初始条件：栈初始条件：栈S S已存在。已存在。操作结果：栈操作结果：栈S S被销毁。被销毁。StackEmpty(SStackEmpty(S)初始条件：栈初始条件：栈S S已存在。已存在。操作结果：若栈操作结果：若栈S S为空，则返回为空，则返回TRUE,TRUE,否则返回否则返回FALSEFALSE。StackLength(SStackLength(S)初始条件：栈初始条件：栈S S已存在。已存在。操作结果：返回操
35、作结果：返回S S的元素个数，即栈的长度。的元素个数，即栈的长度。GetTopGetTop（S S，&e&e）初始条件：栈初始条件：栈S S已存在且非空。已存在且非空。操作结果：用操作结果：用e e返回返回S S的栈顶元素。的栈顶元素。2022年8月3日星期三ClearStack(&SClearStack(&S)初始条件：栈初始条件：栈S S已存在。已存在。操作结果：将操作结果：将S S清为空栈。清为空栈。Push(&S,ePush(&S,e)初始条件：栈初始条件：栈S S存在。存在。操作结果：插入元素操作结果：插入元素e e为新的栈顶元素。为新的栈顶元素。PopPop（&S&S，&e&e）初
36、始条件：栈初始条件：栈S S已存在且非空。已存在且非空。操作结果：删除操作结果：删除S S的栈顶元素，并用的栈顶元素，并用e e返回其值。返回其值。ADT StackADT Stack2022年8月3日星期三1.3 1.3 算法分析算法分析 1 1算法算法 算法算法(algorithm)(algorithm)是对特定问题求解步骤的描述，是是对特定问题求解步骤的描述，是指令的有限序列，其中每条指令表示一个或多个操作。指令的有限序列，其中每条指令表示一个或多个操作。一个算法需具备下列一个算法需具备下列5 5个重要特性：个重要特性：(1)(1)有穷性：一个算法必须总是在执行有穷步之后结束，有穷性：一
37、个算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。且每一步都可在有穷时间内完成。1.3.1 1.3.1 算法的概念及描述算法的概念及描述2022年8月3日星期三 (2)(2)确定性：算法中的每条指令的含义都必须明确，确定性：算法中的每条指令的含义都必须明确，无二义性。在任何情况下，对于相同的输入，必须能得无二义性。在任何情况下，对于相同的输入，必须能得出相同的输出。出相同的输出。(3)(3)可行性：算法是可行的，即算法中描述的操作可行性：算法是可行的，即算法中描述的操作均可通过已经实现的基本运算的有限次执行来实现。均可通过已经实现的基本运算的有限次执行来实现。(4)(4)输入：
38、一个算法有零个或者多个输入，这些输输入：一个算法有零个或者多个输入，这些输入取自于某个特定的对象的集合。入取自于某个特定的对象的集合。(5)(5)输出：一个算法至少有一个输出，这些输出是输出：一个算法至少有一个输出，这些输出是同输入有着某些特定关系的量。没有输出的算法是没有同输入有着某些特定关系的量。没有输出的算法是没有意义的。意义的。2022年8月3日星期三 2 2算法的描述算法的描述 借助各种工具来描述算法，通常有以下几种借助各种工具来描述算法，通常有以下几种描述工具：描述工具：自然语言自然语言 流程图流程图 形式化语言形式化语言 具体的程序设计语言。具体的程序设计语言。本书采用的描述工具
39、是类本书采用的描述工具是类C C语言，以下对其语言，以下对其作简要说明：作简要说明：2022年8月3日星期三(1)(1)预定义常量和类型：预定义常量和类型：函数结果状态代码函数结果状态代码#defineTRUE#defineTRUE 1 1#defineFALSE#defineFALSE 0 0#defineOK#defineOK 1 1#defineERROR#defineERROR 0 0#defineOVERFLOW-2#defineOVERFLOW-2 Status Status是函数的类型，其值是函数结果状态代是函数的类型，其值是函数结果状态代码码typedef inttypedef
40、 int Status;Status;2022年8月3日星期三 (2)(2)数据结构的表示（存储结构）用类型定义数据结构的表示（存储结构）用类型定义(typedef(typedef)描述。数据元素类型约定为描述。数据元素类型约定为 ElemTypeElemType，由用户在使用该数据类型时自行定义。由用户在使用该数据类型时自行定义。(3)(3)基本操作的算法都用以下形式的函数描述：基本操作的算法都用以下形式的函数描述：函数类型函数类型 函数名（函数参数表）函数名（函数参数表）算法说明算法说明语句序列语句序列 函数名函数名2022年8月3日星期三 常用常用a a、b b、c c、d d、e e等
41、用作数据元素名。等用作数据元素名。常用常用i i、j j、k k、l l、m m、n n等用作整型变量名，等用作整型变量名，常用常用p p、q q、r r等用作指针变量名。等用作指针变量名。当函数返回值为函数结果状态代码时，函数定义为当函数返回值为函数结果状态代码时，函数定义为StatusStatus类型。类型。除了值调用方式外，增添了除了值调用方式外，增添了C+C+语言的引用调用的参语言的引用调用的参数传递方式。数传递方式。2022年8月3日星期三(4)(4)赋值语句有：赋值语句有：简单赋值语句：变量名简单赋值语句：变量名=表达式；表达式；串联赋值语句：变量名串联赋值语句：变量名1=1=变量
42、名变量名2=2=变量名变量名k=k=表达表达式；式；成组赋值语句：成组赋值语句：(变量名变量名1 1，变量名，变量名k)=(k)=(表达式表达式1 1，表达式，表达式k)k)；结构名结构名=结构名；结构名；结构名结构名=(=(值值1 1，值，值k)k)；变量名变量名=表达式；表达式；变量名变量名 起始下标终止下起始下标终止下标标=变量名变量名 起始下标终止下标起始下标终止下标；2022年8月3日星期三交换赋值语句：变量名交换赋值语句：变量名变量名；变量名；条件赋值语句：变量名条件赋值语句：变量名=条件表达式条件表达式?表达式表达式T T：表达：表达式式F F；(5)(5)选择语句有：选择语句有
43、：条件语句条件语句1 1：if(if(表达式表达式)语句；语句；条件语句条件语句2 2：if(if(表达式表达式)语句；语句；elseelse语句；语句；2022年8月3日星期三 开关语句：开关语句：switch(switch(表达式表达式)casecase值值1 1：语句序列：语句序列1 1；breakbreak；casecase值值n n：语句序列：语句序列n n；breakbreak；defaultdefault：语句序列：语句序列n+1n+1；(6)(6)循环语句有：循环语句有：forfor语句：语句：for(for(赋初值表达式序列；条件；修改表达赋初值表达式序列；条件；修改表达式序
44、列式序列)语句；语句；2022年8月3日星期三whilewhile语句：语句：while(while(条件条件)语句；语句；dowhiledowhile语句：语句：dodo语句序列；语句序列；while(while(条件条件)；(7)(7)结束语句有：结束语句有：函数结束语句：函数结束语句：returnreturn表达式；表达式；returnreturn；casecase结束语句：结束语句：breakbreak；异常结束语句：异常结束语句：exit(exit(异常代码异常代码)；2022年8月3日星期三(8)(8)输入和输出语句有：输入和输出语句有：输入语句：输入语句：scanfscanf(格
45、式串格式串，变量，变量1 1，变量，变量n)n)；输出语句：输出语句：printfprintf(格式串格式串，表达式，表达式1 1，表达式，表达式n)n)；(9)(9)注释：注释：单行注释：单行注释：文字序列文字序列(10)(10)基本函数有：基本函数有：求最大值：求最大值：max(max(表达式表达式1 1，表达式，表达式n)n)2022年8月3日星期三求最小值：求最小值：min(min(表达式表达式1 1，表达式，表达式n)n)求绝对值：求绝对值：abs(abs(表达式表达式)文件结束：文件结束：eofeof(文件变量文件变量)或或eofeof行结束：行结束：eolneoln(文件变量文件
46、变量)或或eolneoln(11)(11)逻辑运算约定：逻辑运算约定：与运算与运算&：对于：对于A&BA&B，当，当A A的值为的值为0 0时，不再对时，不再对B B求求值。值。或运算或运算：对于：对于ABAB，当，当A A的值为非的值为非0 0时，不再对时，不再对B B求求值。值。2022年8月3日星期三【例1-6】计算两数中的较大数，可以用类C语言描述。Status max(int a,int b)if(a=b)return(a);return(b);void main()int a=3,b=4,c;c=max(a,b);printf(The Max is%d,c);2022年8月3日星期
47、三 度量一个程序的执行时间通常有两种方法：度量一个程序的执行时间通常有两种方法：(1)(1)事前分析估算法：用数学方法直接对算法的效率进行事前分析估算法：用数学方法直接对算法的效率进行分析。要考虑以下因素：分析。要考虑以下因素：问题的规模问题的规模 编写程序时所用的程序设计语言编写程序时所用的程序设计语言 机器的速度机器的速度 算法所用的策略。算法所用的策略。1.3.21.3.2 算法的复杂度分析算法的复杂度分析1 1算法的时间复杂度算法的时间复杂度2022年8月3日星期三 (2)(2)事后统计法：计算机内部均设有计时功能，可事后统计法：计算机内部均设有计时功能，可设计一组或若干组测试数据，然
48、后分别运行根据不同设计一组或若干组测试数据，然后分别运行根据不同的算法编制的程序，并比较这些程序的实际运行时间，的算法编制的程序，并比较这些程序的实际运行时间，从而确定算法的优劣。这种方法有两个缺陷：从而确定算法的优劣。这种方法有两个缺陷：必须先运行根据算法编制的程序，这通常比较麻必须先运行根据算法编制的程序，这通常比较麻烦；烦；这种方法得出的结果往往对计算机的硬件、软件这种方法得出的结果往往对计算机的硬件、软件环境依赖性较强，有时容易掩盖算法本身的优劣。环境依赖性较强，有时容易掩盖算法本身的优劣。2022年8月3日星期三 编译程序时所产生的机器代码的质量也会对执行效编译程序时所产生的机器代码
49、的质量也会对执行效率产生影响。率产生影响。算法由控制结构和原操作构成，其执行的时间取决算法由控制结构和原操作构成，其执行的时间取决于两者的综合效果。于两者的综合效果。为了客观地比较同一问题的不同算法的优劣，通常为了客观地比较同一问题的不同算法的优劣，通常从算法中选取一种对于所研究的问题来说是基本运算的从算法中选取一种对于所研究的问题来说是基本运算的原操作，用该原操作执行的次数作为算法的时间度量。原操作，用该原操作执行的次数作为算法的时间度量。2022年8月3日星期三 一般情况下，算法中基本原操作重复执行的次数是一般情况下，算法中基本原操作重复执行的次数是问题规模问题规模n n的某个函数的某个函
50、数f(nf(n)，因而算法的时间复杂度记，因而算法的时间复杂度记作：作：T(n)=O(f(nT(n)=O(f(n)当问题的规模当问题的规模n n增大时，算法执行时间的增长率和增大时，算法执行时间的增长率和f(nf(n)的增长率相同，称为算法的渐近时间复杂度的增长率相同，称为算法的渐近时间复杂度(asymptotic time complexity)(asymptotic time complexity)，简称时间复杂度。，简称时间复杂度。2022年8月3日星期三 当当T(nT(n)与数据个数与数据个数n n无关时，无关时，T(nT(n)=O(1)=O(1)，称为常，称为常量阶；量阶；当当T(n
