应用型独立学院数据结构课程案例设计

张新彩 邬迎

摘要：针对数据结构课程设计实施过程中存在的問题进行了分析，结合应用型独立学院学生的特点，课程组精心设计课程设计案例，并举例说明案例实施过程，通过有效的过程管理，达到课程设计目的。

关键词：数据结构;课程设计案例;过程管理

中图分类号：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.

【通联编辑：张薇】