采用循环双向链表, 能实现多个长整型进行加法运算
/*
* 文件名: 1_2.c
* 实验环境: Turbo C 2.0
* 完成时间: 2003年2月17日
*--------------------------------------------------------------------
* 改进说明: 采用循环双向链表, 能实现多个长整型进行加法运算.
*/
#include <math.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define OPERAND_NUM 2
#define POSITIVE 1
#define NEGATIVE 0
typedef int ElemType;
typedef int status;
typedef struct NodeType
{
ElemType data;
struct NodeType *prior;
struct NodeType *next;
} NodeType, *LinkType;
status CreateOpHeadBuff(LinkType **, int);
status CreateOperandList(LinkType *, int);
void CreateResultList(LinkType *, LinkType *, int);
status DeleteZero(LinkType *);
status PushDataToList(LinkType *, int, int);
status AppendNodeToList(LinkType *, LinkType);
LinkType ComputePNList(LinkType, LinkType, int);
LinkType ComputePPNNList(LinkType, LinkType, int);
status MakeNode(LinkType *, ElemType);
status PrintList(LinkType);
status ClearMemory(LinkType *, int);
status DeleteList(LinkType);
status ErrorProcess(char[], int);
int main(void)
{
int iCounter,
iOpNum = 2;/* 操作数的个数, 默认为2 */
char strNum[10], cOrder[5];
LinkType ResultList = NULL, /* 结果链表的头指针 */
*ListHeadBuff = NULL; /* 指向操作数头指针缓冲 */
do
{
printf("请输入需要的操作数的个数, 注意至少为2: ");
gets(strNum);
iOpNum = atoi(strNum);
} while (iOpNum < 2);
/* 构造操作数链表的头指针缓冲区 */
CreateOpHeadBuff(&ListHeadBuff, iOpNum);
/* 提示用户输入数据,并构造操作数链表 */
while (!CreateOperandList(ListHeadBuff, iOpNum))
{
printf("\n出现非法输入, 需要退出吗?\n");
printf("键入Y则退出, 键入N重新输入(Y/N):");
gets(cOrder);
if (cOrder[0] == 'Y' || cOrder[0] == 'y')
{
ClearMemory(ListHeadBuff, iOpNum);
return 0;
}
}
printf("打印输入情况:\n");
for (iCounter = 0; iCounter < iOpNum; iCounter++)
{
printf("- - - 第%d个操作数 - - -\n", iCounter + 1);
DeleteZero(ListHeadBuff + iCounter);
PrintList(*(ListHeadBuff + iCounter));
}
/* 相加所有操作数链表的结果，并存放在ResultList中*/
CreateResultList(&ResultList, ListHeadBuff, iOpNum);
printf("打印结果:\n");
PrintList(ResultList);
ClearMemory(ListHeadBuff, iOpNum);
DeleteList(ResultList);
printf("运算完毕!");
getch();
return 0;
}
status CreateOpHeadBuff(LinkType **pBuff, int size)
{
int iCounter;
*pBuff = (LinkType *)malloc(sizeof(LinkType) * size);
if (!*pBuff)
{
printf("Error, the memory is overflow!\n");
return FALSE;
}
for (iCounter = 0; iCounter < size; iCounter++)
*(*pBuff + iCounter) = NULL;
return TRUE;
}
status CreateOperandList(LinkType *headBuff, int iOpNum)
{
int iCounter = 0, iTemp = 0,
iNodeNum = 0, /* 记录每一个操作数链表中加入的操作数个数 */
iSign = POSITIVE; /* 标识操作数的正(1)负(0)，初始为正的 */
char strScrNum[150], /* 用户输入的所有操作数字符 */
*cpCurr, /* 当前操作数字符尾 */
*cpCurrNum, /* 当前操作数字符头 */
strTsl[7]; /* 准备转换的操作数字符 */
LinkType NewNode;
printf("请输入所有操作数\n");
printf("例如输入3个操作数: \n\
1111, 2222; -3333, 4444; -3333, 9999, 0202;\n: ");
gets(strScrNum);
/* 检测输入正确性 */
if (!ErrorProcess(strScrNum, iOpNum)) return FALSE;
for (cpCurr = cpCurrNum = strScrNum; *cpCurr != '\0'; cpCurr++)
{
if (*cpCurr == ',' || *cpCurr == ';')
{
if (*(cpCurr + 1) == '\0') cpCurr++;
strncpy(strTsl, cpCurrNum, cpCurr - cpCurrNum);
strTsl[cpCurr - cpCurrNum] = '\0';
iTemp = atol(strTsl);
/* 异常处理,如strTsl=="-3333","10000" */
if (0 > iTemp || iTemp > 9999)
{
printf("\n出现非法输入 2!\n");
return FALSE;
}
/* 为操作数链表加入结点 */
MakeNode(&NewNode, iTemp);
AppendNodeToList(headBuff + iCounter, NewNode);
iNodeNum++; /* 当前链表已经加入的一个结点 */
if (*cpCurr == ';')
{
/* 将控制结点插在链表头 */
PushDataToList(headBuff + iCounter, iNodeNum, iSign);
iNodeNum = 0; /* 逻辑结点个数初始化为0 */
iSign = POSITIVE; /* 符号标识默认为正的 */
if ((iCounter + 1) < iOpNum)
iCounter++; /* 标识下一个链表头指针 */
}
cpCurrNum = cpCurr + 1;
}
else if (*cpCurr == '-')
{
iSign = NEGATIVE; /* 符号标识改为负的 */
cpCurr++;
cpCurrNum = cpCurr;
}
else if (*cpCurr == '+');
/* 读完后停止构造操作数链表 */
if (*cpCurr == '\0')
{
PushDataToList(headBuff + iCounter, iNodeNum, iSign);
break;
}
} /* end for */
return TRUE;
}
/*
* 正正,结果为正的.
* 负负,结果为负的.
* 长正短负,结果为正的.
* 长负短正,要变为长正短负,结果为负的.
* 异号时同样长
* 注意要删除每次算出的中间链表，最后传回Result
*/
void CreateResultList(LinkType *ResultHead,
LinkType *headBuff, int iOpNum)
{
int iCounter, iSign;
LinkType ResultList = NULL, TempList, CurrNode_1, CurrNode_2;
for (ResultList = *headBuff, iCounter = 1;
iCounter < iOpNum; iCounter++)
{
TempList = ResultList;
if (ResultList->data > 0 &&
(*(headBuff + iCounter))->data > 0)/* 正正,结果为正的 */
ResultList = ComputePPNNList(
TempList, *(headBuff + iCounter), POSITIVE);
else if (ResultList->data < 0 &&
(*(headBuff + iCounter))->data < 0)/* 负负,结果为负的 */
ResultList = ComputePPNNList(
TempList, *(headBuff + iCounter), NEGATIVE);
else
{
if (ResultList->data + (*(headBuff + iCounter))->data == 0)
{ /* 异号时同样长 */
CurrNode_1 = ResultList;
CurrNode_2 = *(headBuff + iCounter);
do
{ /* 直到找到第一个不等值的结点 */
if (CurrNode_1->data > CurrNode_2->data)
{
iSign = (ResultList->data > 0) ?
POSITIVE : NEGATIVE;
ResultList = ComputePNList(
TempList, *(headBuff + iCounter), iSign);
break;
}
else if (CurrNode_1->data < CurrNode_2->data)
{
iSign = ((*(headBuff + iCounter))->data > 0) ?
POSITIVE : NEGATIVE;
ResultList = ComputePNList(
*(headBuff + iCounter), TempList, iSign);
break;
}
CurrNode_1 = CurrNode_1->next;
CurrNode_2 = CurrNode_2->next;
} while (CurrNode_1 != ResultList);
}
else if (fabs(ResultList->data) >
fabs((*(headBuff + iCounter))->data))
{
iSign = (ResultList->data > 0) ? POSITIVE : NEGATIVE;
ResultList = ComputePNList(
TempList, *(headBuff + iCounter), iSign);
}
else if (fabs(ResultList->data) <
fabs((*(headBuff + iCounter))->data))
{
iSign = ((*(headBuff + iCounter))->data > 0) ?
POSITIVE : NEGATIVE;
ResultList = ComputePNList(
*(headBuff + iCounter), TempList, iSign);
}
}
if (*headBuff > TempList || TempList > *(headBuff + iCounter))
DeleteList(TempList); /* 清除上次的中间链表 */
/* 删除多出的0,如删除0000,0010,3333中的0000为0010,3333*/
DeleteZero(&ResultList);
}
*ResultHead = ResultList;
}
/*
* 每次只处理两个操作数链表,符号相异时List_1为正的, List_2为负的
* 如果两个操作数链表不一样长则List_1为长的结果链表的结构和操作
* 数链表一样, 最后返回结果链表
*/
LinkType ComputePNList(LinkType List_1, LinkType List_2, int iSign)
{
int iResult = 0, iBorrow = 0, iResultNodeNum = 0;
LinkType CurrNodeArray[2],
NewNode = NULL, ResultList = NULL;
/* 初始为每一个操作数链表的尾结点地址 */
CurrNodeArray[0] = (List_1)->prior;
CurrNodeArray[1] = (List_2)->prior;
while ((CurrNodeArray[0] != List_1)
|| (CurrNodeArray[1] != List_2))
{
if (iBorrow < 0) /* 处理前一位的借位 */
if (CurrNodeArray[0]->data > 0)
{
iBorrow = 0;
iResult = -1;
}
else if (CurrNodeArray[0]->data == 0)
{
iBorrow = -1; /* 继续向高位借1位 */
iResult = 9999;
}
if ((CurrNodeArray[0] != List_1)
&& (CurrNodeArray[1] != List_2))
{
if ((CurrNodeArray[0]->data < CurrNodeArray[1]->data)
&& iBorrow == 0)
{
iBorrow = -1; /* 不够减则向高位借1位 */
iResult += 10000;
}
iResult += CurrNodeArray[0]->data -
CurrNodeArray[1]->data;
CurrNodeArray[0] = CurrNodeArray[0]->prior;
CurrNodeArray[1] = CurrNodeArray[1]->prior;
}
else if (List_1 != CurrNodeArray[0]) /* 处理剩下的链表 */
{
iResult += CurrNodeArray[0]->data;
CurrNodeArray[0] = CurrNodeArray[0]->prior;
}
/* 将算好的结点加入结果链表 */
PushDataToList(&ResultList, iResult, POSITIVE);
iResultNodeNum++;
if ((CurrNodeArray[0] == List_1)
&& (CurrNodeArray[1] == List_2))
{
/* 在链表头插入控制结点 */
MakeNode(&NewNode, iResultNodeNum);
PushDataToList(&ResultList, iResultNodeNum, iSign);
}
iResult = 0; /* 准备计算下一个结点 */
}
return ResultList;
}
/* 每次只处理两个操作数链表,正正,结果为正的,负负,结果为负的 */
LinkType ComputePPNNList(LinkType List_1, LinkType List_2, int iSign)
{
int iResult = 0, iCarry = 0, iResultNodeNum = 0;
LinkType CurrNodeArray[2],
NewNode = NULL, ResultList = NULL;
/* 初始为每一个操作数链表的尾结点地址 */
CurrNodeArray[0] = (List_1)->prior;
CurrNodeArray[1] = (List_2)->prior;
while (TRUE)
{
if (iCarry > 0) /* 处理前一位的进位 */
{
iResult += iCarry;
iCarry = 0;
}
if (CurrNodeArray[0] != List_1 &&
CurrNodeArray[1] != List_2)
{
iResult += CurrNodeArray[0]->data + CurrNodeArray[1]->data;
CurrNodeArray[0] = CurrNodeArray[0]->prior;
CurrNodeArray[1] = CurrNodeArray[1]->prior;
}
else if (CurrNodeArray[0] != List_1)
{
iResult += CurrNodeArray[0]->data;
CurrNodeArray[0] = CurrNodeArray[0]->prior;
}
else if (CurrNodeArray[1] != List_2)
{
iResult += CurrNodeArray[1]->data;
CurrNodeArray[1] = CurrNodeArray[1]->prior;
}
if (iResult >= 10000)
{
iCarry = iResult / 10000;
iResult = iResult % 10000;
}
PushDataToList(&ResultList, iResult, POSITIVE);
iResultNodeNum++;
if (iCarry == 0 && CurrNodeArray[0] == List_1
&& CurrNodeArray[1] == List_2)
{
MakeNode(&NewNode, iResultNodeNum);
PushDataToList( &ResultList, iResultNodeNum, iSign);
break;
}
iResult = 0; /* 准备计算下一个结点 */
}
return ResultList;
}
/*
* 删除多出的0,如删除0000,0010,3333中的0000为0010,3333
* ,但链表为只有一个逻辑结点为0时则不删除.
*/
status DeleteZero(LinkType *List)
{
LinkType CurrNode, DelNode;
/*
* 一旦遇到第一个不为0的结点则退出, 但
* 链表为只有一个逻辑结点为0时则不删除
*/
CurrNode = DelNode = (*List)->next;
while (fabs((*List)->data) > 1 && CurrNode->data == 0)
{
(*List)->next = CurrNode->next;
CurrNode->next->prior = *List;
DelNode = CurrNode;
CurrNode = CurrNode->next;
free(DelNode);
/* 控制结点减少一个逻辑结点的个数 */
(*List)->data += ((*List)->data > 0) ? -1 : 1;
}
return TRUE;
}
status PushDataToList(LinkType *head, int iNodeNum, int sign)
{
LinkType NewNode;
/* sign为1时为正的, sign为0时为负的 */
iNodeNum *= (sign == POSITIVE) ? 1 : -1;
MakeNode(&NewNode, iNodeNum);
if (*head != NULL)
{
/* 将NewNode所指的结点插入链表，使成为头结点 */
NewNode->next = *head;
NewNode->prior = (*head)->prior;
(*head)->prior = NewNode;
NewNode->prior->next = NewNode;
}
*head = NewNode;
return TRUE;
}
status AppendNodeToList(LinkType *head, LinkType NewNode)
{
static LinkType CurrNode = NULL;
if (*head == NULL)
*head = CurrNode = NewNode;
else
{
/* 在链表尾部添加结点 */
NewNode->next = CurrNode->next;
CurrNode->next = NewNode;
NewNode->prior = CurrNode;
NewNode->next->prior = NewNode;
/* 当前指针向前一步 */
CurrNode = CurrNode->next;
}
return TRUE;
}
status MakeNode(LinkType *p, ElemType e)
{
*p = (LinkType)malloc(sizeof(NodeType) * 1);
if (!(*p))
{
printf("Error, the memory is overflow!\n");
return FALSE;
}
(*p)->data = e;
(*p)->prior = (*p)->next = (*p);
return TRUE;
}
status PrintList(LinkType head)
{
/* LinkType CurrNode = head; use for debug */
LinkType CurrNode = head->next;
if (head == NULL) return FALSE;
if (head->data < 0) printf("-");
while (TRUE)
{
printf(" %04d", CurrNode->data);
CurrNode = CurrNode->next;
if (CurrNode == head) break;
printf("%c", ',');
}
printf("\n");
return TRUE;
}
status ClearMemory(LinkType *headBuff, int iOpNum)
{
int iCounter;
for (iCounter = 0; iCounter < iOpNum; iCounter++)
DeleteList(*(headBuff + iCounter));
free(headBuff);
return TRUE;
}
status DeleteList(LinkType head)
{
LinkType CurrNode;
if (head == NULL) return FALSE;
while (1)
{
CurrNode = head;
CurrNode->next->prior = CurrNode->prior;
CurrNode->prior->next = CurrNode->next;
if (head == head->next)
{
free(CurrNode);
break;
}
head = head->next;
free(CurrNode);
}
return TRUE;
}
/* 输入异常处理 */
status ErrorProcess(char strScrNum[], int iOpNum)
{
int iTemp = 0;
char *cpCurr;
if (!strlen(strScrNum))
{
printf("你没有输入数据!");
return FALSE;
}
for (cpCurr = strScrNum; *cpCurr != '\0'; cpCurr++)
{
if (!(*cpCurr == ' ' || *cpCurr == ',' || *cpCurr == ';'
|| *cpCurr == '-' || *cpCurr == '+'
|| ('0' <= *cpCurr && *cpCurr <= '9'))
|| (*(cpCurr + 1) == '\0' && *cpCurr != ';')
|| (*(cpCurr + 1) == '+' && *cpCurr == '-')
|| (*(cpCurr + 1) == '-' && *cpCurr == '+')
|| (*(cpCurr + 1) == '-' && *cpCurr == '-')
|| (*(cpCurr + 1) == '+' && *cpCurr == '+'))
{
printf("\n出现非法输入 1!\n");
return FALSE;
}
if (*cpCurr == ';') iTemp++;
}
if (iTemp != iOpNum) return FALSE;
return TRUE;
}