2014年算法与数据结构说明书-211.

1、*实践教学*兰州理工大学计算机与通信学院2014年春季学期算法与数据结构课程设计2.递归替换3跳马问题4.长整数的运算专业班级：姓 名：学 号：指导教师：成 绩：摘要1刖言2正文31. 采用类C语言定义相关的数据类型 32. 各模块的伪码算法43. 函数的调用关系图114. 调试分析.11.5. 测试结果错误！未定义书签。6. 源程序（带注释）16总结29参考文献30致谢31附件I基本算法实现 32这次的课程设计是排序算法比较问题，递归替换问题，跳马问题和长整数运算 问题。其中排列算法中我只用到了三种排序方法，分别为冒泡，插入，选择。而递归 替换我选择了这学期所学的汉诺塔。跳马问题则是在书籍上

2、看到，加深其理解 并实现程序。长整数则是求助老师，贴吧上的人。我对自己的课程设计有着较 深的理解，前三种基本都是递归算法和回溯算法的体现，然而长整数却是用到 了结构体和链表。其中长整数难度较高，其理解较难，花了我相当长的时间。关键字：数组，结构体，结构体指针，双向循环链表，前向指针，后向指针,头指针，数字字符,十进制数，动态分配存储空间课程设计是我们学习过程中一个非常重要的环节，它重在测试大家实践能力，知 识应用能力和解决问题的能力同时它又需要以扎实的理论知识为基础在做课程设计时我们大家必须具备基本的程序设计知识，在平时的学习过程中多上机实习,试着用自己的思路去编程，调试及运行,在这过程中不断

3、地积累经验，这 样在做课程设计时就会比较得心应手.我在做此课程设计时花的时间比较长，但我自己认为这最大的可取之处在于我 并没有用大多数的时间去编写源代码，而是用在如何构思上面，在经过深思熟虑之 后再动手写源代码因此整个课程设计进行得比较顺利，几乎没有出现”反工”的情况. 但是其中也出现了一些解决不了的问题，具体见正文.同时我感触很深的一点是在编写代码时必须有一定的方法，这就涉及到计算机 科学与技术这门学科所提到的方法论，其中很多的方法都具有很高的参考价值1. 采用类c语言定义相关的数据类型1. 一维数组 array5=3,1,2,5,4;2. 参数盘子个数n,塔a, b, c3. 维数组横格

4、Movel8=-2,-1,1,2,2,1,-1,-2;纵格 Movev8=1,2,2,1,-1,-2,-2,-1;和二维数组 int A88;4. 长整数的运算上述程序设计思想主要用到的数据结构是结构体和双向循环链表struct DuLNode /双向循环链表的结点；int data;struct DuLNode *prior;struct DuLNode *n ext;2. 各模块的伪码算法1. 排序算法比较问题：统一用三角替换方法void swap(i nt array,i nt i,i nt j)int tmp=arrayi;arrayi=arrayj;arrayj=tmp;插入算法：v

5、oid InsertSort(int array,int n)for(i nt i=1;iO；j-)if(arrayjarrayj-1) swap(array,j,j-1);elsebreak;冒泡算法：void BubbleSort(int array,int n)for(i nt i=0;ii;j-)if(arrayjarrayj-1)swap(array,j,j-1);选择算法： void Selectio nSort(i nt array,i nt n) for(i nt i=0;i n-1;i+)int smallest=i;for(i nt j=i+1;j arrayj) smal

6、lest=j;swap(array,i,smallest);2汉诺塔：递归部分void move(i nt n, char a,char b,char c)if(n=1)prin tf(t%c-%cn,a,c);elsemove( n-1,a,c,b);prin tf(t%c-%cn,a,c);move( n-1,b,a,c);3.跳马问题：开始马的遍历for(i nt t=2;t=0&I1=0&v1=0&I2=0&v2=d)b=d;s=p;if（bc a-bg a-c b-aPress bny kev to cone inue图3运算结果跳马问题：输入马在棋盘的位置图4输入方位查看其结果图5

7、查看结果长整数运算程序初始测试结果:图1-长整数相加图1-36.源程序（带注释）排序比较：#i nclude using n amespace std;/*交换函数，作用是交换数组中的两个元素的位置*/void swap(i nt array,i nt i,i nt j)int tmp=arrayi;arrayi=arrayj;arrayj=tmp;/*冒泡排序*/void BubbleSort(i nt array,i nt n)for(i nt i=0;ii;j-)if(arrayjarrayj-1) swap(array,j,j-1);int mai n()int array5=3,1,

8、2,5,4;BubbleSort(array,5);for(i nt i=0;i5;i+)coutarrayi;coute ndl;return 0;# in clude# in clude# in cludestruct DuLNode 双向循环链表的结点int data;struct DuLNode *prior;struct DuLNode *n ext;；#i nclude using n amespace std;/*交换函数，作用是交换数组中的两个元素的位置*/void swap(i nt array,i nt i,i nt j)int tmp=arrayi;arrayi=arra

9、yj;arrayj=tmp;/*选择排序*/void Selecti on Sort(i nt array,i nt n)for(i nt i=0;i n-1;i+)int smallest=i;for(i nt j=i+1;j arrayj)smallest=j;swap(array,i,smallest);int mai n()int array5=3,1,2,5,4;Selecti on Sort(array,5);for(i nt i=0;i5;i+)coutarrayi;coute ndl;return 0;#i nclude using n amespace std;/*交换函数，

10、作用是交换数组中的两个元素的位置*/void swap(i nt array,i nt i,i nt j)int tmp=arrayi;arrayi=arrayj;arrayj=tmp;/*选择排序*/void Selecti on Sort(i nt array,i nt n)for(i nt i=0;i n-1;i+)int smallest=i;for(i nt j=i+1;j arrayj)smallest=j; swap(array,i,smallest);int mai n()int array5=3,1,2,5,4;Selecti on Sort(array,5); for(i

11、nt i=0;i5;i+) coutarrayi;coute ndl;return 0;汉诺塔：#in clude void move(i nt n, char a,char b,char c)if(n=1)printf(t%c-%cn,a,c);/当n只有1个的时候直接从a移动到celse/第n-1个要从a通过c移动到bn-1个移动过来之后b变开始盘，b通过amove( n-1,a,c,b);prin tf(t%c-%cn,a,c);move( n-1,b,a,c);移动到c mai n()int n;printf(请输入要移动的块数：);sea nf(%d,&n);move( n,a,b,

12、c);跳马问题：#i ncludevoid main()int Movel8=-2,-1,1,2,2,1,-1,-2;int Movev8=1,2,2,1,-1,-2,-2,-1;int A88;int I,v,l1,v1,l2,v2,m, n,s,b,d;初始化为零for(i nt c=0;c=7;c+)for(i nt r=0;r=7;r+)Acr=0;提示用户输入马的起始位置，coutvv = = = = = = = = = = = = = = = = = = = = = =e ndl;coute ndl;v;Alv=1;开始马的遍历for(i nt t=2;t=0&I1=0&v1=0&

13、I 2=0&v2=d)b=d;s=p;if(b=8)l+=Movels;v+=Movevs;Alv=t;打印出马的路线，for(m=0;m=7;m+)for(n=0;n=7;n+)coutAm n;coute ndl;长整数的运算：void mai n()/void put_i n( char str);void Swap(char str1,char str2); 当相加的两数符号不同时，把绝对值大的放在str1中,绝对值小的放在str2中；void display(struct DuLNode *head); /十进制数的输出函数；struct DuLNode *Convert(char

14、str30); /把数字字符转变为十进制数的函数，用链表来存放，一个结点存放一位十进制，返回表头指针；struct DuLNode *Add(struct DuLNode *h1,struct DuLNode *h2);/ 实现加法的函数；struct DuLNode *Sub(struct DuLNode *h1,struct DuLNode *h2);/ 实现减法的 函数;struct DuLNode *h1,*h2,*h;char str130=+234145687996565667 ;char str230=-987654879 ;/ put_i n( str1);put_i n(st

15、r2);h仁Con vert(str1);h2=Co nvert(str2);cout输入操作数:endl;if(str10=-)/如果操数为时，负号必须先输出，以下雷同；coutstr10;display(h1);if(str20=-)coutstr20;display(h2);if(str10=+&str20=+)|(str10=-&str20=-)/ 如果参加运算的两数符号相同则直接相加，符号与第一个操作数的符号相同；h=Add(h1,h2);/实现相同符号的两长整数的绝对值相加；else/如果参加运算的两数符号不同，则比较两数的绝对值，绝对值大的放在str1绝对值小的放在str2中；S

16、wap (str1,str2);h仁Convert(str1);把数字字符串str1转变为十进制数；h2=Convert(st；/把数字字符串str2转变为十进制数；h=Sub(h1,h2);/实现两长整数相减；cout两数相加的结果为:endl;if(str1O=-)/运算的结果若为负则要输出此负号coutdata=stri-50+2;p-n ext=NULL;for(j=i-1;j0;j-)q=(struct DuLNode *)malloc(sizeof(struct DuLNode);十进数q-data=strj-50+2;数字字符与十进制数之间的转换通过的ASCII码二数字字符的AS

17、CII码-48实现；head=q;q-n ext=p;p-prior=q;p=q;p=head;q=p;p=p-n ext; while(p)q=p；p=p-n ext; q-n ext=head; head-prior=q; retur n head; struct DuLNode *Add(struct DuLNode *h1,struct DuLNode *h2) struct DuLNode *p1,*p2,*e nd1,*e nd2,*p,*q,*h,*pp;p仁 h1;p2=h2;while(p1- next!=h1)p1=p1- n ext;end1=p1;while(p2- n

18、ext!=h2)p2=p2-n ext;end2=p2;int t,t1;t仁0;p=(struct DuLNode *)malloc(sizeof(struct DuLNode);PP=P；while(p1-prior!=e nd1&p2-prior!=e nd2)t=p1-data+p2-data+t1;t仁 t/10;p-data=t%10;q=(struct DuLNode *)malloc(sizeof(struct DuLNode);p-prior=q;q-n ext=p;p=q;p1=p1-prior;p2=p2-prior;t=p1-data+p2-data+t1;p-data

19、=t%10;t仁t/10;if(p1-prior!=e nd1)p1=p1-prior;while(p1!=e nd1)q=(struct DuLNode *)malloc(sizeof(struct DuLNode); t=p1-data+t1;t仁 t/10;q-data=t%10;q-n ext=p;p-prior=q;p=q;p1=p1-prior;q=(struct DuLNode *)malloc(sizeof(struct DuLNode);q-data=t1;q-n ext=p;p-prior=q;elsep2=p2-prior;while(p2!=e nd2)q=(struc

20、t DuLNode *)malloc(sizeof(struct DuLNode); t=p2-data+t1;t仁 t/10;q-data=t%10;q-n ext=p;p-prior=q;p2=p2-prior;q=(struct DuLNode *)malloc(sizeof(struct DuLNode);q-data=t1;p-prior=q;q-n ext=p;h=q;h-prior=pp;pp-n ext=h;return h;void display(struct DuLNode *head)struct DuLNode *p,*q;int i,j;i=1;p=head;q=p

21、;if(p-data=0)p=p-n ext;q=p;while(p-n ext!=head)i+;p=p-n ext;p=q;if(in ext!=head)coutp-data;p=p-n ext;coutdata0;j-)coutdata; p=p-n ext;cout,;i=0;while(p-n ext!=head)coutdata;p=p-n ext;i+;if(i=4)coutvv,;i=0;coutdata next!=h1)p1=p1- n ext;end仁p1;用end1记录第一个十进制操作数最低位的结点；while(p2- next!=h2)p2=p2-n ext;end

22、2=p2;用end2记录第二个十进制操作数最低位的结点；p=(struct DuLNode *)malloc(sizeof(struct DuLNode);/创建一个新的链表来存放运算结果,p是该链表的表头指针；pp=p;if(p1-datadata)t1=1;elset1=0;t=p1-data+10*t1-p2-data;p-data=t;p1=p1-prior;p2=p2-prior;while(p1!=e nd1&p2!=e nd2)if(t 仁=1)t1 仁1;elset1 仁0;if(p1-data=p2-data&t11=1)|(p1-datadata)t1=1;elset仁0;

23、t=p1-data+t1*10-t11-p2-data;q=(struct DuLNode *)malloc(sizeof(struct DuLNode);q-data=t;q-n ext=p;p-prior=q;p=q;p1=p1-prior;p2=p2-prior;while(p1!=e nd1)q=(struct DuLNode *)malloc(sizeof(struct DuLNode); if(p1-data=O&t仁=1)t=p1-data+t1*10-t1;t1=1;elset=p1-data-t1;t仁0;q-data=t;q-n ext=p;p-prior=q;q-n ex

24、t=p;p=q;p1=p1-prior;h=q;h-prior=pp;pp-n ext=h;return h; void Swap(char str1 ,char str2)in tie n1,le n2;/两字符串的长度；len 1=strle n( strl);len 2=strle n(st ；if(le n1le n2)char str30;strcpy(str,str1);strcpy(str1,str2);strcpy(str2,str);return;else if(le n1=le n2)char str1130,str2230;int i;for(i=0;ile n1-1;i+)str11i=str1i+1;for(i=0;ile n2-1;i+