数制转换问题课程设计报告.docx

数制转换问题课程设计报告中北大学 1 设计目的 数据结构课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： n 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； n 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； n 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 2. 设计内容和要求 内容 任意给定一个M进制的数x，转换为其它任意进制的数据。 基本要求 、对给字一个M进制的数据x，求出此数x的10进制值(用MD表示)； 、实现对x向任意的一个非M进制的数的转换； 、至少用两种方法实现上述要求(用栈解决，用数组解决，其它方法解决)。 核心问题: 将一个任意数的进制进行转换 数据模型: 栈的应用、数组的应用 3本设计所采用的数据结构 数据结构 、用数组实现该问题： 使用简单一维数组int aN，int bN， int cN。 、用栈实现该问题： 数据类型定义如下： typedef struct int *base; int *top; int stacksize; SqStack; 输入数据: 一个M进制的数x 输出数据: 其它任意进制的数据* 4功能模块详细设计 4.1 详细设计思想 算法思想 、用数组实现该问题： 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进制数的转换； 1 HtoD(int f)是实现十六进制数转换为十进制数的函数，并在其中调用D2M(int g,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进制数的转换。 流程图 数组流程图 2 开始 执行main函数 switch选择功能 选择操作编号 2.退出 exit(0) 1进入转换系统 输入需转换进制的数字 m=2| m=16 m=10 m=8 3 MtoD HtoD 输入十进制数 输出结输出结DtoM 果 果 输出结果 栈的流程图 开始 执行main函数 switch选择功能 选择操作编号 2.退出 exit(0) 1进入转换系统 InitStack构造空栈 输入需转换进制的数字 m=2|m=8|m=16 m=10 MtoD 输入一个十进制数 4 DtoM DtoM 输出结果 销毁栈 4.2 核心代码 源程序有两个，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+; 5 else if(g>0) DtoM(g,h); ci=reminder; i+; for(j=i-1;j>=0;j-) if(cj>=65) printf("%c",cj); else printf("%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+) 6 y+=(int)pow(e,j)*ai; /强制类型转换，以免造成数据丢失 j+; printf("所得的10进制的结果:%d ",y); printf("n需要转换的进制M:"); /以下为HtoD(int f)是实现十六进制数转换为十进制数的函数，并在其中调用D2M(int g,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("%d",&s); printf("请输出转换成%d进制的结果:",s); DtoM(y,s); return 0; 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); 7 printf("请输出转换成%d进制的结果:",s); DtoM(y,s); return 0; / void main是主函数，功能是给出测试的数据，并在特定条件下调用D2M函数和M2D函数 void main int m,r,x,t; for(;) printf("tt* * * * * * - welcome ! - * * * * * * n"); printf("tt 数制转换系统 n"); printf("tt* * * * * * * * * * * * * * * * * * * * * * *n"); printf("tt n"); printf("tt* * * * * * * * * * * * * * * * * * * * * * *n"); printf("tt* 1. 进入数制转换系统 *n"); printf("tt* 2. 退出该系统 *n"); printf("tt* * * * * * * * * * * * * * * * * * * * * * *n"); printf("tt 请选择(12):"); 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) /十进制转换成其它进制 8 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"); 9 文件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) /构造一个空栈 int GetTop(SqStack S, int &e) /若栈不为空，则用e返回S的栈顶元素，并返回0，否则返回1 10 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; if(S.top=S.base) return 1; e=*(S.top-1); return 0; int Push(SqStack &S , int e) /插入元素e为新的栈顶元素 int Pop(SqStack &S, int &e) /若栈不空，则删除S的栈顶元素，用e返回其值，并返回0，否则返回1 int StackEmpty(SqStack S) /若栈空，则返回1，否则返回0 int DestroyStack(SqStack &S) /销毁栈S，栈S不再存在 /以下 SqStack S是指定义栈S SqStack S; /定义栈S 11 if(S.top-S.base>=S.stacksize) /栈满，追加存储空间 *S.top+=e; return 0; 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; if(S.top=S.base) return 1; e=*-S.top; return 0; if(S.top=S.base) return 1; return 0 ; free(S.base); S.top=NULL; /防止程序后面不小心使用了它 S.base=S.top; return 0 ; / 下面的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); else printf("%d",e); return 0; / 下面是M2D，它的功能是M进制转换为十进制的函数 MtoD /其他进制转换为十进制的函数MtoD char c1000; printf("请输入需要转换的数的位数:"); scanf("%d",&n); printf("请输入需要转换的数的每位并用空格隔开:"); for(i=0;i<n;i+) 12 scanf("%x",&ci); Push(S,ci); i=0; /void main是主函数。其功能是输入需要测试的数据以及需要转换的进制，并在特定情形下调用D2M函数和M2D函数，而且实现M进制数向任意非M进制数的转换 void main int t; for(;) printf("tt* * * * * * - welcome ! - * * * * * * n"); while(!StackEmpty(S) printf("转换成10进制的结果是:"); printf("%d",y); return 0; Pop(S,e); y+=(int)pow(m,i)*e; i+; printf("tt 数制转换系统 n"); printf("tt* * * * * * * * * * * * * * * * * * * * * * *n"); printf("tt n"); printf("tt* * * * * * * * * * * * * * * * * * * * * * *n"); printf("tt* 1. 进入数制转换系统 *n"); 13 printf("tt* 2. 退出该系统 *n"); printf("tt* * * * * * * * * * * * * * * * * * * * * * *n"); printf("tt 请选择(12):"); loop:scanf("%d",&t); switch(t) case 1:InitStack(S); /构造一个空栈 printf("请输入需要转换的进制M(2or8or10or16):"); scanf("%d",&m); if(m=10) /十进制转换成其他进制 if(m=2|m=8|m=16) /其他进制转换成十进制，且其他任意进制的相printf("请给定一个需要转换的10进制数:"); scanf("%d",&x); printf("请输入需要转换成的进制数:"); scanf("%d",&t); DtoM(x,t); 互转换 printf("n"); DestroyStack(S); /销毁栈S，栈S不再存在 break; MtoD; printf("n给定要转换成的进制M:"); scanf("%d",&s); DtoM(y,s); case 2: exit(0); default: printf("输入有误,请重新选择:"); 14 goto loop; printf("n"); 5课程设计心得及存在问题 心得：多多上机实践，才能学到真正的东西。在切身体会当中，发现了数值转换的精华所在，例如说怎么样取十六进制数，并且进栈出栈。将栈和数组结合，也可以达到要求。 问题：切身体会，方能学以致用！对于数值转换的基本原理，必须清楚，才能将程序中的设计思想完整的贯穿下来。 15