數(shù)制轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)

頁第一章課題背景1.1引言1.1.1課程設(shè)計目的在生活中我們經(jīng)常會遇到各式各樣的數(shù)制，例如2，8，10，16進(jìn)制，其實數(shù)制之間的轉(zhuǎn)換問題不僅僅是數(shù)學(xué)問題，還是我們計算機需要研究的范圍之一。高速發(fā)展的現(xiàn)代社會，計算機浩浩蕩蕩地成為了人們生活中不可缺少的一部分，幫助人們解決通信，聯(lián)絡(luò)，互動等各方面的問題。計算機在處理數(shù)字是和人是不同的，計算機使用的是二進(jìn)制，人們在日常生活中使用十進(jìn)制，但是在一些特定場合使用其他進(jìn)制的表示，所以需要進(jìn)行不同進(jìn)制之間的轉(zhuǎn)換其中包括有數(shù)據(jù)結(jié)構(gòu)，C語言中的遞歸算法與數(shù)組的存儲問題。本設(shè)計在2，8，10，16進(jìn)制之間，能實現(xiàn)對輸入的任意數(shù)制進(jìn)行相對應(yīng)的數(shù)制轉(zhuǎn)換。在此程序設(shè)計中我采用了C語言中的數(shù)組與遞歸的算法，以及數(shù)據(jù)結(jié)構(gòu)中的棧，實現(xiàn)了如下功能：1.對輸入的任意數(shù)制能夠求出此數(shù)的10進(jìn)制值2.實現(xiàn)在2，8，10，16進(jìn)制之間對輸入的任意數(shù)制x向任意的一個非M進(jìn)制數(shù)的轉(zhuǎn)換。3.至少用兩種或兩種以上的算法實現(xiàn)上述功能要求。在程序設(shè)計中，可以用使用很多種方法解決該問題。例如：數(shù)組、棧、遞歸。不同的方法實現(xiàn)轉(zhuǎn)換的原理基本相同，只是代碼的細(xì)節(jié)不同。在我的程序中不同的方法所需的函數(shù)在一個單獨的頭文件里面，便以管理和修改。第二章設(shè)計簡介及設(shè)計方案論述2.1選題分析 2.1.1數(shù)組的結(jié)構(gòu)為了處理方便，把具有相同類型的若干變量按有序的形式組織起來的一種形式。這些按序排列的同類數(shù)據(jù)元素的集合稱為數(shù)組。由于處理簡單的情況，最大的數(shù)字將不大于整形的范圍，整形為4個字節(jié)，因此開辟的數(shù)組為33個元素。 2.1.2棧的結(jié)構(gòu) 棧作為一種數(shù)據(jù)結(jié)構(gòu)，是一種只能在一端進(jìn)行插入和刪除操作的特殊線性表。它按照先進(jìn)后出的原則存儲數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）。棧具有記憶作用，對棧的插入與刪除操作中，不需要改變棧底指針。在此程序中我首先定義了一個結(jié)構(gòu)體，結(jié)構(gòu)體中包含棧元素的首地址、棧頂位置、棧頂位置、棧的最大范圍。棧元素的存儲空間在程序中再動態(tài)開辟。和上面一樣，棧的最大為33。 2.1.3遞歸的結(jié)構(gòu)遞歸做為一種算法在程序設(shè)計語言中廣泛應(yīng)用。一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。在這個程序中，遞歸不需要自己定義存儲空間，大量的減少了需要定義變量所需要的存儲空間。第三章詳細(xì)設(shè)計3.1算法說明在此程序的算法設(shè)計中，我采用了數(shù)組，棧，遞歸的算法。3.1.1數(shù)組的算法M進(jìn)制轉(zhuǎn)十進(jìn)制：從該M進(jìn)制數(shù)的最后一位開始算，依次列為第0、1、2...n位并分別乘以M的0、1、2...n次方，將得到的次方相加便得到對應(yīng)的十進(jìn)制數(shù)。由于輸入的M進(jìn)制的數(shù)可能出現(xiàn)字符，所以使用了字符數(shù)組進(jìn)行存儲。并在輸入后將字符全部轉(zhuǎn)換為數(shù)字，并存儲到全局變量s數(shù)組里面，每個數(shù)組元素存儲一位。result=0;i=0result=0;i=0i小于M進(jìn)制的字符長度取出數(shù)組元素s[i]與M的i次方相乘，相乘結(jié)果加入result中，i自加1。Y函數(shù)結(jié)束N圖3-1M進(jìn)制轉(zhuǎn)十進(jìn)制處理流程圖十進(jìn)制轉(zhuǎn)換為其他進(jìn)制：首先取x對需要轉(zhuǎn)換的進(jìn)制n取余，然后再對其取整，將取到的余數(shù)存入數(shù)組中，然后重復(fù)上面的步驟，將得到的余數(shù)依次存入數(shù)組中，知道x變成0。然后將數(shù)組反向輸出。輸出的數(shù)可能大于10，所以進(jìn)行了必要的判斷。初始化數(shù)組元素位置i=0;初始化數(shù)組元素位置i=0;x>0?Yx除以n，余數(shù)存入數(shù)組，數(shù)組下標(biāo)i后移，商賦值給x函數(shù)結(jié)束N3.1.2棧的算法 算法思路和上面基本相同，只是將取到的余數(shù)依次入棧，輸出時只要依次出棧就行。3.1.3遞歸的算法 遞歸過程中不需要另外的存儲取到的余數(shù)，只需要在遞歸返回時輸出相應(yīng)的結(jié)果就行。3.2變量設(shè)計 #defineMAX0x7fffffff定義了整形數(shù)的最大值，防止數(shù)字溢出。intm;用于表示輸入的數(shù)據(jù)是哪個進(jìn)制的數(shù)。chars[33];輸入時用于存儲輸入的十進(jìn)制數(shù)x的m進(jìn)制表示。處理過程中用于存儲m進(jìn)制表示的每一位所代表的的數(shù)字。 intn;要將輸入的m進(jìn)制數(shù)轉(zhuǎn)換成的進(jìn)制。 intlen;輸入的字符數(shù)據(jù)有多長。 注：其他變量在程序中均有說明。3.3函數(shù)功能設(shè)計表5-1程序中的函數(shù)函數(shù)功能intTurn10(intl);將m進(jìn)制的數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)voidTurnx(intx);將十進(jìn)制的數(shù)轉(zhuǎn)換成n進(jìn)制數(shù)intCalcRecursion(intk,intc);將m進(jìn)制轉(zhuǎn)換成10進(jìn)制voidRecursion(intx);將十進(jìn)制數(shù)x轉(zhuǎn)換成n進(jìn)制數(shù)voidInitStack(PSTACKs);初始化棧voidPush(PSTACKs,intx);將一個元素壓入棧中intPop(PSTACKs);取出棧頂元素voidUseStack(intx);將十進(jìn)制數(shù)x轉(zhuǎn)換成n進(jìn)制數(shù)voidConvert(char*s);將輸入的數(shù)據(jù)轉(zhuǎn)換成數(shù)字第四章設(shè)計結(jié)果及分析4.1運行與調(diào)試說明及分析程序開始運行時提示用戶按照規(guī)定的輸入格式輸入數(shù)據(jù)數(shù)據(jù)的進(jìn)制不能超過36，因為36后不好表達(dá)。數(shù)據(jù)中也不能出現(xiàn)除a..z,A..Z,0..9之外的字符m進(jìn)制數(shù)中的每一位不可能大于等于m，否則數(shù)據(jù)應(yīng)該是錯的。當(dāng)數(shù)據(jù)輸入正確時將給出不同進(jìn)制之間的轉(zhuǎn)換結(jié)果輸出完成后，程序?qū)⒄＝Y(jié)束。總結(jié)數(shù)據(jù)結(jié)構(gòu)是一門純屬于設(shè)計的科目，它需用把理論變?yōu)樯蠙C調(diào)試。在學(xué)習(xí)科目的第一節(jié)課起，老師就為我們闡述了它的重要性。它對我們來說具有一定的難度。它是其它編程語言的一門基本學(xué)科。剛開始學(xué)的時候確實有很多地方我很不理解，每次上課時老師都會給我們出不同的設(shè)計題目，對于我們一個初學(xué)者來說，無疑是一個具大的挑戰(zhàn)，撞了幾次壁之后，我決定靜下心來，仔細(xì)去寫程序。老師會給我們需要編程的內(nèi)容一些講解，順著老師的思路，來完成自己的設(shè)計，我們可以開始運行自己的程序，可是好多處的錯誤讓人看的可怕，還看不出到底是哪里出現(xiàn)了錯誤，但是程序還是得繼續(xù)下去，我多次請教了老師和同學(xué)，逐漸能自己找出錯誤，并加以改正。VC++6.0里檢查錯誤有時候真是讓你難以找到為什么錯。經(jīng)過了這次課程設(shè)計，現(xiàn)在已經(jīng)可以了解很多錯誤的原因，這對我來說是一個突破性的進(jìn)步，眼看著一個個錯誤通過自己的努力在我眼前消失，覺得很是開心。在這一段努力學(xué)習(xí)的過程中，我的編程設(shè)計有了明顯的提高。雖然程序中不是很完美，還未能實現(xiàn)對小數(shù)之間的數(shù)制轉(zhuǎn)換問題，但是對于我來說已經(jīng)不錯了，今后還需繼續(xù)努力。參考文獻(xiàn)[1] 譚浩強.C語言程序設(shè)計教程.北京：清華大學(xué)出版社，2008[2] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社，2010[3]王曉東.計算機算法設(shè)計與分析.電子工業(yè)出版社，2007

附錄1：源程序清單//程序名稱：課程設(shè)計.c//程序功能：分別采用數(shù)組、棧、遞歸實現(xiàn)進(jìn)制間的轉(zhuǎn)換//程序作者：余歲//最后修改日期：2014-6-24#include<stdio.h>#include<string.h>#include<stdlib.h>#include"public.h" //公用的函數(shù)頭文件#include"array.h" //數(shù)組實現(xiàn)轉(zhuǎn)換的頭文件#include"Recursion.h" //遞歸實現(xiàn)轉(zhuǎn)換的頭文件#include"stack.h" //堆棧實現(xiàn)轉(zhuǎn)換的頭文件intmain(){ intx,i; while(1) { system("pause"); system("cls"); //提示用戶按照正確的格式輸入數(shù)據(jù) printf("請輸入要轉(zhuǎn)換的數(shù)據(jù),格式:原數(shù)據(jù)進(jìn)制數(shù)據(jù)要轉(zhuǎn)換的進(jìn)制(<=36):\n"); //讀入數(shù)據(jù) scanf("%d%s%d",&m,s,&n); if(m==n) { printf("原數(shù)據(jù)進(jìn)制應(yīng)該要轉(zhuǎn)換的進(jìn)制不同!\n"); } else if(m>36||n>36) { printf("輸入的進(jìn)制超出了可以表達(dá)的范圍!\n"); } else { //計算數(shù)字用m進(jìn)制表示時的位數(shù) len=strlen(s); //數(shù)據(jù)的位數(shù) 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("輸入的數(shù)據(jù)中出現(xiàn)不符合要求的字符！\n"); continue; } Convert(s); //將字符數(shù)據(jù)轉(zhuǎn)換為數(shù)字，并存入數(shù)組中 for(i=0;i<len;++i) if(s[i]>m) break; if(i!=len) { printf("輸入的數(shù)據(jù)有錯誤！\n"); continue; } break; } } //計算出x的十進(jìn)制表示，便以后面的使用 x=Turn10(len); //輸出使用數(shù)組計算出的結(jié)果 printf("用數(shù)組算出x為：%d\n",x); //輸出使用遞歸計算出的結(jié)果 printf("用遞歸算出x為：%d\n",CalcRecursion(len-1,1)); //轉(zhuǎn)換為其他進(jìn)制 //x的n進(jìn)制表示，用數(shù)組實現(xiàn) printf("%d的%d進(jìn)制表示(數(shù)組計算):",x,n); Turnx(x); //x的n進(jìn)制表示，用遞歸實現(xiàn) printf("%d的%d進(jìn)制表示(遞歸計算):",x,n); Recursion(x); //x的n進(jìn)制表示，用堆棧實現(xiàn) printf("\n%d的%d進(jìn)制表示(堆棧計算):",x,n); UseStack(x); return0;}//頭文件名稱：array.h/****************************************\*功能：將m進(jìn)制的數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)*參數(shù)：l:s數(shù)組元素的個數(shù)\****************************************/intTurn10(intl){ inta[32]={1},i=0,result; //數(shù)組a存儲m的k次冪,result為轉(zhuǎn)換后的十進(jìn)制數(shù) //當(dāng)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) //當(dāng)s的下標(biāo)減少時，a的下標(biāo)應(yīng)該增加 { result+=s[l]*a[i]; //將得到的次方乘以x中一位相乘后相加 } returnresult; //返回得到的十進(jìn)制數(shù)}/****************************************\*功能：將十進(jìn)制的數(shù)轉(zhuǎn)換成n進(jìn)制數(shù)*參數(shù)：x:十進(jìn)制數(shù)值\****************************************/voidTurnx(intx){ inti=0,t; charresult[32]; //n進(jìn)制表示的每一位 while(x) //當(dāng)x不為0時 { t=x%n; //用t保存x對n的余數(shù)，便以下面判斷 if(t>9) result[i++]=t-10+'A'; //大于9的數(shù)用字母A..F表示 else result[i++]=t+'0'; //小于9的數(shù)用字符0..9表示 x/=n; } for(--i;i>=0;--i) //逆向輸出每一位 printf("%c",result[i]); printf("\n");}//頭文件名稱：public.h#defineMAX0x7fffffffint m; //輸入的數(shù)據(jù)為哪個進(jìn)制int n; //要轉(zhuǎn)換成哪個進(jìn)制int len; //輸入的字符串的長度char s[33]; //m進(jìn)制數(shù)/****************************************\*功能：將輸入的數(shù)據(jù)轉(zhuǎn)換成數(shù)字*參數(shù)：s：輸入的x的m進(jìn)制的字符串指針\****************************************/voidConvert(char*s){ inti=0; //從字符串的0地址開始 while(s[i]) //當(dāng)s[i]！=0的 { //字符轉(zhuǎn)換成對應(yīng)的數(shù)字 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進(jìn)制轉(zhuǎn)換成10進(jìn)制*參數(shù)：k：初始化時為s數(shù)組元素的個數(shù)，遞歸時為數(shù)組的下標(biāo)c：m的k-1次方\****************************************/intCalcRecursion(intk,intc){ if(k>=0) //下標(biāo)>=0時 { //返回k對應(yīng)的元素乘以對應(yīng)的次方 returns[k]*c+CalcRecursion(k-1,c*m); } else return0;}/****************************************\*功能：將十進(jìn)制數(shù)x轉(zhuǎn)換成n進(jìn)制數(shù)*參數(shù)：x:十進(jìn)制數(shù)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 //堆棧的最大位置//定義棧數(shù)據(jù)結(jié)構(gòu)typedefstruct_stack{ int*addr; //棧的存儲地址 intlength; //棧的最大長度 inttop; //棧頂 intbottom; //棧底}STACK,*PSTACK;/****************************************\*功能：初始化棧*參數(shù)：s：棧的地址\****************************************/voidInitStack(PSTACKs) { s->addr=malloc(MAXSTACK*sizeof(int)); //申請空間 s->length=MAXSTACK; //設(shè)定棧的最大長度 s->top=-1;s->bottom=0; //初始化棧指針}/****************************************\*功能：將一個元素壓入棧中*參數(shù)：s：棧的地址x：要壓入的元素\****************************************/vo