《计算机软件技术基础 教学课件 ppt 作者 李淑芬 第2章》由会员分享，可在线阅读，更多相关《计算机软件技术基础 教学课件 ppt 作者 李淑芬 第2章（47页珍藏版）》请在金锄头文库上搜索。
1、第 2 章,数据结构概述,2.1 数据结构的基本知识,1 . 数据结构研究内容,用计算机求解的四个基本阶段,分析阶段 分析待解决的问题，抽象数学模型 设计阶段 设计求解此数学模型的算法 编码阶段 依据算法编写程序代码 测试阶段 调试并测试应用系统,举例 1,人事信息管理系统 用顺序文件存储，需要顺序查询 利用数据库组织、管理, 以备查询,编号 姓名 性别 出生年月 籍贯 学历 职务,01 张三 男 1954/9 北京 大学 教师,02 李四 男 1968/3 上海 大学 教师,举例 1 小结,数学模型：线性结构 基本操作：查询、增加、删除、更新 组织形式：内容无序 顺序查找方法 内容有序 二分
2、查找方法,举例 2,输出 n 的全排列。,举例 2小结,数学模型：树型结构 基本操作： 生成树型结构 输出树中某层的全部结点,举例 3,已知某省各县之间的交通图。现要在这个省内建立一所省级医院，问题是这所医院应该建在哪个县，才能使离这个医院最远的县到达该医院的路途最近 ?,举例 3,问题转化为求有向图的 中心点。,举例 3,设图G=(V,E) 。对于任意顶点k，我们称 E(k)= maxdist(i,k) ( iV) 为顶点 k 的偏心度，具有最小 偏心度的顶点为图G的中心点。,举例 3,d为中心点，所以省医院应该建在d县。,举例 3 小结,数学模型：有向图结构 基本操作 生成有向图 求有向图
3、的中心点,总结,数据结构主要研究诸如线性结构，树型结构及图型结构等非数值性数学模型在计算机中的表示及操作。,2 基本概念和术语,2.1 数据结构的基本知识,数据 (Data),对客观事物的符号表示 能输入到计算机中 能被计算机加工处理 符号的总称(集合) 例如：整数,实数,字符串,图像,声音,数据元素 (Data Element),是数据的基本单位 数据集合中的一个实体,一个数据元素可以由若干个数据项组成，数据项是数据不可分割的最小单位。,数据对象 (Data Object),性质相同的数据元素的集合 是数据集合的子集 整数集合即为整数数据对象 字母集合即为字母数据对象 图像集合即为图像数据对
4、象,数据、数据元素、数据对象,数据元素,数据对象,数据结构 (Data Structure),指相互之间存在一种或多种特定关系的数据元素的 集合 = Data_Structure = ( D, S ) D ：数据元素的有限集合 S ：D上关系的有限集合,举例：复数抽象数据类型,complex=(C,R) C=c1,c2 R=P P= c1为实部，c2为虚部,数据结构(Data Structure),程序设计 = 数据结构+算法,3 四种基本的数据结构,2.1 数据结构的基本知识,四种基本的数据结构,集合,关系 是否属于同一集合,四种基本数据结构,线性结构,关系 数据元素（元素）之间仅存在前后
5、关系，又称一对一关系。,四种基本数据结构,树型结构,关系 数据元素（结点）之间存在层次关系，又称一对多关系。,四种基本数据结构,图型结构,关系 数据元素（顶点）之间存在邻接关系，又称多对多关系。,4 数据的逻辑结构与存储结构,2.1 数据结构的基本知识,逻辑结构,在数据结构中描述的关系是数据元素之间的逻辑关系，又称逻辑结构。,物理结构(存储结构),数据结构在计算机中的表示（映像）被称为物理结构或存储结构，其中应该包含数据元素的内容及其关系的表示。,数据元素的映像,位,位串,数据元素的映像,结点,域,关系的映像,顺序映像 顺序存储结构 非顺序映像 链式存储结构,顺序映像,特点：借助于数据元素在存
6、储器中的位置来表示数据元素之间的逻辑关系 实现：一维数组类型,非顺序映像,特点：借助指示元素存储地址的指针来表示数据元素之间的逻辑关系 实现：指针类型或引用类型,2.2 算法分析,一.算法的概念定义,为解决特定问题所采用的步骤描述，它是指令的有限序列，其中每条指令表示一个或多个操作。,一.算法的概念特性,有穷性：算法执行有穷步后,自动停止 确定性：含义确切, 无二义性 可行性：每个基本操作均可实现 输入：零个或多个输入 输出：至少一个输出,二.算法的评价评价标准,正确性 可读性 健壮性 时间及空间的使用效率,事后统计 事先估算 选择的实现语言 编译程序的质量 硬件本身的速度 设计的算法 问题的
7、规模,二.算法的评价时间效率的量度,二.算法的评价算法的构成,控制结构,基本语句,算法,二.算法的评价语句频度,基本语句执行的次数称为语句频度,二.算法的评价语句频度,for (i=1;i=n;i+) for (j=1;j=n;j+) cij=0; for (k=1;k=n;k+) cij+=aik*bkj = f(n)=n3+n2,二.算法的评价语句频度,i=0; while (i=n) k=0 ;else k=i; = 平均 f(n)=(0+1+2+.+n-1)/n=(n-1)/2,二.算法的评价时间复杂度,设语句频度函数为 f(n) T(n) = O(f(n) T(n)表示随着n的增长与f(n)同步增长 举例：O(n) 表示随着n 的增长，时间以线性速度增长。,二.算法的评价常见的时间复杂度,O(1) O(log n) O(n) O(nlog n) O(n2) O(n3) .,二.算法的评价算法的空间复杂度,空间复杂度 S(n)= O(f(n),三.算法的描述方法,自然语言 流程图传统流程图与N-S图 类PASCAL 语言 高级语言,
