栈

数制的转换

顺序栈

头部

#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100
typedef int SElemType;  // 定义int类型的SElemType名称
typedef int Status;     // 定义int类型的Status名称
typedef struct stack    // 声明栈结构
{
    SElemType *base;    // 栈底指针
    SElemType *top;     // 栈顶指针
    int stacksize;      // 栈的大小
}stack; // 栈名称

函数声明

// 声明各项操作函数
Status InitStack(stack *S);
int StackEmpty(stack *S);
int Push(stack *S, int n);
int Pop(stack *S, int *e);

主函数

int main(void)
{
    int N, M;
    printf("请输入十进制数：");
    scanf("%d", &N);
    printf("请输入你要转换的数制(小于十进制)：");
    scanf("%d", &M);
    stack S;    // 定义栈
    InitStack(&S);  // 初始化栈
    while(N)
    {
        Push(&S, N % M);    // 取模入栈
        N = N / M;      
    }
    while (!StackEmpty(&S))
    {
        int e;
        Pop(&S, &e);
        printf("%d", e);
    }
    return 0;
}

初始化

// 初始化
Status InitStack(stack *S)
{
    S->base = (int *)malloc(sizeof(int)*MAXSIZE);   // 给S->base分配 int大小*MAXSIZE 的空间
    if(!S->base)    // 若S->base为0则分配空间失败
        return 0;
    S->top = S->base;   // 栈顶指向栈底
    S->stacksize = MAXSIZE;
    return 1;
}

判断是否为空

// 判断是否为空
int StackEmpty(stack *S)
{
    if (S->top==S->base)
        return 1;
    else
        return 0;
}

入栈

// 入栈
int Push(stack *S, int n)
{
    if(S->top-S->base==S->stacksize)    // 栈满
        return 0;
    *S->top++ = n;  // 元素n压入栈顶，栈顶指针加一
    return 1;
}

出栈

// 出栈
int Pop(stack *S, int *e)
{
    if(S->top == S->base)   // 栈空
        return 0;
    *e = *--S->top; // 元素
    return 1;
}
// 这里出栈使用了指针传递栈顶值

也可以直接返回栈顶值，改动部分为

int Pop(stack *S);
printf("%d", Pop(&S));
int Pop(stack *S)
{
    if(S->top == S->base)   // 栈空返回-1
        return -1;
    else
        return *--S->top;   // 栈不空返回栈顶的值
}

链栈

头部

#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 100;
typedef int SElemType;

typedef struct node
{
    SElemType data; // 栈结点的数据域
    struct node *next;  // 栈结点的指针域
} node;

typedef struct LinkStack
{
    int size;
    struct node *base;
    struct node *top;
}LinkStack; // 栈链的数据结构

函数声明

LinkStack *InitStack(LinkStack *S);
int StackEmpty(LinkStack* S);
int Push(LinkStack* S, int n);
int Pop(LinkStack* S, int *e);

主函数

int main(void)
{
    int N, M;
    printf("请输入十进制数：");
    scanf("%d", &N);
    printf("请输入你要转换的数制(小于十进制)：");
    scanf("%d", &M);
    LinkStack S;
    InitStack(&S);
    while(N)
    {
        Push(&S, N % M);
        N = N / M;
    }
    while (!StackEmpty(&S))
    {
        int e;
        Pop(&S, &e);
        printf("%d", e);
    }
    return 0;
}

初始化

LinkStack *InitStack(LinkStack *S)
{
    S->base = (node *)malloc(sizeof(node)); // 为栈底分配存储空间
    S->size = 0;    // 链栈大小
    S->base = S->top = 0;   // 栈顶栈底为0
}

判断是否为空

int StackEmpty(LinkStack* S)
{
    if(S->top == S->base)
        return 1;
    else
        return 0;
}

入栈

int Push(LinkStack* S, int n)
{
    node *p = (LinkStack *)malloc(sizeof(LinkStack));
    p->data = n;    // 将值赋给p指针的数据域
    p->next = S->top;   
    S->top = p;
    S->size++;
    return 1;
}

具体入栈过程

出栈

int Pop(LinkStack* S, int *e)
{
    if(S->top == S->base)
        return 0;
    node *p = S->base;
    *e = S->top->data;
    p = S->top;
    S->top = S->top->next;
    free(p);
    return 1;
}

具体出栈过程