數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)課件章節(jié)9

第9章Python數(shù)據(jù)結(jié)構(gòu)Python語言中有四種內(nèi)置的數(shù)據(jù)結(jié)構(gòu)，分別為列表（list）、元組（tuple）、字典（dict）和集合（set）。同時(shí)Python里還有標(biāo)準(zhǔn)庫和內(nèi)置函數(shù)來實(shí)現(xiàn)一些復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。9.1列表（list）列表是最常用的Python數(shù)據(jù)類型，它可以作為一個(gè)方括號(hào)內(nèi)的逗號(hào)分隔值出現(xiàn)。列表的數(shù)據(jù)項(xiàng)不需要具有相同的類型。創(chuàng)建一個(gè)列表，只要把逗號(hào)分隔的不同的數(shù)據(jù)項(xiàng)使用方括號(hào)括起來即可。如下所示：

list1=['dog','cat',2020,2021] list2=[1,2,3,4,5] list3=["a","b","c","d"]1．訪問列表中的值列表索引從0開始，第二個(gè)索引是1，依此類推；索引也可以從尾部開始，最后一個(gè)元素的索引為-1，往前一位為-2，以此類推?！据敵觥?23452．更新和刪除列表元素在列表中，可以使用append()方法來添加列表項(xiàng)；可以使用del語句可以從一個(gè)列表中依索引而不是值來刪除一個(gè)元素；可以使用remove()移除列表中某個(gè)值的第一個(gè)匹配項(xiàng)?！据敵觥縖1,2,3,4,5,6][1,2,4,5,6][2,4,5,6]3．將列表當(dāng)做堆棧使用列表方法使得列表可以很方便的作為一個(gè)堆棧來使用，堆棧作為特定的數(shù)據(jù)結(jié)構(gòu)，最先進(jìn)入的元素最后一個(gè)被釋放（后進(jìn)先出）。用append()方法可以把一個(gè)元素添加到堆棧頂。用pop()方法可以把一個(gè)元素從堆棧頂釋放出來。【輸出】[1,2,3,4,5][1,2,3,4]5．利用列表來排序

使用列表的內(nèi)置函數(shù)sort()可輕松地實(shí)現(xiàn)對(duì)列表進(jìn)行排序。sort()函數(shù)用于對(duì)原列表進(jìn)行排序，如果指定參數(shù)，則使用比較函數(shù)指定的比較函數(shù)。sort()函數(shù)一共有三個(gè)參數(shù)：list.sort(cmp=None,key=None,reverse=False)

其中cmp為可選參數(shù),如果指定了該參數(shù)會(huì)使用該參數(shù)的方法進(jìn)行排序；key主要是用來進(jìn)行比較的元素，只有一個(gè)參數(shù)，具體的函數(shù)的參數(shù)就是取自于可迭代對(duì)象中，指定可迭代對(duì)象中的一個(gè)元素來進(jìn)行排序；reverse是排序規(guī)則，reverse=True降序，reverse=False升序（默認(rèn)）。需要注意的是，該方法沒有返回值。例如：【輸出】[2,3,4,6,7,8][8,7,6,4,3,2][[3,1],[1,2],[8,3],[5,4]]列表包含的函數(shù)如表所示。列表包含的方法如表所示。9.2元組（tuple）Python的元組與列表類似，不同之處在于元組的元素不能修改。元組使用小括號(hào)()，列表使用方括號(hào)[]。元組創(chuàng)建很簡(jiǎn)單，只需要在括號(hào)中添加元素，并使用逗號(hào)隔開即可。由于元組的元素不能修改，所以不能刪除元組中的元素，只能刪除整個(gè)元組。在元組里訪問元素的操作與列表的類似。

Python元組包含的函數(shù)如表所示。9.3字典（dict）

字典的每個(gè)鍵值key=>value對(duì)用冒號(hào)分割，每個(gè)鍵值對(duì)之間用逗號(hào)分割，整個(gè)字典包括在花括號(hào){}中，格式如下所示：dic={key1:value1,key2:value2}

在字典中，鍵一般是唯一的，如果重復(fù)最后的一個(gè)鍵值對(duì)會(huì)替換前面的，值不需要唯一。值可以取任何數(shù)據(jù)類型，但鍵必須是不可變的，如字符串，數(shù)字或元組，如果是列表，則不能作為鍵。在Python中，字典與散列表類似。在字典里訪問值、修改字典、刪除字典元素的操作與列表的類似。字典包含的函數(shù)如表所示。字典包含的方法分別如表所示。9.4集合（set）

集合（set）是一個(gè)無序的不重復(fù)元素序列。可以使用大括號(hào){}或者set()函數(shù)創(chuàng)建集合，值得注意的是：創(chuàng)建一個(gè)空集合必須用set()而不是{}，因?yàn)閧}是用來創(chuàng)建一個(gè)空字典。集合的創(chuàng)建格式如下：parame={value01,value02,...}或set(value)1．添加元素s.add(x)將元素x添加到集合s中，如果元素已存在，則不進(jìn)行任何操作。s.update(x)也可以添加元素，而且參數(shù)可以是列表、元組、字典等。2．移除元素s.remove(x)將元素x從集合s中移除，如果元素不存在，則會(huì)發(fā)生錯(cuò)誤。s.discard(x)也能移除集合中的元素，且如果元素不存在，不會(huì)發(fā)生錯(cuò)誤。s.pop()會(huì)隨機(jī)刪除集合中的一個(gè)元素。3．判斷元素是否在集合中存在xins是判斷元素x是否在集合s中，存在返回True，不存在返回False。集合包含的方法如表所示。9.5collection.deque

在Python中通常用collection庫中的deque對(duì)象來實(shí)現(xiàn)隊(duì)列。該類聲明為：classcollections.deque([iterable[,maxlen]])

該對(duì)象返回一個(gè)新的雙向隊(duì)列對(duì)象，從左到右初始化（用append()方法），從iterable（迭代對(duì)象)數(shù)據(jù)創(chuàng)建。如果iterable沒有指定，新隊(duì)列為空。Deque隊(duì)列是由棧或者queue隊(duì)列生成的（發(fā)音是“deck”，”double-endedqueue”的簡(jiǎn)稱）。Deque支持線程安全，內(nèi)存高效添加和彈出，從兩端都可以，兩個(gè)方向的操作的時(shí)間復(fù)雜度都是O(1)。

雖然list對(duì)象也支持類似操作，不過這里優(yōu)化了定長(zhǎng)操作和pop(0)和insert(0,v)的開銷。它們引起O(n)內(nèi)存移動(dòng)的操作，改變底層數(shù)