CC++基础及算法整理.doc

9月15日1、 static有什么用途（请至少说明两种）a) 限制变量的作用域b) 设置变量的存储域问题扩展：1.1、static全局变量与普通的全局变量有什么区别？static局部变量和普通局部变量有什么区别？static函数与普通函数有什么区别？全局变量(外部变量)的说明之前再冠以static 就构成了静态的全局变量。全局变量本身就是静态存储方式， 静态全局变量当然也是静态存储方式。 这两者在存储方式上并无不同。这两者的区别虽在于非静态全局变量的作用域是整个源程序， 当一个源程序由多个源文件组成时，非静态的全局变量在各个源文件中都是有效的。 而静态全局变量则限制了其作用域， 即只在定义该变量的源文件内有效， 在同一源程序的其它源文件中不能使用它。由于静态全局变量的作用域局限于一个源文件内，只能为该源文件内的函数公用， 因此可以避免在其它源文件中引起错误。从以上分析可以看出， 把局部变量改变为静态变量后是改变了它的存储方式即改变了它的生存期。把全局变量改变为静态变量后是改变了它的作用域， 限制了它的使用范围。static函数与普通函数作用域不同。仅在本文件。只在当前源文件中使用的函数应该说明为内部函数(static)，内部函数应该在当前源文件中说明和定义。对于可在当前源文件以外使用的函数，应该在一个头文件中说明，要使用这些函数的源文件要包含这个头文件static全局变量与普通的全局变量有什么区别：static全局变量只初使化一次，防止在其他文件单元中被引用;static局部变量和普通局部变量有什么区别：static局部变量只被初始化一次，下一次依据上一次结果值；static函数与普通函数有什么区别：static函数在内存中只有一份，普通函数在每个被调用中维持一份拷贝1.2、程序的局部变量存在于（堆栈）中，全局变量存在于（静态区 ）中，动态申请数据存在于（ 堆）中。问题扩展：1.2.1、什么是栈？什么是堆？ 在具体的C/C+编程框架中，这两个概念并不是并行的。深入到汇编级进行研究就会发现，栈是机器系统提供的数据结构，而堆是由C/C+函数库提供的。这两个概念可以从数据结构和系统两个层次去理解：1、从数据结构层次理解，栈是一种先进后出的线性表，只要符合先进后出的原则的线性表都是栈。至于采用的存储方式（实现方式）是顺序存储（顺序栈）还是链式存储（链式栈）是没有关系的。堆则是二叉树的一种，有最大堆最小堆，排序算法中有常用的堆排序。2、从系统层次理解，栈是系统为运行的程序分配的先进后出的存储区域。在学习bootloader时知道，在上电后初始化阶段要为各个工作模式下分配堆栈，这里的堆栈实际上就是指stack，堆栈的说法只是因为历史的原因。在执行函数时，函数内部局部变量的存储单元可以在栈上创建（针对CISC架构而言，RISC架构下，局部变量的存储单元是在寄存器上创建），函数执行结束时这些存储单元自动被释放。堆是系统管理的可以被程序利用的全局存储空间，动态内存分配就是从堆上分配。2、 引用与指针有什么区别？1) 引用必须被初始化，指针不必。2) 引用初始化后不能被改变，指针可以改变所指的对象。3) 不存在指向空值的引用，但是存在指向空值的指针。问题扩展：2.1什么是引用，什么是指针？引用只是一个变量的别名，程序中的应用不占据实际的内存空间，而指针则是一个数值，其意义就是被指向数据所存放的内存地址，而指针同样也是一个数据，他的存放需要占据内存空间。 使用引用来代表其它变量时，对于整个程序而言会更加安全。而使用指针可以使得整个程序更加灵活。9月16日1、 描述实时系统的基本特性在特定的时间内完成特定的任务，实时性与可靠性。2、 什么是平衡二叉树？左右子树都是平衡二叉树，且左右子树的深度差值的绝对值不大于13、 堆栈溢出一般是由什么原因造成的？没有回收垃圾资源4、什么函数不能声明为虚函数？constructor问题扩展：4.1 什么是虚函数？a) 简单地说，那些被virtual关键字修饰的成员函数，就是虚函数。虚函数的作用，用专业术语来解释就是实现多态性（Polymorphism），多态性是将接口与实现进行分离；用形象的语言来解释就是实现以共同的方法，但因个体差异而采用不同的策略。b) 虚函数用来表现基类和派生类的成员函数之间的一种关系. 虚函数的定义在基类中进行,在需要定义为虚函数的成员函数的声明前冠以关键字 virtual. 基类中的某个成员函数被声明为虚函数后,此虚函数就可以在一个或多个派生类中被重新定义. 在派生类中重新定义时,其函数原型,包括返回类型,函数名,参数个数,参数类型及参数的先后顺序,都必须与基类中的原型完全相同. 虚函数是重载的一种表现形式,是一种动态的重载方式4.2 为什么使用虚函数通过对象指针进行的普通成员函数调用,仅仅与指针的类型有关,而与此刻正指向什么对象无关.要想实现当指针指向不同对象时执行不同的操作,就必须将基类相应中的成员函数定义为虚函数4.3虚函数与重载函数的关系 一般的重载函数,函数的返回类型及所带的参数必须至少有一样不完全相同,只需函数名相同即可. 基类中定义的虚函数在派生类中重新定义时,其函数原型,包括返回类型,函数名,参数个数,参数类型及参数的先后顺序,都必须与基类中的原型完全相同. 重载虚函数时,若与基类中的函数原型出现不同,系统将根据不同情况分别处理: (1)仅仅返回类型不同,其余相同,系统会当作出错处理; (2)函数原型不同,仅仅函数名相同,系统会认为是一般的函数重载,将丢失虚特性4.4纯虚函数 仅仅用来为要从基类中派生的函数占据一个位置。 纯虚函数在基类中没有定义，它们被初始化为0。 任何用纯虚函数派生的类，都要自己提供该函数的具体实现。 定义纯虚函数 virtual void myMethod(void) = 0;5、 冒泡算法的时间复杂度是什么？O(N2)问题扩展：5.1根据什么评价一个算法与数据结构算法执行过程中所占用的存储单元数目和算法执行的时间效率。占用的存储单元数目和算法的执行效率一般是用其与结点数的关系给出的，前者称为空间复杂度，后者称为时间复杂度。5.2常见算法时间复杂度：O(1): 表示算法的运行时间为常量O(n): 表示该算法是线性算法O(2n): 二分查找算法O(n2): 对数组进行排序的各种简单算法，例如直接插入排序的算法。O(n3): 做两个n阶矩阵的乘法运算O(2n): 求具有n个元素集合的所有子集的算法O(n!): 求具有N个元素的全排列的算法优-劣O(1)O(2n)O(n)O(n2)0.000001&x-0.000001就认为X是与0相等的数 浮点数是非精确存储，只能设置一个精度，然后在允许误差内的就认为是相等的；对浮点型数比较的时候用=是不对的,如if(0=x)这样来与0值比较是不对的.9月17日1、 不能做switch()的参数的类型是：Switch()的参数不能为实型数问题扩展：1.1 什么是实型数？实型数就是通常说的浮点数，包括float、double、long double等等类型。实型文字常量可以用科学计数法形式或者普通十进制形式表示。如2e5,1.0这样的2、 局部变量能否和全局变量重名？答：能，局部会屏蔽全局。要用全局变量，需要使用“:”局部变量可以与全局变量同名，在函数内引用这个变量时，会使用到同名的局部变量，而不会用到全局变量。对于某些编译器而言，在同一个函数内可以定义多个同名的局部变量，比如在两个循环体内都定义一个同名的局部变量，而那个局部变量的作用域就在那个循环体内。3、 如何引有一个已经定义过的全局变量？答：extern可以用引用头文件的方式，也可以用extern关键字，如果用引用头文件方式引用某个在头文件中声明的全局变量，假定你将那个变量写错了，那么在编译期间会报错，如果你用extern方式引用时，假定你犯了同样的错误，那么在编译期间不会报错，而在连接期间报错。4、 全局变量可不可以定义在可被多个.c文件包含的头文件中？为什么？答：可以。在不同的.c文件中以static形式来声明同名全局变量。可以在不同的.c文件中声明同名的全局变量，前提是其中只能有一个.c文件中对此变量赋初值，此时连接不会报错。5、 队列和栈有什么区别？队列先进先出，栈后进先出问题扩展：5.1 什么是队列？队列简称队，是线性表的一种特殊形式，是一种应用很广的数据结构。对于它的所有插入在表的一端进行，所有删除在表的另一端进行。从一端进队，从另一端出队，即先进先出原则，称为先进先出表(First In First Out)。9月18日1、 关键字const有什么含意？我只要一听到被面试者说：const意味着常数，我就知道我正在和一个业余者打交道。去年Dan Saks已经在他的文章里完全概括了const的所有用法，因此ESP(译者：Embedded Systems Programming)的每一位读者应该非常熟悉const能做什么和不能做什么.如果你从没有读到那篇文章，只要能说出const意味着只读 就可以了。尽管这个答案不是完全的答案，但我接受它作为一个正确的答案。（如果你想知道更详细的答案，仔细读一下Saks的文章吧。）如果应试者能正确回答这个问题，我将问他一个附加的问题：下面的声明都是什么意思？const int a;int const a;const int *a;int * const a;int const * a const;/*/前两个的作用是一样，a是一个常整型数。第三个意味着a是一个指向常整型数的指针（也就是，整型数是不可修改的，但指针可以）。第四个意思a是一个指向整型数的常指针（也就是说，指针指向的整型数是可以修改的，但指针是不可修改的）。最后一个意味着a是一个指向常整型数的常指针（也就是说，指针指向的整型数是不可修改的，同时指针也是不可修改的）。如果应试者能正确回答这些问题，那么他就给我留下了一个好印象。顺带提一句，也许你可能会问，即使不用关键字 ，也还是能很容易写出功能正确的程序，那么我为什么还要如此看重关键字const呢？我也如下的几下理由：1) 关键字const的作用是为给读你代码的人传达非常有用的信息，实际上，声明一个参数为常量是为了告诉了用户这个参数的应用目的。如果你曾花很多时间清理其它人留下的垃圾，你就会很快学会感谢这点多余的信息。（当然，懂得用const的程序员很少会留下的垃圾让别人来清理的。）2) 通过给优化器一些附加的信息，使用关键字const也许能产生更紧凑的代码。3) 合理地使用关键字const可以使编译器很自然地保护那些不希望被改变的参数，防止其被无意的代码修改。简而言之，这样可以减少bug的出现。2、 数据声明（Data declarations）用变量a给出下面的定义a) 一个整型数（An integer） b)一个指向整型数的指针（ A pointer to an integer） c)一个指向指针的的指针，它指向的指针是指向一个整型数（ A pointer to a pointer to an integer） d)一个有10个整型数的数组（ An array of 10 integers） e) 一个有10个指针的数组，该指针是指向一个整型数的。（An array of 10 pointers to integers） f) 一个指向有10个整型数数组的指针（ A pointer to an array of 10 integers） g) 一个指向函数的指针，该函数有一个整型参数并返回一个整型数（A pointer to a function that takes an integer as an argument and returns an integer） h) 一个有10个指针的数组，该指针指向一个函数，该函数有一个整型参数并返回一个整型数（ An array of ten pointers to functions that take an integer argument and return an integer ）答案是： a) int a; / An integer b) int *a; / A pointer to an integer c) int *a; / A pointer to a pointer to an integer d) int a10; / An array of 10 integers e) int *a10; / An array of 10 pointers to integers f) int (*a)10; / A pointer to an array of 10 integers g) int (*a)(int); / A pointer to a function a that takes an integer argument and returns an integer h) int (*a10)(int); / An array of 10 pointers to functions that take an integer argument and return an integer 人们经常声称这里有几个问题是那种要翻一下书才能回答的问题，我同意这种说法。当我写这篇文章时，为了确定语法的正确性，我的确查了一下书。但是当我被面试的时候，我期望被问到这个问题（或者相近的问题）。因为在被面试的这段时间里，我确定我知道这个问题的答案。应试者如果不知道所有的答案（或至少大部分答案），那么也就没有为这次面试做准备，如果该面试者没有为这次面试做准备，那么他又能为什么出准备呢？3、写一个标准宏MIN ，这个宏输入两个参数并返回较小的一个。#define MIN(A,B) （A） = (B) ? (A) : (B) 这个测试是为下面的目的而设的：1) 标识#define在宏中应用的基本知识。这是很重要的。因为在 嵌入(inline)操作符 变为标准C的一部分之前，宏是方便产生嵌入代码的唯一方法，对于嵌入式系统来说，为了能达到要求的性能，嵌入代码经常是必须的方法。2)三重条件操作符的知识。这个操作符存在C语言中的原因是它使得编译器能产生比if-then-else更优化的代码，了解这个用法是很重要的。3) 懂得在宏中小心地把参数用括号括起来4) 我也用这个问题开始讨论宏的副作用，例如：当你写下面的代码时会发生什么事？least = MIN(*p+, b);（这个没看懂）9月23日1、 冒泡算法void BubbleSort(int* pData, int Count)int iTemp;for(int i=1;i=i;j-)if(pDatajpDataj-1)iTemp = pDataj-1;pDataj-1 = pDataj;pDataj = iTemp;main()int d5 = 1, 9, 3, 5, 2;BubbleSort(d, 5);for(int i=0;i5;i+)coutdiendl;2、 字符串逆序输出char* ReverseStr(char* src)int len = strlen(src);char* dest = (char*)malloc(len+1);char* d = dest;char* s = &srclen-1;while(len-!=0)*d+=*s-;*d=0;return dest;main()char* str = ReverseStr(hello,wordl!);printf(%sn,str);free(str);3、 Josehpus问题struct josephusint code;josephus * next;void main()int number;int interval;int start;coutnumber;coutinterval;coutstart;josephus * ptrJose = new josephusnumber;josephus * ptrCurrent = ptrJose;for(int i=1;inext=ptrJose+i%number;ptrCurrent-code=i;ptrCurrent=ptrCurrent-next;cout0 & start=number)if(start=1)ptrCurrent=&ptrJosenumber-1;elseptrCurrent=&ptrJosestart-2;elsecoutnext!=ptrCurrent)for(int i=0;inext;coutNo.setw(4)code is eliminated.next=ptrCurrent-next;ptrCurrent=pivot;coutendl;coutthe winner issetw(4)codeendl;delete ptrJose;4、 快速排序int data9 = 54,38,96,23,15,72,60,45,83;void quick_sort(int data, int low, int high)int i, j, pivot;if (low high)pivot=datalow;i=low; j=high; while(ij)while (i=pivot)j-;if(ij)datai+=dataj; / while (ij & datai=pivot)i+;if(ij) dataj-=datai; / datai=pivot; / quick_sort(data,low,i-1);quick_sort(data,i+1,high); void main()quick_sort(data, 0, 8);for(int i=0;i8;i+)coutdataiendl;下面是对这段程序的分析: “pivot=datalow;”表示将最低端即第一个元素作为枢轴记录，暂存到pivot中去，“while(ij)”表示当高低指针相遇时循环终止，否则继续。“while (i=pivot) j-;”表示从高端（即数组后面）开始搜索，直到搜索到一个比枢轴值小的某个元素，条件“dataj=pivot”用的是大于或等于号，可见，在搜索过程中若遇到相等的则跳过并继续搜索，条件“ij”不可少，因为在搜索过程中，low与high可能相遇，此“ij”跟外层while的条件“ij”无关，作用各不相同，外层while的条件“ij”是判断在进行从高端向低端搜索一趟、从低端向高端搜索一趟之后高低指针是否相遇，而前者却是在单向的搜索过程中为防止高低指针相遇。当经过“while (i=pivot)j-;”的搜索之后，搜索到一个比枢轴小的元素，因为在搜索完之后i、j可能相等，若相等，就没有交换的必要，因此紧接下面设置了一个判断“if(ij)”，若成立，那么就要将比枢轴记录小的记录移到低端“datai+=dataj;”，这里的“datai+”表示先使用了datai之后才加1，相当于“datai=dataj; i+;”两句的效果。为什么要i+？是因为刚交换的记录肯定比枢轴小，那么紧接下面的语句“while (ij & datai=pivot)”就少了一次不必要的比较（因为：datai=pivot必定成立，而ij在前面的if语句中已成立，则“ij & datai=pivot”必成立，若没有i+，while中的“ij & datai=pivot”在肯定成立的情况下执行了一次），提高了效率。执行“datai+=dataj;”之后，高端的dataj覆盖了datai的值，第一次覆盖时，覆盖的是datalow的值，因为最开始时，“pivot=datalow;”将最低端即第一个元素作为枢轴记录暂存到pivot中去了，所以不必担心，会丢失信息，由于dataj的值赋给了datai，那么dataj原来的位置j就可以看做一个空白，下一次覆盖时，就将低端的datai复制到这个位置。紧接下来的“while (ij & datai=pivot) i+;”是从低端向高端搜索，直到找到一个比枢轴大的元素，先进行判断“if(ij)”，若成立，如前所述，执行“dataj-=datai;”就将低端的datai复制到上次赋值后空出的j位置。如此反复，直到外层while的条件不成立，即i=j，即高低指针相遇，表示已经找到了枢轴记录pivot的最终位置i，执行“datai=pivot;”于是，枢轴记录移到最终位置。接下来的“quick_sort(data,low,i-1); quick_sort(data,i+1,high);”表示，对被pivot分开的左右子序列进行递归的快速排序。Char型转换成long型long myatol(const char* src)long l=0;const char* p = src;while(*p != 0)l = l*10 + (int)(*p - 0);p+;return l;反转字符串char* ReverseStr(char* src)int len = strlen(src);char* dest = (char*)malloc(len+1); /0char* d = dest;char* s = &srclen-1; /char* s = src + len - 1;while(len- != 0)*d+ = *s-;*d=0;return dest;main()char* test = hello world!;cout ReverseStr(test) 0);if(!sign)n = -n;char* d = dest;do*(d+) = (char)(n%10 + 0) ;while(n /= 10) 0);if(!sign)*(d+)=-;*d=0;char* result = ReverseStr(dest); return result;main()int i=-321;char* dest = (char*)malloc(20);cout myitoa(i, dest) endl;Int型转char*char* itoh(int n)char* buff = (char*)malloc(11);buff0=0;buff1=x;buff10=0;char* temp = buff + 2;for(int i=0;i8;i+)tempi=(char)(n28);tempi=tempi=0 ? tempi : tempi+16;tempi=tempi10 ? tempi+48 : tempi+55;return buff;main()int i=120;cout itoh(i) endl;递归反序输出void inverse(char* p)if(*p = 0)return;inverse( p+1 );printf(%c, *p);main()char* test = hello world!;inverse(test);coutendl;求组合数：求n个数的组合int N,nom100; /*N存放在排列的数的个数，nom存要要排列的数*/ /*/ void inint() /*接收输入函数*/ int i; printf(please input the number n= );scanf(%d,&N); printf(please input %d numbers: n, N);for(i=0;iN;i+) scanf(%d,&nomi); /*/ void swap(int *a,int *b) /*交换函数*/ int temp; temp=*a; *a=*b; *b=temp; /*/ void print() /*打印输出函数*/ int i; for(i=0;iN;i+) printf(%d ,nomi); printf(n); /*/ int sort(int k) /*回溯函数*/ int i; if(k=N) print(); return(0); for(i=k;i=k;i-) ak=i; if (k1) comb(i-1,k-1); else for (j=a0;j0;j-) printf(%2d,aj); printf(n); void main() int n, m;printf(please input two number:n);scanf(%d, &n);scanf(%d, &m);a0=m; printf(combination result: n);comb(n, m); 测试please input two number:53combination result: 5 4 3 5 4 2 5 4 1 5 3 2 5 3 1 5 2 1 4 3 2 4 3 1 4 2 1 3 2 1题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：struct ListNode int m_nKey; ListNode* m_pNext;分析：这是一道很有意思的面试题。该题以及它的变体经常出现在各大公司的面试、笔试题中。看到这道题后，第一反应是从头到尾输出比较简单。于是很自然地想到把链表中链接结点的指针反转过来，改变链表的方向。然后就可以从头到尾输出了。反转链表的算法详见本人面试题精选系列的第19题，在此不再细述。但该方法需要额外的操作，应该还有更好的方法。接下来的想法是从头到尾遍历链表，每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始输出结点的值，此时输出的结点的顺序已经反转过来了。该