• 首页

    • 求助~~c语言做超大整数的加减，用栈实现

    要求：
    能够表示超大整数（可能长达100位）,包括输入,输出, 正负等
    能够提供一些简单的辅助理解函数,如求整数的位数,求整数的某一位上的数字， 等
    完成超大整数的加法、减法运算（用链栈实现）
    非常非常感谢~~最好有注释~~有加分~~
    太长的话可以发邮箱death_pomelo@126.com

    推荐答案   2011-04-28
    #include <stdio.h>
    #include <malloc.h>
    #include <math.h>
    #include <string.h>
    #include <ctype.h>
    #define M 40
    /*定义堆栈*/
    typedef struct{
    double data[M];
    int top;
    }Stack;
    /*初始化堆栈*/
    InitStack(Stack *s)
    {
    s->top=0;
    }
    /*判断栈是否为空*/
    int StEmpty(Stack *s)
    {
    if(s->top==0)
    {
    return 1;
    }
    else
    {
    return 0;
    }
    }
    /*入栈操作*/
    StPush(Stack *s,double x)
    {
    if(s->top==M)
    {
    printf("The stack is overflow!");
    }
    else
    {
    s->top=s->top+1;
    s->data[s->top]=x;
    }
    }
    /*出栈操作*/
    double StPop(Stack *s)
    {
    double t;
    if(!StEmpty(s))
    {
    t=s->data[s->top];
    s->top=s->top-1;
    }
    else
    {
    printf("StPop:The stack is empty!");
    t=NULL;
    }
    return t;
    }
    /*获取栈顶元素*/
    double StGetTop(Stack *s)
    {
    double t;
    if(!StEmpty(s))
    {
    t=s->data[s->top];
    }
    else
    {
    printf("StGeTop:The stack is empty!");
    t=NULL;
    }
    return t;
    }
    /*将数字字符转换成整形*/
    int ChrTransferint(char c)
    {
    int n;
    switch(c)
    {
    case '0': n=0;break;
    case '1': n=1;break;
    case '2': n=2;break;
    case '3': n=3;break;
    case '4': n=4;break;
    case '5': n=5;break;
    case '6': n=6;break;
    case '7': n=7;break;
    case '8': n=8;break;
    case '9': n=9;break;
    }
    return n;
    }
    /*获取两个操作符之间数字字符的个数,返回的是最后一个数字字符的位置*/
    int GetNumsize(char str[],int n1)
    {
    int n2=n1;
    while(isdigit(str[n2])||(str[n2])==46)/*isdigit()判断是否数字字符*/
    {
    n2=n2+1;
    }
    return n2;
    }
    /*判断上个函数中获得的数字字符串中是否包含小数点，并返回它的位置，不包含，返回-1*/
    int IsIncludepoint(char str[],int n1,int n2)
    {
    int n3=-1;
    int i;
    for(i=n1;i<=n2;i++)
    {
    if(str[i]=='.')
    {
    n3=i;
    break;
    }
    }
    return n3;
    }
    /*将数字字符转换成数值*/
    double Transfer(char str[],int n1,int n2,int n3)
    {
    double data=0;
    int i,ct;
    if(n3<0)
    {
    for(i=n2;i>=n1;i--)
    {
    ct=ChrTransferint(str[i]);
    data=data+ct*pow(10,n2-i);/*pow(x,y)计算x的y次方的值*/
    }
    }
    else
    {
    for(i=n3-1;i>=n1;i--)
    {
    ct=ChrTransferint(str[i]);
    data=data+ct*pow(10,n3-1-i);/*pow(x,y)计算x的y次方的值*/
    }
    for(i=n3+1;i<=n2;i++)
    {
    ct=ChrTransferint(str[i]);
    data=data+ct*pow(0.1,i-n3);/*pow(x,y)计算x的y次方的值*/
    }
    }
    return data;
    }
    /*主程序*/
    main()
    {
    char str[M],c;
    char a;
    int n,p1,p2,p3; /*n为字符串长度，p1,p2,p3分别为数字字符起始位置，结束位置，和小数点位置*/
    double data; /*存放转换后的数值*/
    int i=0;
    Stack *so=(Stack *)malloc(sizeof(Stack)); /*存储操作符 '(':1,'+':2,'-':3, '*':4,'/':5 字符'),＝'不压栈*/
    Stack *sd=(Stack *)malloc(sizeof(Stack)); /*存储操作数*/
    InitStack(so);
    InitStack(sd);
    printf("Please input formula(format:(1+2)*1.2/4=):\n");
    n=0;
    while((a=getchar())!='\n')
    {
    str[n]=a;
    n++;
    }
    while(i<n)
    {
    char c;
    c=str[i];
    if(c=='(')
    { /*c若是'('直接入栈so，i++*/
    StPush(so,1);
    i++;
    }
    else if(isdigit(c))
    {
    p1=i; /*c若是数字字符，一并将后面的连续数字字符转换为数值并压栈到sd,并把i设为后面的*/
    p2=GetNumsize(str,p1);
    p3=IsIncludepoint(str,p1,p2-1); /*第一个非数字字符的位置*/
    data=Transfer(str,p1,p2-1,p3);
    StPush(sd,data);
    i=p2;
    }
    else if(c=='+')
    {
    StPush(so,2); /*c若是'+'直接入栈so,i++*/
    i++;
    }
    else if(c=='-')
    {
    StPush(so,3); /*c若是'-'直接入栈so,i++*/
    i++;
    }
    else if(c=='*')
    {
    if(str[i+1]=='(') /*c若是‘*’它后面的字符是否为'('，若是直接将'*'压栈so，*/
    {
    StPush(so,4);
    i++;
    }
    else
    {
    double t1,t2,t3; /*若不是，为数字字符,将后面的连续数字字符一并转换成数值t2,sd出栈给t1,将t3=t2*t1压栈到sd*/
    t1=StPop(sd); /*操作符'*'不压栈so*/
    p1=i+1;
    p2=GetNumsize(str,p1);
    p3=IsIncludepoint(str,p1,p2-1);
    t2=Transfer(str,p1,p2-1,p3);
    t3=t1*t2;
    StPush(sd,t3);
    i=p2;
    }
    }
    else if(c=='/')
    {
    if(str[i+1]=='(')
    {
    StPush(so,5);
    i++;
    }
    else
    {
    double t1,t2,t3;
    t1=StPop(sd); /*c是'/'同'*'*/
    p1=i+1;
    p2=GetNumsize(str,p1);
    p3=IsIncludepoint(str,p1,p2-1);
    t2=Transfer(str,p1,p2-1,p3);
    t3=t1/t2;
    StPush(sd,t3);
    i=p2;
    }
    }
    else if(c==')')
    {
    double t1,t2,t3;
    int p;
    while((p=StPop(so))!=1&&!StEmpty(so)) /*c若是')',出栈so,判断是'+'或'-',出栈sd两个操作数，进行加减运算*/
    { /*直到StPop=='('*/
    t1=StPop(sd);
    t2=StPop(sd);
    if(p==2)
    {
    t3=t2+t1;
    StPush(sd,t3);
    }
    else if(p==3)
    {
    t3=t2-t1;
    StPush(sd,t3);
    }
    }
    if(StGetTop(so)==4) /*然后判断so栈顶是否为'*'或者'/'*/
    {
    StPop(so);
    t1=StPop(sd); /*为'*'出栈so,出栈 sd 获得2个操作数，进行乘法操作*/
    t2=StPop(sd);
    t3=t2*t1;
    StPush(sd,t3);
    }
    else if(StGetTop(so)==5)
    {
    StPop(so);
    t1=StPop(sd); /*为'/'出栈so,出栈 sd 获得2个操作数，进行除法操作*/
    t2=StPop(sd);
    t3=t2/t1;
    StPush(sd,t3);
    }
    i++;
    }
    else if(c=='=')
    {
    double t1,t2,t3; /*c若是'='，这是so内只有加减号，出栈so到p ，sd到t1,t2*/
    int p;
    while(!StEmpty(so))
    {
    t1=StPop(sd);
    t2=StPop(sd);
    p=StPop(so);
    if(p==2)
    {
    t3=t2+t1; /*p=='+',加法运算，并将结果t3压栈sd*/
    StPush(sd,t3);
    }
    else if(p==3)
    {
    t3=t2-t1;
    StPush(sd,t3); /*p=='-',减法运算，并将结果t3压栈sd*/
    }
    }
    i++;
    }
    }
    if(!StEmpty(so)||StEmpty(sd))
    {
    printf("Input error,Back!\n"); /*若so不为空，或者sd为空，且sd中只有一个元素,则输入的式子不对*/
    }
    else
    {
    double end;
    int i; /*否则，sd中的那个数据就是最后计算结果，打印输出*/
    end=StGetTop(sd);
    printf("The value of this formula:\n");
    for(i=0;i<n;i++)
    {
    printf("%c",str[i]);
    }
    printf("%f\n",end);
    温馨提示：答案为网友推荐，仅供参考
    其他回答
    第1个回答  2011-04-07
    这个代码没有用链表操作，直接用数组和字符串来代替了，因为这样操作更简单易行，如果需要或其他要求在回复我吧，而且主要代码加了注释

    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<cstring>
    using namespace std;

    int a[110],b[110],c[110];
    int lena,lenb,len,i;
    string sa,sb;

    int maxx(int x,int y) {
    return x>y?x:y;
    }

    void init() // 将读入的字符串转化成整型数组
    {
    lena=sa.length();
    lenb=sb.length();
    for (i=0;i<lena;i++) a[lena-i-1]= sa[i] - '0';
    for (i=0;i<lenb;i++) b[lenb-i-1]= sb[i] - '0';
    len=maxx(lena,lenb);
    }

    void jiafa() //大数加法，注意进位
    {
    for (i=0;i<len;i++)
    {
    c[i]+=a[i] + b[i];
    c[i+1]+=c[i]/10;
    c[i]%=10;
    }
    if ( c[len]==0 ) len--;

    for (i=len;i>=0;i--) printf("%d",c[i]);
    printf("\n");
    }

    void jianfa() //大数减法 ，注意符号，注意被减数小于减数的情况
    {
    int need=0;
    if ( lena<lenb || lena==lenb && sa<sb ) need=1;
    if ( need )
    {
    printf("-");
    memcpy(c,a,sizeof(a)); memcpy(a,b,sizeof(b)); memcpy(b,c,sizeof(c));
    }
    for (i=0;i<len;i++)
    {
    c[i]=a[i] - b[i];
    if ( c[i] < 0 )
    {
    c[i] +=10;
    a[i+1]--;
    }
    }
    while (len>=0 && c[len]==0)
    len--;

    if (len<0) printf("0");
    else for (i=len;i>=0;i--) printf("%d",c[i]);
    printf("\n");

    if ( need )
    {
    memcpy(c,a,sizeof(a)); memcpy(a,b,sizeof(b)); memcpy(b,c,sizeof(c));
    }
    }

    void weishu() //求数组长度
    {
    printf("第一个数的长度为 :%d\n",sa.length());
    }

    void N_number(int x) //求第一个数的第N位数字
    {
    printf("第一个数的第%d位是数字%d\n",x,a[lena-x]);
    }

    int main()
    {
    int k,x;

    memset(a,0,sizeof(a)); //数组清零
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));

    printf("Please input the fisrt number:"); // 读入两个很大很大的数
    cin>>sa;
    printf("Please input the second number:");
    cin>>sb;

    init(); //初始化，即将字符串转化成整型数组

    printf("-----------Please choose-----------\n"); //选择操作类型
    do
    {
    printf("-----------1加法-------------------\n");
    printf("-----------2减法-------------------\n");
    printf("-----------3求第一个数的位数-------\n");
    printf("-----------4求第一个数的第n位数----\n");
    scanf("%d",&k);
    }while (k<0 || k>4 );

    switch (k) //分别处理
    {
    case 1:jiafa(); break;
    case 2:jianfa(); break;
    case 3:weishu(); break;
    case 4:
    printf("--please input n:");
    scanf("%d",&x);
    if (x>sa.length()) printf("n is too big!\n");
    else N_number(x);
    break;
    }

    return 0;
    }追问

    作业要求用链表或栈……谢谢你呀~

    第2个回答  2011-04-07
    /*加法*/
    int addMBInt1(MBigInt* dst, MBigInt* src1, MBigInt* src2)
    {
    long int len = 0; //两个大整数的长度最大值
    long int dstlen = 0; //目标数组分配的最大值
    un_short mark = 0;//进位标志
    unsigned int result;//数组对应元素相加结果
    long sign = src1->sign;//整数的符号
    int i = 0;
    len = (src1->length >= src2->length)?src1->length:src2->length;
    dstlen = len;
    if(-1 == extendMBInt(dst,len))//扩展足够内存
    {
    return 0;
    }
    //较小数位的整数的长度
    len = (src1->length>src2->length)? src2->length: src1->length;
    for(i = 0; i < len; i++) //对两个大整数的数位相同部分进行计算
    {
    result = src1->pBigInt[i] + src2->pBigInt[i] + mark;
    dst->pBigInt[i] = (result&0xffff);
    mark = result >> 16;
    }
    //对第一个大整数数位多出部分进行计算
    if(src1->length > src2->length)
    {
    while(i < src1->length)
    {
    result = src1->pBigInt[i] + mark;
    dst->pBigInt[i] = result & 0xffff;
    mark = result >> 16;
    i++;
    }
    if(mark != 0)
    {
    dst->pBigInt[i] = mark;
    }
    dstlen = src1->length + 1;
    }
    //对第二个大整数数位多出部分进行计算
    else if(src1->length < src2->length)
    {
    while(i < src2->length)
    {
    result = src2->pBigInt[i] + mark;
    dst->pBigInt[i] = result & 0xffff;
    mark = result >> 16;
    i++;
    }
    if(mark != 0)
    {
    dst->pBigInt[i] = mark;
    }
    dstlen = src2->length + 1;
    }
    dst->sign = sign; //符号的更改
    dst->length = dstlen; // 长度设置
    return 1;
    }

    int extendMBInt(MBigInt *mbi,long int size)
    {
    if(mbi->alloclen < size)
    {
    long int i = 0;
    un_short *pt = NULL;
    long int newAlloc = mbi->alloclen;
    while(newAlloc< size)
    { /* 分配至少能容纳size个元素的长度，步进为STEP_BINT */
    newAlloc += STEP_BINT;
    }
    if((pt = (un_short *)realloc(mbi->pBigInt,sizeof(un_short)*newAlloc)) == NULL)
    return FAILE_MEMORY_BINT;
    mbi->pBigInt = pt;
    for(i = mbi->alloclen; i < newAlloc; ++i) /* 对新的元素置0*/
    {
    mbi->pBigInt[i] = 0;
    }
    mbi->alloclen= newAlloc;
    }
    return RETURN_OK_BINT;
    }

    /*符号相反的加法--减法*/
    int addMBInt2(MBigInt* dst, MBigInt* src1, MBigInt* src2)
    {
    long int len = 0; //两个大整数的长度最大值
    un_short len1 = 0;
    long int dstlen = dst->alloclen; //目标数组分配的最大值
    un_short mark = 0;//进位标志
    int result = 0;//数组对应元素相加结果
    int sign = src1->sign;//整数的符号
    int I = 0;
    len = (src1->length > src2->length)? src1->length: src2->length;
    len1 = (src1->length > src2->length)? src2->length: src1->length;
    un_short *psrc1=src1 -> pBigInt,*psrc2 = src2->pBigInt,*pdst = NULL;
    if(-1 == extendMBInt(dst,len))
    {
    return 0;//扩展足够内存
    }
    int re = compareMBInt(src1,src2); //对两个大整数进行无符号比较
    if(re == 0) //两个大整数大小相等，进行加法运算后位0
    {
    dst -> length = 0;
    dst -> sign = 0;
    return 1;
    }
    if(re == -1)//无符号比较，大整数src2比大整数src1大
    {
    sign = src2->sign;
    psrc1 = src2->pBigInt;
    psrc2 = src1->pBigInt;
    len1 = src1->length;
    }
    for(i = 0;i< len1; i++)//对两整数相同长度部分进行计算
    {
    if((result = (psrc1[i] - psrc2[i] - mark))<0) mark = 1;
    else mark = 0;
    if(mark == 1)result += 65536;//表示向高一位借了1
    dst->pBigInt[i] = result;
    }
    while(i < len)//对数位较大部分的计算
    {
    result = psrc1[i] - mark;//表示给低位借走了1
    if(result >= 0)
    {
    dst->pBigInt[i ++ ] = result;
    mark = 0;
    }
    else
    { //表示向高一位借了1
    dst->pBigInt[ i ++ ] = result + 65536;
    }
    }
    dst->length = len; //长度设置
    dst->sign = sign; //符号位设置
    trimMBInt(dst); //对结果去掉前面的0
    return 1;
    }
    第3个回答  2011-04-20
    main()
    void chang(int X,int p);
    {
    int s[1000],top;
    top=0;
    while(x)
    s[++top]=x%p;
    x=x/p;
    }
    while(top)
    {
    if(s[top]<10)
    printf("%d",48+s[top--]);
    else printf("%d",55+s[top--]);
    }

    选择排序
    #include"stdio.h"
    void SelectSort(int s[],int n)
    {int i,j,k,t;
    for(i=0;i<n:i++)
    {k=i:
    for(j=i+1;j<=n;j++)
    if(s[k]>s[j])k=j;
    t=s[i];s[i]=s[k];s[k]=t;
    }
    另外,虚机团上产品团购,超级便宜
    第4个回答  2011-04-28
    long int len = 0; //两个大整数的长度最大值
    long int dstlen = 0; //目标数组分配的最大值
    un_short mark = 0;//进位标志
    unsigned int result;//数组对应元素相加结果
    long sign = src1->sign;//整数的符号
    int i = 0;
    12

    相关了解……

    你可能感兴趣的内容

    大家正在搜
    c语言栈的使用c语言如何用栈c语言入栈和出栈c语言中什么是栈c语言栈到底是什么c语言栈和堆c语言栈是什么意思若栈s1中保存整数若将整数1234依次进栈
    相关问题
    怎样用C语言做超大整数的加减运算?
    C语言中怎么实现两个超大整数的相加减乘除
    怎样用C语言做超大整数的减法运算？
    超级大的整数的加减用c语言怎么写？
    要求用C语言编写程序实现大整数的四则运算（加、减、乘、除）
    跪求：一个简单的基于C语言切用栈做的大整数的四则运算计算器。...
    用c语言实现大整形运算，64位长整型的加减法，输入限制为64...
    C语言 大整数加减法

    本站内容来自于网友发表，不代表本站立场，仅表示其个人看法，不对其真实性、正确性、有效性作任何的担保
    相关事宜请发邮件给我们
    © 非常风气网