數據結構課程中的綜合性實驗案例設計

康長青　朱麗娟　胡春陽　吳中博　王敏

摘? 要： 綜合性實驗案例是提升實踐教學質量的關鍵環節。針對現有的數據結構算法時空分析實驗安排缺失或綜合性不強的現狀，提出融合知識、能力、素質的綜合性實驗設計模式。通過課前資料查詢，課上對比分析和課后優化拓展三個階段，介紹了綜合性實驗案例的設計框架和能力素質目標。詳細介紹了結構體和函數、空間復雜度、時間復雜度和系統優化四個功能模塊的階段實驗目標、分級遞進內容和教學策略。給出了實驗的考核方案和教學效果分析。該教學模式有助于達成一流本科課程目標，可供同行借鑒和參考。

關鍵詞： 綜合性實驗; 數據結構; 設計框架; 對比分析; 教學策略

中圖分類號：G642? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2022）04-83-03

Comprehensive experimental case design in the course of data structure

Kang Changqing Zhu Lijuan Hu Chunyang Wu Zhongbo Wang Min

（1. School of Computer Engineering， Hubei University of Arts and Science， Xiangyang， Hubei 441053， China;

2. School of Physics and Electronic Engineering， Hubei University of Arts and Science）

Abstract： Comprehensive experimental cases have an important impact on improving teaching quality. Taking algorithm time complexity and space complexity of data structure as examples，the existing algorithms experiments have the disadvantages of lack of arrangement or lack of comprehensiveness. A comprehensive experimental design model that integrates knowledge， ability and quality was proposed to solve the above problems. Firstly， the design framework and goals of comprehensive experimental cases are introduced through three stages of pre-class information search， comparative analysis in class， and optimization and expansion after class. Then the stage experiment objectives， graded progressive content and teaching strategies of the four functional modules of structure and function， space complexity， time complexity and system optimization were presented in detail. Finally， the evaluation method of the experiment and the analysis of the teaching effect were given. The proposed model is beneficial to achieving the goals of first-class undergraduate courses and has some reference significance and promotion value.

Key words： comprehensive experiment; data structure; design framework; comparative analysis; teaching strategies

0 引言

教育部《關于一流本科課程建設的實施意見》中要求確立學生中心、產出導向、持續改進的理念，提升課程的高階性，突出課程的創新性，增加課程的挑戰度[1]。在此背景下，地方應用型本科院校如何進行專業核心課程的改革和建設[2]，對人才培養質量的提高起著舉足輕重的作用。

數據結構作為計算機類專業課程體系中的核心課程，理應率先進行高階性、創新性和挑戰性改革，努力創建省級一流本科課程。

掌握算法的時間分析和空間分析的技術是數據結構課程的教學目標之一[3，4]，經常采用傳統的課堂講授來達成目標，存在學生印象不深，方法未學會，短時間不能掌握等問題，而現有的算法時空分析實驗要么安排缺失，要么綜合性不強[5]，因此論文提出采用綜合性實驗案例設計來達成課程目標，并逐步培養學生解決復雜工程問題的綜合能力和高級思維。

1 融合知識、能力、素質的綜合實驗課設計思路

算法的時空分析實驗是數據結構課程的第一個實驗，考慮以提升學生綜合能力和素質為重點目標，重新設計算法的時空分析實驗內容如表1所示。

從表1可以看出，實驗分為五個功能模塊，分別為：結構體和函數復習模塊，空間復雜度模塊，時間復雜度模塊，系統優化模塊、實驗總結和分析模塊。

結構體和函數復習模塊主要考慮學生程序設計基礎薄弱的現狀，設計一些程序填空題和編程興趣題，用兩周時間，在課前完成，培養學生查閱文獻，溝通交流的意識，讓學生反思自己的知識薄弱點，主動查缺補漏。空間復雜度模塊主要任務是同一問題的不同函數設計，培養學生程序設計和軟件測試技能，學會在判斷和權衡的基礎上深度分析，樹立空間資源管理和積極學習的意識。 時間復雜度模塊要求對數學問題進行快慢算法的設計，培養學生算法設計和測試技巧，樹立探究和驗證，克服障礙，勇于探究的職業技能和態度。系統優化模塊通過讓學生查閱閱讀實用的系統優化資料，培養學生整體思維，分析確定系統優化的優先級和焦點，激發求知欲和終生學習的意識，為自己進行職業規劃，明確自己職業的任務和責任。實驗總結分析模塊主要對實驗進行總結和分析，內容包括解決問題的新思路，自己實驗工作的優勢和不足，在綜合能力提升方面的進步等等，鍛煉學生的圖標和寫作交流能力，為未來職業工作匯報和團隊交流，打下基礎。

2 綜合性實驗具體案例設計和實踐

依據表1的實驗設計思路，開展綜合性實驗具體案例設計，因此我們精心設計了五個功能模塊（結構體和函數復習模塊，空間復雜度模塊，時間復雜度模塊，系統優化模塊和實驗總結和分析模塊）的實驗子目標、實驗內容和教學策略等。

2.1 結構體和函數復習模塊案例設計

實驗目標：①能夠學會使用文獻搜索技巧查詢資料;②學會庫函數的調用，掌握計算代碼段運行時間的基本步驟;③能夠掌握常見的庫函數的調用錯誤及調試方法。

實驗內容：①在C語言庫文件time.h中有哪些不同的結構體和操作日期和時間的函數，這些結構體的詳細成員有哪些，代表的含義是什么？有哪些操作日期和時間的函數以及函數的作用是什么？②以結構體time_t，和對應的time（）函數為例，給出一段成功調用time（）的程序代碼并截圖給出效果圖;③以結構體timeb，或clock_t為例，給出計算代碼段運行時間的程序代碼和運行結果;④程序調試中有哪些常見的調用錯誤。⑤分析time_t， timeb， timeval， clock_t這四個結構體調用時間精度的差別和適用范圍。

教學策略：以學生線下自學為主，通過小組交流匯報，肯定學生的過程努力和結果。教師講解關鍵字搜索和中英文資料搜索的技巧。

2.2 空間復雜度測試模塊案例設計

實驗目標：①了解軟件測試中的靜態測試，動態測試和單元測試;②理解空間復雜度的概念和理論分析方法;③培養合理利用空間資源的意識，判斷和權衡，主動問題分析。

實驗內容：①用循環的編程思想依次輸出從N個有規律整數的函數設計（程序1）;②編寫一個遞歸的函數（程序2），實現依次輸出N個有規律整數;③針對程序1和2，給出一組相同N的值來確定兩個程序都能正常運行，其中一個非正常運行，利用空間復雜度的概念，分析兩個程序的空間復雜度。

教學策略：教師講解各種測試概念，強調測試的重要性，引導學生分析遞歸程序的復雜度，學生自主完成函數設計和軟件測試。

2.3 時間復雜度測試模塊案例設計

實驗目標：①掌握利用遞推算法求解問題;②理解時間復雜度的概念和理論分析方法;③學會調用時間函數，編寫同一問題不同算法的運行時間的程序;④了解利用軟件測試技術，分析驗證不同算法的時間效率。

實驗內容：①利用循環語句設計算法（算法1）進行多項式1+x+…+ x求和，并分析其時間復雜度;②利用遞推算法（算法2）進行多項式1+x+…+x求和，并分析其時間復雜度;③利用timeb，及相關函數設計利用循環和非遞推算法的計算時間的程序;④軟件測試中計算時間都為零，原因是什么，如何設計輸入相同的避免函數時間為零;⑤分析表2中X和N的值是否相同，兩個程序輸入參數不一樣，能夠比較算法的計算時間？兩個算法的計算時間是否和理論復雜度的分析結果一致，為什么？

教學策略：學生自主完成算法設計和問題分析，輔助部分學生進行遞推算法的計算程序設計，必要時提供參考代碼，引導學生克服困難和障礙，學會分析實驗結果，驗證理論。

2.4 系統優化模塊案例設計

實驗目標：①培養學生整體思維，系統思維和把握熱點技術趨勢的思維;②學會采用探究式學習進行系統優化，了解算法級別，函數級別，循環級別，語句級別，指令級別優化串行代碼，激發求知欲并養成終生學習的良好習慣。③逐步養成盡善盡美的工作態度，崇尚奮斗，勇于擔當的家國情懷。

實驗內容：①閱讀谷歌公司的C++編碼規范中的頭文件規則和命名約定規則，改造自己編寫的程序;②閱讀文獻[6]中的算法性能和程序性能的度量與分析，串行代碼性能優化技術，談談你的認識和看法;③Linux環境下提供了納秒級精度的計時函數clock_gettime，在Linux環境下使用GCC編譯器能否解決資金算法計時為0的問題;④基于SSE/AVX的向量化編程方法，改造算法，并進行時間效率的對比和分析。

教學策略：要求學生自主完成閱讀任務，鼓勵學生以小組形式完成探究性實驗任務，把握系統優化的思維，強調代碼規范對于求職面試和職業生涯的重要性。

2.5 實驗總結分析模塊案例設計

實驗目標：①鍛煉學生的圖表和文字寫作交流能力;②良好的軟件工程文檔和職業工作匯報材料;③學會利用口頭和文字材料進行團隊協作和溝通。

實驗內容：①對實驗結果進行分析，有沒有解決求解程序運行時間到新方法和思路？②程序中遇見的錯誤有哪些，和自己如何解決的？未解決的問題有哪些？③在算法設計，資料查找，對比分析，軟件測試，溝通交流等綜合能力提升方面，收獲和不足有哪些？是否有未來的學習計劃和努力方向？

2.6 綜合實驗項目考核設計

針對本次算法的時空分析綜合性實驗，設計實驗考評成績構成和評價方式為：結構體和函數模塊占15%，采用組內成員互評得分方式;空間復雜度模塊占20%，以同學間現場檢查互評進行;時間復雜度模塊占40%，以教師檢查提問形式評價;系統優化模塊占15%，采用小組匯報整體得分形式;最終實驗報告（含實驗總結和分析模塊）的占10%，需要學生提交到在線作業批改系統，教師通過內容查重后，單獨評價。

經過以上綜合式實驗內容設計和實踐后，學生普遍反映該實驗項目銜接自然，挑戰度較高，完成實驗后增加了對算法的感性認識，增強了學習興趣，特別在程序設計，文獻查找，對比分析，系統思維，溝通討論等綜合能力提升度較大，取得了良好的教學成效。

3 結論

一流本科課程要求增加課程的高階性、創新性和挑戰度，要求培養學生解決復雜問題的綜合能力和高級思維。本論文以數據結構課程中的算法時空分析內容為例，兼顧地方應用型本科高校的實際，探索了融合知識、能力、素質的綜合性實驗設計思路，取得了良好的教學效果，對其他相關課程的改革有一定的借鑒和參考意義。當然該綜合性教學案例也存在耗費時間長，對基礎不好的學生挑戰性較高的不足，未來我們將在課程實踐中不斷聽取學生的意見，并持續改進和優化案例，努力提升實踐教學質量。

參考文獻（References）：

[1] 教育部關于一流本科課程建設的實施意見[EB/OL].http：//www.moe.gov.cn/srcsite/A08/s7056/201910/t20191031_406269.html.

[2] 李敏之，王陽萍，李海軍.新工科建設指引下的西部高校一流本科課程建設——以大學計算機基礎課程為例[J].計算機教育，2020，311（11）：93-97

[3] 陳越，何欽銘.數據結構[M].北京：高等教育出版社，2012

[4] 陳越，何欽銘，馮雁.“數據結構”綜合性課程設計教學探索與實踐[J].計算機教育，2008，68（8）：56-57

[5] 張兆維，王建華，陶曦鳴.“數據結構”課程的課內實驗教學探索與實踐[J]. 計算機時代，2020，335（5）：96-99

[6] 劉文志.并行算法設計與性能優化[M].北京：機械工業出版社，2015