数据结构课程设计报告2.doc

课程设计报告课程名称 设计题目 专业班级 学 号 姓 名 指导教师 设计时间 2011 年 10月 8日一、引言（简要说明设计题目的目的、意义、内容、主要任务等）1、设计题目的目的本次课程设计的题目是数制转换程序，设计此题目主要目的在于加深对c语言课程理论与数据结构课程理论实践方面的理解。通过编写一定规模和难度的程序，进行一次全面的c语言编程训练，掌握数据结构的思想，提高分析问题和解决问题的能力，并提高调试程序的能力，更深一步的掌握理论应用于实践。2、设计题目的意义数制转换是计算机科学技术中最为基础的运算，在日常生活中人们习惯性地使用十进制数进行计算，而在计算机内部所有的信息（数字、字符、汉字、计算机的指令、状态等）都是用二进制数来表示的。在计算机中，二进制的运算、处理比十进制数的更容易实现。但是二进制数表示起来有时候会很长，不方便书写。因此，有时为了缩短书写，在计算机中还采用十六进制书写所以我们需要把数制从二进制数形式转换成其他进制的形式，甚至在不同进制之间进行转换。3、设计题目的内容本课程设计主要解决完成数制转化问题。完成功能如下：1) 任意给一个二进制、八进制、十进制、十六进制的数；2) 完成二进制、八进制、十进制、十六进制之间的数制转换；3) 用两种以上的方法实现上述数制转换要求（本课程设计使用数组解决，用栈解决）。4、设计题目的主要任务本次课程设计的主要任务是完成对数制转换进行编程，并在编程过程中找出自身的不足，锻炼调试程序能力，提高实践动手能力。5、基础知识栈，是硬件。主要作用表现为一种数据结构，是只能在某一端插入和删除的线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。 栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（push），删除则称为退栈（pop）。 栈也称为先进后出表。 栈可以用来在函数调用的时候存储断点，做递归时要用到栈！ 以上定义是在经典计算机科学中的解释。 在计算机系统中，栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中，栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址减小，弹出的操作使得栈顶的地址增大。 栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧或者活动记录。堆栈帧一般包含如下几方面的信息： 1. 函数的返回地址和参数 2. 临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量。数组是在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来的一种形式。这些按序排列的同类数据元素的集合称为数组。在语言中， 数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。二维数组前面介绍的数组只有一个下标，称为一维数组， 其数组元素也称为单下标变量。在实际问题中有很多量是二维的或多维的， 因此语言允许构造多维数组。多维数组元素有多个下标， 以标识它在数组中的位置，所以也称为多下标变量。 本小节只介绍二维数组，多维数组可由二维数组类推而得到。本课程设计主要采用栈与数组的方式完成系统设计。二正文（课程设计的主要内容，包括实验与观测方法和结果、仪器设备、计算方法、编程原理、数据处理、设计说明与依据、加工整理和图表、形成的论点和导出的结论等。正文内容必须实事求是、客观真切、准确完备、合乎逻辑、层次分明、语言流畅、结构严谨，符合各学科、专业的有关要求。）1、课程设计的主要内容（问题描述）完成数制转化问题。设计要求：任意给定一个m进制的数x ，实现如下要求：4) 求出此数x的二进制、八进制、十进制、十六进制；5) 实现对x向任意的一个非m进制的数的转换；6) 用两种以上的方法实现上述要求（可用数组解决，用栈解决，其它方法解决）。 2、 设计思路数制转换的基本原理是：将一个指定进制的数，从高位到低位，一位一位取出，并计算出每位的十进制值，然后乘以其数基的特定幂指数，得出这一位数的十进制值，将所有各位的十 进制值相加得出这个数的十进制值，然后再将该十进制数转换为指定数制的数，此过程可以采用求余法进行，用这个十进制数作为被除数，用指定的数基作除数，连续求余，得出的余数依由个位到十位等的顺序组成新数，即得指定数制的数。本次课程设计，我主要用了数组和栈两种的方法来实现的。堆栈的主要应用就是可以实现：后进先出(last-in/first-out)。转2进制或者8进制的时候（一般的方法），先得到是低位的数字，然后得到高位的数字，刚好使用堆栈可以把这个顺序颠倒过来，每得到一个数字就把它压栈，最后把所有的数字弹出，依次显示出来就行了。3、程序设计构造概述3.1应用数组方法的程序主要构造了以下几个函数：1）int init()：int init() 函数的作用是显示提示主菜单， 同时读入内容并存入字符串数组ipt中；2）bool islegal(int jinzhi)：函数bool islegal(int jinzhi) 用来判定输入数据的合法性；3) _int64 todec(int jinzhi)：_int64 todec(int jinzhi) 函数作用是将输入的数据转成10进制；4) void dectoothers(_int64 dec)：void dectoothers(_int64 dec) 函数是将转换成的十进制数转换为所要求的四种进制数；5）void out()：函数void out()的功能是将转换后的数分别输出；6）int main(int argc, char* argv)：int main(int argc, char* argv) 为主函数。3.2应用栈的方法则主要应用了以下几个函数1）void initial(seqstack *s)：实现栈的建立；2）void initial(seqstack *s)：初始化栈；3）int isfull(seqstack*s)：实现进栈；4）datatype top(seqstack*s)：实现出栈；5）void zhuanhuan(int n ,int m)： 判断输入数据合法性及数值转换等；6）int main()：其中 int main（）为主函数。4.补充说明两个程序中，都应用了命令“system(pause);”来实现反复执行功能的作用，同时在反复执行是我应用了“system(cls);”实现刷屏，使运行界面看起来更简洁明了。5、运行环境可在windows系统，vc+平台下直接运行。6、程序说明本程序中包含了相对较多的函数，从而来对目标功能的实现。下面我们就将程序中比较重要的几个函数以流程图的方式来进行大概说明。（1）用数组的方式实现程序的相关程序流程图如下： 开始main()jinzhi=init()if(!islegal(jinzhi)dectoother(todec(jinzhi)out( )nyend图1主函数（2）用栈的方法实现的部分相关函数的流程图如下：void push()s-data+s-top=xends-datas-top-data type pop()if(isempty(s)endprintf(“%d”,i);nyynynif(isfull(s)endvoid zhuanhuan ()inititial(&s)while(isempty(&s)push(&s,n/m) n=n/mpop(&s)图2进栈图2出栈图3转换函数7、运行界面介绍1 运行数组和栈两种方法的程序主界面都相差不多，下面我们就以相关运行图来加以说明。（1）运用数组方法程序的运行图如下：图4运行界面图5运行结果页面图6运行界面（2）用栈的方法实现的程序运行图如下：图7主界面 图8运行界面图9退出界面 图10错误界面8、源代码（以下为本程序的源代码及说明）（1）以数组方式实现程序代码：#include iostream #include stdlib.h #include string.h using namespace std; int binarray1000=0,octarray1000=0,decarray1000=0,hexarray1000=0; char ipt1000; /=显示提示性内容 同时读入内容 并存入字符串数组 ipt中 =int init() int type=0;/代表用户先择的项 for(int i=0;i1000;i+) binarrayi=0; octarrayi=0; decarrayi=0; hexarrayi=0; coutn=欢迎使用进制转换程序=endl; coutendl 说明：本程序可以对二进制数，八进制数，十进endl;cout制数及十六进制数之间进行自由转化endl;coutendlendl;coutt;coutendlendlt 1. 十进制tt2. 二进制endl;coutt 3. 八进制tt4. 十六进制endlt 0. 退出endlendl; coutt;again: coutendltype; switch(type) case 0:cout程序结束！endl感谢使用本系统; system(pause); exit(0); case 1: coutipt; return 10; break; case 2: coutipt; return 2; break; case 3: coutipt; return 8; break; case 4: coutipt; return 16; break; default: cout输入有误，请重新输入！; goto again; /=bool islegal(int jinzhi) /判定输入的合法性 if(jinzhi=16) /misuse of = as = at first for(int i=0;i=0)&(ipti=a)&(ipti=a)&(ipti=f) return false; else for(int i=0;i=0&ipti-0=0;i-) result+=(ipti-0)*nsqr; nsqr*=jinzhi; return result; else for(int i=strlen(ipt)-1;i=0;i-) if(ipti=0&ipti=a&ipti0) /反复取余转成n进制 binarrayi=ori%2;ori/=2; i+; ori=dec,i=0; while(ori0) octarrayi=ori%8;ori/=8; i+; ori=dec,i=0; while(ori0) hexarrayi=ori%16;ori/=16; i+; ori=dec,i=0; while(ori0) decarrayi=ori%10;ori/=10; i+; /=void out() coutendl转换结果：endl=0;i-) if(decarrayi!=0&find=false) find=true; pos=i; for(i=pos;i=0;i-) coutdecarrayi; coutendl; cout=0;i-) if(binarrayi!=0&find=false) find=true; pos=i; for(i=pos;i=0;i-) coutbinarrayi; coutendl; cout=0;i-) if(octarrayi!=0&find=false) find=true; pos=i; for(i=pos;i=0;i-) coutoctarrayi; coutendl; cout=0;i-) if(hexarrayi!=0&find=false) find=true; pos=i; for(i=pos;i=0;i-) if(hexarrayi=9)couthexarrayi; else coutchar(hexarrayi-10+a); coutendl; /=int main(int argc, char* argv) int jinzhi; loop: jinzhi=init(); if(!islegal(jinzhi) coutn输入有误，请重新输入!n; goto loop; dectoothers(todec(jinzhi); out(); system(pause); system(cls); goto loop; system(pause); return 0; （2）以栈的形式实现程序的代码。#include#include #include#define stacksize 1000using namespace std;typedef int datatype;typedef struct datatype datastacksize; int top;seqstack;/=初始化栈=void initial(seqstack *s) s-top=-1;int isempty(seqstack*s)return s-top=-1;int isfull(seqstack*s) return s-top=stacksize-1; void push(seqstack*s,datatype x)if(isfull(s)printf(溢出);exit (1);s-data+s-top=x; datatype pop(seqstack *s)if(isempty(s)printf(无数值); exit(1);return s-datas-top-;datatype top(seqstack*s)if(isempty(s)printf(无数值);exit(1);return s-datas-top;void zhuanhuan(int n ,int m)int i;seqstack s; initial(&s);while(n)push(&s,n%m);n=n/m;while(!isempty(&s)i=pop(&s);printf(%d,i);int main() int n,m; again:coutn=欢迎使用程序 =endl; coutendl 说明：本程序可将非负十进制数endl; coutt转化为其他进制:endl; coutendlendl; coutt;coutendlendln; if(n=0) coutendlt感谢使用本系统!endlendl;couttendl; exit(0); else coutendlm; coutendlt转换后的所得m进制数为：; zhuanhuan(n,m); coutendlendl; couttendl; system(pause); system(cls); goto again; system(pause); return 0; 三、结论（应当准确、完整、明确精练；也可以在结论或讨论中提出建议、设想、尚待解决问题等。）经过一段时间的课程设计，无论从学习上还是自身角度，都得到了很大的提高。在课程设计过程中，发现许多在理论学习过程中所未发现的问题，同时，通过自己的努力，顺利的解决了这些问题，这也是一种磨砺。这次的数据结构课程设计为我们提供了与众不同的学习方法和学习机会。通过学习c语言等内容来完成课程设计，让我们从传统上的被动授学转变为主动求学，从死记硬背的模式中脱离出来，形成了在实践中学习的能力，增强了领悟能力和解决问题的能力。不仅可以巩固以前学过的知识，拓宽了知识面，而且学到了很多书本上没有学到的知识，通过这次课程设计使我懂得了理论与实际相结合是很重