第一篇：教案程序代码-查找与排序
一、查找
1、顺序查找
int search(ET v[], int n , ET x){ int k=0;while(k 2、二分法查找 int bsearch(ET v[] , int n, ET x){ int i, j, k;while(i<=j){ k=(i+j)/2;if(x==v[k])return k;if(x 3、分块查找 struct indnode { int key;int k;};int insearch(ET v[], struct indnode s[], int n, int m, ET x){ int i, j, t;i=0;j=m-1;while(i<=j){ t=(i+j)/2; if(x<=s[t].key)j=t-1; else if(x>s[t].key)i=t+1;} if(i 二、排序 1、双向冒泡 void bubsort(ET p[], int n) { int m, k, j, i;ET d; k=0;m=n-1; while(k if(p[i]>p[i+1]) { d=p[i];p[i]=p[i+1];p[i+1]=d;m=i;} j=k+1;k=0;for(i=m;i>=j;i--) if(p[i-1]>p[i]) { d=p[i];p[i]=p[i+1];p[i+1]=d;k=i;} } } 2、快速排序1 void qksort(ET p[], int m, int n){ int i;if(n>m) { i=split(p, m, n); qksort(p, m, i-1);qksort(p, i+1, n);} return;} static int split(ET p[], int m , int n){ int I, j, k, u;ET t;i=m-1;j=n-1;k=(i+j)/2;if(p[i]>=p[j]&&p[j]>=p[k])u=j;else if(p[i]>=p[k]&&p[k]>=p[j])u=k;else u=i;t=p[u];p[u]=p[i];while(i!=j){ while(i while(i if(i 3、快速排序2 void quicksort(int p[],int left,int right){ int i, j, t; i=left;j=right;t=p[i]; while(i { } p[i]=t; outtable(p); if(left if(j 4、直接插入排序 void insort(ET p[], int n) { int j, k;ET t; for(j=1;j { t=p[j]; k=j-1; while(k>=0 && p[k]>t) { p[k+1]=p[k];k=k-1;} p[k+1]=t;} } 5、希尔排序 void shlsort(ET p[], int n){ int h, j, k;ET t; h=h/2; while(h>0) { for(j=h;j<=n-1;j++) { t=p[j]; k=j-h; while(k>=0 && p[k]>t) { p[k+h]=p[k];k=k-h;} p[k+h]=t;} h=h/2;} } 6、选择排序 void select(ET p[], int n){ int i, j, k;ET d;for(i=0;i p[i]=p[j];i++; } while((i } for(j=i+1;j void heap(ET p[], int n){ int i, k;ET t; k=n/2; for(i=k-1;i>=0;i--)sift(p, n-1, i); for(i=n-1;i>=1;i--) { t=p[0];p[0]=p[i];p[i]=t; sift(p, i-1, 0); } return;} static sift(ET A[], int n, int m) { int j;ET t; t=h[m];j=2*(m+1)-1;while(j<=n){ if(j 如有打错的地方请指出。 电 子 科 技 大 学 实 验 报 告 学生姓名：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）,是排序算法中最为快速的一种，但是不稳定，对基本有序的序列效率较差。 二分查找算法在查找算法中，速度快，效率高，但是要求数据要有序。 十一、总结及心得体会： 当空间充足，对稳定性要求不高的情况，排序算法宜使用快速排序。 快速排序和二分查找配合，可以以较高的效率查找目标元素。 查找及排序算法实现 一、实验目的 1、熟练掌握二叉排序树查找算法及C语言描述。 2、熟练掌握折半查找算法及C语言描述。 3、熟练掌握简单选择排序算法及C语言描述。 4、熟练掌握简单插入排序算法及C语言描述。 5、熟练掌握冒泡（起泡）排序算法及C语言描述。 6、了解各种查找及排序算法的优缺点、实用性及应用。 7、将理论与实际相结合，切实提高自己的逻辑能力和动手能力。 二、设计内容 1.折半查找算法 折半查找算法的思路： 初始状态：假设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值，初始时，令low=0,high=n-1,mid=(low+high)/2 让key与mid指向的记录比较 若key==r[mid].key，查找成功,算法结束；若key 起泡排序的思路： 首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即L.r[1].key>L.r[2].key），则将两个记录交换之，然后比较【第二个记录和第三个记录】的关键字。以此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称做第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上，然后进行第二趟起泡排序，对前n-1个记录进行同样操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置上。一般地，第i躺起泡排序是从L.r[1]到L.r[n-i+1]以此比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。整个排序过程需进行k(1<=k 首先以一个元素为基准，从一个方向开始扫描，比如从左至右扫描，以a[0]为基准，接下来从a[0]...a[9] 中找出最小的元素，将其与a[0]交换，然后将基准位置右 移一位，重复上面的动作，比如，以a[1]为基准，找出a[1]至a[9]中最小的，将其与a[1]交换，一直进行到基准位置移到数组最后一个元素时排序结束（此时基准左边所有元素均递增有序，而基准为最后一个元素，故完成排序）。4.直接插入排序算法 直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的，记录数增1的有序表。 一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r[1...i-1]中插入一个记录r[i]后，变成含有i个记录的有序子序列r[1....i].在自i-1起往前搜索的过程中，可以同时后移记录。 整个排序过程为进行n-1躺插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止 三、程序源代码 1.二叉排序树的创建、遍历和查找删除算法 #include void Insert(Tree &T,KeyType key){ if(!T){ T=new LNode;T->data=key;T->lchild=T->rchild=NULL;} else } { } if(key } int num;char c;while(scanf(“%d”,&num)){ } Insert(T,num);c=getchar();if(c=='n')return;void In_Order(Tree T)//中序遍历 { if(T){ In_Order(T->lchild);printf(“%d ”,T->data);} In_Order(T->rchild);} void Delete(Tree &p){ Tree q,s;if(!p->rchild){ q = p;p=p->lchild;free(q);} else if(!p->lchild){ } q = p;p=p->rchild;free(q); else { } q = p;s = p->lchild;while(s->rchild){ } q = s;s = s->rchild;p->data = s->data;if(q!=p)q->rchild = s->lchild;else q->lchild = s->lchild;free(s);} void DelNode(Tree &T,KeyType key){ } if(!T){ printf(“n该结点不存在n”);return;} else { } if(key == T->data)Delete(T);else if(key < T->data)DelNode(T->lchild, key);else DelNode(T->rchild,key);Tree Search(Tree T,KeyType key)//二叉排序树查找 { if(!T){ } printf(“该结点不存在”);return 0;else if(key == T->data)return T;else if(key < T->data) return(Search(T->lchild, key));else return(Search(T->rchild, key));} int main()//主函数 { Tree T,p;T=NULL;KeyType x; printf(“请输入二叉树各结点：n”); CreatTree(T); printf(“中序遍历为：n”);In_Order(T);printf(“n请输入要查找和删除的结点：n”);scanf(“%d”,&x);p=Search(T, x);if(p){ } DelNode(T, x);printf(“中序遍历为：n”);In_Order(T); } 2、冒泡排序和折半查找算法 #include int BubbleSort(int c[]){ int i,t,j;for(i=0;i<9;i++){ } for(j=0;j<9-i;j++){ } if(c[j]>c[j+1]){ } t=c[j];c[j]=c[j+1];c[j+1]=t; printf(“n您所输入的数字的升序排列是:nn”);for(i=0;i<10;i++){ printf(“%d”,c[i]);printf(“ ”);} return 1;} //折半查找 int BinarySearch(int b[]){ } int t,mid;int i=0;int j=9;printf(“nn请输入您要查找的数字：”);scanf(“%d”, &t);while(i<=j){ mid=i+(j-i)/2; } return 1;if(t==b[mid]){ printf(“n您要查找的数字的排列位置是：%dn”,mid+1);break;} else if(t int main(int argc,char *argv[]){ int a[10];printf(“请您输入数据:nn”);for(int i=0;i<10;i++){ scanf(“%d”,&a[i]); } } BubbleSort(a);BinarySearch(a);return 0; 3、简单选择排序和简单插入排序算法 #include int i,j,min,p,key,k; for(i=0;i { key=0; min=a[i]; } for(j=i;j if(a[j] if(key==1){a[p]=a[i]; a[i]=min;} for(k=0;k printf(“%d ”,a[k]);printf(“n”); return 1;} int InserSort(int*a,int n){ int i,j,k;for(i=2;i<=n;i++){ a[0]=a[i];for(j=1;j { if(a[j]>a[i]){for(k=i;k>j;k--) a[k]=a[k-1]; a[k]=a[0]; } } break;} } for(j=1;j<=n;j++){ } printf(“%d ”,a[j]);printf(“n”);return 1;int main(){ int a[80],i,n,b;printf(“请输入关键字的个数：”);scanf(“%d”,&n);printf(“排序类型：n”);printf(“1.选择排序n”);printf(“2.插入排序n”);printf(“请选择：”);scanf(“%d”,&b);switch(b){ case 1: printf(“请输入关键字：n”);for(i=0;i SelectionSort(a,n); return 1; break; case 2: printf(“请输入关键字：n”); for(i=1;i<=n;i++){ scanf(“%d”,&a[i]);} printf(“插入排序的流程以及结果：n”); InserSort(a,n);return 1; } break;}while(a!=0); 四、实验运行结果 1.二叉排序树的创建、遍历和查找删除算法 2、冒泡排序和折半查找算法 3、简单选择排序和简单插入排序算法 七、心得体会 通过本次的数据结构课程设计报告，掌握了查找和排序的几种基本排序算法，了解了他们各自的特点和优缺点，完成了对于他们C语言的描述和实际应用，对他们有了一个更加具体、深刻的认识，同时也锻炼了我们的逻辑思维能力和动手实践能力，使我们受益匪浅，给我们今后的计算机专业课程学习带来很大的帮助。 中班数学活动：《有趣的排序》 活动目标： 1、通过观察、尝试，引导幼儿发现规律，并对2种颜色进行各种有规律的排序。 2、在操作活动中，进一步提高孩子发现问题、解决问题的能力及发散性思维能力。 3、在游戏活动中，让幼儿感受排序的趣味性。活动准备： 1、PPT，黑板，自制图片。 2、各种排列规律的卡片。活动过程： （一）图片导入，自由探索。 观察、讨论图片上不同的变化，说说它们的排列规律。 师：今天，王老师带来几张神奇的图片，请你看一看，找一找，这三张图片的神奇之处在哪里？（出示三张不同变化规律的图片，激发幼儿兴趣。） 幼儿：通过观察，自由发言，找出图片规律。 （二）初步感受规律，尝试按物体颜色规律排序。 师：十一国庆假期，小朋友们和爸爸妈妈都去哪里旅游了？那你们是怎么去的呀？（火车、汽车......） 老师也去旅游了，你们看老师是怎么去的？（火车） 1、出示火车图片的排列，让幼儿感知物体排列的次序规律。学习按颜色间隔排列的方法。 2、请幼儿补规律。找出卡片上物体的规律，想想接着应该排什么？ 3、幼儿动手操作，把缺的补上去，将规律补完整，并说说为什么要这样补。 （三）尝试按规律排序，动手操作。 师：旅游景点到了，我们先要将车子放到停车场里，然后再去游玩。请你来观察，停车场里有什么规律？ 幼儿说一说自己的想法。（幼儿一边回答，教师一边操作，并引导孩子将规律说出来） （四）自主尝试设计规律，将两种颜色的花瓶有规律的排序。 师：说了这么多规律，现在请小朋友们自己动手试一试，老师给你们准备了漂亮的花瓶，请你们按照规律来排一排。听清楚要求：从头到尾坚持一种规律。 幼儿自选操作活动，教师巡回指导。鼓励幼儿大胆地尝试进行有规律的排列。 请幼儿介绍自己是按什么规律排列的。 （五）按规律排队 师：我们能不能像刚才排列花瓶一样，按照一种规律来排队呢？ 幼儿自己说一说自己的想法。幼儿根据规律排队。 查找资料 教学目标： ①知识与技能 掌握运用Inter网收集资料的方法 让学生学会使用“百度”搜索引擎搜索资料 ②过程与方法 利用完成任务练习，培养学生在网上迅速搜集信息，整理筛选信息的能力 ③情感态度 让学生养成正确的网络道德意识 让学生养成保护环境的环保意识 教学过程 ㈠导入 T：在我们的学习与生活中，都需要查找各种资料，那么同学们都是利用什么工具来查找资料的呢？ S： T：的确（我们还可以利用因特网），因特网不仅提供丰富的信息资料，还提供方便快捷的查找方法 T：在因特网上有许多专业机构专门对某一领域的信息建立资源网站，为人们提供专业的信息资源服务，那么今天我们就来学习如何查找资料 ㈡过程 活动一：查找“恐龙”的科普知识 T：大家有没有听说过“恐龙”呢？ S： T：是不是，觉得恐龙是很神秘的动物呢，那么今天我们就来查找一些恐龙的资料 T：那么在查找有关恐龙的资料之前，首先我们先来认识一个网站：中国科普博览网 T：现在，同学们先看老师操作：启动IE浏览器，找到地址栏，输入网址，按enter键或者转到，就打开了中国科普博览的首页，打开首页，里面有很多的资料，包含了很多方面的知识，当我们的鼠标在首页移动的时候，会发现光标的样式会发生变化，当它发生变化时就说明它是一个超级链接，现在点击“生命奥秘”，然后找到“恐龙”就找到了有关恐龙的知识资料了 T：同学都会了没有，好接下来就请同学们用老师刚才的那个方法，查 找有关“计算机病毒”方面的科普知识，阅读里面的内容。不会的同学可以看老师ppt的步骤 T： 同学们的任务都完成了没有？没有的话，等下再操作了，现在我们进入下一个活动 活动二：查找有关“酸雨”的信息 T：当我们不知道要查找的资料应该用具体的哪个网站时，我们该用生命办法来查找资料呢？ S： T：我们还可以利用专门的因特网上搜索网页网址的搜索网站，下面我们先介绍几个常用的搜索引擎 T：那么下面我们就以百度搜索引擎为例，通过百度查找关于“酸雨”的资料 T：动IE浏览器，在地址栏输入百度网址，按enter进入首页，其次要找到搜索引擎的位置，在文本框中输入关键词“酸雨”点击百度一下，百度搜索网站就会根据关键词，在因特网上进行搜索，接着的页面就是显示这个词的网页标题以及简要信息，点击其中的一个标题，就可以打开该网页，查看具体信息了 T：那么如果输入的关键词太简单了，搜索出来的往往会不符合我们的要求，要是逐一查看去筛选就会浪费很多时间，那要怎么办呢？ S： T：那么我们可以将滚动条往下拉，下面有一个相关搜索栏，可以看到有列出符合我们要求的关键词，这样再进行搜索的结果就会更加的准确 T： 那么接下来同学们打开百度搜索网站，查找“蚯蚓”和成语“兵不厌诈”的有关资料，等下请同学起来说一下。不会的同学可以看老师ppt上面的步骤。 ㈢总结： 那么我们今天学习了如何查找资料，同时在不懂具体网站时还可以利用其他搜索引擎，例如百度搜索，来查找我们所需要的资料第二篇：数据结构实验报告-排序与查找
第三篇：数据结构课程设计-查找排序
第四篇：排序教案
第五篇：查找资料教案
点击咨询 