應(yīng)用型獨(dú)立學(xué)院數(shù)據(jù)結(jié)構(gòu)課程案例設(shè)計(jì)

張新彩 鄔迎

摘要：針對(duì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)施過(guò)程中存在的問(wèn)題進(jìn)行了分析，結(jié)合應(yīng)用型獨(dú)立學(xué)院學(xué)生的特點(diǎn)，課程組精心設(shè)計(jì)課程設(shè)計(jì)案例，并舉例說(shuō)明案例實(shí)施過(guò)程，通過(guò)有效的過(guò)程管理，達(dá)到課程設(shè)計(jì)目的。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu);課程設(shè)計(jì)案例;過(guò)程管理

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

文章編號(hào)：1009-3044（2022）21-0172-03

開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

在進(jìn)行計(jì)算機(jī)相關(guān)專業(yè)的學(xué)習(xí)中，數(shù)據(jù)結(jié)構(gòu)課程是非常重要的一門較為基礎(chǔ)的課程，在眾多學(xué)科中具有很重要的地位[1]。數(shù)據(jù)結(jié)構(gòu)課程理論教學(xué)多以講授線性結(jié)構(gòu)、樹(shù)、圖、查找和排序等知識(shí)，由于實(shí)踐性較強(qiáng)，各個(gè)學(xué)校都安排了一定學(xué)時(shí)的課程設(shè)計(jì)，以使學(xué)生能靈活地選擇合適的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)，并能利用算法來(lái)解決實(shí)際生活中的問(wèn)題，以進(jìn)一步提升學(xué)生使用程序解決實(shí)際問(wèn)題的能力。文獻(xiàn)[2]提出一種基于能力培養(yǎng)的教學(xué)模式，將教學(xué)設(shè)計(jì)分成3個(gè)階段，旨在提高學(xué)生的綜合應(yīng)用能力。

1 課程設(shè)計(jì)存在的問(wèn)題

經(jīng)過(guò)授課數(shù)據(jù)結(jié)構(gòu)課程和進(jìn)行課程設(shè)計(jì)的經(jīng)驗(yàn)得知，學(xué)生的學(xué)習(xí)效果并不理想。究其原因，主要存在如下方面：

1）理論與應(yīng)用相脫節(jié)?，F(xiàn)階段，有相當(dāng)一部分學(xué)生，在學(xué)習(xí)完數(shù)據(jù)結(jié)構(gòu)后，只知道如何做題，卻不知它的意義何在？能用它干什么？究其原因主要是沒(méi)有理解其含義，再就是與實(shí)踐脫節(jié)，這就要求老師在講解相關(guān)知識(shí)的時(shí)候多講一些具體應(yīng)用，另外在課程設(shè)計(jì)環(huán)節(jié)針對(duì)相關(guān)知識(shí)點(diǎn)設(shè)計(jì)一些具體案例，加深學(xué)生對(duì)知識(shí)的理解。

2）程序設(shè)計(jì)基礎(chǔ)較弱。就獨(dú)立學(xué)院而言，通常是入學(xué)第一學(xué)期學(xué)習(xí)程序設(shè)計(jì)語(yǔ)言，第二學(xué)期開(kāi)設(shè)數(shù)據(jù)結(jié)構(gòu)課程，但通常因?yàn)榇蠖鄶?shù)學(xué)生之前沒(méi)有接觸過(guò)計(jì)算機(jī)語(yǔ)言，一開(kāi)始學(xué)習(xí)程序設(shè)計(jì)有一定難度，很多學(xué)生一學(xué)期下來(lái)也僅達(dá)到能基本獨(dú)立編寫(xiě)較簡(jiǎn)單程序的程度，對(duì)算法的理解和應(yīng)用還不夠透徹，而此課程又跟數(shù)據(jù)結(jié)構(gòu)關(guān)系較緊密，導(dǎo)致其在數(shù)據(jù)結(jié)構(gòu)實(shí)踐環(huán)節(jié)完成實(shí)驗(yàn)時(shí)舉步維艱。

2 課程設(shè)計(jì)改革思路

課程組也針對(duì)上述問(wèn)題，提出并實(shí)施如下改革思路。

1）結(jié)合企業(yè)實(shí)際需求，以立足培養(yǎng)高質(zhì)量的應(yīng)用技術(shù)型人才為目標(biāo)，注重培養(yǎng)學(xué)生實(shí)踐動(dòng)手能力，以學(xué)科前沿、與實(shí)際結(jié)合緊密的案例為指引，最大化實(shí)踐為導(dǎo)向，重組教學(xué)內(nèi)容，達(dá)到學(xué)以致用。

2）對(duì)學(xué)生實(shí)時(shí)因材施教的教學(xué)方法，精心設(shè)計(jì)教學(xué)內(nèi)容。采用線上線下相結(jié)合，啟發(fā)式與問(wèn)題驅(qū)動(dòng)相結(jié)合的教學(xué)方法，有助于培養(yǎng)和提高學(xué)生對(duì)于計(jì)算的能力。采用案例驅(qū)動(dòng)、啟發(fā)式、層次化、理論課程與實(shí)踐課程相結(jié)合的方法，提高學(xué)生參與課堂的積極性，增加學(xué)生自主學(xué)習(xí)的能力。

3）注重實(shí)踐教學(xué)改革，開(kāi)展多層次的課內(nèi)、課外實(shí)踐教學(xué)，進(jìn)行高質(zhì)量的課程設(shè)計(jì)，直接與企業(yè)直接需求相結(jié)合，形成教學(xué)、實(shí)踐、應(yīng)用生態(tài)圈，促進(jìn)教、學(xué)相長(zhǎng)，進(jìn)而形成良性循環(huán)，更加符合應(yīng)用型人才的要求。

4）提高學(xué)生參與學(xué)科競(jìng)賽的積極性，增加學(xué)生參賽自信心。進(jìn)一步加強(qiáng)專業(yè)實(shí)驗(yàn)室的建設(shè)，增加硬件投入，完善校內(nèi)實(shí)驗(yàn)室設(shè)施，鼓勵(lì)學(xué)生積極投身學(xué)科競(jìng)賽，增強(qiáng)學(xué)生實(shí)踐動(dòng)手能力。加強(qiáng)學(xué)校與企業(yè)之間的合作，結(jié)合企業(yè)實(shí)際需求進(jìn)一步改進(jìn)課程建設(shè)，為社會(huì)輸送高質(zhì)量的應(yīng)用技術(shù)型人才。

5）以O(shè)BE數(shù)據(jù)結(jié)構(gòu)課程為基礎(chǔ)，構(gòu)建多元化的課程考核評(píng)價(jià)體系，結(jié)合課程目標(biāo)[2]，注重過(guò)程考核，著重對(duì)學(xué)生對(duì)具體問(wèn)題進(jìn)行程序設(shè)計(jì)的實(shí)施過(guò)程、綜合應(yīng)用能力、團(tuán)隊(duì)合作等方面進(jìn)行考核，旨在提高學(xué)生綜合素質(zhì)。同時(shí)對(duì)教學(xué)實(shí)施過(guò)程實(shí)施有效的管理，及時(shí)聽(tīng)取督導(dǎo)組、學(xué)生的反饋意見(jiàn)，根據(jù)評(píng)價(jià)持續(xù)不斷改進(jìn)。

3 課程內(nèi)容設(shè)計(jì)

案例的選擇是教學(xué)改革中的核心環(huán)節(jié)之一[3]。選擇合適的案例對(duì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)內(nèi)容設(shè)置而言至關(guān)重要。所謂合適針對(duì)獨(dú)立學(xué)院的學(xué)生而言，主要是要結(jié)合上課所學(xué)的知識(shí)，另外還需要考慮到學(xué)生的層次，學(xué)生理解、接受能力有個(gè)體差異，所以案例難易應(yīng)適當(dāng)，所選案例應(yīng)盡量具有實(shí)際應(yīng)用價(jià)值或者能解決一些有趣的問(wèn)題，讓他們有興趣去學(xué)習(xí)。對(duì)于程度較好的學(xué)生，最好選擇一些具有綜合性的案例，能運(yùn)用到不同的知識(shí)點(diǎn)，達(dá)到融會(huì)貫通，除此之外，綜合性案例還有助于培養(yǎng)學(xué)生的團(tuán)隊(duì)協(xié)作能力。對(duì)于基礎(chǔ)一般的學(xué)生，應(yīng)該通過(guò)案例去引導(dǎo)其去思考，考慮如何運(yùn)用數(shù)據(jù)來(lái)解決問(wèn)題，鼓勵(lì)他們獨(dú)立進(jìn)行代碼編寫(xiě)，有問(wèn)題去尋求解決方案，從簡(jiǎn)單結(jié)構(gòu)開(kāi)始，等上手后再練習(xí)復(fù)雜的數(shù)據(jù)結(jié)構(gòu)應(yīng)用，循序漸進(jìn)。只有這樣，才能進(jìn)一步地提高學(xué)生對(duì)于課程難點(diǎn)的分析、解決能力，實(shí)現(xiàn)自主學(xué)習(xí)，提高學(xué)習(xí)動(dòng)力，達(dá)到課程設(shè)計(jì)的目的。

根據(jù)合作企業(yè)的實(shí)際用人需求，著重提高學(xué)生實(shí)踐操作能力，培養(yǎng)能夠立足于社會(huì)的高質(zhì)量人才，精心設(shè)計(jì)以下與實(shí)際生活結(jié)合緊密的課程設(shè)計(jì)案例，并以*號(hào)標(biāo)出其難易程度，學(xué)生分層次進(jìn)行課程設(shè)計(jì)，達(dá)到學(xué)以致用。

4 課程設(shè)計(jì)實(shí)施過(guò)程

在課程設(shè)計(jì)實(shí)施過(guò)程中，實(shí)現(xiàn)在教師指導(dǎo)下的以“學(xué)生”為中心的探究式教學(xué)。分布式任務(wù)驅(qū)動(dòng)型案例體系要引入具體案例，根據(jù)案例中的問(wèn)題進(jìn)行具體分析，加強(qiáng)學(xué)生主動(dòng)思考問(wèn)題能力，分析問(wèn)題所使用的數(shù)據(jù)結(jié)構(gòu)，應(yīng)用所學(xué)知識(shí)提出合適的解決方案，再通過(guò)編寫(xiě)程序代碼的方式來(lái)驗(yàn)證解決方案是否具備可行性，有效地培養(yǎng)了學(xué)生理論聯(lián)系實(shí)際能力和實(shí)踐動(dòng)手能力。

以串結(jié)構(gòu)為例，“病毒感染檢測(cè)”案例具體實(shí)施流程圖如圖1所示。

4.1 問(wèn)題描述

任務(wù)：將患者的DNA和帶有病毒的DNA標(biāo)記為兩種字母組成的字符串序列，對(duì)患者的DNA序列進(jìn)行檢查，看是否存在帶有病毒的DNA序列。如果出現(xiàn)過(guò)該帶有該病毒的DNA序列，則判斷該患者已感染了該病毒;反之則未發(fā)生感染。需要注意的是，人的DNA序列與病毒的DNA序列形狀不同，分別為線性與環(huán)狀[5]。

4.2 問(wèn)題分析

在此案例中，可以將病毒的DNA序列看作是子串，患者的DNA序列看作是主串，病毒感染檢測(cè)任務(wù)的實(shí)質(zhì)就是看子串是否在主串中出現(xiàn)過(guò)。采用KMP模式匹配算法對(duì)主串中子串的具體位置進(jìn)行查找，查找成功即返回起始位置，否則返回0。

4.3 涉及知識(shí)

1）串的存儲(chǔ)表示;

2）建立串;

3）模式匹配算法;

4）病毒感染檢測(cè)算法。

4.4 算法實(shí)施過(guò)程

1）設(shè)計(jì)串的存儲(chǔ)結(jié)構(gòu)，可以為順序存儲(chǔ)也可以為鏈?zhǔn)酱鎯?chǔ)，為方便操作，采用順序存儲(chǔ)結(jié)構(gòu)。

串的定長(zhǎng)順序存儲(chǔ)結(jié)構(gòu)如下所示：

#define MAXSTRLEN 255

typedef unsigned char SString[MAXSTRLEN+1];

通過(guò)上述代碼即可定義串類型，其包括255元素的串，下標(biāo)為1-255。MAXSTRLEN可根據(jù)具體要操作的數(shù)據(jù)長(zhǎng)度來(lái)設(shè)定。（注意：0單元用于放置串的長(zhǎng)度）

2）定義StrAssign函數(shù)，進(jìn)行串賦值，用于生成一個(gè)值為某一字符串常量的串。進(jìn)行賦值時(shí)需注意，要檢查字符串常量的長(zhǎng)度，若其大于MAXSTRLEN，則無(wú)法放置。賦值時(shí)串的0下標(biāo)位置存儲(chǔ)字符串常量的長(zhǎng)度，串的下標(biāo)為1～字符串長(zhǎng)度中依次存儲(chǔ)字符串常量下標(biāo)為0～字符串長(zhǎng)度-1的字符。

3）定義get_next函數(shù)，完成對(duì)模式串T求解next函數(shù)值，代碼不再闡述。

4）定義Index_KMP函數(shù)，完成KMP模式匹配算法，代碼不再闡述。

5）定義病毒感染檢測(cè)Virus_detection函數(shù)，首先對(duì)病毒DNA序列進(jìn)行擴(kuò)充至兩倍（由于病毒的DNA序列是環(huán)狀的）;然后分段取出病毒序列，調(diào)用get_next（）函數(shù)求解出其對(duì)應(yīng)的next函數(shù)值，再調(diào)用KMP模式匹配算法檢測(cè)病毒序列是否在患者DNA序列中出現(xiàn);最后，只要有一段取出的病毒序列在病人DNA序列中出現(xiàn)，則返回OK，否則，返回ERROR。

int Virus_detection（SString S，SString T）

{

int i，j，m，flag;

SString temp;

m=S[0];

for（i=m+1，j=1;j<=m;j++）

{

S[i++]=S[j];

}

S[2*m+1]='＼0';

for（i=0;i

{

for（j=1;j<=m;j++）

temp[j]=S[i+j];

temp[m+1]='＼0';

temp[0]=m;

get_next（temp，next）;

flag=Index_KMP（T，temp，1）;

if（flag）

break;

}

if（flag）

return OK;

else

return ERROR;

}

6）編寫(xiě)主函數(shù)，完成對(duì)病人DNA序列和病毒DNA序列進(jìn)行賦值，采用病毒檢測(cè)函數(shù)對(duì)患者DNA序列進(jìn)行檢查，若出現(xiàn)病毒序列則為OK，證明輸出存在感染，反之則未出現(xiàn)感染。若還有要檢測(cè)的病人DNA序列，再次進(jìn)行輸入即可。

int main（）

{

SString S，T;

int k;

char flag='Y';

char string1[MAXSTRLEN]，string2[MAXSTRLEN];

printf（"輸入病毒DNA序列："）;

gets（string1）;

while（flag=='Y'）

{

printf（"輸入病人的DNA序列："）;

gets（string2）;

StrAssign（S，string1）;

StrAssign（T，string2）;

k=Virus_detection（S，T）;

if（k）

printf（"患者已感染。＼n"）;

else

printf（"患者未感染。＼n"）;

printf（"是否還有需要檢測(cè)的病人序列？（Y/N）"）;

scanf（"%c"，&flag）;

getchar（）;

}

printf（"您的全部檢測(cè)已結(jié)束，謝謝使用！"）;

return 0;

}

7）編譯鏈接運(yùn)行此程序，輸入病毒和病人DNA序列，得出結(jié)果如圖2所示。

綜上所述，病毒感染檢測(cè)任務(wù)已完成，整體運(yùn)算實(shí)施流程如圖3所示。

4.5 總結(jié)與分析

通過(guò)上述過(guò)程，利用KMP模式匹配算法完成了對(duì)由字符串組成的病毒序列進(jìn)行了病毒感染檢測(cè)。要求同學(xué)們能夠熟練定義串的存儲(chǔ)結(jié)構(gòu)，對(duì)KMP算法的整個(gè)思想有進(jìn)一步的深入了解，對(duì)利用KMP算法解決具體問(wèn)題有進(jìn)一步的掌握。如果需要對(duì)多個(gè)病毒序列進(jìn)行檢測(cè)，也可通過(guò)把病毒序列的輸入放入到while循環(huán)內(nèi)部即可，只需要對(duì)源程序做稍微調(diào)整即可完成。如果數(shù)據(jù)量太多時(shí)，我們可將所有的病毒DNA和患者DNA保存至文件中，逐一讀取，逐一處理來(lái)完成。當(dāng)然除此之外，可以利用KMP算法對(duì)主串中子串的位置和某串出現(xiàn)的次數(shù)進(jìn)行計(jì)算，同學(xué)們可以進(jìn)一步延伸來(lái)利用KMP算法求解其他問(wèn)題。可以看出，KMP模式匹配算法有很廣泛的應(yīng)用。

5 強(qiáng)化實(shí)施過(guò)程管理，進(jìn)行多元化考核

在課程任務(wù)實(shí)施過(guò)程中，強(qiáng)調(diào)簡(jiǎn)單問(wèn)題自主完成，復(fù)雜問(wèn)題分工合作，充分利用小組團(tuán)隊(duì)合作方式，提高學(xué)生的團(tuán)隊(duì)合作及分析解決問(wèn)題的能力。重視過(guò)程化考核，采用分組分階段匯報(bào)形式，來(lái)強(qiáng)化過(guò)程管理，對(duì)學(xué)生遇到的問(wèn)題、掌握的情況能夠深入了解。對(duì)于一些問(wèn)題中的易錯(cuò)知識(shí)點(diǎn)或難度較大的問(wèn)題通過(guò)PPT講解、代碼演示等對(duì)問(wèn)題進(jìn)行進(jìn)一步分析、講解，鼓勵(lì)學(xué)生通過(guò)不同的存儲(chǔ)結(jié)構(gòu)、多種方案完成問(wèn)題求解。最后通過(guò)題目完成個(gè)數(shù)、考勤、課堂表現(xiàn)、代碼質(zhì)量、匯報(bào)等多方面對(duì)學(xué)生靈活運(yùn)行數(shù)據(jù)結(jié)構(gòu)解決具體問(wèn)題的綜合應(yīng)用能力、團(tuán)隊(duì)合作進(jìn)行考核，同時(shí)根據(jù)反饋不斷更新教學(xué)資源，完善教學(xué)方法，加強(qiáng)教學(xué)效果，實(shí)現(xiàn)教學(xué)質(zhì)量的大幅提升。

6 結(jié)語(yǔ)

課程組通過(guò)對(duì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)進(jìn)行精心案例設(shè)計(jì)，更有效地使教學(xué)理論與實(shí)踐緊密結(jié)合，有效地提高學(xué)生的思維計(jì)算能力，對(duì)學(xué)生實(shí)踐能力和程序能力實(shí)現(xiàn)重點(diǎn)培養(yǎng)，彰顯了我院OBE教育理念培養(yǎng)高層次應(yīng)用型人才的辦學(xué)特色。通過(guò)教學(xué)改革，課程設(shè)計(jì)內(nèi)容設(shè)置更加科學(xué)，教學(xué)資源更加完善，考核機(jī)制更加合理，學(xué)生的學(xué)習(xí)效果穩(wěn)步提升，實(shí)踐動(dòng)手能力不斷增強(qiáng)。

參考文獻(xiàn)：

[1] 張安勤，田秀霞，張挺.數(shù)據(jù)驅(qū)動(dòng)的數(shù)據(jù)結(jié)構(gòu)課程案例設(shè)計(jì)研究與實(shí)踐[J].軟件工程，2020，23（4）：54-56.

[2] 王樹(shù)梅，張文斌.基于能力培養(yǎng)的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)教學(xué)模式探討[J].計(jì)算機(jī)教育，2020（11）：103-106，110.

[3] 姜振鳳，黃婕.基于OBE的數(shù)據(jù)結(jié)構(gòu)課程考核評(píng)價(jià)體系設(shè)計(jì)與實(shí)踐[J].計(jì)算機(jī)教育，2020（9）：123-127，132.

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

[5] 嚴(yán)蔚敏，李冬梅，吳偉民.數(shù)據(jù)結(jié)構(gòu)：C語(yǔ)言版[M].2版.北京：人民郵電出版社，2015.

【通聯(lián)編輯：張薇】