[研究生入学考试]北京邮电大学-数据结构讲义.pptVIP

数据结构 题型(1) 题型(2) 第一章 绪论 基本概念 学习数据结构的意义 基本术语 数据 被计算机加工处理的对象。 数据元素（记录、表目） 数据的基本单位，是数据集合中的一个有意义的个体。 数据项 一个数据元素可由若干个数据项组成。 基本术语2 数据对象 是性质相同的数据元素的集合，是数据的一个子集。 学号 姓名 班号 性别 出生日期 入学成绩 001 刘影 01 女 623 002 李恒 01 男 679 003 陈诚 02 男 638 … … … … … … 数据结构 具有结构的数据元素的集合。它包括数据元素的逻辑结构、存储结构和相适应的运算。 逻辑结构 数据元素之间的逻辑关系，与计算机无关。 可用一个二元组表示：Data_Structure = (D,R) D：数据元素的有穷集合，R：集合D上关系的有穷集合。 [例] 设有数据结构 B = (D,R) ， 其中 D= {d1, d2, d3, d4, d5, d6}， R={r}， r={d1,d2, d1,d3, d1,d4, d3,d5, d3,d6}， 试画出其逻辑结构图。 （以班级学生关系为例） (1)集合结构 数据元素除了“属于同一集合”的联系之外，没有其它的关系。 (2)线性结构 数据元素之间存在一对一的关系。 (3)树型结构 数据元素之间存在一对多的关系。 (4)图状结构或网状结构 数据元素之间存在多对多的关系。 存储结构：数据的逻辑结构在计算机中如何表示。 数据元素的映象 用二进制位(bit)的位串表示数据元素。 每个数据元素的映象称为结点 每个数据项的映象称为数据域 关系的映象 两种基本方法及其组合使用。 顺序映象：以相对的存储位置表示关系 链式映象：以附加信息(指针)表示关系 注意：数据的逻辑结构和存储结构的关系 可以用数组等线形存储的方式存储逻辑上的树形结构 也可以用树状的复杂的存储结构来存储逻辑上的集合关系以达到提高检索速度的目的 数据的逻辑结构+运算的定义-------面向用户，需求分析 （抽象数据类型） 概念层 数据的存储结构+运算的实现-------面向计算机 实现层 抽象数据类型 抽象数据类型(ADT) 一个数学模型以及定义在该模型上的一组操作 “抽象”是指数据类型的数学抽象特性，其定义仅仅取决于它的一组逻辑特性，而与在计算机内部的表示和实现无关 算法和算法分析 算法的概念 建立在数据结构基础上的、求解问题的一系列确切的步骤。 一个算法必须满足以下五个重要特性 有穷性：对任何合法输入执行有穷步后能结束。 确定性：每条指令必须有确切的含义。 可行性：算法的每一条指令均能执行。 输入：有零个或多个输入。 输出：有一个或多个输出。 正确性（最重要的标准） 算法应满足具体问题的需求 对于典型的、苛刻而带有刁难性的一组有效输入得到正确的结果 健壮性 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙或随机的输出结果 可读性 算法应该好读。以有利于阅读者对程序的理解和维护 高效性：时间复杂度 算法执行占用的CPU时间，随问题规模n的变化函数 高效性：空间复杂度 算法执行占用的内存总量，随问题规模n的变化函数 算法效率的度量 时间复杂度 空间复杂度 算法执行的时间 事后统计的方法 先运行依据算法的程序 所得时间的统计量依赖于计算机的硬件、软件等环境因素 收集此算法的执行时间和实际占用空间的统计资料。 事前分析估算的方法 求出该算法的一个时间界限函数； 时间复杂度 n 问题规模，一般为数据的输入量 f(n) 算法中基本操作重复执行的次数—频度 是问题规模n的某个函数 算法的时间量度、时间复杂度 算法中各语句的频度之和T(n) T(n)=O(f(n)) 随问题规模的增大，执行时间的增长率和f(n)的增长率相同 时间复杂度曲线 常见的时间复杂度：