第1章 数据结构概论课件.pptVIP

数据结构(C语言版);数据结构教学指南;课程性质和任务;;课时分配建议表 ;第1章 数据结构概论;要想成为一个专业的开发人员，至少需要以下三个条件： (1) 能够熟练地选择和设计各种数据结构和算法。 (2) 至少要能够熟练地掌握一门程序设计语言。 (3) 熟知所涉及的相关应用领域的知识。 瑞士著名的计算机科学家沃思（N·Wirth）提出了： 算法 + 数据结构 = 程序 正说明了数据结构和算法的重要性。 ;例：求圆的面积。 　　已知：半径为r，面积为a。 　　main( ) 　　｛double a,r=50.0; 　　　a=3.14159*r*r; 　　　printf(“r=%.2f，a=%.2f\n”,r,a); 　　　｝ 简单数据结构关系;例：关系型数据结构;昆明冶金高等专科学校;80;小结 　　凡是能够输入计算机并能被计算机处理的信息都被称为数据，计算机科学是一门研究数据表示和数据处理的科学。 　　数据结构研究的就是如何处理有结构的数据的学科，进一步，数据结构是研究非数值计算的程序设计问题中出现的计算机操作对象以及它们之间的关系和操作的学科。 　　数据结构是计算机各专业的专业基础课，是十分重要的核心课程。;⒈数据（data） 　　是对客观事物的符号表示，指能输入计算机并能被计算机处理的符号的总称。 数值数据：整型、实型、布尔型等。 非数值数据：字符、文字、图像、声音等。 ⒉数据元素（data element） 　　是数据的基本单位，是对一个客观实体的数据描述，在计算机程序中通常作为一个整体进行处理。数据元素也被称为结点或记录。;⒊数据项（data item） 　　数据的具有独立意义的不可分的最小单位，是对数据的数据元素属性的描述，也被称为字段或域。 ⒋数据对象（data object） 　　具有相同性质的数据元素的集合。在某个具体问题中，数据元素都具有相同的性质（数据元素的值不一定相等），属于同一数据对象。;学号;⒌数据结构（data structure） 　　数据结构可解释为用来探讨计算机内部各种数据的存储方式，并对于如何有效地维护、处理和应用数据，提供评估的方法；用于探讨如何将原始的数据加以分析整理，创建数据间的相互关系，以最有利的类型存放在内存中以便计算机处理，并提供一种策略使计算机能够充分从内存中存取这些数据。也可解释为： ⑴数据项与数据项的先后、相互关系； ⑵使数据所需的存储空间容量最小； ⑶使数据所需的存取时间最短； ⑷以最有利于用户的环境，提供最好的界面，再加些技巧，算法和策略。;　　简单地说，数据结构指数据之间的相互关系，即数据的组织形式。一般包括以下三个方面。 ⑴数据之间的逻辑关系，也称为数据的逻辑结构。 ⑵数据元素及其关系在计算机存储器内的表示，称为数据的存储结构，也称为物理结构。 ⑶数据的运算，即针对数据的存储结构所进行的运算。 通过讨论看出：数据结构是研究数据元素之间的相互关系和这种关系在计算机中的存储表示，并对这种结构定义相应的运算，设计出相应的算法，且确保经过这些运算后所得到的结果仍然是原来的结构类型。 　　数据结构讨论的问题主要有： ⑴如何以最节省存储空间的方式来表示数据； ⑵各种不同的数据结构表示方法及其相关算法； ⑶如何有效地改进算法效率，使程序的执行速度更快； ⑷数据处理的各种技巧，如排序、查找等算法。　;　　数据结构又包括数据逻辑结构和数据物理结构。 　　逻辑结构是指数据元素之间所固有的相互关系; 　　物理结构又称存储结构，是数据结构在计算机中的表示（又称映象），它不仅存储了数据元素的数据信息，还存储了数据元素之间的关系信息。 　　同一种逻辑结构可以有几种不同的物理结构来实现它。在程序设计中，研究物理结构更为重要，因为对于同一问题，数据的存储结构不同，解决问题的方法就有所不同。 　　数据结构研究数据的逻辑结构和物理结构，并在这种结构上定义相关的运算，设计实现这些运算的算法，分析算法的效率。 ; 逻辑结构;;　　总之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，这个关系描述的是数据元素之间的逻辑关系。数据的逻辑关系也称为数据的逻辑结构，它与数据的存储无关，是独立于计算机的，因此，数据的逻辑结构可以看成是从具体的问题中抽象出来的数学模型。 　　数据的逻辑结构分为三种基本结构类型。 ①集合。 　　数据具有符合某一条件的相同的性质，且无其他关系，只是同属于一个集合而已。如自然数的全体，实数域的全体，各种颜色属于色彩集合等。 ②线性结构。 　　有且仅有一个起点和一个终点，并且所有结点只有一个直接前趋和一个直接后继，如线性表、队列等，结点之间是一对一的关系。如一年四季中的春、夏、秋、冬。;③非线性结构。 　　一个结点可能有多个直接前趋或