孟凡榮 張斌 楊雷

摘要：隨著計算機網(wǎng)絡(luò)時代的到來，計算思維的概念應(yīng)運而生。培養(yǎng)計算思維能力的實踐更為重要。許多高校都努力實踐如何將計算思維的能力培養(yǎng)融入到平日的課程教學(xué)中。本文討論計算思維與數(shù)據(jù)結(jié)構(gòu)的關(guān)系，從計算思維的抽象與自動化的本質(zhì)出發(fā)，以數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)對象建模和問題數(shù)學(xué)建模以及算法的計算機實現(xiàn)為線索，對如何在數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)中進行計算思維能力的培養(yǎng)進行了深入探討。

關(guān)鍵詞：計算思維能力；數(shù)據(jù)結(jié)構(gòu)；問題求解；模型及算法

中圖分類號：G642.0 文獻標志碼：A 文章編號：1674-9324（2015）10-0117-04

一、引言

隨著計算機網(wǎng)絡(luò)時代的到來，計算思維的概念應(yīng)運而生。按照計算思維的倡導(dǎo)者Wing教授的觀點，計算思維代表著一種普遍的態(tài)度和一類普適的技能，不僅僅是計算機科學(xué)家，每一個人都應(yīng)熱心于它的學(xué)習(xí)和運用。自從計算思維的概念提出以后，計算思維與理論思維、實驗思維并稱為三大科學(xué)思維。數(shù)據(jù)結(jié)構(gòu)課程是計算機科學(xué)與技術(shù)專業(yè)的一門專業(yè)基礎(chǔ)課，是計算機算法設(shè)計與分析、操作系統(tǒng)、數(shù)據(jù)庫原理、軟件工程等課程的重要的前導(dǎo)課程。該課程的任務(wù)是學(xué)會從分析與解決問題入手，能夠合理選定數(shù)據(jù)的邏輯結(jié)構(gòu)、組織數(shù)據(jù)，并為所加工的數(shù)據(jù)選取適宜的存儲結(jié)構(gòu)，完成其基本操作算法，初步掌握算法的時間與空間復(fù)雜性的分析方法，同時進行復(fù)雜程序設(shè)計的訓(xùn)練，編寫符合軟件工程規(guī)范的軟件，將數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識應(yīng)用于實踐。近年來，許多高校都努力實踐將計算思維的能力培養(yǎng)融入到平日的課程教學(xué)中。本文從計算思維與數(shù)據(jù)結(jié)構(gòu)的關(guān)系，應(yīng)用數(shù)據(jù)抽象和問題抽象、建立數(shù)據(jù)對象模型和問題對象模型，應(yīng)用計算機實現(xiàn)問題求解的算法等三個方面探討如何在數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)中進行計算思維能力的培養(yǎng)。

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

計算思維具有概念化、技能化、思維化、數(shù)學(xué)與工程思維的互補性、普適性等重要特征。計算思維的精髓是運用計算機科學(xué)的基礎(chǔ)概念去求解問題、設(shè)計系統(tǒng)和理解人類的行為。計算思維通過抽象和分解來完成復(fù)雜的任務(wù)或設(shè)計復(fù)雜的系統(tǒng)；通過選擇合適的方式來對問題陳述并建立數(shù)學(xué)模型；通過采取保護、冗余、容錯、糾錯和恢復(fù)等措施解決具體的技術(shù)問題；利用啟發(fā)式推理來尋求問題的解答，并利用海量數(shù)據(jù)進行快速的計算。計算思維的核心思想是基于計算的思維，如何計算是實現(xiàn)計算思維能力的關(guān)鍵。而實現(xiàn)計算的有效工具是應(yīng)用計算機。計算思維是借助于計算機而實現(xiàn)的思維，正如電動機的出現(xiàn)引發(fā)了自動化思維，計算機的出現(xiàn)催生了計算思維。數(shù)學(xué)和計算機已成為計算思維應(yīng)用中不可分割的重要工具。有了計算機，計算思維就有了用武之地。采用計算思維可以使我們把一個看似復(fù)雜困難的問題轉(zhuǎn)化為一個簡單易解的問題加以解決。所以說，計算思維是一種科學(xué)思維，是人類的一種進步思維。計算機科學(xué)與技術(shù)專業(yè)一般包括計算機科學(xué)、計算機工程、軟件工程和信息技術(shù)等專業(yè)。數(shù)據(jù)結(jié)構(gòu)課程與計算機高級程序設(shè)計語言、算法設(shè)計與分析課程一起構(gòu)成程序設(shè)計基礎(chǔ)、算法與復(fù)雜性領(lǐng)域的核心知識單元。一方面，數(shù)據(jù)結(jié)構(gòu)課程是高級程序語言課程的后續(xù)強化程序設(shè)計訓(xùn)練，另一方面，它又是算法設(shè)計與分析課程的前導(dǎo)基礎(chǔ)知識訓(xùn)練。數(shù)據(jù)結(jié)構(gòu)課程教學(xué)內(nèi)容包括理論教學(xué)和實踐教學(xué)。理論教學(xué)主要包括數(shù)據(jù)的線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)和集合類型的選取、組織和應(yīng)用。其中，線性結(jié)構(gòu)包括線性表、棧和隊列、數(shù)組和字符串等；樹結(jié)構(gòu)主要包括二叉樹、線索樹、排序樹、一般樹等；圖結(jié)構(gòu)主要包括無向圖、有向圖、帶權(quán)圖、一般圖等；集合類型主要包括查找、排序和文件等。數(shù)據(jù)結(jié)構(gòu)實踐課程是數(shù)據(jù)結(jié)構(gòu)課程的重要組成部分。教學(xué)計劃是一個整體。實踐教學(xué)體系是整體教學(xué)計劃的一部分，也是一個與理論教學(xué)體系有機結(jié)合的、相對獨立的完整結(jié)構(gòu)體系。理論課程體系主要體現(xiàn)專業(yè)結(jié)構(gòu)、知識結(jié)構(gòu)的培養(yǎng)目標要求，從而確定理論課程的知識領(lǐng)域、核心知識單元和知識點。而實踐課程體系主要體現(xiàn)能力結(jié)構(gòu)的培養(yǎng)目標要求，由能力結(jié)構(gòu)確定實踐課程體系的各個單元的目標結(jié)構(gòu)和具體指標。數(shù)據(jù)結(jié)構(gòu)的課堂理論教學(xué)主要采用啟發(fā)式、講解式和案例驅(qū)動式等教學(xué)方式。而實踐教學(xué)方式則主要采用項目驅(qū)動方式，采用課題教學(xué)法和單元教學(xué)法。數(shù)據(jù)結(jié)構(gòu)實踐課程的教學(xué)體系由課程實習(xí)、課程實驗、課程設(shè)計、課程社會實踐、實踐教學(xué)評測和實踐教學(xué)文檔及資源等部分構(gòu)成。計算思維具有普適性，而數(shù)據(jù)結(jié)構(gòu)的應(yīng)用同樣具有廣泛性。不僅是工科的非計算機專業(yè)，甚至是許多非工科的非計算機專業(yè)也同樣需要問題求解和數(shù)據(jù)分析，也面臨著計算機的應(yīng)用，所以也把數(shù)據(jù)結(jié)構(gòu)課程作為必修課或選修課，研究數(shù)據(jù)的選取和組織，通過數(shù)據(jù)結(jié)構(gòu)課程的導(dǎo)入，將計算思維的能力培養(yǎng)融入其中。計算思維的本質(zhì)是抽象和自動化。抽象是在多個層次上進行的。通過數(shù)據(jù)抽象建立數(shù)據(jù)的對象模型，通過問題抽象建立問題的數(shù)學(xué)模型，應(yīng)用約簡、嵌入、轉(zhuǎn)化、仿真等方法，使用計算機處理海量數(shù)據(jù)，通過算法實現(xiàn)問題的求解。數(shù)據(jù)結(jié)構(gòu)內(nèi)容的實質(zhì)恰恰是“模型+算法”。狹義的數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)元素之間存在的一種或多種關(guān)系的集合。廣義的數(shù)據(jù)結(jié)構(gòu)則是在狹義的定義的基礎(chǔ)上再加上基本操作的集合，使數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)成為可能。通過建立數(shù)據(jù)的對象模型和問題的數(shù)學(xué)模型，并對建立的模型研究出實現(xiàn)算法，從而實現(xiàn)編程的自動化。提出計算思維的目的是實現(xiàn)計算思維的能力。數(shù)據(jù)結(jié)構(gòu)課程的目的是數(shù)據(jù)結(jié)構(gòu)的應(yīng)用實現(xiàn)，這與計算思維的目的不謀而合。所以，構(gòu)建一個基于計算思維的數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)體系，不僅自然，而且易行。

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

在數(shù)據(jù)結(jié)構(gòu)課程中，當面對一個問題時，首先是要從問題中抽象出數(shù)據(jù)對象，然后分析數(shù)據(jù)對象中各元素之間的邏輯關(guān)系，在確定數(shù)據(jù)的邏輯結(jié)構(gòu)后，適當選取數(shù)據(jù)的存儲結(jié)構(gòu)，再考慮存儲結(jié)構(gòu)的基本操作實現(xiàn)。在此基礎(chǔ)上，建立數(shù)據(jù)的對象模型。

1.ADT（Abstract Data Type）是建立數(shù)據(jù)對象模型的最好工具。狹義的數(shù)據(jù)結(jié)構(gòu)定義只涉及到數(shù)據(jù)的表示和邏輯關(guān)系。但數(shù)據(jù)結(jié)構(gòu)的完整性描述應(yīng)該包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)以及數(shù)據(jù)的運算。ADT是指一個數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。用ADT創(chuàng)建數(shù)據(jù)對象時，強調(diào)的是數(shù)據(jù)的本質(zhì)特征、數(shù)據(jù)所能完成的功能以及數(shù)據(jù)的外部接口。抽象數(shù)據(jù)類型ADT可用三元組（D，S，P）表示。其中，D是數(shù)據(jù)對象；S是D上的關(guān)系集；P是基于D的基本操作集。數(shù)據(jù)類型是高級語言中已經(jīng)實現(xiàn)的基本數(shù)據(jù)結(jié)構(gòu)。抽象數(shù)據(jù)類型的概念，是數(shù)據(jù)類型概念的擴展和進一步應(yīng)用。利用已經(jīng)實現(xiàn)的基本數(shù)據(jù)類型來擴展新的數(shù)據(jù)類型，從而實現(xiàn)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。例如傳統(tǒng)C語言中的棧、隊列、樹、二叉樹和圖等復(fù)雜數(shù)據(jù)類型，就要用到抽象數(shù)據(jù)類型的概念去實現(xiàn)。所以，抽象數(shù)據(jù)類型ADT是數(shù)據(jù)結(jié)構(gòu)中創(chuàng)建數(shù)據(jù)對象模型的理想工具。從某種意義上說，數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)就是抽象數(shù)據(jù)類型的設(shè)計與實現(xiàn)。無論是C語言描述的數(shù)據(jù)結(jié)構(gòu)還是C++描述的數(shù)據(jù)結(jié)構(gòu)，在分析和創(chuàng)建數(shù)據(jù)對象的本質(zhì)上是完全一致的，都是將數(shù)據(jù)的靜態(tài)屬性和動態(tài)方法（基本操作）進行統(tǒng)一封裝，只是實現(xiàn)的方法不同而已。

2.認識已有的數(shù)據(jù)對象，分析數(shù)據(jù)的本質(zhì)特征，為數(shù)據(jù)的選取和組織打下良好的基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)課程中為我們提供了許多已有的數(shù)據(jù)對象模型，如順序表、單鏈表、順序棧、循環(huán)隊列、二叉樹、鄰接表圖、哈希表等。學(xué)習(xí)、領(lǐng)會并實現(xiàn)這些數(shù)據(jù)對象模型，是應(yīng)用數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵。許多復(fù)雜的數(shù)據(jù)對象的操作都可以由基本操作實現(xiàn)。例如，ADT List描述了線性表結(jié)構(gòu)及其基本操作的邏輯定義，建立了線性表的一個數(shù)據(jù)模型。利用上述定義的基本操作可以實現(xiàn)線性表其他更加復(fù)雜的操作。值得注意的是，在應(yīng)用實踐中，盡管已經(jīng)分析和確定了問題的數(shù)據(jù)對象模型，理清了數(shù)據(jù)之間的邏輯關(guān)系，但數(shù)據(jù)的存儲結(jié)構(gòu)的確定仍然十分重要，影響著算法的運行效率。例如，同樣是有序表，但有序順序表、有序鏈表、有序二叉樹所適應(yīng)的算法顯然不同。實際應(yīng)用中，面對一個比較復(fù)雜的問題，為了問題的求解，還應(yīng)綜合運用已有的數(shù)據(jù)對象知識。例如，為了提高查找的效率，采用哈希表組織數(shù)據(jù)時，應(yīng)用線性探測再散列或應(yīng)用鏈地址法解決沖突，其算法效率是不同的。分析證明，鏈地址法解決沖突要優(yōu)于線性探測再散列。如果數(shù)據(jù)空間不是問題的話，最好采用鏈地址法解決沖突較好。這就要求我們，既要有哈希表的數(shù)據(jù)對象知識，又要有鏈表的數(shù)據(jù)對象知識。

3.設(shè)計與實現(xiàn)新的數(shù)據(jù)對象，以便解決更加復(fù)雜的問題。盡管數(shù)據(jù)結(jié)構(gòu)的類型很多，但基本操作一般都具有共同的特性。歸納起來，數(shù)據(jù)結(jié)構(gòu)中的基本操作可分為四類：創(chuàng)建和銷毀結(jié)構(gòu)類，包括數(shù)據(jù)結(jié)構(gòu)的創(chuàng)建、初始化，以及必要的銷毀結(jié)構(gòu)操作；屬性操作類，包括讀取或設(shè)置數(shù)據(jù)結(jié)構(gòu)中的各基本屬性的值；查找類，包括特定查找和遍歷操作；更新類，包括插入、刪除或修改數(shù)據(jù)元素的內(nèi)容或更新關(guān)系。有了上述知識，我們就可以根據(jù)問題的數(shù)據(jù)特性，應(yīng)用ADT開發(fā)出用于解決實際問題的新的數(shù)據(jù)類型。例如線段樹、二進制堆、多重索引鏈表等數(shù)據(jù)對象的應(yīng)用。課程實驗是設(shè)計與實現(xiàn)數(shù)據(jù)對象模型的最好實訓(xùn)手段。實驗課題的基本內(nèi)容包括線性表類應(yīng)用實驗、棧和隊列類應(yīng)用實驗、樹和圖類應(yīng)用實驗、查找和排序類應(yīng)用實驗以及自主研究性應(yīng)用實驗等。課程實驗的課題類型有驗證性實驗、應(yīng)用性實驗和創(chuàng)新設(shè)計性實驗。根據(jù)課程學(xué)時和學(xué)生特點，驗證性實驗屬于學(xué)生自主研究性學(xué)習(xí)的課下實驗，設(shè)計應(yīng)用性試驗和自主創(chuàng)新性實驗是課上實驗。通過課程實驗，真正創(chuàng)建以驗證性實驗為基礎(chǔ)，以設(shè)計應(yīng)用性實驗為中心，以自主創(chuàng)新性實驗為提高的課程實驗機制。

四、應(yīng)用問題抽象，建立問題的數(shù)學(xué)模型

當面對一個新的復(fù)雜問題時，不易直接求解，通常的想法是通過對問題的分析，不斷地抽象和分解、轉(zhuǎn)化或轉(zhuǎn)換，得到一個與原問題本質(zhì)相同的，可以采用計算機及其相關(guān)技術(shù)求解的，但看起來相對簡單的一個問題。把初始的問題或?qū)ο蠓Q為原型，把抽象分解后的理想化對象稱為數(shù)學(xué)模型。一個實際問題的數(shù)學(xué)模型建立后必須以一定的技術(shù)手段，如推理證明、計算、模擬等進行檢驗。如果所建數(shù)學(xué)模型不符合實際情況，就必須修改問題的數(shù)學(xué)模型。與實際問題相比，數(shù)學(xué)模型具有等價性、抽象性、高效性、可類比性等特點。這也是用計算思維求解問題的精髓所在。對于一些簡單的問題，往往只靠數(shù)據(jù)對象模型的建立，就可以解決問題，這時的數(shù)據(jù)對象模型，實質(zhì)上就是問題的數(shù)學(xué)模型。但對于許多復(fù)雜的問題，僅有數(shù)據(jù)對象模型還是不夠的，必須在問題定義和分析的基礎(chǔ)上，建立問題的數(shù)學(xué)模型才能求解。這也是數(shù)據(jù)結(jié)構(gòu)課程教學(xué)的特點。建立數(shù)學(xué)模型的本質(zhì)是挖掘數(shù)據(jù)間的關(guān)系和數(shù)據(jù)的變化規(guī)律。在建模時，如果能夠在繁雜的數(shù)據(jù)中找到有價值的線索，并加以合理應(yīng)用，往往可使問題獲得簡化，便于問題的解決。建立數(shù)學(xué)模型沒有固定的套路可言，方法比較多樣化。通常的建模方法可分為直接設(shè)計法、分類設(shè)計法和歸納設(shè)計法三種形式。直接設(shè)計法是直接對問題對象進行考察的設(shè)計方法。直接設(shè)計法需要解題者大膽猜想解題方法，并結(jié)合目標反復(fù)嘗試，調(diào)整方案和使用數(shù)學(xué)推理證明。分類設(shè)計法，簡單說，就是在分類的基礎(chǔ)上進行設(shè)計。歸納法利用了歸納的思想，是模型設(shè)計的一個經(jīng)典的實現(xiàn)形式。數(shù)據(jù)結(jié)構(gòu)中常見的數(shù)學(xué)模型一般有樹形模型、圖論模型、集合模型和排序模型等。例如，最小代價生成樹問題。問題的定義是：在n個城市之間修建高速公路網(wǎng)，如何修建使得總的工程費用為最省。問題的定義很明白，接下來是分析問題。這里有兩個特征含義，一個含義是最小生成樹問題，即若使得n個城市連通，僅需要n-1條邊就足夠了，當然，這n-1條邊需要連接n個城市；另一個含義是最小代價問題，即n-1條邊所構(gòu)成的最小生成樹的各邊代價之和為最小。顯然，n個城市及其之間的數(shù)據(jù)聯(lián)系可以用圖形結(jié)構(gòu)來表示，但這不足以解決實際問題。所以，必須靠MST性質(zhì)，利用最小生成樹的原理來解決。可以用數(shù)學(xué)來證明MST性質(zhì)是完全正確的。因此，這個問題是典型的最小代價生成樹模型。像光纖網(wǎng)絡(luò)鋪設(shè)、校園道路修建、城市觀光導(dǎo)游等問題都屬于此類問題。課程設(shè)計是設(shè)計與實現(xiàn)問題的數(shù)學(xué)模型的最好實訓(xùn)手段。課程設(shè)計是指對理論課程的核心知識點以及能力結(jié)構(gòu)的綜合技能的專業(yè)訓(xùn)練。依據(jù)培養(yǎng)目標的能力結(jié)構(gòu)，遵從教育規(guī)律和認知規(guī)律，將課程設(shè)計的課題項目分級分類設(shè)計，以促進學(xué)生的階梯式發(fā)展。課程設(shè)計的課題包括：綜合訓(xùn)練性題目和研究學(xué)習(xí)性及創(chuàng)新設(shè)計性題目兩大類。例如，立體化停車場管理、電梯運行模擬、哈夫曼壓縮軟件設(shè)計、二進制堆及其應(yīng)用、線段樹及其應(yīng)用等。

五、應(yīng)用計算機，實現(xiàn)問題求解的算法

數(shù)據(jù)結(jié)構(gòu)中的數(shù)學(xué)模型一般是指能夠應(yīng)用窮舉法、貪心法、分治法、回溯法和分支法等處理的問題模型。數(shù)學(xué)建模最重要的步驟是建立數(shù)學(xué)模型和求解數(shù)學(xué)模型，如果說建立數(shù)學(xué)模型的過程更多地是依賴數(shù)學(xué)基礎(chǔ)，求解數(shù)學(xué)模型則更多地是依靠應(yīng)用計算機。正因為有了計算機，有了計算機網(wǎng)絡(luò)，才有了今天計算思維的認同與發(fā)展。在對問題求解的過程中，必須對問題的數(shù)學(xué)模型完成算法的設(shè)計與實現(xiàn)。首先是根據(jù)數(shù)學(xué)模型，確定適當?shù)挠嬎悴呗?，選取合適的算法。因為不同的算法對結(jié)果的復(fù)雜性和穩(wěn)定性影響很大。其次是根據(jù)問題的算法，編寫計算機程序。這時要應(yīng)用數(shù)據(jù)對象模型，因為同一個問題，使用不同的數(shù)據(jù)結(jié)構(gòu)，編寫出的程序也會差別很大。

1.對同一個問題，往往可以用不同的算法求解，在選擇求解算法的過程中，可以很好地進行計算思維能力的訓(xùn)練。以最小代價生成樹問題的求解為例。假如是n個城市的連通圖，數(shù)據(jù)對象是圖形結(jié)構(gòu)，數(shù)學(xué)模型是最小代價生成樹。若應(yīng)用窮舉法，需對n個城市進行n！次全排列，求解每種排列的代價之和進行比較，從而找出問題的最小代價。若應(yīng)用貪心法，對稠密圖，采用prim算法，首先任選一個頂點，以后每次從剩余的頂點中選擇另外一個頂點，附加一條邊，只要滿足添加的邊的代價之和為當前最小即可。如此，直到選擇了n個頂點，當然也包括n-1條邊。若采用分治法，對稀疏圖，可以采用破圈算法，對于n個頂點的連通圖，實行減一分治?，F(xiàn)將m條邊按代價大小非遞增排列，然后從中按順序考慮每一條邊，只要判斷減掉該邊后，該圖任然連通且所剩邊數(shù)目大于n-1即可。若采用回溯法或分支法，同樣可以得到問題的答案，其原理類同窮舉法，不再贅述。隨著數(shù)據(jù)規(guī)模的增大，究竟哪一種算法是最優(yōu)的，可以用算法的時間復(fù)雜性和空間復(fù)雜性綜合衡量。顯然，應(yīng)用計算機，為最優(yōu)算法的選擇提供了可能。

2.對同一個問題，往往可以用不同的數(shù)據(jù)結(jié)構(gòu)，進而采用不同的算法求解，同樣可以很好地進行計算思維能力的訓(xùn)練。以四則運算表達式求值問題的求解為例。假如四則運算表達式的形式為字符串，表達式存儲在數(shù)組中。數(shù)學(xué)模型是后綴表達式。問題的定義是，十進制整數(shù)的四則運算求解。若采用順序棧進行問題求解，則數(shù)據(jù)對象是特殊線性表的順序棧?？梢圆捎煤缶Y表達式的求解算法。算法的執(zhí)行過程是，每次應(yīng)用一個順序棧，共應(yīng)用兩次順序棧。第一次將表達式轉(zhuǎn)換成后綴式，第二次，對轉(zhuǎn)換后的后綴表達式求值。若采用二叉樹進行問題求解，則求解過程同樣可以用到棧，數(shù)據(jù)對象是二叉樹和順序棧。算法的執(zhí)行過程是，每次應(yīng)用一個順序棧，共應(yīng)用兩次順序棧。第一次將表達式轉(zhuǎn)換成二叉樹，第二次，對轉(zhuǎn)換后的二叉樹進行后序遍歷（后綴表達式）求值。若采用有向無環(huán)圖進行問題求解，則求解過程同樣可以用到棧，數(shù)據(jù)對象是圖結(jié)構(gòu)和棧。算法的執(zhí)行過程是，應(yīng)用一個順序棧，第一次將表達式轉(zhuǎn)換成二叉有向無環(huán)圖，第二次，對轉(zhuǎn)換后的有向無環(huán)圖進行后序遍歷（后綴表達式）求值。不同的數(shù)據(jù)結(jié)構(gòu)，可以采用不同的算法，算法的時間復(fù)雜性和空間復(fù)雜性可能不同。隨著數(shù)據(jù)規(guī)模的增大，究竟哪一種算法是最優(yōu)的，可以應(yīng)用計算機為最優(yōu)算法的選擇提供求解。將一個問題用多種思路、多種數(shù)據(jù)結(jié)構(gòu)、多種算法求解，可以發(fā)展學(xué)生計算思維能力的靈活性，培養(yǎng)學(xué)生計算思維能力的習(xí)慣性。

3.計算思維能力的培養(yǎng)離不開上機實踐訓(xùn)練。加強實踐性教學(xué)，是提高學(xué)生計算思維能力的重要手段。在數(shù)據(jù)結(jié)構(gòu)實踐課程教學(xué)中，將項目教學(xué)法應(yīng)用到課程實驗和課程設(shè)計等各個教學(xué)活動中，通過課題的立項與開題、組建課題小組、方案分析、方案設(shè)計、方案實現(xiàn)和項目驗收的工作流程對學(xué)生進行計算思維能力培養(yǎng)的工程實踐訓(xùn)練。誠然，計算思維是概念化，不是程序化。計算思維的實現(xiàn)也不等同于計算機編程。但是，不可否認的是，應(yīng)用計算機來解決具體問題時，把算法思想變成可執(zhí)行的程序代碼是驗證算法的有效性和解決問題的最好方法。例如，應(yīng)用計算機解決數(shù)據(jù)的排序問題。假設(shè)，數(shù)據(jù)是整型數(shù)據(jù)，存儲在順序表中。將一個無序的整數(shù)序列轉(zhuǎn)換成有序序列，方法很多。傳統(tǒng)的方法有插入排序、選擇排序和交換排序，改進后優(yōu)化的排序方法有希爾排序、快速排序和堆排序。但優(yōu)化后的排序方法的穩(wěn)定性都不好。若忽略數(shù)據(jù)的空間性能，時間性能又好且穩(wěn)定性又高的方法首選歸并排序。不過，歸并排序又與數(shù)據(jù)的初始狀態(tài)無關(guān)，無法體現(xiàn)最好的排序性能。而且，除了采用順序表排序外，還可以采用二叉樹排序，甚至采用非關(guān)鍵字比較方法的基數(shù)排序。究竟采用何種排序方法，有了計算機的使用，問題性能的比較和算法的選擇可以迎刃而解。實踐證明，學(xué)生對將多種數(shù)據(jù)結(jié)構(gòu)應(yīng)用于一個復(fù)雜問題的解決，有很高的積極性。

六、結(jié)束語

本文以Wing教授的計算思維為引入，以計算思維在數(shù)據(jù)結(jié)構(gòu)中的實踐探索為主線，以培養(yǎng)計算思維能力的實踐為重點，努力探討如何將計算思維的能力培養(yǎng)融入到平日的課程教學(xué)中。本文討論了計算思維與數(shù)據(jù)結(jié)構(gòu)的關(guān)系，從計算思維的抽象與自動化的本質(zhì)出發(fā)，以數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)對象建模和問題數(shù)學(xué)建模為線索，對如何在數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)中，用計算機處理海量數(shù)據(jù)并實現(xiàn)算法，從而進行計算思維能力的培養(yǎng)做了深入探討。

參考文獻

[1]Wing J M.Computational Thinking.Communications of the ACM，2006，49（3）：33-35.

[2]教育部高等學(xué)校計算機科學(xué)與技術(shù)專業(yè)教學(xué)指導(dǎo)委員會.高等學(xué)校計算機科學(xué)與技術(shù)專業(yè)人才專業(yè)能力構(gòu)成與培養(yǎng)[M].北京：機械工業(yè)出版社，2010.

[3]Mark M.Meerschaert.數(shù)學(xué)建模方法與分析[M].第2版.劉來福，楊淳，黃海洋，譯.北京：機械工業(yè)出版社，2005.

[4]孟凡榮，賈杰，王興偉.網(wǎng)絡(luò)工程專業(yè)創(chuàng)新性實踐課程體系構(gòu)建與實施[J].計算機教育，2013，（194）14：104-108.

[5]劉昕，石樂義，元雪東.面向計算思維的數(shù)據(jù)結(jié)構(gòu)課程教學(xué)改革[J].計算機教育，2013，（196）16：35-38.