数据结构作业的代码——————利用栈实现进制转换

作业code3

• 十进制转换二进制（代码已经给大家，详情参考“PPT-Jk17数据结构第二次上机任务-实验3-2018年9月26日”）
• 实现十进制与任意进制的转换
• 用顺序表和链表两种数据结构实现上述两类功能

---

顺序栈实现进制转换

#include <stdio.h>
#include <malloc.h>
#include <iostream>
using namespace std;
typedef int SElemType;
typedef int Status;
#define INIT_SIZE 100
#define STACKINCREMENT 10
#define Ok 1
#define Error 0
#define True 1
#define False 0
typedef struct
{
    SElemType *base;
    SElemType *top;
    int stacksize;
} SqStack;

//初始化栈
Status InitStack(SqStack *s)
{
    s->base = (SElemType *)malloc(INIT_SIZE * sizeof(SElemType));
    if(!s->base)
    {
        puts("存储空间分配失败！");
        return Error;
    }
    s->top = s->base;
    s->stacksize = INIT_SIZE;
    return Ok;
}

//清空栈
Status ClearStack(SqStack *s)
{
    s->top = s->base;
    return Ok;
}

//栈是否为空
Status StackEmpty(SqStack *s)
{
    if(s->top == s->base)
        return True;
    else
        return False;
}

//销毁栈
Status Destroy(SqStack *s)
{
    free(s->base);
    s->base = NULL;
    s->top = NULL;
    s->stacksize=0;
    return Ok;
}

//获得栈顶元素
Status GetTop(SqStack *s, SElemType &e)
{
    if(s->top == s->base)
        return Error;
    e = *(s->top - 1);
    return Ok;
}

//压栈
Status Push(SqStack *s, SElemType e)
{
    if(s->top - s->base >= s->stacksize)//栈满
    {
        s->base = (SElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(SElemType));
        if(!s->base)
        {
            puts("存储空间分配失败！");
            return Error;
        }
        s->top = s->base + s->stacksize;//修改栈顶位置
        s->stacksize += STACKINCREMENT;//修改栈长度

    }
    *s->top++ = e;
    return Ok;
}

//弹栈
Status Pop(SqStack *s, SElemType *e)
{
    if(s->top == s->base)
        return Error;
    --s->top;
    *e = *(s->top);
    return Ok;
}

//遍历栈
Status StackTraverse(SqStack *s,Status(*visit)(SElemType))
{
    SElemType *b = s->base;//此处不能直接用base或top移动，即不能改变原栈的结构
    SElemType *t = s->top -1;
    while(t >= b)
        visit(*t--);
//        visit(*b++);
    printf("\n");
    return Ok;
}

Status visit(SElemType c)
{
    printf("%d",c);
    return Ok;
}

int main()
{
        SqStack a;
        SqStack *s = &a;
        SElemType e,n;
        InitStack(s);
        printf("请输入十进制数：");
        cin>>n;
        printf("\n%d的二进制数是:",n);
        InitStack(s);
        while(n)
        {
                e = n%2;
                Push(s,e);
                n/=2;
        }
        StackTraverse(s,visit);
        puts("");
        Destroy(s);
    return 0;
}

---

链式栈实现进制转换

#include<bits/stdc++.h>
#define ElemType  int
#define SElemType int
#define Status    int
#define ERROR     0
#define OK        1

using namespace std;

typedef struct StackNode{//构造栈的节点
        ElemType data;
        struct StackNode *next;
}StackNode,*LinkStack;

LinkStack S,p;

Status InitStack(LinkStack &S)//初始化栈
{
        S=NULL;
        return OK;
}

Status Push(LinkStack &S,SElemType &e)//在栈顶插入元素e
{
        p = new StackNode;      //生成新节点
        p->data = e;            //将新节点数据域置为e
        p->next = S;            //将新节点插入栈顶
        S = p;                  //修改栈顶指针为p;
        return OK;
}

Status Pop(LinkStack &S,SElemType &e)//删除栈顶元素，用e返回其值
{
        if(S == NULL)     return ERROR; //栈空
        e = S->data;                    //将栈顶元素赋给e
        p = S;                          //用p临时保存栈顶元素空间，以备释放
        S = S->next;                    //修改栈顶指针
        delete p;                       //释放栈顶元素的空间
        return OK;                      //
}

Status GetTop(LinkStack S)
{
        if(S != NULL)
                return S->data;
}

void display(struct StackNode* head)//遍历栈
{
    struct StackNode *current;
    current = head;
    if(current!= NULL)
    {
        printf("Stack: ");
        do
        {
            printf("%d ",current->data);
            current = current->next;
        }
        while (current!= NULL);
        printf("\n");
    }
    else
    {
        printf("The Stack is empty!\n");
    }
}

int empty(struct StackNode* head)
{
    return head == NULL ? 1 : 0;
}


int main()
{
        int n,e,x;
        printf("请输入十进制数：");
        cin>>n;
        printf("\n%d的二进制数是:",n);
        InitStack(S);
        while(n)
        {
                e = n%2;
                Push(S,e);
                n/=2;
        }
        while(!empty(S))
        {
                Pop(S,e);
                printf("%d",e);
        }
        puts("");
        return 0;
}