已阅读5页,还剩16页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
* 实践教学实践教学 * 兰州理工大学兰州理工大学 软件学院 算法与数据结构算法与数据结构 课程设计课程设计 题 目: 长整数的运算 专业班级: 软件二班 目目 录录 摘摘 要要.1 前前 言言.2 正正 文文.3 1.采用类c语言定义相关的数据类型.3 2.各模块的伪码算法.3 3.函数的调用关系图.6 4.调试分析.7 5.测试结果.7 6.源程序(带注释).8 总总 结结.15 参考文献参考文献.16 致致 谢谢.17 附件附件 部分源程序代码部分源程序代码.18 1 摘摘 要要 数据结构 该设计要求学生设计程序,实现两个任意长的整数求和及差的运算问题。通 过该题目的设计过程,可以加深理解线性表的逻辑结构、存储结构,掌握线性表 上基本运算的实现,进一步理解和熟练掌握课本中所学的各种数据结构,学会如 何把学到的知识用于解决实际问题,培养学生的动手能力 关键词:双循环链表;插入;删除;长整数加减 2 前前 言言 利用双向循环链表来实现对长整数的存储。每个节点只存储四位十进制数字, 即不超过 9999 的非负整数。双向链表有头指针,它的 data 值存储长整数的符号, 1 为正,-1 为负,0 代表长整数为 0;它的 over 值存储除头节点外节点的个数。 其他节点的 data 值存储四位整数,over 存储该四位整数溢出 09999 范围的情 况,一般 over0 表示四位数超出 9999,overnext; while(p!=head i+; if(i!=n) printf(“插入位置错误n“); return 0; 3.加法函数设计思路: 先将各位做加减,然后根据所得长整数正负和各结点 data 值进位或退位计算 所得长整数的值并输出。 void add(dlnode *h1,dlnode *h2) /两数相加 dlnode *p1=h1-prior,*p2=h2-prior; while(p1!=h1 p1=p1-prior; p2=p2-prior; p1=h1-prior; while(p1!=h1-next) /处理链表元素 if(p1-data=10000) p1-prior-data+=p1-data/10000; p1-data%=10000; if(p1-datanext!=0) p1-prior-data-=1; p1-data+=10000; p1=p1-prior; if(h1-next-data=10000) /处理最前面的数 insertnode(h1,0,h1-next-data/10000); h1-next-next-data%=10000; if(h1-datanext-data/10000); h1-next-next-data%=-10000; printnode(h1); 4.减法函数设计思路: void jian(dlnode *h1,dlnode *h2) /两数相减 dlnode *p1=h1-prior,*p2=h2-prior; while(p1!=h1 p1=p1-prior; p2=p2-prior; p1=h1-prior; while(p1!=h1-next) /处理链表元素 if(p1-data=10000) p1-prior-data+=p1-data/10000; p1-data%=10000; if(p1-datanext!=0) p1-prior-data-=1; p1-data+=10000; p1=p1-prior; if(h1-next-data=10000) /处理最前面的数 6 insertnode(h1,0,h1-next-data/10000); h1-next-next-data%=10000; if(h1-datanext-data/-10000); h1-next-next-data%=-10000; printnode(h1); 3.3. 函数的调用关系图函数的调用关系图 开始 主函数 调运 void add(dlnode *h1,dlnode *h2) 建立链表 主函数 结束 束) 调运 void initnode(dlnode *h1) 建立运算 7 4.4. 调试分析调试分析 a、 调试中遇到的问题及对问题的解决方法 调试过程中的困难: 在数据的运算中,应为是根据数的大小来选择运算的,所以过程相对比较繁 琐。而且对于双向链表的两个指针的定位以及链表的插入和删除等操作花费的较 多的时间。在这查阅参照了大量的网络资料。 b、算法的时间复杂度和空间复杂度 由于链表采用双向循环链表结构,可以从链表两头操作,各种操作的算法时 间复杂度比较合理,各函数以及确定链表中的结点位置都是 o(n),n 为链表长 度。 5.5. 测试结果测试结果 a、输入 0 和 0 做加法运算,输出“0” ,结果如下图: b、输入 2345,6789 和-7654,3211 做减法运算,输出“1,0000,0000” , 结果如下图: 8 c、输入 1,0000,0000,0000 和 9999,9999 做减法运算,输出 “9999,0000,0001” ,结果如下图: d、输入 1,0001,0001 和 1,0001,0001 做减法运算,输出“0” ,结果如下 图: e、输入 1,2345,6789 和 9,8765,4321 做加法运算,结果如下图: 6.6. 源程序(带注释)源程序(带注释) #include #include #include #include #define n 100 typedef int datatype; 9 typedef struct doublenode /定义链表元素 datatype data; struct doublenode *prior; struct doublenode *next; dlnode; void initnode(dlnode *head) /初始化链表 if(*head=(dlnode*)malloc(sizeof(dlnode)=null) exit(1); (*head)-prior=*head; (*head)-next=*head; int insertnode(dlnode *head,int n,datatype x) /向链表第 n 个位置插入元素 x dlnode *p,*nt; int i=0; p=head-next; while(p!=head i+; if(i!=n) printf(“插入位置错误n“); return 0; if(nt=(dlnode *)malloc(sizeof(dlnode)=null) exit(1); nt-data=x; nt-prior=p-prior; nt-prior-next=nt; nt-next=p; 10 p-prior=nt; return 1; int digit(int n) /判断整数 n 有几位 int i; for(i=1;n/=10,i+) if(n/10=0) return i; void printnode(dlnode *head) /打印链表 dlnode *p=head-next; int i; while(p-data=0) /去掉前面的一串 0 p=p-next; if(p=head) printf(“0n“); return; printf(“%d“,p-data); /最前面的一个数进行特殊处理,不用补零 p=p-next; while(p!=head) /打印后面的数字 printf(“,“); if(p-data=0) printf(“0000“); p=p-next; 11 continue; for(i=0;idata);i+) /补零 printf(“0“); printf(“%d“,p-data); p=p-next; printf(“n“); void destroynode(dlnode *head) dlnode *p,*p1; p=(*head)-next; while(p!=*head) p1=p; p=p-next; free(p1); free(p); head=null; void add(dlnode *h1,dlnode *h2) /两数相加 dlnode *p1=h1-prior,*p2=h2-prior; while(p1!=h1 p1=p1-prior; p2=p2-prior; p1=h1-prior; while(p1!=h1-next) /处理链表元素 if(p1-data=10000) p1-prior-data+=p1-data/10000; p1-data%=10000; if(p1-datanext!=0) p1-prior-data-=1; p1-data+=10000; p1=p1-prior; if(h1-next-data=10000) /处理最前面的数 insertnode(h1,0,h1-next-data/10000); h1-next-next-data%=10000; if(h1-datanext-data/10000); h1-next-next-data%=-10000; printnode(h1); void jian(dlnode *h2,dlnode *h1) /两数相减 dlnode *p1=h1-prior,*p2=h2-prior; while(p1!=h1 p1=p1-prior; p2=p2-prior; p1=h1-prior; while(p1!=h1-next) /处理链表元素 if(p1-data=10000) p1-prior-data+=p1-data/10000; p1-data%=10000; if(p1-datanext!=0) p1-prior-data-=1; p1-data+=10000; p1=p1-prior; if(h1-next-data=10000) /处理最前面的数 insertnode(h1,0,h1-next-data/10000); h1-next-next-data%=10000; 13 if(h1-datanext-data/-10000); h1-next-next-data%=-10000; printnode(h1); int main() /入口函数 dlnode *head1,*head2; char data1n,data2n; char d110,d210; int i,j,k; int xun; initnode( initnode( while(1) printf(“输入数据:n“); scanf(“%s %s“,data1,data2); initnode( initnode( i=0;k=0; while(data1i!=;) /将数 1 用链表储存 for(j=0;jstrlen(data2) /较长的数作为被加数 add(head1,head2); else add(head2,head1); break; case 2:if(strlen(data1)strlen(data2) /较长的数作为被减数 jian(head1,head2); else jian(head2,head1); break; default:break; 15 destroynode( destroynode( return 0; 16 总总 结结 关于实验本身的收获是掌握了双向链表,通过该题目的设计过程,可以加 深理解线性表的逻辑结构、存储结构,掌握线性表上基本运算的实现,进一 步理解和熟练掌握课本中所学的各种数据结构,学会如何把学到的知识用于 解决实际问题,培养学生的动手能力。而实验外的就是更好的利用了网路资源, 通过网络的搜索引擎等。加深了自己在这方面知识的补充。并且在于同学交流中分 析了彼此算法的优劣程度。我觉得这是本次实验最大的收获。 17 参考文献参考文献 1 严蔚敏,吴伟民.数据结构(c 语言版).清华大学出版社. 2 严蔚敏,吴伟民.数据结构题集(c 语言版).清华大学出版社. 3 data structure with c+. william ford,william topp .清华大 学出版社(影印版). 4 谭浩强.c 语言程序设计. 清华大学出版社. 5数据结构与算法分析(java 版) , a practical introduction to data structures and algorithm analysis java edition clifford a. shaffer , 张铭,刘晓 丹译 电子工业出版社 2001 年 1 月 18 致致 谢谢 首先,我要感谢我的算法与数据结构及课程设计老师王连相老师,谢谢 王老师对我的谆谆教导,让我懂得了算法与数据结构的理论知识,为我做课 程设计奠定了理论基础。另外,感谢王老师在我做课程设计的过程中给我提出的 宝贵意见和建议,我根据王老师的建议对我的程序进行了改进,从而使程序更加 完善。最后我还要感
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年耕地租赁合同
- 广告设备购销合同2024年
- 合伙企业协议格式
- 房地产代理销售协议书2024年
- 服装制造商合作合同
- 2024年二手房屋买卖合同范例
- 担保合作协议填写指南
- 合伙餐馆协议书样本专业
- 装修预算合同范本2024年
- 2024设备搬迁运输合同
- 人教版数学五年级上册课本习题(题目)
- 钢筋合格证(共6页)
- BIM技术全过程工程管理及应用策划方案
- 弯扭构件制作工艺方案(共22页)
- 水利工程填塘固基、堤身加固施工方法
- 中医针灸的骨边穴怎样定位
- 人教版八年级上册英语单词表默写版(直接打印)
- 电脱水、电脱盐讲解
- 江西省科技创新平台建设(PPT课件)
- 违约损失率(LGD)研究
- 沟槽回填施工方案(完整版)
评论
0/150
提交评论