找BUG


layout: default title: 找BUG category: [技术, C/C++] comments: true ---

找一找BUG

一段代码,实现一个pop,push,和getmin都是O(1)的方法.

最初源代码

伙伴代码如下,代码的地址可以通过这个访问: Ubuntu Pastebin https://paste.ubuntu.com/p/cX2Cq56PYt/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 1000
#define STACKINCREMENT 100
#define OVERFLOW -2
#define INFEASIBLE -1

typedef int ElemType;
typedef int Status;
typedef struct
{
    ElemType *base;
    ElemType *top;
    int stacksize, maxstacksize;
}SqStack;

Status InitStack(SqStack);           //初始化栈
Status DestoryStack(SqStack);        //销毁栈
Status ClearStack(SqStack);          //清空栈
ElemType StackLength(SqStack);         //返回栈长度
ElemType GetTop(SqStack);              //返回栈顶元素
Status Push(SqStack, ElemType);      //入栈
ElemType Pop(SqStack);     //出栈
Status StackTraverse(SqStack);         //遍历栈
Status StackEmpty(SqStack);    //检查栈空

//实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作

//要求:1. pop、push、getMin操作的时间复杂度都是O(1)
//      2. 设计的栈类型可以使用现成的栈结构

#include <stdio.h>
#include "stack.h"

void push(int);
int pop(void);
int getmin(void);

int main()
{
    int newIn;

    while((newIn = getchar()) != EOF)
    {   
        push(newIn);
    }

    printf("pop is %d\n", pop());
    printf("min is %d\n", getmin());

    return 0;
}

SqStack stackData;
SqStack stackMin;

InitStack(stackData);
InitStack(stackMin);

//设计的满足题目要求的入栈操作
void push(int newNum)
{
    if(StackEmpty(stackMin))
    {
        Push(stackMin, newNum);     
    }
    else if(newNum <= GetTop(stackMin))
    {
        Push(stackMin, newNum);
    }
    Push(stackData, newNum);
}

//满足题目要求的出栈操作
int pop(void)
{
    int value;

    if(StackLength(stackData) == 0)
    {
        printf("stack is empty.\n");
        return FALSE;
    }
    value = Pop(stackData);
    if(value == GetTop(stackMin))
    {
        Pop(stackMin);
    }

    return value;
}
//满足题目要求的获取最小元素
int getMin(void)
{
    if(StackEmpty(stackMin))
    {
        printf("stack is empyt,no min number.\n");
        return FALSE;
    }
    else
    {
        return GetTop(stackMin);
    }
}

//栈的九种操作

//构造
Status InitStack(SqStack &S)
{
    S.base = (ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if(!S.base)
    {
        printf("栈空间分配失败!\n");
        return ERROR;
    }
    S.top = S.base;
    S.stacksize = 0;
    S.maxstacksize = STACK_INIT_SIZE;
    
    return OK;
}

//销毁
Status DestoryStack(SqStack &S)
{
    S.top = NULL;
    free(S.base);

    return OK;
}

//清空
Status ClearStack(SqStack &S)
{
    S.top = S.base;
    S.stacksize = 0;

    return OK;
}

//栈长
ElemType StackLength(SqStack S)
{
    return S.stacksize;
}

//栈顶
ElemType GetTop(SqStack S)
{
    if(S.top == S.base)
    {
        printf("栈为空!\n");
        return FALSE;
    }
    else
    {
        return *(S.top - 1);
    }
}

//插入
Status Push(SqStack &S, ElemType newNum)
{
    if(S.stacksize >= S.maxstacksize)
    {
        S.base = (ElemType*)realloc(S.base, (STACK_INIT_SIZE + STACKINCREMENT) * sizeof(ElemType));
        if(!S.base)
        {
            printf("重新分配栈空间失败.\n");
            return ERROR;
        }
        S.top = S.base + STACK_INIT_SIZE;
        S.maxstacksize = S.maxstacksize + STACKINCREMENT;
    }
    *S.top = newNum;
    S.top++;
    S.stacksize++;

    return OK;
}

//删除
ElemType Pop(SqStack &S)
{
    int newNum;

    if(S.top == S.base)
    {
        printf("栈为空,删除失败.\n");
        return ERROR;
    }

    S.top--;
    newNum = *S.top;
    S.stacksize--;

    return newNum;
}

//遍历
Status StackTraverse(SqStack S)
{
    if(S.top == S.base)
    {
        printf("栈中没有元素.\n");
        return FALSE;
    }
    else
    {
        ElemType *p;
        
        p = S.top;
        while(p > S.base)
        {
            p--;
            printf("%d ", *p);
        }
    }

    return OK;
}

Status StackEmpty(SqStack S)
{
    if(S.top == S.base)
    {
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}

初步更正之后代码

更改之后代码如下,同样代码可以访问: Ubuntu Pastebin https://paste.ubuntu.com/p/rV8B5NHJ9h/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 1000
#define STACKINCREMENT 100
#define OVERFLOW -2
#define INFEASIBLE -1

typedef int ElemType;
typedef int Status;
typedef struct
{
    ElemType *base;
    ElemType *top;
    int stacksize, maxstacksize;
}SqStack;

/*
//先声明也需要添加完整的类型,比较规范wk
Status InitStack(SqStack);           //初始化栈
Status DestoryStack(SqStack);        //销毁栈
Status ClearStack(SqStack);          //清空栈
ElemType StackLength(SqStack);         //返回栈长度
ElemType GetTop(SqStack);              //返回栈顶元素
Status Push(SqStack, ElemType);      //入栈
ElemType Pop(SqStack);     //出栈
Status StackTraverse(SqStack);         //遍历栈
Status StackEmpty(SqStack);    //检查栈空
*/

Status InitStack(SqStack &S);           //初始化栈
Status DestoryStack(SqStack &S);        //销毁栈
Status ClearStack(SqStack &S);          //清空栈
ElemType StackLength(SqStack  S);         //返回栈长度
ElemType GetTop(SqStack S);              //返回栈顶元素
Status Push(SqStack &S, ElemType E);      //入栈
ElemType Pop(SqStack &S);     //出栈
Status StackTraverse(SqStack S);         //遍历栈
Status StackEmpty(SqStack S);    //检查栈空


//实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作

//要求:1. pop、push、getMin操作的时间复杂度都是O(1)
//      2. 设计的栈类型可以使用现成的栈结构

//#include <stdio.h>//这里不该再次出现,要么开头一次性wk
//#include "stack.h"


//void push(int);
void push(int n);//声明需要参数,不只是类型wk
//int pop(void);
int pop();//为空可以省略,一般也没人会去写void wk
//int getmin(void);
int getmin();//同上


//为了排除错误,直接诶移到后面wk
/*
int main()
{
int newIn;

  while((newIn = getchar()) != EOF)
  { 
  push(newIn);
  }
  
    printf("pop is %d\n", pop());
    printf("min is %d\n", getmin());
    
      return 0;
      }
*/


SqStack stackData;
SqStack stackMin;

//InitStack(stackData);
//InitStack(stackMin);

//设计的满足题目要求的入栈操作
void push(int newNum)
{
    if(StackEmpty(stackMin))
    {
        Push(stackMin, newNum);     
    }
    else if(newNum <= GetTop(stackMin))
    {
        Push(stackMin, newNum);
    }
    Push(stackData, newNum);
}

//满足题目要求的出栈操作
//int pop(void)
int pop()//同上wk
{
    int value;
    
    if(StackLength(stackData) == 0)
    {
        printf("stack is empty.\n");
        return FALSE;
    }
    value = Pop(stackData);
    if(value == GetTop(stackMin))
    {
        Pop(stackMin);
    }
    
    return value;
}
//满足题目要求的获取最小元素
//int getMin(void)
int getmin()//同上wk,名字注意大小写
{
    
    if(StackEmpty(stackMin))
    {
        printf("stack is empyt,no min number.\n");
        return FALSE;
    }
    else
    {
        return GetTop(stackMin);
    }
}

//栈的九种操作

//构造
Status InitStack(SqStack &S)
{
    S.base = (ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if(!S.base)
    {
        printf("栈空间分配失败!\n");
        return ERROR;
    }
    S.top = S.base;
    S.stacksize = 0;
    S.maxstacksize = STACK_INIT_SIZE;
    
    return OK;
}
Status DestoryStack(SqStack &S)

//销毁
{
    S.top = NULL;
    free(S.base);
    
    return OK;
}

//清空
Status ClearStack(SqStack &S)
{
    S.top = S.base;
    S.stacksize = 0;
    
    return OK;
}

//栈长
ElemType StackLength(SqStack S)
{
    return S.stacksize;
}

//栈顶
ElemType GetTop(SqStack S)
{
    int t;
    if(S.top == S.base)
    {
        printf("栈为空!\n");
        return FALSE;
    }
    else
    {
        t=*(S.top - 1);
        return t;
    }
}

//插入
//Status Push(SqStack &S, ElemType newNum)
Status Push(SqStack &S, ElemType newNum)//同声明处理
{
    if(S.stacksize >= S.maxstacksize)
    {
        S.base = (ElemType*)realloc(S.base, (STACK_INIT_SIZE + STACKINCREMENT) * sizeof(ElemType));
        if(!S.base)
        {
            printf("重新分配栈空间失败.\n");
            return ERROR;
        }
        S.top = S.base + STACK_INIT_SIZE;
        S.maxstacksize = S.maxstacksize + STACKINCREMENT;
    }
    *S.top = newNum;
    
    printf("push %d.\n",newNum);
    S.top++;
    S.stacksize++;
    
    return OK;
}

//删除
ElemType Pop(SqStack &S)
{
    int newNum;
    
    if(S.top == S.base)
    {
        printf("栈为空,删除失败.\n");
        return ERROR;
    }
    
    S.top--;
    newNum = *S.top;
    S.stacksize--;
    
    return newNum;
}

//遍历
Status StackTraverse(SqStack S)
{
    if(S.top == S.base)
    {
        printf("栈中没有元素.\n");
        return FALSE;
    }
    else
    {
        ElemType *p;
        
        p = S.top;
        while(p > S.base)
        {
            p--;
            printf("%d ", *p);
        }
    }
    
    return OK;
}

Status StackEmpty(SqStack S)
{
    if(S.top == S.base)
    {
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}





int main()
{
    
    int newIn;
    InitStack(stackData);//初始化在主函数内部wk
    InitStack(stackMin);//
    //  while((newIn = getchar()) != -1)
    while((scanf("%d",&newIn)) != -1)//获取字母更改为数字wk
    {   
        push(newIn);
    }
    
    printf("pop is %d\n", pop());
    printf("min is %d\n", getmin());
    
    return 0;
}

再次更正之后代码

这次代码是在纯c里面编译通过的,主要是&符号在c里面作为形参形参似乎不行,只能全部换了,考虑到要赋值处理,就没有直接用结构体作为形参.

而是将指针作为形参进行操作,这次代码应该是可以运行了.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 1000
#define STACKINCREMENT 100
#define OVERFLOW -2
#define INFEASIBLE -1

typedef int ElemType;
typedef int Status;
typedef struct
{
    ElemType *base;
    ElemType *top;
    int stacksize, maxstacksize;
}SqStack;

/*
//先声明也需要添加完整的类型,比较规范wk
Status InitStack(SqStack);           //初始化栈
Status DestoryStack(SqStack);        //销毁栈
Status ClearStack(SqStack);          //清空栈
ElemType StackLength(SqStack);         //返回栈长度
ElemType GetTop(SqStack);              //返回栈顶元素
Status Push(SqStack, ElemType);      //入栈
ElemType Pop(SqStack);     //出栈
Status StackTraverse(SqStack);         //遍历栈
Status StackEmpty(SqStack);    //检查栈空
*/

Status InitStack( SqStack *S);           //初始化栈
Status DestoryStack( SqStack *S);        //销毁栈
Status ClearStack( SqStack *S);          //清空栈
ElemType StackLength( SqStack  S);         //返回栈长度
ElemType GetTop( SqStack S);              //返回栈顶元素
Status Push( SqStack *S, ElemType E);      //入栈
ElemType Pop( SqStack *S);     //出栈
Status StackTraverse( SqStack S);         //遍历栈
Status StackEmpty( SqStack S);    //检查栈空


//实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作

//要求:1. pop、push、getMin操作的时间复杂度都是O(1)
//      2. 设计的栈类型可以使用现成的栈结构

//#include <stdio.h>//这里不该再次出现,要么开头一次性wk
//#include "stack.h"


//void push(int);
void push(int n);//声明需要参数,不只是类型wk
//int pop(void);
int pop();//为空可以省略,一般也没人会去写void wk
//int getmin(void);
int getmin();//同上


//为了排除错误,直接诶移到后面wk
/*
int main()
{
int newIn;

  while((newIn = getchar()) != EOF)
  { 
  push(newIn);
  }
  
    printf("pop is %d\n", pop());
    printf("min is %d\n", getmin());
    
      return 0;
      }
*/


SqStack stackData;
SqStack stackMin;

//InitStack(stackData);
//InitStack(stackMin);

//设计的满足题目要求的入栈操作
void push(int newNum)
{
    if(StackEmpty(stackMin))
    {
        Push(&stackMin, newNum);        
    }
    else if(newNum <= GetTop(stackMin))
    {
        Push(&stackMin, newNum);
    }
    Push(&stackData, newNum);
}

//满足题目要求的出栈操作
//int pop(void)
int pop()//同上wk
{
    int value;
    
    if(StackLength(stackData) == 0)
    {
        printf("stack is empty.\n");
        return FALSE;
    }
    value = Pop(&stackData);
    if(value == GetTop(stackMin))
    {
        Pop(&stackMin);
    }
    
    return value;
}
//满足题目要求的获取最小元素
//int getMin(void)
int getmin()//同上wk,名字注意大小写
{
    
    if(StackEmpty(stackMin))
    {
        printf("stack is empyt,no min number.\n");
        return FALSE;
    }
    else
    {
        return GetTop(stackMin);
    }
}

//栈的九种操作

//构造
Status InitStack( SqStack* S)
{
    (*S).base = (ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if(!(*S).base)
    {
        printf("栈空间分配失败!\n");
        return ERROR;
    }
    (*S).top = (*S).base;
    S->stacksize = 0;
    S->maxstacksize = STACK_INIT_SIZE;
    
    return OK;
}
Status DestoryStack( SqStack *S)

//销毁
{
    (*S).top = NULL;
    free((*S).base);
    
    return OK;
}

//清空
Status ClearStack( SqStack *S)
{
    (*S).top = (*S).base;
    S->stacksize = 0;
    
    return OK;
}

//栈长
ElemType StackLength( SqStack S)
{
    return S.stacksize;
}

//栈顶
ElemType GetTop( SqStack S)
{
    int t;
    if(S.top == S.base)
    {
        printf("栈为空!\n");
        return FALSE;
    }
    else
    {
        t=*(S.top - 1);
        return t;
    }
}

//插入
//Status Push(SqStack &S, ElemType newNum)
Status Push( SqStack *S, ElemType newNum)//同声明处理
{
    if(S->stacksize >= S->maxstacksize)
    {
        (*S).base = (ElemType*)realloc((*S).base, (STACK_INIT_SIZE + STACKINCREMENT) * sizeof(ElemType));
        if(!(*S).base)
        {
            printf("重新分配栈空间失败.\n");
            return ERROR;
        }
        (*S).top = (*S).base + STACK_INIT_SIZE;
        S->maxstacksize = S->maxstacksize + STACKINCREMENT;
    }
    *(*S).top = newNum;
    
    printf("push %d.\n",newNum);
    (*S).top++;
    S->stacksize++;
    
    return OK;
}

//删除
ElemType Pop( SqStack *S)
{
    int newNum;
    
    if((*S).top == (*S).base)
    {
        printf("栈为空,删除失败->\n");
        return ERROR;
    }
    
    (*S).top--;
    newNum = *(*S).top;
    S->stacksize--;
    
    return newNum;
}

//遍历
Status StackTraverse( SqStack S)
{
    if(S.top == S.base)
    {
        printf("栈中没有元素.\n");
        return FALSE;
    }
    else
    {
        ElemType *p;
        
        p = S.top;
        while(p > S.base)
        {
            p--;
            printf("%d ", *p);
        }
    }
    
    return OK;
}

Status StackEmpty( SqStack S)
{
    if(S.top == S.base)
    {
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}





int main()
{
    
    int newIn;
    InitStack(&stackData);//初始化在主函数内部wk
    InitStack(&stackMin);//
    //  while((newIn = getchar()) != -1)
    while((scanf("%d",&newIn)) != -1)//获取字母更改为数字wk
    {   
        push(newIn);
    }
    
    printf("pop is %d\n", pop());
    printf("min is %d\n", getmin());
    
    return 0;
}

备注

其实,有个大小写的问题找了好一会,因为没找到对应的函数,一个大小写不同,会导致函数的声明不对应的. 目前是指针对vc6.0的环境测试成功了,但是纯c的环境有些问题,后面继续更新.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏电光石火

ssm整合Redis

这次谈谈Redis,关于Redis应该很多朋友就算没有用过也听过,算是这几年最流行的NoSql之一了。  Redis的应用场景非常多这里就不一一列举了,这次...

3548
来自专栏向治洪

ReactNative调用Android原生模块

有时候App需要访问平台API,但React Native可能还没有相应的模块包装;或者你需要复用一些Java代码,而不是用Javascript重新实现一遍;又...

2157
来自专栏开发与安全

muduo网络库学习之muduo_inspect 库涉及到的类

muduo inspect 库通过HTTP方式为服务器提供监控接口, 现在只实现进程相关信息的监控,通过成员ProcessInspector 实现。 Pro...

2085
来自专栏IMWeb前端团队

使用joi来验证数据模型

我们用nodejs实现一些功能时,往往需要对用户输入的数据进行验证。然而,验证是一件麻烦的事情,很有可能你需要验证数据类型,长度,特定规则等等,在前端做表单验证...

4280
来自专栏强仔仔

SpringBoot中Redis的set、map、list、value、实体类等基本操作介绍

今天给大家介绍一下SpringBoot中Redis的set、map、list、value等基本操作的具体使用方法 上一节中给大家介绍了如何在SpringBoot...

7218
来自专栏扎心了老铁

commons-pool与commons-pool2连接池(Hadoop连接池)

commons-pool和commons-pool2是用来建立对象池的框架,提供了一些将对象池化必须要实现的接口和一些默认动作。对象池化之后可以通过pool的概...

1.1K6
来自专栏小樱的经验随笔

HUST 1583 长度单位

1583 - 长度单位 时间限制:1秒 内存限制:128兆 536 次提交 103 次通过 题目描述我们生活中常用的长度单位有英尺、英寸和厘米,众所周知它们...

35610
来自专栏大大的微笑

web项目定时执行任务

首先写了个servlet 例如 package com.uap.weixin.service; import java.text.DateFormat; im...

2286
来自专栏腾讯Bugly的专栏

深入源码探索 ReactNative 通信机制

本文从源码角度剖析 ReactNative 中 Java <> Js 的通信机制(基于最新的 ReactNative for Android Release 2...

3369
来自专栏飞扬的花生

在ASP.MVC中使用Ajax

      Asp.net MVC 抛弃了Asp.net WebForm那种高度封装的控件,让我们跟底层的HTML有了更多的亲近。可以更自由、更灵活的去控制HT...

2199

扫码关注云+社区

领取腾讯云代金券