2020数据结构课程设计 超长整数四则运算（C语言+双向循环链表）
设计题目任务：设计一个实现任意长的整数进行加法、减法运算的演示程序。要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(2^15 - 1)~ (2^15 - 1)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。加上前端后的效果设计过程说明数据结构是双向循环链表，其结构如图所示。链表中的结点ABC都是0~9999的int类型变量，从低位
·
设计题目
任务：设计一个实现任意长的整数进行加法、减法运算的演示程序。
要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(2^15 - 1)~ (2^15 - 1)。
输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。
加上前端后的效果
设计过程说明
-
数据结构是双向循环链表，其结构如图所示。链表中的结点ABC都是0~9999的int类型变量，从低位到高位。即万进制。另外表头结点L用来存储数的符号和结点个数。
-
对双向循环链表的基本操作有 ①初始化 ②插入 ③删除，其中插入和删除操作都只对尾部结点操作，不对中间结点操作。
-
函数举例
以Add()为例，将链表a+链表b的结果赋给链表c
如果AB同号，把两个链表从头到尾两两相加，处理进位
如果AB异号，先比较AB绝对值，结果符号由较大数决定，结果的绝对值为大数减小数，从低位开始减，不够就向上一位借 -
接口说明
int GetNum(LinkList &L);
void Output(LinkList &L);
测试主函数中使用了GetNum()来输入一个数，用Output()来打印结果。
源代码
如果想直接使用Windows可执行程序，见下方资源链接，顺便可以帮孩子看看有无bug😆
https://download.csdn.net/download/qq_45572675/72409866
下面的.cpp源码是我在Dev-C++中写的
#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<conio.h>
/**双向循环链表的结构体定义**/
typedef struct Node{
int data;
struct Node *pre,*next;
}Node,*LinkList;
/*****函数声明*****/
int GetNum(LinkList &L); //读取一个数
void Output(LinkList &L); //输出
//以上2个函数 根据输入要求修改即可
void InitList(LinkList &L); //初始化一个双向循环链表(存放一个大数)
void Add(LinkList a,LinkList b,LinkList &c);//a+b=c
void Sub(LinkList a,LinkList b,LinkList &c);//a-b=c
void Mul(LinkList a,LinkList b,LinkList &c);//a*b=c
void Div(LinkList a,LinkList b,LinkList &c);//a/b=c
//以上5个函数 供用户调用
void ListInsert(LinkList &L,int x); //在链表尾部插入一个值为x的结点
void ListDelete(LinkList &L); //删去链表尾节点即高位
void Adjust(LinkList &L); //对一个链表位调整
int Compare(LinkList a,LinkList b); //比较两个数的绝对值大小
//以上4个函数 是函数间调用不用管
int main()
{
LinkList a,b,c;
InitList(a);
InitList(b);
InitList(c);
printf("Input number_A, end with ENTER\n");
if(!GetNum(a)){printf("EORROR:wrong number\n");return 0;}
//debug(a);
//Output(a);
printf("Input number_B, end with ENTER\n");
if(!GetNum(b)){printf("EORROR:wrong number\n");return 0;}
printf("Select an operation\n");
printf("[1] +\n[2] -\n[3] *\n[4] /\n");
char op=getch();
switch(op)
{
case '1':
printf("A + B = ");
Add(a,b,c);
Output(c);
break;
case '2':
printf("A - B = ");
Sub(a,b,c);
Output(c);
break;
case '3':
printf("A * B = ");
Mul(a,b,c);
Output(c);
break;
case '4':
printf("A / B = ");
if(abs(b->data)==1&&b->next->data==0)//b为0
{printf("EORROR:denominator zero\n");return 0;}
Div(a,b,c);
Output(c);
break;
default:{printf("EORROR:wrong operation\n");return 0;}
}
printf("\n\n\nauthor:oyxy2019\n\n");
system("pause");
return 0;
}
void InitList(LinkList &L)//初始化一个双向循环链表
{
//表头结点数据域的符号代表长整数的符号
//其绝对值表示元素结点数目
L=(LinkList)malloc(sizeof(Node));
L->data=0;
L->next=L;
L->pre=L;
}
void ListInsert(LinkList &L,int x)//在链表尾部插入一个值为x的结点
{
LinkList p=(LinkList)malloc(sizeof(Node));
LinkList q=L->pre;
p->data=x;
p->next=L;
p->pre=q;
q->next=p;
L->pre=p;
if(L->data>=0)L->data++;
else L->data--;
}
void ListDelete(LinkList &L)//删去链表尾节点即高位
{
if(L->data==0)return;
LinkList p=L->pre;
LinkList q=p->pre;
q->next=L;
L->pre=q;
free(p);
if(L->data>=0)L->data--;
else L->data++;
}
void Adjust(LinkList &L)//对一个链表进行调整
{
LinkList p=L->next;
while(p!=L)
{
while(p->data>9999)//处理进位
{
if(p->next==L)ListInsert(L,0);
p->next->data+=p->data/10000;
p->data%=10000;
}
p=p->next;
}
while(L->pre->data==0&&abs(L->data)>1)ListDelete(L);//处理前导零
}
int Compare(LinkList a,LinkList b)//比较两个数的绝对值大小a>b返回1 a=b返回2 a<b返回0
{
if(abs(a->data)!=abs(b->data))
{
if(abs(a->data)>abs(b->data))return 1;
else return 0;
}
LinkList p=a->pre,q=b->pre;
while(p!=a&&q!=b)
{
if(p->data!=q->data)
{
if(p->data>q->data)return 1;
else return 0;
}
p=p->pre;
q=q->pre;
}
return 2;
}
void Add(LinkList a,LinkList b,LinkList &c)//a+b=c
{
if(a->data*b->data>0)//ab同号
{
LinkList p=a->next,q=b->next;
while(p!=a&&q!=b)
{
ListInsert(c,p->data+q->data);
p=p->next;
q=q->next;
}
while(p!=a)
{
ListInsert(c,p->data);
p=p->next;
}
while(q!=b)
{
ListInsert(c,q->data);
q=q->next;
}
if(a->data<0)c->data=-c->data;
}
else
{
switch(Compare(a,b))
{
case 2://a==b abs
ListInsert(c,0);
return;
case 1://a>b
{
LinkList p=a->next,q=b->next;
while(p!=a&&q!=b)
{
if(p->data<q->data)//不够减则向上借位
{
p->next->data--;
p->data+=10000;
}
ListInsert(c,p->data-q->data);
p=p->next;
q=q->next;
}
while(p!=a)
{
ListInsert(c,p->data);
p=p->next;
}
if(a->data<0)c->data=-c->data;//绝对值较大者确定符号
break;
}
case 0://a<b
{
LinkList p=a->next,q=b->next;
while(p!=a&&q!=b)
{
if(q->data<p->data)//不够减则向上借位
{
q->next->data--;
q->data+=10000;
}
ListInsert(c,q->data-p->data);
p=p->next;
q=q->next;
}
while(q!=b)
{
ListInsert(c,q->data);
q=q->next;
}
if(b->data<0)c->data=-c->data;
break;
}
}
}
Adjust(c);//处理进位
}
void Sub(LinkList a,LinkList b,LinkList &c)//a-b=a+(-b)=c
{
b->data=-b->data;
Add(a,b,c);
b->data=-b->data;
}
void Mul(LinkList a,LinkList b,LinkList &c)//a*b=c
{
if(abs(a->data)==1&&a->next->data==0||abs(b->data)==1&&b->next->data==0)
{
ListInsert(c,0);//AB中有一个数为0
return;
}
for(int i=1;i<=(abs(a->data)+abs(b->data));i++)ListInsert(c,0);
LinkList p=a->next;
for(int i=1;p!=a;p=p->next,i++)
{
LinkList q=b->next;
for(int j=1;q!=b;q=q->next,j++)
{
int k=i+j-1;
LinkList t=c;
while(k--)t=t->next;
t->data+=p->data*q->data;
}
}
if(a->data*b->data<0)c->data=-c->data;//ab异号
Adjust(c);
}
void Div(LinkList a,LinkList b,LinkList &c)//a/b=c
{
if(Compare(a,b)==0)//a<b,ans=0
{
ListInsert(c,0);
return;
}
for(int i=1;i<=abs(a->data);i++)ListInsert(c,0);//商的最大位数
int flag=0;//b为负数时转正
if(b->data<0)
{
b->data=-b->data;
flag=1;
}
LinkList tmp;
InitList(tmp);
for(LinkList t=c->pre,p=a->pre;t!=c;t=t->pre,p=p->pre)
{
LinkList q=(LinkList)malloc(sizeof(Node));//将a高位部分拷给tmp
q->data=p->data,q->next=tmp->next,q->pre=tmp;
tmp->next->pre=q,tmp->next=q;
tmp->data++;
while(Compare(tmp,b))//把除法转换为从高到低的减法
{
t->data++;
LinkList r;//余数
InitList(r);
Sub(tmp,b,r);
while(tmp->data!=0)ListDelete(tmp);
InitList(tmp);
for(LinkList p=r->next;p!=r;p=p->next)
ListInsert(tmp,p->data);//把r拷给tmp，相当于tmp-=b
}
}
if(flag)b->data=-b->data;
if(a->data*b->data<0)c->data=-c->data;//ab异号
Adjust(c);
}
int GetNum(LinkList &L)//读取一个数
{
char ss[100005];
int sum=0;
scanf("%[^\n]",ss);
getchar();
for(int i=0;i<strlen(ss);i++)//如果出现非数字且不是第一个正负号
if(!(i==0&&(ss[0]=='-'||ss[0]=='+'))&&(!(ss[i]>='0'&&ss[i]<='9')))
return 0;
int j=0;
for(int i=strlen(ss)-1;i>=0;i--)
{
if(ss[i]>='0'&&ss[i]<='9')
{
j++;
if(j==4||i==0||(i==1)&&ss[0]=='-')
{
int sum=0;
for(int k=i;k<i+j;k++)sum=10*sum+(ss[k]-'0');
ListInsert(L,sum);
j=0;
}
}
}
if(ss[0]=='-')L->data=-L->data;
if(L->data==0)return 0;
Adjust(L);
return 1;
}
void Output(LinkList &L)//输出
{
LinkList p=L->pre;
if(L->data<0)printf("-");
while(p!=L)
{
if(p->next!=L)printf("%04d",p->data);
else printf("%d",p->data);
if(p->pre!=L)printf(",");
p=p->pre;
}
printf("\n");
}
华为开发者空间，是为全球开发者打造的专属开发空间，汇聚了华为优质开发资源及工具，致力于让每一位开发者拥有一台云主机，基于华为根生态开发、创新。
更多推荐
39
0- 0
已为社区贡献1条内容
所有评论(0)