数据结构：用顺序栈与链栈分别实现进制转换算法详解 任意进制转换（c/c++版）

创建顺序栈的方式与顺序表差不多，只是在操作上有所规定。

#include
using namespace std;

#define OK 1
#define ERROR 0
#define MAXSIZE 10   //顺序栈最大存储空间
typedef int Status;  //返回状态
typedef struct
{
	int n;         //元素
}number;
typedef struct
{
	number* base;      //栈底指针
	number* top;       //栈顶指针
	int stackmax;      //栈空间
}sqstack;

为了丰富应用，并练习，本程序的元素用了结构体类型定义

int main()
{
	int x, n;
	cout << "请输入进制转换的数字：";
	cin >> x;
	cout << "请输入转换的进制：";
	cin >> n;
	sqstack S;
	initstack(S);
	cout << "转换后的数字为：";
	turn(S, x, n);
	return 0;
}

在主函数中initstark是初始化函数，turn是转换函数。至于为什么没有出栈入栈函数，是因为这两个函数嵌套在turn函数中。

Status initstack(sqstack& S)      //初始化函数
{
	S.base = new number[MAXSIZE];     //空间分配
	if (!S.base) return ERROR;        //判断是否成功
	S.top = S.base;           
	S.stackmax = MAXSIZE;         //初始化大小
	return OK;
}

void input(sqstack& S, int e)
{
	S.top->n = e;       //输入
	S.top++;             //指针上移
}

void output(sqstack S)
{
	while (S.top != S.base)    //循环直到栈为空
	{
		cout << (S.top - 1)->n;    //输出栈顶指向的位置下面元素，也就是栈顶元素所在位置
		S.top--;            //向下移动
	}
}

Status turn(sqstack& S, int x, int n)
{
	while (x!=0)           //辗转相除法
	{
		input(S, x % n);    //将每次的余数入栈
		x = x / n;
	}
	output(S);              //将栈内元素完全输出
	return OK;
}

#include
using namespace std;

#define OK 1
#define ERROR 0
#define MAXSIZE 10
typedef int Status;

typedef struct
{
	int n;
}number;

typedef struct Slnode
{
	number data;
	struct Slnode* next;
}Slnode,*linkstack;

与常规单链表差不多，只是换个名字，有特定规范。

与上边顺序栈的主函数是一样的。

Status initstack(linkstack& S)
{
	S = NULL;
	return OK;
}

void input(linkstack& S, int e)
{
	Slnode* p = new Slnode;
	p->data.n = e;
	p->next = S;
	S = p;
}

void output(linkstack& S)
{
	int e;
	Slnode* p;
	while (S != NULL)
	{
		p = new Slnode;  //临时节点
		e = S->data.n;
		p = S;
		S = S->next;
		delete p;
		cout << e;
	}
}

void turn(linkstack& S, int x,int n)
{
	while (x!=0)
	{
		input(S, x % n);
		x = x / n;
	}
	output(S);
}

这里要注意的是，链栈是没有头节点的。

F_NCIAE_A231_2022/3/16