当前位置:首页 >> 学科竞赛 >>

数据结构


数据结构

一.栈 二.队列 三.树 四.图


? 先进后出表(FILO)或下推表 ? 假设栈的最大长度为m,所有结点都具有同一类型stype,则定义栈如下: Const m=栈的最大长度; Type stack=array[1..m] of stype; {栈类型} Var s:stack; {栈} t:integer;

{栈顶指针} xx:stype; ? 栈的基本运算:

? 入栈 push ? 出栈 pop ? 读取栈顶元素 top

入栈 push(s,x,t)
? 过程push(s,x,t)往栈S中压入一个值为X的结点。
Procedure push(var s:stack; x:stype; var t:integer;); Begin if t=m then writeln(‘full!’) else begin t:=t+1; s[t]:=x; end; End;

出栈 pop(s,t)
? 函数pop(s,t)从栈s中弹出一个结点。 Function pop(var s:stack; var t:integer;):stype; Begin if t=0 then writeln(‘empty!’) else begin pop:=s[t]; t:=t-1; end; End; Procedure pop(var s:stack; var t:integer); Begin if t=0 then writeln(‘empty!’) else begin xx:=s[t]; t:=t-1; end; end;

读取栈顶元素 top(s,t)
? 函数top(s,t)读栈顶元素。 Function top(s:stack; t:integer;):stype; Begin if t=0 then writeln(‘empty!) else top:=s[t]; End;

栈的应用
? 括号匹配 ? 计算表达式的值 ? 非递归的回溯法

括号匹配
问题描述: 假设一个算术表达式中可包含三种括号: ( ) [ ] { },且这三种括号按任意 次序嵌套使用,如:[ [ ( ) ] ]是合法的,而{ { } }([ ]是不合法的。试利用栈 的运算,编写差别给定表达式中所含括号是否正确配对出现的算法。

括号匹配
procedure push(var st: stack;var top:integer; y:integer); begin top:=top+1; st[top]:=y; end;
procedure pop(var st:stack;var top:integer; var x:integer); begin x:=st[top]; dec(top); end;

readln(s); len:=length(s); yes:=true; top:=0; for i:=1 to len do begin case s[i] of '(':push(st,top,1); '[':push(st,top,2); '{':push(st,top,3); ')':begin pop(st,top,x); if x<>1 then begin yes:=false;break; end; end; ']':begin pop(st,top,x); if x<>2 then begin yes:=false;break; end; end; '}':begin pop(st,top,x); if x<>3 then begin yes:=false;break; end; end; end; end; if top<>0 then yes:=false; if yes then writeln('yes') else writeln('no');

计算表达式的值
? 输入一个表达式,该表达式含+、-、*、/、(、)和操作数,所含字符数不超过255, 以@结束,输出该表达式的值。 ? 分析:字符串输入,不能进行数值计算,所以,需要将输入的中缀表达式转换成后 缀表达式。

输入字符串:e 后缀表达式:a 存放运算符的栈:s
例e:5 * 8 + 3 * ( 5 * 2 / 3 -4 ) + 7 则a:5 8 * 3 5 2 * 3 / 4 - * + 7 +

计算表达式的值
当e[i]为:
? ? ? ? ?

数字: e[i]压入a; (: e[i]压入s; ): 将s中栈顶至“(”间的所有运算符出栈进入a,丢弃(; +、-: 将s中栈顶至“(”间的所有运算符出栈进入a, e[i]进入s; *、/: 将s中栈顶至“(”前的第一个+或-前的所有运算符出栈进入a,e[i]压入s; 例e:5 * 8 + 3 * ( 5 * 2 / 3 -4 ) + 7 则a:5 8 * 3 5 2 * 3 / 4 - * + 7 +

?

?

program houzhuibiaodashi; const m=100; {栈的最大长度} type stack1=array[1..m] of char; stack2=array[1..m] of integer; var kk,a,e:string; s: stack1; s2:stack2; t,i,k,j:integer; w:char; {后缀表达式和中缀表达式} {栈,存放暂不参与计算的运算符} {栈,存放暂不参与计算的操作数} {栈顶和中缀表达式的字符指针}

procedure push(var s:stack1;x:char;var t:integer); begin if t=m then writeln('overflow') else begin t:=t+1; s[t]:=x; end; end; function pop(var s:stack1; var t:integer):char; begin if t=0 then writeln('underflow') else begin pop:=s[t]; t:=t-1; end; end;

{入栈}

{出栈}

procedure push2(var s:stack2;x:integer;var t:integer); begin if t=m then writeln('overflow') else begin t:=t+1; s[t]:=x; end; end;

{入栈}

function pop2(var s:stack2; var t:integer):integer; begin if t=0 then writeln('underflow') else begin pop2:=s[t]; t:=t-1; end; end;
function top(s:stack1;t:integer):char; begin if t=0 then writeln('stack empty') else top:=s[t]; end;

{出栈}

{读栈顶元素}

BEGIN {主程序} readln(e); a:=''; i:=1; t:=0; while e[i]<>'@' do begin case e[i] of '0'..'9':begin {数字e[i]压入a} while e[i] in ['0'..'9'] do begin a:=a+e[i]; i:=i+1; end; a:=a+'.'; i:=i-1; end; '(':push(s,'(',t); {'('压入s} ')':begin {将s中栈顶至'('间的所有运算符出栈进入a,丢弃'('} w:=pop(s,t); while w<>'(' do begin a:=a+w; w:=pop(s,t); end; end;

'+','-':begin

{将s中栈顶至'('间的所有运算符出栈进入a, '+','-'进入s} if t<>0 then begin w:=top(s,t); while w<>'(' do begin a:=a+w; w:=pop(s,t); if t=0 then break else w:=top(s,t); end; end; push(s,e[i],t); {将s中栈顶至'('前的第一个+或-前的所有运算符出栈进入a,'*','/'压入s} if t<>0 then begin w:=top(s,t); while (w='*') or(w='/') do begin a:=a+w; w:=pop(s,t); if t=0 then break else w:=top(s,t); end; end; push(s,e[i],t); {case语句} {准备扫描下一个字符} {while语句}

end; '*','/':begin

end; end; i:=i+1; end;

while t<>0 do a:=a+pop(s,t); a:=a+'@'; writeln(a);

{输出后缀表达式}

i:=1; t:=0; {计算后缀表达式的值} while a[i]<>'@' do begin case a[i] of '0'..'9':begin k:=0; repeat k:=10*k+ord(a[i])-ord('0'); i:=i+1; until a[i]='.'; push2(s2,k,t); end; '+':push2(s2,pop2(s2,t)+pop2(s2,t),t); '-':begin j:=pop2(s2,t); push2(s2,pop2(s2,t)-j,t); end; '*':push2(s2,pop2(s2,t)*pop2(s2,t),t); '/':begin j:=pop2(s2,t); push2(s2,pop2(s2,t) div j,t); end; end; i:=i+1; end; writeln(pop2(s2,t)); END.

队列
? ? 先进先出表(FIFO) 插入的一端称为队尾r,删除的一端称为队首f

a
f

b

c
r

一个队列

b
f

c
r

删除一个元素

b
f

c

d
r

插入一个元素

队列
定义队列: Const m=队列元素的上限; Type equeue=array[1..m] of qtype; Var q:equeue; r,f:integer; ? 初始:f=r=0 ? 队满:r=m ? 队空:f=r 队列的主要运算: ? 入队(ADD) ? 出队(DEL)

入队ADD(q,x,r)
? 过程ADD(q,x,r)在队列q的尾端插入元素x Procedure ADD(var q:equeue; x:qtype; var r:integer;); Begin if r=m then writeln(‘full!’) else begin r:=r+1; q[r]:=x; end; End;

出队 DEL(q,y,f)
? 过程DEL(q,y,f)取出q队列的队首元素y Procedure DEL(var q:equeue; var y:qtype; var f:integer;); Begin if f=r then writeln(‘empty’) else begin f:=f+1; y:=q[f]; end; End;

假溢出
? 随着队列一端插入,一端删除,队列在数组中不断向队尾方向移动,而在队首产生一片 不以利用的空闲存储区,最后会导致当r=m时,不能再加入元素,形成假溢出。

m

m

m

r

m

3 2 1
f r
初始 f=r=0

r

3 2 1

f r

3 2 1

f

3 2 1

f
加入3个元素 f=0 r=3 删除3个元素 f=r=3 加入m-3个元素,队满 r=m f=3

循环队列
?初始:f=r=m ?入队:r:=r+1; if r=m+1 then r:=1; ?出队:f:=f+1; if f=m+1 then f:=1; ?队空:f=r; ?队满:f=r mod m+1; r:=r mod m +1 f:=f mod m +1

m

A[m] A[m-1]

m-1

f

3
2

r

1

A[m+1]

队列的应用——广义线性表
广义表的计算: 有一个表L={a1,a2,……an},其中L为第一个广义表的表名,ai为表元素(1<=i<=n)。当ai为一位十进制整数时,表示为 元素;当ai为大写字母时,表示另一个表,但不能循环定义。例如下列定义是合法的(约定L是第1个表的表名): L=(3,4,3,4,K,8,0,8,P); K=(5,5,8,9,9,4); P=(4,7,8,9); 输入:输入全部广义表,每行一个广义表。 输出:输出两行。第1行为最大元素值,第2行为全部广义表的数和。

const lmax=100; {广义表串长的上限} type tabtype=record {广义表的数据类型} length:0..lmax; {表长} element:array[1..lmax]of char; {表的数据序列} end; qtype=record {队列的数据类型} base:array[0..lmax] of char; {队列} front,rear:0..lmax; {首尾指针} end; var t:array[‘A’..‘Z’] of tabtype; {t[ch]: 表名为ch的广义表} q:qtype; {队列} ch:char; i:integer; s:string;

构造广义表T
每一个广义表用一个字符串s读入,s中的所有数字和字母看作是表的元素,将其中的小写字母统一转换成大写。q队列依次存储广义表L中的字母元 素(即表名)。先读入广义表L,将其元素存入T[L]中,表L中出现的字母依次进入队列q;若队列q不空,队首元素ch出队,读入广义表ch,将其元 素存入T[ch]中,表ch中出现的字母再依次入队……直至队列空为止。 初始时,广义表名’L’进入队列q:

q:

T[‘L’]

‘L’

f
随后, ’L’出队列q:

r

3

4

3

4

K T[‘K’]

8

0

8

P

q:

fr
读入L表,’K’和’P’相继入队列q:

5 ‘P’

5

8

9

9 T[‘P’]

4

q:

‘K’

f

r

4

7

8

9

构造广义表T
procedure inqueue(var q:qtype;c:char); begin inc(q.rear); q.base[q.rear]=c; end; function outqueue(var q:qtype):char; begin inc(q.front); outqueue:=q.base[q.front]; end; procedure create; begin for ch:='A' to 'Z' do t[ch].length:=0; q.front:=0; q.rear:=0; inqueue(q,'L'); while q.front<>q.rear do begin ch:=outqueue(q); readln(s); i:=1; while s[i]<>'(' do i:=i+1; while s[i]<>')' do begin s[i]:=upcase(s[i]); if s[i] in ['A'..'Z','0'..'9'] then begin inc(t[ch].length); t[ch].element[t[ch].length]:=s[i]; if s[i] in ['A'..'Z'] then inqueue(q,s[i]); end; inc(i); end; end; end;

计算广义表L的最大值
设m(为最大元素值,从T[‘L’]开始搜索: 1、若表中的第i个元素为数字码,则m与之比较,若m小于该数码,则被取代之; 2、若表中的第i个元素为字母c,则递归搜索以该字母为表名的广义表T[c]。 function maxnumber(c:char):char; var ch,max,m:char; i:integer; begin max:='0'; for i:=1 to t[c].length do begin ch:=t[c].element[i]; if ch in ['A'..'Z'] then m:=maxnumber(ch) else m:=ch; if max<m then max:=m; end; maxnumber:=max; end;

计算广义表L的数和
设k为当前数和,从T[‘L’]开始搜索: 1、若表中的第i个元素为数字码,则将该数码对应的数值累计入k; 2、若表中的第i个元素为字母c,则递归搜索以该字母为表名的广义表T[c]。

function total(c:char):integer; var k,i,m:integer; ch:char; begin k:=0; for i:=1 to t[c].length do begin ch:=t[c].element[i]; if ch in ['A'..'Z'] then m:=total(ch) else m:=ord(ch)-ord('0'); k:=k+m; end; total:=k; end;

主程序
BEGIN create; writeln(maxnumber('L')); writeln(total('L')); END.

统计细胞个数
例:一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞 数字则为同一细胞,求给定矩形阵列的细胞个数。 输入: 整数m,n(m行,n列) 矩阵 输出: 细胞的个数。 样例: 输入: 4 10 0234500067 1034560500 2045600671 0000000089 输出: 4

0234500067 1034560500 2045600671 0000000089

统计细胞个数
算法步骤: 1、从文件中读入m*n矩阵,将其转换为0、1矩阵存入pic数组中; 2、沿pic数组矩阵从上到下,从左到右,找到遇到的第一个细胞;将 细胞的位置入队h,并沿其上、下、左、右四个方向上搜索,如果遇到细 胞(pic[I,j]=1)则将其位置入队,入队后的位置pic[I,j]数组置为0; 3、将h队的队头出队,沿其上、下、左、右四个方向上搜索,如果遇 到细胞则将其位置入队,入队后的位置pic数组置为0; 4、重复3,直至h队空为止,则此时找出了一个细胞; 5、重复2,直至矩阵找不到细胞; 6、输出找到的细胞数。

统计细胞个数
const dx:array[1..4] of -1..1=(-1,0,1,0); dy:array[1..4] of -1..1=(0,1,0,-1); var s:string; pic:array[1..50,1..80] of 0..1; {0:无细胞;1:有细胞} m,n,i,j,num:integer; h:array[1..4000,1..2] of byte; {队列:存细胞的坐标,1:行;2:列}

统计细胞个数
procedure doing(p,q:integer); {处理坐标(p,q)的细胞} var i,f,r,x,y:integer; begin inc(num); {细胞数量加1} pic[p,q]:=0; f:=1; {队列头} r:=1; {队列尾} h[f,1]:=p; h[f,2]:=q; {遇到的第一个细胞入队} repeat for i:=1 to 4 do {沿细胞的上下左右四个方向搜索细胞} begin x:=h[f,1]+dx[i]; y:=h[f,2]+dy[i]; if (x>0) and (x<=m) and (y>0) and (y<=n) and (pic[x,y]=1) then begin inc(r); h[r,1]:=x; h[r,2]:=y; pic[x,y]:=0; end; {为细胞的入队} end; inc(f); {队头指针加1,出队列} until f>r; {直至队空为止} end;

统计细胞个数
Begin fillchar(pic,sizeof(pic),0); num:=0; fillchar(h,sizeof(h),0); readln(m,n); for i:=1 to m do begin readln(s); for j:=1 to n do if s[j]='0' then pic[i,j]:=0 else pic[i,j]:=1; end; for i:=1 to m do for j:=1 to n do if pic[i,j]=1 then doing(i,j); {在矩阵中寻找细胞} writeln(num); End.


? ? ? ? 树的递归定义: 有且仅有一个结点没有前驱(父结点),该结点为树的根 除根外,其余所有结点有且仅有一个前驱 除根外,每一个结点都通过唯一的路径连到根上
r 根结点

第一层

分支结点

a

b

c

第二层

e

f j

g 叶结点

h k

i

第三层 第四层


? ? ? ? ? 结点的度=该结点的子树树目 树的度=max(所有结点的度) 树的深度(高度)=树中最大的层次 森林:若干棵互不相交的树的集合 有序树和无序树

树的表示方法
? 自然界的树形表示法:用结点和边表示树 ? 括号表示法:先将根结点放入一对()中,然后把它的子树按由左而 右的顺序放入()中,而对子树也采用同样方法处理:同层子树放入 它们根结点后面的()中,同层子树之间用逗号隔开: (r(a(e,f(j)),b(g),c(h(k),i)))

树的存储结构
? 静态记录数组
所有结点存储在一个数组中,数组元素为记录类型,包括数据域和长度为n(n为树 的度)的数组,分别存储该结点的每一个儿子的下标。 Const n=树的度; max=结点数的上限; Type node=record data:datatype; ch:array[1..n]of integer; end; treetype=array[1..max] of node; Var tree:treetype;

树的存储结构
? 动态多重链表
每个结点由数据域和n(n为树的度)个指针域共n+1个域组成。 const n=树的度; Type treetype=^node; node=record data:datatype; next:array[1..n] of treetype; end; var root:treetype;

二叉树
? ? ? ? 二叉树的递归定义 二叉树是以结点为元素的有限集,它或者为空,或者满足以下条件: 有一个特定的结点称为根; 余下的结点分为互不相交的子集L和R,其中R是根的左子树,L是根的右子树,L和 R又是一棵二叉树。 二叉树和树是两个不同的概念: 树的每个结点可以有任意多个后继,而二叉树中每个结点的后继不能超过2; 树的子树可以不分次序(有序树除外),而二叉树的子树有左右之分。 树不能为空,但二叉树可空。

? ? ? ?

二叉树的形态
? 二叉树的五种基本形态

a 空二叉树

b 只有一个结点的二叉树

c 只有左子树的二叉树

d 只有右子树的二叉树

e 左、右子树均有的二叉树

二叉树的两个特殊形态
? 满二叉树:一棵深度为K且有2K-1个结点的二叉树称为满二叉树

? 完全二叉树:如果一棵二叉树最多只有最下面两层结点度数可以小于2,并且最下面 一层的结点都集中在该层最左边的若干位置上,则称此二叉树为完全二叉树。

二叉树的存储结构
? 顺序存储结构
Const m=树中结点数上限; Type node=record data:datatype; prt,lch,rch:0..m; end; Treetype=array[1..m]of node; Var tree:treetype;

二叉树的存储结构
? 链式存储结构
Type bitrpetr=^node; node=record data:datatype; lch,rch:bitrpetr; end; Var bt:bitreptr;

二叉树的遍历
? 前序:abdheicfjkgl ? 中序:dhbeiajkfclg ? 后序:hdiebkjflgca
b d h e i j k f l a c g

前序遍历
? 二叉链表 Procedure preorder(bt:bitreptr); Begin if bt<>nil then begin 访问处理bt^.data; preorder(bt^.lch); preorder(bt^.rch); end; End; ? 二叉树的顺序存储结构 Procedure preorder(i:integer;); Begin if i<>0 then begin 访问处理tree[i].data; preorder(tree[i].lch); preorder(tree[i].rch); end; End;

中序遍历
? 二叉链表 Procedure inorder(bt:bitreptr); Begin if bt<>nil then begin inorder(bt^.lch); 访问处理bt^.data; inorder(bt^.rch); end; End; ? 二叉树的顺序存储结构 Procedure inorder(i:integer;); Begin if i<>0 then begin inorder(tree[i].lch);
访问处理tree[i].data;

inorder(tree[i].rch); end; End;

后序遍历
? 二叉链表 Procedure postorder(bt:bitreptr); Begin if bt<>nil then begin postorder(bt^.lch); postorder(bt^.rch); 访问处理bt^.data; end; End; ? 二叉树的顺序存储结构 Procedure inorder(i:integer;); Begin if i<>0 then begin inorder(tree[i].lch); inorder(tree[i].rch);
访问处理tree[i].data;

end; End;

普通有序树的遍历
1、普通树转换成二叉树 ? 长子变左儿子 ? 兄弟变右儿子 2、遍历二叉树
w x r a w d h x e m b f i o s j n h c t u a r b x d e m c h r a b

f
d s e i m o o n n j

c

w

f
i

s
j

t

u

t u

普通有序树的遍历
按照先根次序和后根次序遍历普通有序树: 输入一棵普通有序树,输出该树的先根次序和后根次序。 [输入] 顶点个数n(1<=n<=200) 以下含有n行,其中第i行(1<=i<=n)的元素依次为结点i的数据值ai。以后各元素为结 点i的儿子序列,以0结束。若ai后仅含一个0,则说明结点i为叶子。 [输出] 两行,分别为普通有序树的先根次序和后根次序。

普通有序树的遍历
例如对于右图中的普通有序树,对应的输入信息为:
18 ‘r’ 2 3 4 0 ‘a’ 5 6 0 ‘b’ 7 0 ‘c’ 8 9 10 0 ‘w’ 0 ‘x’ 11 12 0 ‘f’ 0 ‘s’ 13 14 0 ‘t’ 0 ‘u’ 0 ‘d’ 15 0 ‘e’ 0 ‘i’ 16 17 18 0 ‘j’ 0 ‘h’ 0 ‘m’ 0 ‘o’ 0 ‘n’ 0

r a w
5 2

1 3 4

b
6

c s i
13 8

x
11

f
12

7

t

9

u

10

d h
15

e

j

14

m

16

o

17

n

18

普通有序树的遍历
Begin fillchar(tree,sizeof(tree),0); readln(n); for i:=1 to n do begin read(tree[i].data); read(j); if j<>0 then begin tree[i].lch:=j; tree[j].prt:=i; p:=j; {从结点j出发转换其他兄弟结点} repeat read(j); {读结点i的下一个儿子序号} if j<>0 then begin tree[p].rch:=j; tree[j].prt:=p; p:=j; end; until j=0; end; readln; end; preorder(1); inorder(1); End.

森林的遍历
? 森林转换成二叉树
r a b c d s t

e
g

f r a s b c f d e f t

r
a b c d

s e

t

g g

由中序和后序确定前序
? 中序和后序确定前序 ? 中序:s’=s1’……sk’……sn’ ? 后序:s’’=s1’’…………sn’’ ? 显然, sn’’为根,在前序中直接输出,设在中序中与sn’’相同的字符为sk’ ? 若k>1,则左子树存在, s1’……sk-1’为左子树的中序遍历,s1’’……sk-1’’为左子树 的后序遍历 ? 若k<n,则右子树存在, sk+1’……sn’为右子树的中序遍历,sk’’……sn-1’’为右子树 的后序遍历

由中序和后序确定前序
Procedure solve1(s1,s2:string); Var k:integer; Begin if length(s2)=1 then write(s2) {递归出口} else begin k:=pos(s2[length(s2)],s1); write(s1[k]); if k>1 then solve1(copy(s1,1,k-1),copy(s2,1,k-1)); if k<length(s1) then solve1(copy(s1,k+1,length(s1)-k),copy(s2,k,length(s2)-k)); end; End;

由中序和前序确定后序
Procedure solve2(s1,s2:string); Var k:integer; Begin if length(s2)=1 then write(s2) else begin k:=pos(s2[1],s1); if k>1 then solve2(copy(s1,1,k1),copy(s2,2,k)); if k<length(s1) then solve2(copy(s1,k+1,length(s1)-k), copy(s2,k+1,length(s2)-k)); write(s2[1]); end; End;

二叉树的应用
? 二叉排序树 ? 最优二叉树

二叉排序树
? ? ? ? 二叉排序树是具有以下性质的非空二叉树: 若根的左子树不空,则左子树的所有结点值均小于根结点值; 若根的右子树不空,则右子树的所有结点值均不小于根结点值; 根结点的左、右子树也分别为二叉排序树。

例:输入序列a1,a2……an(1<=n<=1000),将a按照递增顺序排列后输出。 ? ① ② ③ 构造二叉排序树的方法: 令a1为二叉树的根; 若a2<a1,则令a2为a1左子树的根结点,否则令a2为a1右子树的根结点; 对a3,a4……an递归重复②。

构造二叉排序树
例:a序列为:35 40 30 90 82 32 33 37
35 30 32 37 33 82 40 90

中序遍历:30 32 33 35 37 40 82 90

构造二叉排序树
procedure createtree; begin fillchar(b,sizeof(b),0); b[1].data:=a[1]; for i:=2 to n do begin b[i].data:=a[i]; p:=1; while true do if a[i]<b[p].data then if b[p].l<>0 then p:=b[p].l else begin b[p].l:=i; break; end else if b[p].r<>0 then p:=b[p].r else begin b[p].r:=i; break; end; end; end; 稳定的

构造二叉排序树
? 主程序 Begin readln(n); for i:=1 to n do read(a[i]); writeln; createtree; inorder(1); End.

最优二叉树
?最优二叉树(哈夫曼树、最优搜索树)
例:计算最优的判定过程 全校学生的成绩由百分制转换成五等分制,在五个等级上分布不均匀,颁布规律如下: 百分制分数范围 0~59 60~69 70~79 80~89 90~100 分布情况% 5 15 40 30 10 现有10000个数据,以下两种判定转化过程:
<60 <80 <70 <80 <60 <90 优

不及格

<70
及格

中 良




<90


不及格

及格

K1=10000*(1*5%+2*15%+3*40%+4*(30%+10%))=31500 K2=10000*(2*(40%+30%+10%)+3*(5%+15%))=22000

最优二叉树
? 结点的路径长度:从根到每个结点的路径长度 ? 叶结点的权值:叶结点被赋予的实数值 ? 设Wk为第k个结点的权值,Pk为第k个叶结点的带权路径长度。 L=W1*P1+W2*P2……Wn*Pn 则使L最小的树称为最优二叉树。

构造最优二叉树
? 构造方法:
① 将给定的N个结点构成N棵二叉树的集合F,其中每棵二叉树Ti中只有一个权值为Wi 的根结点Ki,其左右、子树均为空; ② 在F中选取根结点权值最小的两棵二叉树作为左、右子树,构造一棵新的二叉树, 并且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和; ③ 在F中删除这两棵二叉树,同时将新得到的二叉树加入F中; ④ 重复②③,直到在F中只含有一棵二叉树为止。
24 7 A 7 A 5 B 5 B 2 C 6 4 D 6 E 11 6 E 7 A 13 24 13 A 7 E 6 B 5 C 2 11 6 D 4

11

6 E

最优二叉树
? 最优二叉树中非叶子结点的度均为2 ? 如果叶结点数为N,则总结点数为2*N-1
证明:设叶结点数为N,总结点数为M, 度为1的结点数为N1(本题中为0),度为2 的结点数为N2。则:M=N+N1+N2 (式子1)
度为1结点有一个孩子,度为2的结点有2

Const n=叶结点的上限; 个孩子,故二叉树中孩子结点总数是: m=2*n-1; N1+2N2; Type node=record 树中只有根结点不是任何结点的孩子, 帮二叉树中的结点总数又可表示为: data:integer; M=N1+2N2+1 (式子2) prt,lch,rch,lth:0..m; 由式子1和式子2可得出:N2=N+1 end; 本题中N1=0,故可得出:M=2N-1 wtype=array[1..n] of integer; treetype=array[1..m] of node; {tree[1..n]为叶子结点, tree[n+1..2*n-2]为分支结点,tree[2*n-1]为根} Var tree:treetype; w:wtype;

构造最优二叉树
Procedure hufm(w:wtype;var tree:treetype; var bt:integer); function min(h:integer):integer; begin m1:=maxint; for p:=1 to h do if (tree[p].prt=0) and (m1>tree[p].data) then begin i:=p; m1:= tree[p].data; end; min:=i; end; Begin fillchar(tree,sizeof(tree),0); for i:=1 to n do read(tree[i].data); for k:=n+1 to m do begin i:=min(k-1); tree[i].prt:=k; tree[k].lch:=i; j:=min(k-1); tree[j].prt:=k; tree[k].rch:=j; tree[k].data:=tree[i].data+tree[j].data; end; bt:=m; End;

求最优判断
Procedure ht(t:integer); {通过前序遍历计算每个叶子的路径长度} Begin if t=m then tree[t].lth:=0 else tree[t].lth:=tree[tree[t].prt].lth+1 if (tree[t].lch<>0) or (tree[t].rch<>0) then begin ht(tree[t].lch); ht(tree[t].rch); end; End; BEGIN readln(n); for i:=1 to 5 do readln(w[i]); hufm(w,tree,bt); ht(bt); sum:=0; for i:=1 to 5 do sum:=sum+tree[i].lth*tree[i].data; writeln(n*sum:0:0); END.

FBI树
【问题描述】 我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含 “0”又含“1”的串则称为F串。 FBI树是一种二叉树 ,它的结点类型包括F结点,B结点和I结点三种。由一个 长度为2N的“01”串S可以构造出一棵FBI树T,递归的构造方法如下: 1、T的根结点为R,其类型与串S的类型相同; 2、若串S的长度大于1,将串S从中间分开,分为等长的左右子串S1和S2;由左子串S1构造R的左子树T1, 由右子串S2构造R的右子树T2。 现在给定一个长度为2N的“01”串,请用上述构造方法构造出一棵FBI树,并输出它的后序遍历序列。 【输入文件】 输入文件fbi.in的第一行是一个整数N(0 <= N <= 10),第二行是一个长度为2N的“01”串。 【输出文件】 输出文件fbi.out包括一行,这一行只包含一个字符串,即FBI树的后序遍历序列。

【样例输入】 3 10001011 【样例输出】 IBFBBBFIBFIIIFF
【数据规模】 对于40%的数据,N <= 2; 对于全部的数据,N <= 10。

FBI树
自下而上逐层生成FBI树: 设tree为FBI树,其中tree[i]为结点i的类型类型标志,即tree[i]∈{‘F’,’B’,’I’} treel,treer分别为FBI树的左儿子序列和右儿子序列,即结点i的左儿子序号为treel[i],右儿子序号为treer[i] 设m=2^n FBI树的叶结点存储于tree[m]..tree[m*2-1],然后从底层出发,自下而上地逐层向上计算tree[m-1]..tree[1], 其中结点i的左儿子序号为2*i,右儿子序号为2*i+1,即treel[i]:=i*2,treer[i]:=i*2+1。 如:当n=3时,编号情况右图:

1 2 4 8 9 10 5 11 12 6 3 7 13 14 15

type

tree1=array[1..2050] of char; treelr=array[1..2050] of integer;

var

treel,treer:treelr;

tree:tree1;

i,n,m:integer;

s:string[2];

ch:char;

readln(n); if n<>0 then begin read(ch); if ch='1' then writeln('I') else writeln('B'); halt; end; m:=1; for i:=1 to n do m:=m*2; for i:=m to m*2-1 do begin read(ch); if ch='1' then tree[i]:='I' else tree[i]:='B'; treel[i]:=0; treer[i]:=0; end;

for i:=m-1 downto 1 do begin treel[i]:=2*i; treer[i]:=2*i+1; s:=tree[2*i]+tree[2*i+1]; if (s[1]='F') or (s[2]='F') then tree[i]:='F' else begin if s[1]=s[2] then if s[1]='I' then tree[i]:='I' else tree[i]:='B' ; if s[1]<>s[2] then tree[i]:='F'; end; end; inorder(1);


? 图是较线性表和树更为复杂的一种数据结构,在这种 数据结构中,数据结点间的联系是任意的,因此它可 以更广泛地表示数据元素之间的关系。 ? 线性表和树是图的特例。

图的基本概念
? 图的定义 ? 如果数据元素集合D中的各元素之间存在任意的前驱和后继关系R,则此数据结构 G=(D,R)称为图。 ? 如果将数据元素抽象成顶点,元素之间的前驱或后继关系用边表示,则图亦可以表 示为G=(V,E),其中V是顶点的有限(非空)集合,E是边的集合,如果元素Vi 是元素Vj的前驱,则用(Vi, Vj)表示它们之间的边。

v1 v2 v4 v5 v3

v1

v2
v3

v4

无向图和有向图
? 无向图
? 在图G=(V,E)中,如果对于任意的Vi,Vj∈V,当(Vi,Vj) ∈ E时,必有(Vj,Vi) ∈ E, 则称此图为无向图(如:图2)。 ? 在一个具有n个顶点的无向图中,边的最大数目为n(n-1)/2,此时的图称为无向完全图 (如:图3)。 ? 在无向图中,与一个顶点相连的边数为该顶点的度。
v1 v1

v2 v4
图2

v3 v5

v2 v4 图3 v5

v3

无向图和有向图
? 有向图
? 在图G=(V,E)中,如果对于任意的Vi,Vj∈V,当(Vi,Vj) ∈ E时, (Vj,Vi) ∈ E未必 成立,则称此图为有向图(如:图4)。 ? 顶点的出度:该顶点后继的个数 ? 顶点的入度:该顶点前驱的个数 ? 顶点的度=出度+入度 v1 ? 图的度=MAX(所有结点的度)
v2
v3 图4

v4

路径和连通集
?在图G=(V,E)中,如果对于顶点Vi,Vj,存在满足下述条件的结点序 列X1,X2……Xk(k>1) ? X1=Vi,Xk=Vj ? (Xi,Xi+1) ∈E i=1,2,……,k-1 则称结点序列X1=Vi,X2,……,Xk=Vj为顶点Vi到顶点Vj的一条路径,而路 径上的边的数目k-1称为该路径的长度,并称顶点集合{X1,…..,Xk}为连通 集。

简单路径和回路
? 如果一条路径上的顶点除起点X1和终点Xk可以相同外,其他顶点均不 相同,则称此路径为一条简单路径。 ? 如:图2中1 2 4 5是一条简单路径,而1 2 4 3 1 5不是。

? X1= Xk的简单路径称为回路(也称为环)。 ? 如:图4中1 4 2 1为一条回路。
v1 v2 v4 图2 v5 v3 v2 v3 图4 v1 v4

有根图
? 在一个图中,若存在一个顶点w,它与其他顶点都是连通的,则称此 图为有根图,顶点w即为它的根。 ? 图5为有根图,1 2 3 4都可以作为根; ? 图6为有根图,1或2为它的根。
1 3 4 图5 2 3 图6

1 2

连通图和连通子图
? 对于无向图而言,若其中任两个顶点之间是连通的,则称该图为连通 图。 ? 一个无向图的连通分支定义为此图的连通子图。 ? 图2是连通的,它的连通子图即为本身。

v1
v2 v4 图2 v5 v3

强连通图和强连通分支
? 对于有向图的任意两个顶点Vi、Vj间(Vi<>Vj ),都有一条从Vi到Vj的有 向路径,同时还有一条从Vj到Vi的有向路径,则称该有向图是强连通 图。 ? 有向图中强连通的最大子图称为该图的强连通分支。 ? 图6不是强连通的,它含有两个强连通分支,如图7。

1 1 2 2 3 图6 图7 3

零图和平凡图
? 在一个图中不与任何顶点相邻接的顶点称为孤立顶点。 ? 如:图7中的3 ? 仅由孤立顶点组成的图称为零图。 ? 仅由一个孤立顶点组成的图称为平凡图。

1 3 2 图7

图的存储结构
? 相邻矩阵表示法: ? 若G=(V,E)是一个具有N个顶点的图,则G的相邻矩阵是如下定义的二维数组A, 其规模为N*N
A[i,j]= 3 8 图8 5 6 v3 2 0 3 5 8 0 3 0 6 4 11 5 6 0 2 0 v4 4 10 v5 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 v4 0 0 1 0 1 0 1 0 0 0 1(或权) 0(或±∞) (Vi,Vj) ∈E (Vi,Vj) ∈E v1 v5 图9 v2 v3

v1

v2

11

A1=

8 4 2 0 10

0 11 0 10 0

A2=

相邻矩阵的特点
Type maxn=顶点数的上限; Var a:array[1..n,1..n] of integer; f:array[1..maxn] of boolen; ? 无向图的相邻矩阵是对称的,而有向图不是。占用的存储单元数只与顶点数有关而与 边数无关。 ? 相邻矩阵方便度数的计算。 ? 容易计算路径的存在性。 在无权有向图或无向图中,判定Vi,Vj两个顶点之间否存在长度为m的路径,只要考虑 am=a*a*a*……*a(m个a矩阵相乘后的乘积矩阵)中(i,j)的元素值是否为0就行了。

图的邻接表示法
? 用邻接表法表示图需要保存一个顺序存储的顶点表和n个边表(每个边表为一个单链 表,存储与一个顶点相连的所有边的信息)。 ? ? ? ? ? 顶点表的每个表目对应于图的一个顶点,包括 顶点信息,即: 与该顶点相连的边数m; 访问标志visited 边表的首指针firstarc。图中每个顶点都有一个边表,其中每一个顶点对应于与该顶 点相关联的一条边,包括: ? 与此边相关联的另一个顶点序号v; ? 若为带权图的话,该边的权值w; ? 指向边表的下一个顶点的后继指针nextarc.

图的邻接表示法
Const max=图的顶点数的上限; Type arcptr=^arcnode; {边表的指针类型} arcnode=record {边表的顶点类型} v:integer; {关联该边的另一顶点序号} w:real; {边的权值} nestar:arcptr; {边表的后继指针} end; vexnode=record {顶点表的表目类型} m:integer; {与该顶点相连的边数} visited:boolean; {访问标志} firstarc:arcptr; {边表的首指针} end; adjlist=array[1..max] of vexnode; {邻接表类型} Var dig:adjlist; {邻接表} n,e:integer; {顶点数和边数}

图的邻接表示法
2
v1 3 v5 1 4 v4 7 v2 5 v3

6 图10

m 1 2 3 4 5 1 2 2 1 1

visited false false false false false

frstarc

v 2 5 4 1 4

w 2 4 7 3 6

nestarc nil

v

w

nestarc

1 2 nil nil

1 5

nil nil

图的邻接表示法
读n; For i:=1 to n do begin with dig[i] do begin m:=0; firstarc:=nil; visited:=false; end; end; 读e; For i:=1 to e do begin 读第i条边关联的顶点序号j,k和该边的权Wjk; dig[j].m:=dig[j].m+1; new(q); with q^ do begin v:=k; w:=w[j,k]; nestarc:=dig[j].firstarc; end; dig[j].firstarc:=q; end;

图的遍历
? 深度优先搜索dfs ? 广度优先搜索bfs

深度优先搜索dfs
? 从某个顶点V0出发,访问此顶点。然后依次从V0的未被访问的邻接点出发深度优先 遍历图,直至图中所有和V0有路径相连的顶点都被访问到。若此时图中尚有顶点未 被访问,则另选一个未曾访问的顶点作为起始点,重复上述过程,直到图中所有顶 点都被访问为止。

? 从V1出发,dfs图8的结果是:V1 V2 V3 V4 V5 ? 从V3出发,dfs图10的结果是:V3 V2 V1 V5 V4 ? 从V1出发,dfs图10的结果是:V1 V2 V5 V4 V3
3 8 2 v2 4 6 10 2 11 v5 v5 v1 3 1 4 v4 7 v2 5 v3

v1

图8

5

v3

v4

6 图10

深度优先搜索dfs
相邻矩阵: Procedure dfs(i:integer); Begin 访问处理结点i; f[i]:=true; for j:=1 to n do if (not f[j]) and (a[i,j]=1) then dfs(j); End; Procedure traver1; Begin fillchar(f,sizeof(f),0); for i:=1 to n do {深度优先搜索每一个未访问的顶点} if not f[i] then dfs(i); End; 调用一次dfs(i),可按深度优先搜索的顺序访问处理顶点i所在的连通分支(强连通分支)

广度优先搜索bfs
? 假设从图中某顶点V0出发,在访问了V0之后依次访问V0的各个未曾访问的邻接点,然后分别 从这些邻接点出发按广度优先搜索的顺序遍历图,直至图中所有可被访问的顶点都被访问过。 ? 从V1出发,bfs图8:V1 V2 V3 V4 V5

v1 8

3

v2 4

11 v5 10

图8

5 6

v3

2

v4

广度优先搜索bfs
队列

f r
队列

v1
v1 r

3 8

v2 4

11 v5 10

f
队列

v1

5 6 v3 2

v4 图8

f r
队列

v2 f

v3

v4 r

v1 v2 v3

队列

v3 f

v4 r

队列

v3 f

v4

v5 r

v1 v2 v3 v4 v5

队列

v3 f

v4

v5 r

广度优先搜索bfs
Procedure bfs(i:integer); Begin 访问处理结点i; f[i]:=true; r:=r+1; q[r]:=i; {结点i进入队列q} while r<>front do begin front:=front+1; {从队列中移出队首元素} for j:=1 to n do if (not f[j]) and (a[q[front],j]=1) then begin 访问顶点j; f[j]:=true; r:=r+1; q[r]:=j; {结点j进入队列q} end; end; End;

广度优先搜索bfs
Procedure traver2; Begin fillchar(f,sizeof(f),0); for i:=1 to n do if (not f[j]) then bfs(i); End;

调用一次bfs(i),可按广度优先搜索的顺序访问处理顶点i所在的连通分支 (强连通分支)

单源最短路径
? 现有一张县城地图,图中的顶点为城镇,无向边代表两个城镇间的连通关系,边上的权 为公路造价,县城所在的城镇为V0。由于该县经济比较落后,因此公路建设只能从县城 开始规划。规划的要求是所有可到达县城的城镇必须建设一条通往县城的汽车线路,该 线路的工程总造价必须最少。 ? 输入:n(城镇数,1<=n<=20) 县城所在的城镇序号V0 e(有向边数,1<=e<=210) 以下e行,每行为3个整数,两个城镇的序号和它们间的公路造价。 ? 输出:k行,每行为一条通往县城的汽车线路的总造价和该条线路途径的城镇序号。

单源最短路径( Dijkstra算法)
? 单源最短路径:设G=(V,E)是一个有向图,它的每一条边(u,v) ∈E都有一个权W(u,v), 在G中指定一个顶点V0,要求把从V0到G的每一个顶点Vj(Vj ∈E)的最短有向路找出来 (或者指出不存在从V0到Vj的有向路,即V0到Vj不可达)。这个问题即为单源最短路 径。 ? Dijkstra算法:
?
?

把图中所有结点分为两组,每一个结点对应一个距离值:
第一组:包括已确定最短路径的结点,结点对应的距离值是由 v0到此结点的最短路径 长度;

?

第二组:包括尚未确定最短路径的结点,结点对应的距离值是v0经由第一组结点(中 间结点)至此结点的最短路径长度;
我们按最短路径长度递增的顺序把第二组的结点加到第一组中去,直至v0可达的所有 结点都包含于第一组。在这个过程中,总保持从v0到第一组各结点的最短路径长度都 不大于从v0至第二组任何结点的路径长度。

?

单源最短路径( Dijkstra算法)
圆内的数字为距离值。绿 色的结点为第一组的结点, 灰色的结点为第二组的结 点
∞ 13 14 9 9

10 88

0

5

7 ∞7

单源最短路径( Dijkstra算法)
?初始时v0进入第一组,v0的距离值为0;第二组包含其它所有结点,这些结点对应的距

离值这样确定(设vi为第二组中的结点):
dist[i]= W[0,i ] ∞ (V0,Vi) ∈E (V0,Vi) ∈E

?然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中。每往第一

组加入一个结点vm,就要对第二组的各结点的距离值作一次修正(设vi为第二组的结点, (vm,vi)为图中的边):
?若加进vm做中间结点使得v0至vi的路径长度更短(即vi的距离值>vm的距离值+Wmi),

则要修改vi的距离(vi的距离值←vm的距离值+Wmi)。修改后再选距离值最小的一个结 点加入到第一组中,…。如此进行下去,直至第一组囊括图的所有结点或再无可加入第 一组的结点存在。显然,这种从第二组的结点中选距离值最小的结点扩展是一种贪心策 略。

用一维数组来实现优先队列。设 n—图的结点数; adj—有向图的相邻矩阵。其中 dist—最短路径集合。其中

dist[i].pre—在v0至vi的最短路径上,vi的前趋结点序号;
dist[i].length—v0至vi的最短路径长度,即vi的距离值;(1≤i≤n)

Const n=图的结点数; Type path=record {路径集合的结点类型} length:real; {距离值} pre:0‥n; {前趋结点序号} end; var adj:array[1‥n,1‥n] of real; {相邻矩阵} dist:array[1‥n] of path; {路径集合}

Dijkstra算法
fillchar(adj,sizeof(adj),0);{建立相邻矩阵adj} for i←1 to n do for j←1 to n do if(i,j)∈E then adj[i,j]←wij else adj[i,j]←∞; for i←1 to n do {路径集合初始化} begin dist[i].length←adj[v0,i]; if dist[i].length<>∞ then dist[i].pre←v0 else dist[i].pre←0; end;{for} adj[v0,v0]←1; {源结点v0进入第一组} repeat min←∞;u←0; for i←1 to n do {从第二组中找距离值最小的结点u} if (adj[i,i]=0)and(dist[i].length<min) then begin u←i;min←dist[i].length;end; if u<>0 {第二组中存在一个距离值最小的结点} then begin adj[u,u]←1; {结点u进入第一组} for i←1 to n do {修正第二组中u可达的结点距离值} if(adj[i,i]=0)and(dist[i].length>dist[u].length+adj[u,i]) then begin dist[i].length←dist[u].length+adj[u,i]; dist[i].pre←u; end; end;{then} until u=0;

Dijkstra算法
算法结束时,沿着结点vi的pre指针回溯,便可确定v0至vi的最短路径: procedure print(i:integer); Begin if i=v0 then 输出结点v0 else begin print(dist[i].pre); 输出结点i和v0至vi的最短路径长度dist[i].length; end;{else} End;{print} 显然递归调用print[1],…,print[n]后,可得知v0至所有结点的最短路径。 主程序: Readln(n); Readln(v0); 输入城镇间的序号及造价; 计算单源最短路径方案; For i:=1 to n do begin if (i<>v0) and (dist[i].length<>∞) then begin writeln(dist[i].length); print(i); end; writeln; end;

图的生成树
? 若图是连通的无向图或强连通的有向图,则从其中任一个顶点出发,调用一次dfs或 bfs后便可以系统地访问图中所有顶点; ? 若图是有根的有向图,则从根出发通过调用一次dfs或bfs后亦可以系统地访问图中所 有顶点; ? 在这种情况下,图中的所有顶点加上遍历过程中经过的边所构成子图称作图的生成 树。
v1 8 5 v3 6 3 v2 11 v5 10 v5
图8的广度优先搜索树

v1 v2 v3 v4

v1

v2 v3

v3

4 2
v4 图8

v2
v1 v5

v4

v5 图9

v4

图9的深度优先搜索树

图的最小生成树
? 现有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上 的权为公路造价。在分析了这张地图后可以发现,任一对城市都是连通的。现在的 问题是,要用公路把所有的城市都联系起来,如何设计可使工程总造价最少。 ? 输入: ? n(城市数,1<=n<=20) ? e(有向边数,1<=e<=210) ? 以下e行,每行为边(I,j)和该边的距离Wij(1<=i<=n, 1<=j<=n) ? 输出: ? n-1行,每行为两个城市的序号,表明这两个城市间建一条公共汽车线路。

图的最小生成树
? 在一张有权连通图中,如何寻找一棵各边权的总和为最小的生成树,就是本章节所 要讨论的问题。 计算最小生成树的思维方向:为了保证边权总和最小,必须保证 ①、添加(u,v)不能够形成回路; ②、在保证①的前提下添加权尽可能小的边,这样的边称之为安全边。 计算最小生成树的步骤:有两种算法可计算图的最小生成树 ? Kruskal算法 ? Prim算法

Kruskal算法
对给定图的所有边从小到大排序,依次试探将边和它的端点加入生成树,如果加 入的边不产生环,则继续将边和它的端点加入,否则,将它删去,直到生成树中 含有n-1条边。

Kruskal算法
Const maxn=210; maxe=maxn*maxn; {顶点数和边数的上限} Type edgetype=Record {边的类型} x,y,c:longint; {边权为c的边(x,y)} End; Var e:Array [1..maxe] of edgetype; {边集,其中第i条边为(e[i].x,e[i].y),该边的权为e[i].c} n,m,ans:longint; {顶点数为n,边数为m} f:Array [1..maxn] of longint; {并查集,其中f[i]为顶点i所在并查集的代表顶点,即子 树根}

Kruskal算法
通过函数top(i)计算顶点i所在子树的根
Function top(i:longint):longint; {计算和返回顶点i所在并查集的代表顶点} Begin if i<>f[i] Then f[i]←top(f[i]); {若i非所在并查集的代表顶点,则沿f[i]递归} top←f[i]; {返回顶点i所在并查集的代表顶点} End;

Kruskal算法
通过过程Union(i,j,c)合并顶点i和顶点j所在的两棵树
现有边权为c的边(i,j)。若该边的两个端点分属于两棵树,顶点i和顶点j所在子树的根分 别为x和y,则(i,j) 加入最小生成树,合并两棵树(即顶点i和顶点j所在的并查集)。 Procedure Union(i,j,c:longint); {合并i和j所在集合} Var x,y:longint; Begin x←top(i); y←top(j); {分别取出顶点i和顶点j所在子树的根} if x<>y Then Begin inc(ans,c); f[y]←x; End; {若i和j分属于两棵子树,则该边权计入最小生 成树的权和,两棵子树合并} End;

Kruskal算法
BEGIN 按照边权值(c域值)递增的顺序排序边集e; For i←1 to n do f[i]←i; {建立由n棵树组成的森林,每棵树包含图的一个顶点} ans←0; { 最小生成树的权和初始化为0} For i←1 to m do union(e[i].x,e[i].y,e[i].c); {枚举每条边,将两个端点分属两棵树的边加入最小生成树} writeln(ans); END.

Prim算法
? 任取一个顶点加入生成树,然后对那些一个端点在生成树中,另一个端点不在生成 树中的边进行排序,取权值最小的边,将它和另外一个端点加进生成树中。重复上 述步骤直到所有顶点都进入了生成树为止。

Prim算法
d[i]—顶点i与生成树相连的最短边长; ba[i]—顶点i在生成树的标志; w[i,j]—(i,j)的边长。若图中不存在边(i,j),则w[i,j]=∞ min—所有未在生成树的顶点的最小距离值

Prim算法
fillchar(ba,sizeof(ba),0); {所有顶点未在生成树} for i:=2 to n do d[i]:=∞; {所有顶点的距离值初始化} d[1]:=0 ;ans:=0; {顶点1的距离值和生成树的权和初始化} for i:=1 to n do {依次范围每个顶点} Begin min:=∞; {在所有未在生成树、且距离值最小(min)的顶点k} for j:=1 to n do if (not ba[j]) and (d[j]<min) then begin k:=j; min:=d[j];end; if min=∞ then begin ans:=-1; break;end;{若这样的顶点不存在,则无解退出} ans:=ans+min; ba[k]:=true;{最小距离值min计入生成树的权和,顶点k进入生成树} for j:=1 to n do {调整与k相连的各顶点的距离值} begin min:=w[k,j]; if min<d[j] then d[j]:=min; end;{for} End;{for} writeln(ans:0:3); {输出最小生成树的权和}

Kruskal与Prim的比较
? 共同点:贪心,选择边权最小的安全边; ? 不同点:Kruskal算法在森林中的两棵树之间添安全 边;Prim算法在单棵树上添安全边。

计算无向图的传递闭包
无向图的传递闭包主要用于计算图的连通性和图中满足条件的连通分支, 借鉴传递闭包的思想,可计算每一对顶点之间的最短路径。 ?判别两个顶点之间确否有路 ?寻找满足条件的连通分支 ?计算每一对顶点间的最短路径(floyd算法)

判别两个顶点之间确否有路
输入一张无向图,指出该图中哪些顶点对之间有路 输入: n(顶点数,1<=n<=20) e(边数,1<=e<=210) 以下e行,每行为有边连接的一对顶点。 输出: K行,每行两个数,为存在通路的顶点对序号i,j(i<j) 分析: 在一张图中,如何判别两个顶点之间是否有路,通常采用传递闭包的计算方法。设: Var link,longlink:array[1..20,1..20] of boolean; {无向图和无向图的传递闭包。} 对于i,j和k=1,2,……n,如果图中顶点i至顶点j间存在通路且通路上所有顶点的序号均属于{1,2,……k}, 则定义longlink[i,j]=true,否则longling[i,j]=false。 longlink[i,j]:= longlink[i,j] or (longlink[i,k] and longlink[k,j])

判别两个顶点之间确否有路
主程序如下: Fillchar(longlink,sizeof(longlink),0); Fillchar(link,sizeof(link),0); Readln(n); readln(e); For k:=1 to e do begin readln(i,j); link[i,j]:=true; link[j,i]:=true;end; Longlink:=link; For k:=1 to n do {计算传递闭包} for i:=1 to n do for j:=1 to n do longlink[i,j]:= longlink[i,j] or (longlink[i,k] and longlink[k,j]) For i:=1 to n-1 do {输出所有存在通路的顶点对} for j:=i+1 to n do if longlink[i,j] then write(i,’ ’,j);

寻找满足条件的连通分支
在一张顶点带权的无向图中,计算含顶点数最多的一个连通分支和顶点的权和最大的连通分支 输入: n(顶点数,1<=n<=20) e(边数,1<=e<=210) 以下e行,每行为有边连接的一对顶点。 输出: 含顶点数最多的一个连通分支 顶点的权和最大的连通分支

寻找满足条件的连通分支
设: best,besti——含顶点数最多的连通分支中的顶点数和代表顶点; max,maxk——顶点的权和最大的连通分支的顶点权和和代表顶点; 输入图的信息; 计算传递闭包longlink; For i:=1 to n do begin k:=0; s:=0; {顶点总数k,顶点权和s} for j:=1 to n do if longlink[i,j] then begin k:=k+1; s:=s+a[i,j]; end; if k>best then begin best:=k; besti:=i; end; if s>max then begin max:=s; maxk:=i; end; if k=n then break; end; dfs(besti); {从顶点besti出发,深度优先搜索含顶点数最多的连通分支} dfs(maxk); {从顶点maxk出发,深度优先搜索顶点的权和最大的连通分支}

计算每一对顶点间的最短路径(floyd算法)
现有一张城市地图,图中的顶点为城市,有向边代表两个城市间的连通关系,边上的权即为距离, 现在的问题是:为每一对可到达的城市间设计一条公共汽车线路,要求线路的长度在所有可能的 方案里是最短的。 输入: n(顶点数,1<=n<=20) e(边数,1<=e<=210) 以下e行,每行为边(i,j)和该边的距离wij。 输出: k行,每行为一条公共汽车线路 分析: 本题可以借鉴计算传递闭包的思想,在枚举途经某中间顶点k的任两个顶点对i和j时,将顶点i 和顶点j中间加入顶点k后是否连通的判断,改为顶点i途经顶点k到达顶点j的路径是否为顶点i至顶 点j的最短路径(1<=i<=n, 1<=j<=n, 1<=k<=n ) n——有向图的顶点个数; path——最短路径集合,其中path[i,j]为vi至vj的最短路上vj的前驱顶点序号(1<=i,j<=n); adj——最短路径矩阵,初始时为有向图的相邻矩阵;

计算每一对顶点间的最短路径(floyd算法)
BEGIN Readln(n); readln(e); Fillchar(adj,sizeof(adj),maxint); For k:=1 to e do begin readln(i,j,w); adj[i,j]:=w; if w<>0 then path[i,j]:=i else path[i,j]:=0; end; For k:=1 to n do for i:=1 to n do for j:=1 to n do if adj[i,j]>adj[i,k]+adj[k,j] then begin adj[i,j]:=adj[i,k]+adj[k,j]; path[i,j]:=path[k,j]; end; For i:=1 to n do for j:=1 to n do if path[I,j]<>0 then begin print(i,j); wirteln; end; END.

Procedure print(i,j:integer); Begin if i=j then write(i) else if path[i,j]=0 then write(i,’and’,j,’no path’) else begin print(i,path[i,j]); write(j); End;

计算拓扑序列
如何判断有向图中是否存在回路 【例题】士兵排队 有n个士兵(1≤n≤26),编号依次为A、B、C、……。队列训练时,指挥官要把一 些士兵从高到矮依次排成一行。但现在指挥官不能直接获得每个人的身高信息, 只能获得“p1比p2高”这样的比较结果(p1,p2∈{ ’A’‥’Z’}),记为p1>p2。 例如A>B,B>D,F>D。士兵的身高关系如图所示: 对应的排队方案有三个:AFBD、FABD、ABFD。 输入k行,每行为a b,表示a>b

输出排队方案。
分析:士兵的身高关系对应一张有向图,图中的顶点对应一个士兵,有向边<vi,vj>表示士兵i高于 士兵j。我们按照从高到矮将士兵排出一个线性的顺序关系,即为对有向图的顶点进行拓扑排序。

计算拓扑序列
⑴拓扑序列的定义:拓扑排序是有向图的另一种重要运算。给出有向图G=(V,E)。若顶 点的线性序列v1’,…,vn’(vi’∈V,1≤i≤n)满足如下条件:

vk’至vk+1’有一条路径(1≤k<n-1)
则称该序列为拓扑序列。 一个有向图结点的拓扑序列不是唯一的。有环图不能拓扑排序。

计算拓扑序列
⑵拓扑序列的计算 ①从图中选择一个入度为0的结点且输出; ②从图中删除该结点及其所有出边(即与之相邻的所有结点的入度减一); 反复执行这两个步骤,直至所有结点都输出了,也就是整个拓扑排序完成了。或者直至 剩图中再没有入度为0的结点,这就说明此图中有环,拓扑排序不能再进行下去了。 例如:

计算拓扑序列
g:array[’A’‥’Z’,’A’‥’Z’] of 0‥1; {图的相邻矩阵} d:array[’A’‥’Z’] of integer; {结点的度数序列} s:set of ’A’‥’Z’; {士兵名集合} m,n:string; {士兵名字符串m和拓扑序列n} 图中的结点为士兵。若a>b,则g[a,b]:=1 (即a向b引入一条有向边);计算结点b的入度(即比士兵b高的人 数)d(b)←d(b)+1。显然最高士兵对应的结点入度为0: var s←[]; {士兵名集合初始化} while 文件未输入完 do begin 读a>b信息; if (a∈{ ‘A’‥ ‘Z’})and (b∈{ ‘A’‥ ‘Z’}) then begin s:=s+[a,b]; {计算士兵名集合} g[a,b]:=1; {构造有向边(a,b)} d[b]:=d[b]+1; {累计结点b的入度} end;{then} end; {while}

计算拓扑序列
计算士兵名字符集m和士兵人数k m:=‘’ ; for a= ‘A’ to ‘Z’ do if a in s then m:=m+a; k:=length(m); 对有向图G作拓扑排序。若图G中有回路,则排队方案不存在;否则拓扑序列n即为一个排队方案。拓扑排序的过程如下: n:= ‘’; {拓扑序列n初始化为空} for i:=1 to k do {依次搜索每一个出列士兵} begin j:=1; while (d[m[j]]>0) and (j≤k) do j:=j+1; {搜索第i个入度为0的结点序号j} if j>k then begin 输出失败信息; halt; end; {若入度为0的结点不存在,则队列不存在最高的士兵,无解退出} n:=n+m[j]; {入度为0的结点j进入拓扑序列n} a:=m[j]; d[a] :=∞; for j:=1 to k do {删去结点j} if g [a,m[j]]>0 then d[m[j]] :=d[m[j]]-1; end;{for} 输出拓扑序列n;

计算关键路径
【例题】计算能影响整个计划完成时间的关键活动 工厂的工程计划用一张有向图表示,有向图的结点表示事件,有向 边表示活动,边上的权标明一项活动需要的时间。结点所表示的事 件实际上就是它入边代表的活动均已完成,出边代表的活动可以开 始这样一种状态。如右图:

图中含12项活动、9个事件。其中事件v1表示开始时活动a1、a2、a3并行实施;事件v5代表活动a4、a5已经完 成,活动a7、a8可以开始。V9表示整个计划完成。活动依事件的顺序要求进行。例如活动a4、a5、a6只有当 事件v2、v3、v4分别发生后才能进行,而它们的完成又标志事件v5、v6的发生。当活动a10、a11、a12完成后, 整个计划完成。上述有向图存在唯一的入度为0的开始结点v1,表明整个计划从该事件开始;存在唯一的出度 为0的完成结点vn,表明该事件完成后,整个计划结束。现在的问题是,整个计划完成至少需要多少时间,为 提前完成计划应该加快哪些活动的速度。 输入: n(事件数,1≤n≤100) e(活动数,1≤e≤4000)。以下为e行,每行为连接两个事件的序号以及活动需要的 时间 输出:完成整个计划的最少时间。以下k行,每行为一个关键活动(i,j)和目前花费的时间wij,加快该活动的 速度能提前完成计划

计算关键路径
⑴关键路径的由来 如果有向图的结点表示活动,有向边表示活动间的优先关系,那么我们通过拓扑排序将图中的结 点排成一个满足活动先后顺序要求的线性序列。如果有向有权图满足下述条件: ①存在唯一的入度为0的结点和唯一的出度为0的结点; ②可通过拓扑排序将图中的结点排成一个满足活动先后顺序要求的线性序列(即有向图没有回路) 则称该有向有权图为AOV网(活动结点网络)。 利用AOV网可以估算出整个计划完成至少需要多少时间,为提前完成计划应该加快哪些活动 的速度等问题。解决这些问题有一种有效的方法——求关键路径方法。由于AOV网中的活动可以 并行进行,因此完成整个计划的最少时间是从开始结点v1到完成结点vn的最长路径长度(路径上 各边权的和)。具有最大长度的路径称作关键路径。 在图中v1→v2→v5→v8→v9是一条关键路径,长度为18。换句话说,整个计划至少需要18个时 间单位完成。关键路径上的活动又称关键活动。如果不能按期完成这些活动会贻误整个计划。找 出关键活动后就可以适当调度,集中力量于关键活动,以保证计划如期或提前完成。

计算关键路径
⑵关键路径的计算
为了找出关键活动,我们先定义几个变量: n—AOV网的结点数; m—AOV网的有向边数; ee[i]—vi事件可能发生的最早时间,即从开始结点v1至结点vi的最长路径长度。我们从ee(1)=0 开始向前递推 ee[j]=max{ee[i]+wij|(i,j)?E}; le[i]—在保证完成结点vn所代表的事件在ee[n]时刻发生的前提下,事件vi允许发生的最晚时间, 即le[i]=ee(n)-vi至vn最长路径长度。我们从le[n]=ee[n]出发向后递推 le[i]=min{le[j]-wij |(i,j)?E} e[k]—活动ak(对应边<vi,vj>)可能的最早开始时间,即等于事件vi的可能的最早发生时间ee[i]; l[k]—活动ak(对应边<vi,vj>)允许的最晚完成时间,即等于事件vj允许最晚发生时间le[j]; (1≤i, j≤n, 1≤k≤m) 显然活动ak的最大可利用时间是l[k]-e[k]。若最大可利用时间等于ak边所带的权 wk(即为计划时间), 则ak是关键活动。 Ak延期,则整个计划将顺延。若最大可利用时间大于 wk,则ak不是关键活动, ak的完成时间允许超过wk。只要不 超过最大可利用时间,无妨于整个计划完成的进度。

计算关键路径
(3)计算能影响整个计划完成时间的关键活动 在找出关键活动后,只要将所有的非关键活动从AOV网中去掉,这时从开始顶点至完 成顶点的所有路径都是关键路径。AOV网中的关键路径可能不止一条。并不是加快任一 关键活动就可以缩短整个计划的完成时间。只有加快那些在所有关键路径上的关键活动 才能达到目的。 设: a为关键路径组成的01矩阵,a0为辅助矩阵; b为关键活动序列,其中b[k].x,b[k].y,b[k].l分别为第k项关键活动的两个顶点序号和时 间花费; nopath为v1至vn间有路可走的标志; 首先计算关键活动序列b和关键活动组成的有向图a。然后逐一地在a图中去除一条关 键活动边,看一看是否存在v1至vn的路径。如果v1至vn间无路可走,则说明这个关键 活动为影响整个计划完成的关键活动。判别过程采用深度优先搜索。

计算关键路径
procedure dfs(i:integer); begin f[i]:=true; if i=n then begin nopath:=false; exit; end; for j:=1 to n do if (not(f[j])) and (a0[i,j]=1) then dfs(j); end;
Begin 活动的时间矩阵w初始化为0; 输入带权有向图的信息(顶点数n,活动数e和活动的时间矩阵w); if 图中的所有顶点不能排成一个拓扑序列 then 失败退出; fillchar(ee,sizeof(ee),0); for i:=1 to n-1 do {计算各个事件的最早发生时间表ee} for j:=1 to n do if ((i,j)∈ e) and (ee[j]<ee[i]+wij) then ee[j]:=ee[i]+wij; 输出完成整个计划的最少时间ee[n]; for i:=1 to n do le[i]:=ee[n]; k:=0; for i:=n-1 downto 1 do {计算各个事件的最晚发生时间表le} for j:=1 to n do if (wij<>0) and (le[i]>le[j]-wij) then le[i]:=ee[j]-wij;

fillchar(a,sizeof(a),0); for i:=1 to n-1 do {计算关键活动和 for j:=1 to n do 由关键活动组成的有向图a} if (wij<>0) and (le[j]-ee[i]=wij) then begin k:=k+1; b[k].x:=i; b[k].y:=j; b[k].l:=wij; a[i,j]:=1; end; for t:=1 to k do {枚举每一个关键活动} begin a0:=a; a0[b[t].x,b[t].y]:=0; {在图a中去除第t个关键活动} fillchar(f,sizeof(f),false); nopath:=true; dfs(1); if nopath then 输出关键活动(b[t].x,b[t].y)和目前花费b[t].l; end; End.


相关文章:
数据结构(本科)形成性考核册答案
数据结构(本科)形成性考核册答案_哲学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 数据结构(本科)形成性考核册答案_哲学_高等教育_教育专区。作业 1...
数据结构概念名词解释大全
数据结构概念名词解释大全_电脑基础知识_IT/计算机_专业资料。数据结构名词解释大全数据:是对客观事物的符号表示。 数据元素:是数据的基本单位,也称节点(node)或记录...
数据结构(C++版)知识点及相应题目
第一章知识点 P3 ·数据结构从逻辑上划分为: (1)线性结构 (2)非线性结构: 树型结构和图型结构 P4 ·从存储结构(物理结构)上划分: (1)顺序结构 :所有元素...
数据结构(C语言版)(第2版)课后习题答案
数据结构(C语言版)(第2版)课后习题答案_计算机软件及应用_IT/计算机_专业资料。数据结构(C语言版)(第2版)严蔚敏 人民邮电大学 课后习题答案 ...
数据结构(C语言)考试重点必背
数据结构概念包含三个方面:数据的逻辑结构、数据的存储结构的数据的操作。 1.3 数据的逻辑结构指数据元素之间的逻辑关系,用一个数据元素的集合定义在此集合 上的...
《数据结构》基本概念
数据结构》基本概念_IT/计算机_专业资料。Struts课程基本概念 数据 数据是信息的载体,在计算机科学中是指所有能输入 输入到计算机中并能被计算机程序识别和处理 处...
十套数据结构试题及答案
5. 设一棵完全二叉树的顺序存储结构中存储数据元素为 ABCDEF,则该二叉树的前序遍历 序列为___,中序遍历序列为___,后序遍历序列为___。 6. 设一棵完全二...
数据结构中用到的 C语言基本知识
数据结构中用到的 C语言基本知识_计算机软件及应用_IT/计算机_专业资料。数据结构中用到的 C语言基本知识 《数据结构》中必要的 C 语言基本知识有必要将数据结构...
数据结构选择题
(B) 3,2,5,8,6 (D) 2,3,6,5,8 (A) 2,3,5,8,6 (C) 3,2,5,6,8 1.设某数据结构的二元组形式表示为 A=(D,R),D={01,02,03,04,05,...
《数据结构》期末考试试题及答案
数据结构》期末考试试题及答案 (2003-2004 学年第 2 学期) 贵州大学理学院数学系信息与计算科学专业 一、 单项选择题 1.对于一个算法,当输入非法数据时,也...
更多相关标签: