数据结构栈数制转换

2016-04-12 21:08:00 weixin_30905981 阅读数 13

常用的进制有四种:二进制、八进制、十进制、十六进制。他们之间都可以进行俩俩的互相转换;

有一种转换方法为余数法,其转换思想与栈的存储正好适应。适用于十进制转换为二进制、八进制、十六进制;

余数法:连续除以基,直到商为0,从低到高纪录数值为转换结果。

因为结果是从低到高纪录的所以使用到栈,先将结果全部入栈之后再全部出栈。

实现函数代码(用到之前写的数据结构-栈的顺序表达结构的头文件):

 1void conversion(int a, int b)  //参数为从a进制转换为b进制
2 { 3 int num = 0; 4 char z = 'A'; 5 printf("请输入你想要转换的%d进制数",a); 6 scanf("%d", &num); 7 while(num) 8 { 9 Push(Scale, num%b);  //取余数逐个进栈 10 num /=b;  //求商 11 } 12 int e = 0; 13 printf("转换为%d进制数为:", b); 14 while(!StackEmpty(Scale)) 15 { 16 Pop(Scale, e);   //逐个出栈 17 if(e >= 10 && e <= 15)  //结果为十六进制时用到转换为字母 18 printf("%c", z+e-10); 19 else 20 printf("%d", e); 21 } 22 printf("\n"); 23 }

这样就用栈实现了由十进制转换为其他进制的算法。

接下来我们讨论下其他的进制转换为十进制的算法:实现方法可以用按权展开法,想了想。这种方法并没有什么好的算法解决。无非是两个循环嵌套,外循环一位位的走,内循环将每一位进行求幂。因为并没有涉及数据结构的思想(我认为这样写很麻烦)所以就只是讨论讨论实现方法,就不抛出代码了。等我想到更好的解决方法后在补上。

好了,现在与十进制有关的转换都实现了,还剩下三类:1、二进制与八进制;2、二进制与十六进制;3、八进制与十六进制;其实这三类都一样的实现。都先转换为十进制在用十进制余数法用栈去求。这样这三类就可以用上面介绍的与十进制有关的转换方法实现了;其实在解决其他进制转换为十进制上,如果只是输出的话完全可以用printf格式化输出实现。%o八进制输出,%x十六机制输出,%d十进制输出。当是格式化输出里没有对应的二进制输出,这点只能写函数实现。

 

转载于:https://www.cnblogs.com/ABook/p/5384469.html

2019-04-13 20:05:22 qq_44713855 阅读数 160

程序如下:(当程序执行后,比如数个1348,结果无限返回2,,是什么问题呢,,跪求大佬。)
#include
#include
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int ElemType;
typedef int Status;
using namespace std;
typedef struct
{
int *base;
int *top;
int stacksize;
}SqStack;
Status initStack(SqStack &S)
{
S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if (!S.base)
{
cout << “内存分配失败!” << endl;
exit(0);
}
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return 1;
//判断栈是否为空
}
Status push(SqStack &S, ElemType e)
{
if (S.top - S.base >= S.stacksize)
{
S.base = (ElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(ElemType));
if (!S.base)
{
exit(0);
}
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return 1;
}//插入元素e为栈顶元素
Status StackEmpty(SqStack S)
{
if (S.top == S.base)
return 1;
else
return 0;
}

Status pop(SqStack S, ElemType &e)
{
if (S.base == S.top)
{
cout << “栈为空!” << endl;
return 0;
}
e = *–S.top;
return 1;
}//删除栈顶元素,并返回
int main()
{
ElemType e;
SqStack S;
initStack(S);
int N;
cin >> N;
while (N)
{
push(S, N % 8);
N /= 8;
}
while (!StackEmpty(S))
{
pop(S, e);
cout << e;
}
cout << endl;
system(“pause”);
return 1;
}

2019-07-04 20:37:08 qq_22847457 阅读数 452

1.案例分析

  • 当将一个十进制整数N转换为八进制数时,在计算过程中,把N与8求余得到的八进制数的各位依次进栈,计算完毕后将栈中的八进制数依次出栈输出,输出结果就是待求得的八进制数。

2.算法步骤

  • ①初始化一个空栈S。
  • ②当十进制数N非零时,循环执行以下操作:
    • 把N与8求余得到的八进制数压入栈S;
    • N更新为N与8的商。
  • ③当栈S非空时,循环执行以下操作:
    • 弹出栈顶元素e;
    • 输出e

3.算法描述

void conversion(int N) 
{//对于任意一个非负十进制数,打印输出与其等值的八进制数
	int e;
	LinkStack S;
	if (InitStack(S))
	{
		printf("链栈S初始化成功!\n");
	}
	else
	{
		printf("链栈S初始化失败!\n");
	}
	while (N) //当N非零时,循环
	{
		Push(S, N % 8);    // 把N与8求余得到的八进制数压入栈S
		N = N / 8;      // N更新为N与8的商
	}
	printf("转化为八进制数是:");
	while (S) // 当栈S非空时,循环
	{
		Pop(S, e); //弹出栈顶元素e
		printf("%d", e); //输出e
	}
	
}

4.代码实现

  • main.cpp
#include <iostream>

using namespace std;

// 链栈的存储结构
typedef struct StackNode
{
	int data;
	struct StackNode *next;
}StackNode, *LinkStack;

// 初始化
int InitStack(LinkStack &S)
{
	S = NULL;   // 将栈顶指针置空
	return 1;
}

// 入栈
int Push(LinkStack &S, int e)
{
	//元素e入栈
	StackNode *p;
	p = new StackNode;  // 生成新节点

	p->data = e;        // 将新节点数据域置为e
	p->next = S;        // 将新节点插入栈顶
	S = p;             // 修改栈顶指针
	return 1;         // 链栈要注意指针的方向是从栈顶指向栈底的 
}

// 出栈
int Pop(LinkStack &S, int &e)
{
	if (S == NULL)
	{
		return 0;    // 栈空
	}
	e = S->data;    //将栈顶元素赋值给e
	StackNode *p;
	p = S;         // 临时保存栈顶元素空间,准备释放
	S = S->next;    // 修改栈顶指针
	delete p;     // 释放原栈顶元素空间
	return 1;
}


// 数制的转换(链栈实现)
void conversion(int N) 
{//对于任意一个非负十进制数,打印输出与其等值的八进制数
	int e;
	LinkStack S;
	if (InitStack(S))
	{
		printf("链栈S初始化成功!\n");
	}
	else
	{
		printf("链栈S初始化失败!\n");
	}
	while (N) //当N非零时,循环
	{
		Push(S, N % 8);    // 把N与8求余得到的八进制数压入栈S
		N = N / 8;      // N更新为N与8的商
	}
	printf("转化为八进制数是:");
	while (S) // 当栈S非空时,循环
	{
		Pop(S, e); //弹出栈顶元素e
		printf("%d", e); //输出e
	}
	
}

int main()
{
	int n;
	
	printf("请输入一个十进制数:");
	scanf("%d", &n);
	
	conversion(n);
	printf("\n");
	
	system("pause");

	return 0;
}
  • 运行结果

2017-03-28 13:39:09 zhongcanw 阅读数 269


将十进制整数转换为k进制数,在此过程中,k进制数是从低到高位产生的,但最后得到的k进制数是从高位到低位读出

的,与生成过程正好相反。因为可以利用一个栈s,按k进制各位的生成顺序进栈,最后再从栈中逐个读取各位数字。

	void  exchange(int value,int n)
	{
		stack<int> s;
		while(value>0)
		{
			s.push(value%n);
			value=value/n;
		}
		while(!s.empty())
		{
			
			cout<<s.top();
			s.pop();
		}
	}

2018-07-25 10:56:14 wu_comet 阅读数 216

//因为数值转换的最后的结果是逆序排列,故可以用堆来实现

//这里用静态的顺序栈来实现数制的转换

include<iostream>
#include<stdio.h>
using namespace std;

#define max_stacksize 200

typedef int ElemType;
typedef struct SqStack{
    ElemType Stack_arry[max_stacksize];
    int top;
}SqStack;


void init_stack(SqStack &s){         //初始化协议栈 
    s.top=-1;
}

int push(SqStack &s,int x){         //进栈操作 
    if(s.top>=max_stacksize-1){
        printf("栈满!");
    }
    else{
        s.Stack_arry[++s.top]=x;
    }
    return 0;
}

int pop(SqStack &s,int &x){        //退栈操作 
    if(s.top==-1){
        printf("栈空!");    
    }
    else{
        x=s.Stack_arry[s.top--]; 
    } 
    return x;
}

void conversion(int n,int d){  //将n进制的数转化为d进制的数
    SqStack s;
    init_stack(s);
    int b,e;
    while(n!=0){
        b=n%d;             //求余
        n=n/d;               //求商
        push(s,b);

    } 
    while(s.top!=-1){
      pop(s,e);
      printf("%d",e);
   }
}

int main(){
    int N,D;
    cin>>N>>D;
    conversion(N,D);
    return 0;
}