1.數據結構
計算機存儲、組織數據的方式；
有特定關系的數據元素集合；
研究數據的邏輯結構、物理結構（真實存在）和對應的算法；
新結構仍保持原結構類型；
選擇更高的運行或存儲效率的數據結構。
邏輯結構——面向問題
物理結構面向計算機
基本目標是將數據及其邏輯關系存儲到計算機的內存中
（1）基本概念
數據——數據對象——數據元素（節點-鏈表中常出現）-整體處理——數據項（數據最小單位）
（2）邏輯結構
1.集合結構
2.線性結構
3.樹狀結構（層次結構）
4.圖形結構（網狀結構）
（3）物理結構
①順序存儲結構
把數據元素/節點存放在地址連續的存儲單元里
1.內存連續
2.相對于鏈式存儲結構每個元素占用空間少
②鏈式存儲結構
把數據元素/節點存放在任意的內存空間內，通過指針域來表示、連接
1.內存不連續
2.通過指針連接
③索引存儲結構
存儲數據同時，建立一個附加索引表（如通訊錄）
1.索引速度快
2.多了一張索引表，占用內存多
3.刪除數據文件時需及時更改索引表
④散列存儲結構
構造相應散列函數，由散列函數值來確定? 數據元素/節點? 存放的地址
1.存時需按對應關系存
2.取時也按對應關系取
2.算法
（1）概念
軟件 = 程序 + 文檔
程序 = 數據結構 + 算法
軟件 = 數據結構 + 算法 + 文檔
算法 = 對結點集合的運算和操作 + 控制結構
軟件、程序、算法——逐層包含關系
算法用來描述特定問題的求解步驟，指令有限序列，每個指令代表一個及以上操作
（2）五大特征
1.有窮性：
? ? ? ? 算法必須在有窮時間內完成
2.確切性：
? ? ? ? 指令必須有確切含義，不可有二義性。為True或False
3.可行性：
? ? ? ? 算法可行，算法中描述的操作都可實現
4.輸入性：
? ? ? ? 可輸入，以刻畫對象的初始情況
5.輸出性：
? ? ? ? 必須有一個或多個輸出
（3）描述
算法的描述樣式多樣化，常用有四種。
1.自然語言描述法：
? ? ? ? 最簡單的描述法
? ? ? ? 優點：簡單、便于理解
? ? ? ? 缺點：不夠嚴謹、易產生歧義。
2.算法框圖法：
? ? ? ? 使用算法描述工具描述算法（如程序流程圖）
? ? ? ? 特點：便于理解交流、簡潔明了
3.偽代碼語言描述法：
? ? ? ? 介于高級程序設計語言與自然語言之間
? ? ? ? 忽略了一些嚴格的語法規則與描述細節
? ? ? ? 比高級程序設計語言更容易描述和被人所理解
4.高級程序設計語言描述法：
? ? ? ? 可在計算機中執行的程序描述算法
? ? ? ? 優點：不用轉換，可直接編譯執行
? ? ? ? 缺點：比較難理解
所謂“程序”是指對所要解決問題的各個對象和處理規則的描述，或者說是數據結構和算法的描述，因此有人說“數據結構+算法 = 程序”。
程序可以不滿足算法的有窮性（如，操作系統）
（4）標準
衡量一個算法的四個標準：
1.正確性：
????????能夠正常運行，且得到正確答案
2.可讀性：
? ? ? ? 便于閱讀、理解和交流
3.健壯性：
? ? ? ? 當輸入不合法時，算法能做出相關處理。
4.時間效率高與、低存儲量需求：
? ? ? ? 執行時間少，耗內存少
（5）時間復雜度
????????一個算法的復雜性分析主要是對算法效率的分析，運行速度的時間效率，以及其運行時所需要占用的空間大小。
????????算法的時間復雜度是一個函數，它定性描述該算法的運行時間，時間復雜度常用 O 表述。
①概念
要想計算時間復雜度首先得找到該算法中的循環，算法中循環執行的次數就是算法的時間復雜度。
函數表達式：
? ? ? ? T(n) = O(f(n))
T(n) 問題規模的時間函數
n 代表的是問題的規模 輸入數據量的大小
O 時間數量級
f(n) 算法中可執行語句重復執行的次數
由此可得計算時間復雜度的一般規律(大O表示法)，如：N*N+N+10
- 如果有常數項將其置為
1。N*N+N+1- 去除表達式中所有加法常數。
N*N+N- 修改的表達式中 只保留最高階項，因為只有它才會對最終結果產生影響。
N*N- 如果最高階項系數存在且不是
1，則將其系數變為1，得到最后的表達式。N*N
計算冒泡排序的時間復雜度：
? ? ? ? Sn = [n*(a1+a2)]/2
3.順序表
每種結構都有存在的意義
線性表的特點：一對一，每個節點最多一個前驅和一個后繼，首尾節點特殊：首節點無前驅，尾節點無后繼。
邏輯結構：線性結構
物理結構：順序存儲結構
def show(buf: list[int]):
????????遍歷列表中的有效元素
last：
? ? ? ? 始終標記列表中最后一個有效元素下標
? ? ? ? 用global修飾
例：
????????練習：自己實現insert（）思想
?????????????????列表：buf = [1, 996, 520, 4, 5]
????????????????要求：第三個位置插入一個元素
def insert(buf, index, data):''':param buf:列表的首地址:param index:插入的位置:param data:給列表中插入的數據:return:'''for i in range(len(buf) - 1, index, -1):# 防止越界buf[i] = buf[i - 1]buf[index] = datadef show(buf):for i in range(len(buf)):print("buf[%s] = %s" % (i, buf[i]))if __name__ == '__main__':buf = [1, 520, 996, 4, 5]show(buf)insert(buf, 3, 888)show(buf)
last版本：
# 始終標記列表中最后一個有效元素的下標
last = 4def insert(buf, index, data):''':param buf:列表的首地址:param index:插入的位置:param data:給列表中插入的數據:return:'''global lastfor i in range(last, index - 1, -1): # last 0 index = 5 ；index + 1# 防止越界buf[i + 1] = buf[i]buf[index] = datalast = last + 1def show(buf):for i in range(last + 1):print("buf[%s] = %s" % (i, buf[i]))if __name__ == '__main__':buf = [1, 520, 996, 4, 5] + [0] * 16show(buf)insert(buf, 3, 888)show(buf)
)
)
)
