羅先錄 周富肯 艾廣燚 向燕飛

摘? 要：計(jì)算機(jī)類專業(yè)的學(xué)生掌握編程解決問題的基本技能，是基本的專業(yè)素質(zhì)。算法是程序設(shè)計(jì)的靈魂，是用系統(tǒng)方法描述解決問題的方法，是從編程通向計(jì)算思維的必由之路。計(jì)算機(jī)類專業(yè)的“系統(tǒng)能力”，是計(jì)算機(jī)類專業(yè)相較于其他專業(yè)的核心競(jìng)爭(zhēng)力。本文總結(jié)了六年來(lái)采用不同編程語(yǔ)言進(jìn)行教學(xué)的比較，討論了如何貫通專業(yè)學(xué)生的這些專業(yè)基本素質(zhì)和核心能力，為我們進(jìn)行教學(xué)時(shí)編程語(yǔ)言選擇提供了基于系統(tǒng)能力的可行方案。

關(guān)鍵詞：程序設(shè)計(jì);數(shù)據(jù)結(jié)構(gòu)與算法;計(jì)算機(jī)系統(tǒng);編程語(yǔ)言

中圖分類號(hào)：TP312? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： It is a professional quality for learners of computer majors to master basic skills of problem solving with programming. Algorithm， the soul of program design， is a stepwise procedure for solving problems systematically， and is the only access to computational thinking. "System Ability" is the core competitiveness of computer majors compared with other majors. This paper summarizes and compares teaching with different programming languages over the past six years， and then discusses how to enhance both professional qualities and core abilities of computer major students. The result of the paper provides a feasible scheme for programming language selection of teaching for cultivation of students' system capability.

Keywords： program design; data structure; algorithm; computer systems; programming language

1? ?引言（Introduction）

數(shù)據(jù)結(jié)構(gòu)與算法課程曾經(jīng)用偽代碼教學(xué)，旨在掌握算法思維本身。現(xiàn)在基本采用一門具體的編程語(yǔ)言進(jìn)行教學(xué)，可能是Linus Torvalds說：“Talk is cheap，show me the code.”，也可能是程序執(zhí)行時(shí)間比算法復(fù)雜度分析更有感覺。當(dāng)前計(jì)算機(jī)系統(tǒng)能力的培養(yǎng)也是一個(gè)倒逼的動(dòng)力，因?yàn)轶w驗(yàn)代碼的執(zhí)行、調(diào)試程序的bug，是讓學(xué)生深入理解計(jì)算機(jī)系統(tǒng)，加強(qiáng)工程能力培養(yǎng)的必由之路[1-4]。

目前，計(jì)算機(jī)類專業(yè)的程序設(shè)計(jì)基礎(chǔ)和數(shù)據(jù)結(jié)構(gòu)與算法這兩門課程的教學(xué)，選擇同一門編程語(yǔ)言進(jìn)行兩門課程的連續(xù)教學(xué)是較好的選擇。這樣為學(xué)生“學(xué)好一門編程語(yǔ)言”+“計(jì)算思維”這個(gè)主線提供了很好的條件[5]。

那么是讓學(xué)生自主選擇課程的這一門編程語(yǔ)言，還是根據(jù)專業(yè)課程體系的需要進(jìn)行設(shè)定，這是我們進(jìn)行課程體系設(shè)計(jì)的時(shí)候容易引起爭(zhēng)論的話題。我們根據(jù)TIOBE編程語(yǔ)言排行榜以及網(wǎng)上招聘和地區(qū)人才需求，“所學(xué)即所用”“一點(diǎn)打透”等原則，在學(xué)生中試行了學(xué)生自由選擇排名前列的幾種編程語(yǔ)言進(jìn)行這兩門課程的教學(xué)。現(xiàn)在根據(jù)計(jì)算機(jī)系統(tǒng)能力建設(shè)的趨勢(shì)，回歸了簡(jiǎn)單的C語(yǔ)言路線。這又會(huì)讓人想起發(fā)明C語(yǔ)言的Dennis M. Richie說：“Keep it simple stupid”[6]。我們做了一些思考和總結(jié)，供專家和同行們參考。

2? 面向?qū)ο缶幊陶Z(yǔ)言的特點(diǎn)（Characteristics of object oriented programming language）

我們以Java語(yǔ)言為例來(lái)說明用面向?qū)ο缶幊陶Z(yǔ)言來(lái)進(jìn)行程序設(shè)計(jì)基礎(chǔ)+數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)的特點(diǎn)。Java的優(yōu)勢(shì)在于實(shí)現(xiàn)了面向?qū)ο蟮闹饕夹g(shù)（封裝、繼承與多態(tài)、接口等），而放棄了容易引起混亂的技術(shù)（例如多繼承）。

（1）封裝。在數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)中，數(shù)據(jù)抽象是首先要面對(duì)的主題?，F(xiàn)在的面向?qū)ο蠹夹g(shù)已經(jīng)很成熟，如果選擇將數(shù)據(jù)成員（數(shù)據(jù)結(jié)構(gòu)）設(shè)為私有屬性隱藏起來(lái)，通過調(diào)用公有成員方法（算法）訪問私有數(shù)據(jù)，Java完成了定義自己的數(shù)據(jù)類型（數(shù)據(jù)抽象）和對(duì)這些數(shù)據(jù)操作的封裝。數(shù)據(jù)類型和相關(guān)操作（算法）有了密切相關(guān)性，定義了一個(gè)類的數(shù)據(jù)成員（數(shù)據(jù)結(jié)構(gòu)）之后，相應(yīng)的算法就是同一個(gè)類中的各種方法，就可以創(chuàng)建對(duì)象，以及派生出更多的細(xì)分、實(shí)用的類。

（2）泛型。泛型是Java 5以上版本提供的支持這一目標(biāo)的方式之一。泛型也就是參數(shù)化類型，例如Stack是某種元素的棧，而Stack處理的就是String對(duì)象。同理，Queue就是處理Date對(duì)象[7]。

算法中經(jīng)常需要進(jìn)行對(duì)象的大小比較，一般采用兩種方法實(shí)現(xiàn)泛型，從而實(shí)現(xiàn)對(duì)象間可比較。一是用Object表示泛型，二是用Comparable接口類型表示泛型。用Comparable接口類型表示泛型時(shí)（從JDK 1.5開始，在java.lang.Comparable中使用了泛型），需要定義對(duì)象為Comparable接口的實(shí)例，然后調(diào)用Comparable的compareTo方法（需要重寫）就可以進(jìn)行對(duì)象間的比較操作[8]。

3.3? ?計(jì)算機(jī)系統(tǒng)角度的C語(yǔ)言

從程序員角度的計(jì)算機(jī)系統(tǒng)看，C語(yǔ)言版本的優(yōu)勢(shì)還在于可以深刻理解計(jì)算機(jī)系統(tǒng)，這個(gè)是當(dāng)前計(jì)算機(jī)教育的一個(gè)趨勢(shì)[1-3]。2010年，教育部高等學(xué)校計(jì)算機(jī)類專業(yè)教學(xué)指導(dǎo)會(huì)組織高校的資深計(jì)算機(jī)教育專家成立“計(jì)算機(jī)類專業(yè)系統(tǒng)能力培養(yǎng)研究專家組”，研究組經(jīng)過對(duì)國(guó)內(nèi)外計(jì)算機(jī)專業(yè)的課程體系、用人單位的需求及技術(shù)的發(fā)展，提出了“計(jì)算機(jī)類專業(yè)系統(tǒng)能力培養(yǎng)專業(yè)課程體系”。并分批設(shè)立了試點(diǎn)高校。如果是計(jì)算機(jī)系統(tǒng)能力試點(diǎn)學(xué)校，就會(huì)了解目前所有的計(jì)算機(jī)系統(tǒng)基礎(chǔ)之類的課程和教材，都是采用了C語(yǔ)言舉例[1，2] ，特別是其中最著名的CMU教材《深入理解計(jì)算機(jī)系統(tǒng)》就是采用了C語(yǔ)言作為例子貫穿整個(gè)教學(xué)[10]。我們以南京大學(xué)袁春風(fēng)《計(jì)算機(jī)系統(tǒng)基礎(chǔ)》為主教材，同時(shí)參考CMU的《深入理解計(jì)算機(jī)系統(tǒng)》，加入了第四批試點(diǎn)高校行列。我們結(jié)合這幾年進(jìn)行程序設(shè)計(jì)基礎(chǔ)+數(shù)據(jù)結(jié)構(gòu)，以及后續(xù)的計(jì)算機(jī)系統(tǒng)基礎(chǔ)課程這三門課連續(xù)教學(xué)中的一些主要概念的逐級(jí)提升或者延伸、最后得以澄清的經(jīng)驗(yàn)體會(huì)來(lái)說明這個(gè)選擇的優(yōu)點(diǎn)。

構(gòu)的訪問 數(shù)組和指針（結(jié)構(gòu)體、鏈表） 線性表、棧、隊(duì)列、樹和圖等抽象數(shù)據(jù)類型等都有兩種結(jié)構(gòu)的實(shí)現(xiàn)方式 順序?qū)崿F(xiàn)的數(shù)組首地址以及循環(huán)模式和鏈?zhǔn)綄?shí)現(xiàn)的鏈?zhǔn)皆L問模式的比較 在匯編代碼級(jí)理解各種數(shù)據(jù)訪問模式的本質(zhì)

棧（stack） 在調(diào)試運(yùn)行遞歸函數(shù)時(shí)觀察調(diào)用的函數(shù)棧 LIFO問題的解決模式，熟悉棧的底層實(shí)現(xiàn)和運(yùn)用 操作系統(tǒng)的棧是一個(gè)特定內(nèi)存區(qū)域，和數(shù)據(jù)結(jié)構(gòu)的棧一樣遵循先進(jìn)后出的規(guī)則 數(shù)據(jù)結(jié)構(gòu)的棧和操作系統(tǒng)函數(shù)調(diào)用棧的區(qū)別、函數(shù)調(diào)用棧的耗時(shí)和溢出是線索

堆（heap） 動(dòng)態(tài)內(nèi)存分配函數(shù)malloc/free（面向?qū)ο缶幊陶Z(yǔ)言的new）的使用 一種特殊的二叉樹數(shù)據(jù)結(jié)構(gòu)，以數(shù)組方式連續(xù)存儲(chǔ) 操作系統(tǒng)的堆是一個(gè)特定的動(dòng)態(tài)內(nèi)存分配區(qū)域（運(yùn)行時(shí)才知道大小需求） 操作系統(tǒng)的堆（棧）強(qiáng)調(diào)數(shù)據(jù)生命周期，而數(shù)據(jù)結(jié)構(gòu)的堆（棧）強(qiáng)調(diào)數(shù)據(jù)組織

排序算法

中的歸并

排序 多項(xiàng)式加法等簡(jiǎn)單運(yùn)用 遞歸實(shí)現(xiàn)或者非遞歸實(shí)現(xiàn) 額外空間的分配，需要理解內(nèi)存的分配和回收的代價(jià) 從系統(tǒng)角度理解“以空間換時(shí)間”和“以時(shí)間換空間”的權(quán)衡

堆排序和

快速排序

比較 兩個(gè)變量比較和交換的方法 對(duì)于同樣的數(shù)據(jù)，排序過程中，堆排序算法的交換次數(shù)要多于快速排序 快速排序中數(shù)據(jù)是局部順序訪問，堆排序是跳躍訪問，對(duì)CPU緩存不友好 從系統(tǒng)角度理解算法快慢的根本原因

文件 文件建立/打開/關(guān)閉、讀/寫、文件指針移動(dòng) 內(nèi)部排序和外部排序 Cache、內(nèi)存、I/O的讀寫 Cache/內(nèi)存/硬盤等存儲(chǔ)層次結(jié)構(gòu)的效率和配合

這樣的例子還可以不斷總結(jié)很多，運(yùn)用C語(yǔ)言實(shí)現(xiàn)的例子，就很容易闡述清楚這些概念背后的內(nèi)涵與延伸，讓學(xué)生深入理解計(jì)算機(jī)系統(tǒng)的運(yùn)行機(jī)制，逐步形成計(jì)算機(jī)專業(yè)的核心能力。

4? ?結(jié)論（Conclusion）

對(duì)于一般專業(yè)學(xué)生來(lái)說，面向解決問題的模式，學(xué)會(huì)一種編程語(yǔ)言后進(jìn)一步學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)，用一種語(yǔ)言學(xué)習(xí)這兩門課程是一個(gè)很順利的學(xué)習(xí)進(jìn)階道路，目前的教材和師資的成熟度也支持這樣的做法。對(duì)于計(jì)算機(jī)類專業(yè)學(xué)生來(lái)說，用C語(yǔ)言進(jìn)行這兩門課程的學(xué)習(xí)，對(duì)于后續(xù)專業(yè)核心課程的學(xué)習(xí)，將會(huì)起到很好地理解與掌握計(jì)算機(jī)系統(tǒng)的作用。特別是目前的計(jì)算機(jī)教育更強(qiáng)調(diào)計(jì)算機(jī)系統(tǒng)能力的培養(yǎng)的形勢(shì)下，更是一個(gè)必然的選擇。

參考文獻(xiàn)（References）

[1] 王志英，周興社，袁春風(fēng)，等.計(jì)算機(jī)專業(yè)學(xué)生系統(tǒng)能力培養(yǎng)和系統(tǒng)課程體系設(shè)置研究[J].計(jì)算機(jī)教育，2013（09）：1-6.

[2] 臧斌宇，彭遠(yuǎn)紅.反思、借鑒、融合、提升—探尋計(jì)算機(jī)系統(tǒng)能力培養(yǎng)之道[J].計(jì)算機(jī)教育，2015（21）：1-2.

[3] 袁春風(fēng)，王帥.大學(xué)計(jì)算機(jī)專業(yè)教育應(yīng)重視“系統(tǒng)觀”培養(yǎng)[J].中國(guó)大學(xué)教學(xué)，2013（12）：41-46.

[4] 尚鳳軍.面向計(jì)算機(jī)系統(tǒng)能力培養(yǎng)的課程和實(shí)踐體系研究[C]. Proceedings of the 3rd International Conference on Applied Social Science Research（ICASSR 2015）， 2015：4-5.

[5] 湯偉.《數(shù)據(jù)結(jié)構(gòu)》和《C語(yǔ)言程序設(shè)計(jì)》新教學(xué)模式研究[J].科技資訊，2017，15（24）：170-171.

[6] Brian W. kernighan， Dennis M. Ritchie. The C Programming Language（Second Edition）[M]. New Jersey：Pearson Education International，1998：23-189.

[7] Robert Sedgewick， Kevin Wayne. 謝路云，譯.算法（第4版）[M].北京：人民郵電出版社，2014：38-107.

[8] 劉小晶，杜選，朱蓉，等.數(shù)據(jù)結(jié)構(gòu)-Java語(yǔ)言描述[M].北京：清華大學(xué)出版社，2015：23-64.

[9] 陳越，何欽銘，徐鏡春，等.數(shù)據(jù)結(jié)構(gòu)（第二版）[M].北京：高等教育出版社，2019：73-276.

[10] Randal E. Bryant， David R. O'Hallarond. 龔奕利，賀蓮，譯.深入理解計(jì)算機(jī)系統(tǒng)[M].北京：機(jī)械工業(yè)出版社，2018：99-276.