title: "數(shù)據(jù)結(jié)構基本概念"
date: 2015-05-02 23:48:15
categories: 數(shù)據(jù)結(jié)構
tags:
數(shù)據(jù)
- 描述客觀事物的符號
- 可以輸入到計算機
- 能夠被計算機程序處理
數(shù)據(jù)元素
- 組成數(shù)據(jù)鄙信、有一定意義膘盖、也被稱為記錄
- 比如：人類中人就是數(shù)據(jù)元素
數(shù)據(jù)項
- 一個數(shù)據(jù)元素可以由很多數(shù)據(jù)項組成
- 是不分割的最小單元
- 比如：人是數(shù)據(jù)元素，眼睛永丝、鼻子西采、嘴...是數(shù)據(jù)項濒蒋。
數(shù)據(jù)對象
- 性質(zhì)相同數(shù)據(jù)元素的集合
- 通常將數(shù)據(jù)對象稱為
數(shù)據(jù)
數(shù)據(jù)結(jié)構 = 數(shù)據(jù)+關系
邏輯結(jié)構 ( 各個元素之間的關系 )
- 集合： 平等
- 線性： 一對一
- 樹形：一對多
- 圖形：多對多
physical
邏輯結(jié)構為了解決具體問題，選擇一個合適的數(shù)據(jù)結(jié)構表示數(shù)據(jù)元素之間的邏輯關系。
物理結(jié)構
邏輯結(jié)構在計算機中的存儲形式
-
順序存儲：
- 需要提前申請大片內(nèi)存蹦掐。
- 數(shù)據(jù)元素存放在地址連續(xù)的存儲單元里。
- 數(shù)據(jù)間
邏輯關系=物理關系 - 物理節(jié)點
只存數(shù)據(jù)僵闯。 - 產(chǎn)生內(nèi)存內(nèi)部碎片卧抗。(內(nèi)部碎片就是已經(jīng)被分配出去（能明確指出屬于哪個進程）卻不能被利用的內(nèi)存空間)。
- 數(shù)據(jù)的插入/刪除
復雜鳖粟， 查詢快社裆。
-
鏈式存儲：
- 數(shù)據(jù)間
邏輯關系!=物理關系。 - 數(shù)據(jù)之間通過
指針向图，指向下一個元素的地址泳秀。 - 物理結(jié)點存
數(shù)據(jù) + 指針 - 產(chǎn)生外部碎片标沪。（外部碎片指的是還沒有被分配出去（不屬于任何進程），但由于太小了無法分配給申請內(nèi)存空間的新進程的內(nèi)存空閑區(qū)域嗜傅。）
- 數(shù)據(jù)的插入/刪除快谨娜，查詢慢。
- memcached： 為了避免外部碎片產(chǎn)生磺陡，內(nèi)存的分配規(guī)則是：slab+chunk 把大小空間分開趴梢，slab是聚合，chunk是大小币他。
- 數(shù)據(jù)間
總結(jié)
- 邏輯結(jié)構
面向問題 - 物理結(jié)構
面向計算機 - 最終
目的是 將數(shù)據(jù)+邏輯關系存到PC的內(nèi)存中坞靶。
