11数据结构基本概念 4、数据结构中常用术语 ①数据:是对客观事物的描述、是信息的载体,能被 计算机加工、处理的数字和符号集合 ②数据元素:是数据的基本单位,可包含若干数据 项、也称为记录。由记录组成的线性表称为文件。 ③数据项:具有独立意义的最小数据单位,即数值 ④数据对象:某种数据类型元素的集合,即一类数 据 例如,整数的数据对象是{…3,-2,-1,0,1,2,3 文符类型的数对線處{A,邳,数,称算4 0709101张三男 团员 90 90 0709101李四女党员 90 7 90 78 0709101王五男 群众 76 86 80 69 表中一行或一列均为一个数据元素
11 ④ 数据对象：某种数据类型元素的集合，即一类数 据 例如，整数的数据对象是 {…-3, -2, -1, 0, 1, 2, 3 … 英文字符类型的数据对象是 {A, B, C, …,±,⊙,★, …} 4、数据结构中常用术语： ① 数据：是对客观事物的描述、是信息的载体，能被 计算机加工、处理的数字和符号集合。 ② 数据元素：是数据的基本单位，可包含若干数据 项、也称为记录。由记录组成的线性表称为文件。 ③ 数据项：具有独立意义的最小数据单位，即数值。 1.1 数据结构基本概念 学 号 姓 名 性 别 政治面貌 马 列 高 数 英 语 计算机 0709101 张三 男 团员 85 90 85 90 0709101 李四 女 党员 90 87 90 78 0709101 王五 男 群众 76 86 80 69 … … … … 表中一行或一列均为一个数据元素 … … … …
11数据结构基本概念 5、数据逻辑结构:数据间相互关系,分为: 00000 ①集合结构数据元素除了同Q 属于一种类型外,别无其它关系。 ②线性结构:数据元素之间存在一对一的关系 ③树型结构:结构中数据元素间存在一对多的关系 ④图状(网状)结构:数据元素之间存在多对多的关系。 6、数据结构的表示方法:即数据的存贮方式 ①顺序存储结构:用数据元素在存储器中的相对位置 来表示数据元素之间的逻辑关系 ②链式存储结构:在每一个数据元素中增加一个存放 地址的指针,用此指针来表示数据元素之间的逻辑关系
12 5、 数据逻辑结构：数据间相互关系，分为： ① 集合结构 数据元素除了同 属于一种类型外，别无其它关系。 ② 线性结构：数据元素之间存在一对一的关系。 ③ 树型结构：结构中数据元素间存在一对多的关系。 ④ 图状(网状)结构: 数据元素之间存在多对多的关系。 6、数据结构的表示方法：即数据的存贮方式。 ① 顺序存储结构：用数据元素在存储器中的相对位置 来表示数据元素之间的逻辑关系。 ② 链式存储结构：在每一个数据元素中增加一个存放 地址的指针，用此指针来表示数据元素之间的逻辑关系。 1.1 数据结构基本概念
11数据结构基本概念 数据结构的形式定义:数据结构是数据存贮逻辑结 构、由二元组成:数据结构①。)型表栈队树图 其中:D是数据元素的有限集, 据题算法时空度 例:履历表的数据结构定义如下:合取存要快速 S=(C, R) 构造顺序与链存 其中:C是含若干个项目,如年龄、职业、填表 日期等的集合{C1,C2,Cn}, R={P},P是定义在集合上的一种关系 区<C1,C2},如,年龄与出生年月日有关。 数据(存贮)结构不同于数据类型,也不同于数据 对象,它不仅要描述数据类型的数据对象,而且要 描述数数据对象各元素之间的相互关系
13 数据(存贮)结构不同于数据类型，也不同于数据 对象，它不仅要描述数据类型的数据对象，而且要 描述数数据对象各元素之间的相互关系。 1.1 数据结构基本概念 数型表栈队树图 据题算法时空度 结合取存要快速 构造顺序与链存 例：履历表的数据结构定义如下： S=(C，R) 其中： C 是含若干个项目，如年龄、职业、填表 日期等的集合﹛ C1，C2，Cn ﹜， R={P} ，P 是定义在集合上的一种关系 {<C1,C2>}，如，年龄与出生年月日有关。 7、数据结构的形式定义：数据结构是数据存贮逻辑结 构、由二元组成：数据-结构=(D ,S) 其中： D 是数据元素的有限集， S 是 D 上关系的有限集
11数据结构基本概念 8、数据的运算:数据运算定义在数据逻辑结构上 的操作,但运算的具体实现要在存贮结构上进行 数据运算对数据结构是非常重要,各种逻辑结构有 相应的各种运算要求。常用的几种运算为 ①插入:向数据结构里加入新的节点。 ②删除:把指定的节点从数据结构里去掉。 ③查找:在数据结构里找寻满足一定条件的 节点。 ④替换:改指定节点一个域或多个域的值 ⑤排序:在线性结构中保证节点数不变的情况下 按某种指定的顺序排列。它是用量最大是算法
14 8、数据的运算：数据运算定义在数据逻辑结构上 的操作，但运算的具体实现要在存贮结构上进行。 数据运算对数据结构是非常重要，各种逻辑结构有 相应的各种运算要求。常用的几种运算为： ① 插入：向数据结构里加入新的节点。 ② 删除：把指定的节点从数据结构里去掉。 ③查找：在数据结构里找寻满足一定条件的 节点。 ④ 替换：改指定节点一个域或多个域的值。 ⑤排序：在线性结构中保证节点数不变的情况下， 按某种指定的顺序排列。它是用量最大是算法 1.1 数据结构基本概念
1.2算法分析与设计 算值设计结构类 法有穷效行确对 1、算法( Algorithm):对特定问题求解步分解表树队栈串 骤的一种描述。如、查找元素的二分法。析剖计量操作序 算法是指令的有限序列,其中每一条指令表示一个或多 个操作。如两个变量交换数据: swap a,b 2、算法的五个重要特性: 1).有穷性:一个算法必须在执行有限次后结束每步定时 2)确定性:每条指令必须有确定含义,不能有二义性。 3).可行性:算法描述的执行步骤必须在计算机上可行。 4).输入:一个算法按功能应有零个或多个输入。 5)输出:算法执行结束要有结果输出或产生相应动作
15 1.2 算法分析与设计 1、算法(Algorithm)：对特定问题求解步 骤的一种描述。 如、查找元素的二分法。 算法是指令的有限序列，其中每一条指令表示一个或多 个操作。如两个变量交换数据：swap a, b 2、算法的五个重要特性： 1). 有穷性：一个算法必须在执行有限次后结束，每步定时 2). 确定性：每条指令必须有确定含义，不能有二义性。 3). 可行性：算法描述的执行步骤必须在计算机上可行。 4). 输入：一个算法按功能应有零个或多个输入。 5). 输出：算法执行结束要有结果输出或产生相应动作。 算值设计结构类 法有穷效行确对 分解表树队栈串 析剖计量操作序 a b c ① ② ③