1、问题描述
设计一个实现任意长的整数进行加法运算的演示程序。
基本要求:
⑴利用链表实现长整数的存储,每个结点含一个整型变量。
⑵任何整型变量的范围是-(215-1)~(215-1)。
⑶输入和输出形式按照中国对于长整数的表示习惯,每四位一组,组间用逗号隔开。如:-2345,6789,3211;
难点在于使用链表实现长整数的存储,因为任何整型变量的范围是-(215-1)~(215-1)而题中又要求每四位一组,组间用逗号隔开。故选择双向链表且每个节点中数据使用4位整数保存,考虑到加法进位选择使用字符串接收输入的长整数并从尾部开始每4位为一组存在链表中。
2、系统设计
先使用字符串接收输入的长整数,然后从尾部开始每4位为一组存在链表中,考虑到后续操作,链表选用带头指针的双向链表,将两个链表中的数据从头节点开始依次取出并相加如果有进位则使用一个int存储并在下一次加法中加入,将每次计算的数依次存入一个带头、尾指针的双向链表中,打印结果时从尾节点向前打印并加上‘,’号
3、源代码清单
main函数为主函数负责调用各个函数
该函数定义了双向链表的节点其中data用来存储数据next为指向下一节点的指针,pri为指向前一节点的指针。
create_node函数负责创造节点参数data为新建的节点内数据的值新建节点的两个指针默认为NULL。
insert_node函数负责调用create_node函数并将获得的节点链接到链表,也可以生成新链表,*head为链表的头指针data为节点的数据
inlist函数负责将字符串的数据存储到链表中并返回存储链表的头指针,参数a为需要存储的字符串
add_lists负责将两个链表相加并调用insert_node函数将结果存储在新链表中然后返回新链表的尾指针,li、l2为需要相加的链表,result为结果链表的头指针。
函数调用关系图
4、运行结果测试与分析
该结果说明运算正确,每四位用‘,’隔开正确
该结果说明结果进位正确
总代码
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include<conio.h>
#define maxn 1000
typedef struct Node
{
int data;
struct Node* next,*pri;
}Node;
Node* create_node(int data) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = data;
new_node->next = NULL;
new_node->pri = NULL;
return new_node;
}
void insert_node(Node** head, int data) {
Node* new_node = create_node(data);
if (*head == NULL) {
*head = new_node;
}
else {
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = new_node;
new_node->pri = temp;
}
}
Node* inlist(char* a) {
int ct = 0;
int sum = 0;
Node* head = NULL;
for (int i = strlen(a) - 1; i >= 0; i--)
{
if (a[i] <= '9' && a[i] >= '0')
{
(int)sum += (a[i] - '0') *pow( 10,ct);
ct++;
if (ct == 4||i==0)
{
insert_node(&head, sum);
ct = 0;
sum = 0;
}
}
}
return head;
}
Node* add_lists(Node* l1, Node* l2, Node* result) {
int carry = 0;
while (l1 != NULL || l2 != NULL)
{
int sum = carry;
if (l1 != NULL) {
sum += l1->data;
l1 = l1->next;
}
if (l2 != NULL) {
sum += l2->data;
l2 = l2->next;
}
carry = sum / 10000;
sum = sum % 10000;
insert_node(&result, sum);
}
if (carry > 0) {
insert_node(&result, carry);
}
Node* xhead = result;
while (xhead) {
xhead = xhead->next;
if(!xhead->next)
{
return xhead;
}
}
}
int main()
{
char a[maxn], b[maxn];
printf("输入第一个长整数\n");
gets(a);
printf("输入第二个长整数\n");
gets(b);
Node* ahead = inlist(a);
Node* bhead = inlist(b);
Node* newhead = NULL;
Node* newtail = NULL;
newtail=add_lists(ahead, bhead, newhead);
printf("结果:");
while (newtail)
{
printf("%d,", newtail->data);
newtail = newtail->pri;
if (!newtail->pri) {
printf("%d", newtail->data);
break;
}
}
return 0;
}