算法与数据结构课程设计课件

1、算法与数据结构课程设计长整数四则运算系统 2009-2010学年度第二学期赣南师范学院数学与计算机科学学院算法与数据结构课程设计综合设计报告课程设计名称： 长整数四则运算系统 专 业： 计算机科学与技术 班 级： 08计本（2） 学 号： 080703085 姓 名： 宋瑞珍 指 导 教 师： 肖老师 。课程设计名称： 长整数四则运算系统 专 业： 计算机科学与技术 班 级： 08计本（2） 学 号： 080703085 姓 名： 宋瑞珍 指 导 教 师： 肖老师 目录问题描述和分析1算法设计2数据结构设计3具体程序实现4目录界面设计5调试情况6算法分析和评价7综合设计总结81、问题描述和分析

2、 实现一个简单的长整数四则运算，在本系统中只对加法与减法作出了相应的系统编写。 1、对于长整数的四则运算可以看作为表达式的求值，表达式求值是程序设计语言中的一个最基本的问题，可以用不同的方法对系统进行编写，有运用栈实现对运算的求值，也可以引用链表来对长整数四则运算进行编写。 2、长整数四则运算实现计算任意长的整数的加法运算. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就计算并显示出这两个数的运算。 3、本演示程序中，集合的元素限定为数字字符09和字符，与；，输入字符可以任意长，输入形式以“回车符”为结束标志，串中字符顺序

3、不限，且允许出现重复字符。 4、利用双向循环链表现实长整数的存储，每个结点含一个整形变量。输入的形式以回车结束，可以直接输入正数或负数。按中国对于长整数的表示习惯，每四位一组，除数字和位于首位置的负号外，其它一切字符都将作为分隔符，连续多个分隔符当一个处理。但不使用分隔符也不影响结果。2、算法设计 长整数四则运算作为一个满足表达式语法规则的链式存储。算法的基本思想是： 首先建立一个双链表进行初始化int InistList(DuList &L,char fh)，fh为符号的标识符，进而进行插入函数的编写通过再链表头部插入新节点int Insfirst(DuList &L,int e或在链表的最

4、后插入新节点int Inslast(DuList &L,int e)，当节点插入建立完毕后计算节点的的节点数目以及计算节点元素e的位数int Count(int e)，对与输入的长整数要进行一定的检查，对于最高位为0的长整数利用去掉无效0函数int Dzero(DuList &L)对长整数进行缩进，然后再进行类型的转换将字符转换成数字型int ConversionD(char *s,int i,int &e)，通过函数int Creat(DuList &L,char *s)对相应的字符进行建立链表为实现上述程序功能，应以双向循环链表表示长整数。为此，需要定义一个抽象数据类型。1. 抽象数据类型

5、定义为：ADT OrderedList数据对象：D=ai|aiint,i=1,2,.n, n0数据关系：R1=|ai-1,aiD|=2,n 基本函数模块：int InistList(DuList &L,char fh)/创建空链表，并初始化,fh为符号标识符int DestroyList(DuList &L)int Insfirst(DuList &L,int e)/在头结点后插入新节点pint Inslast(DuList &L,int e)/在链表最后插入新节点int CountNode(DuList L)/计算链表的节点数int Count(int e)/计算节点元素e的位数int Dz

6、ero(DuList &L)/去掉无效0函数int CountB(DuList L)/计算长整数位数函数int ConversionD(char *s,int i,int &e)/将字符转化为数字int Creat(DuList &L,char *s)/通过相应的字符串建立链表。int Cmp(DuList L,DuList K)/结点相同时的比较两数大小函数int print(DuList L)/输出链表函数DuList add(DuList L,DuList K,char fh)/无符号加法,fh为符号标识符DuList sub(DuList L,DuList K,char fh)/无符号

7、减法函数,fh为符号标识位DuList Computing(DuList L,DuList K,char ys)/四则运算控制函数int PanGS(char *s)/判断输入格式int Prtmess1()/显示主菜单int Prtmess2()/显示菜单信息int InputS(char *cz,char *cz1)/从键盘输入两个长整数int main() 3、数据结构设计设计两个链表typedef struct DulNode为链表的定义类型#define ERROR 0#define OK 1#define OVERFLOW -1typedef struct DulNode/双向链表

8、存储结构struct DulNode *prior;/前指针struct DulNode *next;/后指针int data;/节点数据DulNode,*DuList;4、具体程序实现 #include #include #include #include using namespace std; #define ERROR 0 #define OK 1 #define OVERFLOW -1typedef struct DulNode/双向链表存储结构struct DulNode *prior;/前指针struct DulNode *next;/后指针int data;/节点数据DulNo

9、de,*DuList;int InistList(DuList &L,char fh)/创建空链表，并初始化,fh为符号标识符L = (DuList)malloc(sizeof(DulNode);/动态分配存储空间if(fh = -) L-data = 1;/L-data存放符号节点，如果是-则为1，否则为0else L-data = 0;L-prior = L;L-next = L;return OK;int DestroyList(DuList &L)DuList p,q;/定义两个结构体指针if(!L)return ERROR;/链表不存在p = L-prior;/p指向链表头节点的前驱

10、while(p!=L)/删除节点节点pq = p-prior;free(p);/释放节点p的空间return OK;int Insfirst(DuList &L,int e)/在头结点后插入新节点pDuList p,q;p = (DuList)malloc(sizeof(DulNode);p-data = e;q = L-next;L-next = p;p-prior = L;p-next = q;q-prior = p;return OK;int Inslast(DuList &L,int e)/在链表最后插入新节点DuList p,q;p = (DuList)malloc(sizeof(D

11、ulNode);p -data = e;q = L-prior;q-next = p;p-prior = q;p-next = L;L-prior = p;return OK;int CountNode(DuList L)/计算链表的节点数DuList p;p = L;int i;for(i = 0;p-next!=L;i+,p=p-next);return i;int Count(int e)/计算节点元素e的位数int i,k;for(i = 1,k=1000;e/k=0;i+,k=k/10);return i;int Dzero(DuList &L)/去掉无效0函数DuList p;if

12、(CountNode(L)next;while(!p-data)p = p-next;L-next = p;p-prior = L;return OK;int CountB(DuList L)/计算长整数位数函数if(L-next = L)return 0;/空链表Dzero(L);/删除0int i;i = Count(L-next-data)+(CountNode(L)-1)*4;/头节点数据的位数加上节点个数*4，每个节点有四位数return i;int ConversionD(char *s,int i,int &e)/将字符转化为数字int k,g,x,sum=0;for(k=1,g

13、=1;knext;q=K-next;while(p!=L&q!=K)/两链表都还没读完if(p-dataq-data) return 1;/p的数值q数值if(p-datadata) return -1;/p的数值next;q=q-next;return 0;int print(DuList L)/输出链表函数int i;DuList p;if(L-data=1&L-next-data=0)/如果结果是-0则符号标识清0，输出0L-data = 0;if(L-data=1&L-next-data!=0)coutnext;while(p-data=0&p-next!=L)/跳过无效零p=p-ne

14、xt;if(p=L) /输出0coutnext=L) /p是最后一个节点，输出最后一个结点的数值coutdata;return OK;if(p-next!=L)/p不是最后一个节点，输出数值并且输出，作为分隔符coutdatanext;while(p-next!=L) /循环输出不是最后结点的数if(p-data=0) cout0000,;elsefor(i=1;idata);i+)/节点上如果某一位为0，则输出0，否则输出数值cout0;coutdatanext;if(p-data=0) cout0000;/输出最后一个节点的数值elsefor(i=1;idata);i+)cout0;cou

15、tdata;return OK;DuList add(DuList L,DuList K,char fh)/无符号加法,fh为符号标识符int temp,cf=0;DuList p,q,R;InistList(R,fh);p=L-prior;q=K-prior;while(p!=L&q!=K) /从最后一个节点开始进行加法，进制10000temp=p-data+q-data+cf;if(temp=10000)/两数相加的和大于10000，temp=temp-10000且进位标识为1Insfirst(R,temp-temp/10000*10000);cf=1;elseInsfirst(R,tem

16、p);/无进位cf=0;p=p-prior;/p向前搜索q=q-prior;/q向前搜索while(p!=L)/K加完，L还有没加的，p加上进位temp=p-data+cf;cf=temp/10000;Insfirst(R,temp-temp/10000*10000);p=p-prior;while(q!=K)/L加完，K还有没加的，q加进位temp=q-data+cf;cf=temp/10000;Insfirst(R,temp-temp/10000*10000);q=q-prior;if(cf!=0) Insfirst(R,cf);/最后判断是否还有进位，如果有在链表表头新增一个节点，数据为

17、进位return R;DuList sub(DuList L,DuList K,char fh)/无符号减法函数,fh为符号标识位DuList p,q,R;int temp,cf=0;InistList(R,fh);p=L-prior;q=K-prior;while(p!=L&q!=K)/进行减法，不够减就借位temp=p-data-q-data-cf;/两数相减并减去借位if(tempprior;q=q-prior;while(p!=L&cf)/减完，还有借位if(p-data-cf=0&p-prior=L)/减去借位 return R;temp=p-data-cf;if(temp0)Ins

18、first(R,temp);p=p-prior;break;elseInsfirst(R,temp+10000);cf=1;p=p-prior;while(p!=L)/把L剩下的都复制过结果链表Insfirst(R,p-data);p=p-prior;return R;DuList Computing(DuList L,DuList K,char ys)/四则运算控制函数DuList R;Dzero(L);/删去L，K无效0Dzero(K);switch(ys) /根据从主函数，链表节点数大的，绝对值就大case +:/根据长整数的符号判别是进行加法还是减法，同时判断出结果的符 号，再调用无符

19、号加法或者减法算出结果 if(!L-data&!K-data) R=add(L,K,+);/两加数数都为正数，执行加法， 符号标识位为+ else if(L-data&K-data) R=add(L,K,-);/两加数都是负数执行减法，运算结果为负，符号标识位为- else if(!L-data&K-data)/被加数是正数，加是负数 if(CountNode(L)CountNode(K) R=sub(L,K,+);/被绝对值加数大于加数绝对值，执行加法，符号标识位为+else if(CountNode(L)CountNode(K) R=sub(L,K,-);/ 被加数绝对值大于加数绝对值，执

20、行被加数减去加数，符号标识符为-else if(CountNode(L)data&K-data) R=add(L,K,+);/被减数为正减数为负，执行加法，符号标识位为+else if(L-data&!K-data) R=add(L,K,-);/被减数为负减数为正，执行加法，符号标识位为- else if(L-data&K-data)/被减数为负减数为负if(CountNode(L)CountNode(K) R=sub(L,K,-);/被减数绝对值大于减数绝对值，用被减数减去减数，符号标识位为+else if(CountNode(L)CountNode(K) R=sub(L,K,+);/被减数

21、绝对值大于减数绝对值，用减数减去被减数，符号标识位为+else if(CountNode(L)CountNode(K) R=sub(K,L,-);/被减数绝对值小于减数绝对值，用被减数减去减数，符号标识位为-else if(Cmp(L,K)=0|Cmp(L,K)=1) R=sub(L,K,+);/两链表节点数相同，L值大于等于K值，用被减数减去减数，符号标识符为+else if(Cmp(L,K)=-1) R=sub(K,L,-);/两链表节点数相同，L值小于K值，用减数减去被减数加数，符号标识符为-break; return R;int PanGS(char *s)/判断输入格式int k,i

22、=1;if(*s57) return ERROR;/输入的不是数字也不是-，出错if(*s=-) k=0;/负数符号不算入节点位数else k=1;while(*(s+i)!=,&*(s+i)!=0)/输入的字符不是,和0，输入错误if(*(s+i)57)return ERROR;k+;i+;if(k4) return ERROR;/每个节点输入的字符大于4个，输入错误if(*(s+i)=0) return OK;/输入完成k=4;while(*(s+i)!=0)/输入的不是0并且不是，则输入错误if(*(s+i)9)return ERROR;if(*(s+i)=,)/如果遇到，k从-1开始算

23、保证每个节点位数是四位if(k!=4)/中间节点的位数不是四位，输入错误return ERROR;k=-1;k+;/如果遇到，后，k从零开始i+;if(k!=4)return ERROR;return OK;int Prtmess1()/显示主菜单cout1、按1加法endl2、按2减法endl3、按3退出endl;return OK;int Prtmess2()/显示菜单信息cout1、按1继续运算endl2、按2返回主选单endl;return OK;int InputS(char *cz,char *cz1)/从键盘输入两个长整数cout请输入长整数!endl;coutcz; while

24、(!PanGS(cz)/判断输入格式是否正确 cout输入格式错误,请重新输入!endl输入格式应为：XXXX，XXXX，XXXX，XXXX(X是数字)endlcz;/输入错误，重新输入coutcz1;while(!PanGS(cz1)/判断输入格式是否正确cout输入格式错误,请重新输入!endl输入格式应为：XXXX，XXXX，XXXX，XXXX(X是数字)endlcz1;/输入错误，重新输入return OK;int main()char cz99999; /定义字符串数组，用里保存从键盘输入的长整数char cz199999;DuList L1,L2,R;int flag=1;char

25、 xz;cout*endl 欢迎使用长整数运算器!endl*endl长整数的输入格式为：XXXX，XXXX，XXXX，XXXX;xz; while(xz3)/判断键入的是否为无效命令cout输入命令代号有错，请重新输入!xz;/输入的操作无效重新输入 switch(xz)/选择执行的运算case 1:while(flag=1)/同一个运算继续进行下去cout现在执行的是加法运算endl;InputS(cz,cz1);/从键盘输入长整数形式的字符串，且同时判别输入格式是否有错 Creat(L1,cz);/把长整数字符串转换为循环链表的储存结构Creat(L2,cz1); R=Computing(

26、L1,L2,+);cout运算结果:;print(R);/结果以长整数标准形式输出coutflag;/是否退出返回主菜单的标志break;case 2:while(flag=1)cout现在执行的是减法运算endl;InputS(cz,cz1);/从键盘输入长整数形式的字符串，且同时判别输入格式是否有错Creat(L1,cz);/把长整数字符串转换为循环链表的储存结构Creat(L2,cz1);R=Computing(L1,L2,-);cout运算结果:;print(R);coutflag; /是否退出返回主菜单的标志break;case 3: return 0; /退出程序flag=1;return 0;5、界面设计2.本程序包含三个模块：1)主程序模块：void main