计算机基础算法实验.doc

计算机基础算法实验班级：学号：姓名：完成日期：算法1 实现两个整数相加1 需求分析课程设计任务是用链表(单链表或双向链表)实现任意位数的整数相加。输入的形式和输入值的范围：长度不超过一百位的整数。输出的形式：有中文提示，分三行输出。2 概要设计LNode *CreatList()操作结果：构造一个链表.LNode Add(LNode *t1,LNode *t2)初始条件：存在两个结点t1,t2; 操作结果：实现两个结点的相加。void print(LNode *L) 初始条件：L存在；操作结果：打印链表L。3 详细设计（1）主过程开始建立链表p1建立链表p2调用Compare函数调用print()函数，打印p3结束（2）打印求和链表过程开始建立结点s1,s2其中一个结点非空时，循环，下一位，对应i.ji=j?Add(s1,s2)Add(s2,s1)赋给P3，打印结束4 调试分析输入的数必须为长度不超过一百位的整数，否则出现错误；如：输入6.4和3.2，输出结果为9-46。根据实际情况的需要，可以将整数的长度定义为1000位，甚至更长。5 总结（1） 熟悉掌握链表的建立及调用，同时对数组的理解进一步加深；（2） 认识到自己的不足，以后多加练习，争取写出更好的算法。实验内容：源程序：#include#include#include#define MAX 100typedef struct LNodeint data;struct LNode *pre,*next;LNode,List;LNode *CreatList()LNode *p,*q,*r;char sMAX;int i=0;printf(输入一个整数：);gets(s);p=(LNode*)malloc(sizeof(List)*MAX);q=r=p;p-data=-1;while(si!=NULL)q=(LNode*)malloc(sizeof(List);q-data=si+-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-data9)t1-data-=10;t1-pre-data+=1;t1=t1-pre;t2=t2-pre;if(t1-next-data9)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;doprintf(%d,p-data);p=p-next;while(p!=NULL);printf(n);int main()LNode *p1,*p2,*p3;p1=CreatList();p2=CreatList();p3=Compare(p1,p2);print(p3);getch();return 0;运行结果：示例输入一个整数：6541输入一个整数：212354两整数的和为：218895运行效果图为：算法2 算术表达式求值1 需求分析课程设计任务是以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，利用给定的算符优先关系，实现对算术四则混合运算表达式的求值，并演示在求值过程中运算符栈、操作数栈、操作数栈和主要操作的变化过程。输入的形式和输入值的范围：不含变量的整数表达式，算术四则混合运算表达式。输出的形式：表达式。2 概要设计Status InitStack(SqStack &S)操作结果：构造一个空栈S。Status GetTop(SqStack S)初始条件：栈S存在且非空。操作结果：用e返回S的栈顶元素.Status Push (SqStack &S,ElemType e) 初始条件:栈S已存在。操作结果：插入元素e为新的栈顶元素.Status Pop (SqStack &S,ElemType &e) 初始条件：栈S存在且非空. 操作结果：删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR.3 详细设计开始表达式的建立a,theta,ba47a=atoi(&a)b47b=atoi(&b)thetatheta=+a+btheta=-a-btheta=*a*btheta=/a/b结束4 调试分析设计算法时，应考虑到运算符的优先关系，依此思想进行设计；该算法的时间复杂度为O(n),n为栈的长度；5. 总结（1） 通过该算法了解到自己对栈的理解不是很到位，因此以后要加强这方面的练习，遇到类似问题时，不会束手无策；（2） 该算法是参考资料加上自己的理解所得，学到了不少的东西，收获也不小。实验内容：源程序：#include #include #include #include #define OVERFLOW -1#define OK 0#define ERROR 1typedef int Status;#define STACK_INIT_SIZE 100 /初始分配量#define STACKINCREMENT 10 /存储空间的分配增量typedef char ElemType; typedef ElemType OperandType; /操作数typedef char OperatorType;typedef struct ElemType *base; ElemType *top; int stacksize;SqStack;Status InitStack(SqStack &S) /构造一个空栈S S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType); if(!S.base) exit (OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;Status GetTop(SqStack S) ElemType e; if (S.top = S.base) return ERROR; e = *(S.top-1); return e;Status Push (SqStack &S,ElemType e) /插入元素e为新的栈顶元素 if (S.top - S.base = S.stacksize) S.base = (ElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof(ElemType); if(!S.base) exit (OVERFLOW); S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK;Status Pop (SqStack &S,ElemType &e) /若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if(S.top = S.base) return ERROR; e = * -S.top; return OK;char In(char c,char OP) if(c=35 & c; else if(mab=2) return 47) a=atoi(&a); if(b47) b=atoi(&b); switch(theta) case +: return a+b; break; case -: return a-b; break; case *: return a*b; break; case /: return a/b; break; OperandType EvaluateExpression() SqStack OPTR,OPND; OperandType a,b,c; OperatorType theta; InitStack(OPTR); Push(OPTR,#); InitStack(OPND); c=getchar(); while (c!=# | GetTop(OPTR)!=#) if (!In(c,OP)Push(OPND,c);c=getchar(); else switch(Precede(GetTop(OPTR),c) case : Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a);