数据结构长整数四则运算

数据结构课程设计题目：长整数四则运算班级学号学生姓名提交日期成绩计算机与通信工程学院长整数四则运算一需求分析：问题描述：设计一个实现任意长的整数进行加法运算的演示程序。

基本要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。

任何整形变量的范围是 -(2^15 - 1) (2^15 - 1)。

输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。

在现实生活中有很多地方，例如航空航海、生物医疗等等方面，都需要很大的数来表示，这些用int甚至长整型long long都是远不够的，所以需要有一种算法来解决这种大数的表示和运算。

该问题只要求了大数的相加运算。

二详细设计：大致思路：【存储】用两个链表，每个节点保存一位数，在链表头保存数的正负，正数保存1，负数保存-1，如果是正数，后面每一位都储存正数，负数每一位都储存负数，数字按照链表头到链表尾从高位到低位的顺序；【相加】从两个链表的尾部开始同步向前相加，加完存到第一个链表，第二个加完的结点销毁，会存在两个链表不一样长的情况，没加的直接连到链表的前面，最高位的符号存到链表的头；【调整】根据表头的符号，调整后面的数字的值，中间会产生进位或者退位的问题，各个节点的符号不一定相同，但对于正负数都可以建立同样的调整模式，将正负到tmp中（1或-1）加或者减(tmp*10)，然后对前一位加或者减tmp*1即可。

第一位保留符号不变，这样不用处理多余的进位，也就不用再产生新的节点，也不用保存符号。

【输出】从前到后遍历已经处理好的表，将每一位进行输出就可以了。

结构体定义struct Node{Node *pre;Node *next;int data;};功能函数void Input(Node *p,Node *t)//处理输入和保存void disply(Node *h,Node *t,int l)//输出void add(Node *h1,Node *t1,Node *h2,Node *t2)//每一位相加int adjust(Node *h,Node *t)//将各个位的正负、大小、进位进行调整源程序：。

1 题目介绍和功能要求1.1 课程设计题目要求【问题描述】：设计一个实现任意长的整数进行加法运算的演示程序。

【题目容】：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。

任何整形变量的围是-(215- 1)~(215- 1)。

输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。

【基本要求】：（1）利用所学知识，设计相应的数据结构；（2）熟练运用开发环境；（3）完成软件的设计与编码；（4）熟练地掌握基本的调试方法。

1.2 题目分析【需求分析】：（1）本程序实现计算任意长的整数的加法运算. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就计算并显示出这两个数的运算。

（2）本演示程序中，数字字符限定为[‘0’~‘9’]和字符‘，’，输入字符可以任意长，输入形式以“回车符”为结束标志，串中字符顺序不限，且允许出现重复字符。

（3）利用双向循环链表现实长整数的存储，每个结点含一个整形变量。

输入的形式以回车结束，可以直接输入正数或负数。

按中国对于长整数的表示习惯，每四位一组，除数字和位于首位置的负号外，其它一切字符都将作为分隔符，连续多个分隔符当一个处理,但不使用分隔符也不影响结果。

2 系统功能模块结构图2.1 系统功能结构框图图2.1 系统功能结构图2.2主要模块的功能说明：（1）主调程序模块：void main(){初始化；do{接受命令；处理命令；}while(“命令”=”退出”)}（2）双向循环链表处理模块//cmplinklen.h //Creat.h //compare 说明：进行链表的存储和处理（3）长整数运算模块//add.h // sub.h //imul.h //idiv.h 说明:对长整数进行四则运算（4）界面模块//title.h //welcome.h说明：控制系统运行操作界面3 数据结构的设计及用法说明3.1概要说明为了实现上述功能，采取双向循环链表表示长整数，每个结点含一个整型变量，仅绝对值不超过9999的整数，整个链表用十进制数表示。

长整数四则运算题目:编制一个演示长整数的四则运算的程序一、需求分析1. 本程序实现计算任意长的整数的四则运算. 以用户和计算机对话的方式,先后输入数字的最多位数,然后程序就计算并显示出这两个数的运算。

2. 利用双向循环链表现实长整数的存储,每个结点含一个整形变量。

输入的形式以回车结束,可以直接输入正数或负数,程序会过滤掉无效的字符。

按中国对于长整数的表示习惯,每四位一组,除数字和位于首位置的负号外,其它一切字符都将作为分隔符,连续多个分隔符当一个处理。

但不使用分隔符也不影响结果。

3. 测试数据(1)0; 0; 输出“0”;(2)-2345,6789; -7654,3211; 输出“-1,000,000”;(3)-9999,9999; 1,0000,0000,0000; 输出“9999,0000,0001”;(4)1,0001,0001; -1,0001,0001; 输出“0”;(5)1,0001,0001; -1,0001,0001; 输出“1”;(6)-9999,9999,9999; -9999,9999,9999; 输出“-1,9999,9999,9998”;(7)1,0000,9999,9999; 1; 输出"1,0001,0000,0000".二、概要设计为实现上述程序功能,应以双向循环链表表示长整数。

为此,需要定义一个抽象数据类型。

1.抽象数据类型定义为:ADT OrderedList{2.数据对象:D={ai|ai∈int,i=1,2,...n, n≥0}基本操作:init(&a,digit4)操作结果:构造一个位数是digit4*4长整数。

pass(&a,&b,&c)初始条件:a,b,c都已存在操作结果:c等于a和b的和。

nep(&a)初始条件:a已存在。

操作结果:a变为输入参数的相反数。

printlong(&a)初始条件:a已存在。

“数据结构”课程设计报告长整数四则运算学生姓名：吴成杰徐文良指导教师：陈少军所在系：电子信息系所学专业：计算机科学与技术年级：2010计算机（1）班目录第1章需求分析 (1)1.1选题要求 (1)1.2选题背景和意义 (1)1.3选题目标 (2)1.4组员分配任务 (2)第2章概要分析 (2)2.1系统数据流图 (2)2.2原始数据 (3)2.3输出数据 (3)2.4对数据的处理 (3)2.5数据结构（存储方式） (4)2.6模块分析 (4)第3章详细设计 (4)第4章系统说明书 (11)第5章系统测试 (12)项目总结 (16)参考文献 (17)第1章需求分析1.1选题要求1、实现一个任意长度的整数进行四则运算的演示程序(1) 运算过程分步骤显示(2) 完成含有加法和减法的四则运算(3) 完成含有乘法和除法的四则运算(4) 包含括号的四则运算2、2个人对应完成2个人各自的任务1.2选题背景和意义（1）选题背景操作系统老师曾经布置我们做一道斐波拉契数列和求30的阶乘，但是计算的结果很大，还不知道该做样的存储，老师告诉我们需要用高精度数的知识能将计算的结果存储起来，数据结构老师也曾经布置过一个实验题，是计算长整数的加法的，但是长整数的位数是固定的。

于是我们试想计算任意长度的整数是不是能把所有的四则运算问题解决。

（2）选题意义我们选的这个课题能计算任意的四则运算，比如：1234567+7654321=8888888987654321-123456789=86419754123*456=5608884/42=2586-25*15+8*（9*2-144/12）=586-375+8*（18-12）=586-375+8*6=586-355+48=211+48=2591.3选题目标实现一个任意长度的整数进行四则运算的演示程序(1) 运算过程分步骤显示(2) 完成含有加法和减法的四则运算(3) 完成含有乘法和除法的四则运算(4) 包含括号的四则运算1.4组员分配任务我们组有两个成员，分别为吴成杰和徐文良，一个负责写主函数、函数整体的框架和写转换函数函数和对输入的字符进行处理，一个负责写出栈函数和写处理函数和拼接，程序出现错误，两个人一起在一起互相商量，修改。

实验报告：长整数四则运算实验者：唐怡04120082 题目：设计一个实现任意长的整数进行加法运算的演示程序一．需求分析1．本演示程序中，长整数为任意长的带符号的长整数的输入及求加法后输出的长整数形式为每四位一组，组间用逗号隔开，输入以“回车符”为结束标志。

2．程度执行的命令包括：1）构造整数1，2）构造整数2，3）做加法运算，4）结束3．测试数据（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．有序表的抽象数据类型定义为：ADT Dulinklist{数据对象：D={ai|ai为带符号整数，1，2,…,n,n>=0}数据关系：R1={<ai-1,ai>|ai-1,ai属于集合D,ai-1<ai,i=2,…..,n}基本操作：InitDulinklist(&)操作结果：构造一个空的有序表LDestroyDulinklist(&)初始条件：有序表L已存在操作结果：销毁有序表LDulinklistLength(L)初始条件：有序表L已存在操作结果：返回有序表L的长度DulinklistEmpty(L)初始条件：有序表L已存在操作结果：若有序表L为空表，则返回TUER，否则返回FALSEGetElem(L,pos)初始条件：有序表L已存在操作结果：若干1〈=POS〈=LENGTH（L），则返回有序表L中第POS个数据元素。

[实验名称]长整数四则运算[需求分析]设计一个实现任意长的整数进行减法运算的演示程序，要求完成长整数的加减运算，乘除运算可选做。

在这里长整数没有范围限制，可任意长。

运算后的进位、借位等都要进行正确处理，可实现动态的输入，实时的输出。

测试数据：0、0；输出“0”2345，6789、-7654，3211；输出“1，0000，0000”1，0000，0000，0000、9999，9999；输出“9999，0000，0001”1，0001，0001、；1，0001，0001；输出“0”自选数据：1,2345,6789; 9,8765,4321；输出“11,1111,1110”[概要设计]数据结构利用双向循环链表来实现对长整数的存储。

每个节点只存储四位十进制数字，即不超过9999的非负整数。

双向链表有头指针，它的data值存储长整数的符号，1为正，-1为负，0代表长整数为0；它的over值存储除头节点外节点的个数。

其他节点的data 值存储四位整数，over存储该四位整数溢出0~~9999范围的情况，一般over>0表示四位数超出9999，over<0表示四位数小于0。

选择该数据结构来完成长整数的加减运算是因为要对长整数进行运算，需要对长整数进行存储，所以选择用链表对长整数存储，又由于存储的顺序是从左到右，而运算的顺序则是从右到左，这样位了操作方便选择循环链表，在运算过程中有进位和借位的操作，所以最终选择双向循环链表的数据结构。

[详细设计]typedef struct DoubleNode //定义链表元素void InitNode(DLNode **head) //初始化链表int InsertNode(DLNode *head,int n,DataType x) //向链表第N个位置插入元素Xint digit(int n) //判断整数N有几位void PrintNode(DLNode *head) //打印链表void DestroyNode(DLNode **head)//销毁链表void add(DLNode *h1,DLNode *h2) //两数相加void jian(DLNode *h1,DLNode *h2) //两数相减int main() //入口函数[调试分析]调试过程中的困难：在数据的运算中，应为是根据数的大小来选择运算的，所以过程相对比较繁琐。

计算机C++实现任意长整数的四则运算一、什么是任意长整数任意长整数，也称作大整数或无限长整数，可以表示出任意长度的整数，是由多个整数构成的有限序列。

它的最大特征是其位数不受限制，可以用来表示任意大小的整数。

二、任意长整数四则运算1、四则运算任意长整数四则运算是指对任意长整数进行加、减、乘、除四种基本运算的操作。

2、C++实现任意长整数的四则运算（1）首先要明确，任意长整数是由多个整数构成的有限序列，所以要想实现四则运算，必须将单个整数进行相应的计算。

（2）因此，可以采用逐位计算的方法来实现任意长整数的四则运算。

具体的步骤如下：（a）以字符串的形式表示任意长整数，并转换成整型数组，每个元素代表任意长整数中的一位数字；（b）从数组的末尾开始，依次取出每一位数字，根据相应的运算符进行计算；（c）将计算结果存入到一个新的数组中；（d）最后，把新数组中的元素按照从小到大的顺序组合成一个新的字符串，这就是任意长整数的四则运算的结果。

三、C++实现任意长整数的四则运算的算法（1）定义函数原型：string Cal(stringstr1,string str2,char op);（2）申请内存空间：int *arr1 = newint[str1.length()]; int *arr2 = newint[str2.length()]; int *res = newint[max(str1.length(),str2.length())];（3）将字符串转化为整型数组：for(int i=0;i <str1.length();i++) arr1[i] = str1[i] - '0'; for(int j=0;j < str2.length();j++) arr2[j] = str2[j] - '0';（4）根据所传入的运算符，进行相应的运算：switch (op) {case '+': //加法运算break; case '-': //减法运算break; case '*': //乘法运算break; case '/': //除法运算break;}（5）将计算结果存入到新的数组中：for(intk=0;k<max(str1.length(),str2.length());k++) res[k] = add[k];（6）将计算结果的数组转换成字符串：string result=""; for(intl=0;l<max(str1.length(),str2.length());l++) result += to_string(res[l]);（7）返回计算结果return result;（8）释放内存空间delete[] arr1; delete[] arr2; delete[] res;四、总结任意长整数四则运算是指对任意长整数进行加、减、乘、除四种基本运算的操作。

数据结构课程设计报告题目：长整数四则运算学院计算机学院专业计算机科学与技术年级班别2010级四班学号3110006015学生姓名张法光指导教师张巍成绩____________________2012年6月一、需求分析1、设计一个实现任意长的整数进行四则运算的程序。

2、利用双向循环链表实现长整数的存储，每个结点含一个整型变量。

3、输入和输出形式是按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开，长整数位数没有上限，以分号结束长整型数据的输入。

4、实现长整数四则运算、阶乘和乘方运算。

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”.二、概要设计为了实现上述功能，采取双向循环链表表示长整数，每个结点含一个整型变量，且仅绝对值不超过9999的整数，整个链表用十进制数表示。

利用头结点数据域的符号表示长整数的符号，相加过程不破坏两个操作数链表，对长整数位数不作上限。

为此需要两个结构数据类型：双向循环链表和长整数，两个类型采用相同的结构，只是双向循环链表用来存储数据，长整型用表示数据的运算。

1、双向循环链表的数据结构及操作定义如下：typedef int Status;typedef int ElemType;typedef struct DuLNode //双向循环链表结点{ElemType data;struct DuLNode * prior;struct DuLNode * next;}DuLNode,* DuLinkList;typedef struct //双向循环链表{DuLinkList head; //双向循环链表头结点，不存放数据int len; //双向循环链表中的结点个数，头结点不计}LinkList;基本操作：Status InitList(LinkList &L);//构造一个空的线性链表void ClearList(LinkList &L);//将线性链表L重置为空表，并释放原链表的结点空间Status HeadInser(LinkList &L,ElemType e);//在线性链表的头结点后插入数据元素为e的新结点Status TailInser(LinkList &L,ElemType e);//在线性链表的头结点前插入数据元素为e的新结点Status HeadDelete(LinkList &L);//删除头结点后的第一个结点Status ListCopy(LinkList &L,LinkList L1);//将L1复制给L，保持L1不变2、长整数的数据类型和和操作定义为：void ScanNum(LinkList &L);//从键盘输入一个长整数，存至L;void PrintNum(LinkList L);//在屏幕打印长整数Lvoid NumChange(LinkList &L);//将长整数L还原成一般格式Status NumLarger(LinkList L1,LinkList L2);//比较正数L1与正数L2的大小，若L1大于或等于L2，返回TRUE，否则返回FALSE void NumPlus(LinkList L1,LinkList L2,LinkList &L3);//将L1与L2相加，结果存至L3; 即C=A+B；void NumMinus(LinkList L1,LinkList L2,LinkList &L3);//计算L1减去L2的值，结果存至L3；即C=A-B;void NumMul(LinkList L1,LinkList L2,LinkList &L3);//将L1与L2相乘，结果存至L3；即C=A*B;Status NumDiv(LinkList L1,LinkList L2,LinkList &L3,LinkList &L4);即C=A/B;//计算L1除以L2，商存至L3，余数存至L4，若L2为零，返回ERROR，否则返回OKStatus jiecheng(LinkList L1,LinkList &L2)即C=A！；//求L1的阶乘L2；若L1小于零，返还ERROR；否则返回OK；Status chengfang(LinkList L1,LinkList L2,LinkList &L3) 即C=A^B;//求L1的L2次方的结果，若L2小于零，返还ERROR；否则返回OK；3、本程序包含四个模块：1）主程序模块：void main( ) //main.c{初始化；do{接受命令；处理命令；}while(“命令”=“结束”)｝2）双向循环链表处理模块//LinkList.h;3）长整数运算模块//LongNum.h ,jiecheng.h , chengfang.h;4）界面模块 //Interface.h各模块之间的调用关系如下：主程序模块==========================================长整数运算模块界面模块======================双向循环链表处理模块=======================三、详细设计1、主要函数主程序模块//main.c双向循环链表处理模块//LinkList.h长整数四则运算模块//LongNum.h阶乘运算模块//jiecheng.h乘方运算模块//chengfang.h界面模块//Interface.hchar ShowMenu() //界面菜单显示char ShowPlus() //加法运算显示char ShowMinus() //减法运算显示char ShowMul() //乘法运算显示char ShowDiv() //除法运算显示char Showchengfang()//乘方运算显示char Showjiecheng() //阶乘运算显示2、函数的主要调用关系图InitList ClearList Interface=============================ShowScanNumJiecheng chengfang NumMinus NumChange======================================================================四、调试分析及编程心得体会刚开始使用C指针有偏颇，通过逐步调试修正错误。