一、基本概念和術(shù)語(yǔ)
1.數(shù)據(jù)
數(shù)據(jù)是描述客觀事物的符號(hào),是計(jì)算機(jī)可以操作的對(duì)象,是能被計(jì)算機(jī)識(shí)別,并輸入到計(jì)算機(jī)處理的符號(hào)集合。
(數(shù)據(jù)不僅僅包括整型、實(shí)型等數(shù)值型,還有字符、聲音、圖像、視頻等非數(shù)值類型)
2.數(shù)據(jù)元素
數(shù)據(jù)元素是組成數(shù)據(jù)的、有一定意義的基本單位,在計(jì)算機(jī)中通常作為整體處理,也稱為記錄(元組、結(jié)點(diǎn)、頂點(diǎn))。
3.數(shù)據(jù)項(xiàng)(屬性、字段)
一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。
數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。
4.數(shù)據(jù)對(duì)象
數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的子集。
5.數(shù)據(jù)結(jié)構(gòu)
在現(xiàn)實(shí)世界中,不同數(shù)據(jù)元素之間不是獨(dú)立的,而是存在特定的關(guān)系,這些關(guān)系稱為結(jié)構(gòu)。
數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
數(shù)據(jù)結(jié)構(gòu)包括三方面的內(nèi)容:邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是密不可分的兩個(gè)方面,一個(gè)算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu),而算法的實(shí)現(xiàn)依賴于所采用的存儲(chǔ)結(jié)構(gòu)。
二、邏輯結(jié)構(gòu)和物理結(jié)構(gòu)(存儲(chǔ)結(jié)構(gòu))
1.邏輯結(jié)構(gòu)
1)定義
邏輯結(jié)構(gòu)是指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間相互關(guān)系(邏輯關(guān)系),即從邏輯關(guān)系上描述數(shù)據(jù)。它與數(shù)據(jù)的存儲(chǔ)無關(guān),是獨(dú)立于計(jì)算機(jī)存儲(chǔ)器的。
2)分類(線性結(jié)構(gòu)和非線性結(jié)構(gòu))
根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特征,通常有下列4類基本結(jié)構(gòu),復(fù)雜程度依次遞進(jìn)。
①集合:結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個(gè)集合外,沒有其他的關(guān)系。
②線性結(jié)構(gòu):線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對(duì)一的關(guān)系。
③樹形結(jié)構(gòu):樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對(duì)多的關(guān)系。
④圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu):結(jié)構(gòu)中的元素之間是多對(duì)多的關(guān)系。
2.物理結(jié)構(gòu)(存儲(chǔ)結(jié)構(gòu))
1)定義
數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)方式。又稱存儲(chǔ)結(jié)構(gòu)。
它研究的是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)方法,包括數(shù)據(jù)元素的表示和元素之間的關(guān)系。
數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)形式主要有兩種:順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)
2)順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)
①順序存儲(chǔ)結(jié)構(gòu)
是利用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯順序。
順序存儲(chǔ)結(jié)構(gòu)是把數(shù)據(jù)元素放在地址連續(xù)的存儲(chǔ)單元中,程序設(shè)計(jì)中使用數(shù)組類型來實(shí)現(xiàn)。(邏輯相鄰物理相鄰)
②鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
利用結(jié)點(diǎn)中指針來表示數(shù)據(jù)元素之間的關(guān)系。
把數(shù)據(jù)元素存儲(chǔ)在任意的存儲(chǔ)單元里,這組存儲(chǔ)單元可以是連續(xù)的,也可以是連續(xù)的,程序設(shè)計(jì)中使用指針類型來實(shí)現(xiàn)。(邏輯相鄰物理不一定相鄰)
3)其他存儲(chǔ)方式
索引存儲(chǔ):類似于目錄,以后可以聯(lián)系操作系統(tǒng)的文件系統(tǒng)章節(jié)來理解。
散列存儲(chǔ):通過關(guān)鍵字直接計(jì)算出元素的物理地址。
三、抽象數(shù)據(jù)類型
定義
①數(shù)據(jù)類型:是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱。
例如:C語(yǔ)言中數(shù)據(jù)類型分為基本類型和構(gòu)造類型
基本類型:整型、浮點(diǎn)型、字符型等
構(gòu)造類型:數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義類型等
②抽象數(shù)據(jù)類型(abstract data type,ADT):是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作。
延伸閱讀:
四、線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)
用一組任意的存儲(chǔ)單元(可能不連續(xù))存儲(chǔ)線性表的數(shù)據(jù)元素。
在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,每個(gè)存儲(chǔ)結(jié)點(diǎn)不僅包含數(shù)據(jù)元素本身的信息,還必須包含每個(gè)元素之間邏輯關(guān)系的信息,即包含直接后繼結(jié)點(diǎn)的地址信息(指針域)。
邏輯順序與物理順序有可能不一致;屬順序存取的存儲(chǔ)結(jié)構(gòu),即存取每個(gè)元素必須從名列前茅個(gè)元素開始遍歷,直到找到需要訪問的元素,所以所花時(shí)間不一定相等。