心智圖資源庫 資料結構
資料結構,整理了資料結構基本概念主要內容和邏輯結構,有助於知識點的理解與記憶,適用於考試複習!
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.可以用陣列和鍊錶
循環鍊錶和循環數組
頭尾指針,下標
第二章