数据结构幻灯片教案（正式版）课件

《数据结构幻灯片教案（正式版）课件》由会员分享，可在线阅读，更多相关《数据结构幻灯片教案（正式版）课件（469页珍藏版）》请在金锄头文库上搜索。

1、数据结构,20102011学年 第二学期 计算机科学系 冯 韵,第一章 绪论 第二章 线性表 第三章 栈和队列 第四章 串 第五章 数组和广义表 第六章 树和二叉树 第七章 图 第八章 查找 第九章 排序,目 录,课程学习的是什么？,学习在思考问题时， 不仅按人的逻辑方式思考，也按计算机的逻辑思维方式思考,学习在解决问题时， 不仅考虑人的处理方式，也要考虑计算机的处理方式,对你而言，是一场有趣的思维体操； 对我而言，是一座顺畅沟通的桥梁,1968年在美国开设。它随着大型程序的出现而出现 我国1980s年代初开设。它是计算机专业的核心课程，考研必考。 学习数据结构的目的： 提高复杂程序设计的能力

2、 培养算法设计能力 为后继课程（如操作系统、编译原理等）打基础,数据结构课程的发展历史及课程的重要性,成 绩 评 定,一、考勤 10% 二、平时成绩 20% （含作业和实验） 三、期末考试成绩 70%,学时分配,第一章 绪论,数据结构 第1章 绪论,教学目的 了解：抽象数据类型的定义、表示和实现方法。 理解：名词、术语的含义，数据的逻辑结构和存储结构之间的关系，算法的概念及5个特性。 掌握：算法时间复杂度的估算方法 重点难点 重点：ADT、算法的概念、描述方法以及评价标准 难点：ADT的表示与实现、算法时间复杂度的估算,用计算机处理的实际问题可分为两大类问题： 数值计算 非数值计算 数值计算问

3、题： 在计算机发展初期，人们主要应用计算机来完成科学计算，即处理数值计算问题，对于这类问题，可以通过抽象出合适的数学模型，然后设计一个相应的算法来解决。 在建筑设计时计算梁结构的应力要求解线性方程组 预报人口增长情况时要求解微分方程等。 非数值计算问题： 但是随着计算机应用领域的不断扩大，计算机更多地应用于处理非数值计算问题，这类问题涉及到数据元素间复杂的相互关系，其数学模型一般无法用数学方程来描述。,一、什么是数据结构,现实中对象之间的关系,线性关系：如列车中各车箱之间的关系、排队买车票人之间的关系、一叠盘子中各盘子之间的关系等。 层次关系：如学校的组织结构、人的辈分关系等。 网状关系：如城

4、市铁路交通网、电话网、计算机网络等。,实际问题中对象之间的关系,关系：线性 1 : 1 特征：一个直接前趋， 一个直接后继,例1、学生名册 （线性结构） 1对1,例2、课题小组 （树形结构） 1对多 组成： 1名教师指导1至3名研究生，1名研究生带1至2名 学生。,关系：树形 1 : n 特征：一个直接前趋， 多个直接后继,实际问题中对象之间的关系,例3：交通图的最短路径问题 （图形结构）多对多,关系：图形 n : n 特征：多个直接前趋， 多个直接后继。,实际问题中对象之间的关系,狭义：数据的组织结构 广义：是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间关系和操作的一门学科。

5、 （三个要素：对象、关系及操作（运算）,结论：数据结构的定义,？为什么要学习数据结构 解决非数值问题的首要任务是选取一种合适的数据结构表示该问题，然后才考虑如何编写有效的算法。,？数据结构研究什么 研究各种数据结构的性质，不仅研究数据的逻辑结构和物理结构以及它们之间的相互关系、而且对每一种结构建立相适应的运算、并使用某种高级语言给出各种运算的算法、分析算法的效率（简单分析），同时也研究各种数据结构在计算机科学和软件工程中的某些应用，讨论数据分类和检索的技术。,逻辑结构+物理结构相互关系，运算算法效率应用数据分类和检索技术,（一）数据： 1、数据(Data)：是对客观事物的符号表示，能够被计算机

6、识别、存储和加工处理。它是计算机程序加工的“原料”。 2、数据元素(Data Element)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 (也称为：记录，元素，结点，顶点等) 3、数据项(Data Object)：组成数据元素的有特定意义的最小单位 。 4、数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。 数据的三个层次,二、基本概念和术语,数据 数据元素 数据项,第1章 绪论,（二）数据结构： 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。数据结构主要指逻辑结构和物理结构。 1、基本结构： 1）集合：结构中的数据元素除了同

7、属于一种类型外，别无其它关系。 2）线性结构：结构中的数据元素之间存在一对一的关系。 3）树形结构：结构中的数据元素之间存在一对多的关系。 4）图状结构或网状结构： 结构中的数据元素之间存在多对多的关系。 2、数据结构的形式定义： 数据结构Data_Structure是一个二元组 Data_Structure （D，R）, 其中，D是数据元素的有限集，R是D上关系的有限集。 例: D_S=(D,S) 其中：D= A,B,C S= ,第1章 绪论,3、数据的逻辑结构：（本质） 对数据结构的抽象的数据描述，数据之间的相互关系称为逻辑结构。 逻辑结构可分为:线性结构和非线形结构，也可分为如上四种基本

8、结构。 4、数据的物理结构： 数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。 数据结构在计算机中有两种不同的表示方法：顺序表示和非顺序表示。 由此得出两种不同的存储结构：顺序存储结构和链式存储结构。 ）顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 ）链式存储结构：借助指示元素存储地址的指针（Pointer）表示数据元素之间的逻辑关系。 ）存储结构的描述虚拟存储结构 数据结构的三要素：逻辑结构，存储结构，运算（对数据施加的操作）。,第1章 绪论,（三）数据类型（data type） 、数据类型（data type）: 是一个值的集合和定义在这个值集上的

9、所有的操作。 、数据类型的分类： 1）原子类型（非机构的）：原子类型的值是不可分解的 2）结构类型：结构类型的值是由若干成分按某种结构组成 的（如数组）。 在一种程序设计语言中，变量所具有的数据种类。 例子、在C语言中： 数据类型：基本类型和构造类型 基本类型：整型、浮点型、字符型 构造类型：数组、结构、联合、指针、枚举型、自定义,第1章 绪论,（四）抽象数据类型 ADT 1、ADT的概念： 抽象数据类型:（Abstract Data Type）ADT:是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型和数据类型实质上是一个概念，它仅取决于数据类型的逻辑性，而与其在计算机内部如何表示和

10、实现是无关的。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。 2、ADT的分类： 1）原子类型:变量的值是不可分解的。 2）固定聚合类型:变量的值由确定数目的成分按某种结构组成。 3）可变聚合类型:其值的成分数目不确定。,第1章 绪论,3、ADT的形式定义 1）我们用一个三元组来表示一个抽象数据类型 （D，S，P） D是数据对象， S是D上的关系集， P是对D的基本操作。 2）格式： ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名 数据对象和数据关系的定义用伪码描述。 数据基本操作的定义格式：

11、 基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述,第1章 绪论,3）例子：抽象数据类型三元组的定义：ADT Triplet数据对象：D=e1,e2,e3|e1,e2,e3ElemSet(定义了关系运算的某个集合)数据关系：R1=,基本操作：InitTriplet( /由InitTriplet分配三个元素存储空间 /基本操作的函数原型说明 Status InitTriplet(Triplet i=n; +i)for(j=1; j=n; +j)cij=0;for(k=1; k=n; +k)cij+=aik*bkj; ,（四）时间复杂度,时间复杂度：一般情况下，算法中基本操作重

12、复执行的次 数是问题规模n 的某个函数f(n)，算法的时间量度记作 T(n)=O(f(n)，它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度（Asymptotic Time Complexity），简称时间复杂度T(n)。 1）算法时间：是由控制结构（顺序，分支，循环）和原操作 （必须的操作）的决定的。 2）语句的频度：是该语句重复执行的次数。,第1章 绪论,1、时间复杂度的定义,2、时间复杂度的计算,1）依据： 所含基本操作执行的次数成正比算法执行时间与算法中。 2）方法： 找出算法中所含基本操作，列出关于基本操作执行次数（称语句频度）的函数f(

13、n)，取出极限即得。,例1：求两个n阶方阵的乘积C=AB，其算法如下： #define n 100 void MatrixMultiply(int Ann,int Bnn,int Cnn) int i,j,k for (i=1;i=n;+i) n+1 for (j=1;j=n;+j) n*(n+1) Cij=0; n2 for (k=1;k=n,k+) n2(n+1) Cij=Cij+aik*bkj; n3 f(n)=2n3+3n2+2n+1 limf(n)= n3 T(n)=O(n3) 例2：（a）+x;s=0; T(n) = O(1) （b）for (i=1;i=n;+i) +x;s+=x

14、; T(n) = O(n) （c）for (j=1;j=n;+j) for (k=1;k=n;k+)+x;s+=x; T(n) = O(n2),3、例子,常数阶O(1) 对数阶O(1og2n) 线性阶O(n) 线性对数阶O(nlog2n) O(n2)、O(n3)、O(nk)、 指数阶O(2n)。,4、常见的时间复杂度,空间复杂性(Space Complexity)： 作为算法所需存储空间的量度，记作S(n)=O(f(n) 其中n为问题的规模（或大小）。一个程序上机执行所需空间包括：程序指令存储的空间数据存储的空间变量分配的空间,返回子目录,第1章 绪论,作业： P7 1.1 1.2 P8 1.

15、8 P10 1.16,（五）算法的空间复杂度：,实际问题：学生学籍管理,学生的自然情况： 包括学号、姓名、性别、出生日期、政治面貌和家庭住址等数据项。 功能要求 插入：将某学生的基本信息插入到登记表中； 删除：将满足条件的基本信息删除； 修改：对基本信息的数据项进行修改； 查询：查找满足条件的学生； 输出：将登记表中的全部（或满足条件）基本信息输出。,学生学籍登记表,问题逻辑结构,姓 名,性别,出生年月,党员,学号,丁一,男,78.1,是,0101,李二,男,90.5,否,0102,张三,男,86.4,否,0103,孙红,女,81.7,是,0104,王冬,女,74.12,否,0105,第二章

16、线性表,第一节 线性表的类型定义 第二节 线性表的顺序表示和实现 第三节 线性表的链式表示和实现1(单链表) 第四节 线性表的链式表示和实现2(静态单链表、循环链表、双向链表)线性表的应用,Return,数据结构 第2章 线性表,考虑：,数据元素之间的关系是什么？数据如何表示？,数据如何存储？,数据如何处理？,教学目的 理解：线性表的逻辑结构特性。 理解：线形表的概念。 掌握：线形表的ADT定义及各种操作。 重点难点 重点：线形表的ADT定义及各种操作。 难点：线形表的ADT定义及各种操作。,第一节 线性表的类型定义,第2章 第1节 线性表的类型定义,线性结构的特点： 在数据元素的非空有限集中