软件算法设计说明书.doc

科 信 学 院
课程设计说明书
（2012/2013学年第二学期）

课程名称 ： 软件综合算法设计
题 目 ： 数制转换问题
专业班级 ：
学生姓名 ：
学 号：
指导教师 ：
设计周数 ： 2周
设计成绩 ：

2013年 7 月 2 日

目 录

一、实验目的 - 2 -
二、实验要求及目标 - 2 -
三、算法思想 - 3 -
１、用数组实现该问题： - 3 -
２、用栈实现该问题： - 3 -
四、模块划分 - 3 -
１、用数组实现该问题： - 3 -
２、用栈实现该问题： - 4 -
五、数据结构 - 4 -
１、用数组实现该问题 - 4 -
２、用栈实现该问题 - 4 -
六、程序源代码及结果 - 5 -
（一）数组 - 5 -
1、源代码 - 5 -
2、运行结果 - 8 -
（二）栈 - 10 -
1、源代码 - 10 -
2.运行结果 - 15 -
七、心得体会 - 17 -
【参考文献】 - 19 -

软 件 综 合 算 法 设 计 报 告
实验名称：数值转换问题

指导老师：杨 荣 爱
组员1：黄静南 学号：110212203
组员2：赵兴凡 学号：110212216
完成时间：2013年7月2日

一、实验目的
了解并掌握软件算法设计的方法与步骤，具备初步的独立分析问题、解决问题的能力。初步掌握软件开发过程的问题分析、系统设计、程序编码和测试等基本方法和技能。积累项目设计及程序调试、测试的经验，提高综合运用所学的理论知识和方法，锻炼独立分析和解决问题的能力。 训练用系统的观点和软件开发一般规范进行软件的开发，培养软件工作者所具备的科学工作方法和作风。

二、实验要求及目标
要求：任意给定一个M进制的数x ，请实现如下要求：
1)求出此数x的10进制值（用MD表示）；
2)实现对x向任意的一个非M进制的数的转换；
3)至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）。
目标：完成实验要求，实现源代码的运行，进而实现要求中的基本功能。

三、算法思想
１、用数组实现该问题：
DTOM()函数和MTOD()函数是实现该问题的主要函数。　DTOM()函数是实现十进制转换。
为其它进制的函数，它是将输入的十进制数ｘ取首先对需要转换的进制M取余，然后再对其取整，接着通过递归调用DTOM()函数依次将得到的整数部分依次先取余后取整，并将所得的余数依次存入一个数组中，然后逆向取出数组中的元素，即得到转换后的结果。而MTOD()函数则是实现其他进制M转换为十进制，并将其转换为非M进制的数。M进制转十进制则是从该M进制数的最后一位开始算，依次列为第０、１、２…ｎ位并分别乘以M的０、１、２…ｎ次方，将得到的次方相加便得到对应的十进制数，再调用DTOM()函数将其转换为非M进制的数。

２、用栈实现该问题：
同样是利用DTOM()和MTOD()两个函数实现。两个函数的思想同利用数组实现时相同。只是栈具有后进先出的性质，故其用Pop()取数较数组的逆向取数方便些。

四、模块划分
１、用数组实现该问题：
⑴　i,j,y,n,s,m,r,reminder,x是定义的全局变量，初始值都为０；
⑵　DTOM(int g,int h)是实现十进制数转换为M进制数的函数；
⑶　MTOD()是实现M(仅指二进制数和八进制数)进制数转换为十进制数的函数，并在其中调用DTOM(int g,int h)实现向非M进制数的转换；
⑷　HTOD(int f)是实现十六进制数转换为十进制数的函数，并在其中调用DTOM(int g,int h)实现向非十六进制数的转换；
⑸　void main()是主函数，功能是给出测试的数据，并在特定条件下调用DTOM()函数和MTOD()函数。

２、用栈实现该问题：
⑴　SqStack定义栈，说明base为栈底指针，top为栈顶指针，stacksize为栈容量；
⑵　int InitStack(SqStack &S)到int DestroyStack(SqStack &S)六大模块分别表示构造一个空栈、用ｅ表示栈元素、插入元素、删除元素、判断栈是否为空以及摧毁栈；
⑶　SqStack S是指定义栈S；
⑷　DTOM(int a,int b)的功能是将十进制数转换成M进制的函数；
⑸　MTOD()的功能是M进制转换为十进制的函数；
⑹　void main()是主函数。其功能是输入需要测试的数据以及需要转换的进制，并在特定情形下调用DTOM()函数和MTOD()函数，而且实现M进制数向任意非M进制数的转换。

五、数据结构
１、用数组实现该问题：
使用简单一维数组int a[N]，int b[N]， int c[N]。

２、用栈实现该问题：
　　数据类型定义如下：
　　typedef struct{
int *base;
int *top;
int stacksize;
}SqStack;

六、程序源代码及结果
（一）数组
1、源代码
#include<stdio.h>
#include<math.h>
#define N 1000
int i,j,y,n,s;
int m,r,reminder;
int x; 　　//全局变量默认初始化为0，不必再赋0了

DTOM(int g,int h) 　//十进制数转换为其他进制数
{
int c[N];
i=0;
reminder=g%h;
g=g/h;
if(reminder>9)
{
c[i]=reminder+55;
i++;
}
else
{
c[i]=reminder;
i++;
}
if(g>0)
DTOM(g,h);
for(j=i-1;j>=0;j--)
if(c[j]>=65)
printf("%c",c[j]);
else
printf("%d",c[j]);
return 0;
}

MTOD(int e) //二进制和八进制数转换为十进制数,并这转换为其他进制数
{
int a[N];
printf("请输入%d进制位数:",m);
scanf("%d",&n);
printf("请输入%d进制的每位并使每位用空格隔开:",m);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=n-1;i>=0;i--)
{
y+=(int)pow(e,j)*a[i]; //强制类型转换，以免造成数据丢失
j++;
}
printf("请输出所得的10进制的结果: ");
printf("%d",y);
printf("\n需要转换的进制M:");
scanf("%d",&s);
printf("请输出转换成%d进制的结果:",s);
DTOM(y,s);
return 0;
}

HTOD(int f) //十六进制数转换为十进制数，并转换为其他进制数
{
int b[N];
printf("请输入%d进制位数:",m);
scanf("%d",&n);
printf("请输入%d进制的每位并使每位用空格隔开:",m);
for(i=0;i<n;i++)
scanf("%x",&b[i]);
for(i=n-1;i>=0;i--)
{
y+=(int)pow(f,j)*b[i]; //强制类型转换，以免造成数据丢失
j++;
}
printf("请输出所得的10进制的结果: ");
printf("%d",y);
printf("\n需要转换的进制M:");
scanf("%d",&s);
printf("请输出转换成%d进制的结果:",s);
DTOM(y,s);
return 0;
}

void main()
{
printf("请给定一个需转换的进制M(2or8or10or16):");
scanf("%d",&m);
if(m==2||m==8) //二进制和八进制转换成十进制
MTOD(m);
else if(m==16) //十六进制转换成十进制
HTOD(m);
else if(m==10) //十进制转换成其它进制
{
printf("请输入一个%d进制数:",m);
scanf("%d",&x);
printf("请输入需要转换成的进制M(2or8or16):");
scanf("%d",&r);
printf("请输出转换成%d进制的结果:",r);
DTOM(x,r);
}
printf("\n");
}

2、运行结果

图1-1

图1-2

图1-3

图1-4

（二）栈
1、源代码
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<math.h>
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
int e,m,x,s,t; //x为要转换的十进制数，e 为临时用的的int型变量
int r,y,i,n;

typedef struct{
int *base; //栈底
int *top; //栈顶
int stacksize; //栈容量
}SqStack;

int InitStack(SqStack &S){ //构造一个空栈
S.base=(int *)malloc(STACK_INIT_SIZE *sizeof(int));
if(!S.base) exit(0); //存储空间失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return 0;
}

int GetTop(SqStack S, int &e){ //若栈不为空，则用e返回S的栈顶元素，并返回0，否则返回1
if(S.top==S.base) return 1;
e=*(S.top-1);
return 0;
}

int Push(SqStack &S , int e){ //插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize){ //栈满，追加存储空间
S.base=(int *)realloc(S.base,
(S.stacksize+STACKINCREMENT)*sizeof(int));
if(!S.base) return 1 ; //存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return 0;
}

int Pop(SqStack &S, int &e){ //若栈不空，则删除S的栈顶元素，用e返回其值，并返回0，否则返回1
if(S.top==S.base) return 1;
e=*--S.top;
return 0;
}

int StackEmpty(SqStack S){ //若栈空，则返回1，否则返回0
if(S.top==S.base)
return 1;
return 0 ;
}

int DestroyStack(SqStack &S){ //销毁栈S，栈S不再存在
free(S.base);
S.top=NULL; //防止程序后面不小心使用了它
S.base=S.top;
return 0 ;
}

SqStack S; //定义栈S

DTOM(int a,int b) //十进制转换成其他进制的函数D2M()
{
while(a)
{
r=a%b;
if(r>9)
r=r+55;
Push(S,r); //压入栈
a/=b; //转换成M进制
}
printf("该数转换成%d进制的结果:",b);
while(!StackEmpty(S))
{
Pop(S,e); //弹出栈
if(e>=65)
printf("%c",e);
else
printf("%d",e);
}
return 0;
}

MTOD() //其他进制转换为十进制的函数M2D()
{
char c[1000];
printf("请输入需要转换的数的位数:");
scanf("%d",&n);
printf("请输入需要转换的数的每位并用空格隔开:");
for(i=0;i<n;i++)
{
scanf("%x",&c[i]);
Push(S,c[i]);
}
i=0;
while(!StackEmpty(S))
{
Pop(S,e);
y+=(int)pow(m,i)*e;
i++;
}
printf("转换成10进制的结果是:");
printf("%d",y);
return 0;
}

void main()
{
InitStack(S); //构造一个空栈
printf("请输入需要转换的进制M(2or8or10or16):");
scanf("%d",&m);
if(m==10) //十进制转换成其他进制
{
printf("请给定一个需要转换的10进制数:");
scanf("%d",&x);
printf("请输入需要转换成的进制数:");
scanf("%d",&t);
DTOM(x,t);
}
if(m==2||m==8||m==16) //其他进制转换成十进制，且其他任意进制的相互转换
{
MTOD();
printf("\n给定要转换成的进制M:");
scanf("%d",&s);
DTOM(y,s);
}
printf("\n");
DestroyStack(S); //销毁栈S，栈S不再存在

}

2.运行结果

图2-1

图2-2

图2-3

图2-4
七、心得体会
组员一（黄静南）：通过这次软件算法设计，我对研究算法设计的重要性有了更加深刻的认知，算法的选择对解决实际问题的效率有很大的影响，实验使我对设计思想有了更加深刻的理解，对以后的实验解决方案有了更多的选择，开阔了我的设计思路。软件算法设计是培养学生综合运用所学知识，发现，提出，分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程。
在实验设计过程中，我还发现了很多学习中的盲点，上理论课时认为已经理解的在程序中运行起来又是另一回事，所以实践与理论结合是学习中非常重要的，尤其是在软件设计方面。随着科学技术发展的日新月异，当今计算机应用在生活中可以说得是无处不在。而计算机应用与编程相互依存，在学好基础的情况下增加实践是最好的选择。
经过这一次两周完整的成功的编程练习，对我产生的莫大的激励，也让我对编程有了更大的兴趣。这次的软件算法设计对我们的锻炼很大，让我们学到了老师没法交给我们的，也让我们明白程序设计的大体步骤，让我们对我们的专业又有更进一步的了解。我不仅体会到自己解决问题的乐趣，也体验到了同学合作的美好。两周时间说长不长，说短也不短，我们不停地翻阅资料和讨论，有过迷茫有过喜悦，不过最后我们终于成功了！满足感油然而生，如果有人问我物质和精神哪个更让人满足，那答案一定是精神，那种感觉只有自己体会了才能懂。总之，这次设计程序让我受益良多，我很珍惜像这种难得的机会

组员二（赵兴凡）：通过这次实验设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，这毕竟独立做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。
独立自主固然重要，但是分工合作也必不可少。通过这次与同学的合作，了解到自身的不足，与同伴做到了互补。我们选的题目看着简单，但是做起来很难，虽然刚学完数据结构，期间还是遇到了很多问题。
程序不是一气呵成的，需要一点一点的修改补充，直到可以成功运行出需要的功能。
这次课程设计给了我以后编程莫大的激励，因为我认为所谓算法通过老师的传授每个人都只会一点点，而课外的东西需要自己去学习。仅靠自己学的那些基础知识是无法编程的，需要融会贯通并且熟练运用。这段时间虽然很不好受，但是我体会到了编程的乐趣，这使我对自己有了信心。这学期学的数据结构也起到了很大的作用，有了数据结构的只是，加上程序设计技术则对以后对计算机技术的深入学习应该会有很大的帮助。最后，感谢各位老师的教导，感谢老师给我们这次实践的机会。

参考文献
[1] 严蔚敏，吴伟民。数据结构（C语言版）。清华大学出版社，2007
[2]陈良银，游洪跃，李伟旭。C语言程序设计（C99版）。清华大学出版社，2006（2007重印）
[3]谭浩强。C++程序设计（第二版）。清华大学出版社，2011.8

课程设计
评 语

课程设计
成 绩

指导教师
（签字）

年 月 日

- 19 -