数据结构课程设计之任意进制转换.doc

大学数据结构课程设计报告题目：数值转换 院（系）：计算机工程学院 学生姓名: 班级： 学号:起迄日期: 6月16号到6月30号指导教师: 20XX20XX年度 第 2 学期 一、需求分析 1.问题描述：任意给定一个M进制的数x ，请实现如下要求1) 求出此数x的10进制值（用MD表示）2) 实现对x向任意的一个非M进制的数的转换。3) 至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）。 2.基本功能 本程序用三种方法，实现把一个M进制数x转换成其他进制数，分别是数组，递归，栈。1. 把其他进制数转换成十进制包含在一个函数中：int getdex()；2. 把十进制转换成其他进制数用了三种方法（数组，递归，栈），数组：void array(int N)。递归 ：void prind_d(int n,int c)。栈： void initstack(stack&s) ，void push(stack &s,char e)，void pop(stack s)。3.实现把一个M进制数x转换成其他进制数：先把M进制数转换成十进制数，再把十进制数转换成其他进制数。封装在三个函数中：void Array()，void Stack()，void Prind()。 3.输入输出 输入要求其他进制数为字符型数据包括在1到9，和A到F这些字符中，输出也是包含在这些字符中。如果输入超过这些范围进行容错处理。二、 概要设计1.设计思路： 把M进制数转换成其他进制数，可以先把M进制数转换成十进制数，调用int getdex()；再把十进制数转换成其他进制数（三种方法：数组，递归，栈）；最后把这两个步骤结合在一起。封装在三个函数中：void Array()，void Stack()，void Prind()；通过switch语句进行选择采用哪种方法转换。 2.数据结构设计： 抽象数据类型栈：ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 <ai-1, ai >| ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。ADT Stack；基本操作：InitStack(&S)操作结果：构造一个空栈 S。Push(&S, e)初始条件：栈 S 已存在。操作结果：插入元素 e 为新的栈顶元素。Pop(&S, &e)初始条件：栈 S 已存在且非空。操作结果：删除 S 的栈顶元素，并用 e 返回其值。3. 软件结构设计：三、 详细设计 1. 定义程序中所有用到的数据及其数据结构，及其基本操作的实现；用到的数据char类型M进制数，typedef structint *base;int *top;int stacksize;stack;基本操作： void array(int N)初始条件：已知一个十进制数操作结果：转换成其他进制数y。int getdex() 初始条件：已知一个M进制数操作结果：转换成十进制数。void prind_d(int n,int c)基本操作：初始条件：已知一个十进制数操作结果：转换成其他进制数y。InitStack(&S)操作结果：构造一个空栈 S。Push(&S, e)初始条件：栈 S 已存在。操作结果：插入元素 e 为新的栈顶元素。Pop(&S, &e)初始条件：栈 S 已存在且非空。操作结果：删除 S 的栈顶元素，并用 e 返回其值。2主函数和其他函数的伪码算法；算法设计说明，存储结构的说明。1. int getdex()；把其他进制数转化为十进制数，算法步骤：（1）定义一个字符型的数组char a【50】，用gets（）函数输入字符串。把M进制数保存在一个字符串数组当中，例如16进制数2A，（2） 用for循环的嵌套实现转换。从i=n-1开始，执行语句：判断a【i】是否大于57（整数大小的比较），（ai<=57，a【i】减去48，ai>57那么ai-55，因为1到9和A,B，C的Aske码有差别。）从而实现字符向整数的转变。（3） 通过for循环把M进制数的每一位取出来用t保存，倒序取出的先取得A，再取2。（4） P=1，然后嵌套的for循环用来求每一位对应的权。例如A对应的p=0,2的权p=1。用for(j=0;j<n-i-1;j+)p=p*x;求p，循环的条件是j<n-i-1;（5） 把十进制数用sum存储，sum=sum+t*p；*存储结构说明:物理存储结构是顺序存储结构，逻辑结构是线性结构，主要是采用数组来存储处理M进制数。2. void array(int N)；把十进制数转成其他进制数。（1） .定义字符数组char HexNum = "0123456789ABCDEF"char a1000=0; (2) 输入要转化成进制数q；用取余数的方法，把余数存储在数组a1000,实现语句为while语句，（ai=HexNumN%q;i=i+1；N=N/q;）其中十进制数N除以q的余数正好对应数组HexNum 的某一元素，例如42除以16，余下2，对应HexNum 中2，余下10对应数组中的A。(3) 倒序输出余数；定义变量m，存储数组a中余数的元素的个数，用for循环从i=m+1；开始输出也就是从数组a【】中最后一个余数开始输出。直到i=0；*本函数定义了两个数组一个存储1-9，A到F这16个字符的另一个存储10进制数除以q进制数的余数的。3. void prind_d(int n,int c)递归的方法把十进制转换成其他进制数。（1） 定义一个递归函数用switch语句判断转换成的四种情况（2） Case 10，输入十进制数n，判断是否<0,如果是则putchar('-')；然后 if(n/10)判断商是否为0；再执行prind_d(n/10,10);递归，直到商为0时停止。跳过prind_d(n/10,10)，执行putchar(n%10+'0');，输出余数，然后倒序的方式输出所有余数。（3） Case 16，case 8，case 2都和case10一样。*十六进制数不太一样要把余数保存在一个数组中， char ch="0123456789ABCDEF"然后倒序输出。4.栈的方式实现十进制转化为其他进制数。（1）void initstack(stack&s)定义一个结构体typedef structint *base;int *top;int stacksize;stack;s.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int);开辟一个STACK_INIT_SIZE大的空间并把首地址赋给栈底指针s.base；s.top=s.base，栈底和栈顶指针相等表明是空栈；栈的大小为s.stacksize=STACK_INIT_SIZE。（2） 入栈void push(stack &s,char e)判断是否栈满s.top-s.base>=s.stacksize；如果栈满另外开辟新的空间s.base=(int *)realloc（），并把首地址赋给s.base。栈的栈顶指针为s.top=s.base+s.stacksize;栈的容量变为：s.stacksize+=STACKINCREMENT ；并把新的元素赋给栈顶指针，*s.top=e;栈顶指针加1，s.top =s.top+1。（3） 出栈。While语句判断s.top!=s.base时结束，栈顶指针的值赋给e，然后减1，判断e>9是否成立，如果是则以字符的形式输出输出否则以整数的形式输出。4. 封装在三个函数中 Array()，Stack()， Prind()把M进制数转换为其他进制数。（1）Array()，Prind()。输入M进制数x，然后转换成十进制数m，分别再用void array(int N)，void prind_d(int n,int c)这两个函数转换成y进制数。（2）Stack()。 temp=(int)N%n，求余数，并入栈，push(s,temp)，但当temp>9时要强制转换成字符类型：temp=(char)(temp+55);然后倒序出栈pop(s)。5,。主函数main（）用一个switch语句来选择用哪种方法，n=1，用数组，n=2用递归，n=3用栈。其他输入输入错误。3. 主要函数的程序流程图，实现设计中主程序和其他子模块的算法，以流程图的形式表示。4. 画出函数之间的调用关系图。四、 调试分析 调试分析：1. 实际完成的情况说明（完成的功能，支持的数据类型等）；可以完成M进制数X到其他进制数的转换2. 程序的性能分析，包括时空分析；程序的时间复杂度为o（n），空间复杂度为0（1）；3. 上机过程中出现的问题及其解决方案；实验过程中要在数组方法中出现问题：保存余数的数组char a1000要都赋予值0，否则在倒序的是否会因为系统自动分配的未知数值出现问题char a1000。本来结果应该是2A结果却是 烫2A。问题2.在把其他进制数转换成十进制数的时候，1到9的ASCII值（t=ai-48）与ABCF字符的ASCII码（t=ai-55）的值有区别，本应该转换成的十进制数是159，但却等于156，所以要分开对待。4. 程序中可以改进的地方说明；试验中还是又可以改进的地方的，例如把小数转化的部分加进去。增强程序的容错性主要在输入输出方面5. 程序中可以扩充的功能及设计实现假想。可以直接实现把M进制数转换成N进制数，而不是通过十进制这个桥梁。五、测试结果栈方法：递归方法：六、用户手册：用visual C打开源文件，按ctrl+F7，进行编译，再按ctrl+F5运行，会出现一个界面再按菜单操作及可七体会与自我评价 实验设计中我学到了模块化处理问题，找到问题，并一个个解决，例如把三种方法封装在三个函数中。但在也存在着一些问题主要是16进制上，它包括一些AB等一些字母，所以要进行特别处理。例如在十进制的转化中要分开处理if(ai<=57)/比较大小都要换成整型的t=ai-48;elset=ai-55;if(i=n-1) 解决数制转换问题时，如果所给的数值不是用十进制表示的，一般用一个字符型数组来存放。数组的每个元素分别存储它的一位数字。然后按位转换求和，得到十进制表示；再十进制表示转换成所求的数制表示。转换的结果也用一个字符型数组表示，每个元素表示换结果的一位数字。根据数制表示中相邻位的基数关系，可以把不同的数制分成两类。一类数制表示中，相邻位的基数是等比关系，例如我们熟悉的十进制表示。另一类数制表示中，相邻位的基数不等比的。例如在时间表示中，从秒到分采用60 进进制；从月到年采用12 进制。把一个数值从数制B 的表示bmbm-1b m-2 . b1 转换成十进制表示dnd n-1d n-2 . d1 比较简单。假设数制B中，第i 位的基数为basei(1 ? i ? m)，直接把basei 与bi 相乘，然后对全部乘积求和。从十进制表示dnd n-1d n-2 . d1 到bmbm-1b m-2 . b1 的转换需要分两种情况考虑：数制 M 中相邻数字的基数是等比关系，即：basei(m)可以表示成Ci-1，其中C 是一个常量。将dnd n-1d n-2 . d1 除以C，余数即为b1；将dnd n-1d n-2 . d1 和C 相除的结果再除以q，余数即为b； ；直至计算出为bm 止。 数制 M 中相邻数字的基数不等比。需要先判断dnd n-1d n-2 . d1 在数制M中需要的位数m，然后从高位到低位依次计算bm、bm-1、b m-2、.、b1。源代码：#include <iostream>using namespace std;#include<string>#include<malloc.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10 typedef structint *base;int *top;int stacksize;stack; /int getdex()char a50;int n,j,i,sum=0,t=0,p=1;int x;printf("输入要转化M进制数: ");scanf("%d",&x);printf("输入一个进制数x: ");cin.get();gets(a);n=strlen(a);for(i=n-1;i>=0;i-)p=1;if(ai<=57)/比较大小都要换成整型的t=ai-48;elset=ai-55;if(i=n-1)p=1;elsefor(j=0;j<n-i-1;j+)p=p*x;sum+=t*p;printf("对应的十进制数：%dn",sum);return sum;/void array(int N)char HexNum = "0123456789ABCDEF"char a1000=0;printf("输入一个要转化的进制数N:");int q;scanf("%d",&q);int i=0,m=0;while(N)ai=HexNumN%q;i=i+1;N=N/q; /printf("%d",i); m=i;for(i=m+1;i>=0;i-)printf("%c",ai);cout<<endl;/ void initstack(stack&s) /构造一个空栈ss.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int);/存储分配失败s.top=s.base;s.stacksize=STACK_INIT_SIZE; / return s; /void push(stack &s,char e)/插入元素e为新的栈顶元素，并返回OK，否则返回ERRORif(s.top-s.base>=s.stacksize)/栈满追加存储空间s.base=(int *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(int);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT ;*s.top=e; s.top =s.top+1;/ return s;/void pop(stack s)/若栈不空则删除s的栈顶元素，用e返回其值，并返回OK，否则返回ERRORint e;/printf("输出相等的一个%d进制数",&n);while(s.top!=s.base)e=*-s.top;if (e>9)printf("%c",e);else printf("%d",e);/void prind_d(int n,int c) switch(c) case 10 : if (n<0) putchar('-'); n=-n; if(n/10) prind_d(n/10,10); putchar(n%10+'0'); break; case 8: if(n/8) prind_d(n/8,8); putchar(n%8+'0'); break; case 16: if (n<0) putchar('-'); n=-n; char ch="0123456789ABCDEF" if(n/16) prind_d(n/16,16); putchar(chn%16); break; case 2: if(n/2) prind_d(n/2,2); putchar(n%2+'0'); break; /void Array()printf("数组方法的运行结果：n"); int a; a=getdex();array(a);/void Stack()printf("栈方法的运行结果：n");stack s; int N,temp; initstack(s); N=getdex(); /printf("输入一个十进制数");/ scanf("%d",&N); printf("请输入要转换成的进制数N :"); int n;/把十进制转换成n进制 scanf("%d",&n); while(N)temp=(int)N%n;if(temp>9)temp=(char)(temp+55);push(s,temp);N=N/n; printf("转换成的N=%d进制数:n",n);pop(s);printf("n");/void Prind()printf("递归方法的运行结果：n"); int c,m; puts("输入要转化的进制数N"); cin>>c; m=getdex();cout<<"N:" prind_d(m,c); cout<<endl;/void main() printf("nn-nn");printf("* * * *欢迎使用本程序!本程序完成数制转换 M 进制数转换成 N 进制数。* * * *nn");printf("-n");doprintf("请按键选择n");printf("*数组 1 *n");printf("*栈 2 *n");printf("*递归 3 *n");int n;cin>>n;switch (n)case 1: Array();continue; case 2:Stack();continue;case 3:Prind();continue;default :printf("输入有误");while(1);