数据结构课程设计报告
题目：长整数四则运算
一、需求分析
1.
问题描述： 由于工程上有时候需要对很大的数
进行计 算，但是计算机本身提供的数据类型无法保存 几百位甚至几千位的数字，所以需要设计专门 的算法对数据进行相应的计算。此程序的设计 任务是：设计一个程序能够实现长整数运算的 程序，而且能够对一些错误异常进行辨别调整， 计算出正确的结果。程序输入格式是字符串， 保存时需要用双向循环链表将字符串每四位保 存在循
环链表中的一个节点中，然后再计算后 运行出结果。
2. 基本功能
功能一：建立双向循环链表 , 计算链表个数， 对链表的数据进行修改，能在链表中插入结点。
功能二：将字符串转换成相应的数字存储在 双向循环链表中
功能三：对存入双向循环链表的长整数进行 相加，相减，相除
3. 输入输出
程序输入以字符串的形式输入， 数
据的类型是字 符串，包含元素的范围是数字，逗号，负号。 输入时用字符串输入，输出时以一链表结点输 出，而且每个结点表示四位。
二、概要设计
1.
设计思路： 由于计算机无法完成位数很大的数字
计算， 设计思路就是将很长的数据进行分割， 一部分一 部分的用计算机固有数据类型进行计算。 将各部 分的结果整合起来。 由于计算机固有的整数类型 存数的对大整数是 2＾15-1 ，所以为了方便，且 符合中国人对长整数的表示习惯， 建立一个双向 循环链表，每个结点存储四位数字， 以万为进制。 从最低位开始加法， 超过一万向
上进位， 所以每 次加法应该是对应两个结点和进位数相加， 进位 值初始为 0；减法也是一个结点计算一次，每次 计算应该是第一个链表对应的结点值减去第二 个结点的值和借位值的和，借位值初始值为 0； 除法的计算可以借助减法， 被减数被减数减一次 则最终结果加一；直至被减数
比减数小。
2.
数据结构设计：
因为计算的是一个连续的数字， 需要桉顺序
一次计算，所以采用的数据结构的逻辑结构是线 性表。因为要求每一个结点只存储四位数字， 为 了将数字连接起来， 采用的数据结构的存储结构 是链式
1．双向循环链表的抽象数据类型定义为： ADT Link
{
数据对象： D={ai | ai ∈ CharSet ， i=1， 2，⋯⋯， n， n≥ 0} 数据关系 ; R={ } 基本操作： InitLinkList(&L,a) 操作结果：构造一个双向循环链表 L ，用 a 判断是正数还是负数 DestroyList(&L) 初始条件：双向循环两已经存 在 操作结果：销毁有序表 L Insert(&L,a) 初始条件：双向循环链表已经存在 操作结果：在循环链表的末尾插入一个结点， 且此结点的数据值为 a HeadInsert(&L,a) 初始条件：双向循环链表已经存在 操作结果：在循环链表的头结点后插入一个结 点，且此结点的数据值为 a CountNode(&L) 初始条件：双向循环链表存在 操作结果： 计算出链表中结点的个数， 并返回 个数 Compare(&L1, &L2) 初始条件： L1和 L2 存在 操作结果：比较两个双向循环链表的大小， 用返回值 1 表示 L1 大于 L2, 返 回值-1 标志 L1 小于 L2,返回值 0 标志 L1 和 L2 相等 ToNum(*s,i,&e) 初始条件： s 为字符串中指向某个字符的指 针 操作结果：将 s 的前 i 个字符转换为数字， 存入 e 中 CreatNum(&L,&s) 初始条件： s 为某个字符串，双向循环链表 L 存在 操作结果：将字符串 s 转换成数字存入到循 环链表 L 中 Add(L1 ， L2, op) 初始条件：双向循环链表 L1 和 L2 存在， op 为结果的标识符 操作结果：两个链表相加，求出结果。 Sub(L1,L2, op) 初始条件：双向循环链表 L1 和 L2 存在 操作结果： L1 减去 L2, 求出结果 ，op 为结果的标识符 EraseZero(Link &L) 初始条件：双向循环链表 L 存在 操作结果：删去 L 链表头结点后， 第一个数据不为零结点前的所有数据为零的结点。 如果结点数据都为零，则保存一个结点。 print(L) 初始条件：双向循环链表 L 存在 操作结果：从 L 头结点开始顺此打印每个结点中的数据 3. 软件结构设计： 本程序包含四个模块： 1. 主程序模块 Int main() { 接受命令 While( “命令” != “退出” ) { 输入字符串 建立双向循环链表 将字符串转换为要求的格式存 入链表的每个结点 对链表中数据进行即兴操作数 再次接受命令 } 2. 双向链表操作模块 - 实现结点的插入、 删 除、修改 3. 字符串转换存储模块 实现将字符串转换 为 数字按格式存储在链表中 4. 数据计算模块— --- 对存储在链表中的 数据进行计算，得到最终期望的结果 各个模块调用的关系如下： 主程序模块中的函数原型： void Interface() ------------------ 操作界面函数 Status CreatNum(Link &L,char*s) Link Compute(Link &L1,Link &L2,char Ope) 创建数字链表函数 数据计算函数 加法计 数据运算模块： Link Add(Link &L1,Link &L2,char op) Link Sub(Link &L1,Link &L2,char op) 减法运算 双向链表操作模块 void InitLinkList(Link &L,char a) Status DestroyList(Link &L) Status Insert(Link &L,Elemtype a) int CountNode(Link L) BOOL Compare(Link &L1,Link &L2) void EraseZero(Link &L) Status HeadInsert(Link &L,Elemtype a) 字符串转换模块 Status CreatNum(Link &L,char*s) Status ToNum(char*s,int i,long &e) 人机界面： 三、 详细设计 1.. 根据分析和链表操作的特点，采用双向循环链表实现，这里头结点存储数字的符号。 typedef long Elemtype ; typedef int Status; typedef int BOOL; typedef struct LNode{ Elemtype data; LNode *next; LNode *prior; }Node,*Link; void InitLinkList(Link &L,char a){ // 对一个双向循环链表进行初始化，分配头结点 L = (Link)malloc( sizeof (Node)); // 动态分配存储空间 If(!L) return FALSE; if (a == '-' ) L->data = -1; //L->data 存放符号节点，如果是‘ - '则为，否则为 0 else L->data = 1; L->prior = L; L->next = L; } Status DestroyList(Link &L){ // 销毁链表 L if (!L) return ERROR;// 链表不存在 p = L->prior; //p 指向链表头节点的前驱 while (p!=L) // 删除节点节点 p { q = p->prior; free(p); // 释放节点 p的空间 p = q; } free(L); // 释放链表 L 的存储空间 return OK; } Status Insert(Link &L,Elemtype a){ // 分配一个结点，并将其数据值存为 a, 插入到链表的末尾 p=(Link)malloc( sizeof (LNode)); if (!p) exit(OVERFLOW); p->next=p->prior=NULL; p->data=a; Link q=L->prior; q->next=p; p->prior=q; p->next=L; L->prior=p; return OK; } Status HeadInsert(Link &L,Elemtype a){ // 分配一个结点，并将其数据值存为 a，按头插入法插入 p=(Link)malloc( sizeof (LNode)); if (!p) exit(OVERFLOW); p->data=a; Link q=L->next; q->prior=p; p->next=q; L->next=p; p->prior=L; return OK; } Status ToNum(char*s,int i,long &e){ // 将字符串 s 的前 i 位转换为正数，并由 e保存 sum=0; for (m=1,n=1;m<=i;n=n*10) //n 的值每次是原来的 10 倍 sum+=(*(s-m)- '0' )*n; m++; } e=sum; // 转换成相应的 return OK; Status CreatNum(Link &L, char *s){ // 将字符串转分割成很多部分，每部分转换为数字后存在一个链表结点中。 InitLinkList(L,s[0]); if (*s== '-' ) { InitLinkList(L,s[0]); s++; } else InitLinkList(L,s[0]); while (*s!= '\\0' ) { if (*s== ',' ) { ToNum(s,i,e); Insert(L,e); i=-1; // 因为这是已经将某一个逗号前 i 个字符变成数字加入 } // 数字链表中，逗号不算本次 i++; s++; } ToNum(s,i,e); Insert(L,e); } int CountNode(Link L){ // 计算链表 L的结点数 Link p=L->next; while (p!=L) { i++; p=p->next; } return i; } BOOL Compare(Link &L1,Link &L2){ // 比较链表 L1和L2的大小，如果 L1大于L2,返回1,如果L2大于L1, 返回-1, 如果相等，返回{ if(CountNode(L1)>CountNode(L2)) // L1 大于 L2 else if(CountNode(L1) 0 else{ p1=L1->next,p2=L2->next; while(p1!=L1&&p2!=L2) { if(p1->data>p2->data) // L1 大于 L2 if(p1->data } } L1和L2相等 } Link Add(Link &L1,Link &L2,char op) 主要函数 // 将字符串 L1和 L2的数据相加，得到的结果链表 头结点指针返回 Int c=0,temp Link p1,p2,p3 p1=p1->prior,p2=p2->prior InitLinkList(L3) p1!=L1&& Temp=p1->data+p2->data+c p2!=L2 是否 temp>=10000 主要函 是 temp=temp-10000 HeadInsert(L3,temp) c=1 P1=p1->prior p2=p2->prior p1!=L1 否 HeadInsert(L3,temp) c=0 temp=p1->data+c c=temp/10000 是否 temp>=10000 是 temp=temp-10000 HeadInsert(L3,temp) 否 HeadInsert(L3,temp) p1=p1->prior p2!=L2 temp=p2->data+c c=temp/10000 是否 temp>=10000 是 temp=temp-10000 HeadInsert(L3,temp) 否 HeadInsert(L3,temp) p2=p2->prior 是否 c=1 是否 HeadInsert(L3,c) Link Sub(Link L1,Link L2,char op) // 将字符串 L1和 L2的数据相减，得到的结果链表的头结点指针返回 Int c=0,temp Link p1,p2,p3 p1=p1->prior,p2=p2->prior InitLinkList(L3) p1!=L1&& p2!=L2 Temp=p1->data-p2->data-c 是否 temp<0 是 temp=temp+10000 HeadInsert(L3,temp) c=1 p1=p1->prior p2=p2->prior 否 HeadInsert(L3,temp) c=0 p1!=L1 temp=p1->data-c 是否 temp<0 是 temp=temp+10000 c=1 HeadInsert(L3,temp) p1=p1->prior p2!=L2 否 HeadInsert(L3,temp) c=0 temp=p2->data-c 是否 temp>=10000 是 temp=temp+10000 c=1 HeadInsert(L3,temp) p2=p2->prior 否 HeadInsert(L3,temp) c=0 是 否 c=1 是否 HeadInsert(L3,c) void EraseZero(Link &L) {// 删除链表 L的无效零元素结点 p=L->next,q; while(p->data==0&&p->next!=L) { q=p; p=p->next; p->prior=q->prior; free(q); } L->next=p; } Link Compute(Link &L1,Link &L2,char Ope) // 主要函数 // 对链表 L1和链表 L2进行计算，即相加，相减等等 EraseZero(L1) EraseZero(L2) p1=L1->prior p2=L2->prior; L1->data==1&& L3=Add(L1,L2, '+') op= L1->data==-1&&L2->data== L2->data==1 1 '+' 是否 L1和 L2相等 是 否 L3= Sub(L1,L2, '+') 是否 L1大于 L2 是 否 L3=Sub L3=Sub(L2,L1, '- ) L1->data==1&&L2->data==- 1 (L1,L2 ，'- ‘) ‘ 是否 L1和 L2相等 是 否 L3= Sub(L1,L2, '+') 是否 L1大于 L2 是 否 L3= L3= Sub(L1,L2, '+‘ ) Sub(L2,L1, '- ‘) L1->data==-11&& L2->data==-1 L1->data==1&& op='- ‘ L2->data==1 L3=Add(L1 ，L2, '- ‘) 是否 L1大于 L2 是 L3=Sub(L1,L2, '+' ) L3=Add(L1,L2, '+' ); 否 L3=Sub(L2,L1, '-' ) L1->data==1&& L2->data==-1 L1->data==-1&& L2->data==1 L1->data==-1&&L2->data== -1 L3=Add(L1,L2, '-' ); 是否 L1大于 L2 是 L3=Sub(L1,L2, '-' ) 否 L3=Sub(L2,L1, '+' ) void Interface() // 界面函数 , 显示操作的主界面 Status print(Link L){ // 顺次打印链表 L 中的数据 EraseZero(L); if(*s<48&&*s!='-'||*s>57) // 第一个不是数字也不是 - ，则出错 return ERROR; if(*s=='-') k=0; else k=1; i=1; while(*(s+i)!='\\0') { if(*(s+i)!=','&&(*(s+i)>57||*(s+i)<48)) return ERROR; i++; i=1; while(*(s+i)!=','&&*(s+i)!='\\0') { i++; k++; } if(k>5) return ERROR; if(*(s+i)=='\\0') return OK; k=4; while(*(s+i)!='\\0') { if(*(s+i)==',') { if(k!=4) return ERROR; k=-1; // 此时逗号字符不能在四个数字的计算之中} if(k!=4) // 最后一个逗号后必须有四个数 return ERROR; return OK; } k++; i++; 函数调用关系图： HeadI Count 四、 调试分析 main 1. 实际完成的功能有：长整数的加法和减法， 支持的数据类型是整形， 能够对异常输入进行判 断，打印和计算的时候能够消除可能出现的前置 零。 In Ton 2. 程序的主要函数 compute时间复杂度为 Add Sub Compare eraseZero O(n) ，其实 n为计算的两个链表的结点个数的较 大值。物理存储使用的是双向链表， 有两个指针 域，空间消耗在合理范围之内 3. 调试中由于是双向链表， 在插入时应该注 意 将 prior 域进行考虑，刚开始写程序时忘记，导 致输出结果错误。 清楚前置零的时候开始没 有考 虑输入数据全是零的时候， 结果将全部的数据结 点都给删除， 最后没有结果输出， 调试中发现这 个问题，应该将每个链表至少保存一个数据结 点。 4. 由于时间仓促，而且长整数四则运算的乘法 一直没有想到好的办法， 如果再有几天时间， 乘 法这个功能完全可以加上。 随之就可以完成乘方 的计算 5. 本程序还有很大的扩充地方， 应该可以将 程 序由正数扩充为浮点数，能够运行更复杂的数 据，如求阶乘，开方等功能。如果实现了，则这 个计算器的功能方面就可以和 windows系统自带 的计算器媲美了 。 五、测试结果 列出你的测试结果， 包括输入和输出。 注意 测试数据应该完整和严格，至少给出 2组测试 结果（含合法数据与非法数据）。 输入0;0 ，输出0 输入 1,0001,0001;-1,0001,0001 ；输出 0 输入1,0001,0001 ；-1,0001,0000 ；输出 1 输入-9999,9999 ；-9999 ；9999；输出 -1,9999,9998 非法数据 1,000 ； 000,1 ；输出“输入错误” 六、用户手册 说明如何使用你编写的程序， 详细列出每一 步的具体操作步骤。 这里可以有适当的运行结 果抓图。用户手册与开发过程无关， 只与使用 有关，必须是 Step by Step 的。 所有运行结果截图均要求有实际数据的内 容，截图尺寸要求按页宽排版两张大小， 且要 求有每张图下面有规范的标题说明如何使用 你编写的程序，详细列出每一步的操作步骤。 1. 进入操作主界面 2．按照命令提示操作 ⑴选 1，进入加法运算 ① 输入第一个操作数： 并且按照提示格式输 入 如果输入错误，比如 1,000 ，则程序会提示 错误，重新输入 ② 如果输入正确， 比如输入 1,0000 ，输入下 一个数 ③ 输入正确，如输入 9999,9999 则计算出结 果 ④ 输出每个链表中的结点值， 便于观察比较 ⑤ 输出结果 1,0000,9999 ⑵选 2，进入减法运算 ① 输入第一个操作数， 并按照提示的格式输 入 如果输入错误， 比如，10,000 ，程序会提示 输入错误，重新输入 ② 如果输入正确，比如 9999,9999 ，输入下 一个数。 ③ 第二个数也输入正确， 比如输入 10,0000 ， 输出结果 ④ 提示是否继续计算，选择 Y或者 y退 出，其他任意键继续操作 七、体会与自我评价 长整数四则运算的一些思考 这次的课程设 计中， 长整数四则运算这个实 验给了我很大的挑战， 在设计中遇到了很多的困 难，比如如何用如何将字符数据分割成很多部分 存储进双向循环链表， 如何判断输入的字符串是 否是正确的； 在输入特殊数据买比如 0000,00000 时，程序能够消除无用的前置零得出正确的结 果，我在这些问题上都考虑的很久， 一点点的攻 破难题， 而在这次实验中我对长正数的各种运算也 有了一定的认识， 对于特别长的数的计算， 只能 先求局部结果， 最后将局部结果综合起来， 得到 最终结果。 比如加法就是从最低位开始计算， 判 断进位后再一次向高位计算， 最终得到结果。 计 算加法的时候， 由于是每四位一个结点， 所以是 以万位为进制。 输出时如果一个结点中数据是以 为，则前面输出三个零，如果是两位，则输出两 个零，如果是三位，则输出一个零，四位数直接 输出。 如果节点数据为零， 则按第一种情况输出 是前面加三个零即可。 为了程序的健壮性， 应该 考虑负数和正数相加的情况， 如果一个较大的正 数加上一个数值较小的负数， 应该是大数减去去 掉振幅符号的小数， 即可。如果是一个较小的正 数加上一个数值较大的负数， 则应该是去掉正负 号的负数减去正数， 最后在结果里加上一个负号 即可。 乘法的基本思想是相加， 但是在双向循环链 表中，如果乘数很大的时候， 单纯的相加要进行 很多次， 效率上完全不够满足要求， 一般是用字 符串直接按位相乘，按竖式结构计算。 除法的实现可以用减法， 但是问题还是和乘 法一样，如果数字太大的话，用双向循环链表， 要进行的减法次数也是很庞大的。 以上是我对长整数四则运算的一点思考， 本 次实验中学到的很多的知识， 对循环链表的操作 也更加的熟悉，更让我增长了许多的编程经验， 我相信以后的编程学习中我会表现的更加出色。 因篇幅问题不能全部显示，请点此查看更多更全内容