双向循环链表实现任意长度整数加法
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<iostream>
#include<malloc.h>
#define LEN sizeof(struct Sqlist)
using namespace std;
int aaa[10000000];
int pp = 0;
typedef struct Sqlist
{
int data,num;//data值存储长整数的符号,1为正,-1为负,0代表长整数为0;num值存储除头节点节点的个数
struct Sqlist* pro,* next;
}Sqlist;
struct Sqlist* creat()//生成链表
{
struct Sqlist* head;
head = (struct Sqlist*)malloc(LEN);
if (head == NULL)
printf("无法分配内存\n");
else
{
head->data = 0;
head->num = 0;
head->pro = head;
head->next = head;
}
return(head);
}
void print(struct Sqlist* head)
{
struct Sqlist* p;
p = head;
if (head->next == head)
printf("longint error!\n");
else
{
if (head->data == -1)
printf("-");
p = head->next;
printf("%d", p->data);
p = p->next;
while (p != head)
{
if (p->data >= 0 && p->data < 10)
printf("000%d", p->data);
if (p->data >= 10 && p->data < 100)
printf("00%d", p->data);
if (p->data >= 100 && p->data < 1000)
printf("0%d", p->data);
if (p->data >= 1000)
printf("%d", p->data);
p = p->next;
}
printf("\n");
}
}
void insert(struct Sqlist* head, struct Sqlist* p)
{
p->next = head->next;
head->next->pro = p;
head->next = p;
p->pro = head;
head->num = head->num + 1;
}
void del(struct Sqlist* head, struct Sqlist* p)
{
head->next = p->next;
p->next->pro = head;
free(p);
head->num = head->num - 1;
}
struct Sqlist* get(char s[])
{
struct Sqlist* head, * q;
int i, j, l = 0;
head = creat();
if (s[0] > '0')
head->data = 1;
if (s[0] == '0')
head->data = 0;
if (s[0] == '-')
{
l = 1;
head->data = -1;
}
j = strlen(s) - 1;
for (i = l; i <= j; i++)
s[i] = s[i] - '0';
while (j - l >= 3)
{
q = (struct Sqlist*)malloc(LEN);
q->data = s[j] + s[j - 1] * 10 + s[j - 2] * 100 + s[j - 3] * 1000;
insert(head, q);
j = j - 4;
}
if (j >= l)
{
q = (struct Sqlist*)malloc(LEN);
q->data = 0;
while (l <= j)
{
q->data = q->data * 10 + s[l];
l++;
}
insert(head, q);
}
return(head);
}
void add(struct Sqlist* a, struct Sqlist* b)
{
struct Sqlist* m, * n, * p, * chead, * q;
if (a->num == 0 || b->num == 0)
printf("长整数错误\n");
else
{
m = a->pro;
n = b->pro;
chead = creat();
while (m != a && n != b)
{
p = (struct Sqlist*)malloc(LEN);
p->data = a->data * m->data + b->data * n->data;
insert(chead, p);
m = m->pro;
n = n->pro;
}
while (m != a || n != b)
{
if (m == a)
{
p = (struct Sqlist*)malloc(LEN);
p->data = b->data * n->data;
n = n->pro;
insert(chead, p);
}
else if (n == b)
{
p = (struct Sqlist*)malloc(LEN);
p->data = a->data * m->data;
m = m->pro;
insert(chead, p);
}
}
p = chead->next;
chead->data = 0;
while (p != chead)
{
if (p->data > 0)
{
chead->data = 1;
break;
}
if (p->data < 0)
{
chead->data = -1;
break;
}
p = p->next;
}
p = chead->pro;
while (p != chead)
{
if (p->next != chead)
p->data = p->data * chead->data + p->next->num;
if (p->next == chead)
p->data = p->data * chead->data;
p->num = 0;
if (p->data >= 10000)
p->num = 1;
if (p->data < 0)
p->num = -1;
p->data = p->data - p->num * 10000;
p = p->pro;
}
p = chead->next;
while (p->data == 0 && p->num == 0 && p->next != chead)
{
q = p;
p = p->next;
del(chead, q);
}
if (p->num > 0)
{
q = (struct Sqlist*)malloc(LEN);
q->data = p->num;
insert(chead, q);
}
}
if (chead->next->data == 0)
chead->data = 0;
print(chead);
}
int main()
{
struct Sqlist* a, * b;
char s1[100], s2[100];
int flag;
printf("请输入数据\n");
gets(s1);
gets(s2);
a = get(s1);
b = get(s2);
cout<<"运行结果为:"<<endl;
add(a,b);
}
需要输出结果位每四位一个逗号
数据结构+大数加法