数据结构课程设计实验报告

学号：姓名：

班级：教师：

内容：大数相乘。

模拟计算器。

马的遍历。日期：2023年7月1日。

课题名称：大数相乘。

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.数据结构设计。

前面提到，要用到栈的操作，这里，由于一个大数的最大长度是一定的，且大数最多执行的操作是插入和删除操作，所以顺序存储结构可以带来更大益处。为了便于大数相加，将大数的各个数字存入到整型数组中。

#define maxsize 100

typedef struct node

int data[maxsize];

int top;

seqstack,*pseqstack;

4.功能函数设计。

1)栈初始化函数init_seqstack(char *ch)

此函数是将传入的字符处理成0~9的整数存入整型数组中。将*ch-’0’转化为整数存入s->data[i]中，结束标志是*ch不等于’\0’

2)首尾倒置函数convert_seqstack(pseqstack a)

此函数是将栈中的数值首尾颠倒，比如以前是1234，现在变成4321。只要将传入的a的栈中的元素依次取出压到c中，再返回c栈即可。

3)大数相加函数add(pseqstack s1,pseqstack s2)

此函数是处理两个大数相加的功能。将传入的两个大数压到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(pseqstack s,int n)

将其中一位大数取出一位数字与另一位大数相乘的结果移位，然后相加，从各位开始，每乘一个数，都要移位一个0

5)复制函数copy_seqstack(pseqstack a,pseqstack b)

将一个a栈中的元素拷贝到b栈中，先将a中的元素压到c栈中，再将c栈中的元素压到b栈中，即可实现复制功能。

6)大数相乘函数multiply(pseqstack s1,pseqstack s2)

此函数是实现大数相乘的核心算法。主要思想就是将s1中取出个位数a，分别与s2中的各个数相乘得到新的大数，再取s1中的十位数，与s1大数相乘，以此类推，然后将各个大数进行移位处理再相加。

5.编码实现。

#include ""

#define maxsize 100

typedef struct node

int data[maxsize];

int top;

seqstack,*pseqstack;

void destroy_seqstack(pseqstack *s)

if(*s)

free(*s);

*s=null;

return;

int push_seqstack(pseqstack s,int x)

if(s->top==maxsize-1)

return 0;

elsepseqstack init_seqstack(char *ch)

pseqstack s;

int i=0;

char *head;

s=(pseqstack)malloc(sizeof(seqstack));

if(s)s->top=-1;

head=ch;

while(*ch!='0')

return s;

int gettop_seqstack(pseqstack s,int *x)

if(s->top==-1)

return 0;

elseint empty_seqstack(pseqstack s)

if(s->top==-1)

return 1;

elsereturn 0;

int pop_seqstack(pseqstack s,int *x)

if(empty_seqstack(s))

return 0;

elsevoid print(pseqstack s)

int i;

for(i=0;i<=s->top;i++)

printf("%d",s->data[i]);

/将栈顶变成栈尾，栈尾变成栈顶。

pseqstack convert_seqstack(pseqstack a)

int x;

pseqstack c;

c=(pseqstack)malloc(sizeof(seqstack));

if(c)c->top=-1;

while(!empty_seqstack(a))

return c;

pseqstack add(pseqstack s1,pseqstack s2)

pseqstack s;

int d=0,a,b,result;

s=(pseqstack)malloc(sizeof(seqstack));

if(s)s->top=-1;

while(!empty_seqstack(s1)&&empty_seqstack(s2))

else if(result/10>0)

while(!empty_seqstack(s1))else

while(!empty_seqstack(s2))else

if(d!=0)

push_seqstack(s,1);

s=convert_seqstack(s);

return s;

pseqstack crol(pseqstack s,int n)

int i;

for(i=0;i push_seqstack(s,0);

return s;

void copy_seqstack(pseqstack a,pseqstack b)

pseqstack c;

int x;

c=(pseqstack)malloc(sizeof(seqstack));

if(c)c->top=-1;

while(!empty_seqstack(a))

while(!empty_seqstack(b))

while(!empty_seqstack(c))

pseqstack multiply(pseqstack s1,pseqstack s2)

pseqstack s,a,b;

int a,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--)

数据结构课程设计实验报告

数据结构课程设计实验报告

数据结构课程设计实验报告

数据结构课程设计实验报告

其他用户还读了