中北大学数据结构与算法课程设计说明书学院、系：软件学院专业：软件工程学生姓名：xxx 学号：xxxx设计题目：数制转换问题起迄日期: 2013年12月9日- 2013年12月20日指导教师:xxx2013 年12月 20 日1、需求分析任意给定一个M进制的数x ，请实现如下要求1) 求出此数x的10进制值（用MD表示）2) 实现对x向任意的一个非M进制的数的转换。

3) 用两种方法实现上述要求（用栈解决和用数组解决）。

2、概要设计流程图数组的流程图：栈的流程图：算法思想１、用数组实现该问题：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(仅指二进制数和八进制数)进制数转换为十进制数的函数，并在其中调用D2M(int g,int h)实现向非M进制数的转换；⑷HtoD(int f)是实现十六进制数转换为十进制数的函数，并在其中调用D2M(intg,int h)实现向非十六进制数的转换；⑸void main()是主函数，功能是给出测试的数据，并在特定条件下调用D2M()函数和M2D()函数。

２、用栈实现该问题：⑴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进制数的转换。

3、详细设计源程序有两个，shuzu.cpp是用数组实现该问题的程序，而stack.cpp是用栈实现该问题的程序：［文件shuzu.cpp］#include<stdio.h>#include<math.h>#include<malloc.h>#include<stdlib.h>#define N 1000// 以下为DtoM(int g,int h)是实现十进制数转换为M进制数的函数，DtoM(int g,int h){int c[N];int i=0;int j;int reminder;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]);elseprintf("%d",c[j]);}//以下MtoD()是实现M(仅指二进制数和八进制数)进制数转换为十进制数的函数，并在其中调用D2M(int g,int h)实现向非M进制数的转换MtoD(int e) //二进制和八进制数转换为十进制数,并这转换为其他进制数{int n,i,y=0,j,s;int a[N];printf("请输入%d进制位数:",e);scanf("%d",&n);j=0;printf("请输入%d进制的每位并使每位用空格隔开:",e);for(i=n-1;i>=0;i--)scanf("%d",&a[i]);for(i=0;i<n;i++){y+=(int)pow(e,j)*a[i]; //强制类型转换，以免造成数据丢失j++;}printf("所得的10进制的结果:%d ",y);printf("\n需要转换的进制M:");scanf("%d",&s);printf("请输出转换成%d进制的结果:",s);DtoM(y,s);return 0;}//以下为HtoD(int f)是实现十六进制数转换为十进制数的函数，并在其中调用D2M(int g,int h)实现向非十六进制数的转换HtoD(int f) //十六进制数转换为十进制数，并转换为其他进制数{int n,j=0,y=0,i,s;int b[N];printf("请输入%d进制位数:",f);scanf("%d",&n);printf("请输入%d进制的每位并使每位用空格隔开:",f);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()是主函数，功能是给出测试的数据，并在特定条件下调用DtoM()函数和MtoD()函数void main(){int m,r,x,t;for(;;){printf("\n\t\t* * * * * * ^-^ welcome !!! ^-^ * * * * * * \n");printf("\t\t 数制转换系统 \n");printf("\t\t* * * * * * * * * * * * * * * * * * * * * * *\n");printf("\t\t \n");printf("\t\t* * * * * * * * * * * * * * * * * * * * * * *\n");printf("\t\t* 1. 进入数制转换系统 *\n");printf("\t\t* 2. 退出该系统 *\n");printf("\t\t* * * * * * * * * * * * * * * * * * * * * * *\n");printf("\t\t 请选择(1－2):");loop:scanf("%d",&t);switch(t){ case 1:printf("请给定一个需转换的进制M(2 or 8 or 10 or 16):");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(2 or 8 or 16):");scanf("%d",&r);printf("请输出转换成%d进制的结果:",r);DtoM(x,r);printf("\n");} break;case 2: exit(0);default:{ printf("输入有误,请重新选择:");goto loop;}printf("\n");}}}［文件stack.cpp］#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;// SqStack定义栈，说明base为栈底指针，top为栈顶指针，stacksize为栈容量/*一下为int InitStack(SqStack &S)到int DestroyStack(SqStack &S)六大模块分别表示构造一个空栈、用ｅ表示栈元素、插入元素、删除元素、判断栈是否为空以及摧毁栈；*/ 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，否则返回1if(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是指定义栈SSqStack S; //定义栈S// 下面的D2M(int a,int b)的功能是将十进制数转换成M进制的函数DtoM(int a,int b) //十进制转换成其他进制的函数DtoM() {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);elseprintf("%d",e);}return 0;}// 下面是MtoD()，它的功能是M进制转换为十进制的函数MtoD() //其他进制转换为十进制的函数MtoD() {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()是主函数。