應用型獨立學院數據結構課程案例設計

張新彩 鄔迎

摘要：針對數據結構課程設計實施過程中存在的問題進行了分析，結合應用型獨立學院學生的特點，課程組精心設計課程設計案例，并舉例說明案例實施過程，通過有效的過程管理，達到課程設計目的。

關鍵詞：數據結構;課程設計案例;過程管理

中圖分類號：G423? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）21-0172-03

開放科學（資源服務）標識碼（OSID）：

在進行計算機相關專業的學習中，數據結構課程是非常重要的一門較為基礎的課程，在眾多學科中具有很重要的地位[1]。數據結構課程理論教學多以講授線性結構、樹、圖、查找和排序等知識，由于實踐性較強，各個學校都安排了一定學時的課程設計，以使學生能靈活地選擇合適的邏輯結構、存儲結構，并能利用算法來解決實際生活中的問題，以進一步提升學生使用程序解決實際問題的能力。文獻[2]提出一種基于能力培養的教學模式，將教學設計分成3個階段，旨在提高學生的綜合應用能力。

1 課程設計存在的問題

經過授課數據結構課程和進行課程設計的經驗得知，學生的學習效果并不理想。究其原因，主要存在如下方面：

1）理論與應用相脫節。現階段，有相當一部分學生，在學習完數據結構后，只知道如何做題，卻不知它的意義何在？能用它干什么？究其原因主要是沒有理解其含義，再就是與實踐脫節，這就要求老師在講解相關知識的時候多講一些具體應用，另外在課程設計環節針對相關知識點設計一些具體案例，加深學生對知識的理解。

2）程序設計基礎較弱。就獨立學院而言，通常是入學第一學期學習程序設計語言，第二學期開設數據結構課程，但通常因為大多數學生之前沒有接觸過計算機語言，一開始學習程序設計有一定難度，很多學生一學期下來也僅達到能基本獨立編寫較簡單程序的程度，對算法的理解和應用還不夠透徹，而此課程又跟數據結構關系較緊密，導致其在數據結構實踐環節完成實驗時舉步維艱。

2 課程設計改革思路

課程組也針對上述問題，提出并實施如下改革思路。

1）結合企業實際需求，以立足培養高質量的應用技術型人才為目標，注重培養學生實踐動手能力，以學科前沿、與實際結合緊密的案例為指引，最大化實踐為導向，重組教學內容，達到學以致用。

2）對學生實時因材施教的教學方法，精心設計教學內容。采用線上線下相結合，啟發式與問題驅動相結合的教學方法，有助于培養和提高學生對于計算的能力。采用案例驅動、啟發式、層次化、理論課程與實踐課程相結合的方法，提高學生參與課堂的積極性，增加學生自主學習的能力。

3）注重實踐教學改革，開展多層次的課內、課外實踐教學，進行高質量的課程設計，直接與企業直接需求相結合，形成教學、實踐、應用生態圈，促進教、學相長，進而形成良性循環，更加符合應用型人才的要求。

4）提高學生參與學科競賽的積極性，增加學生參賽自信心。進一步加強專業實驗室的建設，增加硬件投入，完善校內實驗室設施，鼓勵學生積極投身學科競賽，增強學生實踐動手能力。加強學校與企業之間的合作，結合企業實際需求進一步改進課程建設，為社會輸送高質量的應用技術型人才。

5）以OBE數據結構課程為基礎，構建多元化的課程考核評價體系，結合課程目標[2]，注重過程考核，著重對學生對具體問題進行程序設計的實施過程、綜合應用能力、團隊合作等方面進行考核，旨在提高學生綜合素質。同時對教學實施過程實施有效的管理，及時聽取督導組、學生的反饋意見，根據評價持續不斷改進。

3 課程內容設計

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

根據合作企業的實際用人需求，著重提高學生實踐操作能力，培養能夠立足于社會的高質量人才，精心設計以下與實際生活結合緊密的課程設計案例，并以*號標出其難易程度，學生分層次進行課程設計，達到學以致用。

4 課程設計實施過程

在課程設計實施過程中，實現在教師指導下的以“學生”為中心的探究式教學。分布式任務驅動型案例體系要引入具體案例，根據案例中的問題進行具體分析，加強學生主動思考問題能力，分析問題所使用的數據結構，應用所學知識提出合適的解決方案，再通過編寫程序代碼的方式來驗證解決方案是否具備可行性，有效地培養了學生理論聯系實際能力和實踐動手能力。

以串結構為例，“病毒感染檢測”案例具體實施流程圖如圖1所示。

4.1 問題描述

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

4.2 問題分析

在此案例中，可以將病毒的DNA序列看作是子串，患者的DNA序列看作是主串，病毒感染檢測任務的實質就是看子串是否在主串中出現過。采用KMP模式匹配算法對主串中子串的具體位置進行查找，查找成功即返回起始位置，否則返回0。

4.3 涉及知識

1）串的存儲表示;

2）建立串;

3）模式匹配算法;

4）病毒感染檢測算法。

4.4 算法實施過程

1）設計串的存儲結構，可以為順序存儲也可以為鏈式存儲，為方便操作，采用順序存儲結構。

串的定長順序存儲結構如下所示：

#define MAXSTRLEN 255

typedef unsigned char SString[MAXSTRLEN+1];

通過上述代碼即可定義串類型，其包括255元素的串，下標為1-255。MAXSTRLEN可根據具體要操作的數據長度來設定。（注意：0單元用于放置串的長度）

2）定義StrAssign函數，進行串賦值，用于生成一個值為某一字符串常量的串。進行賦值時需注意，要檢查字符串常量的長度，若其大于MAXSTRLEN，則無法放置。賦值時串的0下標位置存儲字符串常量的長度，串的下標為1～字符串長度中依次存儲字符串常量下標為0～字符串長度-1的字符。

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

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

5）定義病毒感染檢測Virus_detection函數，首先對病毒DNA序列進行擴充至兩倍（由于病毒的DNA序列是環狀的）;然后分段取出病毒序列，調用get_next（）函數求解出其對應的next函數值，再調用KMP模式匹配算法檢測病毒序列是否在患者DNA序列中出現;最后，只要有一段取出的病毒序列在病人DNA序列中出現，則返回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）編寫主函數，完成對病人DNA序列和病毒DNA序列進行賦值，采用病毒檢測函數對患者DNA序列進行檢查，若出現病毒序列則為OK，證明輸出存在感染，反之則未出現感染。若還有要檢測的病人DNA序列，再次進行輸入即可。

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（"是否還有需要檢測的病人序列？（Y/N）"）;

scanf（"%c"，&flag）;

getchar（）;

}

printf（"您的全部檢測已結束，謝謝使用！"）;

return 0;

}

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

綜上所述，病毒感染檢測任務已完成，整體運算實施流程如圖3所示。

4.5 總結與分析

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

5 強化實施過程管理，進行多元化考核

在課程任務實施過程中，強調簡單問題自主完成，復雜問題分工合作，充分利用小組團隊合作方式，提高學生的團隊合作及分析解決問題的能力。重視過程化考核，采用分組分階段匯報形式，來強化過程管理，對學生遇到的問題、掌握的情況能夠深入了解。對于一些問題中的易錯知識點或難度較大的問題通過PPT講解、代碼演示等對問題進行進一步分析、講解，鼓勵學生通過不同的存儲結構、多種方案完成問題求解。最后通過題目完成個數、考勤、課堂表現、代碼質量、匯報等多方面對學生靈活運行數據結構解決具體問題的綜合應用能力、團隊合作進行考核，同時根據反饋不斷更新教學資源，完善教學方法，加強教學效果，實現教學質量的大幅提升。

6 結語

課程組通過對數據結構課程設計進行精心案例設計，更有效地使教學理論與實踐緊密結合，有效地提高學生的思維計算能力，對學生實踐能力和程序能力實現重點培養，彰顯了我院OBE教育理念培養高層次應用型人才的辦學特色。通過教學改革，課程設計內容設置更加科學，教學資源更加完善，考核機制更加合理，學生的學習效果穩步提升，實踐動手能力不斷增強。

參考文獻：

[1] 張安勤，田秀霞，張挺.數據驅動的數據結構課程案例設計研究與實踐[J].軟件工程，2020，23（4）：54-56.

[2] 王樹梅，張文斌.基于能力培養的數據結構課程設計教學模式探討[J].計算機教育，2020（11）：103-106，110.

[3] 姜振鳳，黃婕.基于OBE的數據結構課程考核評價體系設計與實踐[J].計算機教育，2020（9）：123-127，132.

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

[5] 嚴蔚敏，李冬梅，吳偉民.數據結構：C語言版[M].2版.北京：人民郵電出版社，2015.

【通聯編輯：張薇】