01数据结构概述.ppt

第1章数据结构概述 数据的逻辑结构 数据的存储结构 数据处理算法的描述与分析 数据结构 是计算机专业的一门重要基础课程 它研究的问题是从实际需要中抽象出来的 是计算机科学各领域以及系统软件都会用到的知识 本章是全书的基础 主要介绍以下几个方面的内容 1 1数据的逻辑结构 人们要让计算机做事情 都必须涉及三个问题 一 确定所要加工处理的数据间的关系 以便进行处理时 能够知道一个数据的后面是哪一个数据 这是数据的逻辑结构问题 二 确定要对数据做哪些处理 这是算法描述问题 三 确定以何种方式把数据存放到计算机的内存 并反映出它们间的邻接关系 这是数据的存储结构问题 1 1 1数据及数据间的邻接关系 数据 是信息的载体 是人们用符号来表示客观事物的一种集合 现在把 数据 定义为 所有能够输入到计算机中被计算机加工 处理的符号的集合 通常 数据由 数据元素 简称 元素 集合而成的 数据元素也常被称作 结点 顶点 记录 每个数据元素都具有完整 确定的实际意义 是数据加工处理的对象 某公司雇员的信息 一个数据元素又可以细分成由若干个 数据项 组成 数据项也常称作 字段 域 它是数据元素中不可再分割的最小标识单位 通常不具备完整 确定的实际意义 只是反映数据元素某一方面的属性 数据结构关心的是从一个数据能够找到另一个数据的那种 关系 人们根据那种关系来组织和存储数据 以便顺利 有效地实现对数据的各种处理要求 如果两个数据结点间有着某种逻辑上的联系 就称这两个结点是 邻接的 若用圆圈代表结点 用结点间的一条连线代表它们之间存在的逻辑关系 那么 就用图1 1来表示结点A和B是 邻接的 直观定义 数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科 图1 1结点的邻接 常见的数据间的邻接关系有三种 线性关系 树型关系以及图状关系 数据间的邻接关系 就是数据的 逻辑结构 1 1 2数据的逻辑结构 所谓数据间具有 线性 关系 是指数据一个接一个地排列成一行 如果所要处理的数据间呈线性关系 那么就说它的逻辑结构是线性的 在线性关系中 排在第1个位置的结点称为起始结点 排在最后一个位置的结点称为终端结点 其余的结点称为中间结点 如图1 2所示 1 线性关系 图1 2线性关系中的各种结点 线性关系的特点是 除起始结点和终端结点外 每个结点的前面和后面 都有且只有一个结点与它邻接 起始结点的前面没有邻接的结点 终端结点的后面没有邻接的结点 简单地说 线性关系的特点是 有头有尾 顺序排列 所谓数据间具有 树型 关系 是指在数据之间具有分支 层次的逻辑关系 如果所要处理的数据之间呈树型关系 那么就说它的逻辑结构是树型的 文件目录间的逻辑结构就是树型的 图1 3所示为一个树型目录图例 2 树型关系 图1 3文件目录间的树型关系 树型关系的特点是 第1层只有一个结点 它是树型关系的起点 除第1层结点和分支末端结点外 位于中间各层的结点的前面只有一个结点与它相邻接 每个结点的后面可以有多个结点与它相邻接 第1层结点的前面没有结点与之邻接 每个分支末端结点的后面没有结点与之邻接 如果数据中的任何两个元素间都可能有邻接关系 那么就说它们之间的关系是图状的 如果所要处理的数据之间呈图状关系 那么就说它的逻辑结构是图状的 图状关系是数据间最复杂的关系 图1 4所示为一张航空网络图 在图状关系中 找不到谁是起点 谁是终点 各个结点的地位可以说都是相同的 3 图状关系 图1 4航空网络 图状关系的特点是 每个结点都可能与多个结点有邻接关系 数据间的线性关系和树型关系 都可以视为是图状关系的一个特例 1 2数据的存储结构 在计算机里存放数据时 既要存储数据本身 也要存储数据间的邻接关系 这样 在对数据进行加工处理时 才能够方便 正确地从一个数据找到与之邻接的另一个数据 数据的 存储结构 就是研究数据在内存中的存储方式 也就是在内存中有哪些存放数据的方法 数据的存储结构也称为数据的 物理结构 从整体上来看 数据在存储器内有两种存放的方式 一种是集中地存放在内存中的一个连接的存储区 另一种是利用存储器中的零星区域 分散地存放在内存地各个地方 在把数据存储到存储器时 是以数据元素 即数据结点 为单位进行的 分配给一个数据结点的存储区域 称为一个 存储结点 在一个存储结点里 除了要有数据本身的内容外 还要有体现数据间邻接关系的内容 所谓数据的 顺序式存储 结构 即是为一组数据分配一个连续的存储区 然后按照数据间的邻接关系 相继存放每个数据 这种存储结构 是借助存储结点间的位置关系 来体现数据元素间的邻接关系的 1 2 1顺序式存储结构 比如 图1 5左侧为一个数据元素所需要的存储尺寸 size字节 图1 5右侧所示为在内存里开辟了一个连续的存储区 用来依次存放数据的若干个存储结点 图1 5顺序存储结构 所谓数据的 链式存储 结构 即是存储每个数据的存储结点都由两个部分组成 一部分用来存放数据元素本身的信息 另一部分用来存放与本数据元素邻接的数据元素存储结点的位置 即存储指向与之邻接的存储结点的指针 起始地址 通过这些指针反映出数据间的逻辑关系 图1 6给出的是一个链式存储结构 1 2 2链式存储结构 图1 6链式存储结构 在链式存储结构中 存储结点里的指针并不局限于只能是一个 而应根据问题的需要安排为一个或多个 如果采用链式存储结构时 存储结点里只有一个指针 则称是单链式结构 如果存储结点里有两个指针 则称是双链式结构 如此等等 1 3算法及算法分析 人们关注数据地逻辑结构 即邻接关系 以及数据在内存中的存储结构 最终目的是要使用计算机对数据进行各种加工处理 比如插入 删除 查找 修改 排序等 实现数据的加工处理时 如果问题较大 较复杂 就应该先通过分析列出与加工处理相关的各个步骤 然后再去用某种计算机程序设计语言编写出程序在计算机上运行 第一步就是所谓的算法描述 第二步就是所谓的程序实现 1 算法和程序的区别 1 3 1算法及算法的描述 算法和计算机程序是两个不同的概念 所谓 算法 是指解决问题的一种方法步骤或者一个过程 对于一个问题 可以用多种算法来解决 而一个给定的算法 则只解决一个特定的问题 一个算法应该具有以下几个重要的特征 1 输入 一个算法应该有n n 0 个初始的输入数据 2 输出 一个算法可以没有或有一个或多个输出信息 它们与输入数据之间会有着某种特定的关系 3 确定性 算法中的每一个步骤都必须具有确切的含义 不能有二义性 4 可行性 算法中描述的每一个操作步骤都必须是可以执行的 也就是说 都可以通过计算机实现 5 有穷性 一个算法必须在经历有限个步骤之后正常结束 不能形成死循环 例1 1判断下面用文字描述的计数过程是否构成一个算法 1 开始 2 n 0 变量n赋初值0 3 n n 1 变量n增1 4 重复执行 3 循环执行增1操作 5 结束 例1 2编写一个算法 按照从小到大的顺序排列两个数值变量x y的内容 即要求最终有x y 解 用文字描述解决这个问题的算法如下 1 输入变量x y的数值 2 把两个数值中的小者存放到x里 3 把两个数值中的大者存放到y里 4 输出x y的值 可以看出 上面的描述符合算法的5个特征 所谓 程序 Program 是指使用某种计算机程序设计语言对一个算法的具体实现 比如 例1 2的算法 可以用如下的C语言程序来实现 include stdio main intx y temp scanf d d 打印输出 算法侧重于对解决问题的方法描述 即要做些什么 而程序是算法在计算机程序设计语言中的实现 即具体要怎样去做 算法是可以用不同方法来描述的 下面给出几种常见的方法 2 算法的描述 算法描述方法1 使用人们习惯的自然语言来描述算法 算法描述方法2 使用人们熟悉的流程图 即框图 来描述算法 例1 4用流程图描述输出整数1 2 3 9 10的过程 解 用流程图描述输出整数1 2 3 9 10的过程的算法如图1 8所示 图1 7流程图的各种图形名称和作用 图1 8用流程图描述算法 算法描述方法3 用 类C语言 来描述算法 本书将采用类C语言来描述算法 算法描述方法4 直接采用C语言来描述算法 例1 5分别用C语言和类C语言来描述输出整数1 2 3 9 10的过程 解 1 用C语言描述输出整数1 2 3 9 10的过程的算法如下 voidnum inti i 1 while i 10 printf i d n i i i 1 2 用类C语言描述输出整数1 2 3 9 10的过程的算法如下 voidnum i 1 while i 10 printf i d n i i i 1 现简单说明C语言的语法结构如下 1 尽量不要使用算法中涉及的变量做具体说明 2 预定义常量和类型 defineTRUE1 defineFALSE 1 defineERRORNULL 3 函数的形式 数据类型 函数名 形式参数 形式参数说明 内部数据说明 执行语句组 函数名 函数的定义主要由函数名和函数体组成 函数体用花括号 和 括起来 函数中用方括号括起来的部分为可选项 函数名之间的圆括号不可省略 函数的结果可由指针或别的方式传递到函数之外 执行语句可由各种类型的语句所组成 两个语句之间用 号分隔 可将函数中的表达式的值通过return语句返回给调用它的函数 最后的花括号 之后的 函数名 为注释部分 可舍 4 赋值语句简单赋值 变量名 表达式 它表示将表达式的值赋给左边的变量 变量 它表示变量加1后赋值给变量 变量 它表示变量减1后赋值给变量 成组赋值 1 变量1 变量2 变量3 变量k 表达式1 表达式2 表达式3 表达式k 2 数组名1 下标1 下标2 数组名2 下标1 下标2 串联赋值 变量1 变量2 变量3 变量k 表达式 条件赋值 变量名 条件表达式 表达式1 表达式2 交换赋值 变量1 变量2 表示变量1和变量2互换 5 条件选择语句if 表达式 语句 if 表达式 语句1 else语句2 情况语句switch 表达式 case判断值1 语句组1 break case判断值2 语句组2 break case判断值n 语句组n break default 语句组 break 注意 switchcase语句是先计算表达式的值 然后用其值与判断值相比较 若它们相一致时 就执行相应的case下的语句组 若不一致 则执行default下的语句组 其中的方括号代表可选项 6 循环语句 for语句for 表达式1 表达式2 表达式3 循环体语句 首先计算表达式1的值 然后求表达式2的值 若结果非零则执行循环体语句 最后对表达式3运算 如此循环 直到表达式2的值为零时止 while语句while 条件表达式 循环体语句 while循环首先计算条件表达式的值 若条件表达式的值非零 则执行循环体语句 然后再次计算条件表达式 重复执行 直到条件表达式的值为假时退出循环 执行该循环之后的语句 do while语句do 循环体语句 while 条件表达式 该循环语句首先执行循环体语句 然后再计算条件表达式的值 若条件表达式成立 则再次执行循环体 再计算条件表达式的值 直到条件表达式的值为零 即条件不成立时结束循环 7 输入 输出语句输入语句 用函数scanf实现 特别当数据为字符时 用getchar函数实现 输出语句 用printf函数实现 当要输出字符数据时 用putchar函数实现 8 其他一些语句 1 return表达式或return 用于函数结束 2 break语句 可用在循环语句或case语句中结束循环过程或跳出情况语句 3 exit语句 表示出现异常情况时 控制退出语句 9 注释形式可用 字符串 或者单行注释或 文字序列 10 一些基本的函数如 max函数 用于求一个或几个表达式中的最大值 min函数 用于求一个或几个表达式中的最小值 abs函数 用于求表达式的绝对值 eof函数 用于判定文件是否结束 eoln函数 用于判断文本行是否结束 对同一个问题可以设计出不同的算法 它们之间当然有好差之分 判定算法质量时应遵循下面的几条原则 1 3 2算法分析 算法是否易读 易于人们理解 算法的结构是否简明 清晰 算法的执行效率是否高 算法的存储利用率是否高 算法的可移植性是否好 在算法分析中 人们最看重的是执行效率 时间 和存储利用率 空间 这两个问题 在数据结构里 对一个算法执行效率的度量 称为 时间复杂度 对一个算法在执行过程中所需占用存储空间的度量 称为 空间复杂度 例1 6变量a b c d中各存一个整数 求a b c中的最大者与d的乘积的算法 voidmax1 a b c d a a d b b d c c d if a b x a elsex b if c x x c printf d n x 图1 9max1的流程 算法2为 voidmax2 a b c d if a b x a elsex b if c x x c x x d printf d n x 图1 10max2的流程 对比max1和max2 前者比后者多做了两次乘法 因此max1比max2得计算量要大 即如果按照这两个算法分别写出程序执行 在相同得软硬件环境下 max1花费的运行时间要比max2多 这就是说 max2的时间性能要比max1好 基本操作 是指算法中那些所需时间与操作数的具体取值无关的操作 赋值 两个数相加或两个数比较大小等 都可以作为基本操作 这些操作的执行时间与具体操作数是无关的 比如说 把数值1和把数值1000赋给变量x 计算机所花费的时间是相同的 都只是执行一个赋值操作 例1 7分析下面所给算法段中基本操作的执行次数 for i 1 i n i y y 1 for j 0 j 2 n j x 解 这里把y y 1 和x 视为基本操作 y y