数据结构课程设计长整数四则运算

数数据据结结构构课课程程设设计计 题目 长整数四则运算 计算机与通信工程学院 班级学号 学生姓名 提交日期 成 绩 长整数四则运算长整数四则运算 一一 需求分析 需求分析 问题描述 设计一个实现任意长的整数进行加法运算的演示程序 基本要求 利用双向循环链表实现长整数的存储 每个结点含一个整形变量 任何整 形变量的范围是 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 将各个位的正负 大小 进位进行调整 源程序 源程序 include include include using namespace std struct Node Node pre Node next int data void Input Node p Node t Node cur string str int tmp 1 char num cin str if str 0 p data 1 tmp 1 else p data 1 cur new Node cur data str 0 0 cur pre p cur next t t pre cur p next cur p cur for int i 1 str i 0 i if str i continue cur new Node cur data str i 0 tmp cur pre p cur next t t pre cur p next cur p cur void disply Node h Node t int l Node p p h p h next while p data 0 l while p t cout data p p next l if l 4 0 if l 0 cout pre p2 t2 pre while p1 h1 p1 p1 pre p2 p2 pre delete p2 next if p2 h2 p2 next h1 next h1 next pre p2 h1 next h2 next h2 next pre h1 if h1 next data 0 h1 data 1 else h1 data 1 int adjust Node h Node t int l 0 tmp h data Node p t pre while p h next if p data tmp 0 if p data 9 p datadata tmp 10 p pre data tmp if p data tmpdatadata 10 p data tmp 10 p pre data tmp p data tmp p data p p pre l l return l int main while 1 char symbol ch Node head1 new Node Node head2 new Node Node tail1 new Node Node tail2 new Node head1 next tail1 head1 pre NULL tail1 pre head1 tail1 next NULL head2 next tail2 head2 pre NULL tail2 pre head2 tail2 next NULL Input head1 tail1 Input head2 tail2 add head1 tail1 head2 tail2 int l adjust head1 tail1 disply head1 tail1 l 三三 调试分析调试分析 将两个链表对应位相加 再进行调整 算法的设计上还是不错的 但是遍历的次数太 多对效率有所影响 这一点应该再修改修改以提高效率 两个链表在相加的时候把结果保存到第一个链表中 同时销毁第二个链表的相对结点 这样节省了空间 在调试过程中 使用的多数是指针