C,C面试指南笔记

《C,C面试指南笔记》由会员分享，可在线阅读，更多相关《C,C面试指南笔记（42页珍藏版）》请在装配图网上搜索。

1、1、C语言语句是指以分号作为结束符,编译后产生机器指令的代码。预处理指令不是C语句。2、变量的声明和定义有什么区别？定义：为变量分配地址和存储空间。声明：不分配地址。一个变量可以在多个地方声明，只能在一个地方定义。加 入extern修饰的是变量的声明，说明此变量将在文件以外或在文件后面部分定义。说明：很多时候一个变量，只是声明，不分配内存空间，直到个体使用时才初始化分配内存空间，如外部变量。3、以最简单的方式使电脑发出蜂鸣声音？使电脑发出蜂鸣有很多方法：可 以 调 用beep；可以用汇编直接操作蜂鸣器对应的管脚。最简单的方式：#includenstdio.hint main(int argc,

2、char*argv)printfrVTR/常用字符的 ASCII值return 0;)4、编程规范包括程序的可行性，可读性，可移植性及可测试性。可行性:是目的，也是规范的灵魂。通常要注意：预处理命令的使用；运算符优先级的区别；指针的使用等。可读性:变量和函数名的命名做到见名知义；适当加注释(写在代码的上方或右方）；无参数函数时最好加void等。可移植性:使用标准库函数，并且把它们和ANSI/ISOC标准中定义的头文件放在一起使用。等等。可测试性:增加打印消息，跟踪程序流程，这样可使测试者更加快捷地找到问题所在；嵌套最好不多于五层。等。5、变量与函数名命名的习惯 满足命名规则，不能用关键字。（以

3、下总结为可读性）标识符最好采用英文单词或其组合，切忌中英混用且不要过长。Windows系统中标识符通常大小写混排如LittleBoyo 指针变量命名基本原则：一重指针为“p+变量类型前缀+名称，如float类型指针pfStat.多重指针类似。程序中最好不要出现局部变量与全局变量完全相同的情况。符号常量常用下划线分隔单词。全局变量加前缀g_。类 的数据成员加前缀m_（表示mem加r）,避免数据成员与成员函数参数同名时混。6、写出bool,int,float.指针变量（用flag表示的）与“零值”比较的if语句。bool:if（flag）else或：if(!flag)elseB；A；不良习惯：If

4、(flag=TRUE);if(flag=FALSE);if(flag=l);if(flag=O)int:If(O!=flag)或：If(O=flag)(A；B；)ElseElseB；A；不良习惯：If(flag=FALSE);if(flag).指针类型：If(NULL=flag)A；ElseB；)或：if(NULL!=flag)B；)ElseA；)不良习惯：If(p=O);if(p!=O);if(p).float:const float NORM=0.0001;If(flag=NORM)&(flag=NORM)A；不良习惯:If(x=O.O);if(x!O.O).应当特别注意：在 in t,指

5、针变量和零值比较时，把零值写在左边。是因为当把“=写成“=”时，编译器可以报错，否则这种逻辑错误不容易被发现。7、代码一、short sl=l;sl=sl+lL;代码二、short sl=l;sl+=lL;以上两段代码是否都正确？类型转换关系：例如：short和 int型数据相加，则将short转换成int.代码一中s i 是 short,转换成long与 1L相加，得到的是long和，但赋值给short型的s i,所以不正确。改为：Short sl=l;sl=(short)(sl+lL);代码二中“+=”会进行类型转换，所以正确。8、C 中任何数据在内存中都是以二进制形式存放的。而数值是以补

6、码表示的。字符型数据在内存中是按其ASCII码值来存储的，其ASCII码值在内存中也是以二进制形式存储的。9、什么是左值，什么是右值？左值位于赋值号左边，右值位于赋值号右边。常量不可寻址，变量可以，变量有两个相关值：地址值和数据值。数据值:存储在内存中的数据，也称为变量的右值。地址值：存储数据值的地址，也称为变量的左值。左值一般是变量，右值可以是变量，表达式或常量。即左值可以为右值，右值不可以为左值。10、字符型数据无论在16位机上还是32位机上都是占一个字节,而基本整型在16位机上占两个字节，在32位机上占四个字节。因此,用sizeof求字节数时要注意分情况。11、Sizeof 与 strl

7、en 的区别 sizeof是一个操作符，而strlen是库函数。Sizeof用来返回一个数据类型的占的字节数，参数可以是数据类型也可以是变量且后面的小括号可以不写。Strlen用来返回一个字符串的长度且只能以0作为结束符的字符串为参数。编译器在编译时就计算出sizeof的值，而strlen函数是在运行时才计算出来。数组做sizeof参数不退化，做strlen参数时退化为指针。例如：#include,stdio.hH#includenstring.hnvoid main(void)char str10=,abcen;int x=strlen(str);int y=sizeof(str);prin

8、tf(H%d,%dn,x,y);)结果为：4,1012、/位域#include,stdio.hHstruct siint i:8;char j:4;int a:4;double b;)；struct s2int i:8;intj:4;double b;int a:4;struct s3int i;char j;double b;int a;)；怎么区分是结构体还是位域？void main(void)printf(Hsizeof(sl)=%dn n,sizeof(struct si);printf(sizeof(s2)=%dnn,sizeof(struct s2);printf(Hsizeof(

9、s3)=%dn,sizeof(struct s3);)注：在 V C 中都是24。怎么回事？书上是：16,24,32说每个数据都要对照结构体内最大数据字节数的最小公倍数补齐。位域：是把一个字节中的位按照实际的需求分成不同的区域，表明每个区域位数，区域的域名，并允许程序按照域名进行操作。如此就可以把不同的对象用一个字节来表示。能节省空间。即成员均按二进制位分配。位域定义格式：struct位域的结构名 位域列表;位域列表表示形式：类 型 说 明 符 位 域 名：位域的长度如上 sl,s2,s3o几点说明：一个位域必须存储在同一个字节中，不能跨两个字节。如一个字节所剩空间不够存放另一个位域时,应从下

10、一单元起存放该位域。也可以有意使某位域从下一单元开始。如：Struct wyUnsigned a:6;Unsigned:0;空域Unsigned b:4;从下一单元开始存放Unsigned c:4;）；在这个位域定义中，a 占第一个字节的6 位，后 2 位 填 0 表示不使用，b 从第二字节开始，占用4 位，c 占用4 位。由 于位域不能跨两个字节，因此位域的长度不能大于一个字节的长度，也就是不能超过8 位二进制位。位域可以无位域名，这时它只用来填充或调整位置。无名的位域是不能使用的。例如：struct kyInt a:l;Int:2;/这两位不能使用Int b:3;Int c:2;）；13、

11、C 和 C+中的static有什么区别？C 中：static用来修饰变量或函数，主要用来说明这个变量或函数只能在本文件代码块中访问，且 static修饰的变量存放在段存储区。主要有以下用途：定 义局部静态变量存储在静态存储区，在程序运行期间不会释放，只在声明时初始化一次，若没有初始化，自动赋值为0 或空字符。具有局部变量的“记忆性”及生存周期“全局性”特点。“记忆性”是指在两次函数调用时，第二次调用开始时，变量能够保持上一次调用结束时的值。“全局性”可改善函数返回指针的问题，局部变量的问题在于当函数退出时其生存期结束。而利用static修饰的局部变量却可以延长其生存期。限 定访问区域被 sta

12、tic修饰的变量及函数只能被同一文件内的代码段访问。C+中，除上述两种还有：定 义静态成员变量和静态成员函数。静态成员变量或静态成员函数表示其不属于任何一个类实例，是类的所有类实例所其有的。实现在多对象实例间进行通信，传递信息。如：#include*iostream.h#includestring.hnclass Apublic:static int a;static int geta();int b;int getb();)；int A:a=100;int A:geta()(return a;)int A:getb()return b;)void main(void)A m,n;m.b=90

13、;coutm.geta()endl;coutm.getb()endl;coutm.aendl;n.a=33;n.b=44;coutm.geta()endl;体现共用coutm.getb()endl;coutm.aendl;体现共用)14、C,C+的结构体有什么区别？C 的结构体是不能有函数成员的，只是一些已有数据结构组合而成，而 C+类可以。C 结构体数据成员没有public,private,protected之分，C+有。C 的结构体没有继承关系，C+有。注：结构体可简单理解为类的前身。15、C 中的malloc和 C+中的new有什么区别？malloc,free,new,delete都是用

14、来动态申请内存和释放内存的。malloc,free是标准函数,而new,delete是运算符。前两个在C,C+中都可使用，要包含相应的头文件，可以覆盖；而后两个只属于C+,不需要头文件的支持，可以重载。Malloc要指定申请内存的大小，其申请的只是一段内存空间。New不必指定申请内存的大小，只是建立一个对象。New和delete调用对应的构造函数和析构函数。而malloc,free只是分配内存和回收内存。malloc,free返回的是void类型指针，new,delete返回的是某种数据类型指针。16、C中指针和C+引用有什么区别？引用是变量或对象的别名，不是值，不占据存储空间，只有声明没有定

15、义。在C+中可用于：函数参数当函数的返回值多于一个时，可用指针实现。如：#includeH iostream.hnvoid swap(int*a,int*b)int temp;temp=*a;*a=*b;*b=temp;)void main(void)int a=10,b=20;cout*before change:,a H*bendl;swap(&a,&b);coutafter change:,H Hbendl;)结果是：before change:10,20after change:20,10也可以用引用实现，如：#includeH iostream.hnvoid swap(int&a,i

16、nt&b)int temp;temp=a;a=b;b=temp;void main(void)int a=10,b=20;cout*before c h a n g e:*b e n d l;swap(a,b);coutnafter change:*bendl;)结果是：before change:10,20after change:20,10引用更加简便和易理解。指针可不初始化且初始化时，可以指向一个地址，也可以为空。引用必须初始化且只能初始化一次。引用之间赋值和指针之间赋值不同。指针赋值如下：int vl=7,v2=9;int*pl=&vl,*p2=&v2;pl=p2;/*pl 指向变了*

17、/引用赋值如下：int vl=7,v2=9;int&rl=vl,&r2=v2;rl=r2;/*改变的是v l的值，将 r2指向的对象v2的值赋值给VI。而rL r2仍指向原来的变量。*/由上述例子可知，指针可以改变指向，而引用总是指向初始化时的对象。17、预处理在 C/C+中预处理如宏定义、文件包含、条件编译等。简述#ifdef,#else,#endif,#ifndef 的作用软件程序的升级是在已成型软件的基础上进行修改和扩充。升级工作非常复杂和烦琐，因为软件不断地升级，程序体积在不断扩大，但是老用户却不能受到影响。条件编译指令便是解决这一问题的最佳选择。条件编译指令#ifdef,#else,

18、#endif,#ifndef 作用有：(1)利用#ifdef和#611由 将某程序功能模块包括进去，以向特定用户提供该功能，在不需要时用户可轻易屏蔽。如：#ifdefMATH#include,math.cH#endif注：如果不许向别的用户提供该功能，则在编译之前将首行的MATH加一个下划线即可。(2)在子程序前加上标记，以便于追踪和调试。#ifdef DEBUGprintf(nindebugging.);#endif(3)应对硬件的限制。由于一些具体应用环境的硬件不一样，限于条件，本地缺乏这种设备，只能绕过硬件，直接写出预期结果。#ifdefYAN2410i=getBordNum();当没有

19、YAN2410硬件时，程序调试运行时绕过此语句#elsei=0;#endif18、typedef和 define有什么区别？(1)用法不同typedef是用来说明一个数据类型的别名，以增强程序的可读性。define是用来定义符号常量和带参数宏。(2)执行时间不同typedef定义是定义语句，占用运行时间。且有类型检查功能。define是预处理，只占编译时间。只是简单进行字符串的替换，不进行类型检查。(3)typedef有作用域限制，define没有，只要在声明后引用均可。#includevoid fl(void)Typedef int INT;Void main(void)INTA=3;Pri

20、ntf(,A:%d,A);)编译不会通过，typedef定义的INT只限制在f l函数里。上述例子不是很恰当，typedef一般不放在函数里，在此只是为了说明问题#includevoid fl(void)#define MAX 100;)Void main(void)Printf(nMAX:%dn,MAX);)编译运行正确。(4)对指针的操作不同#include#define pCHAR char*typedef char*pchar;void main(void)pCHAR a,b;pchar x,y;printf(Hsizeof(a):%dnsizeof(b):%dnH,sizeof(a)

21、,sizeof(b);printf(sizeof(x):%dnsizeof(y):%dn*,sizeof(x),sizeof(y);)结果为：Sizeof(a):4Sizeof(b):lSizeof(x):4Sizeof(y):4注意：用define定义的char*只是简单替换19、#define CHAR char*和 typedefchar*CHAR 有什么区别？由define定义的类型别名可以被其他修饰符扩展如unsigned,而typedef不可。define定义的类型别名代表指针时，其连续声明的变量中只有第一个是指针，其他的均为非指针的普通变量，而typedef能够保证连续声明的所有

22、变量都为同一类型的指针。如18.20、const(l)const用来定义一个常量：定义时初始化，之后不能被更新。如：const double PI=3.14;便于类型检查：用const方法可以使编译器对处理内容有更多的了解。如：void fl(const int a)编译器就可以知道a 在该函数中不能改变，若改变就会报错。(3)同宏定义一样方便进行参数的修改和调整：如果想改变某个值,只需改变定义处。(4)节省空间：避免不必要的内存分配。如：#define MAX 100const int max=100;不分配空间int a=max;为 max分配空间,以后不再分配Intb=MAX;编译时进行

23、宏替换，为 b 分配空间？Int c=max;分配空间Intd=MAX;编译时进行宏替换，为 d 分配空间？比宏定义节省空间？为函数重载提供参考，如下：class Avoid fl(void);void fl(void)const;声明为上一 函数的重载)21、说明下面a 的各种声明含义。Const int a;/a 只读Int const a;/a 只读Constint*a;/*定义了一个指针a,这个指针指向常整形数据。即指针是普通指针，可以改变其值，但是其指向的常整形数据是不能通过指针改变的。*/Int*const a;/*定义了一个常指针a,这个指针指向整型数。即指针的值不能改变，但是指

24、向的整型变量的值是可以改变的。*/Int const*a const;/*定 义 了 一 常 指 针 a,这个指针指向一个常整型数。即指针的值不能改变，其指向的整型数据的值也不能改变。*/22、const,define定义常量的区别常量的引入可以增强程序的可读性，可以使程序的维护和调试更加方便，使书写简便。区别：(l)const定义常量有数据类型，而 define没有。很多集成开发环境只支持对const定义的常量的调试，不 支 define定义的常量。(3)Const定义的常量是要分配内存空间的，而 define定义的常量却不分配空间。23、static在 C 中主要用于定义全局静态变量，局部

25、静态变量，静态函数。C+中新增了：定义静态数据成员和静态函数成员。24、volatile表示动态的，易变的。在嵌入式编程中状态寄存器变量会随时被外界条件改变，属于这种类型的变量。在多线程编程中临界变量被几个线程共享，也是易变的。25、一个参数可以既是const又 是 volatile吗？Volatile修饰的变量的值是程序不可控的，可以任何不被程序明确指明的方式改变，例如：外部端口。它的变化不用程序内部的赋值语句就可实现。编译器不会优化这种由volatile修饰的变量。C onst修饰的变量在程序中是只读的，不能被改变的。但这仅限于程序内部，它可以被程序外的东西改变。例 如 用 const修饰

26、外部端口，程序内部不能修改它的值，但是外部却可以。但是编译器会优化掉const修饰的变量。现在用volatile和 const来同时修饰一个变量，比如外部端口。这个变量在程序内部不能够改变，并且编译器不会对其优化，但是外部条件却可以改变。另外一种常见的情况是只读的状态寄存器。它 受 volatile修饰，但它却可能被意想不到地改变。可以，用 const和 volatile同时修饰变量，表示这人变量在程序内部是只读的，不能改变的，只在程序外部条件下改变，并且编译器不会优化这个变量。每次使用这个变量时，都要小心地去内存读取这个变量的值，而不是去寄存器读取它的备份。Volatile可用来修饰指针。常

27、见例：子中断服务子程序修改一个指向一个buffer的指针时，必须用volatile来修饰这个指针。26、引用引用是指某一目标变量的别名。对引用的操作和对变量的直接操作一样。定义：数 据 类 型&引用名=目标变量名；引用可用作：(1)函数参数在C+中大多时候引用可代替指针实现址传递。如：#includevoid swap(char&x,char&y)/引用作参数int temp=0;temp=x;x=y;y=temp;)void main(void)char a=0,b=0;cin a b,cout”before swap,endl;cout,a:,b:,endl;swap(a,b);cout”

28、after swap,endl;cout,a:,b:,endl;return;）结果：a bbefore swapa:ab:bafter swapa:bb:a注意：引用作函数参数时，在内存中没有产生参数的副本即不分配内存空间，只是目标变量的别名。而一般变量作参数时，要给形参分配内存空间。没有数组的引用。因为没法给若干个元素定义一个别名。引用的声明一定要初始化。数据类型是指目标变量的数据类型。（2）常引用定义：const数据类型&引用名=目标变量名；如：char x=l;const char&rx=x;rx=2;错误，rx是只读的x=2;正确注意：不能通过目标变量的常引用来改变目标变量的值。(3

29、)作函数返回值定义格式：数 据 类 型&函数名(形参列表)函数体例1：#includeint temp;int fl(int x)temp=(int)(x*x*3);return temp;)int&f2(int x)temp=(int)(x*x*3);return temp;void main(void)int a=fl(5);系统生成要返回值的副本即临时变量int&b=fl(100);有时会出错。不能从被调函数中返回一个临时变量或局部变量的引用int c=f2;/系统不生成返回值的副本，可以从被调函数中返回一个全局变量的引用int&d=f2(5);系统不生成返回值的副本，可以从被调函数中返

30、回一个全局变量的引用coutaendl;coutcendl;coutdendl;)注意：不能返回局部变量的值。局部变量在被调用函数返回后就被销毁掉，它返回的引用所指向的内存已没有任何意义，运行时会出现不可预知的错误。如：#includeint&fl(int x)int temp;temp=x;cout”in fl:,endl;cout&temp is:,&tempendl;cout”temp is:,tempendl;return temp;void main(void)int&a=fl(5);a=9;cout”in main,endl;cout”&a is,&aendl;couta is:,

31、aendl;)结果：注意：不能返回函数内部new分配的内存的引用。可以返回类成员的引用，但最好是常引用。27、常引用常引用的引入主要是为了避免使用变量的引用时，在不知情的情况下改变变量的值。即在很多时候，只想访问变量的值，不希望改变变量的值。常引用是唯一的选择。常引用的作用：(1)用途普通变量的只读别名，通过这个别名只能获得这个变量的值，不能通过这个别名改变这个变量的值。#includevoid main(void)char x=,a,;const char&y=x;cout,x:,x,y:,yendl;x=b;cout,x:,x,y:,yendl;y=a;cout,x:,x,y:,yendl

32、;)在 VC6.0中会出现编译错误：error c2166:l-value specifies const object即左值是个只读对象。(2)用于函数的形参。常引用作形参，可确保在函数内不会意外改变实参的值。28、指针说明以下声明的含义：int*p10;定义了一个指针数组p,10个元素都是整型指针。int(*p)10;定义了一个指向具有10个整型元素数组的数组指针Po int*p(int);定义了一个函数p,该函数有一个整型参数，返回值为整型指针。int(*p)(int);定义了一个指向函数指针P，指向的函数有一个整型参数，返回值为整型数据。int(*p)10;等价于int(*(*p)10

33、.*p是数组指针，定义了一个指向含有10个整型元素数组的二级数组指针。char*(*p)10;等价于(char*)(*p)10o*p是数组指针，指向含有10个元素的数组,数组元素的类型是char*。float(*p10)();定义了一个含有10个元素的数组p,数组的元素是函数指针，这个函数没有参数，返回类型是float型的。double*(*p)10);P为数组的指针，数组有10个元素，元素为double*型。short(*p)(char);p为函数指针，它指向的函数有一个ch ar型的参数，返回值为short型数据。long(*(*p)(int,int)(int);假设pF=(*p)(int

34、,int),pF是个函数指针，原式变为：long(*pF)(int)。pF指向的函数有一个int型的参数，返回值为10ng型数据。p为函数指针，它指向的函数有两个in t型参数，返回值为函数指针型数据，这个返回的函数指针指向的函数有一个int型的参数，返回值为long型数据。29、指针常量和常量指针的区别指针常量是指定义的指针只能在定义的时候初始化，之后不能改变其值。定义格式如下：数据类型*const指针变量名；const位于*右侧，说明声明的对象是一个常量，而对象的数据类型是指针。如：char a5=abcd;char*const cp=a;指针常量的指向不能变，即上例中c p只能指向a,初

35、始化指向谁就不能再改变。但其指向的对象的值是可以变的，即上例中数组a元素的值可以变。常量指针是指向常量的指针。定义格式：数据类型con st*常量指针名；或：const数据类型*常量指针名；const位于指针声明符*的左侧，说明常量指针的值是可以改变的即指向可以变，但是其指向的内容是不能用这个指针改变的，可以自己改变。30、(1)#indudevoid main(void)char sl=,abcd,5char s2=abcd;const char s3=abcd;const char s4=abcd;const char*s5=”abcd”；const char*s6=”abcd”；char

36、*s7=”abcd”；char*s8=abcd”;cout(sl=s2)endl;cout(s3=s4)endl;cout(s5=s6)endl;cout(s7=s8)endl;结果：0011sl,s2,s3,s4,是数组，有各自的内存空间，所以地址不等。s5,s6,s7,s8是指针，指向相同的常量。字符串常量 abed”产生一个临时指针变量&(“abcd”)。所以地址相等。(2)写出结果#includevoid main(void)int b=0;int a5=0,l,2,3,4;for(int i=0;i5;)i=ai+l;coutaiendl;)return;)会下标越界，但编译器不会报

37、错，C/C+不进行数组越界检查。结果是：1 2340 123401 234.(死循环)(3)程序是否有错#define MAX 255#includevoid main(void)unsigned char strMAX,i;for(i=0;i=MAX;i+)stri=i;)可以赋i为2 5 5,再加1,看看结果。该程序会出现下标越界及死循环。同上。在0255之间循环。31、a为数组名，a和&a有什么区别？写出结果：#includevoid main(void)int a5=l,2,3,4,5；int*ptr=(int*)(&a+l);printf(u%d,%dn,*(a+l),*(ptr-l

38、);return;a 与&a是不同的。a+1是数组的首地址加1,是数组的第二个元素 al的地址。&a+l系统会主为是数组a 的首地址加上一个数组a 的偏移，即偏移一个数组的大小。数组名a 可以作为数组的首地址，&a是数组的指针。结果为：2,532、解析(*(void(*)()0)();void(*0)():是一个返回值为void,参数为空的函数指针0.(void(*)()0:把 0 强制转换成返回值为void,参数为空的函数指针。*(void(*)()0：力口*表示整个是一个返回值为void,无参数，且起始地址为0 的函数的名字。(*(void(*)()0)()：上述函数名的调用。33、野指针

39、是怎么产生的，如何避免？野指针是指指向不可用内存的指针。通常对这种指针进行操作时，程序会发生不可预知的错误。在以下三种情况发生：(1)指针变量声明时没有被初始化。任何指针变量刚被创建时都不会自动初始化为NULL指针，它的默认值是随机的，它会指向一个随机地址。通常在定义指针时要求赋值为NULLo#includetypedef int*pint;void swap(int*pl,int*p2)int*p;没有初始化，成为野指针。改为intp;后面一起改*p=*pl;*pl=*p2;*p2=*p;)void main(void)int a=l,b=3;pint pl=&a,p2=&b;cout,a:

40、,*p l,b:,*p2endl;swap(pl,p2);cout,a:,*p l,b:,*p2endl;return;)(2)指针p 被 free或 delete之后，没有置为NULL,让人误以为p是个合法的指针。为避免这种情况最好在free或 delete后赋值为NULL.(3)指针操作超越了变量的作用范围。如：#includeclass Apublic:void func(void)value=3;coutfunc();)void main(void)A*p;f(P)；p-func();出错return;)因为在f 中p 指向了 A 的对象a,并调用了 func,输出in fun ofA

41、o在f 结束后，a 被释放，p 指向了“垃圾”内存。但在main中又用p 调用 func。由于p 指向的内存不可用，导致内存操作错误。解决方法:在变量的作用域结束前释放掉变量的地址空间并让指针指向 NULL.数据结构常见面试题1、链表和数组的区别存储形式：链表可以是一块不连续的动态空间，长度可变；数组要求是一块连续空间，声明时要确定长度。数据访问：数组可随机访问，速度快，查找操作直接使用偏移地址；链表则要顺序检索，效率低。数据插入和删除：链表可快速插入和删除；数组则可能要移动大量数据。越界问题：链表不存在越界问题；而数组有。占用空间：存储相同数据时，链表要比数组占用更多空间，因为它除了存数据还

42、要存指针。2、快速寻找单链表中间结点。方法：双指针同时从头结点开始遍历。快指针每次移动两个结点，慢指针每次移动一个结点。快指针到链表尾部时，当链表长度为奇数时，慢指针指向的即是链表中间指针。当链表长度为偶数时，慢指针指向的结点和慢指针指向结点的下个结点都是链表的中间结点。算法设计：typedef struct NODE(int a;struct node*next;NODE;NODE*middle(lnode*head)(NODE*fast,*slow,*p;if(head=NULL)return NULL;fast=slow=head;while(!(p=fast-next)&!p-next

43、)?是 II 还是&slow=slow-next;fast=p-next;return slow;3、设计算法将单链表反序过程：把头结点（无头指针）指向空，后面的结点的next指针指向它前面的一个元素,最后尾结点成了头结点。算法：(1)循环算法List reverse(List n)(if(!n)return n;list cur=n-next;list pre=n;list temp;pre-next=NULL;while(NULL!=cur-next)(temp=cur;temp-next=pre;pre=temp;cur=cur-next;)return temp;返回头指针（2）递归算

44、法List*reverse(List*oldList,List*newHead=NULL)(List*next=oldList-next;oldList-next=newHead;newHead=oldList;return(next=NULL)?newHead:reverse(t,newHead);4、单循环链表单循环链表的尾结点指针指向首结点，形成一个环，可以从链表中的任一结点出发，访问链表中的所有结点。带环单向链表是指环的起点不是链表第个结点，即一个单向链表和一个环形链表的结合体。设计一个程序，用键盘输入的一些数字创建一个单向循环链表，求出链表的和度，打印链表各个元素。之后可以根据需求把

45、这个循环链表改装成单向链表或带环的单向链表。结点结构typedef struct node(int data;struct node*next;Lnode,*LinkList;单向循环链表void CreatLinkList(LinkList&L)int i;LinkList pl;头结点指针L=(LinkList)malloc(sizeof(struct node);头结点pl=L;指针指向pl-next=L;/H有个结点的循环链表couKcplease input the data of the node,e n d l,input 0 to end:;cini;while(i)(从键盘读

46、取数据，用这些数据据初始化结点，再插入循环链表LinkList p=(LinkList)malloc(sizeof(struct node);if(!p)coutvdata=i;pl-next=p;pl=p;pl-next=L;cout,9please input the data of the node,e n d l,input 0 to end:;cini;void PrintfLinkList(LinkList L)(LinkList temp=L-next;coutvvthe list is:“next!=L-next)(couttemp-dataendl;temp=temp-nex

47、t;int LinkListLength(LinkList L)(int i=0;LinkList temp=L-next;while(temp-next!=L-next)i+；temp=temp-next;)return i;void LinkListCircle(LinkList&L,int i,int LinkListLength)(LinkList pl,p2;pl=p2=L-next;for(int m=O;mvLinkListLength-l;m+)寻找表尾结点(pl=pl-next;if(i=0)将原表改为非循环单链表pl-next=NULL;return;)for(m=0;mn

48、ext;)pl-next=p2;5、高效方法检测一个较大的单向链表是还带环如果个单向链表不带环，尾结点的next肯定是NULL,否则尾结点的next指向链表中的某一个结点元素。双指针实现原理：定义两个指针，快指针每次移动两个结点，慢指针每次移动一个结点。快指针每移动一次都要和慢指针比较。直到当快指针的next指向空时，证明这个链表就是不带环的单向链表，或者快指针等于慢指针，证明这个链表就是带环的。具体实现：bool research_cycleLink(LinkList headNode)LinkList pl,p2;bool result=false;pl=headNode;if(p l-next=NULL)(printf(“只有一个结点。n)；)else if(p 1 -next-next=NULL)(printf(只有两个结点。n)；)else(p2=(p 1 -next)-next;while(pl!=NULL)&(p2!=NULL)(if(pl=p2)(result=true;break;else(if(p2-next=NULL)(result=false;break;)pl=pl-next;p2=(p2-next)-next;)return result;int型数据的最大倍数是10.