数据结构PPT.ppt

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

1、第1章 概述1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表示与实现 1.4 算法和算法分析提出预备知识 (1) typedef的格式与用法(2)数组(特别是结构体数组)的定义和使用(3)结构体的定义与使用(4)链表的建立、插入与删除(5)递归函数的定义与使用19381938年出生，年出生，2525岁毕业于加州理工学院数岁毕业于加州理工学院数学系，博士毕业后留校任教，学系，博士毕业后留校任教，2828岁任副教岁任副教授。授。3030岁时，加盟斯坦福大学计算机系，岁时，加盟斯坦福大学计算机系，任教授。从任教授。从3131岁起，开始出版他的历史性岁起，开始出版他的历史性经典巨著

2、：经典巨著：The Art of Computer ProgrammingThe Art of Computer Programming他计划共写他计划共写7 7卷，然而出版三卷之后，已震卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年仅誉图灵奖，此时，他年仅3636岁。岁。数据结构的创始人克努思数据结构的兴起和发展 程序设计的实质是什么?数据表示：将数据存储在计算机中数据处理：处理数据，求解问题数据结构问题起源于程序设计 数据结构的兴起和发展 数据结构随着程序设计的发展而发展无结构阶段无结构阶段结构化阶段结构化阶段： 数据

3、结构算法程序数据结构算法程序面向对象阶段面向对象阶段： ( (数据结构算法数据结构算法) )程序程序数据结构的发展并未终结1.1 什么是数据结构计算机求解问题 问题抽象出问题的模型求模型的解问题数值问题、非数值问题 数 值 问 题数学方程 非数值问题数据结构例1 学籍管理问题表结构学号学号姓名姓名性别性别出生日期出生日期政治面貌政治面貌0001王王 军军男男1983/09/02团员团员0002李李 明明男男1982/12/25党员党员0003汤晓影汤晓影女女1984/03/26团员团员完成什么功能?各表项之间是什么关系？1.1 什么是数据结构例2 人机对弈问题树结构如何实现对弈?各格局之间是什

4、么关系？.1.1 什么是数据结构例3 教学计划编排问题图结构C4, C5, C6数据库原理数据库原理C7C2, C4计算机原理计算机原理C6C3, C4数据结构数据结构C5C1, C2程序设计程序设计C4C1离散数学离散数学C3无无计算机导论计算机导论C2无无高等数学高等数学C1先修课先修课课程名称课程名称编号编号1.1 什么是数据结构C1C2C3C4C6C5C7如何表示课程之间的先修关系？如何表示课程之间的先修关系？1.1 什么是数据结构数据结构一般包括以下三方面内容： 数据元素之间的逻辑关系，也称数据的逻辑结构数据的逻辑结构（Logical Structure）； 数据的逻辑结构是从逻辑关

5、系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。1.1 什么是数据结构数据结构一般包括以下三方面内容： 数据元素及其关系在计算机存储器内的表示，称为数据的存储结构数据的存储结构（Storage Structure）； 数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。1.1 什么是数据结构数据结构一般包括以下三方面内容： 数据的运算数据的运算，即对数据施加的操作。 数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽

6、象的操作。 所谓抽象的操作抽象的操作，是指我们只知道这些操作是做什么，而无须考虑如何做。只有确定了存储结构之后，才考虑如何具体实现这些运算。1.1 什么是数据结构数据结构是指： 数据之间逻辑关系 数据在内存中的映像(存储结构) 数据有关操作的算法的总称。1.1 什么是数据结构注意：数据结构三方面的关系数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。(1)存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。 例：线性表是一种逻辑结构，若采用顺序方法的存储表示，可

7、称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。1.1 什么是数据结构注意：数据结构三方面的关系数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。(2)数据的运算也是数据结构不可分割的一个方面。在给定了数据的逻辑结构和存储结构之后，按定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。例：若对线性表上的插入、删除运算限制在表的一端进行，则该线性表称之为栈；若对插入限制在表的一端进行，而删除限制在表的另一端进行，则该线性表称之为队列。更进一步，若线性表采用顺序表或链表作为存储结构，则对插入和删除运算做了上述限制之

8、后，可分别得到顺序栈或链栈，顺序队列或链队列。1.1 什么是数据结构注意：数据结构三方面的关系数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。(3)逻辑结构与存储结构的关系数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。 一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。 返回1.2 基本概念和术语一、基本术语数据：计算机处理的信息的全体。 数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的“原料”。数据元素(Data E

9、lement):是数据的基本单位。数据元素也称元素、结点、顶点、记录。 一个数据元素可以由若干个数据项数据项（也可称为字段、域、属性）组成。数据项是具有独立含义的最小标识单位。1.2 基本概念和术语二、四种基本结构 根据数据元素之间的关系，可以分成以下几种结构：(1)集合(2)线性结构(3)树形结构(4)图状结构1.2 基本概念和术语三、描述数据逻辑结构的方法(1)抽象定义法 Data_Structure=(D,S)其中，D是数据元素的集合，S是关系的集合(2)图释法1.2 基本概念和术语四、数据的存储结构 (1)顺序存储结构 该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的

10、逻辑关系由存储单元的邻存储单元的邻接关系接关系来体现。 由此得到的存储表示称为顺序存储结构 (Sequential Storage Structure),通常借助程序语言的数数组组描述。 该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。batcateat 起始地址起始地址例：（例：（bat, cat, eat）1.2 基本概念和术语四、数据的存储结构 (2)链式存储结构 该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针指针字段表示。由此得到的存储表示称为链式存储结构（Linked Storage Structure）,通常借助于

11、程序语言的指针类型指针类型描述。0200020803000325 cat0325 bat0200 eat 例: (bat, cat, eat)1.2 基本概念和术语四、数据的存储结构 (3)索引存储方法 该方法通常在储存结点信息的同时，还建立附加的索引表。(4)散列存储方法 该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。1.2 基本概念和术语四、数据的存储结构 说明：(1)四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。(2)同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法

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

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

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

15、间和语句频度例：求两个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次

16、。 语句(2)作为语句(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)的数量级(阶)称为算法的渐进时间复杂度。1.4 算法和算法分析四、算法分析2算法的时间性能分析(2)问题规模和算法的时间复杂度例：算法MatrixMultidy的时间复杂度T(n)如下式所示，当n趋向无穷大时，显然有这表明，当n充分大时，T(n)和n3之比是一个不等于零的常数。即T(n)和n3是同阶的，或者说T(n)和n3的数量级相同。记作T(n)=O(n3)是算法MatrixMulti