【数据结构实验】用链表实现两个大整数的相加减 |
您所在的位置：网站首页 › 两个表数值相减 › 【数据结构实验】用链表实现两个大整数的相加减 |
|
一、实验内容
【问题描述】 设计一个实现任意长的整数进行加法运算的演示程序 。 【基本要求】 利用双向链表实现长整数的存储，每个结点含一个整形变量。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。 【测试数据】 （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”。 二、实验目的熟悉掌握链表的基本操作。 三、算法分析说明与代码编写指导本例的代码不是实现大整数加减的最快方法，本实验的最主要目的是让同学们熟悉链表的常见用法。 通过双向链表建立节点表示大整数，每4个数位分一节，所以一个节点保存4位数。读取时，从低位往高位开始读取。计算时，也从低位往高位开始计算。输出则从高位往低位输出，每两个节点之间补一个逗号即可。计算过程模拟列竖式手算的过程，当两个数都是非负数时，直接相加。当两个数都是负数时，将绝对值相加然后添加负号；当两个数只有一个是负数时，比较绝对值，然后按照大数减小数的方法计算绝对值的差，当绝对值大的数为负时，补充负号。本程序对输入具有一定容错性，会自动删除高位的0，输入的时候允许用逗号分节，在最高位到最低位以内的任何间位分节均可。程序是循环运行的，如果需要终止，直接按×退出。 代码： #include #include #include #pragma warning(disable:4996) struct bigintnode { //大整数结构体的每一个节点 short data = 0; bigintnode* prev = nullptr, * next = nullptr; bigintnode() { data = 0, prev = nullptr, next = nullptr; } }; struct bigint { //大整数结构体 bigintnode* tail = nullptr, * head = nullptr; bigint() { tail = new(bigintnode), head = tail; } }; //s存储输入内容，u标记读取位置，n用于读取并保存数据，d为每一节（4位分一节）已经读取的位数。cmpres储存比较绝对值的结果。a>b、a=b、a bigintnode* p = a.tail, * q; while (p->prev != nullptr) { q = p, p = p->prev, delete q; }//将大整数a置零 a.tail = p, p->data = 0, p->next = nullptr; for (--pos; s[pos] != ' ' && s[pos] != '-'; --pos) { if (s[pos] == ',')continue; n = n + e[d] * (s[pos] - 48), ++d;//从低位到高位依次读取数字，e[d]代表10的d次方。 if (d == 4) { p->data = n; p->prev = new(bigintnode); a.head = p->prev; p->prev->next = p; p = p->prev; n = 0, d = 0; }//读取完一节，存储到大整数a中，开一个新的节点用于后续存储高位数字。 } if (n != 0) { p->data = n; p->prev = new(bigintnode); a.head = p->prev; p->prev->next = p; p = p- |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |