数据结构演示课件第一章节.ppt

数据结构Data Structure 　 河南大学软件学院 ;第1章 序 论;1.1 什么是数据结构;例如: 数值计算的程序设计问题 ;１．计算机解决具体问题的步骤;２．寻求数学模型;例１　图书馆书目检索系统;例２　人机对弈问题　;例３　多叉路口交通灯的管理;例３　多叉路口交通灯的管理; 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。;Q2：学习数据结构有什么用？;3. 研究涉及范围;1.2 数据结构基本概念;数据：;数据元素:;数据项：;术语：数据、数据元素和数据项;Q1：什么是数据结构？;例1-4（p5)：在计算机科学中，复数可取如下定义：复数是一种数据结构：;集合结构： 仅同属一个集合 线性结构: 一对一（1:1) 树 结 构: 一对多（1:n) 图 结 构: 多对多 (m:n);解释1： 什么叫数据的逻辑结构？;例：用图形表示下列数据结构。;（2） S=(D, R) D={di | 1≤i≤5} R={di , dj , ij}; 逻辑结构是数学上的抽象概念，而研究数据结构是为了进行程序设计，所以完整的数据结构定义还应该包括它在计算机中的表示或实现。 数据的逻辑结构在计算机中的表示就称为数据的物理结构。;解释2：什么叫数据的物理结构？;数据元素的映象方法：;顺序映象:;链式映象;例：（见教材P6）复数3.0－2.3i 的两种存储方式：; 在不同的编程环境中，存储结构可有不同的描述方法。 当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。 ;Q1 数据类型与抽象数据类型的区别？ Q2 抽象数据类型如何定义？ ;Q1 数据类型与抽象数据类型的区别？;Q2 抽象数据类型如何定义？;解释3：什么是数据的运算？;例：给复数的抽象数据类型定义;注意： 由于数据结构是和它的操作集分不开的，因此以后我们对数据结构的定义均包括它们操作的定义，也就是说直接将它们定义为抽象数据类型。;1.3 抽象数据类型的表示与实现;抽象数据类型如何表示和实现？;typedef struct { float realpart； float imagpart； }complex；;float GetReal( cpmplex Z )； // 返回复数 Z 的实部值;// -----基本操作的实现;1.4 算法和算法分析;答：算法是解决某一特定类型问题的有限运算序列。是一系列输入转换为输出的计算步骤。;二、算法设计的原则;1． 正确性;2. 可读性;3．健壮性;三、 算法效率的度量; 事前分析估算法和 算法执行时间相关的因素： ; 一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。;如何估算 算法的时间复杂度？;算法 = 控制结构 + 原操作;例：; void mult(int a[], int b[], int c[] ) { // 以二维数组存储矩阵元素，c 为 a 和 b 的乘积 for (i=1; i=n; ++i) for (j=1; j=n; ++j) { c[i,j] = 0; for (k=1; k=n; ++k) c[i,j] += a[i,k]*b[k,j]; } //for } // mult;例二：赋值语句;例三 起泡排序;注1 O（）为渐近符号。 注2 空间复杂度S(n)按数量级递增顺序也与上表类同。;四、算法的存储空间需求