数据结构使用C语言（第4版）-精选.ppt

线性结构 树结构 图结构 * 数据的存储结构 　 顺序存储结构：把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素存储位置关系上。 指针是指向物理存储单元地址的变量。由数据元素域和指针域组成的一个结构体称为结点。 链式存储结构：使用指针把相互直接关联的结点(即直接前驱结点或直接后继结点)链接起来，其特点是逻辑上相邻的数据元素在物理上不一定相邻，数据间的逻辑关系表现在结点的链接关系上。 * 顺序存储结构 链式存储结构 * 数据的操作 　 从抽象角度，数据的操作主要讨论某种数据类型数据应具备的操作的逻辑功能，抽象角度下的操作一般和数据的逻辑结构一起讨论； 具体来说，数据的操作主要讨论操作的具体实现算法。具体问题的操作实现必须在数据的存储结构确定后才能进行。 数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等典型的常用数据结构。在讨论这些典型数据结构时，主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论。 * 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个抽象数据元素a0, a1,…,an-1逆置的算法，即要求逆置后的数组中数据元素序列为an-1 , … , a1 , a0 ,并要求原数组中的数据元素值被改变。 void Reverse(int n, DataType a[]) { int i,m=n/2; DataType temp; for(i=0;im;i++) //进行m次调换 { temp=a[i]; a[i]=a[n-1-i]; a[n-1-i]=temp; } } * 算法满足以下性质: (1)输入性(2)输出性 (3)有限性 (4)确定性 (5)可执行性 算法设计满足以下目标: (1)正确性 (2)可读性 (3)健壮性 (4)高时间效率 (5)高空间效率 算法时间效率的度量 算法的执行时间需通过根据该算法编制的程序在计算机上运行时所消耗的时间来度量。方法有两种: (1)事后统计方法 (2)事前分析方法 * 程序运行消耗时间的有关因素: (1)书写算法的程序设计语言 (2)编译产生的机器语言代码质量