长整数的代数计算 算法

长整数的代数计算 问题描述 应用线性数据结构解决长整数的计算问题。设计数据结构完成长整数的表示和存储，并编写算法来实现两长整数的加、减、乘、除等基本代数运算。 基本要求 ① 长整数长度在一百位以上。 ② 实现两长整数在取余操作下的加、减、乘、除操作，即实现算法来求解a+b mod n, a-b mod n, ab mod n, ab mod n。 ③ 输入输出均在文件中。 ④ 分析算法的时空复杂性。

// Calculator.cpp : Defines the entry point for the console application.
//
#include “stdafx.h“ 
#include 
#include 
#include 
#include 
#include
using namespace std;

#define LEN sizeof（struct Node） 
#define MAX 1000
#define OK        1
#define ERROR     0
#define OVERFLOW -1 
#define TRUE  1 
#define FALSE 0 
typedef int Status;
typedef struct Node
{
	int data;
	struct Node *prior *next;
}Node *NodeList;
int axp（int a int k） //求指数函数值 
{
	int r = 1;
	if （k == 0）
		return 1;
	for （; k > 0; k--）
		r = r*a;  return r;
}
Status zhuanhuan（char str[] NodeList &oprh） //输入转换函数
{//将字符串形式的操作数转换成所需的类型 
	NodeList p;
	int i k buffer;
	k = buffer = 0;
	oprh = （NodeList）malloc（LEN）;
	oprh->next = oprh;
	oprh->prior = oprh;
	for （i = strlen（str） - 1; i >= 0; i--）
	{
		if （（i != 0 || （str[0] != ‘-‘ && str[0] != ‘+‘）） && （str[i] > ‘9‘ || str[i] < ‘0‘）） //判断输入是否合法    return ERROR; 
			if （str[0] == ‘0‘ && str[1] != ‘\0‘）
				return ERROR;
		if （（str[0] == ‘-‘ || str[0] == ‘+‘） && str[1] == ‘0‘）
			return ERROR;
		if （str[i] != ‘-‘ && str[i] != ‘+‘）
		{
			buffer = buffer + （str[i] - ‘0‘）*axp（10 k）;
			k++;
			if （k == 4 || str[i - 1] == ‘-‘ || str[i - 1] == ‘+‘ || i == 0）
			{
				p = （NodeList）malloc（LEN）;//将新建结点插入到头结点之后 
				oprh->next->prior = p;
				p->prior = oprh;
				p->next = oprh->next;
				oprh->next = p;
				p->data = buffer;
				buffer = k = 0;
			}
		}
	}
	return OK;
}
Status shuru（NodeList &opr1 NodeList &opr2 char str[]）//输入函数
{
	int flag = OK;
	printf（“\n\n请输入第一个操作数:\n“）;
	//scanf（“%s“ str）;
	cin >> str;
	getchar（）;
	flag = zhuanhuan（str opr1）;
	while （!flag）
	{
		printf（“整数输入有误，请重新输入:\n“）;
		//scanf（“%s“ str）;
		cin >> str;
		getchar（）;
		flag = zhuanhuan（str opr1）;
	}
	printf（“\n\n请输入第二个操作数:\n“）;
	//scanf（“%s“ str）;
	cin >> str;
	getchar（）;
	flag = zhuanhuan（str opr2）;
	while （!flag）
	{
		printf（“整数输入有误，请重新输入：\n“）;
//		scanf（“%s“ str）;
		cin >> str;
		getchar（）;
		flag = zhuanhuan（str opr2）;
	}
	return OK;
}
//输出函数
Status shuchu（NodeList oprr char str[]）
{
	Status initbuf（char str[]）;
	NodeList p;
	int i j num[4];
	if （!oprr）
		return ERROR;
	p = oprr;
	i = j = 0;
	initbuf（str）;
	p = p->next;
	if （p->next == oprr && p->data == 0）//若要输出的数为0则执行 
		str[i++] = ‘0‘;
	else
		while （p != oprr）
		{
			num[0] = p->data / 1000;
			num[1] = （p->data - num[0] * 1000） / 100;
			num[2] = （p->data - num[0] * 1000 - num[1] * 100） / 10;
			num[3] = p->data - num[0] * 1000 - num[1] * 100 - num[2] * 10;
			while （j < 4）
			{
				if （num[j] != 0 || （str[0] == ‘-‘ && str[1] != ‘\0‘） || （str[0] != ‘-‘ && str[0] != ‘\0‘））//此判断语句是为了避免输出诸如：00123…的情况
					str[i++] = num[j] + ‘0‘;//?????
				j++;
			}
			p = p->next;
			j = 0;
		}
	str[i] = ‘\0‘;
	printf（“%s“ str）;
	printf（“\n“）;
	return OK;
}
Status initbuf（char str[]）//缓冲区部分初始化函数
{
	int i;
	for （i = 0; i <= 10; i++）
		st

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2016-03-07 21:22  Calculator\
     目录           0  2016-03-07 21:21  Calculator\Calculator\
     文件       13278  2016-03-07 21:21  Calculator\Calculator\Calculator.cpp
     文件        4539  2016-03-07 18:54  Calculator\Calculator\Calculator.vcxproj
     文件        1337  2016-03-07 18:54  Calculator\Calculator\Calculator.vcxproj.filters
     目录           0  2016-03-07 21:21  Calculator\Calculator\Debug\
     文件        1113  2016-03-07 21:18  Calculator\Calculator\Debug\Calculator.Build.CppClean.log
     文件          91  2016-03-07 21:21  Calculator\Calculator\Debug\Calculator.log
     文件      161974  2016-03-07 21:21  Calculator\Calculator\Debug\Calculator.obj
     文件     1638400  2016-03-07 21:18  Calculator\Calculator\Debug\Calculator.pch
     目录           0  2016-03-07 21:21  Calculator\Calculator\Debug\Calculator.tlog\
     文件        6384  2016-03-07 21:21  Calculator\Calculator\Debug\Calculator.tlog\CL.read.1.tlog
     文件        1276  2016-03-07 21:21  Calculator\Calculator\Debug\Calculator.tlog\CL.write.1.tlog
     文件         175  2016-03-07 21:21  Calculator\Calculator\Debug\Calculator.tlog\Calculator.lastbuildstate
     文件        1558  2016-03-07 21:21  Calculator\Calculator\Debug\Calculator.tlog\cl.command.1.tlog
     文件        1414  2016-03-07 21:21  Calculator\Calculator\Debug\Calculator.tlog\link.command.1.tlog
     文件        2654  2016-03-07 21:21  Calculator\Calculator\Debug\Calculator.tlog\link.read.1.tlog
     文件         678  2016-03-07 21:21  Calculator\Calculator\Debug\Calculator.tlog\link.write.1.tlog
     文件       11143  2016-03-07 21:18  Calculator\Calculator\Debug\stdafx.obj
     文件      257024  2016-03-07 21:21  Calculator\Calculator\Debug\vc120.idb
     文件      397312  2016-03-07 21:21  Calculator\Calculator\Debug\vc120.pdb
     文件        1736  2016-03-07 18:54  Calculator\Calculator\ReadMe.txt
     文件         297  2016-03-07 18:54  Calculator\Calculator\stdafx.cpp
     文件         320  2016-03-07 18:54  Calculator\Calculator\stdafx.h
     文件         314  2016-03-07 18:54  Calculator\Calculator\targetver.h
     文件     8388608  2016-03-07 21:22  Calculator\Calculator.sdf
     文件         976  2016-03-07 18:54  Calculator\Calculator.sln
     文件       19968  2016-03-07 21:22  Calculator\Calculator.v12.suo
     目录           0  2016-03-07 21:18  Calculator\Debug\
     文件       82432  2016-03-07 21:21  Calculator\Debug\Calculator.exe
     文件      472432  2016-03-07 21:21  Calculator\Debug\Calculator.ilk
............此处省略4个文件信息