数据结构大数相乘.docx
- 文档编号:10899205
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:38
- 大小:95.34KB
数据结构大数相乘.docx
《数据结构大数相乘.docx》由会员分享,可在线阅读,更多相关《数据结构大数相乘.docx(38页珍藏版)》请在冰点文库上搜索。
数据结构大数相乘
课题名称:
大数相乘
1.问题描述
计算机的内存有限,而且各个函数类型的范围有限,如果要计算两个更大的乘数,就会超出范围,得到不精确的数,如何得到更精确的数,而又不受计算机内存空间的限制,本程序就可以解决大数相乘的问题。
2.设计思路
这个程序的关键是如何保存大数的各个数字,以及如何处理大数乘法的进位问题。
本人是运用栈的思想做的,先定义一个整型的栈,大数传入栈的整型数组中,在乘法运算函数中,先从一个栈中取出一个大数S1的个位上的数字a,再从另一个大数S2取出一个个位数字b,再将a*b+d(d为进位数)的个位数字压到栈S中,十位上进位的数字先保存到d中,再从S2中取出一个十位数,与a相乘,得到的个位数字再压到栈S中,再从S2中取出一个数字,以此类推,直到S2中的数字被a乘完,得到一个新的大数S,将该栈保存到A栈中,将S销毁,再从S1中取出大数的十位数字,与S2的各个数字相乘,得到一个新的大数压到S中,将S保存到B中,将B移位处理后,然后与A相加得到另一个大数,以此类推,最终可相加得到想要的结果。
这其中还用到了大数相加的原理。
3.数据结构设计
前面提到,要用到栈的操作,这里,由于一个大数的最大长度是一定的,且大数最多执行的操作是插入和删除操作,所以顺序存储结构可以带来更大益处。
为了便于大数相加,将大数的各个数字存入到整型数组中。
#defineMAXSIZE100
typedefstructnode
{
intdata[MAXSIZE];
inttop;
}SeqStack,*PSeqStack;
4.功能函数设计
(1)栈初始化函数Init_SeqStack(char*ch)
此函数是将传入的字符处理成0~9的整数存入整型数组中。
将*ch-’0’转化为整数存入S->data[i]中,结束标志是*ch不等于’\0’
(2)首尾倒置函数Convert_SeqStack(PSeqStackA)
此函数是将栈中的数值首尾颠倒,比如以前是1234,现在变成4321。
只要将传入的A的栈中的元素依次取出压到C中,再返回C栈即可
(3)大数相加函数Add(PSeqStackS1,PSeqStackS2)
此函数是处理两个大数相加的功能。
将传入的两个大数压到S1和S2中,当S1或S2不为空时,从S1中取出a,从S2中取出b,得到Result=(a+b)%10+d,其中初始时d=0,再判断Result是否大于10,如果小于10直接压到栈S中,如果大于10将Result%10压入栈中,令d=(a+b)/10+Result/10;如果运算后其中的一个栈空了,另一个不空的栈的数值加上进位数d再直接压到S中,这样可以得到一个大数。
(4)移位函数Crol(PSeqStackS,intn)
将其中一位大数取出一位数字与另一位大数相乘的结果移位,然后相加,从各位开始,每乘一个数,都要移位一个0
(5)复制函数Copy_SeqStack(PSeqStackA,PSeqStackB)
将一个A栈中的元素拷贝到B栈中,先将A中的元素压到C栈中,再将C栈中的元素压到B栈中,即可实现复制功能
(6)大数相乘函数Multiply(PSeqStackS1,PSeqStackS2)
此函数是实现大数相乘的核心算法。
主要思想就是将S1中取出个位数a,分别与S2中的各个数相乘得到新的大数,再取S1中的十位数,与S1大数相乘,以此类推,然后将各个大数进行移位处理再相加
5.编码实现
#include"stdafx.h"
#include"stdlib.h"
#include"stdio.h"
#include"string.h"
#defineMAXSIZE100
typedefstructnode
{
intdata[MAXSIZE];
inttop;
}SeqStack,*PSeqStack;
voidDestroy_SeqStack(PSeqStack*S)
{
if(*S)
free(*S);
*S=NULL;
return;
}
intPush_SeqStack(PSeqStackS,intx)
{
if(S->top==MAXSIZE-1)
return0;
else
{
S->top++;
S->data[S->top]=x;
return1;
}
}
PSeqStackInit_SeqStack(char*ch)
{
PSeqStackS;
inti=0;
char*head;
S=(PSeqStack)malloc(sizeof(SeqStack));
if(S)
S->top=-1;
head=ch;
while(*ch!
='\0')
{
if(*head=='-')
S->data[i]=(*(++ch)-'0')*(-1);
else
S->data[i]=*ch-'0';
ch++;
S->top++;
i++;
}
returnS;
}
intGetTop_SeqStack(PSeqStackS,int*x)
{
if(S->top==-1)
return0;
else
{
*x=S->data[S->top];
return1;
}
}
intEmpty_SeqStack(PSeqStackS)
{
if(S->top==-1)
return1;
else
return0;
}
intPop_SeqStack(PSeqStackS,int*x)
{
if(Empty_SeqStack(S))
return0;
else
{
*x=S->data[S->top];
S->top--;
return1;
}
}
voidprint(PSeqStackS)
{
inti;
for(i=0;i<=S->top;i++)
printf("%d",S->data[i]);
}
//将栈顶变成栈尾,栈尾变成栈顶
PSeqStackConvert_SeqStack(PSeqStackA)
{
intx;
PSeqStackC;
C=(PSeqStack)malloc(sizeof(SeqStack));
if(C)
C->top=-1;
while(!
Empty_SeqStack(A))
{
Pop_SeqStack(A,&x);
Push_SeqStack(C,x);
}
returnC;
}
PSeqStackAdd(PSeqStackS1,PSeqStackS2)
{
PSeqStackS;
intd=0,a,b,Result;
S=(PSeqStack)malloc(sizeof(SeqStack));
if(S)
S->top=-1;
while(!
Empty_SeqStack(S1)&&!
Empty_SeqStack(S2))
{
Pop_SeqStack(S1,&a);
Pop_SeqStack(S2,&b);
Result=(a+b)%10+d;
//判断Result是否大于等于10
if(Result/10==0)
{
Push_SeqStack(S,Result);
d=(a+b)/10;
}
elseif(Result/10>0)
{
Push_SeqStack(S,Result%10);
d=(a+b)/10+Result/10;
}
}
while(!
Empty_SeqStack(S1))
{
Pop_SeqStack(S1,&a);
Result=a%10+d;
if(Result/10==0)
{
Push_SeqStack(S,Result);
d=a/10;
}
else
{
Push_SeqStack(S,Result%10);
d=a/10+Result/10;
}
}
while(!
Empty_SeqStack(S2))
{
Pop_SeqStack(S2,&a);
Result=a%10+d;
if(Result/10==0)
{
Push_SeqStack(S,Result);
d=a/10;
}
else
{
Push_SeqStack(S,Result%10);
d=a/10+Result/10;
}
}
if(d!
=0)
Push_SeqStack(S,1);
S=Convert_SeqStack(S);
returnS;
}
PSeqStackCrol(PSeqStackS,intn)
{
inti;
for(i=0;i Push_SeqStack(S,0); returnS; } voidCopy_SeqStack(PSeqStackA,PSeqStackB) { PSeqStackC; intx; C=(PSeqStack)malloc(sizeof(SeqStack)); if(C) C->top=-1; while(! Empty_SeqStack(A)) { Pop_SeqStack(A,&x); Push_SeqStack(C,x); } while(! Empty_SeqStack(B)) { Pop_SeqStack(B,&x); } while(! Empty_SeqStack(C)) { Pop_SeqStack(C,&x); Push_SeqStack(A,x); Push_SeqStack(B,x); } } PSeqStackMultiply(PSeqStackS1,PSeqStackS2) { PSeqStackS,A,B; inta,b,c,d=0,Result,i,count=0; S=(PSeqStack)malloc(sizeof(SeqStack)); if(S) S->top=-1; A=(PSeqStack)malloc(sizeof(SeqStack)); if(A) A->top=-1; B=(PSeqStack)malloc(sizeof(SeqStack)); if(B) B->top=-1; while(! Empty_SeqStack(S1)) { Pop_SeqStack(S1,&a); d=0; for(i=S2->top;i>-1;i--) { b=S2->data[i]; //printf("%d,",b); Result=a*b%10+d; if(Result/10==0) { Push_SeqStack(S,Result); d=a*b/10; } elseif(Result/10>0) { Push_SeqStack(S,Result%10); d=a*b/10+Result/10; } } if(d! =0) Push_SeqStack(S,d); //printf("\nS为: "); //print(S); S=Convert_SeqStack(S); if(count==0) { Copy_SeqStack(S,A);//将S栈拷贝到A栈 //printf("\nA为: "); //print(A); } else { B=Crol(S,count);//将B左移count位 //printf("\nB为: "); //print(B); A=Add(A,B); //printf("\nA为: "); //print(A); } count++; Destroy_SeqStack(&S); S=(PSeqStack)malloc(sizeof(SeqStack)); if(S) S->top=-1; } A=Convert_SeqStack(A); while(GetTop_SeqStack(A,&c)&&c==0) Pop_SeqStack(A,&c); if(Empty_SeqStack(A)) Push_SeqStack(A,0); A=Convert_SeqStack(A); returnA; } voidmain() { PSeqStackA,B,C; inti; //char*ch1={"1234876543329"},*ch2={"78656453534223656896"}; //char*ch1={"99"},*ch2={"1"}; //char*ch1={"111111111111111111111"},*ch2={"111111111111111111111"}; //char*ch1={"11111111"},*ch2={"-11111111"}; //char*ch1={"99996757657464"},*ch2={"0"}; charch1[50],ch2[50]; system("color70"); printf("请输入第一个大数: "); gets(ch1); printf("\n请输入第二个大数: "); gets(ch2); printf("该乘式为: "); A=Init_SeqStack(ch1); print(A); printf("*"); B=Init_SeqStack(ch2); print(B); printf("\n"); //C=Add(A,B); C=Multiply(A,B); printf("\n计算结果为: "); for(i=0;i<=C->top;i++) { printf("%d",C->data[i]); } //print(C); printf("\n"); //printf("实际结果为: 78656454769100200225"); } 6.运行与测试 首先屏幕会提示你输入第一个大数,然后按回车键,屏幕会提示你输入第二个大数,再按回车键,即可得到计算结果 7.设计中存在的问题及感想 本程序的缺陷对负数以及小数相乘没有处理好,只能处理大的整数,这是一个遗憾。 其实这个大数相乘程序我是根据大数相加的思想来做的,大数相加的进位思想是加进位,而大数相乘是乘进位,我想这是一样的原理。 大数相加时,进位数不超过1,而两个一位数相乘得到的进位数不超过8所以进位数都控制在一位数以内,这就不太复杂了。 不过本程序还有一个问题,就是计算效率不高,虽然测试的时间不慢,但是我当测试100000个数时,其效率可见明显降低。 本来想用傅里叶算法的,可是傅里叶算法思想没看懂,所以用了自己的本方法。 课题名称: 模拟计算器 1.问题描述 如果让我们计算4+2*(8-5)-4/2=? 我们该怎么计算? 为了实现这个功能,特地做了这个计算器,可以对包含加、减、乘、除的运算符的任意整型式进行求解。 2.设计思路 这个程序的关键就是如何将输入的中缀表达式转化为后缀表达式,然后再对后缀表达式进行求值运算。 对于中缀表达式转为后缀表达式,在参数先定义两个指针型字符串infixexp和postfixexp,infixexp是传入的中缀表达式字符串,postfixexp是传出的后缀表达式字符串,再定义一个栈,当栈顶元素不等于’#’时,然后判断infixexp中的每一个字符是不是数,如果是数,传入postfiexp中,否则进一步判断w是不是’)’,若不是判断栈顶元素的优先级,将操作符压入栈中,以此类推,最终得到后缀表达式。 对于后缀表达式的运算,主要判断是不是数字还是操作符,如果是数字压到栈中,如果是操作符,从栈中取出两个数字运算。 本人对于本程序还设计了一个操作界面,用的是MFC语言设计的,操作界面主要有一个文本框和19个按钮组成,有清零按钮,删除按钮,加减乘除按钮,以及各个操作数按钮,’=’按钮,这些按钮大部分都是传入相应的字符串到文本框中,当按下’=’号按钮时,再从文本框中得到字符串,对字符串进行处理,然后运算出结果。 3.数据结构设计 主要建立了一个CCaculatordlg的类,该类继承MFC中CDialog的特征,这样可以在MFC中建立一个单文档对话框,这个对话框可以添加一些控件来做成一个计算器界面,如何对于该计算器操作,就要看控制各个控件函数怎么实现的。 这里的类如下: classCCaculatorDlg: publicCDialog { //Construction public: intpostfix_exp(char*A); intinfix_exp_value(char*infixexp,char*postfixexp); intpriority(charop); intIsNum(charc); //intinfix_exp_value(char*infix,char*postfixexp); doublenum; //charCalculateExpre; //doubleCalculateResult; //doubleCalculateNum; charch[50],ch1[10],ch2[10],op; chartext[50]; //stack CCaculatorDlg(CWnd*pParent=NULL);//standardconstructor //DialogData //{{AFX_DATA(CCaculatorDlg) enum{IDD=IDD_CACULATOR}; //NOTE: theClassWizardwilladddatamembershere //}}AFX_DATA //Overrides //ClassWizardgeneratedvirtualfunctionoverrides //{{AFX_VIRTUAL(CCaculatorDlg) protected: virtualvoidDoDataExchange(CDataExchange*pDX);//DDX/DDVsupport //}}AFX_VIRTUAL //Implementation protected: //Generatedmessagemapfunctions //{{AFX_MSG(CCaculatorDlg) afx_msgvoidOnAdd(); afx_msgvoidOnBtn1(); afx_msgvoidOnBtn0(); afx_msgvoidOnBtn2(); afx_msgvoidOnBtn3(); afx_msgvoidOnBtn4(); afx_msgvoidOnBtn5(); afx_msgvoidOnBtn6(); afx_msgvoidOnBtn7(); afx_msgvoidOnBtn8(); afx_msgvoidOnBtn9(); afx_msgvoidOnClear(); afx_msgvoidOnDivide(); afx_msgvoidOnEquals(); afx_msgvoidOnMinus(); afx_msgvoidOnMultiply(); afx_msgvoidOnReset(); virtualBOOLOnInitDialog(); afx_msgvoidOnRbrackets(); afx_msgvoidOnLbrackets(); //}}AFX_MSG DECLARE_MESSAGE_MAP() }; 4.功能函数设计 (1)按键0函数CCaculatorDlg: : OnBtn0() 先得到文本框字符串,然后将该字符串末尾处加0,再将所有的字符串显示到文本框中 (2)按键1函数CCaculatorDlg: : OnBtn1() 先得到文本框字符串,然后将该字符串末尾处加1,再将所有的字符串显示到文本框中 (3)按键2函数CCaculatorDlg: : OnBtn2() 先得到文本框字符串,然后将该字符串末尾处加2,再将所有的字符串显示到文本框中 (4)按键3函数CCaculatorDlg: : OnBtn3() 先得到文本框字符串,然后将该字符串末尾处加3,再将所有的字符串显示到文本框中 (5)按键4函数CCaculatorDlg: : OnBtn4() 先得到文本框字符串,然后将该字符串末尾处加4,再将所有的字符串显示到文本框中 (6)按键5函数CCaculatorDlg: : OnBtn5() 先得到文本框字符串,然后将该字符串末尾处加5,再将所有的字符串显示到文本框中 (7)按键6函数CCaculatorDlg: : OnBtn6() 先得到文本框字符串,然后将该字符串末尾处加6,再将所有的字符串显示到文本框中 (8)按键7函数CCaculatorDlg: : OnBtn7() 先得到文本框字符串,然后将该字符串末尾处加7,再将所有的字符串显示到文本框中 (9)按键8函数CCaculatorDlg: : OnBtn8() 先得到文本框字符串,然后将该字符串末尾处加8,再将所有的字符串显示到文本框中 (10)按键9函数CCaculatorDlg: : OnBtn9() 先得到文本框字符串,然后将该字符串末尾处加9,再将所有的字符串显示到文本框中 (11)按键加函数CCaculatorDlg: : OnAdd() 先得到文本框字符串,然后将该字符串末尾处加’+’字符,再将所有的字符串显示到文本框中 (12)按键减函数CCaculatorDlg: : OnMinus() 先得到文本框字符串,然后将该字符串末尾处加’-’字符,再将所有的字符串显示到文本框中 (13)按键乘函数CCaculatorDlg: : OnMultiply() 先得到文本框字符串,然后将该字符串末尾处加’*’,再将所有的字符串显示到文本框中 (14)按键除函数CCaculatorDlg: : OnDivide() 先得到文本框字符串,然后将该字符串末尾处加’\’,再将所有的字符串显示到文本框中 (15)按键清除函数CCaculatorDlg: : OnClear(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 大数 相乘
![提示](https://static.bingdoc.com/images/bang_tan.gif)