数据结构董成成_第二次实验报告.doc

湖北汽车工业学院实验报告 班 号 T1223-3 学 号 20120230309 姓 名 董成成 选课班中的序号 09 完成日期2014年4月28日7至8节 实验二 栈和队列基本操作的编程实现 一 、 实验目的 1.了解栈和队列的逻辑结构和存储结构的工作原理； 2.理解栈和队列的用途； 3.掌握栈和队列的程序设计； 二、实验要求 由于本次实验涉及到栈和队列两种数据结构的原理，实验题目将按照分级和分类的方式提供，任何学生都可以选择其中之一或多个综合来达成对原理的理解。细节由学生按照自己的能力随意拓展和提高，程序源码实现原创设计。 存储结构最简模式为：顺序存储，使用一维数组实现。鼓励使用链表结构，一般可以采用单链表结构。时间足够的情况下，希望把这些在课外全部自行编程实现。特别是希望和第一次实验采取相反的策略进行选择，以此来提高自己对于不同的存储结构的熟练运用。 界面设计最简模式为：无界面设计，极少提示。鼓励更加人性化的界面设计，提示清晰，操作过程流畅。如果启用文件，则可以采用全程无界面设计模式。 原始数据构建方式最简模式为：键盘输入。其他的方式也在鼓励之中：数据内置，计算机自动生成，文件读入。 数据类型最简模式为：整数。其他依次鼓励使用的为：实数、字符、英语字符串、汉字字符串。 实验内容 功能设计难度系数分为五级制：1：很容易，2：较容易，3：有一定难度，4：难度较大，5：难度很大。 栈功能演示系统。难度系数：2 汉字回文字符串的判断程序。难度系数：3 十进制正整数转换为八进制的程序。难度系数：4 环状队列功能演示系统。难度系数：2 十进制正小数转换为八进制的程序。难度系数：3 用计算机自动产生作业名、申请时间和打印时间的随机数据，然后用队列管理，随时显示队列中的数据和已经打印完毕的作业名。难度系数：4 开发语言最简模式为：C语言。以下依次为更加鼓励的设计环境：C++（不带对象），C++（带对象），C++带图形包（带对象），C++ windows mfc（带对象）。 知识分布界面的显示和控制、原始数据构建、全部数据遍历属于C语言。进栈和出栈、进队和出队等原理属于数据结构原理范畴。 重点实验内容图示 空环队 入队9次，出队4次 再入队3次，出队3次 再入队4次 这次实验，我做的是十进制正整数转换为八进制的程序，运用了栈。 把十进制转化为其他进制的方法，即辗转相除法。启用除法，把十进制数作为被除数，把要转化的进制数作为被除数，把余数记录下来，然后把商作为被除数，如此反复直到不能再除为止，所有余数就是结果，但是次序正好和希望的相反，所以必须设法产生逆序。启用栈后就可以得到正确的结果。 以下是辗转相除法的流程图： 但是在程序中有一点缺陷，即转化出来的在屏幕上显示的数字只是表面现象，只是由几个数字组合而成的。所以要把出栈后的多个数字转化成一个数字还需要进一步的讨论，这也算是本程序的一个不完善的地方。 栈作为数据结构，其主要的用途就是保存一批数据的逆序信息从而产生逆序的数据。栈的调用很好的运用了这一功能，后进后出的这一功能在这里得到了很好的运用。 主要的实现代码如下： for(;;) { printf(\n***T1223-3-09 董成成 进制转换***：); printf(\n请输入十进制数：); scanf(%d,num); for(;num!=0;){ remainder=num%8; push(remainder); num=num/8; count++; } printf(\n转换成八进制后为：); for(;count!=0;){ pop(); count--; } system(pause); system(cls); } 在这里，先输入一个十进制的数字，定义了一个int型的变量num来存储，定义了一个int型的变量remainder来存储num%8的余数。在for循环下，当num不等于0时，取num%8的余数赋值给remainder，将remainder进栈，取num=num/8，在num=0时结束循环。 在显示转换后的8进制时，只需要出栈就可以了。调用pop()函数： int pop()//出栈 { if (isempty()==0) return 0; printf(%d,stack[top]); top--; return 0; } 在程序中，运用了一个int型的变量count来计数，判断栈内的元素个数；当数据进栈的时候，count++；出栈的时候，count--。 其中isempty()函数式用来判断栈是否为空，当count=0时，isempty()返回值