用栈的思想实现将一个十进制数字转换为八进制--数据结构-Toy模板网

这篇具有很好参考价值的文章主要介绍了用栈的思想实现将一个十进制数字转换为八进制--数据结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

用栈的思想实现将一个十进制数字转换为八进制--数据结构

魔王的介绍：😶‍🌫️一名双非本科大一小白。

魔王的目标：🤯努力赶上周围卷王的脚步。

魔王的主页：🔥🔥🔥大魔王.🔥🔥🔥
❤️‍🔥大魔王与你分享：“并不是你喝了一瓶雪花，就有人愿意陪你勇闯天涯。”

前言

学完栈的思想后，我们知道了栈只能从栈顶进出，如果栈顶位置不出，就没办法操纵栈里的其他元素，那么你是否真的理解栈了呢，那就看看你能不能将标题这个进制转换的题用栈的思想实现吧。如果感觉这一题不够，可以点击这里20. 有效的括号跳转到我的另一篇刷题总结，里面的这个题挺有意思，必须运用栈区的思想才能解决，如果不忙的话，希望给个三连❤️‍🔥（点赞）✨（收藏）🥳（评论）！

一、直接十进制转八进制

思路

想要做出这题，那就先实现一下最简单的单纯的十进制转八进制吧。
思路：类比我们一直用的十进制数字，八进制就是大于等于8进1，就这。

代码实现

//输出八进制
#include <stdio.h>
void conversion(int n)
{
	if (n >= 8)
	{
		conversion(n / 8);//递归思想
		printf("%d", n%8);
	}
	else
	{
		printf("%d", n);
	}
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	conversion(n);
	return 0;
}

二、栈的思想实现

说明

我们可以通过两种方式实现：
第一种是顺序表，通过尾插实现栈，当然最后打印操作也只能从后往前打印，遵守后进先出的思想，也就会栈的思想。
第二种是链表，通过让首插实现。最后打印的操作是从第一个结点开始，每次弄完要出栈，才能访问下一个结点。
下面是采用顺序表实现的。

思路

上面那个直接实现是用递归（递推回归）在每个栈帧空间结束时打印出相应数字，那么我们用栈的思想的话就需要压栈，先把要打印的东西放进栈里，然后用栈的思想（后进先出），从栈顶开始逐个打印，而且每次打印完栈顶元素，要让栈顶元素弹出（删掉）之后才能访问接下来的元素（后进先出，只能从栈顶进出）。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int DateType;

typedef struct Stack
{
	DateType* arr;
	int sz;//元素的个数，是从一开始的，所以访问时要-1才是对应的元素。
	int capacity;
}Stack;

void CheckStack(Stack* s)
{
	assert(s);
	if (s->sz == s->capacity)
	{
		Stack* temp = (DateType*)realloc(s->arr, sizeof(DateType) * s->capacity * 2);
		assert(temp);//判断是否开辟成功
		s->arr = temp;
		temp = NULL;//野指针置空
		s->capacity *= 2;
	}
}

void PushStack(int n, Stack* s)
{
	assert(s);
	CheckStack(s);
	s->arr[s->sz] = n;
	s->sz++;
}

bool EmptyStack(Stack*s)
{
	assert(s);
	if (s->sz == 0)//s->sz是元素个数，所以为0是就是空，返回真。
	{
		return true;
	}
	return false;
}

void InitStack(Stack* s)
{
	assert(s);
	s->arr = malloc(sizeof(DateType) * 5);
	s->sz = 0;
	s->capacity = 5;
}

void PopStack(Stack* s)
{
	assert(s);
	assert(s->sz);//s->sz是个数，所以为0时没意义，如果为0，应该是进不去的，但是既然进来了，那肯定某个地方错了。
	s->sz--;
}

void conversion(int n, Stack* s)
{
	assert(s);
	if (n >= 8)
	{
		PushStack(n % 8, s);
		conversion(n / 8, s);
	}
	else
		PushStack(n, s);
}

int main()
{	
	Stack s;
	InitStack(&s);
	int* arr = NULL;
	int n = 0;
	scanf("%d", &n);
	conversion(n, &s);
	while(!EmptyStack(&s))//不是空进入循环，是空就退出
	{
		printf("%d", s.arr[s.sz-1]);
		PopStack(&s);
	}
	return 0;
}