论坛 › 数据结构与算法 › 任意长度的大数加法（栈的应用）

圣狄雅哥 发表于 2018-2-3 14:55:49

本帖最后由 圣狄雅哥 于 2018-2-3 14:59 编辑

//实现输入任意长度字符串的整数减法
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
typedef char ElemType;

typedef struct
{
    ElemType *base;
    ElemType *top;
    int stacksize;
}sqstack;

void Initstack(sqstack *s)
{
    s->base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
    if(!s->base)
    {
      exit(0);
    }
    s->top=s->base;
    s->stacksize=STACK_INIT_SIZE;
}

void push(sqstack*s,ElemType e)
{
    if(s->top-s->base>=s->stacksize)
    {
      s->base=(ElemType*)realloc(s->base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(ElemType));
      if(!s->base)
      {
            exit(0);
      }
      s->top=s->base+s->stacksize;
      s->stacksize+=STACKINCREMENT;
    }
    *(s->top++)=e;
}

void pop(sqstack*s,ElemType*e)
{
    if(s->top==s->base)
    {
      return;
    }
    *e=*(--s->top);
}

int stacklen(sqstack *s)
{
    return (s->top-s->base);
}

void SUBTRACTION(sqstack*s1,sqstack*s2,sqstack*s3)
{
    char a,b,c;
    char carry=0;
    while(stacklen(s1)!=0&&stacklen(s2)!=0)
    {
      pop(s1,&a);
      pop(s2,&b);
      c=(a-48)-(b-48)-carry+48;
      if(c<'0')
      {
            c=c+'9'-47;
            carry=1;
      }
      else
      {
            carry=0;
      }
      push(s3,c);
    }
    if(stacklen(s1)!=0)
    {
      while(stacklen(s1)!=0)
      {
            pop(s1,&a);
            c=a-carry;
            if(c<'0')
         {
            c=c+'9'-47;
            carry=1;
         }
         else
          {
             carry=0;
          }
      push(s3,c);
      }
    }
    else if(stacklen(s2)!=0)
    {
      while(stacklen(s2)!=0)
      {
            pop(s2,&b);
            c='0'-carry-b;
            carry=1;
            c=c+'9'-47;
      push(s3,c);
      }
    }
    if(carry==1)
    {
      while(stacklen(s3)!=0)
      {
            pop(s3,&b);
            push(s2,b);
      }
      carry=0;
      while(stacklen(s2)!=0)
      {
            pop(s2,&b);
            c='9'-b+49-carry;
            push(s3,c);
            carry=1;
      }
      push(s3,'-');
    }
}

int main()
{
    char e;
    sqstack s1, s2, s3;

    Initstack(&s1);
    Initstack(&s2);
    Initstack(&s3);

    printf("请输入第一串任意整数，输入＃表示结束：");
    scanf("%c", &e);
    while( e != '#' )
    {
      push(&s1, e);
      scanf("%c", &e);
    }
    getchar();      // 回收回车符

    printf("\n请输入第二串任意整数，输入＃表示结束：");
    scanf("%c", &e);
    while( e != '#' )
    {
      push(&s2, e);
      scanf("%c", &e);
    }
    getchar();      // 回收回车符

    SUBTRACTION(&s1, &s2, &s3);

    printf("\n两者的差是：");
    while(stacklen(&s3) != 0)
    {
      pop(&s3, &e);
      printf("%c", e);
    }

    return 0;
}

圣狄雅哥 发表于 2018-2-3 15:03:15

小甲鱼那个程序改写的减法就是这样了

ba21 发表于 2018-2-22 21:31:03

看

wunanpty 发表于 2018-3-2 02:40:04

ipangpang 发表于 2018-3-24 14:54:34

挺

纵横秦月 发表于 2018-3-27 01:07:03

哇

1093331524 发表于 2018-3-28 17:43:53

{:10_257:}棒棒的

Kitty喜欢小鱼干 发表于 2018-8-9 10:35:40

直接蒙了

Kitty喜欢小鱼干 发表于 2018-8-9 11:28:52

假如c的值是11，那么11-9=2，而栈操作是满10进1，将1放在carry中，0放在c中； '2'+48是将2变成ASCTT码中的2，若要使放入carry中的是1，放入c中的是0，则要加上47。

撒旦发射 发表于 2018-11-9 16:10:11

/

ShaoDaria 发表于 2019-3-17 17:36:41

我想看代码

凌桓丶 发表于 2019-10-7 22:31:49

66666666666666

大裤衩子 发表于 2020-10-9 16:53:19

{:10_277:}

Lappland 发表于 2020-11-13 19:35:26

测试

bwzxhjy 发表于 2022-11-9 23:00:12

学习学习

Suud 发表于 2023-3-24 18:14:12

学习

查看完整版本: 任意长度的大数加法（栈的应用）