ch24aok2.c

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

        */
        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 a1 = 0;
    int a2 = 0;
    int a3 = 0;
    int b3 = 0;
    INT v1 = 0;
    INT v2 = 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 pre-allocated answer array has enough places after the
    * point to cater for the larger of the incoming addends.
    * 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):                     
    */
    /* Point to the ends of the incoming addends: */
    k = abs(aOne[0]);
    m = abs(aTwo[0]);

    /* Get the number of places after the point for each addend: */
    a1 = aOne[1];
    a2 = aTwo[1];

    /* Compute the number of places after the point for the answer: */
    i = abs(**aAnswer);
    b3 = i - a3;

    /* Loop backwards along the two addends, adding corresponding words: */
    for (; (i>1); i--)
    {
        /*
        * Compute the decimal position we are in the answer. This
        * may well be negative, when we are before the point:
        */
        a3 = i - b3;

        /*
        * If this decimal position is within the range of the first
        * addend, then use it, otherwise use zero:
        */
        if (a3<=a1)
        {
            v1 = aOne[k];
            k--;
        }
        else 
            v1 = 0;

        /*
        * and the same for the second addend as for the first:
        */
        if (a3<=a2)
        {
            v2 = aTwo[m];
            m--;
        }
        else 
            v2 = 0;

        /* Compute the sum: */
        w = v1 + v2 + 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;

    }   /* 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 a1 = 0;
    int a2 = 0;
    int a3 = 0;
    int b3 = 0;
    INT v1 = 0;
    INT v2 = 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]);

    /* Get the number of places after the point for each addend: */
    a1 = aOne[1];
    a2 = aTwo[1];

    /* Compute the number of places after the point for the answer: */
    i = abs(**aAnswer);
    b3 = i - a3;

    for (; (i>1); i--)
    {
        /*
        * Compute the decimal position we are in the answer. This
        * may well be negative, when we are before the point:
        */
        a3 = i - b3;

        /*
        * If this decimal position is within the range of the first
        * addend, then use it, otherwise use zero:
        */
        if (a3<=a1)
        {
            v1 = aOne[k];
            k--;
        }
        else 
            v1 = 0;

        /*
        * and the same for the subtrahend as for the minuend:
        */
        if (a3<=a2)
        {
            v2 = aTwo[m];
            m--;
        }
        else 
            v2 = 0;

        /* Perform the subtraction, including the carry (borrow): */
        w = v1 - v2 - 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;

    }   /* 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;
    int b1 = 0;
    int a1 = 0;
    int b2 = 0;
    int a2 = 0;

    /*
    * This routine compares the absolute values 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);

    /*
    * Remember the length of the smaller, as that is the maximum
    * length of scan:
    */
    k = min(i,j);

    /* Get the number of places before and after the point for both: */
    a1 = *(aOne + 1);
    b1 = i - a1;
    a2 = *(aTwo + 1);
    b2 = j - b2;

    /* If the pre-point lengths are not equal, then we know the answer: */
    if (b1<b2)
        iAnswer = -1;
    else if (b1>b2)
        iAnswer = 1;
    else
    {
        /*
        * The two arguments are equal in length pre-point. Scan from left
        * to right till we find the first word that differs, if any:
        */
        for (i=2; ((i<=k) && (iAnswer==0)); i++)
        {
            if ((*aOne+i)!=(*aTwo+i))
            {
                /* There is a difference. Which way is it? */
                if ((*aOne+i)<(*aTwo+i))
                    iA