数据结构(一).ppt
《数据结构(一).ppt》由会员分享,可在线阅读,更多相关《数据结构(一).ppt(26页珍藏版)》请在三一文库上搜索。
1、数据结构(一),基本概念,数据 可以被计算机识别、存储和加工处理的符号的集合。 是计算机操作的对象的总称。 是信息的载体。 例子 数值计算程序(实数或整数) 编译程序(源程序) 图像处理程序(图像),基本概念,数据元素 组成数据的基本单位。 是数据中的一个“个体”。 又称元素、记录、结点或者顶点。 数据项 数据元素由数据项组成。 是数据结构中讨论的最小单位。 又称域、字段。,基本概念,数据结构 相互之间存在着某种关系的数据元素的集合。 逻辑结构 数据元素之间的逻辑关系。 存储结构 逻辑结构在存储器中的映象。,基本概念,数据的逻辑结构,可形式表示为二元组: L = ( N, R ) 其中 N 是
2、结点的有限集合 R 是 N 上的关系集合 例子 L = ( N, R ) N = a0, a1, a2 R = r r = ( a0, a1 ), ( a0, a2 ) ,基本概念,设L=( N, R )是一个逻辑结构,R= r , 若a, bN,且关系( a, b )r, 则: 称 a 是 b 的 前趋结点, 称 b 是 a 的 后继结点, 称 a 和 b 是 相邻结点, 如果不存在aN,使( a, b )r ,则称b为始结点, 如果不存在bN,使( a, b )r,则称a为终结点, 既非始结点又非终结点的结点被称为内结点。,基本概念,数据的逻辑结构 线性结构 树形结构 图状结构 集合结构,
3、基本概念,线性结构 结构中有且仅有一个始结点和一个终结点,每个内结点有且仅有一个前趋结点和一个后继结点。 非线性结构 结构中的结点可能有多个前趋结点和多个后继结点。,基本概念,一行表示一个结点(元素),每个结点由学号、姓名、性别等九个域(数据项)组成。 表的第一行是始结点;最后一行是终结点;中间的行都是内结点。 表的逻辑结构是线性结构。,基本概念,数据的存储结构 “数据元素”的映象 “关系”的映象 数据元素的映象方法 用二进制位(bit)的位串表示数据元素 (321)10 = (101000001)2 A = (001000001)2,基本概念,关系的映象方法 顺序映象 以相对的存储位置表示后
4、继关系 链式映象 以附加信息(指针)表示后继关系,x y,存储结构只含数据元素本身 的信息,无附加信息,链式映象中,存储结构除数据元素本身信息外,需要附加信息指示存储位置,基本概念,算法 是能够解决某类问题的由若干指令组成的有限序列。 一个算法可以用自然语言、程序设计语言或专门设计的伪语言描述。 算法必须满足五个特性: (1)有限性 (2)确定性 (3)输入 (4)输出 (5)可行性,基本概念,有限性:任何一条指令都只能执行有限次,换句话说,算法必须在执行有限步后结束。 确定性:算法中每条指令的含义必须明确,不允许有二义性,对于相同的输入只能得出相同的输出。 输入:一个算法可以有零个或多个输入
5、数据,这些输入数据取自确定的对象集合。 输出:算法有一个或多个输出,这些输出是同输入有某个特定关系的量。 可行性:算法中的所有操作都必须足够基本,都可以通过已经实现的基本操作运算有限次实现之。,基本概念,算法的设计原则: 正确性 可读性 坚固性(健壮性) 高效率与低存储量需求,基本概念,正确性:说一个算法是正确的,是指对于一切合法的输入数据,该算法经过有限时间(算法意义上的有限)的执行都能产生正确(或者说满足规格说明要求)的结果。 可读性: 可读性好的算法有助于设计者和他人阅读、理解、修改和重用。晦涩难读的程序易于隐藏较多错误。 坚固性: 当输入数据非法时,算法能适当地作出合适的反应。 高效率
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构
链接地址:https://www.31doc.com/p-4197414.html