ch24aok.c

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

                /*
                * Note that this is a very low probability step. It happens 
                * only in the order of 2/BASE. We have to add back, but
                * ignoring the top end carry:                        
                */
                *(plQuotient + j) = *(plQuotient + j) - 1;
                carry = 0;
                for (i=n+1; (i>0); i--)
                {
                    k = (*plNumerator) - i;
                    *(plNumerator+j+k) += (i==1) ? 0 : 
                                          (*(plDenominator + k) + carry);
                    if (*(plNumerator + j + k) > BASE)
                    {
                        *(plNumerator + j + k) -= BASE;
                        carry = 1;
                    }
                    else
                        carry =0;
                }   /* end of "for/i" adding back in                  */
            }       /* end of "if/then" borrow was non zero           */
        }           /* end of "if/then" quotient digit was non zero   */

        /* Knuth D7:                                                  */

        /* Loop back to get the next quotient "digit"                 */

    }   /* end of "for/j" major loop along digits of numerator        */

    /* Knuth D8:                                                      */
    /* Normalize the result:                                          */
    k = aNormalize ( pplQuotient, aAnswer );

    /* Calculate and apply the sign of the answer:                    */
    /*
    *  This is according to the logic: 
    *        /  |  +   - 
    *        _____________
    *        +  |  +   -
    *        -  |  -   +
    *
    */
    if (((*aNumerator<0) && (*aDenominator>0))
    ||  ((*aNumerator>0) && (*aDenominator<0)))
        **aAnswer = - **aAnswer;

    /*
    *  This has been an integer division. If you require the remainder,
    *  you may calculate it by dividing the current contents of the
    *  array plNumerator by the value littleD (using the function cascDivide).
    *  This will not itself leave a further remainder.
    */

    /* Free the allocated intermediate work areas:                    */
    free ( pInter );
    free ( plSubtrahend );
    free ( plMinuend );
    free ( plQuotient );
    free ( plNumerator );
    free ( plDenominator );

    return iStatus;
}


/* Allocate an INT array for the aDivide internal operation which is  */
/* one longer than the incoming array:                                */
int aDivNormalize ( INT * pinNumerator, INT ** ppoutNumerator )
{
    int iStatus = EXIT_SUCCESS;
    int iNmax = 0;
    int i = 0;
    int j = 0;
    int k = 0;
    int iAllocLength = 0;
    INT * pAnswer = NULL;
    INT ** ppAnswer = &pAnswer;

    /* What is the length required for the new allocation to make?    */
    iNmax = abs(*pinNumerator);
    iAllocLength = iNmax + 1;

    /* make the allocation:                                           */
    i = aAllocate ( iAllocLength, ppAnswer );

    /* Now copy the original into the new area.                       */
    /* Set up the initial zero:                                       */
    *(pAnswer + 1) = 0;

    /* Now copy the rest of the input array to the output:            */
    for (k=2; (k <= iAllocLength); k++)
        *(pAnswer + k) = *(pinNumerator + k - 1);

    /* Point the answer to the newly allocated:                      */
    *ppoutNumerator = pAnswer;

    return iStatus;
}

/* Normalize an INT array                                             */
int aNormalize ( INT ** aUnNormal, INT ** aNormal )
{
    /*
    * Although this routine may allocate space for its answer, if it 
    * does so it frees the space used by its first argument. Hence the   
    * caller does NOT have to consider whether to free the returned  
    * space from this routine.                                       
    */

    int iStatus = EXIT_SUCCESS;
    int i = 0;
    int j = 0;
    int k = 0;
    int m = 0;
    int iSign = 1;
    INT * plNormal = NULL;
    INT ** pplNormal = &plNormal;
    
    /*
    * This function takes two arguments. The first is a pointer to   
    * a pointer to an array of INT. This array may be un-normalized. 
    * The second argument is a pointer to a pointer. This latter is  
    * not yet pointing to anything, but will (at the termination of  
    * this routine) be an array of INT. This will be a normalized    
    * copy of the first argument. If the first array is normal then   
    * this pointer is identical to the first. If the first argument  
    * is not normal, then a new array is allocated, and the first is 
    * de-allocated, and the incoming first pointer set to NULL       
    */
    
    if ((aUnNormal==NULL) || (aNormal==NULL) || ((*aUnNormal)==NULL))
    {
        /*
        * If any of the incoming pointers is NULL, or the first     
        * array does not exist, then indicate an error:            
        */
        iStatus = EXIT_FAILURE;
    }
    else
    {
        /*
        * We know that the incoming pointers are (apparently) OK, So 
        * set the initial outgoing value to be simply a copy of the  
        * incoming:                                                  
        */
        plNormal = *aUnNormal;

        /*
        * Determine how many words (INTs) in the first array we have 
        * to scan:                                                   
        */
        k = abs((*aUnNormal)[0]);
        if ((*aUnNormal)[0]<0)
            iSign = -1;
        
        /*
        * If there is anything at all in the first array, then count 
        * the number of zero words with which it begins:              
        */
        if (k>0)
        {
            j = (*aUnNormal)[1];
            m = 0;
            for (i = 1; ((j==0)&&(i<=k)); i++)
            {
                j = (*aUnNormal)[i];
                if (j==0)
                    m++;
            }
        }
        
        /*
        * At this point we know that 'm' contains a count of the     
        * number of zero words at the start of the UnNormal input.   
        * So we need to (a) allocate a new array, and (b) copy the   
        * old into the new, and (c) deallocate the old array:        
        */
        if (m>0)
        {
            /* Allocate the new normal array:                         */
            k = abs((*aUnNormal)[0]) - m;

            /* Note that a normal zero has at least one leading word: */
            /* do not normalize away all the digits!                  */
            if (k<=0)
            {
                k = 1;
                m--;
            }
            j = aAllocate(k, pplNormal);

            /* Copy the un-normal to the normal:                      */
            for (i=1; (i<(k+1)); i++)
            {
                j = i + m;
                *(plNormal + i) = (*aUnNormal)[j];
            }

            /* Set the sign in the new, remembered from the old:      */
            if (iSign<0)
                *plNormal = - (*plNormal);

            /* de-allocate the old un-normal:                         */
            free(*aUnNormal);

            /* And tell the caller this has happened:                 */
            *aUnNormal = NULL;

        }   /* end of "if/then" there was a necessity to allocate new */

        /* And point the caller to the new normalized value:          */
        *aNormal = plNormal;

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

/* Add an INT array to an INT array                                   */
int aAdd ( INT * aOne, INT * aTwo, INT ** aAnswer )
{
    /* This routine allocates space for the answer, which the caller  */
    /* must, at some time, release                                    */

    int iStatus = EXIT_SUCCESS;
    int i = 0;
    int j = 0;
    int k = 0;
    int iSign = 1;
    int bUseAdd = 1;
    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. This routine    
    * allocates enough space for the answer, and computes the sum.   
    * The answer is normalized before returning to the caller.       
    */
    
    /* Test the incoming pointers for validity:                       */
    if ((aOne==NULL) || (aTwo==NULL) || (aAnswer==NULL))
    {
        /* At least one of the arguments was bad: indicate to caller: */
        iStatus = EXIT_FAILURE;
        return iStatus;
    }
    else
    {
        /*
        * Compute the maximum length of the answer array. This caters
        * for the worst case of carry upwards from the top word:     
        */
        i = max(abs(aOne[0]), abs(aTwo[0])) + 1;

        /* Allocate enough space for the answer, but only point to it */
        /* locally:                                                   */
        j = aAllocate(i, ppInt);

        /*
        * We need to look at the signs of the incoming arguments. If 
        * these are the same, then we simply add the arguments, as if
        * they were both positive, and give the answer that sign. If,
        * however, they differ in sign, then we force them both positive
        * and do a subtraction. After the subtraction we determine the
        * outgoing sign. Hence we call either "internalAdd" or "internal-
        * Subtract" to do the real calculation. Note that each of these
        * internal routines normalizes its answer before returning, so
        * we can just hand that answer back to the caller (after any
        * adjustment of sign).
        */

        if ((*aOne>0) && (*aTwo>0))
        {
            bUseAdd = 1;
            iSign = 1;
        }
        else if ((*aOne<0) && (*aTwo<0))
        {
            bUseAdd = 1;
            iSign = -1;
        }
        else
        {
            bUseAdd = 0;
            iSign = 1;
        }

        if (bUseAdd==1)
            j = internalAdd ( aOne, aTwo, ppInt );
        else
        {
            /*
            * We know that we have to subtract - these elements
            * differ in sign. Place the positive element first.
            * We do NOT compare the absolute or signed values of
            * the two arguments here (using aCompare) - we only
            * need to know their signs:
            */
            if (*aOne>0)
                j = internalSubtract ( aOne, aTwo, ppInt );
            else
                j = internalSubtract ( aTwo, aOne, ppInt );
            /*
            * Note that the sign will have been computed by the
            * internalSubtract routine, so there is no need to
            * alter it in this routine.
            */
        }

        /* Correct the sign of the answer:                           */
        if (iSign<0)
            **ppInt = - (**ppInt);

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

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

/* Subtract an INT array from an INT array                            */
int aSubtract ( INT * aOne, INT * aTwo, INT ** aAnswer )
{
    /* This routine allocates space for the answer, which the caller  */
    /* must, at some time, release                                    */

    int iStatus = EXIT_SUCCESS;
    int i = 0;
    int j = 0;
    int k = 0;
    int iSign = 1;
    int bUseAdd = 1;
    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. This routine    
    * allocates enough space for the answer, and computes the difference.
    * The answer is normalized before returning to the caller.       
    */
    
    /* Test the incoming pointers for validity:                       */
    if ((aOne==NULL) || (aTwo==NULL) || (aAnswer==NULL))
    {
        /* At least one of the arguments was bad: indicate to caller: */
        iStatus = EXIT_FAILURE;
        return iStatus;
    }
    else
    {
        /*
        * Compute the maximum length of the answer array. This caters
        * for the worst case of borrow upwards from/to the top word:     
        */
        i = max(abs(aOne[0]), abs(aTwo[0])) + 1;

        /* Allocate enough space for the answer, but only point to it */
        /* locally:                                                   */
        j = aAllocate(i, ppInt);

        /*
        * We need to look at the signs of the incoming arguments. If 
        * these are the same, then we subtract the absolutely smaller
        * from the absolutely larger, and give the result the sign of
        * the absolutely larger. If the signs are different, then we
        * add together the absolute values, and give the result the
        * appropriate sign.
        */

        if ((*aOne>0) && (*aTwo<0))
        {
            bUseAdd = 1;
        }
        else if ((*aOne<0) && (*aTwo>0))
        {
            bUseAdd = 1;