数据结构课程设计 数制转换 数组和栈.docx

中北大学数据结构与算法课程设计说明书学院、系：软件学院专生；xxx:程xxx设计题目：数制转换问题起迄日期：2013年12月9日-2013年12月20日指导教师：xxx2013年12月20日1、需求分析任意给定一个M进制的数x，请实现如下要求1）求出此数x的10进制值（用MD表示）2）实现对x向任意的一个非M进制的数的转换。3）用两种方法实现上述要求（用栈解决和用数组解决）。2、概要设计流程图数组的流程图：栈的流程图:算法思想1、用数组实现该问题：DtoM()函数和MtoD ()函数是实现该问题的主要函数。DtoM()函数是实现十进制 转换为其它进制的函数，它是将输入的十进制数x取首先对需要转换的进制M取余，然 后再对其取整，接着通过递归调用DtoM()函数依次将得到的整数部分依次先取余后取 整，并将所得的余数依次存入一个数组中，然后逆向取出数组中的元素，即得到转换后 的结果。而MtoD ()函数则是实现其他进制M转换为十进制，并将其转换为非M进制的 数。M进制转十进制则是从该M进制数的最后一位开始算，依次列为第0、1、2n 位并分别乘以M的0、1、2n次方，将得到的次方相加便得到对应的十进制数，再 调用DtoM()函数将其转换为非M进制的数。2、用栈实现该问题：同样是利用DtoM()和MtoD ()两个函数实现。两个函数的思想同利用数组实现时相 同。只是栈具有后进先出的性质，故其用Pop()取数较数组的逆向取数方便些。模块划分1、用数组实现该问题：i,j,y,n,s,m,r,reminder,x是定义的全局变量，初始值都为0；DtoM(int g,int h)是实现十进制数转换为M进制数的函数；MtoD ()是实现M(仅指二进制数和八进制数)进制数转换为十进制数的函数，并 在其中调用D2M(int g,int h)实现向非M进制数的转换；HtoD(int f)是实现十六进制数转换为十进制数的函数，并在其中调用D2M(int g,int h)实现向非十六进制数的转换；void main()是主函数，功能是给出测试的数据，并在特定条件下调用D2M() 函数和M2D()函数。2、用栈实现该问题：SqStack定义栈，说明base为栈底指针，top为栈顶指针，stacksize为栈容 量； int InitStack(SqStack &S)到 int DestroyStack(SqStack &S)六大模块分别 表示构造一个空栈、用e表示栈元素、插入元素、删除元素、判断栈是否为空 以及摧毁栈；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 cN;int i=0;int j;int reminder;reminder=g%h;g=g/h;if(reminder>9)ci=reminder+55;i+；elseci=reminder;i+;if(g>0)DtoM(g,h);for(j=i-1;j>=0;j-)if(cj>=65)printf("%c”,cj);elseprintf("%d”,cj);以下MtoD()是实现M(仅指二进制数和八进制数)进制数转换为十进制数的函数，并在 其中调用D2M(int g,int h)实现向非M进制数的转换MtoD(int e)/二进制和八进制数转换为十进制数，并这转换为其他进制数int n,i,y=0,j,s;int aN;printf("请输入%d进制位数:"，e);scanf("%d”,&n);j=0;printf（"请输入%d进制的每位并使每位用空格隔开:",e）;for(i=n-1;i>=0;i)scanf("%d”,&ai);for(i=0;i<n;i+)y+=(int)pow(e,j)*ai;/强制类型转换，以免造成数据丢失j+;printf("所得的10进制的结果:d ”,y);printf("n需要转换的进制M:");scanf("%d”,&s);printf("请输出转换成%d进制的结果:"，s);DtoM(y,s);return 0;/以下为HtoD(int f)是实现十六进制数转换为十进制数的函数，并在其中调用D2M(intg,int h)实现向非十六进制数的转换HtoD(int f)/十六进制数转换为十进制数，并转换为其他进制数int n,j=0,y=0,i,s;int bN;printf("请输入%d进制位数:"，f);scanf("%d”,&n);printf("请输入%d进制的每位并使每位用空格隔开:",f);for(i=0;i<n;i+)scanf("%x”,&bi);for(i=n-1;i>=0;i)y+=(int)pow(f,j)*bi;/强制类型转换，以免造成数据丢失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("ntt* * * * * * "-" welcome ! ”-" * * * * * * n"); printf("tt数制转换系统n");printf("tt* * * * * * * * * * * * * * * * * * * * * * *n");printf("ttn)；printf("tt* * * * * * * * * * * * * * * * * * * * * * *n"); printf("tt*1.进入数制转换系统*n");printf("tt*2.退出该系统*n");printf("tt* * * * * * * * * * * * * * * * * * * * * * *n"); printf("tt请选择(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 structint *base;/栈底int *top;/栈顶int stacksize; /栈容量SqStack;/ SqStack定义栈，说明base为栈底指针，top为栈顶指针，stacksize为栈容量/*一下为 int InitStack(SqStack &S)到 int DestroyStack(SqStack &S)六大模块分别表示 构造一个空栈、用e表示栈元素、插入元素、删除元素、判断栈是否为空以及摧毁栈；*/ 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，否则返回0if(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 c1000;printf("请输入需要转换的数的位数:");scanf("%d”,&n);printf(-请输入需要转换的数的每位并用空格隔开:");for(i=0;i<n;i+)scanf("%x”,&ci);Push(S,ci);i=0;while(!StackEmpty(S)Pop(S,e); y+=(int)pow(m,i)*e;i+；printf("转换成10进制的结果是:")；printf(%d,y);return 0;/void main()是主函数。其功能是输入需要测试的数据以及需要转换的进制，并在特定情 形下调用DtoM()函数和MtoD()函数，而且实现M进制数向任意非M进制数的转换 void main()int t;for(;)printf("tt* * * * * * "-" welcome ! ”-" * * * * * * n");printf("tt数制转换系统n");printf("tt* * * * * * * * * * * * * * * * * * * * * * *n");printf("ttn);printf("tt* * * * * * * * * * * * * * * * * * * * * * *n");printf("tt*1.进入数制转换系统*n");printf("tt*2.退出该系统*n");printf("tt* * * * * * * * * * * * * * * * * * * * * * *n");printf("tt请选择(1 2):");loop:scanf("%d”,&t);switch(t) case 1: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不再存在break;case 2: exit(0);default: printf("输入有误，请重新选择:")；goto loop;printf(n)；4、调试分析数组调试结果如图：, welcome ? ? ?数制转换系统菖:2位制8伸 瞽数霁M:抻 的10制岫 的进成 牛场个进进富换 误一16 有定入入出转出 入给量偏请请也誓请t=JS每果使结F O 10 F O 8 F Orn 6用10"统 *系 *魅换* * *1.进入数割转换系统2-退出该索统«,洼一入 we leone ? ? ?数制转换系统*栈调试结果:定数请请4兀该入入入成艾5换系统*请选择需要转'奂的进制M<2or8orl0orl6> ：16蚩要薛涣的数的位数壮器寒偏奂的数的每位并用空格隔开无计10® SB结果是壮跛替换成的进®M：8换成演制的结果= 312* 卜一入 ueleone ? A数制转换系统*5、心得总结这一次的课程设计题目是数制转换问题，时间有些紧张，在进行十六进制转换为十进制 是出现了一些小问题，但是很快的解决了。只有多多上机实践，才能学到真正的东西。在切 身体会当中，发现了数值转换的精华所在，例如说怎么样取十六进制数，并且进栈出栈。将 栈和数组结合，也可以达到要求。切身体会，方能学以致用！对于数制转换的基本原理，必 须清楚，才能将程序中的设计思想完整的贯穿下来。