《c语言二分法查找法的图形演示程序.docx》由会员分享，可在线阅读，更多相关《c语言二分法查找法的图形演示程序.docx（9页珍藏版）》请在三一办公上搜索。
1、c语言二分法查找法的图形演示程序 电子实习报告 这次电子实习的目的是为了提高我们的编程能力，与上次的电工实习一样重要，要成为一名合格的大学本科毕业生，这是一个不可或缺的环节，所以我们要把握好这次机会，全力以赴，做到更好。 需求分析 这次实习，每个同学的题目都不一样，这才能考验学生的水平嘛，我的题目是：编写二分法查找法的图形演示程序，用箭头跟踪指示出二分查找过程中的查找位置。当我刚拿到题目的时候，顿时吃了一惊，这也太难了，让我用二分法查找一个 数还说的过去，那个我们学过，可是要用箭头跟踪指示出来可就让我大伤脑筋，用C语言绘图我们压根就没学过，我还想跟指导老师好好商量商量，让她多给点提示，可是仔细
2、一想，要是我学过，这两个星期都花上面都不合算，这也就是实习的目的所在啊，就的现学现用，顺便培养一下我们的自学能力，真是一箭双雕啊。 接着，还是在指导老师的指点下，我先去图书馆找找相关的资料，用是碰钉子了， C语言这方面的书是少之又少，而且也 是盲目的在那翻阅，见与绘图有关的书都翻翻，还是没有头绪，最后借了本C语言精彩编程。接着我又借了一本C图象处理编程，只有这两本书的紧密结合才能编出我那程序。 首先我的想法是只在Borland C+这个环境下完成，先把头绪给理清一遍，从我这题目中可以看到，要编出来主要有两大步：二分法和跟踪箭头。这二分法查找要求被查找的数据是按照某种顺序排列的有序序列，因此应该
3、先将数据排序，再用二分法查找要查找的数据。二分法查找又称折半查找，是一种效率高的有序顺序表上的查找方法，下面讨论一下二分查找的实现方法： 设顺序表存储在一维数组S中，设置三个变量low,high和mid，它们分别指向当前查找范围的下界，上界和中间位置。初始化时，令low=0,high=n-1,设置待查找数据元素的关键字为key. (1) mid=low+high/2. (2) 比较Key与smid.key值的大小，若smid.key= Key，则查找成功，结束查找，若smid.keyKey，表明关键字为Key的记录可能在于记录smid的后半部分，修改查找范围，令下界指示变量low= mid+1
4、，上界指示变量high的值保持不变。若smid.keyKey，表明关键字为Key的记录只可能存在于smid的前半部，修改查找范围，令high = mid-1，变量low保持不变。 (3) 当前变量low与high的值，若low =high，重复执行第步和第步，若low high，表明整个表已经查找完毕，表中不村在关键字为的Key记录。 当然这里边也用到了冒泡排序法，所谓的冒泡排序就是指按增加或减少的顺序对一组类似的信息重新进行安排的过程。一般来说，当对信息进行排序时，只有信息中的某一小部分被用作排序的关键字，根据关键字对各元素进行比较。当必须要进行比较时，彼此交换的则是整个元素。 以上是对数据
5、的查找方法的分析，下面就具体说说跟踪箭头的问题： 对于这个箭头也就是光标了，这用到了C语言的图象处理，有对光标的控制程序和显示程序。光标的显示是动态图象，即一个移动的图象在屏幕上的运动，它到某处就遮盖掉部分背景，当再移到别处时原来被覆盖的内容应该被恢复，否则画面要被移动的图象所破坏。动态显示一般由下列4个步骤组成： 图符与背景的异或来实现。第1次异或显示光标，第2次异或恢复背景。16色图形显示中的光标通常采用次法，WINDOWS图形编程中还时常采用这种方法。 存储背景参数，恢复时再重新生成。文字画面或下拉式菜单等通常采用此法。DOS环境下的字处理软件常采用这种方法。 用存储背景图象像素数据的方
6、法来实现。用get_image子程序保存背景的图象数据，以后用put_image子程序恢复数据。复杂的图象画面通常采用的方法。 程序设计 本程序用到好几种数据类型，有整型，结构体，字符型 主函数的流程图如下： 开始 输入要从多少个数中查找 输入那些具体数据 输入要查找的那个数 调用排序函数bubblesort 调用那写生成箭头的函数settextstyle，inttoch等 调用二分法查找函数binarysearch 结束 这就是主函数的流程图。 调试分析 在运行过程中，就是刚开始接触Turboc的时候很不了解，因为这那环境下，鼠标不能用，只能用键盘操作。 编好的文件也不知道怎么在Turboc
7、下打开，摸索后才发现可以在load中打开，不过的先把文件放在Turboc文件下。 这也是调试时出现的错误，本以为程序应该没多大问题了，可出来五个错误，真让我束手无策，同样也是经过许久才找到问题所在，没改路径，所以有好多文件就找不找 。这就是那个没修改路径出来错误的界面。出现这些错误都是因为我对那个Turboc环境不熟悉。 在运行中也遇到问题，比如说，如果我查找的范围稍微大点，结果可能就看不到，因为设置的时候就出了点问题。这个问题后来也解决了，改进了一下程序，将运行的演示过程切换到另下一个屏幕，所以数据再多也可以显示。 使用方法 本程序是为了用二分法查找法的图形演示，可以有箭头跟踪指示出二分查找
8、过程中的位置。使用方法如下几步： 1 进入turboc或VC界面下，打开文件ERFENFA.C，在去OPTIONDIRECTION中修改路径。 2 CTRL+F9运行程序。 3 运行界面会提示：Please input the stall number:用户就可以输入你要从几个数中查找，但不超过二十个，输完敲回车。 4 运行界面会提示：Please input yours numbers:用户可以输入你那些数据，输完敲回车。 5 运行界面会提示：Please input the key number:用户应该输入你要查找的那个数，当然这个数必须是你上面数据中的一个，输完敲回车。 6 你就可以看
9、到查找的整个演示过程。 以上六步就是对本程序的使用步骤。 测试结果 1）测试数据 Please input the stall number(9)/计算整数的位数 i/=10; j+; i=x; *n=j;/返回整数的位数 chj+1=0;/在字符串数组末尾添加0，用于打印判断 do/整数转换为字符串，从低位开始 chj=i%10+48; i/=10; j-; while(i9); if(i0) chj=i+48; void draw(int x,int y)/画箭头函数，(x,y)为整数在屏幕上显示的坐标 moveto(x,y+25);/把光标移到这个坐标 lineto(x+5,y+14);
10、/从上面那个坐标到这个坐标画直线lineto(x+10,y+25);/从上面那个坐标到这个坐标画直线 moveto(x+5,y+14);/把光标移到这个坐标 lineto(x+5,y+29);/从上面那个坐标到这个坐标画直线 int binarysearch(seqlist s,int x)/二分查找 int low=0,high=s.size-1; int mid,col; col=getbkcolor;/获取屏幕背景颜色 while(low=high) mid=(low+high)/2; setcolor(4);/设置画笔颜色为红色 draw(s.datamid.dress0,s.data
11、mid.dress1);/开始画箭头 if(s.datamid.key=x) return 1; else if(s.datamid.keyx)high=mid-1; sleep(2);/暂停2秒 setcolor(col);/设置画笔颜色为背景色，也就是把先前的箭头变为背景色 draw(s.datamid.dress0,s.datamid.dress1);/开始画箭头 return -1; void bubblesort/冒泡排序，对顺序表排序 int i,j,flag=1; st temp; for(i=1;is.size&flag=1;i+) flag=0; for(j=0;js.dat
12、aj+1.key) flag=1; temp=s.dataj; s.dataj=s.dataj+1; s.dataj+1=temp; void main int i,j,temp2,n,m; int gd=DETECT,gm; initgraph(&gd,&gm,); printf(请输入你要输入数据的个数(20) printf(error!n); printf(请输入你要输入数据的个数(=20):); scanf(%d,&s.size); for(i=0;is.size;i+) printf(请输入第%d个数据:,i+1); scanf(%d,&s.datai.key); printf(请输
13、入要查找的数:); scanf(%d,&m); temp0=0; temp1=25; s.data0.dress0=temp0; s.data1.dress1=temp1; clrscr;/清楚屏幕上的字符 bubblesort; settextstyle(SMALL_FONT,HORIZ_DIR,6);/设置字符串的显示格式 for(j=0;js.size;j+) inttoch(s.dataj.key,&n); if(j600)/TC屏幕宽为600，超过要换行显示 s.dataj+1.dress0=0; s.dataj+1.dress1=s.dataj.dress1+40; temp1=s.dataj+1.dress1; temp0=s.dataj+1.dress0; i=binarysearch(s,m); if(i=1) outtextxy(10,temp1+100,congratulate succeed!); else outtextxy(10,temp1+100,lost!); getch; closegraph;
