《宁夏大学_国家税收_第一章绪论》由会员分享，可在线阅读，更多相关《宁夏大学_国家税收_第一章绪论（20页珍藏版）》请在金锄头文库上搜索。
1、,,第一章,绪 论,数据结构 第一章 绪论,3,第一节 什么是数据结构,例 学生信息表格线性结构,数据结构 第一章 绪论,4,例 对弈树-树型结构,数据结构 第一章 绪论,5,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科,数据结构 第一章 绪论,6,第二节 基本概念和术语,数据(data) 数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数据元素(data element) 数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(Data Item)组
2、成。数据项是具有独立含义的最小标识单位。数据元素又称为元素、结点、记录。数据对象(data object) 数据对象是具有相同性质的数据元素的集合。 例如整数数据对象、学生数据对象。,数据结构 第一章 绪论,7,数据结构(data structure)指某一数据对象的所有数据成员之间的关系。记为： Data_Structure = D, R 其中，D 是某一数据对象，R 是该对象中所有数据成员之间的关系的有限集合。四类基本数据结构：集合：结构中的数据元素之间除了同性于一个集合的关系外，别无其他关系。线性结构：结构中的数据元素之间存在一个对一个的关系。,集合关系图,数据结构 第一章 绪论,8,树
3、形结构：结构中的数据元素存在一个对多个的关系。图状结构或网关结构：结构中的数据元素之间存在多个对多个的关系。,树形关系图,图状关系图,数据结构 第一章 绪论,9,例：树形结构的数学模型,可以定义如下数据结构：Tree=(P,R)其中：P=F1,Z1,Z2,S1,S2,S3 R=R1,R2 R1= R2=,数据结构是数据的组织形式数据元素间的逻辑关系，即数据的逻辑结构；数据元素及其关系在计算机存储内的表示，即数据的存储表示；数据的运算，即对数据元素施加的操作。,数据结构 第一章 绪论,10,数据的逻辑结构,数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；数据的逻辑结构可以看作是从具体问题抽
4、象出来的数据模型；数据的逻辑结构与数据元素本身的形式、内容无关；数据的逻辑结构与数据元素的相对位置无关。数据的逻辑结构分类线性结构 线性表非线性结构 树 图（或网络）,数据结构 第一章 绪论,11,数据的存储结构,数据的存储结构是逻辑结构用计算机语言的实现；数据的存储结构依赖于计算机语言。 顺序存储表示 链接存储表示 索引存储表示 散列存储表示,数据结构 第一章 绪论,12,抽象数据类型,数据类型 定义：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称.C语言中的基本数据类型 char int float double void构造数据类型由基本数据类型或构造数据类型组成。构造
5、数据类型由不同成分类型构成。基本数据类型可以看作是计算机中已实现的数据结构。数据类型就是数据结构，不过它是从编程者的角度来使用的。数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。,数据结构 第一章 绪论,13,抽象数据类型由用户定义，用以表示应用问题的数据模型由基本的数据类型组成, 并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离,数据结构 第一章 绪论,14,第四节 算法和算法分析,定义：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。特性： 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都
6、是确切、无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本要求：正确性 应当满足具体问题的需求可读性 方便阅读与交流健壮性 对于正确或错误的数据应具判断能力效率与低存储量需求 要达到高效低空间占用,数据结构 第一章 绪论,15,算法效率的度量,事后统计的方法事前分析估算的方法空间复杂度时间复杂度时间复杂度运行时间 = 算法中每条语句执行时间之和。每条语句执行时间 = 该语句的执行次数（频度）* 语句执行一次所需时间。语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句
7、的频度之和。,数据结构 第一章 绪论,16,例：求两个n阶方阵的乘积C = AB,void MatrixMultiply ( int Ann, int Bnn, int Cnn ) for ( int i = 0; i n; i+ ) n for ( int j = 0; j n; j+ ) n Cij = 0; n2 for ( int k = 0; k n; k+ ) n2 Cij = Cij + Aik * Bkj; n3 + n3 + 2n2 + 2n,数据结构 第一章 绪论,17,算法中所有语句的频度之和是矩阵阶数n的函数 T(n) = n3 + 2n2 + 2n 一般地，称 n 是
8、问题的规模。则时间复杂度 T(n) 是问题规模 n 的函数。当n趋于无穷大时，把时间复杂度的数量级（阶）称为算法的渐进时间复杂度 T(n) = O(n3)渐进时间复杂度大O表示法加法规则 （主要针对顺序程序段 ） T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m)c log2n n nlog2n n2 n3 2n 3n n!,数据结构 第一章 绪论,18,变量计数,x = 0; y = 0;for ( int k = 0; k n; k + ) x +;for ( int i = 0; i n; i+ ) for ( int j = 0; j n;
9、j+ ) y +;,T1(n) = O(1),T2(n) = O(n),T3(n) = O(n2),T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2),例：求渐近时间复杂度,数据结构 第一章 绪论,19,乘法规则 （主要针对嵌套程序段 ）则渐进时间复杂度为：T(n)=Ti(n)*Tj(k)=O(n)*O(k),for ( int i = 1; i = n; i+ ) for ( int j = 1; j =k; j+ ) y +;,数据结构 第一章 绪论,20,空间复杂度存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等)变量所占空间可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过new和delete命令动态使用空间,完,
