数据结构.ppt

数据结构(C语言版)Data Structure数据结构是程序设计的中级课程,主要培养学生分析数据、组织数据的能力,告诉学生如何编写效率高、结构好的程序。本书在内容的选取、概念的引入、文字的叙述以及例题和****题的选择等方面,都力求遵循面向应用、逻辑结构简明合理、由浅入深、深入浅出、循序渐进、便于自学的原则,突出其实用性与应用性。进入章节第一章绪论本章介绍了数据结构这门学科诞生的背景、发展历史以及在计算机科学中所处的地位,重点介绍了数据结构有关的概念和术语,大家学****本章后应能掌握数据、数据元素、逻辑结构、存储结构、数据处理、数据结构、算法设计等基本概念,并了解如何评价一个算法的好坏。【知识点】数据、数据元素、数据结构、数据类型、抽象数据类型、算法及其设计原则、时间复杂度、空间复杂度? 数据结构? 基本概念和术语?? 基本概念和术语一、数据(data)数据是指所有能输入到计算机中并被计算机程序处理的符号的总称。是计算机加工的“原料”。如文字、表格、图象、声音等,都称为数据。二、数据元素、(data element):是组成数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。又称为结点或记录。例如,在表1-1所示的学生成绩表中,为了便于处理,把其中的每一行(代表一位学生)作为一个基本单位来考虑,故该数据由3个数据元素构成。(data item):有时,一个数据元素可由多个数据项组成。数据项是数据的不可分割的最小单位。又称为字段或域。例如,在表1-1所示的表格数据中,每个数据元素都有学号、姓名、语文、数学、英语等五个字段构成。数据项是构成数据的最小单位。表1-1 学生成绩表表1-2 一班学生成绩表三、数据对象、(data object):是性质相同的数据元素的集合,是数据的一个子集。例如,一个班级的成绩表如表1-2所示,可以看成数据对象。(data structure):?定义一:数据元素集合(也可称数据对象)中各元素的关系。?定义二:相互之间存在特定关系的数据元素集合。:1)逻辑结构:数据元素之间的逻辑关系。在表1-1所示的表格数据中,各结点之间在逻辑上有一种线性关系,它指出了3个结点在表中的排列顺序。根据这种线性关系,可以看出表中第一位学生是谁,第二位学生是谁,等等。2)存储结构(物理结构):数据元素及其关系在计算机存储器的表示。在表1-1所示的表格数据在计算机中可以有多种存储表示,例如,可以表示成数组,存放在内存中;也可以表示成文件,存放在磁盘上,等等。3)数据的运算:对数据施加的操作。(书P9)如对数据进行查找、插入、删除、修改、合并、排序、统计以及简单计算等的操作过程。算法的设计取决于选定的数据逻辑结构,而算法的实现依赖于采用的存储结构。为了叙述上的方便和避免产生混淆,通常我们把数据的逻辑结构统称为数据结构(Date Structure),把数据的物理结构统称为存储结构(Storage Structure)。(逻辑结构)的三(四)(逻辑结构)的形式定义:数据结构是一个二元组Data_Structure =(D,S)数据结构名称=(D,S)其中:?D 是数据元素的有限集,即数据元素的集合。?S 是D上关系的有限集,即数据元素之间的关系的集合。