论坛 › 数据结构与算法 › 栈、进栈、出栈、二进制转八进制

奥普瓯江 发表于 2021-10-29 18:14:39

栈、进栈、出栈、二进制转八进制

本帖最后由 奥普瓯江 于 2021-10-30 17:43 编辑

原理：

备注：

        这里有一个错误就是在释放malloc上，因为我对malloc函数理解有问题，所以造成了，多次释放
void DeStack(SqStack **E)          //释放内存
{
    Elemtype *temp;

    for(int i = 0; i < ((*E)->StackSize); i++)
    {
      temp = (*E)->base;
      (*E)->base++;
      free(temp);
    }
    free(*E);
}
运行错误
我一共用malloc在能存中申请了MAXSIZE个空间，是一次性申请的所以释放也应该是一次性的，我只需要释放一次(*E)->base但是我在这个程序中却释放了，(*E)->StackSize次所以在调试时会出现内存泄漏，或者时提示，用vs6.0进行调试会出现以下提示



在CodeBlock中调试会出现执行free(temp);这个代码第三遍后出现错误结束程序





代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
#define MAXSIZE 100

typedef int Elemtype;

//建立类
typedef struct
{
    Elemtype *base;   //尾指针
    Elemtype *top;      //头指针
    int StackSize;      //剩余空间
}SqStack;

void InitStack(SqStack **E);      //初始化创建空栈
void PushStack(SqStack **E, Elemtype N);          //进栈
Elemtype PopStack(SqStack *E);          //出栈
void DeStack(SqStack **E);          //释放内存
bool StackEmpty(SqStack *E);      //判断真假

bool StackEmpty(SqStack *E)      //判断真假
{
    return E->top == E->base;
}

void DeStack(SqStack **E)          //释放内存
{
    free((*E)->base);
    free(*E);
}

Elemtype PopStack(SqStack *E)         //出栈
{
    E->top--;
    E->StackSize++;
    return *(E->top);
}

void PushStack(SqStack **E, Elemtype N)          //进栈
{
    if((*E)->top - (*E)->base >= (*E)->StackSize)
    {
      (*E)->base = (Elemtype *)realloc((*E)->base, ((*E)->StackSize + MAXSIZE) * sizeof(Elemtype ));      //复制前面的base中的数据进入到扩大后的base中
      if(!(*E)->base)
      {
            printf("内存分配失败本程序结束运行\n");          //判断是内存地址是否分配成功
            exit(0);
      }
      (*E)->top = (*E)->base + (*E)->StackSize;         //因为以是新的内存空间所有，top中标记的地址也是错误的，所以按照以占用多少空间从新赋予top地址（realloc已经把数据复制过来了）
      (*E)->StackSize = (*E)->StackSize + MAXSIZE;      //从新赋予记述节点数据
    }
    *((*E)->top) = N;
    (*E)->top++;
    (*E)->StackSize--;

}
void InitStack(SqStack **E)      //初始化创建空栈
{
    *E = (SqStack *)malloc(sizeof(SqStack ));
   (*E)->base = (Elemtype *)malloc(MAXSIZE * sizeof(Elemtype ));   //向指针类中的base赋予空间

    if(!(*E)->base)
    {
      printf("内存分配失败本程序结束运行\n");          //判断是内存地址是否分配成功
      exit(0);
    }
    (*E)->top = (*E)->base;         //把初始地址传给头指针
    (*E)->StackSize = MAXSIZE;      //初始剩余空间数量
}
int main()
{
    SqStack *T, *F;

    char litte;
    Elemtype N = 0;

    InitStack(&T);
    InitStack(&F);

    //把ASCII传给字符串
    scanf("%s", litte);

    for(int i = 0; litte != 0; i++ )
    {
      litte = litte - '0';
      PushStack(&T,litte);
    }

    //转八进制
    while(!StackEmpty(T))
    {
       for(int i = 0; i < 3 && !StackEmpty(T); i++)
       {
         N += PopStack(T) * pow(2, i);      //倒着出栈运算
       }
       PushStack(&F,N);                         //在进栈
       N = 0;
    }
    while(F->top != F->base)
    {
      printf("%d", PopStack(F));            //打印栈中的每一个数据
    }

    DeStack(&T);
    DeStack(&F);
    return 0;
}

查看完整版本: 栈、进栈、出栈、二进制转八进制