1、3.2 数据与结构学 习 目 标3.能比较不同数据结构的特点，会选用合适的数据结构组织数据解决简单问题。2.了解树、图结构的基本概念及特点。1.熟悉队列结构的概念和特点，能够使用python语言对队列进行操作。各种类型的数据被编码表示成二进制数据，存储到计算机中。在利用计算机解决问题的过程中，这些数据将是最基本的元素。但是，零散孤立的数据是很难被有效利用的。根据所要解决的问题的不同，我们还需要依据数据关系建立合适的结构。采用这些结构将数据组织起来，才能有利于操作和管理，进而更高效地解决实际问题。本节我们将学习表、队列、树、图等数据结构，了 解结构中数据间的关系，在一定的结构上完成算法设计;学会
2、在生活中根据实际问题，建立合适的数据结构，进而运用所学的知识解决问题。阅读教材第56页至57页任务一的活动1“了解订单数据”，填写表3.2.1.（P31）网站名称网站名称订单中的数据订单中的数据Python中对应的数据类型中对应的数据类型A网站商品名称字符串单价浮点型数量整型B网站商品名称字符型数量整型价格浮点型数据类型数据类型数据类型数据类型简单数据类型复合数据类型简单数据类型不能分解成更小的数据类型。如：整型（int）、浮点型（float）、字符串（str）、布尔型（bool）。复合数据类型则由简单数据类型组成。如：元组（tuple）、集合（set）、列表（list）、字典（dict）。数
3、据类型数据类型一、数据类型认识Python简单数据类型 在Python语言中，简单数据类型有整数（int）、浮点数（float）、字符串（str）、布尔（bool）、复数（complex）等数据类型。整数（整数（int）用来表示整数数值，就是没有小数部分的数值。在Python中，整数包括正整数、负整数和0，并且它的位数是任意的，主要用来进行数学运算。浮点数（浮点数（float）浮点数由整数部分和小数部分组成，主要用于处理包括小数的数。字符串（字符串（str）在Python中，加了引号的字符都被认为是字符串，其声明有三种方式，分别是：单引号、双引号和三引号，这三种引号形式在语义上没有差别，只是在
4、形式上有些差别，其中单引号和双引号中的字符序列必须在一行上，而三引号内的字符序列可以分布在连续的行上。布尔（布尔（bool）和其他编程语言一样，Python布尔类型也是用于逻辑运算，有两个值：True（真）和False（假）。在Python中的布尔值可以转化为数值，其中True表示1，False表示0。type(8)#type()函数返回数据的类型#返回int类型type(3.14)#返回float类型type(Thank you!)#返回str类型type(True)#返回bool类型数据类型数据类型简单数据类型Python语言中，复合数据类型有元组（tuple）、集合（set）、列表（di
5、ct）等。l 元组 BookInfo0=(“Id0010230,15.68,36”)BookInfo1=(“Id2315937,20,2”)bookinfo0=(id0010230,15.58,36)type(bookinfo0)bookinfo1=(id2315937,20,2)bookinfo1120数据类型数据类型复合数据类型l 集合Bookset=bookinfo0,bookinfo1 bookinfo0=(id0010230,15.68,36)bookinfo1=(id2315937,20,2)bookset=bookinfo0,bookinfo1 type(bookset)l 列表
6、Booklist=bookinfo0,bookinfo1 bookinfo0=(id0010230,15.68,36)bookinfo1=(id2315937,20,2)booklist=bookinfo0,bookinfo1 type(booklist)复合数据类型数据类型数据类型一、数据类型Python复合数据类型某用户预订的商品编号为ID0010230、单价为15.68元，数量为36，可将这3个不同类型的简单数据组织成“元组”复合数据类型：BookInfo0=(ID0010230,15.68,36)type(BookInfo0)#返回元组类型另一用户预订的商品编号为ID2315937、单
7、价为20元，数量为2，可记作：BookInfo1=(ID2315937,20,2)BookInfo1120#返回元组BookInfo1中索引为1的项的值在Python语言中，复合数据类型有元组（tuple）、集合（set）、列表(list)、字典（dict）等元元组组 一、数据类型订单汇总，可以定义为一个集合(集合里的项称为元素，彼此之间没有顺序)：BookSet=BookInfo0,BookInfo1 type(BookSet)#返回集合类型 BookSet(ID2315937,20,2),(ID0010230,15.68,36)#返回集合的值 BookInfo0 in BookSet#测试
8、元素BookInfo0是否属于集合BookSetTrue#返回逻辑真集合 订单汇总，也可以按订单产生的先后顺序组成一个列表(列表里的项是有顺序编号的)：BookList=BookInfo0,BookInfo1 type(BookList)#返回列表类型 BookList0(ID0010230,15.68,36)BookList1(ID2315937,20,2)BookList01*BookList02+BookList11*BookList12604.48#返回计算结果列表 是Python中标准数据类型之一，它也是容器类型，可以存储不同的数据，并且具有可变性。字典顾名思义，就是拥有类似字典的特
9、性，通过“键”能够快速查找对应的“值”。这种基本的数据结构称为“键值对”。广义上来说，其他标准数据类型中也存在“键值对”，只是它们的键只能是索引号，而字典的键可以是不可变的数据类型（数字、字符串和元组）。实例1tel=dict(sape,4139),(guido,4127),(jack,4098)print(tel)#输出结果为：sape:4139,guido:4127,jack:4098#会发现直接转化成字典。key:value实例2tec=x:x*2 for x in(2,4,6)print(tec)#输出结果2:4,4:16,6:36字典(dictionary)实例3 knights=A
10、pollo:the Brave,Prothemeus:the uglyfor k,v in knights.items():print(k,-,v)#输出结果Apollo-the BraveProthemeus-the ugly实例4for i,v in enumerate(tick,Dida,Mouo):print(i,v)#enumerate()函数返回的是列表中的索引与键值#输出结果0 tick1 Dida2 Mouo实例5questions=name,quest,favoriate coloranswers=lacelot,the holy grail,bluefor q,v in z
11、ip(questions,answers):print(What is your 0?It is 1.format(q,v)#通过zip函数把两个不相关的序列，弄成一组#输出结果为：What is your name?It is lacelot.What is your quest?It is the holy grail.What is your favoriate color?It is blue.数据类型转换：函数格式函数格式使用示例使用示例描述描述int(x,base)int(8)可以转换的包括String类型和其他数字类型，但是会丢失精度 float(x)float(1)/float
12、(1)可以转换String和其他数字类型，不足的位数用0补齐，例如1会变成1.0complex(real,imag)complex(1)/complex(1,2)第一个参数可以是String或者数字，第二个参数只能为数字类型，第二个参数没有时默认为0str(x)str(1)将数字转化为Stringrepr(x)repr(Object)返回一个对象的String格式eval(str)eval(12+23)执行一个字符串表达式，返回计算的结果,如例子中返回35list(s)list(1,2,3,4)将序列转变成一个列表，参数可为元组、字典、列表，为字典时，返回字典的key组成的集合chr(x)ch
13、r(0 x30)chr()用一个范围在 range（256）内的（就是0255）整数作参数，返回一个对应的字符。返回值是当前整数对应的ascii字符。ord(x)ord(a)返回对应的 ASCII 数值，或者 Unicode 数值hex(x)hex(12)把一个整数转换为十六进制字符串oct(x)oct(12)把一个整数转换为八进制字符串编制订单数据处理程序 网店接受了大量的订单，如何安排发货呢?实际上，网店在处理订单时，一般采取“先下单，先发货”的原则。因此，所有的订单将按照下单的时间顺序放进一个列表中，先放进去的先发货，所有订单排列在一起，像是一群人在排队。下面的Python程序可以实现以
14、下功能:提供“添加订单”“发货”“查看订单列表”“退出”四个操作选项。当我们选择“1”后输入订单数据，程序将订单数据添加到订单数据表中;选择“2”后，程序将当前订单列表中最早进入的数据删除(表示已安排发货处理);选择“3”可以显示当前订单列表中所有的订单数据;选择“4”将结束运行。请你完善下列Python程序，模拟添加订单和发货的过程，了解订单列表的操作过程。编制订单数据处理程序listque=#定义列表listque存储订单x=0while(x!=4):#当x=!4时，执行循环 print(1.添加订单)print(2.发货)print(3.查看订单列表)print(4.退出)x=int(i
15、nput(输入你的选择:)#输入选择项 if x=1:y=input(输入订单编号:)#输入订单编号 listque.append(y)#在列表listque中添加订单号 elif x=2:if len(listque)=0:#如果订单列表为空 print(订单列表为空)else:print(发货单号:+listque.pop(0)elif x=3:print(等待发货:,listque)#查询列表listque中的订单号 print()input(运行完毕，请按回车键退出.)订单处理程序数据类型数据类型数据结构：存在特定关系的数据元素的集合。常用的数据结构有：数组，栈，链表，队列，树，图，堆
16、，散列表等 数据结构也称逻辑结构：集合结构、线性结构、树结构、图结构（网状结构）数据结构数据结构数据结构数据结构 线性数据结构线性数据结构又称线性表。特点：除首元素没有前驱元素、尾元素没有后继元素外，其它元素都只有一个前驱元素和一个后继元素。数据元素之间是一对一的关系。常见的线性数据结构（1）栈 常见的线性结构有：栈、队列和串等都属于线性结构。栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进
17、先出。从一端放入元素的操作称为入队，取出元素为出队，示例图如下：（2）队列 典型的例子如超市里排队付款的队伍。队列是一种有限制的线性结构。特点：数据元素只能在一端依次添加（进队），在另一端依次删除（出队）。队列在Python中，用列表实现队列的创建；队列的基本操作：入队，出队，求队长，判队空。队列数据结构数据结构队列的计算机实现：在Python中，队列一般用列表(list)实现，常用操作：q=#定义空列表qq.append(x)#元素x入队（添加）q.pop(0)#返回队首元素,队首元素出队(删除)len(q)#返回队列q的长度(元素个数)qi#返回列表q中索引(index)为i的元素.索引有
18、2套编号方式：正编号(从左到右编号依次为0,1,2,)和负编号(从右到左编 号依次为-1,-2,-3,)数据结构数据结构 队列 阅读教材“探究快递配送过程”的活动1，了解快递派送线路，完成P60的连点成树。派送点学校收发室某单位传达室收件人A同学收件人B同学职工小王职工小李ABCDEFG数据结构数据结构 树结构树的递归定义如下：树是由n（n=0）个节点组成的有限集合。若n=0，则称为空树。任何一个非空树均满足以下二个条件：（1）仅有一个根节点。（2）当n0时，其余节点可分为m(m=0)个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。特点：数据元素之间是一对多的关系。数据结构数据结
19、构树结构是一种具有层次关系的非线性结构。树结构树结构树是一种具有层次关系的非线性数据结构快递到达目的地城市后，物流图的结构呈树状了解物流网络 岳阳市 长沙市 南通市 南京 泰州市 扬州市了解物流网络数据结构数据结构 图结构图结构 结构是由-组节点(称为顶点)和-组节点间的连线(称为边或弧)构成的一种数据结构。图结构中的每个顶点都可以与其他顶点有边相连，图结构中数据元素之间是多对多的关系。图3.2.6表示的是商品从供货点到收货点的派送过程的图结构。图3.2.7也是-个图结构，其中，标为(4“1”的顶点与两条边相连，顶点“4”与“2”“8”“9”相连。在物流网络中，分拨中心、配送中心、货物需求点等
20、可以抽象为图的顶点，城市道路、各级铁路等可以抽象为图的边，如城市以及城市之间的运输道路就是图结构。利用图结构，我们还可以解决物流中的许多问题，如道路网络分析、车辆运营安排等。图结构是由一组节点（称为顶点）和一组节点间的连线（称为边或弧），构成的一种数据结构。特点：图结构中的每个顶点都可以与其他顶点有边相连，数据元素之间是多对多的关系。数据结构数据结构 图结构所有的顶点构成一个顶点集合，所有的边构成边的集合，一个完整的图结构就是由顶点集合和边集合组成。图结构在数学上记为以下形式：G=（V,E）或者 G=（V（G），E（G）其中 V（G）表示图结构所有顶点的集合，顶点可以用不同的数字或者字母来表示
21、。E（G）是图结构中所有边的集合，每条边由所连接的两个顶点来表示。图结构中顶点集合V（G）不能为空，必须包含一个顶点，而图结构边集合可以为空，表示没有边。无向图无向图如果一个图结构中，所有的边都没有方向性，那么这种图便称为无向图。典型的无向图，如图二所示。由于无向图中的边没有方向性，这样我们在表示边的时候对两个顶点的顺序没有要求。例如顶点VI和顶点V5之间的边，可以表示为(V2，V6),也可以表示为(V6，V2)。对于图二无向图，对应的顶点集合和边集合如下：V（G）=V1，V2，V3，V4，V5，V6 E（G）=（V1,V2），（V1，V3），（V2，V6），（V2，V5），（V2，V4），（
22、V4，V3），（V3，V5），（V5，V6）有向图有向图一个图结构中，边是有方向性的，那么这种图就称为有向图，如图三所示。由于图的边有方向性，我们在表示边的时候对两个顶点的顺序就有要求。我们采用尖括号表示有向边，例如表示从顶点V2到顶点V6，而表示顶点V6到顶点V2。对于有向图，对应的顶点集合和边集合如下：V（G）=V1，V2，V3，V4，V5，V6 E（G）=，快递门店B 快递门店A家 快递门店C地点地点地点地点时间时间/分分家-快递门店A2家-快递门店B5家-快递门店C10A-B4A-C6B-C4该同学家及快递店间步行所需时间表规划取快递最快路线数据结构数据结构数据结构数据结构加权图快递门
23、店A 快递门店C 家2610454规划取快递最快路线快递门店B 【朴素算法】穷举遍历，依次列出所有可能走法。将图中每个节点进行编号，编号互不相同：如作为根节点的“家”编号为“X”,其3个子节点（快递门店A，快递门店B，快递门店C）分别编号为“A”“B”“C”，详见下图。求解最短用时分析树数据结构数据结构【朴素算法】穷举遍历，依次列出所有可能走法如上图将图中每个节点进行编号，编号互不相同：如作为根节点的“家”编号为“X”,其3个子节点（快递门店A，快递门店B，快递门店C）分别编号为“A”“B”“C”，详见下图。【算法演示【算法演示1】求解最短时间（基于图】求解最短时间（基于图3.2.10的分析树
24、）的分析树）【算法演示【算法演示2】求解最短时间（直接对图】求解最短时间（直接对图3.2.9进行深度优先遍历）进行深度优先遍历）练习练习人、狼、羊、菜过河问题：有一个人带着一只狼、一只羊和一捆白菜，来到一条河边，河边只有一条小船，人每次过河最多只能带一样，如果人不在现场，狼就要吃羊，羊就要吃菜。他应该怎样安排过河呢？请完成下面的“树”结构分析图，帮他找到可行的过河方案。提示：可约定对象在左岸用0表示，在右岸用1表示。程序与调试程序与调试结构类型结构类型数据（节点）之间数据（节点）之间的关系的关系生活中相应结构应用举例生活中相应结构应用举例队列队列（线性）（线性）一对一一对一排队排队（上车、过马路、付款）、医院就诊电子牌上的就诊队列树树一对多一对多书的目录结构书的目录结构图图多对多多对多全国航运图，铁路运输图全国航运图，铁路运输图数据结构的比较数据结构的比较l 队列是一种线性数据结构，本质特征是FIFO。l 队列在Python中，用列表实现队列的创建；队列的基本操作：入队，出队，求队长，判队空。l 树结构和图结构是两种比较难的数据结构，我们应领会其本质特征，会用树结构和图结构对工作、学习、生活中的具体问题进行抽象和分析，解决一些简单问题。课堂小结
