1、數(shù)據(jù)結(jié)構(gòu)與算法（Python）

數(shù)據(jù)結(jié)構(gòu)和算法是什么艾恼？答曰：兵法！

1.1算法的概念

算法是計(jì)算機(jī)處理信息的本質(zhì)，因?yàn)橛?jì)算機(jī)程序本質(zhì)上是一個(gè)算法來告訴計(jì)算機(jī)確切的步驟來執(zhí)行一個(gè)指定的任務(wù)蜡饵。一般地，當(dāng)算法在處理信息時(shí)胳施，會(huì)從輸入設(shè)備或數(shù)據(jù)的存儲(chǔ)地址讀取數(shù)據(jù)溯祸，把結(jié)果寫入輸出設(shè)備或某個(gè)存儲(chǔ)地址供以后再調(diào)用。

• ==算法是獨(dú)立存在的一種解決問題的方法和思想==。====

對于算法而言焦辅，實(shí)現(xiàn)的語言并不重要博杖，重要的是思想。

算法可以有不同的語言描述實(shí)現(xiàn)版本（如C描述筷登、C++描述剃根、Python描述等），我們現(xiàn)在是在用Python語言進(jìn)行描述實(shí)現(xiàn)前方。

算法的五大特性

1. 輸入: 算法具有0個(gè)或多個(gè)輸入
2. 輸出: 算法至少有1個(gè)或多個(gè)輸出
3. 有窮性: 算法在有限的步驟之后會(huì)自動(dòng)結(jié)束而不會(huì)無限循環(huán)狈醉，并且每一個(gè)步驟可以在可接受的時(shí)間內(nèi)完成
4. 確定性：算法中的每一步都有確定的含義，不會(huì)出現(xiàn)二義性
5. 可行性：算法的每一步都是可行的惠险，也就是說每一步都能夠執(zhí)行有限的次數(shù)完成

1.2第一次嘗試

需求：已知a+b+c=1000 a2+b2=c2 求a,b,c可能的值

import time

start_time = time.time()

# 注意是三重循環(huán)
for a in range(0, 1001):
    for b in range(0, 1001):
        for c in range(0, 1001):
            if a**2 + b**2 == c**2 and a+b+c == 1000:
                print("a, b, c: %d, %d, %d" % (a, b, c))

end_time = time.time()
print("elapsed: %f" % (end_time - start_time))
print("complete!")

運(yùn)行結(jié)果：
a, b, c: 0, 500, 500
a, b, c: 200, 375, 425
a, b, c: 375, 200, 425
a, b, c: 500, 0, 500
elapsed: 214.583347
complete!
注意運(yùn)行的時(shí)間: 160.913325秒
我的電腦運(yùn)行了大概26min苗傅。。班巩。

1.3第二次嘗試

import time

start_time = time.time()

# 注意是兩重循環(huán)
for a in range(0, 1001):
    for b in range(0, 1001-a):
        c = 1000 - a - b
        if a**2 + b**2 == c**2:
            print("a, b, c: %d, %d, %d" % (a, b, c))

end_time = time.time()
print("elapsed: %f" % (end_time - start_time))
print("complete!")

運(yùn)行結(jié)果：
a, b, c: 0, 500, 500
a, b, c: 200, 375, 425
a, b, c: 375, 200, 425
a, b, c: 500, 0, 500
elapsed: 0.182897
complete!
注意運(yùn)行的時(shí)間: 0.609427秒

1.4算法效率衡量

1.4.1執(zhí)行時(shí)間反應(yīng)算法效率

對于同一問題渣慕，我們給出了兩種解決算法，在兩種算法的實(shí)現(xiàn)中抱慌，我們對程序執(zhí)行的時(shí)間進(jìn)行了測算摇庙，發(fā)現(xiàn)兩段程序執(zhí)行的時(shí)間相差懸殊（160.913325秒相比于0.609427秒），由此我們可以得出結(jié)論：實(shí)現(xiàn)算法程序的執(zhí)行時(shí)間可以反應(yīng)出算法的效率遥缕，即算法的優(yōu)劣卫袒。

1.4.2單靠時(shí)間值絕對可信嗎？

假設(shè)我們將第二次嘗試的算法程序運(yùn)行在一臺配置古老性能低下的計(jì)算機(jī)中单匣，情況會(huì)如何夕凝？很可能運(yùn)行的時(shí)間并不會(huì)比在我們的電腦中運(yùn)行算法一的160.913325秒快多少。
==單純依靠運(yùn)行的時(shí)間來比較算法的優(yōu)劣并不一定是客觀準(zhǔn)確的户秤！==

程序的運(yùn)行離不開計(jì)算機(jī)環(huán)境（包括硬件和操作系統(tǒng)）码秉，這些客觀原因會(huì)影響程序運(yùn)行的速度并反應(yīng)在程序的執(zhí)行時(shí)間上。那么如何才能客觀的評判一個(gè)算法的優(yōu)劣呢鸡号？

1.4.3時(shí)間復(fù)雜度與“大O記法”

我們假定計(jì)算機(jī)執(zhí)行算法每一個(gè)基本操作的時(shí)間是固定的一個(gè)時(shí)間單位转砖，那么有多少個(gè)基本操作就代表會(huì)花費(fèi)多少時(shí)間單位。算然對于不同的機(jī)器環(huán)境而言鲸伴，確切的單位時(shí)間是不同的府蔗，但是對于算法進(jìn)行多少個(gè)基本操作（即花費(fèi)多少時(shí)間單位）在規(guī)模數(shù)量級上卻是相同的，由此可以忽略機(jī)器環(huán)境的影響而客觀的反應(yīng)算法的時(shí)間效率汞窗。

對于算法的時(shí)間效率姓赤，我們可以用“大O記法”來表示。

“大O記法”：對于單調(diào)的整數(shù)函數(shù)f仲吏，如果存在一個(gè)整數(shù)函數(shù)g和實(shí)常數(shù)c>0不铆，使得對于充分大的n總有f(n)<=c*g(n)蝌焚，就說函數(shù)g是f的一個(gè)漸近函數(shù)（忽略常數(shù)），記為f(n)=O(g(n))誓斥。也就是說只洒，在趨向無窮的極限意義下，函數(shù)f的增長速度受到函數(shù)g的約束劳坑，亦即函數(shù)f與函數(shù)g的特征相似毕谴。

時(shí)間復(fù)雜度：假設(shè)存在函數(shù)g，使得算法A處理規(guī)模為n的問題示例所用時(shí)間為T(n)=O(g(n))泡垃，則稱O(g(n))為算法A的漸近時(shí)間復(fù)雜度析珊，簡稱時(shí)間復(fù)雜度羡鸥，記為T(n)

1.4.4如何理解“大O記法”

對于算法進(jìn)行特別具體的細(xì)致分析雖然很好蔑穴，但在實(shí)踐中的實(shí)際價(jià)值有限。對于算法的時(shí)間性質(zhì)和空間性質(zhì)惧浴，最重要的是其數(shù)量級和趨勢存和，這些是分析算法效率的主要部分。而計(jì)量算法基本操作數(shù)量的規(guī)模函數(shù)中那些常量因子可以忽略不計(jì)衷旅。例如捐腿，可以認(rèn)為3n2和100n2屬于同一個(gè)量級，如果兩個(gè)算法處理同樣規(guī)模實(shí)例的代價(jià)分別為這兩個(gè)函數(shù)柿顶，就認(rèn)為它們的效率“差不多”茄袖，都為n2級。

1.4.5最壞時(shí)間復(fù)雜度

分析算法時(shí)嘁锯，存在幾種可能的考慮：

1. 算法完成工作最少需要多少基本操作宪祥，即最優(yōu)時(shí)間復(fù)雜度
2. 算法完成工作最多需要多少基本操作，即最壞時(shí)間復(fù)雜度
3. 算法完成工作平均需要多少基本操作家乘，即平均時(shí)間復(fù)雜度

對于最優(yōu)時(shí)間復(fù)雜度蝗羊，其價(jià)值不大，因?yàn)樗鼪]有提供什么有用信息仁锯，其反映的只是最樂觀最理想的情況耀找，沒有參考價(jià)值。
對于最壞時(shí)間復(fù)雜度业崖，提供了一種保證野芒，表明算法在此種程度的基本操作中一定能完成工作。
對于平均時(shí)間復(fù)雜度双炕，是對算法的一個(gè)全面評價(jià)复罐，因此它完整全面的反映了這個(gè)算法的性質(zhì)。但另一方面雄家，這種衡量并沒有保證效诅，不是每個(gè)計(jì)算都能在這個(gè)基本操作內(nèi)完成胀滚。而且，對于平均情況的計(jì)算乱投，也會(huì)因?yàn)閼?yīng)用算法的實(shí)例分布可能并不均勻而難以計(jì)算咽笼。

• ==因此，我們主要關(guān)注算法的最壞情況戚炫，亦即最壞時(shí)間復(fù)雜度剑刑。==

1.4.6時(shí)間復(fù)雜度的幾條基本計(jì)算規(guī)則

1. 基本操作，即只有常數(shù)項(xiàng)双肤，認(rèn)為其時(shí)間復(fù)雜度為O(1)
2. 順序結(jié)構(gòu)施掏，時(shí)間復(fù)雜度按加法進(jìn)行計(jì)算
3. 循環(huán)結(jié)構(gòu)，時(shí)間復(fù)雜度按乘法進(jìn)行計(jì)算
4. 分支結(jié)構(gòu)茅糜，時(shí)間復(fù)雜度取最大值
5. 判斷一個(gè)算法的效率時(shí)七芭，往往只需要關(guān)注操作數(shù)量的最高次項(xiàng)，其它次要項(xiàng)和常數(shù)項(xiàng)可以忽略
6. 在沒有特殊說明時(shí)蔑赘，我們所分析的算法的時(shí)間復(fù)雜度都是指最壞時(shí)間復(fù)雜度

1.4.7算法分析

1. 第一次嘗試的算法核心部分
   時(shí)間復(fù)雜度：
   T(n) = O(nnn) = O(n3)
2. 第二次嘗試的算法核心部分
   時(shí)間復(fù)雜度：
   T(n) = O(nn(1+1)) = O(n*n) = O(n2)

由此可見狸驳，我們嘗試的第二種算法要比第一種算法的時(shí)間復(fù)雜度好多的。

2缩赛、常見時(shí)間復(fù)雜度

所消耗的時(shí)間從小到大：

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

3耙箍、Python內(nèi)置類型性能分析——timeit模塊

timeit模塊可以用來測試一小段Python代碼的執(zhí)行速度。

timeit.Timer(stmt='pass', setup='pass', timer=<timer function>)

Timer是測量小段代碼執(zhí)行速度的類酥馍。
stmt參數(shù)是要測試的代碼語句（statment）辩昆；
setup參數(shù)是運(yùn)行代碼時(shí)需要的設(shè)置；
timer參數(shù)是一個(gè)定時(shí)器函數(shù)旨袒，與平臺有關(guān)汁针。

timeit.Timer.timeit(number=1000000)

Timer類中測試語句執(zhí)行速度的對象方法。
number參數(shù)是測試代碼時(shí)的測試次數(shù)峦失，默認(rèn)為1000000次扇丛。
方法返回執(zhí)行代碼的平均耗時(shí)，一個(gè)float類型的秒數(shù)尉辑。

list的操作測試

def test1():
    ls= []
    for i in range(1000):
        ls = ls + [i]

def test2():
    ls = []
    for i in range(1000):
        ls.append(i)

def test3():
    ls = []
    for i in range(1000):
        ls.insert(0,i)

def test4():
    ls = [i for i in range(1000)]

def test5():
   ls = list(range(1000))

from timeit import Timer
t1 = Timer(stmt='test1()',setup='from __main__ import test1')
print('concat',t1.timeit(number=10000),'second')

t2 = Timer(stmt='test2()',setup='from __main__ import test2')
print('append',t2.timeit(number=10000),'second')

t3 = Timer(stmt='test3()',setup='from __main__ import test3')
print('insert',t3.timeit(number=10000),'second')

t4 = Timer(stmt='test4()',setup='from __main__ import test4')
print('list gen',t4.timeit(number=10000),'second')

t5 = Timer(stmt='test5()',setup='from __main__ import test5')
print('list',t5.timeit(number=10000),'second')

運(yùn)行結(jié)果
concat 18.341660484899588 second
append 1.0099177848925684 second
insert 5.361922586350083 second
list gen 0.45405794180203074 second
list 0.18035762155434298 second

pop操作測試

from timeit import Timer
x1 = [x for x in range(2000000)]
t = Timer('x1.pop(0)','from __main__ import x1')
print('pop(0)',t.timeit(number=1000),'second')

x2 = [x for x in range(2000000)]
t = Timer('x2.pop()','from __main__ import x2')
print('pop()',t.timeit(number=1000),'second')

運(yùn)行結(jié)果
pop(0) 2.033923430381945 second
pop() 0.00011084076000633658 second

測試pop操作：從結(jié)果可以看出帆精，pop最后一個(gè)元素的效率遠(yuǎn)遠(yuǎn)高于pop第一個(gè)元素

4、數(shù)據(jù)結(jié)構(gòu)

4.1概念

數(shù)據(jù)是一個(gè)抽象的概念隧魄，將其進(jìn)行分類后得到程序設(shè)計(jì)語言中的基本類型卓练。如：int，float购啄，char等襟企。數(shù)據(jù)元素之間不是獨(dú)立的，存在特定的關(guān)系狮含，這些關(guān)系便是結(jié)構(gòu)顽悼。數(shù)據(jù)結(jié)構(gòu)指數(shù)據(jù)對象中數(shù)據(jù)元素之間的關(guān)系曼振。

Python給我們提供了很多現(xiàn)成的數(shù)據(jù)結(jié)構(gòu)類型，這些系統(tǒng)自己定義好的蔚龙，不需要我們自己去定義的數(shù)據(jù)結(jié)構(gòu)叫做Python的內(nèi)置數(shù)據(jù)結(jié)構(gòu)冰评，比如列表、元組木羹、字典甲雅。而有些數(shù)據(jù)組織方式，Python系統(tǒng)里面沒有直接定義坑填，需要我們自己去定義實(shí)現(xiàn)這些數(shù)據(jù)的組織方式抛人，這些數(shù)據(jù)組織方式稱之為Python的擴(kuò)展數(shù)據(jù)結(jié)構(gòu)，比如棧脐瑰，隊(duì)列等妖枚。

4.2算法與數(shù)據(jù)結(jié)構(gòu)的區(qū)別

• ==程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法==
• 總結(jié)：算法是為了解決實(shí)際問題而設(shè)計(jì)的，數(shù)據(jù)結(jié)構(gòu)是算法需要處理的問題載體

4.3抽象數(shù)據(jù)類型(Abstract Data Type)

抽象數(shù)據(jù)類型(ADT)的含義是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作蚪黑。即把數(shù)據(jù)類型和數(shù)據(jù)類型上的運(yùn)算捆在一起盅惜，進(jìn)行封裝中剩。

引入抽象數(shù)據(jù)類型的目的是把數(shù)據(jù)類型的表示和數(shù)據(jù)類型上運(yùn)算的實(shí)現(xiàn)與這些數(shù)據(jù)類型和運(yùn)算在程序中的引用隔開忌穿，使它們相互獨(dú)立。

最常用的數(shù)據(jù)運(yùn)算有五種：

1. 插入
2. 刪除
3. 修改
4. 查找
5. 排序

5结啼、順序表

在程序中掠剑，經(jīng)常需要將一組（通常是同為某個(gè)類型的）數(shù)據(jù)元素作為整體管理和使用，需要?jiǎng)?chuàng)建這種元素組郊愧，用變量記錄它們朴译，傳進(jìn)傳出函數(shù)等。一組數(shù)據(jù)中包含的元素個(gè)數(shù)可能發(fā)生變化（可以增加或刪除元素）属铁。

對于這種需求眠寿，最簡單的解決方案便是將這樣一組元素看成一個(gè)序列，用元素在序列里的位置和順序焦蘑，表示實(shí)際應(yīng)用中的某種有意義的信息盯拱，或者表示數(shù)據(jù)之間的某種關(guān)系。

這樣的一組序列元素的組織形式例嘱，我們可以將其抽象為線性表狡逢。一個(gè)線性表是某類元素的一個(gè)集合，還記錄著元素之間的一種順序關(guān)系拼卵。線性表是最基本的數(shù)據(jù)結(jié)構(gòu)之一奢浑，在實(shí)際程序中應(yīng)用非常廣泛，它還經(jīng)常被用作更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)基礎(chǔ)腋腮。

根據(jù)線性表的實(shí)際存儲(chǔ)方式雀彼，分為兩種實(shí)現(xiàn)模型：

1. 順序表壤蚜，將元素順序地存放在一塊連續(xù)的存儲(chǔ)區(qū)里，元素間的順序關(guān)系由它們的存儲(chǔ)順序自然表示徊哑。
2. 鏈表仍律，將元素存放在通過鏈接構(gòu)造起來的一系列存儲(chǔ)塊中。

5.1順序表的結(jié)構(gòu)與實(shí)現(xiàn)

一個(gè)順序表的完整信息包括兩部分实柠，一部分是表中的元素集合水泉，另一部分是為實(shí)現(xiàn)正確操作而需記錄的信息，即有關(guān)表的整體情況的信息窒盐，這部分信息主要包括元素存儲(chǔ)區(qū)的容量和當(dāng)前表中已有的元素個(gè)數(shù)兩項(xiàng)草则。

5.2順序表的兩種基本實(shí)現(xiàn)方式

1. 一體式結(jié)構(gòu)，存儲(chǔ)表信息的單元與元素存儲(chǔ)區(qū)以連續(xù)的方式安排在一塊存儲(chǔ)區(qū)里蟹漓，兩部分?jǐn)?shù)據(jù)的整體形成一個(gè)完整的順序表對象炕横。
   一體式結(jié)構(gòu)整體性強(qiáng)，易于管理葡粒。但是由于數(shù)據(jù)元素存儲(chǔ)區(qū)域是表對象的一部分份殿，順序表創(chuàng)建后，元素存儲(chǔ)區(qū)就固定了嗽交。
2. 為分離式結(jié)構(gòu)卿嘲，表對象里只保存與整個(gè)表有關(guān)的信息（即容量和元素個(gè)數(shù)），實(shí)際數(shù)據(jù)元素存放在另一個(gè)獨(dú)立的元素存儲(chǔ)區(qū)里夫壁，通過鏈接與基本表對象關(guān)聯(lián)拾枣。

元素存儲(chǔ)區(qū)替換：

1. 一體式結(jié)構(gòu)由于順序表信息區(qū)與數(shù)據(jù)區(qū)連續(xù)存儲(chǔ)在一起，所以若想更換數(shù)據(jù)區(qū)盒让，則只能整體搬遷梅肤，即整個(gè)順序表對象（指存儲(chǔ)順序表的結(jié)構(gòu)信息的區(qū)域）改變了。
2. 分離式結(jié)構(gòu)若想更換數(shù)據(jù)區(qū)邑茄，只需將表信息區(qū)中的數(shù)據(jù)區(qū)鏈接地址更新即可姨蝴，而該順序表對象不變。

元素存儲(chǔ)區(qū)擴(kuò)充
采用分離式結(jié)構(gòu)的順序表肺缕，若將數(shù)據(jù)區(qū)更換為存儲(chǔ)空間更大的區(qū)域左医，則可以在不改變表對象的前提下對其數(shù)據(jù)存儲(chǔ)區(qū)進(jìn)行了擴(kuò)充，所有使用這個(gè)表的地方都不必修改搓谆。只要程序的運(yùn)行環(huán)境（計(jì)算機(jī)系統(tǒng)）還有空閑存儲(chǔ)炒辉，這種表結(jié)構(gòu)就不會(huì)因?yàn)闈M了而導(dǎo)致操作無法進(jìn)行。人們把采用這種技術(shù)實(shí)現(xiàn)的順序表稱為動(dòng)態(tài)順序表泉手，因?yàn)槠淙萘靠梢栽谑褂弥袆?dòng)態(tài)變化黔寇。

擴(kuò)充的兩種策略
每次擴(kuò)充增加固定數(shù)目的存儲(chǔ)位置堕担，如每次擴(kuò)充增加10個(gè)元素位置略号，這種策略可稱為線性增長许师。

特點(diǎn)：節(jié)省空間铜靶，但是擴(kuò)充操作頻繁，操作次數(shù)多憋飞。

每次擴(kuò)充容量加倍霎苗，如每次擴(kuò)充增加一倍存儲(chǔ)空間。

特點(diǎn)：減少了擴(kuò)充操作的執(zhí)行次數(shù)榛做，但可能會(huì)浪費(fèi)空間資源唁盏。以空間換時(shí)間，推薦的方式检眯。

5.3順序表的操作

增加元素厘擂，刪除元素

5.4Python中的順序表

Python中的list和tuple兩種類型采用了順序表的實(shí)現(xiàn)技術(shù)，具有前面討論的順序表的所有性質(zhì)锰瘸。
tuple是不可變類型刽严，即不變的順序表，因此不支持改變其內(nèi)部狀態(tài)的任何操作避凝，而其他方面舞萄，則與list的性質(zhì)類似。

6管削、鏈表

6.1為什么需要鏈表

• 鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間倒脓，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。

6.2鏈表的定義

鏈表（Linked list）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)佩谣，是一種線性表把还，但是不像順序表一樣連續(xù)存儲(chǔ)數(shù)據(jù)实蓬，而是在每一個(gè)節(jié)點(diǎn)（數(shù)據(jù)存儲(chǔ)單元）里存放下一個(gè)節(jié)點(diǎn)的位置信息（即地址）茸俭。

6.3單向鏈表

單向鏈表也叫單鏈表，是鏈表中最簡單的一種形式安皱，它的每個(gè)節(jié)點(diǎn)包含兩個(gè)域调鬓，一個(gè)信息域（元素域）和一個(gè)鏈接域。這個(gè)鏈接指向鏈表中的下一個(gè)節(jié)點(diǎn)酌伊，而最后一個(gè)節(jié)點(diǎn)的鏈接域則指向一個(gè)空值腾窝。

image

• 表元素域elem用來存放具體的數(shù)據(jù)。
• 鏈接域next用來存放下一個(gè)節(jié)點(diǎn)的位置（python中的標(biāo)識）
• 變量p指向鏈表的頭節(jié)點(diǎn)（首節(jié)點(diǎn)）的位置居砖，從p出發(fā)能找到表中的任意節(jié)點(diǎn)虹脯。

單鏈表的實(shí)現(xiàn)

#定義節(jié)點(diǎn)類
class SingleNode(object):
    def __init__(self,item):
        #信息域：存儲(chǔ)節(jié)點(diǎn)數(shù)據(jù)的
        self.item = item
        #鏈接域：鏈接下一個(gè)節(jié)點(diǎn)的
        self.next = None


#定義單向鏈表
class SingleLinkList(object):
    def __init__(self):
        #head:頭節(jié)點(diǎn)的引用
        self._head = None

    def is_empty(self):
        #鏈表是否為空
        return self._head == None

    def length(self):
        #鏈表長度
        count = 0
        #cur指向鏈表的首節(jié)點(diǎn)
        cur = self._head
        #判斷cur是否為None
        while cur != None:
            #cur不等于None，就表示一個(gè)節(jié)點(diǎn)存在
            #給計(jì)數(shù)器加1
            count += 1
            #cur指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
            cur = cur.next
        return count

    def travel(self):
        # 遍歷整個(gè)鏈表
        # cur指向鏈表的首節(jié)點(diǎn)
        cur = self._head
        # 判斷cur是否為None
        while cur != None:
            #打印當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)
            print(cur.item)
            #cur指向下一個(gè)節(jié)點(diǎn)
            cur = cur.next

    def add(self,item):
        #鏈表頭部添加元素
        #生成新的節(jié)點(diǎn)對象
        node = SingleNode(item)
        #設(shè)置node節(jié)點(diǎn)的next指向原來的頭節(jié)點(diǎn)
        node.next = self._head
        #把node節(jié)點(diǎn)設(shè)置成了新的頭節(jié)點(diǎn)
        self._head = node

    def append(self,item):
        #鏈表尾部添加元素
        #定義新的節(jié)點(diǎn)
        node = SingleNode(item)
        if self.is_empty():
            self._head = node
        else:
            #cur指向鏈表的開頭
            cur = self._head
            while cur.next != None:
                cur = cur.next
            #cur是鏈表的最后一個(gè)節(jié)點(diǎn)
            cur.next = node

    def insert(self,pos, item):
        #指定位置添加元素
        if pos<=0:
            #在鏈表的頭部添加節(jié)點(diǎn)
            self.add(item)
        elif pos>=self.length():
            #在鏈表的尾部添加節(jié)點(diǎn)
            self.append(item)
        else:
            node = SingleNode(item)
            #計(jì)數(shù)器奏候，用來確定插入位置
            count = 0
            cur = self._head
            while count < pos - 1:
                count+=1
                cur = cur.next;
            node.next = cur.next
            cur.next = node

    def remove(self,item):
        #刪除節(jié)點(diǎn)
        cur = self._head
        #pre:保存cur的上一個(gè)節(jié)點(diǎn)
        pre = None
        while cur != None:
            if cur.item == item:
                #確定要?jiǎng)h除的節(jié)點(diǎn)
                if not pre:
                    #刪除的是第一個(gè)節(jié)點(diǎn)
                    #把當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)當(dāng)作首節(jié)點(diǎn)
                    self._head = cur.next
                else:
                    # 刪除的不是第一個(gè)節(jié)點(diǎn)
                    pre.next = cur.next
                break
            else:
                #不相等循集，不是要?jiǎng)h除的節(jié)點(diǎn)
                #遍歷下一個(gè)節(jié)點(diǎn)
                pre = cur
                cur = cur.next

    def search(self,item):
        #查找節(jié)點(diǎn)是否存在
        cur = self._head
        while cur != None:
            #判定是不是要查找的節(jié)點(diǎn)
            if cur.item == item:
                return True
            else:
                cur = cur.next
        return False

if __name__ == '__main__':
    sl = SingleLinkList()
    sl.add(1)
    sl.add(2)
    sl.append(3)
    sl.insert(2,6)
    print('length:',sl.length())
    sl.travel()
    print(sl.search(2))
    sl.remove(2)
    print('length:', sl.length())

鏈表與順序表的對比

鏈表失去了順序表隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域蔗草，空間開銷比較大咒彤，但對存儲(chǔ)空間的使用要相對靈活疆柔。

6.4單向循環(huán)鏈表

單鏈表的一個(gè)變形是單向循環(huán)鏈表，鏈表中最后一個(gè)節(jié)點(diǎn)的next域不再為None镶柱，而是指向鏈表的頭節(jié)點(diǎn)旷档。

單向循環(huán)列表的實(shí)現(xiàn)

class Node(object):
    """節(jié)點(diǎn)"""
    def __init__(self, item):
        self.item = item
        self.next = None


class SinCycLinkedlist(object):
    """單向循環(huán)鏈表"""
    def __init__(self):
        self._head = None

    def is_empty(self):
        """判斷鏈表是否為空"""
        return self._head == None

    def length(self):
        """返回鏈表的長度"""
        # 如果鏈表為空，返回長度0
        if self.is_empty():
            return 0
        count = 1
        cur = self._head
        while cur.next != self._head:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """遍歷鏈表"""
        if self.is_empty():
            return
        cur = self._head
        print(cur.item)
        while cur.next != self._head:
            cur = cur.next
            print(cur.item)


    def add(self, item):
        """頭部添加節(jié)點(diǎn)"""
        node = Node(item)
        if self.is_empty():
            self._head = node
            node.next = self._head
        else:
            #添加的節(jié)點(diǎn)指向_head
            node.next = self._head
            # 移到鏈表尾部歇拆，將尾部節(jié)點(diǎn)的next指向node
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            cur.next = node
            #_head指向添加node的
            self._head = node

    def append(self, item):
        """尾部添加節(jié)點(diǎn)"""
        node = Node(item)
        if self.is_empty():
            self._head = node
            node.next = self._head
        else:
            # 移到鏈表尾部
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            # 將尾節(jié)點(diǎn)指向node
            cur.next = node
            # 將node指向頭節(jié)點(diǎn)_head
            node.next = self._head

    def insert(self, pos, item):
        """在指定位置添加節(jié)點(diǎn)"""
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            node = Node(item)
            cur = self._head
            count = 0
            # 移動(dòng)到指定位置的前一個(gè)位置
            while count < (pos-1):
                count += 1
                cur = cur.next
            node.next = cur.next
            cur.next = node

    def remove(self, item):
        """刪除一個(gè)節(jié)點(diǎn)"""
        # 若鏈表為空鞋屈，則直接返回
        if self.is_empty():
            return
        # 將cur指向頭節(jié)點(diǎn)
        cur = self._head
        pre = None
        # 若頭節(jié)點(diǎn)的元素就是要查找的元素item
        if cur.item == item:
            # 如果鏈表不止一個(gè)節(jié)點(diǎn)
            if cur.next != self._head:
                # 先找到尾節(jié)點(diǎn)，將尾節(jié)點(diǎn)的next指向第二個(gè)節(jié)點(diǎn)
                while cur.next != self._head:
                    cur = cur.next
                # cur指向了尾節(jié)點(diǎn)
                cur.next = self._head.next
                self._head = self._head.next
            else:
                # 鏈表只有一個(gè)節(jié)點(diǎn)
                self._head = None
        else:
            pre = self._head
            # 第一個(gè)節(jié)點(diǎn)不是要?jiǎng)h除的
            while cur.next != self._head:
                # 找到了要?jiǎng)h除的元素
                if cur.item == item:
                    # 刪除
                    pre.next = cur.next
                    return
                else:
                    pre = cur
                    cur = cur.next
            # cur 指向尾節(jié)點(diǎn)
            if cur.item == item:
                # 尾部刪除
                pre.next = cur.next

    def search(self, item):
        """查找節(jié)點(diǎn)是否存在"""
        if self.is_empty():
            return False
        cur = self._head
        if cur.item == item:
            return True
        while cur.next != self._head:
            cur = cur.next
            if cur.item == item:
                return True
        return False

if __name__ == "__main__":
    ll = SinCycLinkedlist()
    ll.add(1)
    ll.add(2)
    ll.append(3)
    ll.insert(2, 4)
    ll.insert(4, 5)
    ll.insert(0, 6)
    print("length:",ll.length())
    ll.travel()
    print(ll.search(3))
    print(ll.search(7))
    ll.remove(1)
    print("length:",ll.length())
    ll.travel()

6.5雙向鏈表

一種更復(fù)雜的鏈表是“雙向鏈表”或“雙面鏈表”故觅。每個(gè)節(jié)點(diǎn)有兩個(gè)鏈接：一個(gè)指向前一個(gè)節(jié)點(diǎn)谐区，當(dāng)此節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)時(shí)，指向空值逻卖；而另一個(gè)指向下一個(gè)節(jié)點(diǎn)宋列，當(dāng)此節(jié)點(diǎn)為最后一個(gè)節(jié)點(diǎn)時(shí)，指向空值评也。

class Node(object):
    #節(jié)點(diǎn)的類
    def __init__(self,item):
        self.item = item
        self.prev = None
        self.next = None

class DLinkList(object):
    #雙向鏈表的類
    def __init__(self):
        #指向鏈表的頭節(jié)點(diǎn)
        self._head = None

    def is_empty(self):
        #鏈表是否為空
        return self._head == None


    def length(self):
        #鏈表長度
        cur = self._head
        #計(jì)數(shù)器
        count = 0
        while cur != None:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        #遍歷鏈表
        cur = self._head
        while cur != None:
            print(cur.item)
            cur = cur.next

    def add(self,item):
        #鏈表頭部添加
        node = Node(item)
        if self.is_empty():
            #如果是空鏈表炼杖，將_head指向node
            #給鏈表添加第一個(gè)元素
            self._head = node
        else:
            #如果鏈表不為空，在新的節(jié)點(diǎn)和原來的首節(jié)點(diǎn)之間建立雙向鏈接
            node.next = self._head
            self._head.prev = node
            #讓_head指向鏈表的新的首節(jié)點(diǎn)
            self._head = node


    def append(self,item):
        #鏈表尾部添加
        #創(chuàng)建新的節(jié)點(diǎn)
        node = Node(item)
        if self.is_empty():
            #空鏈表盗迟，
            self._head = node
        else:
            #鏈表不為空
            cur = self._head
            while cur.next != None:
                cur = cur.next
            #cur的下一個(gè)節(jié)點(diǎn)是node
            cur.next = node
            #node的上一個(gè)節(jié)點(diǎn)是
            node.prev = cur

    def insert(self,pos,item):
        #指定位置添加
        if pos <=0:
            self.add(item)
        elif pos > self.length()-1:
            self.append()
        else:
            node = Node(item)
            cur = self._head
            count = 0
            #把cur移動(dòng)到指定位置的前一個(gè)位置
            while count < (pos - 1):
                count+=1
                cur = cur.next
            #node的prev指向cur
            node.prev = cur
            #node的next指向cur的next
            node.next = cur.next
            cur.next.prev = node
            cur.next = node

    def remove(self,item):
        #刪除節(jié)點(diǎn)
        if self.is_empty():
            return
        else:
            cur = self._head
            if cur.item == item:
                #首節(jié)點(diǎn)是要?jiǎng)h除的節(jié)點(diǎn)
                if cur.next == None:
                    #說明鏈表中只有一個(gè)節(jié)點(diǎn)
                    self._head = None
                else:
                    #鏈表多于一個(gè)節(jié)點(diǎn)的情況
                    cur.next.prev = None
                    self._head = cur.next
            else:
                # 首節(jié)點(diǎn)不是要?jiǎng)h除的節(jié)點(diǎn)
                while cur != None:
                    if cur.item == item:
                        cur.prev.next = cur.next
                        cur.next.prev = cur.prev
                        break
                    cur = cur.next

    def search(self,item):
        #查找節(jié)點(diǎn)是否存在
        cur = self._head
        while cur != None:
            if cur.item == item:
                return True
            cur = cur.next
        return False


if __name__ == '__main__':
    dls = DLinkList()
    dls.add(10)
    dls.add(12)
    dls.append(15)
    dls.append(16)
    dls.insert(2,32)
    dls.insert(3,36)
    print('dls lenght:',dls.length())
    dls.travel()
    print(dls.search(15))
    dls.remove(32)
    print('dls length:',dls.length())
    dls.travel()

7坤邪、棧

棧（stack），有些地方稱為堆棧罚缕，是一種容器艇纺，可存入數(shù)據(jù)元素、訪問元素邮弹、刪除元素黔衡，它的特點(diǎn)在于只能允許在容器的一端（稱為棧頂端指標(biāo)，英語：top）進(jìn)行加入數(shù)據(jù)（英語：push）和輸出數(shù)據(jù)（英語：pop）的運(yùn)算腌乡。沒有了位置概念盟劫，保證任何時(shí)候可以訪問、刪除的元素都是此前最后存入的那個(gè)元素与纽，確定了一種默認(rèn)的訪問順序侣签。
由于棧數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出（LIFO, Last In First Out）的原理運(yùn)作急迂。

7.1棧結(jié)構(gòu)實(shí)現(xiàn)

椨八可以用順序表實(shí)現(xiàn)，也可以用鏈表實(shí)現(xiàn)僚碎。

7.2棧的操作

class Stack(object):
    #棧的實(shí)現(xiàn)
    def __init__(self):
        self.items = []

    def is_empty(self):
        #判斷棧是否為空
        return self.items == []

    def push(self,item):
        #壓棧：在棧中加入數(shù)據(jù)元素
        self.items.append(item)

    def pop(self):
        #彈棧操作：從棧中彈出元素
        return self.items.pop()

    def peek(self):
        #返回棧頂?shù)臄?shù)據(jù)元素
        return self.items[len(self.items)-1]

    def size(self):
        #返回棧的尺寸
        return len(self.items)

if __name__ == '__main__':
    stack = Stack()
    print(stack.is_empty())
    stack.push('hello')
    stack.push('python')
    stack.push('qiku')
    stack.push('zhengzhou')
    print(stack.is_empty())
    print(stack.size())
    print(stack.peek())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())
    print(stack.pop())

8猴娩、隊(duì)列

隊(duì)列（queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。

隊(duì)列是一種先進(jìn)先出的（First In First Out）的線性表胀溺，簡稱FIFO裂七。

允許插入的一端為隊(duì)尾，允許刪除的一端為隊(duì)頭仓坞。隊(duì)列不允許在中間部位進(jìn)行操作背零！假設(shè)隊(duì)列是q=（a1，a2无埃，……徙瓶，an），那么a1就是隊(duì)頭元素嫉称，而an是隊(duì)尾元素侦镇。這樣我們就可以刪除時(shí)，總是從a1開始织阅，而插入時(shí)壳繁，總是在隊(duì)列最后。這也比較符合我們通常生活中的習(xí)慣荔棉，排在第一個(gè)的優(yōu)先出列闹炉，最后來的當(dāng)然排在隊(duì)伍最后。

8.1隊(duì)列的實(shí)現(xiàn)

同棧一樣润樱，隊(duì)列也可以用順序表或者鏈表實(shí)現(xiàn)渣触。

8.2操作

class Queue(object):
    #隊(duì)列的實(shí)現(xiàn)
    def __init__(self):
        self.items = []

    def is_empty(self):
        #判斷隊(duì)列是否為空
        return self.items == []

    def enqueue(self,item):
        #插入到隊(duì)列的頭部
        self.items.insert(0,item)

    def dequeue(self):
        #刪除數(shù)據(jù)
        return self.items.pop()

    def size(self):
        #返回隊(duì)列的大小
        return len(self.items)


if __name__ == '__main__':
    q = Queue()
    q.enqueue("hello")
    q.enqueue("sssss")
    q.enqueue("aaaaa")
    print(q.size())
    print(q.is_empty())
    print(q.dequeue())
    print(q.size())
    print(q.dequeue())
    print(q.size())

9、雙端隊(duì)列

雙端隊(duì)列（deque壹若，全名double-ended queue）嗅钻，是一種具有隊(duì)列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。
雙端隊(duì)列中的元素可以從兩端彈出店展，其限定插入和刪除操作在表的兩端進(jìn)行养篓。雙端隊(duì)列可以在隊(duì)列任意一端入隊(duì)和出隊(duì)。

#雙端列表的定義
class Deque(object):
    def __init__(self):
        self.items = []

    def add_front(self,item):
        #從隊(duì)頭加入一個(gè)item元素
        self.items.insert(0,item)

    def add_rear(self,item):
        #從隊(duì)尾加入一個(gè)item元素
        self.items.append(item)

    def remove_front(self):
        #從隊(duì)頭刪除一個(gè)item元素
        return self.items.pop(0)

    def remove_rear(self):
        #從隊(duì)尾刪除一個(gè)item元素
        return self.items.pop()

    def is_empty(self):
        #判斷雙端隊(duì)列是否為空
        return self.items == []

    def size(self):
        # 返回隊(duì)列的大小
        return len(self.items)


if __name__ == '__main__':
    deqeue = Deque()
    print(deqeue.is_empty())
    deqeue.add_front(22)
    deqeue.add_front(33)
    deqeue.add_rear(44)
    deqeue.add_rear(55)
    print(deqeue.is_empty())
    print(deqeue.size())
    print(deqeue.remove_front())
    print('size:',deqeue.size())
    print(deqeue.remove_rear())
    print('size:',deqeue.size())

10壁查、排序算法

排序算法（英語：Sorting algorithm）是一種能將一串?dāng)?shù)據(jù)依照特定順序進(jìn)行排列的一種算法觉至。

10.1排序算法的穩(wěn)定性

穩(wěn)定性：穩(wěn)定排序算法會(huì)讓原本有相等鍵值的紀(jì)錄維持相對次序。也就是如果一個(gè)排序算法是穩(wěn)定的睡腿，當(dāng)有兩個(gè)相等鍵值的紀(jì)錄R和S，且在原本的列表中R出現(xiàn)在S之前峻贮，在排序過的列表中R也將會(huì)是在S之前席怪。

當(dāng)相等的元素是無法分辨的，比如像是整數(shù)纤控，穩(wěn)定性并不是一個(gè)問題挂捻。然而，假設(shè)以下的數(shù)對將要以他們的第一個(gè)數(shù)字來排序船万。

(4, 1) (3, 1) (3, 7)（5, 6）

在這個(gè)狀況下刻撒，有可能產(chǎn)生兩種不同的結(jié)果骨田，一個(gè)是讓相等鍵值的紀(jì)錄維持相對的次序，而另外一個(gè)則沒有：

(3, 1) (3, 7) (4, 1) (5, 6) （維持次序）

(3, 7) (3, 1) (4, 1) (5, 6) （次序被改變）

不穩(wěn)定排序算法可能會(huì)在相等的鍵值中改變紀(jì)錄的相對次序声怔，但是穩(wěn)定排序算法從來不會(huì)如此态贤。不穩(wěn)定排序算法可以被特別地實(shí)現(xiàn)為穩(wěn)定。作這件事情的一個(gè)方式是人工擴(kuò)充鍵值的比較醋火，如此在其他方面相同鍵值的兩個(gè)對象間之比較悠汽，（比如上面的比較中加入第二個(gè)標(biāo)準(zhǔn)：第二個(gè)鍵值的大小）就會(huì)被決定使用在原先數(shù)據(jù)次序中的條目芥驳，當(dāng)作一個(gè)同分決賽柿冲。然而，要記住這種次序通常牽涉到額外的空間負(fù)擔(dān)兆旬。

10.2冒泡排序

冒泡排序（英語：Bubble Sort）是一種簡單的排序算法假抄。它重復(fù)地遍歷要排序的數(shù)列，一次比較兩個(gè)元素丽猬，如果他們的順序錯(cuò)誤就把他們交換過來慨亲。遍歷數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成宝鼓。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端刑棵。

冒泡排序算法的運(yùn)作如下：

1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大（升序）愚铡，就交換他們兩個(gè)蛉签。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對沥寥。這步做完后碍舍，最后的元素會(huì)是最大的數(shù)。
3. 針對所有的元素重復(fù)以上的步驟邑雅，除了最后一個(gè)片橡。
4. 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較淮野。

def bubble_sort(alist):
    for j in range(len(alist)-1,0,-1):
        # j表示每次遍歷需要比較的次數(shù)捧书，是逐漸減小的
        for i in range(j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]

li = [54,26,93,17,77,31,44,55,20]
bubble_sort(li)
print(li)

時(shí)間復(fù)雜度

• 最優(yōu)時(shí)間復(fù)雜度：O(n) （表示遍歷一次發(fā)現(xiàn)沒有任何可以交換的元素，排序結(jié)束骤星。）
• 最壞時(shí)間復(fù)雜度：O(n2)
• 穩(wěn)定性：穩(wěn)定

10.2選擇排序

選擇排序（Selection sort）是一種簡單直觀的排序算法经瓷。

它的工作原理如下：

1. 在未排序序列中找到最小（大）元素洞难，存放到排序序列的起始位置舆吮，
2. 再從剩余未排序元素中繼續(xù)尋找最小（大）元素
3. 放到已排序序列的末尾。
4. 以此類推色冀，直到所有元素均排序完畢潭袱。

選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上锋恬，則它不會(huì)被移動(dòng)屯换。選擇排序每次交換一對元素，它們當(dāng)中至少有一個(gè)將被移到其最終位置上伶氢，因此對n個(gè)元素的表進(jìn)行排序總共進(jìn)行至多n-1次交換趟径。在所有的完全依靠交換去移動(dòng)元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N癣防。

def selection_sort(alist):
    n = len(alist)
    # 需要進(jìn)行n-1次選擇操作
    for i in range(n-1):
        # 記錄最小位置
        min_index = i
        # 從i+1位置到末尾選擇出最小數(shù)據(jù)
        for j in range(i+1, n):
            if alist[j] < alist[min_index]:
                min_index = j
        # 如果選擇出的數(shù)據(jù)不在正確位置蜗巧，進(jìn)行交換
        if min_index != i:
            alist[i], alist[min_index] = alist[min_index], alist[i]

alist = [54,226,93,17,77,31,44,55,20]
selection_sort(alist)
print(alist)

時(shí)間復(fù)雜度

• 最優(yōu)時(shí)間復(fù)雜度：O(n2)
• 最壞時(shí)間復(fù)雜度：O(n2)
• 穩(wěn)定性：不穩(wěn)定（考慮升序每次選擇最大的情況）

10.3插入排序

插入排序（英語：Insertion Sort）是一種簡單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列蕾盯，對于未排序數(shù)據(jù)幕屹，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入级遭。插入排序在實(shí)現(xiàn)上望拖，在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位挫鸽，為最新元素提供插入空間说敏。

def insert_sort(alist):
    # 從第二個(gè)位置，即下標(biāo)為1的元素開始向前插入
    for i in range(1, len(alist)):
        # 從第i個(gè)元素開始向前比較丢郊，如果小于前一個(gè)元素盔沫，交換位置
        for j in range(i, 0, -1):
            if alist[j] < alist[j-1]:
                alist[j], alist[j-1] = alist[j-1], alist[j]

alist = [54,26,93,17,77,31,44,55,20]
insert_sort(alist)
print(alist)

時(shí)間復(fù)雜度

• 最優(yōu)時(shí)間復(fù)雜度：O(n) （升序排列，序列已經(jīng)處于升序狀態(tài)）
• 最壞時(shí)間復(fù)雜度：O(n2)
• 穩(wěn)定性：穩(wěn)定