第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
算法实验 实验报告 实现两个整数相加.doc
1.实现两个整数相加
1．需求分析：
课程设计任务是用链表(单链表或双向链表)实现任意位数的整数相加
(1) 输入的形式和输入值的范围；
输入的形式为字符，输入值的范围为整数。
(2) 输出的形式；整型 。
(3) 程序所能达到的功能；
实现任意位数的两个整数相加。
(4) 测试数据：包括正确的输入及输出结果和含有错误的输入及其输出的结果。
正确：
请输入第一个整数：
123
请输入第二个整数：
456
两个数的和是：
579
错误：
请输入第一个整数：
12.3
请输入第二个整数：
45.6
两个数的和是：
57-49
2.概要设计
ADT List{
数据对象：D={ai| ai∈ElemSet,i=1,2,…，n,n≥0}
数据关系：R1={|ai-1,ai∈D,i=2,…,n}
基本操作：initList(linklist &l)输入整数，存入链表
print(linklist l)//输出链表
add(linklist &l,linklist l1,linklist l2)//求和
main()主函数
3.详细设计
算法：
#include
#include
#include
typedef struct line
{
int data;
struct line *next;
}list,*linklist;
void initList(linklist &l)//输入整数，存入链表
{
char c;
linklist p;
l=(linklist)malloc(sizeof(list));
l->next=0;
while((c=getchar())!='\n')
{
p=(linklist)malloc(sizeof(list));
p->data=c-48;
p->next=l->next;
l->next=p;
}
}
void print(linklist l)//输出链表
{
l=l->next;
while(l!=0)
{
printf("%d",l->data);
l=l->next;
}
}
void add(linklist &l,linklist l1,linklist l2)//求和
{
int a,b=0;
linklist p;
l1=l1->next;
l2=l2->next;
l=(linklist)malloc(sizeof(list));
l->next=0;
while(l1!=0&&l2!=0)
{
a=l1->data+l2->data+b;
l1=l1->next;
l2=l2->next;
b=a/10;
a=a%10;
p=(linklist)malloc(sizeof(list));
p->data=a;
p->next=l->next;
l->next=p;
}
if(!l1&&!l2)
{
if(b==1)
{
p=(linklist)malloc(sizeof(list));
p->data=1;
p->next=l->next;
l->next=p;
}
}
if(l1)
{
while(l1!=0)
{
a=l1->data+b;
l1=l1->next;
b=a/10;
a=a%10;
p=(linklist)malloc(sizeof(list));
p->data=a;
p->next=l->next;
l->next=p;
}
if(b==1)
{
p=(linklist)malloc(sizeof(list));
p->data=1;
p->next=l->next;
l->next=p;
}
}
if(l2)
{
while(l2!=0)
{
a=l2->data+b;
l2=l2->next;
b=a/10;
a=a%10;
p=(linklist)malloc(sizeof(list));
p->data=a;
p->next=l->next;
l->next=p;
}
if(b==1)
{
p=(linklist)malloc(sizeof(list));
p->data=1;
p->next=l->next;
l->next=p;
}
}
}
void main()
{
linklist l1,l2,l3;
printf("请输入第一个整数\n");
initList(l1);
printf("请输入第二个整数：\n");
initList(l2);
printf("两个整数的和是：\n");
add(l3,l1,l2);//求和
print(l3);
getchar();
printf("\n");
开始
建立链表 11
建立链表 12
输出 11
输出 12
运算求和
结束
4.调试分析
时间复杂度：O(n)
设计和调试时存在问题：整数存入两个链表后，如何在链表中计算求和。
解决问题： 定义一个新的链表，将两个链表的和存入新链表中
5 总结：
学会了如何建立链表，知道了如何将数存入链表进行与运算，了解了如何进位，插入，删
除，如何修改节点中的指针，将课本上的知识通过自己动手解决问题，但是有些基础语法不
熟练，独立完成程序能力不强，不能是程序最优化，今后要更加注重实践，多锻炼，多写代
码，才能更好的运用所学知识。
2.算术表达式求值
1. 需求分析：
输入的形式和输入值的范围：以字符序列的形式从终端输入语法正确的、不含变量的整
数表达式。
输出的形式：整数
程序所能达到的功能：对算术四则混合运算表达式的求值。
测试数据： 3+4*5+6=29
2. 概要设计：
栈的抽象数据类型的定义
ADT Stack{
数据对象：D={ai|ai 属于 Elemset,i=1,2,……n(n>=0)}
数据关系：R1={|ai-1,ai 属于 D，i=1,2,……n(n>=0)}
基本操作：
InitStack(&OPND, "OPND") 定义操作数栈
InitStack(&OPTR, "OPTR") 定义运算符栈
3. 详细设计
算法：
#include
#include
#include
#define DEBUG
#define NULL 0
#define ERROR -1
#define STACKSIZE 20
/* 定义字符类型栈 */
typedef struct{
char stackname[20];
char *base;
char *top;
} Stack;
Stack OPTR, OPND; /* 定义前个运算符栈，后个操作数栈 */
char expr[255] = ""; /* 存放表达式串 */
char *ptr = expr;
int step = 0; /* 计算的步次 */
int InitStack(Stack *s, char *name)
{
s->base=(char *)malloc(STACKSIZE*sizeof(char));
if(!s->base) exit (ERROR);
strcpy(s->stackname, name);
s->top=s->base;
return 1;
}
int In(char ch)
{
return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#');
}
void OutputStatus( )
{
char *s;
printf("\n%-8d", ++step);
for(s = OPTR.base; s < OPTR.top; s++)
printf("%c", *s);
printf("\t");
for(s = OPND.base; s < OPND.top; s++)
printf("%d ", *s);
printf("\t\t%c", *ptr);
}
int Push(Stack *s,char ch)
{
#ifdef DEBUG
char *name = s->stackname;
OutputStatus();
if(strcmp(name, "OPND") == 0)
printf("\tPUSH(%s, %d)", name, ch);
else
printf("\tPUSH(%s, %c)", name, ch);
#endif
*s->top=ch;
s->top++;
return 0;
}
char Pop(Stack *s)
{
char p;
#ifdef DEBUG
OutputStatus();
printf("\tPOP(%s)", s->stackname);
#endif
s->top--;
p=*s->top;
return (p);
}
char GetTop(Stack s)
{
char p=*(s.top-1);
return (p);
}
/* 判断运算符优先权，返回优先权高的 */
char Precede(char c1,char c2)
{
int i=0,j=0;
static char array[49]={
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'<', '<', '<', '<', '<', '=', '!',
'>', '>', '>', '>', '!', '>', '>',
'<', '<', '<', '<', '<', '!', '='};
switch(c1)
{
/* i 为下面 array 的横标 */
case '+' : i=0;break;
case '-' : i=1;break;
case '*' : i=2;break;
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
