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