数据结构之顺序栈实现进制转换

栈的应用

进制转换

• 1.需要用到前面博文顺序栈基本操作

示例：

#include <iostream>
#include <stdio.h>

using namespace std;

#define STACK_INT_SIZE 10 //存储空间初始分配量
#define STACK_INTCREMENT 2 //存储空间分配增量
#define N 16   //定义待转换的进制N

typedef int SElemType;

struct SqStack {
	SElemType *base; //在构造之前和销毁后，base的值为NULL
	SElemType *top;  //栈顶指针
	int stacksize;   //当前已分配的存储空间，以元素为单位
}; //顺序栈

//顺序栈的基本操作
void InitStack(SqStack &S)
{
	//构造一个空栈
	if (!(S.base = (SElemType*)malloc(STACK_INT_SIZE * sizeof(SElemType)))) {
		return;
	}

	S.top = S.base;
	S.stacksize = STACK_INT_SIZE;
}


void DestoryStack(SqStack &S)
{
	//销毁S
	free(S.base);
	S.base = NULL;
	S.top = NULL;
	S.stacksize = 0;
}

void ClearStack(SqStack &S)
{
	//把S置为空栈
	S.top = S.base;
}

int StackEmpty(SqStack S)
{
	if (S.top == S.base)
	{
		return 1;
	}
	else {
		return 0;
	}
}

int StackLength(SqStack S)
{
	//返回S的元素个数，栈的长度
	return S.top - S.base;
}


int GetTop(SqStack S, SElemType &e)
{
	//如果栈不空，则用e返回S的栈顶元素，返回值为1
	//否则返回值为0
	if (S.top > S.base)
	{
		e = *(S.top - 1);
		return 1;
	}
	else {
		return 0;
	}

}


void Push(SqStack &S, SElemType e)
{
	//插入元素e为新的栈顶元素
	if (S.top - S.base >= S.stacksize) //栈满，分配空间
	{
		S.base = (SElemType *)realloc(S.base, (S.stacksize + STACK_INTCREMENT) * sizeof(SElemType));
		if (!S.base)
			return;
		S.top = S.base + S.stacksize;
		S.stacksize += STACK_INTCREMENT;
	}
	*(S.top)++ = e;
}

int Pop(SqStack &S, SElemType &e)
{
	//若栈不空，删除栈S的栈顶元素，用e返回，返回值1
	//若栈空，返回0
	if (S.top == S.base)
		return 0;
	e = *--S.top;
	return 1;
}

void StackTraverse(SqStack S, void(*visit)(SElemType))
{
	//从栈底到栈顶依次对栈中的每个元素调用visit()
	while (S.top > S.base)
	{
		visit(*S.base++);
	}
	printf("\n");
}

void print(SElemType e)
{
	printf("%d\n", e);
}


void Conversion(void) {
	SqStack s;
	unsigned int n;
	SElemType e;
	InitStack(s); // 初始化栈
	printf("将十进制整数n转换为%d进制数，请输入：n(>=0)=", N);
	scanf_s("%u", &n); // 输入非负十进制整数n
	while (n)
	{
		Push(s, n%N); // 入栈n除以N的余数(N进制的低位)
		n = n / N;
	}

	while (!StackEmpty(s))  //当栈不空
	{
		Pop(s,e);  // 弹出栈顶元素且赋值给e
		
#if 1  //16进制转换
		if (e <= 9) {
			printf("%d", e); //输出e
		}
		else
		{
			printf("%c", e+55); //// 大于9的余数，输出相应的字符
		}
#endif
		
	}

	printf("\n");
}

int main(void)
{
	Conversion();
	system("pause");
	return 0;
}