本文共 6017 字,大约阅读时间需要 20 分钟。
程序设计思路:
首先需要采用尾插法建立两个链表
在考虑大整数加法时,需要考虑数据正负的情况 因此我们对数据取绝对值进行运算 假设有两个链表List1和List2 当List1和List2都为正数时,直接进行相加计算 当List1和List2都为负数时,对绝对值进行相加计算,然后采用链表的头插法在顶端插入负号。 当List1和List2一正一负时,需要考虑两个数绝对值的大小 当List1为负数,List2为正数,且List1的绝对值大于List2,计算结果就是,List1的绝对值减去List2的绝对值,然后用头插法插入一个负号。而若List1的绝对值小于List2的绝对值,直接使用List2的绝对值减去List1绝对值即可。 当List1为正数,List2为负数时,分析同上。实现代码如下:
头文件list.h
#include#include typedef struct Node{ char val; struct node* pnext;}Node_t, *pNode_t;void HeadInsert(pNode_t* pphead, pNode_t* pptail, char val); void TailInsert(pNode_t* pphead, pNode_t* pptail, char val); void PrintNode(pNode_t phead); void ReverseNode(pNode_t* pphead); void AddCount(pNode_t phead1, pNode_t phead2, pNode_t* ppReshead, pNode_t* ppRestail); void MinusCount(pNode_t phead1, pNode_t phead2, pNode_t* ppReshead, pNode_t* ppRestail); void Add(pNode_t phead1, pNode_t phead2, pNode_t* ppReshead, pNode_t* ppRestail);int GetLength(pNode_t phead);int Compare(pNode_t phead1, pNode_t phead2);
main.c文件
#define _CRT_SECURE_NO_WARNINGS#include "list.h"#include#include int main(){ while (1) { char val; pNode_t phead1 = NULL; pNode_t ptail1 = NULL; pNode_t phead2 = NULL; pNode_t ptail2 = NULL; pNode_t pReshead = NULL; pNode_t pRestail = NULL; while (scanf("%c", &val) != EOF) { if (val == '\n') { break; } TailInsert(&phead1, &ptail1, val); } PrintNode(phead1); while (scanf("%c", &val) != EOF) { if (val == '\n') { break; } TailInsert(&phead2, &ptail2, val); } PrintNode(phead2); Add(phead1, phead2, &pReshead, &pRestail); PrintNode(pReshead); } return 0;}void HeadInsert(pNode_t* pphead, pNode_t* pptail, char val){ pNode_t pnew = (pNode_t)calloc(1, sizeof(Node_t)); pnew->val = val; if (NULL == (*pphead)) { *pphead = pnew; *pptail = pnew; } else { pnew->pnext = *pphead; *pphead = pnew; } return;}void TailInsert(pNode_t* pphead, pNode_t* pptail, char val){ pNode_t pnew = (pNode_t)calloc(1, sizeof(Node_t)); pnew->val = val; if (NULL == (*pphead)) { *pphead = pnew; *pptail = pnew; } else { (*pptail)->pnext = pnew; *pptail = pnew; } return;}void PrintNode(pNode_t phead){ if (NULL == phead) { printf("the list is empty\n"); return; } else { while (phead) { printf("%c", phead->val); phead = phead->pnext; } printf("\n"); } return;}void ReverseNode(pNode_t* pphead){ pNode_t prehead = *pphead; pNode_t curhead = (*pphead)->pnext; pNode_t afthead; prehead->pnext = NULL; while (curhead) { afthead = curhead->pnext; curhead->pnext = prehead; prehead = curhead; curhead = afthead; } (*pphead) = prehead; return;}int GetLength(pNode_t phead){ int cnt = 0; while (phead) { phead = phead->pnext; cnt++; } return cnt;}int Compare(pNode_t phead1, pNode_t phead2){ int len1 = GetLength(phead1); int len2 = GetLength(phead2); if (len1 > len2) { return 1; } else if (len2 > len1) { return -1; } else { while (phead1 && phead2) { if (phead1->val > phead2->val) { return 1; } else if (phead1->val < phead2->val) { return -1; } phead1 = phead1->pnext; phead2 = phead2->pnext; } return 0; }}void AddCount(pNode_t phead1, pNode_t phead2, pNode_t* ppReshead, pNode_t* ppRestail){ char value; int remain = 0; ReverseNode(&phead1); ReverseNode(&phead2); while (phead1 && phead2) { value = phead1->val + phead2->val + remain - '0'; if (value > '9') { value -= 10; remain = 1; } else { remain = 0; } TailInsert(ppReshead, ppRestail, value); phead1 = phead1->pnext; phead2 = phead2->pnext; } while (phead1) { value = phead1->val + remain; if (value > '9') { value -= 10; remain = 1; } else { remain = 0; } TailInsert(ppReshead, ppRestail, value); phead1 = phead1->pnext; } while (phead2) { value = phead2->val + remain; if (value > '9') { value -= 10; remain = 1; } else { remain = 0; } TailInsert(ppReshead, ppRestail, value); phead2 = phead2->pnext; } if (1 == remain) { TailInsert(ppReshead, ppRestail, '1'); } ReverseNode(ppReshead); return;}void MinusCount(pNode_t phead1, pNode_t phead2, pNode_t* ppReshead, pNode_t* ppRestail){ char value; int remain = 0; ReverseNode(&phead1); ReverseNode(&phead2); while (phead1 && phead2) { value = phead1->val - phead2->val + remain + '0'; if (value < '0') { value += 10; remain = -1; } else { remain = 0; } TailInsert(ppReshead, ppRestail, value); phead1 = phead1->pnext; phead2 = phead2->pnext; } while (phead1) { value = phead1->val + remain; if (value < '0') { value += 10; remain = -1; } else { remain = 0; } TailInsert(ppReshead, ppRestail, value); phead1 = phead1->pnext; } ReverseNode(ppReshead); while ((*ppReshead)->val == '0') { (*ppReshead) = (*ppReshead)->pnext; } return;}void Add(pNode_t phead1, pNode_t phead2, pNode_t* ppReshead, pNode_t* ppRestail){ if (phead1->val == '-' && phead2->val == '-') { AddCount(phead1->pnext, phead2->pnext, ppReshead, ppRestail); HeadInsert(ppReshead, ppRestail, '-'); } else if (phead1->val == '-') { if (Compare(phead1->pnext, phead2) > 0) { MinusCount(phead1->pnext, phead2, ppReshead, ppRestail); HeadInsert(ppReshead, ppRestail, '-'); } else if (Compare(phead1->pnext, phead2) == 0) { HeadInsert(ppReshead, ppRestail, '0'); } else { MinusCount(phead2, phead1->pnext, ppReshead, ppRestail); } } else if (phead2->val == '-') { if (Compare(phead1, phead2->pnext) > 0) { MinusCount(phead1, phead2->pnext, ppReshead, ppRestail); HeadInsert(ppReshead, ppRestail, '-'); } else if (Compare(phead2->pnext, phead1) == 0) { HeadInsert(ppReshead, ppRestail, '0'); } else { MinusCount(phead2->pnext, phead1, ppReshead, ppRestail); HeadInsert(ppReshead, ppRestail, '-'); } } else { AddCount(phead1, phead2, ppReshead, ppRestail); } return;}
转载地址:http://ixxmb.baihongyu.com/