面试宝典之C++面试知识分享

2012.07.201.strcpy函数/*static*/char*my_strcpy(char*pDest,constchar*pSrc){ assert((pDest!=NULL)&&(pSrc!=NULL)); char*pRet=pDest;//recordthepositionofdestination. while((*pRet++=*pSrc++)!='\0') { NULL; } returnpDest;}返回值用char*是为了实现链式表达式而返回具体值，如intlength=strlen(strcpy(strDest,“helloworld”));关键点：①static方法：使某个函数只在一个源文件中有效，不能被其他源文件所用。（1）它允其他源文件建立并使用同名的函数，而不相互冲突。（2）声明为静态的函数不能被其他源文件所调用，因为它的名字不能得到。②源字符串用const：保证源字符的内容不被改变(地址可以变)。constchar*str涉及到的字符串，指针的地址可以变，但是指针指向地址的内容不能变；char*conststr涉及到的指针内容不能改变。提高性能的方法：staticchar*my_strcpy2(char*pDest,constchar*pSrc){ assert((pDest!=NULL)&&(pSrc!=NULL)); char*s=(char*)pSrc; intdelt=pDest-pSrc;//地址之差 while((s[delt]=*s++)!='\0');//s[delt]实为*(s+delt) returnpDest;}char*my_memset(char*pDst,intval,size_tsize){ char*start=pDst; while(size>0) { *pDst=(char)val; pDst=pDst+1; size--; } returnstart;}void*my_memset(void*pDst,intval,size_tsize)//库函数写法{ void*start=pDst; while(size>0) { *(char*)pDst=(char)val; pDst=(char*)pDst+1; size--; } returnstart;}memcpy是不考虑内存重叠的。void*my_memcpy(void*pDst,constvoid*pSrc,size_tsize){ void*ret=pDst; while(size>0) { *(char*)pDst=*(char*)pSrc; pDst=(char*)pDst+1; pSrc=(char*)pSrc+1; size--; } returnret;}void*my_memmove(void*pDst,constvoid*pSrc,size_tsize){ void*ret=pDst; if((char*)pDst<=(char*)pSrc||(char*)pSrc+size>=pDst)//内存没有重叠时与memcpy一样 { while(size>0) { *(char*)pDst=*(char*)pSrc; pDst=(char*)pDst+1; pSrc=(char*)pSrc+1; size--; } } else//OverLappingbuffers内存重叠 { pDst=(char*)pDst+size-1; pSrc=(char*)pSrc+size-1; while(size>0) { *(char*)pDst=*(char*)pSrc; pDst=(char*)pDst-1; pSrc=(char*)pSrc-1; size--; } } returnret;}2.赋值语句inti=1;intmain(){ inti=i;//undefinedvalue.里面定义了i之后就屏蔽了全局变量 return0;}3.求一个数转换成二进制的数中的1的个数的求法：intCount1forBinary(intx){ intcount=0; while(x) { count++; x=x&(x-1);//每次消去最后一个1 } returncount;}补充：判断一个数是不是2的N次方的方法：！(x&(x-1))4.C语言中printf和C++中cout计算参数时是从右到左压栈的。printf("%d,%d",*ptr,*(++ptr));//输出的结果应该是一样的cout<<*ptr<<"\n"<<*(++ptr)<<endl;//输出的结果应该是一样的5.优先级：++--优先于*&(取值取址)优先于sizeof()优先于*/%优先于<<>>6.求平均值：intf(intx,inty){ return(x&y)+((x^y)>>1);}7.不用判断语句求两个数中间比较大的数max=(a+b)+abs(a-b)/2;8.不用中间变量，交换a、b的值方法一：a=a+b;b=a-b;a=a-b;//a+b可能会越界方法二：a=a^b;b=a^b;a=a^b;2012.07.211.C++的类中的数据成员加上mutable后，修饰为const的成员函数，就可以修改它了。intfun()const{ /****/只能调用const的变量，不能改变}cout<<setw(tmp)<<setfill(‘‘)<<tmp<<endl;//setw()为设置宽度，setfill()为设置填充字符2.sizeof的用法charss3[100]="0123456789"; cout<<"sizeof(ss3):"<<sizeof(ss3)<<endl;//100，预分配的大小 cout<<"strlen(ss3):"<<strlen(ss3)<<endl;//10，内部实现是用一个循环计算字符串的长度，直到“\0”为止。 intss4[100]; cout<<"sizeof(ss4):"<<sizeof(ss4)<<endl;//400cout<<"strlen(ss4):"<<strlen(ss4)<<endl;//错误，因为strlen的参数只能是char*，且必须是以”\0”结束。char*str1=(char*)malloc(100); cout<<"sizeof(str1):"<<sizeof(str1)<<endl;//4，指针的大小cout<<"sizeof(*str1):"<<sizeof(*str1)<<endl;//1，第一个字符sizeof(struct)时，struct要考虑对齐，一般都是取结构体中最长的来对齐，结构体默认对齐长度为8。sizeof()计算栈中分配的大小，因此静态变量等全局数据区内的数的大小是不会计算在内的。sizeof()按字节大小计算。内存对齐的规则：1、

对于结构的各个成员，第一个成员位于偏移为0的位置，以后每个数据成员的偏移量必须是min(#pragmapack()指定的数，这个数据成员的自身长度)

的倍数。2、

在数据成员完成各自对齐之后，结构(或联合)本身也要进行对齐，对齐将按照#pragmapack指定的数值和结构(或联合)最大数据成员长度中，比较小的那个进行。默认的#pragmapack

指定的值为8，如果最大数据结构成员长度为int，则结果本身按照4字节对齐，结构总大小必须为4的倍数。内存对齐的主要作用是：1、

平台原因(移植原因)：不是所有的硬件平台都能访问任意地址上的任意数据的；某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。2、

性能原因：经过内存对齐后，CPU的内存访问速度大大提升。CPU把内存当成是一块一块的，块的大小可以是2，4，8，16字节大小，因此CPU在读取内存时是一块一块进行读取的。块大小称为memoryaccessgranularity（粒度）

本人把它翻译为“内存读取粒度”。原因在于，为了访问未对齐的内存，处理器需要作两次内存访问；而对齐的内存访问仅需要一次访问。与strlen()的区别，具体实现①sizeof是运算符，strlen是函数；②sizeof操作符的结果类型是size_t；③sizeof可以用类型做参数，还可以用函数做参数，而strlen只能用char*的变量做参数，且必须是以’\0’结尾的；④大部分编译器在编译时就计算sizeof的值，是类型或者变量的长度，而strlen在运行时计算，计算字符串的长度，而不是内存的大小；⑤sizeof后如果是变量名可以不加括号。intmy_strlen(constchar*str){ assert(str!=NULL); intlen=0; while((*str++)!='\0')//先执行*，再执行++ { len++; } returnlen;}intmy_strlen2(constchar*str)//库函数{ constchar*eos=str; while(*eos++); return(eos-str-1);}3.程序中常规的的变量，都是从大地址向小地址放的（存放在一个堆栈中，堆栈以大地址为底）。4.数组作为参数传给函数时传的是指针而不是数组，传递的是数组的首地址，如fun(char[8])、fun(char[])都等价于fun(char*)，编译器是不知道数组的大小的。5.类虚继承后，会添加虚表。虚继承是为了解决多重继承中的重定义而产生的。classB:publicvirtualA{}虚基类：在虚继承体系中的通过virtual继承而来的基类，如A。6.inline内联函数，在调用的地方不是跳转，而是把代码直接写到那里。与宏函数相比，内联函数要做类型检查。（const与宏的差别也是const有类型设置，会检查类型。）对于短小的代码，inline减少了普通函数调用时的资源消耗，可以带来效率的提升，而它会增加空间的消耗。2012.07.231.指针和引用的区别引用不能为空，内容不能改变，使用前不会测试它的合法性；而指针正好相反。定义引用时必须初始化(const变量一样)。2.地址值相减，转换成int之后要/sizeof(int)。P68int*m=(int*)2000; int*n=(int*)1000; printf("%d\n",m-n);//-2503.const指针：constint*a；可以执行a++，但是不能执行(*a)++指向const的指针：int*const；可以执行(*a)++，但不能执行a++4.数组名本身就是指针，加个&就变成了双指针，即二位数组。inta[]={1,2,3,4,5}; int*ptr=(int*)(&a+1); cout<<ptr-a<<endl;//5，ptr指向下一行5.malloc与free是C++/C的标准库函数，而new/delete是C++的运算符。对于非内部数据结构的对象而言，只用malloc/free无法满足动态对象的要求。malloc和free是库函数而不是运算符，不在编译器控制权限之内，不能够执行构造函数和析构函数。6.智能指针auto_ptr是安全指针，包含在空间std中，用它构造的对象，析构函数总在退栈过程中被调用。auto_ptr<Object>pObj(newObject);auto_ptr<Object>source(){returnnewObject;}7. vector<CDemo>*a1=newvector<CDemo>(); a1->push_back(d1);//浅拷贝 deletea1;//释放vector对象，vector包含的元素也同时释放了8.静态模板类：template<classT>template用法STL9.一个空类默认产生的成员函数：默认构造函数、析构函数、拷贝构造函数、赋值函数。拷贝构造函数：CExample(const

CExample&C)就是我们自定义的拷贝构造函数。可见，拷贝构造函数是一种特殊的构造函数，函数的名称必须和类名称一致，它的唯一的一个参数是本类型的一个引用变量，该参数是const类型，不可变的。例如：类X的拷贝构造函数的形式为X(X&x)。当用一个已初始化过了的自定义类类型对象去初始化另一个新构造的对象的时候，拷贝构造函数就会被自动调用。也就是说，当类的对象需要拷贝时，拷贝构造函数将会被调用。以下情况都会调用拷贝构造函数：

一个对象以值传递的方式传入函数体

一个对象以值传递的方式从函数返回

一个对象需要通过另外一个对象进行初始化。深拷贝和浅拷贝可以简单理解为：如果一个类拥有资源，当这个类的对象发生复制过程的时候，资源重新分配，这个过程就是深拷贝，反之，没有重新分配资源，就是浅拷贝。CA(constCA&C)

{

a=C.a;

str=newchar[a];//深拷贝

if(str!=0)

strcpy(str,C.str);

}10.class和struct的区别：class中变量默认是private，struct中变量默认是public。C++中存在struct是为了兼容以前的C项目。11.类中，初始化列表的初始化顺序是根据成员变量的声明顺序来执行的。常量必须在构造函数的初始化列表里初始化或者将其设置成static。classA{ A(){constintSize=0;}};或者classA{ staticconstintSize=0;};12.MFC中Cobject的析构函数是虚拟的。原因：多态的情况，CBase*p=newCChild();析构时，如果不是virtual则会调用父类的析构函数，而实际new的子类的空间可能不会完全释放；而如果是virtual的析构函数，则会调用虚拟指针执行的子类的析构函数来释放空间。13.strcpy,strncpy,strlcpystrcpy是依据/0作为结束判断的，如果to的空间不够，则会引起bufferoverflow。strcpy(char*to,constchar*from){

char*save=to;

for(;(*to=*from)!='/0';++from,++to);

return(save);}strncpy(path,src,sizeof(path)-1);//要赋值的长度path[sizeof(path)-1]='/0';len=strlen(path);strlcpy(char*dst,constchar*src,size_tsize);而使用strlcpy，就不需要我们去手动负责/0了，仅需要把sizeof(dst)告之strlcpy即可：strlcpy(path,src,sizeof(path));len=strlen(path);if(len>=sizeof(path))

printf("srcistruncated.");并且strlcpy传回的是strlen(str)，因此我们也很方便的可以判断数据是否被截断。2012.07.241.String类P112classString{public: String(constchar*str=NULL);//普通构造函数 String(constString©);//拷贝构造函数 ~String(); String&operator=(constString&other);//赋值函数private: char*m_data;};String::String(constchar*str/*=NULL*/){ if(NULL==str) { m_data=newchar[1]; m_data='\0'; } else { intlength=strlen(str); m_data=newchar[length+1]; strcpy(m_data,str); }}String::~String(){ delete[]m_data;}String::String(constString©){ intlength=strlen(copy.m_data); m_data=newchar[length+1]; strcpy(m_data,copy.m_data);}String&String::operator=(constString&other){ if(this==&other) { return*this; } delete[]m_data; m_data=newchar[strlen(other.m_data)+1]; strcpy(m_data,other.m_data); return*this;}调用：Strings1("hello"); Strings2=s1;或者Strings2(s1);//拷贝构造函数 Strings3; s3=s2;//赋值函数2.重载在编译期间就确定了，是静态的，重载和多态无关。真正与多态相关的是覆盖（虚函数）。当定义了父类的虚函数后，父类指针根据赋给它的不同的子类的指针，动态地调用属于子类的该函数，这样的函数调用在编译期间是无法确定的，调用子类的虚函数的地址无法给出。封装可以隐藏细节，使得代码模块化，继承可以扩展存在的代码模块，它们都是为了代码重用。而多态是为了接口重用。override—覆盖（派生类函数覆盖基类virtual函数），overload—重载（语义、功能相似的几个函数用同一个名字表示，但参数或返回值不同），overwrite—重写（派生类的函数屏蔽了与其同名的基类函数）。重写：（1）如果派生类的函数与基类的函数同名，但是参数不同。此时，不论有无virtual关键字，基类的函数将被隐藏（注意别与重载混淆）。

（2）如果派生类的函数与基类的函数同名，并且参数也相同，但是基类函数没有virtual关键字。此时，基类的函数被隐藏（注意别与覆盖混淆）。classParent{public: voidF() { cout<<"ParentF().\n"; } virtualvoidG() { cout<<"ParentG().\n"; } intAdd(intx,inty) { returnx+y; } floatAdd(floatx,floaty)//overload { returnx+y; }};classChild:publicParent{ voidF()//overwrite { cout<<"ChildF().\n"; } virtualvoidG()//override { cout<<"ChildG().\n"; }};Child*child; Parent*p=(Parent*)child;(或者Parent*p1=newChild;p1->G();) p->F();//ParentF(). p->G();//ChildG().3.voidfunction()const;//常成员函数,它不改变对象的成员变量.也不能调用类中任何非const成员函数。4.析构函数可以是private的。classTest1{public: Test1() { cout<<"Constructor."<<endl; }; voidDeleteTest1() { cout<<"Deletetest1."<<endl; deletethis; }private: ~Test1() { cout<<"Destructor."<<endl; }};Test1*t1=newTest1(); //deletet1;编译的时候会报错，因为析构函数时private的，delete调用不到它 t1->DeleteTest1();5.构造函数不能是virtual的。构造函数可以是private的，但是该类不能被实例化，因为不能执行初始化。private的构造函数不会生成默认的拷贝构造函数。6.构造函数是从最初始的基类开始构造，各个类的同名变量没有形成覆盖，都是单独的变量。接口的调用是就近的，优先调用离自己最近的接口（从当前层往上向父辈、祖父辈）。7. A*pa=newA(); B*pb=(B*)pa;//始终是A类空间 deletepa,pb;//删除所指向的地址，但pa、pb指针并没有删除，也就是悬浮指针 pa=newB();//B类的空间 pb=(B*)pa;8.子类继承父类时，不管什么继承方式，子类都会继承父类的任何数据成员和方法，不管数据成员和方法是什么类型，只是因为继承方式或类型的原因而使这些数据成员或方法在子类不可见，不能访问。classSizeTest{private: intm_data;};classSizeTestSub:privateSizeTest{};cout<<sizeof(SizeTest)<<""<<sizeof(SizeTestSub)<<endl;//449.私有继承时，基类的成员只能由直接派生类访问，而无法往下继承。10.虚继承classVA{ chark[3];//4public: virtualvoidaa(){}//4};classVB:publicvirtualVA//8或4{ charj[3];//4public: virtualvoidbb(){}//加到的虚表最后};classVC:publicvirtualVB//8或4{ chari[3];//4public: virtualvoidcc(){}//加到的虚表最后};cout<<sizeof(VA)<<""<<sizeof(VB)<<""<<sizeof(VC)<<endl;//82032/81624虚继承时用在多重继承时，当一个类继承的多个父类都继承自同一个祖父类时，这个类中会存在多个祖父类的成员函数和数据成员，调用该成员函数和数据成员时，编译器无法辨别访问的是哪一个而报错。若采用虚继承，系统碰到多重继承时会自动载入一个祖父类的拷贝，当再次请求载入祖父类时就回被忽略，保证了继承类成员函数的唯一性。虚继承和虚函数虽然有相似的地方，但是他们之间绝对没有任何联系。classVehicle{public: voidShowVehicle() { cout<<"Thisisthevehicle."<<endl; } intm_data;};classCar:virtualpublicVehicle{};classBoat:virtualpublicVehicle{};classAmphibiancar:publicCar,publicBoat{};Amphibiancar*amp=newAmphibiancar(); amp->ShowVehicle(); amp->m_data=10; cout<<sizeof(Vehicle)<<""<<sizeof(Car)<<""<<sizeof(Boat)<<""<<sizeof(Amphibiancar)<<endl;//8121216classA{public: intm_data1;};classB:virtualpublicA{public: voidShow() { cout<<"Bshow."<<endl; }private: intm_data2;};没有虚继承时，内存布局为：1>classB size(8):1> +---1> |+---(baseclassA)1>0 ||m_data11> |+---1>4 |m_data21> +---添加虚继承后，内存布局为：1>classB size(12):1> +---1>0 |{vbptr}1>4 |m_data21> +---1> +---(virtualbaseA)1>8 |m_data11> +---1>1>B::$vbtable@:1>0 |01>1 |8(Bd(B+0)A)1>1>1>vbi: classoffseto.vbptro.vbtefVtorDisp1>A80409.虚函数：classA{public: intm_data1; virtualvoidShow() { cout<<"Ashow."<<endl; } virtualvoidShow2() { cout<<"Ashow2."<<endl; }};classB:publicA{public: voidShow() { cout<<"Bshow."<<endl; } virtualvoidShow3() { cout<<"Bshow3."<<endl; }private: intm_data2;};类添加虚函数之后，在类内存的最顶端会添加一个vfptr的指针，指向一个名为vftable的表，表内容如下：1>A::$vftable@:1> |&A_meta1> |01>0 |&A::Show//第一个虚函数1>1 |&A::show2//第二个虚函数类的布局如下：1>classA size(12):1> +---1>0 |{vfptr}1>4 |m_data11> +---如果B继承自A，则B会先把A的数据成员和方法拷过来，再添加自己的。1>classB size(20):1> +---1> |+---(baseclassA)1>0 ||{vfptr}1>4 ||m_data11> |+---1>8 |m_data21> +---10.虚函数和虚继承结合。1>classB size(20):1> +---1>0 |{vfptr}//先放虚函数1>4 |{vbptr}//再放虚继承1>8 |m_data21> +---1> +---(virtualbaseA)1>12 |{vfptr}1>16 |m_data11> +---1>1>B::$vftable@B@:1> |&B_meta1> |01>0 |&B::Show31>1>B::$vbtable@:1>0 |-41>1 |8(Bd(B+4)A)1>1>B::$vftable@A@:1> |-121>0 |&B::Show1>1 |&A::Show21>1>B::Showthisadjustor:121>B::Show3thisadjustor:01>1>vbi: classoffseto.vbptro.vbtefVtorDisp1>A124402010.07.251.dynamic_cast<父类>(子类)，将子类强制转换为父类C*pC=newC;B*pB=dynamic_cast<B*>(pC);//C继承自B类若是比较pB==pC，则pB会隐式转换为(C*)pB。2.privateconstructor/destructorprivateconstructor：防止类直接实例化，可以通过调用静态方法来产生类。(单例模式)classPoint{public: staticPointrectangular(floatx,floaty);//Rectangularcoord's staticPointpolar(floatradius,floatangle);//Polarcoordinates //Thesestaticmethodsaretheso-called"namedconstructors"private: Point(floatx,floaty);//Rectangularcoordinates floatx_,y_;};inlinePoint::Point(floatx,floaty):x_(x),y_(y){}inlinePointPoint::rectangular(floatx,floaty){returnPoint(x,y);}inlinePointPoint::polar(floatradius,floatangle){returnPoint(radius*std::cos(angle),radius*std::sin(angle));}3.C++运行时开销特性包括：①虚基类；（虚基类表指针的空间开销，指针引用的时间开销）②虚函数；（同上）③RTTI(dynamic_cast和typeid)；（typeid用于获取一个对象或引用的确切类型）④异常；⑤对象的构造和析构。RTTI是RuntimeTypeInformation缩写，作用是动态判别执行时期的类型。动态映射dynamic_cast<目标*><源指针>，先恢复源指针的RTTI信息，再取目标的RTTI信息，比较两者是否相同，或者是目标类型的基类，由于它要检查一长串的基类列表，故动态映射的开销比typeid大。2012.07.261.static_cast：编译器隐式执行任何类型转换都显示完成。编译时使用类型信息执行转换，在转换执行必要的检测（指针越界、类型检查），其操作是安全的。const_cast：转换去掉对象的const属性。reinterpret_cast：通常为操作数的位模式提供较低层的重新解释。dynamic_cast：运行时检查，用于继承体系中进行安全的向下转换downcast，即基类的指针/引用到派生类的指针/引用的转换。当然也可以进行向上转换，但是没必要，因为完全可以用虚函数实现。2.移位是最有效的计算乘/除算法的运算之一。3.内存中，数据低位字节存入低地址，高位字节存入高地址，而数据的地址采用它的低地址来表示。4.设置变量某个bit位，常用方法：define和bitmask操作。#defineBIT_MASK(bit_pos)(0x01<<(bit_pos))a|=BIT_MASK(3);//设置第3位为1a&=~BIT_MASK(3);//清除第3位，设为05.volatile(挥发性)：语法和const一样，但是volatile的意思是“在编译器认识的范围外，这个数据可能被改变”。不知什么原因，环境正在改变数据（可能通过多任务处理），所以，volatile告诉编译器不要擅自做出有关数据的任何假定（在优化期间特别重要）。6.const只读。合理的使用const可以使编译器很自然的保护那些不希望被改变的参数，防止其被无意的代码修改。7.在类中的static成员函数属于整个类所拥有，这个函数不接收this指针，因而只能访问类的static变量。static变量分配在全局区，但是使用范围会根据具体情况来限制。2012.07.281.单链表的创建、插入、删除、计算长度、逆置、求倒数第K个、求中间节点、排序

#defineMAX_DATA100typedefstructListNode{ intdata; structListNode*next;}LIST;LIST*CreateList(intn)//nislength{ srand(unsignedint(time(NULL))); if(0>=n) { returnNULL; } LIST*head=newLIST; head->data=rand()%MAX_DATA; head->next=NULL; LIST*p=head; inti=n; i--; while(i>0) { LIST*qTemp=newLIST; qTemp->data=rand()%MAX_DATA; qTemp->next=NULL; p->next=qTemp; p=qTemp; i--; } returnhead;}voidPrintList(constLIST*head){ inti=0; cout<<"Listdata:\n"; while(NULL!=head) { i++; cout<<head->data<<"\t"; head=head->next; if(i%7==0) { cout<<"\n"; } } cout<<"\n============================="<<endl;}intInsertList(LIST*&head,intn,intdata){ LIST*p; p=newLIST; p->data=data; p->next=NULL; if(NULL==head) { head=p; return1; } if(1==n) { p->next=head; head=p; return1; } inti=1; LIST*q=head; while(i<n-1&&q!=NULL) { i++; q=q->next; } if(NULL==q) { cout<<"Can'tfindthe"<<n<<"thdata!"<<endl; return-1; } p->next=q->next; q->next=p; return1;}intDeleteList(LIST*&head,intn){ cout<<"Deletethe"<<n<<"thdata."<<endl; inti=1; LIST*p=head; if(NULL==head) { cout<<"Listisempty!!"<<endl; return-1; } if(1==n)//deletehead { head=head->next; deletep; p=NULL; return1; } LIST*q; while(NULL!=p&&i<n) { i++; q=p; p=p->next; } if(NULL==p) { cout<<"Can'tfindthe"<<n<<"thdata!"<<endl; return-1; } q->next=p->next; p->next=NULL; deletep; p=NULL; return1;}intGetLength(constLIST*head){ intlength=0; while(NULL!=head) { length++; head=head->next; } returnlength;}voidReverse_Method1(LIST*&head)//Reversethearrowinlist{ if(NULL==head||NULL==head->next) { return; } LIST*p=head; LIST*q=head->next; LIST*r=q; p->next=NULL; while(NULL!=q) { r=q->next; q->next=p; p=q; q=r; } head=p;}voidReverse_Method2(LIST*&head)//Headinsert{ if(NULL==head||NULL==head->next) { return; } LIST*p=head->next; LIST*q; head->next=NULL; while(NULL!=p) { q=p->next; p->next=head; head=p; p=q; }}intFindReverseN(LIST*head,intn)//找链表的倒数第n个节点，利用窗口的思想{ if(NULL==head) { cout<<"Listisempty!!"<<endl; return-1; } LIST*p=head; inti=0; while(i<n&&NULL!=head) { head=head->next; i++; } if(i!=n) { cout<<"Lististooshort!!"<<endl; return-1; } while(NULL!=head) { head=head->next; p=p->next; } if(NULL==p) { cout<<"Error!!"<<endl; return-1; } cout<<"Thereverse"<<n<<"datais:"<<p->data<<endl; return1;}intFindMiddle(LIST*head){ LIST*p=head; if(NULL==head) { cout<<"Listisempty!"<<endl; return1; } if(head->next==NULL) { cout<<"Themiddledatais:"<<head->data<<endl; } while(NULL!=head&&NULL!=head->next) { p=p->next; head=head->next->next; } if(NULL!=p) { cout<<"Themiddledatais:"<<p->data<<endl; return1; } else { cout<<"Error!"<<endl; return-1; }}voidSortList(LIST*&head)//Insert{ if(NULL==head||NULL==head->next) { return; } LIST*p=head->next; LIST*q,*r; head->next=NULL; while(NULL!=p) { r=p->next; if(head->data>p->data) { p->next=head; head=p; } else { q=head; while(NULL!=q->next&&q->next->data<p->data)//qnext { q=q->next; } p->next=q->next; q->next=p; } p=r; }}2.双链表的创建、插入、删除DoubleList*CreateDoubleList(intn){ if(0==n) { returnNULL; } srand(unsignedint(time(NULL))); DoubleList*head=newDoubleList; head->data=rand()%MAX_DATA; head->prev=NULL; head->next=NULL; if(1==n) { returnhead; } n--; DoubleList*p=head; while(n>0) { DoubleList*q=newDoubleList; q->data=rand()%MAX_DATA; q->next=NULL; q->prev=p; p->next=q; p=q; n--; } returnhead;}intInsertDoubleList(DoubleList*&head,intn,intdata){ DoubleList*q=newDoubleList; q->data=data; if(1==n) { q->prev=NULL; q->next=head; head=q; return1; } DoubleList*p=head; n--; n--; while(n>0&&p!=NULL) { p=p->next; n--; } if(NULL==p) { return-1; } q->next=p->next; q->prev=p; if(p->next==NULL) { } else { p->next->prev=q; } p->next=q; return1;}intDeleteDoubleList(DoubleList*&head,intn){ DoubleList*p=head; if(1==n) { head=head->next; head->prev=NULL; p->next=NULL; deletep; } n--; while(n>0&&NULL!=p) { p=p->next; n--; } if(NULL==p) { return-1; } p->prev->next=p->next; if(p->next!=NULL) { p->next->prev=p->prev; } p->next=NULL; p->prev=NULL; deletep; return1;}3.循环链表，约瑟夫环问题：n个节点，从第k个人报数，数到m出列voidCirleFunction(LIST*head,intm){ LIST*p=head; LIST*q; while(p->next!=p) { inti=0; q=p; while(i<m) { q=p; p=p->next; i++; } q->next=p->next; cout<<p->data<<""; deletep; p=q; } cout<<p->data;}4.队列：出队、入队voidCQueue::Push(intiData){ if(front==(rear+1)%MAX_DATA)//队满了 { cout<<"Queueisfull!"<<endl; } else { data[rear]=iData; rear=(rear+1)%MAX_DATA; cout<<"Queuepusheddata:"<<iData<<endl; }}intCQueue::Pop(){ if(front!=rear) { inttemp=data[front]; front=(front+1)%MAX_DATA; cout<<"Queuepopdata:"<<temp<<endl; returntemp; } else { cout<<"Queueisempty!"<<endl; return-1; }}5.栈：出栈、入栈voidCStack::Push(intiData){ if(top<MAX_DATA-1) { top++; data[top]=iData; cout<<"Pusheddata:"<<iData<<endl; } else { cout<<"Stackisfull!"<<endl; }}intCStack::Pop(){ if(-1<top) { inttemp=data[top]; top--; cout<<"Popeddata:"<<temp<<endl; returntemp; } else { cout<<"Stackisempty!"<<endl; return-1; }}6.调用函数时，首先进行参数压栈，一般情况下压栈顺序为从右到左，最后压函数地址；windows平台中，栈是从上到下生长的（高地址往低地址）。7.两个栈实现一个队列：一个栈做入队，一个栈做出队。voidCQueue_with_Stack::Push(intiData){ if(stack2.IsFull()==false) { stack2.Push(iData); } else { if(stack1.IsFull()==false) { while(stack1.IsFull()==false) { stack1.Push(stack2.Pop()); } stack2.Push(iData); } else { cout<<"Queuewithstackisfull!"<<endl; } }}intCQueue_with_Stack::Pop(){ if(stack1.IsEmpty()==false) { returnstack1.Pop(); } else { if(stack2.IsEmpty()==false) { while(stack2.IsEmpty()==false) { stack1.Push(stack2.Pop()); } returnstack1.Pop(); } else { cout<<"Queuewithstackisempty!"<<endl; return-1; } }}8.stack和heap的差别：stack：编译器自动分配和释放，存放函数的参数值、局部变量的值等。heap：一般由程序员分配和释放，若程序员不释放，程序结束时可能由操作系统回收。2012.07.291.进程的每个线程都有私有的栈，所以每个线程虽然代码一样，但本地变量的数据都是互不干扰的。2.对于操作系统来说，new一块内存，windows不仅分配给你内存，还用4字节在那内存后作为内存分配边界。3.中序遍历二叉搜索树可以得到一个关键字的有序序列。4.判断两个树相等P190关键点：左右子树可以互换。5.数据库范式1NF：所有属性的值域中每一个值都不可再分解的值。2NF：每个非主属性完全函数依赖与R的某个候选值。3NF：每个非主属性都不传递以来于R的候选键。BCNF：每个属性都不传递依赖于R的候选键。4NF：设R是一个关系模式，D是R上的多值依赖集合。如果D中成立非平凡多值依赖X->->Y时，X必是R的超键，那么R是第四范式。6.游标用于定位结果集的行。通过判断全局变量@@FETCH_STATUS可以判断其是否到了最后。通常次变量不等于0表示出错或到了最后。VC中_RecordSet判断是不是到了最后用ret->adoEOF()!=0。7.防止SQL注入式攻击：①替换单引号为2个引号；②删除用户输入内容中所有连字符；③用来执行查询的数据库账户，限制其权限；④用存储过程来执行所有查询；⑤检查用户输入合法性；⑥用户登录名称密码等数据加密保存；=7\*GB3⑦检查提取数据的查询所返回的记录数量。8.聚集索引的顺寻就是数据的物理存储顺序，一个表中最多有一个聚集索引。聚集索引对于那些经常要搜索范围值的列特别有效，使用聚集索引找到包含第一个值的行后，便可以确保包含后序索引值的行在物理相邻。非聚集索引是索引顺序与物理排列顺序无关，数据存储在一个地方，索引存储在另一个地方，索引带有指针指向数据的存储位置。索引中项目按索引键值的顺序存储，而表中的信息按另一种顺序存储（聚集索引）。9.复制表（只复制结构，源表名A，新表名B）：select*intoBfromAwhere1=0（新建表B）拷贝表（拷贝数据）：select*intoBfromA（新建表B）10.建立一张临时表：createtable#Temp(usernamevarchar(50),pwdvarchar(20))11.查出第5到第7行的记录declare@iintset@i=1createtable#T(useridint)//临时表while(@i<=10)begin insertinto#T select@i set@i=@i+1end方法1：selectuseridfrom( selecttop3userid from(selecttop7userid from#T orderbyuserid)Ta//定义表 orderbyuseriddesc )Tb//定义表orderbyuserid方法2：selecttop3useridfrom#Twhereuseridnotin( selecttop4userid from#T orderbyuserid)orderbyuserid方法3：selecttop3useridfrom#Twhereuserid>ALL( selecttop4userid from#T orderbyuserid)orderbyuserid12.删除表droptabletname13.更改正在运行的数据库的名称：sp_rename'原表名’,'新表名'14.主网分成两个网段，第一个子网是/17，则第二个为/17。其中，17是从前往后数。15.socket通讯：server：①创建socket；②bind端口；③listen监听端口；④循环accept接受连接；⑤send/recv发送接收数据。client：①创建socket；②connect服务器；③send/recv发送接收数据。16.TCP端口：FTP：21，Telnet：23，SMTP：25，HTTP：80；UPD端口：DNS：53，SNMP：161，QQ：8000和4000。17.ping是用的是ICMP协议，即InternetControlMessageProtocol，Internet控制消息协议。Tracert也是ICMP协议。控制消息是指网络通不通、主机是否可达、路由是否可用等网络本身的消息。18.TCP是主机对主机层的传输控制协议，提供可靠的连接服务，采用三次握手确认建立一个连接：位码即tcp标志位，有6种标示：SYN(synchronous建立联机)ACK(acknowledgement确认)PSH(push传送)FIN(finish结束)RST(reset重置)URG(urgent紧急)，Sequencenumber(顺序号码)Acknowledgenumber(确认号码)第一次握手：主机A发送位码为syn＝1,随机产生seqnumber=1234567的数据包到服务器，主机B由SYN=1知道，A要求建立联机；第二次握手：主机B收到请求后要确认联机信息，向A发送acknumber=(主机A的seq+1),syn=1,ack=1,随机产生seq=7654321的包第三次握手：主机A收到后检查acknumber是否正确，即第一次发送的seqnumber+1,以及位码ack是否为1，若正确，主机A会再发送acknumber=(主机B的seq+1),ack=1，主机B收到后确认seq值与ack=1则连接建立成功。完成三次握手，主机A与主机B开始传送数据。连接终止协议（四次挥手）由于TCP连接是全双工的，因此每个方向都必须单独进行关闭。这原则是当一方完成它的数据发送任务后就能发送一个FIN来终止这个方向的连接。收到一个FIN只意味着这一方向上没有数据流动，一个TCP连接在收到一个FIN后仍能发送数据。首先进行关闭的一方将执行主动关闭，而另一方执行被动关闭。（1）TCP客户端发送一个FIN，用来关闭客户到服务器的数据传送（报文段4）。（2）服务器收到这个FIN，它发回一个ACK，确认序号为收到的序号加1（报文段5）。和SYN一样，一个FIN将占用一个序号。（3）服务器关闭客户端的连接，发送一个FIN给客户端（报文段6）。（4）客户段发回ACK报文确认，并将确认序号设置为收到序号加1（报文段7）。2012.07.301.排序：算法、时间复杂度（最好最差平均）、空间复杂度、稳定性P198(1)冒泡排序（bubblesort）时间复杂度：最差、平均都是O(n2)；最好是O(n)，空间复杂度：1稳定性：稳定voidSort(){ for(inti=iLength-1;i>0;i--) { for(intj=0;j<i;j++) { if(dData[j].iData>dData[j+1].iData) { Swap(dData[j],dData[j+1]); } } }}(2)鸡尾酒排序（Cocktailsort，双向冒泡排序）时间复杂度：空间复杂度：稳定性：稳定(3)插入排序（insertionsort）时间复杂度：空间复杂度：稳定性：稳定voidSort(){ for(inti=1;i<iLength;i++) { intj=i-1; DataTypedTemp=dData[i]; while(j>=0&&dData[j].iData>dTemp.iData) { dData[j+1]=dData[j]; j--; } dData[j+1]=dTemp; }}(4)归并排序（mergesort）时间复杂度：空间复杂度：稳定性：稳定(5)桶排序（bucketsort）时间复杂度：空间复杂度：稳定性：稳定(6)基数排序（radixsort）时间复杂度：空间复杂度：稳定性：稳定(7)二叉树排序（binarytreesort）时间复杂度：空间复杂度：稳定性：稳定(8)图书馆排序（librarysort）时间复杂度：空间复杂度：稳定性：稳定(9)选择排序（selectionsort）时间复杂度：O(n2)空间复杂度：1稳定性：不稳定voidSort(){ for(inti=0;i<iLength;i++) { intm=i; for(intj=i+1;j<iLength;j++) { if(dData[j].iData<dData[m].iData) { m=j; } } if(m!=i) { Swap(dData[m],dData[i]); } }}(10)希尔排序（shellsort）时间复杂度：空间复杂度：稳定性：不稳定(11)堆排序（heapsort）时间复杂度：空间复杂度：稳定性：不稳定(12)快速排序（quicksort）时间复杂度：空间复杂度：稳定性：不稳定分治策略：将原问题分解为若干个规模更小但结构与原问题相似的子问题，递归解决子问题，然后将这些子问题的解组合为原问题的解。2.按策略划分内部排序方法：插入排序、选择排序、交换排序、归并排序、分配排序。3.若排序算法所需的辅助空间为O(1)，则称为就地排序。4.栈的最小值栈中存放一个最小值的栈，入栈时跟最小值的栈顶元素比较一下，如果小，则入到最小值的栈。出栈时跟最小值的栈顶元素比较一下，如果相等，则最小值栈也出栈。前提是栈中没有重复的元素。2012.07.311.SQLServer中ifelse用法declare@xint,@yint,@zint--注意变量之间要打，select@x=1,@y=2,@z=3if@x>@yprint'x>y'--打印elseif@y>@zprint'y>z'elseprint'z>y'2.casewhen用法updateemployeesete_wage=casewhenjob_level='1'thene_wage*1.08whenjob_level='2'thene_wage*1.07whenjob_level='3'thene_wage*1.06elsee_wage*1.05end3.while用法declare@xint,@yint,@zintselect@x=1,@y=1while@x<3begin print@x while@y<3 begin select@z=100*@x+@y print@z select@y=@y+1 end select@x=@x+1 select@y=1end4.waitfor用法waitfordelay'00:00:05'--等待s后执行，注意必须为'select*fromemployeewaitfortime'19:19:00'--等到:19:00执行select*fromemployee5.删除表中所有行truncatetabletime_temp6.索引（1）原则：a,只有表的所有者可以在同一个表中创建索引；b,每个表中只可以创建一个聚集索引；c,每个表中最多可以创建249个非聚集索引；d,在经常查询的字段上建立索引；e,定义text,image和bit数据类型的裂伤不能创建索引；f,在外键列上可以创建索引，主键上一定要有索引；g,在那些重复值比较多的，查询较少的列上不要建立索引。（2）方法：a,使用SQLserverManagementStudio创建索引。b,使用T-SQL语句中的createIndex语句创建索引c,使用Createtable或者alterTable语句为表列定义主键约束或者唯一性约束时，会自动创建主键索引和惟一索引。创建索引T-SQL语句：create[unique][clustered|nonclustered]indexindex_nameon<object>(cloumn[asc|desc][,……n])[include(column_name[,……n])]--指定要添加到非聚集索引的叶级别的非键列[with(<relational_index_option>[,……n])][onfilegroup_name]--指定文件组创建指定索引创建聚集索引createclusteredindexzindexonemployee(job_level)createnonclusteredindexwage_indexonemployee(e_wage)查看索引execsp_helpindexemployee修改索引alterindexallonemployeerebuildwith(fillfactor=80,sort_in_tempdb=on,statistics_norecompute=on)删除索引dropindexemployee.wage_index分析索引①showplan_alloffsetshowplan_alloffselectid,enmeaning,chsmeaning,unitfromwordswhereunit='1'②statisticsioon/off语句setstatisticsioonselectid,enmeaning,chsmeaning,unitfromwordswhereunit='1'(28行受影响)表'words'。扫描计数1，逻辑读取3次，物理读取0次，预读0次，lob逻辑读取0次，lob物理读取0次，lob预读0次。维护索引①使用dbccshowcontig语句,显示指定表的数据和索引的碎片信息。当对表中进行大量修改或添加数据后，应该执行此语句查看有无碎片。语法：dbccshowcontig[{table_name|table_id|view_name|view_id},index_name|index_id]withfast②使用dbccdbreindex语句，意思是重建数据库中表的一个或多个索引。③使用dbccindexdefrag,整理指定的表或视图的聚集索引和辅助索引碎片。7.数据操作SELECT--从数据库表中检索数据行和列INSERT--向数据库表添加新数据行DELETE--从数据库表中删除数据行UPDATE--更新数据库表中的数据数据定义CREATETABLE--创建一个数据库表DROPTABLE--从数据库中删除表ALTERTABLE--修改数据库表结构CREATEVIEW--创建一个视图DROPVIEW--从数据库中删除视图CREATEINDEX--为数据库表创建一个索引DROPINDEX--从数据库中删除索