微创的2道数据结构题

        上次在CSDN论坛上看见有个关于微创的面试题，粗略看了一下，数据结构已经丢了二年多了，现在突然看到这样的题目，突然有种怀旧的感觉。
        于是有点手痒，决定做做，原以为这2道题最多半小时之内就可以搞定，结果竟然花了一个半小时，而且还调试了半天才行！不知道是不是老了，唉！

1）实现string toHex(int)把一个十进制转换成十六进制。（完全用算法实现）
2）实现一个计算大位数（如100位以上）相乘结果的函数string multiply(sting,string)。（请完全用算法实现）
 
(1)
string Int2Hex(int a_iInt)
{
 string strRet;
 strRet = "";
 
 // if a_iInt < 0 then return null;
 if(a_iInt < 0)
 {
     return strRet;
 }
 
 int i;
 int iTmp;
 int iResidue;  // the residue
 int iQuotient; // the quotient
 char cTmp;
 
 for(iTmp = a_iInt;iTmp >= 16;)
 {
     iResidue = iTmp % 16;
     iQuotient = iTmp / 16;
    
     if(iResidue >= 10)
     {
         cTmp = 'A' + iResidue - 10;
     }else // 0 <= iResidue <= 9
     {
         cTmp = '0' + iResidue;
     }
    
     strRet = cTmp + strRet;
     iTmp = iQuotient;    
 }
 
 if(iResidue >= 10)
 {
     cTmp = 'A' + iQuotient - 10;
 }else // 0 <= iResidue <= 9
 {
     cTmp = '0' + iQuotient;
 }
 strRet = cTmp + strRet;
 
 return strRet;
}


(2)

string multiply(string a_strMultp1,string a_strMultp2)
{
    string strRet; // the product;
    int iMultp1Len; // the length of multiplier1
    int iMultp2Len; // the length of multiplier2
    int iRetLen;
   
    // initialize the parameters
    iMultp1Len = a_strMultp1.length();   
    iMultp2Len = a_strMultp2.length();
    iRetLen = 0;
    strRet = "";
   
    // if either's length is 0,then exit;
    if(iMultp1Len <= 0 || iMultp2Len <= 0)
    {
        return strRet;
    }
   
    int i;
    int j;
    int iCarry; // the Carry;
    int iDigit;  // the Digit;
    char cTmp;
   
    iCarry = 0;
    iDigit = 0;

   
    for(i = 0 ; i < iMultp2Len ; i ++)
    {       
        for(j = iMultp1Len - 1; j >= 0; j --)
        {
            iDigit = (a_strMultp2[i] - '0')*(a_strMultp1[j] - '0') + iCarry;
            iCarry = iDigit / 10;
            iDigit = iDigit % 10;
           
            cTmp = iDigit + '0';
            IntAdd(strRet,cTmp,iMultp1Len - j);
        }
       
        if(iCarry >= 1)
        {
            IntAdd(strRet,iCarry + '0',iMultp1Len + 1);
            iCarry = 0;
        }
       
        if(i < iMultp2Len - 1)
        {
          strRet = strRet + '0';
        }   
    }   
   
    return strRet;   
}


// the function is called by the funtion above
void IntAdd(string &a_strSor,char a_cAdd,int a_iIndex)
{
    int iStrIndex;
    iStrIndex = a_strSor.length() - a_iIndex;   
    char cCarry = 0;
    if(iStrIndex < 0)
    {
        a_strSor = '0' + a_strSor;
        iStrIndex = a_strSor.length() - a_iIndex;
    }
   
    do{
        cCarry = (a_strSor[iStrIndex] - '0') + (a_cAdd - '0') + cCarry;
        a_cAdd = '0';
        a_strSor[iStrIndex] = cCarry % 10 + '0';
        iStrIndex-- ;
        cCarry = cCarry / 10;
    }while(cCarry != 0 && iStrIndex >= 0);
   
    // the highest digit is not less than 1
    if(iStrIndex <= 0 && cCarry > 0)
    {
        cCarry = cCarry + '0';
        a_strSor = cCarry + a_strSor;
    }
}

本文地址：http://com.8s8s.com/it/it24530.htm