数据结构与算法 练习（三）

数制的转换

1. 初始化一个空栈S
2. 当十进制N非零时,循环执行以下操作
   • 把N与8求余得到的八进制数压入栈S;
   • N更新为N与8的商;
3. 当栈S非空时,循环执行以下操作
   • 弹出栈顶元素e;
   • 输出e;

基础设置

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

/* 顺序栈结构 */
typedef struct {
    SElemType data[MAXSIZE];
    int top; /* 用于栈顶指针 */
}SqStack;

// 构建一个空栈S
Status InitStack(SqStack *S){
    
    S->top = -1;
    return OK;
}


// 将栈置空
Status ClearStack(SqStack *S){
    
    //疑问: 将栈置空,需要将顺序栈的元素都清空吗?
    //不需要,只需要修改top标签就可以了.
    S->top = -1;
    return OK;
}

// 判断顺序栈是否为空;
Status StackEmpty(SqStack S){
    if (S.top == -1)
        return TRUE;
    else
        return FALSE;
}

// 返回栈的长度
int StackLength(SqStack S){
    return S.top + 1;
}

// 获取栈顶
Status GetTop(SqStack S,SElemType *e){
    if (S.top == -1)
        return ERROR;
    else
        *e = S.data[S.top];
    
    return OK;
    
}

// 插入元素e为新栈顶元素
Status PushData(SqStack *S, SElemType e){
    
    //栈已满
    if (S->top == MAXSIZE -1) {
        return ERROR;
    }
    
    //栈顶指针+1;
    S->top ++;
    //将新插入的元素赋值给栈顶空间
    S->data[S->top] = e;
    
    return OK;
}

// 删除S栈顶元素,并且用e带回
Status Pop(SqStack *S,SElemType *e){
    
    //空栈,则返回error;
    if (S->top == -1) {
        return ERROR;
    }
    
    //将要删除的栈顶元素赋值给e
    *e = S->data[S->top];
    //栈顶指针--;
    S->top--;
    
    return OK;
}

// 从栈底到栈顶依次对栈中的每个元素打印
Status StackTraverse(SqStack S){
    int i = 0;
    printf("此栈中所有元素");
    while (i<=S.top) {
        printf("%d ",S.data[i++]);
    }
    printf("\n");
    return OK;
}

核心代码

void conversion(int N) {
    
    SqStack S;
    SElemType e;
    //1.初始化一个空栈S
    InitStack(&S);
    
    //2.当十进制N非零时,循环执行以下操作
    while (N) {
        PushData(&S, N%8);
        N = N/8;
    }
    
    //3.当栈S非空时,循环执行以下操作
    while (!StackEmpty(S)) {
        Pop(&S, &e);
        printf("%d\n",e);
    }
    
}