孙丽云数据结构第1章绪论(第1讲).pptVIP

数据结构;1、该课程共72学时，其中上课56学时，上机16学时； 2、最终成绩包括平时成绩（上课及作业情况）、上机成绩、期中成绩、期末成绩； 3、答疑； 4、公共邮箱： 用户名：shujujiegou007@126.com 密码：xinxi007 5、一定要记笔记！;1、求从键盘输入的任意两个数的和； 2、若从键盘输入+，则计算键盘输入的两个数的和，若从键盘输入*，则计算键盘输入的两个数的乘积； 3、求从键盘输入的10个整型数的和（用循环结构实现） 思考：若要求数据输入在主函数中，求和在自定义函数中，该如何实现？;熟悉利用数组名作为函数的参数：从键盘输入十个同学的成绩，找出90分以上（包括90分）的同学的人数，找出最高分，并计算出平均分（输出结果保留2位小数）。 要求：（1）每个问题都用自定义函数实现； （2）试着将数据输入也用自定义函数实现。;本章主题：数据结构的基本概念和术语 教学目的：了解数据结构的基本概念，理解常用术语 教学重点：熟悉数据结构常用术语，掌握基本概念，了解算法时间复杂度和空间复杂度的分析与评价 教学难点：数据元素间的 4 种结构关系。 主要内容： 1.1 什么是数据结构 1.2 算法描述 1.3 算法分析与评价;计算机科学技术发展速度惊人，它的广泛应用已从传统的数值计算领域发展到各种非数值计算领域，如用于控制和管理； 计算机加工处理的对象已从简单的数值发展到字符、表格和图象等各种具有一定结构的非数值性数据。;针对每一种新的应用领域的处理对象： 如何选择合适的数据表示（结构）； 如何有效地组织计算机存储； 在此基础上又如何有效地实现对象之间的“运算”关系； 数据结构就是研究和解决这些问题的重要基础理论。 因此，“数据结构”课程已成为计算机类专业的一门重要专业基础课。;1.1 什么是数据结构;一个含12位数的十进制数可以用三个4位的十进制数表示 3214,6587,9345 ─ a1(3214),a2(6587),a3(9345) 在a1、a2和a3 之间存在“次序”关系 a1,a2 、 a2,a3 3214，6587，9345 ≠ 6587，3214，9345 　a1 　a2 　a3 　　　a2　　a1 　a3;例2、电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的信息。;数据结构在程序设计中的地位： 程序设计 = 算法 + 数据结构 数据结构是关于数据组织和处理的基本技术的一门学科，是程序设计的中级课程，主要培养我们分析数据、组织数据的能力，告诉我们如何编写效率高、结构好的程序。; ; ;3．数据对象(Data Object) 数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。; ; ;数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。 数据结构包括3方面内容：逻辑结构、存储结构（或称物理结构）、数据运算。 逻辑结构：描述数据元素间的逻辑关系，与数据的存储无关。 数据逻辑结构可以用二元组（D，R）描述D：数据元素定义域集合R：数据元素上的关系集合 关系a, b中，a称为b的前驱，b称为a的后继;根据数据元素间的逻辑关系的特点，可将基本逻辑结构分为： 集合结构：结构中的数据元素除了同属于一种类型外，别无其它关系。较少使用 线性结构：结构中的数据元素之间存在一对一的关系。 树型结构：结构中的数据元素之间存在一对多的关系。 图形结构（或称网状结构）：结构中的数据元素之间存在多对多的关系。;学号;物理结构（存储结构）：数据结构在计算机中的存储表示。它包括数据元素的表示和关系的表示。 基本物理结构 顺序存储结构 链式存储结构;0;1.1.3 数据结构(Data Structure); ;1.2 算法描述;算法的重要特性 有穷性：算法总在执行有穷步后结束，且每一步都在有穷时间内完成。 确定性：不存在二义性，且相同的输入一定得到相同的输出。 可行性：算法描述的操作都可通过已经实现的基本运算执行有限次来实现。 输入：一个算法有零个或多个输入。 输出：一个算法有一个或多个输出。; ;算法设计的要求 正确性：算法应满足具体问题的需求。 可读性：便于理解、调试程序和维护。 健状性：算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。;算法效率的度量——时间复杂度;算