数据结构-实验8查找的算法（共5篇）
篇1：数据结构-实验8查找的算法
8.1 实现顺序查找的算法
一，实验目的
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、有序表的查找之折半查找：前提必须是有序表，性能只有在均匀分布的时候才是最优的。 3、二叉排序树查找：通过一系列的查找和插入过程形成的树。之所以叫做排序树，因为按照中序遍历可得一个有序的序列。 实验项目：必做：顺序查找、折半查找 选做：二叉查找树 实验类型: 验证性 实验内容： 顺序查找：用数组或链表实现，数据有序或无序均可； 折半查找：必须用数组实现，且数据有序； 随着人们的生活水平的提高,家用轿车越来越多,这对交通管理提出了严峻的挑战,所以车辆牌照的智能识别系统成为新世纪交通管理的重要组成部分,它将对规范交通秩序,加快我国的现代化进程起到推波助澜的作用。车牌定位和车牌识别是车辆牌照的智能识别系统中的两个组成部分,其中车牌定位是系统中的一个关键部分,定位的准确度将直接影响车牌识别的效果。目前的车牌定位有基于神经网络的方法,基于边缘检测和纹理特征,以及灰度阈值法,直线边缘检测法等[1]。本文提出一种基于边界查找车牌定位算法,该算法不仅定位准确,而且计算量小,实时性高。 一、图像预处理 1.1 灰度均衡与图像滤波 由于图像采集卡采集到的图像受到光照不均,环境污染,车身反光等因素的影响,图像的质量受到一定程度失真,为便于后面处理速度提高以及定位准确,有必要进行灰度变换,灰度均衡是进行灰度变换的一个好的方法,它将原图像转变为灰度范围在0～255的图像,图像的对比度由此得到了提高,处理后的图像仍还含有噪声点,并且这些噪声点属于高频成分,如果不对这些噪声点进行处理,后面的车牌定位、字符分割和字符识别过程将受到严重的影响,必须滤除。对具有零均值噪声的均匀邻域进行平均化时,取均值是对f(i,j)较好的估计。但当该邻域跨越两块区域的边界时,由于两块不同的样本参与运算,将导致边界模糊。所以我选择了中值滤波,因为该滤波算法不仅能有效的抑制噪声,而且图像也不会变模糊,从而有利于车牌定位。 中值滤波的定义:设是含n个实数的有序数组,则A中各数中值是A[(n-1)/2]。 有时要区分考虑n为奇数或偶数的情况。当n为奇数时,数组具有如上定义的唯一中值。当n为偶数时,我们定义两个中值,A[n/2]及A[n/2-1],或者一个中值,即取这两个值的平均值,虽然采用有序排列来定义中值,在实际中这n个值并不需要做全排序。对著名的快排序算法进行修改,使它只对包含第(n+1)/2个元素在内的A的子数组进行递归排序。一旦排序支点元素位于原数组中间位置,整个集合的中值就可知道。 1.2 图像二值化[2][3] 对一副灰度图像进行处理,把其中感兴趣的像素分离出来作为前景像素,把不感兴趣的 其余部分作为背景像素,就可以得到一幅二值图像[4]一幅灰度车牌图像的大小为M行N列,方向为图像处理、智能信息处理等。 f(i,j)(0≤i 这里的T称为阈值(Threshold),经过二值化处理后,字符前景和车牌背景就由黑白两种颜色分开,选择不同的阈值会得到不同的分离结果,这里我采用了Otsu算法[5]对灰度图像进行二值化。基本思想是:它把所有像素分成两组,通过使两组像素的组内方差最小来确定阈值。首先定义直方图函数为一个概率函数P,其中P(0),…,P(I)表示灰度值0,…,I的直方图概率,P(i)=|{(r,c)Image(r,c)=i}|/|RxC|,其中RxC是图像的空间区域。如果直方图是方模式的,通过直方图求阈值也就是确定一个最好的阈值t,利用这个阈值把直方图的两种模式分开。根据阈值t可以确定灰度值小于或等于t的像素集的方差,以及灰度值大于t的像素集的方差。Otsu关于最佳阈值的定义是使组内方差的加权和最小的阈值,其中权是指各组概率。 设σ2w是小组内各方差的加权和,即组内方差;σ2i(t)是值小于或等于t的小组的方差,σ22(t)是值大于t的小组的方差;是值小于或等于t的小组的概率,q2(t)是值大于t的小组的概率;u2(t)是第一组的均值,u2(t)是第二组的均值。则组内方差σ2w定义为: 其中 利用简单的顺序搜索所有可能的t值,确定使最小的最佳阈值t,实验结果表明该算法能够选择合理的阈值t,使车牌字符与背景形成鲜明的对比。原车牌图像如图1所示, 二值化的图像如图2所示。 二、连通成分标记 因为二值化后的图像包含很多我们不感兴趣的物体,所以为了定位的准确,我们必须对我们感兴趣的连通区域进行标记。假设B是一幅二值图像,而且B[r,c]=B[r',c']=v,其中v=0或者v=1。如果存在一个像素序列[r,c]=[r0,c0],[r1,c1],…,[rn,cn]=[r',c'],其中B[ri,ci]=v,i=0,…,n,并且对任何i=0,…,n,[ri,ci]与[ri-1,ci-1]相邻的,则像素[r,c]语像素[r',c']通过值v连在一起。像素序列[r0,c0],[r1,c1],…,[rn,cn]就形成了从[r,c]到[r',c']的连接路径。一个值为v的连通成分,即值为v的像素的集合C,集合中的每个像素都通过值v相连接。 我们采用递归标记算法对二值图像进行标记。该算法思想是:首先把二值图像的像素值取负,使原来值1的像素变成值为-1。这样可以把未处理的像素(值为-1)与成分标记1分开。输入的是二值图像B,输出的是标记图象LB。这个过程是有search()函数实现的。 search()函数实现如下: (1)将起始标记label=0; (2)把B[ri,ci]作为开始,i=0,…,n,如果像素B[ri,ci]=-1,则转至(3),否则从函数中返回; (3)搜索当前点的八邻域,如果至少有一个邻域的像素值不等于-1;则将B[ri,ci]=label,label+=1; (4)i+=1,递归调用search(); 这样我们就得到一幅标记图像,为下一步的定位奠定了基础。 三、对车牌进行定[6,7] 我们采取边界查找算法对车牌进行定位的,该算法从左到右,从上到下扫描一遍图像,就可以抽取特定区域的边界。该算法输入的是一幅标记图像,其像素值表示区域的标记。假设用背景区域标记表示属于背景区域的像素,这些背景区域可能是不连通的,它们的边界不需要检测,此算法找到特定区域的边界后就立即停止查找。 车牌的标准像素宽及高我们分别记为:Width,Hight 该算法的实现过程如下: (1)输入一幅标记图像B; (2)B[ri,ci]表示当前被扫描的像素值。i=0,…,n,如果B[ri,ci]=B[ri+Width,ci]=B[ri,ci+Hight]=B[ri+Width,ci+Hight],由该处退出循环;否则转至(3); (3)i+=1,转至(2); 实验表明该算法定位车牌的准确率很高。 定位后的车牌如3所示。 四、实验结论 在vc++6.0[8]编译器上实现了该算法,为了检验我们提出的基于边界查找车牌定位系统的可行性,在收费站点分别在雨天晴天对该车牌定位系统进行了现场检验,结果表明该算法定位较为准确。我们采集了410幅图像,其中404幅定位准确,定位准确率在98.5%,基本上达到了定位的要求。 五、结束语 本文提出的基于边界查找的车牌定位算法,相对于传统的车牌定位算法有很大的改进,它不仅定位准确,而且计算量小,实时性高,能够适应大部分天气情况,但是该算法对车牌受到污染以及磨损的情况,定位不是十分的准确。所以下一步我们的工作是研究如何克服这些问题。 参考文献 [1]章毓晋编著:图像处理与分析[M].清华大学出版社.1999年3月. [2]Feng Meng Ling,Tan Yap Peng.Adaptive Binarization Method for Document Image Analysis Multimedia and Expo[C]//Proc.of ICME’04.2004-06-27:339-342. [3]Byeong Rae Lee,Kyungsoo Park,Hyunchul Kang,Haksoo Kim,Chungkyue Kim:Adaptive Local Binarization Method for Recognition of Vehicle License Plates.IWCIA2004:646-655. [4]刘明军车牌字符分割算法的比较研究[J].济南大学学报(自然科学版),2006,20(4):60-63. [5]赵清杰钱芳蔡利栋译著:计算机视觉[M].机械工业出版社.2005年3月. [6]Yu M.,Kim Y.D..An approach to Korean license plate recognition based on vertical edge matching.In:Proceedings of IEEE international Conference on Systems,Man.and Cybernetics.Nashville,2000,4:2975-2980. [7]D.S.Kim,S.I.Chien.Automatic Car License Plate Extraction Using Modified Generalized Symmetry Transform and Image Warping.In Proc.IEEE Int.Symp.Industrial Electro nics,VOL.3,2001:2022-2027. 【摘 要】针对在数据结构与算法实验教学中如何提高学生的编程和算法设计能力，分析并指出了在实验教学中普遍存在的问题，结合实验课的教学改革，开发实验平台，以期有效激发学生的学习兴趣和积极性，培养动手和创新能力。 【关键词】数据结构与算法 实验改革 平台建设 【中图分类号】 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”); 【数据结构-实验8查找的算法】相关文章： 数据结构查找习题及答案05-02 进路搜索的数据结构与算法及其仿真04-11 基于数据结构的最短路径算法的研究09-12 大数据算法的论文题目05-03 基于大数据算法的论文题目05-04 两种数据关联算法的比较02-09 数据结构与算法题目05-06 基于大数据深度学习算法的习题推荐10-31 树形结构的应用 数据结构实验04-25篇2：数据结构-实验8查找的算法
篇3：基于边界查找车牌定位算法的研究
篇4：数据结构-实验8查找的算法
篇5：数据结构查找实验报告