資源簡介
長整數的代數計算
問題描述
應用線性數據結構解決長整數的計算問題。設計數據結構完成長整數的表示和存儲,并編寫算法來實現兩長整數的加、減、乘、除等基本代數運算。
基本要求
① 長整數長度在一百位以上。
② 實現兩長整數在取余操作下的加、減、乘、除操作,即實現算法來求解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\li
?????文件????????2654??2016-03-07?21:21??Calculator\Calculator\Debug\Calculator.tlog\li
?????文件?????????678??2016-03-07?21:21??Calculator\Calculator\Debug\Calculator.tlog\li
?????文件???????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個文件信息
評論
共有 條評論