第二章考試要點(diǎn)

本章內(nèi)容主要是:數(shù)據(jù)結(jié)構(gòu)、算法的基本概念;線性表邏輯結(jié)構(gòu)，鏈表、數(shù)組的存儲(chǔ)和運(yùn)算;隊(duì)列與棧的定義，存儲(chǔ)及應(yīng)用;樹和二叉樹的定義，互相轉(zhuǎn)換，二叉樹的存儲(chǔ)，二叉樹的周游;圖的基本概念，圖的存儲(chǔ)的周游;排序的基本概念與排序算法(選擇排序，插入排序，交換排序，歸并排序);檢索的基本概念與檢索算法(順序檢索，二分檢索，散列技術(shù)檢索，二叉排序樹)。

以下介紹一些常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論它們?cè)谟?jì)算機(jī)中的存儲(chǔ)表示，以及在這些數(shù)據(jù)結(jié)構(gòu)上進(jìn)行的各種運(yùn)算和實(shí)際的執(zhí)行算法，并對(duì)算法的效率進(jìn)行簡單的分析。

一、基本概念

1.什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)是描述客觀事物的數(shù)字、字符以及所有能直接輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的集合。

數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。通常，一個(gè)數(shù)據(jù)對(duì)象中的數(shù)據(jù)元素不是孤立的，而是彼此之間存在著一定的聯(lián)系，這種聯(lián)系就是數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的聯(lián)系需要在對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)和加工中反映出來，因此，數(shù)據(jù)結(jié)構(gòu)概念一般包括三方面的內(nèi)容:數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式、以及在這些數(shù)據(jù)上定義的運(yùn)算的集合。

(1)數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)只抽象地反映數(shù)據(jù)元素之間的邏輯關(guān)系，它與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。

數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類，線性結(jié)構(gòu)的邏輯特征是:有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有的結(jié)點(diǎn)都最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼。線性表就是一個(gè)典型的線性結(jié)構(gòu)。非線性結(jié)構(gòu)的邏輯特征是:一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)和直接后繼。樹、圖等都是非線性結(jié)構(gòu)。

(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器里的實(shí)現(xiàn)(亦稱為映象)。它是依賴于計(jì)算機(jī)的，并有四種基本的存儲(chǔ)映象方法。它們是:

①順序存儲(chǔ)方法 該方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元內(nèi)，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。順序存儲(chǔ)方法主要用于線性的數(shù)據(jù)結(jié)構(gòu)，非線性的數(shù)據(jù)結(jié)構(gòu)也可以通過某種線性化方法來實(shí)現(xiàn)順序存儲(chǔ)。

②鏈接存儲(chǔ)方法 在鏈接存儲(chǔ)方法中，邏輯上相鄰的結(jié)點(diǎn)在物理位置上未必相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。

③索引存儲(chǔ)方法 該方法通常是在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，還建立一個(gè)附加的索引表，索引表中的每一項(xiàng)稱為索引項(xiàng)，索引項(xiàng)的一般形式是:(關(guān)鍵字，地址)。關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。

④散列存儲(chǔ)方法 在散列存儲(chǔ)方法中，結(jié)點(diǎn)的存儲(chǔ)地址是根據(jù)結(jié)點(diǎn)的關(guān)鍵字值直接計(jì)算出來的。上述四種基本的存儲(chǔ)方法也可以組合起來對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)映象。

(3)數(shù)據(jù)的運(yùn)算

數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算的集合。常用的運(yùn)算有:查找、插入、刪除、更新、排序等。顯然，對(duì)數(shù)據(jù)運(yùn)算的具體實(shí)現(xiàn)方法只有在確定了存儲(chǔ)結(jié)構(gòu)之后才能加以考慮。

總結(jié)

以上是生活随笔為你收集整理的计算机国二复习攻略,全国计算机等级考试四级复习纲要二[1]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。