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

《数据结构课程设计之任意进制转换》由会员分享，可在线阅读，更多相关《数据结构课程设计之任意进制转换（18页珍藏版）》请在装配图网上搜索。

1、井井大学数据结构课程设计报告题目：数值转换院（系）：计算机工程学院学生姓名：班级：学号起迄日6月16号到6月30号指导教师：指导教师评语辛成缱20XX 20XX 年度 第 2学期一、需求分析1.问题描述 ：任意给定一个 M 进制的数 x ，请实现如下要求1) 求出此数x的10进制值(用MD表示)2) 实现对x向任意的一个非M进制的数的转换。3) 至少用两种或两种以上的方法实现上述要求(用栈解决，用数组解决，其它方法解 决)。2. 基本功能本程序用三种方法，实现把一个M进制数x转换成其他进制数，分别是数组，递归，栈。1. 把其他进制数转换成十进制包含在一个函数中：int getdex()；2.

2、把十进制转换成其他进制数用了三种方法(数组 ，递归，栈)，数组： void array(intN) 。递归 ： 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

3、到F这些字符中，输出也是包含在这些字 符中。如果输入超过这些范围进行容错处理。二、 概要设计1. 设计思路：把 M 进制数转换成其他进制数，可以先把 M 进制数转换成十进制数，调用 int getdex(；) 再把十进制数转换成其他进制数(三种方法：数组，递归，栈)；最后把这两个步骤结合在 一起。封装在三个函数中：void Array () void Stack() void Prind()通过switch语句进行选择 采用哪种方法转换。2. 数据结构设计：抽象数据类型栈： ADT Stack 数据对象：D = ai | ai W ElemSet, i=l,2,.,n, n 三 0 数据关系：

4、R1 = | ai-1, ai WD, i=2,.,n 约定an端为栈顶，al端为栈底。ADT Stack ；基本操作：InitStack(&S) 操作结果：构造一个空栈 S 。Push(&S, e) 初始条件：栈 S 已存在。操作结果：插入元素 e 为新的栈顶元素。Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。3. 软件结构设计：三、 详细设计l. 定义程序中所有用到的数据及其数据结构，及其基本操作的实现； 用到的数据 char 类型 M 进制数， typedef structint *base;int *top;int sta

5、cksize;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主函数和其他函

6、数的伪码算法； 算法设计说明，存储结构的说明。l.int getdex()把其他进制数转化为十进制数，算法步骤：(1)定义一个字符型的数组char a【50】，用gets ()函数输入字符串。把M进制数保存在一个字符串 数组 当中，例如 16进制数 2A，(2 )用for循环的嵌套实现转换。从 i二n-1开始，执行语句：判断a【】是否大于57(整数大小的比较)，(ai57那么ai-55因为1至U 9和A,B, C 的 Aske 码有差别。) 从而实现字符向整数的转变。(3 )通过fo循环把M进制数的每一位取出来用t保存，倒序取出的先取得A，再取2(4 ) P=1，然后嵌套的for循环用来求每一

7、位对应的权。例如A对应的p=0,2的权p=1。用 for(j=0;jn-iT;j+) p=p*x;求 p，循环的条件是 jn-iT;(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%

8、q; i=i+1； N=N/q;)其中十进制数 N除以q的余数正好对应数组 HexNum 的某一元素，例如 42 除以 16，余下 2，对应 HexNum 中 2，余下 10 对应数组 中的 A 。(3) 倒序输出余数；定义变量 m存储数组a中余数的元素的个数，用化彳盾环从i=m+1 ；开始输出也就是从数组*a【】中最后一个余数开始输出。直到i=0； F本函数定义了两个数组一个存储1-9， A到 这16个字符的另一个存储10进制数除以q进制数的余数的。3.void prind_d(in t n,int递归的方法把十进制转换成其他进制数。(1 )定义一个递归函数用swi tch语句判断转换成的四

9、种情况(2) Case 10，输入十进制数n，判断是否0,如果是则put char(-；然后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(st

10、ack&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_SIZEs.base=(int *)realloc2 )入栈 void push(stack &s,char e)判断是否栈满 s.top-s.base=s.s

11、tacksize ；如果栈满另外开辟新的空间)，并把首地址赋给 s.base 。栈的栈顶指针为 s.top=s.base+s.stacksize; 栈的容量变为：s.s tacksize+二STACKINCREMENT；并把新的元素赋给栈顶指针，*s.t op二e;栈顶指针加e ，然后减 1 ，判断1， s.top =s.top+1 。3 )出栈。 While 语句判断 s.top!=s.base 时结束，栈顶指针的值赋给e9 是否成立，如果是则以字符的形式输出输出否则以整数的形式输出。4.封装在三个函数中Array()， Stack()，Prind()把M进制数转换为其他进制数。(1)Arr

12、ay(), Prind()。输入M进制数x然后转换成十进制数m，分别再用void array(intN)， void prind_d(int n,int这两个函数转换成y进制数。(2) Stack()o temp=(int)N%n，求余数，并入栈，push(s, temp),但当 temp9 时要强制转换 成字符类型： temp=(char)(temp+55);然后倒序出栈 pop(s) o5,。主函数main ()用一个switch语句来选择用哪种方法，n=l，用数组，n=2用递归，n=3用栈。其他输入输入错 误。3.主要函数的程序流程图，实现设计中主程序和其他子模块的算法，以流程图 的形式

13、表示。开始chara 50int n,j,i,sum=0,t二 p=1;int x;开始输入一个数x输入Nchar HeNum=-0123456789ABCDEF;char a1000 = 0;cin.ge t();get s(a);n=s trlen(a);i=n-1I是i=ai二HexN umN%q;i=i+1;N=N/q;是p=1;4=0;printf (cpri ntf (c，ai否,aiIF否j=0是p=p *xt 二ai-48一 p=1是coutendl;coutendl; j j+sum+二t*p;prind_d(n/2,2);put char(n%2+0)break;开始int

14、 n,int cswit ch(c)prind_d(int n,int c)if(n/16)prind_d(n/16,16);putchar(chn%16);if(n/8) prind_d(n/8,8);put char(n%8+0);break;4.画出函数之间的调用关系图。调试分析:1. 实际完成的情况说明(完成的功能，支持的数据类型等)； 可以完成M进制数X到其他进制数的转换2. 程序的性能分析，包括时空分析；程序的时间复杂度为o( n),空间复杂度为0(1)；3. 上机过程中出现的问题及其解决方案；实验过程中要在数组方法中出现问题：保存余数的数组char a1000要都赋予值 0，否则

15、在倒序的是否会因为系统自动分配的未知数值出现问题char a1000。问题2在把其他进制数转换成十进制数的时候，1到9的ASCII值(t二ai-48与ABCF字符的ASCII码(t二ai-35的值有区别，4. 程序中可以改进的地方说明；试验中还是又可以改进的地方的，例如把小数转化的部分加进去。增强程序的容错性主要在输入 输出方面5. 程序中可以扩充的功能及设计实现假想。可以直接实现把 M进制数转换成N进制数，而不是通过十进制这个桥梁。五、测试结果o= 2 x： J01010:42的进制数卓址B1 应的亠进审娄栈方法:茨:行也芻换16 运化进进转N= 法要一的人成 方入入应叢数faran42进数

16、的制：lb递归方法:输入要转化番入要转蚀进制数：2 输丁个迸料数口 101010对应的+$1蠶42：2 A壽按键选择 用户手册：，再按ct rl+F5运行，会出现一个界面用visual打开源文件，按ctrl+F7进行编译* ”欢迎使用本程序戈本程序完成数制转换n进制数转换成N进制数-K -H- M= -幘按键选择m rr-JW W -r -rw wi-mi w再按菜单操作及可七.体会与自我评价实验设计中我学到了模块化处理问题，找到问题，并一个个解决，例如把三种方法封装在三个函数中。但在也存在着一些问题主要是16进制上，它包括一些AB等一些字母，所以要进行 特别处理。例如在十进制的转化中要分开处

17、理if(ai=57)/比较大小都要换成整型的t二ai-48;elset=ai-55;if(i=n-l)解决数制转换问题时，如果所给的数值不是用十进制表示的，一般用一个字符型数组来 存放。数组的每个元素分别存储它的一位数字。然后按位转换求和，得到十进制表示；再十进制表示转换成所求的数制表示。转换的结果也用一个字符型数组表示，每个元素表示 换结果的一位数字。根据数制表示中相邻位的基数关系，可以把不同的数制分成两类。一 类数制表示中，相邻位的基数是等比关系，例如我们熟悉的十进制表示。另一类数制表示中，相邻位的基数 不等比的。例如在时间表示中，从秒到分采用 60 进进制；从月到年采用 12 进制。把一

18、个 数值从数制 B 的表示 bmbm-1b m-2 . b1 转换成十进制表示 dnd n-1d n-2 . d1 比较简 单。假设数制B中，第i位的基数为basei(l ? 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，余数即为bl ；将 dnd n-1d n-2 . d1 和C相除的结果再除以 q，余数即为b；直至计算

19、出为 bm止。数制 M 中相邻数字的基数不等比。需要先判断 dnd n-1d n-2 . d1 在数制M中需要的 位数 m ，然后从高位到低位依次计算 bm 、 bm-1 、 b m-2 、 .、. b1 。源代码：#include using namespace std;#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structint *base;int *top;int stacksize;stack;/ int getdex()char a50;int n,j,i,sum=0,t=0

20、,p=1;int x;printf输入要转化M进制数：)；scanf(%d,&x);prin tf输入一个进制数 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;jn-i-1;j+) p=p*x; sum+=t*p;prin tf对应的十进制数：dn，sum);return sum;/ void array(int N)char HexNum = 0123456789ABCDEF;char a1000

21、=0;prin tf输入一个要转化的进制数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);coutendl;/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 pus

22、h(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 ，否

23、则返回 ERRORint e;/ printf输出相等的一个%d进制数，&n);while(s.top!=s.base)e=*-s.top;if (e9)printf(%c，e);elseprintf(%d，e);/ void prind_d(int n,int c)switch(c)case 10 :if (n0)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 (n9) temp=(char)(temp+55); push(s,temp);N=N/n;prin tf转换成的N=%d进制数:n,n);pop(s); printf(n);/void Prind()prin tf递归方法的运行结果：n);int c,m;put s(输入要转化的进制数N)；cinc;m=getdex();coutN:;prind_d(m,c);coutn;switch (n)case 1:Array();continue;case 2:Stack();continue;case 3:Prind();continue;defaul t :print输入有误)；while(1);