《Python语言教程》课件-第9章 数据结构与操作

ISBN:978-7-111-59261-7

数据结构就是用来将数据组织在一起的一种结构形式。换句话说，数据结构是用来存储一系列关联数据的一种类型。在Python中已有四种内建的数据结构，分别是List、Tuple、Dict与Set。大部分的应用程序不需要其他类型的数据结构就可以实现。本章主要介绍一些传统数据结构（譬如：栈、队列、链表等）的Python实现及其表达操作。第9章数据结构与操作学习重点和难点：基本数据结构常用操作

基本数据结构及其操作的Python语言实现，Python语言初步应用的体现。第9章数据结构与操作9.1数据结构9.2常用操作9.3应用实例第9章数据结构与操作第9章数据结构与操作9.1.1数组9.1.2列表与堆栈9.1.3栈的实现类9.1.4列表与队列9.1.5队列的实现类9.1.6推导式与嵌套解析9.1.7遍历技巧9.1.8链表操作9.1.9(二叉树）结构9.1.1数组

数组是必须在使用前预先请求固定大小的内存空间，一般放同类型的若干数据。为此数组有以下特性：1）请求空间后大小固定，不能再改变（会有数据溢出问题）；2）在内存中有空间连续性的要求，数组内存空间是专用的；3）在旧式编程语言中（如C语言），程序不会对数组的操作做下界判断，也就有潜在的越界操作的风险。

9.1.1数组

因为简单数组强烈倚赖电脑硬件之内存，所以不适用于现代的程序设计。欲使用可变大小、硬件无关性的数据类型，Java等程序设计语言均提供了更高级的数据结构：ArrayList、Vector等动态数组。

从严格意义上来说：Python里没有严格意义上的数组。但一般来说List就是Python的高级数据结构，就可以认为它是Python里的数组。List作为数组的应用例子。

9.1.2列表与堆栈什么是堆栈（Stack）？堆栈也可直接称栈，在计算机科学中，是一种特殊的串列形式的数据结构，它的特殊之处在于只能允许在链接串列或阵列的一端（称为堆叠顶端指标top）进行加入资料（Push）和输出资料（Pop）的运算。另外堆叠也可以用一维阵列或链接串列的形式来完成。由于堆叠数据结构只允许在一端进行操作，因而按照后进先出（LIFO,LastInFirstOut）的原理运作。出栈栈底元素栈底元素栈底栈顶入栈ana2a19.1.2列表与堆栈特点：先入后出，后入先出。除头尾节点之外，每个元素有一个前驱，一个后继。操作：从原理可知，对堆栈(栈)可以进行的操作有：1）top()：获取堆栈顶端对象；2）push()：向栈里添加一个对象；3）pop()：从栈里推出一个对象。

在Python中，列表就可以借用来实现一个栈，能提供接口如下：1）s=[]#创建一个栈2）s.append(x)#往栈内添加一个元素3）s.pop()#在栈内删除一个元素4）nots#判断是否为空栈5）len(s)#获取栈内元素的数量6）s[-1]#获取栈顶的元素9.1.3栈的实现类栈是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶，Top）进行加入数据（Push）和输出数据（Pop）的运算。没有了位置概念，保证任何时候可以访问、删除元素都是对此前最后存入的那个元素，确定了一种默认的访问顺序。下面是栈的一种实现类。栈结构实现：栈可以用顺序表实现，也可以用链表实现。栈的操作有：Stack()创建一个新的空栈push(item)添加一个新的元素item到栈顶pop()弹出栈顶元素peek()返回栈顶元素is_empty()判断栈是否为空size()返回栈的元素个数

栈的实现类：classStack(object):#栈的实现类

def__init__(self):self.item=[]defis_empty(self):returnself.item==[]defpush(self,item):self.item.append(item)defpop(self):returnself.item.pop()defpeek(self):ifself.is_empty():print('stackisempty')else:returnself.item[len(self.item)-1]defsize(self):returnlen(self.item)什么是队列（Queue）？和堆栈类似，只是队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。所以队列是是先进先出（FIFO,First-In-First-Out）的线性表。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作。假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样删除时总是从a1开始，而插入时总是在队列最后。这也比较符合日常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。特点：1）先入先出，后入后出；2）除尾节点外，每个节点有一个后继，除头节点外,每个节点有一个前驱。操作：1）push（）：入队；2）pop（）：出队。9.1.4列表与队列同栈一样，也可以用列表自己编写队列类。下面是队列的一种实现类。队列的实现：队列也可以用顺序表或者链表实现。队列操作：Queue()创建一个空的队列enqueue(item)往队列尾添加一个item元素dequeue()从队列头部删除一个元素is_empty()判断一个队列是否为空size()返回队列的大小travel()从头到尾遍历输出队列中的所有元素9.1.5队列的实现类1、列表推导式列表推导式提供了从序列创建列表的简单途径。通常应用程序将一些操作应用于某个序列的每个元素，用其获得的结果作为生成新列表的元素，或者根据确定的判定条件创建子序列。每个列表推导式都在for之后跟一个表达式，然后有零到多个for或if子句。返回结果是一个根据表达式从其后的for和if上下文环境中生成出来的列表。如果希望表达式推导出一个元组，就必须使用括号。9.1.6推导式与嵌套解析这里我们将列表中每个数值乘3，获得一个新的列表：>>>vec=[2,4,6]>>>[3*xforxinvec]#[6,12,18]现在来增加点复杂度：>>>[[x,x**2]forxinvec]#[[2,4],[4,16],[6,36]]这里对序列里每一个元素逐个调用某方法：>>>freshfruit=['banana','loganberry','passionfruit']>>>[fruit.strip()forfruitinfreshfruit]['banana','loganberry','passionfruit']9.1.6推导式与嵌套解析在字典中遍历时，关键字和对应的值可以使用items()方法同时解读出来：>>>knights={'gallahad':'thepure','robin':'thebrave'}>>>fork,vinknights.items():...print(k,v)#输出：gallahadthepure/nrobinthebrave在序列中遍历时，索引位置和对应值可以使用enumerate()函数同时得到：>>>fori,vinenumerate(['tic','tac','toe']):...print(i,v)#输出：0tic\n1tac\n2toe(\n代表换行，下同)同时遍历两个或更多的序列，可以使用zip()组合：>>>questions=['name','quest','favoritecolor']>>>answers=['lancelot','theholygrail','blue']>>>forq,ainzip(questions,answers):...print('Whatisyour{0}?Itis{1}.'.format(q,a))Whatisyourname?Itislancelot.Whatisyourquest?Itistheholygrail.Whatisyourfavoritecolor?Itisblue.9.1.7遍历技巧要反向遍历一个序列，首先指定这个序列，然后调用reversesd()函数：>>>foriinreversed(range(1,10,2)):...print(i,end='')#输出：97531要按顺序遍历一个序列，使用sorted()函数返回一个已排序的序列，并不修改原值：>>>basket=['apple','orange','apple','pear','orange','banana']>>>forfinsorted(set(basket)):...print(f,end='')#输出：applebananaorangepear9.1.7遍历技巧1、什么是链表链表（Linkedlist）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存有下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(log2n)和O(1)。9.1.8链表操作

特点：使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

操作：1）init()：初始化；2）insert()：插入；3）travel()：遍历；4）delete()：删除；5）find()：查找。9.1.8链表操作根据线性表的实际存储方式，分为两种实现模型：1）顺序表，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。2）链表，将元素存放在通过链接构造起来的一系列存储块中。顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活。链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。9.1.8链表操作链表（Linkedlist）是⼀种常⻅的基础数据结构，是⼀种线性表，但是不像顺序表⼀样连续存储数据，而是在每⼀个节点（数据存储单元）里存放下⼀个节点的位置信息（即地址）。根据结构的不同，链表可分为单项链表、单项循环链表、双向链表、双向循环链表等。这里简单介绍单项链表。2、链表的实现链表由一系列不必在内存中相邻的结构（或节点）构成，这些对象按线性顺序排序。每个节点含有数据元素（数据域）和指向后继元素的指针（指针域），最后一个单元的指针指向NULL，表示链表结束。为了方便链表的删除与插入操作，可以为链表添加一个表头。如图所示，其中含有链表插入节点（通过两次节点调整）与删除节点（通过修改一个指针）操作示意，通过不断插入与删除节点来维护链表的变化。9.1.8链表操作D1D2D3D4D5D45D1NullhdH删除D3节点链表头数据指针插入D45节点单链表的操作主要有：1）isEmpty()链表是否为空；2）size()链表长度；3）travel()遍历整个链表；4）add(item)链表头部添加元素；5）append(item)链表尾部添加元素；6）insert(pos,item)指定位置添加元素；7）remove(item)删除节点；8）search(item)查找节点是否存在；9）index(item):查找索引元素在链表中的位置。9.1.8链表操作堆的定义：具有n个元素的序列（h1,h2,...,hn)，当且仅当满足（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=h2i+1）(i=1,2,...,n/2)时称之为堆。不失一般性，这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。9.1.9（二叉树）结构为此，堆是一种数据结构，可以将堆看作一棵完全二叉树，这棵二叉树满足，任何一个非叶节点的值都不大于（或不小于）其左、右子节点的值。关于二叉树的结点：1）在二叉树的第i层上至多有2i-1个结点。提示：可以用归纳法，假若第i层有至多2i-1个结点，那么第i+1层至多就有2*2i-1即2(i+1)-1个结点。2）深度为k的二叉树至多有2k-1个结点。考虑满二叉树的情况，所有结点求和所得。3）有n个结点的完全二叉树的高度h为

。结合2），n<=2h-14）完全二叉树结点编号如图所示。9.1.9（二叉树）结构9.1.9（二叉树）结构初始时可以把n个元素的序列看作是一棵顺序存储的二叉树（如图所示，即ABCDEFGHIJKLMNOPQ顺序排列存储），调整它们的存储顺序，使之成为一个堆，这时堆的根节点的数是最大的。这样，按图所示的结点编号顺序就可以用列表来表达完全二叉树(列表模拟完全二叉树)，并对这样的列表来调整顺序，来建立堆。

设有[49,38,65,97,76,13,27,49]列表，为完全二叉树节点数据。建堆前为如下图所示的完全二叉树：9.1.9（二叉树）结构

堆建好了，基于堆结构，可以有许多操作的，譬如：1）堆尾部插入元素；2）堆尾部删除元素；3）取堆顶元素；4）求堆里元素个数；5）判断堆是否空；6）堆向下调整；7）堆向上调整；8）替换堆顶元素等等，这些操作的具体实现略。9.1.9（二叉树）结构9.2常用操作9.2.1查找9.2.2排序9.2.1查找1、无序表查找

无序表查找就是对数据不排序的线性表查找、遍历数据元素。

算法分析：最好情况是在第一个位置就找到了，此为O(1)；最坏情况在最后一个位置才找到，此为O(n)；所以平均查找次数为(n+1)/2。最终时间复杂度为O(n)。例如：defsequential_search(lis,key):length=len(lis)foriinrange(length):

iflis[i]==key:returnielse:returnFalseif__name__=='__main__':LIST=[21,25,1,5,8,123,22,54,7,99,300,222,30,22]result=sequential_search(LIST,123)print(result)Python的列表（list）中查找元素,并不需要编写如上程序，可以直接使用list.index()方法来查找，但该方法其时间复杂度也为O(n)。list.index()方法查找代码如下：

LIST=[21,25,1,5,8,123,22,54,7,99,300,222,30,22]

LIST.index(123)9.2.1查找2、有序表查找有序表中的数据必须按某个主键进行某种排序。此时，使用二分查找等方法效率更高。其基本原理如下：1）从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；2）如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较；3）如果在某一步骤数组为空，则代表找不到。二分查找也称为折半查找，算法每一次比较都使搜索范围缩小一半，其时间复杂度为O(log2n)。【例9-2】分别用递归和循环方法来实现二分查找。9.2.1查找Python有一个bisect模块，用于维护有序列表。bisect模块实现了一个算法用于插入元素到有序列表。在一些情况下，这比反复排序列表或构造一个大的列表再排序的效率更高。bisect是二分法的意思，这里使用二分法来排序，它会将一个元素插入到一个有序列表的合适位置，这使得不需要每次调用sort的方式维护有序列表。使用示例见书本。9.2.2排序常用的排序算法有如下8种，它们分别为：选择排序、冒泡排序、插入排序、归并排序、快速排序、堆排序、基数排序、希尔排序等。9.2.2排序1、选择排序基本思想：选择排序的思想非常直接，就是从所有序列中先找到最小（或最大）的，然后放到第一个位置。之后再看剩余元素中最小（或最大）的，放到第二个位置……以此类推，经过n-1趟选择排序得到有序结果（设n为元素个数，下同）。可以看到，选择排序是固定位置找元素。平均时间复杂度为O(n2)。9.2.2排序2、冒泡排序基本思想：它的思路是两两向后比较，重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序不符合排序要求就交换过来。走访数列一趟至少排定一个元素，重复进行直到没有再需要交换的，至多n-1趟。算法平均时间复杂度为：O(n2)。9.2.2排序3、插入排序

基本思想：插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n2)。9.2.2排序4、归并排序基本思想：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。归并过程：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。9.2.2排序5、快速排序基本思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。快速排序的时间复杂度：最理想O(nlogn)、最差O(n2)。9.2.2排序6、堆排序堆排序的思想：将一个无序序列调整为一个堆，就可以找出这个序列的最大值（或最小值），然后将找出的这个值交换到序列的最后一个，这样有序序列元素就增加一个，无序序列元素就减少一个，对新的无序序列重复这样的操作，就实现了排序。时间复杂