数据结构课程设计-长整数加减运算.doc

课 程 设 计 报 告课程名称 数据结构课程设计 题 目 长整数加减运算 指导教师 设计起始日期 3.213.28 学 院 计算机学院 系 别 计算机科学与工程 学生姓名 班级/学号 成 绩 一、 需求分析设计一个实现任意长的整数间进行四则运算的程序，要求完成长整数的加运算和减运算。长整数的长度没有限制，可以是任意长。正确处理好运算之后的进位和借位。（1） 输入：-*,*,*;-*,*,*,* /-表示“-”可选（2） 输出：*,*，*,*是否继续计算(Y/N):（3） 功能：能正确进行相关数据的加减运算（4） 测试数据： 0；0；输出“0” 2345,6789；7654,3211；输出“1,0000,0000” 1,0000,0000,0000；-9999,9999；输出“9999,0000,0001” 1,0001,00001；-1,0001,0000；输出“0” 自选数据 二、 概要设计1、 使用双向循环链表实现长整数的运算及存储，构造双向循环链表，创建双向循环链表表示两个整数2、 设计两整数相加的函数Add()，addtwo()，其中Add()调用addtwo()函数，addtwo()具体实现两个整数的加减操作，进位及借位问题；设计显示函数Display()及主函数main()三、 详细设计1、 数据结构设计双向循环链表的构造 typedef struct LinkNode int data; /记录每个节点的整数（小于） LinkNode *next, *pre; /记录下一个节点的地址和前一个节点的地址linklist;2、 创建两个长整数的链表伪算法 void Creat(char a) /引入字符串，创立两个链表，分别表示两个整数 int 记录字符串i；记录加数节点数j；记录被加数节点数s；标记字符串中的-号记录字符串中的字符转化为整数的值k，使每个节点记录位l while(指针所指不是“；”)被加数字符数m自动加1 /m记录字符串中被加数的字符数 n=m; while(执政没有指到结尾处) 总字符串n位数自动加1; /n记录字符串的总字符数 if被加数不是负数 head0-data=(-1); /记录整数符号 w=1; else head0-data=1; for(i=m-1;i=w;i-) If指针所指为数字，而不是“，” /把字符转化为整数 k+=(ai-0)*sum(l); /sum()计算的乘方 l+; if(ai=,|i=w) 把整数存到双向循环链表中 s+; /节点数加 k=0; /重新初始化k和l l=0; head0-pre-data*=s; /存储整数符号和节点数四、 调试分析a、 调试过程中，连续输入数字运算，速度会明显变慢，发现在初始化链表及运算后没有释放链表，造成系统资源浪费，经改造后自爱后面添加了析构函数b、 算法的时空分析创建整数链表有三个循环，次数都为n。时间复杂度和空间复杂都都为O（n）五、 使用说明和测试结果1、使用说明：用户按照屏幕所显示的提示来正确输入数字其中-表示“-”为可选，从右至左每四位数字一个“，”2、测试结果： 六、 心得体会通过此实验，加深了我对链表的基本操作，对双向链表及循环链表的操作及实际运用有了很深的体会，在处理数字的进位借位时有了进一步的提高。七、 附录1、 链表的创建:#include#include#includetypedef struct LinkNode int data; /记录每个节点的整数（小于） LinkNode *next, *pre; /记录下一个节点的地址和前一个节点的地址linklist; linklist *head0; linklist *head1; /head0，head1分别记录两个整数链表的头指针 linklist *currptr; linklist *result; /result记录结果链表的头指针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标记字符串中的-号 /k记录字符串中的字符转化为整数的值，l使每个节点记录位 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!=,) /把字符转化为整数 k+=(ai-0)*sum(l); /sum()计算的乘方 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+; /节点数加 k=0; /重新初始化k和l l=0; head0-pre-data*=s; /存储整数符号和节点数2、 测试函数: void main() /主函数 char ch20;/链表对象 char Yes_No; LinkList() ; LinkList1(); printf(|输入两个任意长的整数。 |n); do printf(|输入形式为：-*,*,*;-*,*,*,*|n); printf(|即符号+数，每位加一个,，两个数之间用;隔开|n); printf(|请输入你要计算的两个数: n); scanf(%s,&ch); /输入任意长字符串 LinkList() ; Creat(ch); /把字符串转化为整数，并存到链表中/调用转化函数 Add(); /实现两个整数相加/调用add()加法运算函数