基于链栈的进制转换算法

2021/9/28 14:11:00

编程Tag： node 算法 int top 进制 nullptr LinkStack 链栈

本文主要是介绍基于链栈的进制转换算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

基于链栈的进制转换算法

题目

将十进制数转换为其它进制数并输出（栈）

分析思路

进制转换在数学中我们使用的是短除法

一步步取余运算

最终从下往上拼接

好比这样：

时间仓促，字迹潦草，见谅

那么我们利用栈的后进先出(LIFO)的特性去做。

基本数据结构-链栈的实现

LinkStack.h

/*
*链栈
*/

#include<iostream>
using namespace std;

struct Node
{
    int val;  //值域
    Node* under;  //栈嘛 往下
};


class LinkStack
{
private:
    /* data */
    Node* top;
public:
    LinkStack(/* args */);
    ~LinkStack();
    void push(int newData);
    int pop();          //弹出(删除)栈顶元素
    int GetTop();       //取出栈顶元素，并不删除
    int Empty();        //判断是否为空栈 1为空 0为非空
    void printStack();  //遍历输出栈
};

LinkStack.cpp

#include"LinkStack.h"

LinkStack::LinkStack()
{
    cout<<"初始化链栈"<<endl;
    this->top=nullptr;
    //top->under=nullptr;
}

LinkStack::~LinkStack()
{
    Node* workNode=top;
    while(top!=nullptr)
    {
        Node* tempNode=top;
        top=top->under;
        delete tempNode;
    }
}

void LinkStack::push(int newData)
{
    Node* newNode=new Node;
    newNode->val=newData;
    //
    Node* oldTop=this->top;
    //
    this->top=newNode;
    newNode->under=oldTop;
}

int LinkStack::pop()
{
    if(top==nullptr)
    {
        cout<<"链栈为空"<<endl;
        throw "链栈为空";
    }
    Node* tempNode=top;
    int tempVal=top->val;
    top=top->under;  //栈顶下移
    delete tempNode;
    return tempVal;
}

int LinkStack::GetTop()
{
    if(top==nullptr)
    {
        cout<<"链栈为空"<<endl;
        throw "链栈为空";
    }
    return this->top->val;
}

int LinkStack::Empty()
{
    if(top==nullptr)
    {
        return 1;  //1代表链栈为空
    }
    else
    {
        return 0;  //0代表链栈非空
    }
}

void LinkStack::printStack()
{
    Node* workNode=top;
    while(workNode!=nullptr)
    {
        cout<<workNode->val<<endl;
        workNode=workNode->under;
    }
}

链栈测试

#include"LinkStack.h"

int main()
{
    LinkStack s1;
    s1.push(8);
    s1.push(9);
    s1.push(10);
    s1.printStack();
    // cout<<s1.Empty()<<endl;
    cout<<s1.pop()<<endl;
    // cout<<s1.Empty()<<endl;
    system("pause");
    return 0;
}

进制转换算法

时间仓促，未经优化，但可以看到直观过程

Turn.h

#include"LinkStack.h"
#include<math.h>        //用于计算10的n次方

//进制转换算法
//将十进制数字转换为k进制数字
//基于链栈实现
//双栈实现？

//英语：  Convert-转换
//参数解释： old为要被转换的十进制数组 k为目标进制
void Convert(int old,int k)
{
    int n=0;      //相当于累加器
    int res=0;  //最终转换完成后的结果
    LinkStack l1;
    while(old>=k)
    {
        cout<<"mod前："<<old<<endl;
        cout<<"old%k="<<old%k<<endl;
        l1.push(old%k);
        old=old/k;
        cout<<"old/k="<<old<<endl;
        cout<<"-------"<<endl;
        n++;
    }
    n++;
    l1.push(old);
    cout<<"n="<<n<<endl;
    int time=n;
    for(int i=0;i<time;i++)
    {
        cout<<"for循环中"<<endl;
        int pop=0;
        pop=l1.pop();
        cout<<"pop="<<pop<<endl;
        cout<<"-----"<<endl;
        int temp=0;
        n=n-1;
        temp=pop*pow(10,n);
        cout<<"temp="<<temp<<endl;
        res+=temp;
    }
    cout<<"最终结果为"<<res<<endl;
    cout<<old<<endl;
    l1.push(old);
    cout<<"累加器："<<n<<endl;
    cout<<"<<<<>>>>"<<endl;
    l1.printStack();
}