第5章数据思维——数据的
组织、管理与挖掘接正文We are entering a new world in which data may be more important than software.
——Tim O’Reilly
（O’Reilly媒体公司创始人兼CEO,预言了开源软件、Web 2.0等数次互联网潮流）
5.1数据的组织和管理
第2章介绍了数值、西文字符、汉字和多媒体信息在计算机中的数据表示和编码。本章主要讲述相互有关联的数据的组织、管理和挖掘及面向数据组织和数据处理时的基本思维框架。本章内容的相关视频,读者可以参考中国大学视频公开课官方网站“爱课程”网（http: //www.icourses.cn）河北工程大学“心连‘芯’的思维之旅”课程中的第五讲。
信息是对客观世界中各种事物的运动状态和变化的反映。数据是信息的一种载体,是信息的一种表达方式,在计算机中信息是使用二进制进行编码的。数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。简言之,数据就是计算机化的信息。
计算机的程序是对信息（数据）进行加工处理。可以说,程序=算法+数据组织和管理,程序的效率取决于两者的综合效果。随着信息量的增大,数据的组织和管理变得非常重要,它直接影响程序的效率。
5.1.1数据结构1. 数据结构概念数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
大学计算机——计算思维导论第5章数据思维——数据的组织、管理与挖掘2. 数据结构的分类
（1） 按照数据元素相互之间的关系,通常分为集合、线性结构、树和图等4类基本结构,如图5.1所示。
图5.14类基本数据结构
集合: 数据元素除了同属于一种类型外,别无其他关系。
线性结构: 数据元素之间存在一对一的关系。
树形结构: 数据元素之间存在一对多的关系。
图状结构: 数据元素之间存在多对多的关系。
（2） 按照数据的线性程度,分为线性结构和非线性结构两大类型。
线性结构。线性结构的条件是: 有且只有一个根结点;每一个结点最多有一个前件,也最多有一个后件。常见的线性结构有线性表、栈、队列等。
非线性结构。不满足线性结构条件的数据结构称为非线性结构。常见的非线性结构有树和图。
（3） 按照数据结构的层次不同,分为逻辑结构和存储结构两大类。
逻辑结构。逻辑结构是对数据集合中各数据元素之间所固有的逻辑关系的抽象描述。
存储结构。又称物理结构,是数据的逻辑结构在计算机存储空间中的存放形式。同一种逻辑结构的数据可以采用不同的存储结构,但会影响数据处理效率。
数据的存储结构主要有顺序、链式两种。顺序存储是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。链式存储不要求逻辑上相邻的结点在物理位置上也相邻,结点间的逻辑关系是由附加的指针字段表示的。
3. 集合(简单数据)
集合是指比较简单的数据,即少量、相互间没有太大关系的数据。比如,在计算某方程组的解时,中间的计算结果数据可以存放在内存中以便以后调用。在程序设计语言中,往往用变量来实现。
4. 线性数据（线性表）
简单说,线性数据是指同类的批量数据,也称线性表。比如,英文字母表（A、B、…、 Z)、1000个学生的学号和成绩、3000个职工的姓名和工资、一年中的四个季节(春、夏、秋、冬)等。
线性数据的组织方法在计算机中一般有两种: 连续方式和非连续方式。在数据存储结构中称为顺序和链式。
（1） 连续方式——顺序存储。连续方式是指将数据存放在内存中的某个连续区域。如图5.2中,假设线性表中有n个元素,每个元素占k个单元,第一个元素的地址为loc(a1),则第i个元素的地址loc(ai)为: loc(ai)=loc(a1)+(i-1)×k,其中loc(a1)称为基地址。
图5.2顺序存储
顺序存储结构采用一组地址连续的存储单元依次存储各个元素,使得线性数据中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,采用顺序存储结构的线性表通常称为顺序表。
顺序存储结构可以借助于高级程序设计语言中的一维数组来表示。
在此方式下,每当插入或删除一个数据时,该数据后面的所有数据都必须向后或向前移动。因此,这种方式比较适合于数据相对固定的情况。
（2） 非连续方式——链表结构。非连续方式是指将数据分散地存放在内存中,每个数据存放一个位置,这些位置一般不连续。
方法是: 扩大每个数据的存储区域,该区域除了存放数据本身外,还存放其后面一个数据的位置信息。
数据元素的逻辑顺序是通过链表中的指针链接来实现的。在链式存储方式中,每个结点由两部分组成: 一部分用于存放数据元素的值,称为数据域;另一部分用于存放指针,称为指针域,用于指向该结点的前一个或后一个结点（即前件或后件）。对于最后一个数据,就填上一个表示结束的特殊值,这种像链条一样的数据组织方法也称链表结构。设一个头指针head指向第一个结点。指定线性表中最后一个结点的指针域为“空”（NULL）,如图5.3所示。
图5.3链表结构
【例51】线性表（A, B, C, D, E, F, G）的单链表存储结构,如图5.4所示,整个链表的存取需从头指针开始进行,依次顺着每个结点的指针域找到线性表的各个元素。 头指针head位置: 16存储地址数据域指针域1D558B2222C137F2516A825GNULL55E37图5.4线性表（A, B, C, D, E, F, G）的单链表存储结构在此方式下,每当插入或删除一个数据时,可以方便地通过修改相关数据的位置信息来完成。因此,这种方式比较适合于数据相对不固定的情况。
线性数据组织方式常用的有栈和队列两种。
栈
如果对线性数据操作增加如下规定: 数据的插入和删除必须在同一端进行,每次只能插入或删除一个数据元素,则这种线性数据组织方式就称为栈结构。通常将表中允许进行插入、删除操作的一端称为栈顶(Top)。同时表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈。
栈的插入操作被形象地称为进栈或入栈,删除操作称为出栈或退栈。
栈是先进后出的结构（First In Last Out,FILO）,如图5.5（a）所示。日常生活中铁路调度就是栈的应用,如图5.5（b）所示。
图5.5栈和栈的应用
队列
如果对线性数据操作增加如下规定: 只允许在表的一端插入元素,而在另一端删除元素,则这种线性数据组织方式就称为队列。
队列具有先进先出（Fist In Fist Out,FIFO）的特性。在队列中,允许插入的一端称为队尾(rear),允许删除的一端则称为队头(front)。
队列运算包括: 入队运算——从队尾插入一个元素;退队运算——从队头删除一个元素。日常生活中排队就是队列的应用。
5. 层次数据（树形数据）
如果要组织和处理的数据具有明显的层次特性,比如,家庭成员间辈分关系、一个学校的组织图,如图5.6所示,这时可以采用层次数据的组织方法,也形象地称为树形结构。
层次模型是数据库系统中最早出现的数据模型,是用树形结构来表示各类实体以及实体间的联系。层次数据库是将数据组织成树结构,并用“一对多”的关系联结不同层次的数据库。
严格地讲,满足下面两个条件的基本层次联系的集合称为树形数据模型或层次数据模型:
（1） 有且只有一个结点没有双亲结点,这个结点称为根结点;
（2） 根以外的其他结点有且只有一个双亲结点，如图5.7所示。
图5.6学校组织层次结构图
图5.7树形数据模型
在第1章例11中,提到了国际象棋世界冠军“深蓝”。国际象棋、西洋跳棋与围棋、中国象棋一样都属于双人完备博弈。所谓双人完备博弈就是两位选手对垒,轮流走步,其中一方完全知道另一方已经走过的棋步以及未来可能的走步,对弈的结果要么是一方赢（另一方输）,要么是和局。
对于任何一种双人完备博弈,都可以用一个博弈树（与或树）来描述,并通过博弈树搜索策略寻找最佳解。博弈树类似于状态图和问题求解搜索中使用的搜索树。搜索树上的第一个结点对应一个棋局,树的分支表示棋的走步,根结点表示棋局的开始,叶结点表示棋局的结束。一个棋局的结果可以是赢、输或者和局。
树在计算机领域中也有着广泛的应用,例如,在编译程序中,用树来表示源程序的语法结构;在数据库系统中,可用树来组织信息;在分析算法的行为时,可用树来描述其执行过程。
6. 图状数据（网状数据）
有时,还会遇到更复杂一些的数据关系,满足下面两个条件的基本层次联系的集合称为图状数据模型或网状数据模型:
（1） 允许一个以上的结点无双亲。
（2） 一个结点可以有多于一个的双亲。
比如,在第4章国际会议排座位问题中,可以将问题转化为在图G中找到一条哈密顿回路的问题。
【例52】哥尼斯堡七桥问题。
17世纪的东普鲁士有一座哥尼斯堡城,城中有一座奈佛夫岛,普雷格尔河的两条支流环绕其旁,并将整个城市分成北区、东区、南区和岛区4个区域,全城共有7座桥将4个城区相连起来,人们可以通过这7座桥到各城区游玩。
人们常通过这7座桥到各城区游玩,于是产生了一个有趣的数学难题: 寻找走遍这7座桥,且只许走过每座桥一次,最后又回到原出发点的路径。该问题就是著名的“哥尼斯堡七桥问题”,如图5.8所示。
1736年,29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文,在解答问题的同时,开创了数学的一个新的分支——图论与几何拓扑。把它转化成一个几何问题——一笔画问题。与上例一样,欧拉抽象出问题最本质的东西,忽视问题非本质的东西（如桥的长度等）,把每一块陆地考虑成一个点,连接两块陆地的桥以线表示,并由此得到了如图5.9所示的几何图形。若我们分别用A、B、C、D四个点表示为哥尼斯堡的四个区域。这样著名的“七桥问题”便转化为是否能够用一笔不重复地画出过此七条线的问题了。他不仅解决了此问题,且给出了要使得一个图形可以一笔画,必须满足如下两个条件: 图形必须是连通的;途中的“奇点”个数是0或2（奇点是指连到一点的边的数目是奇数条）。
图5.8哥尼斯堡七桥问题
图5.9简化后的一笔画问题
由此判断“七桥问题”中4个点全是奇点,可知图不能一笔画出,也就是不存在不重复地通过所有桥的路径。
“哈密尔顿回路问题”与“欧拉回路问题”的不同点是: “哈密尔顿回路问题”是访问每个结点一次,而“欧拉回路问题”是访问每条边一次。
欧拉的论文为图论的形成奠定了基础。图论是对现实问题进行抽象的一个强有力的数学工具,已广泛地应用于计算学科、运筹学、信息论、控制论等学科。
图5.10赋权图示例
在实际应用中,有时图的边或弧上往往与具有一定意义的数有关,即每一条边都有与它相关的数,称为权,这些权可以表示从一个顶点到另一个顶点的距离或耗费等信息。我们将这种带权的图称为赋权图或网,如图5.10所示。
可以利用算法求出图中的最短路径、关键路径等,因此图可以用来解决多类问题: 电路网络分析、线路的铺设、交通网络管理、工程项目进度安排、商业活动安排等,是一种应用极为广泛的数据结构。
网状模型与层次模型的区别在于: 网状模型允许多个结点没有双亲结点;网状模型允许结点有多个双亲结点;网状模型允许两个结点之间有多种联系（复合联系）;网状模型可以更直接地去描述现实世界;层次模型实际上是网状模型的一个特例。思考与探索
链式存储这种非连续方式中,每个数据都增加了存放位置信息的空间,所以是靠空间来换取数据频繁插入和删除等操作的时间的设计,这种空间和时间的平衡问题是计算机中算法和方法设计中的经常要考虑的问题。
7. 数据结构与算法
数据结构与算法之间存在着密切的关系。可以说不了解施加于数据上的算法需求就无法决定数据结构;反之算法的结构设计和选择又依赖于作为其基础的数据结构,即数据结构为算法提供了工具。算法是利用这些工具来解决问题的最佳方案。
（1） 数据结构与算法的联系。数据结构是算法实现的基础,算法总是要依赖于某种数据结构来实现的。算法的操作对象是数据结构。算法的设计和选择要同时结合数据结构,简单地说数据结构的设计就是选择存储方式,如确定问题中的信息是用普通的变量存储还是用其他更加复杂的数据结构。算法设计的实质就是对实际问题要处理的数据选择一种恰当的存储结构,并在选定的存储结构上设计一个好的算法。不同的数据结构的设计将导致差异很大的算法。数据结构是算法设计的基础。算法设计必须考虑到数据结构,算法设计是不可能独立于数据结构的。 另外,数据结构的设计和选择需要为算法服务。如果某种数据结构不利于算法实现它将没有太大的实际意义。知道某种数据结构的典型操作才能设计出好的算法。
总之,算法的设计同时伴有数据结构的设计,两者都是为最终解决问题服务的。
（2） 数据结构与算法的区别。数据结构关注的是数据的逻辑结构、存储结构以及基本操作,而算法更多的是关注如何在数据结构的基础上解决实际问题。算法是编程思想,数据结构则是这些思想的逻辑基础。
5.1.2文件系统和数据库〖*2〗5.1.2.1文件系统在较为复杂的线性表中,数据元素(data element)可由若干数据项组成,由若干数据项组成的数据元素称为记录(record),由多个记录构成的线性表称为文件(file)。
以文件方式进行数据组织和管理,一般需要进行文件建立、文件使用、文件删除、文件复制和移动等基本操作,其中文件的使用必须经过打开、读、写、关闭这四个基本步骤。程序设计语言一般都提供了文件管理功能。
一旦数据的逻辑结构发生变化,就必须修改程序中对于文件结构的定义,而且应用程序的改变也会影响文件的数据结构的改变,因此,数据和程序缺乏独立性。
5.1.2.2数据库系统
如果数据量非常大,关系也很复杂,这时可以考虑使用数据库技术来组织和管理。
数据管理技术是在20世纪60年代后期开始的,经历了人工管理、文件管理、数据库系统三个阶段,与前两个阶段相比,数据库系统具有以下特点:
数据结构化: 在数据库系统中数据是面向整个组织的,具有整体的结构化。同时存取数据的方式可以很灵活,可以存取数据库中的某一个数据项、一组数据项、一个记录或者一组记录。
共享性高、冗余度低、易扩充: 数据库系统中的数据不再面向某个应用而是面向整个系统,因而可以被多个用户、多个应用共享使用。使用数据库系统管理数据可以减少数据冗余度,并且数据库系统弹性大,易于扩充,可以适用各种用户的要求。
数据独立性高: 数据独立性包括数据的物理独立性和数据的逻辑独立性。物理独立性是指用户的应用程序与存储在磁盘上的数据库中的数据是相互独立的。数据的物理存储改变了,应用程序不用改变。逻辑独立性是指用户的应用程序与数据库的逻辑结构是相互独立的,数据的逻辑结构改变了,用户程序也可以不变。
利用数据库系统,可以有效地保存和管理数据,并利用这些数据得到各种有用的信息。
1. 数据库系统概述
数据库系统主要包括数据库（DataBase）和数据库管理系统（Database Management System,DBMS）等。
（1） 数据库。数据库是长期存储在计算机内的、有组织的、可共享的数据集合。数据库中的数据按一定的数据模型组织、描述和存储,具有较小的冗余度、较高的数据独立性和易扩展性,并可为各种用户共享。
（2） 数据库管理系统。数据库管理系统具有建立、维护和使用数据库的功能;具有面向整个应用组织的数据结构、高度的程序与数据的独立性,数据共享性高、冗余度低、一致性好、可扩充性强、安全性和保密性好、数据管理灵活方便等特点;具有使用方便、高效的数据库编程语言的功能;能提供数据共享和安全性保障。
数据库系统包括两部分软件——应用层与数据库管理层。
应用层软件负责数据库与用户之间的交互,决定整个系统的外部特征,例如采用问答或者填写表格的方式与用户交互,也可以采用文本或图形用户界面的方式等。
数据库管理系统负责对数据进行操作,例如数据的添加、修改等,是位于用户与操作系统之间的一层数据管理软件,主要有以下几个功能:
数据定义功能: 提供数据定义语言,以对数据库的结构进行描述。
数据操纵功能: 提供数据操纵语言,用户通过它实现对数据库的查询、插入、修改和删除等操作。
数据库的运行管理: 数据库在建立、运行和维护时由DBMS统一管理、控制,以保证数据的安全性、完整性、系统恢复性等。
数据库的建立和维护功能: 数据库的建立、转换,数据的转储、恢复,数据库性能监视、分析等,这些功能需要由DBMS完成。
（3） 数据库管理员。数据库和人力、物力、设备、资金等有形资源一样,是整个组织的基本资源,具有全局性、共享性的特点,因此对数据库的规划、设计、协调、控制和维护等需要专门人员来统一管理,这些人员统称为数据库管理员。
2. 数据模型
各个数据以及它们相互间关系称为数据模型。数据库从结构上主要有4种数据模型,即层次型、网状型、关系型和面向对象模型。
关系模型是1970年IBM公司的研究员E.F.Codd首次提出的,是目前最
![《计算机——计算思维导论》[51M]百度网盘|亲测有效|pdf下载](/uploads/s0309/e688e70869823a93.jpg)