宁夏大学国家税收绪论课件

1、宁夏大学国家税收绪论宁夏大学国家税收绪论1教学辅助课件教学辅助课件主讲人：牛三勇主讲人：牛三勇宁夏大学宁夏大学 经济管理学院经济管理学院 工商管理系工商管理系宁夏大学国家税收绪论宁夏大学国家税收绪论2第一章第一章绪绪 论论工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大学国家税收绪论3第一节第一节 什么是数据结构什么是数据结构n例例 学生信息表格学生信息表格线性结构线性结构 学学 号号 姓姓 名名 性性别别 籍籍 贯贯 出出生生年年月月 1 98131 刘刘激激扬扬 男男 北北 京京 1979.12 2 98164 衣衣春春生生 男男 青青 岛岛 1979.07 3 98165 卢

2、卢声声凯凯 男男 天天 津津 1981.02 4 98182 袁袁秋秋慧慧 女女 广广 州州 1980.10 5 98224 洪洪 伟伟 男男 太太 原原 1981.01 6 98236 熊熊南南燕燕 女女 苏苏 州州 1980.03 7 98297 宫宫 力力 男男 北北 京京 1981.01 8 98310 蔡蔡晓晓莉莉 女女 昆昆 明明 1981.02 9 98318 陈陈 健健 男男 杭杭 州州 1979.12工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大学国家税收绪论4n例例 对弈树对弈树-树型结构树型结构工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大学国

3、家税收绪论5n数据结构是一门研究非数值计算的程序设计问题中计算机的操作数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科对象以及它们之间的关系和操作等的学科工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大学国家税收绪论6第二节第二节 基本概念和术语基本概念和术语n数据数据(data)数据是信息的载体，是描述客观事物的数、字符、以及所有能输入数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。到计算机中，被计算机程序识别和处理的符号的集合。n数据元素数据元素(data element) 数

4、据的数据的基本单位基本单位。在计算机程序中常作为一个整体进行考虑和处理。在计算机程序中常作为一个整体进行考虑和处理。n有时一个数据元素可以由若干有时一个数据元素可以由若干数据项数据项(Data Item)组成。组成。数据数据项项是是具有独立含义的最小标识单位具有独立含义的最小标识单位。n数据元素又称为元素、结点、记录。数据元素又称为元素、结点、记录。数据对象数据对象(data object)数据对象是具有相同性质的数据元素的集合。数据对象是具有相同性质的数据元素的集合。 例如整数数据对象、学生数据对象。例如整数数据对象、学生数据对象。工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大

5、学国家税收绪论7n数据结构数据结构(data structure)指某一数据对象的所有数据成员之间的关系。指某一数据对象的所有数据成员之间的关系。记为：记为： Data_Structure = D, R 其中，其中，D 是某一数据对象，是某一数据对象，R 是该对象中所有数据成员之间的关是该对象中所有数据成员之间的关系的有限集合。系的有限集合。四类基本数据结构：四类基本数据结构：n集合：结构中的数据元素之间除了同性于一个集合的关系外，别集合：结构中的数据元素之间除了同性于一个集合的关系外，别无其他关系。无其他关系。n线性结构：结构中的数据元素之间存在一个对一个的关系。线性结构：结构中的数据元素之

6、间存在一个对一个的关系。集合关系图集合关系图线性关系图线性关系图工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大学国家税收绪论8n树形结构：结构中的数据元素存在一个对多个的关系。树形结构：结构中的数据元素存在一个对多个的关系。n图状结构或网关结构：结构中的数据元素之间存在多个对多个的图状结构或网关结构：结构中的数据元素之间存在多个对多个的关系。关系。树形关系图树形关系图图状关系图图状关系图工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大学国家税收绪论9例：树形结构的数学模型例：树形结构的数学模型可以定义如下数据结构：可以定义如下数据结构：Tree=(P,R)其中：其中：

7、P=F1,Z1,Z2,S1,S2,S3 R=R1,R2 R1= R2=F1S3Z2Z1S2S1数据结构数据结构是数据的是数据的组织形式组织形式n数据元素间的数据元素间的逻辑关系逻辑关系，即数据的，即数据的逻辑结构逻辑结构；n数据元素及其关系在计算机存储内的表示，即数据的数据元素及其关系在计算机存储内的表示，即数据的存存储表示储表示；n数据的运算，即对数据元素施加的数据的运算，即对数据元素施加的操作操作。工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大学国家税收绪论10数据的逻辑结构数据的逻辑结构n数据的逻辑结构数据的逻辑结构从逻辑关系上描述数据从逻辑关系上描述数据，与数据的存储无关

8、与数据的存储无关；n数据的逻辑结构可以看作是数据的逻辑结构可以看作是从具体问题抽象出来的数据模型从具体问题抽象出来的数据模型；n数据的逻辑结构数据的逻辑结构与数据元素本身的形式、内容无关与数据元素本身的形式、内容无关；n数据的逻辑结构与数据元素的相对位置无关数据的逻辑结构与数据元素的相对位置无关n数据的逻辑结构分类数据的逻辑结构分类n线性结构线性结构u 线性表线性表n非线性结构非线性结构u 树树u 图（或网络）图（或网络）工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大学国家税收绪论11数据的存储结构数据的存储结构n数据的存储结构是逻辑结构用计算机语言的实现；数据的存储结构是逻辑结

9、构用计算机语言的实现；n数据的存储结构依赖于计算机语言。数据的存储结构依赖于计算机语言。u 顺序存储表示顺序存储表示u 链接存储表示链接存储表示u 索引存储表示索引存储表示u 散列存储表示散列存储表示工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大学国家税收绪论12抽象数据类型抽象数据类型n数据类型数据类型 定义：定义：一组性质相同的值的集合一组性质相同的值的集合, 以及定义于这个值集合上的一以及定义于这个值集合上的一组操作的总称组操作的总称.nC语言中的基本数据类型语言中的基本数据类型 char int float double voidn构造数据类型由构造数据类型由基本数据类型

10、基本数据类型或或构造数据类型构造数据类型组成。组成。n构造数据类型由构造数据类型由不同成分类型不同成分类型构成。构成。n基本数据类型可以看作是基本数据类型可以看作是计算机中已实现的数据结构计算机中已实现的数据结构。n数据类型就是数据结构，不过它是从编程者的角度来使用的。数据类型就是数据结构，不过它是从编程者的角度来使用的。n数据类型是模板，必须定义属于某种数据类型的变量，才能参加数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。运算。工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大学国家税收绪论13抽象数据类型抽象数据类型u由用户定义，用以表示应用问题的由用户定义，用以

11、表示应用问题的数据模型数据模型u由由基本的数据类型基本的数据类型组成组成, 并包括并包括一组相关的服务一组相关的服务（或称操作）（或称操作）u信息隐蔽信息隐蔽和和数据封装数据封装，使用与实现相分离，使用与实现相分离工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大学国家税收绪论14第四节第四节 算法和算法分析算法和算法分析n定义：定义：是对特定问题求解步骤的一种描述，它是指令的有限序列，是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。其中每一条指令表示一个或多个操作。n特性：特性：u 输入输入 有有0个或多个输入个或多个输入u 输出输出 有一个或

12、多个输出有一个或多个输出(处理结果处理结果)u 确定性确定性 每步定义都是确切、无歧义的每步定义都是确切、无歧义的u 有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束u 有效性有效性 每一条运算应足够基本每一条运算应足够基本要求：要求：u正确性正确性 应当满足具体问题的需求应当满足具体问题的需求u可读性可读性 方便阅读与交流方便阅读与交流u健壮性健壮性 对于正确或错误的数据应具判断能力对于正确或错误的数据应具判断能力u效率与低存储量需求效率与低存储量需求 要达到高效低空间占用要达到高效低空间占用工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大学国家税收绪论15算法效率

13、的度量算法效率的度量n事后统计的方法事后统计的方法n事前分析估算的方法事前分析估算的方法u空间复杂度空间复杂度u时间复杂度时间复杂度u时间复杂度时间复杂度n运行时间运行时间 = 算法中每条语句执行时间之和。算法中每条语句执行时间之和。n每条语句执行时间每条语句执行时间 = 该语句的执行次数（频度）该语句的执行次数（频度）* 语句执行一次语句执行一次所需时间。所需时间。n语句执行一次所需时间取决于语句执行一次所需时间取决于机器的指令性能和速度机器的指令性能和速度和和编译所产编译所产生的代码质量生的代码质量，很难确定。很难确定。n设每条语句执行一次所需时间为单位时间，则一个算法的运行时设每条语句执

14、行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。间就是该算法中所有语句的频度之和。工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大学国家税收绪论16例：例：求两个求两个n阶方阵的乘积阶方阵的乘积C = A Bvoid 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

15、 + n3 + 2n2 + 2n 工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大学国家税收绪论17n算法中所有语句的频度之和是算法中所有语句的频度之和是矩阵阶数矩阵阶数n的函数的函数 T(n) = n3 + 2n2 + 2n n一般地，称一般地，称 n 是问题的规模。则时间复杂度是问题的规模。则时间复杂度 T(n) 是问题规模是问题规模 n 的函数。的函数。n当当n趋于无穷大时，把时间复杂度的数量级（阶）称为算法的渐趋于无穷大时，把时间复杂度的数量级（阶）称为算法的渐进时间复杂度进时间复杂度 T(n) = O(n3)n渐进时间复杂度渐进时间复杂度n大大O表示法表示法n加法规则加法

16、规则 （主要（主要针对顺序程序段针对顺序程序段 ） 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; 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)例：求渐近时间复杂度例：求渐近时间复杂度工商管理系工商管理系 牛三勇牛三勇宁夏大学国家税收绪论宁夏大学国家税收绪论19n乘法规则乘法规则 （主要（主要针对嵌套程序段针对嵌套程序段 ）则渐进时间复杂度为：则渐进时间复杂度为：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 +;工商管理系工商管理系 牛三