2018年国家电网考试备考计算机之数据结构与算法

华图教育 | 2017-11-02

领取最新备考资料

2018年国家电网公司招聘公告预计于2017年10月末(一批)、2018年3月(二批)、2018年5月(三批)发布，届时广大考生请及时关注华图教育事业单位频道，我们会第一时间发布国家电网考试信息!更多2018年国家电网备考资料，尽在事业单位频道(http://sydw.huatu.com/)!

计算机——数据结构与算法

1.数据结构

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为：Data_Structure=(D,R)，其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。

数据的逻辑结构：指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。逻辑结构包括：1.集合2.线性结构3.树形结构4.图形结构

2.数组 (Array)

在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。在C语言中，数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。

数组类别：

多维数组

有时需要追踪记录数组中的相关信息。

例如，为了追踪记录计算机屏幕上的每一个像素，需要引用它的 X、Y坐标。这时应该用多维数组存储值。

可用 Visual Basic 声明多维数组。

例如，下面的语句声明了一个过程内的 10 × 10 的二维数组。

Static MatrixA (9,9) As Double

可用显式下界来声明两个维数或两个维数中的任何一个：

Static MatrixA (1 To 10,1 To 10) As Double

可以将所有这些推广到二维以上的数组。例如：

Dim MultiD (3,1 To 10,1 To 15)

这个声明建立了三维数组，大小为 4 × 10 × 15。元素总数为三个维数的乘积，为 600。

注意

在增加数组的维数时，数组所占的存储空间会大幅度增加，所以要慎用多维数组。使用 Variant 数组时更要格外小心，因为他们需要更大的存储空间。

用循环操作数组：

可以用 For循环嵌套有效的处理多维数组。例如，在 MatrixA 中基于每个元素在数组中的位置为其赋值：

Dim I As Integer,J As Integer

Static MatrixA(1 To 10,1 To 10) As Double

For I = 1 To 10

For J = 1 To 10

MatrixA (I,J) = I * 10 + J

Next J

Next I

一维数组

定义

一维数组是最简单的数组，其逻辑结构是线性表。要使用一维数组，需经过定义、初始化和应用等过程。

数组声明

在数组的声明格式里，“数据类型”是声明数组元素的数据类型，可以是java语言中任意的数据类型，包括简单类型和结构类型。“数组名”是用来统一这些相同数据类型的名称，其命名规则和变量的命名规则相同。

数组声明之后，接下来便是要分配数组所需要的内存，这时必须用运算符new，其中“个数”是告诉编译器，所声明的数组要存放多少个元素，所以new运算符是通知编译器根据括号里的个数，在内存中分配一块空间供该数组使用。利用new运算符为数组元素分配内存空间的方式称为动态分配方式。

举例：

int[]x; //声明名称为x的int型数组

x=new int[10]; //x数组中包含有10个元素，并为这10个元素分配内存空间

在声明数组时，也可以将两个语句合并成一行，格式如下：

数据类型[]数组名= new 数据类型[个数];

利用这种格式在声明数组的同时，也分配一块内存供数组使用。如上面的例子可以写成：

int[]x = new int [10];

等号左边的int[]x相当于定义了一个特殊的变量x，x的数据类型是一个对int型数组对象的引用，x就是一个数组的引用变量，其引用的数组元素个数不定。等号右边的new int[10]就是在堆内存里创建一个具有10个int型变量的数组对象。int[]x = new int [10];就是将右边的数组对象赋值给左边的数组引用变量。
#p#副标题#e#

二维数组

定义

前面介绍的数组只有一个下标，称为一维数组，其数组元素也称为单下标变量。在实际问题中有很多量是二维的或多维的，因此C语言允许构造多维数组。多维数组元素有多个下标，以标识它在数组中的位置，所以也称为多下标变量。本小节只介绍二维数组，多维数组可由二维数组类推而得到。二维数组类型说明的一般形式是：

类型说明符数组名[常量表达式1][常量表达式2]…;

其中常量表达式1表示第一维下标的长度，常量表达式2 表示第二维下标的长度。例如：

int a[3][4]; 说明了一个三行四列的数组，数组名为a，其下标变量的类型为整型。该数组的下标变量共有3×4个，即：

a[0][0],a[0][1],a[0][2],a[0][3]

a[1][0],a[1][1],a[1][2],a[1][3]

a[2][0],a[2][1],a[2][2],a[2][3]

二维数组在概念上是二维的，即是说其下标在两个方向上变化，下标变量在数组中的位置也处于一个平面之中，而不是象一维数组只是一个向量。但是，实际的硬件存储器却是连续编址的，也就是说存储器单元是按一维线性排列的。如何在一维存储器中存放二维数组，可有两种方式：一种是按行排列，即放完一行之后顺次放入第二行。另一种是按列排列，即放完一列之后再顺次放入第二列。在C语言中，二维数组是按行排列的。在如上中，按行顺次存放，先存放a[0]行，再存放a[1]行，最后存放a[2]行。每行中有四个元素也是依次存放。由于数组a说明为

int类型，该类型占两个字节的内存空间，所以每个元素均占有两个字节(图中每一格为一字节)。

元素的表示方法

二维数组的元素也称为双下标变量，其表示的形式为：数组名[下标][下标]

其中下标应为整型常量或整型表达式。例如：a[3][4] 表示a数组三行四列的元素。

下标变量和数组说明在形式中有些相似，但这两者具有完全不同的含义。数组说明的方括号中给出的是某一维的长度，即可取下标的最大值; 而数组元素中的下标是该元素在数组中的位置标识。前者只能是常量，后者可以是常量，变量或表达式。

一个学习小组有5个人，每个人有三门课的考试成绩。求全组分科的平均成绩和各科总平均成绩。

课程成绩姓名Math　C　DBASE

张　80　75　92

王　61　65　71

李　59　63　70

赵　85　87　90

周　76　77　85

可设一个二维数组a[5][3]存放五个人三门课的成绩。再设一个一维数组v[3]存放所求得各分科平均成绩，设变量l为全组各科总平均成绩。编程如下：

void main()

{

int i,j,s=0,l,v[3],a[5][3];

printf("input score\n");

for(i=0;i<3;i++){

for(j=0;j<5;j++)

{ scanf("%d",&a[j]);

s=s+a[j];}

v[i]=s/5;

s=0;

}

l=(v[0]+v[1]+v[2])/3;

printf("math:%d\nc languag:%d\ndbase:%d\n",v[0],v[1],v[2]);

printf("total:%d\n",l);

} for(i=0;j<3;i++)

for(j=0;j<5;j++)

{ scanf("%d",&a[j]);

s=s+a[j];}

v=s/5;

s=0;

}

l=(v[0]+v[1]+v[2])/3;

程序中首先用了一个双重循环。在内循环中依次读入某一门课程的各个学生的成绩，并把这些成绩累加起来，退出内循环后再把该累加成绩除以5送入v之中，这就是该门课程的平均成绩。外循环共循环三次，分别求出三门课各自的平均成绩并存放在v数组之中。退出外循环之后，把v[0],v[1],v[2]相加除以3即得到各科总平均成绩。最后按题意输出各个成绩。
#p#副标题#e#

初始化

二维数组初始化也是在类型说明时给各下标变量赋以初值。二维数组可按行分段赋值，也可按行连续赋值。例如对数组a[5][3]：

1.按行分段赋值可写为static int a[5][3]={ {80,75,92},{61,65,71},{59,63,70},{85,87,90},{76,77,85} };

2.按行连续赋值可写为static int a[5][3]={ 80,75,92,61,65,71,59,63,70,85,87,90,76,77,85 };

这两种赋初值的结果是完全相同的。

void main()

{

int i,j,s=0,l,v[3];

static int a[5][3]={ {80,75,92},{61,65,71},{59,63,70},

{85,87,90},{76,77,85} };

for(i=0;i<3;i++)

{ for(j=0;j<5;j++)

s=s+a[j];

v=s/5;

s=0;

}

l=(v[0]+v[1]+v[2])/3;

printf("math:%d\nc languag:%d\ndbase:%d\n",v[0],v[1],v[2]);

printf("total:%d\n",l);

}

初始化的额外说明

对于二维数组初始化赋值还有以下说明：

1.可以只对部分元素赋初值，未赋初值的元素自动取0值。

例如：static int a[3][3]={,,}; 是对每一行的第一列元素赋值，未赋值的元素取0值。赋值后各元素的值为：1 0 02 0 03 0 0

static int a [3][3]={{0,1},{0,0,2},}; 赋值后的元素值为 0 1 00 0 23 0 0

2.如对全部元素赋初值，则第一维的长度可以不给出。

例如：static int a[3][3]={1,2,3,4,5,6,7,8,9}; 可以写为：static int a[][3]={1,2,3,4,5,6,7,8,9};

分解

数组是一种构造类型的数据。二维数组可以看作是由一维数组的嵌套而构成的。设一维数组的每个元素都又是一个数组，就组成了二维数组。当然，前提是各元素类型必须相同。

根据这样的分析，一个二维数组也可以分解为多个一维数组。C语言允许这种分解有二维数组a[3][4]，可分解为三个一维数组，其数组名分别为a[0],a[1],a[2]。对这三个一维数组不需另作说明即可使用。这三个一维数组都有4个元素，例如：一维数组a[0]的元素为a[0][0],a[0][1],a[0][2],a[0][3]。最后必须强调的是，a[0],a[1],a[2]不能当作下标变量使用，它们是数组名，不是一个单纯的下标变量。

字符数组

用来存放字符量的数组称为字符数组。

字符数组类型说明的形式与前面介绍的数值数组相同。例如：char c[10]; 由于字符型和整型通用，也可以定义为int c[10]但这时每个数组元素占2个字节的内存单元。

字符数组也可以是二维或多维数组，例如：char c[5][10];即为二维字符数组。

字符数组也允许在类型说明时作初始化赋值。例如：static char c[10]={`c`,` `,`p`,`r`,o`,g`,r`,`a`,`m`};赋值后各元素的值为：数组C c[0]c[1]c[2]c[3]c[4]c [5]c[6]c[7]c[8]c[9]其中c[9]未赋值，由系统自动赋予0值。

当对全体元素赋初值时也可以省去长度说明。例如：static char c[]={`c`,` `,`p`,`r`,`o`,`g`,`r`,`a`,`m`};这时C数组的长度自动定为9。

main()

{

int i,j;

char a[][5]={{'B','A','S','I','C',},{'d','B','A','S','E'}};

for(i=0;i<=1;i++)

{

for(j=0;j<=4;j++)

printf("%c",a[j]);

printf("\n");

}

本例的二维字符数组由于在初始化时全部元素都赋以初值，因此一维下标的长度可以不加以说明。字符串在C语言中没有专门的字符串变量，通常用一个字符数组来存放一个字符串。在2.1.4节介绍字符串常量时，已说明字符串总是以'\0'作为串的结束符。因此当把一个字符串存入一个数组时，也把结束符'\0'存入数组，并以此作为该字符串是否结束的标志。有了'\0'标志后，就不必再用字符数组的长度来判断字符串的长度了。
#p#副标题#e#

C语言允许用字符串的方式对数组作初始化赋值。例如：

static char c[]={'c',' ','p','r','o','g','r','a','m'}; 可写为：

static char c[]={"C program"}; 或去掉{}写为：

static char c[]="C program";

用字符串方式赋值比用字符逐个赋值要多占一个字节，用于存放字符串结束标志'\0'。上面的数组c在内存中的实际存放情况为：C program'\0'是由C编译系统自动加上的。由于采用了'\0'标志，所以在用字符串赋初值时一般无须指定数组的长度，而由系统自行处理。在采用字符串方式后，字符数组的输入输出将变得简单方便。除了上述用字符串赋初值的办法外，还可用scanf函数和printf函数一次性输入输出一个字符数组中的字符串，而不必使用循环语句逐个地输入输出每个字符。

void main()

{

static char c[]="BASIC\ndBASE";

printf("%s\n",c);

} printf("%s\n",c);

注意在本例的printf函数中，使用的格式字符串为“%s”，表示输出的是一个字符串。而在输出表列中给出数组名则可。不能写为：printf("%s",c[]);

void main()

{

char st[15];

printf("input string:\n");

scanf("%s",st);

printf("%s\n",st);

} char st[15];

本例中由于定义数组长度为15，因此输入的字符串长度必须小于15，以留出一个字节用于存放字符串结束标志'\0'。应该说明的是，对一个字符数组，如果不作初始化赋值，则必须说明数组长度。还应该特别注意的是，当用scanf函数输入字符串时，字符串中不能含有空格，否则将以空格作为串的结束符。例如运行例4.8，当输入的字符串中含有空格时，运行情况为：input string:this is a book this 从输出结果可以看出空格以后的字符都未能输出。为了避免这种情况，可多设几个字符数组分段存放含空格的串。程序可改写如下：

Lesson

void main()

{

char st1[6],st2[6],st3[6],st4[6];

printf("input string:\n");

scanf("%s%s%s%s",st1,st2,st3,st4);

printf("%s %s %s %s\n",st1,st2,st3,st4);

}

本程序分别设了四个数组，输入的一行字符的空格分段分别装入四个数组。然后分别输出这四个数组中的字符串。在前面介绍过，scanf的各输入项必须以地址方式出现，如 &a,&b等。但在例4.8中却是以数组名方式出现的，这是为什么呢?这是由于在C语言中规定，数组名就代表了该数组的首地址。整个数组是以首地址开头的一块连续的内存单元。如有字符数组char c[10]，在内存可表示如图4.2。设数组c的首地址为2000，也就是说c[0]单元地址为2000。则数组名c就代表这个首地址。因此在c前面不能再加地址运算符&。如写作scanf("%s",&c);则是错误的。在执行函数printf("%s",c) 时，按数组名c找到首地址，然后逐个输出数组中各个字符直到遇到字符串终止标志'\0'为止。

3.队列 (Queue)

一种特殊的线性表，它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列是按照“先进先出”或“后进后出”的原则组织数据的。队列中没有元素时，称为空队列。

顺序队列

空队时指针(下标)front和rear在一起都指向队前方，当有元素进队，则rear后移;有元

素出队，则front后移，最后，开始时分配给队的前端不再被利用。

为了充分利用队列，顺序队列总是做成一个逻辑上的循环队列。

#p#副标题#e#

注意：空队时rear等于front，满队时必须空一个位置。

顺序循环队列类模板

templateclass Queue

{

int rear,front; //队尾与队头下标

T *elements; //存放队列元素的容器

int maxSize; //队列最多可容纳元素个数+1

public:

Queue(int ms=18);

~Queue()

{

delete[] elements;

}

bool IsEmpty() const //判队空

{

return front==rear;

}

bool IsFull() const //判队满

{

return (rear+1)%maxSize==front;

}

int Length() const //求队中元素数，注意求余算法

{

return (rear-front+maxSize)%maxSize;

}

void EnQue(const T &data); //进队

T DeQue(); //出队

T GetFront(); //取队头数据

void MakeEmpty()//队置空(初始态)

{

front=rear=0;

}

};

4.链表 (Linked List)

是一种物理存储单元上非连续、非顺序的存储结构，它既可以表示线性结构，也可以用于表示非线性结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

基本操作(pascal语言)

建立

第一行读入n，表示n个数

第二行包括n个数

以链表的形式存储输出这些数
#p#副标题#e#

在以z为头的链表中搜索第一个n，如果找到则删去，返回值为1，否则返回0

查找

类似于删除，只需要找到不删即可
#p#副标题#e#

插入

插入，在以zz为头的链表第w个的前面插入nn元素，函数返回值正常是0，如果w超过了链表的长度，函数返回链表的长度

5.树 (Tree)

数据结构中为了存储和查找的方便，用各种树结构来存储文件。树结构包括：二叉查找树(二叉排序树)、平衡二叉树(AVL树)、红黑树、B-树、B+树、字典树(trie树)、后缀树、广义后缀树。各种树的表示方法、特点及各自的用途如下：

1、二叉查找树(二叉排序树)

(图a)

二叉查找树是一种动态查找表(图a)，具有这些性质：

(1)若它的左子树不为空，则左子树上的所有节点的值都小于它的根节点的值;

(2)若它的右子树不为空，则右子树上所有节点的值都大于它的根节点的值;

(3)其他的左右子树也分别为二叉查找树;

(4)二叉查找树是动态查找表，在查找的过程中可见添加和删除相应的元素，在这些操作中需要保持二叉查找树的以上性质。

2、平衡二叉树(AVL树)

(图b)

含有相同节点的二叉查找树可以有不同的形态，而二叉查找树的平均查找长度与树的深度有关，所以需要找出一个查找平均长度最小的一棵，那就是平衡二叉树(图b)，具有以下性质：

(1)要么是棵空树，要么其根节点左右子树的深度之差的绝对值不超过1;

(2)其左右子树也都是平衡二叉树;

(3)二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1。
#p#副标题#e#

3、红黑树

(图c)

红黑树是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。具有以下性质：

(1)根节点只能是黑色;

(2)红黑树中所有的叶子节点后面再接上左右两个空节点，这样可以保持算法的一致性，而且所有的空节点都是黑色;

(3)其他的节点要么是红色，要么是黑色，红色节点的父节点和左右孩子节点都是黑色，及黑红相间;

(4)在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，从而保证了是一个平衡二叉树。

4、B-树

图d)

B-树是一种平衡多路查找树，它在文件系统中很有用。一棵m阶B-树(图d为4阶B-树)，具有下列性质：

(1)树中每个节点至多有m棵子树;

(2)若根节点不是叶子节点，则至少有2棵子树;

(3)除根节点之外的所有非终端节点至少有棵子树;

(4)每个节点中的信息结构为(A0,K1,A1,K2......Kn,An)，其中n表示关键字个数，Ki为关键字，Ai为指针;

(5)所有的叶子节点都出现在同一层次上，且不带任何信息，也是为了保持算法的一致性。
#p#副标题#e#

5、B+树

(图e)

B+数是B-树的一种变形，它与B-树的差别在于(图e为3阶B+树)：

(1)有n棵子树的节点含有n个关键字;

(2)所有的叶子节点包含了全部关键字的信息，及指向这些关键字记录的指针，且叶子节点本身按关键字大小自小到大顺序链接;

(3)所有非终端节点可以看成是索引部分，节点中仅含有其子树(根节点)中最大(或最小)关键字，所有B+树更像一个索引顺序表;

(4)对B+树进行查找运算，一是从最小关键字起进行顺序查找，二是从根节点开始，进行随机查找。

6、字典树(trie树)

(图f)

字典树是一种以树形结构保存大量字符串。以便于字符串的统计和查找，经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。具有以下特点(图f)：

(1)根节点为空;

(2)除根节点外，每个节点包含一个字符;

(3)从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

(4)每个字符串在建立字典树的过程中都要加上一个区分的结束符，避免某个短字符串正好是某个长字符串的前缀而淹没。

7、后缀树

后缀树则是一个字符串的所有后缀组成的字典树。具体内容再前几章已讲过。

8、广义后缀树

广义后缀树是好几个字符串的的所有后缀组成的字典树，同样每个字符串的所有后缀都具有一个相同的结束符，不同字符串的结束符不同。

6.图 (Graph)

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

1.图的存储结构
#p#副标题#e#

1.1 邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(邻接矩阵)存储图中的边或弧的信息。

设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

看一个实例，下图左就是一个无向图。

从上面可以看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角相对应的元全都是相等的。

从这个矩阵中，很容易知道图中的信息。

(1)要判断任意两顶点是否有边无边就很容易了;

(2)要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素之和;

(3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点;

而有向图讲究入度和出度，顶点vi的入度为1，正好是第i列各数之和。顶点vi的出度为2，即第i行的各数之和。

若图G是网图，有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

这里的wij表示(vi,vj)上的权值。无穷大表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。下面左图就是一个有向网图，右图就是它的邻接矩阵

。

那么邻接矩阵是如何实现图的创建的呢?代码如下。
#p#副标题#e#

从代码中可以得到，n个顶点和e条边的无向网图的创建，时间复杂度为O(n + n2 + e)，其中对邻接矩阵Grc的初始化耗费了O(n2)的时间。
#p#副标题#e#

1.2 邻接表

邻接矩阵是不错的一种图存储结构，但是，对于边数相对顶点较少的图，这种结构存在对存储空间的极大浪费。因此，找到一种数组与链表相结合的存储方法称为邻接表。

邻接表的处理方法是这样的：

(1)图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过，数组可以较容易的读取顶点的信息，更加方便。

(2)图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

例如，下图就是一个无向图的邻接表的结构。

对于邻接表结构，图的建立代码如下。

#p#副标题#e#

对于无向图，一条边对应都是两个顶点，所以，在循环中，一次就针对i和j分布进行插入。

本算法的时间复杂度，对于n个顶点e条边来说，很容易得出是O(n+e)。

1.3 十字链表

对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才知道，反之，逆邻接表解决了入度却不了解出度情况。下面介绍的这种有向图的存储方法：十字链表，就是把邻接表和逆邻接表结合起来的。

重新定义顶点表结点结构，如下所示。
#p#副标题#e#

重点需要解释虚线箭头的含义。它其实就是此图的逆邻接表的表示。对于v0来说，它有两个顶点v1和v2的入边。因此的firstin指向顶点v1的边表结点中headvex为0的结点，如上图圆圈1。接着由入边结点的headlink指向下一个入边顶点v2，如上图圆圈2。对于顶点v1，它有一个入边顶点v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，如上图圆圈3。

十字链表的好处就是因为把邻接表和逆邻接表整合在一起，这样既容易找到以v为尾的弧，也容易找到以v为头的弧，因而比较容易求得顶点的出度和入度。

而且除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图应用中，十字链表是非常好的数据结构模型。

这里就介绍以上三种存储结构，除了第三种存储结构外，其他的两种存储结构比较简单。

二、图的遍历

图的遍历和树的遍历类似，希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫图的遍历。

对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通过有两种遍历次序方案：深度优先遍历和广度优先遍历。

2.1 深度优先遍历

深度优先遍历，也有称为深度优先搜索，简称DFS。其实，就像是一棵树的前序遍历。

它从图中某个结点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中的所有顶点都被访问到为止。

我们用邻接矩阵的方式，则代码如下所示。

#p#副标题#e#

如果使用的是邻接表存储结构，其DFSTraverse函数的代码几乎是相同的，只是在递归函数中因为将数组换成了链表而有不同，代码如下。

对比两个不同的存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找某个顶点的邻接点需要访问矩阵中的所有元素，因为需要O(n2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。

2.2 广度优先遍历

广度优先遍历，又称为广度优先搜索，简称BFS。图的广度优先遍历就类似于树的层序遍历了。

邻接矩阵做存储结构时，广度优先搜索的代码如下。

对于邻接表的广度优先遍历，代码与邻接矩阵差异不大，代码如下。

对比图的深度优先遍历与广度优先遍历算法，会发现，它们在时间复杂度上是一样的，不同之处仅仅在于对顶点的访问顺序不同。可见两者在全图遍历上是没有优劣之分的，只是不同的情况选择不同的算法。
#p#副标题#e#

7.堆 (Heap)

在计算机科学中，堆是一种特殊的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小(或最大)，且根结点的两个子树也是一个堆。

例程

为将元素X插入堆中，找到空闲位置，建立一个空穴，若满足堆序性(英文：heap order)，则插入完成;否则将父节点元素装入空穴，删除该父节点元素，完成空穴上移。直至满足堆序性。这种策略叫做上滤(percolate up)。

void Insert( ElementType X, PriorityQueue H ){ int i; if( IsFull(H) ) { printf( "Queue is full.\n" ); return; } for( i = ++H->Size; H->Element[i/2] > X; i /= 2 ) H->Elements[i] = H->Elements[i/2]; H->Elements[i] = X;}

以上是插入到一个二叉堆的过程。

DeleteMin，删除最小元，即二叉树的根或父节点。删除该节点元素后，队列最后一个元素必须移动到堆得某个位置，使得堆仍然满足堆序性质。这种向下替换元素的过程叫作下滤。

ElementType DeleteMin( PriorityQueue H ){ int i, Child; ElementType MinElement, LastElement; if( IsEmpty( H ) ) { printf( "Queue is empty.\n" ); return H->Elements[0]; } MinElement = H->Elements[1]; LastElement = H->Elements[H->Size--]; for( i = 1; i*2 <= H->Size; i = Child ) { /* Find smaller child. */ Child = i*2; if( Child != H->Size && H->Elements[Child+1] < H->Elements[Child] ) Child++; /* Percolate one level. */ if( LastElement > H->Elements[Child] ) H->Elements[i] = H->Elements[Child]; else break; } H->Elements[i] = LastElement; return MinElement;}

7.算法设计的分析技术

算法是对问题求解过程的准确描述，由有限条指令组成，这些指令能在有限时间内执行完毕并产生确定性的输出。

进行算法的时间复杂度分析，就是求其T(n)，并用O、Ω或是Θ以尽可能简单的形式进行表示。

理想情况下，希望能够使用Θ表示算法的时间复杂性。退而求其次，可以使用O或是Ω。

使用O时，希望估计的上界的阶越小越好。

使用Ω时，希望估计的下界的阶越大越好。

树的高度为ëlognû,所以将一个元素插入大小为n的堆所需要的时间是O(logn).

delete(H,i) 所需要的时间是O(logn).

make-heap(A): 从数组A创建堆

方法1：从一个空堆开始，逐步插入A中的每个元素，直到A中所有元素都被转移到堆中。

时间复杂度为O(nlogn).

方法2：