數據驅動的數據結構課程案例設計研究與實踐

張安勤 田秀霞 張挺

摘? 要：我們在各行各業的諸多領域以及學習和生活中產生了大量的數據，現在的時代已經是一個數據時代。文章分析了當前數據結構課程教學中存在的問題，結合當前數據時代前沿研究領域和行業應用，設計了單個知識點的案例和融合多個知識點的綜合案例。在此基礎上，對教學方法和考核方式進行了改革。我們的教學改革拓展了學生的知識和技能，提高了學生分析和解決實際復雜問題的綜合素質和創新能力。

關鍵詞：數據結構;數據驅動;案例設計;教學改革

中圖分類號：TP311? ? ?文獻標識碼：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）

數據結構課程是計算機相關專業的專業基礎課程，在專業課程體系中起著承上啟下的作用。課程對培養學生的數據模型抽象能力、算法設計能力和復雜的程序設計能力具有重要的作用。課程所討論的知識內容和算法技術，無論對于后續學習其他專業課程，或是將來從事軟件開發工作，都是必須掌握的基礎內容[1]。

我們的各行各業學習和生活中的諸多領域產生了大量的數據，現在的時代已經是一個數據時代，數據已經成為一種新能源，對數據的存儲、處理，以及分析面臨著巨大的需求。

在這個數據時代，一方面，我們的《數據結構》課程內容仍然是前沿研究領域的重要基礎;另一方面，這些基礎理論內容也需要針對數據時代的新問題與新挑戰進行調整和改革。但目前，我們的課程教學采用傳統主流數據結構的知識講解，偽代碼描述算法，再附加一些課程實驗的教學模式，已無法適應數據時代的需求和挑戰。因此，在《數據結構》課程教學過程中，需要將課程基礎理論內容與數據時代的特點相融合、與學界和業界前沿領域相融合，兼顧基礎知識與學科前沿、理論與實踐并重。

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

在數據結構的實際教學中，存在的問題主要有兩種情況：

（1）學生基本理論聽得懂，算法理解和實現存在困難。甚至出現筆試分數很高，但是實驗和課程設計環節無法完成算法實現和一個完整的應用系統的情況。

（2）學生覺得學習內容枯燥無味，對課程內容沒興趣。

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

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

（2）受數據結構傳統教學的影響，重視理論部分的課堂教學，輕視實踐環節。雖然近幾年，由于我校定位為應用型本科大學，對實驗和實踐環節的重視情況有所改善，但是力度不夠，沒有具體的方法和措施。

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

（4）教材和實驗中的案例老套，沒有緊跟當前學術和業界的最新發展，難以吸引學生的注意力，學生的學習和編碼沒有積極性。

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

3? ?案例設計（Case design ）

3.1? ?案例設計的要求

案例需要滿足的要求：

（1）切合教學的知識點;

（2）與學界和業界前沿領域相融合;

（3）學生比較容易接受，能夠激發學生興趣。

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

3.2? ?結合知識點的教學案例

數據結構課程的主要知識點有線性表、棧、隊列、串、二叉樹、圖、查找、排序。數據結構教學團隊設計的案例圍繞課程的主要知識點展開。

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

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

1 手機通訊錄管理 線性表線性表的順序存儲和鏈式存儲 手機通訊錄上的聯系人數據的邏輯結構是線性結構，手機聯系數據在手機中用順序表存儲和鏈表存儲時，實現插入、刪除和查找功能

2 分隔符匹配 棧的先進后出，入棧和出棧 檢查字符串數據中分隔符是否左右匹配。分隔符包括大括號，中括號，小括號，每個分隔符都要左右進行匹配，如果不匹配報錯并輸出不匹配位置

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

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

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

6 班級社交網絡分析 圖的構建和圖的遍歷算法 收集班級同學之間的手機通話數據，短信數據，微信數據和QQ數據，建立班級同學社交網絡圖。查找核心同學，活躍同學，以及指定同學的交往圈子

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

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

3.3? ?綜合教學案例

除了針對各個知識點的案例外，課程團隊還設計了融合多個知識點的綜合案例。

筆者所在大學是以電力為特色的學校，為了使學生了解和體會自己所學知識和電力的關系，在電力行業的應用，我們設計了綜合案例2低壓配電網構建。低壓配電網直接和廣大用戶相聯系，是電力系統中極為重要的一環。基于最小生成樹的低壓配電網布局方法操作簡單、實用性強，是一種有效地電網規劃層面的輔助決策方法[6]。這個案例主要是利用課程中最小生成樹算法來進行低壓配電網構建。

綜合案例表如表2所示。通過這些案例的實現，學生在理解理論模型的同時，熟悉和強化了模型的實際應用，解決復雜實際問題的綜合能力和創新能力得到了提高。

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

2 低壓配電網構建 若要在n個小區之間鋪設電網線路，只需要架設n-1條線路即可。以最低的經濟代價建設這個電網，是一個圖的最小生成樹問題

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

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

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

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

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

（2）研討交流[8]。課程的每個章節的知識點學習后，引導學生圍繞課堂的基本知識點對案例問題的求解算法進行研討并在課下實現案例，在實驗課上進行點評，并請完成優秀的同學走上講臺和大家分享交流。

這種教學方法不僅訓練了學生表達能力，也提高了同學的學習積極性，得到了同學、同行和督導老師的認可。

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

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

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

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

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

6? ?結論（Conclusion）

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

參考文獻（References）

[1] 陳青青.數據結構課程中分步式案例設計的探索與實踐[J].計算機教育，2019（10）：109-112.

[2] 張兆維，劉慧.兼顧考研與就業的數據結構課程教學探索[J].計算機教育，2019（10）：82-85.

[3] 楊武，盧玲，陳媛.數據結構課程的大案例構建方法[J].計算機教育，2018（7）：92-95.

[4] 霍玲玲，王智，孫江.數據結構教學方法的研究[J].計算機教育，2015（2）：73-76.

[5] 葉核亞.數據結構（Java版）（第4版）[M].北京：電子工業出版社，2015.

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

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

[8] 張玉紅，李培培，胡學鋼.關于人工智能專業中數據結構課程教學的幾點思考[J].計算機教育，2019（8）：106-109.

作者簡介：

張安勤（1974-），女，博士，副教授.研究領域：數據挖掘.

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

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