数据结构与算法课程设计说明书-用递归实现Koch雪花变换

PAGE课程设计说明书课程名称：数据结构与算法设计题目：koch递归雪花院系：计算机科学与信息工程学院课程设计任务书设计题目Koch递归雪花学生姓名所在院系计算机科学与信息工程系专业、年级、班软件工程<1>班设计要求：用递归算法实现Koch雪花。(1)根据程序要求制定相应头文件(2)构造心中图形，设计出相应算法(3)编写相应的代码，查缺补漏学生应完成的工作：(1)根据课程设计要求，分析思路并构建模型，划分子模块、完善其功能；(2)根据各模块的功能设计并编写程序段、连接各程序段使之形成一个有机的整体；(3)调试、运行程序进而得到正确的结果；(4)根据实验设计运行过程，写出实验论文并总结实验教训。参考文献阅读：(1)C语言程序设计（潭浩强第二版，清华大学出版社）；(2)数据结构（吴伟民等C语言版，清华大学出版社）；(3)数据结构实验教程（高晓兵等，清华大学出版社）；(4)算法分析与设计（郑宗汉、郑晓明，清华大学出版社）。工作计划：(1)第一周的第一天：布置设计题目；说明进度安排。(2)第一周的第二天：审题，查阅资料，进行设计前的必要资料准备。(3)第一周的第三天、第四天、第五天：程序编写、上机调试(4)第二周的第一天至第三天：上机调试程序、结果分析。(5)第二周的第四天：撰写设计报告。(6)第二周的第五天：设计答辩。任务下达日期：2015年6月14日任务完成日期：2015年6月28日指导教师（签名）：学生（签名）：邹鑫用递归实现Koch雪花变换摘要：随着信息技术的发展，关于各种程序中的数据结构也是层出不穷，对于项目某一方面计算或者是某一方面的研究，出现了专门的数据结构算法，递归就是其中之一，递归作为数据结构中算法的精华，其作用使得数据结构在算法中有着不可取代的作用，在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。关键字：数据结构；递归；雪花算法；算法表目录1.设计背景 11.1递归的广泛应用 11.2递归的需求 12.设计方案 12.1总体设计流程 12.2Koch雪花的模块化 23.方案实施 23.1递归算法 23.2具体步骤 24.结果与结论 34.1结果分析 34.2程序运行结果 34.3课程设计总结 55.收获与致谢 66.参考文献 67.附件 61.设计背景1.1递归的广泛应用递归算法一般用于解决三类问题：(1)数据的定义是按递归定义的。（Fibonacci函数）(2)问题解法按递归算法实现。这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi问题。(3)数据的结构形式是按递归定义的。如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述。1.2递归的需求递归函数在数值计算、数据结构、人工智能及各种事务处理过程中有着广泛的应用。递归算法不但编程简洁明了,且在有些问题的处理上具有独特的效果和难以取代的位置。但递归概念比较抽象,对于深入理解和灵活应用递归函数并非易事,在具体应用中有时会无从下手或找不到合适的递归函数模型。2.设计方案2.1总体设计流程1.建立Koch雪花系统（1）递归算法；（2）建立正文的编码文件。（3）实现代码文件的译码2.2Koch雪花的模块化1.程序用到的抽象数据类型的定义；2.定义递归函数；3.系统子程序及功能；4.代码文件的译码。3.方案实施3.1递归算法递归算法基本思想：递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。递归算法解决问题的特点：(1)递归就是在过程或函数里调用自身。(2)在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。(3)递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。(4)在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。3.2具体步骤(1)建立平面二维坐标系，原点位于屏幕客户区中心，x轴水平向右为正，y轴垂直向上为正。(2)以原点为圆心绘制半径为r的圆,与y轴交于点.从点开始,顺时针方向将圆三等分,得到和点。构成等边三角形。(3)沿着等边三角形的三边外侧分别绘制三段递归深度为4，夹角为60度的Koch曲线，形成Koch雪花。(4)设置背景色为黑色，Koch雪花为白色，代表雪花中心点的十字线为蓝色绘制。(5)设置旋转角RotateAngle，起始角为0度，SetTimer()函数每隔五十秒调用一次OnTimer()函数，在OnTimer()函数中RotateAngle以10度步长增长，使Koch雪花围绕坐标系原点按顺时针旋转。4.结果与结论4.1结果分析以中心位于屏幕客户区中心的正三角形为基，沿每条边外侧绘制分段Koch曲线，形成Koch雪花。使用双缓冲机制绘制Koch雪花动态图形，使用定时器控制Koch雪花的旋转。Koch曲线生成规则如下：取一段长度为L的起点为A，终点为B的直线段，将其三等份，等分点为C和E。保留两端的线段，将中间一段CE改换成夹角为θ的两个长度为L/3的直线段CD和DE。然后再对图中的每一小段都按上述方式处理，得到不同深度的Koch曲线。Koch曲线的变换规则是将每一条直线段用一条折线替代，称为该分形的生成元，分形的基本特性完全由生成元决定，就可以生成各种各样的分形图形。4.2程序运行结果4.4课程设计总结通过做这个课程设计，使我对递归有了更多的理解。同时让我对结构的使用也更了解。进过老师的几次讲解和帮助，是我最终完成了这个程序。在写详细设计中，我又发现了不少细节问题。这说明我的程序还有不少可以改进的地方。而且我这程序没有用到文件流，使的信息无法保存以用作下一次的查找。这是下个主要改进的地方。还有如何更高效、更省时是改进的目标。5.收获与致谢总的来说,在整个设计的过程中,对文件的知识有了相当程度的了解掌握,基本上学会了对文件的设计和对文件的操作等。在对文件的自学过程中也认识，在学习的过程中要灵活的把所学的知识运用到实践当中，并且还要巩固练习和运用，这样才可以牢牢的记住。试验也对数据结构的知识进行了复习，尤其是递归等知识点，在对程序不断的修改和逐步改进提升的过程中，积累了不少经验，为在以后的学习和实践应用奠定了一定的基础。这次课程设计受益非浅，学到了不少知识，同时也认识到自身的不足，需要加强自身训练，学以致用，学会自我总结，吸取教训，积累经验，在学习和实践中来不断的提升自己。6.参考文献[1]C语言程序设计（潭浩强第二版，清华大学出版社）；[2]数据结构（吴伟民等c语言版，清华大学出版社）；[3]数据结构实验教程（高晓兵等，清华大学出版社）；[4]算法分析与设计（郑宗汉、郑晓明，清华大学出版社）。7.附件附源程序清单电子档一份Application.h#include<windows.h>#include<GL/gl.h>#include<GL/GLU.h>#pragmacomment(lib,"opengl32.lib")#pragmacomment(lib,"glu32.lib")LRESULTCALLBACKwndProc(HWNDhWnd,UINTmsg,WPARAMwParam,LPARAMlParam);voidshowMessage(constchar*msg);intrun();voidinit();voidupdateFrame();voidrender();boolcreateWindow(HINSTANCEinst);voidinitRenderContext();voidfinalRenderContext();Application.cpp#include"Application.h"#include"resource.h"HWNDhWnd;HDChDC;HGLRChRC;LPCSTRWINDOW_CLASS_NAME="KochSnowflakeWindow";LPCSTRWINDOW_TITLE="Koch雪花";voidrenderSence();voidonMouseMove(doublex,doubley);intWINAPIWinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow){ createWindow(hInstance); intexitCode; exitCode=run(); returnexitCode;}voidrender(){ glClear(GL_COLOR_BUFFER_BIT); renderSence(); SwapBuffers(hDC);}voidresize(GLsizeiwidth,GLsizeiheight){ height=height==0?1:height; glViewport(0,0,width,height); glMatrixMode(GL_PROJECTION); glLoadIdentity(); doublex1,y1; if(width>=height){ x1=(double)width/height; y1=1.0; } else{ x1=1.0; y1=(double)height/width; } gluOrtho2D(-x1,x1,-y1,y1); glMatrixMode(GL_MODELVIEW); glLoadIdentity();}LRESULTCALLBACKwndProc(HWNDhWnd,UINTmsg,WPARAMwParam,LPARAMlParam){ switch(msg){ caseWM_CREATE: returnDefWindowProc(hWnd,msg,wParam,lParam); caseWM_CLOSE: PostQuitMessage(0); break; caseWM_PAINT: render(); returnDefWindowProc(hWnd,msg,wParam,lParam); caseWM_SIZE: resize(LOWORD(lParam),HIWORD(lParam)); break; caseWM_MOUSEMOVE: { RECTrc; GetClientRect(hWnd,&rc); doublew=rc.right-rc.left; doubleh=rc.bottom-rc.top; doublex=((double)LOWORD(lParam))*2/w-1.0; doubley=((double)HIWORD(lParam))*2/h-1.0; onMouseMove(x,y); } break; default: returnDefWindowProc(hWnd,msg,wParam,lParam); } return0;}voidshowMessage(constchar*msg){ MessageBox(NULL,msg,"Message",MB_OK|MB_ICONINFORMATION);}boolcreateWindow(HINSTANCEinst){ WNDCLASSwc; DWORDstyle,exStyle; ZeroMemory(&wc,sizeof(wc)); wc.style=CS_HREDRAW|CS_VREDRAW|CS_OWNDC; wc.lpfnWndProc=wndProc; wc.hInstance=inst; wc.hIcon=LoadIcon(inst,MAKEINTRESOURCE(IDI_APP)); wc.hCursor=LoadCursor(NULL,IDC_ARROW); wc.lpszClassName=WINDOW_CLASS_NAME; if(!RegisterClass(&wc)){ showMessage("Registerclassfail!"); returnfalse; } RECTwinRect={0,0,640,480},areaRect; style=WS_OVERLAPPEDWINDOW; exStyle=WS_EX_APPWINDOW|WS_EX_WINDOWEDGE; AdjustWindowRectEx(&winRect,style,FALSE,exStyle); SystemParametersInfo(SPI_GETWORKAREA,NULL,&areaRect,NULL); hWnd=CreateWindowEx(exStyle,WINDOW_CLASS_NAME,WINDOW_TITLE, style|WS_CLIPSIBLINGS|WS_CLIPCHILDREN, (areaRect.right-winRect.right)/2,(areaRect.bottom-winRect.bottom)/2, winRect.right-winRect.left,winRect.bottom-winRect.top, NULL,NULL,inst,NULL); if(!hWnd){ showMessage("Createwindowfail!"); returnfalse; } initRenderContext(); ShowWindow(hWnd,SW_SHOW); returntrue;}voidinitRenderContext(){ hDC=GetDC(hWnd); PIXELFORMATDESCRIPTORpfd; intfmt; ZeroMemory(&pfd,sizeof(pfd)); pfd.nSize=sizeof(pfd); pfd.nVersion=1; pfd.dwFlags=PFD_DRAW_TO_WINDOW|PFD_SUPPORT_OPENGL|PFD_DOUBLEBUFFER; pfd.iPixelType=PFD_TYPE_RGBA; pfd.cColorBits=32; pfd.iLayerType=PFD_MAIN_PLANE; fmt=ChoosePixelFormat(hDC,&pfd); SetPixelFormat(hDC,fmt,&pfd); hRC=wglCreateContext(hDC); if(!hRC){ showMessage("CreateContextfail!"); } else{ wglMakeCurrent(hDC,hRC); } glShadeModel(GL_SMOOTH); glEnable(GL_LINE_SMOOTH); glEnable(GL_BLEND); glBlendFunc(GL_SRC_ALPHA,GL_ONE_MINUS_SRC_ALPHA); glClearColor(0.06f,0.19f,0.34f,1.0f); glClearDepth(1.0f); glHint(GL_LINE_SMOOTH_HINT,GL_NICEST); }voidfinalRenderContext(){ wglMakeCurrent(NULL,NULL); wglDeleteContext(hRC); ReleaseDC(hWnd,hDC);}intrun(){ MSGmsg; boolrunning=true; while(running){ if(PeekMessage(&msg,NULL,0,0,PM_REMOVE)){ if(msg.message==WM_QUIT){ running=false; } else{ TranslateMessage(&msg); DispatchMessage(&msg); } } else{ Sleep(1); } } finalRenderContext(); return(int)msg.wParam;}resource.h//{{NO_DEPENDENCIES}}//MicrosoftVisualC++generatedincludefile.//UsedbyKochSnowflake.rc//#defineIDI_ICON1101#defineIDI_APP101//Nextdefaultvaluesfornewobjects//#ifdefAPSTUDIO_INVOKED#ifndefAPSTUDIO_READONLY_SYMBOLS#define_APS_NEXT_RESOURCE_VALUE102#define_APS_NEXT_COMMAND_VALUE40001#define_APS_NEXT_CONTROL_VALUE1001#define_APS_NEXT_SYMED_VALUE101#endif#endifdrawing.cpp#include"Application.h"#include<math.h>constdoublepi=3.1415926536;voidrender();voidkochCurve(doublex0,doubley0,doubleangle,doublelength,intn,doublealpha);doubletheta=pi/3;intiterNum=5;voidbranchCurve(doubledirect,doublex0,doubley0,doubleangle,doublelength,intn,doublealpha){ length=length/cos(theta)/2; angle+=direct*theta; kochCurve(x0,y0,angle,length,n,alpha); x0+=length*cos(angle); y0+=length*sin(angle); angle-=direct*theta*2; kochCurve(x0,y0,angle,length,n,alpha);}voidkochCurve(doublex0,doubley0,doubleangle,doublelength,intn,doublealpha){ glColor4d(1.0,1.0,1.0,alpha); if(n==0){ doublex1=x0+length*cos(angle); doubley1=y0+length*sin(angle); glBegin(GL_LINES); glVertex2d(x0,y0); glVertex2d(x1,y1); glEnd(); } else{ length=length/3; n--; kochCurve(x0,y0,angle,length,n,alpha); x0+=length*cos(angle); y0+=length*sin(angle); branchCurve(1,x0,y0,angle,length,n,alpha); branchCurve(-1,x0,y0,angle,length,n,alpha/2.5); x0+=length*cos(angle); y0+=length*sin(angle); kochCurve(x0,y0,angle,length,n,alpha); }}voidonMouseMove(doublex,doubley){ x=x*3/2; if(x>1.0)x=1.0; if(x<-1.05)x=-1