兰州理工大学数据结构课程设计-猴子吃桃子问题； 跳马问题；通过单字符置换可以将一个单词改为另一个单词.pdf

实践教学兰州理工大学计算机与通信学院2014年秋季学期数据结构课程设计题 目：猴子吃桃子问题；跳马问题；通过单字符置换可以将一个 单词改为另一个单词专业班级：12级信息与计算科学（2）班姓 名：_学 号：12540236指导教师：_成 绩：_目录摘要.1一.猴子吃桃问题.21.采用类语言定义相关的数据类型.22.算法设计.23.调试分析.34.测试结果.45.源程序（带注释）.6二.跳马问题.101.采用类语言定义相关的数据类型.102.算法设计.103.调试分析.114.测试结果.115.源程序（带注释）.13三.通过单字符置换可以将一个单词改为另一个单词.161.采用类语言定义相关的数据类型.162.算法设计.163.调试分析.184.测试结果.185.源程序（带注释）.19总结.23参考文献.24致谢.25摘要本程序主要主要解决猴子吃桃问题，跳马问题，通过单字符置换可以将一个 单词改为另一个单词。猴子吃桃问题是分别采用数组数据结构，链式数据结构以 及递归方法根据猴子每天吃的桃子数来求解一群猴子摘的桃子数。跳马问题也称 为骑士周游问题，是算法的设计中的经典问题。如果有这样一种走法，则称所走 的这条线为马的周游路线。在8*8的方格棋盘中马的行走规则从棋盘的某一方格 出发，开始在棋盘上周游，如果能不重复地走遍棋盘上的每一个方格，这样的一 条周游路线在数学上被称为国际象棋棋盘上马的哈密尔顿链。通过单字符置换可 以将一个单词改为另一个单词是假设存在一个5字母单词的字典，给出一个算法 确定单词A是否可以通过一系列的单字符置换转换为单词B,并且如果可以的话,输出相应的单词序列。正如bleed通过序列bleed、blend、blond、blood转换为bloodo 这些程序主要功能是加深我们对算法与数据结构中存储，线性表和栈的理解。让 我们对算法与数据结构有个更深刻的认识。关键词：猴子吃桃；跳马；字符转换；数据结构第1页共25页一.猴子吃桃问题有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到 了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃 子。要求：1）采用数组数据结构实现上述求解；2）采用链式数据结构实现上述求 解；3）采用递归实现上述求解。1.采用类语言定义相关的数据类型typedef struct Node（int i;intk;数据域struct Node*next;/指针域 Node,*PNode;定义一个指针用于链表求解2.算法设计1.一维数组解决。建立一个一维数组a10从第九天开始算起令a9=l利用for循环计算前八 天猴子吃的桃子数目并同时将后一天吃的桃子数赋值到前一天。最后即可得出猴 子一共吃的桃子数。2.递归函数解决：定义一个整形函数DiGui使用if函数控制是否调用函数本身。桃子数等与一 这说明第九天吃了一个桃子函数便可以结束。如果桃子数不为一则一直调用函数 本身知道调用结束。3链式数据结构解决：定义头指针PL P2指针指向头结点。P2指针负责传值进行循环。利用for函 数进行循环。并将后一天的之赋值给前一天。最后便可得到猴子吃的总的桃子数。主函数控制各子函数的调用流程如图1T所示第2页共25页开始图IT主控制程序流程图3.调试分析a、调试中遇到的问题及对问题的解决方法；根据第十天所剩桃子个数，采用倒推方法，递归的求出第九天，第八天，第七 天.直到算出刚开始猴子拥有桃子的总数。解决方法主要是用递归算法采用数组存储方法。b、算法的时间复杂度和空间复杂度。通过1、2、3数字键选择计算方法时间复杂度为0(n),空间复杂度为0(1)第3页共25页4.测试结果1）执行程序进入主菜单，如图1T所示图1-2主菜单2）输入1用数组方法求解，如图1-2所示图1-3数组求解第4页共25页3）输入2用链表求解，如图1-3所示图1-4链表求解4）输入3用递归方法求解，如图4所示图1-5递归求解第5页共25页5）输入4退出程序，如图1-5所示图1-6退出界面5.源程序(带注释)#include#includetypedef struct Nodeint i;int k;/数据域struct Node*next;/指针域)Node,*PNode;定义一个指针用于链表求解 int ShuZu。/数组求解(int i,a10;a9=l;for(i=8;i=0;i-)ai=(ai+l+l)*2;第6页共25页return a0;int DiGui(int i,int j,int k)递归求解(if(j=i)return k;k=(k+l)*2;DiGui(i,j-l,k);)int LianBiao。/链表求解(int i;PNode pl,p2;if(p 1=(PNode)malloc(sizeof(Node)=NULL)生成新的结点 printf(分配内存失败!)exit(O);)pl-i=10;pl-k=l;pl-next=NULL;for(i=9;i0;i-)if(p2=(PNode)malloc(sizeof(Node)=NULL)printf(分配内存失败!)exit(O);)p2-i=9;p2-k=(pl-k+l)*2;p2-next=NULL;free(pl);pl=p2;第7页共25页return pl-k;int main。/主函数 char n;int i,j,k;i=ShuZu();DiGui(l,10,l);k=LianBiao();for(;)printf(t*欢迎进入猴子吃桃问题*n printf(t*1 数组方法*w”)printf(t*2 链表方法*q”)printf(t*3 递归方法*q”)printf(t*4 退 出*4)printf(t 输入选项(1 4):);scanf(%s,&n);switch(n)case T:printf(n);printf(tttt数组方法得出的总桃子数为：%dn,i);printf(n);printf(tttt*如需继续进入主菜单请按回车键*n);break;case 2:printf(n);printf(tttt链表方法得出的总桃子数为：%dn,k);第8页共25页printf(n);printf(tttt*如需继续进入主菜单请按回车键*n);break;case 3:printf(n);printf(tttt递归方法得出的总桃子数为：%dn,j);printf(n);primf(tttt*如需继续进入主菜单请按回车键*n)；break;case 4:printf(n);printf(谢谢使用本系统人0);exit(O);break;default:printf(n);printf(n请键入一个正确的选择)printf(n);printf(tttt*如需继续进入主菜单请按回车键*n);break;getchar();getchar();system(cls);)第9页共25页二.跳马问题要求在64个国际象棋格子,任意位置放一个马,如何不重复地把格子走完。1.采用类语言定义相关的数据类型include typedef struct DataTypeint board8 8;/定义一个 int 的二位数组 boardint step;/*走的步数*/int test;/*可以遍历成功的次数*/SeqList;SeqList L;int start;int del tar=-2,-1,1,2,2,1,-1,-2;int deltac=1,2,2,1,-1,-2,-2,T;/*马的可能走法对当前位置的 横纵增量*/2.算法设计该问题分为两步首先 在8*8的棋盘上的任意一 个位置上放一个马（r,c）,求马所在位置的出口数。其次选择出口最少的那个 位置。函数执行流程图如图2-1所示图2 T函数执行流程图第10页共25页3.调试分析a、调试中遇到的问题及对问题的解决方法对于跳马问题，一般情况下，可以采用回溯法找解，但对于该问题来说，只 要找到一种解法即可。然而，在写该问题的程序时，有时得到的不止一种，这就 和“贪婪法”的思想相悖，在经过反复的思考和查阅资料之后，才明白须将if(step64)放在dowhile(step=64)循环语句之外，才能达到用贪婪法”解 决该问题的目的。b、算法的时间复杂度和空间复杂度时间复杂度的计算是按照运算次数来进行的，关于空间复杂度的计算是在程 序运行过程所要借助的内容空间大小。时间复杂度：。(/)；空间复杂度：0(n)04.测试结果1)进入主界面 如图2 T所示图2-2主界面第11页共25页2）输入初始的行列，结果如图2-2所示图2-3输入初始数据图3）重新设置初始行列5 6如图2-3所示图2-4重新设置初始数据图第12页共25页5.源程序(带注释)#include typedef struct DataType(int board88;定义一个 int 的二位数组 boardint step;/*走的步数*/int test;/*可以遍历成功的次数*/JSeqList;SeqList L;/int board8J8J;int start;int deltar=-2,-1,1,2,2,1,-1,-2);int deltac=1,2,2,1,-1,-2,2-1；/*马的可能走法对当前位置的横纵增量*/int exitn(int r,int c,int nexta)/*求马所在位置(r,c)的出U数,nexta为出口号*/int i,k,a,b;int num=0;for(i=0;i=7;i+)(k=(i+start)%8;a=r+deltark;b=c+deltack;if(a=0&b=0&b=7&L.boardab=0)(nextanum=k;num+4-;)return num;)int number(int r,int c)/*返回下次可以找到的增量的个数*/int i,k,a,b;int num=0;for(i=0;i=7;i+)(k=(i+start)%8;a=r+deltark;b=c+deltack;if(a=0&b=0&b=7&L.boardab=0)num+;第13页共25页return num;int next(int r,int c)/*选择下一个出口*/int nexta8,num,numl=0,min,i,k;/*min 用来确定最少出口数*/min=9;num=exitn(r,c,nexta);/*num 为(r,c)的出 口 个数*/if(num=0)(return-1;/*没有出 口*/)for(i=0;i=num-l;i+)/*找出口最少的点*/numl=number(r+deltarnextaij,c+deltacnextai|);if(numl=min)min=numl;k=nextai;)return k;/*返HI出口最少的点*/)int main()(int ber,bee;/*用于保存输入初始的行列*/int r,c;int i,j,k;printf(Enter the first node:(ber bec)/n);while(scanf(%d%d,&ber,&bec)!=-1)接收起点(start=0;L.test=1;while(start=7)/*进行测试的次数*/(do(for(i=0;i=7;i+)for。=0;j=7;j+)L.boardij=0；/*初始化 board 数组*/第14页共25页r=ber;/*将当前值赋给r*/c=bee;/*将当前值赋给c*/L.boardrc=1;/*将初始位置赋值为1*/for(L.step=2;L.step=64;L.step+)(if(k=next(r,c)=-1)/*此路不通*/(start+;break;/*进行下一次测试*/)r+=deltark;c+=deltack;L.board r c=L.step;while(L.step 64)/*如果步数大于棋盘的格子数，则表明遍历成功*/(printf(方案%d:n,L.test+);for(i=0;i=7;i+)/*打印出该方案*/for。=0;j=7;j+)(printf(%4d,L.boardij);printf(nn);)start+break;/end if/end while(start blond blood 转换为 blood。1.采用类语言定义相关的数据类型#define LEN 6define LINE 23ttdefine MAXVALUE 100typedef struct DataType(int graph LINE LINE;定义一个 int 的二位数组 graphint aLINELINE;int pathLINELINE;SeqList;char dieLINELEN=bland,blank,bleak,bleed,blend”,blind,blink,blond,blood,bloom,blown,blows,brand,brank,bread,break,bream,breed,brown,clank,clink,dread,dream;定义一个由5个字母组成的字典bool edge_test(char source,char target);2.算法设计最初简单的想法是，对于第一个给定的单词，将其中的任意字母替换，循环 查找是否可以变换为另一个单词，但仔细思考发现，事实上这种方法是很难到达 循环结束终点的，因为其中的变换步骤是不定的，也就是说单词可以通过有限步 变到另一个单词，只要存在变换，这种方法就是可行解。于是想到将任意单词抽象为节点，任意两个单词之间可以通过变换一个字母 到达的变换可以抽象为图中两个节点是相连通的，而不能仅通过替换一个字母变 换就到达终点的两个节点之间是不连通的，问题变为如果任意两个单词之间存在 可行解，意味着图中两个单词是连通的。我们发现，寻找两个节点的通路就能找 到一种解法。所以可以查找图中两个节点之间的最短路径，用Floyd算法进行求解，Floyd 第16页共25页算法直接给出了所有节点之间的最短路径。若不存在路径的情况，即两个节点之 间没有可达的路径，则这两个节点必定存在不同的连通分支中，意味着字典中的 词是存在着至少两个连通分支的。Floyd算法流程图如图3-1所示图3-1 Floyd算法执行流程图第17页共25页3.调试分析a、调试中遇到的问题及对问题的解决方法调试过程出现了 edge_test没定义的问题，解决办法是在最前面加上 bool edge_test(char source,char target);b、算法的时间复杂度和空间复杂度该算法的复杂度为0(r?)；空间复杂度为0(n)4.测试结果1)执行程序进入主界面，如图3-1所示 C:UsersAdministratorDe51dop儆据结构课程设计字符置涣Debuglcyzifuzhihuan.exe o j 回图3-1主界面第18页共25页2）输入bleed blood,输出结果如图3-2所示3-2结果输出5.源程序(带注释)#include#includedefine LEN 6#define LINE 23#define MAXVALUE 100typedef struct DataType(int graphLINELINE;/定义一个 int 的二位数组 graphint aLLINEJLLINEJ;int pathLINELINEJ;SeqList;char dicLINELEN=bland,blank,bleak,bleed,blend,blind,blink,blond,blood,bloom,blown,blows,brand,brank,bread,break,bream,breed,brown,clank,clink,dread,dream);定义一个由5个字母组成的字典bool edge_test(char source,char targetJ);int main()第19页共25页给graph川赋初值SeqList L;for(int i=0;i LINE;i+)for(intj=0;j LINE;j+)if(true=edge_test(dicij,dicj)L.graphij=1;)else if(i!=j)L.graphij=MAXVALUE;else L.graphi|jJ=0;/Floyd算法求最短路径int j,k,n=LINE;for(i=0;i n;i+)for(j=0;j n;j+)L.aij=L.graph皿；if(i!=j&L.aij M AX VALUE)L.pathij=i;)elseL.pathiJj=0;for(k=0;k n;k+)for(i=0;i n;i+)for(j=0;j n;j+)if(L.aik+L.akjL.aij)L.aij=L.aik+L.akj;L.pathi|j=L.pathk|j;char source LIN EJ,target LLLN EJ;printff请输入要被转换的字符:n);scanf(%s,source);printf(请输入转换得到的字符:n);scanf(%s,target);int indexs=-1;第20页共25页int indext=-1;for(i=0;i,dicindextj);printf(%sn,dicindexs);)else if(indexs=L.pathindexsjxj)printf(%s-,dicindext);printf(%s-,dicx);printf(%sn,dicindexsj);elsewhile(true)if(indexs!=L.pathindexsx)int y=L.pathindexsx;if(x=y)printf(不存在变换系列n);exist=false;break;)elseif(!exist)printf(%s-,dicindext);printf(%sdicx);exist=true;x=y；第21页共25页else exist=true;break;)if(exist)printf(%s-,dicx);if(exist)printf(%sn,dicindexs);return 0;bool edge_test(char source,char target)(int tagLEN-l;for(int i=0;iLEN-l;i+)if(sourceij!=targetij)tagi=1；)elsetagi=0;int sum=0;for(i=0;iLEN-l;i+)sum+=tagi;if(sum=1)return true;)else return false;第22页共25页总结数据结构是计算机程序设计的重要理论技术基础，它是计算机科学的核心课 程。随着高级语言的发展，数据结构在计算机的研究和应用中已展现出强大的生 命力，它兼顾了诸多高级语言的特点，是一种典型的结构化程序设计语言，它处 理能力强，使用灵活方便，应用面广，具有良好的可移植性。两周紧张的课设就这样结束了，通过这两周的实践学习，不仅使我们巩固了 以前的知识并在此基础上还对数据结构的特点和算法有了更深的了解，使我们在 这门课程的实际应用上也有了一个提高。首先这两周的学习，使我们在巩固了原有的理论知识上，又培养了灵活运用 和组合集成所学过知识及技能来分析、解决实际问题的能力，使我们体会到自身 知识和能力在实际中的应用和发挥。总之，两个礼拜的课程设计让我们受益匪浅。我们深深认识到，要学好一门 学科，没有刻苦钻研的精神是不行的，只有在不断的尝试中，经历失败，从失败 中总结经验，然后再不断的尝试，才能获得成功。通过这次课程设计，我对C语言的掌握提高到了一个新的水平，能够利用C 语言编写出一个实用的程序，很大程度提高了程序综合设计能力、分析能力和编 程能力。掌握了很多新的编程技巧，积累了一些编程经验。我还学到了编程的思 想，这对于以后的学习以至到以后的工作中都是很有用的。第23页共25页 第24页共25页Edition北京：电子工业.2001PracticalIntroductiontoDataStructuresandAlgorithmAnalysisJava5CliffordA.Shaffer.张铭，刘晓丹译.数据结构与算法分析（Java版）,A4谭浩强.c语言程序设计M.北京：清华大学.2 005.学.（影印版）.20053 WilliamFord,WilliamTopp.DATASTRUCTUREWITHC+.北京：清华大2 严蔚敏，吴伟民.数据结构题集（C语言版）血.北京：清华大学.2 0031严蔚敏，吴伟民.数据结构（C语言版）M.北京：清华大学.2 003参考文献致谢在这次课程设计的过程中，我得到了许多人的帮助。首先，我要感谢我的老 师在课程设计上给予我的指导，提供给我的帮助，这是我能顺利完成这次报告的 主要原因，更重要的是老师帮我解决了许多技术上的难题，让我能把系统做得更 加完善。在此期间，我不仅学到了许多新的知识，而且也开阔了视野，提高了自 己的设计能力。其次，我要感谢帮助过我的同学，他们也为我解决了不少我不太 明白的设计商的难题。再多华丽的言语也显苍白。在此，谨向老师致以诚挚的谢 意和崇高的敬意。同时感谢学校给我们提供了必要的实验器材，提供了很大的方 便。最后，感谢老师能在百忙之中对我的论文进行审察，由于本人知识有限，不 足之处在所难免，还请老师指正。第25页共25页