数据结构(大话).ppt

数 据 结 构 成绩评定 ◆比例 ①平时：30% 课堂，项目，编程 ②考试：70% 18周，闭卷，时间95分钟 参考书籍 参考书籍 第1章　绪　论 1.1 什么是数据结构 1.2 学习数据结构的意义 1.3 数据结构涵盖的主要内容 1.4 什么是抽象数据类型 1.5 算法效率的度量 数据结构产生的背景 例3多叉路口交通灯管理问题 1.1 什么是数据结构 是相互之间存在一种或多种特定关系的数据元素的集合，表示为： 数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息 ）。 数据元素(data element)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。 数据项(Data item)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性 等）。 数据项(Data object)——性质相同的数据元素的集合。 1.2 学习数据结构的意义 　　计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。 　　数据结构是一门学科，针对非数值计算的程序设计问题，研究计算机的操作对象以及它们之间的关系和操作等等。 1.3 数据结构涵盖的内容 （1） S=(D, R) D={ a, b, c, d, e, f } R={(a,e), (b,c), (c,a), (e,f), (f,d)} d1 d5 d2 d4 d3 　　　答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。 答：在数据的逻辑结构上定义的操作算法。 它在数据的存储结构上实现。 1.4 什么是抽象数据类型 1.4.1 数据类型与抽象数据类型的区别 1.4.2 抽象数据类型如何定义 例：给出自然数(Natural Number )的抽象数据类型定义。 1.4.3 抽象数据类型如何表示和实现 抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。 1.5 算法效率的度量 1.5.1 什么是算法？如何评判算法的好坏？ 1.5.2 时间复杂度和空间复杂度如何表示？ 1.5.3 计算举例 1.5.1 什么是算法？如何评判一个算法的好坏？ 算法中实现基本操作的语句（基本语句）重复执行的次数，称为算法的频度。 记作：T(n)=O(f(n)) 随问题规模n的增大，算法的频度T(n)和f(n)的增长率同阶。 例1： x+=5; 单个语句的频度为1，则 程序段的时间复杂度为T(n)=O(1)。 1.5.3 计算举例 例题 s=0 /* 1 */ for (i=0; in; i ++) /* n+1 */ for (j=0; jm; j ++) /* n(m+1) */ s+=B [i][j]; /* n*m */ sum=s /* 1 */ 时间复杂度: 1.5.2 时间复杂度和空间复杂度如何表示？ 本章小结 数据结构课程—— 数据结构＋算法＝程序，涉及数学、计算机硬件和软件。 数据结构定义——指互相有关联的数据元素的集合，可用data_Structure=(D,R)表示。 数据结构内容——数据的逻辑结构、存储结构和基本运算 数据结构学习工具——抽象数据类型和伪码（类C） 算法效率指标——时间效率和空间效率 练习： ①复习C语言，重点是结构体和递归概念，链表操作。 练习 计算下列程序段的时间复杂度： 1) i=s=0 while(sn) { i++; S+=i; } 2）i=1； while(i=n) i=i*2; 数据结构课程的起点： 第3章 线性表 3.1 线性表的逻辑结构 3.2 线性表的顺序表示和实现 3.3 线性表的链式表示和实现 3.4 应