1、普 通 高 中 教 科 书选择性必修信息技术普通高中教科书信息技术1数据与数据结构Shuju yu Shuju Jiegou选择性必修 1数据与数据结构广东教育出版社广东教育出版社定价：10.59元批准文号：粤发改价格2017434号 举报电话:12358ook2020信息技术选择性必修1-6封面.indd 12020/5/28 下午2:31信息技术广东教育出版社普 通 高 中 教 科 书徐福荫 主编广州数据与数据结构Shuju yu Shuju Jiegou1选择性必修 ook2020信息技术-8扉页.indd 32020/5/28 下午2:522 2 图书在版编目(CIP)数据信息技术选择
2、性必修1：数据与数据结构 / 徐福荫主编广州：广东教育出版社，2019.12（2021. 1重印）普通高中教科书ISBN 978-7-5548-3027-7. 信. 徐. 计算机课高中教材. G634.671中国版本图书馆CIP数据核字（2019）第208284号 编写单位 广东教育出版社 主 编 徐福荫 副 主 编 朱光明 黄国洪 本册主编 刘毅婉 严开明 核心编写人员（以姓氏笔画为序） 丘韶科 李苑文 周玳珈 黄淑燕 责任编辑 姜树彪 严洪超 责任技编 杨启承 陈 瑾 装帧设计 何 维信息技术 必修1 数据与数据结构XINXI JISHU BIXIU 1 SHUJU YU SHUJU JI
3、EGOU广 东 教 育 出 版 社 出 版（广州市环市东路472号12-15楼）邮政编码：510075网址：http:/广东新华发行集团股份有限公司发行广东新华印刷有限公司南海分公司印刷（佛山市南海区盐步河东中心路）890毫米1240毫米16开本9印张180 000字2019年12月第1版2021年1月第3次印刷ISBN 978-7-5548-3027-7定价：10.59元批准文号：粤发改价格2017434 号 举报电话：12315著作权所有请勿擅用本书制作各类出版物违者必究如有印装质量或内容质量问题，请与我社联系。质量监督电话：020-87613102 邮箱：gjs-购书咨询电话：020-8
4、777243822X2204.indd 22020/12/3 17:15:1511前 言信息技术作为当今先进生产力的代表，已经成为我国经济发展的重要支柱和网络强国的战略支撑。信息技术涵盖了获取、表示、传输、存储和加工信息在内的各种技术。自电子计算机问世以来，信息技术沿着以计算机为核心、到以互联网为核心、再到以数据为核心的发展脉络，深刻影响着社会的经济结构和生产方式，加快了全球范围内的知识更新和技术创新，推动了社会信息化、智能化的建设与发展，催生出现实空间与虚拟空间并存的信息社会，并逐步构建出智慧社会。在数字化时代，数据对科学发现、技术进步、经济发展以及人们的日常生活有着越来越深刻的影响。理解数
5、据的作用及价值，对同学们适应信息社会、学会数字化生存有着重要意义。数据结构是信息技术学科的核心内容之一，对培养同学们的信息意识与计算思维、深入理解及掌握信息技术学科知识与实践方法、形成学科核心素养，具有非常重要的作用。本教科书是针对数据、数据结构及其应用而设置的选择性必修模块。通过本教科书的学习，同学们可以进一步了解数据的作用，在掌握常用数据结构的概念、特点、操作、编程实现方法等内容的基础上，能对简单的数据问题进行分析，选择恰当的数据结构，用一种程序设计语言编程实现，在问题解决过程中对数据抽象、数据结构的思想与方法有初步的认识。本教科书按“数据与数据结构”“数据的组织和存储”“数据结构应用”三
6、部分内容展开，围绕信息技术学科核心素养，设计了“超市数据与社会关系的调查”“超市商品的信息化管理程序设计”“超市服务自动化的模拟实验”“俄罗斯方块游戏的抽象数据类型案例分析”“超市促销商品的选择与查询程序设计”项目范例。教师围绕“情境主题规划探究实施成果评价”的项目范例主线开展教学活动，帮助同学们掌握本教科书的基础知识、方法与技能，增强信息意识，发展计算思维，提高数字化学习与创新能力，树立正确的信息社会价值观和责任感，从而促进同学们的信息素养提升。本教科书要求同学们对现实世界中的真实性问题进行自主、协作、探21X2204.indd 12019/9/26 13:52:512 2 究学习。同学们围
7、绕“项目选题项目规划方案交流探究活动项目实施成果交流活动评价”的项目学习主线开展学习活动，体验“做中学、学中创、创中乐”的项目学习理念和“从实践入手、先学后教、先练后讲”的项目学习策略，将知识建构、技能培养与思维发展融入运用数字化工具解决问题和完成任务的过程中，从而促进信息意识、计算思维、数字化学习与创新、信息社会责任的信息技术学科核心素养达成。本教科书设置了“项目范例”“项目选题”“项目规划”“方案交流”“探究活动”“项目实施”“成果交流”“活动评价”等学习栏目，指导同学们开展项目学习活动。其中，“项目范例”是教师通过“情境”“主题”“规划”“探究”“实施”“成果”“评价”等活动，引导同学们
8、了解开展项目学习活动的全过程；“项目选题”是同学们从真实世界选择自己感兴趣的项目主题；“项目规划”是同学们根据项目选题，制订自己的项目方案；“方案交流”是同学们展示、交流自己设计的项目方案，师生共同探究、完善其方案；“探究活动”是同学们通过“问题”“观察”“分析”“阅读”“思考”“交流”“实践”“实验”“体验”“调查”“讨论”“拓展”等活动，获取知识和技能的过程；“项目实施”是同学们运用在项目学习过程中所获得的知识和技能来完成项目方案；“成果交流”是教师组织同学们展示交流项目成果，共享创造、分享快乐；“活动评价”是教师组织同学们开展项目评价活动。本教科书各章首页的导言，叙述了本章的学习目的与方
9、式、学习目标与内容，让同学们对整章有个总体认识。每章设置了“本章扼要回顾”，通过知识结构图把每章的主要内容及它们之间的关系描述出来，这有助于同学们建立自己的知识结构体系。每章结尾的“本章学业评价”设计了基于学业质量水平的测试题，并通过本章的项目活动评价，让同学们综合评价自己在信息技术知识与技能、解决实际问题的过程与方法，以及相关情感态度与价值观的形成等方面，是否达到了本章的学习目标。此外，本教科书中为同学们提供了配套学习资源包，里面含有超市数据与社会关系的分析调查报告、超市商品的信息化管理程序、超市服务自动化的模拟程序及超市促销商品的选择与查询程序等，还提供了同学们开展学习探究的程序设计示例。
10、当然，同学们还可以自己收集素材，让自己的项目学习作品更有特色。 前言21X2204.indd 22019/9/26 13:52:5111目 录目 录CONTENTS 第一章 认识数据和数据结构1项目范例 超市数据与社会关系的调查21.1 数据及其价值4111数字、数值与数据 5112数据与社会的关系 7113数据的价值和意义 91.2对实际问题的数据抽象 11121抽象问题中的数据 11122分析数据之间的关系13123建立数据模型 151.3认识数据结构 17131数据结构 17132数据类型 21133数据结构的重要作用2221X2204.indd 12019/9/26 13:52:512
11、 2 2 目录 第二章 数据的存储方式27项目范例 超市商品的信息化管理程序设计 282.1数据存储的顺序结构与链式结构 30211数据存储的顺序结构 30212数据存储的链式结构322.2数据的顺序存储与组织34221数组 34222数组的基本操作 402.3数据的链式存储与组织43231指针与指针变量 44232链表 46233链表的基本操作 472.4数组与链表及其应用 51241数组与链表 51242数组与链表的应用52 第三章 线性数据的组织和存储58项目范例 超市服务自动化的模拟实验593.1线性表 62311线性表及其运算 62312线性表的应用 633.2用字符串存储数据 64
12、321字符串及其存储 64322字符串的基本操作6821X2204.indd 22019/9/26 13:52:51333.3用队列组织先进先出数据69331队列 69332队列的基本操作 73333队列的实现 743.4用栈组织后进先出数据 79341栈79342栈的基本操作 82343顺序栈的实现 82 第四章 抽象数据类型88项目范例 俄罗斯方块游戏的抽象数据类型案例分析894.1认识抽象数据类型91411抽象数据类型 91412抽象数据类型的应用93413抽象数据类型的实现944.2用抽象数据类型表示队列和栈 96421用抽象数据类型表示队列 96422用抽象数据类型表示栈 974.3
13、用抽象数据类型表示二叉树98431树98432二叉树 100433二叉树的抽象数据类型 101434二叉树的基本操作方法 102目录21X2204.indd 32019/9/26 13:52:514 4 目录 第五章 数据结构的应用107项目范例 超市促销商品的选择与查询程序设计1085.1迭代与递归 111511迭代111512递归 1135.2查找 115521顺序查找 115522二分查找 1165.3排序 120531认识排序 120532冒泡排序 122533快速排序 1245.4算法与数据结构的联系与区别 128541算法与数据结构的联系 128542算法与数据结构的区别 130附
14、录1 部分术语、缩略语中英文对照表134附录2 项目活动评价表13521X2204.indd 42019/9/26 13:52:511 第一章 数据与信息1在数字化时代，数据与大数据对科学发现、技术进步、经济发展以及人们的日常生活有着越来越深刻的影响。人们产生数据、分析数据、使用数据，使数据成为新的原材料、生产资料和基础设施。把握数据的内涵与外延，才能把握时代的脉搏。本章将通过“数据与社会关系的调查”项目，进行自主、协作、探究学习，让同学们理解数字、数值和数据的基本含义，懂得对生活中的实际问题进行数据抽象，认识数据结构在解决问题过程中的重要作用，从而将知识建构、技能培养与思维发展融入运用数字化
15、工具解决问题和完成任务的过程中，促进信息技术学科核心素养达成，完成项目学习目标。 数据及其价值 对实际问题的数据抽象 认识数据结构第一章认识数据和数据结构第一章 数据与信息21X2204.indd 12019/9/26 13:52:512 2第一章 认识数据和数据结构超市数据与社会关系的调查项目范例情 境现代超市涉及大量的数据处理，对管理和技术提出了很高的要求。超市商品、客户群、资金流的管理都是数据处理的问题。如超市设置的收银机（如图1-1所示），收银的过程就包含了大量的数据处理工作；对超市客户数据的高效管理也能使经营更有针对性。超市借助计算机管理系统减少人工操作所带来的低效率、易出错等问题，
16、精确适时地反映和处理超市各项经营活动。主 题超市数据与社会关系的调查规 划根据项目范例的主题，在小组中组织讨论，利用思维导图工具，制订项目学习规划，如图1-2所示。图1-2“超市数据与社会关系的调查”项目学习规划图1-1超市收银台21X2204.indd 22019/9/26 13:52:533 第一章 数据与信息3探 究根据项目学习规划的安排，通过调查、案例分析、文献阅读和网上资料搜索，开展“超市数据与社会关系的调查”项目学习探究活动，如表1-1所示。表1-1“超市数据与社会关系的调查”项目学习探究活动探究活动学习内容知识技能超市收银机数据应用调查列举数据应用实例。调查收银机的功能。分析数据
17、与社会各领域的关系。理解数字、数值和数据的基本含义。认识数据在社会应用中的价值和意义。抽取事物中的数据。调查收银机收集的数据。分析数据关系。分析收银机使用的数据之间的关系。超市客户群市场调查列举数据应用实例。调查超市客户群体。理解数据结构的概念。认识数据结构在解决问题过程中的重要作用。抽取事物中的数据。分析客户的属性。确定数据关系。分析客户数据关系。建立数据模型。确定客户数据模型。实 施实施项目学习各项探究活动，进一步理解数据对信息社会的重要性。成 果在小组开展项目范例学习过程中，利用思维导图工具梳理小组成员在“头脑风暴”活动中的观点，建立观点结构图，运用多媒体创作工具（如演示文稿、在线编辑工
18、具等），综合加工和表达，形成项目范例可视化学习成果，并通过各种分享平台发布，共享创造、分享快乐。例如，运用在线编辑工具制作的“超市数据与社会关系的调查”可视化报告，可以在教科书的配套学习资源包中查看，其目录截图如图1-3所示。图1-3“超市数据与社会关系的调查”可视化报告的目录截图超市数据与社会关系的调查21X2204.indd 32019/9/26 13:52:534 4第一章 认识数据和数据结构评 价根据教科书附录2的“项目活动评价表”，对项目范例的学习过程和学习成果在小组或班级上进行交流，开展项目学习活动评价。项目选题同学们以36人组成一个小组，选择下面一个参考主题，或者自拟一个感兴趣的
19、主题，开展项目学习。1. 图书馆数据与社会关系的调查2. 校运会数据与社会关系的调查3. 社团活动数据与社会关系的调查项目规划各小组根据项目选题，参照项目范例的样式，利用思维导图工具，制订相应的项目方案。方案交流各小组将完成的方案在全班进行展示交流，师生共同探讨、完善相应的项目方案。1.1 数据及其价值数据是现实世界客观事物的符号记录，是以文字、图像、声音等表现形式存在的数字资源，是信息的载体，是计算机加工的对象。数据，已经渗透到当今每一个行业和业务职能领域，成为重要的生产因素。人们对于大数据的挖掘和运用，预示着新一波生产率增长和消费者盈余浪潮的到来。21X2204.indd 42019/9/
20、26 13:52:535 1.1 数据及其价值51.1. 1 数字、数值与数据人类从很久以前就懂得采用不同的方法对生产、生活中的事项进行记录，如用绳结的多少来记录数量的多少，用符号、图形、文字来记录事件、场景。记录的结果是产生了数据。而随着技术的不断发展进步，记录的方法和工具不断改进，数据的内涵也在不断拓展和延伸。1数字数字（Number）是一种用来表示数的书写符号。数字在不同的记数系统中表示的形式各不相同，阿拉伯数字是最普遍的一种。同一个数在不同的记数系统中有不同的表示，比如，数37（十进制阿拉伯数字）可以有多种写法：十进制阿拉伯数字写作“37”，中文数字写作“三十七”，罗马数字写作“XXX
21、VII”，二进制阿拉伯数字写作“100101”（除十进制和二进制外，还有其他进制）。2数值量是事物在同一种属性上的差别，通常用数字和单位来表示。例如，对于“质量”这种属性，一个大苹果质量约150克，一个小苹果质量约100克；对于“长度”这种属性，一张A4纸的两条边长分别为29.7厘米、21厘米一个量用数字表示时，这个数字叫作这个量的数值（Numerical Value）。例如，“150克”的“150”，“29.7厘米”的“29.7”。3数据数据（Data）是指对现实世界客观事物进行记录并可以鉴别的符号。数据是事实或观察的结果，是对客观事物的逻辑归纳，是用于表示客观事物的未经加工的原始素材。例如
22、，一个苹果，通过观察可以发现它的颜色是红色，形状近似球形；称重可以获得它的质量（如150克）；吃起来可以知道它的味道是香甜的；也可以画一幅画来描绘它，照一张相片来记录它红色、150克、香甜、画、相片都是数据，可用于表示这个苹果“相片中、画中描述的、近似球形的、红色的、香甜的、质量为150克的物品”。当然，数据越详细越准确，对于“苹果”这个事物的表示就越准确。在计算机科学中，数据是对所有输入计算机并被计算机识别、存储和处理的符号的总称，是联系现实世界和计算机世界的途径。现在的计算机存储和处理的对象十分广泛，数据的含义也变得广泛了，如图像、声音等也可以经过一定的输入变换，利用计算机进行加工和处理。
23、数据是信息的载体，是计算机程序加工的“原材料”。例如，在数值计算中所使用的数据是整数和实数，文本编辑程序中使用的数据是字符串。计算机处理的数据既可以是“150”这样的数值数据，也可以是文字、图片等非数值数据。而随着技术的应用和发展，计算机处理的对象越来越多的是非数值数据。在大数据时代，数据不仅是信息的载体，也是人们提取信息、做出决策的重要依据，成为人们认识和理解现实世界客观事物的重要资源。1.1 数据及其价值21X2204.indd 52019/9/26 13:52:536 6第一章 认识数据和数据结构探究活动分 析有人说：“数字是形，数据是体，数值是魂。”请根据数字、数值和数据的含义，分析下
24、列案例分别包含了哪些数字、数值和数据，并根据已有的样例补充完整。案例一每年的5月17日，全球电信业都要庆祝自己共同的节日世界电信日。从2006年开始，这个日子又增添了一个特殊的含义，联合国和国际电信联盟一起向世界发出邀请，与各成员国共同庆祝首届世界信息社会日。分析案例中包含的数字、数值和数据，将表格补充完整。数字5，17，2006。数值数据5月17日，2006年，世界电信日。案例二知网，是国家知识基础设施（NationalKnowledgeInfrastructure，NKI）的概念，由世界银行于1998年提出。中国知网（CNKI）工程是以实现全社会知识资源传播共享与增值利用为目标的信息化建设
25、项目，由清华大学发起，始建于1999年6月。在中国知网中检索“核心素养”的网页截图如图1-4所示。图1-4中国知网检索“核心素养”的网页截图分析案例中包含的数字、数值和数据，将表格补充完整。数字数值7807条结果中的“7807”。数据谈“核心素养”一文被引用的次数为307次，被下载的次数为25 582次。21X2204.indd 62019/9/26 13:52:537 1.1 数据及其价值71.1. 2 数据与社会的关系观 察回家过年是每一个中国人的期盼，一年一度的春运也随之成了牵动全社会的民生大事。2017年春运前后，与出行相关的政府部门、网站、媒体纷纷通过各种渠道发布了春运大数据报告，以
26、下是其中的一些报道。请仔细阅读，并与同学讨论，体会当今社会数据、大数据与社会生产、生活的关系。根据交通运输部数据统计，2016年春运期间全国运输系统共发送旅客29.1亿人次，2017年春运将有望突破30亿人次。春运期间的出行需求主要以跨市出行（离开常住城市）为主，跨市出行的客流量将直接影响整个春运期间的客流量。2017年春运大潮从1月13日开始，至2月21日结束。春运前夕，新京报联合某在线票务服务公司，依据实时数据，发布了2017年春运大数据报告。自发布日起，每周滚动更新除夕前三天（1月24日1月26日）由北京飞往全国各主要热门城市的机票价格情况，以及节后返程高峰期（2月2日2月4日）全国主要
27、热门城市飞回北京的机票价格情况，并给予订票提示。因2017年春节相比去年提前10天，春运车票的预订大幕已经开启。为了方便用户提前安排春节出行，抢到一张炙手可热的回家车票，某网站通过对60多万条飞机航线、50余万条铁路客运线进行大数据计算，发布2017年春运大交通数据报告，为回家旅客提供参考。某公司曾根据往年春运大数据，预测2017年春运返乡高峰会出现在腊月二十八，次高峰为腊月二十四。而实际上，次高峰预测准确，但返乡高峰却提前至腊月二十七。一方面是由于大部分企业会在该日期前后给员工提前放春节假期，另一方面则可能是此预测发布后，用户纷纷选择错峰出行。分析以上报道，可以得出：（1）当今社会，不管知道
28、还是不知道、愿意还是不愿意，人们在社会生活中生成的数据正在被各种途径收集、整理、利用。（2）大数据计算可以给人们的社会活动提供参考。（3）大数据计算的结果，能够调节、影响人们的活动。当今社会是一个高速发展的社会，科技发达，信息流通，人们之间的交流越来越密切，生活也越来越方便。我们每个人都在为社会这个“数据库”贡献数据：我们一出生，身份数据就被采集；从上学到就业、从工作到生活，都离不开各种数据的传送和接收。尤其在信息技术飞速发展的今天，人们利用互联网社交、娱乐、购物、理财社交平台、教育平台、电商平台、政府公共服务平台、金融平台，互联网、物联网，庞大的数据量正在这个看不见、摸不着的信息流中急剧增加
29、、快速流动。1.1 数据及其价值21X2204.indd 72019/9/26 13:52:538 8第一章 认识数据和数据结构1社会中的每个人都成为数据的提供者人们在电商平台购买商品、在网站预定车票和酒店、到银行办理业务、通过通信软件聊天、注册成为某个商家的VIP客户当人们在生活中刷各种各样的卡、读取各种各样的证件、在线录入各种各样的信息、线下填写各种各样的表格的时候，就是一次次主动向不同的系统提供数据的时候。另外，人们浏览网页时，点击的网页被记录下来；使用电商平台时，查看的历史被记录下来；在街上行走时，经过的路径会被监控系统记录下来；使用手机时，位置、运动信息、通信情况也可能被记录下来不管
30、人们知情还是不知情，生活中的很多数据已经被记录下来。2自然界中的事物也是数据的提供者通过各种监测系统和设备，人们可以获得空气质量的数据、河流水位的数据、气候变化的数据等。而且，技术的发展和应用，使得人们不但可以记录自然界中的事物，还能记录它们的变化和关联。3大数据正在影响和改变着人们的生活手机APP查询物流情况让人们及时掌握快递的运送状态；导航软件让人们在陌生环境中也能快速而准确地到达目的地；网上购票免去人们寒风中彻夜排队的辛劳人们日益普及的网络行为，无时无刻不在产生大量的数据。这些无法用常规软件工具进行高效捕捉、管理和处理的数据集合，被称为大数据。大数据的分析和应用为人们的生活、公司的运营甚
31、至政府的决策提供依据，影响和改变着人们的生活，成为推动信息社会发展的重要资源。我们正面临着一个“一切都被记录，一切都被分析”的数据化时代。讨 论以小组为单位，收集数据应用的事例，就下列问题开展讨论。（1）中国互联网络信息中心每年都会发布中国互联网络发展状况统计报告，请下载最新一期的报告并进行阅读，讨论其中的数据来源。（2）北斗卫星导航系统（BeiDouNavigationSatelliteSystem，BDS）是我国自行研制的全球卫星导航系统，致力于向全球用户提供高质量的定位、导航和授时服务，如图1-5所示。导航系统的自动化地图和路线规划功能，使人们无论是在熟悉还是陌生的环境下，都能泰然处之，
32、快速而准确地到达目的地。数据的应用给人们的生活带来了便捷的同时，是否也带来了其他影响？你还了解其他同类的应用事例吗？图1-5卫星定位系统21X2204.indd 82019/9/26 13:52:549 1.1 数据及其价值91.1. 3 数据的价值和意义阅 读图1-6是网购物品物流详情的手机截图。请仔细阅读这幅图，与同学一起探讨可以从中获得什么数据，得到什么信息。从图中大致可以获得：商品预计“2016-12-08”送达快递单号“6671208650*”商品一共“4件”“2016-12-0602:19:35”商品从无锡发出商家所在地是“苏州”细心的同学可能还会获得：截图的时间是“20:24”手
33、机使用的网络是“中国电信”手机的“蓝牙”状态开启手机设置了“闹钟”正在使用“4G”数据流量上网通过对读图提取到的数据进行分析，人们能够掌握一个正在运输过程中的包裹的信息、截图所使用的手机的当前状态信息。数据中蕴藏着宝藏。在数字化时代，数据和大数据对科学发现、技术进步、经济发展以及人们的日常生活有着越来越深刻的影响。随着海量数据的生成和存储，数据的价值越来越多地得到体现。数据和大数据成为新的原材料、生产资料和基础设施。理解数据和大数据的作用及价值，掌握数据获取、加工、管理、分析的方法，对我们适应信息社会、学会数字化生存有着十分重要的意义。1新的原材料在大数据时代，数据本身也扮演原材料的角色。人们
34、生产出数据产品，提供基于数据分析的服务，都建立在“有数据可供加工”的基础之上。例如，通过电子商务网站记录的数据，商家可以获取一个用户浏览、收藏、购买的数据，以此为材料可以加工分析出该用户的购买偏好、价格偏好、消费水平。商家可以精准地推送广告从而获得收益。2生产资料2013年被公认为世界的大数据元年。在这一年里，数据呈现井喷现象，各行各业的管图1-6物流数据1.1 数据及其价值21X2204.indd 92019/9/26 13:52:541010第一章 认识数据和数据结构理者都在讨论大数据，庞大的数据资源渗透了社会各个领域。在未来，数据将会像土地、石油和矿产一样，成为经济运行中的根本性资源，也
35、是重要生产力。3基础设施2009年，在甲型H1N1流感爆发的几周前，一家互联网公司的工程师们通过分析人们在网上的搜索记录成功地预测了流感的传播。这种分析和预测建立在大数据的基础上：在此过程中，他们分析了超过5000万条词条，处理了4.5亿个不同的数据模型。基于大数据的数据挖掘和分析，将成为未来极其可观的一个产业方向，并将会越来越多地应用在交通、教育、医疗、公共服务等领域。大数据逐渐成为现代社会基础设施的一部分，就像公路、铁路、港口、水电和通信网络一样不可或缺。讨 论以小组为单位，讨论下列案例中数据的价值和意义。案例一越来越多的政府部门、企业等开始意识到数据正在成为组织中最重要的资产，数据分析能
36、力正在成为组织的核心竞争力。案例二联合国在2012年发布了大数据政务白皮书，指出大数据对于联合国和各国政府来说是一个历史性的机遇，人们如今可以使用极为丰富的数据资源，来对社会经济进行前所未有的实时分析，帮助政府更好地响应社会和经济运行。案例三有一份名为“大数据，是下一轮创新、竞争和生产力的前沿”的专题研究报告提出，“对于企业来说，海量数据的运用将成为未来竞争和增长的基础”。该报告在业界引起广泛反响。交 流当我们解决实际问题的时候，数据究竟从哪来？它们如何发生作用？在项目范例中，通过调查获知，超市设置收银机，收银员可以很方便地对顾客购买的商品进行精确计价，提高收付款速度；收银结算的同时也获得了商
37、品销售的数据。而为了实现精确收费，收银机联接的计算机系统还需要处理大量数据。该调查形成的报告可参考配套学习资源包中的文档“第一章范例成品超市数据与社会关系的调查报告.docx”。请在小组中交流你对该调查报告的感悟，与同学们共同考虑如何开展本小组的项目。项目实施各小组根据项目选题及拟订的项目方案，结合本节所学知识，开展以下活动。1. 收集所选定项目中的数据。2. 分析数据与社会关系及其价值。21X2204.indd 102019/9/26 13:52:5411 1.2对实际问题的数据抽象111.2对实际问题的数据抽象计算机越来越多地用于控制、管理及数据处理等非数值计算的工作，这些工作的操作对象及
38、其关系是一些具有一定结构的数据，无法用数学方程进行描述。因此，我们必须对实际问题进行数据抽象，分析待处理对象的特性以及各处理对象之间存在的关系，建立问题的数据模型。1.2. 1 抽象问题中的数据人们利用计算机来帮助解决现实生活中的许多问题。用计算机解决问题，一般要经历以下过程：从问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，再编写程序调试，直到得到最终解答。寻求数学模型的过程实质就是分析问题、从中提取操作对象，并找出这些操作对象之间的关系，然后用数学的语言加以描述。例如对于鸡兔同笼的问题，其数学模型是一个二元一次方程组，设计一个算法解此方程组，并编程实现，就解决了这一问题。但
39、是，有许多非数值计算的问题，无法用数学方程来表示操作对象。当前，计算机已成为高效处理数据的工具。数据是计算机程序处理的对象，通过计算机程序处理数据，速度快、效率高、出错少。用数据来表示现实世界的事物及其活动，让这些事物可以在计算机中存储、计算、处理，是实现计算机解决问题的基础。探究活动分 析对于“超市客户”这一特定事物，可从“分析数据以便定位超市经营策略”的需求出发，抽取其中包含的数据。分析如下：1. 明确问题解决目标。根据“项目范例”的“主题”“规划”和“探究”的设计，明确项目要解决的问题，并逐步细化，如图1-7所示。图1-7根据目标细化问题1.2对实际问题的数据抽象21X2204.indd
40、 112019/10/8 11:06:001212第一章 认识数据和数据结构2.收集资料，进行分析，探究问题的解。研究表明，对超市经营有影响的各种因素中，人的因素起重要作用。“人”的属性众多（如图1-8所示），“超市客户”的属性则需要筛选，可以从超市客户管理需要的角度进行筛选，如表1-2所示。表1-2 “超市客户”属性的筛选消费水平跟踪联系消费欲望消费习惯姓名年龄性别职业地址家庭人数联系方式实 践根据上述分析，超市的客户管理系统要做到准确推送商品信息，跟踪目标客户的消费情况，确定超市的经营定位，则姓名、性别、联系方式、年龄、职业、地址等属性应列入数据表的考虑范围，如表1-3所示。表1-3解决问
41、题所需要的数据事物属性人姓名、年龄、性别、家庭人数、收入、职业、教育状况、身高、体重、视力、联系方式、地址目的需抽取的数据1. 准确推送商品信息姓名、联系方式、地址。2. 确定超市的经营定位年龄、职业、收入。我们已经知道，数据是事实或观察的结果，用来表示客观事物的属性。抽取出来的属性中，姓名、性别、职业等属性，直接采用收集到的数据如“张达”“男”“公务员”就可以了；而对于“年龄”这一项，因为年龄会随着时间不断变化，因此可以换成同样可以区分年龄大小但值固定的“出生年月”来表示；“联系方式”属性则采用了现在最普遍使用的“手机号码”来表示。最后，得到如表1-4所示的超市客户表。图1-8“人”的属性2
42、1X2204.indd 122019/9/26 13:52:5513 1.2对实际问题的数据抽象13表1-4超市客户表姓名性别出生年月职业手机号码地址消费记录张达男197401公务员13712345678熊二男197509工人13523456789李季女197808律师13034567891现实世界的事物纷繁多样，事物本身具备多种属性。从复杂多样、表现各异的现实世界的事物到规则有序的计算机世界的数据，让现实世界的问题在计算机中存储、计算、处理，需要一个转换的过程：从解决问题的需要出发，抽取出与问题解决相关的属性，用合适的数据表示这些属性；理清数据间的关系，建立数据模型。这个过程就是数据抽象的过
43、程。思 考各小组试着列出选定项目中事物及其活动的属性，再从中选择与问题解决目标相关的属性。这个过程可能一次成功，也可能要经过反复几次的调整修改。1.2. 2 分析数据之间的关系计算机处理的数值计算问题能直接抽象出数学模型，但更多的非数值计算的问题、数据间的复杂关系并不能直接用数学模型表示。这些复杂的关系中，最基本的关系有三种，即线性关系、层次关系和网状关系。1线性关系一个班学生的学号，从1号到50号，学号之间是顺序排列的，前后有序，如图1-9所示。从图1-9中可以看出，数据间的关系比较简单，每个数据仅有一个直接前驱和一个直接后继（第一个数据仅有后继，最后一个数据仅有前驱）。数据间的这种关系称为
44、线性关系。如表1-4的“超市客户表”，表中的各行数据之间就是线性关系。线性关系是计算机中最常见的数据关系。图1-9顺序排列的学号1.2对实际问题的数据抽象21X2204.indd 132019/9/26 13:52:551414第一章 认识数据和数据结构2层次关系初读红楼梦的同学可能不能很好地分清其中家族成员之间的关系。但如果借助如图1-10所示的“关系树”，则可以清晰地描述这些关系。图1-10就像一棵倒立的树。每个结点（圆圈）有且仅有一个前驱（根除外），有任意多个后继（叶子可以看作具有0个后继的结点）。这种数据间具有的一对多的联系称为层次关系，具有层次关系的数据表示为一棵倒立的树。现实生活中
45、也有不少例子，其数据间的关系为层次关系。例如，记录博弈过程的棋盘数据之间就是层次关系；学校里年级、班级的组织架构就是层次关系；班级成员中的班长、组长、组员间也构成层次关系。3网状关系随着经济的发展，城市之间的交通发达，人们出行的选择变得多样化。城市之间的交通联系可用如图1-11所示的关系来表示。图1-10红楼梦家族部分成员关系图1-11城市间的交通联系21X2204.indd 142019/9/26 13:52:5615 1.2对实际问题的数据抽象15在图1-11中，数据间的联系是多对多的：每个数据既有多个前驱，也有多个后继。这种数据间的多对多联系称为网状关系。例如，学校教育教学活动中涉及的人
46、员之间的关系就是网状关系：一个教师同时教多个学生，一个学生也同时有多个教师授课。综合以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是用诸如表、树、图之类的数据模型进行描述。1.2. 3 建立数据模型数据模型是客观事物及其关系的数据描述，是对客观事物进行数据抽象的结果。当描述客观事物属性的数据被抽取出来，数据间的关系就能理清，建立数据模型也就水到渠成了。建立数据模型的过程如图1-12所示。具有线性关系的数据，其数据模型是表如超市客户表、商品表、各种场景下的学生表等。线性关系是计算机中最常见的数据关系，表是计算机中最常见的数据模型。在本教科书的后续章节中将要学习到的链表、队列
47、、栈、字符串，其数据模型都是表。具有层次关系的数据，其数据模型是树如家族成员树（如图1-10所示）、班级成员树、学校机构树等。具有网状关系的数据，其数据模型是图如城市交通图（如图1-11所示）、学校人员图、（师生）教学图等。图1-12建立数据模型的过程1.2对实际问题的数据抽象21X2204.indd 152019/9/26 13:52:571616第一章 认识数据和数据结构表中的每一行，树、图中的每一个结点都被称为一个数据元素（Data Element）。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。有时候一个数据元素可由若干个数据项（Data Item）组成。例如
48、表中每个客户信息是一个数据元素，而客户信息中的每一项（如姓名、出生年月等）为一个数据项。数据项是数据的不可分割的最小单位。数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N=0，1，-1，2，-2，3，-3，。交 流在小组中交流，列举更多生活中包含表、树、图模型的事物，画出数据模型示意图，填写表1-5。表1-5生活中的表、树、图模型生活中的事物数据模型示意图表树图21X2204.indd 162019/9/26 13:52:5717 1.3认识数据结构17实 践针对本组的项目选题进行分析，抽取出其中的数据。可参考表1-3开展学习活动。1.
49、3认识数据结构数据以及数据的“结构”，与加工和处理这些数据的方法密切相关。为了描述和处理越来越复杂的数据关系，人们需要研究数据结构。数据结构是信息技术学科的核心内容之一，对培养信息意识与计算思维、深入理解及掌握信息技术学科知识与实践方法、形成学科核心素养，具有非常重要的作用。1.3. 1 数据结构1数据的组织方式上一节中的表1-4“超市客户表”，是对客观事物“超市客户”进行数据抽象所得的数据模型。它是现实世界中数据和数据间关系的抽象表示。在计算机世界中表示和存储数据、数据间的关系，需要用到数据结构。观 察超市商品种类繁多，超市的进、销、存系统经常需要对某种商品进行操作。因此，“查找”功能的效率
50、往往直接影响整个系统的效率。那么，影响查找效率的因素有哪些呢？假设超市商品数据是随机排列的查找的方法最简单：从头开始逐个比较，顺序查对，直到找到目标为止。查找操作必须对所有数据进行，所以虽然方法简单却效率低下。假设超市商品数据是有组织的可按照商品所属类别进行分类，同类商品数据放在一起，则商品查找效率将大大提高：先找到商品所属类别，再从该类别下的首个数据开始进行逐个比较查对即可，无须对所有数据进行查找。图1-13（a）中的数据就是随机排列的，而图1-13（b）中的数据则按洗漱用品、食品、清洁用品等分类组织。1.3认识数据结构21X2204.indd 172019/9/26 13:52:57181
