都說 程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法 育谬，最開始不太懂?dāng)?shù)據(jù)結(jié)構(gòu)，而且覺得算法更是不靠譜帮哈，數(shù)學(xué)太爛膛檀，后來懵懵懂懂的明白了數(shù)據(jù)結(jié)構(gòu)，為了實(shí)現(xiàn)某些功能但汞，也寫過一些算法宿刮。

不過就目前的經(jīng)驗(yàn)而言，個(gè)人覺得算法還是要根據(jù)數(shù)據(jù)結(jié)構(gòu)來寫的私蕾。

最近有一個(gè)算法要實(shí)現(xiàn)僵缺，算法攻城獅只會(huì)寫C++，我是寫java的踩叭，而且java和C除了用動(dòng)態(tài)(靜態(tài))鏈接庫之外磕潮，沒法混編翠胰，這種情況下，只需要了解一下他的算法原理自脯，然后給根據(jù)自己的數(shù)據(jù)結(jié)構(gòu)去寫就行了之景，畢竟，他也不了解我的數(shù)據(jù)結(jié)構(gòu)膏潮。

一個(gè)關(guān)于 數(shù)據(jù)結(jié)構(gòu)和算法 的牛逼網(wǎng)站
https://visualgo.net

這里還是主要說一下Python的數(shù)據(jù)結(jié)構(gòu)

列表

list的常用方法

• append(x)
  • 在列表的末尾添加一個(gè)項(xiàng)
  • 等價(jià)于a[len(a):] = [x]
• extend(iterable)
  • 遍歷iterable中所有項(xiàng)來擴(kuò)展列表
  • a[len(a):] = iterable
• insert(i, x)
  • 在指定位置插入一個(gè)值
  • i=位置锻狗，x=值
• remove(x)
  • 從列表中刪除第一項(xiàng)x值
  • 如果沒有值，返回一個(gè)錯(cuò)誤焕参。
• pop([i])
  • 刪除列表中指定位置的值轻纪，并返回它
  • 如果沒有指定，則刪除最后一項(xiàng)并返回
  • 方括號代表可選參數(shù)
• clear()
  • 清空所有項(xiàng)
  • del a[:]
• index(x[, start[, end]])
  • 在第一個(gè)值為x的列表中返回從零開始的索引
  • 如果沒有這樣的項(xiàng)叠纷，就會(huì)產(chǎn)生一個(gè)ValueError
  • 返回的索引是相對于完整序列開始計(jì)算的刻帚，不是開始參數(shù)。
• count(x)
  • x的個(gè)數(shù)
• sort(key=None, reverse=False)
  • 排序
  • 這是個(gè)多參數(shù)方法
  • 詳見 https://docs.python.org/3/library/functions.html#sorted
• reverse()
  • 反轉(zhuǎn)
  • 返回一個(gè)反轉(zhuǎn)后的list
• copy()
  • 復(fù)制
  • a[:]

Python的設(shè)計(jì)

• 像insert, remove,sort之類的方法涩嚣，都不輸出返回值崇众，默認(rèn)為None。
• Python中所有 可變數(shù)據(jù)結(jié)構(gòu) 的設(shè)計(jì)原則都是這樣的

>>> nums = ["one","two","three","one","five","one"]
>>> nums.count("one")
3
>>> nums.count("fix")
0
>>> nums.index("one")
0
>>> nums.index("five")
4
# 從位置4開始的one
>>> nums.index("one",4)
5
>>> nums.reverse()
>>> nums
['one', 'five', 'one', 'three', 'two', 'one']
>>> nums.append("six")
>>> nums
['one', 'five', 'one', 'three', 'two', 'one', 'six']
# 默認(rèn)排序
>>> nums.sort()
>>> nums
['five', 'one', 'one', 'one', 'six', 'three', 'two']
>>> nums.pop()
'two'

堆棧中使用list

• 用append()可以添加到棧頂
• 用pop()可以從棧頂開始檢索
• 后進(jìn)先出

>>> stack = [3,4,5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]

>>> stack.pop()
7
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]

隊(duì)列中使用list

• 添加的第一個(gè)元素也是被檢索的第一個(gè)元素(低效航厚，先進(jìn)先出)
• 雖然追加到末尾速度最快顷歌，但是添加刪除會(huì)很慢(需要逐漸位移)
• collections.deque可以解決這個(gè)問題，可以從兩端快速添加或者刪除

>>> from collections import deque
>>> queue = deque(["one","two","three"])
>>> queue.append("four")
>>> queue.append("five")
>>> queue
deque(['one', 'two', 'three', 'four', 'five'])
>>> queue.popleft()
'one'
>>> queue
deque(['two', 'three', 'four', 'five'])

List Comprehensions

List Comprehensions為創(chuàng)建列表提供了一種簡潔的方式阶淘。

通常生成一個(gè)列表是直接new一個(gè)新列表衙吩，其中每個(gè)item是另一個(gè)集合或迭代器的結(jié)果，或者他們的的子集溪窒。

# 一個(gè)平方列表
>>> squares = []
>>> for x in range(10):
    squares.append(x**2)

    
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
# 創(chuàng)建(或覆蓋)一個(gè)名為x的變量坤塞，該變量在循環(huán)完成后仍然存在。
>>> x
9

# 還有一種方式可以計(jì)算出沒有任何副作用的平方列表
>>> squares = list(map(lambda x: x**2,range(10)))
>>> squares
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

# 相當(dāng)于這樣
squares = [x**2 for x in range(10)]

# 相信你已經(jīng)看出來為什么了澈蚌，限定了它的范圍
# 而且可讀性更強(qiáng)摹芙，接下來用這種方式玩一個(gè)蛋疼的循環(huán)

>>> ballachefor = [(x,y) for x in [1,2,3] for y in [3,1,4] if x != y]
>>> ballachefor
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

# 等價(jià)于這樣，很容易懂宛瞄，因?yàn)樗鼈兊捻樞蚴窍嗤?>>> for x in [1,2,3]:
    for y in [3,1,4]:
        if x != y:
            dantengfor.append((x,y))

            
>>> dantengfor
[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

List Comprehension括號內(nèi)包含表達(dá)式的括號浮禾，然后是for子句，然后是0或if子句份汗。結(jié)果是一個(gè)new list盈电，該列表來自于對該表達(dá)式上下文中的表達(dá)式進(jìn)行評估，以及是否遵循它的子句杯活。

如果它是一個(gè)元祖匆帚，則必須用()，就像上面的例子一樣

代碼呀旁钧，還是要多練

>>> vec = [-4,-2,0,2,4]

>>> [x*2 for x in vec]
[-8, -4, 0, 4, 8]

>>> [x for x in vec if x>= 0]
[0, 2, 4]

>>> [abs(x) for x in vec]
[4, 2, 0, 2, 4]

>>> freshnums = ["one","two","three"]
>>> [weapon.strip() for weapon in freshnums]
['one', 'two', 'three']

>>> [(x,x**2) for x in range(6)]
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25)]

嵌套列表

>>> matrix = [[1,2,3],[4,5,6],[7,8,9]]
>>> [[row[i] for row in matrix] for i in range(3)]
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]

# 等價(jià)于

>>> convert = []
>>> for i in range(3):
    convert2 = []
    for row in matrix:
        convert2.append(row[i])
    convert.append(convert2)

    
>>> convert
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]

# 對于這些內(nèi)置函數(shù)復(fù)雜流語句可以用zip()函數(shù)

>>> list(zip(*matrix))
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]

刪除語句

#The del statement
del_stmt ::=  "del" target_list

• del方法可以從列表中根據(jù)索引刪除一個(gè)項(xiàng)吸重，而不是它的價(jià)值互拾。這不同于pop()方法返回一個(gè)值。del語句也可以從列表中移除片或清除整個(gè)列表
• 刪除是遞歸地定義賦值定義的方式非常相似
• 刪除一個(gè)目標(biāo)表的遞歸刪除每個(gè)目標(biāo),從左到右嚎幸。
• 刪除一個(gè)名稱刪除綁定的名稱從本地或全局命名空間,取決于這個(gè)名字出現(xiàn)在全局聲明相同的代碼塊颜矿。
• 如果名字是釋放狀態(tài),會(huì)拋出NameError異常。

>>> a = [-3,-2,-1,0,1,2,3,301]

>>> del a[0]
>>> a
[-2, -1, 0, 1, 2, 3, 301]

>>> del a[-1]
>>> a
[-2, -1, 0, 1, 2, 3]

>>> del a[:]
>>> a
[]

# 刪除整個(gè)變量
>>> del a
>>> a
Traceback (most recent call last):
  File "<pyshell#50>", line 1, in <module>
    a
NameError: name 'a' is not defined

元組和序列

列表和字符串有很多共同屬性嫉晶。他們是序列數(shù)據(jù)類型的兩個(gè)例子骑疆。Python是不斷發(fā)展的，正如之前一直用的2车遂，到3不兼容之前的版本了...

它添加了新的標(biāo)準(zhǔn)序列數(shù)據(jù)類型:tuple封断。

元組看起來和list有點(diǎn)像，但還是不一樣的舶担，比如，可以不帶括號彬呻，不可變衣陶，而且是通過索引找對象，list通過循環(huán)就可以

# 元組
>>> t = 123,321,"hello"
>>> t[2]
'hello'
>>> t
(123, 321, 'hello')

# 嵌套元組
>>> u = t,(1,2,3)
>>> u
((123, 321, 'hello'), (1, 2, 3))

# 元組和字符串一樣闸氮，是不可變的
>>> t[0] = 123
Traceback (most recent call last):
  File "<pyshell#66>", line 1, in <module>
    t[0] = 123
TypeError: 'tuple' object does not support item assignment

# 但是可以包含可變對象剪况，如list
>>> v = ([1,2,3],[3,2,1])
>>> v
([1, 2, 3], [3, 2, 1])


# 創(chuàng)建一個(gè)空元組
>>> empty = ()
>>> empty
()

# 不帶逗號就是字符串
>>> one = "hello"
>>> one
'hello'

# 帶逗號就是元組
>>> one = "hello",
>>> one
('hello',)

# 元組的拆包
>>> x,y,z = t
>>> t
(123, 321, 'hello')
>>> x
123
>>> y
321
>>> z
'hello'

Sets

• sets也是python的數(shù)據(jù)類型之一
• set是一個(gè)無序集合（沒有重復(fù)元素）
• 基本用于item測試和消除重復(fù)元素
• set對象也支持?jǐn)?shù)學(xué)運(yùn)算(唯一性，交集,差異和對稱差分)
• 花括號或者set()函數(shù)都可以用來創(chuàng)建sets
• 創(chuàng)建一個(gè)空set蒲跨，必須用set(),不能用{},花括號是用來創(chuàng)建一個(gè)空字典的
• list包含的译断，set都包含

# 去重
>>> nums = {"one","two","one","three","four","five","six","five"}
>>> nums
{'four', 'five', 'two', 'six', 'one', 'three'}

# item 測試
>>> "one" in nums
True
>>> "seven" in nums
False

# set 操作
>>> a = set("aabbccdd")
>>> b = set("aaccee")

# 拆分a
>>> a
{'a', 'b', 'c', 'd'}

# 差異(a有，b沒有)
>>> a-b
{'b', 'd'}

# 合并
>>> a | b
{'e', 'a', 'b', 'c', 'd'}

# 交集
>>> a & b
{'a', 'c'}

# a,b各自獨(dú)有的合集
>>> a ^ b
{'e', 'b', 'd'}

# list包含的或悲，set都包含
>>> a = {x for x in "aabbccddee" if x not in "abc"}
>>> a
{'e', 'd'}

字典dictionary

dict,字典在其他語言中叫“關(guān)聯(lián)存儲”或“關(guān)聯(lián)數(shù)組”孙咪，和序列不同的是，序列是range范圍巡语，字典是index索引翎蹈，可以是任何不可變類型。

• 數(shù)字和字符串可以一直是鍵
• 只包含字符串男公、數(shù)字荤堪、或元組的元組也可以是鍵
• 如果一個(gè)tuple直接或間接包含任何可變對象,則不能作為一個(gè)關(guān)鍵。
• 不能用list作為key
• 最好是把dict看作一組無序的鍵值對,在一個(gè)字典是唯一的枢赔。
• 用一對{}可以創(chuàng)建一個(gè)空字典澄阳。
• 向字典添加鍵值對，要用“踏拜，”分隔

字典的主要操作是多個(gè)key一個(gè)value和根據(jù)key取value碎赢。也可以用del刪除一個(gè)鍵值對。如果你正在用的key已經(jīng)被使用了执隧，那么與舊值關(guān)聯(lián)的key會(huì)被遺棄揩抡。
在字典中使用多個(gè)key户侥，將返回一個(gè)無序列表，如果要排序,就用sorted(d.keys())峦嗤。

>>> tel  = {"zhangsan":133,"lisi":134,"wangwu":135}
>>> tel["zhaoliu"] = 136
>>> tel
{'zhangsan': 133, 'lisi': 134, 'wangwu': 135, 'zhaoliu': 136}
>>> tel
{'zhangsan': 133, 'lisi': 134, 'wangwu': 135, 'zhaoliu': 136}
>>> tel["zhangsan"]
133
>>> tel["zhang"]
Traceback (most recent call last):
  File "<pyshell#24>", line 1, in <module>
    tel["zhang"]
KeyError: 'zhang'
>>> del tel["zhaoliu"]
>>> tel
{'zhangsan': 133, 'lisi': 134, 'wangwu': 135}
>>> list(tel.keys())
['zhangsan', 'lisi', 'wangwu']
>>> sorted(tel.keys())
['lisi', 'wangwu', 'zhangsan']
>>> "zhangsan" in tel
True
>>> "zhaoliu" in tel
False

dirt()構(gòu)造函數(shù)直接通過鍵值對構(gòu)建字典:

>>> dict([("zhangsan",133),("lisi",134),("wangwu",135)])
{'zhangsan': 133, 'lisi': 134, 'wangwu': 135}

另外蕊唐，dict comprehensions可以從任意鍵值對表達(dá)式中創(chuàng)建字典

>>> {x: x**2 for x in (2,4,6)}
{2: 4, 4: 16, 6: 36}

當(dāng)key是字符串時(shí)，更容易使用關(guān)鍵字參數(shù)指定鍵值對:

>>> dict(zhangsan=133,lisi=134,wangwu=135)
{'zhangsan': 133, 'lisi': 134, 'wangwu': 135}