ch24aok.c

稀疏矩阵、链表、图、队列、二叉树、多叉树、排序、遗传算法等的实现

        }
        else
        {
            /*
            * The signs are the same. Perform an internalSubtract
            */
            bUseAdd = 0;
            iSign = aAbsCompare ( aOne, aTwo );
            if (iSign<0)
            {
                /*
                * The first argument is smaller than the second. Take
                * the first from the second, and use the sign of the
                * second:
                */
                j = internalSubtract ( aTwo, aOne, ppInt );
                if (*aTwo<0)
                    *pInt = - *pInt;
            }
            else if (iSign>0)
            {
                /* 
                * The first argument is larger than the second. Take
                * the second from the first, and use the sign of the
                * first:
                */
                j = internalSubtract ( aOne, aTwo, ppInt );
                if (*aOne<0)
                    *pInt = - *pInt;
            }
            else
            {
                /*
                * This is the special case where we know that the two
                * arguments have the same sign AND are equal in magnitude
                * so the answer is zero. We simply allocate a zero array
                * (which we have already done), and normalize it:
                */
                j = aNormalize(ppInt, ppInt);
            }

            /*
            * We have the answer - return to caller, indicating failure
            * if detected:
            */
            if (j!=0)
                iStatus = EXIT_FAILURE;
            return iStatus;
        }

        /*
        * If control falls through to here, then we have to
        * add the absolute values together, and take the 
        * sign of the first as the outgoing sign:
        */
        j = internalAdd ( aOne, aTwo, ppInt );
        if (j!=0)
            iStatus = EXIT_FAILURE;

        if (*aOne<0)
            **ppInt = - **ppInt;


        /* Tell caller the address of the answer:                     */
        aAnswer = ppInt;

    }       /* end of "if/else" incoming pointers were OK             */
    
    return iStatus;
}

/* Add an INT array to an INT array, all pre-allocated, all positive  */
int internalAdd ( INT * aOne, INT * aTwo, INT ** aAnswer )
{

    int iStatus = EXIT_SUCCESS;
    int i = 0;
    int j = 0;
    int k = 0;
    int m = 0;
    INT w;
    INT carry = 0;
    INT * pInt;
    INT ** ppInt = &pInt;
    
    /*
    * This routine adds together two very large numbers. Each of the 
    * arguments is assumed to be in an array of INT. The sum is
    * computed and passed back in the third argument.
    * The answer is normalized before returning to the caller.       
    */
    
    /*
    * We start at the right hand end of each input array,    
    * putting the answer into the right hand end of the new  
    * array. Note that we (a) keep "carry" up to date, and   
    * (b) we use value zero if the subscripts overshoot the  
    * incoming arrays (which they will):                     
    */
    k = abs(aOne[0]);
    m = abs(aTwo[0]);
    i = max(k,m);
    for (; (i>0); i--)
    {
        w = (k>0) ? aOne[k] : 0 + 
            (m>0) ? aTwo[m] : 0 + 
            carry;

        /* Have we overshot the maximum value we can place in */
        /* a single word?                                     */
        if (w>BASE)
        {
            carry = 1;
            w -= BASE;
        }
        else
            carry = 0;

        /* Set the answer from our result:                    */
        (*ppInt)[i] = w;

        /* Get ready to process the next words to the left, by*/
        /* decrementing their subscripts:                     */
        m--;
        k--;

    }   /* end of "for/i" loop backwards along the answer     */

    /* Now normalize the answer:                              */
    k = aNormalize(aAnswer, aAnswer);

    /* Did the Normalize function indicated something wrong?  */
    if (k!=0)
        iStatus = EXIT_FAILURE;
    
    return iStatus;
}

/* Subtract an INT array from an INT array, all pre-allocated, & +ve  */
int internalSubtract ( INT * aOne, INT * aTwo, INT ** aAnswer )
{

    int iStatus = EXIT_SUCCESS;
    int i = 0;
    int j = 0;
    int k = 0;
    int m = 0;
    INT w;
    INT carry = 0;
    INT * pInt;
    INT ** ppInt = &pInt;
    
    /*
    * This routine subtracts two very large numbers. Each of the 
    * arguments is assumed to be in an array of INT. The difference
    *  "One minus Two"
    * is computed and passed back in the third argument.
    * The answer is normalized before returning to the caller.
    * Both of the incoming arguments are assumed to be positive, and
    * their actual signs are simply not inspected here. This is an
    * internal routine, and the callers (aAdd and aSubtract) will be 
    * making the appropriate sign corrections
    */
    
    /*
    * We start at the right hand end of each input array,    
    * putting the answer into the right hand end of the new  
    * array. Note that we (a) keep "carry" up to date, and   
    * (b) we use value zero if the subscripts overshoot the  
    * incoming arrays (which they will). "carry" is also "borrow".
    */
    k = abs(aOne[0]);
    m = abs(aTwo[0]);
    i = max(k,m);
    for (; (i>0); i--)
    {
        w = (k>0) ? aOne[k] : 0 - 
            (m>0) ? aTwo[m] : 0 - 
            carry;

        /*
        * Have we overshot the maximum value we can place in 
        * a single word (improbable), or is the answer word  
        * negative? Force the answer word positive and in range: 
        */
        if (w>BASE)
        {
            carry = -1;
            w -= BASE;
        }
        else if (w<0)
        {
            carry = 1;
            w += BASE;
        }
        else
            carry = 0;

        /* Set the answer from our result:                    */
        (*ppInt)[i] = w;

        /* Get ready to process the next words to the left, by*/
        /* decrementing their subscripts:                     */
        m--;
        k--;

    }   /* end of "for/i" loop backwards along the answer     */

    /*
    * At this stage the "carry" flag indicates the sign of   
    * the final answer:                                      
    *    carry    output sign
    *      -1     error in algorithm
    *       0     positive
    *      +1     negative
    *
    * If the output is negative we only need to flip the sign
    * of the normalized result.
    */

    /* Now normalize the answer:                                      */
    k = aNormalize(aAnswer, aAnswer);

    /*
    * Did the Normalize function indicate something wrong, or
    * was there an error in the subtraction algorithm?
    */
    if ((k!=0) || (carry<0))
        iStatus = EXIT_FAILURE;

    /* Set the outgoing sign:                                         */
    if (carry>0)
        **aAnswer = - (**aAnswer);
    
    return iStatus;
}

/* Compare the values of two very large numbers                      */
int aCompare ( INT * aOne, INT * aTwo )
{
    int iAnswer = 0;
    int i = 0;
    int j = 0;
    int k = 0;

    /*
    * This routine compares the absolute valus of two very large
    * numbers passed in. 
    * The returned value is one of:
    *     -1     first argument is smaller than second
    *      0     first and second arguments are equal
    *     +1     first argument is greater than second
    * The routine tries to take shortcuts to getting the answer, to
    * avoid having to scan down the whole of both arguments.
    * Note that both arguments are assumed to have been normalized
    * by the caller, so that there are no excess leading zeros.
    */

    /* Firstly, can we decide merely from the signs of the numbers?   */
    i = *aOne;
    j = *aTwo;

    if ((i>0) && (j<0))
    {
        iAnswer = +1;
        return iAnswer;
    }
    else if ((i<0) && (j>0))
    {
        iAnswer = -1;
        return iAnswer;
    }
    /*
    * If control falls through, then the two arguments are the same
    * sign, so we have to compare their absolute values:
    */

    iAnswer = aAbsCompare ( aOne, aTwo );
    /*
    * If the arguments are different, and both are negative, then
    * we need to invert the sense of the answer we have found, as
    * currently we have the absolute value comparison here:
    */
    if ((iAnswer!=0) && (*aOne<0))
        iAnswer = - iAnswer;

    return iAnswer;
}

/* Compare the absolute values of two very large numbers              */
int aAbsCompare ( INT * aOne, INT * aTwo )
{
    int iAnswer = 0;
    int i = 0;
    int j = 0;
    int k = 0;

    /*
    * This routine compares the absolute valus of two very large
    * numbers passed in. 
    * The returned value is one of:
    *     -1     absolute value of first argument is smaller than second
    *      0     first and second arguments are equal
    *     +1     absolute value of first argument is greater than second
    * The routine tries to take shortcuts to getting the answer, to
    * avoid having to scan down the whole of both arguments.
    * Note that both arguments are assumed to have been normalized
    * by the caller, so that there are no excess leading zeros.
    */

    /* Get the lengths of the two arguments: */
    i = abs(*aOne);
    j = abs(*aTwo);

    /* If the lengths are not equal, then we know the answer: */
    if (i<j)
        iAnswer = -1;
    else if (i>j)
        iAnswer = 1;
    else
    {
        /*
        * The two arguments are equal in length. Scan from left
        * to right till we find the first word that differs, if any:
        */
        for (i=1; ((i<=j) && (iAnswer==0)); i++)
        {
            if ((*aOne+i)!=(*aTwo+i))
            {
                /* There is a difference. Which way is it? */
                if ((*aOne+i)<(*aTwo+i))
                    iAnswer = -1;
                else
                    iAnswer = 1;
            }   /* end of "if/then" there is a difference         */
        }       /* end of "for/i" scanning down the arguments     */
    }           /* end of "if/else" arguments are the same length */

    return iAnswer;
}

/* Allocate and initialize to zero an INT array                       */
int aAllocate ( int iCount, INT ** aAnswer )
{
    int iStatus = EXIT_SUCCESS;
    INT * pInt = NULL;
    int i = 0;
    
    /*
    * This allocates an array of "iCount+1" INT's, and sets the 
    * first of these INT's to iCount, and all the rest to zero:      
    */
    pInt = calloc ( sizeof (INT), iCount + 1);
    
    if (pInt==NULL)
    {
        /* We could not allocate the memory: tell the caller          */
        iStatus = EXIT_FAILURE;
        return iStatus;
    }
    else
    {
        /* Set the body of the new array to zero:                     */
        for (i=1; (i <= iCount); i++)
            pInt[i] = 0;

        /* Set the counter word to indicate the length of the array:  */
        *pInt = iCount;
    }
    
    /* Provided that the incoming pointer can be used, tell caller:   */
    if (aAnswer!=NULL)
        *aAnswer = pInt;

    return iStatus;
}