《数据结构》幻灯片(c语言)-第01章

第1页,数 据 结 构,主 讲：马慧芳 副教授 办公地点：教9-C502 电子邮件：mahuifangyeah.net 联系电话：13919465723,第2页,本章主要内容,一、数据结构教学计划 二、 第一章 绪论 1、 什么是数据结构 2、 基本概念和术语 3、 抽象数据类型(ADT) 4、 类C语言语法规则 5、 算法的描述和算法分析,第3页,一、数据结构教学计划,英文名称 Data Structure 先修课程 计算机导论、计算机高级语言、离散数学 后续课程 操作系统、数据库技术、编译方法、人工 智能引论、信息系统原理与工程等 授课学时 60学时 上机实践 10机时,第4页,配套题集 数据结构题集，严蔚敏等编 清华大学出版社，2011.11 参考教材 1. Fundamentals of Data Structures in C ，李建中 张岩 李治军 译 机械工业出版社，2006.7 2. 数据结构:C语言描述 ，殷人昆著机械工业出版社，2011.6 3. 数据结构与算法分析，冯舜玺 译，机械工业出版社，2004.1 注：可参考数据结构的C+语言方面的书籍。,一、数据结构教学计划,第5页,一、数据结构教学计划,课程地位 本课程不仅是一般的程序设计的基本训练，而且是设计和实现编译程序、操作系统、数据库系统、人工智能系统和其它系统程序的重要基础，是一门核心课程，对培养计算机及有关专业高层次科技人才具有重要意义。,第6页,课程任务 讲授那些最重要、最常用的数据结构，阐明数据结构内在的逻辑关系，讨论它们在计算机中的存储表示，并结合各种典型应用说明它们在进行各种运算时的动态性质和实现操作的算法。,一、数据结构教学计划,第7页,课程要求 1.熟悉各类典型的数据结构的逻辑特性、不同 的存储方法与存储量、算法及效率的关系、定义于数据结构上的主要基本操作及其算法，了解它们的应用环境,为学习后续课程奠定基础； 2.进一步提高软件设计和编程水平； 3.增强根据求解问题性质,选择合适的数据结构及控制求解算法的时间与空间复杂性的能力。,一、数据结构教学计划,第8页,第9页,要求： 、了解数据结构、算法的概念、基本的逻辑结 构和存储结构、基本操作； 、掌握类C语言体系和抽象数据类型的概念； 、知道算法的时间复杂性和空间复杂性概念。 重点： 、数据结构与算法的概念； 、类C语言体系； 、抽象数据类型。,二、第一章 绪论,第10页,1、什么是数据结构,二、第一章 绪论,简义：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。,数据结构是计算机科学专业的一门核心课程，它的研究对象为问题求解方法、程序设计方法及一些典型数据结构的算法。,第11页,数据结构,程序设计,算 法,问题求解,程序编写,1、什么是数据结构,第12页,“好”数据结构“好”算法“好”程序,良好、合理的数据结构 清晰、实用的算法 简洁、高效的程序,1、什么是数据结构,第13页,数据结构在计算机科学技术中是一门综合性的专业基础课，计算机科学技术各个领域都要用到多种数据结构。在我国计算机各专业的教学计划中，它是核心课程之一。在我院教学计划中，数据结构已成为我院各专业一门公共必修课程。中国已列入93年计算机教程中。推荐学时为100学时。 其基本内容包括：基本数据结构，抽象数据类型，递归算法，复杂性分析，排序和搜索，可计算性和不可判定性，问题求解策略，并行和分布式算法等。,数据结构在计算机科学中所处的地位：,1、什么是数据结构,第14页,客观事物的符号表示，是计算机程序加工的原料。它是信息的载体，能被计算机识别、存储和加工处理。 随着计算机软、硬件的发展，计算机应用领域的不断扩大，数据的含义也随之拓广。文字、表格、图像、声音、光和电的输入等等均可列入数据的范畴。, 数据(Data),2、基本概念和术语,二、第一章 绪论,第15页,是数据的基本单位，即数据这个集合中的一个实体。通常作为整体进行考虑和处理。有些情况下，数据元素也称为元素、结点、顶点、记录等。一个数据元素可能仅含一个数据项，亦可包含若干个数据项。, 数据元素(Data Element),2、基本概念和术语, 数据项(Data Item),亦称字段、域,数据项是具有独立含义的不可分割的最小标识单位。,第16页, 数据对象(Data Object),性质相同的数据元素的集合，是数据的一个子集。数据对象可以是有限的，也可以是无限的。 如：整数对象是集合N=0,±1, ± 2,.；字母字符的集合等。,2、基本概念和术语,第17页, 数据类型(Data Type),简称类型，一个值的集合和定义在值集上的一组操作的总称。它显式地或隐含地规定了变量或表达式所有可能的取值范围以及在这些值上允许进行的操作。 原子类型(Atomic Type)：如C中的标量类型（整型、实型、字符型）以及指针类型等。 结构类型(Structured Type）：亦称结构类型，如C中的数组、记录、文件类型等。 抽象数据类型(Abstract Data Type, ADT）：下面有专门介绍。,2、基本概念和术语,第18页, 数据处理(Data Processing),对数据进行诸如查找、插入、删除、合并、排序、统计、简单计算、输入、输出等的操作过程。,2、基本概念和术语, 结构(Structure),相互关联的元素之间的构成关系。这种关系可以是物理上的，也可以是逻辑上的，或其它关系。,第19页,定义：是相互之间存在一种或多种特定关系的数据元素的集合。 组成：由某一数据对象及该对象中所有数据成员之间的关系组成。 Data Structure = （ Data Object, Relationships ） 数据结构是指在程序中信息的逻辑组织方法，一般来说，这种方法也受到所选择的程序设计语言的限制。, 数据结构(Data Structure),2、基本概念和术语,第20页,数据的逻辑结构：指各数据元素之间的逻辑关系，是用户按使用需要建立起来的，呈现在用户面前的结构形式。 数据的物理结构：亦称数据的物理结构、存储结构，是指数据在计算机内的表示方法，即存储形式。, 数据结构(Data Structure),2、基本概念和术语,第21页,1）数据元素之间的逻辑关系，亦称数据的逻辑结构；, 数据结构的三个方面,2）数据元素及其关系在计算机存储器内的表示，亦称数据的存储结构；,3）数据的运算，即对数据施加的操作。,2、基本概念和术语,第22页, 数据结构的三个方面,例1： 一个线性表 逻辑结构：哪个元素是表中第一个元素；哪个元素是表中最后一个元素；哪些元素在一个给定元素之前或之后；等等。 存储结构：它的元素在存储器中是顺序地邻接存放，还是用指针连接在一起的；等等。 运算：在表中查找一个元素；从表中删去一个元素；向表中插入一个元素；等等。,2、基本概念和术语,第23页, 数据的四种基本逻辑结构与四种基本存储结构,1）从逻辑角度看，数据可归结为四种基本结构： 集合、线性结构、树结构和图结构,2）从存储角度看，数据可归结为四种基本结构： 顺序结构、链接结构、索引结构和散列结构,2、基本概念和术语,第24页,1）数据的四种基本逻辑结构,线性结构：结构中的数据元素之间存在一对一的关系,树结构：结构中的数据元素之间存在一对多的关系,图结构：结构中的数据元素之间存在多对多的关系。,集合：结构中的数据元素之间除“同属于一个集合”的关系，无其他关系,第25页,2）数据的四种基本存储结构, 链接存储结构 不要求逻辑上相邻的结点其物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。, 顺序存储结构 把逻辑上相邻的结点存储在物理位置上相邻存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。, 散列存储结构 根据结点的关键字直接计算出该结点的存储地址。, 索引存储结构 通常在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），关键字是能唯一标识一个结点的那些数据项。,第26页, 定义在数据结构上的基本操作,删除(Delete) 删去数据结构中某个指定的数据元素。,插入(Insert) 在数据结构中的指定位置上增添新的数据元素。,更新(Update) 改变数据结构中某个数据元素的值，在概念上等价于删除和插入操作的组合。,查找(Find) 在数据结构中寻找满足某个特定要求的数据元素(位置或值)。,2、基本概念和术语,第27页, 定义在数据结构上的基本操作,排序(Sort) （在线性结构中）重新安排数据元素之间的逻辑顺序关系，使之按值由小到大或大到小（即递增、不降或递减、不增）的次序排列。 注：一般将插入、删除与修改统称为更新；查找亦称搜索(Search) 。,2、基本概念和术语,第28页,同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，主要是使其运算方便及根据算法的时空要求来具体确定。 常将同一逻辑结构的不同存储结构以不同的数据结构的命名。如线性表顺序表、链表、散列表。 给定了数据的逻辑结构和存储结构，若定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。如线性表中的栈、队列、顺序栈、链栈、链队列。,2、基本概念和术语,第29页,抽象数据类型(Abstract Data Type,ADT)是指一个数学模型以及定义在这个模型上的一组操作。 抽象数据类型仅取决于它的逻辑特性，与其在计算集中的表示无关。即无论其内部结构如何变化，只要它的数学特性没有变化，都不影响其外部使用。一个ADT的定义并不涉及它的实现细节，这些实现细节对于ADT的用户是隐蔽的封装性/信息隐蔽 数据结构是ADT的物理实现。,3、抽象数据类型(ADT),二、第一章 绪论,第30页,例2：整数的数学概念和施加于整数的运算构成一个ADT，不同计算机中实现可能不同，其数学特性是相同，因此对用户完全相同。,3、抽象数据类型(ADT),例3：一个整数线性表的ADT应包含下列操作： 插入一个整数到线性表尾 删除线性表中特定位置上的整数 在线性表中查找特定整数,第31页,ADT包括以下三部分内容： ADT的规格说明(Specification) ADT的表示(Representation) ADT的实现(Implementation) 用元组表示： ADT = ( 数据对象, 关系集, 处理集 ),3、抽象数据类型(ADT),3、抽象数据类型(ADT),第32页,本书的表示格式： ADT 抽象数据类型名 数据对象： 数据关系： 基本操作： ADT 抽象数据类型名,3、抽象数据类型(ADT),3、抽象数据类型(ADT),用伪码表示,基本操作名(参数表) 初始条件： 操作结果：,第33页,在具体实现时，完成任务的算法、数据类型、数据结构、程序的逻辑组织，甚至采用哪种程序设计语言都是可以自由选择的 与具体实现无关。 ADT的主要目的之一是对用户隐蔽所有的表示方法，算法的详细细节、实现操作的具体代码以及其它所有对外界不必要的细节，都被局限于具体实现的模块内部，从而实现了信息的隐蔽。 ADT的一个重要优点是其简单性。ADT的目的是将数据的本质特征、它们的结构及操作同它们的非本质的具体表示及实现细节相区分开来，从而得到了简化。,3、抽象数据类型(ADT),第34页,例4：在数据结构中，复数可定义为一种简单的抽象数据类型： Complex=(C,R) 其中C是含有两个实数的集合C1,C2， R=P，P是定义在集合C上的一种关系， 有序偶表示C1是复数的实部，C2是复数的虚部。,3、抽象数据类型(ADT),第35页,Specif