软考-程序员-专用复习资料

常考基础必知必会

A.排序：排序有儿种，各种排序的比较，哪些排序是稳定的，快排的算法；

B.查找：哈希查找、二叉树查找、折半查找的对比，哈希映射和哈希表的区别？

C.链表和数组的区别，在什么情况下用链表什么情况下用数组？

D.栈和队列的区别？

E.多态，举例说明;overload和override的区别？

F.字符串有关的函数，比如让你写一个拷贝字符串的函数啊，或者字符串反转啊什么

的。strcpy和memcpy?

G.继承、多继承？

H.面向对象有什么好处？

I.说说static的与众不同之处，如果一个变量被声明为static,它会被分配在哪里?在什

么时候分配空间等？

J.什么是虚函数、纯虚函数、虚的析构函数，用途？

K.内存泄漏及解决方法？

网络部分：

OSI模型7层结构，TCP/IP模型结构？

B.TCP/UDP区另I」？

C.TCP建立连接的步骤?

D.香农定理？

二叉树三种遍历的非递归算法(背诵版)

L先序遍历非递归算法

#definemaxsize100

typedefstruct

(

BitreeElem[maxsize];

inttop;

}SqStack;

voidPreOrderUnrec(Bitreet)

{

SqStacks;

Stacklnit(s);

P=t；

while(p!=null||!StackEmpty(s))

|

while(p!=null)〃遍历左子树

(

visite(p->data);

push(s,p);

p=p->lchild;

}//endwhile

if(!StackEmpty(s))〃通过下•次循环中的内嵌while实现右子树遍历

p=pop(s);

p=p->rchild;

}//endif

}//endwhile

}//PreOrderUnrec

2.中序遍历非递归算法

#definemaxsize100

typedefstruct

BitreeElem[maxsize];

inttop;

}SqStack;

voidInOrderUnrec(Bitreet)

SqStacks;

Stacklnit(s);

P=t；

while(p!=null||!StackEmpty(s))

while(p!=null)〃遍历左子树

(

push(s,p);

p=p->lchild;

}//endwhile

if(!StackEmpty(s))

(

p=pop⑸；

visite(p->data);//访问根结点

p=p->rchild;〃通过下■次循环实现右子树遍历

}//endif

}//endwhile

}//InOrderUnrec

3.后序遍历非递归算法

#definemaxsize100

typedefenum{L,R}tagtype;

typedefstruct

(

Bitreeptr;

tagtypetag;

}stacknode;

typedefstruct

stacknodeElem[maxsize];

inttop;

}SqStack;

〃后序遍历

voidPostOrderUnrec(Bitreet)

(

SqStacks;

stacknodex;

Stacklnit(s);

P=t；

do

»

while(p!=null)〃遍历左子树

{

x.ptr=p;

x.tag=L;//标记为左子树

push(s,x);

p=p->lchild;

while(!StackEmpty(s)&&s.Elem[s.top].tag=R)

x=pop(s);

p=x.ptr;

visite(p->data);〃tag为R,表示右子树访问完毕，故访问根结点

)

if(!StackEmpty(s))

(

s.Elem[s.top].tag=R;〃遍历右子树

p=s.Elem[s.top].ptr->rchild;

)

{while(!StackEmpty(s));

}//PostOrderUnrec

3.后序遍历非递归算法

#definemaxsize100

typedefenum{L,R}tagtype;

typedefstruct

(

Bitreeptr;

tagtypetag;

}stacknode;

typedefstruct

stacknodeElem[maxsize];

inttop;

}SqStack;

〃后序遍历

voidPostOrderUnrec(Bitreet)

(

SqStacks;

stacknodex;

Stacklnit(s);

P=t；

do

»

while(p!=null)〃遍历左子树

{

x.ptr=p;

x.tag=L;//标记为左子树

push(s,x);

p=p->lchild;

while(!StackEmpty(s)&&s.Elem[s.top].tag==R)

x=pop(s);

p=x.ptr;

visite(p->data);//tag为R,表示右子树访问完毕，故访问根结点

)

if(!StackEmpty(s))

{

s.Elem[s.top].tag=R;〃遍历右子树

p=s.Elem[s.top].ptr->rchild;

}

{while(!StackEmpty(s));

}//PostOrderUnrec

2、线性表

(1)性表的链式存储方式及以下儿种常用链表的特点和运算：单链表、循环链表，双向

链表，双向循环链表。

(2)单链表的归并算法、循环链表的归并算法、双向链表及双向循环链表的插入和删除

算法等都是较为常见的考查方式。

(3)单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的

各自好处。

3、栈与队列

你可以问一下自己是不是已经知道了以下几点:

(1)栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队

列，链队等。栈与队列存取数据(请注意包括：存利取两部分)的特点。

(2)递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问

题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历

与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。

(3)栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求

考查此为题目的算法设计题不多。

(4)循环队列中判队空、队满条件，循环队列中入队与出队(循环队列在插入时也要判断

其是否已满，删除时要判断其是否已空)算法。

【循环队列的队空队满条件

为了方便起见，约定：初始化建空队时，令

front=rear=0,

当队空时：front=rear,

当队满时：front=rear亦成立，

因此只凭等式front=rear无法判断队空还是队满。

有两种方法处理上述问题：

(1)另设一个标志位以区别队列是空还是满。

(2)少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为

队列“满”状态的标志。

队空时：front=rear,

队满时：(rear+1)%maxsize=front]

如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以

不看书，并不是可以不作题哦。

循环队列的主要操作：

(1)创建循环队列

(2)初始化循环队列

(3)判断循环队列是否为空

(4)判断循环队列是否为满

(5)入队、出队

〃空出头尾之间的一个元素不用

/include

#include

#defineMAXSIZE100

typedefstruct

intelem[MAXSIZE];

intfront,rear;

JQuque;〃定义队头

intinitQue(Quque**q)//初始化

{

(*q)->front=0;

(*q)->rear=0;

)

intisFull(Quque*q)

{

if(q->fh)nt=(q->rear+l)%MAXSIZE)〃判满(空出一个元素不用)刘勉刚

return1;

else

return0;

intinsertQue(Quque**q,intelem)

if(isFull(*q))retum-1;

(*q)->elem[(*q)->rear]=elem;

(*q)->rear=((*q)->rear+1)%MAXS1ZE;〃插入

returnO;

intisEmpty(Quque*q)

ifi(q->front==q->rear)//^lj空

return1;

else

return0;

intdeleteQue(Quque**q,int*pelem)

if(isEmpty(*q))

return0;

*pelem=(*q)->elem[(*q)->front];

(*q)->front=((*q)->front+1)%MAXSIZE;

retumO;

4、串

串一章需要攻破的主要堡垒有：

1.串的基本概念，串与线性表的关系(串是其元素均为字符型数据的特殊线性表)，空串

与空格串的区别，串相等的条件；

2.串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串

长等等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。

3.顺序串与链串及块链串的区别和联系，实现方式。

4.KMP算法思想。KMP中next数组以及nextval数组的求法。明确传统模式匹配算法

的不足，明确next数组需要改进。可能进行的考查方式是：求next和nextval数组值，根据

求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。

5、多维数组和广义表

矩阵包括：对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。

熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。

掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。

6、树与二叉树

树一章的知识点包括：

二叉树的概念、性质和存储结构，二叉树遍历的三种算法（递归与非递归），在三种基本

遍历算法的基础上实现二叉树的其它算法,线索二叉树的概念和线索化算法以及线索化后的

查找算法，最优二叉树的概念、构成和应用，树的概念和存储形式，树与森林的遍历算法及

其与二叉树遍历算法的联系，树与森林和二叉树的转换。

（1）二叉树的概念、性质和存储结构

考查方法可有：直接考查二叉树的定义，让你说明二叉树与普通双分支树（左右子树无

序）的区别;考查满二叉树和完全二叉树的性质，普通二叉树的五个性质：

A.第i层的最多结点数，

B.深度为k的二叉树的最多结点数，

C.n0=n2+l的性质,

D.n个结点的完全二叉树的深度，

E.顺序存储二叉树时孩子结点与父结点之间的换算关系（root从1开始，则左为：2*i,

右为：2*i+l）o

二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合,二叉树的三叉链表表示方

法。

（2）二叉树的三种遍历算法

这一知识点掌握的好坏，将直接关系到树一章的算法能否理解，进而关系到树一章的算

法设计题能否顺利完成。二叉树的遍历算法有三种：先序，中序和后序。其划分的依据是视

其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法，理解其

执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。由于二叉树•章的很多算法,

可以直接根据三种递归算法改造而来(比如：求叶子个数)，所以，掌握了三种遍历的非递归

算法后，对付诸如：“利用非递归算法求二叉树叶子个数”这样的题目就卜笔如有神了。

(3)可在三种遍历算法的基础上改造完成的其它二叉树算法：

求叶子个数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，建立二

叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点，诸如此类

等等等等。如果你可以熟练掌握二叉树的递归和非递归遍历算法，那么解决以上问题就是小

菜一碟了。

(4)线索二叉树：

线索二叉树的引出，是为避免如二叉树遍历时的递归求解。众所周知，递归虽然形式上

比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险,

为了避免此类情况，线索二叉树便堂而皇之地出现了。对于线索二叉树，应该掌握：线索化

的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题

(如：查找某一类线索二叉树中指定结点的前驱或后继结点就是一类常考题)。

(5)最优二叉树(哈夫曼树)：

最优二义树是为了解决特定问题引出的特殊二叉树结构，它的前提是给二义树的每条边

赋予了权值，这样形成的二叉树按权相加之和是最小的。最优二叉树一节，直接考查算法源

码的很少，一般是给你组数据，要求你建立基于这组数据的最优二义树，并求出其最小权

值之和，此类题目不难，属送分题。

（6）树与森林:

二叉树是一种特殊的树，这种特殊不仅仅在于其分支最多为2以及其它特征，一个最重

要的特殊之处是在于：二叉树是有序的!即：二叉树的左右孩子是不可交换的，如果交换了

就成了另外一棵二叉树。树与森林的遍历，不像二叉树那样丰富，他们只有两种遍历算法:

先根与后根（对于森林而言称作：先序与后序遍历）。此二者的先根与后根遍历与二叉树中的

遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序

遍历。二叉树、树与森林之所以能有以上的对应关系，全拜二叉链表所赐。二叉树使用二叉

链表分别存放他的左右孩子，树利用二叉链表存储孩子及兄弟（称孩子兄弟链表），而森林也

是利用二叉链表存储孩子及兄弟。

7、图

1.图的基本概念：图的定义和特点，无向图，有向图，入度，出度，完全图，生成子

图，路径长度，回路，（强）连通图，（强）连通分量等概念。

2.图的几种存储形式：邻接矩阵，（逆）邻接表，十字链表及邻接多重表。在考查时，有

的学校是给出一种存储形式，要求考生用算法或手写出与给定的结构相对应的该图的另一种

存储形式。

3.考查图的两种遍历算法：深度遍历和广度遍历

深度遍历和广度遍历是图的两种基本的遍历算法,这两个算法对图•章的重要性等同于

“先序、中序、后序遍历”对于二叉树一章的重要性。在考查时，图一章的算法设计题常常是

基于这两种基本的遍历算法而设计的，比如：“求最长的最短路径问题''和"判断两顶点间是

否存在长为K的简单路径问题”，就分别用到了广度遍历和深度遍历算法。

4.生成树、最小生成树的概念以及最小生成树的构造：PRIM算法和KRUSKAL算法。

考查时，一般不要求写出算法源码，而是要求根据这两种最小生成树的算法思想写出其

构造过程及最终生成的最小生成树。

5.拓扑排序问题：

拓扑排序有两种方法，一是无前趋的顶点优先算法，二是无后继的顶点优先算法。换句

话说，一种是“从前向后”的排序，一种是“从后向前''排。当然，后一种排序出来的结果是“逆

拓扑有序'’的。

6.关键路径问题：

这个问题是图一章的难点问题。理解关键路径的关键有三个方面：

•是何谓关键路径；

二是最早时间是什么意思、如何求；

三是最晚时间是什么意思、如何求。

简单地说，最早时间是通过“从前向后”的方法求的，而最晚时间是通过“从后向前”的方

法求解的，并且，要想求最晚时间必须是在所有的最早时间都已经求出来之后才能进行。

在实际设计关键路径的算法时，还应该注意以下这•点：采用邻接表的存储结构，求最

早时间和最晚时间要采用不同的处理方法，即：在算法初始时，应该首先将所有顶点的最早

时间全部置为0。关键路径问题是工程进度控制的重要方法，具有很强的实用性。

7.最短路径问题：

V关键路径问题并称为图一章的两只拦路虎。概念理解是比较容易的，关键是算法的理

解。最短路径问题分为两种：•是求从某一点出发到其余各点的最短路径（单源最短路径）;

二是求图中每一对顶点之间的最短路径。这个问题也具有非常实用的背景特色，一个典型的

应该就是旅游景点及旅游路线的选择问题。解决第一个问题用DIJSKTRA算法，解决第二

个问题用FLOYD算法，注意区分。

8、查找(search)

先弄清楚以下几个概念：关键字、主关键字、次关键字的含义;静态查找与动态查找的

含义及区别;平均查找长度ASL的概念及在各种查找算法中的计算方法和计算结果，特别是

一些典型结构的ASL值，应该记住。

一般将search分为三类：在顺序表上的查找;在树表上的查找;在哈希表上的查找。

(1)线性表上的查找：

主要分为三种线性结构：

顺序表——传统查找方法：逐个比较；

有序顺序表——二分查找法(注意适用条件以及其递归实现方法)；

索引顺序表——对索引结构，采用索引查找算法。注意这三种表下的ASL值以及三种

算法的实现。

(2)树表上的查找：

树表主要分为以下几种：二叉排序树(即二叉查找树)，平衡二叉查找树(AVL树)，B树,

键树。其中，尤以前两种结构为重，也有部分名校偏爱考B树的。由于二叉排序树与平衡

二叉树是一种特殊的二叉树。

二叉排序树，简言之，就是“左小右大”，它的中序遍历结果是一个递增的有序序列。平

衡二叉排序树是二叉排序树的优化，其本质也是一种二叉排序树，只不过，平衡排序二叉树

对左右子树的深度有了限定：深度之差的绝对值不得大于1。对于二叉排序树，“判断某棵

二叉树是否二叉排序树''这••算法经常被考到，可用递归，也可以用非递归。平衡二叉树的

建立也是一个常考点，但该知识点归根结底还是关注的平衡二叉树的四种调整算法，调整的

一个参照是：调整前后的中序遍历结果相同。

B树是二叉排序树的进一步改进，也可以把B树理解为三叉、四叉….排序树。除B树

的查找算法外，应该特别注意•下B树的插入和删除算法，因为这两种算法涉及到B树结

点的分裂和合并，是一个难点。键树(keywordtree),又称数字搜索树(digitalsearchtree)或字

符树。trie树也可说等同于键树或属于键树的一种。键树特别适用于查找英文单词的场合。

一般不要求能完整描述算法源码，多是根据算法思想建立键树及描述其大致查找过程。

(3)基于哈希表的查找算法：

哈希译自“hash”一词，意为“散列”或“杂凑”。哈希表查找的基本思想是：根据当前待查

找数据的特征，以记录关键字为自变量，设计个function,该函数对关键字进行转换后，

其解释结果为待查的地址。基于哈希表的考查点有：哈希函数的设计，冲突解决方法的选择

及冲突处理过程的描述。

9、内部排序

考查你对书本上的各种排序算法及其思想以及其优缺点和性能指标(时间复杂度)能否

了如指掌。

排序方法分类有：插入、选择、交换、归并、计数等五种排序方法。

(1)插入排序中又可分为：直接插入、折半插入、2路插入(?)、希尔排序。这几种插入排

序算法的最根本的不同点，说到底就是根据什么规则寻找新元素的插入点。直接插入是依次

寻找，折半插入是折半寻找，希尔排序，是通过控制每次参与排序的数的总范隹1“由小到大”

的增量来实现排序效率提高的目的。

(2)交换排序，又称冒泡排序，在交换排序的基础上改进又可以得到快速排序。快速排

序的思想，-语以敝之：用中间数将待排数据组吩为二。

(3)选择排序可以分为：简单选择、树选择、堆排序。选择排序相对于前面几种排序算

法来说，难度大一点。这三种方法的不同点是，根据什么规则选取最小的数。

简单选择，是通过简单的数组遍历方案确定最小数；

树选择，是通过“锦标赛”类似的思想，让两数相比，不断淘汰较大(小)者，最终选出最

小(大)数；

而堆排序，是利用堆这种数据结构的性质，通过堆元素的删除、调整等一系列操作将最

小数选出放在堆顶。堆排序中的堆建立、堆调整是重要考点。

(4)归并排序，是通过“归并”这种操作完成排序的目的，既然是归并就必须是两者以上

的数据集合才可能实现归并。所以，在归并排序中，关注最多的就是2路归并。算法思想比

较简单，有一点，要铭记在心：归并排序是稳定排序。

(5)基数排序，是一种很特别的排序方法，也正是由于它的特殊，所以，基数排序就比

较适合于一些特别的场合，比如扑克牌排序问题等。基数排序，又分为两种：多关键字的排

序(扑克牌排序)，链式排序(整数排序)。基数排序的核心思想也是利用“基数空间”这个概念

将问题规模规范、变小，并且，在排序的过程中，只要按照基排的思想，是不用进行关键字

比较的，这样得出的最终序列就是一个有序序列。

本章各种排序算法的思想以及伪代码实现，及其时间复杂度都是必须掌握的。

///////〃〃//////〃//〃/////〃//〃〃//〃〃////稳定性分析///〃/〃////〃////////〃////〃/〃/〃〃/////〃///

排序算法的稳定性,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序

和排序后它们两个的前后位置顺序相同。

稳定性的好处：若排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上

排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，

逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算

法稳定，对基于比较的排序算法而言，元素交换的次数可能会少•些(个人感觉，没有证实)。

分析一下常见的排序算法的稳定性，每个都给出简单的理由。

(1)冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，

交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩

交换•下的;如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来,

这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算

法。

(2)选择排序

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元

素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，

因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小

的元素乂出现在个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口,

举个例子，序列58529,我们知道第一遍选择第1个元素5会和2交换，那么原序列中

2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

(3)插入排序

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个

有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要

插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则•直往前

找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元

素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就

是排好序后的顺序，所以插入排序是稳定的。

(4)快速排序

快速排序有两个方向，左边的i下标一直往右走，当a[i]v=a[center_index],其中cent

erjndex是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，

当a[j]>a[center_index]»如果i和j都走不动了，i<=j,交换a[i]和a[j],重复上面的过程，

直到问。交换a[j]和a[centerjndex],完成一趟快速排序。在中枢元素和a|j]交换的时候，

很有可能把前面的元素的稳定性打乱，比如序列为53343891011,现在中枢元素5

和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个

不稳定的排序算法，不稳定发生在中枢元素和aU]交换的时刻。

(5)归并排序

归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)

或者2个序列(1次比较和交换)，然后把各个有序的段序列合并成一个有序的长序列，不断合

并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素

如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中,

稳定是是否受到破坏?没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处

在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳

定的排序算法。

(6)基数排序

基数排序是按照低位先排序，然后收集;再按照高位排序，然后再收集;依次类推，直到

最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后

的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,

分别收集，所以其是稳定的排序算法。

(7)希尔排序(shell)

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大,

所以插入排序的元素个数很少，速度很快;当元素基本有序了，步长很小，插入排序对于有

序的序列效率很高。所以，希尔排序的时间复杂度会比。(22)好一些。由于多次插入排序，

我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程

中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序

是不稳定的。

(8)堆排序

我们知道堆的结构是节点i的孩子为2*i和2*i+l节点，大顶堆要求父节点大于等于其

2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过

程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆)，这3个元素之间

的选择当然不会破坏稳定性。但当为n/2-1,n/2-2,...1这些个父节点选择元素时，就会破坏

稳定性。有可能第n/2个父节点交换把后面•个元素交换过去了，而第n/2-l个父节点把后

面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排

序不是稳定的排序算法。

冒泡排序插入排序二路插入排序希尔排序快速排序选择排序归并排序堆排序算法

的C/C++实现

#include

usingnamespacestd;

〃交换两个数的值

voidswap(int&a,int&b)

(

inttmp;

tmp=a;

a=b;

b=tmp;

〃屏幕输出数组

voiddisplay(intarray[],intlen)

cout«HtheresuItis:"«ENDL;<p>

for(inti=0;i<len;i-H-)

(

cout«ARRAY[I]«np?;<>

重者在下为止。

时间复杂度o(nA2)

空间复杂度0(1)

比较次数n(n+l)/2

*/

voidbubble_sort(intarray[],intlen)

(

for(inti=len-1;i>=0;i—)

{

fbr(intj=0;j<i;j++)

if(array[j]>array[j+l])

swap(array[j],arrayfj+l]);

直接插入排序

算法思想：把n个待排序的元素看成为一个有序表和•个无序表，开始时有序表中只包

含一个元

素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它

插入到有序表中的适当位置，使之成为新的有序表，重复n-l次可完成排序过程。

时间复杂度。(22)

空间复杂度0(1)

比较次数n(n+l)/2

*/

voidinsert_sort(intarray[],intlen)

{

inttmp,i,j;

fbr(i=l;i<len;i-H-)

if(array[i]<array[i-l])

tmp=array[i];

array[i]=array[i-l];

〃插入到相应位置

for(j=i-2;j>=0;j-)

(

//往后移

if(array[j]>tmp)

array[j+l]=array[j];

else

(

array[j+l]=tmp;

break;

)

iKj=-1)

array[j+1]=tmp;

2-路插入排序

算法思想：增加一个辅助空间d,把r[l]赋值给d[l],并将d[l]看成是排好序后处于中间

位置的记录。然后从r[2]开始依次插入到d[l]之前或之后的有序序列中。

时间复杂度。(22)

空间复杂度0(1)

比较次数n(n+l)/2

*/

voidbi_insert_sort(intarray[],intlen)

{

int*arrd=(int*)malloc(sizeof(int)*len);

arr_d[O]=array[0];

inthead=O,tail=0;

fbr(inti=l;i<len;i-H-)

if(array[i]>arr_d[O])

intj；

for(j=tail;j>O;j-)

if(array[i]<ARR_D[J])<p>

arr_d|j+l]=arr_d[j];

else

break;

arrdfj+l]=array[i];

tail+=1;

else

if(head=0)

arr_d[len-l]=array[i];

head=len-l;

else

{

intj;

for(j=head;j<=len-l;j-H-)

{

if(array[i]>arr_d[j])

arr_d[j-l]=arr_d[j];

else

break;

arr_d[j-l]=array[i];

head-=1;

for(inti=0;i<len;i-H-)

intpos=(i+head);

ifi(pos>=len)pos-=len;

array[i]=arr_d[pos];

}

free(arrd);

}

/*

希尔排序

算法思想：先将整个待排序记录分割成若干子序列分别进行直接插入排

序，待整个序列中的记录基本有序时，再对全体记录进行一

次直接插入排序

时间复杂度o(nA2)

空间复杂度0(1)

比较次数？

*/

voidshell_insert(intarray[],intd,intlen)

(

inttmp,j;

for(inti=d;i<len;i-H-)

{

if(array[i]<array[i-d])

(

tmp=array[i];

j=i-d;

do

(

array[j+d]=array[j]；

j=j-d;

}while(j>=0&&tmp<array[j]);

array[j+d]=tmp;

voidshell_sort(intarray[],intlen)

intinc=len;

do

(

inc=inc/2;

shell_insert(array,inc,len);

}while(inc>1);

)

/*

快速排序

算法思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题。

递归地解这些子问题，然后将这些子问题的解组合成为原问题的解。

时间复杂度o(nlogn)

空间复杂度o(logn)

比较次数？

*/

voidquick_sort(intarray[],intlow,inthigh)

if(low<high)

intpivotloc=partition(array,low,high);

quick_sort(array,low,pivotloc-1);

quick_sort(array,pivotloc+1,high);

intpartition(intarray口,intlow,inthigh)

intpivotkey=array[low];

while(low<high)

while(low<high&&array[high]>=pivotkey)

-high;

swap(array[low],array[high]);

while(Iow<high&&array[low]<=pivotkey)

++low;

swap(array[low],array[high]);

array[low]=pivotkey;

returnlow;

/*

直接选择排序

算法思想：每•趟在n-i+1个记录中选取关键字最小的记录作为有序序列中的第i个记

录

时间复杂度o(nA2)

空间复杂度0(1)?

比较次数n(n+l)/2

*/

intSelectMinKey(intarray[],intiPos,intlen)

intret=0;

fbr(inti=iPos;i<len;i++)

if(array[ret]>array[i])

ret=i;

returnret;

voidselect_sort(intarray[],intlen)

for(inti=0;i<len;i++)

intj=SelectMinKey(array,i,len);

if(i!=j)

(

swap(array[i],array(j]);

归并排序

算法思想：设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..

m],R[m+l..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成

后将R1复制回R[low..high]中。

时间复杂度o(nlogn)

空间复杂度o(n)

比较次数？

*/

voidmerge(intarray[],inti,intm,intn)

intj,k;

intiStart=i,iEnd=n;

intarrayDest[256];

fbr(j=m+l,k=i;i<=m&&j<=n;++k)

{

if(array[i]<arrayfj])

arrayDest[k]=array[i++];

else

arrayDest[k]=array[j++];

}

if(i<=m)

fbr(;k<=n;k++,i++)

arrayDest[k]=array[i];

if(j<=n)

fbr(;k<=n;k++,j-H-)

arrayDest[k]=array[j];

fbr(j=iStart;j<=iEnd;j-H-)

array[j]=arrayDest[j];

}

voidmerge_sort(intarray[],ints,intt)

{

intin;

if(s<t)

(

m=(s+t)/2;

merge_sort(atTay,s,m);

merge_sort(array,m+l,t);

merge(array,s,m,t);

堆排序

算法思想：堆排序(HeapSort)是指利用堆(heaps)这种数据结构来构造的一种排序算法。

堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是

小于(或者大于)它的父节点。

时间复杂度o(nlogn)

空间复杂度0(1)

比较次数：较多

voidheap_adjust(intarray[],inti,intlen)

intrc=array[i];

fbr(intj=2*i;j

if(j<len&&array[j]<array[j+l])j-H-;

ififrc>=array[j])break;

array[i]=array[j];i=j;

array[i]=rc;

voidheap_sort(intarray[],intlen)

inti;

for(i=(len-1)/2;i>=0;i—)

heap_adjust(array,i,len);

for(i=(len-1);i>0;i—)

swap(array[0],array[i]);〃弹出最大值，重新对i・l个元素建堆

heapadjust(array,0,i-l)；

intmain()

intarray[]={45,56,76,234,1,34,23,2,3,55,88,100};

intlen=sizeofi(array)/sizeofi(int);

//bubble_sort(array,len);〃冒泡排序

/*insert_sort(array,len);*/〃插入排序

/*bi_insert_sort(array,len);*///二路插入排序

/*shell_sort(array,len);*/〃希尔排序

/*quick_sort(array,0,len-1);*/〃快速排序

/*select_sort(array,len);*/〃选择排序

/*merge_sort(array,0,len-1);*/〃归并排序

heap_sort(array,len);//堆排序

display(array,len);

return0;

)

<|>对排序算法的总结

按平均时间将排序分为四类：

(1)平方阶(O(n2))排序

一般称为简单排序，例如直接插入、直接选择和冒泡排序;

(2)线性对数阶(O(nlgn))排序

如快速、堆和归并排序；

(3)O(nl+£)阶排序

£是介于0和1之间的常数，即0<£<1,如希尔排序;

(4)线性阶(0(n))排序

如桶、箱和基数排序。

各种排序方法比较

简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。

影响排序效果的因素

因为不同的排序方法适应不同的应用环境和要求,所以选择合适的排序方法应综合考虑

下列因素：

①待排序的记录数目n;

②记录的大小(规模)；

③关键字的结构及其初始状态；

④对稳定性的要求；

⑤语言工具的条件；

⑥存储结构；

⑦时间和辅助空间复杂度等。

不同条件下，排序方法的选择

(1)若n较小(如n<50),可采用直接插入或直接选择排序。

当记录规模较小时.，直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,

应选直接选择排序为宜。

(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜;

(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排

序。

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机

分布时，快速排序的平均时间最短；

堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这

两种排序都是不稳定的。

若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排

序算法并不值得提倡，通常可以将它和直接插入排序结合在起使用。先利用直接插入排序

求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归

并排序仍是稳定的。

10、OSI模型7层结构，TCP/IP模型结构？

osi参考模型

osi参考模型中的数据封装过程

下面的图表试图显示不同的TCP/IP和其他的协议在最初OSI模型中的位置：

7应用层例如HTTP、SMTP、SNMP、FTP、Telnet、SIP、SSH、NFS、RTSP、XMPP、

Whois,ENRP

6表示层例如XDR、ASN.l、SMB、AFP、NCP

5会话层例如ASAP、TLS、SSH、ISO8327/CCITTX.225、RPC、NetBIOS、ASP、

Winsock、BSDsockets

4传输层例如TCP、UDP、RTP、SCTP、SPX、ATP>IL

3网络层例如IP、ICMP、IGMP、IPX、BGP、OSPF,RIP、IGRP,EIGRP>ARP、RA

RP、X.25

2数据链路层例如Ethernet、Tokenring^HDLC、Framerelay>ISDN>ATM、802.11

WiFi、FDDLPPP

1物理层例如wire、radio、fiberoptic、Carrierpigeon

tcp/ip参考模型

tcp/ip参考模型分为四个层次：应用层、传输层、网络互连层和主机到网络层：

tcp/ip参考模型的层次结构

通常人们认为OSI模型的最上面三层（应用层、表示层和会话层）在TCP/IP组中是一个

应用层。由于TCP/IP有一个相对较弱的会话层，由TCP和RTP下的打开和关闭连接组成,

并且在TCP和UDP下的各种应用提供不同的端口号，这些功能能够被单个的应用程序（或

者那些应用程序所使用的库）增加。与此相似的是，IP是按照将它下面的网络当作•个黑盒

子的思想设计的，这样在讨论TCP/IP的时候就可以把它当作一个独立的层。

4应用层

（OSI5到7层）例如HTTP、FTP,DNS

（如BGP和RIP这样的路由协议，尽管由于各种各样的原因它们分别运行在TCP和UD

P上，仍然可以将它们看作网络层的一部分）

3传输层

（0SI4和5层）例如TCP、UDP、RTP、SCTP

（如OSPF这样的路由协议，尽管运行在IP上也可以看作是网络层的一部分）

2网络互连层

（0SI3层）对于TCP/IP来说这是因特网协议（IP）

（如ICMP和IGMP这样的必须协议尽管运行在IP上，也仍然可以看作是网络互连层的

一部分;ARP不运行在IP上）

1网络接口层

（OSH和2层）例如Ethernet、Wi-Fi、MPLS等。

应用层

该层包括所有和应用程序协同工作，利用基础网络交换应用程序专用的数据的协议。应

用层是大多数普通与网络相关的程序为了通过网络与其他程序通信所使用的层。这个层的处

理过程是应用特有的;数据从网络相关的程序以这种应用内部使用的格式进行传送，然后被

编码成标准协议的格式。

一些特定的程序被认为运行在这个层上。它们提供服务直接支持用户应用。这些程序和

它们对应的协议包括HTTP（TheWorldwideWeb）、FTP（文件传输）、SMTP（电子邮件）、SS

H（安全远程登陆）、DNS（名称<->IP地址寻找）以及许多其他协议。

一旦从应用程序来的数据被编码成一个标准的应用层协议，它将被传送到IP栈的下一

层。

在传输层，应用程序最常用的是TCP或者UDP,并且服务器应用程序经常与一个公开

的端口号相联系。服务器应用程序的端口由IntemetAssignedNumbersAuthority（IANA）正式

地分配，但是现今一些新协议的开发者经常选择它们自己的端口号。由于在同一个系统上很

少超过少数几个的服务器应用，端口冲突引起的问题很少。应用软件通常也允许用户强制性

地指定端口号作为运行参数。

连结外部的客户端程序通常使用系统分配的•个随机端口号。监听•个端口并且然后通

过服务器将那个端口发送到应用的另外一个副本以建立对等连结（如IRC上的dec文件传输）

的应用也可以使用•个随机端口，但是应用程序通常允许定义•个特定的端口范围的规范以

允许端口能够通过实现网络地址转换（NAT）的路由器映射到内部。

每一个应用层（TCP/IP参考模型的最高层）协议般都会使用到两个传输层协议之一：

面向连接的TCP传输控制协议和无连接的包传输的UDP用户数据报文协议。

常用的应用层协议有：

运行在TCP协议上的协议：

HTTP（HypertextTransferProtocol,超文本传输协议），主要用于普通浏览。

HTTPS（HypertextTransferProtocoloverSecureSocketLayer,orHTTPoverSSL,安

全超文本传输协议）,HTTP协议的安全版本。

FTP（FileTransferProtocol,文件传输协议），由名知义，用于文件传输。

POP3（PostOfficeProtocol,version3,邮局协议），收邮件用。

SMTP（SimpleMailTransferProtocol.简单邮件传输协议），用来发送电子邮件。

TELNET（TeletypeovertheNetwork,网络电传），通过•个终端（terminal）登陆到网络。

SSH（SecureShell,用于替代安全性差的TELNET）,用于加密安全登陆。

运行在UDP协议上的协议：

BOOTP（BootProtocol,启动协议），应用于无盘设备。

NTP（NetworkTimeProtocol,网络时间协议），用于网络同步。

其他：

DNS（DomainNameService,域名服务），用于完成地址查找，邮件转发等工作（运行在

TCP和UDP协议上）。

ECHO（氏hoProtocol,回绕协议），用于查错及测量应答时间（运行在TCP和UDP协议上）。

SNMP（SimpleNetworkManagementProtocol,筒单网络管理协议），用于网络信息的收

集和网络管理。

DHCP（DynamicHostConfigurationProtocol,动态主机配置协议），动态配置IP地址。

ARP（AddressResolutionProtocol,地址解析协议），用于动态解析以太网硬件的地址。

传输层

传输层的协议，能够解决诸如可靠性（“数据是否已经到达目的地?”）和保证数据按照正确

的顺序到达这样的问题。在TCP/IP协议组中，传输协议也包括所给数据应该送给哪个应用

程序。

在TCP/IP协议组中技术上位于这个层的动态路由协议通常被认为是网络层的一部分；

一个例子就是OSPFQP协议89）。

TCP（IP协议6）是一个“可靠的”、面向连结的传输机制，它提供一种可靠的字节流保证

数据完整、无损并且按顺序到达。TCP尽量连续不断地测试网络的负载并且控制发送数据

的速度以避免网络过载。另外，TCP试图将数据按照规定的顺序发送。这是它与UDP不同

之处，这在实时数据流或者路由高网络层丢失率应用的时候可能成为一个缺陷。

较新的SCTP也是一个“可靠的“、面向连结的传输机制。它是面向纪录而不是面向字节

的，它在一个单独的连结上提供了通过多路复用提供的多个子流。它也提供了多路自寻址支

持，其中连结终端能够被多个IP地址表示（代表多个物理接口），这样的话即使其中一个连

接失败了也不中断。它最初是为电话应用开发的（在IP上传输SS7）,但是也可以用于其他的

应用。

UDP（IP协议号17）是一个无连结的数据报协议。它是一个"besteffbrt”或者“不可靠”协

议——不是因为它特别不可靠，而是因为它不检查数据包是否已经到达目的地，并且不保证

它们按顺序到达。如果一个应用程序需要这些特点，它必须自己提供或者使用TCP。

UDP的典型性应用是如流媒体（音频和视频等）这样按时到达比可靠性更重要的应用，或

者如DNS查找这样的简单查询/响应应用，如果建立可靠的连结所作的额外工作将是不成比

例地大。

DCCP目前正由IEFT开发。它提供TCP流动控制语义，但对于用户来说保留了UDP

的数据报服务模型。

TCP和UDP都用来支持一些高层的应用。任何给定网络地址的应用通过它们的TCP或

者UDP端口号区分。根据惯例使一些大众所知的端口与特定的应用相联系。

RTP是为如音频和视频流这样的实时数据设计的数据报协议。RTP是使用UDP包格式

作为基础的会话层，然而据说它位于因特网协议栈的传输层。

网络互连层

正如最初所定义的，网络层解决在•个单•网络上传输数据包的问题。类似的协议有X.

25和ARPANET的Host/IMPProtocol.,

随着因特网思想的出现，在这个层上添加了附加的功能，也就是将数据从源网络传输到

目的网络。这就牵涉到在网络组成的网上选择路径将数据包传输，也就是因特网。

在因特网协议组中，1P完成数据从源发送到目的基本任务。IP能够承载多种不同的高

层协议的数据;这些协议使用一个唯一的IP协议号进行标识。ICMP和IGMP分别是1和2。

一些IP承载的协议，如ICMP（用来发送关于IP发送的诊断信息）和IGMP（用来管理多

播数据），它们位于IP层之上但是完成网络层的功能，这表明了因特网和OSI模型之间的不

兼容性。所有的路由协议，如BGP、OSPF、和RIP实际上也是网络层的一部分，尽管似

乎它们应该属于更高的协议栈。

网络接口层

网络接口层实际上并不是因特网协议组中的一部分,但是它是数据包从一个设备的网络

层传输到另外一个设备的网络层的方法。这个过程能够在网卡的软件驱动程序中控制，也可

以在韧体或者专用芯片中控制。这将完成如添加报头准备发送、通过物理媒介实际发送这样

一些数据链路功能。另一端，链路层将完成数据帧接收、去除报头并且将接收到的包传到网

络层。

然而，链路层并不经常这样简单.它也可能是•个虚拟专有网络（VPN）或者隧道，在这

里从网络层来的包使用隧道协议和其他（或者同样的）协议组发送而不是发送到物理的接口

±oVPN和隧道通常预先建好，并且它们有一些直接发送到物理接口所没有的特殊特点(例

如，它可以加密经过它的数据)。由于现在链路“层”是一个完整的网络，这种协议组的递归

使用可能引起混淆。但是它是一个实现常见复杂功能的一个优秀方法。(尽管需要注意预防

一个已经封装并且经隧道发送卜去的数据包进行再次地封装和发送)。

1物理层(physicallayer)

物理层规定了激活、维持、关闭通信端点之间的机械特性、电