2022年长整数数据结构课程设计 .pdf

《2022年长整数数据结构课程设计 .pdf》由会员分享，可在线阅读，更多相关《2022年长整数数据结构课程设计 .pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 数据结构课程设计报告题 目：长整数四则运算院 （系）：计算机工程学院专业：计算机嵌入式班级：嵌入式 1091 学生：李士岩指导教师：寇海洲孙成富邱军林殷 路2010 年 12 月名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 15 页 - - - - - - - - - 2 目 录一、需求分析 . 3二、概要设计 . 3三、程序设计步骤. 6四、运行结果 . 14 五、课程设计小结. 15 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -

2、- - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 15 页 - - - - - - - - - 3 一、需求分析：计算机中存储的数据是有范围限制的，对于超出存储限制的数据无法直接进行运算，为此需要设计相应的程序来完成这种超出范围限制的长整数间的四则运算。（1）输入 : 两个长整数；（2）输出 : 计算结果；（3）功能 : 双向循环链表实现长整数的存储，每个结点含一个整形变量。（4）测试数据：（1）0；0；应输出“ 0” 。（2）-2345,6789 ；-7654,3211 ；应输出“ -1,0000,0000” 。（3）-9999,9999 ；1,0

3、000,0000,0000；应输出“ 9999,0000,0001 ” 。（4）1,0001,0001 ；-1,0001,0001；应输出“ 0” 。（5）1,0001,0001 ；-1,0001,0000；应输出“ 1” 。（6）-9999,9999,9999；-9999,9999,9999；应输出“ 1,9999,9999,9998” 。（7）1,0000,9999,9999；1；应输出“ 1,0001,0000,0000” 。二、概要设计1、数据结构：节点：head Data4 next 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -

4、 - - - 名师精心整理 - - - - - - - 第 3 页，共 15 页 - - - - - - - - - 4 双向循环链表：2、程序流程设计：首先是设计双向链表，实现基本功能，然后设计主函数读入表达式，能够正确的分离运算符和数据， 分别存入双向链表中。然后设计一个函数表达式是哪种运算，以及结果的正负。 。具体设计如下：（1） ；用户输入表达式。（2） ：将用户输入的字符串转化成双向循环链表。（3） ：根据用户的输入形式确定执行调用函数；（4） ：最后打印输出；（5） ：a+b 算法： 1、从链表的Z 最后位节点向前加。设置up 记录进位情况。没进位为0，进位为1. 2、如果第一个操

5、作数大，则对第一个操作数剩余节点处理。3、如果第二个操作数大，则对第二个操作数剩余节点处理。4、如果最后， up 的值为 1，则创建新的节点储存。（6） ：a-b 算法： 1、从链表的最后位节点向前加，设down记录借位情况，没借位为0，借位为 -1 2、如果第一个操作数大，则记录结果为正，对第一个操作数剩余节点处理 3、如果第二个操作数大，则记录结果为正，对第二个操作数剩余节点处理 4、最后，将0000，, ，0000，xxxx 前的 0 滤掉。流程图：Node Node Node 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

6、- 名师精心整理 - - - - - - - 第 4 页，共 15 页 - - - - - - - - - 5 开始初始化双向循环链表和一些相关变量读取输入流的一个数据读取一个字符是保存运算符读取数入流的一个整形数据存入第一个数据链表中读取一个字符记录第一个数据的符号放回输入流判 断 是 不是正负号不是判 断 是 不是运算符不是放回输入流读取数入流的一个整形数据存入第二个数据链表中读取一个字符判 断 是不是 = 计算并输出结果结束是不是是判 断 是不 是 正负号名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -

7、 - - - - - 第 5 页，共 15 页 - - - - - - - - - 6 三、程序设计#include #include #include #include typedef struct LinkNode int data; /记录每个节点的整数（小于10000）LinkNode *next, *pre; /记录下一个节点的地址*pre; /记录前一个节点的地址linklist; linklist *head0; linklist *head1; /head0，head1分别记录两个整数链表的头指针linklist *currptr; linklist *result; /res

8、ult 记录结果链表的头指针/LinkList(); /构造函数，初始化链表/LinkList1(); /析构函数，释放空/void Creat(char a); /引入字符串，创立两个链表，分别表示两个整数/void Add(); /实现两个整数相加/void Display(); /显示结果void addtwo(); int sum(int n); void LinkList() /构造函数，初始化链表 /linklist *head0,*head1; /linklist *currptr; head0=(linklist *)malloc(sizeof(linklist); /申请一个

9、空间记录整数的符号和节点数head1=(linklist *)malloc(sizeof(linklist); result=(linklist *)malloc(sizeof(linklist); head0-next=head0; head0-pre=head0; /初始化链表，建立双向循环链表head1-next=head1; head1-pre=head1; result-next=result; result-pre=result; currptr=NULL; void LinkList1() /析构函数，释放空间 linklist *p1=head0,*p2=head1,*p3=r

10、esult; /三个指针分别指向三条链表的头指针while(p1!=p1-pre) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 15 页 - - - - - - - - - 7 p1-pre-next=p1-next; p1-next-pre=p1-pre; currptr=p1; p1=p1-next; free(currptr); while(p2!=p2-pre) /逐个删除节点，释放空间 p2-pre-next=p2-next; p2-next-pre=p2-

11、pre; currptr=p2; p2=p2-next; free(currptr); while(p3!=p3-pre) p3-pre-next=p3-next; p3-next-pre=p3-pre; currptr=p3; p3=p3-next; free(currptr); / delete p1; / delete p2; / delete p3; void Creat(char a) /引入字符串，创立两个链表，分别表示两个整数 int i=0,j=0,m=0,n=0,k=0,l=0,s=0,w=0; /i 记录字符串，j 记录加数节点数；s 记录被加数节点数/w 标记字符串中的-

12、号/k 记录字符串中的字符转化为整数的值，l 使每个节点记录4 位while(am!=;) m+; /m 记录字符串中被加数的字符数n=m; while(an!=0) n+; /n 记录字符串的总字符数if(a0=-) head0-data=(-1); /记录整数符号w=1; else head0-data=1; for(i=m-1;i=w;i-) if(ai!=,) /把字符转化为整数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 15 页 - - - - - - -

13、- - 8 k+=(ai-0)*sum(l); l+; if(ai=,|i=w) currptr=(linklist *)malloc(sizeof(linklist); /把整数存到双向循环链表中currptr-data=k; currptr-next=head0; currptr-pre=head0-pre; head0-pre-next=currptr; head0-pre=currptr; head0=currptr; s+; /节点数加 1 k=0; /重新初始化k 和 l l=0; head0-pre-data*=s; /存储整数符号和节点数/与建第一个整数链表一样，建立第二个整数

14、链表head1 k=0;l=0; if(am+1=-) head1-data=(-1); m+; else head1-data=1; for(i=n-1;im;i-) if(ai!=,) k+=(ai-0)*sum(l); l+; if(ai=,|i=m+1) currptr=(linklist *)malloc(sizeof(linklist); currptr-data=k; currptr-next=head1; currptr-pre=head1-pre; head1-pre-next=currptr; head1-pre=currptr; head1=currptr; 名师资料总结

15、 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 15 页 - - - - - - - - - 9 j+; k=0; l=0; head1-pre-data*=j; void Add() /实现两个整数相加 linklist *temp; if(abs(head0-pre-data)abs(head1-pre-data) /两个整数中，绝对值大的为被加数addtwo(); else if(abs(head0-pre-data)pre-data) temp=head0; head0=he

16、ad1; head1=temp; addtwo(); else if(abs(head0-pre-data)=abs(head1-pre-data) int k1,k2; linklist *p=head0,*q=head1; /如果节点数相同，则判断节点中数值大小while(p-data=q-data&p!=head0-pre-pre&q!=head1-pre-pre) p=p-next; q=q-next; k1=p-data; k2=q-data; if(k1k2) addtwo(); else temp=head0; head0=head1; head1=temp; addtwo();

17、 void addtwo() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 15 页 - - - - - - - - - 10 /节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的/默认 head0存的整数绝对值比head1 大 int s=0,m1=head0-data,m2=head1-data; m1=(head0-pre-data/abs(head0-pre-data); /head0 的符号m2=(head1-pre-data/abs(head1-pr

18、e-data); /head1 的符号linklist *p=head0-pre-pre,*q=head1-pre-pre; result-data=head0-pre-data; /存结果的节点数和符号while(q!=head1-pre) /head0 存的整数绝对值比head1大，即 head0的节点数大于或等于head1 currptr=(linklist *)malloc(sizeof(linklist); currptr-data=(p-data)*m1+(q-data)*m2+s; /两整数相加if(m1*m2)0) /如果符号相同 if(abs(currptr-data)-10

19、000=0) /相加后超过10000，则进位 s=currptr-data/10000; currptr-data=abs(currptr-data)%10000; else /abs(currptr-data)-10000data=abs(currptr-data); else if(m10&m2datadata+=10000; s=-1; else if(m10) /符号不同，在此相当于实现负整数加上正整数 s=0; if(currptr-data0) /大于 0，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

20、 - - - - - - - 第 10 页，共 15 页 - - - - - - - - - 11 currptr-data=10000-currptr-data; s=1; else currptr-data=abs(currptr-data); currptr-next=result; /存入链表currptr-pre=result-pre; result-pre-next=currptr; result-pre=currptr; result=currptr; p=p-pre; q=q-pre; /当 head0节点数比head1 长时，继续建链while(p!=head0-pre) c

21、urrptr=(linklist *)malloc(sizeof(linklist); currptr-data=p-data+s; s=currptr-data/10000; if(m1*m2)0) if(abs(currptr-data)-10000=0) s=currptr-data/10000; currptr-data=abs(currptr-data)%10000; else s=0;currptr-data=abs(currptr-data); else if(m10&m2datadata+=10000; s=-1; else if(m10) s=0; if(currptr-da

22、ta0) currptr-data=10000-currptr-data; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 15 页 - - - - - - - - - 12 s=1; else currptr-data=abs(currptr-data); currptr-data=abs(currptr-data)%10000; currptr-next=result; currptr-pre=result-pre; result-pre-next=currptr;

23、 result-pre=currptr; result=currptr; p=p-pre; if(s!=0) /处理相加后，进位问题 currptr=(linklist *)malloc(sizeof(linklist); currptr-data=abs(s); currptr-next=result; currptr-pre=result-pre; result-pre-next=currptr; result-pre=currptr; result=currptr; result-pre-data=m1*(abs(result-pre-data)+1); void Display() /

24、显示结果 linklist *p=result; int FuHao=result-pre-data/abs(result-pre-data);/ 结果的符号while(p-data=0&p!=result-pre-pre) /当运算后前几个节点的数据为0 时，不输出 p=p-next; result-pre-data=(abs(result-pre-data)-1)*FuHao; /结果记录非0 节点数 printf(%d,FuHao*p-data); /首先显示符号和第一个节点中的数if(abs(result-pre-data)!=1) p=p-next; /判断非 0 节点数是否为1 w

25、hile(p!=result-pre-pre) /继续输出 printf(,); /每 4 位一组，并用， 隔开printf(%04d,p-data); p=p-next; if(p=result-pre-pre&abs(result-pre-data)!=1) /显示最后一个节点数据名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 15 页 - - - - - - - - - 13 printf(,); printf(%04d,p-data); int sum(int

26、n) /计算 10 的乘方 int i,s=1; for(i=1;i=n;i+) s=s*10; return s; void main() /主函数char ch20;/ 链表对象char Yes_No; LinkList() ; LinkList1(); printf(| 输入两个任意长的整数。|n); do printf(| 输入形式为： (-)*,*,*;(-)*,*,*,*|n); printf(| 即符号 +数，每 4 位加一个 ,，两个数之间用;隔开|n); printf(| 请输入你要计算的两个数: n); scanf(%s,&ch); /输入任意长字符串LinkList()

27、; Creat(ch); /把字符串转化为整数，并存到链表中/调用转化函数Add(); /实现两个整数相加/调用 add()加法运算函数Display(); /输出结果 /调用输出函数printf( 是否继续计算 (Y/N):); /询问是否继续计算getchar(); Yes_No=getchar(); while(Yes_No=y|Yes_No=Y); /Yes_No 不等于 Y 或y时，程序退出 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 15 页 - - -

28、 - - - - - - 14 四、运行结果：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 15 页 - - - - - - - - - 15 四、课程设计小结：进一步掌握了双向链表的结构和基本操作。熟悉了加减法的实现及应用，在编程中会出现一些语法方面的错误，C语言掌握得不够牢固，算法方面因为有老师上课及实验时的指导所以能够了解。但是不是不够熟练。需要继续练习。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 15 页 - - - - - - - - -