数据结构第一章.ppt

1、数据结构,主 讲 衡 霞 ,数据结构,主 讲 邓万宇 ,Data Structure,参考书： 数据结构-C语言描述 耿国华编 西安电子科技大学出版社 数据结构C语言版 严蔚敏 吴伟民 清华大学出版社 数据结构题集 严蔚敏 清华大学出版社 C语言程序设计 王曙燕 科学出版社,课时安排： 数据结构48学时 上机12学时 上机地点：计算机系网络实验室（2#实验楼427）,第一章 绪 言,数据与数据结构 逻辑结构与存储结构 算法的描述和分析,1.1 数据与数据结构,书目文件,线性表,操作对象：书目信息 元素间的关系：顺序排列,程序=数据结构+算法,例1 书目自动检索系统,Programs = Dat

2、a Structures + Algorithm,例2 人机对奕问题,操作对象： 格局（棋盘状态） 元素间的关系： 树（由比赛规则决定）,树,C、E为单行道 AB和EC可同时通行 EB和AD不能同时通行,规定：每个顶点表示一种通路 顶点间的连线表示：两条通路不能同时通行,图的顶点染色：每个顶点染一种颜色，有线相连的顶点不同色,多叉路口交通灯管理问题,图,数据结构概念: 是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。,D.S = (D,R),其中D为数据元素的有限集，R是D上关系的有限集合,是相互之间存在一种或多种特定关系(称为结构)的数据元素的集合（或

3、称带结构的数据元素的集合）。,数据结构形式化定义：,1.2 基本概念和术语 数据（data) 所有能输入到计算机中去的描述客观事物的符号的总称 数据元素（data element） 组成数据的基本单位,是数据集合中的个体,它也可以再由 不可分割的数据项组成 数据项（data item） 数据的不可分割的最小单位,数据元素可以是数据项的集合 数据对象（data object) 性质相同的数据元素的集合 数据结构（data structure) 数据元素和数据元素关系的集合,数据项,数据元素,1.3 逻辑结构与存储结构 逻辑结构 数据元素之间抽象化的相互关系,存储结构（物理结构） 数据的逻辑结构在

4、计算机存储器中的存储方式,逻辑结构四种基本分类,集合: 数据元素间除“同属于一个集合”外，无其它关系,线性结构: 一个对一个，如线性表、栈、队列,树形结构: 一个对多个，如树,图状结构: 多个对多个，如图,存储结构分类,顺序存储结构: 借助元素在存储器中的相对位置来表示数据元素间的 逻辑关系,链式存储结构: 借助指示元素存储地址的指针表示数据元素间的逻辑 关系,存储结构,逻辑结构,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,抽象数据类型 数据类型 指某种程序设计语言所允许使用的变量种类 一个数据类型不仅定义了相应变量可以设定的值的集合和 存储方法,

5、而且还规定了对变量允许进行的一组运算及其规则。,抽象数据类型 (Abstract Data Type, ADT) 是指一个数学模型以及定义在此数学模型上的一组操作 是初等数据类型基础上的进一步抽象,【抽象数据类型举例】线性表 数学模型：数据元素的集合 关系：该集合内的元素有这样的关系：除第一个和最后一个 外，每个元素有唯一的前趋和唯一的后继。 允许操作：插入一个元素、删除一个元素、查找等。,数学模型,抽象数据类型,算法、数据结构,源程序,运用ADT概念来设计软件的过程,1.4 算法的描述和分析 算法（algorithm） 解决某一特定问题的具体步骤的描述，是指令的有限序列 算法特性,算法的描述

6、：采用C语言 算法的评价：衡量算法优劣的标准 正确性 可读性 健壮性 效率与低存储量,数据结构的不同直接影响算法的选择和效率,算法效率 用依据该算法的程序在计算机上执行所消耗的时间来度量,事后统计 利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分 缺点： 必须先运行依据算法编制的程序 所得时间统计量依赖于硬件、软件等环境因素,掩盖算法本身的优劣,事前分析估计 一个高级语言程序在计算机上运行所消耗的时间取决于 依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，所

7、以使用绝对时间单位衡量算法效率不合适,主要考虑两条标准： 算法所需的存储量、算法实现所需的运算量,空间复杂度： S(n)=O(f(n) 算法所需存储空间的量度 一个上机执行的程序除需要存储空间来寄存本身所用指 令、常数、变量和输入数据外，也需要一些对数据进行操作的 工作单元和存储一些为实现计算所需信息的辅助空间。,时间复杂度： T(n)=O(f(n) (算法耗费的时间 = 算法中每条语句的执行时间之和) 随问题规模n的增大算法执行时间的增长率和f(n)的增长率相 同 从算法中选取一种对于所研究的问题来说是基本操作的 原操作，以该基本操作在算法中重复执行的次数(语句的频度) 作为算法运行时间的衡

8、量准则。,算法时间复杂度的计算方法 假定每条语句的执行时间为单位时间。算法的时间复杂度是该算法中所有语句的执行频度之和的数量级估算。,temp = i; i = j; j = temp;,T(n)=O(1),当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度所决定的。,x=0;y=0; for (k=1;k=n;k+) x+; for (i=1;i=n;i+) for (j=1;j=n;j+) y+;,T(n)=O(n2),数量级,for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik

9、*bkj; ,T(n)=O(n3),例7.5 求两个矩阵A和B的乘积C,=,C00=A00*B00+A01*B10+A02*B20,C01=A00*B01+A01*B11+A02*B21,14,32,C10=A10*B00+A11*B10+A12*B20,32,C11=A10*B01+A11*B11+A12*B21,77,Cij+=Aik*Bkj;,main ( ) int A23=1,2,3,4,5,6; int B32=1,4,2,5,3,6; int C22=0,0,0,0, i, j,k; ,Array C=A*B: 14 32 32 77,for (i=0; i2; i+) for

10、(j=0; j2; j+) for(k=0;k3;k+) Cij+=Aik*Bkj;,printf(“Array C=A*B:n); for (i=0; i2; i+) for (j=0; j2; j+) printf(%6d, Cij); printf(n); ,i=1; j=0; while (i+jj) j+; else i+; ,i=1; k=0; while (i= n-1) k=k+10*i; i+; ,i=1; k=0; do k=k+10*i; i+; while (i= n-1);,i=1; k=0; while (i= n-1) i+; k=k+10*i; ,O(n),鸡兔问题：鸡兔共30只，脚共有90个。,main() int i,j; ,main() int i,j; ,main() int i,j; i=30-j; if ( 2*i+4*j=90 ) printf(x=%d,y=%d,i,j); ,要点：循环结构解决枚举类问题,频度：22,频度：30,频度：900,for(i=0;i30;i+) for(j=0;j30;j+),if( 2*i+4*j=90 ,for(i=0;i30;i+), j=30-i; if ( 2*i+4*j=90 ) printf(x=%d,