ch24aok2.c

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

                return iStatus;
            }
            else if (aOne[2]==1)
            {
                /*
                * The first multiplicand is a one. Hence the answer is
                * a copy of the second multiplicand:
                */
                i = abs(aTwo[0]);
                j = aAllocate ( i , aAnswer );
                if (j!=0)
                    iStatus = EXIT_FAILURE;
                else
                {
                    /*
                    * The copy can be a complete copy, including the two
                    * initial counter words.
                    */
                    for (k=0;(k<=i);k++)
                        *(*aAnswer+k) = aTwo[k];
                }   /* end of "if/else" allocation of answer was OK       */
                return iStatus;
            }       /* end of "if/then" first multiplicand have value one */
        }           /* end of "if/then" first multiplicand perhaps 0/1    */

        /*
        * There was nothing special about the first operand. How about
        * the second?
        */
        if ((abs(aTwo[0])==2) && (aTwo[1]==0))
        {
            if (aTwo[2]==0)
            {
                /*
                * The second multiplicand is zero. Hence the answer is
                * a normalized zero:
                */
                j = aAllocate ( 2, aAnswer );
                if (j!=0)
                    iStatus = EXIT_FAILURE;
                return iStatus;
            }
            else if (aTwo[2]==1)
            {
                /*
                * The second multiplicand is a one. Hence the answer is
                * a copy of the first multiplicand:
                */
                i = abs(aTwo[0]);
                j = aAllocate ( i , aAnswer );
                if (j!=0)
                    iStatus = EXIT_FAILURE;
                else
                {
                    /*
                    * The copy can be a complete copy, including the two
                    * initial counter words.
                    */
                    for (k=0;(k<=i);k++)
                        *(*aAnswer+k) = aOne[k];
                }   /* end of "if/else" allocation of answer was OK     */
                return iStatus;
            }       /* end of "if/then" second multiplcand is one       */
        }           /* end of "if/then" second multiplicand perhaps 0/1 */

        /*
        * We do not have any of the special cases, so we do the multiply.
        * Determine the size of the output array required:                         
        */
        i = abs(aOne[0]) + abs(aTwo[0]) + 1;

        /* Allocate enough space for the answer:                      */
        j = aAllocate(i, ppInt);

        /* Did this allocation work? if not, tell caller:             */
        if (j!=0)
            iStatus = EXIT_FAILURE;
        else
        {
            /*
            * The allocation appeared to work. Set the number of decimal
            * places in the newly allocated array to be the sum of the
            * number of places in the two multiplicands:
            */
            *(pInt+1) = aOne[1] + aTwo[1];

            /*
            * Now compute the product of the two incoming, by computing
            * the pairwise product of each pair of incoming INT's, 
            * shifting up each time.
            *  
            * Note that multiplication proceeds from right to left:  
            * that is, we use the RIGHTmost digits first - just as we
            * do on pencil and paper.                                
            */
            for (k=abs(aTwo[0]); (k>1); k--)
            {
                for (j=abs(aOne[0]); (j>1); j--)
                {
                    /*
                    * Compute the pairwise product of One[j] by      
                    * Two[k], and place the result in answer[L-j]    
                    * where L = i + 1 - k                            
                    * Note that this may overflow, so we have to add 
                    * the high end of our answer into the next answer
                    * element "to the left" (with lower subscript):  
                    */
                    m = pairMultiply ( aOne[j], aTwo[k], w);
                    pInt[i + 2 - k - j] += w[1];
                    pInt[i + 1 - k - j] += w[0];
                }   /* End of inner "for/j" along first operand       */
            }       /* end of outer "for/k" along second operand      */

            /*
            * Now consider the sign of the output. Currently it is   
            * set to positive, but we need to apply the logic:       
            *              * | +   -                                 
            *             ___________                                
            *              + | +   -                                 
            *              - | -   +                                 
            */
            if (((aOne[0]>0)&&(aTwo[0]<0))
            ||  ((aOne[0]<0)&&(aTwo[0]>0)))
                pInt[0] = - pInt[0];

            /*
            * At this point we have in the local array the possibly  
            * un-normalized product of the input arrays. Normalize:  
            */
            m = aNormalize (ppInt, aAnswer);

            /* If there was a problem in normalization. Tell caller:  */
            if (m!=0)
                iStatus = EXIT_FAILURE;
        }   /* end of "if/else" allocation worked                     */
    }   /* end of "if/else" the incoming pointers were OK             */

    return iStatus;
}

/* Divide one INT by another INT, getting quotient and remainder      */
int oneDivide ( INT * iNumerator, INT * iDenominator, INT * iAnswerOD )
{
    int iStatus = EXIT_SUCCESS;

    /*
    * This routine divides the single INT pointed at by the first    
    * parameter by the second INT pointed at by the second parameter.
    * The quotient is given in the first of the pair of INTs pointed 
    * at by the third parameter, and the remainder in the second of  
    * that pair.                                                     
    */

    iAnswerOD[0] = *iNumerator / *iDenominator;
    iAnswerOD[1] = *iNumerator % *iDenominator;

    return iStatus;
}

/* Divide a pair of INTs by one INT, getting quotient and remainder   */
int pairDivide ( INT * iNumerator, INT * iDenominator, INT * iAnswerPD )
{
    int iStatus = EXIT_SUCCESS;
    int j = 0;
    INT r = 0;
    INT w = 0;

    /*
    * This routine divides the pair of INTs pointed at by the first  
    * parameter by the single INT pointed at by the second parameter.
    * The answer is given in the first two of the triplet of INTs    
    * pointed at by the third parameter, and the remainder in the    
    * third of that triplet.                                         
    */

    /* The algorithm used is that of Knuth, Vol 3. 4.3.1, Ex 16       */

    r = 0;
    for (j=0;(j<=1);j++)
    {
         w = (r * BASE + *(iNumerator + j));
         *(iAnswerPD+j) = w / *(iDenominator);
         r = w % *(iDenominator);
    }
    *(iAnswerPD+2) = r;

    return iStatus;
}

/* Divide an INT array by one INT, getting just the quotient          */
int cascDivide ( INT * aNumerator, INT * iDenominator, 
                 int places, INT ** aAnswer )
{
    /*
    * This routine allocates space for the answer, which the caller  
    * must, at some time, release.
    */

    /*
    * This routine divides the long number, in the INT array pointed 
    * to by the first argument, by the single INT pointed to by the  
    * second argument. Space for the result is allocated. The final  
    * output (pointed to by the pointer the third argument points to)
    * is normalized. Since division may increase the number of places
    * after the decimal point, the argument "places" (the third argument)
    * is used to determine how many extra words are to be allocated to
    * the answer, over and above the number of places give in the
    * incoming numberator (first argument).
    * The sign of the single INT is assumed to be positive, and the
    * sign of the answer is that of the incoming long array (numerator).
    */

    int iStatus = EXIT_SUCCESS;
    int j = 0;
    int k = 0;
    int kk = 0;
    INT r = 0;
    INT w = 0;
    int iSign = 1;
    INT * pInt;
    INT ** ppInt = &pInt;

    if ((aNumerator==NULL) || (iDenominator==NULL) || ((aAnswer)==NULL))
    {
        /*
        * If any of the incoming pointers is NULL, then return with  
        * error indication:                                          
        */
        iStatus = EXIT_FAILURE;
        return iStatus;
    }

    /* The algorithm used is again that of Knuth, Vol 3. 4.3.1, Ex 16 */

    /* Determine the length of the numerator, and remember its sign   */
    r = 0;
    k = abs(*aNumerator);
    /*
    * The variable "k" indicates the number of elements in the incoming
    * array (numerator). This means that this contains:
    *      DIGITS_IN_BASE * (k - 1)
    * places. We need to ensure that what we allocate is at least as
    * long as the greater of 
    *   (a) k and 
    *   (b) (places+DIGITS_IN_BASE-1)/DIGITS_IN_BASE
    */
    kk = (places + DIGITS_IN_BASE - 1) / DIGITS_IN_BASE;
    j = max(kk,k);
    aAllocate(j, ppInt);
    if (*aNumerator<0)
        iSign = -1;
    else
        iSign = 1;
    /*
    * The number of places after the point in the new intermediate
    * array is equal to the number of places in the incoming array plus
    * the extra words (if any) that have been allocated
    */
    *(pInt + 1) = *(aNumerator + 1) + (j>k) ? j-k : 0;
    k = j;

    for (j=2; (j<=k); j++)
    {
         w = (r * BASE + *(aNumerator + j));
         *(pInt + j) = w / *(iDenominator);
         r = w % *(iDenominator);
    }

    /*
    * Note that at the very end we have an outgoing, residual        
    * carry. This is simply lost, though we may have already saved
    * a lot of extra information in the extra words in the output.
    */

    /* Normalize the intermediate answer into the final answer:   */
    /* Note that this also frees the intermediate work area       */
    j = aNormalize ( ppInt, aAnswer );

    /* Apply the incoming sign to the answer:                         */
    if (iSign<0)
        **aAnswer = - (**aAnswer);

    return iStatus;
}

/* Divide an INT array by an INT array, getting just the quotient     */
int aDivide ( INT * aNumerator, INT * aDenominator, 
              int places,  INT ** aAnswer )
{
    /*
    * This routine allocates space for the answer, which the caller  
    * must, at some time, release                                    
    */

    /*
    * This is the most complex of the routines, and uses the algorithm  
    * described by Knuth in "The Art of Computer Programming".   
    * This is an extension of the simple "pencil and paper" technique
    * that we were taught at school - and many of us have since forgotten.
    */

    int iStatus = EXIT_SUCCESS;
    int i = 0;
    int j = 0;
    int k = 0;
    int l = 0;
    int m = 0;
    int n = 0;
    int borrow = 0;
    int iNmax;
    int iDmax;
    INT carry = 0;
    INT iBase = BASE;
    INT wN[2];
    INT aW[3];
    INT aX[3];
    INT aY[3];
    INT aZ[3];
    INT bigD = 0;
    INT littleD = 0;
    /* Space for a local copy of the numerator. This copy will be     */
    /* long enough to be longer than the denominator.                 */
    INT * plNumerator = NULL;
    INT ** pplNumerator = &plNumerator;
    /* Space for a local copy of the Normalized denominator. This will*/
    /* ensure that the leading INT does not have value zero:          */
    INT *plDenominator = NULL;
    INT ** pplDenominator = & plDenominator;
    /* Space for a local copy of the resultant quotient. This copy is */
    /* prior to the required normalization.                           */
    INT * plQuotient = NULL;
    INT ** pplQuotient = &plQuotient;
    /* Space for three work areas required during the calculation.    */
    INT * plSubtrahend = NULL;
    INT ** pplSubtrahend = &plSubtrahend;
    INT * plMinuend = NULL;
    INT ** pplMinuend = &plMinuend;
    INT * pInter = NULL;
    INT ** ppInter = &pInter;

    /*
    * There are three special cases to check for in Division. If the
    * denominator is one, then we do not have to perform the operation,
    * but just copy the numerator. If the numerator is zero, then the
    * answer is zero. If the denominator is zero, then we have an error
    */

    /* So look at the denominator: */
    if ((abs(*aDenominator)==2) && (*(aDenominator+1)==0))
    {
        if (*(aDenominator+2)==0)
        {
            /* The denominator is zero - error */
            iStatus = EXIT_FAILURE;
            return iStatus;
        }   /* end of "if/then" denominator has value zero */
        else if (*(aDenominator+2)==1)
        {
            /*
            * The denminator has value one - make a copy of the
            * numerator as the answer:
            */
            i = abs(*aNumerator);
            j = aAllocate ( i, aAnswer );
            if (j==0)
            {
                for (k=0;(k<=i);k++)
                    *(*aAnswer+k) = *(aNumerator+k);
            }   /* end of "if/then" alloction of answer was OK */
            else
                iStatus = EXIT_FAILURE;
            return iStatus;
        }   /* end of "if/then" denomintor has value one */
    }       /* end of "if/then" denominator perhaps 0/1  */