1、书 书 书华东师范大学出版社总 主 编: 李晓明副总主编: 赵 健本册主编: 李晓明编写人员( 按姓氏笔画排序) :白晓琦 李晓明 周 刚 顾秋辉责任编辑: 竺 笑美术设计: 储 平普通高中教科书 信息技术 选择性必修1 数据与数据结构上海市中小学(幼儿园)课程改革委员会组织编写出版发行 华东师范大学出版社( 上海市中山北路3 6 6 3号)印 刷 上海昌鑫龙印务有限公司版 次 2 0 2 1年3月第1版印 次 2 0 2 1年3月第1次开 本 8 9 0毫米 1 2 4 0毫米 1/1 6印 张 9 . 7 5字 数 1 7 4千字书 号 I S B N 9 7 8 7 5 7 6 0 0
2、5 4 9 3定 价 1 2 . 1 0元版权所有未经许可不得采用任何方式擅自复制或使用本产品任何部分违者必究如发现内容质量问题, 请拨打电话0 2 1 6 0 8 2 1 7 1 4如发现印、 装质量问题, 影响阅读, 请与华东师范大学出版社联系。电话: 0 2 1 6 0 8 2 1 7 1 1全国物价举报电话: 1 2 3 1 5声明 按照 中华人民共和国著作权法 第二十五条有关规定, 我们已尽量寻找著作权人支付报酬。著作权人如有关于支付报酬事宜可及时与出版社联系。本册教材图片提供信息: 本册教材中的部分图片由全景网、 视觉中国等图片网站提供。华东师范大学出版社致同学们致同学们亲爱的同学
3、们:数据与数据结构, 是计算机科学, 尤其是程序设计中的两个核心概念。数据类型的丰富性, 让我们得以方便地表达复杂的事物; 数据结构的精巧性, 让我们得以高效地实现优美的算法。按照 普通高中信息技术课程标准(2 0 1 7版) 的规定, “ 数据与数据结构” 是一个选择性必修模块。本册适合于那些将来有可能选择计算机科学、 人工智能、 大数据和物联网等相关专业的同学学习。该模块的学习有助于同学们进一步提高对这些专业的兴趣进而坚定选择这些专业的信心。另一方面, 对“ 数据与数据结构” 基本知识的理解和适当掌握, 也有超越应试的意义。因为它是计算思维的一部分, 在基于互联网和大数据之上的信息社会中,
4、 计算无时无处不在, 对其核心概念与过程的熟悉和理解, 不仅有助于同学们对信息社会运行的理解, 也有助于同学们从计算思维的视角提升工作效率。贯穿本册的思路是, 力争不仅要讲“ 是什么” 和“ 如何做” , 还要讲“ 为什么” 。好比汽车, 我们可以只是驾驶着它解决通行, 也可以打开前盖看看它里面的部件及其之间的关系, 了解它是怎么工作的。同学们会看到, 一旦开始学习, 就会接触一些术语, 如字符串、 数组、 线性表、 堆栈、 队列、 二叉树、 图及哈希表等。本册将不满足于仅从概念上解释它们是什么, 还要试图解释它们为什么会出现在用计算思维解决问题的情境中。学习数据与数据结构, 编程实践是必须的
5、, 编程是手段而不是目的。本册既借助P y t h o n的一些高级功能来为实现应用程序提供方便, 同时也兼顾数据类型和数据结构细节的剖析。目前, 大数据和人工智能的广泛应用, 既拓展了数据与数据结构1 华东师范大学出版社数据与数据结构 知识的用武之地, 也展现了数据与数据结构知识创新的空间。相信同学们通过本课程的学习, 能够在相关认知和能力方面都有显著提高,为将来的不断进步奠定基础。编者2华东师范大学出版社目录目录第一章引言 . . . 1项目主题随时提供有序的报名信息. . . 3第一节数据. . . 4第二节数据结构. . . 1 0第二章数据类型 . . . 1 5项目主题用数据描述身
6、边的同学. . . 1 7第一节基本类型. . . 1 8第二节常用类型. . . 2 4第三节组合类型. . . 3 3第四节抽象类型. . . 3 61 华东师范大学出版社数据与数据结构第三章基础数据结构 . . . 4 1项目主题送餐机器人的行走路线. . . 4 3第一节线性表. . . 4 4第二节栈. . . 6 1第三节队列. . . 6 9第四章常用数据结构 . . . 7 7项目主题心算游戏好帮手. . . 7 9第一节二叉树. . . 8 0第二节图*. . . 9 4第三节哈希表*. . . 1 0 12华东师范大学出版社目录第五章数据结构应用 . . . 1 0 9项目
7、主题人脸识别系统中的信息管理. . . 1 1 1第一节排序. . . 1 1 2第二节查找. . . 1 2 2附录参考程序. . . 1 3 1后记 . . . 1 4 53华东师范大学出版社第 一 章引言本章学习目标从计算机程序的角度理解数据的含义。初步理解数据类型的概念及意义。初步理解数据结构的概念及意义。了解数据类型与数据结构的关系。华东师范大学出版社数据与数据结构本章将从计算机科学的角度, 开启关于数据类型和数据结构的讨论。数据类型是程序设计语言中的基本概念之一。数据类型的引入帮助我们在程序设计时更为方便、 准确地描述和处理各种数据。数据结构是一个与算法紧密关联的概念, 合理的数据
8、结构搭配合适的算法能够有效地提高程序的运行效率。数据结构中的“ 数据” , 以 0和 1的组合形式存储于计算机的存储单元中, 其代表的具体含义则取决于该数据的数据类型。数据结构中的“ 结构” , 是本课程学习的主要内容, 在程序中它既服务于算法, 也可能随着算法的运行而变化。数据结构并不神秘, 从同学们开始学习程序设计的那一刻起, 它就已经悄无声息地存在于代码的字里行间了。本章知识结构2华东师范大学出版社第一章引言项目主题随时提供有序的报名信息项目情境设想同学们要参加一个活动, 他们按照随机的顺序来到报名点, 工作人员一一记录他们的信息, 包括学号、 姓名和性别等。不时会有负责人来了解报名的情
9、况,除了想知道已有多少人报名外, 还希望立刻看到一个按某种顺序( 学号或姓氏笔画等) 展现的已报名人的名册。如果你是该工作人员, 会怎么做呢?项目任务任务 1任务 2任务 3任务 4 通过讨论项目情境中的要求, 理解如果不用程序而是就在纸上做报名登记, 可能有哪些方式, 分别会带来哪些困难( 这里假设潜在报名的人会很多) 。 假设每个报名者的信息包括( 学号、 姓名、 性别) 三项内容, 通过考察 Py t h o n提供的丰富的语言机制, 设计一个数据类型来表示单个学生的信息, 并对你 的 设 计 选 择 进 行评估。 设计一个数据结构来记录“ 当前已报名学生” 。假设你预先不知道会有多少人
10、来报名, 那么你的数据结构应该是随实际报名学生数动态变化的。设计中会有哪些考量, 你做取舍的理由何在? 实现一个程序, 它接收随机而来的报名者信息和要看报名情况的指令, 一旦后者出现, 就按学号顺序直接打印出当前已报名者的名单。要求程序中不得调用排序函数。3 华东师范大学出版社数据与数据结构第一节数据数据是信息技术中最常用的术语之一, 其内涵和外延都十分丰富。作为对本课程后续内容的引导, 本节首先带领同学们从多视角初步了解数据的基本概念, 同时明确本课程中数据概念的主要视角, 并通过几个例子初步探讨数据类型的意义。一、 进一步认识数据本课程的必修1 数据与计算 中已经介绍过数据这一含义宽泛的概
11、念。为了有效地讨论与数据相关的问题, 人们需要对数据在不同语境下所表示的含义达成一定的共识。1 . 宽泛性日常生活中, 经常会接触到诸如“ 国民经济运行的主要数据” “ 人口统计数据” “ 中学生健康数据” 等各种各样的“ 数据” 。这里的“ 数据”可能指一个表, 也可能指几张图, 它们是相应背景下某种状态的直接反映。本课程必修模块中讨论过数据意义、 价值等方面的问题, 这些问题中提到的“ 数据” 存在于日常生活中的综合应用层面, 可能与计算机处理没有任何关系。对于普通电脑用户而言, 最常接触的是电脑桌面上或文件夹中的各种数据文件, 例如一张图片、 一个电子表格或一个视频文件等。它们通常由某些
12、特定的应用程序生成, 需要特定的应用程序才能打开和处理。因此, 可以说它们是应用程序的输入或输出数据, 其效用只能借助于计算机的处理才能体现出来。对于计算机编程人员或者说计算机应用开发人员而言, 除了要理解上述程序的输入输出数据, 还要理解程序内部的数据, 具体而言就是每一个常量或每一个变量代表什么, 计算机能对它做些什么。而这些程序内部的数据在应用层面不一定有可以解释的含义。2 . 层次观从信息技术的角度看, 以上三种情况由表及里地体现了数据作为4华东师范大学出版社第一章引言 (a) (b)一个概念的三个层面。如图1 . 1(a) 所示, 将它看作上中下三层。普通泛指的数据对应下层的自然与社
13、会状态的记录。为了用计算机处理它们, 通常需要将它们数字化, 成为计算机中的数据文件。但计算机中可以称为数据的文件不一定都是那些记录, 例如本书的电子版。因此就有了中间层的“ 其他数字化产物” 部分。进一步地, 当用计算机程序来处理那些文件时, 除了其中的内容要变成程序内部的数据表示外, 程序中一般都还需要一些额外的辅助数据才能实现目标。因此就有了上层的“ 其他辅助要素” 部分。这样一种观念也可以由图1 . 1(b)来简略表达, 即可以从“ 程序中” “ 计算机中” 和“ 计算机外” 三个层面来谈论数据。这种概念上的分层有利于我们在讨论问题时, 根据不同语境及不同的服务目的, 理解“ 数据”
14、这一术语的不同含义。例如, 当谈论数据的价值时, 涉及的主要是数据第一层面的含义。这在前面两个必修模块中已有充分讨论。当谈论两个功能相似但品牌不同的应用程序的兼容性时, 则可能会涉及数据第二层面的含义。在本模块中,我们主要关心数据第三层面的含义, 即计算机程序具体处理的数据。例如, 有的视频播放器能读入多种格式的视频文件并正常播放, 有的则只能播放单一格式的视频文件。前者被认为兼容性强。又如, 某些网站只能使用特定的浏览器访问, 也属于这类问题。此时网页即浏览器程序的输入数据。这样划分数据概念虽然不够完备( 即不一定每一个现实情境下的数据都能恰好归类于其中) , 但它能使我们讨论数据问题时保持
15、适当的针对性和相关性。二、 数据类型在计算机科学和程序设计中, 数据类型是数据的一种属性。通过对该属性的声明, 编程人员让编译器或解释器得知他使用相关数据的意图。5 图 1 . 1 关于数据含义的一种层次示意图华东师范大学出版社数据与数据结构1 . 计算机硬件不懂编码计算机硬件最核心的部分是C P U和存储器。存储器由若干能够存放固定字长数据的单元构成,C P U按照程序指令的要求将其中的数据( 由0和1构成) 读出, 执行某种操作后, 再将数据写回去。至于所处理的二进制数据代表什么, 可不可以做某种操作, 计算机硬件一般是不知道的。例如, 假设我们知道有两个存储单元存放的数据是A S C I
16、 I编码的字符“#” 和“ ?” ( 即0 0 1 0 0 0 1 1和0 0 1 1 1 1 1 1) , 但不小心让计算机对它们做加法了, 即0 0 1 0 0 0 1 1 + 0 0 1 1 1 1 1 1,C P U经过处理给出0 1 1 0 0 0 1 0。如果将结果看成A S C I I编码即表示字符“b” 。一般来看,这个操作没有任何意义。而“#”+“ ?”=“b” 是让人莫名其妙的。这个例子说明计算机可能会做出无意义的操作。而在另一些情况下, 这种“ 不理解” 二进制代码含义的情况则有可能导致计算机做出错误的操作, 造成损失。在计算机技术发展的早期, 程序员只能使用机器语言编程
17、, 他们必须非常熟悉各个二进制串的含义, 十分小心地编写程序, 避免让计算机做“ 不该做” 的操作。受此限制, 软件生产效率低下, 难以编出大规模复杂的程序, 阻碍了计算机在社会经济生活中的普及应用。2 . 程序语言应运而生高级程序设计语言, 例如F o r t r a n、 C、 J a v a、 P y t h o n等的诞生及其编译技术的发展, 为解决这个瓶颈问题建立了一条基本途径。程序设计语言要求程序员指出数据的类型( 数值型、 逻辑型、 字符型等) , 编译器根据不同数据类型的语义, 检查是否有“ 不合法” 的操作, 若发现,则在程序调试阶段就报告给程序员, 从而避免程序运行时出错。
18、例如在P y t h o n中, 如果运行如下程序: a =1b =2c = a *b就会产生一个类型错误(T y p e E r r o r) , 告知a和b是两个字符, 不能相乘。看起来简单, 实际上要做好各种类型错误的检查是很不容易的,6华东师范大学出版社第一章引言这是现代编译器的一个重要功能。探究活动在 Py t h o n中编一个会产生“ Ty p e Er r o r ” 的小程序。数据类型, 作为程序设计语言中的一个重要概念, 也是不断发展的, 以给程序员提供更有效的方式向计算机表达问题求解算法, 从而提高程序开发的效率。所谓“ 更有效” 的含义就是表达层次更高。例如一个将1 0
19、 0个数求和的程序, 原则上可以用1 0 0个标量来表示那些数( 需要1 0 0个变量名) , 在程序中要写9 9次加法, 非常麻烦。如果使用数组类型, 只需一个变量名, 用下标来指示不同的数, 可将9 9次加法蕴含在循环语句中, 呈现为一行加法指令, 使表达水平大大提高。在程序设计中, 变量是一个上位概念, 可以是标量(s c a l a r) , 可以是数组(a r r a y) , 还可以是其他数据类型。标量是包含一个值的变量, 而数组则可以包含多个值。3 . 数据类型让编程高效少错高级程序设计语言中各种数据类型的有效运用, 离不开编译技术的配合。在高级程序设计语言发展过程中, 有时会发
20、生程序语言中规定了某种功能, 但某一版本的编译器“ 不支持” 的情况, 经过一段时间后, 会出现新版编译器实现对该功能的支持。例如, 当赋值语句两边类型不相同时,P y t h o n 2会做一些缺省的处理, 而P y t h o n 3则要求程序员在程序中明确表达类型转换, 以避免因疏忽造成的错误。例如下面这段程序, 在P y t h o n 2和P y t h o n 3中的执行结果是不同的: a 1 = 3 a 2 = 3 0b = 2p r i n t a 1 b a 2 b P y t h o n 2的执行结果是: 1 1 . 5,P y t h o n 3的执行结果是: 1 . 5
21、 1 . 5。也就是说,P y t h o n 2如果看到两个操作数都是整数, 其计算结果就自动取整( 此操作称为“ 缺省” 操作) 。这种操作看似方便, 实则往往会带来潜在的错误。在P y t h o n 3中, 如果确实想将计算结果取7 华东师范大学出版社数据与数据结构整, 则需要使用p r i n t(i n t(a 1/b) ) 或者p r i n t(a 1/ /b) 语句来达到目的。数据类型同时也是其他某些学科领域中的基础概念。在统计学科中, 有类别数据和数值数据之分, 例如性别就是一种类别数据, 它可以取值“ 男” 或“ 女” 。计算机做统计数据处理时, 需要在计算机和统计这两个
22、学科不同数据类型体系之间建立起某种方便的对应, 如用整数值0和1分别表示统计类别数据值“ 男” 和“ 女” 。4 . 文件扩展名的意义与数据类型相关的一个概念是数据格式, 它是数据文件的一种属性, 常常通过文件扩展名来表达, 告知操作系统应该启动哪一个应用程序对它进行处理。图 1 . 2 不同类型的文件广义地讲, 数据类型和数据格式都是对本课程的必修模块中学过的“ 编码” 概念的应用, 即通过命名, 对0、 1串的语义作出规定。数据类型针对程序内部的数据, 数据格式则主要针对程序的输入输出数据。首先请通过如下实际操作案例, 体会数据格式的含义及其意义。打开电脑中的一个目录, 可看到如图1 .
23、2所示的显示画面。此目录中包含9个文件, 不同的图标分别代表其中的一个文件。用鼠标双击其中一个图标,会启动相应的应用程序, 并可进行某些操作, 如画图、 编辑文档、 看视频等。作为普通电脑用户, 对这些常规操作似乎已经习惯成自然, 通常不会去想这种过程为何能够发生。现在请尝试回答以下三个问题: (1) 为什么点击A. d o c x的图标, 文本编辑软件会被启动, 点击另一个文件D.m p 4, 视频播放器就会被启动呢? (2) 如果修改文件名, 将A. d o c x改成X. d o c x, 再次点击图标, 结果会发生改变吗? 如果将A. d o c x改成A. m p 4呢? (3)C.
24、 p n g和G.j p g的文件名和扩展名都不相同, 分别点击它们, 会成功启动同一个应用程序吗? 为什么?文件内容不变, 只是扩展名变了, 会导致计算机的不同行为。这样的问题与数据格式直接相关。计算机需要用户正确地告诉它数据文件的类型, 方能正常有效地工作。图1 . 2中的9个文件, 涉及8种8华东师范大学出版社第一章引言数据格式, 不同数据格式以不同文件扩展名的形式标识。使用计算机打开文件, 有时会出现所谓“ 乱码” 的情况。其实, 不一定真是文件的“ 码” 乱了, 而是打开它的程序不对。动手试一试, 我们能从操作中得到实际的体验。体验思考课堂上( 或课后) 实际动手体验本章第一节第二部
25、分中的例子, 回答所提出的问题, 包括讨论为什么修改文件名很顺利, 而修改文件扩展名可能会被警告。9 华东师范大学出版社数据与数据结构第二节数据结构不同于数据类型是多个学科都可能有的概念( 含义有别) , 数据结构是计算机学科的特有概念。数据结构是关于数据之间关系的描述,及其形成与访问的方式。关于数据结构的知识是计算机学科的基础知识, 运用数据结构的能力是开发高水平程序的要求。本节将从总体上讨论数据结构的意义及其与数据类型的关系, 一些典型的数据结构与应用则是本书要讲述的主要内容, 将在第三、 四、 五章详细介绍。一、 数据结构的意义这里说的“ 简单” 和“ 复杂” , 是就语义而言的。无论是
26、做科学计算、 进行文字处理还是上网冲浪, 这些复杂的程序应用, 在计算机硬件中化为简单的活动, 即在二值(0、 1) 逻辑上的高速变换。这个例子听起来简单, 但它是许多实际应用的抽象, 如互联网路由器就需要有类似的功能。实际情况中采用此结构的有计算机硬件的存储器、 程序中用的一维数组等。数据结构这一概念, 是随着程序设计技术的发展, 为弥合计算机硬件的简单性和程序应用的复杂性之间的鸿沟, 逐步形成并发展起来的。请通过以下应用实例, 初步体会上文所述。数据结构的选择影响程序执行的效率有一程序, 不断接收输入数据( 即它面对的是一个“ 数据流” ) , 针对每一个新到数据( 严格讲应称为数据元素)
27、 , 均需判断是否曾经接收过。若是, 则抛弃; 若否, 则保留。如何提高此判断的效率? 下面以输入数据流4, 3, 5, 1, 4, 2, 3, 1为例, 分析两种不同处理方法的效率。方法一, 采用简单的线性存储结构, 即存储空间中的存储单元是顺序编号的0, 1, 2, 3, , n - 1, 处理过程可描述如下: 每收到一个数, 就将其依次与空间中已有的数进行比较, 发现有相等的, 就停止; 若一直到最后还没有相等的, 就把这个新数放在后面。所给输入数据流处理后在存储空间中留下的结果为4, 3, 5, 1, 2。如果用比较次数作为衡量效率的指标, 针对原输入数据流中的8个数据, 每一个输入数
28、据需用的比较次数见表1 . 1, 总比较次数为1 7。1 0华东师范大学出版社第一章引言表 1 . 1 简单线性结构下的比较次数数据43514231比较次数01231424方法二, 想象有一种非线性的存储结构, 每当收到一个新的数, 就在该结构的引导下进行判断, 必要的话, 也对该结构进行动态更新, 以支持对后续数据的判断。图1 . 3以所给输入数据流展示该结构的变化过程, 图中所含8个线框中的内容, 顺序对应8个数据依次到来经判断处理后的结果, 虚线框内表示此次接收到的是已有数据, 仍需做判断, 但对整个留存结果无影响。图 1 . 3 非线性存储结构的变化过程每个节点可能左右两个子树都有,
29、也可能只有一个, 甚至没有。没有子树的节点称为叶节点。后面要学习的一个概念, 此处可以比拟俄罗斯套娃, 各层形态相同, 层层嵌套, 逐层缩小。鉴于此处示例数据不宜过多, 仅假设了用1次比较就能给出的判断( 在计算机中实际需要2次) , 从而得到总次数1 3 x = 0 1 + 0 2 x = 0 3F a l s e x0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4为规避这类问题, 在必须判断两个浮点数( 变量) 是否相等时, 在P y t h o n中可以使用语句r o u n d(x , d ) 对x四舍五入,d是小数保留的位数, 当然d的选择应适当。此处四舍五入的
30、语句如下: 2 2华东师范大学出版社第二章数据类型 r o u n d 0 1 + 0 2 1 0 3例2 . 4 复数类型: 有些语言( 包括P y t h o n) 也支持复数类型, 在P y t h o n中复数表示为a +b j形式, 例如3 + 2 j, 6 - 4 j等。而对于一个复数类型变量z, 可通过z . r e a l获得实部, 通过z .i m a g获得虚部, 它们均为单精浮点数。如在P y t h o n运行环境下: z = 4 + 3 j z i m a g3 0 z r e a l4 0 z = z + 2 - 1 j z 6 + 2 j 作业练习试利用 Py t
31、 h o n的复数类型写一个求解一元二次方程的程序, 即对任何实数 a 、 b和 c , 都能按照求根公式给出方程 a x2+b x +c =0的两个根。( 提示: Py t h o n有支持复数运算的函数库 c ma t h , 其中包含求平方根的函数s q r t 。 )2 3 华东师范大学出版社数据与数据结构第二节常用类型在基本数据类型之上, 程序设计语言一般会提供关键字, 让程序员能表达比较高层的常用数据类型, 典型的有字符串(s t r i n g) 和数组(a r r a y) 。顾名思义, 前者可以看成由若干字符“ 串接” 得到的整体, 后者则是由若干同类型数据元素构成的多维数据
32、体。它们不仅在逻辑上意味着是一个连续的数据体, 从而在程序中可以直接引用其中的单个元素或“ 片段” , 而且在物理上也通常存放于内存的一段连续空间中, 因此有较高的访问效率。这是字符串和数组的共同特点。一、 字符串原则上讲, 字符串也可采用链式存储( 如同第三章将学习的线性表) , 但除了在连接串与串以及子串替换操作时较方便, 总的来说不如顺序存储有效, 在程序语言中很少用到。1 . 什么是字符串字符串是由0个或多个字符组成的有限序列。一般使用顺序存储结构, 末尾以某个特殊符号( 如 0) 表示结束, 但此符号不作为字符串的内容, 也不计入字符串的长度, 图2 . 3是字符串“D a t a
33、T y p e” 顺序存储的例子。长度为 9结束标记串值DataType0空闲空间空间下标0123456789图 2 . 3 字符串存储示意图字符串通常用s = a0a1a2 an - 1表示, 其中s是串的名称,n是串的长度, 每个ai(0 i s t r 1 = D a t a T y p e s t r 2 = p y t h o n s t r 1D a t a T y p e s t r 2p y t h o n可直接使用下标的方式访问字符串中的字符或子串, 但下标越界会导致报错。如下所示: s t r 1 = D a t a T y p e s t r 1 0 D s t r 1
34、0 4 D a t a s t r 1 5 T y p e s t r 1 1 1 I n d e x E r r o r s t r i n g i n d e x o u t o f r a n g e体验思考1. 设已有字符串 s = I a m a Py t h o n le a r n e r . , 请用两种办法取出其中的 a m 子串。2. 数字重复出现次数的统计: 随机生成 50 0个三位正整数, 升序输出所有的不同的数字及每个数字重复的次数。2 5 华东师范大学出版社数据与数据结构3 . 字符串的比较有时需要对字符串进行排序。两个字符串之间的先后顺序( 或者说大小) 是如何确
35、定的呢? 不同的程序设计语言规定不尽相同。在P y t h o n中, 串的比较是通过组成串的字符的A S C I I编码大小的比较来进行的( 即把字符的A S C I I编码看成是十六进制正整数) 。例如字符a的编码是6 1 H, A是4 1 H, 那么就规定aA。对于两个字符串,先比较第一个字符, 如果第一个相同的话, 再比较第二个, 依此类推,一旦发现两串对应位置上有一个字符比另一个大, 就规定大字符所在的字符串大; 如果一个字符串已经没有字符可比了, 而另一个还有, 则后者大。当且仅当两个串的长度相等并且各个对应位置上的字符均相同时, 则称两个串相等。如下所示: s t r 1 = a
36、 d m i n s t r 2 = a d m i n i s t r a t o r s t r 3 = a d v i s e s t r 1 s t r 2F a l s e s t r 2 s t r 3F a l s e s t r 3 s t r 2 s t r 1T r u e4 . 字符串的基本操作P y t h o n中针对字符串对象提供的一些常用操作方法如表2 . 1中所示。表 2 . 1 Py t h o n中字符串常用操作方法针对长度为 n的字符串 s描述s i j k 切片: 提取对应的部分作为一个子串, 下边界 j 并不包含在内, k 为递增步长s . c o u
37、 n t ( s 1)返回子串 s 1在字符串中出现的次数2 6华东师范大学出版社第二章数据类型(续 表)针对长度为 n的字符串 s描述s . in d e x ( s 1)如果 s 中包含子串 s 1, 返回子串 s 1第一个字符所在位置, 如果没有, Va lu e Er r o rs . f in d ( s 1)如果 s 中包含子串 s 1, 返回子串 s 1第一次出现时第一个字符所在的位置, 如果没有, 返回-1s . r e p la c e ( s 1, s 2 )在 s 中用另一个字符串 s 2替换指定子串 s 1s . s p li t ( x )通过指定的分隔符 x 将字符
38、串 s 拆分为一组子串s . lo w e r ( ) 、 s . u p p e r ( )将字符串 s 中字符转换为小写或大写利用这些方法, 我们可以轻松满足一些看起来复杂的需求。例2 . 6 给出特定字符在一个字符串中的出现次数, 程序如下。 s t r = A l g o r i t h m+D a t a S t r u c t u r e s =P r o g r a m s s u b = a p r i n t s t r c o u n t s u b s t r c o u n t s u b 以上实例输出结果如下: s t r c o u n t s u b 3例2 .
39、7 从P y t h o n字符串中提取数字字符。 d e f i s_n u m u c h a r # 判断一个u n i c o d e编码的字符是否是数字字符i f u c h a r =u u 0 0 3 0 a n d u c h a r = t h i s d a t a 1 i f t h i s d a t a 0 = t h i s d a t a 2 r e t u r n t h i s d a t a 0 e l s e r e t u r n t h i s d a t a 2 i f t h i s d a t a 1 = t h i s d a t a 2 r
40、e t u r n t h i s d a t a 1 e l s e r e t u r n t h i s d a t a 2 于是, 用户可在程序中应用如下: a b c = e v a l i n p u t a b c x =T r i p l e a b c p r i n t x w i n 用户不仅不用关心T r i p l e是怎么实现的, 而且即使已经知道了T r i p l e是怎么实现的, 也只能用w i n 来访问一个具有T r i p l e类型的数据x。其他操作会被P y t h o n认为是非法的。假设用户已知T r i p l e是用一个列表实现的, 在创建了
41、具有T r i p l e类型的数据对象x后, 用3 9 华东师范大学出版社数据与数据结构户试图在程序中访问x 0 ,P y t h o n就会报错。这就叫数据被“ 封装了” , 相当于对数据提供了一种保护, 只允许做规定的操作。当然, 有时候也需要访问“ 内部数据” , 例如希望定义如下将两个T r i p l e相加的函数: d e f a d d_t r i p l e x y z =T r i p l e 0 0 0 z 0 =x 0 + y 0 z 1 =x 1 + y 1 z 2 =x 2 + y 2 r e t u r n z 此函数需要访问T r i p l e中的单个数据。程
42、序语言一般也提供相应的支持, 在P y t h o n中可在类的定义中用_s e t i t e m_( ) 和_g e t i t e m_( ) 来指出这种可能。探究活动修改正文中的 Tr i p le实现, 让下面的程序能正确执行。 a b c = e v a l i n p u t a b c x =T r i p l e a b c a b c = e v a l i n p u t a b c y =T r i p l e a b c z = a d d_t r i p l e x y p r i n t z w i n 项目实践讨论本章项目情境中数据( 各属性) 的关系和逻辑结构
43、, 用 A DT( 即抽象数据类型) 的方法表示它们。收集数据( 属性值) , 编程实现数据的存储和相似度计算。讨论结果准确性的评价标准, 并根据需要调整方案。作业练习用 Py t h o n语言的类结构来定义“ 复数” 的抽象数据类型。 c l a s s C o m p l e x A o b j e c t 4 0华东师范大学出版社第 三 章基础数据结构本章学习目标理解线性表、 栈、 队列三种数据结构的含义、 基本操作、 应用场景。掌握实现上述三种数据结构的一种方法, 了解不同实现方法的差异。能够将它们应用于本章项目任务中。华东师范大学出版社数据与数据结构数据结构, 是表达数据及其之间关
44、系的一个概念。只有在恰当的数据结构支持下, 计算机算法才能够实现为高效运行的程序。数据结构中的“ 数据” , 可能直接对应程序输入的原始数据, 也可能是程序运行中生成的中间数据。数据结构中表达的关系, 可能是原始数据中呈现的自然关系, 也可能是算法逻辑所要求的关系。如在本书引言中指出的, 数据结构和数据类型有着密切的关系。与数据类型类似, 一种数据结构通常都对应有一组可以施行于其上的操作。就好比对于数值型数据, 可以做加减乘除四则运算; 对于字符串, 可以提取其中的子串等。因此, 也可以( 但不必须) 基于数据结构定义抽象数据类型。通过这两个概念的交织与嵌套, 我们得以描述各种复杂的事物, 进
45、而让计算机也能够处理它们。作为数据结构学习的开始, 本章学习线性表、 栈和队列三种基本数据结构。数据元素之间的结构性关系, 对数据元素的访问方式, 数据结构本身在特定操作下的动态变化, 尤其是与算法互动的基本方式, 这些内容是在学习中需要着意体会的。本章知识结构4 2华东师范大学出版社第三章基础数据结构项目主题送餐机器人的行走路线项目情境随着信息时代的到来, 越来越多的智能机器人进入了我们的工作和生活中。看! 不少餐厅开始使用送餐机器人( 如图 3 . 1( a ) ) , 这些可爱的机器人在厨房和各个餐桌间来回穿梭, 为客人配送菜品。它们是如何做到高效、 准确地在餐厅之中行走的呢?(a) (
46、b)餐厅通常是由餐桌和通道组成的, 于是每一个餐厅都有一个类似于图 3 . 1( b )所示的平面图。其中橙色表示机器人可以到达的地方, 蓝色表示餐桌或其他不能通过的设施。本项目的目标为, 给定任意一个类似于图 3 . 1( b ) 的平面图, 以及一个起始点( 例如图中左上角厨房处) 和一个终点( 例如右下角餐桌处) , 为机器人规划出一条最佳的行走路线。项目任务任务 1任务 2任务 3任务 4 分析项目中的关键步骤, 寻找特征, 建立数据模型。 设计不同的方案,选择合适的数据结构进行组织和存储。 选择其中一种方案编程实现, 显示一条从任意给定起点到终点的路线, 归纳总结机器人送餐方案, 探
47、究列举在生活中更广泛的应用。4 3 图 3 . 1 机器人送餐示意图华东师范大学出版社数据与数据结构第一节线性表线性表是一种最基础的数据结构, 是指在位置上有前后顺序( 线性序) 的一组数据元素, 从而可以界定出第一个数据元素、 第二个数据元素以及最后一个数据元素。程序可以在线性表的任意位置执行插入和删除数据元素的操作, 导致其长度的变化。线性表的主要应用体现在其中数据元素的位序与它们值序的关系上。一、 什么是线性表反映现实世界的数据常常具有一种天然的顺序。例如, 每小时测量一次气温, 将得到的2 4个数按照顺序写出来最有意义。又如, 若有人告诉你下面这些数是2 0 0 3年到2 0 1 8年
48、参加全国高考的人数( 单位: 万) : (6 1 3, 7 2 9, 8 7 7, 9 5 0, 1 0 1 0, 1 0 5 0, 1 0 2 0, 9 4 6, 9 3 3, 9 1 5, 9 1 2, 9 3 9, 9 4 2, 9 4 0, 9 4 0, 9 7 5)你会很自然地认为它们是按照年份顺序排列的。线性表, 就是表达这类数据的数据结构概念, 一般地记为: (a0, a1, , ai - 1, ai, ai + 1, , an - 1)有同学可能好奇, 第一个元素的下标怎么不从1开始呢? 这是计算机科学中的一个有趣现象,在有些场合, 一组数据元素的第一个的确也是从1开始编号的,
49、 但在许多场合( 尤其在现代程序设计中) 则是从0开始。为什么呢? 当你们学到后面队列一节的时候应该能得到答案。这里, 我们不妨先认识这种现象。其中,a0称为第一个元素,a1为第二个元素; 对于n i 0, 称ai为ai - 1的后继,ai - 1为ai的前序;n称为线性表的长度, 即其中元素的个数。线性表不仅能静态地存放这类数据, 还要能支持对这类数据的操作。比如一个班级的学生名册是按照姓氏笔画排序的, 学期中转来一个新同学, 要把他的名字放入名册中的适当位置( 保持整体按姓氏笔画排序的规则) , 很可能需要把有些同学的名字往后挪一个位置, 中间空出一个位置给他。反过来, 若一个同学转走了,
50、 也需要对名册做出调整。这样的情况, 在线性表相关操作上分别称为“ 插入” 和“ 删除” 。为了支持高效的程序设计, 线性表上还可以有其他操作, 但这两个是最基本、 最具标志性的操作, 它们的共同点是改变了线性表的长度( 即线性表数据元素的个数) , 具有动态性。4 4华东师范大学出版社第三章基础数据结构二、 线性表的实现与应用1 . 线性表实现的基本考虑一般而言, 实现一种数据结构会涉及两个方面, 一是如何存储它所包含的数据元素集合, 二是如何支持在它上面定义的操作。线性表有两种实现方式: 顺序存储实现和链接存储实现。它们的基本形态如图3 .2所示。(a) 顺序存储线性表 (b) 链接存储线
