邏輯結(jié)構(gòu) & 物理結(jié)構(gòu)
一般從兩個角度對數(shù)據(jù)進行描述，一個是邏輯結(jié)構(gòu)，一個是物理結(jié)構(gòu)
邏輯結(jié)構(gòu)：描述的是數(shù)據(jù)與數(shù)據(jù)之間的邏輯關(guān)系
物理結(jié)構(gòu)：描述的是數(shù)據(jù)在內(nèi)存中存儲的形式
邏輯結(jié)構(gòu)
-
線性結(jié)構(gòu)：數(shù)據(jù)之間的關(guān)系是一對一的，所有符合一對一的都是線性結(jié)構(gòu)
數(shù)組、鏈表 是線性結(jié)構(gòu)
字符串是 特殊線性結(jié)構(gòu)，存儲內(nèi)容只能是字符串
隊列、棧是特殊線性結(jié)構(gòu)，區(qū)別在于讀取方式
- 隊列是先進先出，即FIFO
- 棧是先進后出，即FILO
集合結(jié)構(gòu)：集合中的所有元素除了同屬于一個集合外，他們之間沒有其他關(guān)系-
樹形結(jié)構(gòu)：數(shù)據(jù)之間的存在一對多的層次關(guān)系
樹形結(jié)構(gòu) 圖形結(jié)構(gòu)：數(shù)據(jù)之間存在多對多的關(guān)系
物理結(jié)構(gòu)
數(shù)據(jù)的物理結(jié)構(gòu)就是數(shù)據(jù)存儲在磁盤中的方式，這里的磁盤指的是計算機的內(nèi)存，主要研究的是數(shù)據(jù)結(jié)構(gòu)在計算機中的實現(xiàn)方式，包括數(shù)據(jù)結(jié)構(gòu)中的元素的表示及元素間關(guān)系的表示，有以下兩種
順序存儲結(jié)構(gòu)： 邏輯上相鄰的數(shù)據(jù)元素，物理存儲位置也相鄰，順序表的存儲空間需要預(yù)先分配，且存儲空間是一段的連續(xù)的內(nèi)存，順序存儲結(jié)構(gòu)如下圖所示
- 優(yōu)點
方法簡單，易實現(xiàn)，因為在各種高級語言中都有數(shù)組
順序存儲結(jié)構(gòu)具有隨機訪問的特點 - 缺點
順序表中做插入/刪除 操作時，需要進行大量的數(shù)據(jù)移動，因此對n較大的順序表效率低
需要預(yù)先分配空間，如果空間預(yù)估過大，會導(dǎo)致順序表后面的大部分空間閑置，浪費內(nèi)存，如果預(yù)估過小，又會造成溢出
鏈式存儲結(jié)構(gòu) ：邏輯上相鄰的數(shù)據(jù)元素，其物理存儲位置不一定相鄰，它使用指針實現(xiàn)元素之間的邏輯關(guān)系，且鏈表的存儲空間是動態(tài)分布的，鏈式存儲結(jié)構(gòu)如下圖所示
- 優(yōu)點：
不需要提前開辟一段連續(xù)的空間，其空間是動態(tài)分配的
插入、刪除操作方便，只需要改變指針的指向，不需要移動數(shù)據(jù)元素 - 缺點
鏈表不能隨機存取元素，如果在鏈式存儲中遍歷，需要遍歷所有的元素
