宁夏大学国家税收第一章绪论.ppt

数据结构 第一章 绪论 第一章 绪 论 第一节 什么是数据结构 例 学生信息表格—线性结构 例 对弈树---树型结构 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科 第二节 基本概念和术语 数据(data) 数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数据元素(data element) 数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。 有时一个数据元素可以由若干数据项(Data Item)组成。数据项是具有独立含义的最小标识单位。 数据元素又称为元素、结点、记录。 数据对象(data object) 数据对象是具有相同性质的数据元素的集合。 例如整数数据对象、学生数据对象。 数据结构(data structure) 指某一数据对象的所有数据成员之间的关系。 记为： Data_Structure = {D, R} 其中，D 是某一数据对象，R 是该对象中所有数据成员之间的关系的有限集合。 四类基本数据结构： 集合：结构中的数据元素之间除了同性于一个集合的关系外，别无其他关系。 线性结构：结构中的数据元素之间存在一个对一个的关系。 树形结构：结构中的数据元素存在一个对多个的关系。 图状结构或网关结构：结构中的数据元素之间存在多个对多个的关系。 例：树形结构的数学模型 可以定义如下数据结构：Tree=(P,R) 其中：P={F1,Z1,Z2,S1,S2,S3} R={R1,R2} R1={F1,Z1F1,Z2} R2={Z1,S1Z1,S2Z2,S3} 数据的逻辑结构 数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关； 数据的逻辑结构可以看作是从具体问题抽象出来的数据模型； 数据的逻辑结构与数据元素本身的形式、内容无关； 数据的逻辑结构与数据元素的相对位置无关。 数据的逻辑结构分类 线性结构 线性表 非线性结构 树 图（或网络） 数据的存储结构 数据的存储结构是逻辑结构用计算机语言的实现； 数据的存储结构依赖于计算机语言。 顺序存储表示 链接存储表示 索引存储表示 散列存储表示 抽象数据类型 数据类型 定义：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称. C语言中的基本数据类型 char int float double void 构造数据类型由基本数据类型或构造数据类型组成。 构造数据类型由不同成分类型构成。 基本数据类型可以看作是计算机中已实现的数据结构。 数据类型就是数据结构，不过它是从编程者的角度来使用的。 数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。 抽象数据类型 由用户定义，用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的服务（或称操作） 信息隐蔽和数据封装，使用与实现相分离 第四节 算法和算法分析 定义：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 特性： 输入 有0个或多个输入 输出 有一个或多个输出(处理结果) 确定性 每步定义都是确切、无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本 要求： 正确性 应当满足具体问题的需求 可读性 方便阅读与交流 健壮性 对于正确或错误的数据应具判断能力 效率与低存储量需求 要达到高效低空间占用 算法效率的度量 事后统计的方法 事前分析估算的方法 空间复杂度 时间复杂度 时间复杂度 运行时间 = 算法中每条语句执行时间之和。 每条语句执行时间 = 该语句的执行次数（频度）* 语句执行一次所需时间。 语句执行一次所需时间取决于机器的指令性能和速度和编译所产生的代码质量，很难确定。 设每条语句执行一次所需时间为单位时间，则一个算法的运行时间就是该算法中所有语句的频度之和。 例：求两个n阶方阵的乘积C = A?B void MatrixMultiply ( int A[n][n], int B[n][n], int C[n][n] ) { for ( int i = 0; i n; i++ ) … n for ( int j = 0; j n;