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

1、大学数据结构课程设计报告题目： 数制转换问题 院（系）：计算机工程学院 学生姓名: 班级： 学号: 起迄日期: 6月20日6月29日指导教师: 指导教师评语： 成绩： 签名： 年 月 日20102011年度 第 2 学期 一、需求分析1.问题描述：任意给定一个m进制的数x，求出此数x的10进制值，输出此数的10进制值，并返回此数的10进制值，计算实现对x向任意的一个非m进制的数的转换。 2.基本功能设计一个函数int xtoten()，任意给定一个m进制的数x，求出此数x的10进制值，输出此数的10进制值，并返回此数的10进制值。设计一个函数void tentox(int x), 将函数int

2、 xtoten()的返回值x传入void tentox(int x)，计算实现对x向任意的一个非m进制的数的转换。3.输入输出设计实现函数int xtoten()输入是字符型数据，输出是double型数据,范围-99999999.999999999999999.999999.设计实现函数void tentox(int x)输入是double型数据，输出是字符型数据, 范围是整数部分30位以内,小数部分10位以内。整数部分可以包括负号，数字，大写字母，小数部分可以包括数字，大写字母。x的进制m应是大于1的整数，转成的其他进制应在2 36之间。输出时，有数则输出，无小数时不输出无意义的0。二、 概

3、要设计1.设计思路：解决问题的思路概述，拟采用的算法的简介。用户输入的数据可能是正数也可能是负数，可能包含小数部分，因而需分开处理。数组实现的算法：求x的十进制：将数值从左向右分别取出，第一数乘以进制加第二个数，得到的数再乘以进制加第三个数，依次类推，直到最后一个数。将小数部分从左向右分别取出，第一个数除以进制，加上第二个数除以进制的平方，依次类推，最后一个数进制的a次方，a为小数的位数。转成其他进制：将十进制数取出，整数部分除以进制取整替代原整数，将余数存入数组，反复取整存余，直到整数部分为0，将数组逆序输出。将小数部分乘进制取整，依次输出得到的整数。栈实现的算法：求x的十进制：将数值从左向

4、右分别取出压栈，弹出时将第一个数乘1加第二个数乘进制加第三个数乘进制的平方，依次类推直到最后一个数。将小数部分入栈，将第一个数除以进制加第二个数除以进制，得到的数加第三个数除以进制，依次类推直到最后一个数。转成其他进制：将十进制数取出，分解为整数部分和小数部分，整数部分除以进制取余压栈，用商代替原整数部分，反复执行，直到整数部分为0。出栈并依次输出各数。将小数部分乘进制取整，依次输出得到的整数。 2.数据结构设计：数据结构及其定义为线性逻辑结构，存储结构为顺序。原因是没有插入和删除工作，用顺序结构合适。定义程序中用到的抽象数据类型：抽象数据类型线性表的定义如下：adt seqstack 数据对

5、象：d=ai| ai elemset,i=1,2,3，n,n0数据关系：r1=<ai-1,ai>| ai-1,ai d,i=1,2,3,，n基本操作：setemptystack(seqstack *s)初始条件：栈s已存在。操作结果：将栈置空。 isemptystack(seqstack *s)初始条件：栈s已存在。操作结果：判断栈是否为空，是返回1，否返回0。push(seqstack *s,int item)初始条件：栈s已存在。操作结果：将item压入栈中。pop(seqstack *s)初始条件：栈s已存在。操作结果：弹出栈尾元素，并将其返回。3.软件结构设计：模块可划分为

6、两部分：第一部分：将x转化为十进制数输出；实现函数double xtoten（）；第二部分：将十进制数转化为其它进制的数，实现函数void tentox（double x）。模块的层次结构及调用关系：本程序人机界面为运行窗口：三、 详细设计 1 数组部分定义：char *p,s40,*q,t40;栈的定义： typedef struct char datemax_size; int top; seqstack;2主函数和其他函数的伪码算法；void main() double md; md=xtoten(); while(1) tentox(md); 用数组实现求出此数x的10进制值的算法：d

7、atatype xtoten()/*任意进制转化为十进制*/ datatype *p,s40,*q,t40; datatype i=1,flag=0; datatype zheng=0,xiao=0,m; p=s; q=t; cout<<"请输入x的进制：" cin>>m; if(m<2) /进制范围判断 cout<<"您输入的进制越界，程序退出"<<endl; exit(1); cout<<"请输入x的整数部分：" fflush(stdin); /刷新输入流 gets

8、(p); if(*p='-') /负数判断 p+; flag=1; /flag为是不是负数的标志，为负数，则赋成1 while(*p)!='0') if(*p>=m+'0'&&m<10) /错误判断 cout<<"您输入的以上数据错误，程序退出"<<endl; exit(1); if(*p>=m+'a'-10) /错误判断 cout<<"您输入的以上数据错误，程序退出"<<endl; exit(1); if(*

9、p>='0'&&*p<='9') /计算整数部分 zheng=zheng*m+*p-'0' p+; else if(*p>='a'&&*p<='z') zheng=zheng*m+*p-'a'+10; p+; else cout<<"您输入的以上数据错误，程序退出"<<endl; exit(1); if(zheng>999999999|zheng<-999999999) /整数范围判断 c

10、out<<"数值过大，超过计算范围，程序退出"<<endl; exit(1); cout<<"请输入x的小数部分：" gets(q); while(*q)!='0') /计算小数部分 if(*q>=m+'0'&&m<10) /错误判断 cout<<"您输入的以上数据错误，程序退出"<<endl; exit(1); if(*q>=m+'a'-10) /错误判断 cout<<"

11、您输入的以上数据错误，程序退出"<<endl; exit(1); if(*q>='0'&&*q<='9') xiao+=(*q-'0')/(m*i); q+;i*=m; else if(*q>='a'&&*q<='z') xiao+=(*q-'a'+10)/(m*i); q+;i*=m; else cout<<"您输入的以上数据错误，程序退出"<<endl; exit(1); c

12、out<<"x的十进制是：" if(flag=1) zheng=0-zheng; xiao=0-xiao; if(xiao=0) /判断是否有小数，若没有，则不输出无意义的0 cout<<zheng; else printf("%-16.6f",zheng+xiao); /最多显示6位小数 cout<<endl; return zheng+xiao; 用数组实现求出此数x的非m进制值的算法源程序：void tentox(datatype x) /*十进制转化为其他进制*/ datatype space,xiao; da

13、tatype * zheng=&space; datatype buf40; datatype m,tem,i,part,temp10,flag=0;if(x<0) /判断x是否为小数，若是，则取x相反数，并将flag赋1 flag=1; x=0-x; xiao=modf(x,zheng); /取出x的小数部分赋给xiao,把整数部分存到zheng指向的单元 tem=*zheng; cout<<"请输入要将x转成的进制：" cin>>m; if(m>36|m<2) /进制范围判断 cout<<"您输入的

14、进制越界，程序退出"<<endl; exit(1); cout<<"x的"<<m<<"进制是：" if(flag=1) cout<<'-' for(i=0;i<100&&tem>0;i+,tem/=m) /计算整数部分 part=tem%m; if(part>=10) bufi='a'+part-10; else bufi=part; -i; while(i>=0) /格式控制 if(bufi>=10) co

15、ut<<bufi-; else cout<<int(bufi-); if(xiao!=0) if(x>0&&x<1) /格式控制 cout<<"0." else cout<<'.' for(i=0;i<10;i+) /计算小数部分 xiao*=m; xiao=modf(xiao,zheng); /取出xiao的小数部分赋给xiao,把整数部分存到zheng指向的单元 tempi=*zheng; for(i=9;i>=0;i-) /将无意义的0设标志，在后面的输出中忽略之

16、if(tempi=0) tempi=-1; if(tempi>0) break; i=0; while(tempi!=-1&&i<10) /输出有意义的小数，最多10位 if(tempi<10) cout<<tempi; if(tempi>=10) cout<<char(tempi+55); i+; cout<<endl;置栈空、判栈空、入栈、出栈的算法源程序：void setemptystack(datatype *s) /*置栈空*/ s->top=-1; datatype isemptystack(data

17、type *s) /*判栈空*/ if(s->top=-1) return ok; return fause; void push(datatype *s, datatype item) /*入栈*/ s->top+; s->dates->top=item; datatype pop(datatype *s) /*出栈*/ datatype temp; temp=s->dates->top; s->top-; return temp; 用栈实现求出此数x的10进制值的算法源程序：datatype xtoten() /*任意进制转化为十进制*/ data

18、type *p,s40,*q,t40; datatype i=1,j=1,flag=0; datatype zheng=0,xiao=0,m; datatype s1,s2; setemptystack(&s1); /栈置空 setemptystack(&s2); /栈置空 datatype part1,part2; p=s; q=t; cout<<"请输入x的进制：" cin>>m; if(m<2) /进制范围判断 cout<<"您输入的进制越界，程序退出"<<endl; exit(

19、1); cout<<"请输入x的整数部分：" fflush(stdin); gets(p); if(*p='-') /负数判断 p+; flag=1; /flag为是不是负数的标志，为负数，则赋成1 while(*p)!='0') if(*p>=m+'0'&&m<10) /错误判断 cout<<"您输入的整数部分错误，程序退出"<<endl; exit(1); if(*p>=m+'a'-10) /错误判断 cout<

20、<"您输入的整数部分错误，程序退出"<<endl; exit(1); push(&s1,*p); /入栈 p+; while(!isemptystack(&s1) /计算整数部分 part1=pop(&s1); /出栈 if(part1>='0'&&part1<='9') zheng+=(part1-'0')*j; j*=m; else if(part1>='a'&&part1<='z') zhen

21、g+=(part1-'a'+10)*j; j*=m; else cout<<"您输入的整数部分错误，程序退出"<<endl; exit(1); if(zheng>999999999|zheng<-999999999) /整数范围判断 cout<<"数值过大，超过计算范围，程序退出"<<endl; exit(1); cout<<"请输入x的小数部分：" gets(q); while(*q)!='0') if(*q>=m+'

22、;0'&&m<10) /错误判断 cout<<"您输入的小数部分错误，程序退出"<<endl; exit(1); if(*q>=m+'a'-10) /错误判断 cout<<"您输入的小数部分错误，程序退出"<<endl; exit(1); push(&s2,*q);q+; /入栈 while(!isemptystack(&s2) /计算小数部分 part2=pop(&s2); /出栈 if(part2>='0'

23、&&part2<='9') xiao=xiao/m+(part2-'0')/m; else if(part2>='a'&&part2<='z') xiao=xiao/m+(part2-'a'+10)/m; else cout<<"您输入的小数部分错误，程序退出"<<endl; exit(1); cout<<"x的十进制是："if(flag=1) /当x为负数时，对zheng和xiao取相反数

24、 zheng=0-zheng; xiao=0-xiao; if(xiao=0) cout<<zheng; else printf("%-16.6f",zheng+xiao); cout<<endl; return zheng+xiao; 用栈实现求出此数x的非m进制值的算法源程序：datatype tentox(double x) /*十进制转化为其他进制*/ datatype space,xiao; datatype *zheng=&space; datatype ch; datatype part,m,i,tem,temp10,flag=

25、0; seqstack s1; setemptystack(&s1); /栈置空 if(x<0) flag=1;x=0-x; xiao=modf(x,zheng); /取出x的小数部分赋给xiao,把整数部分存到zheng指向的单元 tem=*zheng; cout<<"请输入要将x转成的进制：" cin>>m; if(m>36|m<2) /进制范围判断 cout<<"您输入的进制越界，程序退出"<<endl; exit(1); while(tem) push(&s1,te

26、m%m); /入栈 tem=tem/m; cout<<"x的"<<m<<"进制是：" if(flag=1) /当x小于0时，输出-号 cout<<'-' while(!isemptystack(&s1) /计算整数部分 part=pop(&s1); if(part>=10) ch='a'+part-10; cout<<ch; else cout<<part; if(xiao!=0) if(x>0&&x<

27、1) /格式控制 cout<<"0." else cout<<'.' for(i=0;i<10;i+) /计算小数部分 xiao*=m; xiao=modf(xiao,zheng); /取出xiao的小数部分赋给xiao,把整数部分存到zheng指向的单元 tempi=*zheng; for(i=9;i>=0;i-) /将无意义的0设标志，在后面的输出中忽略之 if(tempi=0) tempi=-1; if(tempi>0) break; i=0; while(tempi!=-1&&i<10)

28、 /输出有意义的小数，最多10位 if(tempi<10) cout<<tempi; if(tempi>=10) cout<<char(tempi+55); i+; cout<<endl; 3.主要函数的程序流程图，实现设计中主程序和其他子模块的算法。用数组实现进制转换的算法流程图： 用栈实现进制转换的算法流程图： 4. 画出函数之间的调用关系图。四、 调试分析 1.实际完成的情况说明（完成的功能，支持的数据类型等）；任意给定一个m进制的数x，求出此数x的10进制值，输出此数的10进制值，并返回此数的10进制值。计算实现对x向任意的一个非m进制的

29、数的转换。支持字符型，double型。2.程序的性能分析，包括时空分析；算法中，求得的十进制数为double型的，由于该十进制数是中间数，承上启下，因而后面求得的各个进制数的精度受限于该十进制数。该十进制数范围在-10000000001000000000之间。int xtoten()时间复杂度o（n），n为输入字符的个数。空间复杂度o(char*80).void tentox(int x) 时间复杂度o（n），n为x字符的个数。空间复杂度o(char*50).3.上机过程中出现的问题及其解决方案；自己感觉程序没错误，编译器也没有报错，但运行时提示“unexpected handled”异常，反

30、复检查程序，我发现有一处未将栈置空，改正后程序正常运行。当输入负数时，程序运行结果错误，经仔细检查，我发现自己只将整数部分取反，没将整数部分取反。4.程序中可以改进的地方说明； 程序中，十进制数为中间数，承上启下，且为double型。所以，程序输出的十进制数和其他进制数的精度都受double型精度的限制，无法再提高。使用long double型数据可以提高精度，但是modf（）函数的参数和返回值都为double型，因而无法使用long double型数据进一步提高精度，所以可以使用<math.h>中，精度更高的数据类型和函数，以进一步提高精度。这里需要注意的是，由于计算机中数据是以

31、二进制的形式存储的，所以十进制小数转换为其他进制时，大多情况下会有误差，因而精度太高时，计算机本身无法避免的误差会显现出来，造成数据失真，所以小数部分输出的位数不能过多，应根据实际情况，合理选取。5.程序中可以扩充的功能及设计实现假想。 程序中将十进制转化为其他进制时，因为是几进制的数据就要有几个字符来代表它的各个数位，所以我选取了，09，az，共36 个字符来表示，最多到36进制，其实还可以增加字符的个数，以表示更大的进制，由于更大的进制不常用，所以我没有扩充其功能，其实可以扩充的，只要找到更多的字符，完全可以使程序将十进制的数转化为任意进制的数。五、测试结果六、用户手册1双击shuzu.c

32、pp和zhan.cpp文件，单击菜单“组建-运行”，运行程序。2输入x的进制，按回车键。3输入x的整数部分，按回车键。4输入x的小数部分，按回车键。5输入要将x转成的进制，按回车键。6反复执行第五步。七、体会与自我评价 课程设计过程的收获:在课程设计开始时，我发现程序中有一个算法需要将十进制数分解为整数部分和小数部分分别计算。刚开始我没找到解决方法，后来我查阅了c程序设计后面的<math.h>库函数，找到了程序中很重要的一个函数double modf（double val，double* iptr），这个函数可以把双精度数val分解为整数部分和小数部分，整数部分存入*iptr指向的

33、单元，解决了困扰我一天的难题。通过这个过程，我提高了自主学习能力。在编写程序时，遇到问题先自己思考解决方法，并上机验证。如果不能解决问题，就再换一种解决方案。实在无法解决时，虚心请教老师和同学，我丰富了自己的知识，提高了编程能力。在程序编写时，由于数组结构接触比较早，并且算法较为简单，因而完成比较早。栈结构虽然数据结构课程刚学过，但自己理解和使用能力欠缺，犯了很多错误后，才调试成功。例如：自己感觉程序没错误，编译器也没有报错，但运行时提示“unexpected handled”异常，反复检查程序，我发现有一处未将栈置空，改正后程序正常运行。这让我认识到使用指针时，需要特别注意为其分配内存空间，

34、否则即使程序通过编译，在执行时也会报错。这种错误往往使人一头雾水，错误比较隐蔽，只有在编写程序时留心，才能尽量避免此类错误。程序实现初步功能后，我想增加其功能。比如说能计算负数。但更改过的程序运行时出错。仔细检查后，我发现自己只将整数部分取反，未将小数部分取反，改正后，程序正常运行。容错处理过程中，由于既要判断数值是否超过进制，还要判断是否输入了非法字符，但我想在一个模块中实现这两个判断，结果导致程序出错。这时我想到老师给我们讲的分而治之的思想，分开处理。第一个判断也为第二个判断奠定了基础，两个判断相辅相成，成功实现了容错处理。通过对误操作的处理尝试，我体会到程序编写时，一定要综合考虑各个方面

35、，编写出健壮的程序十分不易。在学习数据结构这门课程时，感觉自己学会了，平时缺乏上机练习。这次课程设计让我发现了自己的很多不足，让我认识到：只有在不断的实践中才能发现自己的问题，并不断提高自己的能力。数据结构这门课程中，介绍了很多重要的结构，比如说，链表栈队列，树，图等结构，还介绍了很多有用的算法，比如查找，排序等。这些知识在今后的学习工作中，都要经常用到，十分重要。因而要不断复习已经学过的知识，提高自己的应用能力。源代码：数组 #include<iostream> #include<cmath> using namespace std; double xtoten()

36、/*任意进制转化为十进制*/ char *p,s40,*q,t40; int i=1,flag=0; double zheng=0,xiao=0,m; p=s; q=t; cout<<"请输入x的进制：" cin>>m; if(m<2) /进制范围判断 cout<<"您输入的进制不合法，程序退出"<<endl; exit(1); cout<<"请输入x的整数部分：" fflush(stdin); /刷新输入流 gets(p); if(*p='-') /负

37、数判断 p+; flag=1; /flag为是不是负数的标志，为负数，则赋成1 while(*p)!='0') if(*p>=m+'0'&&m<10) /错误判断 cout<<"您输入的整数部分错误，程序退出"<<endl; exit(1); if(*p>=m+'a'-10) /错误判断 cout<<"您输入的整数部分错误，程序退出"<<endl; exit(1); if(*p>='0'&&

38、;*p<='9') /计算整数部分 zheng=zheng*m+*p-'0' p+; else if(*p>='a'&&*p<='z') zheng=zheng*m+*p-'a'+10; p+; else cout<<"您输入的整数部分错误，程序退出"<<endl; exit(1); if(zheng>999999999|zheng<-999999999) /整数范围判断 cout<<"数值过大，超过计算

39、范围，程序退出"<<endl; exit(1); cout<<"请输入x的小数部分：" gets(q); while(*q)!='0') /计算小数部分 if(*q>=m+'0'&&m<10) /错误判断 cout<<"您输入的小数部分错误，程序退出"<<endl; exit(1); if(*q>=m+'a'-10) /错误判断 cout<<"您输入的小数部分错误，程序退出"<&

40、lt;endl; exit(1); if(*q>='0'&&*q<='9') xiao+=(*q-'0')/(m*i); q+;i*=m; else if(*q>='a'&&*q<='z') xiao+=(*q-'a'+10)/(m*i); q+;i*=m; else cout<<"您输入的小数部分错误，程序退出"<<endl; exit(1); cout<<"x的十进制是：&q

41、uot; if(flag=1) zheng=0-zheng; xiao=0-xiao; if(xiao=0) /判断是否有小数，若没有，则不输出无意义的0 cout<<zheng; else printf("%-16.6f",zheng+xiao); /最多显示6位小数 cout<<endl; return zheng+xiao; void tentox(double x) /*十进制转化为其他进制*/ double space,xiao; double* zheng=&space; char buf40; int m,tem,i,part,

42、temp10,flag=0; if(x<0) /判断x是否为小数，若是，则取x相反数，并将flag赋1 flag=1; x=0-x; xiao=modf(x,zheng); /取出x的小数部分赋给xiao,把整数部分存到zheng指向的单元 tem=*zheng; cout<<"请输入要将x转成的进制：" cin>>m; if(m>36|m<2) /进制范围判断 cout<<"您输入的进制不合法，程序退出"<<endl; exit(1); cout<<"x的"

43、;<<m<<"进制是：" if(flag=1) cout<<'-' for(i=0;i<100&&tem>0;i+,tem/=m) /计算整数部分 part=tem%m; if(part>=10) bufi='a'+part-10; else bufi=part; -i; while(i>=0) /格式控制 if(bufi>=10) cout<<bufi-; else cout<<int(bufi-); if(xiao!=0) if(x&g