第一篇:《数据结构》实验教学方法探讨的教育论文
摘要:《数据结构》是计算机专业的专业基础课程,具有很强的实践性。本文结合笔者在课程教学的一些体会,从实验教学设计、实验教学手段等方面对《数据结构》实践教学方法提出自己的一些看法和建议。
关键词:数据结构实验教学
引言
《数据结构》是计算机专业课程体系的核心课程之一。课程主要讲述各种数据的逻辑结构、物理结构及基本操作的实现算法以及数据查找、排序算法,并对各种算法进行性能分析和比较。
根据调查发现,目前大多数院校《数据结构》课程教学现状不容乐观。学生普遍反映课程学习比较困难,教师也感觉教学效果不理想。实验教学更是因为程序设计语言基础不扎实、课程内容太抽象等原因而较难开展,有些学校因此而缩短学时甚至不开设实验。一些专家和教师就课程实验教学改革已经提出了一些具体的教学方法,如案例驱动、课题答辩等。这些方法都具有比较重要的借鉴价值,但某些文章过于片面的强调某一种教学方法。笔者认为根据学生的实际情况完善教学设计、加强教学管理,通过行之有效的教学手段使学生学有所获才是根本。下面结合自己的实际教学工作,谈谈对数据结构实验教学方法的认识。我校《数据结构》课程理论学时48,实践学时16,教材选用严蔚敏的《数据结构(C语言版)》)。
1讲好理论第一课,明确课程性质
仅从课程名称来看,《数据结构》就很容易被误解为实践性不强的理论课。讲好第一堂理论课非常重要,应让学生明确课程性质并理解实践学习的重要性。
结合程序设计语言、操作系统等课程内容,笔者设计了一些学生比较熟悉并容易理解的应用实例和学生一起探讨,如:inta[10]和a[i]=5的确切含义;文件簇的链式形态;国际象棋大师与超级计算机的对决;图的着色问题等。在讲解图的着色问题时引导学生思考图的存储中需要关心什么,怎么存以及大致的程序逻辑等。通过对实例的分析,引入课程主要内容,学生也可明确课程的性质和专业地位并思考课程学习目标。
2制定实验教学计划,设计实验内容
程序设计语言是数据结构的前驱课程之一,多数院校都是以C语言程序设计作为学生程序逻辑训练的课程。数据结构教材中采用类C语言来描述算法,对指针、结构体等内容并未作详细的介绍。对于刚刚学完C语言的学生来说,指针等内容本来就比较模糊,要将类C算法转换为程序实现就更加困难。
在制定实验教学计划时,可以采用由易到难、逐步加深的方式来安排实验内容。结合实验学时数和教学大纲要求,笔者将实验内容作了如下设计和安排:
2.1第一次上机任务只要求学生运用以前学过的C语言知识来编写一个程序:给定一个整数序列,要求①用冒泡或选择算法进行排序;②输入一个整数X,在此有序序列中进行查找,如成功,则返回其位置;③如查找不成功,将X插入到序列中并使序列仍然有序。此题目运用到数组的定义、排序、查找、数组元素插入算法等相关内容。通过此实验,不仅能了解学生程序语言的熟悉程度,也能了解学生对排序和查找等基础算法的掌握情况,为后面教学内容设计作好铺垫。
2.2结合教学进度要求学生实现常见数据结构的基本操作,并能作一些验证性的实验。如用数字菜单的形式实现单向链表的基本操作,并完成两个有序链表合并算法的验证。实验要求学生能实现大多数基本操作算法,完成头文件的设计,并能利用已实现的基本操作完成复杂算法的验证。通过此类实验,学生对数据结构的理解更直观,程序逻辑更清晰,C语言的掌握能力逐渐增强,同时也为面向对象课程的学习打下一定的基础。
2.3设计性实验即课程设计安排。课程设计的目的在于培养学生分析和解决实际问题的能力,训练和提高学生规范的程序设计方法。教师可推出一些典型的并与后续课程有一定联系的题目供学生选择。每个题目规模不能太小,并能反映相关数据结构在程序设计中起的关键作用。如:①实现一个串的基本操作演示程序,提供命令行的输入(仿照COMMAND),并对命令行能进行简单的编译和出错处理,最后根据命令动词的功能来执行命令;②利用哈夫曼编码算法实现简单文本文件的压缩和解压。题目随着理论教学进度推出,有难有易,学生结合自己实际来选择并可提前完成。
3规范实验过程,加强实验教学管理
为保障计划的有效实施,必须规范实验过程并加强实验教学管理。
3.1根据计划制定实验指导书。指导书中给出每个实验的目的、学时、内容等。其中设计性实验另给出一些基本的分析思路,每个实验都适当的添加一些选作题。学生通过阅读实验指导书能进一步明确每次实验的具体内容和要求。
3.2要求学生做好上机前的准备。大二学生的编码速度普遍较慢,如果把实验课时间主要用于输入代码是非常不值得的,应将主要精力放在程序调试上面。这样不仅有充足的提问时间,也便于教师归纳并集中讲解学生调试过程中所遇到的常见问题。
3.3要求学生实验后完成实验报告。报告中须给出问题分析、数据描述、算法描述、程序描述、测试结果和心得体会等内容。教师对学生提交的实验报告进行分析,总结并指出实验的成功和不足之处。
3.4加强实验教学管理,从正面引导学生。随着网络信息技术的发展,网络中提供的各种信息服务和娱乐方式使部分学生的学习积极性逐渐降低,学习目标也越来越不明确。如果管理松懈,有些学生就会把实践学习当成是简单的Ctrl-C和Ctrl-V,不能达到实验教学的预期目标。因此,教师应了解学生的学习动态,加强实践教学管理,并根据实际情况进行相应调整和改进。
4丰富教学手段,搞好实验指导
在实践教学过程,教师不能只停留于解决学生提出的问题,还应不断摸索教学方法,丰富教学手段。
4.1演示基本算法实现时可采用互动的方式进行。先按类型定义→初始化→输入测试数据→输出的实现顺序和学生一起得到结果;再让学生逐个实现其余算法,最后完成头文件的设计。学生通过教师演示和实际操作可以更快的掌握类C算法和C程序的转换思路。
4.2数据结构中的程序规模相比C语言来说更大。由于缺乏经验,很多学生在程序调试中会出现较多的语法和逻辑错误,可利用多媒体网络教学手段在学生机上直接演示并讲解程序调试的方法和技巧。
4.3学生实验过程中尽力营造一种你追我赶的竞争氛围,通过激励机制提高学生学习积极性。如果有同学较早实现了某些算法,可有选择性的适当的“刺激”部分学生以激发其不服输的心理,从而带动其他学生。
4.4鼓励学生多实践,要求学生通过实践来找出理论学习中存在的问题,提高自己的抽象思维和逻辑推理能力。对于编程能力较强的学生,鼓励他们多做题,做难题,为今后参加各种资格水平考试和专业竞赛作好准备。
5总结
《数据结构》是一门理论和实践结合性非常强的课程,其课程性质决定了教学过程的复杂性。作为承担课程教学的老师,不管是理论教学还是实验教学,都应结合学生的特点,从教学设计、教学手段、教学管理等多方面进行深入具体的探讨和研究,并运用到教学实践中。只有这样,才能真正使学生理解《数据结构》课程意义和课程核心地位。
参考文献:
[1]严蔚敏,吴伟民.《数据结构(C语言版)》[M].北京:清华大学出版社.1997.[2]黄现代.“数据结构”课程教学改革与实践[J].北京:计算机教育.2007(16).[3]李丹丹.数据结构教学改革与实践[J].北京:北京城市学院学报.2007(3).
第二篇:大学物理实验教学方法反思论文
[摘要]知识经济时代的来临,促进了复合型人才和高新型技术人才的发展,我国高校为了让高水平的专业人才在多领域中发挥重要的推动作用,在实际教学中不断地研究创新教学方式,从而促进高校人才的培养。而在大学物理实验教学中,当前的教学方式还无法将教学的效果完美体现,高校需要在教学方式的选择上,同时代的发展相结合,创新培养方式,推动创新型人才的培养。因此,从大学物理实验教学的理论基础开始分析,对物理规律探索下的物理实验教学方法简要阐述,通过构建大学物理实验教学的模型,以促进教学成效的优化。
[关键词]物理规律探索;大学物理实验;教学方式创新
当前社会的发展促进了人才的发展,许多高新型技术人才逐渐展露出自身的积极意义,其不仅能够作为国家经济和国立发展的动力,还能够让社会各行各业中的高层次发展水平进一步提升。所以,在物理学科中,高水平专业人才的培养成为重点的教学目标之一。物理学科在长期的教学发展中,逐渐形成了有关教学的重要的指导思想和探索物理知识的规律和方式,这些规律能够有效的促进学生对物理学科的认知,为学生的物理创造力提供有力的知识基础。近些年,物理规律探索下的大学物理实验教学方式被广泛关注,教师需要在整理完善理论基础以及实验方法的基础上,不断的开创新的教学模式,帮助我国创新型人才的培养模式更加系统化。
1大学物理实验教学的理论基础
1.1元认知理论
主体认知活动的认知是元认知理论的主要内容,其中包含了自身认知能力、认知过程以及这两者之间的相互作用,这一理论主要研究元认知知识、元认知监控、元认知体验。元认知知识主要对认知的规律和知识内容的研究;元认知监控主要是指认知活动的运用过程;而元认知体验则是包含了监控过程中产生的不同情绪,一些人的自我效能感较高,在元认知监控过程中,体会的经验会较多。现代教学中,自主学习能力的培养和元认知能力的培养相符[1],大学中为学生开展的不同类型的教育活动能够有效的促进学生的认知能力和认知情感发展,让学生通过不同的渠道,掌握正确的思维方式,提升自我效能感。
1.2交往学习理论
这一理论主要是指学习者通过和其他人的交流、沟通、互动,完善致使的获取和能力的提升,所以,这一理论又被称为人及学习理论,或者沟通学习理论。在实际的学习中,学习者之间的沟通要在平等、自由的基础上,沟通双方保持尊重,并且在沟通的过程中,能够获得灵感、启发、借鉴,促进学习者的学习效果,让学习者从思想误区中走出来,促进双方的心理和智力的提升。这样,才能是良好的沟通交流。而大学教学中,交往学习理论能够完美的运用在其中,学生和教师之间、学生和学生之间都能够进行交流,尤其在实践中,通过合理的组员分配,对单一问题实现充分的研究探讨[2]。
2物理规律探索下的大学物理实验教学方式
2.1教学方式中的观察实验法
大学物理学方法论在物理学的发展中,经过了漫长的过程之后,形成了较为成熟的科学探索方法,其中包含了许多极为有益于物理学发展的方式。而观察实验法在物理学研究上属于基础的探索方式,大多数物理规律的发现和生活观察以及实验的验证结果有着直接的关系。例如:牛顿发现了万有引力现象等等,但是,在生活中,很多物理现象致使表面人们看到的现象,并且这些现象还有可能误导人得出错误的结论,例如:物体下落速度和物体的重量成正比这一说法。物理学研究需要经过漫长的观察实验,验证总结之后,循环往复的找出其中的新型规律,这样才能保证在长期的发展中,实现物理学的拓展。
2.2教学方式中的逻辑思维法
逻辑思维顾名思义使用思维上的逻辑分析,将物理现象通过归纳演绎、系统分析、推论验证、假说试验真方式,将物理规律的过程发现。逻辑思维法得出的结论需要在事实材料为依据的基础上实现,否则得出的结论必然会被推翻。而在归纳演绎中,就是将大量的事实依据进行归纳,对其中的次要因素和干扰性因素排除之后,将不同的环节进行研究,而后对不同环节中的研究成果综合分析,最终完成复杂的问题研究,例如:物理学中的力学分解、微元思想等等。而推论验证主要是对已经看到的事实或者现象提出一种假设[3],这种假设需要符合物理学基本的理论,而后,再通过试验的方式,对得出的假设进行验证,一般会需要大量的实验来完成这一步,如果实验法对同一个问题提出了不同假说,那么在采用不同方式进行论证的同时,能够将错误的观点排除,通过不断地验证之后,将正确的结论得出,从而实现物理学的规律验证。
2.3教学方式中的数学方法
这一方法在物理规律探索中,属于重要的方式,数学方法不仅仅能够将物理学研究计算推理,还能够将数学中的思维运用到物理学中,帮助物理学的研究更加深入化。例如:瞬时速度、电场强度和磁场感应等等都应用了数学思维。
3结语
物理规律探索下的大学物理实验教学更加有利于学生的物理思维培养,教师要用科学的教学方式激发学生对物理学习的兴趣,从而引导性地促进学生创新意识的产生,为创新型人才的培养提供良好的发展基础。
【参考文献】
[1]李冬梅.基于物理规律探索下大学物理实验教学方法的研究[J].高教学刊,2018,34(5):88-90.[2]张春玲.基于物理规律探索的大学物理实验教学方法初探[D].上海:华中师范大学,2014.[3]梅策香,柳钰,曾利霞.大学物理教学方法中实验教学的作用研究[J].科技经济导刊,2016,34(29):171.
第三篇:数据结构 实验指导书
数 据 结 构 实 验 指 导 书
数据结构实验指导书
目录
数据结构实验指导书.......................................................................................................................1
目录...........................................................................................................................................1 实验指导书概述...............................................................................................................................2 上机实验题目...................................................................................................................................3
实验一 C语言相关知识复习................................................................................................3
一、实验目的...................................................................................................................3
二、实验内容...................................................................................................................3 实验二 单链表的插入、删除...............................................................................................3
一、实验目的...................................................................................................................3
二、实验内容...................................................................................................................3
三、实现提示...................................................................................................................4 实验三 栈及其应用.................................................................................................................5
一、实验目的...................................................................................................................5
二、实验内容...................................................................................................................5 实验四 二叉树的递归算法.....................................................................................................6
一、实验目的...................................................................................................................6
二、实验内容...................................................................................................................6 实验五 图的遍历.....................................................................................................................7
一、实验目的...................................................................................................................7
二、实验内容...................................................................................................................7 实验六 有序表的查找.............................................................................................................7
一、实验目的...................................................................................................................7
二、实验内容...................................................................................................................7 实验七 哈希表.........................................................................................................................7
一、实验目的...................................................................................................................7
二、实验内容...................................................................................................................7 实验八 内部排序算法的应用.................................................................................................8
一、实验目的...................................................................................................................8
二、实验内容...................................................................................................................8
实验指导书概述
“数据结构”是计算机专业一门重要的专业技术基础课程,是一门关键性核心课程。本课程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法,介绍了多种常用的查找和排序技术,并对其进行了性能分析和比较,内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。
由于以下原因,使得掌握这门课程具有较大难度: 内容多,时间短,给学习带来困难;
贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点; 隐含在各部分的技术和方法丰富,也是学习的重点和难点; 先修课程中所介绍的专业性知识不多,加大了学习难度。
由于数据结构课程的技术性与实践性,《数据结构课程实验》的设置十分必要。为了帮助学生更好地学习本课程,理解和掌握算法设计所需的技术,为整个专业学习打好基础,要求运用所学知识,上机解决一些典型问题,通过分析、设计、编码、调试等各环节的训练,使学生深刻理解、牢固掌握所用到的一些技术。
上机实践是对学生的一种全面综合训练,是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通过上机实践,使学生在可能短的时间内对数据结构知识的实践和应用有一个比较全面和系统的认识,达到理论与实践相结合的目的。
为了达到上述目的,本指导书安排了8个实验题目,它们与教科书的各章有紧密的关系,使学生在实验后能加深对课程内容的理解,增强动手能力。
每个实验题目采取了统一的格式,由问题描述、基本要求、测试数据、实现提示等部分组成。
问题描述旨在为读者建立问题提出的背景环境,指明问题“是什么”;
要求则对问题进一步求精,划出问题的边界,指出具体的参量或前提条件,并规定该题的最低限度要求;
测试部分旨在为检查学生上机作业提供方便,在完成实习题时应自己设计完整和 严格的测试方案,当数据输入量较大时,提倡以文件形式向程序提供输入数据;
实现提示对实现中的难点及其解法思路等问题作了简要提示,个别问题给出了参考实现。
下面带*的题目为选做题目。
上机实验题目
实验一 C语言相关知识复习
一、实验目的
复习C语言中函数、数组、结构体、文件等概念,掌握它们的描述与操作方法;熟悉掌握C++中typedef、引用参数调用(&)的概念及使用方法,为理解数据结构课程的后续内容以及算法书写奠定基础。
二、实验内容 问题描述:编写一个函数,求一个整数数组中的最大、最小值。
要求:在函数声明中采用引用参数传递方式实现最大、最小值的返回。测试:在主函数中输入10个数,调用此函数,打印输出最大和最小值。2 关于指针的使用:
用malloc方式分别申请两个指针,并实现两个指针内容的比较大小操作。要求:此功能在一个函数内实现,该函数接受两个整数值,存储到两个指针内容中,输出两者中的最大值。
测试:从主函数中输入两个数,调用该函数,打印输出交换后的值。
实验二 单链表的插入、删除
一、实验目的
1、熟悉某种数据结构在计算机上实现的方法。
2、掌握单链表的定义、创建、插入、删除、遍历等基本操作的实现。
3、体会单链表操作、有序表插入、删除的一般方法。
二、实验内容
问题描述:已知递增有序的单链表A,编写算法实现向A中插入或删除一个元素,并保持A的有序性。
实验要求:
1、结点的数据均为整型。
2、若表中已经存在此元素,则不插入
三、实现提示
1.在已知的线性表中插入或删除,需要下面的辅助函数:线性表的创建、线性表的遍历
2.在单链表表中插入或删除,需依次实现:
a)单链表结构的定义
b)单链表的创建(头插法或尾插法建表)c)单链表的遍历
d)单链表的插入、删除(采用顺序查找方法,顺头指针往后,查找插入或删除位置,再修改指针)
//头文件
#include “stdlib.h” //预定义常量 #define NULL 0
//单链表的定义
typedef struct LNode{ int data;struct LNode *next;}LNode,*LinkList;//单链表的创建
void Create_List(LinkList &L){ int data;LinkList p,q;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;
q=L;
scanf(“%d”,&data);while(data!=0){
p=(LinkList)malloc(sizeof(LNode));
p->data=data;
p->next=q->next;
q->next=p;
q=p;
scanf(“%d”,&data);} }
//单链表的遍历
void TranverseList(LinkList L){
LinkList p;
p=L->next;
if(p==NULL)
{
printf(“niln”);
return;
}
while(p!=NULL)
{
printf(“%d ”,p->data);
p=p->next;
}
printf(“n”);}
实验三 栈及其应用
一、实验目的
1、熟悉栈的顺序表示与实现。
2、熟悉栈的应用。
3、理解并掌握递归函数的设计与实现。
二、实验内容 问题描述:利用栈实现十进制数n转化为d进制数 要求:
1)输入一个n和d,打印输出d进制数序列。
2)利用顺序栈来实现十进制数n转化为其他d进制数。此时,需要同时实现初始化空栈、入栈、出栈、判栈空等辅助功能。测试数据:
(1)输入n:1348
d:8 输出:2504(2)输入n:9
d:8 输出:11(3)输入n:0
d:8 输出:0 2 问题描述:利用栈实现算术表达式求值。要求:
1)参与运算的操作数为10以内的数值。测试数据:
自拟。
实验四 二叉树的递归算法
一、实验目的
1、掌握二叉树的表示与实现。
2、掌握二叉树的定义、创建、遍历等基本操作的实现。
3、熟悉求二叉树深度等递归算法的设计与实现。
二、实验内容
问题描述:已知二叉树t,分别采用顺序存储结构、二叉链表存储结构实现求二叉树的深度,并对二叉树分别进行中序遍历。要求:
1、二叉树分别采用顺序或二叉链表存储。
2、树中的数据类型约定为整型。测试数据:
1、输入序列:-+aØØ*bØØ-cØØdØØ/eØØfØØ创建二叉树; 输出:深度:5
前序序列:-+a*b-cd/ef
中序序列:a+b*c-d-e/f
后序序列:abcd-*+ef/-T:d / e f
2、t=nil
输入:Ø
输出:深度:0 实验五 图的遍历
一、实验目的
熟悉图的基本操作,掌握图遍历的设计与实现。
二、实验内容
问题描述:已知的描述校园景点的图,实现对该图的深度优先和广度优先遍历。要求:
图采用邻接矩阵存储,顶点信息包括景点的名称和简单描述。
实验六 有序表的查找
一、实验目的
1、理解各种查找方法的基本思想
2、熟悉有序表查找方法的算法实现
二、实验内容 已知一有序的序列{1,3,5,7,9},采用折半法分别查找3和6。
2已知输入一无序的序列{5,1,3,9,7},创建一棵二叉排序树,然后对其遍历,输出递增有序的序列。
实验七 哈希表
一、实验目的
理解哈希表的概念和基本操作;熟悉哈希表的创建、查找、插入的算法实现。
二、实验内容
问题描述:已知11位好友的名字各不相同,设计并实现一个哈希表,根据好友的名字,可以取得其生日。要求:
1、好友的信息包含名字和生日两个数据项,其中好友的名字为主键,用汉语拼音形式存放;
2、哈希函数采取:好友名字中所有拼音字母ASCII码值的和 MOD 11(除以1取余);
3、采取线性探测再散列的方式处理冲突。
实验八 内部排序算法的应用
一、实验目的
理解各种内部排序方法的基本思想;熟悉各种内部排序方法的算法实现
二、实验内容
问题描述:已知一序列{503,087,512,061,908,170,897,275,653,426},分别采取下列排序方法对其进行排序:
(1)直接插入排序;
(2)简单选择排序;
(3)起泡排序;(4)快速排序;(5)堆排序。
第四篇:实验7 数据结构
实验七
稀疏矩阵的实现基本操作
班级:1208341
4学号:1208141姓名:陈峰
一、实验内容
(1)掌握稀疏矩阵的压缩存储;(2)掌握稀疏矩阵的转置算法;
二、实验目的
(1)实现上三角阵的压缩存储;
(2)用三元组书序表存储稀疏矩阵,并实现矩阵的转置;
三、设计思想
(1)创建一个数组;(2)输入数据;
(3)给定矩阵任一元素的下标;(4)打印给定下标所对应的数据;(5)创建三元组顺序表;(6)输入矩阵中的数据;(7)输出对应的矩阵;
四、程序源代码
(1)三元组顺序表存储稀疏矩阵并实现矩阵的转置;
#include
# define MAXSIZE 100 # define MAXRC 10
struct Triple {
int i,j;
/*该非零元的行下标和列下标*/
int e;};struct TSMtrix {
struct Triple data[MAXSIZE+1];
/*非零元三元组表,data[0]未用*/
int rpos[MAXRC+1];
/*各行第一个非零元的位置表*/
int cpos[MAXRC+1];
/*各列第一个非零元的位置表*/
int num[MAXRC+1];
/*各列非零元的个数*/
int mu,nu,tu;
/*矩阵的行数、列数和非零元个数*/ };
void CreateMtrix(struct TSMtrix *M){ /*创建一个稀疏矩阵*/
int i,elem,col,row,mu,nu,tu;
printf(“please input matrix col,row,unzeroed numbers:n”);
scanf(“%d%d%d”,&mu,&nu,&tu);
M->mu=mu;
M->nu=nu;
M->tu=tu;
for(i=1;i<=tu;i++)
{
printf(“please input element col,row,value:n”);
scanf(“%d%d%d”,&col,&row,&elem);
if(mu<0 || nu<0 || mu>M->mu || nu>M->nu)
{
printf(“error!”);
i--;
}
else
{
M->data[i].i=col;
M->data[i].j=row;
M->data[i].e=elem;
}
} }
void ShowMtrix(struct TSMtrix M){ /*打印出矩阵*/
int i=1,j=1,dir=1;
printf(“The matrix is:n”);
for(i=1;i<=M.mu;i++)
{
for(j=1;j<=M.nu;j++)
{
if(M.data[dir].i==i && M.data[dir].j==j)
{
printf(“%d
”,M.data[dir].e);
/*存在非零元*/
dir++;
}
else
printf(“0
”);
}
printf(“n”);
} }
void FastTransposeSMtrix(struct TSMtrix M,struct TSMtrix *T){ /*矩阵的快速转置*/
int t=1,p=1,q,col=M.nu;
T->mu=M.mu;
T->nu=M.nu;
T->tu=M.tu;
if(T->tu)
{
for(col=1;col<=M.nu;col++)
M.num[col]=0;
for(t=1;t<=M.nu;t++)
++M.num[M.data[t].j];
M.cpos[1]=1;
/*找到M中cpos的位置*/
for(col=2;col<=M.nu;col++)
M.cpos[col]=M.cpos[col-1]+M.num[col-1];
for(p=1;p<=M.tu;p++)
{
col=M.data[p].j;
q=M.cpos[col];
T->data[q].i=M.data[p].j;
T->data[q].j=M.data[p].i;
T->data[q].e=M.data[p].e;
++M.cpos[col];
}
} }
main(){
struct TSMtrix M;
struct TSMtrix N;
CreateMtrix(&M);
ShowMtrix(M);
printf(“n”);
FastTransposeSMtrix(M,&N);
ShowMtrix(N);
getch();}
(2)实现矩阵的经典转置算法并测试;
#include
typedef struct { int i,j;Elemtype e;}te;
typedef struct { te data[maxsize+1];//存储非0元素的数组,该数组是从1开始,所以下面的p从等于1开始// int mu,nu,tu;//mu 表示行数,nu 表示列数,tu 表示该矩阵中非0的个数// }tx;
//向矩阵中输入元素 int intput(tx &a){
int row,col,p=1;//row 表示元素的行标,col 表示元素的列标,p表示非0元素的计数器//
int temp;
printf(“请输入矩阵行数:”);
scanf(“%d”,&a.mu);
printf(“请输入矩阵列数:”);
scanf(“%d”,&a.nu);
printf(“请输入原始矩阵的每行每列元素:n”);
for(row=1;row<=a.mu;row++)//双重循环// {
for(col=1;col<=a.nu;col++)
{
scanf(“%d”,&temp);
if(temp!=0)
{
a.data[p].i=row;
a.data[p].j=col;
a.data[p].e=temp;
p++;
}
a.tu=p;
}
printf(“n”);
}
return 0;}
//输出上面的矩阵
int output(tx &a){
int row,col;
int p=1;
printf(“输出原始矩阵:n”);
for(row=1;row<=a.mu;row++)
{
for(col=1;col<=a.nu;col++)
{
if(row==a.data[p].i && col==a.data[p].j)
{
printf(“t%d”,a.data[p].e);
p++;
}
else
//剩余的输出0//
printf(“t%d”,0);
}
printf(“n”);//换行符的位置//
}
return 0;}
//定义了一个新的矩阵b// int transpose(tx a,tx &b)
{
int row,col;
//找出非0元素//
int p,q=1;
b.mu=a.nu;//矩阵b的行数等于矩阵a的列数//
b.nu=a.mu;//矩阵b的列数等于矩阵a的行数//
b.tu=a.tu;//非0元素的个数///
if(a.tu!=0)//判断是否有非0元素// {
//双重循环//
for(col=1;col<=a.nu;col++)
// 该循环是以列循环目的是:把非0元素中列标小的元素从头排列//
{
for(p=1;p<=a.tu;p++){
if(a.data[p].j==col)
//循环非0数组中的元素,并找出a.data[p].j等于当时的a矩阵在中的col// { //把矩阵a中非0元素的行标和列标等于矩阵b非0元素的列标和行标//
b.data[q].i=a.data[p].j;
b.data[q].j=a.data[p].i;
b.data[q].e=a.data[p].e;
q++;
} }
}
printf(“n”);
}
return 0;}
//输出转置后的矩阵
int outputtranspose(tx &b){
int q=1;
int row,col;
printf(“输出转置后的矩阵:n”);
for(row=1;row<=b.mu;row++)
{
for(col=1;col<=b.nu;col++)
{
if(row==b.data[q].i && col==b.data[q].j)//找出b矩阵非0元素//
{
printf(“t%d”,b.data[q].e);
q++;
}
else
printf(“t%d”,0);//剩余的输出0//
}
printf(“n”);
}
return 0;}
void main(){ tx a,b;intput(a);output(a);transpose(a,b);outputtranspose(b);}
五、调试及测试数据
(1)三元组顺序表存储稀疏矩阵并实现矩阵的转置;
(2)实现矩阵的经典转置算法并测试;
六、实验总结
在本实验中,老师给出了“三元组顺序表存储稀疏矩阵并实现矩阵的转置”的完整实验代码供我们参考。通过对参考例子的代码的理解,看懂之后程序代码之后就能比较轻松地写出题目的代码。在本次实验中能够清楚的知道要做什么,从哪里开始做,怎么做,思路很清晰。经过编程,学会了串的操作与实现,并且对C++也有了新的认识。
第五篇:数据结构实验指导书
目 录
实验规则················································2 实验环境················································2 实验报告要求············································3 实验一 单链表
(一)······································4 实验二 单链表
(二)······································5 实验三 栈···············································6 实验四 二叉树···········································7 实验五 最短路径·········································8 实验六 内部排序·········································9
实 验 规 则
为了顺利完成实验教学任务,确保人身、设备的安全,培养严谨、踏实、实事求是的科学作风和爱护国家财产的优良品质,特制定以下实验规则:
1、实验前必须充分预习,完成指定的预习任务。预习要求如下:
(1)认真阅读指导书,进行必要的设计与计算。(2)熟悉实验内容。
(3)预先复习,并按要求编写程序。(4)未完成预习任务者不得进入实验室。
2、遵守以下纪律:
(1)在实验室不得做和实验无关的事情。
(2)进行任课老师指定内容以外的实验,必须经指导教师同意。(3)遵守纪律,不迟到。
(4)保持实验室内安静、整洁,爱护公物,不许乱写乱画。
实 验 环 境
本实验在386以上的微机上进行,运行环境为VC6.0。
实验报告要求
1、实验题目 2.实验目的 3.实验环境
4.实验内容与完成情况(可以附上自主设计的源程序)5.出现的问题及对问题的解决方案 6.实验思考:(学生对本次实验的收获的总结)
实验一 单链表
(一)一、实验目的
掌握线性表的链式存储结构及其基本操作。
二、预习要求
1、看懂书上的算法,深入理解链表的物理存储模式和逻辑模式。
2、根据要求,编写程序准备上机调试。
三、实验内容
实现一个简单的学生信息管理系统,该系统的功能有:
1、利用单链表建立学生基本信息表
2、浏览每个学生的信息
3、根据学号查询某个学生的基本信息
4、添加学生信息到单链表中
5、删除一个学生的信息
四、实现提示
设计结点的结构体类型,包括学生的学号、姓名、年龄、性别;要求设计一个简单的菜单界面,根据需要选择所要进行的操作;构造函数,每一个函数实现上述的一个功能。
实验二 单链表
(二)一、实验目的
掌握线性表的链式存储结构及其基本操作。
二、预习要求
1、看懂书上的算法,深入理解链表的物理存储模式和逻辑模式。
2、根据要求,编写程序准备上机调试。
三、实验内容
1、实现单链表的就地逆置。
2、建立两个非递减有序单链表,然后合并成一个非递减链表。
3、建立两个非递减有序单链表,然后合并成一个非递增链表。
4、编写一个主函数,调试上述算法。
四、选做题、思考题
1、如何用带表头结点的单链表作为多项式的存储表示,实现两个多项式的相加。
2、约毖夫环的实现。
3、如何利用文件实现学生信息的存取。
实验三 栈
一、实验目的
深入了解并掌握栈的特性及其在实际中的应用;熟练掌握栈的算法实现;运用栈操作求解实际问题。
二、预习要求
1、看懂书上的算法,深入理解栈的特性和存储结构,以便在实际问题背景下灵活运用。
2、根据要求,编写程序准备上机调试。
三、实验内容
利用栈实现数据的分类,要求当输入为偶数时进栈1,当输入为奇数时进栈2,最后分别从栈1和栈2输出偶数和奇数序列。
四、实现提示
1、开辟一个连续的存储空间,实现两个栈顺序存储空间的共享;分别在两端设置栈顶指针,并按要求实现栈操作。
2、采用顺序存储实现栈的初始化、入栈、出栈操作。
五、选做题、思考题
1、两栈空间共享时,栈满的条件是什么?
2、为停车场编制进行管理的模拟程序(习题集P96,2.1)。
3、编写程序,利用栈实现表达式求值。
实验四 二叉树
一、实验目的
通过实践掌握二叉树的存储结构和遍历思想;掌握二叉树的常见算法的程序实现。
二、预习要求
二叉树的三种遍历方法。
三、实验内容
1、输入字符序列,建立二叉链表。
2、利用栈,编写非递归算法,编程实现二叉树的中序遍历。
3、求二叉树的叶子结点个数。
4、在主函数中设计一个简单的菜单,分别调试上述算法。
四、选做题、思考题
1、如何实现二叉树的后序遍历(非递归)。
2、如何求二叉树的高度。
实验五 最短路径(旅游景点导游咨询模拟)
一、实验目的
利用图的最短路径原理为用户提供路径咨询,掌握求最短路径的算法并编程实现。
二、预习要求
学习了解图的存储结构,掌握求最短路径的两种算法。
三、实验内容
设计一个旅游景点导游模拟程序,为来访的客人提供景点最短路径的信息查询服务,任意选取n城市,构成一个有向带权图,图中顶点表示城市,边上的权值表示两点间的距离,根据用户指定的始点和终点输出相应的最短路径。
四、实现提示
咨询以用户和计算机的对话方式进行,由用户输入起始点和终点,输出信息:最短路径是多少?并指出所经过的城市。存储结构可选用邻接矩阵。
五、选做题、思考题
1.如何实现对城市信息进行编辑(如:添加或删除)的功能。
2.用邻接表作存储结构,求一指定景点出发,到其余各景点的最短路径。
实验六 内部排序
一、实验目的
直观感受算法的关键字比较次数和关键字移动次数。
二、预习要求
1、常见的排序算法(插入排序、交换排序、选择排序、归并排序、基数排序等)的思想、特点及其适用条件。
2、根据要求,编写程序准备上机调试。
三、实验内容
1、对直接插入排序和简单选择排序算法进行关键字比较次数和关键字移动次数的比较。
2、利用链式存储结构,编写程序,实现直接插入排序和冒泡排序。
四、实现提示
测试数据可以为几组典型的数据:正序、逆序、乱序。
五、选做题、思考题
1、快速排序算法的非递归实现。
2、结合实验,理解针对不同待排元素的特点而选择不同排序方法的重要性。
3、如何对本实验进行时间、空间的复杂度分析。