計(jì)算思維在數(shù)據(jù)結(jié)構(gòu)中的實(shí)踐探索

李慧玲

（長(zhǎng)治學(xué)院，山西 長(zhǎng)治 046000）

1 計(jì)算思維與數(shù)據(jù)結(jié)構(gòu)

計(jì)算思維具有多重特征，其主要表現(xiàn)為概念化、思維化、數(shù)學(xué)與工程思維的互補(bǔ)性等等。計(jì)算思維的精華即通過(guò)學(xué)習(xí)計(jì)算機(jī)科學(xué)基礎(chǔ)理論去解決實(shí)際問(wèn)題，并且去理解人們的行為。它利用抽象和分解的形式，實(shí)現(xiàn)復(fù)雜的任務(wù)并且設(shè)計(jì)出復(fù)雜的系統(tǒng)；利用合理的方法詮釋問(wèn)題并且建立數(shù)學(xué)模型；利用冗余、容錯(cuò)、糾錯(cuò)和恢復(fù)等方式解決技術(shù)問(wèn)題；利用數(shù)據(jù)來(lái)進(jìn)行計(jì)算。計(jì)算思維的一個(gè)中心思想即基于計(jì)算的思維，所以如何實(shí)現(xiàn)計(jì)算能力變得尤為重要。

2 應(yīng)用數(shù)據(jù)抽象，建立數(shù)據(jù)的對(duì)象模型

在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的過(guò)程中，遇到一個(gè)問(wèn)題，首先必須進(jìn)行抽象選擇，找到數(shù)據(jù)對(duì)象并且對(duì)其進(jìn)行分析。當(dāng)確定出這個(gè)數(shù)據(jù)的邏輯關(guān)系之后，選擇數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，之后對(duì)存儲(chǔ)結(jié)構(gòu)的基本操作實(shí)現(xiàn)進(jìn)行考慮。接著，建立對(duì)應(yīng)的數(shù)據(jù)模型。

2.1 利用ADT建立數(shù)據(jù)對(duì)象模型

ADT主要指的是一個(gè)數(shù)學(xué)模型，同時(shí)它還指一組操作，這組操作主要是基于數(shù)學(xué)模型建立的。在使用 ADT建立數(shù)據(jù)對(duì)象的過(guò)程中，主要把握的應(yīng)該是數(shù)據(jù)的本質(zhì)特點(diǎn)以及數(shù)據(jù)能夠?qū)崿F(xiàn)的功能、數(shù)據(jù)外部接口。對(duì)于抽象數(shù)據(jù)類型ADT，我們也可以使用三元組（D，S， P）的方式來(lái)表示。在三元組中，D即為數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是基于D的基本操作集。數(shù)據(jù)類型較為容易理解，是指高級(jí)語(yǔ)言中實(shí)現(xiàn)了的基本數(shù)據(jù)結(jié)構(gòu)。而抽象數(shù)據(jù)類型，則是數(shù)據(jù)類型的深入發(fā)展。通過(guò)已有的基本數(shù)據(jù)類型實(shí)現(xiàn)對(duì)新的數(shù)據(jù)類型的擴(kuò)展，進(jìn)而使得更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)得以實(shí)現(xiàn)。換句話說(shuō)，數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)相當(dāng)于抽象數(shù)據(jù)類型的設(shè)計(jì)與實(shí)現(xiàn)。

2.2 認(rèn)識(shí)已有的數(shù)據(jù)對(duì)象

在數(shù)據(jù)結(jié)構(gòu)課程中，我們具備較多的數(shù)據(jù)對(duì)象模型，比如順序棧、循環(huán)隊(duì)列、二叉樹(shù)、鄰接表圖、哈希表等等。充分掌握這些數(shù)據(jù)對(duì)象模型，對(duì)于實(shí)際的應(yīng)用數(shù)據(jù)結(jié)構(gòu)有著積極作用。一些比較復(fù)雜的數(shù)據(jù)對(duì)象的操作，都能通過(guò)基本操作來(lái)完成。舉一個(gè)簡(jiǎn)單的例子，ADT List對(duì)線性表結(jié)構(gòu)及其基本操作的邏輯定義進(jìn)行了解釋，同時(shí)創(chuàng)建了相應(yīng)的數(shù)據(jù)模型。根據(jù)這個(gè)定義的基本操作，我們可以完成其他線性表的操作，即使操作相對(duì)復(fù)雜。

2.3 設(shè)計(jì)與實(shí)現(xiàn)新的數(shù)據(jù)對(duì)象

數(shù)據(jù)結(jié)構(gòu)中的基本操作歸納為四類：創(chuàng)建和銷毀結(jié)構(gòu)類，屬性操作類，查找類，以及更新類?；谶@些內(nèi)容，我們可以參照數(shù)據(jù)的特征，通過(guò)ADT實(shí)現(xiàn)對(duì)新的數(shù)據(jù)類型的開(kāi)發(fā)。

3 應(yīng)用問(wèn)題抽象，建立問(wèn)題的數(shù)學(xué)模型

對(duì)于一個(gè)未曾面對(duì)過(guò)的復(fù)雜問(wèn)題，采用直接求解的方式是不太恰當(dāng)?shù)?。遇到這種情況，我們一般的思路是分析問(wèn)題，再對(duì)問(wèn)題進(jìn)行抽象和分解、轉(zhuǎn)換，最后得到一個(gè)本質(zhì)和原問(wèn)題相對(duì)接近的問(wèn)題。這個(gè)問(wèn)題必須是能夠利用計(jì)算機(jī)解決、較為簡(jiǎn)單的。我們通常把原始的問(wèn)題對(duì)象命名為原型，進(jìn)行抽象分解后的則是數(shù)學(xué)模型。在解決一個(gè)實(shí)際問(wèn)題時(shí)，完成建模之后還需采用對(duì)應(yīng)的技術(shù)方式來(lái)對(duì)其進(jìn)行檢驗(yàn)，比如計(jì)算、模擬等等。若建立的這個(gè)數(shù)學(xué)模型與實(shí)際的狀況存在較大差距，必須馬上對(duì)有問(wèn)題的模型進(jìn)行修改。較之于實(shí)際的問(wèn)題，數(shù)學(xué)模型具備一定的優(yōu)點(diǎn)，有等價(jià)性、抽象性、高效性等等都是它的特點(diǎn)。之所以要建立數(shù)學(xué)模型，主要是為了更好地掌握數(shù)據(jù)之間的關(guān)系，以及它們的變化情況。在創(chuàng)建數(shù)學(xué)模型的過(guò)程中，若能發(fā)現(xiàn)有價(jià)值的線索，可以大大降低問(wèn)題的難度。

4 算法

在數(shù)學(xué)模型的建立過(guò)程中，最為重要的兩個(gè)環(huán)節(jié)即數(shù)學(xué)模型的創(chuàng)建和求解。在建立數(shù)學(xué)模型的過(guò)程中，更多的是依靠一定的數(shù)學(xué)基礎(chǔ)。在求解問(wèn)題時(shí)，問(wèn)題的數(shù)學(xué)模型必須進(jìn)行算法的設(shè)計(jì)與實(shí)現(xiàn)。這就需要依據(jù)數(shù)據(jù)模型，制定出最為合理的計(jì)算方法，并且找到恰當(dāng)?shù)乃惴āＳ捎谒惴ǖ牟煌?，結(jié)果必須存在較大的差異。在對(duì)算法進(jìn)行選擇時(shí)，計(jì)算思維能力便得到了一定程度的訓(xùn)練。拿最小代價(jià)生成樹(shù)問(wèn)題的求解來(lái)說(shuō)，它可以采用多種算法。如果是n個(gè)城市的連通圖，數(shù)據(jù)對(duì)象是圖形結(jié)構(gòu)，數(shù)學(xué)模型是最小代價(jià)生成樹(shù)。這時(shí)使用窮舉法，必須多這些城市進(jìn)行 n！次全排列。之后，還要求解各種排列的代價(jià)之和，并且作出比較，進(jìn)而找到問(wèn)題的最小代價(jià)。這時(shí)，如果使用貪心法，對(duì)稠密圖，采用prim算法。任意選擇一個(gè)頂點(diǎn)，之后的每次從剩下的頂點(diǎn)中選擇出另外一個(gè)頂點(diǎn)，再附加一條邊。此時(shí)，只要滿足添加的邊的代價(jià)之和為當(dāng)前最小即可。這樣一直持續(xù)至選擇了n個(gè)頂點(diǎn)，當(dāng)然也包括n-1條邊。

當(dāng)然，同一個(gè)問(wèn)題，也可以使用不同的數(shù)據(jù)結(jié)構(gòu)，同時(shí)選擇不同的算法來(lái)求解。在這個(gè)過(guò)程中，計(jì)算思維能力也能得到較好的訓(xùn)練。這里以四則運(yùn)算表達(dá)式求值問(wèn)題的求解為例。假如四則運(yùn)算表達(dá)式的形式為字符串，表達(dá)式存儲(chǔ)在數(shù)組中。

5 結(jié)束語(yǔ)

總之，其主要以計(jì)算思維為引入，將計(jì)算思維在數(shù)據(jù)結(jié)構(gòu)中的實(shí)踐探索貫穿整個(gè)研究課程，始終將如何培養(yǎng)計(jì)算思維能力的實(shí)踐作為研究重心。在充分把握計(jì)算思維與數(shù)據(jù)結(jié)構(gòu)的關(guān)系之后，我們就可以立足于計(jì)算思維的抽象與自動(dòng)化本質(zhì)，通過(guò)建模，用計(jì)算機(jī)整理海量數(shù)據(jù)，進(jìn)而提升自身的計(jì)算思維能力。

[1]劉昕, 石樂(lè)義, 亓雪冬.面向計(jì)算思維的數(shù)據(jù)結(jié)構(gòu)課程教學(xué)改革[J].計(jì)算機(jī)教育.2013(16)：39-42.

[2]孟凡榮, 賈杰, 王興偉.網(wǎng)絡(luò)工程專業(yè)創(chuàng)新性實(shí)踐課程體系構(gòu)建與實(shí)施[J].計(jì)算機(jī)教育.2013(14)：108-112.

[3]楊建磊.我國(guó)高校計(jì)算機(jī)基礎(chǔ)課程改革目標(biāo)的新定位——基于計(jì)算思維理論[J].甘肅科技.2012(15)：83+90-91.