求助~~c语言做超大整数的加减,用栈实现
发布网友
发布时间：2022-10-02 11:09
共5个回答
热心网友
时间：2023-10-07 14:30
#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);
热心网友
时间：2023-10-07 14:30
#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;
}追问作业要求用链表或栈……谢谢你呀~
热心网友
时间：2023-10-07 14:31
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;
}
热心网友
时间：2023-10-07 14:31
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;
}
另外,虚机团上产品团购,超级便宜
热心网友
时间：2023-10-07 14:32
long int dstlen = 0; //目标数组分配的最大值
un_short mark = 0;//进位标志
unsigned int result;//数组对应元素相加结果
long sign = src1->sign;//整数的符号
int i = 0;
