《数据结构域算法设计-第二章 信息系统的技术基础 课件》由会员分享,可在线阅读,更多相关《数据结构域算法设计-第二章 信息系统的技术基础 课件(178页珍藏版)》请在金锄头文库上搜索。
1、Copyright NCEPU, 2012. All rights reserved第二章 管理信息系统的技术基础 第一节 数据处理 第二节 数据库技术 第三节 计算机网络 第四节 Web开发的基本技术Copyright NCEPU, 2012. All rights reserved第一节 数据处理 本节内容: 一、数据处理的概念和发展阶段 二、数据组织Copyright NCEPU, 2012. All rights reserved一、数据处理的概念和发展阶段 -1数据处理的概念数据处理指把来自科学研究、生 产实践和社会经济活动等领域中的原始 数据, 用一定的设备和手段, 按一定的 使用
2、要求, 加工成另一种形式的数据。 Copyright NCEPU, 2012. All rights reserved数据处理的目的1.把数据转换成便于观察分析、传送或 进一步处理的形式。2.从大量的原始数据中抽取部分数据, 推导出对人们有价值的信息。3.利用计算机科学地保存和管理已经过 处理(如校验、整理等)的大量数据,以便人们 能方便而充分地利用这些宝贵的信息资源。 一、数据处理的概念和发展阶段 -2Copyright NCEPU, 2012. All rights reserved数据处理的基本内容 1.数据收集:根据系统自身的需求和用户的需求 。 2.数据转换:将实际数据采用代码表述。
3、 3.数据的筛选、分组和排序 4.数据的组织:将具有逻辑关系的数据组织起来 ,按一定的存储方式配置在计算机的存储器中。 5.数据的运算:指算术运算和逻辑运算。 6.数据存储 7.数据检索 8.数据输出 一、数据处理的概念和发展阶段 -3Copyright NCEPU, 2012. All rights reserved数据处理的特点管理活动的基本内容,也是MIS的基 本功能。一般不涉及复杂的运算,但要 求处理的数据量很大:1 数据以何种方式存储在计算机中。2 采用何种数据结构能有利于数据的 存储和取用。3 采用何种方法从已组织好的数据中 检索数据。一、数据处理的概念和发展阶段 -4Copyri
4、ght NCEPU, 2012. All rights reserved数据的组织组织 方式及内存联联系的表示方法决定着数据处处理的效 率。 (一)数据结构数据结构是计算机信息处理中的一个重要概念 ,包括数据的存储结构及结构上的运算或操作。 分为:逻辑结构物理结构二、数据组织 -1 Copyright NCEPU, 2012. All rights reserved逻辑结构数据间的逻辑关系,逻辑结构包括两大类:线性 结构和非线性结构,线性表、栈、队列及串为线性结 构,而树和图则为非线性结构。 物理结构又称存贮结构,指数据元素在计算机存贮器中的 存储方式,存储方式一般有四种:顺序存储、链接存 储
5、、索引存储及散列存储。 映象对于给定的逻辑结构需要寻找一种对应的存储结 构,以便在计算机中存储。通常把这种对应关系称为 映象。如顺顺序表数据结结构、链链表数据结结构。二、数据组织 -2 Copyright NCEPU, 2012. All rights reserved1 指针与链在数据结构中,表征某一数据结构特点及其 连接方式的基本单位称为结构的结点(Node)。一 个结点通常有几个域,用来存放与结点有关的信 息。存放结点本身信息的域称为数据域,存放结 点与其他结点关系信息的域,称为指针域或链域 ,其中存放有与结点有关的结点的地址称为指针 。若干带指针的结点组成的集合,称为链。 结 点的结构
6、如下图:NO.NAMEAGENEXT二、数据组织 -3 Copyright NCEPU, 2012. All rights reserved结点例子NO.NAMEAGENEXTNo.NameAge 0152王一22 1234王二28 2345王三25职工登记表采用链接存储方式Copyright NCEPU, 2012. All rights reserved0152王一22H1234王二282345王三25指针的作用利用指针可以把数据的逻辑结构与物理结构 分离开,数据的物理存储位置可以任意安排,而 在逻辑上通过指标把它们联系起来。Copyright NCEPU, 2012. All right
7、s reserved2 线性表线性表是指数据的结构形式本质上是 一维的线性关系,其中的每个结点都是同 一类型的数据结构。如英文字母表、产品的编号等。线性 表中每个结点中的元素可以是一个数字、 一串字符、或一项记录。 二、数据组织 -4 Copyright NCEPU, 2012. All rights reserved线性表的顺序存贮(最简单的存储方式)线性表的结点按逻辑次序依次存放在一组连 续的存贮单元里,用这种方法存储的线性表称为 顺序表。对于顺序表,若开始结点的存放位置为 LOC(k1), 每个结点占用空间大小为L,则第i个 结点ki的存放位置可由下式直接计算得到LOC(ki)=LOC(
8、k1)+L*(i-1)顺序表对于任何一个结点的检索都很方便。二、数据组织 -5 Copyright NCEPU, 2012. All rights reserved线性表的插入与删除要在线性表中插入一个元素,由于插入后的 线性表仍要求有序,必须将插入位置以后的元素 依次向后移动一个单元。同样,若要删除元素, 则需把后面的元素依次向前移动一个单元。当线性表长度为n时,作一次插入或删除操 作平均要移动n/2个元素。仅适用于经常进行检索,但数据不经常变动 的情况。二、数据组织 -6 Copyright NCEPU, 2012. All rights reserved序号 结点内容 序号结点内容1 9
9、 1 92 15 2 153 17 3 174 25 4 235 39 5 256 6 39插入前 插入后序 号结点 内容序 号结点 内容1 9 1 92 15 2 153 17 3 174 23 4 255 25 5 396 39 6 删除前 删除后二、数据组织 -7 Copyright NCEPU, 2012. All rights reserved链表 链接方式存储的线性表称为链表 。 链表结构在每个结点设有链指针,用来 指示下一个结点的位置,结点本身则可 以存放在任意一组存贮单元中,这些存 贮单元可以是连续的,也可以是分散的 。结点之间的逻辑关系由指针表示。二、数据组织 -8 Copy
10、right NCEPU, 2012. All rights reserved链表的插入与删除在链表的插入和删 除操作中,只需改 变前后结点的指针 ,而不需要进行大 量的数据移动。 H A B.C D H.A.B C D (b) 插入结点C.D .H.AB C.D .H.A(a) 删除结点二、数据组织 -9 Copyright NCEPU, 2012. All rights reserved3 树树是结点之间有分支的、层次关系的结构 ,类似于自然界中的树。是最重要的一类非线 性结构。适用于大量层次化嵌套数据。反映不同规格的钢材的库存情况 的树结构 如下图 代码 直径指针1 直径指针2 直径 长度
11、指针1 长度指针2 直径 长度指针1 长度指针2 长度 单价 库存量长度 单价 库存量长度 单价 库存量长度 单价 库存量二、数据组织 -10 Copyright NCEPU, 2012. All rights reserved(二)数据文件 1 数据文件的概念 把数据按某种数据结构组织起来存放在外部设备上, 就构成数据文件。 一般来说,数据文件是为某一目的而形成的同类记录 的集合,记录是文件中数据组织的基本单位,由若干个数 据项组成。文件系统是数据处理的主要方式,建造容易,使用灵 活,处理速度快,特别适合单项业务系统使用;是数据库 系统的基础。 二、数据组织 -11 Copyright NC
12、EPU, 2012. All rights reserved2 常用的文件的组织方式: (1) 顺序文件 即文件中的记录是按照某些关键字排序的文件。是根据记录的序号或相对位置进行存取的文件组织方式。特点:存取第i个记录,必须先存取前面的i-1个记录;插入记录只能加在末尾。优点:连续存取、速度快,主要用于顺序存取、批量修改 。缺点:其平均查找长度为(n+1)/2,n为文件所含记录数。(2) 索引文件 为便于检索,另外建一张指示逻辑记录和物理记录之间对 应关系的索引表。这类包括文件数据区和索引表两大部分 的文件称为索引文件。索引表的索引项应当按顺序排列,而数据文件本身可按顺 序排列,也可不按顺序排
13、列。Copyright NCEPU, 2012. All rights reserved(2) 索引文件 当记录很多时,索引表也很大,一个物理块可能容纳不下 ,查索引表时,可能要多次访问外存,可以对索引表建立 一个索引,称为查找表。 检索记录时,先查找查找表,再查索引表,最后读取记录 。最大键号物理块号 121 422 643查 找 表Copyright NCEPU, 2012. All rights reserved(2) 索引文件 当记录数目十分大,查找表也可能占用许多物理块, 这时就要作查找表的索引,称为第二查找表。通常最高可 有四级索引:索引文件 索引表 查找表达式 第二查找 表达式
14、第三查找表文件系统的结构只限于记录内部,因而仅能适用于单 项应用的场合,对于一个组织的MIS而言,要考虑全局数 据结构,要求不仅能描述数据本身,还得描述数据之间的 关系 采用数据库组织数据。Copyright NCEPU, 2012. All rights reserved本节内容: 一、数据库系统的构成 二、数据库设计的主要内容 三、实体联系模型 四、数据模型 五、关系的规范化 六、数据库操作 七、数据库保护第二节 数据库技术Copyright NCEPU, 2012. All rights reserved计算机系统:硬软件、网络系统。 数据库:物理数据库(实际数据)、描述数据库(逻辑结构
15、)。 数据库管理系统(DBMS):为数据库的建立、使用、 维护而配置的软件。包括数据描述语言(用于描述数据库的结 构)、数据操纵语言(提供对数据查询、更新等操作)、数据 库管理例行程序。比如:Informix、Oracle、Sybase、VFP、 Access、PowerBuilder等。 人员:数据库管理员:为保证数据库的完整性等。系统程序员:设计数据库管理系统的人员。 用户:应用程序员、专门用户、参数用户。一、数据库系统的构成Copyright NCEPU, 2012. All rights reserved按用户的观点对数据和信息建模。常 常首先将现实世界的客观对象抽象为某一 种不依赖于
16、计算机系统和某一个DBMS的信 息结构即概念模型(E-R模型),然后再把 概念模型转换为计算机上某一DBMS支持的 数据模型(如关系模型)。二、数据库设计的主要内容Copyright NCEPU, 2012. All rights reserved需求分析 概念设计 逻辑设计物理设计实施与运行数据库设计步骤(调研分析)(E-R模型)(转换成某种DBMS 支持的数据模型)(在存储设备上选定 存储结构和方法)Copyright NCEPU, 2012. All rights reserved建立概念模型常涉及的概念:1 实体(Entity):现实世界中存在的对象。2 属性:实体具有的某种特性。3 联系:一是实体内部的联系;二指实体之 间的联系。一对一联系(1:1) 一对多联