论坛交流
首页办公自动化| 网页制作| 平面设计| 动画制作| 数据库开发| 程序设计| 全部视频教程
应用视频: Windows | Word2007 | Excel2007 | PowerPoint2007 | Dreamweaver 8 | Fireworks 8 | Flash 8 | Photoshop cs | CorelDraw 12
编程视频: C语言视频教程 | HTML | Div+Css布局 | Javascript | Access数据库 | Asp | Sql Server数据库Asp.net  | Flash AS
当前位置 > 文字教程 > C语言程序设计教程
Tag:新手,函数,指针,数据类型,对象,Turbo,入门,运算符,数组,结构,二级,,tc,游戏,试题,问答,编译,视频教程

采用循环双向链表, 能实现多个长整型进行加法运算

文章类别:C语言程序设计 | 发表日期:2008-9-24 14:45:37

/*
* 文件名: 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;
}

视频教程列表
文章教程搜索
 
C语言程序设计推荐教程
C语言程序设计热门教程
看全部视频教程
购买方式/价格
购买视频教程: 咨询客服
tel:15972130058