单链表实现十进制大整数运算。

发布网友 发布时间：2023-11-06 12:18

我来回答

共2个回答

热心网友 时间：2024-10-21 09:59

//
// File name : Main.cpp
//
// Code by : jiangyonghang
//
// Project name : SingleLinkedListAddMinus
//
// Create datetime: 2011-07-10 06:53:10
//

// Tested or implemented header
// ...

// C system headers
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#pragma warning(disable:4996)

// C++ system headers
// ...

// Headers from other projects
// ...

// Headers of current project
// ...

typedef struct DigitNode
{
int num;
struct DigitNode *higher_one;
}DigitNode;

typedef struct ListNumber
{
DigitNode *list;
unsigned int len;
int positive;
}ListNumber;

void InitNumber(ListNumber *number);
void ClearNumber(ListNumber *number);
int GetHighestDigit(ListNumber number);
void RemoveHighestDigit(ListNumber *number);
int NotLessThan(ListNumber first, ListNumber second);

ListNumber ReadNumber();
char ReadOperator();
int Input(ListNumber *first, char *operator_char, ListNumber *second);
void AppendAsSmallEnd(ListNumber *number, int new_digit);
void AppendAsBigEnd(ListNumber *number, int new_digit);

ListNumber Calculate(ListNumber first, char operator_char, ListNumber second);
ListNumber Add(ListNumber first, ListNumber second);
ListNumber Minus(ListNumber first, ListNumber second);
void PrintResult(ListNumber result);

int main()
{
ListNumber first_number;
ListNumber second_number;
ListNumber result;
char operator_char = '\0';

int ret_code = false;
InitNumber(&first_number);
InitNumber(&second_number);
InitNumber(&result);

while (1)
{
ret_code = Input(&first_number, &operator_char, &second_number);
if (ret_code)
{
result = Calculate(first_number, operator_char, second_number);
if (result.list)
{
printf("Calculation is done.\n");
PrintResult(result);
}
else
{
printf("Calculation is failed.\n");
break;
}
}
else
{
printf("Input is failed.\n");
break;
}

ClearNumber(&first_number);
ClearNumber(&second_number);
ClearNumber(&result);
}

return 0;
}

void InitNumber(ListNumber *number)
{
if (number)
{
number->len = 0;
number->list = NULL;
number->positive = true;
}
return;
}

void ClearNumber(ListNumber *number)
{
DigitNode *now = NULL;
if (!number)
return;

now = number->list;
while (now)
{
DigitNode *next = now->higher_one;
free(now);
now = NULL;
now = next;
}

number->list = NULL;
number->len = 0;
number->positive = true;
return;
}

int GetHighestDigit(ListNumber number)
{
const DigitNode *kNow = number.list;
if (0 == number.len)
return 0;

while (kNow->higher_one)
kNow = kNow->higher_one;

return kNow->num;
}

void RemoveHighestDigit(ListNumber *number)
{
DigitNode *now_top = number->list;
if (number->len <= 0)
return;

if (1 == number->len)
{
free(number->list);
number->len = 0;
number->positive = true;
}

while (now_top->higher_one->higher_one)
{
now_top = now_top->higher_one;
}
free(now_top->higher_one);
now_top->higher_one = NULL;
number->len--;

return;
}

int NotLessThan(ListNumber first, ListNumber second)
{
const DigitNode *kFirstHighestDigit = first.list;
const DigitNode *kSecondHighestDigit = second.list;

if (first.len > second.len)
return true;
if (first.len < second.len)
return false;
if (0 == first.len)
return true;
while (kFirstHighestDigit || kSecondHighestDigit)
{
if (GetHighestDigit(first) != GetHighestDigit(second) )
return GetHighestDigit(first) > GetHighestDigit(second);
kFirstHighestDigit = kFirstHighestDigit->higher_one;
kSecondHighestDigit = kSecondHighestDigit->higher_one;
}

return 0;
}

ListNumber ReadNumber()
{
ListNumber result;
DigitNode *new_digit = NULL;
char temp = '\0';

InitNumber(&result);

while (1)
{
if (scanf("%c", &temp) != 1)
break;

if (!isdigit(temp) )
{
if (result.list)
{
break;
}
else
{
continue;
}
}

AppendAsSmallEnd(&result, temp - '0');
}

return result;
}

char ReadOperator()
{
char temp;
while (1)
{
temp = getchar();
if (
(' ' == temp) ||
('\t' == temp) ||
('\r' == temp) ||
('\n' == temp)
)
continue;
break;
}
return temp;
}

int Input(ListNumber *first, char *operator_char, ListNumber *second)
{
ClearNumber(first);
*operator_char = 0;
ClearNumber(second);

*first = ReadNumber();
if (!first->list)
return false;

*operator_char = ReadOperator();
if (
(*operator_char != '+') &&
(*operator_char != '-')
)
return false;

*second = ReadNumber();
if (!second->list)
return false;

return true;
}

void AppendAsSmallEnd(ListNumber *number, int new_digit)
{
if (number)
{
DigitNode *new_node = (DigitNode*)malloc(sizeof(DigitNode) );
if (new_node)
{
new_node->num = new_digit;
new_node->higher_one = number->list;
number->list = new_node;
number->len++;
}
}

return;
}

void AppendAsBigEnd(ListNumber *number, int new_digit)
{
if (number)
{
if (0 == number->len)
{
AppendAsSmallEnd(number, new_digit);
}
else
{
DigitNode *add_position = number->list;
while (add_position->higher_one)
add_position = add_position->higher_one;

add_position->higher_one = (DigitNode*)malloc(sizeof(DigitNode) );
if (add_position->higher_one)
{
add_position->higher_one->num = new_digit;
add_position->higher_one->higher_one = NULL;
number->len++;
}
}
}

return;
}

ListNumber Calculate(ListNumber first, char operator_char, ListNumber second)
{
ListNumber result;

InitNumber(&result);

if ('+' == operator_char)
result = Add(first, second);
else if ('-' == operator_char)
result = Minus(first, second);

while (0 == GetHighestDigit(result) )
{
if (result.len > 1)
{
RemoveHighestDigit(&result);
}
else
{
break;
}
}

return result;
}

ListNumber Add(ListNumber first, ListNumber second)
{
ListNumber result;
int upper_left = 0;

const DigitNode *kFirstDigit = first.list;
const DigitNode *kSecondDigit = second.list;

InitNumber(&result);

while (kFirstDigit || kSecondDigit || upper_left)
{
if (kFirstDigit)
{
upper_left += kFirstDigit->num;
kFirstDigit = kFirstDigit->higher_one;
}
if (kSecondDigit)
{
upper_left += kSecondDigit->num;
kSecondDigit = kSecondDigit->higher_one;
}

AppendAsBigEnd(&result, upper_left % 10);

upper_left /= 10;
}

return result;
}

ListNumber Minus(ListNumber first, ListNumber second)
{
ListNumber result;
int minus_mark = 0;
const DigitNode *kFirstNode = NULL;
const DigitNode *kSecondNode = NULL;

InitNumber(&result);

if (!NotLessThan(first, second) )
{
ListNumber temp = first;
first = second;
second = temp;
result.positive = false;
}

kFirstNode = first.list;
kSecondNode = second.list;

while (kFirstNode)
{
int first_digit = 0;
int second_digit = 0;
if (kFirstNode)
first_digit = kFirstNode->num;
if (kSecondNode)
second_digit = kSecondNode->num;
if (first_digit - minus_mark >= second_digit)
{
AppendAsBigEnd(&result, first_digit - minus_mark - second_digit);
minus_mark = 0;
}
else
{
AppendAsBigEnd(&result, first_digit - minus_mark + 10 - second_digit);
minus_mark = 1;
}
kFirstNode = kFirstNode->higher_one;
if (kSecondNode)
kSecondNode = kSecondNode->higher_one;
}

return result;
}

void PrintResult(ListNumber result)
{
char *output = (char*)malloc((result.len + 1) * sizeof(char) );
int i = 0;
const DigitNode *kNow = NULL;
if (!result.positive)
putchar('-');

i = result.len;
output[i] = '\0';
kNow = result.list;
i--;
for (; i >= 0; i--)
{
if (!kNow)
{
break;
}

output[i] = '0' + kNow->num;
kNow = kNow->higher_one;
}

if (i < 0)
puts(output);
else
puts("Print failed!");
free(output);
return;
}

需要注释的话请追问……注释太多未必好懂追问给注释吧

追答注释太多超过百度*了
已将答案发布到我空间“软件发布”分类

热心网友 时间：2024-10-21 09:59

#include <stdio.h>
#include <string.h>
int main()
{
char s[150];
int i,sum[600],b[600],lenth,j,c,t;
memset(sum,0,sizeof(sum)); //把sum[i]所有的位全部置为0..能看懂不?~~
scanf("%s",s); //输入字符串1
lenth=strlen(s);
i=500;
j=lenth-1;
memset(b,0,sizeof(b));
while(j>=0)
b[i--]=s[j--]-'0';//把字符转变成数字.最后一个字符在i=500位置.倒数第二个在i=499,依此类推.存在b[i]中
i=500;
c=0;
while(i!=100) //实现b[i]跟sum[i]个对个相加.进位啥啥啥的...从最后往前加.因为要对齐嘛.
{
t=sum[i]+b[i]+c;
sum[i]=t%10;
c=t/10;
i--;
}
scanf("%s",s);//第二个字符串.操作跟上面一样的.
lenth=strlen(s);
i=500;
j=lenth-1;
memset(b,0,sizeof(b));
while(j>=0)
b[i--]=s[j--]-'0';
i=500;
c=0;
while(i!=100)
{
t=sum[i]+b[i]+c;
sum[i]=t%10;
c=t/10;
i--;
}
i=1;
while(sum[i]==0) //前面多余的0不输出.
i++;
while(i<=500)
printf("%d",sum[i++]); //从不为0处往后一直输出.
printf("\n");
return 0;
}追问哥你这是单链表吗？而且只有加法没有减法。

追答晕..写得兴起,不知所以了.呵呵.
单链表的话应该可以把对应的数组 a[i]改成*(a+i);这个倒是容易..减法的话,还要改代码......累了~~~~~写了好久,等有心人帮忙改下罗.呵呵.