軟考軟件設(shè)計(jì)師專題講義九：數(shù)據(jù)結(jié)構(gòu)概述

　　專題九：數(shù)據(jù)結(jié)構(gòu)知識(shí)

　　數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)軟件的一門(mén)基礎(chǔ)課程,計(jì)算機(jī)科學(xué)各個(gè)領(lǐng)域及有關(guān)的應(yīng)用軟件都要用到各種數(shù)據(jù)結(jié)構(gòu).語(yǔ)言編譯要使用棧、散列表及語(yǔ)法樹(shù);操作系統(tǒng)中用隊(duì)列、存儲(chǔ)管理表及目錄樹(shù)等;數(shù)據(jù)庫(kù)系統(tǒng)運(yùn)用線性表、多鏈表及索引樹(shù)等進(jìn)行數(shù)據(jù)管理;而在人工智能領(lǐng)域，依求解問(wèn)題性質(zhì)的差異將涉及到各種不同的數(shù)據(jù)結(jié)構(gòu)，如廣義表、集合、搜索樹(shù)及各種有向圖等等。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)目的是要熟悉一些最常用的數(shù)據(jù)結(jié)構(gòu)，明確數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，知道它們?cè)谟?jì)算機(jī)中的存儲(chǔ)表示，并結(jié)合各種典型應(yīng)用說(shuō)明它們?cè)谶M(jìn)行各種操作時(shí)的動(dòng)態(tài)性質(zhì)及實(shí)際的執(zhí)行算法，進(jìn)一步提高軟件計(jì)和編程水平。通過(guò)對(duì)不同存儲(chǔ)結(jié)構(gòu)和相應(yīng)算法的對(duì)比，增強(qiáng)我們根據(jù)求解問(wèn)題的性質(zhì)選擇合理的數(shù)據(jù)結(jié)構(gòu)，并將問(wèn)題求解算法的空間、時(shí)間及復(fù)雜性控制在一定范圍的能力。

　　軟件設(shè)計(jì)師考試大綱對(duì)數(shù)據(jù)結(jié)構(gòu)部分的要求是熟練掌握常用數(shù)據(jù)結(jié)構(gòu)和常用算法，因此，本專題從數(shù)據(jù)結(jié)構(gòu)的概述出發(fā)，對(duì)基本的概念引出常用的數(shù)據(jù)結(jié)構(gòu)類型的介紹和講解，同時(shí)在講解各種數(shù)據(jù)結(jié)構(gòu)中間采用算法與數(shù)據(jù)結(jié)構(gòu)相結(jié)合的方式，在算法步驟中使用數(shù)據(jù)結(jié)構(gòu)，對(duì)數(shù)據(jù)結(jié)構(gòu)的重點(diǎn)、難點(diǎn)進(jìn)行了分析，最后講解了與數(shù)據(jù)結(jié)構(gòu)緊密相關(guān)的排序和查找算法，以及一些以往考試題的分析。

　　1. 數(shù)據(jù)結(jié)構(gòu)概述

　　數(shù)據(jù)結(jié)構(gòu)研究了計(jì)算機(jī)需要處理的數(shù)據(jù)對(duì)象和對(duì)象之間的關(guān)系;刻畫(huà)了應(yīng)用中涉及到的數(shù)據(jù)的邏輯組織;也描述了數(shù)據(jù)在計(jì)算機(jī)中如何存儲(chǔ)、傳送、轉(zhuǎn)換。

　　學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)注意的問(wèn)題：

　　n 系統(tǒng)掌握基本數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)及其不同實(shí)現(xiàn)。

　　n 了解并掌握各種數(shù)據(jù)結(jié)構(gòu)上主要操作的實(shí)現(xiàn)及其性能(時(shí)間、空間)的分析。

　　n 掌握各種數(shù)據(jù)結(jié)構(gòu)的使用特性，在算法設(shè)計(jì)中能夠進(jìn)行選擇。

　　n 掌握常用的遞歸、回溯、迭代、遞推等方法的設(shè)計(jì)

　　n 掌握自頂向下、逐步求精的程序設(shè)計(jì)方法。

　　n 掌握自頂向下、逐步求精的程序設(shè)計(jì)方法。

　　在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的知識(shí)之前，我們要了解一下數(shù)據(jù)結(jié)構(gòu)中的基本概念。

　　數(shù)據(jù)：對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)中就是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序所處理的符號(hào)的總稱。

　　數(shù)據(jù)項(xiàng)： 是數(shù)據(jù)的不可分割的最小單位;

　　數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行處理;一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。

　　數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。

　　數(shù)據(jù)結(jié)構(gòu)上的基本操作： ◆插入操作 ◆刪除操作 ◆更新操作 ◆查找操作 ◆排序操作

　　數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)對(duì)象及相互關(guān)系和構(gòu)造方法，一個(gè)數(shù)據(jù)結(jié)構(gòu)B形式上可以用一個(gè)二元組表示為B=(A，R)。其中，A是數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)(稱為結(jié)點(diǎn))的非空有限集合，R是定義在A上的關(guān)系的非空有限集合。

　　根據(jù)數(shù)據(jù)元素之間的關(guān)系的不同特性，通常有下列4類基本結(jié)構(gòu)。

　　Ø 集合——結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個(gè)集合”的關(guān)系外，別無(wú)其他關(guān)系。

　　Ø 線性結(jié)構(gòu)——結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系。

　　Ø 樹(shù)形結(jié)構(gòu)——結(jié)構(gòu)中的元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系。

　　Ø 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)——結(jié)構(gòu)中的元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系。

　　數(shù)據(jù)結(jié)構(gòu)中，結(jié)點(diǎn)與結(jié)點(diǎn)間的相互關(guān)系是數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(又稱為映象)稱為數(shù)據(jù)的物理結(jié)構(gòu)，也稱存儲(chǔ)結(jié)構(gòu)。

　　數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方式：順序映象和非順序映象，并由此得到兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

　　任何一個(gè)算法的設(shè)計(jì)取決于選定的數(shù)據(jù)(邏輯)結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu)。

　　數(shù)據(jù)的邏輯結(jié)構(gòu)分為兩類：

　　線性結(jié)構(gòu)：線性表、棧、隊(duì)列和串

　　非線性結(jié)構(gòu)：樹(shù)、圖

　　數(shù)據(jù)的存儲(chǔ)方法有四類：

　　順序存儲(chǔ)方法

　　鏈接存儲(chǔ)方法

　　索引存儲(chǔ)方法

　　散列存儲(chǔ)方法

　　　　　　　計(jì)算機(jī)軟考軟件設(shè)計(jì)師練習(xí)試題及答案解析匯總