C/C++ 面试题1

（1）如何在不使用第三个变量的情况下交换变量值

第一种：算术运算：把a、b看做数轴上的点，围绕两点间的距离来进行计算

int a,b;
a=10;b=12;
a=b-a; //a=2;b=12
b=b-a; //a=2;b=10
a=b+a; //a=12;b=10

具体过程：第一句“a=b-a”求出ab两点的距离，并且将其保存在a中；第二句“b=b-a”求出a到原点的距离（b到原点的距离与ab两点距离之差），并且将其保存在b中；第三句“a=b+a”求出b到原点的距离（a到原点距离与ab两点距离之和），并且将其保存在a中。完成交换。
此算法与标准算法相比，多了三个计算的过程，但是没有借助临时变量。（以下称为算术算法）

缺点：是只能用于数字类型，字符串之类的就不可以了。a+b有可能溢出(超出int的范围)，溢出是相对的， +了溢出了，-回来不就好了，所以溢出不溢出没关系，就是不安全。

第二种：栈实现。不多解释了
int exchange(int x,int y)
{
stack S;
push(S,x); //压栈
push(S,y);
x=pop(S); //出栈
y=pop(S);
}

第三种：位运算
int a=10,b=12;
a=a^b;
b=a^b;
a=a^b;
此算法能够实现是由异或运算的特点决定的，通过异或运算能够使数据中的某些位翻转，其他位不变。这就意味着任意一个数与任意一个给定的值连续异或两次，值不变

第四种：地址算法

if(a<b)
{
a=(int*)(b-a);
b=(int*)(b-(int(a)&0x0000ffff)); //高16位位段地址，即基地址，后16位才是位移地址
a=(int*)(b+(int(a)&0x0000ffff));
}
else
{
b=(int*)(a-b);
a=(int*)(a-(int(b)&0x0000ffff));
b=(int*)(a+(int(b)&0x0000ffff));
}

（2）对一系列数据进行排序有哪几种方法

选择排序

冒泡排序

插入排序

快速排序

堆排序

归并排序

基数排序

希尔排序

位图排序

（3）解释长指针与短指针的不同

这与CPU寻址有关。在16位机器下，地址线为20位。但CPU处理能力只有16位。于是访问内存的方案是分段。即基址（段）+偏址是逻辑地址，从中可计算物理地址。基址（段）有16位，偏址也16位，寻址时将基址左移4位加偏址既可寻址。注意，段只有16位。其大小为2的16次方。即64K。
解释：
当你访问地址（指针）在一个段内，这是这个指针是近指针。当你访问地址（指针）不在一个段内，这是这个指针是远指针。因为它跨段寻址。所以“远”。
对于32为的CPU，32位的操作系统，其地址线为32，寻址能力达到4Gb,远远大于物理地址，它的一个段为4Gb（2的32次方，第31位加1）。实际上，这时谈论段已没有意义。所以在32位的操作系统上无近远指针之说。之所以存在，是因为兼容。

（4）给出strlen函数的实现方法

int strlen(const char *pStr)

{

　　int iLen = 0;

　　assert(NULL != pStr ); /* assert的功能是如果返回错误，则终止程序的运行 */

　　while(*pStr++ != '')

　　{

　　　　iLen ++;

　　}

　　return iLen ;

}

(5) 给出printf函数的实现方法

intprintf(const char *pcFormat, ...)

{

　　int i;

　　va_list tArg;

　　va_start(tArg, pcFormat);

　　i = vprintf(pcFormat, tArg);

　　va_end(tArg, pcFormat);

　　return i;

}

(6)实现双向链表的删除函数

 1 #include <stdio.h>
 2 
 3 PT_DoubleList ptDoubleListHeader;
 4  
 5 typedef struct DoubleList
 6 {
 7     char *pcName;
 8     struct DoubleList *pPre;
 9     struct DoubleList *pNext;
10 }T_DoubleList, PT_DoubleList;
11 
12 static int Delete_DoubleList(PT_DoubleList ptDoubleList, char *pcName)
13 {
14     PT_DoubleList *ptTemp;
15     
16     if(!ptDoubleList || !pcName || ptDoubleListHeader)
17     {
18         return -1;
19     }
20     else
21     {
22         ptTemp = ptDoubleListHeader;
23         
24         /* 头指针就相同 */
25         if(0 == strcmp(ptTemp->pcName, pcName))
26         {
27             /* 就一个头指针 */
28             if(!ptTemp->pNext)
29             {
30                 ptDoubleListHeader = NULL;
31                 return 0;
32             }
33             /* 头指针后还有元素 */
34             else
35             {
36                 ptDoubleListHeader = ptTemp->pNext;
37                 ptDoubleListHeader->pPre =  NULL;
38                 free(ptTemp);
39                 return 0;
40             }
41         }
42         
43         /* 头指针不相同 */
44         ptTemp = ptDoubleListHeader->pNext;
45         while(ptTemp)
46         {
47             if(0 == strcmp(ptTemp->pcName, pcName))
48             {
49                 /* 是最后一个元素 */
50                 if(!ptTemp->pNext)
51                 {
52                     ptTemp->pPre->pNext = ptTemp->pNext;
53                 }
54                 else
55                 {
56                     ptTemp->pPre->pNext = ptTemp->pNext;
57                     ptTemp->pNext->pPre = ptTemp->pPre;
58                 }
59                 
60                 free(ptTemp);
61                 return 0;
62             }
63             ptTemp = ptTemp->pNext;
64         }        
65         return -1;    
66     }
67 }

(7)实现双向链表的添加函数

 1 static int Register_DoubleList(PT_DoubleList ptDoubleList)
 2 {
 3     PT_DoubleList ptDoubleListCpy;
 4 
 5     if(!ptDoubleList)
 6     {
 7         return -1;
 8     }
 9     else
10     {
11         ptDoubleListCpy = malloc(struct DoubleList);
12         memcpy(ptDoubleListCpy, ptDoubleList, sizeof(struct DoubleList));
13         if(!ptDoubleListHeader)
14         {
15             ptDoubleListCpy->ptNext = ptDoubleListHeader; /* 第一次是NULL */
16             ptDoubleListCpy->pPre = NULL;
17             ptDoubleListHeader = ptDoubleListCpy;
18         }
19         else
20         {
21             /* 头插入的方式 */
22             ptDoubleListCpy->ptNext = ptDoubleListHeader;
23             ptDoubleListHeader->pPre = ptDoubleListCpy;
24             ptDoubleListHeader = ptDoubleListCpy;
25             ptDoubleListHeader->pPre = NULL;
26         }
27     }    
28 }