DataStructure & Algorithm
===
```python
# codind:utf-8
# Q. a+b+c=1000, a^2+b^2=c^2
# 枚舉法
# 解一: 197s
# import time
# start = time.time()
# for a in range(0,1001):
# for b in range(0,1001):
# for c in range(0,1001):
# if a+b+c==1000 and a**2+b**2==c**2:
# print("a, b , c: %d ,%d ,%d"%(a, b, c))
# 解二: 1s
# c = 1000-a-b
import time
start = time.time()
for a in range(0,1001):
for b in range(0,1001):
c = 1000-a-b
if a**2+b**2==c**2:
print("a, b , c: %d ,%d ,%d"%(a, b, c))
end = time.time()
print("time: %d" %(end-start))
print("end")
```
> 如何判斷算法效率?
> - 單純以運行時間?
> - 計算機環境等足以影響運行時間,
> - 故以運行時間判斷不一定好
> - 基本運算數量
> - 機器執行總時間不同,
> - 但執行基本運算數量(步驟數)大體相同
> - 基本運算數量的總和, 稱為『時間複雜度』
### 時間複雜度(解一)
> `for a` > 1000, `for b` > 1000, `for c` > 1000
> `if(a+b+c`, `a+b+c==1000`,
> `a\**2`,`b\**2`,`c\**2`, `a\**2+b\**2`,`a\**2+b\**2\==c**2`,`and`>8
> `print(%)`, `print()`>2
> T = 1000\*1000\*1000\*10
>
> Q. a+b+c=2000, a^2^+b^2^=c^2^
> T = 2000\*2000\*2000\*10
> Q. a=b=c=N ,...
> T(n) = N^3^ * 10 > T(n)即為時間複雜度
#### 大O記法
> - 取時間複雜度的漸進函數(忽略常數)
> - T(n) = N^3^ * 10 > G(n) = N^3^
> - 亦即T(n) = k*G(n) + c = O(G(n))
#### 時間複雜度基本計算規則
> - 順序: +
> - 循環: *
> - 分支: 取最大值
> - 基本操作> O(1)
> - 一般分析算法都是指『最壞時間複雜度』
> - 最優時間複雜: 最少基本操作
> - 最壞時間複雜: 最多基本操作
> - 平均時間複雜: (最優+最壞)/2
> - 最後忽略常數項與次要項
> - ax^2^+bx+c:
> - a,c :常數
> - bx: 次要
#### 時間複雜度(解二)
> for a > 1000, for b > 1000
> c = O(1)
> if = 1(True, print) or 0(False) > max=1
> T(n) = 1000 \* 1000 \* (1+max(1,0)) = 1000^2^ \*2
> T(n) = n^2^ \* 2 = O(n^2^)
#### 常見時間複雜度
|舉例|階|
|:--:|:--:|
|10|O(1)|
|an+b|O(n)|
|an^2^+b|O(n^2^)|
|an^3^+b|O(n^3^)|
|alog~2~n+b|O(logn)|
|an+bnlog~2~n+c|O(nlogn)|
|2^n^|O(2^n^)|
> O(1)<O(logn)<O(n)<O(nlogn)<O(n^2^)<O(n^3^)<O(2^n^)<O(n!)<O(n^n^)
## timeit
`class timeit.Timer(stmt='pass', setup='pass', timer=<timer function>)`
> - Timer: 測試代碼執行速度的類
> - stmt: 測試代碼語句(statment)
> - setup: 設置
> - timer: 定時器(與平台有關)
`timeit.Timer.timeit(number=1000000)`
> - timeit返回平均速度
> - number: 測試次數
```python
#coding:utf-8
from timeit import Timer
# 運作模式:(vs.extend)
# 先建立一個空列表
# 將li丟進該列表後,再將i丟進該列表
# 最後li指向新的列表
def t1():
li = []
for i in range(10000):
li = li + [i]
# +=的運作模式跟extend差不多,
# 都是在原來的列表進行操作
def t2():
li = []
for i in range(10000):
li += [i]
# extend運作模式:(vs.+)
# 直接在li列表中加入i
# extend追加列表或可迭代對象, 將其所有元素都添加(vs.append)
def t3():
li = []
for i in range(10000):
li.extend([i])
# append只能追加單一元素(vs.extend)
# 對列表尾添加(vs.insert)
def t4():
li = []
for i in range(10000):
li.append(i)
# 對列表頭添加(vs.append)
# 因為數據結構的關係, 對頭添加的速度非常慢
def t5():
li = []
for i in range(10000):
li.insert(0, i)
# 註一
def t6():
li = [i for i in range(10000)]
# 註二
def t7():
li = list(range(10000))
# Timer 不是在這個文件執行, 故要導入到該執行文件中
# 作為啟動文件, 名字應該是__main__
timer1 = Timer("t1()", "from __main__ import t1")
print("+:", timer1.timeit(1000))
timer2 = Timer("t2()", "from __main__ import t2")
print("+=:", timer2.timeit(1000))
timer3 = Timer("t3()", "from __main__ import t3")
print("extend:", timer3.timeit(1000))
timer4 = Timer("t4()", "from __main__ import t4")
print("append:", timer4.timeit(1000))
timer5 = Timer("t5()", "from __main__ import t5")
print("insert:", timer5.timeit(1000))
timer6 = Timer("t6()", "from __main__ import t6")
print("[i for i in range]:", timer6.timeit(1000))
timer7 = Timer("t7()", "from __main__ import t7")
print("range(list):", timer7.timeit(1000))
```
```$
+: 181.142842282
+=: 0.9807232400000032
extend: 1.4030078149999952
append: 0.8890636299999812
insert: 22.47004824000001
[i for i in range]: 0.4352005479999832
range(list): 0.19273629400001369
```
```python
# 註一: 複習
In [29]: a = (i for i in range(10))
In [30]: a
Out[30]: <generator object <genexpr> at 0x10d4a3f48>
In [31]: next(a)
Out[31]: 0
In [32]: next(a)
Out[32]: 1
In [33]: list(a)
Out[33]: [2, 3, 4, 5, 6, 7, 8, 9]
In [34]: a = [i for i in range(10)]
In [35]: a
Out[35]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# 註二: 複習(python2 vs python3的range)
# python3
In [36]: a = range(10)
In [37]: a
Out[37]: range(0, 10)
In [38]: list(a)
Out[38]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# python2
In [1]: a = range(10)
In [2]: a
Out[2]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
```
#### dict內置操作的時間複雜度
|||
|:--:|:--:|
|copy|O(n)|
|get item|O(1)|註一|
|set item|O(1)|
|delete item|O(1)|
|contains(in)|O(1)|
|iteration|O(n)|
> 註一:
> > key取value
## 數據結構
> - 對於計算機來說, 基本類型僅為str, floar, int, char等
> - 且基本類型也僅僅存一個數據而已, 如何把數個基本元素組合即為數據結構欲探討的議題
> - 數據組成方式不同, 處理數據時的算法也就不同
```python
# Q. 如何保存學生信息?
# [()]
student1 = [
("Mary", 18, "ADDR1"),
("Edison", 17, "ADDR2")
]
# 查詢
for i in student1: # O(n)
if i(0) == "Mary":
print(i)
# [{}]
student2 = [
{
"name":"Mary",
"age": 18,
"ADDR":"ADDR1"
},
{
}
]
# {{}}
student3 = {
"Mary":{
"age": 18,
"ADDR": "ADDR1"
},
"Edison":{
}
}
# 查詢
student3["Mary"] # O(1)
```
> 程序 = 數據結構 + 算法
### 抽象數據類型(Abstract Data Type)
> - 把數據類型與其運算方法封裝
> - 常見的運算方法如增刪改查
```python
class arr(obj):
def pop(self):
def append(self):
...
```
## 線性表
### 順序表
> Q. Int = 1,11,111, 如何保存這三個整數?
```
# li = [] => 高階數據結構
- 內存
- 連續的存儲單元
- 基本單元: 1Byte = 8bit
- 一個單元會有一個地址標示, CPU就可以依據標示找到相應數據
_ _ _ _ _ _ _ _
0x01 |_|_|_|_|_|_|_|_| : 1Byte
0x02 |_|_|_|_|_|_|_|_|
0x03 |_|_|_|_|_|_|_|_|
0x04 |_|_|_|_|_|_|_|_|
- INT
- 對於32位元機器來說, Int佔4Byte
- Int a = 1
_ _ _ _ _ _ _ _
0x01 |0|0|0|0|0|0|0|0|
0x02 |0|0|0|0|0|0|0|0|
0x03 |0|0|0|0|0|0|0|0|
0x04 |0|0|0|0|0|0|0|1|
‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾
- char:
- 1Byte
- 字符,
- 字符集合 = str
- 類型
- 以上面0x01~0x04為例,
- 如果我告訴計算機為整數, 那麼就是1
- 如果我告訴計算機為char, 那麼此時就要對應 char * 4
- 00000000為何
- 00000001為何
- 亦即類型定義了記憶體中佔多大, 以及電腦讀取時如何處理這些二進制數據
- 順序表
- 按順序連續存放, 此時即可方便處理, 此稱為順序表
- 回到問題, 如何存儲 li = [1,11,111]
________
li-> 0x18~0x22 |_______1| : 4Byte
0x22~0x26 |______11|
0x26~0x30 |_____111|
- 向os申請12Byte, os會一次返回
- 數據存儲完畢後, li就會指向起始地址(0x18)
- li[0] = 0x18 + 0*4Byte
- li[2] = 0x18 + 2*4Byte
- 故該數字代表偏移量的意思
- 此種存儲方法前提必須每個存儲數據大小相同
- 元素外置
- 當存儲數據大小不同的數據時, 此時就無法用基本順序表存儲
- 故此時可以存儲數據地址
- 每個地址事實上佔用4Byte
- li = [11, "ab\0", 1.11]
________ ________
li-> 0x300~0x304 |____0x99|-> 0x99 |_11_____|
0x304~0x308 |___0x121|-> 0x121 |_"ab\0"_|
0x308~0x312 |___0x231|-> 0x231 |_1.11___|
```
#### 順序表的結構
```
# 順序表包含了表頭信息與數據區
# 而表頭信息包含了容量與元素個數
# 容量:
# 在向os申請內存空間時, 必須估計大小, 否則os也不知道要給你多少
# 元素個數:
# 已使用多少空間
# 一體式 li = [1,11,111] -> 0x10
_max _num ____ ____ ____ ____
| 4| 3| 1| 11| 111| |
‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾
0x10 0x14 0x18 0x22 0x26 0x30
# 分離式 li = [1,11,111]
_max _num ____ ____ ____ ____ ____
| 4| 3|0x18| | 1| 11| 111| |
‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ↘ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾
0x55 0x59 0x63 0x18 0x22 0x26 0x30
# 區別:
# 假設 li = [1,11,111,10,7]
# 此時超過當時申請的空間
# 一體式:
# 重新申請新的內存空間後存儲對應數據
# 故li 指向會改變
# 分離式:
# 只需申請數據區的內存空間
# 信息區重新指向新內存空間地址即可
# 故li 指向不變
# 擴充預留
# 預留多: 佔用大, 擴充次數少
# 預留少: 佔用小, 擴充次數多
```
#### 順序表增刪
```
# 增
# 表尾添加
_max _num ____ ____ ____ ____ ____ ____ ____ ____
| 8| 3| 1| 11| 111| 21| 22| 23| 26| →20|
‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾
# 直接插入: O(1)
# 保序添加
_max _num ____ ____ ____ ____ ____ ____ ____ ____
| 8| 3| →20| 1| 11| 111| 21| 22| 23| 26|
‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾
# 先將26往後移,接著將23往後移...: O(7)
# 最後插入20: O(8)/ O(n)
# 非保序添加(少見)
_max _num ____ ____ ____ ____ ____ ____ ____ ____
| 8| 3| →20| 11| 111| 21| 22| 23| 26| 1|
‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾ ‾‾‾‾
# 將1一到最後一位
# 插入20: O(2)/O(1)
# 刪除亦同, 刪完往前補
# 表尾: O(1)
# 保緒: O(n)
# 非保緒: O(1)
```
#### Python順序表
```
# list
- 下標查詢(index x[]): O(1) > 順序表
- 『任意元素』加入, 『id標示不變』> 元素外置,分離式
- 建立一個空列表時, 系統分配8個元素存儲區(存儲地址\4Byte)
- 擴充: 每次4倍, 當該表到一定大小時, 則改為一倍
# tuple
- 下標查找> 順序表
```
#### list內置操作的時間複雜度
|Operation|Big-O Efficiency||
|:--:|:--:|:--:|
|index x[]|O(1)||
|index assignment|O(1)||
|append|O(1)||
|pop()|O(1)||
|pop(i)|O(n)||
|insert(i,item)|O(n)||
|del operator|O(n)|註一|
|iteration|O(n)|迭代|
|contains(in)|O(n)|需遍歷一次才知道存不存在|
|get slice[x:y]|O(k)|註二|
|del slice|O(n)|註三|
|set slice|O(n+k)|註四|
|reverse|O(n)||
|concatenate|O(k)|註五|
|sort|O(n log n)||
|multiply|O(nk)||
> 註一:
> - 元素外置,
> - 列表地址可以一次刪除,
> - 但是指向的存儲空間必須一個一個刪
>
> 註二:
> > - k: 距離
> > - 取x時: O(1)
> > - 取到y即停止: O(k)
>
> 註三:
> > - 刪除後, 後面的要補上, 故O(n)
>
> 註四:
> ```python
> In [12]: a = [1,2,3,4,5]
> In [13]: a[0:2] = [55,66,77,88]
> In [14]: a
> Out[14]: [55, 66, 77, 88, 3, 4, 5]
> # 先刪掉指定切片O(n)
> # 補充多少個O(k)
> ```
>
> 註五:
> > - li += [li]
> > - 往後面添加多少個元素: O(k)
>
> 註六:
> ```python
> In [15]: a = [1] # n
> In [16]: a*5 # k
> Out[16]: [1, 1, 1, 1, 1]
> ```
### 鏈表
#### 單鏈表
```
______ ______
| 數據區| 鏈接區|
‾‾‾‾‾‾ ‾‾‾‾‾‾
element next
__ ____ __ ____ __ ____
p-> | 1|0x66|-> |11|0x87|-> |20| ⊥ |
‾‾ ‾‾‾‾ ‾‾ ‾‾‾‾ ‾‾ ‾‾‾
0x55 0x66 0x87
# P 變量
# ⊥ 表示指向空的意思
# 數據區+鏈接區, 整體稱為節點(node)
# 實現:
# 思考:
a = 10
b = 20
a,b = b,a
是如何實現的?
# a = 10, b = 20
_a__ __ _b__ __
|next|->|10|, |next|->|20|
‾‾‾‾ ‾‾ ‾‾‾‾ ‾‾
# a,b = b,a
# 先找到b的地址後, 地址指向存有20的內存
# 接著換a
# a,b = 20,10
# a->20, b->10
# 最後a與b中的鏈接區改變next的指向
# 故改變的只有a,b本身的內存指向,
# 原本存有10與20的內存完全沒有變動
# cf. C
# int a = 10;
_a
|10|
‾‾
# C語言申請空間時就指定了該空間的類型, 且該空間的別名就為a
# a空間只能保存int
# def func():
pass
a = func
# 所以python的變量才可以任意改變元素類型, 因為他保存的僅僅是地址
# 實現單鏈概念
____________0x55 ____________0x66
|class node1(): | |class node2(): |
| element = 10| | element = 20|
| next = node2| -> | next |
‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾ ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
# 亦即node1的next指向0x66
```
#### 實現單鏈表
```python
#coding:utf-8
class Node(object):
def __init__(self, elem):
self.elem = elem
# 一開始並不知道指向誰,所以先指向None
self.next = None
class SingleLinkList(object):
""""""
# 需要保存頭節點(p)信息,故創建head屬性, 保存在對象中
# 對於使用者來說,並不需要知道頭節點屬性, 故私有
# 假設有用戶會先創立一個節點, 然後直接傳進來讓head指向的需求
# 假設有用戶沒有先創或傳node進來的需求, 故將node預設為Node, 以避免沒傳參報錯
def __init__(self, node=None):
self.__head = node
def is_empty(self):
"""判斷鏈表是否為空"""
return self.__head == None
def length(self):
""""""
# current游標: 用來移動遍歷節點
cur = self.__head
# content記錄數量
# 初始值要等於0?1?
# 如果初始值為1的話, 那麼一開始node=None時要額外處理, 否則會多1
# 以人腦的邏輯來看, 應該是一開始0, 數一次+1, 故我使用0
content = 0
# 判斷式cur!=None? cur.next!=None?
# 如果下次是next就不+的話, 會少+1次
while cur != None:
content+=1
cur = cur.next
return content
def travel(self):
"""遍歷列表"""
cur = self.__head
while cur != None:
print(cur.elem , end=" ")
cur = cur.next
print("")
def append(self, item):
"""尾插法"""
# item不是節點! 而是一個數據
# 故首先建立一個節點
node = Node(item)
# 如果一開始就指向None,
# 由於None沒有next, 故會出錯
# 所以須先判斷
# if self.__head == None:
if self.is_empty():
self.__head = node
else:
cur = self.__head
# 先讓游標一直往後走, 走到next=None跳出
while cur.next != None:
cur = cur.next
# 此時游標停在尾節點處, 尾節點指向剛創建的節點即可
cur.next = node
def add(self, item):
"""頭插法"""
node = Node(item)
# 注意順序,
# 如果先把self.__head指向node,
# 那麼原本self.__head的數據就會0而被回收
# node.next就沒東西指了
node.next = self.__head
self.__head = node
def insert(self, pos, item):
""""""
# 特殊情況: 位置插在0或負數, 視為頭插
if pos <=0:
self.add(item)
# 特殊情況: 位置插在最後面, 通通視為尾插
elif pos > (self.length()-1):
self.append(item)
else:
node = Node(item)
# pre/prior 當前的上一個
pre = self.__head
count = 0
while count < (pos-1):
count +=1
pre = pre.next
node.next = pre.next
pre.next = node
def remove(self, item):
""""""
cur = self.__head
pre = None
while cur != None:
if cur.elem == item:
# 如果是頭節點, pre指向None> 沒有next
# 故要直接用self來操作
if cur == self.__head:
self.__head = cur.next
else:
pre.next = cur.next
break
else:
pre = cur
cur = cur.next
def search(self, item):
""""""
cur = self.__head
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next
return False
if __name__ == "__main__":
sll = SingleLinkList()
print(sll.is_empty())
print(sll.length())
sll.append(1)
print(sll.is_empty())
print(sll.length())
print("-"*10)
sll.append(2)
sll.add(99)
sll.append(3)
sll.append(4) #99 1 2 3 4
sll.insert(-100, 1000)
sll.insert(2, 100)
sll.insert(100, 10)
sll.travel()
print("-"*10)
print(sll.search(3))
print(sll.search(999))
sll.remove(3)
sll.travel()
sll.remove(1000)
sll.travel()
sll.remove(10)
sll.travel()
```
```python
# == 判斷返回T/F
In [14]: a = None
In [15]: print(a==None)
True
# len
__sll cont=0__node1 cont=1__node2 cont2__node3 cont=3
|_head| -> |elem = 100 | |elem = 10 | |elem = 10 |
| | |next = node2| -> |next = node3| -> |next = None | -> None
‾‾‾‾‾ ‾‾‾‾‾‾‾‾‾‾‾‾ ‾‾‾‾‾‾‾‾‾‾‾‾ ‾‾‾‾‾‾‾‾‾‾‾‾
->None 0 +1=1 +1=2 +1=3
```
### 鏈表 vs 順序表
|操作|鏈表|順序表|
|:--:|:--:|:--:|
|訪問|O(n)|O(1)|
|頭插(刪)|O(1)|O(n)|
|尾插(刪)|O(n)|O(1)|
|中插(刪)|O(n)|O(n)|
||離散|連續|
- 優點: 有效運用『分散』的內存(順序表: 連續內存)
- 缺點:
- 單個節點所需空間較大
- 每個節點都需要存數據跟鏈接
- 順序表只需要存一次(表頭信息)
- 無法一次性定位
### 雙鏈表
```
prev __ next -> prev __ next -> prev __ next
p-> |None| 1|0x66| |0x55|11|0x87| |0x66|20| ⊥ |
‾‾‾‾ ‾‾ ‾‾‾‾ <- ‾‾‾‾ ‾‾ ‾‾‾‾ <- ‾‾‾‾ ‾‾ ‾‾‾‾
0x55 0x66 0x87
```
```python
#coding:utf-8
from singleLinkList import SingleLinkList
class Node(object):
def __init__(self, elem):
self.elem = elem
self.next = None
self.prev = None
class DoubleLinkList(object):
def __init__(self, node=None):
self.__head = node
def is_empty(self):
"""判斷鏈表是否為空"""
return self.__head == None
def length(self):
""""""
cur = self.__head
content = 0
while cur != None:
content+=1
cur = cur.next
return content
def travel(self):
"""遍歷列表"""
cur = self.__head
while cur != None:
print(cur.elem , end=" ")
cur = cur.next
print("")
def add(self, item):
node = Node(item)
node.next = self.__head
# 順序一
#self.__head.prev = node
#self.__head = node
# 順序二
self.__head = node
node.next.prev = node
def append(self, item):
"""尾插法"""
node = Node(item)
if self.is_empty():
self.__head = node
else:
cur = self.__head
while cur.next != None:
cur = cur.next
cur.next = node
node.prev = cur
def insert(self, pos, item):
""""""
if pos <=0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
node = Node(item)
cur = self.__head
count = 0
while count < pos:
count +=1
cur = cur.next
node.prev = cur.prev
node.next = cur
# 順序一
cur.prev.next = node
cur.prev = node
# 順序二
#cur.prev = node
#node.prev.next = node
def remove(self, item):
""""""
cur = self.__head
while cur != None:
if cur.elem == item:
if cur == self.__head:
self.__head = cur.next
# 如果只有一個節點
# 那個next會指向None
# 而None沒有prev
# 故應判斷cur.next is True(不是None)
if cur.next:
cur.next.prev = None
else:
# 理由同上
if cur.next:
cur.next.prev = cur.prev
cur.prev.next = cur.next
break
else:
cur = cur.next
def search(self, item):
""""""
cur = self.__head
while cur != None:
if cur.elem == item:
return True
else:
cur = cur.next
return False
if __name__ == "__main__":
dll = DoubleLinkList()
print(dll.is_empty())
print(dll.length())
dll.append(1)
print(dll.is_empty())
print(dll.length())
print("-"*10)
dll.append(2)
dll.add(99)
dll.append(3)
dll.append(4) #99 1 2 3 4
dll.insert(-100, 1000)
dll.insert(2, 100)
dll.insert(100, 10)
dll.travel()
print("-"*10)
print(dll.search(3))
print(dll.search(999))
dll.remove(3)
dll.travel()
dll.remove(1000)
dll.travel()
dll.remove(10)
dll.travel()
```
### 單向循環鍊錶
> 尾節點轉回來連到頭節點
```python
#coding:utf-8
class Node(object):
def __init__(self, elem):
self.elem = elem
self.next = None
class SingleCycleLinkList(object):
""""""
def __init__(self, node=None):
self.__head = node
# 先判斷節點不為None
if node:
node.next = node
def is_empty(self):
"""判斷鏈表是否為空"""
return self.__head == None
def length(self):
""""""
if self.is_empty():
return None
cur = self.__head
# 用next會少一次, 故起始設1
content = 1
# while cur != None:
# 循環列表會從頭, 故不會有None
# cur == self.__head也無法使用,
# 因為頭節點本來就會指向self.__head,
# 故會無法判斷是第一輪還是循環回來的
while cur.next != self.__head:
content+=1
cur = cur.next
return content
def travel(self):
"""遍歷列表"""
if self.is_empty():
return None
cur = self.__head
while cur.next != self.__head:
print(cur.elem , end=" ")
cur = cur.next
# 尾節點未打印
print(cur.elem)
def append(self, item):
"""尾插法"""
node = Node(item)
if self.is_empty():
self.__head = node
node.next = node
else:
cur = self.__head
while cur.next != self.__head:
cur = cur.next
node.next = self.__head
cur.next = node
self.travel()
def add(self, item):
"""頭插法"""
node = Node(item)
if self.is_empty():
self.__head = node
node.next = node
else:
cur = self.__head
while cur.next != self.__head:
cur = cur.next
node.next = self.__head
self.__head = node
#cur.next = node
cur.next = self.__head
def insert(self, pos, item):
""""""
if pos <=0:
self.add(item)
elif pos > (self.length()-1):
self.append(item)
else:
node = Node(item)
pre = self.__head
count = 0
while count < (pos-1):
count +=1
pre = pre.next
node.next = pre.next
pre.next = node
def remove(self, item):
""""""
# 一開始就None
if self.is_empty():
return
cur = self.__head
pre = None
while cur.next != self.__head:
if cur.elem == item:
# 頭節點
if cur == self.__head:
temp = self.__head
while temp.next != self.__head:
temp = temp.next
self.__head = cur.next
temp.next = self.__head
# 中間節點
else:
pre.next = cur.next
# 用break退出循環後會執行下面的if,
# 然後被指向None...,
# 故結束後直接return退出def
# break
return
else:
pre = cur
cur = cur.next
# 退出循環後, cur指向尾節點
if cur.elem == item:
# 只有一個節點
if pre == None:
self.__head = None
else:
pre.next = cur.next
def search(self, item):
""""""
if self.is_empty():
return False
cur = self.__head
while cur.next != self.__head:
if cur.elem == item:
return True
else:
cur = cur.next
if cur.elem == item:
return True
return False
if __name__ == "__main__":
sll = SingleCycleLinkList()
print(sll.is_empty())
print(sll.length())
sll.append(1)
print(sll.is_empty())
print(sll.length())
print("-"*10)
sll.append(2)
sll.add(99)
sll.append(3)
sll.append(4) #99 1 2 3 4
sll.insert(-100, 1000)
sll.insert(2, 100)
sll.insert(100, 10)
sll.travel()
print("-"*10)
print(sll.search(3))
print(sll.search(999))
sll.remove(3)
sll.travel()
sll.remove(1000)
sll.travel()
sll.remove(10)
sll.travel()
```
### 思考
> - 雙向循環鏈錶
> - 鏈表做表頭信息
```
__ prev __ next -> prev __ next
p-> | | -> |None| 1|0x66| |0x55|11|0x87|
‾‾ ‾‾‾‾ ‾‾ ‾‾‾‾ <- ‾‾‾‾ ‾‾ ‾‾‾‾
0x55 0x66
```
## 棧(Stack)
> - 一種線性容器
> - 只允許從一端操作
> - 後進先出(Last In First Out, LIFO)
```python
#coding:utf-8
class Stack(object):
""""""
def __init__(self):
self.__list = []
def push(self, item):
""""""
# 視資料結構而定
# 尾插
# 順序表O(1)
# 鏈表O(n)
# 頭插
# 順序表O(n)
# 鏈表O(1)
# 這裡使用順序表寫, 故用尾插
self.__list.append(item)
# self.__list.insert(0, item)
def pop(self):
""""""
return self.__list.pop()
# return self.__list.pop(0)
def peek(self):
""""""
if self.__list:
return self.__list[-1]
else:
return None
def is_empty(self):
""""""
return self.__list == []
def size(self):
""""""
return len(self.__list)
if __name__ == "__main__":
s = Stack()
print(s.is_empty())
s.push(1)
s.push(2)
s.push(3)
print(s.is_empty())
print(s.size())
print(s.pop())
print(s.pop())
print(s.pop())
print(s.is_empty())
```
## 隊列(queue)
> - 一種線性容器
> - 只允許一端進一端出
> - 先進先出(FIFO)
```python
#coding:utf-8
class Queue(object):
""""""
def __init__(self):
self.__list = []
def enqueue(self, item):
""""""
# 當出入隊頭尾插複雜度剛好相反時,
# 視使用頻率而定
self.__list.append(item)
# self.__list.insert(0, item)
def dequeue(self):
""""""
return self.__list.pop(0)
#return self.__list.pop()
def is_empty(self):
""""""
return self.__list == []
def size(self):
""""""
return len(self.__list)
if __name__ == "__main__":
q = Queue()
print(q.is_empty())
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.size())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.size())
```
### 雙端隊列(deque, double-ended queue)
> 雙進雙出
```python
#coding:utf-8
class Deque(object):
""""""
def __init__(self):
self.__list = []
def add_front(self, item):
"""頭插"""
self.__list.insert(0, item)
def add_rear(self, item):
"""尾插"""
self.__list.append(item)
def remove_front(self):
"""頭刪"""
return self.__list.pop(0)
def remove_rear(self):
"""尾刪"""
return self.__list.pop()
def is_empty(self):
""""""
return self.__list == []
def size(self):
""""""
return len(self.__list)
if __name__ == "__main__":
q = Deque()
print(q.is_empty())
q.add_front(1)
q.add_front(2)
print(q.size())
print(q.remove_front())
print(q.remove_front())
print(q.size())
```
## 排序算法(Sorting Algorithm)
### 穩定性
```
# li = [(8,0),(3,1),(2,2),(8,3),(4,4)]
還小至大排序
(2,2),(3,1),(4,4),(8,0),(8,3) > 依序 > 穩定
(2,2),(3,1),(4,4),(8,3),(8,0) > 改序 > 不穩定
```
### 冒泡排序(Bubble Sort)
> 重複遍歷排序
> 一次比較兩個
```python
#coding:utf-8
# [0] [1] [2] [3] n = 4
# 第一趟比較
# [0]<>[1] [1]<>[2] [2]<>[3]
# 此時 [3] 會得到最大的數
# 總共比較了 n-1 次
# 第二趟比較
# [0]<>[1] [1]<>[2]
# [5]已經是最大的數了，故不需要再參與比較
# 此趟會得到[2]第二大的數
# 總共比較了 n-2 次
# 第三趟比較
# [0]<>[1]
# [1]得到第三大的數
# 總共比較了 n-3 次
# 總共會跑 n-1 趟 (確定[1]~[3]) 的數
# [1]~[3] 都確定時, [0] 就確定了
''' 以前寫的東西
def bubble_sort(alist):
n = len(alist) # 假設n=4
for j in range(0, n-1):
"""Y軸"""
print(j,"-"*10)
for i in range(0, n-1-j):
"""X軸"""
# 直接從0開始, 取首位比較方便
# 第1圈(j=0)比較 n-1(3)次 > n-1-0
# 第2圈(j=1)比較 n-2(2)次 > n-1-1
# 第3圈(j=2)比較 n-3(1)次 > n-1-2
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
print(i,alist)
'''
# 19/ 11/ 19 的新想法
# 把j改成1, 表示第一圈, 這樣比較易讀
def bubble_sort(alist):
n = len(alist)
count = 0
for j in range(1,n):
print('第%d圈'%j)
count += 1
for i in range(0,n-j):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
count += 1
print('i = %d: '%(i), alist)
print(count)
if __name__ == "__main__":
li = [54,26,93,17,77,31,44,55,20]
bubble_sort(li)
# j = 0 [26, 54, 17, 77, 31, 44, 55, 20, 93]
# j = 1 [26, 17, 54, 31, 44, 55, 20, 77, 93]
# j = 2 [17, 26, 31, 44, 54, 20, 55, 77, 93]
# j = 3 [17, 26, 31, 44, 20, 54, 55, 77, 93]
# j = 4 [17, 26, 31, 20, 44, 54, 55, 77, 93]
# j = 5 [17, 26, 20, 31, 44, 54, 55, 77, 93]
# j = 6 [17, 20, 26, 31, 44, 54, 55, 77, 93]
# j = 7 [17, 20, 26, 31, 44, 54, 55, 77, 93]
# 從結果可以看到，有可能還沒跑完所有趟數就已經完全排好了
# 此時應該用判斷來跳出而簡化時間複雜度
```
```python
#coding:utf-8
# 優化
'''以前的我寫法
def bubble_sort(alist):
n = len(alist)
for j in range(0, n-1):
"""Y軸"""
count = 0
print(j,"-"*10)
for i in range(0, n-1-j):
"""X軸"""
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
count+=1 # 如有交換, 計數+1
print(i,count,alist)
# 如果都沒換表示順序正常, 跳出
if 0 == count:
break
'''
# 19/ 11/ 19 的新想法
def bubble_sort(alist):
n = len(alist)
count = 0 # 專門紀錄時間複雜度
for j in range(1,n):
print('第%d圈'%j)
count+=1
isSort = True # 一開始假設已經排好了
for i in range(0,n-j):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
isSort = False # 如果有進if交換, 表示還沒排好
count +=1
print('i = %d: '%(i), alist)
print(isSort)
if isSort: # 如果跑完整趟內圈for都沒進if, 表示已經排序完成, 直接跳出
break
print(count)
if __name__ == "__main__":
#li = [54,26,93,17,77,31,44,55,20]
li = [1,2,3,5,4]
bubble_sort(li)
# 最優O(n)
# 最壞O(n^2)
# 穩定性: 穩定
# li = [(8,0),(3,1),(2,2),(8,3),(4,4)]
# (3,1),(8,0),(2,2),(8,3),(4,4)
# (3,1),(2,2),(8,0),(8,3),(4,4) 依樣大，不換
# (3,1),(2,2),(8,0),(4,4),(8,3)
# ...
# (2,2),(3,1),(4,4),(8,0),(8,3) 最後8,0還是在8,3前面
```
### 選擇排序(Selection Sort)
> - 從序列中找到最小(大)值, 放到前面依序排列
```python
#coding:utf-8
def selection(alist):
""""""
n = len(alist)
print(alist)
for j in range(n-1):
min = j
print(j,'-'*10)
#for i in range(1,n):
for i in range(j+1, n):
if alist[min] > alist[i]:
min = i
print(min)
alist[min], alist[j] = alist[j], alist[min]
print(alist)
# alist = [54,226,93,17,77,31,44,55,20]
# 0 1 2 3 4 5 6 7 8
#
# j = 0
# min = 0 vs 0+1...
# alist[0], alist[3]= alist[3], alist[0]
#
# j = 1
# min = 1 vs 1+1... j vs j+1
# min = 2,3,4,5,6,7,8
# [1],[8]=[8],[1]
if __name__ == "__main__":
alist = [54,226,93,17,77,31,44,55,20]
selection(alist)
# 最優O(n^2) 每個都必須比較
# 最壞O(n^2)
# 穩定性: 不穩定
# li = [(8,0),(3,1),(2,2),(8,3),(4,4)]
# max = 8,0 > (3,1),(2,2),(8,3),(4,4),(8,0)
# max = 8,3 > (3,1),(2,2),(4,4),(8,3),(8,0) 8,3跑到前面了
```
### 插入排序(insert sort)
> - 從無序序列中取一個與有序序列比較,
> - 與選擇排序不同處:
> - 選擇排序
> - 選擇排序為在無序序列中選擇最小(大)至有序序列依序排列
> - 被選擇者所排序位置為固定
> - 插入排序
> - 插入排序為選擇後與有序序列比較,
> - 有序序列為浮動的
```python
#coding:utf-8
def insertSort(alist):
n = len(alist)
print(alist)
for j in range(1, n):
# i 代表起始位置
i = j
# 從無序序列取起始位置(i)值與有序序列比較
while i > 0:
# 相比滿足條件換位
if alist[i-1] > alist[i]:
alist[i-1], alist[i] = alist[i], alist[i-1]
i-=1
# 不滿足表示正確序列, 跳出
else:
break
print(alist)
# 26, 54, 93 17
# i-3 i-2 i-1 i
# 26,54, 17, 93
# i-1
if __name__ == "__main__":
li = [54,26,93,17,77,31,44,55,20]
insertSort(li)
# 最優O(n)
# 最壞O(n^2)
# 穩定
```
### ShellSort
> - 插入排序改版
> - Shell步長為1相當於Insert
```python
#coding:utf-8
def shell_sort(alist):
""""""
# n = 9
n = len(alist)
# gap = 4
gap = n // 2
print(alist)
print("-"*10)
while gap>=1:
for i in range(gap, n):
print(i)
while i>=gap:
if alist[i] < alist[i-gap]:
alist[i], alist[i-gap] = alist[i-gap], alist[i]
i-=gap
else:
break
print(alist)
print("-"*10)
# 縮短步長
gap //= 2
if __name__=="__main__":
li = [54,26,93,17,77,31,44,55,20]
shell_sort(li)
#print(li)
# 最優: 依步長而定O(n^1.3)
# 最壞: O(n^2)
# 不穩定
```
### 快速排序(Quicksort)
> - 思想:
> - 將第一個值插入中間
> - 形成左邊比首值小, 右邊比首值大的效果
> - 兩邊再重複同樣操作, 直到剩一個值為止
> - 使用非常頻繁！最重要！
```python
#coding:utf-8
def quick_sort(alist, first, last):
""""""
if first >= last:
return
#n = len(alist)
#middle_value = alist[0]
#low = 0
#hight = n-1
middle_value = alist[first]
low = first
hight = last
print(middle_value, low, hight)
# 把大於mid的都丟到右邊, 小於的都丟左邊
while low < hight:
while low < hight and alist[hight] >= middle_value:
hight-=1
alist[low] = alist[hight]
print("-", alist)
while low < hight and alist[low] < middle_value:
low+=1
alist[hight] = alist[low]
print("|", alist)
# 退出時,low = hight
# 此時即分線, 放入middle
alist[low] = middle_value
print(alist)
# 接著使用嵌套方式重複執行
#quick_sort(alist[:low])
#quick_sort(alist[low+1:])
# 使用切片傳值返回的是一個新的列表(註),
# 不論怎麼操作都是對新列表操作而非原本的list > 白忙一場
# mid左邊
quick_sort(alist, first, low-1)
# mid右邊
quick_sort(alist, low+1, last)
if __name__ == "__main__":
li = [54,26,93,17,77,31,44,55,20]
quick_sort(li, 0, len(li)-1)
#print(li)
# 最優O(nlogn)
# while low<hight 全部都要跑一遍 > n
# 嵌套次數視數量而定, 每次切半 > log2n
# 最壞O(n^2)
# 不穩定
```
```python
# 註
In [1]: def test(a):
...: print(id(a))
...: test(a)
...:
In [2]: b = [1,2,3,4,5,6]
In [3]: test(b)
4437755336
4437755336
4437755336
...
# 切片返回的是新的指向
In [4]: def test(a):
...: print(id(a))
...: test(a[:3])
...:
In [5]: test(b)
4437755336
4440166280
4440138504
...
```
> - 最優O(nlogn)
> - while low<hight 全部都要跑一遍 > O(n)
> - 嵌套次數視數量而定, 每次切半 > log~2~n >O(logn)
> - 最壞O(n^2^)
> - 已經排序完成的話再執行的效果,
> - 每次middle_value都等於alist[0]
> - 這樣就要切n次, 故O(n^2^)
> - 不穩定
### 歸併排序(Merge Sort)
> - 全部拆成一個後再兩兩依序合併
```python
#coding:utf-8
def merge_sort(alist):
""""""
print(alist)
n = len(alist)
if n <= 1 :
return alist
# 開拆
mid = n // 2
left_li = merge_sort(alist[:mid])
right_li = merge_sort(alist[mid:])
# 開組
left_pointer = 0
right_pointer = 0
result = []
print(left_li, right_li)
while left_pointer < len(left_li) and right_pointer < len(right_li):
if left_li[left_pointer] <= right_li[right_pointer]: # = 穩定,避免交錯
result.append(left_li[left_pointer])
left_pointer+=1
else:
result.append(right_li[right_pointer])
right_pointer+=1
# 把剩下的收一收
# 切片超出範圍不會出錯, 會返回空列表(註)
result += left_li[left_pointer:]
result += right_li[right_pointer:]
print(result)
return result
if __name__ == "__main__":
li = [54,26,93,17,77,31,44,55,20]
merge_li = merge_sort(li)
#print(li)
#print(merge_li)
```
```python
# 註
In [1]: a = [1,2,3]
In [2]: a[4:]
Out[2]: []
```
> - 最優O(nlogn)
> - 每次都要兩兩比較 > n
> - 拆幾次就合幾次, 亦即合 log~2~n 次
> - 最壞O(nlogn)
> - 每次都切半, 沒有特殊切法
> - 快
> - 但是必須產生額外的空間來運行
> - 穩定
## 搜索
### 二分查找( Binary Search)
> - 每次切半, 視查找東西在一半之前還後,
> - 接著重複過程到找到或不能再切為止
> - 使用條件:
> - 有序 : 要知道在前還後
> - 支持下標索引(順序表) : 切半用
```python
#coding:utf-8
def binary_search(alist, item):
"""遞歸"""
n = len(alist)
mid = n // 2
if n > 0:
if alist[mid] == item:
return True
elif alist[mid] > item:
return binary_search(alist[:mid], item)
elif alist[mid] < item:
return binary_search(alist[mid+1:], item)
return False
def binary_search_2(alist, item):
"""非遞歸"""
n = len(alist)
first = 0
last = n-1
while first <= last:
mid = (first+last) // 2
if alist[mid] == item:
return mid
elif item < alist[mid]:
last = mid-1
elif alist[mid] < item:
first = mid+1
return False
if __name__ == "__main__":
li = [1,2,3,4,5,6]
#print(binary_search(li, 1))
#print(binary_search(li, 6))
#print(binary_search(li, 7))
print(binary_search_2(li, 1))
print(binary_search_2(li, 6))
print(binary_search_2(li, 7))
```
> - 最壞: 每次切半可切幾次 > log~2~n > O(logn)
> - 最優: 1 > 一切就中
> - vs.`for i in range(n)`
> - 最壞: O(n)
> - 最優: 1
## 樹
> - 特點：
> - 每個節點下的節點稱為『子節點』
> - 沒有父節點的節點稱為『根節點』
> - 每個子節點只有一個父節點
> - 術語：
> - 節點度: 幾個下級(B:3, G:2)
> - 樹度: 最大節點度(B>3)
> - 枝葉點(終端節點): 最下層的節點(K,J,F,L,O,P)
> - 節點層次: 1>A, 2>BC, 3>DEFGH...
> - 樹的深度(高度): 最大層次(5)
> - 種類:
> - 無序樹(自由樹)
> - 有序樹
> - 二叉樹: 樹的度為2
> - 完全二叉樹: 除了最底層外，每層都達最大度
(假設有五層, 1>2>4>8>n)
> - 滿二叉樹: 所有層都滿(1>2>4>8>16)
> - 平衡二叉樹: 子樹高度差不大於1
> - 排序二叉樹: 類似二分查找邏輯
> - 霍夫曼樹:
> - B樹
>
> - 存儲:
> - 順序存儲
> 
> - 鏈式存儲(常用)
### 二叉樹
```python
#coding:utf-8
class Node(object):
def __init__(self, elem):
self.elem = elem
self.lchild = None
self.rchild = None
class Tree(object):
def __init__(self):
self.root = None
def add(self, elem):
node = Node(elem)
if self.root is None:
self.root = node
return
queue = [self.root]
# 註1
while queue:
cur_node = queue.pop(0)
if cur_node.lchild == None:
cur_node.lchild = node
return
else:
queue.append(cur_node.lchild)
if cur_node.rchild == None:
cur_node.rchild = node
return
else:
queue.append(cur_node.rchild)
def breadth_travel(self):
"""廣度遍歷(層次遍歷)"""
if self.root == None:
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
print(cur_node.elem, end="")
if cur_node.lchild is not None:
queue.append(cur_node.lchild)
if cur_node.rchild is not None:
queue.append(cur_node.rchild)
def preorder(self, root):
"""先序遍歷(根左右)"""
if root is None:
return
print(root.elem, end="")
self.preorder(root.lchild)
self.preorder(root.rchild)
def inorder(self, root):
"""中序遍歷(左根右)"""
if root is None:
return
self.inorder(root.lchild)
print(root.elem, end="")
self.inorder(root.rchild)
def postorder(self, root):
"""後序遍歷(左右根)"""
if root is None:
return
self.postorder(root.lchild)
self.postorder(root.rchild)
print(root.elem, end="")
if __name__ == "__main__":
tree = Tree()
tree.add(0)
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
tree.add(6)
tree.add(7)
tree.add(8)
tree.add(9)
tree.breadth_travel()
print(" ")
tree.preorder(tree.root)
print(" ")
tree.inorder(tree.root)
print(" ")
tree.postorder(tree.root)
print(" ")
```
```python
# 註1
In [1]: bool([])
Out[1]: False
In [3]: bool([None])
Out[3]: True # 即使[]元素僅為None, 判斷一樣事True
```
Sign in with Wallet
Connect another wallet