数据结构教案

第1章绪论

1.2基本概念和术语

一、数据、数据元素、数据项

1.数据•：凡能被计算机存储、加工的对象,通称为数据。

2.数据元素：是数据的基本单位，一般具有完整、确定的实际意义。

3.数据项：是数据不可分割H勺最小单位。

注意：数据、数据元素、数据项是数据组织H勺三个层次。

如：(80,90,100,110,120)、表格

二、数据日勺逻辑构造

1.逻辑构造：数据元素之间H勺“邻接”关系

2.四种逻辑构造

线性构造：数据元素之间存在“一对一”的关系

Y

树形构造：数据元素之间存在“一对多”的关系

图状构造：数据元素之间存在“多对多”的关系

集合：数据元素之间没有邻接关系

三、数据日勺存储构造

1.存储构造：数据元素在计算机内的寄存方式

2.两种存储构造

｛次序存储：将数据元素依次寄存到一组持续的存储单元中。

链式存储：将数据元素寄存到非持续的存储单元中，并运用指针将各个存储单元链接起

来。

四、数据H勺基本操作

V加工型操作：变化数据元素的个数或数据元素H勺内容

引用型操作：数据元素H勺个数或数据元素的内容均未变化

五、数据构造

1.含义：包括三方面H勺内容：

r逻辑构造：反应数据元素之间的邻接”关系

〔存储构造：反应数据元素在计算机内的寄存方式

数据的操作

2.数据按构造分，可分为4类，每一类对应着一种逻辑构造

数据逻辑构造

线性表线性构造

树树型构造

图图状构造

查找表集合

1.3算法描述

1.算法：处理问题的措施和环节。

2.算法口勺描述措施

'框图

v

非形式语言：如中文

类C语言程序

C语言程序

1.4算法分析

1.对同一问题，可以设计多种不一样的算法，但必有一种算法的时间效率最高。

2.估算一种算法的运行时间

①确定问题的输入规模n。

②根据问题的特点，选择一种操作作为“原则操作二

(一般以条件判断或照值语句为原则操作)

③确定在给定输入下共执行多少次原则操作，从而算出运行时间T。

3.算法日勺时间复杂度

对算法的运行时间T(n),忽视所有的常数、低次项，忽视最高项的系数，称为算法日勺时

间复杂度，以O表达。

运行时间时间复杂度

T(n)=c常数阶0(1)

T(n)=cn线性阶O(n)

T(n尸cM平方阶0(n2)

T(〃)=c,2"指数阶a2”)

7(〃)=。log；对数阶0(log:)

1.5指针和构造

一、什么是指针

1.存储单元的地址

每一种存储单元由一种或多种字节构成，存储单元中第一种字节H勺编号称为存储单元的

地址。

2.什么叫指针？

指针总是指向某个变量。指针时值是所指向变量的地址，指针的类型是所指向变量的类

型。

二、指针变量

1.指针变量的定义

类型*指针变量名；

例：inl*p;

解释：定义一种指针p，它只能指向int型变量。

2.两个运算符

&：取地址运算符，例&i

*:指针运算符，例*P

例：int*p,i=3;

p=&i；

printf("%d,%d\n",i,*p);

阐明：

①&和*互为逆运算，即：&*p=p,*&i=i

②定义指针变量时，指针变量名前面H勺不是指针运算符。

③指针可以与整数进行加、减运算.

指针±n=指针的原值±sizeof(指针日勺类型)Xn

④同类型的两个指针可以互相赋值.

三、指针与数组

1.数组名代表该数组H勺首地址，例a==&a[0]

2.设inta[6],则

a[i],*(a+i)是等价日勺

&a[i],a+i是等价的

3.表达数组元素的I措施

下标法：例a[i]

指针法：例*(a+i)

4.设指针p指向数组a的某一种元素，则p++：使p指向数组的下一种元素;

四、构造

1.定义构造类型

struct构造名

｛组员定义列表)

彳列：structperson

｛intno;

charname[6];

｝；

2.定义构造变量

structpersonx;

1.引用构造变量的组员

构造变量名.组员名

2.构造变显日勺初始化

3.构造指针

例：已知structpersonx,*p;

P=&x;

则表达x的no组员有三种形式：x.no,p->no,(*p).no

第2章线性表

2.1线性表依J定义

1.线性表的表达形式：

L=(ai,az,as,…，an)

2.线性表的基本操作

每种操作都采用一种函数来完毕，这些函数是自定义函数，使用之前必须先定义。

2.2线性表H勺次序存储构造

一、次序表欧I类型定义

次序表实际是一种构造变量，包括两个域：

datas：寄存线性表的I元素，last：寄存线性表的长度。

typedefstruct

{类型datas[maxsizel;

intlast;

}sequenlist;

scqucnlistL;

二、为线性表1=Ca\b，d,……)创立一种次序表，规定LI向第1个元素存入数组

『、J1号元素中。

typedefstruct

{chardatas[20];

intlast;

}sequenlist;

voidmain()

{sequenlistL;

charch;

inti=l;

ch=getchar();

while(ch!-\n')

{L.datas[i]=ch;

i++；

ch=getchar();

)

L.last=i-1;

for(i=1;i<=L.last;i++)

printf("%4c',,L.datas[i]);

printf(n\n");

三、基本操作在次序表上时实现

I.insert(a,x,i)：将元素x插入到次序表a的第i号元素之前

2.deletedi)：删除次序表a的第i号元素

第3章链式存储构造

3.1线性表的链式存储构造

一、次序表欧I优缺陷

长处：空间运用率高，可以随机读取表中任一元素。

缺陷：插入、删除操作要移动大量的数据，时间性能差。

二、单链表

1.单链表的构成

每个单链表由多种结点构成，每个结点包括两个域：

数据域data：寄存线性表的元素

指针域next：寄存下一种结点的J地址

2.单链表的类型定义

typcdcfstructnode

｛类型data;

structnode*ncxt;

}linklist;

linklist*head;

阐明：不带头结点口勺单链表为空H勺条件：head==null

带头结点11勺单链表为空11勺条件：head->next==nuII

3.单链表的建立(尾插入法)

例：为L=Ca\'b','c','d',……)创立单链表。

#include"malloc.h"

#include"sidio.h"

typcdefstructnode

{chardata;

structnode*next;

}linklist;

voidmain()

{charch;

〃定义三根指针，head指向头结点，t指向新产生11勺结点，last指向最终的结点

linklist*hcad,*t,*last;

t=malloc(sizeof(linklist));

t->ncxt=NULL;

head=t;

last=t;

ch=getchar();

while(ch!=*\n,)

{t=malloc(sizeof(linklist));

t->data=ch;

t->next=NULL:

last->next=t;

last=t;

ch=getchar();

)

I

4.单链表的插入需设置两支指针：p.to

p：指向待插入结点的前一种结点

t：指向新产生口勺结点

5.单链表日勺删除需设置两支指针：p、I。

P：指向待删除结点的前一种结点

t：指向待删除结点

三、其他链表

单链表

〔单向循环链表（循环链表）

双向循环链表（双向链表）

I.循环链表

最终一种结点的指针域不是NULL,而是指向头结点。

2.双链表

每个结点包括三个域：一种数据域和两个指针域。

双链表日勺特点是找结点的前趋和后继都很轻易。

第4章栈和队列

4.1栈

一、栈的定义

1.基本概念

栈顶、栈底、进栈、出栈、空栈

2.栈日勺表达形式

S=（ai,a2,a?,…，an）

按ai,a2,a3,…，an次序进栈，但按an,…，a3,a?,ai次序出栈。

ai称为栈底元素，an称为栈顶元素。

栈乂称后进先出线性表（LIFO）表。

二、栈II勺次序存储构造

I.次序栈的类型定义

次序栈虫际上是一种肉造变量,包括两个域：

data：寄存栈中元素，top：寄存栈顶元素所在单元的编号。

typedefstruct

{类型data[maxsize];

inttop;

}seqstack;

seqstacks;

栈空条件:s.top=0：

栈满条件:s.top=maxsize-l

2.为5=—d,,d,……）创立一种次序栈,规定S日勺第1个元素存入数组的1号

元素中。

typedefstruct

（chardata|20];

inttop;

}seqstack;

voidmain()

{seqstacks;

charch;

inti=l;

ch=gctchar();

while(ch!='\n')

{s.data|i|=ch;

i++；

ch=gctchar();

1

s.top=i-l;

for(i=l;i<=S.top;i++)

pnntf("%-4c',.s.data[i]);

printf("\n");

}

三、栈的链式存储构造

1.链栈的类型定义

typedefstructnode

{类型data;

structnode*next;

}linkstack;

linkstack*top:

注意：

①链栈总是以栈顶指针top开头，top用于标识整个链栈。

②链栈只会出现栈空状况，栈空条件为:top==NULL

2.链栈的建立(头插入法)

例：为界('a','b',c\'d',……)创立一种链栈。

#include“malloc.h"

#include"stdio.h"

typedefstructnode

{chardata;

structnode*next;

}linkstack;

voidmain()

{linkstack*top,*t;

charch;

top=NULL;

ch=getcharO;

while(ch!=,\n)

{t=malloc(sizeof(linkstack));

t->data=ch;

t->next=top;

top=t;

ch=getchar0;

)

printf("出栈次序为:\n");

while(top->next!=NULL)

{printf("%-4c”,top->data);

top=top->next;

)

printf('\n");

)

4.2队列

一、队列的定义

1.基本概念

队头、队尾、空队

2.队列的表达形式：

Q=（ai,az,a3，…，an）

按a”a2,a3,…，an次序进队，仍按a1，a2,a3,…，an次序出队。

队列又称先进先出线性表（FIFO表）

二、队列的）次序存储构造

1.次序队的类型定义

次序队实际.卜.是一种构造变量，包括三个域：

data：寄存队列的元素；

front：寄存队头元素所在单元的前一种单元的编号：

rear：寄存队尾元素所在单元的编号。

typedefstruct

{类型data[maxsize];

intfront,rear;

}seueue;

seueueq;

2.次序队的建立

例：为(2=Ca','b','c','d',）创立一种次序队。

typedefstruct

(chardata[20J;

intfront,rear;

}seucue;

voidmain()

{seucucq;

charch;

inti=0;

ch=getchar();

while(ch!='\n')

{q.data[i]=ch;

i++；

ch=gctchar();

)

q.front=-1;

q.rear=i-l;

〃输出队列元素

fbr(i=O;i<=q.rear;i++)

printf("%-4c',.q.data[i]);

printf("\n");

)

3.次序队日勺队空、队满

①队空条件：q.front=q.rear

②队满条件：q.rcar=maxsizc-l

'队真满：q.front=-l;

、q.rear=maxsize-1

队假满:q.front队-I;

q.rear=maxsize-1

4.次序队的插入、删除操作

①插入新元素：rear后移而front不变

q.rcar=q.rcar+l;

q.data[q.rearl=x;

②删除元素：front后移而rear不变

q.front=q.front+l;

三、循环队

1.为充足运用存储空间，克服“假满”，可以把数组看作首尾相接的圆环，形成“循环队”。

2.循环队的性质

①存储单元的编号从0开始，按顺时针方向，编号逐渐增大，最终一种存储单元代I编号为

maxsize-1。

②在循环队中，当q.rear=maxsize-l时，只要数组有两个以上的存储单元为空，就可以把新

元素插入到空单元中。

③当队列中元素的个数为maxsize-1时，就认为队满。

3.循环队的插入、删除操作

①插入新元素：rear顺时针移动而front不变

q.rear=(q.rear+1)%maxsize;

q.data[q.rear]=x;

②删除元素：front顺时针移动而rear不变

q.front=(q.front+1)%maxsize;

4.循环队的队空、队满

队空条件：q.front=q.rear

队满条件：(q.rear+1)%maxsize=q.front

四、队列的链式存储构造

1.链队的类型定义

①链队是一种具有队头指针front和队尾指针rearH勺单链表;

②front指向队头结点欧J前一种结点，rear指向队尾结点;

③链队由包括front和rear的I构造变量lq标识。

typedefstructnode_st

{类型data;

structnode_st*nexl;

}node;

（ypedefstruct

{node*front;

node*rear;

）linkqueue;

linkqueuelq;

2.链队的建立（尾插入法）

例：为Q=Ca','b','c','d',……）创立一种链队。

#include"malloc.h"

#includc"stdio.h"

typeclefstructnode_st

{chardata;

structnode_st*next;

}node;

typedefstruct

{node*front;

node*rear;

}linkqueue;

voidmain()

{charch;

linkqueueIq;

node*p;

p=malloc(sizeof(node));

p->next=NULL;

lq.front=p;

lq.rcar=p;

ch=getchar();

whilc(ch!-\n')

{p=malloc(sizeof(node));

p->data=ch;

p->next=NULL;

lq.rear->next=p;

lq.rear=p;

ch=getchar();

)

//输出队列中的元素

p=lq.front->ncxt;

while(p!=NULL)

{printf("%-4c”,p->data);

p=p->next;

)

printf(M\n");

)

3.链队的队空条件

lq.front=lq.rear

4.各式链式存储构造比较表

有无头结点用何指针标识创立措施

链表有头指针head尾插入法

链栈无栈顶指针2P头插入法

链队有由包括front和rear日勺构造变量lq标识。尾插入法

第6章树和二叉树

6.1树的定义和基本操作

一、树型构造和线性构造

树型构造：每个结点可以有多种直接后继

线性构造：每个结点只有一种直接后继

二、树的定义

树是n(n20)个结点的有限集合，任意一棵非空树满足：

①有且只有一种根结点；

②其他结点被提成若干个互不相交的集合，每个集合又是一棵树。

三、树日勺特点

①除根结点外，每个结点有且只有一种直接前趋；

②除最底层的结点外，每个结点可以有多种直接后继；

③若某棵树有多种结点，则每个结点可以看作根结点，要么是整棵树的根结点，要么是某

棵子树的根结点。

四、基本术语

①结点的度、树的度

②叶子结点、分支结点

度为0U勺结点称为叶子结点：度不小于0的结点称为分支结点。

③孩子结点、双亲结点、兄弟结点

具有同一双亲的结点互为兄弟

④结点的子孙、结点口勺祖先

⑤结点的层数、树的高度

结点日勺层数：从树根开始算起，根的层数为I;

树的高度：树中所有结点层数的最大值。

6.2二叉树

一、二叉树FI勺定义：参照P73

二、二叉树日勺性质

（1）二叉树的第i层上最多有2'T个结点。

（2）深度为k的二叉树最多有2"-1个结点。

（3）满二又树：除最底层MJ结点外，其他结点的度均为2的二叉树。

（4）完全二叉树：假如对一棵满二叉树的最底层从最右边开始，持续删去若干个结点，就

得到完全二叉树。

（5）对一棵完全二叉树的结点进行编号，则对编号为i的结点，其左孩子的编号为2i,右

孩子的编号为2i+l,双亲结点的编号为1%]

三、二叉树的存储构造

1.次序存储构造:

♦先将二叉树的结点依次编号，再将结点存入一维数组中，数组元素的序号对应结点口勺

编号。

♦对二叉树的I结点进行编号，编号原则是：

①根结点的编号为1.

②对于编号为i日勺结点，其左孩子的编号为2i,右孩子的编号为2i+l.

♦满二叉树、完全二叉树一般采用次序存储构造，一般二叉树则采用链式存储构造。

2.链式存储构造：

①二叉链表：每个结点包括三个域：

数据域data,左指针或Ichild,右指针域rchild

②对二叉树H勺访问只能从根指针root开始，二叉树为空的条件：rool=NULL,

四、二叉树的遍历

1.什么叫二叉树的I遍历？

按照一定规律访问二叉树FI勺所有结点，使得每个结点均被访问一次且仅被访问一次。

2.二叉树由三部分构成：

根结点、左子树、右子树

3.三种遍历次序

①先根遍历：根结点、左子树、右子树

②中根遍历：左子树、根结点、右子树

③后根遍历：左子树、右子树、根结点

6.3树和森林

一、对树中各结点编号

从根结点开始，按层依次编号，且根结点的编号为0。

二、树日勺存储构造

J双亲链表

L孩子链表

孩子兄弟链表

1.双亲链表

(1)每个结点包括两个域名：

数据域：寄存该结点的数据元素

指针域：寄存该结点之双亲H勺编号

(2)将所有结点组织成一维数组，并以各结点H勺编号作为数组元素H勺序号。

2.孩子链表

(1)为每个结点建立一种“孩子链表”。

(2)结点x的孩子链表是一种带头结点U勺单链表，用于存储该结点的所有孩子的编号。

(3)将所有头结点组织成一维数组。

3.孩子兄弟链表

(1)每个结点具有三个域:

数据域：寄存该结点的数据元素

孩子域：用于指向该结点H勺第一种孩子

兄弟域：用于指向该结点的第一种兄弟

(2)二叉树的二叉链表与树的孩子兄弟链表在组织构造完全相似。

二叉链表孩子兄弟链表

数据域数据域

左指针域孩子域

右指针域兄弟域

三、树与二叉树的转换

1.树转换为二叉树

①将树转换为二叉树，只要将树中各结点的第一种孩子看作左孩子，第一种兄弟看作

右孩子即可。

②任一棵树对应的二叉树的右子树必空。

2.森林转换为二叉树

①将每棵树先转换为二叉树B|,B2,Bn

②以B1为基准，将B?作为Bl根结点的右子树，将B3作为B2根结点的右子树，…

3.二叉树转换为森林

①将二叉树根结点的右子树撤去，得到多棵二叉杭B|,B2,…，B„

②将二叉树分别转换为树T|,T2,…，Tn。

四、树淤J遍历

先根遍历：根结点、各棵子树

I后根遍历：各棵子树、根结点

层次遍历

6.4哈夫曼树和鉴定树

一、基本术语

1.叶子结点的途径长度：从根结点到某个叶子结点所通过的分支数。

2.树的途径长度：树中各叶子结点的途径长度之和。

3.叶子结点的权：各叶子结点出现的概率。

4.带权途径长度（WPL）

各个叶子结点的权Wi与对应的途径长度li乘积之和，称为树的带权途径长度。

1=1

二、哈夫曼树

I.什么叫哈夫曼树？

带权途径长度WPL最小H勺二叉树，称为哈夫曼树。

特点：

①一般地说，权值越大H勺叶子结点离根越近。

②哈夫曼树的时间性能最佳，是最优的二叉树。

③哈夫曼树中各结点口勺度只能是。或2。

④具有n个结点口勺哈夫曼树共有2n-l个结点。

2.怎样构造一棵哈夫曼树？(参照P88)

3.哈夫曼编码

对一棵哈夫曼树约定：指向左孩子日勺分支表达为()，指向右孩子口勺分支表达为Io取从根

到叶子结点一路上的“0”或“1”构成U勺序列，称为叶子结点的前缀编码。

三、分类和鉴定树

1.用于描述分类问题H勺二叉树称为鉴定树。

鉴定树的每个分支结点对应一种判断，每个叶子结点对应一种分类成果。

2.一种分类问题对应着若干棵鉴定树，其中必有一棵鉴定树的WPL最小，WPL又称平均

比较次数。

3.一棵鉴定树对应着一种算法，哈夫曼树对应口勺算法的时间性能最佳。

4.怎样对一种分类问题写最优的算法？

①对分类成果画哈夫曼树；

②根据哈夫曼树写算法；

第7章图

7.I图的定义和术语

一、图的定义

图G由顶点集V和边集E构成，记为G=(V,E)c

①最简朴的图只有一种顶点；

②每条边由其连接的两个顶点表达：

例：无向边(vl,v2)：有向边Vvl,v2>,<v2.vl>

二、术语

1.邻接点

若顶点V"Vj存在一-条边，则Vi，Vj互为邻接点。

在有向边VV"Vj>中，称Vi为起点，Vj为终点。

2.顶点时入边，出边

若存在一条有向边<Vi，Vj>,则称它为ViH勺出边，Vj的入边。

3.顶点的入度，出度

①顶点的度：与顶点v有关联的边数，记为D(v)；

②顶点的入度，出度：

在有向图中，顶点v¥j入边的数目，称为入度，记为ID(v)；

顶点v的山边的数目，称为山度，记为OD(V)；

D(v)=ID(v)+OD(v)

4.无向完全图，有向完全图

无向完全图：任意两个顶点之间都存在一条边H勺无向图;

有向完全图：任意两个顶点之间都存在方向相反H勺两条边的有向图;

5.子图

设有两个图G=(V,E)和G'=(Vz,E'),若*是V口勺子集，E，是E的子集，则

G'是G的子图。

6.连通图和连通分局

连通：在无向图中，若两个顶点有途径，则称两顶点是连通的；

连通图：任意两个顶点都连通日勺无向图；

连通分量：无向图中的极大连通子图。

7.强连通图和强连通分量

强连通：在有向图中，若Vi到Vj,Vj至iJVi均有途径，则称Vi，Vj是强连通的；

强连通图：任意两个顶点都强连通的有向图：

强连通分量：有向图中的极大连通子图。

8.带权图：又称网

”带权有向图(有向网)

V

带权无向图(无向网)

7.2图的存储构造

一、邻接矩阵

1.邻接矩阵的构建

①将各个顶点排成一行和一列，形成矩阵。

②若行、列顶点之间存在i条边，则对应元素记1,否则，对应元素记0。

2.邻接矩阵的特点

无向图H勺邻接矩阵是对称II勺.有向图的邻接矩阵一股不对称。

3.用邻接矩阵表达加权图

只要把1元素换成对应边的权值，0元素换成8即可。

4.邻接矩阵的用途

便于查找每个顶点的度、入度、出度。

无向图：每个顶点的度等于该顶点对应的行或列中1元素的个数。

有向图：每个顶点欧I出度等于该顶点对应行中1元素的个数，入度等于对应列中1元素

的个数。

二、邻接链表

树的孩子链表、图的邻接逑表组织构造相似。

1.邻接链表的构建

①为每个顶点建立一种钢接链表，一种图有几种顶点，就有几种邻接链表。

②顶点xH勺邻接链表是一种带头结点的单链表，用于存储与x相邻接日勺顶点序号。

③将所有头结点组织成一维数组。

2.邻接链表的用途

便于求顶点口勺度、出度。

无向图：每个顶点的度等于它U勺邻接链表中表结点I付个数。

有向图：每个顶点的出度等于它日勺邻接链表中表结点口勺个数。

3.怎样求顶点的入度？

构造一种逆邻接链表，即顶点x日勺逆邻接链表存储的是与x的入边有关联日勺顶点序号。

注：一种图II勺邻接矩阵是唯一II勺，但邻接表一般不唯一。

7.3图的遍历

1.树的遍历

r先根遍历：根结点、各棵子树

〔后根遍历：各棵子树、根结点

层次遍历

2.图H勺遍历：适应于无向图，也适应于有向图。

/深度优先搜索遍历：类似树日勺先根遍历。

广度优先搜索遍历：类似树的层次遍历

3.深度优先搜索遍历：

首先访问出发点Vi，然后任选一种Vi日勺未访问过时邻接点Vj,以Vj为新的出发点继续

进行深度优先搜索。

深度优先搜索遍历、广度优先搜索遍历得到H勺顶点序列不唯一。

7.4图时应用

一、最小生成树

I.什么叫生成树？

从n个顶点的连通图G中.取它的所有顶点和n-1条边构成子图G'・假如这些辿刚好

将5的J所有顶点连通但又不形成回路，则称子图5是GH勺一棵生成树。

注意：①一种连通图可以有多棵生成树。

②生成树是边数很少的I连通子图。

③连通分量：指极大连通子图。

④根据图B勺宽度优先遍历或深度优先遍历可构造生成树。

2.最小生成树

①生成树欧I权：各条边权值之和

权值最小H勺生成树，称为最小生成树。

②带权无向图才可构造最小生成树。

求造价最低的通讯网问题，实际是求最小生成树问题。

3.构造最小生成树H勺算法：Prim（普里姆）算法

二、拓扑排序

1.拓扑序列

在有向图中，若不存在回路，则所有顶点可排成一种线性序列，以便列出各顶点的前后

关系，称此序列为拓扑序列。

2.拓扑排序：实既有向图的一种拓扑序列U勺过程。

任何一种有向无环图，其所有顶点可以排成一种拓扑序列，且其拓扑序列不唯一。

若图中入度为0的顶点和出度为0的顶点都是唯一的.则其拓扑序列是唯一的。

3.构成有向图拓扑序列的过程

①从图中选择一种入度为0的顶点，输出该顶点。

②从图中删除该顶点及其有关联的J所有边。

③反复执行1,2,直到找不到入度为0的顶点。

三、最短途径

1.最短途径问题

①带权有向图才存在最短途径问题。

②图的途径长度：一条途径上各条边H勺权值之和。

2.求•种源点到其他各个顶点的最短途径：Dijkstra迪杰斯特拉）算法

从源点到其他各个顶点的最短途径中，先求最短口勺一条，再求次短口勺一条，以此次序,

最终求最长日勺■条。

3.Dijkstra算法描述

①假设S为顶点集合，初值为源点vO。

②首先从vO出发口勺所有边中找出权值最小口勺边日勺终点加入到S中。

③下一条最短途径是终点不在S中，中间只通过S中的I顶点且途径长度最短，找到后

将终点加入到S中。

④反复执行（3）,直到所有顶点都加入到S中。

例：根据P115图717.求顶点VI到其他各顶点的最短途径。

线占V2V3V4V5集合S

第1次10OO30100{VI,V2}

第2次1()6030100{VI,V2,V4}

第3次10503090{VI,V2,V4,V3}

第4次10503()60{VI,V2,V4,

V3,V5}

VI到各顶点的最短途径是:

V1->V2：(VI,V2)

V1-V4：(VI,V4)

V1-*V3：(VI,V4,V3)

V1-V5：(VI,V4,V3,V5)

第8章查找

8.1基本概念

・、多种数据H勺逻辑构造

数据逻辑构造特点

线性表线性构造数据元素之间存在着一对一的逻辑关系。

树树型构造数据元素之间存在着一对多的逻辑关系。

图图状构造数据元素之间存在着多对多的逻辑关系。

查找表集合数据元素之间不存在任何关系。

二、查找表

1.定义:查找表是一种以集合为逻辑构造，以查找为关键运算附数据构造。

例：i种平面表格，当各条记录可以任意排列时，就成为查找表。

2.关键字：由一种或多种数据项构成，可标识若干条记录；

主键：由一种或多种数据项构成，能唯一标识一条记录。

3.查找：在查找表中寻找关键字值等于给定值的记录，若找到，则返回记录号；否则，则

查找失败。

4.静态查找表和动态查找表

静态查找表：只做建表、查找操作；

动态查找表：做建表、查找、插入、删除操作。

8.2静态查找表

♦静态查找表欧J存储构造：

次序表、有序表、索引次序表

一、次序表上的查找

1.次序表口勺类型定义

typedefstruct

(intkey;

类型data;

}ELEMENT;

typcdcfstruct

{ELEMENTrfma