python structure_GitHub - CYZYZG/Data_Structure_with_Python: 这是我在学习《基于Python的数据结构》的时候的笔记与代码...
Data_Structure_with_Python
這是我在學習《基于Python的數據結構》的時候的筆記與代碼
主要參考：數據結構與算法(Python)
對于算法的時間效率，我們可以用“大O記法”來表示。
“大O記法”：對于單調的整數函數f，如果存在一個整數函數g和實常數c>0，使得對于充分大的n總有f(n)<=c*g(n)，就說函數g是f的一個漸近函數(忽略常數)，記為f(n)=O(g(n))。也就是說，在趨向無窮的極限意義下，函數f的增長速度受到函數g的約束，亦即函數f與函數g的特征相似。
時間復雜度：假設存在函數g，使得算法A處理規(guī)模為n的問題示例所用時間為T(n)=O(g(n))，則稱O(g(n))為算法A的漸近時間復雜度，簡稱時間復雜度，記為T(n)
最壞時間復雜度
算法完成工作最多需要多少基本操作，即最壞時間復雜度
時間復雜度的幾條基本計算規(guī)則
基本操作，即只有常數項，認為其時間復雜度為O(1)
順序結構，時間復雜度按加法進行計算
循環(huán)結構，時間復雜度按乘法進行計算
分支結構，時間復雜度取最大值
判斷一個算法的效率時，往往只需要關注操作數量的最高次項，其它次要項和常數項可以忽略
在沒有特殊說明時，我們所分析的算法的時間復雜度都是指最壞時間復雜度
常見時間復雜度
常見時間復雜度之間的關系
timeit模塊
timeit模塊可以用來測試一小段Python代碼的執(zhí)行速度。
class timeit.Timer(stmt='pass', setup='pass', timer=)
Timer是測量小段代碼執(zhí)行速度的類。
stmt參數是要測試的代碼語句(statment)；
setup參數是運行代碼時需要的設置；
timer參數是一個定時器函數，與平臺有關。
timeit.Timer.timeit(number=1000000)
Timer類中測試語句執(zhí)行速度的對象方法。number參數是測試代碼時的測試次數，默認為1000000次。方法返回執(zhí)行代碼的平均耗時，一個float類型的秒數。
list內置操作的時間復雜度
dict內置操作的時間復雜度
Python的內置數據結構
Python給我們提供了很多現(xiàn)成的數據結構類型，這些系統(tǒng)自己定義好的，不需要我們自己去定義的數據結構叫做Python的內置數據結構，比如列表、元組、字典。
Python的擴展數據結構
而有些數據組織方式，Python系統(tǒng)里面沒有直接定義，需要我們自己去定義實現(xiàn)這些數據的組織方式，這些數據組織方式稱之為Python的擴展數據結構，比如棧，隊列等。
算法與數據結構的區(qū)別
數據結構只是靜態(tài)的描述了數據元素之間的關系。
高效的程序需要在數據結構的基礎上設計和選擇算法。
程序 = 數據結構 + 算法
總結：算法是為了解決實際問題而設計的，數據結構是算法需要處理的問題載體
抽象數據類型(Abstract Data Type)
抽象數據類型(ADT)的含義是指一個數學模型以及定義在此數學模型上的一組操作。即把數據類型和數據類型上的運算捆在一起，進行封裝。引入抽象數據類型的目的是把數據類型的表示和數據類型上運算的實現(xiàn)與這些數據類型和運算在程序中的引用隔開，使它們相互獨立。
最常用的數據運算有五種：
插入
刪除
修改
查找
排序
線性表
一個線性表是某類元素的一個集合，還記錄著元素之間的一種順序關系。
根據線性表的實際存儲方式，分為兩種實現(xiàn)模型：
順序表，將元素順序地存放在一塊連續(xù)的存儲區(qū)里，元素間的順序關系由它們的存儲順序自然表示。
鏈表，將元素存放在通過鏈接構造起來的一系列存儲塊中。
順序表的兩種存儲方式：
元素內置(一體式結構)：表里存儲的元素大小固定
元素外置(分離式結構)：表里只存儲鏈接
表中存儲的兩個信息
1.表中的元素集合
2.信息主要包括元素存儲區(qū)的容量和當前表中已有的元素個數兩項
增加元素
a. 尾端加入元素，時間復雜度為O(1)
b. 中間插入，時間復雜度為O(n)
刪除元素
a. 刪除表尾元素，時間復雜度為O(1)
b. 中間元素刪除，時間復雜度為O(n)
Python中的順序表
list和tuple
tuple是不可變類型，即不變的順序表，因此不支持改變其內部狀態(tài)的任何操作，而其他方面，則與list的性質類似。
list就是一種采用分離式技術實現(xiàn)的動態(tài)順序表。
鏈表與順序表的對比
鏈表失去了順序表隨機讀取的優(yōu)點，同時鏈表由于增加了結點的指針域，空間開銷比較大，但對存儲空間的使用要相對靈活。
鏈表與順序表的各種操作復雜度如下所示：
鏈表的主要耗時操作是遍歷查找
順序表查找很快，主要耗時的操作是拷貝覆蓋
3.棧
4.隊列
代碼：
排序算法(Sorting Algorithm)：是一種能將一串數據按照特定順序進行排列的一種算法。
穩(wěn)定性
穩(wěn)定性：穩(wěn)定排序算法會讓原本有相等鍵值的紀錄維持相對次序。也就是如果一個排序算法是穩(wěn)定的，當有兩個相等鍵值的紀錄R和S，且在原本的列表中R出現(xiàn)在S之前，在排序過的列表中R也將會是在S之前。
當相等的元素是無法分辨的，比如像是整數，穩(wěn)定性并不是一個問題。然而，假設以下的數對將要以他們的第一個數字來排序。
(4, 1) (3, 1) (3, 7)(5, 6)
在這個狀況下，有可能產生兩種不同的結果，一個是讓相等鍵值的紀錄維持相對的次序，而另外一個則沒有：
(3, 1) (3, 7) (4, 1) (5, 6) (維持次序)
(3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)
不穩(wěn)定排序算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩(wěn)定排序算法從來不會如此。不穩(wěn)定排序算法可以被特別地實現(xiàn)為穩(wěn)定。作這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個對象間之比較，(比如上面的比較中加入第二個標準：第二個鍵值的大小)就會被決定使用在原先數據次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。
常見排序算法效率比較
代碼：
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩(wěn)定排序算法。
希爾排序過程
希爾排序的基本思想是：將數組列在一個表中并對列分別進行插入排序，重復這過程，不過每次用更長的列(步長更長了，列數更少了)來進行。最后整個表就只有一列了。將數組轉換至表是為了更好地理解這算法，算法本身還是使用數組進行排序。
例如，假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應該看起來是這樣(豎著的元素是步長組成)：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我們對每列進行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
將上述四行數字，依序接在一起時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。這時10已經移至正確位置了，然后再以3為步長進行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后變?yōu)?#xff1a;
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步長進行排序(此時就是簡單的插入排序了)
6.二分查找
樹(英語：tree)是一種抽象數據類型(ADT)
樹的術語
節(jié)點的度：一個節(jié)點含有的子樹的個數稱為該節(jié)點的度；
樹的度：一顆樹中，最大的節(jié)點的度稱為樹的度；
葉節(jié)點或終端節(jié)點：度為零的節(jié)點；
父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點；
子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點；
兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互相稱為兄弟節(jié)點；
節(jié)點的層次：從根節(jié)點開始定義起，根為第一層，根的子節(jié)點為第二層，以此類推；
樹的高度或深度：樹中節(jié)點的最大層次；
堂兄弟節(jié)點：父節(jié)點在同一層次的節(jié)點互為堂兄弟；
節(jié)點的祖先：從根節(jié)點到該節(jié)點所經分支上的所有節(jié)點；
子孫：以某一節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫；
森林：由m(m >= 0)顆互不相交的樹的集合稱為森林；
樹的種類
無序樹：樹中任意節(jié)點的子節(jié)點之間沒有順序關系
有序樹：樹中任意節(jié)點的子節(jié)點之間有順序關系
二叉樹：每個節(jié)點最多含有兩個子樹
完全二叉樹：除最底層最后一個外其他必須有子樹
滿二叉樹：所有葉節(jié)點都在最底層的完全二叉樹
平衡二叉樹：當且僅當任何節(jié)點的兩顆子樹的高度差不大于1的二叉樹
排序二叉樹：二叉搜索樹
霍夫曼樹(用于信息編碼)：帶權路徑最短的二叉樹
B樹：一種對讀寫操作進行優(yōu)化的自平衡的二叉查找樹，能夠保持數據有序，擁有杜宇兩個子樹
常見的一些樹的應用場景
1.xml，html等，那么編寫這些東西的解析器的時候，不可避免用到樹
2.路由協(xié)議就是使用了樹的算法
3.mysql數據庫索引
4.文件系統(tǒng)的目錄結構
5.所以很多經典的AI算法其實都是樹搜索，此外機器學習中的decision tree也是樹結構
二叉樹的遍歷
深度優(yōu)先遍歷和廣度優(yōu)先遍歷
深度優(yōu)先一般用遞歸，廣度優(yōu)先一般用隊列。一般情況下能用遞歸實現(xiàn)的算法大部分也能用堆棧來實現(xiàn)。
深度優(yōu)先遍歷
先序遍歷 在先序遍歷中，我們先訪問根節(jié)點，然后遞歸使用先序遍歷訪問左子樹，再遞歸使用先序遍歷訪問右子樹
根節(jié)點->左子樹->右子樹
def preorder(self, root):
"""遞歸實現(xiàn)先序遍歷"""
if root == None:
return
print root.elem
self.preorder(root.lchild)
self.preorder(root.rchild)
中序遍歷 在中序遍歷中，我們遞歸使用中序遍歷訪問左子樹，然后訪問根節(jié)點，最后再遞歸使用中序遍歷訪問右子樹
左子樹->根節(jié)點->右子樹
def inorder(self, root):
"""遞歸實現(xiàn)中序遍歷"""
if root == None:
return
self.inorder(root.lchild)
print root.elem
self.inorder(root.rchild)
后序遍歷 在后序遍歷中，我們先遞歸使用后序遍歷訪問左子樹和右子樹，最后訪問根節(jié)點
左子樹->右子樹->根節(jié)點
def postorder(self, root):
"""遞歸實現(xiàn)后續(xù)遍歷"""
if root == None:
return
self.postorder(root.lchild)
self.postorder(root.rchild)
print root.elem
前序和后序在本質上都是將父節(jié)點與子結點進行分離，但并沒有指明左子樹和右子樹的能力，因此得到這兩個序列只能明確父子關系，而不能確定一個二叉樹。
由二叉樹的中序和前序遍歷序列可以唯一確定一棵二叉樹 ，由前序和后序遍歷則不能唯一確定一棵二叉樹
由二叉樹的中序和后序遍歷序列可以唯一確定一棵二叉樹，由前序和后序遍歷則不能唯一確定一棵二叉樹
總結
以上是生活随笔為你收集整理的python structure_GitHub - CYZYZG/Data_Structure_with_Python: 这是我在学习《基于Python的数据结构》的时候的笔记与代码...的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python的装饰器迭代器与生成器_py
- 下一篇： java ltpa_LTPA Cooki