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

.z.目录TOC\o"1-3"\h\u185971前言1321061.1设计背景和意义114281.1.1数据结构简介 242501.1.2选择算法的原因 2391.2设计的原理和内容2199822正文2254432.1设计的目的和意义2266852.2目标和总体方案213642.3设计方法和内容3318852.3.1模块划分3304842.3.2主要程序模块3173672.4程序的设计思想和内容6209172.4.1用数组实现该问题641202.4.2用栈实现该问题640092.5设计创新和关键技术6186172.6程序调试6323662.7程序流程图7251092.8结论829308参考文献929218附录 91前言1.1设计背景和意义1.1.1数据结构简介数据结构是计算机程序设计的重要理论设计基础，是一门综合性的专业基础科。数据结构是研究数据之间的相互关系，也即数据的组织形式的一门科学。它不仅是计算机学科的核心课程，数据结构是计算机存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率的算法。在计算机科学中，"数据结构”不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。1.1.2选择算法的原因在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。1.2设计的原理和内容设计了一个10进制转换其它进制(36进制以内)及逆转换的软件，该软件具有简单的将10进制数转换成2、8、16进制数以及较复杂的高进制数的转换和逆转功能。本软件采用C语言编写以VC++作为软件开发环境，采用顺序栈存储方式来存储运算中的数位，借助栈后进先出的特点，易于结果输出。操作简单，界面清晰，易于为用户所接受。2正文2.1设计的目的和意义我们是计算机科学与技术专业的本科生，《数据结构》是我们重要的必修课程。当代社会学要大学培养出理论扎实，动手实践能力强的大学生。所以，本次课程设计的目的就在于通过一次实践性的活动加深对这门课程的理解，使我们在感性的认识上进一步升华为理性的认识。为后继课程的学习打下坚实的基础。通过本次数据结构课程设计，我们基本上掌握了课程设计流程，还掌握了一些知识和技能，这对于我们以后对于数据结构的学习有了很大的帮助和提高，加深了我们对数据结构的理解，，为今后的学习打下了坚实的基础。同时也提高了我们对于编程这方面的能力。2.2目标和总体方案本次设计的目标在于设计出一个能够实现数制转换的程序，于是特制订了一个总体的方案：程序的设计第一步：查阅有关数据结构数制转换操作的资料，用半天的时间。第二步：设计这个项目的整体架构和算法。用一到两天的时间。第三步：使用C语言程序设计程序语言进行算法的描述。两天的时间。程序的调试进行程序的调试。用一天。最后，我在完整的整理一遍，完成课设。2.3设计方法和内容2.3.1模块划分2.3.1.1用数组实现该问题（1）i,j,y,n,s,m,r,reminder,*是定义的全局变量，初始值都为０；（2）D2M(intg,inth)是实现十进制数转换为M进制数的函数；（3）M2D()是实现M(仅指二进制数和八进制数)进制数转换为十进制数的函数，并在其中调用D2M(intg,inth)实现向非M进制数的转换；（4）H2D(intf)是实现十六进制数转换为十进制数的函数，并在其中调用D2M(intg,inth)实现向非十六进制数的转换；（5）voidmain()是主函数，功能是给出测试的数据，并在特定条件下调用D2M()函数和M2D()函数。2.3.1.2用栈实现该问题（1）SqStack定义栈，说明base为栈底指针，top为栈顶指针，stacksize为栈容量；（2）intInitStack(SqStack&S)到intDestroyStack(SqStack&S)六大模块分别表示构造一个空栈、用ｅ表示栈元素、插入元素、删除元素、判断栈是否为空以及摧毁栈；（3）SqStackS是指定义栈S；（4）D2M(inta,intb)的功能是将十进制数转换成M进制的函数；（5）M2D()的功能是M进制转换为十进制的函数；（6）voidmain()是主函数。其功能是输入需要测试的数据以及需要转换的进制，并在特定情形下调用D2M()函数和M2D()函数，而且实现M进制数向转任意非M进制数的换。2.3.2主要程序模块（1）：D2M(intg,inth){ intc[N]; i=0; reminder=g%h; g=g/h; if(reminder>9) { c[i]=reminder+55; i++; }else { c[i]=reminder; i++; } if(g>0) D2M(g,h); for(j=i-1;j>=0;j--) if(c[j]>=65) printf("%c",c[j]); else printf("%d",c[j]); return0;}自定义函数D2M用于在用数组实现该问题的程序中十进制数转换为其他进制数（2）：M2D(inte){inta[N];printf("请输入%d进制位数:",m); scanf("%d",&n); printf("请输入%d进制的每位并使每位用空格隔开:",m); for(i=0;i<n;i++)scanf("%d",&a[i]); for(i=n-1;i>=0;i--) { y+=(int)pow(e,j)*a[i];//强制类型转换，以免造成数据丢失 j++; } printf("请输出所得的10进制的结果:"); printf("%d",y);printf("\n需要转换的进制M:"); scanf("%d",&s); printf("请输出转换成%d进制的结果:",s); D2M(y,s); return0;}自定义函数M2D用于在用数组实现该问题的程序中二进制和八进制数转换为十进制数，并且转换为其他进制数（3）：H2D(intf){ intb[N]; printf("请输入%d进制位数:",m); scanf("%d",&n); printf("请输入%d进制的每位并使每位用空格隔开:",m); for(i=0;i<n;i++)scanf("%*",&b[i]); for(i=n-1;i>=0;i--) { y+=(int)pow(f,j)*b[i];//强制类型转换，以免造成数据丢失 j++; } printf("请输出所得的10进制的结果:"); printf("%d",y); printf("\n需要转换的进制M:"); scanf("%d",&s); printf("请输出转换成%d进制的结果:",s); D2M(y,s); return0;}自定义函数H2D用于在用数组实现该问题的程序中十六进制数转换为十进制数，并转换为其他进制数（4）：D2M(inta,intb){ 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); } return0;}自定义函数D2M用于在用栈实现该问题的程序中十进制数转换成其他进制数（5）：M2D()其他进制数转换为十进制数{charc[1000]; printf("请输入需要转换的数的位数:"); scanf("%d",&n); printf("请输入需要转换的数的每位并用空格隔开:");for(i=0;i<n;i++) { scanf("%*",&c[i]); Push(S,c[i]); }i=0; while(!StackEmpty(S)) { Pop(S,e); y+=(int)pow(m,i)*e; i++; } printf("转换成10进制的结果是:"); printf("%d",y); return0;}自定义函数M2D用于用栈实现该问题的程序中其他进制数转换为十进制数2.4程序的设计思想和内容2.4.1用数组实现该问题D2M()函数和M2D()函数是实现该问题的主要函数。D2M()函数是实现十进制转换为其它进制的函数，它是将输入的十进制数ｘ取首先对需要转换的进制M取余，然后再对其取整，接着通过递归调用D2M()函数依次将得到的整数部分依次先取余后取整，并将所得的余数依次存入一个数组中，然后逆向取出数组中的元素，即得到转换后的结果。而M2D()函数则是实现其他进制M转换为十进制，并将其转换为非M进制的数。M进制转十进制则是从该M进制数的最后一位开始算，依次列为第０、１、２…ｎ位并分别乘以M的０、１、２…ｎ次方，将得到的次方相加便得到对应的十进制数，再调用D2M()函数将其转换为非M进制的数。2.4.2用栈实现该问题同样是利用D2M()和M2D()两个函数实现。两个函数的思想同利用数组实现时相同。只是栈具有后进先出的性质，故其用Pop()取数较数组的逆向取数方便些。2.5设计创新和关键技术利用了栈的先进后出特点来满足数制转换中从最后一位余数依次取出的要求，利用数组的特性依次存储取于数运算的结果余数，再从该数组的最后一个元素从后往前依次取出即为转换后的数。2.6程序调试1十进制数527的调试情况如下：2十六进制数1A2C9的调试情况如下：2.7程序流程图数组数组栈输入*转换的位数输入需要转换的数输入将转换的进制数输出结果开始输入需转换的数的进制2.8结论通过本次课程设计，我认识到熟练掌握基础算法的重要性，对栈的含义及其基本算法有了更好的理解和应用。栈"先进后出”的算法加上Push()和Pop()方便了对要转换的数进行读取,和对转换后数倒置的输出。在编写过程中常遇到的不少问题，例如，变量类型的转换和ASCII码转义字符的应用，变量的定义和*围，算法循环语句的退出条件等，我通过不断调试，翻阅课本和网上搜索材料得到了解决，也认识到这些细节上的处理更当注意。在调试时,学会了在有问题的地方注释并能经常使用printf()函数测试输出结果。在测试时对测试数据的选取更当考虑全面能检测错误输入并进行提示。通过这次实验我学会运用课本和老师平时讲授知识进行切身实践，通过网络搜索学到了新的库函数，提高了我实际编写程序的能力。参考文献[1]严蔚敏，*伟民编著.数据结构（C语言版）.清华大学，2006年[2]李春葆，曾慧，*植民编著.数据结构程序设计题典.清华大学，2002年[3]郭翠英编著.C语言课程设计案例精编.中国水利水电，2004年[4]谭浩强编著.C程序设计.清华大学，2005年[5]许卓群，*乃孝，杨冬青，唐世渭编著.《数据结构》.高等教育，1988年[6]晋良颍编著.《数据结构》.人民邮电，2002年附录用数组实现：#include<stdio.h>#include<math.h>#defineN1000inti,j,y,n,s;intm,r,reminder;int*;//全局变量默认初始化为0，不必再赋0了D2M(intg,inth)//十进制数转换为其他进制数{ intc[N]; i=0; reminder=g%h; g=g/h; if(reminder>9) { c[i]=reminder+55; i++;}else { c[i]=reminder; i++; } if(g>0) D2M(g,h); for(j=i-1;j>=0;j--) if(c[j]>=65) printf("%c",c[j]); else printf("%d",c[j]); return0;}M2D(inte)//二进制和八进制数转换为十进制数,并这转换为其他进制数{ inta[N];printf("请输入%d进制位数:",m); scanf("%d",&n); printf("请输入%d进制的每位并使每位用空格隔开:",m); for(i=0;i<n;i++)scanf("%d",&a[i]); for(i=n-1;i>=0;i--) { y+=(int)pow(e,j)*a[i];//强制类型转换，以免造成数据丢失 j++; } printf("请输出所得的10进制的结果:"); printf("%d",y);printf("\n需要转换的进制M:"); scanf("%d",&s); printf("请输出转换成%d进制的结果:",s); D2M(y,s); return0;}H2D(intf)//十六进制数转换为十进制数，并转换为其他进制数{ intb[N]; printf("请输入%d进制位数:",m); scanf("%d",&n); printf("请输入%d进制的每位并使每位用空格隔开:",m); for(i=0;i<n;i++)scanf("%*",&b[i]); for(i=n-1;i>=0;i--) { y+=(int)pow(f,j)*b[i];//强制类型转换，以免造成数据丢失 j++; } printf("请输出所得的10进制的结果:"); printf("%d",y); printf("\n需要转换的进制M:"); scanf("%d",&s); printf("请输出转换成%d进制的结果:",s); D2M(y,s); return0;}voidmain(){ printf("请给定一个需转换的进制M(2or8or10or16):"); scanf("%d",&m); if(m==2||m==8)//二进制和八进制转换成十进制 M2D(m); elseif(m==16)//十六进制转换成十进制 H2D(m); elseif(m==10)//十进制转换成其它进制 { printf("请输入一个%d进制数:",m); scanf("%d",&*); printf("请输入需要转换成的进制M(2or8or16):"); scanf("%d",&r); printf("请输出转换成%d进制的结果:",r); D2M(*,r); } printf("\n");}用栈实现：#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<math.h>#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量inte,m,*,s,t;//*为要转换的十进制数，e为临时用的的int型变量intr,y,i,n;typedefstruct{int*base;//栈底int*top;//栈顶intstacksize;//栈容量}SqStack;intInitStack(SqStack&S){//构造一个空栈 S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int)); if(!S.base)e*it(0);//存储空间失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return0;}intGetTop(SqStackS,int&e){//若栈不为空，则用e返回S的栈顶元素，并返回0，否则返回1 if(S.top==S.base)return1; e=*(S.top-1); return0;}intPush(SqStack&S,inte){//插入元素e为新的栈顶元素 if(S.top-S.base>=S.stacksize){//栈满，追加存储空间 S.base=(int*)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base)return1;//存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return0;}intPop(SqStack&S,int&e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回0，否则返回1 if(S.top==S.base)return1; e=*--S.top; return0;}intStackEmpty(SqStackS){//若栈空，则返回1，否则返回0 if(S.top==S.base) return1; return0;}intDestroyStack(SqStack&S){//销毁栈S，栈S不再存在 free(S.base); S.top=NULL;//防止程序后面不小心使用了它 S.base=S.top; return0;}SqStackS;//定义栈SD2M(inta,intb)//十进制转换成其他进制的函数D2M(){ while(a) {