心智圖資源庫 資料結構
資料結構，整理了資料結構基本概念主要內容和邏輯結構，有助於知識點的理解與記憶，適用於考試複習！
01資料結構
資料結構-演算法心智圖
資料結構排序演算法
資料結構查找演算法
資料結構與演算法
資料結構實作與演算法解析
資料結構-堆疊與佇列
資料結構心智圖
資料結構-線性表
資料結構2（更新中
資料結構
緒論
資料結構基本概念
數據
資料元素、資料項
舉例概括
資料對象、資料結構
資料類型、抽象資料類型
三要素
邏輯結構
線性結構
集合
樹狀結構
圖結構(網狀結構)
非線性結構
物理結構(儲存結構)
順序存儲
鍊式儲存
索引存儲
散列存儲
非順序存儲
數據的運算
演算法
基本概念
什麼是演算法
程式＝資料結構＋演算法
資料結構是要處理的訊息
演算法是處理資訊的步驟
演算法的五個特性
有窮性
有窮時間內能執行完
演算法是有窮的
程序可以是無窮的
確定性
相同輸入只會產生相同輸出
可行性
可以用現有的基本操作實現演算法
輸入
丟給演算法處理的數據
輸出
演算法處理的結果
「好」演算法的特質
正確性
能正確解決問題
可讀性
演算法的描述要讓其他人也看得懂
健壯性
演算法能處理一些異常狀況
高效率與低儲存量需求
即演算法執行省時、省內存
時間複雜度低、空間複雜度低
演算法效率的度量
時間複雜度
如何計算
①找到一個基本操作（最深層循環）
②分析該基本運算的執行次數x與問題規模n的關係x＝f（n）
③x的數量級O( x)就是演算法時間複雜度T(n)
常用技巧
加法規則：O( f( n))× O( g( n))＝O( max( f( n), g( n)))
乘法規則：O( f( n))× O( g( n))＝O( ( f( n)× g( n)))
“常對冪指階”
三種複雜度
最壞時間複雜度：考慮輸入資料「最壞」的情況
平均時間複雜度：考慮所有輸入資料都等機率出現的情況
最好時間複雜度：考慮輸入資料“最好的情況”
空間複雜度
記憶體開銷
①儲存變數
②遞迴調用
普通程式
①找到所佔空間大小和問題規模相關的變數
②分析所佔空間x與問題規模n的關係x＝f(n)
③x的數量級O( x)就是演算法空間複雜度S(n)
遞迴程式
①找到遞歸呼叫的深度x與問題規模n的關係x＝f(n)
②x的數量級O( x)就是演算法空間複雜度
註：有的演算法各層函數所需儲存空間不同，分析方法略有區別
加法規則：同時間複雜度
乘法規則：同時間複雜度
第一章
線性表
線性表的定義和基本操作
定義
線性表具有相同資料型態的n(n＞＝0)個資料元素的有限序列，其中n為表長，當n＝0時 線性表是一個空表。
位元序
位序從1開始數組下標從0開始
表長、空表
表頭元素和表尾元素
直接前驅和直接後繼
除第一個元素外，每個元素都有且僅有一個直接前驅； 除最後一個元素，每個元素有且僅有一個直接後繼。
值得注意的特性
資料元素同類型、有限、有序
基本操作
創銷、增刪改查
判空、判長、列印輸出(自訂函數功能)
其他值得注意的點
理解什麼時候要傳入參數的引用“＆”
函數命名要有可讀性
順序表(順序儲存)
定義(儲存結構)
邏輯上相鄰的資料元素物理上也相鄰
實現方式
靜態分配記憶體
使用“靜態數組”實現，定義最大存儲數量
大小一旦確定就無法改變
動態分配記憶體
使用“動態數組”，結構體中定義data指標透過malloc動態分配記憶體(存在堆區)
L.data＝(ElemType *)malloc(sizeof(ElemType)*size)
順序表存滿時，可再用malloc動態拓展順序表的最大容量
需要將資料元素複製到新的儲存區域，並用free函數釋放原始區域
用到的頭#include <stdlib.h>
特點
隨機訪問
能在O(1)時間內找到第i個元素
儲存密度高
拓展容量不方便
插入、刪除資料元素不方便
操作功能
插入
時間複雜度 最好O(1)最壞O(n)平均O(n)
刪除
程式碼要點
程式碼要注意位序i和下標的區別
演算法要有健壯性，注意判斷i的合法性
引用的使用
尋找
按位查找
動態分配記憶體情況下 時間複雜度O(1)
按值查找
靜態分配時間複雜度 最好O(1)最壞O(n)平均O(n)
靜態動態都一樣
鍊錶
頭指針
佇列
1.可以用陣列和鍊錶
循環鍊錶和循環數組
頭尾指針，下標
第二章
Wondershare EdrawMind
