数据结构实验报告（共11篇）
1.数据结构实验报告 篇一
数据结构实验报告
一． 题目要求
1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历；
3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二． 解决方案
对于前三个题目要求，我们用一个程序实现代码如下 #include
typedefintElemType;
//数据类型 typedefint Status;
//返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType
data;
structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉树函数
if(T==NULL){
T =(BiTree)malloc(sizeof(BiTNode));
T->data=key;
T->lChild=T->rChild=NULL;
return 1;} else if(key
InsertBST(T->rChild,key);} else
return 0;} BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL;inti=0;while(i //数据域 InsertBST(bst,a[i]); i++;} returnbst;} int Delete(BiTree&T) { BiTreeq,s; } if(!(T)->rChild){ //右子树为空重接它的左子树 q=T;T=(T)->lChild;free(q);}else{ if(!(T)->lChild){ //若左子树空则重新接它的右子树 q=T;T=(T)->rChild;}else{ q=T;s=(T)->lChild;while(s->rChild){ q=s;s=s->rChild;} (T)->data=s->data;//s指向被删除结点的前驱 if(q!=T) q->rChild=s->lChild; else q->lChild=s->lChild; free(s);} } return 1; //删除函数，在T中删除key元素 intDeleteBST(BiTree&T,int key){ if(!T)return 0;else{ if(key==(T)->data)return Delete(T); else{ if(key<(T)->data) returnDeleteBST(T->lChild,key); else returnDeleteBST(T->rChild,key); } } } intPosttreeDepth(BiTree T){//求深度 inthr,hl,max;if(!T==NULL){ hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;} else return 0; } void printtree(BiTreeT,intnlayer){//打印二叉树 if(T==NULL)return;printtree(T->rChild,nlayer+1);for(inti=0;i ”);} printf(“%dn”,T->data);printtree(T->lChild,nlayer+1);} void PreOrderNoRec(BiTree root)//先序非递归遍历 { BiTree p=root;BiTreestack[50];intnum=0;while(NULL!=p||num>0){ while(NULL!=p) { printf(“%d ”,p->data); stack[num++]=p; p=p->lChild; } num--; p=stack[num]; p=p->rChild;} printf(“n”);} void InOrderNoRec(BiTree root)//中序非递归遍历 { BiTree p=root; } intnum=0;BiTreestack[50];while(NULL!=p||num>0){ while(NULL!=p){ stack[num++]=p; p=p->lChild;} num--;p=stack[num];printf(“%d ”,p->data);p=p->rChild;} printf(“n”);void PostOrderNoRec(BiTree root)//后序非递归遍历 { BiTree p=root;BiTreestack[50];intnum=0;BiTreehave_visited=NULL; while(NULL!=p||num>0){ while(NULL!=p) { stack[num++]=p; p=p->lChild; } p=stack[num-1]; if(NULL==p->rChild||have_visited==p->rChild) { printf(“%d ”,p->data); num--; have_visited=p; p=NULL; } else { p=p->rChild; } } printf(“n”);} int main(){//主函数 printf(“ ---------------------二叉排序树的实现-------------------”);printf(“n”);int layer;inti;intnum;printf(“输入节点个数:”);scanf(“%d”,&num);printf(“依次输入这些整数（要不相等）”);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i scanf(“%d”,arr+i);} BiTreebst=CreateBST(arr,num);printf(“n”);printf(“二叉树创建成功!”);printf(“n”);layer=PosttreeDepth(bst);printf(“树状图为:n”);printtree(bst,layer);int j;int T;int K;for(;;){ loop: printf(“n”);printf(“ ***********************按提示输入操作符************************:”);printf(“n”);printf(“ 1:插入节点 2:删除节点 3:打印二叉树 4:非递归遍历二叉树 5:退出”);scanf(“%d”,&j); switch(j){ case 1: printf(“输入要插入的节点:”); scanf(“%d”,&T); InsertBST(bst,T); printf(“插入成功!”);printf(“树状图为:n”); printtree(bst,layer); break; case 2: } printf(“输入要删除的节点”);scanf(“%d”,&K);DeleteBST(bst,K);printf(“删除成功!”);printf(“树状图为:n”);printtree(bst,layer);break;case 3: layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4: printf(“非递归遍历二叉树”);printf(“先序遍历:n”);PreOrderNoRec(bst);printf(“中序遍历:n”);InOrderNoRec(bst); printf(“后序遍历:n”); PostOrderNoRec(bst); printf(“树状图为:n”); printtree(bst,layer); break;case 5: printf(“程序执行完毕!”); return 0;} goto loop;} return 0;对于第四小问，要储存学生的三个信息，需要把上面程序修改一下，二叉树结构变为 typedefintElemType; //数据类型 typedefstring SlemType; typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ SlemType name;ElemType score;ElemType no; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree;参数不是key,而是另外三个 intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉树函数 if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->no=no;T->name=name;T->score=score; T->lChild=T->rChild=NULL; return 1;} else if(no InsertBST(T->rChild,no,score,name);} else return 0;} 其他含参函数也类似 即可完成50个信息存储 用数组存储50个信息，查看以往代码 #include cout<<“该学号信息已经存在，添加失败”< break;} cout<<“重新输入添加的学号”< for(int n=m+1;n<20;n++){ if(ptr[m].average() student a; a=ptr[m]; ptr[m]=ptr[n]; ptr[n]=a; }} ptr[m].show();} break;case 4: cout<<“谢谢使用”< 二叉排序树储存数据界面（储存学生信息略） 创建二叉树： 插入节点： 删除节点： 非递归遍历： 退出： 数组储存学生信息界面 分析查找效率： 因为二叉树查找要创建二叉树，而数组查找只创建一个数组，二叉树的创建时间比较长，所以对于数据量较少的情况下数组的查找效率比较高。但当数据量增加时，二叉树的查找优势就显现出来。所以数据量越大的时候，二叉树的查找效率越高。 四． 总结与改进 这个实验工作量还是很大的，做了很久。树状图形输出还是不美观，还需要改进。 一开始打算用栈实现非递归，但是根据书里面的伪代码发现部分是在C++编译器里运行不了的（即使补充了头文件和数据的定义），所以之后参考了网上的数组非递归，发现其功能和栈相似。 递归遍历的实现比非递归的遍历真的简单很多。 开始时只看到前三问，所以没有写到储存学生数据的代码，里面还可以用clock（）函数加一个计算查找所要数据时间的代码，让二叉树查找与数组查找到效率比较更加直观。 关键词：数据结构与算法,实验教学,改革 数据结构与算法是计算机专业的核心基础课程之一, 通过本门课程的学习, 可以使学生透彻地理解各种数据对象的特点, 学会数据的组织方法和实现方法, 并进一步培养良好的程序设计能力, 而该课程的实验课是学生验证、掌握和应用数据结构理论的重要途径。 一、数据结构与算法上机实验课程的现状 数据结构与算法课程涉及大量数据类型及算法, 理论性很强, 抽象难懂, 对学生的学习造成了一定的难度。受传统的教学模式的影响, 课程的实验教学一直处于从属地位, 同时因学生基本程序设计能力有待提高等因素影响, 实验效果不甚理想。如何使学生理论学习和实践学习相结合, 提高学生的实践能力, 已成为高等院校培养应用型本科人才的一项重要课题。 目前在数据结构与算法实验教学过程中发现的问题主要有以下几点: 1.学生对于上机实验的重要性认识不够。对于学生来说, 由于部分院校的教学资源所限, 数据结构与算法课程长期以来都是课堂和实验分开进行, 授课教师对于上机实验过程几乎不参与, 这就导致了学生重视课堂理论的讲授, 而忽视上机实验课程的重要性。 2.课程实验缺乏层次性。上机实验教学内容大多为简单的验证性实验, 缺乏综合性、应用型、设计性实验项目。增加论述。 3.课程理论性强、难度大。数据结构与算法课程理论性极强, 抽象难懂, 很多学生在课堂听课过程中不能够完全理解, 无法建立起数据结构和相应算法的概念, 长此以往导致学生对于这门课程的畏惧和抵触情绪, 同时也严重打击了学生上机实验的积极性。 4.学生对掌握程序语言的程度不够。学生对程序设计语言掌握得不理想, 也是导致学生上机实验缺乏积极性的一个重要原因。数据结构与算法是学生在学过一门或几门语言课程之后开设的, 其算法大都由C或C++语言描述, 要求学生能够使用某种程序设计语言对算法进行程序设计, 并且上机调试通过。以我学院为例, 学生在学习数据结构时, 虽然已经学过C语言, 但仅是初学, 并不精通。因此对于抽象的数据类型、动态分配存储空间等概念, 在理解上还是有一定困难的。由于对程序设计语言掌握得不好, 大部分学生在编程的过程中陷入迷茫的状态, 阻碍了他们对各类数据结构和算法等知识点的理解和应用, 使教学目标难以实现。 二、实验教学的改革和探索 (一) 实验教学内容的改革 数据结构与算法课程主要使学生掌握程序数据的结构、组织和管理技术以及在此基础上的算法设计与分析技术, 不仅为后续课程操作系统、编译原理、数据库原理、软件工程、人工智能等课程提供必要的知识准备, 更重要的是可以提高学生软件分析、设计、编程和数据组织的能力。根据数据结构与算法整个课程体系的划分, 本课程的上机实验主要分为以下几种类型: 1. 验证性实验。 这一类型的实验主要在上机实验课中完成。以西安交通大学城市学院为例, 本门课程有8个学时的上机实验, 主要任务是将课堂上讲过的内容以实验的形式贯穿起来, 所涉及的实验以教材中提及到的基本算法和例题为主, 基本都是验证性的实验。以单链表为例, 要求学生通过定义线性表的抽象数据类型, 在链式存储结构下完成单链表的建立、插入、删除、查找、求前驱节点和求后继节点等操作, 通过实验教学, 在加深学生对数据结构课程内容理解的同时, 达到理论联系实际的目的。 学生通过完成此类实验, 一方面可以强化基础知识, 另一方面也可以通过编写算法掌握高级语言程序, 同时还可以训练学生良好的编程风格、基本实验技能和科学严谨的实验作风。 2. 综合性实验。 综合性实验部分实在课程设计阶段来完成。主要任务是考查学生运用所学基本数据结构解决实际问题的能力。所设计的实验项目可以是课程设计指导书中提供的参考题目, 也可以是工程中的实际课题, 选题要与所学阶段性知识紧密联系, 任务有一定的难度和综合性, 对学生的编程思路和方法有启发作用的项目。例如:学习了栈和队列知识后可以要求学生设计一个停车场管理系统, 以栈模拟停车场, 以队列模拟车场外的便道, 按照从终端读入的输入数据序列进行模拟管理。又如:学习了图的路径的相关算法后, 可利用学生熟悉的当地交通情况、旅游景点等设计问路系统。这些问题与课本理论知识联系密切, 而且具有一定的实用价值。 3. 研究性实验。 此类实验是针对于学有余力的学生, 可安排一些研究性实验, 针对计算机专业学生的特点, 可以以软件开发的形式进行, 让学生以创新者的角色去做实验。所设计的实验项目都是实际工程中的课题, 题目的解法要求符合工程实际情况, 具有可行性。学生可以自己提出实验题目和开发工具, 自己设计实验过程等, 有条件者还可以进入工程实践中进一步提升实践能力。 (二) 实验教学方法的改革 根据我院学生的特点和学院培养应用性本科人才教育宗旨, 我们在实验教学的方法上进行了改革。 1. 先简后难, 循序渐进。 在上机实验课中, 主要以验证性试验为主, 针对堂课讲授的知识安排配套的练习。练习的内容以编写的数据结构与算法实验指导书的形式发给学生, 每节课明确实验任务、实验方法和结果要求, 使学生在有限的课堂时间中完成相应训练目标, 掌握基础知识, 夯实基础;在课程完成之后的课程设计阶段, 加大难度, 主要以综合性的题目为主, 对于程度特别好的学生也可以完成研究性的项目。针对这一阶段的训练, 我们也编写了相应的课程设计指导书, 提供给学生适合的参考题目和编程提示。有助于学生更好的完成项目要求。通过一系列的训练, 培养学生算法设计能力以及创造性思维, 以达到提高学生应用知识解决复杂问题能力的目标。 2. 启发式教学和分组实验。 在教学方法上, 把传统教法中老师讲, 学生听的“灌输法”转化为“启发式”的教学方法, 引导学生自主思考, 常常提问“WWW”, 即“What, Hao, Why”:这个问题做什么的?需要用的哪方面的知识?怎么去解决问题?如何解决?教师教给学生提出问题、分析问题和解决问题的方法, 学生自行探究问题和解决问题, 激发学生探求知识的欲望和积极的学习兴趣。 在训练的形式上, 改变传统的“集体化”路线, 根据程度的不同将2~4名学生分成多个小组, 任命一名学习能力强、组织能力好的学生担任项目组长, 以软件开发小组的形式协同工作, 合理分工, 共同学习, 通过团队讨论解决问题。各小组成员不仅要完成自己的工作, 还要与其他成员合作, 共同完成整个项目。教师应多给予学生鼓励, 激发学生的思维, 促进他们合作的欲望和热情, 使课堂活泼积极, 并且适时的提供必要的启发式帮助, 只提供意见, 不具体替学生完成。让学生从解决问题和团队合作中获得成就感和自我认同感, 在轻松的氛围中达到激发学生兴趣, 提高学生综合实践能力的目标。 (三) 项目答辩和实验报告结合的考核方法。 1. 项目答辩。 在课程设计实验结束时, 专门抽出时间对个小组成员的工作进行考核, 要求每个小组选派2名学生进行答辩, 在规定时间内陈述小组工作情况, 遇到的问题及解决的办法, 最终达到的效果及心得体会等。根据答辩情况, 给予优、良、中、差和不及格五档评分。通过这种团队合作和答辩的方式大大提升了学生的实践能力、组织和口头表达能力及合作精神。 2. 实验报告的规范。 课程设计实验结束后要求学生写出实验报告, 以作为实验环节评分的书面依据之一和存档材料。实验报告以规定格式的电子文档书写、打印并装订, 排版及图、表要清楚、工整。每个小组每个题目提交一份实验报告, 实验报告除介绍本小组成员所做工作外还应包括以下内容: (1) 需求分析。以规范的技术文档语言陈述说明项目设计的任务并明确规定: (1) 输入的形式和输入值的范围; (2) 输出的形式; (3) 程序所能达到的功能; (4) 测试数据:包括正确的输入及其输出结果和含有错误的输入及其输出结果。 (2) 概要设计。说明本程序中用到的所有抽象数据类型的定义、主控程序的流程以及各程序模块之间的层次关系。 (3) 详细设计。本阶段的主要任务是实现概要设计中定义的所有数据类型, 对各操作、主程序和其他模块均要求写出伪码算法, 同时可以使用流程图或者N———S图进行描述, 画出函数和过程的调用关系图。 (4) 调试分析。在程序的调试过程中出现的问题以及解决办法, 回顾和讨论设计与实现过程中的相关问题。 (5) 测试结果。列出完整和严格的测试数据, 包括输入和输出。 (6) 用户使用说明。说明程序的使用方法, 并列出每一步的具体操作步骤。 (7) 代码注释。算法必须给出完整、正确的文字注释。 三、改革的效果 通过数据结构与算法实验教学的改革, 学生的学习热情和积极性得到了明显的提高, 学生的主动思考和积极实践的热情得以激发。学生能够在实验期间主动积极的参与并解决问题, 提高了学生的实践能力和编程能力。通过分组合作的方式进行项目训练, 培养了学生的团队合作意识和严谨的工作作风。通过小组答辩, 教师了解了每组学生的学习情况, 把握学生的学习状态和程度, 有助于在日后的教学中给予适当的指导。教师在此过程中不断总结问题, 积累经验, 使教学质量得到显著提高。 四、结束语 数据结构与算法在计算机课程体系中占据重要地位, 其实验环节的教学质量直接关系到本门课程的学习效果。在实验教学过程中必须以培养学生的综合实践能力为宗旨, 不断改进教学方法, 加大实验教学力度, 做到夯实基础, 提高能力, 为学生后续专业课程的学习打下良好的基础。 参考文献 [1]耿国华.数据结构——C语言描述[M].北京:高等教育出版社, 2006. [2]赵玉霞.《数据结构》课程上机实验改革初探[J].福建电脑, 2007, (4) :213-214. [3]严蔚敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版社, 1997. [4]宁正元, 王秀丽, 林大辉.与数据结构[M].北京:清华大学出版社, 2006. 关键词：数据结构实验教学 0引言 《数据结构》是计算机专业课程体系的核心课程之一。课程主要讲述各种数据的逻辑结构、物理结构及基本操作的实现算法以及数据查找、排序算法，并对各种算法进行性能分析和比较。 根据调查发现，目前大多数院校《数据结构》课程教学现状不容乐观。学生普遍反映课程学习比较困难，教师也感觉教学效果不理想。实验教学更是因为程序设计语言基础不扎实、课程内容太抽象等原因而较难开展，有些学校因此而缩短学时甚至不开设实验。一些专家和教师就课程实验教学改革已经提出了一些具体的教学方法，如案例驱动、课题答辩等。这些方法都具有比较重要的借鉴价值，但某些文章过于片面的强调某一种教学方法。笔者认为根据学生的实际情况完善教学设计、加强教学管理，通过行之有效的教学手段使学生学有所获才是根本。下面结合自己的实际教学工作，谈谈对数据结构实验教学方法的认识。我校《数据结构>课程理论学时48，实践学时16，教材选用严蔚敏的《数据结构(C语言版)》)。 1讲好理论第一课.明确课程性质 仅从课程名称来看，<数据结构》就很容易被误解为实践性不强的理论课。讲好第一堂理论课非常重要，应让学生明确课程性质并理解实践学习的重要性。 结合程序设计语言、操作系统等课程内容，笔者设计了一些学生比较熟悉并容易理解的应用实例和学生一起探讨。如：int a[10]和a[i]-5的确切含义；文件簇的链式形态；国际象棋大师与超级计算机的对决：图的着色问题等。在讲解图的着色问题时引导学生思考图的存储中需要关心什么，怎么存以及大致的程序逻辑等。通过对实例的分析，引入课程主要内容，学生也可明确课程的性质和专业地位并思考课程学习目标。 2制定实验教学计划.设计实验内容 程序设计语言是数据结构的前驱课程之一，多数院校都是以c语言程序设计作为学生程序逻辑训练的课程。数据结构教材中采用类C语言来描述算法，对指针、结构体等内容并未作详细的介绍。对于刚刚学完C语言的学生来说，指针等内容本来就比较模糊，要将类C算法转换为程序实现就更加困难。 在制定实验教学计划时，可以采用由易到难、逐步加深的方式来安排实验内容。结合实验学时数和教学大纲要求，笔者将实验内容作了如下设计和安排： 2.1第一次上机任务只要求学生运用以前学过的C语言知识来编写一个程序：给定一个整数序列，要求①用冒泡或选择算法进行排序：②输入一个整数x，在此有序序列中进行查找，如成功，则返回其位置；③如查找不成功，将×插入到序列中并使序列仍然有序。此题目运用到数组的定义、排序、查找、数组元素插入算法等相关内容。通过此实验，不仅能了解学生程序语言的熟悉程度，也能了解学生对排序和查找等基础算法的掌握情况，为后面教学内容设计作好铺垫。 2.2结合教学进度要求学生实现常见数据结构的基本操作，并能作一些验证性的实验。如用数字菜单的形式实现单向链表的基本操作，并完成两个有序链表合并算法的验证。实验要求学生能实现大多数基本操作算法，完成头文件的设计，并能利用已实现的基本操作完成复杂算法的验证。通过此类实验，学生对数据结构的理解更直观，程序逻辑更清晰，C语言的掌握能力逐渐增强，同时也为面向对象课程的学习打下一定的基础。 2.3设计性实验即课程设计安排。课程设计的目的在于培养学生分析和解决实际问题的能力，训练和提高学生规范的程序设计方法。教师可推出一些典型的并与后续课程有一定联系的题目供学生选择。每个题目规模不能太小，并能反映相关数据结构在程序设计中起的关键作用。如：①实现一个串的基本操作演示程序，提供命令行的输入(仿照COMMAND)，并对命令行能进行简单的编译和出错处理，最后根据命令动词的功能来执行命令：②利用哈夫曼编码算法实现简单文本文件的压缩和解压。题目随着理论教学进度推出，有难有易，学生结合自己实际来选择并可提前完成。 3规范实验过程.加强实验教学管理 为保障划的有效实施，必须规范实验过程并加强实验教学管理。 3.1根据计划制定实验指导书。指导书中给出每个实验的目的、学时、内容等。其中设计性实验另给出一些基本的分析思路，每个实验都适当的添加一些选作题。学生通过阅读实验指导书能进一步明确每次实验的具体内容和要求。 3.2要求学生做好上机前的准备。大二学生的编码速度普遍较慢，如果把实验课时间主要用于输入代码是非常不值得的，应将主要精力放在程序调试上面。这样不仅有充足的提问时间，也便于教师归纳并集中讲解学生调试过程中所遇到的常见问题。 3.8要求学生实验后完成实验报告。报告中须给出问题分析、数据描述、算法描述、程序描述、测试结果和心得体会等内容。教师对学生提交的实验报告进行分析，总结并指出实验的成功和不足之处。 3.4加强实验教学管理，从正面引导学生。随着网络信息技术的发展，网络中提供的各种信息服务和娱乐方式使部分学生的学习积极性逐渐降低，学习目标也越来越不明确。如果管理松懈，有些学生就会把实践学习当成是简单的Ctrl-C和CtrI-V，不能达到实验教学的预期目标。因此，教师应了解学生的学习动态，加强实践教学管理，并根据实际情况进行相应调整和改进。 4丰富教学手段。搞好实验指导 在实践教学过程，教师不能只停留于解决学生提出的问题，还应不断摸索教学方法，丰富教学手段。 4.1演示基本算法实现时可采用互动的方式进行。先按类型定义一初始化一输入测试数据一输出的实现顺序和学生一起得到结果；再让学生逐个实现其余算法，最后完成头文件的设计。学生通过教师演示和实际操作可以更快的掌握类C算法和C程序的转换思路。 4.2数据结构中的程序规模相比C语言来说更大。由于缺乏经验，很多学生在程序调试中会出现较多的语法和逻辑错误，可利用多媒体网络教学手段在学生机上直接演示并讲解程序调试的方法和技巧。 4.8学生实验过程中尽力营造一种你追我赶的竞争氛围，通过激励机制提高学生学习积极性。如果有同学较早实现了某些算法，可有选择性的适当的“刺激”部分学生以激发其不服输的心理，从而带动其他学生。 4.4鼓励学生多实践，要求学生通过实践来找出理论学习中存在的问题，提高自己的抽象思维和逻辑推理能力。对于编程能力较强的学生，鼓励他们多做题，做难题，为今后参加各种资格水平考试和专业竞赛作好准备。 5总结 通过在主函数中调用对栈操作的这些函数,完成对数据进制的转换。测试数据:将 9分别转换成 2-9等不同进制输出。详细设计 linkstack* set(//建立空堆栈 { linkstack *l;//定义堆栈类指针 l=NULL;//将指针付为空值 返回栈 l;} linkstack* push(linkstack *k,int a//向堆 栈中插入数据 { linkstack *l;//建立栈指针 l=(linkstack*malloc(sizeof(linkstack;/申请地址 l->data=a;向栈的数据域赋值 l 的指针域指向下一个结构体 k=l;返回堆栈 k;} int empty(linkstack *k//判断堆栈是否为空 { if(k==NULL//如果堆栈为空 return 1;//返回 1 else//否则 return 0;//返回 0 } int gettop(linkstack *k//取栈顶元素 { return k->data;//返回栈顶元素 } 详细设计 … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … void main(//主函数 { linkstack *m;//定义堆栈指针 int a,b,c;//定义整型变量 m=set(;调用建栈函数建栈 printf(“t请 输 入 要 转 换 的 数 字 :nt”;scanf(“%d”,&a;输入要转换的数 printf(“t请输入要转换成多少进制(范 围 2-9:nt”;scanf(“%d”,&c;while(a如果 a 不为 0 { b=a%c;//求余 m=push(m,b;a=a/c; } printf(“t该数的 %d进制表示为:”,c;while(!empty(m//如果不为空 { printf(“%d ”,gettop(m;//输出栈 顶元素 m=pop(m;//栈顶元素出栈 } printf(“nt”;} 指导教师:日期:年 月 日 合 肥 学 院 学 生 实 验 报 告 函数的返回的类型与接收函数值的变量类型不对,不能正常编译。程序结果如下图所示: 该软件按为在 dos 下运行的软件,第一步提示用户输入要转换的数据;输入数据后,会提示输入要转换成多少进制的数;然后就会输出结果。 教师签字: 日期: 年 月 日 测试结果 调试分析 操作说明 迷宫问题实验报告 ——实验二 专业：物联网工程 班级：物联网1班 学号：15180118 姓名：刘沛航 一、实验目的 本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。 二、实验内容 用一个m*m长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 三、程序设计 1、概要设计 （1）设定栈的抽象数据类型定义 ADT Stack{ 数据对象：D={ai|ai属于CharSet，i=1、2…n，n>=0} 数据关系：R={|ai-1,ai属于D，i=2,3,…n} 基本操作： InitStack(&S) 操作结果：构造一个空栈 Push（&S，e） 初始条件：栈已经存在 操作结果：将e所指向的数据加入到栈s中 Pop（&S,&e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素 Getpop（&S，&e） 初始条件：栈已经存在 操作结果：若栈不为空，用e返回栈顶元 StackEmpty(&S) 初始条件：栈已经存在 操作结果：判断栈是否为空。若栈为空，返回1，否则返回0 Destroy(&S) 初始条件：栈已经存在 操作结果：销毁栈s }ADT Stack （2）设定迷宫的抽象数据类型定义 ADT yanshu{ 数据对象：D={ai,j|ai,j属于{‘ ’、‘*’、‘@’、‘#’},0<=i<=M,0<=j<=N} 数据关系：R={ROW,COL} ROW={|ai-1,j,ai,j属于D，i=1,2,…M,j=0,1,…N} COL={|ai,j-1,ai,j属于D,i=0,1,…M，j=1,2,…N} 基本操作： InitMaze(MazeType &maze, int a[][COL], int row, int col){ 初始条件：二维数组int a[][COL],已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障碍，值1表示通路。 操作结果：构造迷宫的整形数组，以空白表示通路，字符‘0’表示障碍 在迷宫四周加上一圈障碍 MazePath（&maze）{ 初始条件：迷宫maze已被赋值 操作结果：若迷宫maze中存在一条通路，则按如下规定改变maze的状态；以字符‘*’表示路径上的位置。字符‘@’表示‘死胡同’；否则迷宫的状态不变 } PrintMaze（M）{ 初始条件：迷宫M已存在 操作结果：以字符形式输出迷宫 } }ADTmaze （3）本程序包括三个模块 a、主程序模块 void main(){ 初始化； 构造迷宫； 迷宫求解； 迷宫输出； } b、栈模块——实现栈的抽象数据类型 c、迷宫模块——实现迷宫的抽象数据类型 2、详细设计 （1）坐标位置类型： typedef struct{ int row;//迷宫中的行 int col;//......的列 }PosType;//坐标 （2）迷宫类型： typedef struct{ int m,n;int arr[RANGE][RANGE];}MazeType;//迷宫类型 void InitMaze(MazeType &maze, int a[][COL], int row, int col)//设置迷宫的初值，包括边缘一圈的值 Bool MazePath(MazeType &maze,PosType start, PosType end)//求解迷宫maze中，从入口start到出口end的一条路径 //若存在，则返回true，否则返回false Void PrintMaze（MazeType maze）//将迷宫打印出来 （3）栈类型： typedef struct{ int step;//当前位置在路径上的“序号” PosType seat;//当前的坐标位置 DirectiveType di;//往下一个坐标位置的方向 }SElemType;//栈的元素类型 typedef struct{ SElemType *base;SElemType *top;int stacksize;}SqStack;栈的基本操作设置如下： Void InitStack（SqStack & S） //初始化，设S为空栈（S.top=NUL）Void DestroyStack(Stack &S)//销毁栈S，并释放空间 Void ClearStack（SqStack & S）//将栈S清空 Int StackLength（SqStack &S）//返回栈S的长度 Status StackEmpty（SqStack &S）？、若S为空栈（S.top==NULL），则返回TRUE，否则返回FALSE Statue GetTop（SqStack &S，SElemType e） //r若栈S不空，则以e待会栈顶元素并返回TRUE，否则返回FALSE Statue Pop(SqStack&S，SElemType e)//若分配空间成功，则在S的栈顶插入新的栈顶元素s并返回TRUE //否则栈不变，并返回FALSE Statue Push(SqStack&S，SElemType &e)//若分配空间程控，则删除栈顶并以e带回其值，则返回TRUE //否则返回FALSE Void StackTraverse（SqStack &S，Status）（*Visit）（SElemType e））//从栈顶依次对S中的每个节点调用函数Visit 4求迷宫路径的伪码算法： Status MazePath(MazeType &maze,PosType start, PosType end){ //求解迷宫maze中,从入口start到出口end的一条路径 InitStack(s);PosType curpos = start;int curstep = 1;//探索第一部 do{ if(Pass(maze,curpos)){ //如果当前位置可以通过,即是未曾走到的通道块 FootPrint(maze,curpos);//留下足迹 e = CreateSElem(curstep,curpos,1);//创建元素 Push(s,e);if(PosEquare(curpos,end))return TRUE;curpos =NextPos(curpos,1);//获得下一节点:当前位置的东邻 curstep++;//探索下一步 }else{ //当前位置不能通过 if(!StackEmpty(s)){ Pop(s,e);while(e.di==4 &&!StackEmpty(s)){ MarkPrint(maze,e.seat);Pop(s,e);//留下不能通过的标记,并退回步 } if(e.di<4){ e.di++;Push(s,e);//换一个方向探索 curpos = NextPos(e.seat,e.di);//设定当前位置是该方向上的相块 }//if }//if }//else }while(!StackEmpty(s));return FALSE;} //MazePath 四、程序调试分析 1.首先呢，想自己读入数据的，回来发现那样，很麻烦，所以还是事先定义一个迷宫。 2.栈的元素类型 一开始有点迷惑，后来就解决了 3.本题中三个主要算法；InitMaze，MazePath和PrintMaze的时间复杂度均为O（m*n）本题的空间复杂度也是O（m*n） 五、用户使用说明 1．本程序运行在windows系列的操作系统下，执行文件为：Maze_Test.exe。 六、程序运行结果 1.建立迷宫： 2．通过1功能建立8*8的迷宫后，通过2功能继续建立迷宫内部： 通过建立自己设定单元数目建立迷宫内墙。3．通过3功能观察已建立的迷宫结构： 4．通过4功能确立迷宫起点和终点： （此处像我们随机选择4,4和2,7分别为起点终点） 5．执行5功能，判断是否有路径走出迷宫： 这种情况无法走出迷宫。 我们再次观察图像设4,4和1,6分别为起点终点，再运行5功能。 观察到可以成功解开迷宫步数从1依次开始。 七、程序清单 #include // 列值 #define MAXLENGTH 25 // 设迷宫的最大行列为25 typedef int MazeType[MAXLENGTH][MAXLENGTH];// 迷宫数组[行][列] typedef struct // 栈的元素类型 { int ord;// 通道块在路径上的＂序号＂ PosType seat;// 通道块在迷宫中的＂坐标位置＂ int di;// 从此通道块走向下一通道块的＂方向＂(0～3表示东～北)}SElemType; // 全局变量 MazeType m;// 迷宫数组 int curstep=1;// 当前足迹,初值为1 #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 // 栈的顺序存储表示 typedef struct SqStack { SElemType *base;// 在栈构造之前和销毁之后，base的值为NULL SElemType *top; int stacksize; // 构造一个空栈S int InitStack(SqStack *S){ // 为栈底分配一个指定大小的存储空间 (*S).base =(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base) (*S).top =(*S).base; return 1; // 栈底与栈顶相同表示一个空栈 (*S).stacksize = STACK_INIT_SIZE;exit(0);}SqStack;// 顺序栈 // 栈顶指针 // 当前已分配的存储空间，以元素为单位 } // 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。int StackEmpty(SqStack S){ if(S.top == S.base) else } // 插入元素e为新的栈顶元素。int Push(SqStack *S, SElemType e){ if((*S).top-(*S).base >=(*S).stacksize)// 栈满，追加存储空间 { } *((*S).top)++=e;return 1;} // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。int Pop(SqStack *S,SElemType *e){ if((*S).top ==(*S).base) 左 return 1;} // 定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹 // 当迷宫m的b点的序号为1(可通过路径)，return 1;否则，return 0。int Pass(PosType b){ if(m[b.x][b.y]==1) else return 0;return 1;return 0;*e = *--(*S).top; // 这个等式的++ * 优先级相同，但是它们的运算方式，是自右向 (*S).base =(SElemType *)realloc((*S).base ，(*S).top =(*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;((*S).stacksize + STACKINCREMENT)* sizeof(SElemType));exit(0);if(!(*S).base)return 0;return 1;} void FootPrint(PosType a) // 使迷宫m的a点的序号变为足迹(curstep)，表示经过 { m[a.x][a.y]=curstep;} // 根据当前位置及移动方向，返回下一位置 PosType NextPos(PosType c,int di){ PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}};// {行增量,列增量} // 移动方向,依次为东南西北 c.x+=direc[di].x;c.y+=direc[di].y;return c;} // 使迷宫m的b点的序号变为-1(不能通过的路径)void MarkPrint(PosType b){ m[b.x][b.y]=-1;} // 若迷宫maze中存在从入口start到出口end的通道，则求得一条 // 存放在栈中(从栈底到栈顶)，并返回1；否则返回0 int MazePath(PosType start,PosType end){ SqStack S;PosType curpos;SElemType e; InitStack(&S);curpos=start;do { if(Pass(curpos)){// 当前位置可以通过，即是未曾走到过的通道块 FootPrint(curpos);// 留下足迹 e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e);// 入栈当前位置及状态 curstep++;// 足迹加1 if(curpos.x==end.x&&curpos.y==end.y)// 到达终点(出口) } else return 1;curpos=NextPos(curpos,e.di);{// 当前位置不能通过 } if(!StackEmpty(S)){ } Pop(&S,&e);// 退栈到前一位置 curstep--;while(e.di==3&&!StackEmpty(S))// 前一位置处于最后一个方向(北){ } if(e.di<3)// 没到最后一个方向(北){ } e.di++;// 换下一个方向探索 Push(&S,e);curstep++;// 设定当前位置是该新方向上的相邻块 curpos=NextPos(e.seat,e.di); MarkPrint(e.seat);// 留下不能通过的标记(-1)Pop(&S,&e);// 退回一步 curstep--;}while(!StackEmpty(S));return 0;} // 输出迷宫的结构 void Print(int x,int y){ int i,j; for(i=0;i } } void main(){ PosType begin,end;int i,j,x,y,x1,y1,n,k;for(j=0;j //清屏函数 printf(“***************************************************nnn”);printf(“ 1请输入迷宫的行数,列数n”);printf(“ 2请输入迷宫内墙单元数n”);printf(“ 3迷宫结构如下n”);printf(“ 4输入迷宫的起点和终点n”);printf(“ 5输出结果n”);printf(“ 0退出n”);printf(“nn请选择 ”);scanf(“%d”,&n);switch(n){ case 1:{ printf(“请输入迷宫的行数,列数(包括外墙)：(空格隔开)”); scanf(“%d%d”, &x, &y); for(j=1;j { for(i=1;i for(j=1;j // 迷宫左边列的周边即左边墙 m[j][y-1]=0;// 迷宫右边列的周边即右边墙 for(i=0;i // 迷宫上面行的周边即上边墙 m[x-1][i]=0;// 迷宫下面行的周边即下边墙 物 联 网 班 -15180118-刘沛 航 } }break; case 2: {printf(“请输入迷宫内墙单元数：”); scanf(“%d”,&j); printf(“请依次输入迷宫内墙每个单元的行数,列数：(空格隔开)n”); for(i=1;i<=j;i++) { scanf(“%d%d”,&x1,&y1); } m[x1][y1]=0; }break; case 3:{ Print(x,y);printf(“刘沛航建立的迷宫，定义墙元素值为0,可通过路径为1，输入0退出”);scanf(“%d”,&k);}break; case 4:{ printf(“请输入起点的行数,列数：（空格隔开）”); scanf(“%d%d”,&begin.x,&begin.y); printf(“请输入终点的行数,列数：（空格隔开）”); scanf(“%d%d”,&end.x,&end.y);}break; case 5:{ if(MazePath(begin,end))// 求得一条通路 { （六）实验名称：数据库及SQL语言 班级_______ 姓名__________ 学号______实验日期： 实验机时：3 学时实验成绩： ----------------- 一.实验目的： 1、学习数据库设计的一般过程及相关技术； 2、学习access数据库管理系统； 3、掌握数据库的输入、查询、更新操作。 二.实验内容： 1、需求陈述：某校图书馆要建立一个图书数据管理系统。该图书馆的图书（书名、分类号、作者、出版社）存放在不同的借阅室（室名），读者（姓名、系名、类别）在书架上找到所需图书后，可以到服务台办理借阅（借阅时间）。 设计要求： 分析需求，建立数据库的概念模型； 将概念模型转换为关系模型（注意：是否需要作规范化处理）； 写出创建基本表的SQL语句； 写出以下查询要求的SQL语句： （1）所有“高等数学习题集”书的信息； （2）读者“李林”借了什么书？ （3）“社会学原理”在哪个借阅室？ 2、在access数据库管理系统中建立所设计的关系表； 3、向各表中输入一组实验数据（元组）（注意：关系完整性）； 4、对数据库进行查询。 三.实验结果： 1、实体-关系图； 2、数据库表； 3、创建基本表的语句； 实验动物是经人工饲育,对其携带的微生物、寄生虫进行控制,遗传背景明确或来源清楚,用于科学研究、教育、生产、检定和其它科学实验的动物,它们的质量保证了动物实验的准确性和可靠性。随着近年医学研究的快速发展,各医学实验除了对实验动物数量需求越来越大,其质量要求也逐步提高,同时也更加关注实验动物的可溯源性和可靠性[1]。“从实验动物到动物实验”,需要建立一套有效的实验动物和动物实验跟踪系统,以便对实验动物的繁育、饲养、试验等环节实施全过程、全方位的跟踪管理和控制。而近年来发展迅速的无线射频识别技术(RFID)和电子标签技术,也成为建立溯源体系的最佳选择[2]。 目前国内较多的研究对象主要是针对大型动物或者宠物的溯源研究,而对实验动物的溯源研究相对匮乏。因此,本文针对实验动物中最常见的实验鼠在繁育、饲养等环节上的特点,提出一种能与RFID技术结合的溯源数据结构和算法,并设计用于实验鼠的射频识别代码结构。将这种算法与RFID结合并应用到实验鼠生命周期管理中,能够降低饲养人员在实验鼠生命周期的日常管理工作的繁琐程度等,实现并保证实验鼠的繁育、饲养及整个生命周期中的跟踪、控制。 下文将分别从实验鼠的谱系结构、溯源数据结构、溯源算法三方面进行阐述。 1 实验鼠谱系结构 建立实验鼠的谱系,有助于实验鼠种群分类和对实验鼠的合理配种,为种群可溯源性提供数据依据。本文将引进的实验鼠定义为F0代并以此节点为起点,建立种群谱系。F0代节点(即引进的实验鼠)为先祖,其所有后代向上溯源,都可追溯到先祖F0。实验鼠谱系结构如图1所示。 在图1中引进实验鼠称为先祖,其子孙称为后代。图1中的2A是3A和3B的双亲(根据2A的性别,决定是3A和3B的父亲还是母亲),3A和3B是2A的子女;3A和3B是同胞;2A是4A的祖先,4A是2A的子孙。 1.1 近交系谱系结构 近交系指经过至少连续20代的全同胞兄妹交配培育而成,品系内所有个体都可追溯到起源于第20代或以后代数的一对共同祖先的动物群。因此,同一品种、品系的近交系实验鼠,其个体之间都具有血缘关系。 近交系实验鼠谱系结构如图2所示。 近交系实验鼠的交配方式是全同胞兄妹交配。双亲是同胞兄妹关系,即有血缘关系,它们属同一代。如果双亲代数是g,其子女的代数G为: G=g+1 1.2 封闭群谱系结构 封闭群是以非近亲交配方式进行繁殖生产的一个实验动物种群,在不从其外部引入新个体的条件下,至少连续繁殖4代以上。又可分为远交群和突变群。 封闭群的谱系结构与人类谱系结构类似,如图3所示。 为保证基因的杂合性,封闭群实验鼠的交配对象不允许有血缘关系。图4的虚线圆表示来自同一品系的其他血缘群的实验鼠,其后代继承了双亲的血缘。由于双亲属于不同代数,其子女的代数是双亲中代数较大的一方的代数值加1,即: G = Max( g(f) , g(m) ) + 1 式中,Max(g(f),g(m))函数返回父代数g(f)值和母代数g(m)值较大一方的值。 2 溯源的数据结构及算法 2.1 数据结构 实验鼠的溯源结构,如图4所示。 图4中,实验鼠A的父标识可追溯其父亲——实验鼠B,和其母亲——实验鼠C。通过递归方式追溯到实验鼠A的祖先:实验鼠D和实验鼠E。这个过程类似二叉树的遍历,因此,本文使用二叉树结构来描述实验鼠的溯源数据结构,其中: 相同血缘的实验鼠集合构成树结构的血缘群T: T={k1,k2,…,kn} (1) 其中,种鼠ki的结构为三元组: ki=<Ks, Kt , g> (2) 其中Ks是种鼠ki的父亲,Kt是种鼠ki的母亲,且s,t<i;g是种鼠ki的代数。 为了将上述结构保存到数据库中,以实现实验鼠的向上溯源,本文设计了图5所示的溯源数据库来存储实验鼠溯源过程中所必需的数据。 图5中,《实验鼠基本信息表》保存了实验鼠常规的身份信息和生物特征数据,如身份编号、双亲编号、品种品系等;《血缘关系表》记录实验鼠所拥有的血缘群编码的集合(实验鼠至少有一条血缘群编码,实验鼠的子女分别继承来自于双亲的血缘群编码)。 2.2 溯源算法 在实验鼠饲养管理中,最常见的就是查验实验鼠3代以内的身份信息或者是在配种繁殖时,明确雌、雄鼠之间的血缘关系。下文说描述的溯源算法,解决了这两类问题。 2.2.1 上向溯源 使用二叉树后序遍历方法对数据表中存储的实验鼠进行溯源,算法如下: 1) 判断实验鼠是否有双亲信息。如果没有,则执行步骤4)。 2) 执行步骤1),对实验鼠的父亲进行身份溯源。 3) 执行步骤1),对实验鼠的母亲进行身份溯源。 4) 显示实验鼠身份信息。 2.2.2 血缘关系判断 • 同父同母,利用《实验鼠基本信息表》中实验鼠的双亲字段判断,算法如下: 1) 判断实验鼠A和实验鼠B的是否有共同的父亲。如果是,则执行步骤2);否则显示“非同父同母”。 2) 判断实验鼠A和实验鼠B的是否有共同的母亲。如果是,则显示“实验鼠A与实验鼠B是同父同母”;否则,显示“非同父同母”。 • 同父异母/同母异父,利用《实验鼠基本信息表》中实验鼠的双亲字段判断,算法如下: 1) 判断实验鼠A和实验鼠B的是否有共同的父亲。如果是,则显示“同父异母”;否则,执行步骤2)。 2) 判断实验鼠A和实验鼠B的是否有共同的母亲。如果是,则显示“同母异父”;否则显示“非同父异母/同母异父”。 • 是否有血缘关系,利用《血缘关系表》中血缘群编码字段判断,代码如下: 1) 获取实验鼠A的所有血缘群编码集合,并按代数降序排列。 2) 获取实验鼠B的所有血缘群编码集合,并按代数降序排列。 3) 依次对实验鼠A的血缘群编码和实验鼠B的血缘群编码进行对比,如果存在相同编码的情况,则记录该血缘群编码和代数信息。 4) 判断是否存在相同血缘群编码和代数信息。如果存在,则显示“实验鼠A与实验鼠B有血缘关系”,并显示相关的血缘群编码和代数信息;否则,显示“无血缘关系”。 2.3 RFID技术与实验鼠射频识别代码结构 射频识别[3](RFID)技术是20世纪90年代开始兴起并逐渐走向成熟,是利用射频信号通过空间耦合(交变磁场或电磁场)实现无接触信息传递并通过所传递的信息达到识别目的的技术。其核心是电子标签和配套的读写器。电子标签具有便于数据读写、标签形状多样、耐环境性好、可重复使用、穿透性强、数据记忆容量大、数据安全等优点。 为了让电子标签中存储的数据的读取和解析具有通用性,要求数据编码必须符合标准的编码规则。我国在2007年12月1日颁布的GB/T 20563-2006:《动物射频识别 代码结构》[4]。该标准定义了64位(8个字节)二进制识别码结构,对纳入管理范围内的动物个体赋予一个生命周期内可用的全球唯一的代码标识。实验鼠的特殊性,使得上述代码结构远不能满足实验鼠的管理要求和溯源需求,因此,本文提出图6的代码结构。 图6中定义了512位(64个字节)二进制识别码结构,主要用于RFID电子标签,是溯源数据结构的一部分。该代码结构不但提供“身份代码”(存储溯源数据结构中的实验鼠身份编码和生产单位等身份来源信息),也提供了存放实验鼠生物特征数据的代码结构,如遗传背景、代数等。该结构能够让电子标签存储实验鼠的常规数据。在数据读取方面,只需通过读写器即可获取实验鼠的大部分常规身份信息,包括实验鼠的品种、品系、周龄、来源地等,提高了操作的简便性和数据的公开化程度。但在饲养管理中出现诸如配种繁殖这种需要了解实验鼠的完整溯源信息的情况时,就需要依靠图7所述的方法来实现。 在饲养过程中,当饲养人员需要查验实验鼠的身份信息时,只需用手持式RFID阅读器对实验鼠扫描。阅读器会读取实验鼠体内电子标签中存储的数据,该数据是按照实验鼠射频识别代码结构来进行编码的(见图7中“1.读取RFID标识”)。成功解析电子标签中的数据后,即可获得实验鼠的常规身份信息,包括身份编码、出生日期、品种、品系等。如需要对该实验鼠进行诸如血缘关系对比或者知晓先祖来源时,可通过WIFI网络连接远程溯源数据库或者直接访问阅读器自身携带的溯源数据库,根据解析获得的实验鼠身份编码,通过溯源算法来获得(见图7中“2.种群溯源”)实验鼠的溯源数据。RFID阅读器将获得的常规身份信息和溯源数据显示在屏幕上(见图7中“3.数据展示”),供饲养人员查看使用。 该方法的优点在于:1) 降低人工管理成本和疏漏,实施观察实验鼠信息;2) 通过RFID阅读器即可查验所有饲养的实验鼠信息,携带及操作方便;3) 允许在没有网络环境(如外发途中实验鼠的身份溯源)的情况下,查验实验鼠身份及种群溯源。 3 结 语 本文设计的实验鼠溯源数据结构和算法,为实验鼠种群溯源提供了一种较为简单的实现方法。血缘群编码的概念简化了种群溯源及血缘关系判断的复杂度,使得溯源数据结构能够被诸如SQL CE这样小型的数据库所支持,便于在RFID阅读器这种便携式设备上实现溯源算法应用程序。同时,利用RFID电子标签的特点,提出了实验鼠的射频识别代码结构,将实验鼠常规身份信息存储在电子标签中,植入实验鼠体内使其随身携带,减少对第三方数据存储源的依赖性,提高实验鼠身份信息的统一化和公开化。未来将重点进行关于实验鼠射频识别代码结构和溯源算法优化的研究与实现,以及能够适用于所有实验动物的射频识别代码通用标准的研究,以便能够提高实验动物的溯源信息的公开化程度和共享程度。 参考文献 [1]赵金燕,陶琳丽,高士争.动物食品安全可溯源系统有源电子标签的设计[J].云南农业大学学报,2008,23(5):648-651. [2]陈一天.RFID及其在动物识别与跟踪中的应用[J].金卡工程,2005,9(7):39-42. [3]朱卫平,盛焕烨,王东.可重构RFID信息采集系统设计与实现[J].计算机应用与软件,2007,24(10):44-45. [4]中华人民共和国国家质量监督检验检疫局,中国国家标准化管理委员会.GB/T20563-2006动物射频识别代码结构[S].2006. [5]温泽锋,夏龙,齐长永,等.浅谈无线射频识别技术(RFID)在SPF级实验动物管理上的应用[J].实验动物科学,2010,27(3):36-38. [6]梁钰超,冯玉凡,汪斌.RFID无线射频识别技术在犬个体识别中的应用研究[J].养犬,2010(4):9-12. [7]施亮,傅泽田,张领先.基于RFID技术的肉牛养殖质量安全可追溯系统研究[J].计算机应用与软件,2010,27(1):40-43. 一、小学生在实验数据处理中遇见的问题 在小学科学教学中学生对于数据的处理还存在许多的问题，这些问题都会严重影响学生的数据收集意识的培养，不利于学生养成严谨的科学探索态度。下面就主要谈几点问题。 1.学生对于数据的收集不太真实 在小学科学教学过程中，学生往往会对课堂实验表现出极大的兴趣，会比较认真地观摩教学实验，一旦学生有机会上手做实验也会非常认真。但是在做实验的过程中，学生经常忽略一个环节，那就是收集数据并记录数据。所以往往会出现学生实验结束后，课本上的记录却是空白情况。等到实验进行完成后，教师需要实验数据时，学生会互相询问数据，凭借自己的记忆，然后比较草率地填写数据，最终造成数据收集不太真实，会导致学生在处理实验现象的时候被不真实的数据所诱导，偏离实验本质要求。例如在《导体和绝缘体》的教学中，学生就只顾去分辨材料，实验也是越做越开心，可是最终却忘记记录材料是否绝缘，导致数据收集不太真实，容易出错，也不利于后期整理材料是否绝缘的实验报告。这种现象在低年级的学生身上很容易发生。 另一方面，教师在科学教学过程中经常会对学生进行提问，但是往往在提问中会找优秀的学生进行回答，当学生回答正确后，教师会停止讨论。所以久而久之，学生开始为了迎合教师的问题而对数据进行“修改”，最终给出“完美”的实验数据。故而，这也导致了学生在科学教学中收集数据不真实，影响学生数据意识的培养。 2.学生对数据的处理不准确 在小学科学教学过程中，还存在一个问题，就是学生对于数据的收集处理不太准确。这也会导致学生在科学数据处理中出现错误，不利于数据意识的培养。例如在小学科学实验中经常会出现对比实验，而且在对比试验中还经常出现比较高的要求，但是学生却不能有效对实验中的对比变量进行认识和控制，所以会导致在科学实验过程中出现数据处理不准确，最终与实验现象差距较大，出现错误等现象。还有在一些需要利用仪器进行实验的科学试验中，学生因为不能准确掌握仪器正确使用方法和规则，也很容易造成数据的错误采集。例如对于温度计的读数，正确方法是平视温度计的刻度线，但是如果学生俯视或者仰视温度计刻度线，那么就会导致温度计读数出现错误，最终导致收集的数据不准确，影响实验效果。 3.学生对实验数据的收集不太全面 在科学实验过程中，经常会发生学生因为时间问题自己保留一部分实验数据，教师就参考学生这部分数据进行实验分析，最终导致实验出现较大的偏差，这样的实验数据导致实验结果不全面，降低实验真实性。所以实验数据收集不全面也是学生经常容易在科学试验中所出现的问题。 二、小学生数据处理中存在问题的原因 对于在小学科学实验教学过程中，学生容易出现的问题需要仔细分析其背后的原因，帮助学生尽快纠正，利于学生养成良好的数据意识，利于学生未来研究能力的提升。 首先从教师角度讲，在小学科学实验教学过程中缺乏对学生数字收集意识的培养。教师从教学计划出发，忽略学生在数字收集上的能力拓展，只是教会学生分析实验现象和实验结果，往往忽略了学生需要掌握数据收集，分析和整理才能更加准确地形成数据意识，也才能更好地分析出实验现象和结果，所以教师在意识上还存在问题。另外教师在指导学生形成数据意识的方法上也存在问题。教师不能激发学生自己形成数据收集的意识，而是一味让学生记录数据，寻找数据，整理数据，缺乏对学生创新能力的培养，让学生只形成简单的数据记录，不能有效建立数据敏感，更不能通过数据得出结论，指导实验。 从学生角度看，学生对于实验比较好奇，但是对实验数据的重视度却偏低，很多时候收集实验数据都只是为了完成任务，而不是提高自己的数据收集能力。所以这种意识淡薄的情况就会导致数据收集出现问题，最终影响数据意识的形成。另外，学生很容易为了获得教师的认可和表扬，就会去对收集的数据进行“修改”，然后导致所有试验数据处理痕迹过多，严重影响实验的真实性，最终导致实验数据无法体现实验现象，更加大学生对数据的收集的淡薄意识，不利于数据意识的创新与发展。最后，学生在实验过程中没有记录数据的意识，导致在试验后没有充分时间整理数据，所以很容易出现错误的数据，这也是数据不准确的主要原因。 最后，仪器的准确度以及操作方法也成为学生数据意识难以形成的原因。 三、对策 既然知道了问题，并且分析了原因，那么就需要进一步落实对策，帮助学生收集好数据，分析好数据，利用好数据，形成良好的数据意识，帮助学生创新与发展，提高学生的探索能力，利于学生未来的成长。 1.充分做好课前准备 首先在小学科学实验教学过程中，教师要加强学生数据意识的培养，要精心为学生数据意识培养设置实验。任何科学的推导都需要数据作为支撑，所以在数据的收集中更加需要精心设计，教师需要为学生数据收集预留空间，教会学生科学地探究知识，结合原有不足的数据收集问题，针对性设计实验，帮助学生观察实验的同时还能做好数据采集工作，帮助学生形成良好的数据收集意识，要时刻提醒学生数据收集的重要性，让学生重视数据，提高数据的准确性。 其次，要为学生创造良好的氛围，让学生在科学实验过程中更加大胆和创新。对于学生数据出现问题后，教师要耐心了解，要倾听学生内心的想法，让数据收集有问题的学生也能畅所欲言。这样可以培养学生的勇气和胆量，更加利于学生在数据收集过程中勇于创新，大胆采集，利于学生建立数据意识。 2.设计好记录表，让数据说话 要让学生养成数据收集的意识，就需要让学生看到数据的价值，最好是能直观为学生展示出来。所以利用数据记录表格就可以准确为学生做好数据记录，帮助学生透过数据看到实验的真实情况，更加了解数据的价值，更有利于学生培养数据意识。例如在“测量心跳和呼吸”这个实验中，教师需要制作一个表格，在“行”与“列”的首个表格中注明“心率”和“呼吸频率”，这样学生就可以将不同的心率对应到不同的呼吸频率中，这样得出的数据就是一一对应，既能有效收集数据，而且还能让数据发声，清楚展示出心率与呼吸频率的对应关系，让学生一目了然，更能体会到数据的真实性和有效性，更容易激发学生数据意识的形成。 3.教师要熟练实验，帮助学生解惑 教师在指导学生实验前需要自己先熟悉实验，要对实验数据进行掌握和预判断。因为每个实验存在的条件不一致，所以很可能在实验过程中出现数据难以掌握的情况，最终数据不能有效解决实验现象，就会打击学生收集数据的积极性，导致学生数据意识的偏差。所以教师需要对每个实验的数据进行预先评价，控制数据的范围，让学生得到的数据能够更加准确。例如“研究拉力大小与小车的运动的关系”，由于摩擦力的存在，所以，最开始小车静止时，拉力计显示的数据会比后面小车运动的数据大，但是学生往往会觉得这是错误的数据，所以教师在预判断的时候就需要指导学生进行数据处理，帮助学生形成良好的数据分析能力，让学生相信数据，借助数据，最终解决问题，不断在数据使用中进行创新与发展，更有利于数据意识的形成。 四、结束语 数据是试验中非常重要的资源，对于现象的解释，实验的成败具有重要作用，所以在小学科学实验教学中帮助学生形成良好的数据意识，让学生在数据上进行创新和发展，为将来的实验学习提供思维方法，帮助学生成长。 实验项目：选择结构程序设计 实验日期：2012年3月26日 实验原理：利用 if 或switch 语句实现多分支选择结构程序设计 实验仪器：PC 实验内容及步骤： 内容：利用scanf函数读入变量x的值，利用if或switch 语句判断x所在的区间，并求函数在x 处的函数值 步骤： 1、程序设计： （1）定义变量；（2）利用scanf给变量x赋值；（3）利用 if 或 switch 判断x所在范围执行相应计算，以求得函数在x 处的函数值；（4）输出相应函数值 2、输入程序、调试并运行通过。 实验报告 实验目的要求：抄写指导手册上相应章节的目的要求 实验环境：windows XPTC或 VC 实验内容：完整抄写P77页4.5小题 实验步骤：直接写代码 实验结果：根据实验题目自己输入相应值并观察程序输出结果 班号： 学号： 一、实验目得 (1)熟悉并掌握数据选择器得功能.(２） 用双 4 选 1 数据选择器 74LS１５3 设计出一个 16 选 1 得数据选择器。 (3)用双 4 选 1 数据选择器 7４LS１53 设计出一个全加法器。 二、实验设备 数字电路实验箱，74LS0０,7４LS153.三、实验内容(1） 测试双 4 选 1 数据选择器７4LＳ153 得逻辑功能。 ７4LS153 含有两个 4 选 1 数据选择器,其中 与 为芯片得公共地址输入端，与 分别为芯片得公共电源端与接地端.Figure1 为其管脚图: Figｕｒe 错误 错误!未定义书签。 未定义书签。 ：路电接连图下按ﻩ Fｉｇuｒe 错误 错误!未定义书签。 (2)设某一导弹发射控制机构有两名司令员 A、B 与两名操作员Ｃ、Ｄ,只有当两名司令员均同意发射导弹攻击目标且有操作员操作,则发射导弹 F．利用所给得实验仪器设计出一个符合上述要求得１６选１数据选择器，并用数字电路实验箱上得小灯与开关组合表达实验结果。 思路 : 由于本实验需要有四个地址输入端来选中 16 个数据输入端得地址之中得一个,进而实现选择该数据输入端中得数据得功能，即 1６选１。而公共得、两 个地址输入端与 使能端(用于片选,已达到分片工作得目得,进而扩展了一位输入)一共可以提供三个地址输入端,故需要采用降维得方法，将一个地址输入隐藏到一个数据输入端 中。本实验可以降一维,也可以降两位。由于两位比较复杂,本实验选择使用降一维得方式。 做法 : :图诺卡得能功需所现实中题用应如出画ﻩ 00 0１ １1 1０ 0０ 01 0 0 0 ０ 0 0 １ 0 １1 ０ ０ １ ０ 10 0 0 1 0 将 D 降到数据输入端中。对应得卡诺图如下: ０0 01 1 0 0 Ｄ 0 0 0 1 0 按上述卡诺图连接电路，用开关控制送给各输入高低电平。其中,“1”表示高电平,“0”表低电平，均由开关上下拨动来控制；A、Ｂ、C、Ｄ分别为题中得两个司令员得同意情况与两个操作员得操作情况;F 为导弹发射情况,将Ｆ接到小灯上即可。电路如 Figuｒｅ 1 所示(图中 即，后面得图均为如此）: Ｆｉgure 3 AB CD C AB (3)用 74LS００与 74LＳ153 设计一位全加器，并用数字电路实验箱上得小灯与开关组合表达实验结果。 一位全加器得功能如下面两个卡诺图所示。其中 A、B 分别表示被加数与加数，CI 表示低位向本位得进位，S 表示运算结果，CO 表示向高位得进位。 CＯ: S: 00 经分析,此全加器有三个输入，而公共得、两个地址输入端与 使能端(用于片选，已达到分片工作得目得，进而扩展了一位输入）刚好一共可以提供三个地址输入端。故按上面得卡诺图,分析后应采用下面得端口解法: 按上面得接法连接电路。用开关控制送给各输入高低电平,“1“表示高电平,“0”表低电平,均由开关上下拨动来控制； 表示低位送进来得进位信号,A、B分别表示被加数与加数;S 与 分别表示加法结果与向高位得进位信号。电路如Ｆｉgure 4 所示： Figｕre 4 四、实验结果(１） 测试双 4 选 1 数据选择器７４ＬＳ153 得逻辑功能: ：下如录记果结将,)亮灯小或(平电高示表”１“,)灭灯小或(平电低示表”0“用ﻩ 0 0 1 0 １ B A A B 1Ｑ ０ 0 ０ 0 0 1 0 1 0 0 1 1０ 0 ０ 1 0 1 0 1 1 0 0 1 1 1 ０ 2Q ０ 0 0 ０ ０ 1 0 1 0 0 １ 1 １ 0 ０ 0 1 0 1 0 1 1 0 ０ 1 1 １ ０(2） 设计出一个符合题目要求得 16 选 1 数据选择器 :下如录记果结将,）亮灯小或(平电高示表”1“，)灭灯小或(平电低示表”0“用ﻩA B C D Ｆ 0 0 0 0 0 0 0 0 1 0 0 0 １ ０ 0 0 0 1 1 0 0 １ 0 0 0 ０ 1 ０ 1 1 0 1 1 0 1 ０ 1 1 1 1 1 0 0 ０ ０ 1 0 0 1 1 １ 0 １ 0 1 1 0 １ 1 1 1 1 0 ０ 0 1 １ 0 1 1 1 １ １ 0 1 １ 1 １ 1 1 。能功辑逻得出计设求要所足满以可路电此，得可表值真得面上由ﻩ(3） 设计一位全加器 :下如录记果结将,)亮灯小或(平电高示表“1“，）灭灯小或(平电低示表＂0“用ﻩA B CI S CO ０ 0 0 0 ０ 0 0 1 1 ０ 0 1 0 1 ０ ０ 1 1 0 1 １ ０ 0 1 ０ 1 0 1 0 1 1 1 0 0 １ 1 1 1 １ 1 由上面得真值表可得,此电路可以满足所要求设计出得逻辑功能。 五、故障排除 在实验(１)中，发现所连接电路与预期得逻辑功能不一致.在检验了导线与小灯都正常后,发现将芯片得管脚接错了，误将 Q 与 接错地方。分析原因，就是由于芯片管脚设置得位置与管脚图上面不一致,两侧均有两个管脚接口.六、心得体会 连了道知中除排得障故在且并，计设得路电辑逻了握掌地好更我,验实次这过通ﻩ接时要瞧引脚上面得标号而不能一味地只认准位置。 关键词:数据结构与算法;综合性实验;设计性实验 一、引言 在计算机科学与技术、软件工程等专业中,《数据结构与算法》课程具有较强的实践性,因此实验教学是该课程教学过程中的一个非常重要的环节。在以往的实验教学中,学生都是按照已经设计好的实验要求和步骤进行着验证性的实验,学生一般是被动地接受或机械式地编程,以完成实验讲义中的验证或孤立的单元实验。这种实验教学模式使得学生缺乏主动性和独立思考问题的能力,不利于他们综合素质的提高和自主创新能力的培养。为了克服这些不足,使学生真正能把理论知识灵活运用到实践当中,我们开设了《数据结构与算法》课程综合性、设计性实验项目并立项进行实践研究,通过两三年的实践,取得了一些经验和成果,学生的实践能力也有了较大提高。 二、综合性、设计性实验项目的实践环节 1.实验项目的选择。 通过《数据结构与算法》课程的学习和前期验证性实践环节,学生已初步具备了进行综合性、设计性实验的能力。为进一步提高学生的设计能力和编程能力,我们设计了4个综合性、设计性实验项目供学生选择: ①校园导游系统的设计(设计性); ②书管理系统的设计(综合性); ③哈夫曼编码/译码器(综合性); ④散列表的设计与实现(设计性)。 2.实验项目的内容。 校园导游系统的设计 问题描述: 设计一个校园导游程序,为来访的客人提供信息查询服务。 基本要求: ①设计你所在的学校的校园平面图,所含景点不少于15个,以图中顶点表示校内各景点,存放景点名称、代号、简介等信息,以边表示路径,存放路径长度等相关信息; ②为来访客人提供图中任意景点相关信息查询; ③为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短路径(静态或动态表示出来)。 图书管理系统的设计 问题描述: 设计一个图书管理系统完成图书管理基本业务。 基本要求: ①每种书的登记内容包括书号、书名、著作者和库存量; ②对书号建立索引表(线性表或树表)以提高查找效率; ③系统主要功能如下: 采编入库:新购一种书,确定书号后,登记到图书账目表中,如果表中已有,则只将库存量增加; 借阅:如果一种书的现存量大于0,则借出一本,登记借阅者的书证号和归还期限,改变现存量; 归还:注销对借阅者的登记,改变该书的现存量。 用户管理。 数据存储(要求用文件实现数据存储)。 哈夫曼编码/译码器 问题描述: 设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼编码,生成编码文件(压缩文件,后缀名.cod);反过来,可将一个压缩文件译码还原为一个文本文件(.txt)。 基本要求: ①随机抽取20个文本文件作为统计样本,统计这些文本文件中各字符的平均出现次数,作为权值,建立哈夫曼树及各个字符的哈夫曼编码; ②将用户输入或选择的待压缩文本文件利用①建立的编码表进行编码,生成压缩文件(后缀名.cod); ③输入一个待解压的压缩文件名称,并利用相应的编码表进行译码; ④显示指定的压缩文件和文本文件; ⑤(选作) 把哈夫曼编码用二进制位紧缩到一个变量中,利用位运算实现真正的数据压缩,并求压缩比。 散列表的设计与实现 问题描述: 设计散列表实现电话号码查找系统。 基本要求: ①随机生成1万个记录,每个记录有下列数据项:电话号码、用户名、地址,每个数据项的内容都是随机生成的; ②分别以电话号码和用户名为关键字建立散列表(自行选择或构造合适的散列函数); ③采用双散列法解决冲突; ④查找并显示给定电话号码的记录; ⑤查找并显示给定用户名的记录。 3.预期目标。 进一步巩固和加深对《数据结构与算法》课程中基本知识的理解,熟悉各种逻辑结构及存储结构; 了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力; 培养学生从事软件开发的编程及创新能力; 提高学生综合运用所学的理论知识解决问题的能力; 训练用系统的观点和软件进行软件开发,培养软件工作者所应具备的科学的工作方法和作风。 4.实验项目的组织与实施。 针对综合性设计性实验项目,安排学生自选项目并进行项目设计和开发,每个项目20学时,按照下面的项目开发设计步骤,最后完成课题的总体设计与实现。 项目分析 根据实验项目内容的要求,充分地分析和理解问题,明确问题要求做什么、解决什么问题、实现什么功能。 概要设计 对项目内容描述中涉及的操作对象,设计相应的数据结构,并按照以数据结构为中心的原则对模块进行划分,定义主程序模块和逻辑结构。逻辑设计的结果是每种数据结构的定义(包括数据结构的描述和每个基本操作的功能说明)。 详细设计 为各个数据结构设计相应的存储结构并写出各模块的算法。设计是编程中重要的一环,在“详细设计”过程中,引导学生结合总体设计制订合理的程序结构和算法,理顺各个模块之间的相互关系,将详细设计的结果用结构图及流程图清晰地描述出来,在本过程中,教师要尽可能帮助学生养成自己解决问题的习惯。 编程 将详细设计的结果进一步求精为程序设计语言程序。在该环节中,教师应指导学生按照规范的程序编写方法去编程,并指导学生按照大型软件中常用的调试方法对程序进行跟踪及改进。 结果分析 在编程过程中及结束后,形成学生、课题小组组长、指导教师三位一体的项目质量监控体系,做到对各个阶段的结果都能进行实时的检测,如有不足之处,小组内成员和学生自行研讨出合理的整改方案并对课题实施进行改进,直至达到功能要求。 5.项目总结。 主要包括学生实验项目总结心得、实验报告撰写,学生成绩的评定。 实验项目总结心得 在实验临将近结束时让学生共同讨论实验结果的正确性,讨论实验设计步骤的合理性,总结经验,进一步改善项目实施的方案及步骤。笔者认为,实验后的总结非常重要,是从理论到实践,再由实践到理论认识的进一步升华,也是使学生提高实验兴趣、锻炼并增解决实际问题的重要过程和手段。 实验报告撰写 学生实验报告一般应包含的内容是:实验题目、实验环境、实验目的、实验任务、数据结构描述、算法流程图表示、实验总结。 学生成绩的评定 教师根据学生的实验设计报告、学生的实际操作能力(程序检查)及学生的创新能力等几个方面综合评定,给出综合成绩。 三、实践的成果 1.对学生的影响。 经过近两年的实验教学实践,有超过70%的学生认为此次实验收获很大,大约80%的学生对这类实验取得的成果表示满意。从总体效果来看,学生通过综合性、设计性实验,提高了设计及编程能力。大部分学生认为《数据结构与算法》综合性、设计性实验项目的开展改变了以往传统的实践教学模式,内容新颖,提高了他们的编程兴趣和热情,对他们帮助很大。 2.对教师的促进。 《数据结构与算法》综合性、设计性实验的指导教师由计算机科学技术学院《数据结构与算法》课程的主讲教师和专业实验室的教师共同承担,我们认为,开展综合性设计性实验项目整合了多个知识环节,既能够帮助学生掌握知识的系统性和衔接性,理清程序设计的思路,促进知识的融会贯通;同时也给主讲教师带来新的挑战,能使教师总结在理论教学中的不足,进一步加强教学方法和内容的改革。 参考文献: [1]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2006. [2]唐册善.数据结构—C语言描述[M].北京:高等教育出版社,2003. 【数据结构实验报告】推荐阅读： 数据结构实验报告线性01-03 数据结构实验报告-查找算法10-07 数据结构实验六11-08 数据结构实验111-10 数据结构实验顺序表09-17 东北大学数据结构实验11-02 课设报告数据结构08-28 数据库实验5实验报告09-20 数据库实验报告实验四10-062.数据结构实验报告 篇二
3.《数据结构》实验教学方法探讨 篇三
4.数据结构实验报告 篇四
5.数据结构迷宫问题实验报告 篇五
6.数据结构实验报告 篇六
7.数据结构实验报告 篇七
8.实验，因数据而精彩 篇八
9.选择结构实验报告 篇九
10.数据选择器实验报告 篇十
11.数据结构实验报告 篇十一