案例教学法在数据结构稀疏矩阵十字链表存储与运算教学中的应用

案例教学法在数据结构稀疏矩阵十字链表存储与运算教学中的应用 2011 年 6 月 June 2011 兴义民族师范学院学报 第 3 期No.3 Journal of Xingyi Normal University for Nationalities 案例教学法在数据结构稀疏矩阵十字链表存储与 运算教学中的应用 徐聚星 (贵州财经学院， 贵州 贵阳 550000) 摘 要:数据结构课程作为一门较难的课程开设于低年级本科生教学中，由于学生的抽象逻辑思维有限造成了学习较为困难。通过以稀疏矩阵十字链表存储与运算为例，简单从案例准备、案例与讨 论以及报告撰写等环节进行阐述，分析授课过程中遇到的问题，并予以研究和解决以起到学 。 生在教学中的主体地位、激发学生学习主动性和自主性的目的，实现教学改革的优化。 关键词:数据结构;稀疏矩阵;案例教学 文章编号:1009—0673(2011)03—0059—04 中图分类号:G623.58 文献标识码:A The Application of Case Study Method in Teaching Data Structure Sparse Matrix Orthogonal List Storage and Operation XU Ju- xing (GuizhouU niversity for Finance andE conomics，Guiyang Guizhou 550004，China) Abstract: For undergraduateins junior grade, data structuirse comparatively difficult becausteh eir logic thinking is finite. This paper takes the storageo paendrati on of sparsem atrix cross chian tablef or example, caspere paration, case naalysis andd iscus- sion, and casaen alysis report writing and so on are beeexnp atiated. Problems mewtit h in teaching process aanreal yzed andw orked out, so atso emphasize student- centered teaching msotimdeu,la te students’initiative and autonomy aondpti mize teachingre form eventually. Key words: data structu;resparsem atrix;case teaching 数据结构是计算机专业及相关专业的一门重数据结构教材中运用了大量的程序实例对数据的要的专业基础课程。在该门课程的讲授过程中，主 逻辑结构和存储结构进行阐述，但由于该门课程 要研究和讨论各种数据类型的逻辑结构和存储结 的逻辑复杂度要求较高，或教师过高估计学生初 构。学生通过对数据结构课程的学习，能够掌握使 次接触和理解抽象逻辑问题的能力，因此造成部 用数据结构的基本分析方法来提高编写程序的能 分教师在授课过程中对某些较为抽象的数据类型 力和应用计算机解决问题的能力。目前，在诸多的 讲授的较为随意，使得学生在理解和学习上出现 收稿日期,2011—05—11 作者简介,徐聚星(1983)，男(回族)，贵州遵义人，贵州财经学院讲师，研究方向:数据结构—、 计算机网络。 全适应学习对象由于数据结构课程多在低年存，必然造成大量存储空间的浪费，而且在真实的。 工程计算中高阶稀疏矩阵的存储带来的浪费是无 本科生中开设，其接触到的高级语言较为有限，法承受的，所以在数据结构中提出了不仅要对非 析抽象逻辑问题的能力也有待于提高，所以认 对教学中案例的描述最好以学生熟悉的编程语零元素进行有效保存，还要保持其固有逻辑结构。 环境为主，比如 VC++、C# 等，而且在讲授过程 但由于矩阵中零元素的分布又是没有规律可寻 的，如何在实际运用中高效、准确、便捷的构造出 做到深入浅出，并让学生尽可能多的参与到案 的分析和讲解中，以提高学生的学习兴趣。除此其存储结构，便是十字链表存储需要解决的问题。 用十字链表存储稀疏矩阵的基本思想是把每外，首先在教学过程中应多注重对案例的分析 个非零元素作为一个结点进行存储，在结点中除 实践，培养学生分析能力和动手能力，并尽可能 了非零元素的值外还增加了该元素所在矩阵中的 参与到对案例的讲解中，使之与理论部分相互行坐标和列坐标，并且额外构建两个指针域，用来 合，巩固所学到的理论知识。其次在案例的选取分别指向该元素所在行的下一个非零元素和所在 面应更加贴近与实际编程环境，讲授中可根据列的下一个非零元素。其结构为图 1- 1。 序的真实运行逻辑逐步对每条程序语言进行分 和讲解，并将时间复杂度和空间复杂度以及程 逻辑进行扩展，使学生时时处于真实或仿真环 中，对问题进行研究和设计最后在案例教学中。 学生能够达到人人参与，可类似于 MBA 教学 的教学模式，多提出问题让学生进行分组讨论， 图 1- 1 励学生对讨论结果进行全班性的发言，帮助学 其中 i 值代表行坐标，j 值代表列坐标，v 值代解答疑难问题，并进行归纳和总结。 表元素值，down 指针指向列的下一个非零元素， 二、稀疏矩阵十字链表存储案例教学法应用 right 指针指向行的下一个非零元素。而行、列链 例 稀疏矩阵作为数据结构课程中较为靠后的章表的头结点和普同结点相同，行链表的头结点只 用到 right 指针域，列链表的头结点只用到 down ，其逻辑结构中包含了线性表的部分知识，而存 指针域，根据头结点的特点在实际运用中为了节 结构主要以链表为主，也涉及到了循环链表和 向链表的相关内容。并且由于其本身的特点还约存储空间，行链表头结点组和列链表头结点组 可对应使用相同的存储结点空间。为了后续运算 够采用三元组存储和带行指针的链表存储等方 方便，还可将这些头结点首尾相连形成一个循环 ，造成了学生在进行这一章节的学习时较容易 链，而第一个头结点的值域为空，可以作为连接各 所学知识进行混淆概念模糊不清抽象逻辑思、、 头结点的链域，并可用已定义好的指针指向该结 混乱等问题的出现所以在讲授的过程中，首先。 点。其结构为图 1- 2。其中行结点[1]与列节点[1]为 对所学知识进行归纳和总结，并对不同数据类 同一个指针结点，而因该矩阵为非方阵，所以头结 的逻辑结构和存储结构进行比较分析;其次通 点多定义了一个[5]号结点。 案例教学的方法和原则对稀疏矩阵的特点进行 解;最后让学生实际参与到稀疏矩阵的扩展运 2011年 徐聚星 第 3 期 案例教学法在数据结构稀疏矩阵十字链表存储与运算教学中的应用 for(i=1; irow=0; p>- col=0; p- >right=p; p>- down=p; hd[i]=p; hd[i- 1]- >v_next.next=p;} // 将 头 结 点 们 hd[S]- >v_next.next=H; 形成循环链表 其次可通过 for 循环为每一个元素赋值，并 结合其逻辑结构将其插入到相应的存储结构中 去，算法如下: for(k=1;k<=t;k++) 图 1- 2 其结点的结构定义为:typedef structn ode scanf( %d,%d,%d,&i,&j,&v);// 输入一 {“”{ int i,j; 个三元组 p= new MNode; struct node*d own,*right; p- >row=i; p- >col=j; p- >v_next.v=v union v_nest { datatype v; q=hd[i]; while (q- >right!=hd [i]&&(q- >right- >col)right; }Mnode,*Mlink; 2.案例分析与讨论p- >right=q-> right; // 插入 q- >right=p; q=hd[i]; 在稀疏矩阵十字链表的建立算法设计中，首 先需要输入的信息有 m(矩阵的行数)，n(矩阵的 while(q- >down!=hd[j]&&(q- >down-> row)down; // 插入 头结点的空链表，并建立起这些头结点组成的循 p- >down=q>- down; 环链表;然后每输入一个三元组(i,j,v)，则将其结 q- >down=p; } 点按其列号的大小插入到第 i 个行链中去，同时 也按其行号的大小将该结点插入到第 j 个列链表 通过对创建稀疏矩阵十字链表存储算法的讲 解和分析，在授课过程中可让学生分组以稀疏矩 中去。在算法中将利用一个辅助数组 Mnode?hd 阵十字链表存储为基础，讨论设计出稀疏矩阵的 [s+1];其中 s=max(m,n)，hd[i]指向第 i 行(第 j 列) 加法，并对设计进行编写和发言。 链表的头结点。在算法中首先需要建立行列的头 在讨论之前可对该算法进行简单的引导说 结点，并将其构建成循环链表算法如下: MLink H; 明，已知两个十字链表存储的稀疏矩阵 A 和 B， Mnode*p,*q,*hd [s+1]; 计算 C=A+B，C 也采用十字链表方式存储，并且 int i,j,m,n,t; datatype v; 在 A 的基础上形成 C。由矩阵的加法规则知，只 scanf(d%,d%,%d,&m,&n,&t); ""有 A 和 B 行列对应相等，二者才能相加。C 中的 非零元素 cij 只可能有 3 种情况:或者是 aij+bij， H=new MNode; // 申请总头结点 或者是 ai(j bij=0)，或者是 bi(j aij=0)，因此当 B 加 H- >row=m; 到 A 上时，对 A 十字链表的当前结点来说，对应H- >col=n; 下列四种情况:或者改变结点的值(aij+bij0)， ?hd[0]=H; 或者不变(bij=0)，或者插入一个新结点(aij=0)， (1)若 pa- >col=pb- >col 且 pa- >v+pb-> v?0， 而文中所提及的知识点也相对较窄，算法也不够 完整和精确，在今后的教学研究过程中，还需通 、只要用 aij+bij 的值改写 pa所指结 点的值域即 。过引入更多的教学方法对课程和算法加以完善， (2)若 pa-> col=pb- >col 且 pa- >v+pb-> v=0， 以起到教为所用，教学相长的目的。需要在矩阵 A 的十字链表中删除 pa 所指结 ，此时需改变该行链表中前趋结点的 right 域， 参考文献: 及该列链表中前趋结点的 down 域。 [1]戎丽霞. 数据结构课程教学改革探索与实 (3)若 pa-> col < pb- >col 且 pa-> col?0(即不 践[M]. 科技创新导报.2011(13) . 表头结点)，则只需要将pa 指 针向右推进一步， [2]梁瑜. 数据结构教学方法探讨[M]. 福建电 脑，2005(10). 继续进行比较。 (4)若 pa-> col > pb- >col 或 pa-> col=0(即是 [3]孙秀惠. 数据结构教学方法探讨[J]. 科技 资讯，2006(31). 头结点)，则需要在矩阵A 的十字链表中插入 个 pb 所指结点。 [4]耿晓中. 数据结构教学研究与探索[J]. 长 春师范学院学报，2007(06) . 3.案例报告分析 [5]刘建国. 高职数据结构课程教学方法改革 在完成整个稀疏矩阵十字链表存储与运算教学 探讨[J]. 北京市经济管理干部学院学报2007，(02) . ，可根据每个分组所讨论修改出的结果进行上 责任编辑:梅秀全 实践，并根据实践情况撰写出案例上机分析报 接第 58 页)为严重大三学生对大学学习有 。健康教育，使其形成良好的心理状态，让学生主动 地、愉悦地投入到学习中。 更为深刻的理解，对未来的规划也有了清楚的 解，去设定新的人生目标，因而他们有更强烈的 习动机，将更多的精力投入到学习中。大一学生参考文献: [1]杨丽娴，莲蓉.学习倦怠的研究现状及展望 课程负担相对较轻，对大学也充满了憧憬，也希 [J].集美大学学报，2005(2). [2]赵红,李飞.地方高师 在新的环境里展现才华，处处充满激情，因而倦 院校学生学习倦怠状 程度较轻。 况实证探析[J].通化师范学院学报，2010(5):87- 90. 五 对策和建议 (一) 进一步改进教学方法，尤其针对贵州省 [3]曹海宾等.综合性大学师范类学生学习倦 怠 现状研究[J].兵团教育学院学报，2009(5):49- 52. [4] 学生的学习基础较差，缺乏学习主动性，更要充 陈妮娅.大学生学习倦怠调查研究[J].现代 调动学生学习的积极性，避免其产生学业倦怠。 教育，2010 (1):190-191 . [5]郭彩琴,肖海雁.大学生(二) 增强专业认同感，让学生从情感上接受 学习倦怠的现状分 己所学专业，不以专业好坏而喜悲，灌输干一“ 析[J]. 山西大同大学学报(社会科学版)，2009(8): ，爱一行”的思想，让学生从理性认识上得到升 93- 94. 。