計(jì)算機(jī)軟件技術(shù)基礎(chǔ)(郵電)

1、1.1數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念1.1.1數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容及其重要性用計(jì)算機(jī)處理問(wèn)題的步驟用計(jì)算機(jī)處理問(wèn)題的步驟 首先需要把客觀對(duì)象抽象為某種形式的數(shù)據(jù)首先需要把客觀對(duì)象抽象為某種形式的數(shù)據(jù) 然后設(shè)計(jì)對(duì)這些數(shù)據(jù)進(jìn)行處理的算法，由計(jì)算機(jī)執(zhí)然后設(shè)計(jì)對(duì)這些數(shù)據(jù)進(jìn)行處理的算法，由計(jì)算機(jī)執(zhí)行設(shè)計(jì)好的算法，行設(shè)計(jì)好的算法， 用某種計(jì)算機(jī)語(yǔ)言（例如：用某種計(jì)算機(jī)語(yǔ)言（例如：C C語(yǔ)言）描述交計(jì)算機(jī)處語(yǔ)言）描述交計(jì)算機(jī)處理。理。數(shù)據(jù)結(jié)構(gòu)的重要性數(shù)據(jù)結(jié)構(gòu)的重要性 程序程序= =數(shù)據(jù)結(jié)構(gòu)算法數(shù)據(jù)結(jié)構(gòu)算法數(shù)據(jù)結(jié)構(gòu)的學(xué)科地位數(shù)據(jù)結(jié)構(gòu)的學(xué)科地位數(shù)學(xué)數(shù)學(xué)代數(shù)系統(tǒng)代數(shù)系統(tǒng)編碼理論編碼理論數(shù)據(jù)類型數(shù)據(jù)類型算子關(guān)系

2、算子關(guān)系數(shù)據(jù)表示數(shù)據(jù)表示數(shù)據(jù)運(yùn)算數(shù)據(jù)運(yùn)算數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)存取數(shù)據(jù)存取機(jī)器組織機(jī)器組織存儲(chǔ)裝置存儲(chǔ)裝置硬件硬件（計(jì)算機(jī)系統(tǒng)設(shè)計(jì)）（計(jì)算機(jī)系統(tǒng)設(shè)計(jì)）文件系統(tǒng)文件系統(tǒng)數(shù)據(jù)組織數(shù)據(jù)組織信息檢索信息檢索軟件軟件（計(jì)算機(jī)程序設(shè)計(jì)）（計(jì)算機(jī)程序設(shè)計(jì)）19681968年美國(guó)的唐納德年美國(guó)的唐納德克努特（克努特（Donald E. Donald E. KunthKunth）教授出版了其名著）教授出版了其名著計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第一卷第一卷基本算法基本算法，首次系統(tǒng)地闡述了，首次系統(tǒng)地闡述了數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容，即：的主要內(nèi)容，即： 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)

3、結(jié)構(gòu) 對(duì)對(duì)數(shù)據(jù)的操作數(shù)據(jù)的操作1.1.2數(shù)據(jù)結(jié)構(gòu)中的基本概念和術(shù)語(yǔ)數(shù)據(jù)數(shù)據(jù) 非數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)（字符、指令等不表示數(shù)值的代碼（字符、指令等不表示數(shù)值的代碼) ) 數(shù)值性數(shù)據(jù)數(shù)值性數(shù)據(jù)（整數(shù)、實(shí)數(shù)、復(fù)數(shù)（整數(shù)、實(shí)數(shù)、復(fù)數(shù)) )數(shù)據(jù)元素?cái)?shù)據(jù)元素(data element)是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。 數(shù)據(jù)項(xiàng)（數(shù)據(jù)項(xiàng)（data item） 數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象(data object) 數(shù)據(jù)的子集。具有相同性質(zhì)的數(shù)據(jù)成員（數(shù)據(jù)元素）的集合。 整數(shù)數(shù)據(jù)對(duì)象 N = 0, 1, 2, ， 學(xué)生數(shù)據(jù)對(duì)象 英文字母數(shù)據(jù)對(duì)象 LETT

4、ER A ， B,Z學(xué)號(hào)學(xué)號(hào)姓名姓名數(shù)學(xué)數(shù)學(xué)計(jì)算機(jī)計(jì)算機(jī)外語(yǔ)外語(yǔ)021001王強(qiáng)王強(qiáng)879096021002李一龍李一龍699189021003張映月張映月877971021004何一端何一端848868一個(gè)若干值的集合以及在這些值上定義的一組操作的總稱。 結(jié)構(gòu)結(jié)構(gòu)(structure)(structure) 數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)結(jié)構(gòu)。 四類基本結(jié)構(gòu)四類基本結(jié)構(gòu) 集合集合 結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的關(guān)系外，別無(wú)其它關(guān)系。如下圖所示：集合 線性結(jié)構(gòu)線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系（結(jié)點(diǎn)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系（結(jié)點(diǎn)之間的連線表示關(guān)系）。例

5、如：學(xué)生名單。如圖所示：之間的連線表示關(guān)系）。例如：學(xué)生名單。如圖所示：樹形結(jié)構(gòu)樹形結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。只能結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。只能與上一層的一個(gè)結(jié)點(diǎn)相關(guān)，可與下一層的多個(gè)結(jié)點(diǎn)相關(guān)。與上一層的一個(gè)結(jié)點(diǎn)相關(guān)，可與下一層的多個(gè)結(jié)點(diǎn)相關(guān)。例如：博弈。例如：博弈。 如圖所示：如圖所示：樹：樹：圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系。圖中任結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系。圖中任一結(jié)點(diǎn)都可與多個(gè)其它結(jié)點(diǎn)關(guān)聯(lián)，即圖的結(jié)點(diǎn)之間的關(guān)系一結(jié)點(diǎn)都可與多個(gè)其它結(jié)點(diǎn)關(guān)聯(lián)，即圖的結(jié)點(diǎn)之間的關(guān)系是任意的。樹是圖的一種特例。是任意的。

6、樹是圖的一種特例。 例如：交通規(guī)劃；郵遞員問(wèn)題。例如：交通規(guī)劃；郵遞員問(wèn)題。 如下圖所示：如下圖所示：圖二、基本概念 數(shù)據(jù)結(jié)構(gòu)(data structure)： 相互之間存在著一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。學(xué)號(hào)學(xué)號(hào)姓名姓名語(yǔ)文語(yǔ)文數(shù)學(xué)數(shù)學(xué)物理物理021001王強(qiáng)王強(qiáng)879096021002李一龍李一龍699189021003張映月張映月877971021004何一端何一端848868 數(shù)據(jù)結(jié)構(gòu)的分類 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 邏輯結(jié)構(gòu)就是數(shù)據(jù)元素之間的邏輯關(guān)系。 線性結(jié)構(gòu)線性結(jié)構(gòu) 數(shù)據(jù)邏輯結(jié)構(gòu)中的一類,它的特征是若結(jié)構(gòu)為非空集,則該結(jié)構(gòu)有且只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn),并且所有結(jié)點(diǎn)都最多只有一

7、個(gè)直接前趨和一個(gè)直接后繼。線性表就是一個(gè)典型的線性結(jié)構(gòu)。 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 非線性結(jié)構(gòu)的邏輯特征是該結(jié)構(gòu)中一個(gè)數(shù)據(jù)元素可能有多個(gè)直接前趨和直接后繼,非線性結(jié)構(gòu)中最普遍的就是圖的結(jié)構(gòu)。數(shù)據(jù)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) ( (物理結(jié)構(gòu)物理結(jié)構(gòu)) ) 反映數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)方法就是數(shù)據(jù)的物理結(jié)構(gòu)反映數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)方法就是數(shù)據(jù)的物理結(jié)構(gòu)。有時(shí)也稱為存儲(chǔ)結(jié)構(gòu)。它是邏輯結(jié)構(gòu)在存儲(chǔ)器里的實(shí)現(xiàn)。有時(shí)也稱為存儲(chǔ)結(jié)構(gòu)。它是邏輯結(jié)構(gòu)在存儲(chǔ)器里的實(shí)現(xiàn)。 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的四種基本存儲(chǔ)方式 順序存儲(chǔ)（Sequential Storage StructureSequential Storage Structure

8、） 該方式把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理位置上相鄰的該方式把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，數(shù)據(jù)元素間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)存儲(chǔ)單元里，數(shù)據(jù)元素間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。體現(xiàn)。 數(shù)組數(shù)組內(nèi)存內(nèi)存 鏈?zhǔn)酱鎯?chǔ) (Linked Storage Structure)(Linked Storage Structure)該方法不要求邏輯上相鄰的數(shù)據(jù)元素在物理位置上該方法不要求邏輯上相鄰的數(shù)據(jù)元素在物理位置上亦相鄰，數(shù)據(jù)元素間的邏輯關(guān)系由附加的指針字段表示。亦相鄰，數(shù)據(jù)元素間的邏輯關(guān)系由附加的指針字段表示。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?？梢詫⑽锢砩嫌纱说?/p>

9、到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?？梢詫⑽锢砩喜贿B續(xù)的數(shù)據(jù)元素在邏輯上相鄰。例：鏈表。不連續(xù)的數(shù)據(jù)元素在邏輯上相鄰。例：鏈表。 數(shù)據(jù)指針數(shù)據(jù)指針數(shù)據(jù)指針數(shù)據(jù)指針數(shù)據(jù)指針數(shù)據(jù)指針數(shù)據(jù)指針數(shù)據(jù)指針數(shù)組數(shù)組內(nèi)存內(nèi)存 索引存儲(chǔ) （ Index Structure）該方法通常在儲(chǔ)存數(shù)據(jù)元素信息的同時(shí)，還建立附加的索該方法通常在儲(chǔ)存數(shù)據(jù)元素信息的同時(shí)，還建立附加的索引表。索引表由若干索引項(xiàng)組成。例如：圖書檢索（按書名、引表。索引表由若干索引項(xiàng)組成。例如：圖書檢索（按書名、作者、出版社、分類號(hào)索引）。作者、出版社、分類號(hào)索引）。 索引項(xiàng)的一般形式索引項(xiàng)的一般形式 (1) (1) 關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的

10、那些數(shù)據(jù)項(xiàng)。關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的那些數(shù)據(jù)項(xiàng)。 (2) (2) 稠密索引中索引項(xiàng)的地址指示數(shù)據(jù)元素所在的存儲(chǔ)位置；稠密索引中索引項(xiàng)的地址指示數(shù)據(jù)元素所在的存儲(chǔ)位置； (3) (3) 稀疏索引中索引項(xiàng)的地址指示一組結(jié)點(diǎn)的起始存儲(chǔ)位置。稀疏索引中索引項(xiàng)的地址指示一組結(jié)點(diǎn)的起始存儲(chǔ)位置。關(guān)鍵字：地址關(guān)鍵字：地址若每個(gè)數(shù)據(jù)元素在索引表中都有一個(gè)索引項(xiàng)若每個(gè)數(shù)據(jù)元素在索引表中都有一個(gè)索引項(xiàng),則該索引表稱之則該索引表稱之為稠密索引（為稠密索引（Dense Index）。）。若一組數(shù)據(jù)元素在索引表中只對(duì)應(yīng)一個(gè)索引項(xiàng)若一組數(shù)據(jù)元素在索引表中只對(duì)應(yīng)一個(gè)索引項(xiàng),則該索引表稱則該索引表稱為稀疏索引（為稀疏

11、索引（Spare Index） 。散列存儲(chǔ)方法（Structure） 根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。（哈希函數(shù)（算法）址。（哈希函數(shù)（算法）哈希函數(shù)哈希函數(shù)地址地址主存儲(chǔ)器主存儲(chǔ)器地址地址對(duì)數(shù)據(jù)的操作（運(yùn)算）對(duì)數(shù)據(jù)的操作（運(yùn)算） 數(shù)據(jù)結(jié)構(gòu)除邏輯結(jié)構(gòu)和物理結(jié)構(gòu)外，第三個(gè)內(nèi)容就是數(shù)據(jù)結(jié)構(gòu)除邏輯結(jié)構(gòu)和物理結(jié)構(gòu)外，第三個(gè)內(nèi)容就是數(shù)據(jù)的操作，例如表的使用和維護(hù)（排序、查找、增加、數(shù)據(jù)的操作，例如表的使用和維護(hù)（排序、查找、增加、修改、刪除等）。修改、刪除等）。在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的操作涉及比加減乘除算術(shù)運(yùn)在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的操作涉及比加減乘除算

12、術(shù)運(yùn)算更廣義的運(yùn)算，這些運(yùn)算常常涉及算法問(wèn)題。高效率算更廣義的運(yùn)算，這些運(yùn)算常常涉及算法問(wèn)題。高效率地存儲(chǔ)數(shù)據(jù)和管理數(shù)據(jù)需要分析和選擇合適的算法。地存儲(chǔ)數(shù)據(jù)和管理數(shù)據(jù)需要分析和選擇合適的算法。 算法算法的定義（算法的定義（lgorithmlgorithm ） 一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列。算序列。算法的算法的特性特性輸入輸入: :有0個(gè)或多個(gè)輸入輸出輸出: :有一個(gè)或多個(gè)輸出(處理結(jié)果)確定性確定性: :每步定義都是確切、無(wú)歧義的有窮性有窮性: :算法應(yīng)在執(zhí)行有窮步后結(jié)束有效性有效性: :每一條運(yùn)算應(yīng)足夠

13、基本算法的分析算法的分析( (lgorithmlgorithm nalysisnalysis) ) 算法分析(algorithm analysis)是指對(duì)算法的執(zhí)行時(shí)間和所需內(nèi)存空間的估算。同一問(wèn)題的求解往往可以使用不同的算法,通過(guò)算法分析,可以比較兩個(gè)算法的效率高低。 算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度 執(zhí)行一個(gè)算法所花費(fèi)的時(shí)間代價(jià)執(zhí)行一個(gè)算法所花費(fèi)的時(shí)間代價(jià)。 當(dāng)要解決的問(wèn)題的規(guī)模以某種單位由當(dāng)要解決的問(wèn)題的規(guī)模以某種單位由1 1增至增至n n時(shí)，對(duì)應(yīng)算時(shí)，對(duì)應(yīng)算法所耗費(fèi)的時(shí)間也以某種單位由法所耗費(fèi)的時(shí)間也以某種單位由f(1)f(1)增至增至f(n)f(n)。此時(shí)稱該算。此時(shí)稱該算法的時(shí)間復(fù)

14、雜度為法的時(shí)間復(fù)雜度為f(n)f(n)。 問(wèn)題的規(guī)模問(wèn)題的規(guī)模例：例：順序查找算法的關(guān)鍵操作是順序查找算法的關(guān)鍵操作是ai ai 的值與給定值做比較。的值與給定值做比較。 順序查找成功的平均比較次數(shù)為（設(shè)：有個(gè)數(shù)據(jù)）：順序查找成功的平均比較次數(shù)為（設(shè)：有個(gè)數(shù)據(jù)）：2111ninni2/ ) 1(1)2() 1(1)(nnnnnnf時(shí)間代價(jià)（最壞、最好和平均情況） 最好情況下的時(shí)間代價(jià)。 在平均情況下的時(shí)間代價(jià)。 最壞情況下的時(shí)間代價(jià)，主要采用大 表示法來(lái)描述。大大O表示法表示法O(n)f(n)T(n) 一般提法一般提法 當(dāng)且僅當(dāng)存在正整數(shù)c和n0,使得T(n) cf (n)對(duì)所有的nn0成立,

15、則稱該算法的漸進(jìn)時(shí)間復(fù)雜度為T( n ) = O(f( n )。這時(shí)也稱該算法的時(shí)間代價(jià)的增長(zhǎng)率為f(n)，意味著當(dāng)充分大時(shí)，該算法的復(fù)雜度不大于f(n)的一個(gè)常數(shù)倍。 基本思想基本思想 關(guān)注復(fù)雜性的數(shù)量級(jí)，而忽略數(shù)量級(jí)的系數(shù)，這樣在分析算法的復(fù)雜度時(shí)，可以忽略個(gè)別語(yǔ)句的執(zhí)行時(shí)間，重點(diǎn)分析算法的主要代價(jià)。假設(shè)：f(n) = 2n3 +2n2 + 2n + 1， 當(dāng)n充分大時(shí)： T( n ) = O(n3 )算法的空間復(fù)雜度算法的空間復(fù)雜度執(zhí)行一個(gè)算法所需占用的空間代價(jià)。當(dāng)要解決的問(wèn)題的規(guī)模以某種單位由1增至n時(shí)，對(duì)應(yīng)算法所需占用的空間也以某種單位由g(1)增至g(n)。此時(shí)稱該算法的空間復(fù)雜度

16、為g(n)。設(shè)S (n) 是算法的漸進(jìn)空間復(fù)雜度，在最壞情況下它可以表示為實(shí)例特性n的某個(gè)函數(shù)f (n)的數(shù)量級(jí)，記為 ： 是為解決問(wèn)題所需要的輔助存儲(chǔ)空間。 只有完成同一功能的幾個(gè)算法之間才具有可比性 可以使用大O表示法來(lái)標(biāo)記這些空間復(fù)雜度,用以比較各算法的優(yōu)劣。 這樣在分析算法的空間復(fù)雜度時(shí)，可以忽略零星變量的存儲(chǔ)空間S (n) = O(f (n)常見(jiàn)的時(shí)間復(fù)雜度常見(jiàn)的時(shí)間復(fù)雜度常數(shù)階O(1)對(duì)數(shù)階O(log2n) 線性階O(n) 線性對(duì)數(shù)階O(nlog2n) 平方階O(n2) 立方階O(n3) k次方階O(nk) 指數(shù)階O(2n)1.1.3 數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型 數(shù)據(jù)結(jié)構(gòu) 數(shù)

17、據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)元素之間的邏輯關(guān)系。物理上的數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的存儲(chǔ)安排。數(shù)據(jù)類型數(shù)據(jù)以數(shù)據(jù)結(jié)構(gòu)分類，具有相同數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)屬同一類，數(shù)據(jù)類型表示某數(shù)據(jù)在數(shù)據(jù)分類中的歸屬，是數(shù)據(jù)的一種屬性。 一組性質(zhì)相同的值的集合, 以及定義于 這個(gè)值集合上的一組操作的總稱。雙精度型double基本數(shù)據(jù)類型整型int字符型單字符型char寬字符型w_char實(shí)型單精度型float邏輯型bool數(shù)組type 指針type * 空類型 void結(jié)構(gòu) struct聯(lián)合 union枚舉enum類 class數(shù)據(jù)類型非基本數(shù)據(jù)類型char int float double v

18、oid 字符型 整型 浮點(diǎn)型 雙精度型 無(wú)類型 數(shù)據(jù)類型 在高級(jí)程序設(shè)計(jì)語(yǔ)言中已實(shí)現(xiàn)了的，或非高級(jí)語(yǔ)言直接支持的數(shù)據(jù)結(jié)構(gòu)。 變量的數(shù)據(jù)類型 在程序設(shè)計(jì)語(yǔ)言中，一個(gè)變量的數(shù)據(jù)類型不僅規(guī)定了這個(gè)變量的取值范圍，而且定義了這個(gè)變量可用的操作。數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型 基本數(shù)據(jù)類型對(duì)應(yīng)于簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)內(nèi)部的構(gòu)成方式，它常常用一個(gè)結(jié)構(gòu)圖來(lái)描述非基本數(shù)據(jù)類型對(duì)應(yīng)于復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)有線性與非線性之分 在非線性數(shù)據(jù)結(jié)構(gòu)中又有層次與網(wǎng)狀之分。 由于數(shù)據(jù)類型是按照數(shù)據(jù)結(jié)構(gòu)劃分的，因此，一類數(shù)據(jù)結(jié)構(gòu)對(duì)應(yīng)著一種數(shù)據(jù)類型。數(shù)據(jù)類型有線性與非線性之分 數(shù)據(jù)類型按照該類型中的數(shù)據(jù)所呈現(xiàn)的結(jié)構(gòu)也有線性與

19、非線性之分，層次與網(wǎng)狀之分。一個(gè)數(shù)據(jù)變量，在高級(jí)語(yǔ)言中的類型說(shuō)明必須是該變量所具有的數(shù)據(jù)結(jié)構(gòu)所對(duì)應(yīng)的數(shù)據(jù)類型。 數(shù)組結(jié)構(gòu)的特點(diǎn) 數(shù)據(jù)元素的個(gè)數(shù)固定，它們之間的邏輯關(guān)系由數(shù)據(jù)元素的序號(hào)(或叫數(shù)組的下標(biāo))來(lái)體現(xiàn)。這些數(shù)據(jù)元素按照序號(hào)的先后順序一個(gè)挨一個(gè)地排列起來(lái)。 每一個(gè)數(shù)據(jù)元素具有相同的結(jié)構(gòu)(可以是簡(jiǎn)單結(jié)構(gòu)，也可以是復(fù)雜結(jié)構(gòu))，因而屬于同一個(gè)數(shù)據(jù)類型(相應(yīng)地是簡(jiǎn)單數(shù)據(jù)類型或構(gòu)造數(shù)據(jù)類型)。這種同一的數(shù)據(jù)類型稱為基類型。 所有的數(shù)據(jù)元素被依序安排在一片連續(xù)的存儲(chǔ)單元中。 記錄結(jié)構(gòu)的特點(diǎn) 與數(shù)組結(jié)構(gòu)一樣，成分?jǐn)?shù)據(jù)的個(gè)數(shù)固定。但成分?jǐn)?shù)據(jù)之間沒(méi)有自然序，它們處于平等地位。每一個(gè)成分?jǐn)?shù)據(jù)被稱為一個(gè)域并賦予域名。