《数据结构(C语言描述).ppt》由会员分享，可在线阅读，更多相关《数据结构(C语言描述).ppt（34页珍藏版）》请在三一办公上搜索。
1、数据结构（C+语言描述）,教学演示文稿,数据结构课程要研究的主要问题：现实世界中的实际问题必须经过抽象，得出反映实际事物本质的数据表示后，才能被计算机处理。如何用计算机所能接受的形式来描述这些数据，如何将这些数据以及它们之间的关系存储在计算机中，以及如何用有效的方法去处理这些数据，是数据结构课程要研究的主要内容。,2.1 基本概念,2.1.1 数据、数据元素、数据对象2.1.2 数据结构,2.1.1 数据、数据元素、数据对象,数据(data)是对客观事物的符号表示，是对现实世界的事物采用计算机能够识别、存储和处理的形式进行描述的符号的集合。例如：科学计算软件处理的是数值数据；文字处理软件处理的
2、是字符数据；多媒体软件处理的是图象、声音等多媒体数据。数据元素(data element)是数据的基本单位，也称结点，在一个计算机程序中通常作为一个整体进行考虑和处理。数据元素也称结点。,2.1.1 数据、数据元素、数据对象,一个数据元素可以由若干个数据项(data item)组成。数据项包括两种：初等项（是数据不可分割的最小单位）、组合项（由若干个数据项组成）。在数据库语言中，数据项称为“字段”，而数据元素称为“记录”。数据对象(data object)是性质相同的数据元素的集合，是数据的一个子集。例如整数对象、实数对象、字符对象等。,表2-1 学生情况表,一个数据元素,一个初等数据项,一个
3、组合数据项,整张表就是一个数据对象，其中每个学生的情况是其中的一个数据元素。,2.1.2 数据结构,从数学意义上讲，数据结构是指数据的组织形式，由数据对象及该对象中数据元素之间的关系组成。数据结构可描述为一个二元组Data-Structure=（D，R）其中：D是数据对象，为数据元素的有限集；R是该对象中数据元素之间关系的有限集。这种意义上的数据结构称为数据的逻辑结构。除此之外，要将数据放在计算机内进行处理，还将涉及数据的存储结构。,2.1.2 数据结构,涉及到计算机的数据结构概念，至今尚未有一个公认的标准定义，但一般认为应包括以下三个方面：（1）数据元素与数据元素之间的逻辑关系，也称为数据的
4、逻辑结构，它独立于计算机；（2）数据元素与数据元素之间的关系在计算机中的存储表示，也称为数据的存储结构或物理结构，它依赖于计算机；（3）数据的运算，即对数据施加的操作。,2.2 数据结构的分类：逻辑结构,如果一个数据结构中的两个结点k、k之间存在的关系可用有序对 表示，则称 k是 k的后继，k是k的前驱，k和k互为相邻结点。如果k没有后继，则k称为终端结点。如果k没有前驱，则称k为开始结点。如果k既不是终端结点，也不是开始结点，则称k为内部结点。数据的逻辑结构分为线性结构和非线性结构两大类。非线性结构又分为树型结构和图状结构。,线性结构,线性结构有且仅有一个开始结点和一个终端结点，并且所有的结
5、点最多只有一个前驱和一个后继。线性表是典型的线性结构。线性表一个学校所有学生的各种特征可用以下表格来记录：学号姓名 性别 出生年月 系班级030401张三男1985.1计算机0304030402李四女1984.12计算机0304030403王五男1984.6计算机0304030404赵六男1985.4计算机0304该表为一个数据结构，其中列称为“字段”，行称为“记录”，记录之间有一对一的线性关系，称为“线性结构”。,树状结构,树状结构中，一个结点最多只有一个前驱，而可以有多个后继。它是最重要的非线性结构。一个学校的组织机构可用以下数据结构来表示：该数据结构的“结点”具有一对多的逻辑关系，就象一
6、棵倒挂的树，故称为“树状结构”。,图状结构,图状结构中，对结点的前驱和后继的个数没有限制，结点之间的关系是任意的。它是最一般的非线性结构。在 n 个城市间建立通信网络，要求在任意两个城市之间都有直接或间接的通信线路，该通信线路可用以下图形来表示：如果每个城市为一个结点，则结点之间的逻辑结构称为“图状结构”，它是一种多对多的数据结构。,2.2 数据结构的分类：存储结构,数据的存储结构（又称物理结构）取决于四种基本的存储方法：顺序存储、链接存储、索引存储、散列存储。顺序存储是把逻辑上相邻的结点存储在物理位置相邻的存储单元里。结点之间的逻辑关系用存储单元的邻接关系来体现。链接存储对逻辑上相邻的结点不
7、要求在存储的物理位置上相邻，结点之间的逻辑关系由附加的指针来表示。索引存储是在存储结点数据的同时，还建立附加的索引表。索引表的每一项称为索引项。一般情况下索引项由关键字和地址组成。散列存储是根据结点的关键字计算出该结点的存储地址。同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。一种逻辑结构可采用一种方法存储，也可采用多种方法组合起来进行存储。,图2.2 基本存储方法,1001,1002,1003,1004,1005,1001,1002,1003,1004,1005,1006,1007,1001,1002,1003,1004,1005,2001,2002,2003,2004,2005,
8、d2,d5,d1,d4,d3,Di=h(keyi),(a)顺序存储,(b)链接存储,(c)索引存储,(d)散列存储,2.3 抽象数据类型,2.3.1 两种软件设计方法2.3.2 数据类型2.3.3 抽象数据类型,2.3.1 两种软件设计方法,面向过程的程序设计：是传统的设计方法，它把软件看成一个处理过程，将软件分解成为若干个表示过程步骤的模块，然后由编程语言的构件（子程序和函数）来实现。面向对象的程序设计：将软件看成由数据对象组成的集合，这些对象是应用问题所涉及的物理实体的数据模型，它们之间的相互作用构成了一个软件系统。面向对象的软件设计方法优于传统的软件设计方法，因为面向对象的软件设计方法采
9、用了抽象数据类型的描述方式，实现了数据抽象和信息隐蔽。,2.3.2 数据类型,数据类型(data type)是一组性质相同的值的集合以及定义在这个集合上的一组操作的总称。按值的不同特性，数据类型可以分为两类：(1)基本类型：如整型、实型、字符型等，通常由程 序语言直接提供。(2)组合类型：由一些基本类型组合构造而成，如记 录、数组、结构等，由用户借助程序 语言提供的描述机制自己定义。,2.3.3 抽象数据类型,抽象是指从特定的实例中抽取共同的性质以形成一般化概念的过程。抽象是对某系统的简化描述，即强调该系统中的某些特性，而忽略一部分细节。对系统进行的抽象描述称为对它的规范说明，对抽象的解释称为
10、对它的实现。数据抽象是一种对数据和操作数据的算法的抽象。数据抽象包含了模块化和信息隐蔽两种抽象。模块化和信息隐蔽是面向对象方法的核心。,2.3.3 抽象数据类型,抽象数据类型（Abstract Data Type，简称ADT）是指抽象数据的组织和与之相关的操作。可看做是数据的逻辑结构及在逻辑结构上定义的操作。在C+中，用类的说明来表示ADT，用类的实现来实现ADT，C+中实现的类相当于数据的存储结构及其在存储结构上实现的对数据的操作。ADT和类的概念反映了软件设计的两次抽象：ADT相当于在概念层（抽象层）上描述问题，而类相当于在实现 层上描述问题。,封装的矩形数据和操作的抽象数据类型如下：AD
11、T Rectangle Data/数据说明 非负实数，给出矩形的长和宽 Operation/操作说明 Area/操作1，求面积 Input：无 Preconditions：无 Process：计算矩形的面积 Output：返回面积值 Postconditions：无 Perimeter/操作2，求周长 Input：无 Preconditions：无 Process：计算矩形的周长 Output：返回周长值 Postconditions：无,封装的矩形数据和操作的抽象数据类型用C+中类（class）表示如下：class Rectangle private:float length,width;p
12、ublic:Rectangle(float l,float w);float Area(void)const;float Perimeter(void)const;Rectangle:Rectangle(float l,float w):length(l),width(w)float Rectangle:Area(void)const return length*width;float Rectangle:Perimeter(void)const return 2.0*(length+width);,2.4 算法和算法分析,2.4.1 算法概念2.4.2 算法分析,2.4.1 算法概念,算法是
13、一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算系列。一个算法应当具有以下的基本特性：（1）输入（2）输出（3）确定性（4）有穷性（5）可行性算法的描述有多种方法，如自然语言方式、图形方式、表格方式等。本教材采用C+程序语言来描述算法。,2.4.2 算法分析,人们常用以下几个标准来衡量一个算法的优劣：(1)正确性(2)可读性(3)健壮性(4)时间效率和存储占用量,1.估计算法运行时间的方法,基本考虑是：撇开所有与计算机硬件和软件有关的因素，只确定依赖于问题的“规模”(通常用n表示)和算法执行“基本操作”的次数。规模一般指输入量的数目，如被排序元素的数目；基本操作一般指定义在某个数据类
14、型上的标准操作，如整数相加、比较大小等。一个算法是由控制结构(顺序、选择、循环)和原操作(加、减、乘、除等)构成的。算法的效率取决于二者的综合效果。一般以基本操作重复执行的次数作为算法运行时间的度量。,2.算法的时间复杂度,一般情况下，算法中“基本操作”重复执行的次数是问题规模 n 的某个函数 f(n)，算法的时间度量记作此式表示随时间规模 n 的增大，算法执行时间的增长率与 f(n)的增长率相同，称为算法的时间复杂度。由于算法的时间复杂度分析只考虑相对于问题规模 n 的增长率，因而在难以精确计算基本操作执行次数的情况下，只要求出它关于 n 的增长率即可。我们可以在计算任何算法运行时间代价时，
15、忽略所有的常数和低次项，用O表示法来表示算法的时间复杂度，它只是一个数量级概念。,算法 2.2 计算两个nn矩阵的乘积,Void MatrixMultixMultiply(int Ann,int Bnn,int Cnn)int I,j,k;for(i=0;i T(n)=O(n3),定义：T(n)=O(f(n)当且仅当存在正整数 c和 n0，对所有的 n(nn0)满足T(n)cf(n)。换句话说，O(f(n)给出了函数 f(n)的上界。由于上述定义中对所有 n(nn0)，只要 n 比较大一般均成立，而我们考虑的算法的时间复杂度也主要是在问题规模 n 相当大时的情况。所以，在分析一个算法的时间复杂
16、度时，一般不考虑 n 为一个较小的数时 T(n)cf(n)不成立的情况。一般情况下，分析一个算法中基本语句执行次数及其与问题规模的关系，便可求出该算法的时间复杂度。,有时，算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始化状态有关。若不特别说明，所讨论的时间复杂度指最坏情况下的时间复杂度。有时也讨论算法的平均时间复杂度。平均时间复杂度是指所有可能的输入实例以等概率出现时，算法的平均（或期望）运行时间。常见的时间复杂度，按数量级递增排列，有：O(1)、O(log2n)、O(n)、O(nlog2n)、O(n2)、O(n3)、O(nk)、O(2n),3 算法的空间要求,类似于算法的时间复杂
17、度，算法在运行过程中需要辅助存储空间的大小称为算法的空间复杂度，记做：其中 n 为问题的规模。算法在运行过程中临时占用的辅助空间随算法不同而异。有的算法只需要占用少量临时工作单元，并且不随问题规模的大小而改变；有的算法需要占用的临时工作单元数随着问题规模 n 的增大而增大，此时按最坏的情况来分析。,例1.程序段,int s=0;for(int i=0;i=n;i+)for(int j=0;j=n;j+)s+;运算次数为n2,设每次增1运算时间为k,则运算时间 T(n)k*n2,时间复杂性为O(n2).,例2.冒泡排序,for(int i=n;i 1;i-)for(int j=1;j aj)int t=ai;ai=aj;aj=t;比较运算次数为：n-1+n-2+2+1=(n-1)*n/2n2/2n2.时间复杂度为O(n2).,例3.程序段,int i=1;while(i 1时成立。程序段的时间复杂度为O(log2(n).,例4.设f(n)=n2+n+6，,当n3时 f(n)5时 f(n)2*2n,O(f(n)=2n,
