試論C++語言在數(shù)據(jù)結(jié)構(gòu)中應(yīng)用

【摘 要】數(shù)據(jù)結(jié)構(gòu)是面向過程編程中的一個(gè)重要概念，即使在面向?qū)ο缶幊讨幸簿哂兄匾牡匚唬驗(yàn)槊鎸?duì)繁多而復(fù)雜的待處理數(shù)據(jù)，如果沒有數(shù)據(jù)結(jié)構(gòu)將數(shù)據(jù)組織起來，那么程序的編寫將變得極為艱難。在整個(gè)程序編寫的過程中，數(shù)據(jù)結(jié)構(gòu)為編程中的法，而使用的語言就是編程中的術(shù)。在該文中將試析C++語言如何在數(shù)據(jù)結(jié)構(gòu)中的運(yùn)用，如何發(fā)揮出數(shù)據(jù)結(jié)構(gòu)更好的效果。

【關(guān)鍵詞】C++；數(shù)據(jù)結(jié)構(gòu)；計(jì)算機(jī)語言

C++語言是從C語言繼承而來，并從C語言的基礎(chǔ)上增加了很多新的特性以適應(yīng)新的技術(shù)要求。應(yīng)該說C++是一個(gè)龐大的功能強(qiáng)悍的一種語言，它既可以完成與C語言一樣的面向過程編程也可以完成面向?qū)ο缶幊獭Ｔ诿嫦蜻^程編程中，C++也同樣完成了對(duì)C語言的擴(kuò)展，增加了很多的庫與函數(shù)，這些庫與函數(shù)的存在賦予了C++在數(shù)據(jù)結(jié)構(gòu)的運(yùn)用中超過C語言的能力。可以說，C++在數(shù)據(jù)結(jié)構(gòu)中的運(yùn)用靈活程度與使用方法超過了C語言。在數(shù)據(jù)與數(shù)據(jù)之間存在著各種各樣的關(guān)系，這些關(guān)系稱之為結(jié)構(gòu)，而數(shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)元素之間特定關(guān)系的集合。數(shù)據(jù)結(jié)構(gòu)可以分為很多部分，但是基本結(jié)構(gòu)主要有四種，這四種分別是：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)。這四種基本的四類結(jié)構(gòu)相互復(fù)合便可以組成成千上萬中不同的數(shù)據(jù)結(jié)構(gòu)。該文主要探討C++語言對(duì)于一些常見結(jié)構(gòu)的運(yùn)用，也就相當(dāng)于從底層講述C++在數(shù)據(jù)結(jié)構(gòu)中的運(yùn)用。

1.數(shù)據(jù)的邏輯表示、存儲(chǔ)形式和操作

要描述一組關(guān)聯(lián)的數(shù)據(jù)元素，必然是一種抽象，一種邏輯的表示形式。這種邏輯表示應(yīng)該獨(dú)立于計(jì)算機(jī)，是數(shù)據(jù)元素本身所固有的。顯然，這樣的一組數(shù)據(jù)元素的邏輯結(jié)構(gòu)應(yīng)該包括數(shù)據(jù)元素本身和數(shù)據(jù)元素之間的聯(lián)系。當(dāng)一組關(guān)聯(lián)的數(shù)據(jù)元素存儲(chǔ)到計(jì)算機(jī)中時(shí)，必然以一種物理的形式組織和存放在計(jì)算機(jī)存儲(chǔ)器中，它應(yīng)該是這組數(shù)據(jù)元素的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的映像，是依賴于計(jì)算機(jī)的。這種映像是這組數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)，它也能夠體現(xiàn)數(shù)據(jù)元素本身以及數(shù)據(jù)元素之間的聯(lián)系。就存儲(chǔ)結(jié)構(gòu)本身而言，它不體現(xiàn)任何相關(guān)的操作，只是對(duì)操作的方式會(huì)提出要求并產(chǎn)生影響。當(dāng)對(duì)一組關(guān)聯(lián)的數(shù)據(jù)元素進(jìn)行加工處理時(shí)，相對(duì)應(yīng)的則是一組相關(guān)的操作，這樣的一組操作稱為施加在這組數(shù)據(jù)元素之上的運(yùn)算。運(yùn)算的定義依賴于數(shù)據(jù)元素的邏輯結(jié)構(gòu)，而運(yùn)算的實(shí)現(xiàn)則依賴于存儲(chǔ)結(jié)構(gòu)，是通過計(jì)算機(jī)語言完成的，是對(duì)數(shù)據(jù)進(jìn)行加工處理的方法和動(dòng)態(tài)過程的描述。如果說數(shù)據(jù)結(jié)構(gòu)這門課程包括了數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和對(duì)數(shù)據(jù)所施加的運(yùn)算等諸多方面的內(nèi)容是行得通的。但如果說數(shù)據(jù)結(jié)構(gòu)包括這3方面的內(nèi)容則顯得過于寬泛。數(shù)據(jù)結(jié)構(gòu)應(yīng)該是一組數(shù)據(jù)元素的靜態(tài)結(jié)構(gòu)的描述，它應(yīng)該包括邏輯層面和物理層面兩個(gè)方面。在邏輯層面上而言，是數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一種邏輯的描述形式，可以采用文字描述或采用圖形方式來表示，也可以用數(shù)學(xué)的符號(hào)形式加以定義；在物理層面上而言，則是數(shù)據(jù)和數(shù)據(jù)之間關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的體現(xiàn)，同樣也是一種靜態(tài)結(jié)構(gòu)形態(tài)。這種靜態(tài)結(jié)構(gòu)是不可見的，為了便于理解，這種形態(tài)也可以用文字描述或圖形描述的方式邏輯地加以表示。或者說，數(shù)據(jù)結(jié)構(gòu)是一組數(shù)據(jù)元素的全體以及數(shù)據(jù)元素之間的關(guān)系的全體，在邏輯層面上稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，在物理層面上稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。也可以說數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的映像。典型的數(shù)據(jù)結(jié)構(gòu)有集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)，它們都有邏輯的表示形式和物理的存儲(chǔ)形態(tài)。數(shù)據(jù)的存儲(chǔ)又有兩種最基本的存儲(chǔ)方式，即順序存儲(chǔ)方式和鏈接存儲(chǔ)方式，散列和索引則是兩種基本方式的復(fù)雜應(yīng)用。這是為了便于數(shù)據(jù)的處理而采用的兩種不同的存儲(chǔ)技術(shù)，而不是數(shù)據(jù)結(jié)構(gòu)的差異。

2.在線性結(jié)構(gòu)中的運(yùn)用

線性具體的表現(xiàn)形式有好多種，如線性鏈表、雙向鏈表、堆棧、隊(duì)列等，但是這些結(jié)構(gòu)都有著共同的特性，它們都是唯一的一個(gè)開頭的數(shù)據(jù)元素，也有唯一的一個(gè)最后的數(shù)據(jù)元素等，且除了第一個(gè)與最后一個(gè)元素外，每個(gè)元素都有唯一的前驅(qū)與后驅(qū)。這使得線性表的結(jié)構(gòu)相對(duì)于其他的數(shù)據(jù)結(jié)構(gòu)比較簡(jiǎn)單，更容易掌握，所以對(duì)于線性結(jié)構(gòu)的使用也是最多的。在線性結(jié)構(gòu)中，一個(gè)數(shù)據(jù)元素的尋找自己的前驅(qū)或者后驅(qū)有兩種方式，這取決于這個(gè)線性結(jié)構(gòu)在內(nèi)存中的存儲(chǔ)方式。線性結(jié)構(gòu)在內(nèi)存中的存儲(chǔ)不一定是線性的，比如鏈表就不是線性的。線性結(jié)構(gòu)的操作主要有三個(gè)，分別是插入、刪除、修改。如果一個(gè)線性結(jié)構(gòu)在內(nèi)存中的存儲(chǔ)也是線性的話，其操作會(huì)相對(duì)簡(jiǎn)單些，在C++語言中，可以直接使用C++提供的強(qiáng)大的運(yùn)算速度處理數(shù)據(jù)元素，但是相對(duì)來講復(fù)雜些，且這種操作手法與使用C語言操作線性結(jié)構(gòu)的手法別無二致。除以上方法外，用戶也可以使用C++的各種各樣的容器，很多的容器都是各種類型的線性結(jié)構(gòu)，使用這些容器就可以大大的減少操作線性結(jié)構(gòu)的代碼。至于C++實(shí)現(xiàn)代碼究竟用的是內(nèi)存非線性存儲(chǔ)還是線性存儲(chǔ)不需要使用者關(guān)心，這部分對(duì)于C++的使用者來講是透明的。

3.在樹中的運(yùn)用

樹與圖都是非線性結(jié)構(gòu)，且樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)。在自然界中存在著很多的樹形結(jié)構(gòu)，為了計(jì)算機(jī)更好的處理這些數(shù)據(jù)，所以抽象出了樹形結(jié)構(gòu)。樹形結(jié)構(gòu)是由眾多的節(jié)點(diǎn)所構(gòu)成，有且僅有一個(gè)根節(jié)點(diǎn)，剩余的節(jié)點(diǎn)組成了互不交叉干涉的子集，也叫根的子樹，實(shí)際編程中用到的樹，往往是多層的樹，除了最下層的節(jié)點(diǎn)外其他的都是一個(gè)子樹，由于這種抽象的類型很像自然界中的樹，所以稱之為樹形結(jié)構(gòu)。樹形結(jié)構(gòu)與線性結(jié)構(gòu)的不同在于樹形結(jié)構(gòu)中的節(jié)點(diǎn)對(duì)應(yīng)一個(gè)前驅(qū)，但是往往對(duì)應(yīng)多個(gè)后驅(qū)，其整體結(jié)構(gòu)并不是順序的，而是從上往下擴(kuò)散開的結(jié)構(gòu)，而且樹也可以分作多種類型，這些樹形結(jié)構(gòu)都有各自的特點(diǎn)，如二叉樹、平衡樹等，這些樹的存儲(chǔ)、構(gòu)建與維護(hù)也經(jīng)常使用不同方法。

對(duì)于C++語言來說，所有使用樹形結(jié)構(gòu)的要求都能滿足。比如樹的鏈接一般是多點(diǎn)鏈接，而計(jì)算機(jī)的存儲(chǔ)空間是順序的，所以樹在計(jì)算機(jī)中存儲(chǔ)往往不是連續(xù)的，必須用到指針，而C++的指針恰恰非常強(qiáng)大。

4.在圖中的運(yùn)用

圖形結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)中最為復(fù)雜的一種結(jié)構(gòu)模型。在線性結(jié)構(gòu)中有且只有一個(gè)前驅(qū)以及后驅(qū)，在樹形結(jié)構(gòu)中節(jié)點(diǎn)只有一個(gè)前驅(qū)以及多個(gè)后驅(qū)，子樹之間并無交叉聯(lián)系，呈現(xiàn)明顯的層次感，但是在圖形結(jié)構(gòu)中，整個(gè)集合中的任意兩個(gè)數(shù)據(jù)元素都可以存在著關(guān)系，這就造成了復(fù)雜的圖形結(jié)構(gòu)。

鑒于圖形結(jié)構(gòu)千差萬別，所以C++語言中沒有提供能夠直接進(jìn)行圖操作的函數(shù)，僅有一些特定的基礎(chǔ)操作，對(duì)于圖形的處理，只能依靠程序編寫者具體問題具體分析了。C++在圖形數(shù)據(jù)結(jié)構(gòu)的處理中，有以下的幾個(gè)優(yōu)點(diǎn)：

（1）較高的代碼效率。雖然C++的運(yùn)算速度不如C語言與匯編，但是相對(duì)于其他的高級(jí)語言來講，已經(jīng)非常快了，處理復(fù)雜問題的圖問題是一個(gè)很合適的選擇。

（2）靈活的指針。C++的指針往往是C++初學(xué)者難以運(yùn)用的功能，但是擁有指針后能施展的能力確實(shí)非常強(qiáng)大的，特別是處理離散數(shù)據(jù)方面具有無可比擬的優(yōu)勢(shì)。

（3）嚴(yán)密的邏輯。C++邏輯非常嚴(yán)密，易于編寫種種復(fù)雜的算法用來處理復(fù)雜的圖形問題。總的來說，在處理圖形結(jié)構(gòu)數(shù)據(jù)時(shí)，C++語言是除了C語言以外的最佳選擇。

【參考文獻(xiàn)】

［１］付勇.數(shù)據(jù)結(jié)構(gòu)的定義及其相關(guān)術(shù)語[J].電腦編程技巧與維護(hù)，2011(10)．