数据结构PPT.ppt

《数据结构PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构PPT.ppt（34页珍藏版）》请在课桌文档上搜索。

1、第1章 概述,1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示与实现 1.4 算法和算法分析,提出预备知识,(1)typedef的格式与用法(2)数组(特别是结构体数组)的定义和使用(3)结构体的定义与使用(4)链表的建立、插入与删除(5)递归函数的定义与使用,1938年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。从31岁起，开始出版他的历史性经典巨著：The Art of Computer Programming他计划共写7卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时

2、，他年仅36岁。,数据结构的创始人克努思,数据结构的兴起和发展,程序设计的实质是什么?,数据表示：将数据存储在计算机中数据处理：处理数据，求解问题,数据结构问题起源于程序设计,数据结构的兴起和发展,数据结构随着程序设计的发展而发展,无结构阶段结构化阶段：数据结构算法程序面向对象阶段：(数据结构算法)程序,数据结构的发展并未终结,1.1 什么是数据结构,计算机求解问题 问题抽象出问题的模型求模型的解问题数值问题、非数值问题 数 值 问 题数学方程 非数值问题数据结构,例1 学籍管理问题表结构,完成什么功能?各表项之间是什么关系？,1.1 什么是数据结构,例2 人机对弈问题树结构,如何实现对弈?各

3、格局之间是什么关系？,1.1 什么是数据结构,例3 教学计划编排问题图结构,1.1 什么是数据结构,如何表示课程之间的先修关系？,1.1 什么是数据结构,数据结构一般包括以下三方面内容：数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。,1.1 什么是数据结构,数据结构一般包括以下三方面内容：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure）；数据的存储结构是逻辑结构用计算机语言的实现（亦称

4、为映象），它依赖于计算机语言。,1.1 什么是数据结构,数据结构一般包括以下三方面内容：数据的运算，即对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作，是指我们只知道这些操作是做什么，而无须考虑如何做。只有确定了存储结构之后，才考虑如何具体实现这些运算。,1.1 什么是数据结构,数据结构是指：数据之间逻辑关系 数据在内存中的映像(存储结构)数据有关操作的算法的总称。,1.1 什么是数据结构,注意：数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据

5、的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。(1)存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。例：线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。,1.1 什么是数据结构,注意：数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。(2)数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。例：若对

6、线性表上的插入、删除运算限制在表的一端进行，则该线性表称之为栈；若对插入限制在表的一端进行，而删除限制在表的另一端进行，则该线性表称之为队列。更进一步，若线性表采用顺序表或链表作为存储结构，则对插入和删除运算做了上述限制之后，可分别得到顺序栈或链栈，顺序队列或链队列。,1.1 什么是数据结构,注意：数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。(3)逻辑结构与存储结构的关系数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其

7、数据处理的效率往往是不同的。,返回,1.2 基本概念和术语,一、基本术语数据：计算机处理的信息的全体。数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的“原料”。数据元素(Data Element):是数据的基本单位。数据元素也称元素、结点、顶点、记录。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。数据项是具有独立含义的最小标识单位。,1.2 基本概念和术语,二、四种基本结构 根据数据元素之间的关系，可以分成以下几种结构：(1)集合(2)线性结构(3)树形结构(4)图状结构,1.2 基本概念和术语,三、描述数据逻辑结构的方法(1)抽象定义法 Data_St

8、ructure=(D,S)其中，D是数据元素的集合，S是关系的集合(2)图释法,1.2 基本概念和术语,四、数据的存储结构(1)顺序存储结构 该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构(Sequential Storage Structure),通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。,1.2 基本概念和术语,四、数据的存储结构(2)链式存储结构 该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表

9、示。由此得到的存储表示称为链式存储结构（Linked Storage Structure）,通常借助于程序语言的指针类型描述。,cat0325,bat0200,eat,例:(bat,cat,eat),1.2 基本概念和术语,四、数据的存储结构(3)索引存储方法 该方法通常在储存结点信息的同时，还建立附加的索引表。(4)散列存储方法 该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。,1.2 基本概念和术语,四、数据的存储结构 说明：(1)四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。(2)同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结

10、构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。,1.2 基本概念和术语,四、数据的存储结构 说明：(3)顺序存储结构与链式存储结构的区别顺序存储结构：用一片连续的空间依次将数据存入；物理结构与逻辑结构相一致；用存储的相对位置可以来表示元素间的逻辑关系。,1.2 基本概念和术语,四、数据的存储结构 说明：(3)顺序存储结构与链式存储结构的区别链式存储结构：可以用互不连续的空间存放数据；物理结构与逻辑结构不一致；用指针来表示元素间的逻辑关系。,1.2 基本概念和术语,五、抽象数据类型1.数据类型：一组性质相同的值集合 定义在这个值集合上一组操作的总称。2.抽象数据类型(

11、1)定义:一个数据模型和定义在该模型上的一组操作。(2)描述:用三元组描述(D,S,P)其中，D是数据对象，S是D上的关系集，P是对D上的基本操作集。,返回,1.4 算法和算法分析,一、算法：完成特定问题的指令序列二、算法的特性 有穷性；确定性；可行性；输入；输出三、算法设计的要求 正确、可读、健壮、高效,1.4 算法和算法分析,四、算法分析1评价算法好坏的标准 求解同一计算问题可能有许多不同的算法，究竟如何来评价这些算法的好坏以便从中选出较好的算法呢？选用的算法首先应该是“正确”的。此外，主要考虑如下三点：执行算法所耗费的时间；执行算法所耗费的存储空间，其中主要考虑辅助存储空间；算法应易于理

12、解，易于编码，易于调试等等。,1.4 算法和算法分析,四、算法分析2算法的时间性能分析(1)算法耗费的时间和语句频度一个算法所耗费的时间=算法中每条语句的执行时间之和 每条语句的执行时间=语句的执行次数语句执行一次所需时间 算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。,频度(Frequency Count),1.4 算法和算法分析,四、算法分析2算法的时间性能分析(1)算法耗费的时间和

13、语句频度例：求两个n阶方阵的乘积 C=AB,#define N 100 void matrixmultiply(int ANN,int BNN,int CNN)int i,j,k;(1)for(i=0;iN;i+)(2)for(j=0;jN;j+)(3)Cij=0;(4)for(k=0;kN;k+)(5)Cij=Cij+Aik*Bkj;,1.4 算法和算法分析,四、算法分析2算法的时间性能分析(1)算法耗费的时间和语句频度分析示例：求两个n阶方阵的乘积 C=AB 语句(1)的循环控制变量i要增加到n，测试到i=n成立才会终止。故它的频度是n+1。但是它的循环体却只能执行n次。语句(2)作为语句

14、(1)循环体内的语句应该执行n次，但语句(2)本身要执行n+1次，所以语句(2)的频度是n(n+1)。同理可得语句(3)，(4)和(5)的频度分别是n2，n2(n+1)和n3。算法MatrixMultiply的时间耗费T(n)是矩阵阶数n的函数。,1.4 算法和算法分析,四、算法分析2算法的时间性能分析(2)问题规模和算法的时间复杂度 算法求解问题的输入量称为问题的规模(Size),一般用一个整数表示。一个算法的时间复杂度(Time Complexity,也称时间复杂性)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为

15、算法的渐进时间复杂度。,1.4 算法和算法分析,四、算法分析2算法的时间性能分析(2)问题规模和算法的时间复杂度例：算法MatrixMultidy的时间复杂度T(n)如下式所示，当n趋向无穷大时，显然有,这表明，当n充分大时，T(n)和n3之比是一个不等于零的常数。即T(n)和n3是同阶的，或者说T(n)和n3的数量级相同。记作T(n)=O(n3)是算法MatrixMultiply的渐近时间复杂度。,1.4 算法和算法分析,四、算法分析2算法的时间性能分析(3)评价算法的时间性能主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。T(n)=O(f(n)其中:n代表问题的规模；f(n)为相应规模下基本操作执行的次数；基本操作一般为最深层循环体内的语句 O代表Order，代表数量级，O(f(n)为取f(n)的数量级。T(n)表示时间复杂度，用它来进行算法的时间性能的分析。,返回,