C,C++与数据结构.doc

《C,C++与数据结构.doc》由会员分享，可在线阅读，更多相关《C,C++与数据结构.doc（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 C/C+、数据结构、算法、STL 工作学习积累1C/C+11.1 重点语法21.2 编程技巧21.3 编程规范21.3.1 代码排版、注释、命名等21.3.2 变量、结构、函数的命名与使用31.3.3 代码效率、测试与维护31.4 程序员面试宝典学习42 数据结构43 STL44 基础算法41 C/C+主要包括C/C+的一些重点语法，编程技巧，编程规范，面试重点考察的知识点。1.1 重点语法结合c/c+ 书籍，将工作中经常设计到又相对容易忽略的语法知识点整理出来，以供不时温故而知新。1.1.1 数据类型、运算符、表达式1 (整型、字符型、实数型、枚举)、（数组、结构、共用体）、指针、空类型。

2、2 常量、变量命名规范，123（10）、0123（8）、0x123（16），数值以补码表示、正数不变、负数按位取反加一。3 char占一个字节，int、uint、shortint、占2-4个字节，long、ulong占4个字节，float占4个字节。有效数字为6-7，double占8个字节、有效数字15-16，所有指针类型（与所指对象无关）均占4个字节。4 int a = 32767、a + 1 为-32768（溢出）达到最大从最小开始，达到最小从最大开始5 注意字符和字符串的区别，字符串在内存存储最后位为0,字符变量和整型变量可互用。6 在一个运算式中（一条语句）系统会自动把低位类型数据转为

3、高位类型数据得到结果为高位类型数据（10*1.3f）,表达式运算中存在有符号类型和无符号类型时，系统都会自动转换为无符号类型来处理。7 表达式运算从左至右、赋值运算从右至左。j = i+ 与j = +i的区别printf（%d,+i)与printf（%d,i+)不同体现在语句中，一个是先增再执行语句，另一个是执行语句后再增。8 注意赋值时类型不同导致的溢出、x *= y + 8 时把右边看为一整体。printf(%d,a = b)先 a=b；再输出a。9 a = 3*5,a*4 先求表达式a = 3*5、再求表达式a*4 最后逗号表达式的值为后面的表达式值。1.1.2 顺序、选则、循环语句1

4、continue 语句强制程序转入循环底部、跳过continue语句之后的任何语句、进入下一次循环。break 语句用于在循环正常测试条件符合之前终止循环执行、跳出循环体。return 从函数体中返回并退出函数体。2 if（a=b）0）,printf(%5d,c=%f,%o,%lx,%s,%u%,a,b,c,a,b,s,a);scanf(%c %d,&a,&b);3 C语言中 0 为假、非 0 为真，（m=ab)&(n=cd)当（m=ab)为真时才执行(n=cd)，（m=ab)|(n=cd)相反。4 max=ab?a:b; printf（%d,ab?a:b);条件表达式先判断ab为真取a继续操

5、作、为假取b进行操作。5 ASCII码中小写字母比大些字母大、a=A+32; 判断是否为大小写 =A、=a。6 注意while 与 do while 的区别、理解for(表达式;表达式;表达式)语句的执行过程。理解switch case default。for(;) ,for(sum=0,i=0;i+)1.1.3 函数、数组与指针1 数组使用前要初始化、二维数组可以当做一组一维数组来处理、注意字符数组与字符串的区别。2 调用函数之前应先声明函数、理解局部变量和全局变量（相对与函数而言）静态变量和外部变量（相对函数间和文件间）。3 静态函数只能在本文件中被引用，理解值参数、数组名参数、指针参数的

6、区别，理解函数的返回值。4 区分变量的指针（地址）和指针变量（保存指针的变量），&（其他变量）和*（指针变量）。5 p指向一个数组的某个元素，则p+1指向数组的下一个元素，即若p指向a0则P+i = &ai，p+合法、a+（错误）。6 理解二维数组和指向指针的指针变量的联系。一般来说、数组都可以通过指针来等价操作。7 指向字符串的指针是把字符串的首地址赋给指针变量： char* ch = fsc;能利用字符指针实现字符串的copy等其他操作。8 理解指向函数的指针(保存函数的入口地址)，int max(int a,int b);int (*p)(int,int);p = max; p(a,b)

7、;9 把函数指针（或者函数名即函数的地址）作为函数参数传入可以实现在函数中调用函数的多样化。10 理解返回指针值的函数、指针数组的定义和使用（int* pt4;）、指向指针的指针的用法。1.1.4结构体、共用体、枚举1 结构体是构造数据类型，struct 变量命成员列表变量名列表;使用前要初始化。2 指向结构体的指针保存的是结构体的起始地址，用结构体变量或其指针作为函数参数传入。3 共用体数据类型、union 变量命成员列表变量名列表，指的每时间是这段内存可以存放成员列表中的其中一个成员。4 结构体的内存长度等于各成员长度之和、共用体的内存长度等于最长的成员的长度，共用体每一瞬时只有一个成员其

8、作用，共用体变量地址和各成员地址一样，只能把指向共用体的指针作为函数参数，存入新成员后原来的就失去作用。5 枚举类型 ：enum 变量名枚举常量列表枚举变量列表; 枚举限定了变量只能取自枚举常量列表中的一种。6 枚举常量默认从0开始、若定义其中一个、后面的逐个加 如：enum colorred=2,blue=5,green,gray,white;只能在同一枚举变量类型之间进行比较和赋值，可以对整型变量进行枚举类型强制转换。7 typedef 定义新的类型名来代替已有的类型名、typedef char* STR;按照正常的类型定义再在前面加上typedef关键子即可。比如定义函数指针新的类型名：

9、typedef int（*p）（int a）; p max,min; 这样max，min都是函数指针。1.1.5 预处理、位运算1 宏名一般用大写，#define . #undef 宏定义不是语句是完全、简单的替换，带参数的宏替换，建议所有的层次都要加括号。宏定义#define 是由预处理完成的，而typedef则是在编译时完成的2 文件包含命令 #include #include的区别，防止重复包含。3 条件编译：#ifdef.#else.#endif ，#ifndef.#else.#endif ，#if.#else.#endif ，减少被编译的时间。#define DEBUG #ifdef

10、 DEBUG printf(x=%d,x); #endif 。4 位运算是指进行二进制位的运算，&（按位与）、|（按位或）、（按位异或） 、（取反）、（右移）。运算量只能是整或字符型、位运算的规制是先把整或字符型数据转换成二进制数再按位运算规制进行操作。5 &（按位与）：两个相应的二进位都为1、则该位的结果为1、否则为0。6 |（按位或）：两个相应的二进位只要有一个为1、则该位的结果为1、否则为0。7 （按位异或）：两个相应的二进位同号则该位结果为（假），异号则为（真），如a 、b交换时用法等。8 （取反）：对一个二进制数按位取反。9 （左移）：将一个数二进制位全部左移若干位，高位左移后溢出（

11、舍弃）、低位补，如：a = a（右移）：将一个数二进制位全部右移若干位，低位右移后溢出（舍弃）、高位补，如：a = a2。11 位运算与赋值运算符结合，如 &= 、右边的都作为一个整体。1.1.6 C+关键字、新增语法1 引用是对象的另一个名字、同一个对象的不同称呼、像人的外号一样。2 extern ：1.外部引用、在一个文件中引用在其它文件中定义的变量、比如在文件1中int i;在文件2中,需include文件1,再extern int i;从而使文件1的i能在文件2中使用。2. extern C、在C+环境下使用C函数的时候，常常会出现编译器无法找到obj模块中的C函数定义从而导致链接失败

12、的情况C+语言在编译的时候为了解决函数的多态、重载问题、会将函数名和参数联合起来生成一个中间的函数名称，而C语言则不会，因此会造成链接时找不到对应函数的情况，此时C函数就需要用extern “C”进行链接指定，这告诉编译器用C的方式来编译函数。3 inline：inline定义解决了一些频繁调用的小涵数大量消耗栈空间的问题，避免了频繁调用函数对栈内存重复开辟所带来的消耗。inline只适合涵数体内代码简单的涵数使用、不能包含复杂的结构控制语句。4 const：const 推出的初始目的、是为了取代预编译指令#define、消除它的缺点、继承它的优点。const 是一个左结合的类型修饰符、常用于

13、常量定义，修饰函数传递参数与返回参数等。const int* const x=&d；int const* const x2=&d；5 friend：友元函数，让该函数或类能够访问另一个类的private和protected成员。6 this：this是指向对象本身的指针、作用域是在对象内部、当在类的非静态成员函数中访问类的非静态成员的时候，编译器会自动将对象本身的地址作为一个隐含参数传递给函数。7 static：要理解static，就必须要先理解auto，auto的含义是由程序自动控制变量的生存周期，通常指的就是变量在进入其作用域的时候被分配，离开其作用域的时候被释放；而static就是不au

14、to，变量在程序初始化时被分配，直到程序退出前才被释放；也就是static是按照程序的生命周期来分配释放变量的，而不是变量自己的生命周期。 void func()int a; static int b; 每一次调用该函数，变量a都是新的，因为它是在进入函数体的时候被分配，退出函数体的时候被释放，所以多个线程调用该函数，都会拥有各自独立的变量a，因为它总是要被重新分配的；而变量b不管你是否使用该函数，在程序初始化时就被分配的了，或者在第一次执行到它的声明的时候分配（不同的编译器可能不同），所以多个线程调用该函数的时候，总是访问同一个变量b，这也是在多线程编程中必须注意的！ static的全部用法

15、：1 类的静态成员：在cpp中必须对它进行初始化：类的静态成员是该类所有实例的共用成员，也就是在该类的范畴内是个全局变量，也可以理解为是一个名为A:s_value的全局变量，只不过它是带有类安全属性的；道理很简单，因为它是在程序初始化的时候分配的，所以只分配一次，所以就是共用的；2 类的静态函数：类的静态函数是在该类的范畴内的全局函数，静态成员函数不含this指针不能访问类的私有成员，只能访问类的静态成员，不需要类的实例即可调用；实际上，它就是增加了类的访问权限的全局函数，静态成员函数可以继承和覆盖,但无法是虚函数。3 只在cpp内有效的全局变量：在cpp文件的全局范围内声明：static i

16、nt g_value = 0; 这个变量的含义是在该cpp内有效，但是其他的cpp文件不能访问这个变量；如果有两个cpp文件声明了同名的全局静态变量，那么他们实际上是独立的两个变量；如果在一个头文件中声明：static int g_value = 0; 那么会为每个包含该头文件的cpp都创建一个全局变量，但他们都是独立的。顺便说一下如何声明所有cpp可共享的全局变量，在头文件里声明为extern的：extern int g_value; / 注意，不要初始化值！然后在其中任何一个包含该头文件的cpp中初始化（一次）就好。然后所有包含该头文件的cpp文件都可以用g_value这个名字访问相同的一

17、个变量。4 只在cpp内有效的全局函数：在cpp内声明：static void func();函数的实现不需要static修饰，那么这个函数只可在本cpp内使用，不会同其他cpp中的同名函数引起冲突；道理和如果不使用static会引起的问题和第3点一样；不要在头文件中声明static的全局函数，不要在cpp内声明非static的全局函数，如果你要在多个cpp中复用该函数，就把它的声明提到头文件里去，否则在cpp内部声明需要加上static修饰。8 virtual：虚函数是C+中用于实现多态的机制、核心理念就是通过基类访问派生类定义的函数，子类重写基类的虚函数必须有相同的参数表和返回值、虚函数多

18、重继承后还是虚函数，具有纯虚函数的类是抽象类、相当于接口只是声明了没有定义且不能实例化、靠子类去实现，虚函数可以直接使用、也可以被子类重载后以多态的形式调用，纯虚函数必须在子类中实现才可以使用、纯虚函数在基类只有声明没有定义，虚函数和纯虚函数都可以在子类中重载后以多态的形式调用。为了完成晚绑定，编译器对每个包含虚函数的类创建一个表（称为VTABLE） 。在VTABLE中，编译器放置特定类的虚函数地址。在每个带有虚函数的类中，编译器秘密地置一指针，称为vpointer（缩写为VPTR） ，指向这个对象的VTABLE。通过基类指针做虚函数调用时（也就是做多态调用时） ，编译器静态地插入取得这个VP

19、TR，并在VTABLE表中查找函数地址的代码，这样就能调用正确的函数使晚捆绑发生。9 operator：返回类型operator 运算符符号(参数说明) 函数体的内部实现，运算符重载函数的使用、一是作为类的友元函数进行使用、二是作为类的成员函数进行使用，运算符重载可以让其能被更广泛的使用而不是局限于int,float等类型、它可以按照你在函数中的定义进行两个类等其他类型之间的运算。运算符的重载实际上是函数的重载。10 template：函数、类模板，能使对同种类型数据结构仅定义一次、根据给定的模板参数生成函数、类实例。 / 类模板的用法Template class CList; / 函数模板的

20、定义template void printArray (T * array,const int count) / for (int i=0;icount;i+) coutarrayi cout），后不应加空格。5 一般情况下，源程序有效注释量必须在20以上。说明性文件（如头文件.h文件、.inc文件、.def文件、编译说明文件.cfg等）头部应进行注释，注释须列出：版权说明、版本号、生成日期、作者、内容、功能、与其它文件的关系、修改日志等，头文件的注释中还应有函数功能简要说明，对源文件和函数都要有类似的说明性注释。6 边写代码边注释，保证注释与代码的一致性；注释应与其描述的代码相近，对代码的注

21、释应放在其上方或右方（对单条语句的注释）相邻位置，不可放在下面，如放于上方则需与其上面的代码用空行隔开。7 在程序块的结束行右方加注释标记，以表明某程序块的结束，如 # ifdef for代码块等。8 始终保持自己一贯的标识符命名风格，标识符、接口函数的命名要清晰、明了，有明确含义，同时使用完整的单词或大家基本可以理解缩写，避免使人产生误解。9 命名规范必须与所使用的系统风格保持一致，并在同一项目中统一，如： Add_User 不允许，add_user、AddUser、m_AddUser 允许。10 源程序中关系较为紧密的代码应尽可能相邻，局部变量哪里用时哪里定义。11 我的命名风格类内变量m

22、开头 m_add_user 全局变量g开头g_add_user 函数名 get_varier（）宏和结构申明都用大写 AIS_RADAR_MSG1.3.2 变量、结构、函数的命名与使用1 防止局部变量与公共变量同名，严禁使用未经初始化的变量作为右值。2 结构的功能要单一，是针对一种事务的抽象，结构中元素的个数应适中，过长根据功能内嵌结构体，同时要注意结构体内的数据对齐。3 结构的设计要尽量考虑向前兼容和以后的版本升级，并为某些未来可能的应用保留余地（如预留一些空间等）。4 明确函数功能，精确（而不是近似）地实现函数设计。对于函数内部的全局变量，静态变量要予以说明和信号量（即P、V操作）等操作保

23、护。5 防止将函数的参数作为工作变量，即参数在函数内部除了赋给不宜进行运算等操作，应在函数内部开辟临时变量进行操作。6 函数的功能应该简单、具体和单一；一些简单的功能也应用函数或者宏来实现。7 优化函数时应遵循如下原则：（1）不能影响模块功能的实现。（2）仔细考查模块或函数出错处理及模块的性能要求并进行完善。（3）通过分解或合并函数来改进软件结构。（4）考查函数的规模，过大的要进行分解。（5）降低函数间接口的复杂度。（6）不同层次的函数调用要有较合理的扇入、扇出。（7）函数功能应可预测。（8）提高函数内聚。（单一功能的函数内聚最高）1.3.3 代码效率、测试与维护1 使用断言来发现软件问题，提

24、高代码可测性。编写代码之前，应预先设计好程序调试与测试的方法和手段，并设计好各种调测开关及相应测试代码如打印函数等。2 编程时要经常注意代码的效率如：1循环体内工作量最小化；2在多重循环中，应将最忙的循环放在最内层；3避免循环体内含判断语句，应将循环语句置于判断语句的代码块之中；4尽量用乘法或其它方法代替除法，特别是浮点运算中的除法。3 用宏定义表达式时，要使用完备的括号；对内存的空间的操作要谨慎。2 数据结构、算法数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。它主要包括：数据的逻辑结构；数据的物理存

25、储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。 逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。数据的物理结构是指逻辑结构的存储镜像。数据可以用不同的形式进行描述或存储在计算机存储器中。最常见的数据描述方法有：公式化描述、链接描述、间接寻址和模拟指针。单链表（List）多项式节点表达式节点修改部分操作添加向前指针域限制操作多项式表达式循环链表双向链表栈和队列2.1 数组及其操作数据对象array的每个实例都是形如（index，value）的数据对集合，其中任意两对数据的index值都各不相同。有关数组的操作有：创建，插

26、入，查找，删除，排序等。C+中数组是一个标准的数据结构，但C+数组的索引（下标）采用如下形式：i1 i2 i3 ik为了实现与数组相关的函数Store和Retrieve，必须确定索引值在数组中的相应线性存储位置。即index与value的一对线性映射。设定义Au1，Au1 u2，Au1 u2 u31 当数组维数为1时（即k=1），对应Ai1使用以下函数：map(i1) = i1 2 当数组维数为2时（即k=2），对应Ai1 i2 使用以下函数：map(i1, i2) = i1* u2+ i23 当数组维数为3时（即k=3），对应Ai1 i2 i3 使用以下函数： map(i1,i2, i3)

27、= i1* u2* u3+ i2* u3+ i32.2 堆栈及其操作堆栈数据结构是通过对线性表的插入和删除操作进行限制而得到的（插入和删除操作都必须在表的同一端完成），因此，堆栈是一个后进先出（last-in-first-out,LIFO）的数据结构。堆栈有公式化描述和链表描述两种表示方式：2.3 队列及其操作队列（quene）是一个线性表，其插入和删除操作分别在表的不同端进行。添加新元素的那一端被称为队尾(rear)，而删除元素的那一端被成为队首(front)，因此，队列是一个先进先出（first-in-first-out,FIFO）的线性表。队列有公式化描述和链表描述两种表示方式：2.4

28、字典及其操作字典（dictionary）是一些元素的集合。每个元素有一个称作key的域，不同元素的key各不相同。如STL中的map。增加了向前指针的链表叫作跳表，散列法是用来搜索、插入、删除记录的另一种随机方法。字典有线性表描述，跳表描述，散列描述三种实现方法。在一个使用有序链表描述的具有n个元素的字典中进行搜索，至多需进行n次比较。如果在链中部节点加一个指针，则比较次数可以减少到n/2+1。搜索时，首先将欲搜索元素与中间元素进行比较。如果欲搜索的元素较小，则仅需搜索链表的左半部分，否则，只要在链表右半部分进行比较即可。字典的散列（hash）描述是用一个散列函数（hash function）

29、把关键字映射到散列表（hash table）中的特定位置。在理想情况下，如果元素e的关键字为k，散列函数为f，那么e在散列表中的位置为f(k)。要搜索关键字为k的元素，首先要计算出f(k)，然后看表中f(k)处是否有元素。如果有，便找到了该元素。如果没有，说明该字典中不包含该元素在前一种情况中，如果要删除该元素，只需把表中f(k)位置置为空即可。在后一种情况中，可以通过把元素放在f(k)位置以实现插入。2.5树及其操作 树（tree）t是一个非空的有限元素的集合，其中一个元素为根（root），余下的元素（如果有的话）组成t的子树（subtree）。数适合描述有层次结构的数据。在层次化的数据之间

30、可能有祖先-后代、上级-下属、整体-部分以及其他类似的关系。2.5.1 二叉树二叉树（binary tree）t是有限个元素的集合（可以为空）。当二叉树非空时，其中有一个称为根的元素，余下的元素（如果有的话）被组成2个二叉树，分别称为t的左子树和右子树。二叉树的常用操作：确定其高度，确定其元素数目，复制，在屏幕或纸上显示二叉树，确定两棵二叉树是否一样，删除整棵树。以上所有操作可以通过对二叉树进行遍历来完成假设对高度为h的满二叉树中的元素按从第上到下，从左到右的顺序从1到2h-1进行编号假设从满二叉树中删除k个元素，其编号为2h-i,1ik，所得到的二叉树被称为完全二叉树。2.5.2优先队列（最

31、大最小树，左高树）优先队列（priority queue）是0个或多个元素的集合，每个元素都有一个优先权或值，对优先队列执行的操作有1)查找；2)插入一个新元素；3)删除。在最小优先队列（min priorityqueue）中，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素；对于最大优先队列（max priority queue），查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。优先权队列中的元素可以有相同的优先权，查找与删除操作可根据任意优先权进行。最大树（最小树）是每个节点的值都大于（小于）或等于其子节点（如果有的话）值的树。最大堆（最小堆）是最大（最小）的完全二叉树。

32、2.5.3竞赛树2.5.4搜索树2.6 图及其操作图（graph）是一个用线或边连接在一起的顶点或节点的集合。正式一点的说法是，图G=(V,E)是一个V和E的有限集合，元素V称为顶点（vertice,也叫作节点或点），元素E称为边（edge,也叫作弧或连线），E中的每一条边连接V中两个不同的顶点。可以用（i，j）来表示一条边，其中i和j是E所连接的两个顶点。 2.7 常用排序算法 排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列，排序分为两类：内排序和外排序。2.7.1插入排序 每次将一个待排序的数据元素，插入到

33、前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。分为：1 直接插入排序：仅有一个记录的表总是有序的，因此，对n个记录的表，可从第二个记录开始直到第n个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键码有序的表。2 折半插入排序（二分法）：在有序表中确定插入位置，可以不断二分有序表来确定插入位置，即一次比较，通过待插入记录与有序表居中的记录按关键码比较，将有序表一分为二，下次比较在其中一个有序子表中进行，将子表又一分为二。这样继续下去，直到要比较的子表中只有一个记录时，比较一次便确定了插入位置。3 表插入排序：通过链接指针，按关键码的大小，实现从小到大

34、的链接过程，为此需增设一个指针项。操作方法与直接插入排序类似，所不同的是直接插入排序要移动记录，而表插入排序是修改链接指针4 希尔排序(Shells Sort)：1. 选择一个步长序列t1，t2，tk，其中titj，tk=1；2. 按步长序列个数k，对序列进行k趟排序；3. 每趟排序，根据对应的步长ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅步长因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。2.7.2选择排序每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。分为：1 简单选择排序

35、：第一趟：从n个记录中找出关键码最小的记录与第一个记录交换；第二趟，从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录交换；如此，第i趟，则从第i个记录开始的n-i+1个记录中选出关键码最小的记录与第i个记录交换，直到整个序列按关键码有序。2 堆排序：设有n个元素，将其按关键码排序。首先将这n个元素按关键码建成堆，将堆顶元素输出，得到n个元素中关键码最小(或最大)的元素。然后，再对剩下的n-1个元素建成堆，输出堆顶元素，得到n个元素中关键码次小(或次大)的元素。如此反复，便得到一个按关键码有序的序列。2.7.3交换排序两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即

36、进行交换，直到没有反序的数据元素为止。分为：1 冒泡排序：对n个记录的表，第一趟冒泡得到一个关键码最大的记录rn，第二趟冒泡对n-1个记录的表，再得到一个关键码最大的记录rn-1，如此重复，直到n个记录按关键码有序的表。2 快速排序：通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序列分成两部分。其中，一部分所有记录的关键码大于等于支点记录的关键码，另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键码有序。2.7.4二路归并排序 1个元素的表总是有序的。所以对n个元素的待排序列，每

37、个元素可看成1个有序子表长度均为2。再进行两两合并，直到生成n个元素按关键码有序的表。2.7.5基数排序 基数排序是一种借助于多关键码排序的思想，是将单关键码按基数分成“多关键码”进行排序的方法。2.7.6排序算法应用小结(1)若n较小(n=50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而记录本身信息量较大时，用直接选择排序较好。 (2)若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。 (3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序法中被认为是

38、最好的方法。 (4)在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于比较的排序算法，至少需要O(nlog2n)的时间。 (5)当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。3 STL STL 提供了通用的模板化的类和函数，这些类和函数实现了许多为人们普遍使用的算法和数据结构。这些算法和数据结构支持矢量、列表、队列和堆栈。标准模板库的核心有三种基础成分：容器、算法和迭代器。 除容器、算法和迭代器之外，STL还依赖其他几种标准组件，其中最主要的组件

39、是分配器（allocator），谓词（predicate），比较函数和函数对象。每种容器都有优点和缺点。例如，当需要一个随机访问的、类似于数组的对象而且不需要进行太多的插人和删除操作时，采用vector是非常适宜的。list虽然能够提供廉价的插人和删除，但是却以降低速度作为交换。map提供一个关联容器，但却会导致附加的开销。3.1 容器 容器是存放其他对象的对象，容器有顺序容器(如：vector、list、queue)和关联容器(如：map、set)，关联容器使人们可以根据关键字进行有效的检索。例如map容器利用惟一的关键字提供对值的访间。每个容器类都定义一组函数，这些函数可以被应用于该容器。例如，一个列表容器包括插人函数、删除函数和合并元素函数；一个堆栈容器包括用于推入和弹出值的函数。string 类也可以看做是一个容器，因此也可以用迭代器