数据结构(C语言版本)课件

数据结构（C语言版本）严蔚敏 吴伟民 编著8/6/2024华侨大学数学系 黄建新 数据结构（C语言版本）7/29/2023华侨大学1前前 言言 o二十一世纪是科学技术高速发展的信息时代，而计算机是处理信息的主要工具，因此，人们已经认识到，计算机知识已成为人类当代文化的一个重要组成部分。o 计算机科学技术以惊人的速度向前发展，它的广泛应用已从传统的数数值值计计算算领域发展到各种非非数数值值计计算算领域。在非数值计算领域里，数据处理的对象已从简单的数值发展到一般的符号，进而发展到具有一定结构的数据。在这里，面临的主要问题是：针对每一种新的应用领域的处理对象，如何选择合适的数据表示（结构），如何有效地组织计算机存贮，并在此基础上又如何有效地实现对象之间的“运算”关系。传统的解决数值计算的许多理论、方法和技术已不能满足解决非数值计算问题的需要，必须进行新的探索。数据结构就是研究和解决这些问题的重要基础理论。因此，“数据结构”课程已成为计算机类专业的一门重要专业基础课。8/6/2024华侨大学数学系 黄建新前 言 7/29/2023华侨大学数学系2 第1章 绪论 目的目的 介绍数据结构中常用的基本概念和术语以及学习数据结构的意介绍数据结构中常用的基本概念和术语以及学习数据结构的意 义。义。要求要求 了解本章介绍的各种基本概念和术语，掌握算法描述和分析的了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方方 法。法。重点重点 了解数据结构的逻辑结构、存储结构及数据的运算三方面的概了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念念 及相互关系。及相互关系。难点难点 算法复杂度的分析方法。算法复杂度的分析方法。8/6/2024华侨大学数学系 黄建新 第1章 绪论目的 介绍数据结构中常用的基31.1 引言 众众所所周周知知，二二十十世世纪纪四四十十年年代代，电电子子数数字字计计算算机机问问世世的的直直接接原原因因是是解解决决弹弹道道学学的的计计算算问问题题。早早期期，电电子子计计算算机机的的应应用用范范围围，几几乎乎只只局局限限于于科科学学和和工工程程的的计计算算，其其处处理理的的对对象象是是纯纯数数值值性性的的信信息息，通通常常，人人们们把把这类问题称为这类问题称为数值计算数值计算数值计算数值计算。近近三三十十年年来来，电电子子计计算算机机的的发发展展异异常常迅迅猛猛，这这不不仅仅表表现现在在计计算算机机本本身身运运算算速速度度不不断断提提高高、信信息息存存储储量量日日益益扩扩大大、价价格格逐逐步步下下降降，更更重重要要的的是是计计算算机机广广泛泛地地应应用用于于情情报报检检索索、企企业业管管理理、系系统统工工程程等等方方面面，已已远远远远超超出出了了科科技技计计算算的的范范围围，而而渗渗透透到到人人类类社社会会活活动动的的一一切切领领域域。与与此此相相应应，计计计计算算算算机机机机的的的的处处处处理理理理对对对对象象象象也也也也从从从从简简简简单单单单的的的的纯纯纯纯数数数数值值值值性性性性信信信信息息息息发发发发展展展展到到到到非非非非数数数数值值值值性性性性的的的的和具有一定结构的信息和具有一定结构的信息和具有一定结构的信息和具有一定结构的信息。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新1.1 引言 7/29/2023华侨大学数学系 黄建新4 4o 因此，再把电子数字计算机简单地看作是进行数值计算的工具，把数据仅理解为纯数值性的信息，就显得太狭隘了。现代计算机科学的观点，是把把计计算算机机程程序序处处理理的的一一切切数数值值的的、非非数数值值的的信信息息，乃乃至至程程序序统统称称为为数数据据（Data），而电子计算机则是加工处理数据（信息）的工具。o由于数据的表示方法和组织形式直接关系到程序对数据的处理效率，而系统程序和许多应用程序的规模很大，结构相当复杂，处理对象又多为非数值性数据。因此，单凭程序设计人员的经验和技巧已难以设计出效率高、可靠性强的程序。于是，就要求人们对计算机程序加工的对象进行系统的研究，即研究数据的特性以及数据之间存研究数据的特性以及数据之间存在的关系在的关系数据结构（数据结构（Date Structure）。8/6/2024华侨大学数学系 黄建新7/29/2023华侨大学数学系 黄建新51.2 数据结构的发展简史及其在计算机科学中所处的地位发展史：发展史：1 1、“数据结构数据结构”作为一门独立的课程在国外是从作为一门独立的课程在国外是从19681968年才开始设年才开始设立的。立的。2 2、1968 1968年美国唐年美国唐 欧欧 克努特教授开创了数据结构的最初体系，克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新1.2 数据结构的发展简史及其在计算机科学中所处的地位7/6 6地位：地位：1.“数据结构数据结构”在计算机科学中是一门综合性的专业在计算机科学中是一门综合性的专业基础课。基础课。2.数据结构是介于数学、计算机硬件和计算机软件三数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。者之间的一门核心课程。3.数数据据结结构构这这一一门门课课的的内内容容不不仅仅是是一一般般程程序序设设计计（特特别别是是非非数数值值性性程程序序设设计计）的的基基础础，而而且且是是设设计计和和实实现现编编译译程程序序、操操作作系系统统、数数据据库库系系统统及及其其他他系系统统程程序的重要基础。序的重要基础。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新地位：7/29/2023华侨大学数学系 黄建新7 71.3 什么是数据结构 计算机解决一个具体问题时，大致需要经过下列几个步骤：首先计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（数学模型的算法（AlgorithmAlgorithm），最后编出程序、进行测试、调整），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。的语言加以描述。计计计计算算算算机机机机算算算算法法法法与与与与数数数数据据据据的的的的结结结结构构构构密密密密切切切切相相相相关关关关，算算算算法法法法无无无无不不不不依依依依附附附附于于于于具具具具体体体体的的的的数数数数据据据据结构，数据结构直接关系到算法的选择和效率。结构，数据结构直接关系到算法的选择和效率。结构，数据结构直接关系到算法的选择和效率。结构，数据结构直接关系到算法的选择和效率。运运算算是是由由计计算算机机来来完完成成，这这就就要要设设计计相相应应的的插插入入、删删除除和和修修改改的的算算法法 。也也就就是是说说，数数据据结结构构还还需需要要给给出出每每种种结结构构类类型型所所定定义义的的各各种运算的算法。种运算的算法。直直观观定定义义：数数数数据据据据结结结结构构构构是是是是研研研研究究究究程程程程序序序序设设设设计计计计中中中中计计计计算算算算机机机机操操操操作作作作的的的的对对对对象象象象以以以以及及及及它它它它们之间的关系和运算的一门学科们之间的关系和运算的一门学科们之间的关系和运算的一门学科们之间的关系和运算的一门学科。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新1.3 什么是数据结构7/29/2023华侨大学数学系8 81.4 基本概念和术语 1 1数据数据 数据是人们利用文字符号、数字符号以及其他规定的符号对数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。例如，一个个人书库管息，包括文字、表格、图象等，都称为数据。例如，一个个人书库管理程序所要处理的数据可能是一张如理程序所要处理的数据可能是一张如表表1-11-1所示的表格。所示的表格。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新1.4 基本概念和术语 7/29/2023华侨大学数学系 9 9 表 1-1 个人书库8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新 10102 2结点结点 结结结结点点点点也也也也叫叫叫叫数数数数据据据据元元元元素素素素，它它它它是是是是组组组组成成成成数数数数据据据据的的的的基基基基本本本本单单单单位位位位。在在程程序序中中通通常常把把结结点点作作为为一一个个整整体体进进行行考考虑虑和和处处理理。例例如如，在在表表1-11-1所所示示的的个个人人书书库库中中，为为了了便便于于处处理理，把把其其中中的的每每一一行行（代代表表一一本本书书）作作为为一一个个基本单位来考虑，故该数据由基本单位来考虑，故该数据由1010个结点构成。个结点构成。一一般般情情况况下下，一一个个结结点点中中含含有有若若干干个个字字段段（也也叫叫数数据据项项）。例例如如，在在表表1-11-1所所示示的的表表格格数数据据中中，每每个个结结点点都都有有登登录录号号、书书号号、书书名名、作作者者、出出版版社社和和价价格格等等六六个个字字段段构构成成。字字字字段段段段是是是是构构构构成成成成数数数数据据据据的的的的最最最最小小小小单单单单位。位。位。位。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新7/29/2023华侨大学数学系 黄建新11113 3逻辑结构逻辑结构逻辑结构逻辑结构 结点和结点之间的逻辑关系称为数据的逻辑结构结点和结点之间的逻辑关系称为数据的逻辑结构结点和结点之间的逻辑关系称为数据的逻辑结构结点和结点之间的逻辑关系称为数据的逻辑结构。在在表表1-11-1所所示示的的表表格格数数据据中中，各各结结点点之之间间在在逻逻辑辑上上有有一一种种线线性性关关系系，它它指指出出了了1010个个结结点点在在表表中中的的排排列列顺顺序序。根根据据这这种种线线性性关关系系，可可以以看出表中第一本书是什么书，第二本书是什么书，等等。看出表中第一本书是什么书，第二本书是什么书，等等。4 4存储结构存储结构存储结构存储结构 数据在计算机中的存储表示称为数据的存储结构数据在计算机中的存储表示称为数据的存储结构数据在计算机中的存储表示称为数据的存储结构数据在计算机中的存储表示称为数据的存储结构。在在表表1-11-1所所示示的的表表格格数数据据在在计计算算机机中中可可以以有有多多种种存存储储表表示示，例例如如，可可以以表表示示成成数数组组，存存放放在在内内存存中中；也也可可以以表表示示成成文文件件，存存放放在在磁磁盘上，等等。盘上，等等。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新7/29/2023华侨大学数学系 黄建新12125数据处理 数数据据处处理理是是指指对对数数据据进进行行查查找找、插插入入、删删除除、合合并并、排排序序、统统计计以以及及简简单单计计算算等等的的操操作作过过程程。在在早早期期，计计算算机机主主要要用用于于科科学学和和工工程程计计算算，进进入入八八十十年年代代以以后后，计计算算机机主主要要用用于于数数据据处处理理。据据有有关关统统计计资资料料表表明明，现现在在计计算算机机用用于于数数据据处处理理的的时时间间比比例例达达到到80%80%以以上上，随随着着时时间间的的推推移移和和计计算算机机应应用用的的进进一一步步普普及及，计计算算机机用用于于数数据处理的时间比例必将进一步增大。据处理的时间比例必将进一步增大。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新7/29/2023华侨大学数学系 黄建新13136 6数据结构数据结构数据结构数据结构（Data StructureData Structure）数数据据结结构构是是研研究究数数据据元元素素（Data Data ElementElement）之之间间抽抽象象化化的的相相互互关关系系和和这这种种关关系系在在计计算算机机中中的的存存储储表表示示（即即所所谓谓数数据据的的逻逻辑辑结结构构和和物物理理结结构构），并并对对这这种种结结构构定定义义相相适适应应的的运运算算，设设计计出出相相应应的的算算法法，而而且且确确保保经经过过这这些些运运算算后后所所得得到到的的新新结结构构仍仍然然是是原原来来的的结结构构类型。类型。为为了了叙叙述述上上的的方方便便和和避避免免产产生生混混淆淆，通通常常我我们们把把数数据据的的逻逻辑辑结结构构统统称称为为数数据据结结构构，把把数数据据的的物物理理结结构构统统称称为为存存储储结结构构（Storage Storage StructureStructure）。）。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新6数据结构（Data Structure）7/29/2021414o四种基本基本结构：（1）集合：结构中的数据元素之间除了“同属于一个集合”的关 系外，别无其他关系。（2）线性结构线性结构：结构中的数据元素之间存在一个对一个的关系。如：图书馆的书目检索系统 （3）树形结构树形结构：结构中的数据元素存在一个对多个的关系。如：计算机和人对奕问题 工厂的组织管理 （4）图状结构图状结构：结构中的数据元素存在多个对多个的关系。如：多叉路口的交通灯管理问题 最短路径问题 同一个逻辑结构可以有不同的内部存储结构；反之，数据的存同一个逻辑结构可以有不同的内部存储结构；反之，数据的存储结构一定要映像数据之间的逻辑关系储结构一定要映像数据之间的逻辑关系。数据结构的形式定义：数据结构是一个二元组 data_structure=(D,S)其中：D是数据元素的有限集，S是D上关系的有限集。8/6/2024华侨大学数学系 黄建新四种基本基本结构：7/29/2023华侨大学数学系 黄建新15例1 一种结构 lineority=(K,R）K=k1,k2,k3,k4,k5,k6,k7 R=r r=,则有：k3-k1-k5-k6-k4-k2-k7 一种线性结构例2 tree=(K,R)K=01,02,03,04,05,06,07,08 R=r r=,树形结构 8/6/2024华侨大学数学系 黄建新例1 一种结构 lineority=(K,R）7/29/216 例3 graph=(K,R)K=01,02,03,04,05,06 R=r r=,图形结构 数据的逻辑结构分类：数据的逻辑结构 线性结构 非线性结构 线性表 树形结构 图 一般线性表 特殊线性表 线性表推广 树 二叉树 有向图 无向图 线性表 栈 队列 串 数组 广义表 8/6/2024华侨大学数学系 黄建新 例3 graph=(K,R)7/29/2023华侨大学17 数据的物理结构方面 二种类型：顺序存储结构和非顺序存储结构 顺序存储结构顺序存储结构：逻辑上相邻的数据元素存储在物理位置上相比邻 的存储单元里，其关系由存储单元的邻接关系来 体现（向量、数组）。非顺序存储结构非顺序存储结构：数据元素在计算机内任意位置上存放，其关系 用指针来链接，称为链式存储结构-链表。按指针个数分为：单链表、双向链表、多重链表 索引存储结构索引存储结构：按（地址关键字）的偶对集合，关键字是唯一标 识结点；地址指出该结点的存储地址。散列存储结构散列存储结构：根据结点关键字来直接算出该结点的存储地址。8/6/2024华侨大学数学系 黄建新 数据的物理结构方面7/29/2023华侨大学数学系 黄187 7数据类型数据类型 数数据据类类型型是是一一个个值值的的集集合合和和定定义义在在这这个个值值上上的的一一组组操操作作的的总总称称。数数据据类类型型是是高高级级程程序序设设计计语语言言中中的的一一个个基基本本概概念念，它它和和数数据据结结构构的的概概念念密密切相关。切相关。一一方方面面，在在程程序序设设计计语语言言中中，每每一一个个数数据据都都属属于于某某种种数数据据类类型型。类类型型明明显显或或隐隐含含地地规规定定了了数数据据的的取取值值范范围围、存存储储方方式式以以及及允允许许进进行行的的运运算算。可以认为，数据类型是在程序设计中已经实现了的数据结构。可以认为，数据类型是在程序设计中已经实现了的数据结构。另另一一方方面面，在在程程序序设设计计过过程程中中，当当需需要要引引入入某某种种新新的的数数据据结结构构时时，总总是借助编程语言所提供的数据类型来描述数据的存储结构。是借助编程语言所提供的数据类型来描述数据的存储结构。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新7数据类型7/29/2023华侨大学数学系 黄建新1919 抽象数据类型（Abstract Data Type,ADT)是指一个数学模型以及定义在该模型上的一组操作，它仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。一个含抽象数据类型的软件模块通常应包含定义、表示和实现三个部分。抽象数据类型的三元组表示 (D S P),其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT抽象数据类型名 数据对象：数据关系：基本操作：ADT抽象数据类型名 其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：基本操作名（参数表）初始条件：操作结果：8/6/2024华侨大学数学系 黄建新 抽象数据类型（Abstract Data 20 基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。例 抽象数据类型三元组的定义：ADT Triplet 数据对象：D=e1,e2,e3|e1,e2,e3属于Elemset 数据关系：R1=,基本操作：InitTriplet(&T,v1,v2,v3)操作结果：构造了三元组T,元素e1,e2,和e3分别被赋以 参数v1,v2和v3的值。DestroyTriplet(&T)操作结果：三元组T被销毁。Get（T,I,&e)初始条件：三元组T已存在，1=I=3 操作结果：用e返回T的第I元的值。8/6/2024华侨大学数学系 黄建新 基本操作有两种参数：赋值参数只为操作提供输入值；引用参21 8 8算法算法 简单地说就是解决特定问题的方法（关于算法的严格定义，在此简单地说就是解决特定问题的方法（关于算法的严格定义，在此不作讨论）。特定的问题可以是数值的，也可以是非数值的。不作讨论）。特定的问题可以是数值的，也可以是非数值的。解决数值问题的算法叫做数值算法，科学和工程计算方面的算法解决数值问题的算法叫做数值算法，科学和工程计算方面的算法都属于数值算法，如求解数值积分，求解线性方程组、求解代数都属于数值算法，如求解数值积分，求解线性方程组、求解代数方程、求解微分方程等。方程、求解微分方程等。解决非数值问题的算法叫做非数值算法，数据处理方面的算法都解决非数值问题的算法叫做非数值算法，数据处理方面的算法都属于非数值算法。例如各种排序算法、查找算法、插入算法、删属于非数值算法。例如各种排序算法、查找算法、插入算法、删除算法、遍历算法等。除算法、遍历算法等。数值算法和非数值算法并没有严格的区别。数值算法和非数值算法并没有严格的区别。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新 8算法 7/29/2023华侨大学数学系 黄建新2222 一般说来，在数值算法中主要进行算术运算，而在非数值算法中一般说来，在数值算法中主要进行算术运算，而在非数值算法中主要进行比较和逻辑运算。另一方面，特定的问题可能是递归的，主要进行比较和逻辑运算。另一方面，特定的问题可能是递归的，也可能是非递归的，因而解决它们的算法就有也可能是非递归的，因而解决它们的算法就有递归算法和非递归递归算法和非递归算法算法之分。从理论上讲，任何递归算法都可以通过循环，堆栈等之分。从理论上讲，任何递归算法都可以通过循环，堆栈等技术转化为非递归算法。技术转化为非递归算法。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新7/29/2023华侨大学数学系 黄建新23231.5 算法和算法的描述算法和算法的描述1.5.1 1.5.1 算法算法算法是执行特定计算的有穷过程。这个过程有算法是执行特定计算的有穷过程。这个过程有5 5个特点：个特点：1.1.动态有穷：当执行一个算法时，不论是何种情况，在经过了动态有穷：当执行一个算法时，不论是何种情况，在经过了 有限步骤后，这个算法一定要终止。有限步骤后，这个算法一定要终止。2.2.确定性：算法中的每条指令都必须是清楚的，指令无二义性。确定性：算法中的每条指令都必须是清楚的，指令无二义性。3.3.输入：具有输入：具有0 0个或个或0 0个以上由外界提供的量。个以上由外界提供的量。4.4.输出：产生输出：产生1 1个或多个结果。个或多个结果。5.5.可行性：每条指令都充分基本，原则上可由人仅用笔和纸在可行性：每条指令都充分基本，原则上可由人仅用笔和纸在 有限的时间内也能完成。有限的时间内也能完成。注意：算法和程序是有区别的，即程序未必能满足动态有穷注意：算法和程序是有区别的，即程序未必能满足动态有穷。在本在本 书书中中，我我们们只只讨讨论论满满足足动动态态有有穷穷的的程程序序，因因此此“算算法法”和和“程程 序序”是通用的。是通用的。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新1.5 算法和算法的描述1.5.1 算法7/29/2024241.5.2 1.5.2 算法的描述算法的描述 一一个个算算法法可可以以用用自自然然语语言言、数数字字语语言言或或约约定定的的符符号号来来描描述述，也也可可以以用用计计算算机机高高级级程程序序语语言言来来描描述述，如如PascalPascal语语言言、C C语语言言或或伪伪代代码码等等。本本书书选用选用C C语言作为描述算法的工具。现简单说明语言作为描述算法的工具。现简单说明C C语言的语法结构如下：语言的语法结构如下：8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新1.5.2 算法的描述 7/29/2023华侨大学数学2525 1 1预定义常量和类型：预定义常量和类型：#define TRUE 1#define TRUE 1；#define FALSE -1#define FALSE -1；#define ERROR NULL#define ERROR NULL；8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新7/29/2023华侨大学数学系 黄建新26262 2函数的形式函数的形式 数据类型数据类型 函数名函数名 （形式参数形式参数）形式参数说明；形式参数说明；内部数据说明；内部数据说明；执行语句组；执行语句组；/*/*函数名函数名*/*/函数的定义主要由函数名和函数体组成，函数体用花括号函数的定义主要由函数名和函数体组成，函数体用花括号“”和和“”“”括起来。函数中用方括号括起来的部分为可选项，函括起来。函数中用方括号括起来的部分为可选项，函数名之间的圆括号不可省略。函数的结果可由指针或别的方式传数名之间的圆括号不可省略。函数的结果可由指针或别的方式传递到函数之外。执行语句可由各种类型的语句所组成，两个语句递到函数之外。执行语句可由各种类型的语句所组成，两个语句之间用之间用“；”号分隔。可将函数中的表达式的值通过号分隔。可将函数中的表达式的值通过returnreturn语句语句返回给调用它的函数。最后的花括号返回给调用它的函数。最后的花括号“”“”之后的之后的/*/*函数名函数名*/*/为注为注释部分，可舍。释部分，可舍。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新2函数的形式7/29/2023华侨大学数学系 黄建新27273赋值语句简单赋值：简单赋值：变量名变量名=表达式，它表示将表达式的值赋给左边表达式，它表示将表达式的值赋给左边的变量；的变量；变量变量+，它表示变量加，它表示变量加1 1后赋值给变后赋值给变量；量；变量变量-，它表示变量减，它表示变量减1 1后赋值给变量；后赋值给变量；8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新3赋值语句7/29/2023华侨大学数学系 黄建新2828成组赋值：成组赋值：1.1.（变变量量1 1，变变量量2 2，变变量量3 3，变变量量k k）=（表表达达式式1 1，表达式，表达式2 2，表达式，表达式3 3，表达式表达式k k）；）；2.2.数组名数组名1 1 下标下标11下标下标2=2=数组名数组名2 2 下标下标11下标下标228/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新7/29/2023华侨大学数学系 黄建新2929串联赋值：串联赋值：变量变量1 1=变量变量2 2=变量变量3 3=变量变量k k=表达式；表达式；条件赋值：条件赋值：变量名变量名=条件表达式？表达式条件表达式？表达式1 1：表达式：表达式2 2；交换赋值：交换赋值：变量变量1 1变量变量2 2，表示变量，表示变量1 1和变量和变量2 2互换；互换；8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新串联赋值：7/29/2023华侨大学数学系 黄建新30304 4条件选择语句条件选择语句if if （表达式）（表达式）语句；语句；if if （表达式）（表达式）语句语句1 1；else else 语句语句2 2；情况语句；情况语句 switch switch （表达式）（表达式）case case 判判断断值值1 1；语语句句组组1 1；break break；case case 判判断断值值2 2；语语句句组组2 2；break break；case case 判断值判断值n n；语句组；语句组n n；break break；default default：语句组；：语句组；break break；注注意意：switch switch casecase语语句句是是先先计计算算表表达达式式的的值值，然然后后用用其其值值与与判判断断值值相相比比较较，若若它它们们相相 一一 致致 时时，就就 执执 行行 相相 应应 的的casecase下下的的语语句句组组；若若不不一一致致，则则执执行行defaultdefault下下的的语语句句组组；其中的方括号代表可选项。其中的方括号代表可选项。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新4条件选择语句7/29/2023华侨大学数学系 黄建新31315 5循环语句循环语句 for for语句语句 for for（表达式（表达式1 1；表达式；表达式2 2；表达式；表达式3 3）循环体语句；循环体语句；首先计算表达式首先计算表达式1 1的值，然后求表达式的值，然后求表达式2 2的值，若结果非零则执行的值，若结果非零则执行循环体语句，最后对表达式循环体语句，最后对表达式3 3运算，如此循环，直到表达式运算，如此循环，直到表达式2 2的值的值为零时止。为零时止。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新5循环语句7/29/2023华侨大学数学系 黄建新32321.while while语句语句 while while（条件表达式）（条件表达式）循环体语句；循环体语句；whilewhile循循环环首首先先计计算算条条件件表表达达式式的的值值，若若条条件件表表达达式式的的值值非非零零，则则执执行行循循环环体体语语句句，然然后后再再次次计计算算条条件件表表达达式式，重重复复执执行行，直直到条件表达式的值为假时退出循环，执行该循环之后的语句。到条件表达式的值为假时退出循环，执行该循环之后的语句。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新7/29/2023华侨大学数学系 黄建新3333 do-while do-while语句语句 do do 循环体语句循环体语句 while while（条件表达式）（条件表达式）该该循循环环语语句句首首先先执执行行循循环环体体语语句句。然然后后再再计计算算条条件件表表达达式式的的值值，若若条条件件表表达达式式成成立立，则则再再次次执执行行循循环环体体，再再计计算算条条件件表表达达式式的的值值，直直到到条条件表达式的值为零，即条件不成立时结束循环。件表达式的值为零，即条件不成立时结束循环。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新 do-while语句7/29/2023华侨大学数学系 34346 6输入、输出语句输入、输出语句 输输入入语语句句：用用函函数数scanfscanf实实现现，特特别别当当数数据据为为字字符符时时，用用getchargetchar函数实现。函数实现。输输出出语语句句：用用printfprintf函函数数实实现现，当当要要输输出出字字符符数数据据时时，用用putcharputchar函数实现。函数实现。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新7/29/2023华侨大学数学系 黄建新35357其他一些语句（1 1）returnreturn表达式或表达式或returnreturn：用于函数结束。：用于函数结束。（2 2）breakbreak语语句句：可可用用在在循循环环语语句句或或casecase语语句句中中结结束束循循环环过过程程或或跳跳出情况语句。出情况语句。（3 3）exitexit语句：表示出现异常情况时，控制退出语句。语句：表示出现异常情况时，控制退出语句。8注释形式 可用可用/*/*字符串字符串*/*/或者或者 单行注释单行注释 或或/文字序列。文字序列。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新7其他一些语句7/29/2023华侨大学数学系 黄建新36369 9一些基本的函数一些基本的函数如：如：max max函数，用于求一个或几个表达式中的最大值；函数，用于求一个或几个表达式中的最大值；min min函数，用于求一个或几个表达式中的最小值；函数，用于求一个或几个表达式中的最小值；abs abs函数，用于求表达式的绝对值；函数，用于求表达式的绝对值；eof eof函数，用于判定文件是否结束；函数，用于判定文件是否结束；eoln eoln函数，用于判断文本行是否结束。函数，用于判断文本行是否结束。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新7/29/2023华侨大学数学系 黄建新3737例例 计计算算f=1f=1！+2+2！+3+3！+n+n！，用，用C C语言描述。语言描述。void factorsumvoid factorsum（n n）int n int n；int iint i，j j；int fint f，w w；f=0 f=0；for for（i=1i=1，i i=n=n；i+i+）w=1 w=1；for for（j=1j=1，j j=i=i；j+j+）w=w*j w=w*j；f=f+w f=f+w；return return；上上述述算算法法所所用用到到的的运运算算有有乘乘法法、加加法法、赋赋值值和和比比较较，其其基基本本运运算算为为乘乘法法操操作作。在在上上述述算算法法的的执执行行过过程程中中，对对外外循循环环变变量量i i的的每每次次取取值值，内内循循环环变变量量j j循循环环i i次次。因因为为内内循循环环每每执执行行一一次次，内内循循环环体体语语句句w=w*jw=w*j只只作作一一次次乘乘法法操操作作，即即当当内内循循环环变变量量j j循循环环i i次次时时，内内循循环环体体的的语语句句w=w*jw=w*j作作i i次次乘乘法法。所所以以，整整个个算算法法所所作作的的 乘乘 法法 操操 作作 总总 数数 是是：f f（n n）=1+2+3+n=n=1+2+3+n=n（n-n-1 1）/2/2。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新例 计算f=1！+2！+3！+n！，用C语言描述。7/38381.5.3 算法评价 设计一个好的算法应考虑以下几个方面：设计一个好的算法应考虑以下几个方面：8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新7/29/2023华侨大学数学系 黄建新3939 1 1正确性正确性 “正确正确”的含义在通常的用法中有很大的含义在通常的用法中有很大的差别，大体可分为以下四个层次：的差别，大体可分为以下四个层次：程序不程序不含语法错误；含语法错误；程序对于几组输入数据能够得程序对于几组输入数据能够得出满足规格说明要求的结果；出满足规格说明要求的结果；程序对于精心程序对于精心选择的典型、苛刻而带有刁难性的几组数据能选择的典型、苛刻而带有刁难性的几组数据能够得出满足规格说明要求的结果；够得出满足规格说明要求的结果；程序对一程序对一切合法的输入数据都能产生满足规格说明要求切合法的输入数据都能产生满足规格说明要求的结果的结果。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新 1正确性7/29/2023华侨大学数学系 黄建40402 2运行时间运行时间 运运行行时时间间是是指指一一个个算算法法在在计计算算机机上上运运算算所所花花费费的的时时间间。它它大大致致等等于于计计算算机机执执行行一一种种简简单单操操作作（如如赋赋值值操操作作、转转向向操操作作、比比较较操操作作等等）所需要的时间与算法中进行简单操作次数的乘积。等等）所需要的时间与算法中进行简单操作次数的乘积。通通常常把把算算法法中中包包含含简简单单操操作作次次数数的的多多少少叫叫做做算算法法的的时时间间复复杂杂性性，它是一个算法运行时间的相对量度。它是一个算法运行时间的相对量度。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新7/29/2023华侨大学数学系 黄建新41413 3占用的存储空间占用的存储空间 一个算法在计算机存储器上所占用的存储空间，包括存储算法本一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入、输出数据所占用的存储空间身所占用的存储空间，算法的输入、输出数据所占用的存储空间 和算法运行过程中临时占用的存储空间。和算法运行过程中临时占用的存储空间。分析一个算法所占用的存储空间要从各方面综合考虑。分析一个算法所占用的存储空间要从各方面综合考虑。算法在运行过程中所占用的存储空间的大小被定义为算法的空间算法在运行过程中所占用的存储空间的大小被定义为算法的空间复杂性。它包括局部变量所占用的存储空间和系统为了实现递归复杂性。它包括局部变量所占用的存储空间和系统为了实现递归所使用的堆栈这两个部分。算法的空间复杂性一般以数量级的形所使用的堆栈这两个部分。算法的空间复杂性一般以数量级的形式给出。式给出。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新3占用的存储空间7/29/2023华侨大学数学系 黄建新42424 4简单性简单性 最最简简单单和和最最直直接接的的算算法法往往往往不不是是最最有有效效的的，但但算算法法的的简简单单性性使使得得证证明明其其正正确确性性比比较较容容易易，同同时时便便于于编编写写、修修改改、阅阅读读和和调调试试，所所以以还还是是应应当当强强调调和和不不容容忽忽视视的的。不不过过对对于于那那些些需需要要经经常常使使用用的的算算法法来来说说，高高效效率（即尽量减少运行时间和压缩存储空间）比简单性更为重要。率（即尽量减少运行时间和压缩存储空间）比简单性更为重要。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新7/29/2023华侨大学数学系 黄建新43431.5.4 1.5.4 算法效率的度量算法效率的度量 1 1、时间复杂度、时间复杂度 算法时间的量度算法时间的量度T(n)=T(n)=算法中基本操作重复执行的次数。算法中基本操作重复执行的次数。一般情况下，一般情况下，T(n)T(n)是问题规模是问题规模n n的某个函数的某个函数f(n)f(n)，记作：，记作：T(n)=O(f(n)T(n)=O(f(n)它表示随问题规模它表示随问题规模n n的增大，算法执行时间的增长率和的增大，算法执行时间的增长率和f(n)f(n)的增长的增长率相同，称作时间复杂度。率相同，称作时间复杂度。例1:+x;s=0;时间复杂度O(1)例2:forI=1;I=n;+I+x;s+=x;时间复杂度为O(n)例3：for(j=1;j=n;+j)for(k=1;k=n;+k)+x;s+=x;时间复杂度为O(n2)8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新1.5.4 算法效率的度量例1:+x;s=0;4444例例4 for(I=2;I=n;+I)4 for(I=2;I=n;+I)for(j=2;j=I-1;+j)+x;aIj=x;for(j=2;j=1&change;-I)for(I=n-1,change=TRUE;I=1&change;-I)change=FALSE;change=FALSE;for(j=0;jI;+j)for(j=0;jaj+1)aj if(ajaj+1)ajaj+1;change=TRUE;aj+1;change=TRUE;8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新例4 for(I=2;I=(y+1)*(y+1)y+;while(x=(y+1)*(y+1)y+;(2)void func(int n)(2)void func(int n)int i=1;k=100;int i=1;k=100;while(In)k+;i+=2;while(In)k+;i+=2;(3)void func(int n)(3)void func(int n)int i=0,s=0;int i=0,s=0;while(sn)i+;s=s+i;while(sn)i+;s=s+i;2 2、在以下逻辑结构中，一个结点可能有多个直接后继结点的是、在以下逻辑结构中，一个结点可能有多个直接后继结点的是 A.A.线性结构线性结构 B.B.树形结构树形结构 C.C.图形结构图形结构3 3、在以下逻辑结构中，只有一个开始结点的有、在以下逻辑结构中，只有一个开始结点的有 ；可能有多个终端；可能有多个终端结点的有结点的有 。A.A.线性结构线性结构 B.B.树形结构树形结构 C.C.图形结构图形结构8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新练习题7/29/2023华侨大学数学系 黄建新51514 4、数据结构包括的三个方面的内容分别是：、数据结构包括的三个方面的内容分别是：A.A.线性结构线性结构 B.B.逻辑结构逻辑结构 C.C.顺序结构顺序结构 D.D.存储结构存储结构 E.E.查找运算查找运算 F.F.数据运算数据运算5 5、以下属于数据的存储结构的是：、以下属于数据的存储结构的是：A.A.二叉树二叉树 B.B.索引索引 C.C.散列散列 D.D.线性表线性表8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新4、数据结构包括的三个方面的内容分别是：7/29/2023华5252答案：答案：1 1、解、解：(1)(1)设设whilewhile语句的执行频度为语句的执行频度为T(n)T(n)，显然有，显然有 ;即即 ，所以算法的时间复杂度，所以算法的时间复杂度为为 （2 2）设）设whilewhile循环语句执行的次数为循环语句执行的次数为m,im,i从从1 1开始递增，最后取开始递增，最后取值为值为1+2m1+2m，有，有i=1+2mn,i=1+2mn,即即m(n-1)/2=O(n)m(n-1)/2=O(n)，所以该算法的时，所以该算法的时间复杂度为间复杂度为O(n)O(n)。（3 3）对于）对于whilewhile循环语句，设执行的次数为循环语句，设执行的次数为m,Im,I从从0 0开始递增开始递增1 1，直到直到mm为止，即为止，即s=)+1+2+m-1=m(m-1)/2s=)+1+2+m-1=m(m-1)/2，并满足，并满足s=m(m-s=m(m-1)/2n1)/2n，则有，则有 ,，所以该算法的时间复杂度为，所以该算法的时间复杂度为 。8/6/20248/6/2024华侨大学数学系华侨大学数学系 黄建新黄建新答案：7/29/2023华侨大学数学系 黄建新5353