微创2道数据结构题介绍

微创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 iscalledby 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;
}
}