利用栈实现进制转换

2023-12-21 08:05:15

一、栈的概念

栈是一种基本的数据结构，分为顺序栈和链式栈两种。栈的基本特点是先入栈的元素后离栈。在理解这一特点时，我们可以把他当做一个箱子，先放入的东西会到最下面，例如下图：将1、2、3、4依次保存入栈，最后放入栈中的元素会保存在栈的顶部。也就是说，在将元素读出栈时，与入栈的顺会是正好相反的。

二、栈基本操作的代码实现

1.宏定义

typedef int Elementype;
typedef struct Node *PNode;
typedef struct Stack *PStack;
typedef struct Node Node;
typedef struct Stack Stack;

2.结构体的创建

typedef struct Node {
    Elementype data;
    struct Node *next;
} Node, *PNode;

typedef struct Stack {
    PNode top;
    PNode bottom;
} Stack, *PStack;

3.栈中节点与栈的创建

PNode Create_Node() {
    PNode p = (PNode) malloc(sizeof(Node));
    if (!p) {
        printf("节点未创建成功");
        exit(-1);
    }
    p->data = 0;
    p->next = NULL;
    return p;
}
PStack Create_Stack() {
    PStack s;
    s = (PStack) malloc(sizeof(Stack));
    if (!s) {
        printf("栈未创建成功");
        exit(-1);
    } else {
        s->top = s->bottom;
        s->top = NULL;
        return s;
    }
}

4.入栈以及遍历操作

void Push_Stack(PStack S, int i) {
    PNode p = Create_Node();
    if (!p) {
        printf("节点未创建成功");
    }
    p->data = i;
    p->next = S->top;
    S->top = p;
}

void Traverse_Stack(PStack S) {
    PNode p;
    p = S->top;
    while (p != S->bottom) {
        printf("%d", p->data);
        p = p->next;
    }
    printf("\n");
}

三、实现进制转换

我们知道在进行进制转换时，用原数除以要转换的进制，直到余数为零。最后将所得余数倒序排列，即可得到转换后的数字。利用这一特点，我们可以将每次的余数保存进栈中，最后遍历得到栈中元素，正好是转化后数字的正确顺序。下面是代码实现（在上面栈的各项操作实现的情况下)。

int main() {
    PStack S = Create_Stack();
    int n;
    printf("请输入需要转化的数字");
    scanf("%d", &n);
    while (n) {
        Push_Stack(S, n % 2);
        n = n / 2;
    }
    Traverse_Stack(S);
}

运行结果：

欢迎大家评论区讨论。

码农公寓