数据结构与算法基础课件章节9.pptx

《数据结构与算法基础课件章节9.pptx》由会员分享，可在线阅读，更多相关《数据结构与算法基础课件章节9.pptx（16页珍藏版）》请在汇文网上搜索。

1、第9章Python数据结构 Python语言中有四种内置的数据结构，分别为列表（list）、元组（tuple）、字典（dict）和集合（set）。同时Python里还有标准库和内置函数来实现一些复杂的数据结构。9.1 列表（列表（list）列表是最常用的Python数据类型，它可以作为一个方括号内的逗号分隔值出现。列表的数据项不需要具有相同的类型。创建一个列表，只要把逗号分隔的不同的数据项使用方括号括起来即可。如下所示：list1=dog,cat,2020,2021list2=1,2,3,4,5list3=a,b,c,d1访问列表中的列表中的值 列表索引从0开始，第二个索引是1，依此类推；索引

2、也可以从尾部开始，最后一个元素的索引为-1，往前一位为-2，以此类推。【输出】【输出】123452更新和更新和删除列表元素除列表元素 在列表中，可以使用append()方法来添加列表项；可以使用del语句可以从一个列表中依索引而不是值来删除一个元素；可以使用remove()移除列表中某个值的第一个匹配项。【输出】【输出】1,2,3,4,5,61,2,4,5,62,4,5,63将列表当做堆将列表当做堆栈使用使用 列表方法使得列表可以很方便的作为一个堆栈来使用，堆栈作为特定的数据结构，最先进入的元素最后一个被释放（后进先出）。用 append()方法可以把一个元素添加到堆栈顶。用pop()方法可以

3、把一个元素从堆栈顶释放出来。【输出】【输出】1,2,3,4,51,2,3,45利用列表来排序利用列表来排序 使用列表的内置函数sort()可轻松地实现对列表进行排序。sort()函数用于对原列表进行排序，如果指定参数，则使用比较函数指定的比较函数。sort()函数一共有三个参数：list.sort(cmp=None,key=None,reverse=False)其中cmp为可选参数,如果指定了该参数会使用该参数的方法进行排序；key主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序；reverse是排序规则，reverse=Tr

4、ue降序，reverse=False升序（默认）。需要注意的是，该方法没有返回值。例如：例如：【输出】【输出】2,3,4,6,7,88,7,6,4,3,23,1,1,2,8,3,5,4列表包含的函数如表所示。列表包含的方法如表所示。9.2 元组（tuple）Python的元组与列表类似，不同之处在于元组的元素不能修改。元组使用小括号()，列表使用方括号。元组创建很简单，只需要在括号中添加元素，并使用逗号隔开即可。由于元组的元素不能修改，所以不能删除元组中的元素，只能删除整个元组。在元组里访问元素的操作与列表的类似。Python元组包含的函数如表所示。9.3 字典（dict）字典的每个键值key

5、=value对用冒号分割，每个键值对之间用逗号分割，整个字典包括在花括号中，格式如下所示：dic=key1:value1,key2:value2 在字典中，键一般是唯一的，如果重复最后的一个键值对会替换前面的，值不需要唯一。值可以取任何数据类型，但键必须是不可变的，如字符串，数字或元组，如果是列表，则不能作为键。在Python中，字典与散列表类似。在字典里访问值、修改字典、删除字典元素的操作与列表的类似。字典包含的函数如表所示。字典包含的方法分别如表所示。9.4 集合（set）集合（set）是一个无序的不重复元素序列。可以使用大括号 或者set()函数创建集合，值得注意的是：创建一个空集合必须

6、用set()而不是，因为 是用来创建一个空字典。集合的创建格式如下：parame=value01,value02,.或set(value)1添加元素添加元素 s.add(x)将元素 x 添加到集合 s 中，如果元素已存在，则不进行任何操作。s.update(x)也可以添加元素，而且参数可以是列表、元组、字典等。2移除元素移除元素 s.remove(x)将元素x从集合s中移除，如果元素不存在，则会发生错误。s.discard(x)也能移除集合中的元素，且如果元素不存在，不会发生错误。s.pop()会随机删除集合中的一个元素。3判断元素是否在集合中存在判断元素是否在集合中存在 x in s是判断元

7、素 x 是否在集合 s 中，存在返回 True，不存在返回 False。集合包含的方法如表所示。9.5 collection.deque 在Python中通常用collection库中的deque对象来实现队列。该类声明为：class collections.deque(iterable,maxlen)该对象返回一个新的双向队列对象，从左到右初始化（用append()方法），从 iterable（迭代对象)数据创建。如果 iterable 没有指定，新队列为空。Deque队列是由栈或者queue队列生成的（发音是“deck”，”double-ended queue”的简称）。Deque支持线程安全，内存高效添加和弹出，从两端都可以，两个方向的操作的时间复杂度都是O(1)。虽然list对象也支持类似操作，不过这里优化了定长操作和pop(0)和insert(0,v)的开销。它们引起O(n)内存移动的操作，改变底层数据表达的大小和位置。如果maxlen没有指定或者是None，deques可以增长到任意长度。否则，deque就限定到指定最大长度。一旦限定长度的deque满了，当新项加入时，同样数量的项就从另一端弹出。deque类型包含的方法如表所示。