数据结构实验三:栈

实验三 栈的实现及应用
一、实验目的1、掌握顺序栈的类型定义方法。

2、掌握在顺序栈上实现的六种基本算法。

2、掌握顺序栈的简单应用。

二、实验内容1、利用顺序栈将一个非负的十进制整数N转换为对应的B进制数。

[基本要求]非负的十进制整数N和B都从键盘输入；转换结果从屏幕输出。

报告内容为小组共同完成

一、实验目的
1、掌握顺序栈的类型定义方法
2、掌握在顺序栈上实现的六种基本算法
3、掌握顺序栈的简单应用
4、理解算法与程序的关系，灵活运用顺序栈算法。
二、实验内容
1、实现顺序栈的基本操作，初始化、进栈、出栈等。
2、利用顺序栈将一个非负的十进制整数N转换为对应的B进制数。
三、代码实现

#include<iostream>
#include<string>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define OVERFLOW -2
typedef int Status;
typedef int SElemType;

typedef struct Stack
{
	SElemType* base;                  //栈底指针 
	SElemType* top;                   //栈顶指针 
	int stacksize;                    //栈可用的最大容量
}SqStack;

Status InitStack(SqStack& s)
{
	s.base = new SElemType[MAXSIZE];      //分配最大容量
	if (!s.base)
	{
		cout << "储存空间分配失败！" << endl;
		return 0;
	}
	s.top = s.base;              //top初始为base，令栈为空
	s.stacksize = MAXSIZE;       //stacksize置为最大容量
	return OK;
}
//入栈
Status Push(SqStack& s, SElemType e)
{
	if (s.top - s.base == s.stacksize)     //判断栈是否已满
		return OVERFLOW;
	*(s.top++) = e;         //先入栈，栈顶指针再上移 
	return OK;
}
//出栈 用e返回值
Status Pop(SqStack& s, SElemType& e)
{
	if (s.top == s.base)      //判断是否为空栈
		return 0;
	e = *--s.top;              //先减减 指向栈顶元素，再赋值给e
	return OK;
}
//取栈顶元素，不修改栈顶指针
bool GetTop(SqStack s, SElemType& e)
{
	if (s.top == s.base)         //判断是否为空栈
		return false;		
	else
		e = *--s.top;                  //先减减 指向栈顶元素，再赋值给e
	return true;
}
//十进制转二进制
void Binary(SqStack s, SElemType& e)            
{
	int a;
	cin >> a;
	cout << a << " 的二进制数是：";
	while (a)                                    
	{
		Push(s, a % 2);                         //除以2，余数入栈
		a = a / 2;                             //除以2继续循环
	}
	while (GetTop(s, e))                       //栈内有元素
	{
		Pop(s, e);                              //出栈
		cout << e;
	}
	cout << endl;
}
//十进制转八进制
void Octal(SqStack s, SElemType& e)             
{
	int a;
	cin >> a;
	cout << a << " 的二进制数是：";
	while (a)
	{
		Push(s, a % 8);                         //除以8，余数入栈
		a = a / 8;                              //除以8继续循环
	}

	while (GetTop(s, e))                       //栈内有元素
	{ 
		Pop(s, e);                              //出栈
		cout << e;
	}
	cout << endl;
}
//十进制转十六进制
void Hexadecimal(SqStack s, SElemType& e)        
{
	char str[MAXSIZE];                            //确定最大空间
	int a;
	int i = 0;
	cin >> a;
	cout << a << " 的十六进制数是：";
	while (a)
	{
		Push(s, a % 16);                          //除以16，余数入栈
		a = a / 16;                              //除以16继续循环
	}
	while (GetTop(s, e))
	{
		Pop(s, e);                              //出栈
		if (e < 10)                             //判断是否超过10，没超过没正常出栈
		{
			str[i] = e + '0';                   
		}
		else                               //若出栈的数在10至15之间，进行转换
		{
			str[i] = e + 'A' - 10;        //输出A,B,C,D,E,F其中某一个
		}
		i++;                     
	}
	str[i] = '\0';            //结束标志
	for (i = 0; str[i] != '\0'; i++)
	{
		cout << str[i];
	}
	cout << endl;
}
//主函数
int main()
{
	int chioce;
	int e;
	Stack s;
	InitStack(s);
	while (true)
	{
		cout << " 1--十进制转二进制 " << endl;
		cout << " 2--十进制转八进制 " << endl;
		cout << " 3--十进制转十六进制 " << endl;
		cout << " 按其他键退出        " << endl;
		cout << " 请作出以上选择:" << endl;
		cin >> chioce;
		switch (chioce)
		{
		case 1:
		{
			cout << "请输入一个十进制的数:" << endl;
			Binary(s, e);
			system("pause");
			system("cls");
			break;
		}
		case 2:
		{
			cout << "请输入一个十进制的数:" << endl;
			Octal(s, e);
			system("pause");
			system("cls");
			break;
		}
		case 3:
		{
			cout << "请输入一个十进制的数:" << endl;
			Hexadecimal(s, e);
			system("pause");
			system("cls");
			break;
		}
		default:
		{
			cout << "退出成功！" << endl;
			return 0;
			break;
		}
		}
	}
}

四、实验难点
1、元素入栈，这里要注意的是每当有元素进栈，栈顶指针就要上移，顺序是元素先进来，指针再移动
2、元素出栈，这个与入栈相反，先将栈顶指针下移到栈顶元素，然后出栈，注意不要把二者搞反
3、十进制转二进制或八进制，将一个数不断除以2或8，余数进栈，直到这个数为零；利用栈的特性，先进后出，输出倒置过来的余数，完成转换
4、十进制转十六进制，道理也是一样，但与前二者相比，多了一步。十六进制有0，1,2,3,4,5,6,7,8,9，A，B，C，D，E，F共十六个符号，分别表示十进制的0至15，但取余时并不能直接输出A，B等等，所以就需要将10至15转成A至F，以十进制数200转成十六进制C8为例，如下5、出现了一个问题，如果不在字符串结尾加上’\0’，就会出现烫烫烫烫……。问题原因也很简单，对于未初始化的栈内存全部填成 0xcc，对应于汉字字符串看就是烫烫烫烫。对于内存未做初始化，那么内存内的值是随机的。它可能包含’\0’。而系统通过判断’\0’来辨识字符串的结束。系统读取字符串，只是从字符数组的开始，一直往后找，一直找到’\0’为止。如果不加，系统只好再往后找，一直找到’\0’为止。如果在字符串之后正好有个’\0′,那字符串就会被正确读出。如果字符串后面隔了一些字节后有’\0′,那系统除了字符串还会读出一堆乱码，就比如这个烫烫烫。如果系统一直往后找，根本找不到’\0′,一直读到了操作系统区（“禁区”），那么程序就会崩溃。

五、实验结果
省略

六、实验心得
通过本次实验，掌握了顺序栈的基本操作和应用，并对课上学习的一些知识进行了加深。也明白了处理问题不能局限于一种方法，进制的转换本可以用其他方法来完成，但是学会了栈的算法，发现栈比其他方法好用的多。这也许就是数据结构的魅力所在，用一些不了解的算法去解决生活中常见的问题。本次的意外收获就是在数组里找到了一个雷区，为日后的编码设计避免了一个很大的缺陷。实验就是这样，不断地探索，不断地发现自己的问题，不断的去寻找解决问题的方法，到最后这些东西都是自己的。