实验报告长整数四则运算

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

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

任何整形变量的范围是 -(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. 理解长整数的概念及其在编程中的应用。

2. 掌握长整数的基本运算方法，包括加法、减法、乘法和除法。

3. 提高编程能力，通过实际操作加深对长整数运算的理解。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发工具：PyCharm三、实验内容1. 长整数的定义与初始化2. 长整数的加法运算3. 长整数的减法运算4. 长整数的乘法运算5. 长整数的除法运算四、实验步骤1. 长整数的定义与初始化在Python中，长整数不需要特殊声明，只需按照常规整数进行定义即可。

下面是长整数的定义与初始化示例：```pythona = 123456789012345678901234567890b = 987654321098765432109876543210```2. 长整数的加法运算长整数的加法运算与常规整数相同，使用`+`符号。

下面是长整数加法运算的示例：```pythonresult = a + bprint("加法运算结果：", result)```3. 长整数的减法运算长整数的减法运算同样与常规整数相同，使用`-`符号。

下面是长整数减法运算的示例：```pythonresult = a - bprint("减法运算结果：", result)```4. 长整数的乘法运算长整数的乘法运算与常规整数相同，使用``符号。

下面是长整数乘法运算的示例：```pythonresult = a bprint("乘法运算结果：", result)```5. 长整数的除法运算长整数的除法运算与常规整数相同，使用`/`符号。

下面是长整数除法运算的示例：```pythonresult = a / bprint("除法运算结果：", result)```五、实验结果与分析1. 长整数的定义与初始化：通过定义长整数，我们了解了长整数在Python中的表示方法。

“数据结构”课程设计报告长整数四则运算学生姓名：吴成杰徐文良指导教师：陈少军所在系：电子信息系所学专业：计算机科学与技术年级：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个数据元素。

数据结构实验报告题目：长整型数四则运算学院计算机学院专业软件工程年级班别2010级1班成绩____________________2012年7月1日目录课程设计实验报告1一、实验概要- 1 -二、实验目的- 1 -三、实验环境- 1 -四、抽象数据类型的定义- 1 -五、存储结构的定义- 1 -六、算法设计- 2 -六、程序运行情况- 30 -七、实验总结- 33 -实验中遇到的问题：-33-实验总结：-33-八、思考题错误！未定义书签。

题目：长整型数四则运算一、实验概要1、设计一个实现任意长的整数进行四则运算的程序。

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

3、程序执行的命令包括：1）、输入长整数1；2）、输入长整数2；3）、输入执行的运算符；4）、计算并输出结果；5）、结束。

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”.二、实验目的输入和输出形式是按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开，长整数位数没有上限，以分号结束长整型数据的输入，进行计算三、实验环境Visual C++6.0四、抽象数据类型的定义1、双向循环链表的数据结构及操作定义如下：typedef short ElemType; //定义基本数据类型，我们采用short来表示任意4位整数。

计算机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;四、总结任意长整数四则运算是指对任意长整数进行加、减、乘、除四种基本运算的操作。

实验题目：设计一数据结构可处理任意长度的整数概要设计1.数据结构的定义采用双向链表存储任意长整数。

双向链表的定义如下：class DblList {private:DblNode *head, *tail;DblNode *current;int sign;public:DblList();用说明：点击打开应用程序。

依次输入任意两个整数（例如123456，+1234567），按回车，会出现菜单，如下图：按‘1’则实现两整数的加法按‘2’则实现两整数的乘法按‘#’结束注：菜单可重复出现直至‘#’退出。

实现加法，乘法如下图：2.测试结果：(1) 123456(2) +1234567(3) -1(4) 12a3(5)+注：当输入错误时，允许重新输入。

五、源程序/* 主函数 *//***************************************************/#include ""void main(){string s;string p;DblList list1;while(1){ xit |"<<endl;cout<<"--------------------------"<<endl;while (1){cin>>choose;if (choose=="1"){list1+list2;break;}else if (choose=="2"){list1*list2;break;}else if (choose=="#"){return;}else{cout<<"输入有误，请重新输入！！"<<endl;continue;}}}}/*头文件，包括长整数数据结构的定义，成员函数的定义*//***********************************************************/#include <iostream>#include <string>#include <cmath>using namespace std;struct DblNode{int data;DblNode * prior;DblNode * next;};bool IsNum(char a){ //判断字符a是否是便是数字int s=a-'0';if(s>=0&&s<10) return true;else return false;}bool IsInt(string a){ //判断字符串a是否表达一串数字bool Jud=1;int i=1;char s=a[0];if (a=="+"||a=="-") return false;if (s=='+'||s=='-') {}else if (s>='1'&&s<='9'){}else if (a[0]=='0'&&a[1]=='\0') return true;else return false;while (a[i]!='\0'){Jud=IsNum(a[i]);if (Jud==0) return false;i++;}return true;}int JudSign(string s){ //返回数字的符号if (s[0]=='-') return -1;else if(s[0]=='0'&&s[1]=='\0') return 0;else return 1;}int CtoI(char a){int i=a-'0';return i;}class DblList { //定义一个双向链表类，存储任意长度的数字private: //并可以进行标准化输出和加法，乘法。

4
长整数四则运算实现
长整数四则运算实现
加法
对于加法，我们需要从低位到高位依次相加。如果结果大于等于10，我们需要进位。我们 可以使用链表或数组来实现这个算法
链表加法示例代码(Python)
THANK YOU
2
数据结构选择
数据结构选择
链表
链表是一种动态数据结构，可以根据需要随时增加或减少节点。链表中的每个节点包含两 部分：数据和指向下一个节点的指针。使用链表可以方便地实现长整数的每一位的存储和 操作
数据结构选择
数组
数组是一种静态数据 结构，其大小在创建 时确定，不能更改。 对于长整数，我们可 以使用数组来表示每 一位数字，从而实现 大数的存储和运算
20XX
数据结构综合实训 -长整数四则运算
时 间：20XX-XX-XX
-
1 2 3 4
1
引言
引言
在计算机科学中，长整数四则运算是一 个经典问题
由于计算机的整数类型通常有固定的范 围，在进行大数运算时，必须采用特殊 的数据结构和技术来处理
本实训将介绍如何使用链表和数组来实 现长整数的表示和四则运算
数据结构选择
3
长整数表示
长整数表示
链表表示法
我们可以将长整数表示为一个链表，其中 每个节点存储一个数字(0-9)。例如，数 字123可以表示为1->2->3。链表的头部表 示整数的低位，尾部表示高位
长整数表示
数组表示串中的每个字符存储在数 组的一个元素中。例如，数字123可以表示为array [ 0]=1, array [ 1]=2, array [ 2]=3

课程设计实验报告：1.4长整数四则运算题目：长整数四则运算一、实验内容【问题描述】设计一个实现任意长的整数进行加法运算的演示程序【基本要求】利用双向循环链表实现长整数的存储，每个结点含一个整形变量。

任何整形变量的范围是-（2八15-1）〜（2八15-1）。

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

【实现基本功能】⑴是想长整数的四则运算；（ii）实现长整数的乘方和阶乘运算；（iii）整形量范围是-（2沏-1）~（2八n-1），其中n是由程序读入的参量。

输入数据的分组方法另行规定；【实现加强版本的功能】⑴四则运算在原来版本的基础上支持小数运算，除法还可以通过输入整数后加小数点与相应要求取的精确位数求出精确值，如：求取3666除以7的后三位精确值，可以在输入时将除数输入为3666.000或3666.0000，就能得出相应的精确位数，当然求取后，没有余数的输出；（ii）乘方的功能也进行了强化，支持小数操作；（iii）添加了多个出错处理（即输入重操作）对相应数据输入与输出进行提示；【加强版的实现原理】⑴加减法运算加强：在原来版本的基础上依照基本的加减法操作将数据用小数点进行分隔，记录下连个输入数的小数位长度，并将小数位较短的一个数据后补0直至小数位数相同，然后用函数处理输出的数据；（ii）乘除法、乘方：其处理方法较为简单，主要是记录数据中小数位数的长度，然后通过每种运算方式不同的运算原理截取小数位，再按照输出格式将数据处理进行输出；（iii）根据定义，阶乘保持不变；【特色分析】⑴加强版程序加上了简单的声音提示，无论是输入与输出均会有八个音符的其中之一对输入与输出与否进行提示，同时在输入输出数据出错时，还会用三个音符对重输入进行提示，增强了人性化操作；【测试数据】（1）0；0；应输出“0”。

（2）-2345,6789；-7654,3211；应输出“-1,0000,0000”。

（3）-9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。

山东理工大学计算机学院课程设计（数据结构）班级计科0503班姓名王新政学号0512105988指导教师肖爱梅张艳华二○○七年七月十三日课程设计任务书及成绩评定课题名称长整数四则运算Ⅰ、题目的目的和要求：设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。

通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。

同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

Ⅱ、设计进度及完成情况Ⅲ、主要参考文献及资料[1]严蔚敏，吴伟民主编. 《数据结构》（C语言版）.清华大学出版社. 2002[2] 殷人昆等著. 《数据结构》（C++版）. 清华大学出版社. 2001[3] 金远平著. 《数据结构》（C++描述）. 清华大学出版社. 2005[4] Frank M.Carrano 等著. 《数据结构与Ｃ++高级教程》.清华大学出版社. 2004[5] 严蔚敏,吴伟民主编. 《数据结构习题集》（C语言版）.清华大学出版社. 2002学科部主任___________（签字）Ⅳ、成绩评定：设计成绩：（教师填写）指导老师：（签字）二○○七年七月十三日目录第一章概述 (1)第二章系统分析 (2)第三章概要设计 (3)第四章详细设计与源程序 (4)第五章调试过程中的问题及系统测试情况 (12)第六章结束语 (13)参考文献 (14)第一章概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。

课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。

《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。

数据结构课程设计报告长整数运算数据结构课程设计报告题目：长整数四则运算一、需求分析1.问题描述：由于工程上有时候需要对很大的数进行计算，可是计算机本身提供的数据类型无法保存几百位甚至几千位的数字，因此需要设计专门的算法对数据进行相应的计算。

此程序的设计任务是：设计一个程序能够实现长整数运算的程序，而且能够对一些错误异常进行辨别调整，计算出正确的结果。

程序输入格式是字符串，保存时需要用双向循环链表将字符串每四位保存在循环链表中的一个节点中，然后再计算后运行出结果。

2.基本功能功能一：建立双向循环链表,计算链表个数，对链表的数据进行修改，能在链表中插入结点。

功能二：将字符串转换成相应的数字存储在双向循环链表中功能三：对存入双向循环链表的长整数进行相加，相减，相除。

3.输入输出程序输入以字符串的形式输入，数据的类型是字符串，包含元素的范围是数字，逗号，负号。

输入时用字符串输入，输出时以一链表结点输出，而且每个结点表示四位。

二、概要设计1.设计思路：由于计算机无法完成位数很大的数字计算，设计思路就是将很长的数据进行分割，一部分一部分的用计算机固有数据类型进行计算。

将各部分的结果整合起来。

由于计算机固有的整数类型存数的对大整数是2＾15-1，因此为了方便，且符合中国人对长整数的表示习惯，建立一个双向循环链表，每个结点存储四位数字，以万为进制。

从最低位开始加法，超过一万向上进位，因此每次加法应该是对应两个结点和进位数相加，进位值初始为0；减法也是一个结点计算一次，每次计算应该是第一个链表对应的结点值减去第二个结点的值和借位值的和，借位值初始值为0；除法的计算能够借助减法，被减数被减数减一次则最终结果加一；直至被减数比减数小。

2.数据结构设计：因为计算的是一个连续的数字，需要桉顺序一次计算，因此采用的数据结构的逻辑结构是线性表。

因为要求每一个结点只存储四位数字，为了将数字连接起来，采用的数据结构的存储结构是链式。

数据结构长整数四则运算实习 1 1.4 长整数四则运算实习报告题目：设计一个实现任意长的整数进行加法运算的演示程序。

一、需求分析1. 本演示程序中，利用双向循环链表实现长整数的存储，每个结点含一个整型变量任何整型变量的范围是 - （ 215-1 ）—（ 215-1 ）。

在每个结点中仅存十进制数的 4位，即不超过 9999 的非负整数，整个链表表示为万进制数。

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

2. 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入数据中的非法字符）和运算结果显示在其后。

3. 程序执行的命令包括：（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,00014) 1,0001,0001 ；-1,0001,0001 ；应输出 0。

5)1,0001,0001 ；-1,0001,0000 ；应输出 1.； -9999,9999,9999 ；应输出 -1,9999,9999,9998struct LinkNode //定义结构体 LinkNode{int data; // LinkNode *next; //LinkNode *pre; // };class LinkList // 定义类 LinkList7)1,0000,9999,9999 ； 1；应输出 1,0001,0000,0000概要设计6)-9999,9999,9999记录每个节点的整数（小于 10000）记录下一个节点的地址记录前一个节点的地址private:Lin kNode *head0,*head1; //headO ,headl分别记录两个整数链表的头指针Lin kNode*currptr;Lin kNode *result; //result 记录结果链表的头指针public:Lin kList(); // ~Li nkList(); // void Creat(stri ng a); // void Add(); // void Display(); // void addtwo(); //构造函数，初始化链表析构函数，释放空间引入字符串，创立两个链表，分别表示两个整数实现两个整数相加显示结果节点多的作为被加数，少的作为加数，实现整大的加小的//数绝对值};void mai n() //主函数do{} while(Yes_No=='y'||Yes_No=='Y'); //Yes_No 不等于'Y'或'y'时，程序退出三、详细设计#include#in clude#in cludeusing n amespace std;struct Lin kNode{int data; //Li nkNode *n ext; // 记录每个节点的整数（小于10000）记录下一个节点的地址Lin kNode*pre;// 记录前一个节点的地址Lin kNode *head0,*head1; //headO,head1分别记录两个整数链表的头指针}; class Lin kList private:Lin kNode *currptr;Lin kNode *result; //result 记录结果链表的头指针public: Lin kList(); // ~Li nkList(); // void Creat(stri ng a); // void Add(); // void Display 。

数据结构课程设计报告题目：长整数四则运算一、需求分析1. 问题描述：由于工程上有时候需要对很大的数进行计算，但是计算机本身提供的数据类型无法保存几百位甚至几千位的数字，所以需要设计专门的算法对数据进行相应的计算。

此程序的设计任务是：设计一个程序能够实现长整数运算的程序，而且能够对一些错误异常进行辨别调整，计算出正确的结果。

程序输入格式是字符串，保存时需要用双向循环链表将字符串每四位保存在循环链表中的一个节点中，然后再计算后运行出结果。

2. 基本功能功能一：建立双向循环链表，计算链表个数，对链表的数据进行修改，能在链表中插入结点。

功能二：将字符串转换成相应的数字存储在双向循环链表中功能三：对存入双向循环链表的长整数进行相加，相减，相除。

3. 输入输出程序输入以字符串的形式输入，数据的类型是字符串，包含元素的范围是数字，逗号，负号。

输入时用字符串输入，输出时以一链表结点输出，而且每个结点表示四位。

二、概要设计1. 设计思路：由于计算机无法完成位数很大的数字计算，设计思路就是将很长的数据进行分割，一部分一部分的用计算机固有数据类型进行计算。

将各部分的结果整合起来。

由于计算机固有的整数类型存数的对大整数是2人15-1 ,所以为了方便，且符合中国人对长整数的表示习惯，建立一个双向循环链表，每个结点存储四位数字，以万为进制。

从最低位开始加法，超过一万向上进位，所以每次加法应该是对应两个结点和进位数相加，进位值初始为0 ;减法也是一个结点计算一次，每次计算应该是第一个链表对应的结点值减去第二个结点的值和借位值的和，借位值初始值为0 ;除法的计算可以借助减法，被减数被减数减一次则最终结果加一；直至被减数比减数小。

2. 数据结构设计：因为计算的是一个连续的数字，需要桉顺序一次计算，所以采用的数据结构的逻辑结构是线性表。

因为要求每一个结点只存储四位数字，为了将数字连接起来，采用的数据结构的存储结构是链式。

1．双向循环链表的抽象数据类型定义为：ADT Link{数据对象：D={ai | ai € CharSet , i=1 , 2 , .......... , n, n > 0}数据关系；R={<ai-1,ai> | ai-1,ai € D,i=2 , ............ , n}}基本操作：InitLinkList(&L,a) 操作结果：构造一个双向循环链表L ，用a 判断是正数还是负数DestroyList(&L)初始条件：双向循环两已经存在操作结果：销毁有序表LInsert(&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 为结果的标识符操作结果：两个链表相加，求出结果。

一、需求分析设计一个实现任意长的整数间进行四则运算的程序，要求完成长整数的加、减运算，乘除运算可选做。

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

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

测试数据：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，1111；1，1111 输出“0”二、概要设计1、数据结构利用双向循环链表来实现对长整数的存储。

选择该数据结构来完成长整数的加减运算是因为a.要对长整数进行运算，需要对长整数进行存储，选择用链表对长整数存储。

b.存储的顺序是从左到右，运算的顺序则是从右到左，为操作方便选择循环链表。

c.在运算过程中有进位和借位的操作。

2、使用算法三、详细设计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() //入口函数四、调试分析由于在程序设计时，对于指针的不了解，编程时使用双重指针，无形中给自己增添了更多麻烦。

老师在检查的过程中指出并教导了这一点。

五、测试结果1、输入0和0做加法运算，输出“0”，结果如下图：2、输入2345，6789和-7654，3211做减法运算，输出“1，0000，0000”，结果如下图：3、输入1，0000，0000，0000和9999，9999做减法运算，输出“9999，0000，0001”，结果如下图：4、输入1，0001，0001和1，0001，0001做减法运算，输出“0”，结果如下图：5、输入1，1111和1，1111做减法运算，输出“0”结果如下图：六、心得体会本次实验主要是针对双向链表的练习，通过这次试验我们大家对于双向循环链表有了更深刻的记忆。

数据结构实验报告——四则运算表达式求值实验五四则运算表达式求值一．问题描述：四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。

二．基本要求：使用二叉树来实现。

三．实现提示：利用二叉树后序遍历来实现表达式的转换，同时可以使用实验二的结果来求解后缀表达式的值。

输入输出格式：输入：在字符界面上输入一个中缀表达式，回车表示结束。

输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。

测试实例：输入：21+23* （12-6 ）输出：21 23 12 6 -*+四．设计概要用二叉树表示表达式：若表达式为数或简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式信息若表达式= （第一操作数）（运算符）（第二操作数），则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符（若为一元算符，则左子树空）。

操作数本身又为表达式.后缀遍历二叉树码实现和静态检查上机调试及测试数据的调试五．源程序：#include#include#include#include#include#include#define STACK_INIT_SIZE 100#define DATA_SIZE 10#define STACKINCREMENT 10#define OK 1#define TRUE 1#define FALSE 0#define ERROR 0#define OVERFLOW -2using namespace std;typedef float SElemtype;typedef int Status;typedef char * TElemType;typedef struct BiTNode {TElemType data;int len; //data字符串中字符的个数struct BiTNode * lchild, * rchild;}BiTNode, *BiTree;typedef struct{SElemtype *base;SElemtype *top;int stacksize;} SqStack;Status IsDigital(char ch)if(ch>='0'&&ch<='9'){return 1; //是数字字母}return 0; //不是数字字母}int CrtNode(stack &PTR, char *c){BiTNode * T;int i=0;T = (BiTNode *)malloc(sizeof(BiTNode));T->data = (char *)malloc(DATA_SIZE*sizeof(char));while(IsDigital(c[i])){T->data [i] = c[i];i++;}T->len = i;T->lchild = T->rchild = NULL;PTR.push (T);return i;}void CrtSubTree(stack &PTR, char c){BiTNode * T;T = (BiTNode *)malloc(sizeof(BiTNode));T->data = (char *)malloc(DATA_SIZE*sizeof(char));T->data [0] = c;T->len = 1;T->rchild = PTR.top(); //先右子树，否则运算次序反了PTR.pop ();T->lchild = PTR.top();PTR.pop ();PTR.push (T);}char symbol[5][5]={{'>', '>', '<', '<', '>'}, //符号优先级{'>', '>', '<', '<', '>'},{'>', '>', '>', '>', '>'},{'>', '>', '>', '>', '>'},{'<', '<', '<', '<', '='}};int sym2num(char s) //返回符号对应优先级矩阵位置{switch(s){case '+': return 0; break;case '-': return 1; break;case '*': return 2; break;case '/': return 3; break;case '#': return 4; break;}}char Precede(char a, char b) //返回符号优先级{return(symbol[sym2num(a)][sym2num(b)]);void CrtExptree(BiTree &T, char exp[]){//根据字符串exp的内容构建表达式树Tstack PTR;//存放表达式树中的节点指针stack OPTR;//存放操作符char op;int i=0;OPTR.push ('#');op = OPTR.top();while( !((exp[i]=='#') && (OPTR.top()=='#')) ) //与{ if (IsDigital(exp[i])){//建立叶子节点并入栈PTRi+=CrtNode(PTR, &exp[i]);}else if (exp[i] == ' ')i++;else{switch (exp[i]){case '(': {OPTR.push (exp[i]);i++;break;}case ')': {op = OPTR.top (); OPTR.pop ();while(op!='('){CrtSubTree(PTR, op);op = OPTR.top (); OPTR.pop ();}//end whilei++;break;}default: //exp[i]是+ - * /while(! OPTR.empty ()){op = OPTR.top ();if (Precede(op, exp[i])=='>'){CrtSubTree(PTR, op);OPTR.pop ();}if(exp[i]!='#'){OPTR.push (exp[i]);i++;}break;}}//end switch}//end else}//end whileT = PTR.top();PTR.pop ();}void PostOrderTraverse(BiTree &T, char * exp ,int &count){//后序遍历表达式树T，获取树中每个结点的数据值生成逆波兰表达式exp //T是表达式树的根节点；字符串exp保存逆波兰表达式；count保存exp中字符的个数//后序遍历中，处理根结点时，依据T->len的值，把T->data中的字符依次添加到当前exp字符串的尾端//添加完T->data后，再添加一个空格字符，同时更新count计数器的值。

数据结构课内实验报告书一、实验题目：长整数四则运算二、实验目的：通过本次实验，熟练掌握链表的存储结构及其各种基本运算，体会链表操作的特点。

三、实验要求：设计一个实现任意长的整数进行加法运算的演示程序。

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

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

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

四、测试数据：（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）存储结构的定义typedef struct int72 {int i[4];} INT72;INT72 a,b,c;typedef struct LinkNode{int data; //记录每个节点的整数（小于10000）LinkNode *next, *pre; //记录下一个节点的地址 *pre; //记录前一个节点的地址}linklist;（2）主要算法的描述void addtwo()//节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的//默认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->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)*m2+s; //两整数相加if((m1*m2)>0) //如果符号相同{if(abs(currptr->data)-10000>=0) //相加后超过10000，则进位{s=currptr->data/10000;currptr->data=abs(currptr->data)%10000;}else //abs(currptr->data)-10000<0，不进位{s=0;currptr->data=abs(currptr->data);}}else if(m1>0&&m2<0)//符号不同，在此相当于实现两个正整数相减{s=0;if(currptr->data<0) //小于0，向前一位借1{currptr->data+=10000;s=-1;}}else if(m1<0&&m2>0)//符号不同，在此相当于实现负整数加上正整数{s=0;if(currptr->data>0) //大于0，{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){currptr=(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(m1>0&&m2<0){s=0;if(currptr->data<0){currptr->data+=10000;s=-1;}}else if(m1<0&&m2>0){s=0;if(currptr->data>0){currptr->data=10000-currptr->data;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;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);}}六、技巧与体会在编写程序中尽量做到独立完成、对于自己想要完成的问题要主动编程完成、这样自己是一个很大的提升、也能学到很多的知识、熟练编程！以后要加强动手时间能力、多与同学交流算法精髓！。

一试验目的和要求1. 实验目的了解线性表的逻辑结构特性，熟练掌握线性表的链式存储结构，熟练掌握线性表在链式存储结构上实现基本操作：查找，插入，删除的算法。

能在实际应用中选用适合的链表结构。

加深对链表的本质了解。

2. 实验要求利用双向链表实现长整数的存储，每个结点含一个整型变量。

设计一个实现任意长的整数进行四则运算的演示程序。

二实验环境萨大苏打sdasd本程序可以在98/2000/XP下运行,可以用VC++6.0执行三程序的逻辑框图四, 程序源代码/*list.h*/#include<malloc.h>#include<process.h>#include<stdlib.h>#include<stdio.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASLBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct DuLNode{ElemType data;struct DuLNode *prior,*next;}DuLNode,*DuLinkList;//构造一个空的双向循环线性表，L为头结点Status InitList_DuL(DuLinkList &L);//在L中确定第i个元素的位置指针pDuLinkList GetElemP_DuL(DuLinkList L,int i);//在带头结点的双链循环线性表L中第i个位置之前插入元素e ,//i的合法值为1<=i<=ListLength_DuL(L)+1Status ListInsert_DuL(DuLinkList &L,int i,ElemType e);//删除带头结点的双链循环线性表L中第i个元素，i的合法值为1<=i<=ListLength_DuL(L) Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e);//若L为空表，则返回TRUE,否则返回FALSEbool ListEmpty_DuL(DuLinkList L);//线性表L已存在，返回L中数据元素个数Status ListLength_DuL(DuLinkList L);//若线性表L已存在，将L置为空表Status ClearList_DuL(DuLinkList &L);//销毁线性表LStatus DestroyList_DuL(DuLinkList &L);//用e返回L中第i个数据元素的值void GetElem_DuL(DuLinkList L,int i,ElemType &e);//返回双向循环链表L中e出现的次数int Counter_DuL(DuLinkList L,ElemType e);//返回第n个e的在链表中位置n的合法值为0<=n<=Counter_DuL( L,n)int Position_DuL(DuLinkList L,int n,ElemType e);/*function.cpp*/#include"list.h"/****************************************************************************** ********************//****************************函数声明**************************************************************//****************************************************************************** ********************/DuLinkList calculate(DuLinkList p,int*j,char *f,int *num,int k); void output(DuLinkList r);DuLinkList Pack_Up(DuLinkList r); //整理链表rvoid exchange(DuLinkList &L,int &j);DuLinkList read_r();void operate(DuLinkList p);void decride_d();int counter(int a); //计算整数位数int max(int *num,int k); //返回最大值/*list.cpp*/#include"list.h"Status InitList_DuL(DuLinkList &L){//构造一个空的双向循环线性表，L为头结点L=(DuLinkList)malloc(sizeof(DuLNode));if(!L)exit(OVERFLOW);L->next=L;L->prior=L;return OK;}//InitList_DuLDuLinkList GetElemP_DuL(DuLinkList L,int i){//在L中确定第i个元素的位置指针pDuLinkList p;p=L;for(int j=0;j<i;j++)p=p->next;return (p);}//GetElemP_DuLStatus ListInsert_DuL(DuLinkList &L,int i,ElemType e){//在带头结点的双链循环线性表L中第i个位置之后插入元素e ,//i的合法值为0<=iDuLinkList s,p;if(i<0)return OVERFLOW;else{p=GetElemP_DuL(L,i);if(!(p))return ERROR;s=(DuLinkList)malloc(sizeof(DuLNode));if(!s)return ERROR;s->data=e;s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;return OK;}}//ListInsert_DuLStatus ListDelete_DuL(DuLinkList &L,int i,ElemType &e){//删除带头结点的双链循环线性表L中第i个元素，i的合法值为1<=i<=ListLength_DuL(L)DuLinkList p;if(!(p=GetElemP_DuL(L,i))||p==L)return ERROR;e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);return OK;}//ListDelete_DuLbool ListEmpty_DuL(DuLinkList L){//若L为空表，则返回TRUE,否则返回FALSEif(L->prior==L->next)return TRUE;else return FALSE;}//listElemty_DuLStatus ListLength_DuL(DuLinkList L){//线性表L已存在，返回L中数据元素个数int i=0;DuLinkList p=NULL;for(p=L;p->next!=L;p=p->next)i++;return (i);}//ListLength_DuLStatus ClearList_DuL(DuLinkList &L){//若线性表L已存在，将L置为空表ElemType e;if(!ListEmpty_DuL(L))for(int i=1;i<=ListLength_DuL(L);i++)ListDelete_DuL(L,i,e);return OK;}//ClearList_DuLStatus DestroyList_DuL(DuLinkList &L){//销毁线性表LElemType e;if(!ListEmpty_DuL(L))for(int i=1;i<=ListLength_DuL(L);i++)ListDelete_DuL(L,i,e);free(L);return OK;}//DestroyList_DuLvoid GetElem_DuL(DuLinkList L,int i,ElemType &e){//用e返回L中第i个数据元素的值if(i<0||i>ListLength_DuL(L))printf("The Function GetElem_Sq() found Nothing in this position\n");elsee=GetElemP_DuL(L,i)->data;}//GetElem_DuLint Counter_DuL(DuLinkList L,ElemType e){//返回双向循环链表L中e出现的次数int i;DuLinkList p=NULL;for(i=0,p=L;p->next!=L;p=p->next)if(p->data==e)i++;return i+1;}//Counter_DuLint Position_DuL(DuLinkList L,int n,ElemType e){//返回第n个e的在链表中位置n的合法值为0<n<=Counter_DuL( L,n) int i,j;DuLinkList p=NULL;if(n<1||n>Counter_DuL(L,e))return OVERFLOW;else{for(i=0,j=0,p=L->next;p!=L;p=p->next){j++;if(p->data==';')i++;if(i==n)break;}return (j);}//else}//Position_DuL/*decride.cpp*/#include<stdio.h>void decride_d(){printf("*************************************************************\n");printf("*注意!! 请严格按照国家对于长整数的表示习惯: \n");printf("*即每四位一组;组间用\',\'隔开\';\'每个数以\";\"结束\n");printf("*否则可能导致系统运行出错!!! \n");printf("**************************************************************\n");printf("输入N:退出,按任意键继续,回车进行计算!\n");printf("**************************************************************\n"); }/*ExChange.cpp*/#include"function.h"#include<math.h>void exchange(DuLinkList &L,int &j){int i=0,sum=0;DuLinkList t;ElemType e;for(i=j,sum=0;i>0;i--){t=GetElemP_DuL(L,ListLength_DuL(L));sum+=((int)t->data-48)*(int)pow(10.0,(double)(j-i));ListDelete_DuL(L,ListLength_DuL(L),e);}ListInsert_DuL(L,ListLength_DuL(L),sum);j=0;}//exchange/*Operration.cpp*/#include"function.h"/****************************************************************************** ********************//****************************操作函数operate(DuLinkList )******************************************//****************************************************************************** ********************/void operate(DuLinkList p){DuLinkList q;int k=0,i=0,n=0;k=Counter_DuL(p,';');int *j=(int *)malloc(k*sizeof(int));char *f=(char *)malloc(k*sizeof(char));int *num=(int *)malloc(k*sizeof(int));for(i=0;i<k;) //分号的位置j[i-1]=Position_DuL(p,++i,';');if(p->next->data=='-')f[0]='-'; //判断正负数else f[0]='+';for(i=1;i<k;i++){if(GetElemP_DuL(p,j[i-1])->next->data=='-')f[i]='-';else f[i]='+';}for(q=p,i=0;i<k;i++){n=0;q=q->next;for(;q!=GetElemP_DuL(p,j[i]);q=q->next)if(q->data==',')n++;num[i]=n+1;}output(Pack_Up(calculate(p,j,f,num,k)));free(j);free(f);free(num);DestroyList_DuL(p);}//operate/*------------------------------------------------------------------------------------------------------*/ DuLinkList calculate(DuLinkList p,int*j,char *f,int *num,int k) //计算{DuLinkList r;int sum=0,i=0,t=0,m=0,ma=0,JW=0;InitList_DuL(r);for(JW=0,m=0,ma=max(num,k);m<=ma;m++){for(i=0,sum=0;i<k;i++){if(num[i]<=0);else{t=(f[i]=='-'?-1:1);if(GetElemP_DuL(p,j[i]-1)->data==',')j[i]-=1;sum+=t*GetElemP_DuL(p,j[i]-1)->data;num[i]--;}}//forfor(i=i-1;i>=0;i--)j[i]-=1;if((sum+JW)<10000&&(sum+JW)>-10000){ListInsert_DuL(r,0,sum+JW);JW=0;}else {ListInsert_DuL(r,0,(sum+JW)%10000);JW=(sum+JW)/10000;} }//for}//calculate/*------------------------------------------------------------------------------------------------------*/ DuLinkList Pack_Up(DuLinkList r) //整理链表r {ElemType e;int i=0;for(i=1;i<ListLength_DuL(r);i++){if(GetElemP_DuL(r,1)->data==0)ListDelete_DuL(r,1,e);else break;}//for 清零。