数据结构实验指导(实验五：查找算法)（精选8篇）
数据结构实验指导(实验五：查找算法) 第1篇
实验五 查找算法
实验项目：必做：顺序查找、折半查找
选做：二叉查找树 实验类型: 验证性 实验内容：
顺序查找：用数组或链表实现，数据有序或无序均可； 折半查找：必须用数组实现，且数据有序；
注意：提交的实验报告要显示已有的数据元素、待查找的数据；应包含查找成功、不成功的情况。
数据结构实验指导(实验五：查找算法) 第2篇
一，实验目的
1.熟悉掌握各种查找方法，深刻理解各种查找算法及其执行的过程； 2.学会分析各种查找算法的性能。
二，实验内容
8.1 实现顺序查找的算法
编写一个程序，输出在顺序表{3,6,2,10,1,8,5,7,4,9}中采用顺序查找法查找关键字5的结果。
8.2 实现折半查找算法
编写一个程序，输出在顺序表{1,2,3,4,5,6,7,8,9,10}中采用折半查找方法查找关键字9的结果。要求：（1）用非递归方法；（2）用递归方法。8.3 实现二叉排序树的基本运算
编写一个程序实现二叉排序树的基本运算，并在此基础上完成如下功能：（1）由{4,9,0,1,8，6,3,5,2,7}创建一个二叉排序树bt；
（2）判断bt是否为一棵二叉排序树（提示：在遍历过程中检查是否符合二叉排序树定义）；
（3）采用非递归方法查找关键字为6的结点，并输出其查找路径（提示：查找过程中保留经过的结点信息，找到后顺序输出之）。8.4 实现哈希表的相关运算
编写一个程序，实现哈希表的相关运算，并在此基础上完成如下功能：
（1）建立{16,74,60,43,54,90,46,31,29,88,77}哈希表A[0…12]，哈希函数为H(k)=key % 11，并采用线性探测法解决冲突。输出哈希表；（2）在上述哈希表中查找关键字为29的记录；
（3）在上述哈希表中删除关键字为77的记录，再将其插入，然后输出哈希表。要求：输出格式
哈希地址：0 1 2 ………..12 关键字值：……………………
三，源代码及结果截图
8.1 //实现顺序查找的算法 #include
//定义表中最多记录个数 typedef int KeyType;typedef int InfoType;typedef struct {
KeyType key;//KeyType为关键字的数据类型 InfoType data;//其他数据 } NodeType;
typedef NodeType SeqList[MAXL];
//顺序表类型 int Search(SeqList R,int n,KeyType k)//顺序查找算法
{ int i=0;while(i printf(“%d ”,R[i].key); i++; //从表头往后找 } if(i>=n) return-1;else { printf(“%d”,R[i].key); return i;} } void main(){ SeqList R;int n=10;KeyType k=5;InfoType a[]={3,6,2,10,1,8,5,7,4,9};int i;for(i=0;i //建立顺序表 R[i].key=a[i];printf(“查找结果：n”);if((i=Search(R,n,k))!=-1) printf(“n元素%d的位置是:%d”,k,i);else printf(“n元素%d不在表中n”,k);printf(“n”);} 8.2 //实现折半查找算法 #include //定义表中最多记录个数 typedef int KeyType;typedef char InfoType[10];typedef struct { KeyType key; //KeyType为关键字的数据类型 InfoType data; //其他数据 } NodeType;typedef NodeType SeqList[MAXL]; //顺序表类型 int BinSearch1(SeqList R,int n,KeyType k)//非递归二分查找算法 { int low=0,high=n-1,mid,count=0;while(low<=high) { mid=(low+high)/2;printf(“第%d 次 查 找 : 在[%d,%d] 中 查 找 到R[%d]:%dn”,++count,low,high,mid,R[mid].key); if(R[mid].key==k) //查找成功返回 return mid;if(R[mid].key>k) //继续在R[low..mid-1]中查找 元 素 } } high=mid-1;else low=mid+1; //继续在R[mid+1..high]中查找 return-1;int BinSearch2(SeqList R,KeyType k,int low,int high,int count)//递归二分查找算法 { int mid;if(low<=high){ mid=(low+high)/2;第%d 次 查 找 : 在[%d,%d] 中 查 找 到 元 素printf(“R[%d]:%dn”,++count,low,high,mid,R[mid].key); if(R[mid].key==k) //查找成功返回 return mid;else if(R[mid].key>k) //继续在R[low..mid-1]中查找 BinSearch2(R, k,low,mid-1,count);else BinSearch2(R, k,mid+1,high,count); //继续在R[mid+1..high]中查找 } else return-1;} void main(){ } SeqList R;KeyType k=9;int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;for(i=0;i //建立顺序表 printf(“用非递归方法:n”);if((i=BinSearch1(R,n,k))!=-1)printf(“元素%d的位置是%dn”,k,i);else printf(“元素%d不在表中n”,k);printf(“用递归方法:n”);if((i=BinSearch2(R,k,0,9,0))!=-1)printf(“元素%d的位置是%dn”,k,i);else printf(“元素%d不在表中n”,k); 8.3 //实现二叉排序树的基本运算 #include int key; struct BTNode *lchild; struct BTNode *rchild;}BTNode;//定义二叉排序树插入结点的算法 int BSTInsert(BTNode *&T,int k){ if(T==NULL) { T=(BTNode *)malloc(sizeof(BTNode)); T->lchild=T->rchild=NULL; T->key=k; return 1; } else { if(k==T->key) return 0; else if(k return BSTInsert(T->lchild, k); else return BSTInsert(T->rchild, k); } } //定义二叉排序树的创建算法 BTNode *createBST(int k[],int n){ BTNode *T; T=NULL; for(int i=0;i<=n-1;i++){ BSTInsert(T,k[i]); } return T;} //判断是否为二叉排序树 Status Judge(BTNode *&T){ } //定义二叉排序树的查找算法 BTNode *BSTSearch(BTNode *&T,int k){ if(T==NULL) return NULL; else if(T==NULL)return 1;else if((T>T->lchild)&&(T } else return 0;Judge(T->lchild);Judge(T->rchild); { printf(“%d ”,T->key); if(T->key==k) return T; else if(k { return BSTSearch(T->lchild, k); } else { return BSTSearch(T->rchild, k); } } } void main(){ int a[50]={4,9,0,1,8,6,3,5,2,7}; BTNode *bt=createBST(a,10); if(Judge(bt)==0)cout<<“bt不是二叉排序树”< } 8.4 //实现哈希表的相关运算 #include //定义最大哈希表长度 #define NULLKEY 0 //定义空关键字值 #define DELKEY-1 //定义被删关键字值 typedef int KeyType; //关键字类型 typedef char * InfoType;//其他数据类型 typedef struct { KeyType key;//关键字域 InfoType data; //其他数据域 int count; //探查次数域 } HashTable[MaxSize]; //哈希表类型 void InsertHT(HashTable ha,int *n,KeyType k,int p)中 { //将关键字k插入到哈希表 int i,adr;adr=k % p;if(ha[adr].key==NULLKEY || ha[adr].key==DELKEY)//x[j]可以直接放在哈希表中 } void CreateHT(HashTable ha,KeyType x[],int n,int m,int p)//创建哈希表 { } else { } n++;i=1;do { adr=(adr+1)% p;i++; //i记录x[j]发生冲突的次数 //发生冲突时采用线性探查法解决冲突 ha[adr].key=k;ha[adr].count=1;} while(ha[adr].key!=NULLKEY && ha[adr].key!=DELKEY);ha[adr].key=k;ha[adr].count=i; { int i,n1=0;for(i=0;i //哈希表置初值 { ha[i].key=NULLKEY; ha[i].count=0; } } int SearchHT(HashTable ha,int p,KeyType k){ int i=0,adr;adr=k % p;while(ha[adr].key!=NULLKEY && ha[adr].key!=k){ } if(ha[adr].key==k)return adr; //查找失败 //查找成功 i++; //采用线性探查法找下一个地址 //在哈希表中查找关键字k for(i=0;i } return-1;int DeleteHT(HashTable ha,int p,int k,int *n)//删除哈希表中关键字k { } void DispHT(HashTable ha,int n,int m) //输出哈希表 { float avg=0;int i;printf(“ 哈希表地址:t”);for(i=0;i } else //在哈希表中未找到该关键字 ha[adr].key=DELKEY;n--; //哈希表长度减1 //在哈希表中找到该关键字 return 1;return 0; printf(“ n”); printf(“ 哈希表关键字:t”); for(i=0;i if(ha[i].key==NULLKEY || ha[i].key==DELKEY)printf(“ ”); //输出3个空格 else printf(“ %3d”,ha[i].key);printf(“ n”);printf(“ 搜索次数:t”);for(i=0;i if(ha[i].key==NULLKEY || ha[i].key==DELKEY)printf(“ ”); //输出3个空格 else printf(“ %3d”,ha[i].count);printf(“ n”); for(i=0;i } if(ha[i].key!=NULLKEY && ha[i].key!=DELKEY)avg=avg+ha[i].count;avg=avg/n;printf(“平均搜索长度ASL(%d)=%gn”,n,avg); void main(){ int x[]={16,74,60,43,54,90,46,31,29,88,77};int n=11,m=13,p=13,i,k=29;HashTable ha;CreateHT(ha,x,n,m,p);printf(“n”);DispHT(ha,n,m);printf(“ 查找关键字29:n”);i=SearchHT(ha,p,k);if(i!=-1)printf(“ ha[%d].key=%dn”,i,k);else printf(“ 未找到%dn”,k);k=77;printf(“ 删除关键字%dn”,k);DeleteHT(ha,p,k,&n);DispHT(ha,n,m);i=SearchHT(ha,p,k);if(i!=-1)printf(“ ha[%d].key=%dn”,i,k);else printf(“ 未找到%dn”,k); } printf(“ 插入关键字%dn”,k);InsertHT(ha,&n,k,p);DispHT(ha,n,m);printf(“n”); 四，实验小结 1、通过本次实验，加深了我对查找表的认识。 2、有序表的查找之折半查找：前提必须是有序表，性能只有在均匀分布的时候才是最优的。 关键词：算法与数据结构,实验教学,教学改革 0 引言 算法与数据结构是计算机专业的一门重要基础课, 它主要研究数据的逻辑结构、存储结构及其相应的处理操作算法[1]。学习算法与数据课程, 不仅要理解书上抽象的理论知识, 更重要的是能够理论联系实际, 针对实际问题在计算机上编写出结构清晰、正确易读、效率高的程序。因此, 上机实验是算法与数据结构课程必不可少的教学环节, 对于训练学生编程能力至关重要。 1 实验内容 上机实验内容要根据学生的基础而定。若基础很好、自学能力强, 可布置规模较大、内容复杂的综合性程序任务;若基础较差, 则可布置简单的程序任务。对于一般本科生, 在选择实验题目时可结合教材内容确定。例如, 若教材使用的是严蔚敏、吴伟民编著的《数据结构》, 线性表的实验题目可定为:单链表的基本操作, 包括创建单链表、插入一个元素、删除一个元素、显示单链表等操作;对于栈的实验题目可设置为:数制转换、括号匹配和表达式求值;对于树和二叉树的实验题目可为:二叉树的创建、遍历和应用 (如求叶子结点个数、求二叉树的深度等) 。实验内容与教材内容相结合可以让学生更好地理解教材上的算法, 知道教材算法是非常实用的, 可以用这些算法解决很多实际问题, 激发学生的学习兴趣。 2 实验教学过程 实验课的内容应在上机前几天布置给学生, 以文档的形式说明实验题目、基本要求、测试数据、实现提示和选做内容等[2]。提前布置可让学生课后思考并提前开始编写程序, 实验课上就可提交程序或者请教师解答疑问。 如果是第一次实验课, 最好能现场演示程序的编写和调试过程。程序中若要用到书上的算法, 可提前准备直接复制。通过现场演示, 使学生对编程过程和程序运行效果有一个直观的认识。学生在学习算法与数据结构课程之前, 一般只学过C、C++程序设计语言, 学生的编程能力还不是很强, 此时需要教师引导。当学生完成第一个实验任务后, 就会有信心完成后面的实验任务, 否则, 可能让学生产生畏难情绪, 害怕编程实验课。 实验课主要是上机编程, 作为教师, 需要主动解答学生编程中存在的问题并注重实验结果验收。 3 常见编程错误及对策 学生在编写程序过程中难免会出现错误, 由于编程经验少, 很多学生看见调试程序显示有很多错误就不知所措。有些学生由于种种原因, 不去请教教师, 最终没有排除错误, 导致学习兴趣大大降低。为了减少这种情况的发生, 教师可以将上机过程中学生常犯的错误进行总结, 告知常见错误的解决方法和简单的调试技巧, 以便学生自己查错。编程过程中的错误可分为两类:语法错误和逻辑错误。若出现语法错误, 则程序无法连接、运行。逻辑错误是程序能通过编译、连接, 但运行结果不正确。学生编程常犯的语法错误有: (1) 使用了未声明的标识符。在开发工具的输出窗口中, 可看见类似这样的错误提示信息“error C2065:'p':undeclared identifier”, 该信息表示单引号中的标识符p没有定义。单引号中的标识符可能是变量名, 此时应在变量p使用之前加上定义变量p的语句。单引号中的标识符也可能是符号常量或类型名, 严蔚敏所编教材中第一章预定义了许多常量和类型, 例如: #define TRUE 1 typedef int Status 在以后的章节中许多算法直接使用第一章定义的常量和类型。学生在将书上算法转化为程序时, 却常常忘记加上常量或类型的定义, 导致编译时出现类似上面的错误提示信息。另外, 学生若在输入程序的过程中不注意英文字母大小写的区别, 则也可能会出现上面的提示信息。例如前面定义了类型“Status”, 而后面程序中将其写成了“status”。 (2) 缺少分号“;”。这类错误在输出窗口中会有如下类似提示信息:error C2143:syntax error:missing';'before'return'。该信息表示在return之前的语句缺少分号。由于程序中每条语句结束处都会有一个分号, 而在程序输入过程中很可能会漏掉某个分号, 此时只需在相应位置补上分号即可。 (3) 缺少花括号”}”。程序中函数体、if语句体、循环体都会用到花括号, 而程序输入中很容易出现多输入或少输入花括号的情况。此类错误比较难发现, 因为编译时会显示很多错误提示信息, 但这些错误很可能都是由于缺少花括号这一个错误造成的, 此时需在相应地方补上花括号。这种错误有时会有如下类似提示信息:fatal error C1004:unexpected end of file found。 (4) 程序中使用中文符号。例如将英文分号输入成中文分号, 则程序编译时会出错。输出窗口会显示多个错误, 其中也会包含有类似下面的提示信息:error C2143:syntax error:missing';'before'return'。 (5) 缺少头文件。若要使用库函数则要将其所在的头文件用include命令行包含进来。这类错误在输出窗口没有明显提示, 通常会提示库函数是未声明的标识符, 此类错误不易发现。学生应该养成良好的编程习惯, 程序开头就将所有有用的头文件包含进来, 避免犯此类错误。 若编程中出现逻辑错误, 可设置断点, 逐步调试程序, 观察变量的中间运行结果, 从而发现程序中的逻辑错误。调试过程常用以下功能键: F9:设置/取消断点; F10:执行下一条语句; F11:执行下一条语句, 若下一条语句是函数调用语句, 则进入函数体内部执行; Ctrl+F10:运行至光标所在处。 参考文献 [1]严蔚敏, 吴伟民.数据结构[M].C语言版.北京:清华大学出版社, 2008. 【摘 要】针对在数据结构与算法实验教学中如何提高学生的编程和算法设计能力，分析并指出了在实验教学中普遍存在的问题，结合实验课的教学改革，开发实验平台，以期有效激发学生的学习兴趣和积极性，培养动手和创新能力。 【关键词】数据结构与算法 实验改革 平台建设 【中图分类号】 G 【文献标识码】A 【文章编号】0450-9889（2014）07C-0132-03 数据结构与算法实验是计算机专业学生必修基础课数据结构与算法的配套实验课程，是培养学生程序设计技能必不可少的重要环节。其目标之一是培养学生能运用理论知识与算法技术分析解决实际问题，能运用高级程序设计语言编程实现算法。从近年实验情况来看，在上机编写程序实现具体算法时遇到的种种问题，效果不容乐观，学生很难按时完成实验所要求的内容。 一、实验教学存在的问题与分析 数据结构与算法实验是一门实践性很强的技术基础课，经过多年实验教学分析，发现普遍存在如下主要问题： （一）课程抽象，实验难度大 数据结构具有一定的抽象性，学生面对抽象概念在学习过程中常会遇到困难，基本每本理论教材在呈现概念时都会受到多方面限制，比如篇幅的限制，省略了算法细节部分或只给出伪代码，由学生自己补充，学生需要将算法用程序设计方法实现，完成有一定难度和技巧的程序设计并上机调试运行。对编程基础稍微薄弱的学生来说，就会出现不小的困难。 （二）实验相关资料偏少 由于学生基础薄弱，实验前又没有更多的相关实验资料进行预习，仅靠看课本理论和实验时的几个学时难以完成实验所要求的任务，也就谈不上创新人才的培养。 （三）学生程序设计语言课程基础薄弱 数据结构与算法课程是第四学期开设，对于很多先修课程要求高，高级程序设计语言是大学生进校第一、二学期学习，第一学期学习过程序设计思想，第二学期学习面向对象程序设计思想，由于大部分同学高中没接触过计算机语言学习，对过程程序设计思想还没掌握透，第二学期的面向对象程序设计学习又开始，学习非常吃力；导致常用的一些语法结构，如指针和结构体等内容难于理解。而这些语法恰恰是程序设计语言教学时的难点，也正好是学生完成数据结构实验必须掌握的内容，这给部分学生学习带来了一定困难。 （四）编程语言难 数据结构与算法编程语言描述主要用到C++语言，并大量用到了指针、链表和结构体等运算，这部分内容正好是大多数学生掌握知识点薄弱的环节，导致学生很难用高级语言将教材中的算法描述出来，由于问题的堆积、实验的欠账，容易使学生丧失学习兴趣和信心，导致学生间抄袭程序或实验报告的现象。 （五）编程技巧差 普通学生在低年级只编写过功能单一、结构简单的程序；而从功能单一的简单程序向涉及算法和稍复杂程序的数据结构编写过渡学习时，需循序渐进的方式和细致的引导，紧密结合理论教学。学生一下从简单编程直接到复杂的程序设计，不仅不适应，且设计技巧性较差。 二、实验教学改革目标的提出 根据以上学生实验时出现的诸多问题，特提出该课程的实验改革目标： 一是紧密配合理论教学，通过相关实验，帮助学生加深对数据的逻辑结构、存储结构、算法思想和具体实现等各个环节的整体理解，强化学生“结构——算法——编程”三者密切相关的意识，让学生思考和发现利用数据结构解决实际应用问题的有效方法，从而使学生分析和解决问题的能力得到锻炼和提高。 二是因材施教，让原本不同水平和能力起点的学生通过数据结构实验，能力和水平都有所提高，并且有兴趣有信心学好数据结构课程。 三是培养学生多方面能力，比如团队精神，口头表达能力，对学生全方面发展起到较好的推动作用。 三、调整实验项目内容，使其更加符合学生的认知规律 数据结构与算法实验内容主要是编程实验，提高学生的实践编程能力，巩固和强化理论课的教学效果。为了保证和提高实验教学质量，加深对课堂知识的理解，培养学生动手能力和思维能力，尝试对数据结构与算法实验项目进行重新设计，主要内容有： 针对编程基础较薄弱的学生，我们开发了数据结构与算法实验教学平台，学生在该平台上可获知实验相关的更多内容，通过平台引导学生重点回顾程序设计语言的基础知识，特别是数组和指针等有关操作。通过这些辅助手段，使学生对将要编写程序的一些语法和程序规则有所复习和掌握。还可通过平台对实验原理的动画演示，得到帮助和启发，从而更好更快地完成实验内容。 每个实验内容以章节为单位安排，依据实验教学目的，针对计算机相关专业所要达到的不同实验教学目标，以及考虑学生个体差异，每个实验项目都设置基础必做题和附加选做题两部分内容。这两类实验都需要紧密结合理论教学。必做题相对简单，目的在于帮助学生掌握基础知识。对于该部分题目，学生容易完成，能提高学生学习积极性并增强学习信心；选做题针对学有余力的学生，各个实验项目中的必做题均设计详细的实验准备内容，用于引导学生更好地进行实验前预习准备工作；主要在于培养和鼓励学生的学习兴趣和扩大知识面，进一步培养学生应用能力和创新意识，保证基础弱的同学学习兴趣，也提高了编程能力强的同学动手能力。例如，与线性表一章理论教学相配合的实验项目是多项式加减法，这个实验是对线性链表的建立、插入、删除、遍历等进行综合运算，对数据结构与算法第一实验内容来说稍有难度，可作为选作题或增加实验学时。在与栈一章理论教学相配合的实验项目是迷宫，这部分实验内容要求掌握回溯法和栈的基本运算等知识，有一定难度；用括号匹配作为必做题，能培养学生独立钻研，有助于学生解决问题能力的训练。 四、实验教学方法探究 实验前学生必须先预习和熟悉实验教学平台，了解实验内容的目的和要求，理解算法，描述语言的语法，查看相关资料，写预习报告。 通过多年实验教学中实验完成情况分析，软件工程专业的学生语言掌握较好，大部分学生能按时完成实验项目，其它专业的学生实验完成情况较差；由此，实验编程语言可以因学生而异，除软件工程专业的学生采用面向对象程序设计C++外，其它专业主要采用C语言描述，并且可增加前期语言学习时间。只有编程语言掌握扎实，数据结构与算法实验才能很好地完成。 开发数据结构与算法实验网络教学平台系统，该平台主要包含有课程介绍、在线课程、互动学习、下载资料等模块。有针对性地对每一个实验项目进行详细讲解和实验原理分析的动画演示，将抽象的数据结构问题制作为教学动画，借助形象的案例理解抽象的概念。教学内容利用Web页面为基本元素出现在站点中，学生通过访问站点来进行交互式学习。以辅助学生自主学习为主要目的，解决学生实验时无从下手的局面，启发学生思维，促进学生程序设计能力的提高。平台系统流程图如图1所示。 在线课程是教学平台核心部分，也是学生对数据结构与算法实验加深理解的重要环节，该平台从实验预习，到实验原理算法的演示，再通过在线课堂的视频教学、在线测试题训练及各种原理进行拓展教学。为了方便学生学习较抽象的数据结构与算法，能顺利进行程序编写，该教学平台还包含有18个flash动画用于原理算法演示，主要包括栈和队列、线性表、递归、查找与排序、树、图等内容，每个flash动画都有实验原理及主要代码实现过程，能更加形象展示数据结构的原理。例如：栈是一种先进后出的数据结构，在对栈原理进行动画设计时，根据用数组实现栈的特点，采取对栈先进行初始化的代码模块来对栈进行初始化，之后运行相应代码模块观察压栈出栈过程，同时还能观察到栈中数据的变化。在大部分flash动画演示过程中，flash页面左侧是代码部分，能体现当前执行的代码，并与右侧的动画演示及讲解分析一一对应。演示过程中如用户需要重新开始，还可点击“重新开始”按钮。这些flash动画演示将代码与动画有机的结合在一起，将抽象的代码转换为有形的动画，大大方便学生学习和对实验内容的理解。 如对栈原理进行动画演示的flash点击界面中压栈代码动画效果，该动画效果包括等待入栈的数字入栈的动画效果和位于等待区域的数字前移的动画效果。等待入栈的数字、入栈的动画效果和位于等待区域的数字前移的动画效果如图3所示。 图3 压栈的动画效果图 该平台互动学习是一个教师和学生互动的场所，实现动态交互的功能，教师能添加、更改、删除各种资源，学生、教师可以查看各种资源库里的资源。同时，学生可从平台上下载练习题和测试练习题资料，练习题有主要算法描述，可帮助学生进一步理解每个章节的算法原理，测试练习题有自动报错功能。 五、改革数据结构实验考核方式 让学生对以前所做实验作一个分析和总结。具体操作方案如下：首先将学生自由分组，小组成员共同从以前做过的实验项目选做题中选择一个进行程序的分析设计和编码实现，要求考虑程序的编写规范，程序的执行效率等方面。考核时，由实验教师从该小组随机抽取学生到讲台进行讲解和演示，根据程序完成情况和学生演示情况，决定该小组成员的平均得分，而每位学生的具体得分由小组成员内部根据该学生在该程序实现中的工作情况决定。通过这种方式，能培养学生的团队意识，达到互学互助的效果，同时也锻炼了学生的表达能力。 数据结构与算法实验环节教学改革的创新之处在于依托一门编程语言以及所开发的实验教学平台，因材施教，根据不同专业实际情况，综合考虑进行实验项目、实验内容和实验准备的合理设置，帮助学生在实验课上找到自己的最好学习方式，提高实验教学质量。 【参考文献】 [1]吴兵.高校计算机文化基础课程网络学习题库的研发[J].实验技术与管理，2011（2） [2]朱洪浩.数据结构课程“工程化”实践教学模式研究[J].赤峰学院学报（自然科学），2013（15） [3]马晓波，王翠茹.《数据结构》实践教学改革探讨[J].内蒙古农业大学学报（社会科学版），2010（02） [4]赵耀红，孙宇.数据结构实验教学的实践与探索[J].长春大学学报，2012（04） //文件名:exp9-1.cpp #include KeyType key; //KeyType为关键字的数据类型 //其他数据 //定义表中最多记录个数 InfoType data; } NodeType;typedef NodeType SeqList[MAXL]; //顺序表类型 int SeqSearch(SeqList R,int n,KeyType k)//顺序查找算法 { int i=0; while(i { } printf(“%d ”,R[i].key);i++; //从表头往后找 if(i>=n)return-1; else } void main(){ SeqList R;{ } printf(“%d”,R[i].key);return i; } int n=10,i;KeyType k=5;int a[]={3,6,2,10,1,8,5,7,4,9};for(i=0;i //建立顺序表 printf(“关键字序列:”);for(i=0;i 截图如下： 实验题9.2 设计一个程序exp9-2.cpp，输出在顺序表{1，2，3，4，5，6，7，8，9，10}中采用折半查找法查找关键字9的过程。 程序如下： //文件名:exp9-2.cpp #include //定义表中最多记录个数 KeyType key; //KeyType为关键字的数据类型 InfoType data; //其他数据 } NodeType;typedef NodeType SeqList[MAXL]; //顺序表类型 int BinSearch(SeqList R,int n,KeyType k)//二分查找算法 { int low=0,high=n-1,mid,count=0;while(low<=high) { mid=(low+high)/2;printf(“ 第%d 次 比 较 :在[%d,%d]R[%d]:%dn”,++count,low,high,mid,R[mid].key); if(R[mid].key==k) //查找成功返回 return mid; if(R[mid].key>k) //继续在R[low..mid-1]中查找 high=mid-1; else low=mid+1; //继续在R[mid+1..high]中查找 } return-1;} void main(){ SeqList R;KeyType k=9;int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;for(i=0;i //建立顺序表 R[i].key=a[i];printf(“关键字序列:”);for(i=0;i 比 较 元 素 中 } else printf(“元素%d的位置是%dn”,k,i);printf(“元素%d不在表中n”,k); 截图如下： 实验题9.3 设计一个程序exp9-3.cpp，输出在顺序表{8，14，6，9，10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87}中采用分块查找法查找（每块的块长为5，共5块）关键字46的过程。 程序如下： //文件名:exp9-3.cpp #include KeyType key; //KeyType为关键字的数据类型 //定义表中最多记录个数 //定义索引表的最大长度 InfoType data; //其他数据 } NodeType;typedef NodeType SeqList[MAXL];typedef struct { KeyType key;int link; //KeyType为关键字的类型 //指向分块的起始下标 //顺序表类型 } IdxType;typedef IdxType IDX[MAXI]; //索引表类型 int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)//分块查找算法 { int low=0,high=m-1,mid,i,count1=0,count2=0;int b=n/m; //b为每块的记录个数 printf(“二分查找n”);while(low<=high) //在索引表中进行二分查找,找到的位置存放在low中 { mid=(low+high)/2;printf(“ 第%d 次 比 较 :在[%d,%d] 中 比 较 元R[%d]:%dn”,count1+1,low,high,mid,R[mid].key); if(I[mid].key>=k) high=mid-1; else low=mid+1; count1++; //累计在索引表中的比较次数 } if(low //在索引表中查找成功后,再在线性表中进行顺序查找 { printf(“比较%d次,在第%d块中查找元素%dn”,count1,low,k); i=I[low].link; printf(“顺序查找:n ”); while(i<=I[low].link+b-1 && R[i].key!=k) { i++;count2++; printf(“%d ”,R[i].key);} //count2累计在顺序表对应块中的比较次数 printf(“n”); printf(“比较%d次,在顺序表中查找元素%dn”,count2,k); if(i<=I[low].link+b-1) return i; else return-1;} 素 } return-1;void main(){ } SeqList R;KeyType k=46;IDX I;int a[]={8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87},i;for(i=0;i<25;i++)R[i].key=a[i]; //建立顺序表 I[0].key=14;I[0].link=0;I[1].key=34;I[1].link=4;I[2].key=66;I[2].link=10;I[3].key=85;I[3].link=15;I[4].key=100;I[4].link=20;if((i=IdxSearch(I,5,R,25,k))!=-1)else printf(“元素%d不在表中n”,k);printf(“元素%d的位置是%dn”,k,i);printf(“n”); 实 验 报 告 学生姓名：XXX 学 号：20*** 指导教师：刘峤 实验地点：信软机房306 实验时间：2014/6/20 一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—排序与查找 三、实验学时：4 四、实验原理： 快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 1）设置两个变量I、J，排序开始的时候I：=1，J：=N 2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]； 3）从J开始向前搜索，即（J：=J-1），找到第一个小于X的值，两者交换； 4）从I开始向后搜索，即（I：=I+1），找到第一个大于X的值，两者交换； 5）重复第3、4步，直到I=J。 二分法查找（折半查找）的基本思想： （1）确定该区间的中点位置：mid=（low+high）/2 min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置 （2）将待查a值与结点mid的关键字（下面用R[mid].key）比较，若相等，则查找成功，否则确定新的查找区间： A)如果R[mid].key>a，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中,这时high=mid-1; B)如果R[mid].key C)如果R[mid].key=a，则查找成功。 （3）下一次查找针对新的查找区间，重复步骤（1）和（2） （4）在查找过程中，low逐步增加，high逐步减少，如果high 五、实验目的： 本实验通过实现快速排序和折半查找算法，使学生理解如何实现快速查找和排序的基本算法思想。通过练习，加强对算法的理解，提高编程能力。 六、实验内容： （1）实现数据序列的输入; （2）实现快速排序算法,并对输入的序列排序后输出； （3）实现折半查找算法,并在步骤(2)排序后的序列上,进行任意地 查找,并输出查询结果。 七、实验器材（设备、元器件）： 八、数据结构及程序 #include #define MAX_LEN 100 void Sort(int *data,int left,int right){ int i,j,temp; i=left; j=right; temp=data[left]; if(left>right) return; while(i!=j){ while(data[j]>=temp&&j>i) j--; if(j>i) data[i++]=data[j]; while(data[i]<=temp&&j>i) i++; if(j>i) data[j--]=data[i]; } data[i]=temp; Sort(data,left,i-1);PC机一台，装有C/C++语言集成开发环境。 Sort(data,i+1,right);} int Search(int *data,int start,int end,int key,int num){ int result; int p =(start + end)/ 2; if(data[p] == key&&start<=end){ result = p; num++; if(data[p] > key) result = Search(data, start, p, key,num); else result = Search(data, p + 1, end, key,num); return result; } else if(num==0&&start>end){ result =-1; printf(“n 404 NO FOUNDn”); return result; } else if(num!=0&&start>end){ result=-1; if(num==1) printf(“nFounded number only one”); else printf(“nFounded number more than one”); return result; } else if(result!=-1){ if(data[p] > key) result = Search(data, start, p-1, key, num); else result = Search(data, p + 1, end, key, num); return result; } else { result=-1; return result; } } void loadFile(int *data,char *filename,int n){ int i; FILE *pfile=NULL; pfile=fopen(filename,“r”); if(!pfile){ printf(“Open file failn”); exit(0); } else printf(“Open file success!n”); for(i = 0;i < n;i++) fscanf(pfile , “%d ”,&data[i]);} int main(int argc, const char * argv[]){ int input=1,data[MAX_LEN],num=0,key=1,i,cmd; char filename[100]; printf(“Choose Mode :n 1.Input Mode 2.File Moden”); scanf(“%d”,&cmd); if(cmd==1){ printf(“Input data :(Enter 0 to detemine)n”); while(input!=0){ printf(“Enter the %d data :”,num+1); scanf(“%d”,&input); if(input!=0){ data[num]=input; num++; } } } else{ printf(“nInput the address of the file: ”); scanf(“%s”,filename); printf(“nInput the number of elem: ”); scanf(“%d”,&num); loadFile(data,filename,--num); } Sort(data, 0, num); printf(“nSort result: ”); for(i=1;i<=num;i++) printf(“%d ”,data[i]); printf(“nn”); while(key!=0){ printf(“nInput a key to search :(Enter 0 to detemine)”); scanf(“%d”,&key); if(key!=0) Search(data, 0, num, key, 0); } return 0;} 九、程序运行结果： 1.打开程序： 2.尝试手动输入模式： 3.搜索已存在数： 4.搜索不存在数： 5.尝试文件读入模式并搜索 实验成功。 十、实验结论： 使用好的排序与查找算法对于程序的运行效率至关重要，一个好的算法，适合的算法能使计算机对数据的处理事半功倍，而选用错误的算法，不但可能事倍功半，还有可能造成不稳定因素。 快速排序的时间复杂度为n（log2n）,是排序算法中最为快速的一种，但是不稳定，对基本有序的序列效率较差。 二分查找算法在查找算法中，速度快，效率高，但是要求数据要有序。 十一、总结及心得体会： 当空间充足，对稳定性要求不高的情况，排序算法宜使用快速排序。 学 生 实 验 报 告 册 课程名称： 学生学号： 所属院部： （理工类） 算法与数据结构 专业班级： 14计单（2） 1413201007 学生姓名： 毛卓 计算机工程学院 指导教师： 章海鸥 16 ——20 17 学年 第 二 学期 金陵科技学院教务处制 金陵科技学院实验报告 实验报告书写要求 实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用A4的纸张。 实验报告书写说明 实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。 填写注意事项 （1）细致观察，及时、准确、如实记录。（2）准确说明，层次清晰。 （3）尽量采用专用术语来说明事物。 （4）外文、符号、公式要准确，应使用统一规定的名词和符号。（5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。 实验报告批改说明 实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。 实验报告装订要求 实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。 金陵科技学院实验报告 实验项目名称： 顺序表 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验1 顺序表 一、实验目的和要求 掌握顺序表的定位、插入、删除等操作。 二、实验仪器和设备 VC6.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。 （2）编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回－1。编写主函数测试结果。（3）在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。 解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。 （4）删除顺序表中所有等于X的数据元素。 2、选做题 （5）已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值相同的元素）。 程序清单： （1）:/*编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。*/ #include 金陵科技学院实验报告 }sequenlist;void main(){ sequenlist L;int i,n;printf(“请输入元素个数：”);scanf(“%d”,&n);printf(“n请输入元素：”);for(i=0;i 如果不存在，返回－1。*/ #include int fun(sequenlist L,int x,int n){ 金陵科技学院实验报告 } int i;for(i=0;i } int i,n,y;int x; printf(“请输入元素个数：”);scanf(“%d”,&n);printf(“n请输入元素：”);for(i=0;i printf(“n请输入要查找的数据元素：”);scanf(“%d”,&x);y=fun(L,x,n);if(y==-1)else printf(“n数据元素 %d 所在的位置为 %d n”,x,y);printf(“n所要查找的数据元素不存在。n”);(3): /*在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。 解题思路：首先查找插入的位置，再移位，最后进行插入操作； 从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置； 金陵科技学院实验报告 然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。*/ #define maxsize 100 typedef struct{ int data[maxsize]; int last;}sequenlist;main(){ int i,x,j; sequenlist l={{1,3,5,6,7,9},5}; printf(“n插入元素前的数据为:”); for(i=0;i<=l.last;i++) printf(“%2d”,l.data[i]); printf(“n请输入要插入的元素:”); scanf(“%d”,&x); for(i=1;i<=l.last;i++) if(l.data[i-1]>x)break; if(i>l.last) { l.data [l.last +1]=x; } else { for(j=l.last;j>=i-1;j--)l.data[j+1]=l.data[j];l.data[i-1]=x; } l.last++; printf(“插入元素后的数据为:n”); 金陵科技学院实验报告 for(j=0;j<=l.last;j++) printf(“%3d”,l.data[j]); printf(“n”);}(4): /*删除顺序表中所有等于X的数据元素。*/ #define maxsize 100 typedef struct{ int data[maxsize]; int last;}sequenlist;main(){ int i,j,x=0,k=0; sequenlist L={{1,3,5,7,2,4,6,8,2,9},9}; printf(“n原数据为:”); for(i=0;i<=L.last;i++)printf(“%3d”,L.data[i]); printf(“n请输入要删除的数据:”); scanf(“%d”,&x); for(i=1;i<=L.last+1;i++) if(L.data[i-1]==x){ for(j=i;j<=L.last+1;j++)L.data[j-1]=L.data[j]; L.last--; i--; k=1; } if(k==1){ printf(“删除后的数据为:n”); for(j=0;j<=L.last;j++)printf(“%3d”,L.data[j]); } else printf(“Not found!n”); 金陵科技学院实验报告 printf(“n”);} 四、实验结果与分析（程序运行结果及其分析）（1）结果： 请输入元素个数：5 请输入元素：1 2 3 4 5 元素输出：1 2 3 4 5（2）结果： 请输入元素个数：5 请输入元素：1 2 3 4 5 请输入要查找的数据元素：5 数据元素5所在的位置为 4（3）结果：插入数据前的元素为：1 3 5 6 7 9 请输入要插入的元素为：10 插入元素后的数据为: 5 6 7 9 10（4）结果：原数据为：1 3 5 7 2 4 6 8 2 9 请输入要删除的数据为：7 删除后的数据为： 3 5 2 4 6 8 2 9 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 单链表 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验2 单链表 一、实验目的和要求 1、实验目的 掌握单链表的定位、插入、删除等操作。 2、实验要求 （1）注意链表的空间是动态分配的，某结点不用之后要及时进行物理删除，以便释放其内存空间。 （2）链表不能实现直接定位，一定注意指针的保存，防止丢失。 二、实验仪器和设备 Visual C++6.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写程序建立一个单链表，并逐个输出单链表中所有数据元素。（2）在递增有序的单链表中插入一个新结点x，保持单链表的有序性。 解题思路：首先查找插入的位置然后进行插入操作；从第一个结点开始找到第一个大于该新结点值的结点即为插入位置；然后在找到的此结点之前插入新结点；注意保留插入位置之前结点的指针才能完成插入操作。 （3）编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。 2、选做题 已知指针LA和LB分别指向两个无头结点单链表的首元结点。要求编一算法实现，从表LA中删除自第i个元素起共len个元素后，将它们插入到表LB中第j个元素之前。程序清单： 金陵科技学院实验报告 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 堆栈和队列 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验3 堆栈和队列 一、实验目的和要求 （1）掌握应用栈解决问题的方法。（2）掌握利用栈进行表达式求和的算法。 （3）掌握队列的存储结构及基本操作实现，并能在相应的应用问题中正确选用它们。 二、实验仪器和设备 Visual C++6.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）判断一个算术表达式中开括号和闭括号是否配对。（2）测试“汉诺塔”问题。 （3）假设称正读和反读都相同的字符序列为”回文”，试写一个算法判别读入的一个以’@’为结束符的字符序列是否是“回文”。 2、选做题 在顺序存储结构上实现输出受限的双端循环队列的入列和出列算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 串 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验4 串 一、实验目的和要求 掌握串的存储及应用。 二、实验仪器和设备 Visual C++6.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写输出字符串s中值等于字符ch的第一个字符的函数，并用主函数测试结果。 （2）编写输出字符串s中值等于字符ch的所有字符的函数，并用主函数测试结果。 解题思路：可以将第一题程序改进成一个子函数，在本题中循环调用。（3）设字符串采用单字符的链式存储结构，编程删除串s从位置i开始长度为k的子串。 2、选做题 假设以链结构表示串，编写算法实现将串S插入到串T中某个字符之后，若串T中不存在这个字符，则将串S联接在串T的末尾。 提示：为提高程序的通用性，插入位置字符应设计为从键盘输入。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 二叉树 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验5 二叉树 一、实验目的和要求 （1）掌握二叉树的生成，以及前、中、后序遍历算法。（2）掌握应用二叉树递归遍历思想解决问题的方法。 二、实验仪器和设备 Visual C++6.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）建立一棵二叉树。对此树进行前序遍历、中序遍历及后序遍历，输出遍历序列。 （2）在第一题基础上，求二叉树中叶结点的个数。（3）在第一题基础上，求二叉树中结点总数。（4）在第一题基础上，求二叉树的深度。 2、选做题 已知一棵完全二叉树存于顺序表sa中，sa.elem[1…sa.last]存储结点的值。试编写算法由此顺序存储结构建立该二叉树的二叉链表。 解题思路：根据完全二叉树顺序存储的性质来确定二叉树的父子关系即“还原”了二叉树，之后再按照二叉树二叉链表的构造方法进行建立。完全二叉树顺序存储的一个重要性质为，第i个结点的左孩子是编号为2i的结点，第i个结点的右孩子是编号为2i+1的结点。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 金陵科技学院实验报告 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 图 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验6 图 一、实验目的和要求 （1）熟练掌握图的基本概念、构造及其存储结构。 （2）熟练掌握对图的深度优先搜索遍历和广度优先搜索遍历的算法。 二、实验仪器和设备 Visual C++6.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）构造一个无向图（用邻接矩阵表示存储结构）。 （2）对上面所构造的无向图，进行深度优先遍历和广度优先遍历，输出遍历序列。 2、选做题 采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。简单路径是指其顶点序列中不含有重复顶点的路径。提示：两个顶点及k值均作为参数给出。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 排序 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验7 排序 一、实验目的和要求 （1）熟练掌握希尔排序、堆排序、直接插入排序、起泡排序、快速排序、直接选择排序、归并排序和基数排序的基本概念。 （2）掌握以上各种排序的算法。区分以上不同排序的优、缺点。 二、实验仪器和设备 Visual C++6.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 用随机数产生100000个待排序数据元素的关键字值。测试下列各排序函数的机器实际执行时间（至少测试两个）：直接插入排序、希尔排序（增量为4，2，1）、冒泡排序、快速排序、直接选择排序、二路归并排序、堆排序和基于链式队列的基数排序。 2、选做题 假设含n个记录的序列中，其所有关键字为值介于v和w之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v…w]，令number[i]统计关键字为整数i的纪录个数，然后按number重排序列以达到有序。试编写算法实现上述排序方法，并讨论此种方法的优缺点。程序清单： 金陵科技学院实验报告 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 五、实验体会（遇到问题及解决办法，编程后的心得体会） 金陵科技学院实验报告 实验项目名称： 查找 实验学时： 2 同组学生姓名： 实验地点： 实验日期： 实验成绩： 批改教师： 批改时间： 金陵科技学院实验报告 实验8 查找 一、实验目的和要求 （1）掌握顺序表查找、有序表查找、索引顺序表查找的各种算法。（2）掌握哈希表设计。 二、实验仪器和设备 Visual C++6.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）在一个递增有序的线性表中利用二分查找法查找数据元素X。 2、选做题 （2）构造一个哈希表，哈希函数采用除留余数法，哈希冲突解决方法采用链地址法。设计一个测试程序进行测试。 提示：构造哈希表只是完成查找的第一步，大家应该掌握在哈希表上进行查找的过程，可以试着编程序实现。程序清单： 金陵科技学院实验报告 四、实验结果与分析（程序运行结果及其分析） 关键词：数据结构,实验,改革 数据结构课程于1978年首次引入我国并在清华大学计算机专业开出,迅速在全国传播开来。在我国《计算机学科教学计划1993》中“数据结构与算法”被列为9个主科目领域的第一位。在美国《Computing Curricula 2001》的12个主科目中也是处于重要的、基础的位置[1]。目前,数据结构与算法设计课程已成为我校计算机专业、网络工程专业、软件专业等相关专业的一门重要的专业技术基础课,而该课程的实验课是学生验证、掌握和应用数据结构理论的重要途径。 由于该课程涉及大量抽象数据类型及算法,理论性很强,对学生的学习造成了一定的难度。同时因学生基本程序设计能力整体有待提高等因素影响,传统的实验教学效果都不太理想,影响了整个课程的教学质量,对学生相应能力的提高也很不利。近几年来,作者在针对计算机专业等几个专业的数据结构课程实验教学过程中,进行了一定的尝试和探索,通过实验环节相应教学设计的创新和实践,教学方法和手段日趋成熟与合理,也使学生认识到了课程的重要性,克服了畏难情绪,提高了学习兴趣和积极性,取得了一定的教学效果。 一、实验教学中存在的问题 在教学过程中发现,很多学生都感觉《数据结构与算法》课程实验枯燥、不易学。上课时不知该做什么,不知从何处入手完成实验题目。原因有以下几点: 1. 课程本身难度大理论性强 《数据结构与算法》课程不仅逻辑性强,而且极具抽象性,即使利用课件也无法完全将理论知识很直观地表现出来。另外《数据结构与算法》课程内容较多,学生前面的知识还没有完全理解,新的知识就接踵而至,使得存在的问题堆积,实验内容很难完成[2]。而且由于理论的抽象性,学生头脑中难以建立起数据结构和相应算法的概念,容易产生畏难和茫然的情绪。学生在实验时往往反映为缺乏信心,无从下手。 2. 学生对程序设计语言掌握得不好 《数据结构与算法》课程具有较强的实践性,其教学基本上都是在学过一门或几门语言的基础上进行的。《数据结构与算法》中的算法大都由类PASCAL、C或C++语言描述,要求学生能够使用某种程序设计语言对算法进行程序设计,并且上机调试通过[3]。以我学院为例,学生在大学第一学期学习过C语言,但往往只接触到简单数据类型和单个函数形式的程序,侧重于基本语法的学习,对数据结构实验中大量用到的头文件、宏定义、结构体、指针、递归、函数调用等知识接触较少,理解较浅。使得在实验课上很多学生编写的程序往往在编译阶段就错误百出。而且一部分学生程序调试能力不够,对大量的英文报错信息看不懂或不理解,很容易失去学习的积极性。最终由于对程序设计语言掌握得不好,大部分学生陷入程序编译错误的调试之中,阻碍了他们对各类数据结构和算法等知识点的理解和应用,形成恶性循环,使教学目标难以实现。 3. 学生的实践机会少 本课程的知识点较多,而且基本都是比较重要、需要掌握的,因此在实验教学中要尽量兼顾到大多数比较重要的知识点。一学期有限的上机实验中,学生练习的题目一般针对《数据结构与算法》中以章节划分为主的知识点,规模较小、针对性较强,缺少一些连贯性和系统性,无法锻炼学生处理复杂问题的能力,学生面对具体问题时,不能综合地运用数据结构知识解决实际问题。因此在实验内容取舍和实验时间安排上就产生了矛盾,如何在二者之间取得平衡就成为一个比较重要的问题。 二、实验教学改革的探索与实践 考虑到该实验课程教学中遇到的实际问题,为配合新一轮人才培养方案的修改,以培养创新型软件人才为目标,对该课原有传统实验教学进行改革,建立与数据结构与算法理论教学紧密结合,分层次的数据结构及算法实验教学模式。改革主要从以下三个方面进行: 1. 实验教学内容的改革 在课程实验大纲指导下,针对学完的知识点适时地选择有代表性、难度适中、综合性的典型算法,以一当十、以点带面,让学生进行编程、上机、调试,这样学生既可以在实验中加深掌握该种数据结构下的数据组织、加工、处理方法,进一步理解算法的设计,又能够锻炼编写和调试程序的能力。例如,可增加设计性实验,包括:单链表的合并、单循环链表的逆置、删除单链表中的重复值、在链式存储结构上实现串模式匹配算法、三角对称矩阵的压缩存储及其转置、确定待排数据排序后的有序号等;综合性实验包括:学生成绩管理、双向链表的插入、查找与删除、约瑟夫环问题、停车场管理、迷宫求解等。目前的所有实验内容涵盖了计算机科学中涉及到的大量经典算法的实现,涉及到数据结构与算法的大量实现细节和编程技巧,能够帮助学生提高运用知识解决实际问题的能力。但是由于重新设计的《数据结构与算法》实验内容大幅度增加了,要想在实验课程规定的时间内完成全部的实验内容是比较困难的。这就涉及到对实验课管理模式的改革。 2. 实验教学管理模式的改革 针对学生实践机会太少的现状,合理整合计算机实验教学资源,实现数据结构与算法实验开放式管理,可以实行“实验预约”,“自由上机”结合“实验选修”的开放式管理。完善实验室开放运行机制,其中包括实验室时间开放、实验室空间开放、实验内容开放。制定相应的实验室开放管理办法、制度和保障措施。实验室开放式管理能增加学生上机的自由度,学生可以利用业余时间反复实践,提高计算机应用能力。以计算机05级某班为试点,在本学期的《数据结构与算法》实验课中试行开放式管理模式。目前,该班级实验课运行流畅。 3. 实验教学方法手段的改革 在教学方法上,不再简单停留于教师讲解和安排完实验任务之后就由学生按部就班地完成实验的形式,而是用启发式教学论的思想来进行教学。在实验课初期,针对学生存在的问题,可以提前辅导C语言知识,重点辅导结构体的定义、指针的使用、函数的定义及调用三个部分,为解决课程中的实际问题作准备。在实验课上针对部分学生C语言程序设计能力薄弱的特点,不断总结学生在程序设计中反应出来的普遍问题,有针对性的在每次课中复习C语言程序设计的部分知识。重点进行讲解实验中容易碰到的问题,引导学生对复杂问题进行分析,学会画流程图分析问题,使设计的程序具有逻辑性,减少出错的可能性。指导学生学会对问题进行模块划分和分解,降低问题难度,分步解决问题。经过几个学期的对比,可以肯定的是教学方法的改变对大多数同学是非常有帮助的。通过课前与课上的辅导,数据结构与算法实验课的课堂效果有明显的提高,大部分同学编写程序的能力有明显的改善。教学评价手段以考核方式为例,改变传统的实验报告,采取软件工程报告书的形式来撰写实验报告。根据实验报告的质量、考核成绩和学生平时参与实验的表现来评定实验课程的成绩。对进行了设计性和综合性实验并参与开放实验,并取得了一定成果的学生在分数上给予鼓励。 对比传统教学与改革后的教学情况,调查学生反馈情况,检验改革成果及效应。在实验过程中,由于同学们可自行安排、调配实验时间及内容,学习的积极性和自信心很高,这些对于提高教学效果的提高有很大的帮助。多数同学还认为,通过独立完成自己所选定的实验,个人的责任感、自信心、创造力得到了激发。从实验验收情况来看,报告内容详细周到,实验小结也没有以往的空话、套话,这从一定程度上也反映了这种实验教学模式取得了良好的效果。通过这样的教学模式,学生学会自主安排实验时间,学会使用实验设备和排除一般故障,学会在实验结束后对设备进行整理和归置,学会及时将实验报告整理归档,从而营造良好的实验教学环境,实现整个实验教学进程的良性循环。 三、结论 《数据结构与算法》实验课程的建设在计算机专业的建设中具有重要的作用,它是一门理论性和实践性很强的课程,它需要理论教学的结果来指导实验教学的过程,更需要实验教学的过程来强化理论教学的效果,因此科学系统安排实验教学是激发学生的学习兴趣、培养学生动手解决实际问题的能力的关键途径。 参考文献 [1]王沁.提高数据结构实验的教学质量[J].江门职业技术学院学报,2005,2 [2]汪军,周鸣争.“数据结构”课程教学方法的改革与实践[J].兰州工业高等专科学校学报,2004,3 【数据结构实验指导(实验五：查找算法)】相关文章： 数据结构实验报告10-18 北邮数据结构实验四06-13 数据结构实验报告答案07-29 数据结构实验报告答案04-01 数据结构实验报告格式04-01 数据结构内排序实验报告05-28 云南大学数据结构实验05-23 数据结构实验教学改革的尝试11-13 数据结构多项式相加实验报告07-30 数据结构中常用算法05-08算法与数据结构实验教学探讨 第3篇
数据结构实验指导(实验五：查找算法) 第4篇
数据结构查找实验报告 第5篇
数据结构实验报告-排序与查找 第6篇
算法与数据结构实验册 第7篇
数据结构实验指导(实验五：查找算法) 第8篇