數(shù)據(jù)驅(qū)動的數(shù)據(jù)結(jié)構(gòu)課程案例設(shè)計研究與實踐

張安勤 田秀霞 張挺

摘? 要：我們在各行各業(yè)的諸多領(lǐng)域以及學(xué)習(xí)和生活中產(chǎn)生了大量的數(shù)據(jù)，現(xiàn)在的時代已經(jīng)是一個數(shù)據(jù)時代。文章分析了當(dāng)前數(shù)據(jù)結(jié)構(gòu)課程教學(xué)中存在的問題，結(jié)合當(dāng)前數(shù)據(jù)時代前沿研究領(lǐng)域和行業(yè)應(yīng)用，設(shè)計了單個知識點的案例和融合多個知識點的綜合案例。在此基礎(chǔ)上，對教學(xué)方法和考核方式進(jìn)行了改革。我們的教學(xué)改革拓展了學(xué)生的知識和技能，提高了學(xué)生分析和解決實際復(fù)雜問題的綜合素質(zhì)和創(chuàng)新能力。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu);數(shù)據(jù)驅(qū)動;案例設(shè)計;教學(xué)改革

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

Abstract：Lots of data are generated in many fields of our study and life.Our present time is the data era.This paper analyzes the main problems existing in the teaching of data structure course at present.Combined with frontier research fields and industrial applications in the current data era，this paper designs the course cases with a single knowledge point and comprehensive cases integrating multiple knowledge points.On this basis，the teaching methods and assessment methods are reformed.Our teaching reform has expanded students' knowledge and skills and has improved students' comprehensive quality and innovation ability to analyze and solve complex practical problems.

Keywords：data structure;data driven;case design;teaching reform

1? ?引言（Introduction）

數(shù)據(jù)結(jié)構(gòu)課程是計算機相關(guān)專業(yè)的專業(yè)基礎(chǔ)課程，在專業(yè)課程體系中起著承上啟下的作用。課程對培養(yǎng)學(xué)生的數(shù)據(jù)模型抽象能力、算法設(shè)計能力和復(fù)雜的程序設(shè)計能力具有重要的作用。課程所討論的知識內(nèi)容和算法技術(shù)，無論對于后續(xù)學(xué)習(xí)其他專業(yè)課程，或是將來從事軟件開發(fā)工作，都是必須掌握的基礎(chǔ)內(nèi)容[1]。

我們的各行各業(yè)學(xué)習(xí)和生活中的諸多領(lǐng)域產(chǎn)生了大量的數(shù)據(jù)，現(xiàn)在的時代已經(jīng)是一個數(shù)據(jù)時代，數(shù)據(jù)已經(jīng)成為一種新能源，對數(shù)據(jù)的存儲、處理，以及分析面臨著巨大的需求。

在這個數(shù)據(jù)時代，一方面，我們的《數(shù)據(jù)結(jié)構(gòu)》課程內(nèi)容仍然是前沿研究領(lǐng)域的重要基礎(chǔ);另一方面，這些基礎(chǔ)理論內(nèi)容也需要針對數(shù)據(jù)時代的新問題與新挑戰(zhàn)進(jìn)行調(diào)整和改革。但目前，我們的課程教學(xué)采用傳統(tǒng)主流數(shù)據(jù)結(jié)構(gòu)的知識講解，偽代碼描述算法，再附加一些課程實驗的教學(xué)模式，已無法適應(yīng)數(shù)據(jù)時代的需求和挑戰(zhàn)。因此，在《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)過程中，需要將課程基礎(chǔ)理論內(nèi)容與數(shù)據(jù)時代的特點相融合、與學(xué)界和業(yè)界前沿領(lǐng)域相融合，兼顧基礎(chǔ)知識與學(xué)科前沿、理論與實踐并重。

2? 教學(xué)中存在的問題及原因（Problems and reasons existing in the teaching ）

在數(shù)據(jù)結(jié)構(gòu)的實際教學(xué)中，存在的問題主要有兩種情況：

（1）學(xué)生基本理論聽得懂，算法理解和實現(xiàn)存在困難。甚至出現(xiàn)筆試分?jǐn)?shù)很高，但是實驗和課程設(shè)計環(huán)節(jié)無法完成算法實現(xiàn)和一個完整的應(yīng)用系統(tǒng)的情況。

（2）學(xué)生覺得學(xué)習(xí)內(nèi)容枯燥無味，對課程內(nèi)容沒興趣。

造成這種情況的原因主要有以下幾點：

（1）課程本身有難度，課程概念繁多、體系復(fù)雜、操作種類多以及部分算法難理解等特點[2]。

（2）受數(shù)據(jù)結(jié)構(gòu)傳統(tǒng)教學(xué)的影響，重視理論部分的課堂教學(xué)，輕視實踐環(huán)節(jié)。雖然近幾年，由于我校定位為應(yīng)用型本科大學(xué)，對實驗和實踐環(huán)節(jié)的重視情況有所改善，但是力度不夠，沒有具體的方法和措施。

（3）由于目前主流數(shù)據(jù)結(jié)構(gòu)教材中提供的都是偽代碼描述，學(xué)生無法看到完整的實現(xiàn)過程，不能產(chǎn)生直觀的印象，造成算法理解困難。這方面，目前筆者所在數(shù)據(jù)結(jié)構(gòu)教學(xué)團(tuán)隊已經(jīng)做了一些工作，把教材中的偽代碼已經(jīng)用Java語言完整地實現(xiàn)出來，并提供給學(xué)生。有些代碼在實驗課程中對學(xué)生進(jìn)行了演示、講解和分析。

（4）教材和實驗中的案例老套，沒有緊跟當(dāng)前學(xué)術(shù)和業(yè)界的最新發(fā)展，難以吸引學(xué)生的注意力，學(xué)生的學(xué)習(xí)和編碼沒有積極性。

《數(shù)據(jù)結(jié)構(gòu)》課程的教學(xué)目的是分析待解決問題數(shù)據(jù)的特性，選擇合適的邏輯結(jié)構(gòu)和相應(yīng)的存儲結(jié)構(gòu)以及相關(guān)算法，并能從時間和空間兩個角度來衡量算法的性能。因此在課程的內(nèi)容中必須有能夠體現(xiàn)從數(shù)據(jù)角度進(jìn)行分析，選擇邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和相應(yīng)算法，并對算法進(jìn)行衡量的案例。同時，對于面向應(yīng)用型的本科專業(yè)的學(xué)生來說，解決實際問題的能力尤為重要。因此，設(shè)計與當(dāng)前學(xué)術(shù)和業(yè)界最新發(fā)展和應(yīng)用結(jié)合的案例，不僅可以提高學(xué)生的課程學(xué)習(xí)的熱情，而且也可以在教學(xué)過程中培養(yǎng)學(xué)生的數(shù)據(jù)思維與學(xué)科前沿意識。

3? ?案例設(shè)計（Case design ）

3.1? ?案例設(shè)計的要求

案例需要滿足的要求：

（1）切合教學(xué)的知識點;

（2）與學(xué)界和業(yè)界前沿領(lǐng)域相融合;

（3）學(xué)生比較容易接受，能夠激發(fā)學(xué)生興趣。

根據(jù)以上要求，筆者所在教學(xué)團(tuán)隊根據(jù)教學(xué)的知識點設(shè)計了針對知識點的教學(xué)案例和融合各知識點的綜合案例，這些案例有的來源于學(xué)生的生活，有的來源于課程教學(xué)團(tuán)隊老師的科研項目[3]，這樣的和實際生活相聯(lián)系的項目[4]不僅能激發(fā)學(xué)生的興趣，而且和當(dāng)前數(shù)據(jù)時代的發(fā)展緊密結(jié)合。我們在實際教學(xué)過程中，配合案例教學(xué)，我們還對教學(xué)方法和考核方式進(jìn)行了改革。

3.2? ?結(jié)合知識點的教學(xué)案例

數(shù)據(jù)結(jié)構(gòu)課程的主要知識點有線性表、棧、隊列、串、二叉樹、圖、查找、排序。數(shù)據(jù)結(jié)構(gòu)教學(xué)團(tuán)隊設(shè)計的案例圍繞課程的主要知識點展開。

以案例班級社交網(wǎng)絡(luò)分析為例，同學(xué)收集整理了班級同學(xué)手機通話和短信數(shù)據(jù)、微信數(shù)據(jù)、QQ數(shù)據(jù)和郵件數(shù)據(jù)，對數(shù)據(jù)進(jìn)行了預(yù)處理，分析了數(shù)據(jù)的邏輯結(jié)構(gòu)，并選擇合適的存儲結(jié)構(gòu)，建立班級社交網(wǎng)絡(luò)，再按照一定算法找出核心人物、活躍人物和指定同學(xué)的交往圈子，并與實際情況對比。在這個過程中，他們不僅理解了數(shù)據(jù)處理的整個過程，也體會到了課程內(nèi)容在實際應(yīng)用和理論研究中的重要意義。

不同知識點的案例如下表1所示。

1 手機通訊錄管理 線性表線性表的順序存儲和鏈?zhǔn)酱鎯?手機通訊錄上的聯(lián)系人數(shù)據(jù)的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，手機聯(lián)系數(shù)據(jù)在手機中用順序表存儲和鏈表存儲時，實現(xiàn)插入、刪除和查找功能

2 分隔符匹配 棧的先進(jìn)后出，入棧和出棧 檢查字符串?dāng)?shù)據(jù)中分隔符是否左右匹配。分隔符包括大括號，中括號，小括號，每個分隔符都要左右進(jìn)行匹配，如果不匹配報錯并輸出不匹配位置

3 手機通話數(shù)據(jù)管理 隊列的先進(jìn)先出，入隊和出隊 手機通話數(shù)據(jù)可以分為三類：未接來電，已接來電和已撥電話。這三類數(shù)據(jù)按照事件發(fā)生的時間先后以隊列形式存儲和管理[5]

4 英文詞頻統(tǒng)計 串的概念、基本操作以及串的模式匹配算法 一首英文的歌詞或文章或小說的文本文件。從文件讀出字符串。將所有大寫轉(zhuǎn)換為小寫，將所有其他分隔符（替換為空格，分隔出一個一個的單詞，并統(tǒng)計單詞出現(xiàn)的次數(shù)

5 圖像的壓縮與解壓縮 二叉樹中的哈夫曼樹和哈夫曼編碼 圖像中每個灰度值出現(xiàn)的概率是不相同的，概率高的灰度值用短碼，概率低的灰度值用長碼，可以實現(xiàn)壓縮編碼。獲取圖像的灰度值，計算每個灰度值的頻率，構(gòu)造哈夫曼樹，進(jìn)行哈夫曼編碼和解碼，實現(xiàn)圖像的解壓縮

6 班級社交網(wǎng)絡(luò)分析 圖的構(gòu)建和圖的遍歷算法 收集班級同學(xué)之間的手機通話數(shù)據(jù)，短信數(shù)據(jù)，微信數(shù)據(jù)和QQ數(shù)據(jù)，建立班級同學(xué)社交網(wǎng)絡(luò)圖。查找核心同學(xué)，活躍同學(xué)，以及指定同學(xué)的交往圈子

7 警察找壞人 不同查找算法的思想 有m條包含有身份證號碼的嫌疑人信息，其中有n個壞人的身份證號碼，如何把m個人中的n個壞人找出來。如果m的數(shù)據(jù)量非常大，應(yīng)該如何查找

8 個性化推薦排序 不同排序算法的思想 電商的個性化推薦一般都轉(zhuǎn)化成點擊率預(yù)估問題，把用戶點擊率越高的商品排在前面，即根據(jù)商品點擊率降序排列。輸出排名前100的商品

3.3? ?綜合教學(xué)案例

除了針對各個知識點的案例外，課程團(tuán)隊還設(shè)計了融合多個知識點的綜合案例。

筆者所在大學(xué)是以電力為特色的學(xué)校，為了使學(xué)生了解和體會自己所學(xué)知識和電力的關(guān)系，在電力行業(yè)的應(yīng)用，我們設(shè)計了綜合案例2低壓配電網(wǎng)構(gòu)建。低壓配電網(wǎng)直接和廣大用戶相聯(lián)系，是電力系統(tǒng)中極為重要的一環(huán)?；谧钚∩蓸涞牡蛪号潆娋W(wǎng)布局方法操作簡單、實用性強，是一種有效地電網(wǎng)規(guī)劃層面的輔助決策方法[6]。這個案例主要是利用課程中最小生成樹算法來進(jìn)行低壓配電網(wǎng)構(gòu)建。

綜合案例表如表2所示。通過這些案例的實現(xiàn)，學(xué)生在理解理論模型的同時，熟悉和強化了模型的實際應(yīng)用，解決復(fù)雜實際問題的綜合能力和創(chuàng)新能力得到了提高。

1 小說人物分析 下載小說，存儲為文本文檔。任取其中10個人物，考慮他們的姓名、別名等因素。主要功能包括：（1）統(tǒng)計每個人物在小說中出現(xiàn)的次數(shù)。（2）統(tǒng)計每個人在小說中出現(xiàn)的篇幅跨度（第一次出現(xiàn)和最后一次出現(xiàn)的行間距），并按照篇幅跨度排序。（3）給出10個人物的交往情況;如果兩個在相距較短的一段文字中出現(xiàn)，我們認(rèn)為兩個人有交往關(guān)系，距離越短，關(guān)系越近。找出10個人中：關(guān)系最緊密的兩個人，關(guān)系最不緊密的兩個人。（4）輸入一個人名，列出該人和其他人關(guān)系的緊密程度排名

2 低壓配電網(wǎng)構(gòu)建 若要在n個小區(qū)之間鋪設(shè)電網(wǎng)線路，只需要架設(shè)n-1條線路即可。以最低的經(jīng)濟(jì)代價建設(shè)這個電網(wǎng)，是一個圖的最小生成樹問題

3 地鐵換乘推薦 利用上海市地鐵交通網(wǎng)數(shù)據(jù)，給出從指定起點到終點的可推薦路線，并按照最短時間，最少換乘對推薦路線排序

4 出租車合乘系統(tǒng) 由于出租車的運輸方式屬于“點對點的最短路徑運輸”[7]，如果要提供合乘服務(wù)，必須是在最短路徑上的乘客才能提供接載多位乘客的任務(wù)。利用最短路徑，字符串模式匹配的算法，實現(xiàn)乘客從指定起點到終點的出租車合乘要求

4? 教學(xué)方法的改革（The reform of teaching methods）

針對各個知識點案例和綜合案例的引入，我們對教學(xué)方法做了一些改革。

（1）提出問題，喚醒學(xué)生學(xué)習(xí)課程的好奇心。在課程的第一節(jié)課，課程緒論中就提出針對各個知識點的案例，吸引學(xué)生注意力，提高學(xué)生對即將要學(xué)習(xí)課程的興趣和積極性。

（2）研討交流[8]。課程的每個章節(jié)的知識點學(xué)習(xí)后，引導(dǎo)學(xué)生圍繞課堂的基本知識點對案例問題的求解算法進(jìn)行研討并在課下實現(xiàn)案例，在實驗課上進(jìn)行點評，并請完成優(yōu)秀的同學(xué)走上講臺和大家分享交流。

這種教學(xué)方法不僅訓(xùn)練了學(xué)生表達(dá)能力，也提高了同學(xué)的學(xué)習(xí)積極性，得到了同學(xué)、同行和督導(dǎo)老師的認(rèn)可。

（3）線上線下相結(jié)合。課程中引入各個知識點的案例，并對案例進(jìn)行分析，對課程知識點講解時間造成了影響，我們采用的方法是把課程的基本知識點的概念性知識錄成視頻提前放到課程網(wǎng)站上，提前讓學(xué)生預(yù)先在網(wǎng)站上學(xué)習(xí)，有些容易理解的概念性知識在課堂上可以少花時間或不花時間，大大提高課堂教學(xué)的效率。

（4）分等級的綜合案例。針對綜合案例，我們是在課程結(jié)束后，專門安排一周的時間來完成。因為同學(xué)的數(shù)據(jù)分析能力、算法設(shè)計能力和代碼編寫能力參差不齊，我們對綜合案例題目按照難易程度分成難、中、易三個等級，共25個案例，同學(xué)可以根據(jù)自己的能力進(jìn)行選擇。

（5）算法設(shè)計比賽。圍繞課程，我們還安排了整個學(xué)院的算法設(shè)計大賽，賽題主要針對大數(shù)據(jù)問題的算法設(shè)計。比賽的過程中參照正式ICPC（國際大學(xué)生程序設(shè)計競賽）比賽的規(guī)則為參賽選手發(fā)放象征著“通過”的氣球，通過一題，發(fā)放題目對應(yīng)顏色的氣球。這樣的比賽提高了學(xué)生算法設(shè)計和編程的興趣，促進(jìn)了學(xué)生課程學(xué)習(xí)的積極性。

5? 考核方式的改革（The reform of assessment methods）

在課程的考核方式上，改變傳統(tǒng)的一次考試決定課程考試結(jié)果的情況。整個課程的成績由線上學(xué)習(xí)成績，課程知識點案例完成成績，參加算法大賽成績，期末考試的卷面成績綜合評價。這種考核方式綜合評價了自學(xué)能力、抽象建模能力和編程能力。避免了出現(xiàn)考分高，動手編程能力差的情況。綜合案例的實現(xiàn)相當(dāng)于一門獨立的1學(xué)分的實踐課程，根據(jù)完成情況另外計分，考核了學(xué)生解決復(fù)雜實際問題的綜合能力和創(chuàng)新能力。

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

當(dāng)前的時代是數(shù)據(jù)的時代，數(shù)據(jù)已經(jīng)成為一種新的能源。數(shù)據(jù)已經(jīng)成為當(dāng)前學(xué)界和業(yè)界研究的熱點。以后的軟件開發(fā)和研究都將以數(shù)據(jù)為中心。數(shù)據(jù)結(jié)構(gòu)課程正是這樣一門融合數(shù)據(jù)分析，數(shù)據(jù)存儲和算法設(shè)計的一門課程。我們在課程的教學(xué)過程中，設(shè)計了以數(shù)據(jù)驅(qū)動的，針對課程知識點的案例和融合多個知識點綜合案例。結(jié)合案例教學(xué)，對教學(xué)方法和考核方式進(jìn)行了改革，對培養(yǎng)學(xué)生綜合運用所學(xué)知識與技能分析和解決復(fù)雜實際問題的綜合能力和創(chuàng)新能力起到較好的效果。后續(xù)，將進(jìn)一步結(jié)合團(tuán)隊老師的科研項目，完善案例，讓學(xué)生早一點體會課程學(xué)習(xí)在科學(xué)研究中的作用，并對課堂教學(xué)進(jìn)行更深入的改革，提高學(xué)生培養(yǎng)的質(zhì)量。

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

[1] 陳青青.數(shù)據(jù)結(jié)構(gòu)課程中分步式案例設(shè)計的探索與實踐[J].計算機教育，2019（10）：109-112.

[2] 張兆維，劉慧.兼顧考研與就業(yè)的數(shù)據(jù)結(jié)構(gòu)課程教學(xué)探索[J].計算機教育，2019（10）：82-85.

[3] 楊武，盧玲，陳媛.數(shù)據(jù)結(jié)構(gòu)課程的大案例構(gòu)建方法[J].計算機教育，2018（7）：92-95.

[4] 霍玲玲，王智，孫江.數(shù)據(jù)結(jié)構(gòu)教學(xué)方法的研究[J].計算機教育，2015（2）：73-76.

[5] 葉核亞.數(shù)據(jù)結(jié)構(gòu)（Java版）（第4版）[M].北京：電子工業(yè)出版社，2015.

[6] 謝建強.基于最小生成樹的低壓配電網(wǎng)布局研究[J].電氣技術(shù)，2016（6）：86-89.

[7] 鄧向林.基于動態(tài)規(guī)劃算法的出租車合乘模式研究[J].微型機與應(yīng)用，2013（8）：79-81.

[8] 張玉紅，李培培，胡學(xué)鋼.關(guān)于人工智能專業(yè)中數(shù)據(jù)結(jié)構(gòu)課程教學(xué)的幾點思考[J].計算機教育，2019（8）：106-109.

作者簡介：

張安勤（1974-），女，博士，副教授.研究領(lǐng)域：數(shù)據(jù)挖掘.

田秀霞（1976-），女，博士，教授.研究領(lǐng)域：信息安全.

張? ?挺（1979-），男，博士，副教授.研究領(lǐng)域：圖像處理.