孟凡榮 張斌 楊雷

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

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

中圖分類號(hào)：G642.0 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1674-9324（2015）10-0117-04

一、引言

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

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

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

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

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

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

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

3.設(shè)計(jì)與實(shí)現(xiàn)新的數(shù)據(jù)對(duì)象，以便解決更加復(fù)雜的問(wèn)題。盡管數(shù)據(jù)結(jié)構(gòu)的類型很多，但基本操作一般都具有共同的特性。歸納起來(lái)，數(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)系。有了上述知識(shí)，我們就可以根據(jù)問(wèn)題的數(shù)據(jù)特性，應(yīng)用ADT開(kāi)發(fā)出用于解決實(shí)際問(wèn)題的新的數(shù)據(jù)類型。例如線段樹(shù)、二進(jìn)制堆、多重索引鏈表等數(shù)據(jù)對(duì)象的應(yīng)用。課程實(shí)驗(yàn)是設(shè)計(jì)與實(shí)現(xiàn)數(shù)據(jù)對(duì)象模型的最好實(shí)訓(xùn)手段。實(shí)驗(yàn)課題的基本內(nèi)容包括線性表類應(yīng)用實(shí)驗(yàn)、棧和隊(duì)列類應(yīng)用實(shí)驗(yàn)、樹(shù)和圖類應(yīng)用實(shí)驗(yàn)、查找和排序類應(yīng)用實(shí)驗(yàn)以及自主研究性應(yīng)用實(shí)驗(yàn)等。課程實(shí)驗(yàn)的課題類型有驗(yàn)證性實(shí)驗(yàn)、應(yīng)用性實(shí)驗(yàn)和創(chuàng)新設(shè)計(jì)性實(shí)驗(yàn)。根據(jù)課程學(xué)時(shí)和學(xué)生特點(diǎn)，驗(yàn)證性實(shí)驗(yàn)屬于學(xué)生自主研究性學(xué)習(xí)的課下實(shí)驗(yàn)，設(shè)計(jì)應(yīng)用性試驗(yàn)和自主創(chuàng)新性實(shí)驗(yàn)是課上實(shí)驗(yàn)。通過(guò)課程實(shí)驗(yàn)，真正創(chuàng)建以驗(yàn)證性實(shí)驗(yàn)為基礎(chǔ)，以設(shè)計(jì)應(yīng)用性實(shí)驗(yàn)為中心，以自主創(chuàng)新性實(shí)驗(yàn)為提高的課程實(shí)驗(yàn)機(jī)制。

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

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

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

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

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

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

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

六、結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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