数据结构与算法设计知识点

数据结构与算法设计知识点

试题类型：

本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10%）,是非判断题（10%）,单项

选择题（40%）,算法填空题（10%）,算法应用题（20%）,算法设计题（10%）。

第一章绪论

重点内容及要求：

1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元素之间的关系

等）。

数据：所有能被输入到计算机中，且能被计算机处理的符号的集合。是

计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。

数据元素：是数据（集合）中的一个“个体”，数据结构中的根本单位，在

计算机程序中通常作为一个整体来考虑和处理。

数据项：是数据结构中讨论的最小单位，数据元素可以是一个或多个数据

项的组合

关键码：也叫关键字（Key）,是数据元素中能起标识作用的数据项。

其中能起到唯一标识作用的关键码称为主关键码（简称主码）；否则称

为次关键码。通常，一个数据元素只有一个主码，但可以有多个次码。

关系：指一个数据集合中数据元素之间的某种相关性。

数据结构：带“结构”的数据元素的集合。这里的结构指元素之间存在的

关系°

数据类型：是一个值的集合和定义在此集合上的一组操作的总称。

2、掌握数据结构的根本概念、数据的逻辑结构（四种）和物理结构（数据元素的表示与关系

的表示、两类存储结构：顺序存储结构和链式存储结构）。

数据结构包括逻辑结构和物理结构两个层次。

数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描

述，可以用一个数据兀素的集合和定义在此集合上的假设十关系来表示

逻辑结构有四种：线性结构、树形结构、图状结构、集合结构

数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称

其为存储结构。

存储结构：顺序存储结构和链式存储结沟

顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关

系来表示数据元素之间的逻辑关系；

链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之

间的逻辑关系。

3、了解算法分析的根本方法，掌握算法时间第杂度相关的概念.

算法：是为了解决某类问题而规定的一个有限长的操作序列

或处理问题的策略

一个算法必须满足以下五个重要特性：L有穷性2.确定性3.可行

性4.有输入5.有输出

设计算法时，通常还应考虑满足以下目标：

1.正确性，2.可读性，3.健壮性

4.高效率与低存储量需求

如何估算算法的时间复杂度？

算法=控制结构+原操作

（固有数据类型的操作）

算法的执行时间W原操作⑴的执行次数X原操作⑴的执行时间

算法的执行时间与原操作执行次数之和成正比

算法的空间复杂度定义为：

S(n)=O(g(n))

表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增

长率相同。

算法的存储量包括：

1.输入数据所占空间

2.程序本身所占空间

3.辅助变量所占空间

第二章线性表

重点内容及要求：

1、掌握线性表的顺序存储结构，了解顺序表的存储特点(数据元素在内存中依次顺序存储),

优点：可随机存取访问；缺点：结点的插入/删除操作不方便。

线性表：是一种最简单的数据结构，也是构造其它各类复杂数据结构

的根底。一个数据元素的有序(次序)集。它有顺序和链式两种存储表示

方法。

线性表必有：

1.集合中必存在唯一的一个“第一元素”

2.集合中必存在唯一的一个“最后元素”

3.除最后元素在外，均有唯一的后继；

4.除第一元素之外，均有唯一的前驱

定义如下：

typedefintElemlype;

typedefstruct(

ElemType*elem;〃存储数据元素的一维数组；

intlength;〃线性表当前长度；

intlistsize;//当前分配数组容量；

JSqList;

VoidInilSqList(SqListA,intmaxsize)//初始化线性表

(

A.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType'i);

if(!A.elem)

cxit（O）;

）

A.length=0;

A.listsize=LIST_INIT_SIZE;

return;

）

2、了解线性表的链式存储结构，重点掌握带头结点的单链表的根本操作（结点的插入与删除

运算），了解单向循环链表和双向链表存储表示方法。

单链表：用一组地址任意的存储单元存放线性表中的数据元素。

以元素（数据元素的映象）+指针（指示后继元素存储位置）=结点

（表示数据元素或数据元素的映象）

单链表是一种顺序存取的结构，求以此为存储表示的线性表长度，可设置

一个计数器

3、了解有序线性表的特点（顺序有序表、有序链表）。

有序线性表：线性表中的数据元素相互之间可以比拟，并且数据元素在线

性表中依值非递减或非递增有序排列，即ai>aM或aE（i=2,3,...,ii）,那么

称该线性表为有序表（OrderedList）

4、学会对线性表设计相关的算法进行相应的处理.

第三章排序

重点内容及要求：

I、掌握对顺序表数据记录进行排序的根本思路和常规操化（比拟、移动），了解排序算法的稳定性

问题。

2、掌握简单项选择择排序、直接插入排序、冒泡排序算法，了解各种排序算法的特点及时间复杂

度。

排序：将一组“无序”的记录序列按某一关键字调整为“有序”的记录序列。

假设整个排序过程不需要访问外存便能完成，那么称此类排序问题为内部

排序；反之那么为外部排序。

选择排序：从记录的无序子序列中“选择”关键字最小或最大的记录，并将

它参加到有序子序列中，以此方法增加记录的有序子序列的长度

根本代码如下

for(i=0;i〈nT;i++)/*外循环控制趟数,n个数选nT趟*/

(

k=i;/*假设当前趟的第一个数为最值,记在k中*/

for(j=i+1;j<n;j++)/*从下一个数到最后一个数之间找最值*/

if(a[kka[j])/*假设其后有比最值更大的*/

k-j;/*那么将其下标记在k中水/

if(k!=i)/*假设k不为最初的i值，说明在其后找到比其更大的数*/

(

t=a[k];a[k]=a[i];}/*那么交换最值和当前序列的第一个数*/

}

插入排序：插入排序是将一个数据插入到已经排好序的有序数据中，从而

得到一个新的、个数加一的有序数据。

代码如下：voidInsertSort(SqList&L)//对顺序表L作插入排序

(

for(i=2;i<=L.length;++i)

if(L.r[i].key<L.key)

(

L.r[0]=L.r[i];//复制为哨兵

for(j=i-l;L.r[0].key<L.r[j].key;—j)

L.r[j+l]=L.r[j];//记录后移

L.r[j+1]=L.r[0];//插入到正确位置

)

}

冒泡排序：泡排序是一种最直观的排序方法，在排序过程中，将相邻的

记录的关键字进行比拟，假设前面记录的关键字大于后面记录的关键字，那

么将它们交换，否则不交换。或者反过来，使较大关键字的记录后移，像水

中的气泡一样，较小的记录向前冒出，较大的记录

像石头沉入后部。故称此方法为冒泡排序法

代码如下：

voidBubbleSort(SqList&L)

{RcdTypeW；

i=L.length：

while(i>1){//i>l说明上一趟曾进行过记录的交换

lastExchangelndex=1;

for(j=1;j<i;j++){

if(L.r[j+l].key<L.r[j].key){

W=L.r[j]；L.r[j]=L.r[j+l]；L.r[j+l]=W；//互换记录

lastExchangclndcx=j;

}

)

i=lastExchangeIndex;//一趟排序中无序序列中最后一个记录的位置

)

)

3、了解什么是堆？

堆是满足以下性质的数列{门,1%…,r„}：

<[小金黯，/篌赢/

[0«J+1匕2

第四章栈和队列

重点内容及要求：

I、掌握栈和队列的结构特点及根本操作（入栈、出栈/入队、出队）。

栈（后进先出），队列（先进先出）

构造空栈：

voidInitStack_Sq（SqStack&S）

{〃构造一个空栈S

S.elem=newSElemType[maxsize];

S.top=-l;

S.stacksize=maxsize;

S.incrementsize=incresize;

）

栈：（入栈）

voidPush_Sq(SqStack&S,SEIemTypee){

if(S.top==S.stacksize-1)

incrementStacksize(S);

//如果顺序栈的空间已满，应为栈扩容

S.elem[++S.top]=e;

//在栈顶插入数据元素

)

栈：(入栈)

boolPop_Sq(SqStack&S,SElemType&e){

〃属设栈不空，那么删除S的栈顶元素,

//用e返回其值，并返回TRUE；

//否则返回FALSEo

ifp==-1)returnFALSE;

■

returnTRUE;

)

2、对于顺序栈，熟悉栈空和栈满的条件；对于链栈.掌握其栈空的条件。

#include<iostream>

usingnamespacesid;

#defineINITSIZE100

#dcfineRESIZE20

typedefstruct{

int*base;

int*top;

intstacksize;

}Sqstack;

intInitstack(SqstackS){

S.base=(int*)malloc(INITSIZE*sizeof(int));

if(!S.base)returnfalse;

S.top=S.basc;

S.stacksize=INITSIZE;

returntrue;

I

intClearstack(Sqstack&S){

frcc(S.basc);

S.base=(int*)malloc(INITSIZE*sizeof(int));

S.top=S.basc;

returntrue;

}

intStackeinpty(SqstackS){

if(S.base==S.top)returntrue;

elsereturnfalse;

}

intPush(Sqstack&S,inte){

if(S.top-S.base>=S.stacksize){

S.base=(int*)rcalloc(S.base,(RESIZE+INITSlZE)*sizeof(int));

if(!S.base)returnfalse;

tacksizc;

S.stacksize+=RESIZE;

)

*S.top++=e;

returntrue;

)

intPop(Sqstack&S,int&e){

if(S.base==S.top)returnfalse;

c=*—S.top；

returntrue;

I

intmain()

{

SqstackS;

intt,e;

Initstack(S);

需要输入元素的个数

while(i-)

{

cin»e;

Push(S.e);

}〃进栈

while(S.top!=S.base)

{

Pop(S,e);

cout«e«"

}//出栈

}

链栈栈空的判断判断链栈是否为空很简单，还记得结构体定义时的那个count吗？如果那个

count为o,就说明链栈为空。

StatusClearStack(LinkStack*S)

{

LinkStackPtrp,q;

p=S->top;

while(p)

{q=P；

p=p->next;

free(q);

)

S->count=0;

returnOK;

3、掌握栈的典型应用一一背包问题求解的根本方法。

背包问题

假设有n件体积分别为wl,w2,…wn的物品和一个能装载体积为T的背包.

能否从n件物品中选择假设干件恰好装满背包，

即wil+wi2+…+、vik=T,那么背包问题有解；

否则无解.

以W(l,8,4,3,5,2),T=10为例

(1,4,3,2),(1,4,5),(8,2)和(3,5,2)是其解。

利用回溯的算法思想求解背包问题

其

算法如下

voidknapsack(intw[],intT,intn){

〃T在算法中是剩余的容积，初值为背包的体积

InitStack(S);k=0;

do{while(T>0&&k<n){

if(T-w[k]>=0){〃第k件物品可以进栈

Push(S,k);T—=w[k];

)

k++;

)

if(T==0)StackTraverse(S);〃输出一个解

Pop(S.k);T+=w[kl;〃退出栈顶物品

k++;

}while(JStackEmpty(S)||k<n);

4、对于带头结点的链队列，掌握队列为空的条件，熟悉入队、出队的根本操作方法。

voidInitQueue(LiQueue"&q)

{q=(LiQueue*)malloc(sizeof(LiQueue));

q->front=q->rear-NULL;

}〃初始化

in(QueueEmp(y(LiQueue

{if(q->rear==NULL)return1;

elsereturn0;

}〃判空

voidenQueue(LiQueue*&q,ElemTypee)

{QNode*s;s=(QNode*)mallDC(sizeof(QNode));

s->data=c;

s->nexl=NULL;

if(q->rear==NULL)

q->front=q->rear=s;

else

{q->rear->nexi=s;q->rear=s;

}

)

//入队

intdcQueue(LiQueue*&q,EIeinType&e)

{QNode*t;if(q->rear==NULL)

returnO;

t=q->fronl;if(q->front==q->rear)

q->front=q->rear=NULL;

else

q->front=q->front->next;

e=t->data;

free(t);

return1;

)

〃出队

intdcQucuc(LiQueue*&q,ElcmTypc&c)

{QNode*t;if(q->rear==NULL)

rcturnO;

t=q->front;if(q->front==q->rear)

q->front=q->rear=NULL;

else

q->front=q->front->next;

e=t->data;

break;

free⑴；

returni;

〃取队头

5、对于采用顺序存储结构的循环队列，掌握队列为空、队列满的条件，及队列的根本操作。

循环队列判断空满有两种方法：

L另设一个标志位以区分队列空满；

2.少用一个元素空间，当队头指针在队尾指针下一位时，队列为满，当队头指针与队尾指针相同是

队列为空。

在循环队列下，仍定义front=rear时为队空，而判断队满那么用两种方法，一是用“牺牲•个单元”，即rear+l=front

(准确记是(rear+1)%m=front,m是队列容量)时为队满。

另一种解法是“设标记”方法，如设标记tag,lag等于0情况下，假设删除时导致front=rcar为队空；tag=l情况

下，假设因插入导致front=rear那么为队满。

第五章串和数组

重点内容及要求：

I、掌握字符串类型的定义及存储表示方法。

一般情况之下用char定义，

串(String),或称字符串是由零个或多个字符组成的有限序列。记作：

S="aOal...ai...an-l/r(n20)

其中，ai属于字符集，n为串的长度，当n=0时串为空串

存储特点

串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的

串值那么被舍去，称之为“截断”

按这种串的表示方法实现的串的运算时，其根本操作为“字符序列的复

制”

2、掌握数组的定义和存储结构，熟悉二维数组中数据元素按行存储的根本方法，会计算元素的存

储地址。

数组的定义和存储结构

数组是线性表的一种扩充，一维数组即为线性表，二维数组定义为“其数

组兀素为一维数组”的线性表

数组的顺序表不和实现

类型特点：

1）只有引用型操作，没有加工型操作

2）数组是多维的结构，而存储空间是

一个一维的结构。

有两种顺序映象的方式:

1）以行序为主序（低下标优先）；

2）以列序为主序（高下标优先）。

3、'了解矩阵压缩存储的目的、原理及根本思路和方法。

矩阵压缩存储的目的

1）零值元素占了很大空间；

2）计算中进行了很多和零值的运算，

遇除法，还需判别除数是否为零。

原理及根本思路和方法

1）尽可能少存或不存零值元素；

2）尽可能减少没有实际意义的运算；

3）操作方便。即：

能尽可能快地找到与下标值（i,j）对应的元素，能尽可能快地找到同一

行或同一列的非零值元。

有两类稀疏矩阵：

1）特殊矩阵

非零元在矩阵中的分布有一定规则

例如：三角矩阵

对角矩阵

2）随机稀疏矩阵

非零元在矩阵中随机出现

4、了解随机稀疏矩阵的压缩存储方法（三元组顺序表、十字链表）。

三元组顺序表

三元组表示

原稀疏矩阵的稀疏矩阵

01400-5

0-7000

3600280

三元组表示的稀疏

矩阵节省了空间，便

于实现矩阵运算吗？

十字链表

第六章二叉树

重点内容及要求：

I、掌握二叉树的定义、特点及相关概念。

对比树型结构和线性结构的结构特点

线性结构树型结构

第一个数据元素根结点

（无前驱）（无前驱）

最后一个数据元素多个叶子结点

（无后继）（无后继）

其它数据元素其它数据元素

（一个前驱、（一个前驱、

X一个后继）多个后继）5

播不术语

结点:数据元素十若干指向子树的分支

结点的度:分支的个数

树的度:树中所有结点的度的最大值

叶子结点:度为零的结点

分支结点：度大于零的结点

结点的层次:假设根结点的层次为1,第I层的结点的子树根结点的层次为

/+1

树的深度：树中叶子结点所在的最大层次

二叉树的定义

二叉树是n（n20）个元素的有限集，它或为空树，或是由一个根

结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。

2、了解二叉树的性质和存诸结构特点，掌握二叉树的顺序存储结构主要用于完全二叉树。二叉

树的性质:

1.在二叉树的第i层上至多有万•1个结点(i^l)o

2.深度为k的二叉树上至多含2k・l个结点121)。

3.对任何一棵二叉树，假设它含有〃0个叶子结点、n2个度为2的结

点，那么必存在关系式：“0=〃2+1。

4.具有〃个结点的完全二叉树的深度为/log2n」+lo

假设对含〃个结点的完全二叉树从上到下且从左至右进行1至〃的

编号，那么对完全二叉树中任意一个编号为i的结点：

(1)假设i=h那么该结点是二叉树的根，无双亲，

否则，编号为4/2_/的结点为其双亲结点；

(2)假设2i>n,那么该结点无左孩子，

否则，编号为2i的结点为其左孩子结点；

(3)假设那么该结点无右孩子结点，

否则，编号为万+I的结点为其右孩子结点。

”两类特殊的二叉树：/公、

满二叉树：指的是深

度为A且含有2"-7个结

点的二叉树。

完全二叉树：树中所

含的〃个结点和满二

叉树中编号为7至〃

的结点----对应。

3、掌握二叉树的二叉链表存储结构,

.二叉链表结点结构:C语言的熠髓如下：

tjpedefstructBiTNode{II1点结构

TElemTypedata;

structBiTNode*lchild.*rchild;

//左右孩子指针

}BiTNode.*BiTree;

结点结构:

Ichilddatarchild

4、了解二叉树遍历的根本方法（先根次序、中根次序及后根次序遍历二叉树）。

I先左后右的遍历算法

先（根）序的遍历算法

中（根）序的遍历算法

岁后I（根）序的遍历算法

先（根）序的遍历算法：中（根）序的遍力算法：后（根）序的遍历算法:

与二叉树为空树，则空操作；否则，号二叉树为空树，则空操作：否则,

若二叉树为空树，则空操作；否则,

!（1）中帆历左子树;（1）后序遍历左子树;

（D访问根结点；

：（2）访问根结点；

际（2）后序遍历右子树;

（2）先序遍历左子树;

|（3）中序遍历右子树.（3）访问根结点.

（3）先序遍历右子树,

曲序遍历：

中z

5、了解堆排序的根本方法、了解二叉排序树的根本特点以及如何构造一棵哈夫曼树。

树和森林

二森林：

是m（m，0）棵互

不相交的树的集合

任何一棵非空树是一个二元组

Tree=（root,F）

其中：root被称为根结点

F被称为子树森林

树和森林的存储结构

1.双亲表示法

2.孩子链表表示法

3.树的二叉链表（孩子-兄弟）

存储表示法

C语言的类型描述：树结构:

MAXTREESIZE100typedefstruct(

结点结构：［dataparent.PTNodenodes

|MAX_TREE_SIZE];

typedefstructPTNode{intr,n;

Elemdata;〃根结点的位置和结点个数

intparent;//双亲位置域}PTree;

}PTNode;

2.孩子链表表示法:

C语言的类型描述：

双亲结点结构data)flrstchild

孩子结点结构:[childnext]

typedefstruct{

typedefstructCTNodc(Elctudata.

intchild;ChildPtrfirstchild:

〃孩子链的头指针

structCTNode*next;

}CTBox;

}*ChildPtr;

树结构:

typedefstruct(

CTBoxnodes[NL\X_TREE_SIZE];

intn,r;

〃结点数和根结点的位置

}CTree;

3.树的二叉链表(孩子-兄弟)存储表示法

C语言的类型描述:

结点结构：firstchUddatanextsibliog

typedefstructCSNode{

Elemdata;

structCSNode

*firstchild.*ncxtsibling;

}CSNode.*CSTree;

第七章图

重点内容及要求：

1、了解图的根本概念和相关术语。

图是较树结构更复杂的非线性结构

图Graph是由一个顶点集V和一个弧集E构成的数据结构，记作Graph=(V,E)。

其中，图的顶点为数据结构中的数据元素，弧的集合E是定义在顶点集合V上的一个关系。

有序对vv,w＞表示从v到w的一条弧，并称v为弧头，w为弧尾。

谓词P(v,w)定义了弧Vv,w＞的意义或信息

由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图

名词和术语

网、子图

完全图、稀疏图、稠密图

邻接点、度、入度、出度

路径、路径长度、简单路径、简单回路

连通图、连通分量、

强连通图、强连通分量

生成树、生成森林

2、/解图的存储结构特点(邻接矩阵、邻接表存储结构)。

邻接矩阵：

定义:矩阵的元素为。Qj)£VR

A-，J=I11(ij)eVR

有向图的邻接矩

012345阵为非对称矩阵

01001

010010

0000

1000111

00010100010

00100111000

11000000100

011100=

typedefstructArcCell(//弧的定义闻的结构定义(邻接矩阵)

VRTypcadj,〃VRTypc是顶点关系类

型。typedefstruct{

//对无权图，用1或0表示相邻否；VertexType〃顶点信息

〃对带权图，则为权值类型.vexs[MAX_VERTEX_NUM];

InfoTjpe*info;〃该弧相关信息的指针AdjMatrixarcs;〃弧的信息

}ArcCcll,intvexnum,arcnum;〃顶点数，弧数

AdjMatrix[MAX_VERTEX_NUM]GraphKindkind;//图的种类标志

『MAXVERTEXNUM];}MGraph;

邻接表存储

4用的旬接我

存管我小

-Ft-®

在有向图的做接表o二ms

中，对每个顶点，二~43l~H°H

我妹之其无链接的是指向该顶

C-W

WB*.由点的弧，

-1)-1

度图打■大的3£

一3g

E-』川

有向图的邻接表

A-4ZEBHA0

B

c■•00

D-QTHdB

可见，在有向图的鸵

族表中不易找到指向E2<20

该)5点的强.

3、了解图的遍历方法(深度优先搜索DFS和广度优先搜索BFS)。

深度优先搜索DFS

连通图的深度优先搜索遍历

从图中某个顶点V0出发，访问此顶点，然后依次从V()的各个未被访问

的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都

被访问到。

voidDFS(GraphQintv){

//从顶点V出发，深度优先搜索遍历连通图G

visitcd[v]=TRUE;VisitFunc(v);

for(w=FirslAdjVex(Gv);

w!=0;w=NextAdjVex(G,v,w))

if(!visi(ed[w])DFS(G,w);

〃对v的尚未访问的邻接顶点w

//递归调用DFS

}//DFS

非连通图的深度优先搜索遍历

首先将图中每个顶点的访问标志设为FALSE,之后搜索图中每个顶点，

如果未被访问，那么以该顶点为起始点，进行深度优先搜索遍历，否则继续

检查下一顶点。

voidDFSTraverse(GraphG){

//对图G作深度优先遍历

tor(v=0;v<G.vexnum;+-v)

visitedfv]=FALSE;//访问标志数组初始化

for(v=0;v<G.vexnum;+-v)

if(!visiled[v])DFS(Gv);

//对尚未访问的顶点调用DFS

广度优先搜索BFS

对连通图，从起始点V到

其余各顶点必定存在路径。

其中，V->W],V->w2,V->w8

的路径长度为1;

V->w7,V->w3,V->w5

的路径长度为2；

V->w6,V->w4

的路径长度为3。

从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未

被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接

点，直至图中所有和V0有路径相通的顶点都被访问到。

voidBFSTraverse(GraphG,intv){

for(v=0;v<Gvcxnuni;-++v)

visited[v]=FALSE;〃初始化访问标志

InitQueue(Q);//置空的辅助队列Q

for(v=0;v<G.vexnum;++v)

if(!visitcdlv]){//v尚未访问

}//BFSTraverse

以深度优先搜索DFS和广度优先搜索BFS的算法为框架，可以派生出

很多有实用价值的应用。

1.求一条从顶点i到顶点s的简单路径；

2.求两个顶点之间的一条路径长度最短的路径;

3.求迷宫的最短路径。

4、了解连通网的最小生成树和单源最短路径算法。

连通网的最小生成树

构造网的一棵最小生成树，即:在e条带权的边中选取n-1条边（不构成

回路），使“权值之和''为最小

用（普里姆算法）或（克鲁斯卡尔算法）解决；

普里姆算法的根本思想:

取图中任意一个顶点V作为生成树的根，之后往生成树上添加新的顶点Wo在添加的顶点W和

已经在生成树上的顶点V之间必定存在一条边，并且该边的权值在所有连通顶点V和W之间的边中

取值最小。之后继续往生成树上添加顶点，直至生成树上含有n-1个顶点为止。

二£情况下所添加的顶点应满足下列条件:例如：

在生成树的构造过程中，图中n个顶点分且19b5

属两个集合：已落在生成树上的顶点集I.和141276

尚未落在生成树上的顶点集VI,则应在所18'7广

有连通I.中顶点和V1•中顶点的边中选取权值16983

最小的边；(Jr%;

27与21

(V所得生成树权值和

=14+8+3+5+16+21=67

克鲁斯卡尔算法的根本思想:

考虑问题的出发点：为使生成树上边的权值之和到达最小，那么应使生成

树中每一条边的权值尽可能地小。

具体做法：先构造一个只含n个顶点的子图SG,然后从权值最小的边

开始，假设它的添加不使SG中产生回路，那么在SG上加上这条边，如此

重复，直至加上n-1条边为止。

比较两种算法

普里姆算法克鲁斯卡尔算法

®19®

时间复杂度

适应范憎

单源最短路径算法

求从某个源点到其余各点的最短路径

从源点到顶点v的最短路径是所有最短路径中长度最短者。

，路径长度最短的最短路径的特点：‘料下二条路径长度次短的最短路径的特点:

在这条路径上，必定只含一条弧，并且这条它可能有三种情况：或者是直接从源点到该

点（只含一条弧）：或者是从源点经过顶点Vi，

弧的权值最小.

再到达该顶点（由两条弧组成）；或者是从源点

经过顶点V2,再到达该顶点。

•下一条路径长度次短的最短路径的特点：•苴仝品汨政”的恁占

"其余景厘路径的特点：

它只可能有两种情况：或者是直接从源点到它或者是直接从源点到该点（只含一条弧）；

该点（只含一条弧）；或者是从源点经过顶点或者是从源点经过已求得最短路径的顶点，再

VP再到达该顶点（由两条弧组成）。.到达该顶点。.

1）在所有从源点出发的弧中选取一条权值最小

求最短路径的迪杰斯特拉算法:

的菰，即为第一条最短路径。

设置辅助数组Dist,其中每个分量Dist[k]表

G.arcs[vO][^]VO和间存在弧

示当前所求得的从源点到其余各顶点k的最短

INFINITYV0和k之间不存在弧

路径.

其中的最小值即为最短路径的长度.

一般情况下，

2）修改其它各顶点的因值。

Dist[k]=＜源点到顶点k的弧上的权值〉假设求得最短路径的顶点为u,

或者=＜源点到其它顶点的路径长度〉若Dist[u]+G.arcs[u][k]＜Dist[k]

+〈其它顶点到顶点k的弧上的权值＞。则将。尔因改为DE同+Gsrs[〃]因.

第八章查找表

重点内容及要求：

I、掌握线性表的查找算法（顺序查找、折半查找、分块查找）。

查找表：静态查找表、动态查找表

静态查找表：顺序查找、折半查找、分块查找

动态查找表：二叉查找树、二叉平衡树、链树（数字查找树）

顺序查找：以顺序表或线性链表表示静态杳找表

实现的算法：

intSearch_Seq(SSTableST,KeyTypekval)

(

//在顺序表ST中顺序查找其关键字等于kval的数据元素。假设找到，那么函数值为该元

素在表中的位置，否则为0。

ST.elem[0].key=kval;//设置“哨兵〃

for(i=ST.length;ST.elem[i].key!=kval;—i);//从后往前查找

returni;}//找不到时，i为0

其中“for(i=ST.length;ST.elem[i].key!=kval;—i);”还可以写成

“for(i=0;i<ST.length;i++)

{if(ST.elem[i].key=kval)

Cout«w输出结果：”«ST.elem[i].key«endl;

Return(i=0);

}“

折半查找(二分查找)：假设以有序表表示静态查找表，那么查找过程可

以按“折半”进行。

实现的算法：

intSearchBin(SSTableST,KeyTypekval)

(

//在有序表ST中折半查找其关键字等于kval的数据元素。假设找到，那么函数值

//为该元素在表中的位置，否则为0。

low=1;high=ST.length;//置区间初值

while(low<=high){

mid=(low+high)/2