数制转换数据结构

页第一章课题背景1.1引言1.1.1课程设计目的在生活中我们经常会遇到各式各样的数制，例如2，8，10，16进制，其实数制之间的转换问题不仅仅是数学问题，还是我们计算机需要研究的范围之一。高速发展的现代社会，计算机浩浩荡荡地成为了人们生活中不可缺少的一部分，帮助人们解决通信，联络，互动等各方面的问题。计算机在处理数字是和人是不同的，计算机使用的是二进制，人们在日常生活中使用十进制，但是在一些特定场合使用其他进制的表示，所以需要进行不同进制之间的转换其中包括有数据结构，C语言中的递归算法与数组的存储问题。本设计在2，8，10，16进制之间，能实现对输入的任意数制进行相对应的数制转换。在此程序设计中我采用了C语言中的数组与递归的算法，以及数据结构中的栈，实现了如下功能：1.对输入的任意数制能够求出此数的10进制值2.实现在2，8，10，16进制之间对输入的任意数制x向任意的一个非M进制数的转换。3.至少用两种或两种以上的算法实现上述功能要求。在程序设计中，可以用使用很多种方法解决该问题。例如：数组、栈、递归。不同的方法实现转换的原理基本相同，只是代码的细节不同。在我的程序中不同的方法所需的函数在一个单独的头文件里面，便以管理和修改。第二章设计简介及设计方案论述2.1选题分析 2.1.1数组的结构为了处理方便，把具有相同类型的若干变量按有序的形式组织起来的一种形式。这些按序排列的同类数据元素的集合称为数组。由于处理简单的情况，最大的数字将不大于整形的范围，整形为4个字节，因此开辟的数组为33个元素。 2.1.2栈的结构 栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。在此程序中我首先定义了一个结构体，结构体中包含栈元素的首地址、栈顶位置、栈顶位置、栈的最大范围。栈元素的存储空间在程序中再动态开辟。和上面一样，栈的最大为33。 2.1.3递归的结构递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。在这个程序中，递归不需要自己定义存储空间，大量的减少了需要定义变量所需要的存储空间。第三章详细设计3.1算法说明在此程序的算法设计中，我采用了数组，栈，递归的算法。3.1.1数组的算法M进制转十进制：从该M进制数的最后一位开始算，依次列为第0、1、2...n位并分别乘以M的0、1、2...n次方，将得到的次方相加便得到对应的十进制数。由于输入的M进制的数可能出现字符，所以使用了字符数组进行存储。并在输入后将字符全部转换为数字，并存储到全局变量s数组里面，每个数组元素存储一位。result=0;i=0result=0;i=0i小于M进制的字符长度取出数组元素s[i]与M的i次方相乘，相乘结果加入result中，i自加1。Y函数结束N图3-1M进制转十进制处理流程图十进制转换为其他进制：首先取x对需要转换的进制n取余，然后再对其取整，将取到的余数存入数组中，然后重复上面的步骤，将得到的余数依次存入数组中，知道x变成0。然后将数组反向输出。输出的数可能大于10，所以进行了必要的判断。初始化数组元素位置i=0;初始化数组元素位置i=0;x>0?Yx除以n，余数存入数组，数组下标i后移，商赋值给x函数结束N3.1.2栈的算法 算法思路和上面基本相同，只是将取到的余数依次入栈，输出时只要依次出栈就行。3.1.3递归的算法 递归过程中不需要另外的存储取到的余数，只需要在递归返回时输出相应的结果就行。3.2变量设计 #defineMAX0x7fffffff定义了整形数的最大值，防止数字溢出。intm;用于表示输入的数据是哪个进制的数。chars[33];输入时用于存储输入的十进制数x的m进制表示。处理过程中用于存储m进制表示的每一位所代表的的数字。 intn;要将输入的m进制数转换成的进制。 intlen;输入的字符数据有多长。 注：其他变量在程序中均有说明。3.3函数功能设计表5-1程序中的函数函数功能intTurn10(intl);将m进制的数转换成十进制数voidTurnx(intx);将十进制的数转换成n进制数intCalcRecursion(intk,intc);将m进制转换成10进制voidRecursion(intx);将十进制数x转换成n进制数voidInitStack(PSTACKs);初始化栈voidPush(PSTACKs,intx);将一个元素压入栈中intPop(PSTACKs);取出栈顶元素voidUseStack(intx);将十进制数x转换成n进制数voidConvert(char*s);将输入的数据转换成数字第四章设计结果及分析4.1运行与调试说明及分析程序开始运行时提示用户按照规定的输入格式输入数据数据的进制不能超过36，因为36后不好表达。数据中也不能出现除a..z,A..Z,0..9之外的字符m进制数中的每一位不可能大于等于m，否则数据应该是错的。当数据输入正确时将给出不同进制之间的转换结果输出完成后，程序将正常结束。总结数据结构是一门纯属于设计的科目，它需用把理论变为上机调试。在学习科目的第一节课起，老师就为我们阐述了它的重要性。它对我们来说具有一定的难度。它是其它编程语言的一门基本学科。刚开始学的时候确实有很多地方我很不理解，每次上课时老师都会给我们出不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序，可是好多处的错误让人看的可怕，还看不出到底是哪里出现了错误，但是程序还是得继续下去，我多次请教了老师和同学，逐渐能自己找出错误，并加以改正。VC++6.0里检查错误有时候真是让你难以找到为什么错。经过了这次课程设计，现在已经可以了解很多错误的原因，这对我来说是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很是开心。在这一段努力学习的过程中，我的编程设计有了明显的提高。虽然程序中不是很完美，还未能实现对小数之间的数制转换问题，但是对于我来说已经不错了，今后还需继续努力。参考文献[1] 谭浩强.C语言程序设计教程.北京：清华大学出版社，2008[2] 严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社，2010[3]王晓东.计算机算法设计与分析.电子工业出版社，2007

附录1：源程序清单//程序名称：课程设计.c//程序功能：分别采用数组、栈、递归实现进制间的转换//程序作者：余岁//最后修改日期：2014-6-24#include<stdio.h>#include<string.h>#include<stdlib.h>#include"public.h" //公用的函数头文件#include"array.h" //数组实现转换的头文件#include"Recursion.h" //递归实现转换的头文件#include"stack.h" //堆栈实现转换的头文件intmain(){ intx,i; while(1) { system("pause"); system("cls"); //提示用户按照正确的格式输入数据 printf("请输入要转换的数据,格式:原数据进制数据要转换的进制(<=36):\n"); //读入数据 scanf("%d%s%d",&m,s,&n); if(m==n) { printf("原数据进制应该要转换的进制不同!\n"); } else if(m>36||n>36) { printf("输入的进制超出了可以表达的范围!\n"); } else { //计算数字用m进制表示时的位数 len=strlen(s); //数据的位数 for(i=0;i<len;++i) if(s[i]<48||(s[i]>=58&&s[i]<=64)|| (s[i]>=91&&s[i]<=96)||s[i]>122) break; if(i!=len) { printf("输入的数据中出现不符合要求的字符！\n"); continue; } Convert(s); //将字符数据转换为数字，并存入数组中 for(i=0;i<len;++i) if(s[i]>m) break; if(i!=len) { printf("输入的数据有错误！\n"); continue; } break; } } //计算出x的十进制表示，便以后面的使用 x=Turn10(len); //输出使用数组计算出的结果 printf("用数组算出x为：%d\n",x); //输出使用递归计算出的结果 printf("用递归算出x为：%d\n",CalcRecursion(len-1,1)); //转换为其他进制 //x的n进制表示，用数组实现 printf("%d的%d进制表示(数组计算):",x,n); Turnx(x); //x的n进制表示，用递归实现 printf("%d的%d进制表示(递归计算):",x,n); Recursion(x); //x的n进制表示，用堆栈实现 printf("\n%d的%d进制表示(堆栈计算):",x,n); UseStack(x); return0;}//头文件名称：array.h/****************************************\*功能：将m进制的数转换成十进制数*参数：l:s数组元素的个数\****************************************/intTurn10(intl){ inta[32]={1},i=0,result; //数组a存储m的k次幂,result为转换后的十进制数 //当a[i]*m不会超出整形范围 while(a[i]<=MAX/m) { a[i+1]=a[i]*m; //m^(i+1)=m^i*m ++i; } i=result=0; //初始化result for(--l;l>=0;--l,++i) //当s的下标减少时，a的下标应该增加 { result+=s[l]*a[i]; //将得到的次方乘以x中一位相乘后相加 } returnresult; //返回得到的十进制数}/****************************************\*功能：将十进制的数转换成n进制数*参数：x:十进制数值\****************************************/voidTurnx(intx){ inti=0,t; charresult[32]; //n进制表示的每一位 while(x) //当x不为0时 { t=x%n; //用t保存x对n的余数，便以下面判断 if(t>9) result[i++]=t-10+'A'; //大于9的数用字母A..F表示 else result[i++]=t+'0'; //小于9的数用字符0..9表示 x/=n; } for(--i;i>=0;--i) //逆向输出每一位 printf("%c",result[i]); printf("\n");}//头文件名称：public.h#defineMAX0x7fffffffint m; //输入的数据为哪个进制int n; //要转换成哪个进制int len; //输入的字符串的长度char s[33]; //m进制数/****************************************\*功能：将输入的数据转换成数字*参数：s：输入的x的m进制的字符串指针\****************************************/voidConvert(char*s){ inti=0; //从字符串的0地址开始 while(s[i]) //当s[i]！=0的 { //字符转换成对应的数字 if(s[i]>='a'&&s[i]<='z') s[i]=s[i]-'a'+10; else if(s[i]>='A'&&s[i]<='Z') s[i]=s[i]-'A'+10; else s[i]-='0'; ++i; }}//头文件名称：Recursion.h/****************************************\*功能：将m进制转换成10进制*参数：k：初始化时为s数组元素的个数，递归时为数组的下标c：m的k-1次方\****************************************/intCalcRecursion(intk,intc){ if(k>=0) //下标>=0时 { //返回k对应的元素乘以对应的次方 returns[k]*c+CalcRecursion(k-1,c*m); } else return0;}/****************************************\*功能：将十进制数x转换成n进制数*参数：x:十进制数x\****************************************/voidRecursion(intx){ intt; if(x>0) { Recursion(x/n); t=x%n; if(t>10) printf("%c",t-10+'A'); else printf("%d",t); }}//头文件名称：stack.h#include<malloc.h>#defineMAXSTACK33 //堆栈的最大位置//定义栈数据结构typedefstruct_stack{ int*addr; //栈的存储地址 intlength; //栈的最大长度 inttop; //栈顶 intbottom; //栈底}STACK,*PSTACK;/****************************************\*功能：初始化栈*参数：s：栈的地址\****************************************/voidInitStack(PSTACKs) { s->addr=malloc(MAXSTACK*sizeof(int)); //申请空间 s->length=MAXSTACK; //设定栈的最大长度 s->top=-1;s->bottom=0; //初始化栈指针}/****************************************\*功能：将一个元素压入栈中*参数：s：栈的地址x：要压入的元素\****************************************/vo