长整数数据结构课程设计2

1数据结构课程设计报告题目：长整数四则运算院（系）：计算机工程学院专业：计算机嵌入式班级：嵌入式1091学生：李士岩指导教师：寇海洲孙成富邱军林殷路2010年12月2目录一、需求分析...................................................................................................................................3二、概要设计...................................................................................................................................3三、程序设计步骤...........................................................................................................................6四、运行结果.................................................................................................................................14五、课程设计小结.........................................................................................................................153一、需求分析：计算机中存储的数据是有范围限制的，对于超出存储限制的数据无法直接进行运算，为此需要设计相应的程序来完成这种超出范围限制的长整数间的四则运算。（1）输入:两个长整数；（2）输出:计算结果；（3）功能:双向循环链表实现长整数的存储，每个结点含一个整形变量。（4）测试数据：（1）0；0；应输出“0”。（2）-2345,6789；-7654,3211；应输出“-1,0000,0000”。（3）-9999,9999；1,0000,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、数据结构：节点：headData[4]next4双向循环链表：2、程序流程设计：首先是设计双向链表，实现基本功能，然后设计主函数读入表达式，能够正确的分离运算符和数据，分别存入双向链表中。然后设计一个函数表达式是哪种运算，以及结果的正负。。具体设计如下：（1）；用户输入表达式。（2）：将用户输入的字符串转化成双向循环链表。（3）：根据用户的输入形式确定执行调用函数；（4）：最后打印输出；（5）：a+b算法：1、从链表的Z最后位节点向前加。设置up记录进位情况。没进位为0，进位为1.2、如果第一个操作数大，则对第一个操作数剩余节点处理。3、如果第二个操作数大，则对第二个操作数剩余节点处理。4、如果最后，up的值为1，则创建新的节点储存。（6）：a-b算法：1、从链表的最后位节点向前加，设down记录借位情况，没借位为0，借位为-12、如果第一个操作数大，则记录结果为正，对第一个操作数剩余节点处理3、如果第二个操作数大，则记录结果为正，对第二个操作数剩余节点处理4、最后，将0000，……，0000，xxxx前的0滤掉。流程图：NodeNodeNode5开始初始化双向循环链表和一些相关变量读取输入流的一个数据读取一个字符是保存运算符读取数入流的一个整形数据存入第一个数据链表中读取一个字符记录第一个数据的符号放回输入流判断是不是正负号不是判断是不是运算符不是放回输入流读取数入流的一个整形数据存入第二个数据链表中读取一个字符判断是不是=计算并输出结果结束是不是是判断是不是正负号6三、程序设计#includestdafx.h#includestdio.h#includemath.h#includestdlib.htypedefstructLinkNode{intdata;//记录每个节点的整数（小于10000）LinkNode*next,*pre;//记录下一个节点的地址*pre;//记录前一个节点的地址}linklist;linklist*head0;linklist*head1;//head0，head1分别记录两个整数链表的头指针linklist*currptr;linklist*result;//result记录结果链表的头指针//LinkList();//构造函数，初始化链表//LinkList1();//析构函数，释放空//voidCreat(chara[]);//引入字符串，创立两个链表，分别表示两个整数//voidAdd();//实现两个整数相加//voidDisplay();//显示结果voidaddtwo();intsum(intn);voidLinkList()//构造函数，初始化链表{//linklist*head0,*head1;//linklist*currptr;head0=(linklist*)malloc(sizeof(linklist));//申请一个空间记录整数的符号和节点数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;}voidLinkList1()//析构函数，释放空间{linklist*p1=head0,*p2=head1,*p3=result;//三个指针分别指向三条链表的头指针while(p1!=p1-pre){7p1-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-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);}//deletep1;//deletep2;//deletep3;}voidCreat(chara[])//引入字符串，创立两个链表，分别表示两个整数{inti=0,j=0,m=0,n=0,k=0,l=0,s=0,w=0;//i记录字符串，j记录加数节点数；s记录被加数节点数//w标记字符串中的‘-’号//k记录字符串中的字符转化为整数的值，l使每个节点记录4位while(a[m]!=';')m++;//m记录字符串中被加数的字符数n=m;while(a[n]!='\0')n++;//n记录字符串的总字符数if(a[0]=='-'){head0-data=(-1);//记录整数符号w=1;}else{head0-data=1;}for(i=m-1;i=w;i--){if(a[i]!=',')//把字符转化为整数8{k+=(a[i]-'0')*sum(l);l++;}if(a[i]==','||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++;//节点数加1k=0;//重新初始化k和ll=0;}}head0-pre-data*=s;//存储整数符号和节点数//与建第一个整数链表一样，建立第二个整数链表head1k=0;l=0;if(a[m+1]=='-'){head1-data=(-1);m++;}elsehead1-data=1;for(i=n-1;im;i--){if(a[i]!=','){k+=(a[i]-'0')*sum(l);l++;}if(a[i]==','||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;9j++;k=0;l=0;}}head1-pre-data*=j;}voidAdd()//实现两个整数相加{linklist*temp;if(abs(head0-pre-data)abs(head1-pre-data))//两个整数中，绝对值大的为被加数addtwo();elseif(abs(head0-pre-data)abs(head1-pre-data)){temp=head0;head0=head1;head1=temp;addtwo();}elseif(abs(head0-pre-data)==abs(head1-pre-data)){intk1,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();}}}voidaddtwo()10//节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的//默认head0存的整数绝对值比head1大{ints=0,m1=head0-data,m2=head1-data;m1=(head0-pre-data/abs(head0-pre-data));//head0的符号m2=(head1-pre-data/abs(head1-pre-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