长整数的代数计算(最好用C++版可以用的,一定追加50分)

长整数的代数计算(最好用C++版可以用的,一定追加50分)
(1)
设计数据结构完成长整数的表示和存储,并编写算法来实现两长整数的加、减、乘、除等基本代数运算.
(2) 课程设计目的
能够应用线性数据结构解决实际问题.
(3) 基本要求
① 长整数长度在一百位以上.
② 实现两长整数在同余代数下的加、减、乘、除操作.
即实现算法来求解a+b mod n,a-b mod n,a´b mod n,a¸b mod n.
③ 输入输出均在文件中.
④ 分析算法的时空复杂性.
(4) 实现提示
需将长整数的加法转化为多个一般整数加法的组合.

#define NULL 0
#include
#include
#include
#include
typedef struct Qnode{
int num; /*数字*/
struct Qnode *low1; /*指向低一位结点*/
struct Qnode *high1; /*指向高一位结点*/
}Qnode,* longnode;
typedef struct {
longnode High; /*指向最高节点*/
longnode Low; /*指向最低节点*/
int digit4; /*每个结点整数的总位数(不包括高位的0)/4 */
}xlong;
void init(xlong *a,int digit4){ /*初始化循环链表a*/
int i;
longnode j,k=0;
a=(xlong*)malloc(sizeof(xlong)); /* 为a的头结点申请空间,并赋初始值 */
a->High=NULL;
a->Low=NULL;
a->digit4=0;
for(i=0;inum=0;
j->high1=NULL;
j->low1=a->High;
if(a->High)
a->High->high1=j;
else
a->Low=j;
a->High=j;
a->digit4++;
}
}
int pass(xlong *a,xlong *b,xlong *c){ /* 两个数字的相加 */
int cf=0;
longnode a1=a->Low,b1=b->Low,c1=c->Low;
while(a1){
c1->num=a1->num+b1->num+cf;
if(c1->num>9999){ /* 如果产生进位(借位) */
cf=1;
c1->num-=10000;
}else{
cf=0;
}
a1=a1->high1;b1=b1->high1;c1=c1->high1;
}
return cf; /* 最高位的进位(借位) */
}
int passa(xlong *a,xlong *b,xlong *c){ /* 两个数字的相减 */
int cf=0;
longnode a1=a->Low,b1=b->Low,c1=c->Low;
while(a1){
c1->num=a1->num-b1->num-cf;
if(c1->num>9999){ /* 如果产生进位(借位) */
cf=1;
c1->num-=10000;
}else{
cf=0;
}
a1=a1->high1;b1=b1->high1;c1=c1->high1;
}
return cf; /* 最高位的进位(借位) */
}
void nep(xlong *a){ /* 求a的相反数 */
int cf=1; /* 因为求相反数是取反加一,所以这里cf=1; */
longnode a1=a->Low;
while(a1){
a1->num=9999-(a1->num)+cf;
if(a1->num>9999){
a1->num-=10000;
}else{
cf=0;
}
a1=a1->high1;
}
return;
}
void printlong(xlong *a){ /* 打印长整数a */
longnode i=a->High;
if(i->num>=5000){ /* 最高位(bit)=1表示负数,即用补码表示 */
printf("-");
nep(a); /* 求反打印其绝对值 */
}
while(i&&i->num==0) i=i->low1; /* 跳过最位的0 */
if(i){
printf("%d",i->num);
i=i->low1;
if(i) printf(",");
}else printf("0"); /* a=0 打0 */
while(i){
printf("%04d",i->num);
if(i->low1)
printf(",");
i=i->low1;
}
}
int ston(char in[],xlong *out)
{ /* 把字符串转化为数字赋给a */
int bit,i,jishu=1,num0=0;
longnode j=out->Low;
i=strlen(in)-1;
printf("strlen=%d\n",i);
while(i>=0 /*&& j*/)
{ /* 循环每一个字节 */
bit=in[i]-'0'; /* 把字符形式的值赋给整数形式的bit */
if(bit>=0 && bit =10000)
{ /* 数字以外的字符 */
j->num=num0;
j=j->high1; /* 存入一个节点 */
num0=0;
jishu=1;
}
} i--;
}
if(num0){j->num=num0;j=j->high1;} /* 把最后一个没存入节点的数存入节点 */
for(;j;j=j->high1) j->num=0; /* 最位不足补0 */
if(out->High->num>=5000) return 1; /* 如果最高位是1,返回1表示出错 */
if(in[0]=='-') nep(out); /* 如果最后一个字符是'－'则取反 */
return 0;
}
void add(){ /*加*/
char *a1,*b1;
int digit4,cf=0;
xlong a,b,c;
do{
printf("How much digits do you need(0