ch24abad.c

来自「稀疏矩阵、链表、图、队列、二叉树、多叉树、排序、遗传算法等的实现」· C语言 代码 · 共 1,132 行 · 第 1/3 页

                /* Knuth D6:                                              */
                /*
                * 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:                                                  */

        /* Get rid of the intermediate work areas, and loop back      */
        /* It is left as an exercise to the reader to place the "free"*/
        /* statements correctly in this routine. It is not quite as   */
        /* obvious as you might at first think. Also consider: are    */
        /* any more "free" statements required? Is this routine memory*/
        /* safe? How could this routine be rephrased so as to require */
        /* less allocation/de-allocation?                             */
        /* This file will NOT compile correctly, as these statments do*/
        /* need to be placed correctly!                               */
#error "Fix the placement of the following free code"
#if (0)
        free ( pInter );
        pInter = NULL;
        free ( pInter2 );
        pInter2 = NULL;
#endif

        /* Clearly the allocation and de-allocation of these work     */
        /* areas, pInter and pInter2, within the central body of this */
        /* loop is very inefficient. Wilst you are considering how to */
        /* remove all the work areas, you could begin by considering  */
        /* how to move their allocation and de-allocation to outside  */
        /* of this loop.                                              */

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

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

    /* Free the allocated intermediate work areas:                    */
    /* See the above excercise to consider placement.                 */
#error "Fix the placement of the following free code"
#if (0)
    free ( plSubtrahend );
    plSubtrahend = NULL;
    free ( plMinuend );
    plMinuend = NULL;
    free ( plQuotient );
    plQuotient = NULL;
    free ( plNumerator );
    plNumerator = NULL;
    free ( plDenominator );
    plDenominator = NULL;
#endif

    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 for 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 s = 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 noral 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)
        {
            s = -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 (s<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 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. 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);

        if (j==0)
        {
            /*
            * 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]);
            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 bacwards along the answer      */

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

            if (k!=0)
            {
                /* The Normalize function indicated something wrong:  */
                iStatus = EXIT_FAILURE;
            }
        }   /* end of "if/then" the initial allocation was OK         */
        else
        {
            /* The initial allocation indicated an error. Pass this   */
            /* back to the caller:                                    */
            iStatus = EXIT_FAILURE;
        }
    }       /* end of "if/else" incoming pointers were OK             */
    
    return iStatus;
}

/* 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 has to allocate an array of "iCount+1" INT's, and set 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;
}