數(shù)據(jù)結(jié)構(gòu)課程中的綜合性實(shí)驗(yàn)案例設(shè)計(jì)

康長(zhǎng)青　朱麗娟　胡春陽(yáng)　吳中博　王敏

摘? 要： 綜合性實(shí)驗(yàn)案例是提升實(shí)踐教學(xué)質(zhì)量的關(guān)鍵環(huán)節(jié)。針對(duì)現(xiàn)有的數(shù)據(jù)結(jié)構(gòu)算法時(shí)空分析實(shí)驗(yàn)安排缺失或綜合性不強(qiáng)的現(xiàn)狀，提出融合知識(shí)、能力、素質(zhì)的綜合性實(shí)驗(yàn)設(shè)計(jì)模式。通過(guò)課前資料查詢，課上對(duì)比分析和課后優(yōu)化拓展三個(gè)階段，介紹了綜合性實(shí)驗(yàn)案例的設(shè)計(jì)框架和能力素質(zhì)目標(biāo)。詳細(xì)介紹了結(jié)構(gòu)體和函數(shù)、空間復(fù)雜度、時(shí)間復(fù)雜度和系統(tǒng)優(yōu)化四個(gè)功能模塊的階段實(shí)驗(yàn)?zāi)繕?biāo)、分級(jí)遞進(jìn)內(nèi)容和教學(xué)策略。給出了實(shí)驗(yàn)的考核方案和教學(xué)效果分析。該教學(xué)模式有助于達(dá)成一流本科課程目標(biāo)，可供同行借鑒和參考。

關(guān)鍵詞： 綜合性實(shí)驗(yàn); 數(shù)據(jù)結(jié)構(gòu); 設(shè)計(jì)框架; 對(duì)比分析; 教學(xué)策略

中圖分類號(hào)：G642? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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 引言

教育部《關(guān)于一流本科課程建設(shè)的實(shí)施意見(jiàn)》中要求確立學(xué)生中心、產(chǎn)出導(dǎo)向、持續(xù)改進(jìn)的理念，提升課程的高階性，突出課程的創(chuàng)新性，增加課程的挑戰(zhàn)度[1]。在此背景下，地方應(yīng)用型本科院校如何進(jìn)行專業(yè)核心課程的改革和建設(shè)[2]，對(duì)人才培養(yǎng)質(zhì)量的提高起著舉足輕重的作用。

數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)類專業(yè)課程體系中的核心課程，理應(yīng)率先進(jìn)行高階性、創(chuàng)新性和挑戰(zhàn)性改革，努力創(chuàng)建省級(jí)一流本科課程。

掌握算法的時(shí)間分析和空間分析的技術(shù)是數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)目標(biāo)之一[3，4]，經(jīng)常采用傳統(tǒng)的課堂講授來(lái)達(dá)成目標(biāo)，存在學(xué)生印象不深，方法未學(xué)會(huì)，短時(shí)間不能掌握等問(wèn)題，而現(xiàn)有的算法時(shí)空分析實(shí)驗(yàn)要么安排缺失，要么綜合性不強(qiáng)[5]，因此論文提出采用綜合性實(shí)驗(yàn)案例設(shè)計(jì)來(lái)達(dá)成課程目標(biāo)，并逐步培養(yǎng)學(xué)生解決復(fù)雜工程問(wèn)題的綜合能力和高級(jí)思維。

1 融合知識(shí)、能力、素質(zhì)的綜合實(shí)驗(yàn)課設(shè)計(jì)思路

算法的時(shí)空分析實(shí)驗(yàn)是數(shù)據(jù)結(jié)構(gòu)課程的第一個(gè)實(shí)驗(yàn)，考慮以提升學(xué)生綜合能力和素質(zhì)為重點(diǎn)目標(biāo)，重新設(shè)計(jì)算法的時(shí)空分析實(shí)驗(yàn)內(nèi)容如表1所示。

從表1可以看出，實(shí)驗(yàn)分為五個(gè)功能模塊，分別為：結(jié)構(gòu)體和函數(shù)復(fù)習(xí)模塊，空間復(fù)雜度模塊，時(shí)間復(fù)雜度模塊，系統(tǒng)優(yōu)化模塊、實(shí)驗(yàn)總結(jié)和分析模塊。

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

2 綜合性實(shí)驗(yàn)具體案例設(shè)計(jì)和實(shí)踐

依據(jù)表1的實(shí)驗(yàn)設(shè)計(jì)思路，開展綜合性實(shí)驗(yàn)具體案例設(shè)計(jì)，因此我們精心設(shè)計(jì)了五個(gè)功能模塊（結(jié)構(gòu)體和函數(shù)復(fù)習(xí)模塊，空間復(fù)雜度模塊，時(shí)間復(fù)雜度模塊，系統(tǒng)優(yōu)化模塊和實(shí)驗(yàn)總結(jié)和分析模塊）的實(shí)驗(yàn)子目標(biāo)、實(shí)驗(yàn)內(nèi)容和教學(xué)策略等。

2.1 結(jié)構(gòu)體和函數(shù)復(fù)習(xí)模塊案例設(shè)計(jì)

實(shí)驗(yàn)?zāi)繕?biāo)：①能夠?qū)W會(huì)使用文獻(xiàn)搜索技巧查詢資料;②學(xué)會(huì)庫(kù)函數(shù)的調(diào)用，掌握計(jì)算代碼段運(yùn)行時(shí)間的基本步驟;③能夠掌握常見(jiàn)的庫(kù)函數(shù)的調(diào)用錯(cuò)誤及調(diào)試方法。

實(shí)驗(yàn)內(nèi)容：①在C語(yǔ)言庫(kù)文件time.h中有哪些不同的結(jié)構(gòu)體和操作日期和時(shí)間的函數(shù)，這些結(jié)構(gòu)體的詳細(xì)成員有哪些，代表的含義是什么？有哪些操作日期和時(shí)間的函數(shù)以及函數(shù)的作用是什么？②以結(jié)構(gòu)體time_t，和對(duì)應(yīng)的time（）函數(shù)為例，給出一段成功調(diào)用time（）的程序代碼并截圖給出效果圖;③以結(jié)構(gòu)體timeb，或clock_t為例，給出計(jì)算代碼段運(yùn)行時(shí)間的程序代碼和運(yùn)行結(jié)果;④程序調(diào)試中有哪些常見(jiàn)的調(diào)用錯(cuò)誤。⑤分析time_t， timeb， timeval， clock_t這四個(gè)結(jié)構(gòu)體調(diào)用時(shí)間精度的差別和適用范圍。

教學(xué)策略：以學(xué)生線下自學(xué)為主，通過(guò)小組交流匯報(bào)，肯定學(xué)生的過(guò)程努力和結(jié)果。教師講解關(guān)鍵字搜索和中英文資料搜索的技巧。

2.2 空間復(fù)雜度測(cè)試模塊案例設(shè)計(jì)

實(shí)驗(yàn)?zāi)繕?biāo)：①了解軟件測(cè)試中的靜態(tài)測(cè)試，動(dòng)態(tài)測(cè)試和單元測(cè)試;②理解空間復(fù)雜度的概念和理論分析方法;③培養(yǎng)合理利用空間資源的意識(shí)，判斷和權(quán)衡，主動(dòng)問(wèn)題分析。

實(shí)驗(yàn)內(nèi)容：①用循環(huán)的編程思想依次輸出從N個(gè)有規(guī)律整數(shù)的函數(shù)設(shè)計(jì)（程序1）;②編寫一個(gè)遞歸的函數(shù)（程序2），實(shí)現(xiàn)依次輸出N個(gè)有規(guī)律整數(shù);③針對(duì)程序1和2，給出一組相同N的值來(lái)確定兩個(gè)程序都能正常運(yùn)行，其中一個(gè)非正常運(yùn)行，利用空間復(fù)雜度的概念，分析兩個(gè)程序的空間復(fù)雜度。

教學(xué)策略：教師講解各種測(cè)試概念，強(qiáng)調(diào)測(cè)試的重要性，引導(dǎo)學(xué)生分析遞歸程序的復(fù)雜度，學(xué)生自主完成函數(shù)設(shè)計(jì)和軟件測(cè)試。

2.3 時(shí)間復(fù)雜度測(cè)試模塊案例設(shè)計(jì)

實(shí)驗(yàn)?zāi)繕?biāo)：①掌握利用遞推算法求解問(wèn)題;②理解時(shí)間復(fù)雜度的概念和理論分析方法;③學(xué)會(huì)調(diào)用時(shí)間函數(shù)，編寫同一問(wèn)題不同算法的運(yùn)行時(shí)間的程序;④了解利用軟件測(cè)試技術(shù)，分析驗(yàn)證不同算法的時(shí)間效率。

實(shí)驗(yàn)內(nèi)容：①利用循環(huán)語(yǔ)句設(shè)計(jì)算法（算法1）進(jìn)行多項(xiàng)式1+x+…+ x求和，并分析其時(shí)間復(fù)雜度;②利用遞推算法（算法2）進(jìn)行多項(xiàng)式1+x+…+x求和，并分析其時(shí)間復(fù)雜度;③利用timeb，及相關(guān)函數(shù)設(shè)計(jì)利用循環(huán)和非遞推算法的計(jì)算時(shí)間的程序;④軟件測(cè)試中計(jì)算時(shí)間都為零，原因是什么，如何設(shè)計(jì)輸入相同的避免函數(shù)時(shí)間為零;⑤分析表2中X和N的值是否相同，兩個(gè)程序輸入?yún)?shù)不一樣，能夠比較算法的計(jì)算時(shí)間？?jī)蓚€(gè)算法的計(jì)算時(shí)間是否和理論復(fù)雜度的分析結(jié)果一致，為什么？

教學(xué)策略：學(xué)生自主完成算法設(shè)計(jì)和問(wèn)題分析，輔助部分學(xué)生進(jìn)行遞推算法的計(jì)算程序設(shè)計(jì)，必要時(shí)提供參考代碼，引導(dǎo)學(xué)生克服困難和障礙，學(xué)會(huì)分析實(shí)驗(yàn)結(jié)果，驗(yàn)證理論。

2.4 系統(tǒng)優(yōu)化模塊案例設(shè)計(jì)

實(shí)驗(yàn)?zāi)繕?biāo)：①培養(yǎng)學(xué)生整體思維，系統(tǒng)思維和把握熱點(diǎn)技術(shù)趨勢(shì)的思維;②學(xué)會(huì)采用探究式學(xué)習(xí)進(jìn)行系統(tǒng)優(yōu)化，了解算法級(jí)別，函數(shù)級(jí)別，循環(huán)級(jí)別，語(yǔ)句級(jí)別，指令級(jí)別優(yōu)化串行代碼，激發(fā)求知欲并養(yǎng)成終生學(xué)習(xí)的良好習(xí)慣。③逐步養(yǎng)成盡善盡美的工作態(tài)度，崇尚奮斗，勇于擔(dān)當(dāng)?shù)募覈?guó)情懷。

實(shí)驗(yàn)內(nèi)容：①閱讀谷歌公司的C++編碼規(guī)范中的頭文件規(guī)則和命名約定規(guī)則，改造自己編寫的程序;②閱讀文獻(xiàn)[6]中的算法性能和程序性能的度量與分析，串行代碼性能優(yōu)化技術(shù)，談?wù)勀愕恼J(rèn)識(shí)和看法;③Linux環(huán)境下提供了納秒級(jí)精度的計(jì)時(shí)函數(shù)clock_gettime，在Linux環(huán)境下使用GCC編譯器能否解決資金算法計(jì)時(shí)為0的問(wèn)題;④基于SSE/AVX的向量化編程方法，改造算法，并進(jìn)行時(shí)間效率的對(duì)比和分析。

教學(xué)策略：要求學(xué)生自主完成閱讀任務(wù)，鼓勵(lì)學(xué)生以小組形式完成探究性實(shí)驗(yàn)任務(wù)，把握系統(tǒng)優(yōu)化的思維，強(qiáng)調(diào)代碼規(guī)范對(duì)于求職面試和職業(yè)生涯的重要性。

2.5 實(shí)驗(yàn)總結(jié)分析模塊案例設(shè)計(jì)

實(shí)驗(yàn)?zāi)繕?biāo)：①鍛煉學(xué)生的圖表和文字寫作交流能力;②良好的軟件工程文檔和職業(yè)工作匯報(bào)材料;③學(xué)會(huì)利用口頭和文字材料進(jìn)行團(tuán)隊(duì)協(xié)作和溝通。

實(shí)驗(yàn)內(nèi)容：①對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，有沒(méi)有解決求解程序運(yùn)行時(shí)間到新方法和思路？②程序中遇見(jiàn)的錯(cuò)誤有哪些，和自己如何解決的？未解決的問(wèn)題有哪些？③在算法設(shè)計(jì)，資料查找，對(duì)比分析，軟件測(cè)試，溝通交流等綜合能力提升方面，收獲和不足有哪些？是否有未來(lái)的學(xué)習(xí)計(jì)劃和努力方向？

2.6 綜合實(shí)驗(yàn)項(xiàng)目考核設(shè)計(jì)

針對(duì)本次算法的時(shí)空分析綜合性實(shí)驗(yàn)，設(shè)計(jì)實(shí)驗(yàn)考評(píng)成績(jī)構(gòu)成和評(píng)價(jià)方式為：結(jié)構(gòu)體和函數(shù)模塊占15%，采用組內(nèi)成員互評(píng)得分方式;空間復(fù)雜度模塊占20%，以同學(xué)間現(xiàn)場(chǎng)檢查互評(píng)進(jìn)行;時(shí)間復(fù)雜度模塊占40%，以教師檢查提問(wèn)形式評(píng)價(jià);系統(tǒng)優(yōu)化模塊占15%，采用小組匯報(bào)整體得分形式;最終實(shí)驗(yàn)報(bào)告（含實(shí)驗(yàn)總結(jié)和分析模塊）的占10%，需要學(xué)生提交到在線作業(yè)批改系統(tǒng)，教師通過(guò)內(nèi)容查重后，單獨(dú)評(píng)價(jià)。

經(jīng)過(guò)以上綜合式實(shí)驗(yàn)內(nèi)容設(shè)計(jì)和實(shí)踐后，學(xué)生普遍反映該實(shí)驗(yàn)項(xiàng)目銜接自然，挑戰(zhàn)度較高，完成實(shí)驗(yàn)后增加了對(duì)算法的感性認(rèn)識(shí)，增強(qiáng)了學(xué)習(xí)興趣，特別在程序設(shè)計(jì)，文獻(xiàn)查找，對(duì)比分析，系統(tǒng)思維，溝通討論等綜合能力提升度較大，取得了良好的教學(xué)成效。

3 結(jié)論

一流本科課程要求增加課程的高階性、創(chuàng)新性和挑戰(zhàn)度，要求培養(yǎng)學(xué)生解決復(fù)雜問(wèn)題的綜合能力和高級(jí)思維。本論文以數(shù)據(jù)結(jié)構(gòu)課程中的算法時(shí)空分析內(nèi)容為例，兼顧地方應(yīng)用型本科高校的實(shí)際，探索了融合知識(shí)、能力、素質(zhì)的綜合性實(shí)驗(yàn)設(shè)計(jì)思路，取得了良好的教學(xué)效果，對(duì)其他相關(guān)課程的改革有一定的借鑒和參考意義。當(dāng)然該綜合性教學(xué)案例也存在耗費(fèi)時(shí)間長(zhǎng)，對(duì)基礎(chǔ)不好的學(xué)生挑戰(zhàn)性較高的不足，未來(lái)我們將在課程實(shí)踐中不斷聽取學(xué)生的意見(jiàn)，并持續(xù)改進(jìn)和優(yōu)化案例，努力提升實(shí)踐教學(xué)質(zhì)量。

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

[1] 教育部關(guān)于一流本科課程建設(shè)的實(shí)施意見(jiàn)[EB/OL].http：//www.moe.gov.cn/srcsite/A08/s7056/201910/t20191031_406269.html.

[2] 李敏之，王陽(yáng)萍，李海軍.新工科建設(shè)指引下的西部高校一流本科課程建設(shè)——以大學(xué)計(jì)算機(jī)基礎(chǔ)課程為例[J].計(jì)算機(jī)教育，2020，311（11）：93-97

[3] 陳越，何欽銘.數(shù)據(jù)結(jié)構(gòu)[M].北京：高等教育出版社，2012

[4] 陳越，何欽銘，馮雁.“數(shù)據(jù)結(jié)構(gòu)”綜合性課程設(shè)計(jì)教學(xué)探索與實(shí)踐[J].計(jì)算機(jī)教育，2008，68（8）：56-57

[5] 張兆維，王建華，陶曦鳴.“數(shù)據(jù)結(jié)構(gòu)”課程的課內(nèi)實(shí)驗(yàn)教學(xué)探索與實(shí)踐[J]. 計(jì)算機(jī)時(shí)代，2020，335（5）：96-99

[6] 劉文志.并行算法設(shè)計(jì)與性能優(yōu)化[M].北京：機(jī)械工業(yè)出版社，2015