数据结构—分析.ppt

* * * * * * * * * * * * * * * * * * 第1章 绪论 主要知识点 数据结构的基本概念 抽象数据类型和软件构造方法 算法和算法的时间复杂度 算法书写规范 1.1 数据结构的基本概念 基本术语 (1)数据：人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。 (2)数据元素：表示一个事物的一组数据。 (3)数据项：构成数据元素的数据。 例如，学生信息可包括学生的学号、姓名、性别、年龄等数据。这些数据构成学生情况的描述的数据项；包括学号、姓名、性别、年龄等数据项的一组数据就构成学生信息的一个数据元素。 本书采用C语言描述数据元素和各个数据项，如定义学生类型结构体类型的变量及其成员。 基本术语 (4)抽象数据元素：没有实际含义的数据元素(如上一章的DataType 定义的变量) 。 (5)抽象数据元素的类型：没有确切定义的数据类型(如上一章的DataType类型)。 (6)数据的逻辑结构：数据元素之间的相互联系方式（相互关系）。 (7)数据的存储结构：数据元素在计算机中的存储方式。 (8)数据的操作：对一种数据类型的数据进行的某种处理。 (9)数据的操作集合：对一种数据类型的数据进行的所有操作。 数据的逻辑结构 线性结构：除第一个和最后一个数据元素外，每个数据元素只有一个前驱和一个后继数据元素。（一对一） 树结构：除根结点外，每个数据元素只有一个前驱数据元素，可有０个或若干个后继数据元素。（一对多） 图结构：每个数据元素可有０个或若干个前驱数据元素和０个或若干个后继数据元素。（多对多） 集合结构：分散的数据元素，相互之间只是属于同一个集合，无其他关系。 线性结构 树结构 图结构 数据的存储结构 　 顺序存储结构：把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素存储位置关系上。 指针是指向物理存储单元地址的变量。由数据元素域和指针域组成的一个结构体称为结点。 链式存储结构：使用指针把相互直接关联的结点(即直接前驱结点或直接后继结点)链接起来，其特点是逻辑上相邻的数据元素在物理上不一定相邻，数据间的逻辑关系表现在结点的链接关系上。 顺序存储结构 链式存储结构 一个 结点 数据的操作 　 从抽象角度，数据的操作主要讨论某种数据类型数据应具备的操作的逻辑功能，抽象角度下的操作一般和数据的逻辑结构一起讨论； 具体来说，数据的操作主要讨论操作的具体实现算法。具体问题的操作实现必须在数据的存储结构确定后才能进行。 数据结构课程主要讨论线性表、堆栈、队列、串、树和二叉树、图等典型的常用数据结构。在讨论这些典型数据结构时，主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论。 1.2 抽象数据类型和软件构造方法 类型是一组值的集合。 数据类型是指一个类型和定义在这个类型上的操作集合。 抽象数据类型是指一个逻辑概念上的类型和这个类型上的操作集合。 数据类型和抽象数据类型的不同之处仅仅在于数据类型指的是高级程序设计语言支持的基本数据类型，而抽象数据类型指的是在基本数据类型支持下用户新设计的数据类型。 抽象数据类型使软件设计成为工业化流水线生产的一个中间环节。一方面，根据给出的抽象数据类型的功能定义，负责设计这些抽象数据类型的专门公司设计该抽象数据类型的具体存储结构以及在具体存储结构下各操作的具体实现算法；另一方面，利用已设计实现的抽象数据类型模块，负责设计应用软件的专门公司可以安全、快速、方便的完成该应用软件系统的设计。 软件的设计采用模块化方法，抽象数据类型就是构造大型软件的最基本模块。 1.3 算法及其时间复杂度 算法是描述求解问题方法的操作步骤集合。 描述算法的语言形式 1.文字形式:用中文或英文这样的文字来描述算法。 2.伪码形式:用一种仿程序设计语言的语言来描述算法。 3.程序设计语言形式:用某种程序设计语言描述算法。其优点是算法不用修改，直接作为程序语句键入计算机，计算机能调用和运行。 例1-1:设计一个把存储在数组中的有n个抽象数据元素a0, a1,…,an-1逆置的算法，即要求逆置后的数组中数据元素序列为an-1 , … , a1 , a0 ,并要求原数组中的数据元素值不能被改变。 void Reverse(int n, DataType a[], DataType b[]) { int i; for(i=0;in;i++) b[i]=a[n-1-i]; //把数组a的元素逆置后赋给数组b } 例1-2:设计一个把存储在数组中的有n个抽象