项目一数据结构

《项目一数据结构》由会员分享，可在线阅读，更多相关《项目一数据结构（31页珍藏版）》请在金锄头文库上搜索。

1、数据结构数据结构项目一共项目一共分为二个分为二个任务任务项目一项目一 数据结构导论数据结构导论任务一任务一 数据结构入门数据结构入门任务二任务二 算法与算法分析算法与算法分析 任务一任务一 数据结构入门数据结构入门一、基本术语一、基本术语 二、数据的逻辑结构二、数据的逻辑结构 三、数据的存储结构三、数据的存储结构 四、数据类型四、数据类型 一、基本术语一、基本术语 1数据数据 2数据元素数据元素 3数据项数据项 4数据对象数据对象 5数据结构数据结构 1数据数据 数据（数据（data）是对客观事物的符号表示，在计算机科学中，是指所）是对客观事物的符号表示，在计算机科学中，是指所有能输入到计算机

2、中并被计算机程序处理的符号的总称。有能输入到计算机中并被计算机程序处理的符号的总称。 2数据元素数据元素 数据元素（数据元素（data element）是数据的基本单位，一个数据元素可由若）是数据的基本单位，一个数据元素可由若干个数据项组成，此时的数据元素通常称为记录（干个数据项组成，此时的数据元素通常称为记录（record）。）。 3数据项数据项 数据项（数据项（data item）是数据不可再分的最小单位，如学生信息记录中）是数据不可再分的最小单位，如学生信息记录中的学号、姓名等。的学号、姓名等。 4数据对象数据对象 数据对象（数据对象（data object）是性质相同的数据元素的集合，

3、是数据的）是性质相同的数据元素的集合，是数据的一个子集。一个子集。 5数据结构数据结构 数据结构（数据结构（data structure）是相互之间存在一种或多种特定关系的数据）是相互之间存在一种或多种特定关系的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。 一般包括三个方面的内容：一般包括三个方面的内容： 数据的数据的逻辑结构逻辑结构 数据的数据的物理结构物理结构 数据的数据的运算及实现运算及实现 二、数据的逻辑结构二、数据的逻辑结构 数据元素之间除了数据元素之间除了同属于一个集合同属于一个集合外，别无其他关系

4、。外，别无其他关系。 数据元素之间是数据元素之间是一对一一对一的关系。的关系。每个数据元素都有唯一的每个数据元素都有唯一的前驱前驱（第一个元素除外）和（第一个元素除外）和后继后继（最后一个（最后一个元素除外）。元素除外）。数据元素之间是数据元素之间是一对多一对多的关系。的关系。 在树形结构中，最上面的结点称为在树形结构中，最上面的结点称为根节点根节点，最下面的结点称为，最下面的结点称为叶子结点叶子结点。 数据元素之间是数据元素之间是多对多多对多的关系。的关系。 每个结点都可以每个结点都可以有多个前驱或后继有多个前驱或后继。 三、数据的存储结构三、数据的存储结构 数据的存储结构或物理结构是指数据

5、在计算机中的表示或存储方式，是数据的存储结构或物理结构是指数据在计算机中的表示或存储方式，是逻辑结构在计算机中的实现，包括数据元素的表示和关系的表示。逻辑结构在计算机中的实现，包括数据元素的表示和关系的表示。 1顺序存储结构顺序存储结构 2链式存储结构链式存储结构 1顺序存储结构顺序存储结构 顺序存储结构是指逻辑上相邻的数据元素，其结点的物理位置（内存中顺序存储结构是指逻辑上相邻的数据元素，其结点的物理位置（内存中的位置）也相邻，结点间的逻辑关系由存储单元的邻接关系体现。的位置）也相邻，结点间的逻辑关系由存储单元的邻接关系体现。 2链式存储结构链式存储结构 在链式存储结构中，结点间的逻辑关系由

6、附加的指针字段来指示的，在链式存储结构中，结点间的逻辑关系由附加的指针字段来指示的，因此，链式存储结构通常借助于程序设计语言中的指针数据类型来实因此，链式存储结构通常借助于程序设计语言中的指针数据类型来实现。现。 四、数据类型四、数据类型 1数据类型数据类型 2抽象数据类型抽象数据类型 1数据类型数据类型 数据类型（数据类型（data type）是和数据结构密切相关的一个概念，它最早出）是和数据结构密切相关的一个概念，它最早出现在高级程序语言中，用来描述操作对象的特性。在用高级语言编写现在高级程序语言中，用来描述操作对象的特性。在用高级语言编写的程序中，每个变量、常量或表达式都有一个确定的数据

7、类型。的程序中，每个变量、常量或表达式都有一个确定的数据类型。 2抽象数据类型抽象数据类型 抽象数据类型（抽象数据类型（abstract data type，简称，简称ADT）是指一个数学模型以）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。逻辑特性，而与其在计算机内部如何表示和实现无关。 ADT 抽象数据类型名抽象数据类型名 数据元素：数据元素： 数据关系：数据关系： 基本操作：基本操作：ADT抽象数据类型名抽象数据类型名其格式定义如下：其格式定义如

8、下：任务二任务二 算法与算法分析算法与算法分析 一、算法的概念一、算法的概念 二、算法的特性二、算法的特性 三、算法的描述方法三、算法的描述方法 四、算法设计的要求四、算法设计的要求 五、算法性能分析五、算法性能分析 六、类六、类C语言简介语言简介 一、算法的概念一、算法的概念 在在计算机领域计算机领域，根据所要处理的问题，在数据的逻辑结构和物理结，根据所要处理的问题，在数据的逻辑结构和物理结构基础上，在有限步骤内解决这一问题所采用的一组指令序列。构基础上，在有限步骤内解决这一问题所采用的一组指令序列。 在在实际生活实际生活中，算法就是为解决某一问题所采取的方法和步骤。中，算法就是为解决某一问

9、题所采取的方法和步骤。二、算法的特性二、算法的特性 有限性：有限性：有限步骤之内正常结束，不能形成无穷循环。有限步骤之内正常结束，不能形成无穷循环。 确定性：确定性：算法中的每一个步骤必须有确定含义，不能有二义性。算法中的每一个步骤必须有确定含义，不能有二义性。 可行性：可行性：算法中的每一个步骤都应当能有效执行，并得到确切结果。算法中的每一个步骤都应当能有效执行，并得到确切结果。 输入：输入：有有0个或多个输入。个或多个输入。 输出：输出：至少有一个或多个输出。至少有一个或多个输出。 三、算法的描述方法三、算法的描述方法 1自然语言自然语言 2流程图流程图 3伪代码伪代码 4程序设计语言程序

10、设计语言 【例例】要求一组数据中的最大数和最小数。要求一组数据中的最大数和最小数。1自然语言自然语言 重复步骤重复步骤，与第，与第4、5等数进行比较，直至结束。等数进行比较，直至结束。 将第将第1个数和第个数和第2个数相比较，记录最大数与最小数。个数相比较，记录最大数与最小数。 将最大数和最小数与第将最大数和最小数与第3个数比较，记录最大数与最小数。个数比较，记录最大数与最小数。2流程图流程图 3伪代码伪代码 开始开始置置i的初值为的初值为2置置Min和和Max的初值为的初值为a1当当i n时，执行如下操作时，执行如下操作 如果如果Minai,则使则使Min=ai 如果如果Maxai,则使则使

11、Max=ai i=i+1（循环体到此结束）（循环体到此结束）打印打印Max和和Min值值结束结束4程序设计语言程序设计语言 main () int a5 = 50, 23, 89, 12, 90; /定义含有五个整数元素的数组定义含有五个整数元素的数组 int i = 1; /i为指示器，初始指向第为指示器，初始指向第2个数组元素个数组元素 int Max, Min; /定义两个变量，用来保存当前的最大值和最小值定义两个变量，用来保存当前的最大值和最小值 Max = a0; /令当前的最大值为第令当前的最大值为第1个数组元素个数组元素 Min = a0; /令当前的最小值为第令当前的最小值为第

12、1个数组元素个数组元素 while (i ai) /如果当前数组元素小于当前最小值，则将当如果当前数组元素小于当前最小值，则将当前数组元素值赋于当前最小值变量前数组元素值赋于当前最小值变量 Min = ai; if (Max ai) /如果当前数组元素大于当前最大值，则将当如果当前数组元素大于当前最大值，则将当前数前数/组元素值赋于当前最大值变量组元素值赋于当前最大值变量 Max = ai; i = i + 1; /循环变量递增循环变量递增1 printf (the maximum is %d,the minimum is %d, Max, Min);四、算法设计的要求四、算法设计的要求 正确

13、性：正确性：“正确正确”的含义可以分为三个层次：的含义可以分为三个层次： 对于几组输入数据能够得出满足要求的结果。对于几组输入数据能够得出满足要求的结果。 对于精心选择的典型、苛刻且带有刁难性的几组输入数据能够得到对于精心选择的典型、苛刻且带有刁难性的几组输入数据能够得到满足要求的结果。满足要求的结果。 对于一切合法的输入数据都能产生满足要求的结果。对于一切合法的输入数据都能产生满足要求的结果。可读性：可读性：算法主要是为了人的阅读与交流，其次才是机器执行。因此，算法主要是为了人的阅读与交流，其次才是机器执行。因此，可读性好有助于人对算法的理解。可读性好有助于人对算法的理解。高效率低存储量：高

14、效率低存储量：通俗地说，效率指的是算法执行的时间。对于同一个通俗地说，效率指的是算法执行的时间。对于同一个问题，若有多个算法可以解决，执行时间短的算法效率就高。存储量指问题，若有多个算法可以解决，执行时间短的算法效率就高。存储量指的是算法执行过程中所需要的最大存储空间。的是算法执行过程中所需要的最大存储空间。 稳健性：稳健性：当输入数据非法时，算法也能做出正确反应或进行相应的处理，当输入数据非法时，算法也能做出正确反应或进行相应的处理，而不会产生一些莫名其妙的输出结果。而不会产生一些莫名其妙的输出结果。 五、算法性能分析五、算法性能分析 算法分析是每个程序设计人员应该掌握的技术。评价一个算法的

15、优劣算法分析是每个程序设计人员应该掌握的技术。评价一个算法的优劣主要看执行这个算法所需的时间（时间复杂度）和存储空间（空间复主要看执行这个算法所需的时间（时间复杂度）和存储空间（空间复杂度）。杂度）。 1时间复杂度时间复杂度 2空间复杂度空间复杂度 1时间复杂度时间复杂度 时间复杂度是指该算法的运行时间与问题规模的对应关系，记作时间复杂度是指该算法的运行时间与问题规模的对应关系，记作 T(n)O(f(n)其中，其中，n表示问题的规模；表示问题的规模；T(n)表示算法中语句的执行次数（称为语句频度或时间频度）；表示算法中语句的执行次数（称为语句频度或时间频度）；f(n)为辅助函数；为辅助函数；O

16、(f(n)表示表示f(n)是是T(n)的同数量级函数。的同数量级函数。 2空间复杂度空间复杂度 一个程序在计算机上执行时，除了需要存储本身所用的指令、常数一个程序在计算机上执行时，除了需要存储本身所用的指令、常数和输入数据以外，还需要一些对数据进行操作的辅助存储空间。因此，和输入数据以外，还需要一些对数据进行操作的辅助存储空间。因此，一个算法（程序）的空间复杂度是指程序运行从开始到结束所需的存一个算法（程序）的空间复杂度是指程序运行从开始到结束所需的存储空间，记作储空间，记作S(n)O(f(n)其中，各参数的意义与上面相同，故不再赘述。其中，各参数的意义与上面相同，故不再赘述。 六、类六、类C语言简介语言简介 类类C语言就是类似语言就是类似C语言的语言，本书中的算法均使用这种语言进行语言的语言，本书中的算法均使用这种语言进行描述，其目的是让编程人员在设计算法时能够更专注对算法思想的分描述，其目的是让编程人员在设计算法时能够更专注对算法思想的分析，而不受语言细节的约束。类析，而不受语言细节的约束。类C语言是标准语言是标准C语言的扩充，个别处语言的扩充，个别处使用了对标准使用了对标准C语言的一种简化表示。语言的一种简化表示。