设计题目

任务：设计一个实现任意长的整数进行加法、减法运算的演示程序。
要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(2^15 - 1)~ (2^15 - 1)。
输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。

加上前端后的效果

在这里插入图片描述

设计过程说明

  1. 数据结构是双向循环链表，其结构如图所示。链表中的结点ABC都是0~9999的int类型变量，从低位到高位。即万进制。另外表头结点L用来存储数的符号和结点个数。
    双向循环链表结构示意图

  2. 对双向循环链表的基本操作有 ①初始化 ②插入 ③删除，其中插入和删除操作都只对尾部结点操作，不对中间结点操作。

  3. 函数举例
    以Add()为例，将链表a+链表b的结果赋给链表c
    如果AB同号，把两个链表从头到尾两两相加，处理进位
    如果AB异号，先比较AB绝对值，结果符号由较大数决定，结果的绝对值为大数减小数，从低位开始减，不够就向上一位借

  4. 接口说明
    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");
}
# 链表 # 数据结构 # c语言
Logo
华为云开发者联盟

为开发者提供学习成长、分享交流、生态实践、资源工具等服务，帮助开发者快速成长。

更多推荐

cover

实践探讨Python如何进行异常处理与日志记录

avatar 华为云开发者联盟
cover

HCDG天津站精彩回顾 | AI高效开发， ModelArts技术动手工作坊

avatar 华为云开发者联盟
cover

一次故障演练，十分钟自动搞定?

avatar 华为云开发者联盟