《《概论线性表》PPT课件》由会员分享，可在线阅读，更多相关《《概论线性表》PPT课件（83页珍藏版）》请在金锄头文库上搜索。
1、第第1 1章章 数据结构概论数据结构概论 本章主要介绍以下内容本章主要介绍以下内容l 数据结构研究的主要内容数据结构研究的主要内容l 数据结构中涉及的基本概念数据结构中涉及的基本概念l 算法的概念、描述方法以及评价标准算法的概念、描述方法以及评价标准1.1 1.1 数据结构研究的主要内容数据结构研究的主要内容当今计算机应用的特点：当今计算机应用的特点： l l 所处理的数据量大且具有一定的关系；所处理的数据量大且具有一定的关系； 2 2 对其操作不再是单纯的数值计算，而更多地是需要对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。对其进行组织、管理和检索。 应用举例应用举例
2、1 1学籍档案管理学籍档案管理 假设一个学籍档案管理系统应包含如下表假设一个学籍档案管理系统应包含如下表1-11-1所示所示的学生信息。的学生信息。表表表表1-11-1 特点：特点： l l 每个学生的信息占据一行，所有学生的信息按学号每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；顺序依次排列构成一张表格； 2 2 表中每个学生的信息依据学号的大小存在着一种前表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；后关系，这就是我们所说的线性结构； 3 3 对它的操作通常是插入某个学生的信息，删除某个对它的操作通常是插入某个学生的信息，删除某个学生
3、的信息，更新某个学生的信息，按条件检索某个学生学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。的信息等等。 应用举例应用举例2 2输出输出n n个对象的全排列个对象的全排列 输出输出n n个对象的全排列可以使用下图个对象的全排列可以使用下图1-11-1所示的形式描述。所示的形式描述。图图 1-1 3个对象的全排列过程个对象的全排列过程特点：特点： l l在求解过程中，所处理的数据之间具有层次关系，这在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；是我们所说的树形结构； l l对它的操作有：建立树形结构，输出最低层结点内容对它的操作有：建立树形结构，输出最低层结
4、点内容等等。等等。应用举例应用举例3 3制定教学计划制定教学计划 在制定教学计划时，需要考虑各门课程的开设顺序。在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表情况如下表1-21-2所示：所示：表表1-2课程先后关系的图形描形式：课程先后关系的图形描形式：c1c9c4c2c12c10c11c5c3c6c7c8图图 1-2 计算机专业必修课程开设先后关系计算机专业必修课程开设先后关系 特点特
5、点 l l课程之间的先后关系用图结构描述；课程之间的先后关系用图结构描述； 2 2通过实施创建图结构，按要求将图结构中的顶点进行通过实施创建图结构，按要求将图结构中的顶点进行线性排序。线性排序。 结论结论 计算机的操作对象的关系更加复杂，操作形式不再是计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。要使计算机进行组织管理，我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些能够更有效地进行这些非数值性处理，就必须弄清楚这些操
6、作对象的特点，在计算机中的表示方式以及各个操作的操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是数据结构这门课程研究的主具体实现手段。这些就是数据结构这门课程研究的主要内容。要内容。1.2 1.2 基本概念和术语基本概念和术语数据数据 是对客观事物的符号表示。在计算机科学中其含义是指是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。所有能够输入到计算机中并被计算机程序处理的符号集合。数据元素数据元素 是数据集合中的一个实体，是计算机程序中加工处理的是数据集合中的一个实体，是计算机程序中加工处理的基本单位。基本单位。 数据
7、元素按其组成可分为简单型数据元素和复杂型数据数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割的最小单位；复杂型数据元素由多个数据数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。项组成，它通常携带着一个概念的多方面信息。 数据结构数据结构 简单地说，就是相互之间存在一种或多种特定关系的数简单地说，就是相互之间存在一种或多种特定关系的数据元素的集合。常见的数据结构有：线性结构、树形结构和据元素的集合。常见的数据结构有：线性结构、树形结
8、构和图形结构。图形结构。 逻辑结构逻辑结构 数据结构中所说的数据结构中所说的“关系关系”实际上是指数据元素之间的实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。逻辑关系，又称此为逻辑结构。存储结构存储结构（物理结构）（物理结构） 是指数据结构在计算机存储器中的具体实现。与孤立是指数据结构在计算机存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。辑结构。常见的存储结构常见的存储结构 顺序存储结构：特点是借助于数
9、据元素的相对存储位顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；置来表示数据元素之间的逻辑结构； 链式存储结构：特点是借助于指示数据元素地址的指链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。针表示数据元素之间的逻辑结构。1.3 1.3 算法算法 1.3.1 1.3.1 算法的概念算法的概念 算法是解决某个特定问题的一种方法或一个过程。算法是解决某个特定问题的一种方法或一个过程。 计算机对数据的操作可以分为数值性和非数值性计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；两种类型。在数值性操作中主
10、要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、而在非数值性操作中主要进行的是检索、排序、插入、删除等等。删除等等。设计算法的基本过程设计算法的基本过程 l l通过对问题进行详细地分析，抽象出相应的数学模型；通过对问题进行详细地分析，抽象出相应的数学模型； 2 2确定使用的数据结构，并在此基础上设计对此数据结确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；构实施各种操作的算法； 3 3选用某种语言将算法转换成程序；选用某种语言将算法转换成程序； 4 4调试并运行这些程序。调试并运行这些程序。算法应该具有下列五个特性算法应该具有下列五个特性（1 1）有穷性
11、：有穷性：一个算法必须在执行有穷步之后结束。一个算法必须在执行有穷步之后结束。（2 2）确定性确定性：算法中的每一步，必须有确切的含义，在他：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。人理解时不会产生二义性。（3 3）可行性可行性：算法中描述的每一步操作都可以通过已有的：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。基本操作执行有限次实现。（4 4）输入：输入：一个算法应该有零个或多个输入。一个算法应该有零个或多个输入。（5 5）输出：输出：一个算法应该有一个或多个输出。这里所说的一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。输出
12、是指与输入有某种特定关系的量。举例举例问题：按从小到大的顺序重新排列问题：按从小到大的顺序重新排列x x，y y，z z三个数值的内容。三个数值的内容。算法：算法： （1 1）输入）输入x x，y y，z z三个数值；三个数值； （2 2）从三个数值中挑选出最小者并换到）从三个数值中挑选出最小者并换到x x中；中； （3 3）从）从y y，z z中挑选出较小者并换到中挑选出较小者并换到y y中；中； （4 4）输出排序后的结果。）输出排序后的结果。 1.3.2 1.3.2 算法的描述算法的描述 选择算法描述语言的准则选择算法描述语言的准则（1 1）该语言应该具有描述数据结构和算法的基本功能；）
13、该语言应该具有描述数据结构和算法的基本功能；（2 2）该语言应该尽可能地简捷，以便于掌握、理解；）该语言应该尽可能地简捷，以便于掌握、理解；（3 3）使用该语言描述的算法应该能够比较容易地转换成任）使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。何一种程序设计语言。 “ “类类C”C”描述语言是通过对描述语言是通过对C C语言进行精心筛选保留语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展修的一个核心子集，并为了便于描述，又做了若干扩展修改，从而，增强了语言的描述功能。改，从而，增强了语言的描述功能。 1. 1. 预定义常量及类型预定义常量及类型 #defi
14、ne TRUE 1 #define TRUE 1 #define FALSE 0 #define FALSE 0 #define OK 1 #define OK 1 #define ERROR 0 #define ERROR 0 #define OVERFLOW -1 #define OVERFLOW -1 数据元素被约定为数据元素被约定为dateType dateType 类型，用户需要根据类型，用户需要根据具体情况，自行定义该数据类型。具体情况，自行定义该数据类型。2. 2. 算法描述为以下的函数形式：算法描述为以下的函数形式： 函数类型函数类型 函数名（函数参数表）函数名（函数参数表）
15、语句序列；语句序列； 为了简化函数的书写，提高算法描述的清晰度，为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给函数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可。另外，在书写算法时，应该养成出相应的注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯。对重点语句段落添加注解的良好习惯。3. 3. 在算法描述中可以使用的赋值语句形式有：在算法描述中可以使用的赋值语句形式有： 简单赋值简单赋值 变量名变量名 = = 表达式；表达式；
16、 串联赋值串联赋值 变量名变量名1 = 1 = 变量名变量名2 = . = 2 = . = 变量名变量名n = n = 表达式；表达式； 成组赋值成组赋值 （变量名（变量名1 1，.，变量名，变量名n n）= =（表达式（表达式1 1，.，表达式表达式n n）；）； 结构赋值结构赋值 结构名结构名1 = 1 = 结构名结构名2 2； 结构名结构名 = =（值（值1 1，值，值2 2，.，值，值n n）；）； 条件赋值条件赋值 变量名变量名 = = 条件表达式条件表达式 ? ? 表达式表达式1 1：表达式：表达式2 2； 交换赋值交换赋值 变量名变量名1 1 变量名变量名2 2；4. 4. 在算法描述中可以使用的选择结构语句形式有：在算法描述中可以使用的选择结构语句形式有：条件语句条件语句1 if 1 if （表达式）（表达式） 语句；语句；条件语句条件语句2 if 2 if （表达式）（表达式） 语句；语句； else else 语句；语句；开关语句开关语句1 switch 1 switch （表达式）（表达式） case case 值值1 1：语句序列：语句序列1 1；breakbr
