《长整数的运算算法与数据结构课程设计1》由会员分享,可在线阅读,更多相关《长整数的运算算法与数据结构课程设计1(21页珍藏版)》请在金锄头文库上搜索。
1、*实践教学* 兰州理工大学 软件学院 算法与数据结构 课程设计题 目: 长整数的运算 专业班级: 软件二班 目 录摘 要1前 言2正 文31.采用类c语言定义相关的数据类型32.各模块的伪码算法33.函数的调用关系图64.调试分析75.测试结果76.源程序(带注释)8总 结15参考文献16致 谢17附件 部分源程序代码18摘 要数据结构该设计要求学生设计程序,实现两个任意长的整数求和及差的运算问题。通过该题目的设计过程,可以加深理解线性表的逻辑结构、存储结构,掌握线性表上基本运算的实现,进一步理解和熟练掌握课本中所学的各种数据结构,学会如何把学到的知识用于解决实际问题,培养学生的动手能力关键词
2、:双循环链表;插入;删除;长整数加减19前 言利用双向循环链表来实现对长整数的存储。每个节点只存储四位十进制数字,即不超过9999的非负整数。双向链表有头指针,它的data值存储长整数的符号,1为正,-1为负,0代表长整数为0;它的over值存储除头节点外节点的个数。其他节点的data值存储四位整数,over存储该四位整数溢出09999范围的情况,一般over0表示四位数超出9999,overnext; while(p!=head&inext; i+; if(i!=n) printf(插入位置错误n); return 0; 3.加法函数设计思路:先将各位做加减,然后根据所得长整数正负和各结点d
3、ata值进位或退位计算所得长整数的值并输出。void add(DLNode *h1,DLNode *h2) /两数相加 DLNode *p1=h1-prior,*p2=h2-prior; while(p1!=h1&p2!=h2) /每个链表元素相加 p1-data+=p2-data ; 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-prio
4、r-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!=h
5、1&p2!=h2) /每个链表元素相减 p1-data-=p2-data ; 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/1000
6、0); h1-next-next-data%=10000; if(h1-datanext-data/-10000); h1-next-next-data%=-10000; PrintNode(h1); 3. 函数的调用关系图开始主函数调运void add(DLNode *h1,DLNode *h2)建立链表主函数结束束)调运void InitNode(DLNode *h1)建立运算4. 调试分析a、 调试中遇到的问题及对问题的解决方法调试过程中的困难:在数据的运算中,应为是根据数的大小来选择运算的,所以过程相对比较繁琐。而且对于双向链表的两个指针的定位以及链表的插入和删除等操作花费的较多的时间
7、。在这查阅参照了大量的网络资料。b、算法的时间复杂度和空间复杂度由于链表采用双向循环链表结构,可以从链表两头操作,各种操作的算法时间复杂度比较合理,各函数以及确定链表中的结点位置都是O(n),n为链表长度。5. 测试结果a、 输入0和0做加法运算,输出“0”,结果如下图:b、 输入2345,6789和-7654,3211做减法运算,输出“1,0000,0000”,结果如下图:c、 输入1,0000,0000,0000和9999,9999做减法运算,输出“9999,0000,0001”,结果如下图:d、 输入1,0001,0001和1,0001,0001做减法运算,输出“0”,结果如下图:e、
8、输入1,2345,6789 和9,8765,4321做加法运算,结果如下图:6. 源程序(带注释)#include #include #include#include #define N 100 typedef int DataType; typedef struct DoubleNode /定义链表元素 DataType data; struct DoubleNode *prior; struct DoubleNode *next; DLNode; void InitNode(DLNode *head) /初始化链表 if(*head=(DLNode*)malloc(sizeof(DLNod
9、e)=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&inext; i+; if(i!=n) printf(插入位置错误n); return 0; if(nt=(DLNode *)malloc(sizeof(DLNode)=NULL) exit(1); nt-data=x; nt-prior=p-prior;
10、nt-prior-next=nt; nt-next=p; 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);