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

男娘i 2022-05-09 12:08 203阅读 0赞

### 作业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;
    }