第1章数据结构基础概论课件

第1章

数据结构基础概论本章主要介绍以下内容数据结构研究的主要内容数据结构中涉及的基本概念算法的概念、描述方法以及评价标准数据结构研究的主要内容基本概念和术语算法1.1

数据结构研究的主要内容当今计算机应用的特点：所处理的数据量大且具有一定的关系；对其操作不再是单纯的数值计算，而更多的是需要对其进行组织、管理和检索。应用举例1——学籍档案管理假设一个学籍档案管理系统应包含如下表1-1所示的学生信息。表1-1图1-13个对象的全排列过程特点：在求解过程中，所处理的数据之间具有层次关系，这是我们所说的树形结构；对它的操作有：建立树形结构，输出最低层结点内容等等。应用举例3——制定教学计划在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表1-2所示：课程先后关系的图形描形式：c1c9c4c2c10c5c3c12c6c7c8c11图1-2计算机专业必修课程开设先后关系特点课程之间的先后关系用图结构描述；通过实施创建图结构，按要求将图结构中的顶点进行线性排序。结论计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是《数据结构》这门课程研究的主要内容。1.2

基本概念和术语数据是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。数据元素是数据集合中的一个实体，是计算机程序中加工处理的基本单位。数据元素按其组成可分为简单型数据元素和复杂型数据元素。简单型数据元素由一个数据项组成，所谓数据项就是数据中不可再分割的最小单位；复杂型数据元素由多个数据项组成，它通常携带着一个概念的多方面信息。数据结构简单地说，就是相互之间存在一种或多种特定关

系的数据元素的集合。常见的数据结构有：线性结构、树形结构和图形结构。逻辑结构数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。存储结构（物理结构）是指数据结构在计算机存储器中的具体实现。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。常见的存储结构顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。1.3

算法1.3.1

算法的概念算法是解决某个特定问题的一种方法或一个过程。计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。算法应该具有下列五个特性有穷性：一个算法必须在执行有穷步之后结束。确定性：算法中的每一步，必须有确切的含义，在他人理解时不会产生二义性。可行性：算法中描述的每一步操作都可以通过已有的基本操作执行有限次实现。输入：一个算法应该有零个或多个输入。输出：一个算法应该有一个或多个输出。这里所说的输出是指与输入有某种特定关系的量。举例问题：按从小到大的顺序重新排列x，y，z三个数值的内容。算法：输入x，y，z三个数值；从三个数值中挑选出最小者并换到x中；从y，z中挑选出较小者并换到y中；输出排序后的结果。1.

预定义常量及类型#define

TRUE

1#define

FALSE

0#define

OK

1#define

ERROR

0#define

OVERFLOW -1数据元素被约定为EntryType

类型，用户需要根据具体情况，自行定义该数据类型。2.

算法描述为以下的函数形式：函数类型函数名（函数参数表）{语句序列；}为了简化函数的书写，提高算法描述的清晰度，

我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给

出相应的注释即可。另外，在书写算法时，应该养成

对重点语句段落添加注解的良好习惯。3.

在算法描述中可以使用的赋值语句形式有：简单赋值 变量名=表达式；串联赋值 变量名1=变量名2=

...=变量名n

=表达式；成组赋值（变量名1，...，变量名n）=（表达式1，...，表达式n）；结构赋值 结构名1=结构名2；结构名=（值1，值2，...，值n）；条件赋值 变量名=条件表达式?表达式1：表达式2；交换赋值 变量名1↔

变量名2；4.

在算法描述中可以使用的选择结构语句形式有：条件语句1 if

（表达式）语句；条件语句2 if

（表达式）语句；else

语句；开关语句1 switch

（表达式）

{case

值1：语句序列1；break；case

值2：语句序列2；break；...case

值n：语句序列n；break；default：语句序列n+1；}开关语句2

switch

{case

条件1：语句序列1；break；case

条件2：语句序列2；break；...case

条件n：语句序列n；break；default：语句序列n+1；}5.

在算法描述中可以使用的循环结构语句形式有：for（表达式1；循环条件表达式；表for循环语句达式2） 语句；while循环语句while

（循环条件表达式）语句；do-while循环语句

do

{语句序列；}while

（循环条件表达式）；6.

在描述算法中可以使用的结束语句形式有：函数结束语句

return

表达式；return;case或循环结束语句

break;异常结束语句

exit（异常代码）；【算法1-1】用类C描述将三个数值排序的算法。viod

Three_Sort(

int

*x,int

*y,int

*z){

//将x,y,z三个指针所指示的内容按从小到大的顺序重新排列if

(*y<*x&&*y<*z)*x↔*y;//挑选出最小的数值并换到

x指针所指的存储单元中else if

(*z<*x&&*z<*y)*x↔*z;if

(*z<*y)

*y↔*z;//在y和z所指示的存储单元中挑选出较小者换到y中}1.3.3

算法的评价算法的评价标准正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。健壮性：算法中拥有对输入数据、打开文件、读取文件记录、分配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选择。时间与空间效率：算法的时间与空间效率是指将算法变换为程序后，