文档介绍：计算机基础算法实验
班级:
学号:
姓名:
完成日期:
算法1 实现两个整数相加
需求分析
课程设计任务是用链表(单链表或双向链表)实现任意位数的整数相加。
输入的形式和输入值的范围:长度不超过一百位的整数。
输出的形式:有中文提示,分三行输出。
概要设计
LNode *CreatList()操作结果:构造一个链表.
LNode Add(LNode *t1,LNode *t2)初始条件:存在两个结点t1,t2; 操作结果:实现两个结点的相加。
void print(LNode *L) 初始条件:L存在;操作结果:打印链表L。
详细设计
(1)
主过程
开始
建立链表p1
建立链表p2
pare函数
调用print()函数,打印p3
结束
(2)
打印求和链表过程
开始
建立结点s1,s2
其中一个结点非空时,循环,下一位,
i>=j?
Add(s1,s2)
Add(s2,s1)
赋给P3,打印
结束
调试分析
输入的数必须为长度不超过一百位的整数,否则出现错误;如:,输出结果为9-46。根据实际情况的需要,可以将整数的长度定义为1000位,甚至更长。
总结
熟悉掌握链表的建立及调用,同时对数组的理解进一步加深;
认识到自己的不足,以后多加练****争取写出更好的算法。
实验内容:
源程序:
#include<>
#include<>
#include<>
#define MAX 100
typedef struct LNode
{
int data;
struct LNode *pre,*next;
}LNode,List;
LNode *CreatList()
{
LNode *p,*q,*r;
char s[MAX];
int i=0;
printf("输入一个整数:");
gets(s);
p=(LNode*)malloc(sizeof(List)*MAX);
q=r=p;
p->data=-1;
while(s[i]!=NULL)
{
q=(LNode*)malloc(sizeof(List));
q->data=s[i++]-'0';
q->pre=r;
r->next=q;
r=q;
}
r->next=NULL;
return p;
}
LNode Add(LNode *t1,LNode *t2)
{
while(t1->data!=-1&&t2->data!=-1)
{
t1->data=t1->data+t2->data;
if(t1->data>9)
{
t1->data-=10;
t1->pre->data+=1;
}
t1=t1->pre;
t2=t2->pre;
}
if(t1->next->data>9)
t1->next->data-=10;
return *t1;
}
LNode *Compare(LNode *p1,LNode *p2)
{
LNode *s1=p1->next,*s2=p2->next,*t1,*t2;
int i=0,j=0;
while(s1!=NULL)
{t1=s1;s1=s1->next;i++;}
while(s2!=NULL)
{t2=s2;s2=s2->next;j++;}
if(i>=j)Add(t1,t2);
else Add(t2,t1);
return i>=j?p1:p2;
}
void print(LNode *L)
{
LNode *p;
printf("两整数的和为:");
if(L->data!=-1)printf("%d",1);
p=L->next;
do
{
printf("%d",p->data);
p=p->next;
}
while(p!=NULL);
printf("\n");
}
int main()
{
LNode *p1,*p2,*p3;
p1=CreatList();
p2=CreatList();
pare(p1,p2);
print(p3);
getch();
return 0;
}
运行结果:示例
输入一个整数:6541
输入一个整数:212354
两整数的和为:218895
运行效果图为:
算法2 算术表达式求值
需求分析
课程设计任务是以字符序列的形式从终端输入语法正确的、不含变量的整数表达式,利用给定的算符优先关系,实现对算术四则混合运算表达式的求值,并演示在求值过程中运算符栈、操作数栈