1.什么是數(shù)據(jù)結(jié)構(gòu)？
數(shù)據(jù)結(jié)構(gòu)就是計算機存儲、組織數(shù)據(jù)的方式。
2.常見的數(shù)據(jù)結(jié)構(gòu)
1.數(shù)組
2.棧
3.隊列
4.鏈表
5.樹
6.堆
7.哈希表
8.圖
2.1 數(shù)組
數(shù)組是可以在內(nèi)存中連續(xù)存儲多個元素的結(jié)構(gòu)，數(shù)組的元素通過數(shù)組下標(biāo)進行訪問，下標(biāo)從0開始。
優(yōu)點：
讀取快，因為讀取數(shù)據(jù)用的索引，只要知道索引就可以取出數(shù)據(jù)? ? ? ? ??
? 缺點：
1. 大小固定后就無法擴容了
2.數(shù)組中只能存儲一種類型的數(shù)據(jù)
3. 插入，刪除慢，因為存儲數(shù)據(jù)的內(nèi)存是連續(xù)的，要插入或刪除就要變更整個數(shù)組中的數(shù)據(jù)位置
2.2 棧
棧是一種特殊的線性表，僅能在棧頂操作，棧底不允許操作。特點：先進后出。
數(shù)組和鏈表都可以組成棧，棧常用于實現(xiàn)遞歸功能。
2.3 隊列
隊列是一種先進先出的數(shù)據(jù)結(jié)構(gòu)，像一根管子，兩頭都是開放的，棧的一頭是封閉的
2.4 鏈表
鏈表是動態(tài)的分配存儲空間，是非連續(xù)，非順序的存儲結(jié)構(gòu)，鏈表在存儲數(shù)據(jù)的內(nèi)存中有兩塊區(qū)域，一塊用來存儲數(shù)據(jù)，一塊用來記錄下一個數(shù)據(jù)保存的位置（指向下一個數(shù)據(jù)的指針），根據(jù)指針的指向，鏈表能形成不同的結(jié)構(gòu)，如單鏈表，雙向鏈表，循環(huán)鏈表等。元素的邏輯順序是通過鏈表的指針地址實現(xiàn)的。鏈表將一些碎片空間利用起來了。
優(yōu)點：
不需要初始化容量，可以任意加減元素
添加，刪除快，因為只需要更改前后兩個元素的指針地址即可。
缺點：
查詢慢，因為查找元素需要遍歷鏈表來查詢，適用于數(shù)據(jù)量小，增減操作頻繁的場景。
2.5 樹
樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個有限節(jié)點組成一個具有層次關(guān)系的集合。把它叫做 “樹” 是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：
每個節(jié)點有零個或多個子節(jié)點；
沒有父節(jié)點的節(jié)點稱為根節(jié)點；
每一個非根節(jié)點有且只有一個父節(jié)點；
除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹；
2.5.1 二叉樹
二叉樹是樹的特殊一種，具有如下特點：
1、每個結(jié)點最多有兩顆子樹，結(jié)點的度最大為2。?
2、左子樹和右子樹是有順序的，次序不能顛倒。?
3、即使某結(jié)點只有一個子樹，也要區(qū)分左右子樹。
二叉樹是一種比較這種的方案，它添加，刪除元素都很快，查找也有優(yōu)化方法，所以有二叉樹既有鏈表和數(shù)組的好處。在處理大批量的動態(tài)數(shù)據(jù)方面很有用。
樹的概念：
根：樹的頂端節(jié)點
葉子：沒有子樹的節(jié)點（度為0的節(jié)點）叫葉子，也就是終端節(jié)點。
度: 節(jié)點所擁有的子樹的個數(shù)成為度
邊：一個節(jié)點和另一個節(jié)點之間的連接叫做邊
層次：樹的層次從根節(jié)點開始；根為第0層，根的子樹為第1層，以此類推。
節(jié)點的高度：該節(jié)點與某個葉子之間存在的最長路經(jīng)上的邊的個數(shù)
節(jié)點的深度：樹的根節(jié)點到該節(jié)點的邊數(shù)。
樹的高度：根節(jié)點的高度
樹的深度：樹中節(jié)點的最大層次
完美二叉樹：所有父節(jié)點都有2個子樹
完全二叉樹：從根節(jié)點到倒數(shù)第二層都滿足完美二叉樹，最后一層的可以不完全填充，其葉子節(jié)點都靠左對齊。
完滿二叉樹：所有分葉子節(jié)點的度都是2（只要有孩子，就必須兩個）
二叉查找樹
（1）二叉查找樹性質(zhì)
<1> 若左子樹不為空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值。
<2> 若右子樹不為空，則右子樹上所有節(jié)點的值均大于或等于它的根節(jié)點的值。
<3> 左右子樹也分別為二叉排序樹
<4> 沒有鍵值相等的節(jié)點
<5> 二叉樹的高度決定了查找效率
（2）二叉查找樹的插入過程
step1：若當(dāng)前的二叉查找樹為空，則插入的元素為根節(jié)點。
step2：若插入的元素值小于根節(jié)點值，則將元素插入到左子樹中。
step3：若插入的元素大于等于根節(jié)點的值，則將元素插入到右子樹中。
（3）二叉查找樹的刪除過程
s1：p為葉子節(jié)點，直接刪除該節(jié)點，再修改其父節(jié)點的指針（注意分根節(jié)點和不是根節(jié)點）
s2：p為單支節(jié)點（只有左子樹或右子樹），讓p的子樹與p的父節(jié)點相連，刪除p即可。
s3：p的左子樹和右子樹均不為空，找到p的后繼y（y為節(jié)點，不是葉子），因為y一定沒有左子樹，所以可以刪除y，連接y的父節(jié)點和右子樹，右子樹成為左子樹，并用y的值代替p的值?；蚍椒ǘ钦业絧的前驅(qū)x，x一定沒有右子樹。所以可以刪除x，并讓x的父節(jié)點成為y的左子樹的父節(jié)點。
2.5.2 紅黑樹
紅黑樹樹一種二叉查找樹，但在二叉查找樹的基礎(chǔ)上額外添加了一個顏色標(biāo)記，同時具有一定的規(guī)則，這些規(guī)則使樹保證了一種平衡，插入，刪除，查找的最壞時間復(fù)雜度為O，紅黑樹每個節(jié)點上都有存儲位表示節(jié)點的顏色，可以是紅或黑
紅黑樹特性：
1. 根節(jié)點是黑色的
2，每個節(jié)點或者是黑色或者是紅色
3. 如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的
4.每一個葉子節(jié)點是黑色的【是指為空（NILor NULL）的葉子節(jié)點】
5.
紅黑樹主要是用它來存儲有序的數(shù)據(jù)，它的時間復(fù)雜度是O(lgn)，效率非常之高。例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虛擬內(nèi)存的管理，都是通過紅黑樹去實現(xiàn)的。
紅黑樹的基本操作：
左旋：被旋轉(zhuǎn)的節(jié)點將變成一個左節(jié)點
右旋：被旋轉(zhuǎn)的節(jié)點將變成一個右節(jié)點
2.6 堆
堆就是用數(shù)組實現(xiàn)的完全二叉樹，所以它沒有使用父指針或子指針，堆根據(jù)“堆屬性”來排序，“堆屬性”決定了樹種節(jié)點的位置。
堆屬性
堆分為兩種：最大堆和最小堆，兩者的區(qū)別再與節(jié)點的排序方式。
最大堆：父節(jié)點的值比每一個子節(jié)點的值都要大，在最小堆中，父節(jié)點的值比每一個子節(jié)點的值都要小，這個屬性對堆中的每一個節(jié)點都成立。注意：堆中根節(jié)點存放的是最大或最小元素，但是其他節(jié)點的排序是未知的，最小的元素未必是最后一個元素，
3 .python的數(shù)據(jù)結(jié)構(gòu)
python的數(shù)據(jù)結(jié)構(gòu)有 列表list，元祖tuple，字典dict
3.1 列表list
python的列表list是由對其他對象的引用組成的連續(xù)數(shù)組，指向這個數(shù)組的指針及其長度被保存在一個列表頭結(jié)構(gòu)中。
當(dāng)python定義一個list時，Cpython會定義指向列表對象的指針數(shù)組ob_item和 申請的內(nèi)存槽的個數(shù)allocated。
list可以存儲任意類型的數(shù)據(jù)，pop()默認(rèn)刪除最后一個元素，pop(1)第二個元素，remove(指定元素)，del(從內(nèi)存中刪除列表)
列表的增加：+（拼接），append（追加），extend(拉伸),insert（插入）
列表的刪除：pop(默認(rèn)刪除最后一個元素)，pop(1）刪除第二個元素，del(從內(nèi)存中刪除列表)
3.2 元組tuple
跟list相似，但tuple的元素不可變，一旦設(shè)定不可通過索引修改。
1.元組是固定的列表，那么元組的意義何在呢？
因為tuple不可變，所以代碼更安全。如果可能，能用tuple代替list就盡量用tuple
并且需要注意元組中元素的可變性??！
2.空的tuple可以記為()，若只有一個元素的tuple記為(1,)
因為記為(1)的話，這個實際代表的是數(shù)字1，此時()是數(shù)學(xué)公式中的小括號
3.因為元組是固定的列表，所以其內(nèi)置的大多數(shù)的方法和列表是差不多的。
4.可以通過tuple將序列轉(zhuǎn)換為元組，用法和list一樣
3.3 字典dict
在python中字dict和set是非常常用的兩種數(shù)據(jù)結(jié)構(gòu)，但是兩種數(shù)據(jù)結(jié)構(gòu)為什么要放在一起討論。因為他們之所以擁有非?？斓乃俣?，是因為他們的內(nèi)部結(jié)構(gòu)都是散列表
dict中的散列表
散列表算法：正常想要獲取dict中的值，首先要知道key,通過dict[key]獲取對應(yīng)的value,在散列表中為了達到這種操作，首先會計算key的hash值即散列值，把這個值最低的幾位數(shù)字當(dāng)作偏移量，在散列表里查找表元（具體取幾位，得看當(dāng)前散列表的大?。?。若找到表元為空，異常KeyError，不為空，表元里會有一對found_key:found_value。這時候python會校驗search_key==found_key是否為真，如果它們相等的話。就會返回found_value。若果兩個值不匹配，則是散列沖突。為了解決散列沖突，算法會在散列值中另外再取幾位，然后用特殊的方法處理一下，把新得到的數(shù)字再當(dāng)作索引來尋找表元。
1.key必須是可hash的，所有不可變類型都是可哈希的故可作為鍵，可變類型不可哈希即不可作為鍵，如列表，字典類型。
2.在內(nèi)存消耗上是巨大的，由于字典使用了散列表，而散列表又必須是稀疏的，這導(dǎo)致它在空間上的效率低下。
3.key查詢很快，hash表空間換時間。
4.key的排列順序，取決于添加順序，并且當(dāng)dict添加新數(shù)據(jù)，原有的排列可能會被打亂，因為Python 會設(shè)法保證大概還有三分之一的表元是空的，所以在快要達到這個閾值的時候，原有的散列表會被復(fù)制到一個更大的空間里面。這時候重新hash導(dǎo)致排列順序改變。
5.由此可知，不要對字典同時進行迭代和修改。如果想掃描并修改一個字典，最好分成兩步來進行：首先對字典迭代，以得出需要添加的內(nèi)容，把這些內(nèi)容放在一個新字典里；迭代結(jié)束之后再對原有字典進行更新。
dict基本操作
1. 創(chuàng)建：d={'a':1,'b':2,'c':3}
2.取值：d['a']
3.添加元素：d['d']=4
4.刪除元素：d.pop('b')；del d['b']
5.訪問元素d['f'],不存在會報錯，用d.get('f')沒有異常，只返回None
6.長度： len(d)
