栈与队列——进制转换

一、实验目的及要求

1.实验目的

掌握栈的概念、抽象数据类型和特点，掌握栈的顺序存储结构或者链式存储结构的存储思想及其程序实现，掌握栈对应存储结构的基本操作。

2.实验要求

用结构体类型描述栈的存储结构，对可能出现的问题预先分析，确定调试步骤和测试方法，编写源程序，尽可能考虑算法的健壮性，对实验中出现的问题进行分析、总结，完成实验报告。

3.上机实验内容：实验环境中，编写具体函数实现栈对应存储结构的数制转换，可以通过编写栈的入栈、出栈等操作函数实现，完成实验报告。实验报告中，要求给出实验目的及要求，实验环境（工具、配置等），实验内容（实验方案、实验步骤、设计思路等），实验结果与分析，最后附源程序。

二、实验环境（工具、配置等）

1.硬件要求：计算机一台。

2.软件要求：Windows操作系统，编译环境不限，如Dev-Cpp或VC++6.0等。

3.数据结构与算法分析，实验实现的语言不限，建议使用C或者C++语言。

三、实验内容（实验方案、实验步骤、设计思路等）

1.实验方案

①学习栈和队列的相关知识，并且观察和总结栈与队列的相关知识，利用栈进行数制转化，同时实现循环队列的。具体如图3-1,3-2

图3-2 栈的基本原理

图3-2 队列的基本原理

②利用栈进行数制转化，并同时实现循环队列的存放，对其进行一系列的测试。

2.实验步骤

• 利用栈进行数值转化：

1）首先用类创建一个栈，并在类中编写函数，实现栈的初始化、进栈、出栈、读取栈顶元素、判断是否为满、是否为空等函数，利用这些函数将数据存储到栈内。

2）利用循环，实现一个不断对十进制数取余的功能，并将所求余数存入栈内，取余后将原数除以所要转化的进制数，再次循环这个过程。

3）对入栈结果进行出栈操作，出栈后数字排列顺序为所求得的最终进制转换后的结果。

②实现循环队列：

1）首先用类创建一个队列，并在类中编写函数，实现队列的初始化、进队、出队、判断队列是否为满的功能。

2）要向队列中传入数据，并将队列中的部分数据进行出队，为使队列位置充分利用，形成循环队列，不断修改头指针和尾指针。

3.设计思路

利用栈进行数制转换：

1）首先要知道十进制数转换为其他进制数的转换方式，利用每一次不断相除取余，将每次的余数保留，最终将所有余数逆序输出，得到的就是要求的转换后其它进制数字。

2）利用栈，将每次取余后的余数入栈，最终将栈内元素出栈，得到的最终结果为相除后余数的逆序输出结果，也就是所求的最终进制转换后的结果。

实现循环队列：

1）建立一个循环队列，包含头指针、尾指针和开辟的数组来接收传入的元素，然后不断往队列里面传入数据，当队列元素个数等于队列最大可容纳的元素时，程序自动提示队已满，

2）当出队的时候，头指针移动位置，为前面腾出位置，后面新元素入队，尾指针不断后再添加新的元素。如图3-4所示。最后将出队后的结果打印输出，检查是否正确。

图3-3 循环队列

 实验结果与源代码于word查看