算法与数据结构综合应用——典型竞赛试题分析.pdf

《算法与数据结构综合应用——典型竞赛试题分析.pdf》由会员分享，可在线阅读，更多相关《算法与数据结构综合应用——典型竞赛试题分析.pdf（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法与数据结构综合应用-典型竞赛试题分析一、数值计算问题：1、打印所有的水仙花数，所谓水仙花数是指一个三位数，其各位数字立方和等于该数字本身，例2、一个数如果恰好等于它的因子之和，这个数就称为完数。例如：6的因子为1、2、3，而6123，因此6是完数。编程序找出1000以内的所有完数。3、有一分数序列：求出这个数列的前20项的和。（32.660259）4、求之值，其中a是一个数字。例如：（当n=5时），n由键盘输入。5、已知四位数3025有一个待殊性质:它的前两位数字30和后两位数字25的和是55,而55的平方刚好等于该数(552=3025)。试编一程序打印具有这种性质的所有四位数。分析：从3

2、2至99之间的数的平方是四位数，满足题目条件的数必须在这些四位数之内选择。分别把它们按前两位数后两位数进行分离,验证分离后的两个两位数之和的平方是否等于分离前的那个四位数,若等于即打印输出,否则放弃。6、求两个自然数，其和是667，最小公倍数与最大公约数之比是120：1。（例如：115，552）迭代法例题：用二分法求方程在区间（0,3）之间的一个解。算法提示：二分法是用计算机求解多项式方程的一中常用方法。基本思想是：,如果和的符号相反，那么在(x1,x2)之间一定存在一个数使f(x)=0即方程的一个解。取x1,x2的中点r，如果f(r)与f(x1)异号，解肯定在(x1,r)之间，否则解在(r,

3、x2)之间，重复直到|f(r)|e0，e0是一个很小的数，通过这种方法能够求出，方程f(x)=0的一个近似解r，误差在e0内。穷举搜索法穷举法也叫枚举法,它的基本思想是依题目的部分条件确定答案的大致范围,在此范围内对所有可能的情况逐一验证,直到全部情况验证完。若某个情况经验证符合题目的全部条件,则为本题的一个答案。若全部情况经验证后都不符合题目的全部条件,则本题无答案。用穷举法解题时，答案所在的范围总是要求是有限的，怎样才能使我们不重复的、一个不漏、一个不增的逐个列举答案所在范围的所有情况，就是本节所讲的列举方法。列举方法按答案的数据类型,常用的有下面三种。顺序列举：顺序列举是指答案范围内的各

4、种情况很容易与自然数对应甚至就是自然数,可以按自然数的变化顺序去列举。排列列举：有时答案的数据形式是一组数的排列,列举出所有答案所在范围内的排列,称为排列列举。组合列举：（参考组合数学知识）当答案的数据形式为一些元素的组合时，往往需要用组合列举。从几个不同的元素中任取m(mn)个元素组成的一组，就叫做从n个元素取m个元素的一个组合。组合是无序的，如：123，132，321，312，213，231是同一个组合（但是6个不同的排列）。例题：【问题提出】找出n个自然数（1，2，3，4，.n）中r个数的组合。例如n=3,r=2，所有的组合为：12,13,23；n5，r3，所有的情况为：123，124，

5、125，134，135，145，234，235，245，345。【算法】当r3时用3重循环实现。for I=5 to1 for j=5 to1for k=5 to 1if Ij AND I!=k AND jK AND Ij AND jkprint I,j,k练习：1、求出具有下列两个性质的最小自然数n：（1）、n是个6位数（2）、若将n的各位数移到其余各位之前，所得的新数是n的4倍。递推法:例题：运动会连续开了n天，一共发了m枚奖章，第一天发1枚并剩下（m1）枚的1/7，第二天发2枚并剩下的1/7，以后每天按规律发放奖章，在最后一天即第n天发剩下的n枚奖章。问运动会一共开了多少天？一共发了几枚

6、奖章？贪心算法一、算法思想贪心法的基本思路：-从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。该算法存在问题：1.不能保证求得的最后解是最佳的；2.不能用来求最大或最小解问题；3.只能求满足某些约束条件的可行解的范围。实现该算法的过程：从问题的某一初始解出发；while 能朝给定总目标前进一步 do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；二、例题分析1、背包问题有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品：A B

7、C D E F G 重量：35 30 60 50 40 10 25 价值：10 40 30 50 35 40 30 分析：目标函数：pi最大约束条件是装入的物品总重量不超过背包容量：wi b)and(a=m)thenbeginknap:=false;exit;end;if knap(a+1,b-itema)thenbeginknap:=true;write(itema:8);exit;end;if not knap(a+1,b)then knap:=false;end;beginwriteln(Please input item weights:);for i:=1 to m doread(i

8、temi);writeln(Total weight:);readln(w);writeln;if not knap(1,w)then writeln(NO ANSWER!);readln;end.2、单源最短路径一个有向图G，它的每条边都有一个非负的权值ci,j，路径长度就是所经过的所有边的权值之和。对于源点需要找出从源点出发到达其他所有结点的最短路径。E.Dijkstra发明的贪婪算法可以解决最短路径问题。算法的主要思想是：分步求出最短路径，每一步产生一个到达新目的顶点的最短路径。下一步所能达到的目的顶点通过如下贪婪准则选取：在未产生最短路径的顶点中，选择路径最短的目的顶点。设置顶点集合S

9、并不断作贪心选择来扩充这个集合。当且仅当顶点到该顶点的最短路径已知时该顶点属于集合S。初始时S中只含源。设u为G中一顶点，我们把从源点到u且中间仅经过集合S中的顶点的路称为从源到u特殊路径，并把这个特殊路径记录下来（例如程序中的disti，j）。每次从V-S选出具有最短特殊路径长度的顶点u，将u添加到S中，同时对特殊路径长度进行必要的修改。一旦V=S，就得到从源到其他所有顶点的最短路径，也就得到问题的解。3、机器调度现有N项任务和无限多台机器。任务可以在机器上处理。每件任务开始时间和完成时间有下表：任务-a-b-c-d-e-f-g开始(si)-0-3-4-9-7-1-6完成(fi)-2-7-7

10、-11-10-5-8在可行分配中每台机器在任何时刻最多处理一个任务。最优分配是指使用的机器最少的可行分配方案。请就本题给出的条件，求出最优分配。三、练习题：已知5个城市之间有班机传递邮件，目的是为了寻找一条耗油量较少的飞行路线。5个城市的联系网络如图所示。图中编号的结点表示城市，两个城市之间的连线上的值表示班机沿该航线已行的耗油量，并假定从城市i到j和城市j到i之间的耗油量是相同的。分析：1.运用贪心思想：在每一步前进的选择上，选取相对当前城市耗油量最小的航线；2.图解：若从1出发，有图：总耗油量=14 1-2-5-3-4-1但若路线改为：1-5-3-4-2-1，则总耗油量=13所以，这样的贪

11、心法并不能得出最佳解。3.改善方案：从所有城市出发的信心过程，求最优的。编程：1.数据结构：城市联系网络图的描述(图的邻接矩阵的描述)：constc=array1.5,1.5 of integer=(0,1,2,7,5),(1,0,4,4,3),(2,4,0,1,2),(7,4,1,0,3);2.贪心过程：begin初始化所有城市的算途径标志；设置出发城市V；for i:=1 to n-1 do n-1个城市begins:=从V至所有未曾到过的城市的边集中耗油量最少的那个城市；累加耗油量；V:=s；设V城市的访问标志；end;最后一个城市返回第一个城市，累加耗油量；end;3.主过程：实现改善

12、方案beginfor i:=1 to n dobegincost1:=maxint;初始化调用贪心过程，返回本次搜索耗油量cost；if cost1且B/A=BA，则C=B/A若A1，则C=B,打印1/C转步骤（2）。QBASIC程序清单：CLSDOINPUT a,b=;a,bLOOP UNTIL a 1 THEN PRINT+;LOOP WHILE a 1PRINT+1;bEND数的划分的研究问题描述求把一个整数n无序划分成k份互不相同的正整数之和的方法总数。分析我们其实可以将这题转化一下.因为我们知道我们在划分时只要按不下降排列就不会有重复.并且每一份都不为0.我们可以形象的把n的k-自然

13、数剖分看作把n块积木堆成k列，且每列的积木个数依次递增，也就是这n块积木被从左到右积木被堆成了楼梯状。比如，下图是10的几种4-剖分。现在，我们不妨把这三个图顺时针旋转90度，成为：对于这道题我们很容易可以想到一种状态表示方法,即用F(I,J,K)来表示把J无序划分成I份其中最大为K的划分方案数.那么,它就等于把J-K无序划分成I-1份,其中最大不超过K的划分方案数，状态转移方程就是对应的pascal程序如下:procedure dp;var i,j,k,l:integer;beginassign(output,outputfile);rewrite(output);f0,0,0:=1;for

14、 i:=1 to m dofor j:=i to n dofor k:=1 to j dofor l:=0 to k doinc(fi,j,k,fi-1,j-k,l);for i:=1 to n do inc(count,fm,n,i);writeln(count);close(output);end;但是如果我们再把上图逆时针翻转90度，那么其实也就等于先在最下一行各摆上一块积木接下来也就是把I-J块积木放上去,并要保持楼梯状.我们可以发现其实上就是把I-J无序拆分成1K份。那么我们可以得到如下动态转移方程procedure dp;var i,j,k:integer;beginf0,0:=1

15、;for i:=1 to n dofor j:=1 to m doif j=j then fi,j:=fi-j,j+fi-1,j-1;assign(output,outputfile);rewrite(output);writeln(fn,m);close(output);end;其实对于这题我们还可以继续优化,例如用滚动数组的方法使存处空间减少,这里就不再累赘了.这里还想介绍一种更容易的做法.若用F(I,J)表示把I无序划分成J份的方案数,则F(5,2)=(1,4,2,3);F(6,3)=(1,1,4,1,2,3,2,2,2)你一定会发现如果把I无序划分为J份,那么它的前几个划分一定等于把I

16、-1无序划分成J-1份每份前面加1的方案数.那么后面那一部拆分方案又会等于什么呢?我们不妨将后面每一份中的每一个数减1,我们会发现它与F(I-J,J)是一一对应的.证明如下我们将一个自然数I划分为K份，为了避免重复，习惯于从小到大地划分。我们将数I分为K份的方法数记作F（I，K），可知：F（I，K）=F（I-K，K）+F（I-1，K-1）证明：设集合A为I的所有划分方案的第一项，0A=（I DIV K），设每一种划分方案的以后K-1个数为A+D1，A+D2，A+D3.A+Dk-1，DiDi+1，于是：D的不下降排列数即I的首项是A的不同划分数。同理，设B为I-K的划分方案的首项集合，以后的K-

17、1个数是B+C1，B+C2.B+Ck-1，所以，C的不下降排列数就是I-K的首项是B的不同划分数，又因为：可知当A-1=B 时，方案数相同，其中A能从2取到（I div k），而B1，(I-k)div k即B1,(I div k)-1,所以，当A2，I div k时，方案总数是F（I-K，K）。又因为当A=1时，方案数是F（I-1，K-1），所以：F（I，K）=F（I-K，K）+F（I-1，K-1）成立。由此我们也可以推出与上面第三个程序一样的状态转移方程.分治策略一、算法思想任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题规模越小，解题所需的计算时间往往也越少，从而也越容易计

18、算。想解决一个较大的问题，有时是相当困难的。分治法的思想就是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。找出各部分的解，然后把各部分的解组合成整个问题的解。1、解决算法实现的同时，需要估算算法实现所需时间。分治算法时间是这样确定的：解决子问题所需的工作总量（由子问题的个数、解决每个子问题的工作量 决定）合并所有子问题所需的工作量2、分治法是把任意大小问题尽可能地等分成两个子问题的递归算法3、分治的具体过程:begin 开始if 问题不可分 then 返回问题

19、解 else begin从原问题中划出含一半运算对象的子问题1；递归调用分治法过程，求出解1；从原问题中划出含另一半运算对象的子问题2；递归调用分治法过程，求出解2；将解1、解2组合成整修问题的解；end;end;结束二、例题分析1、金块问题老板有一袋金块(共n块，n是2的幂（n=2）)，将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。分析:问题可以简化为：在含n（n是2的幂（n=2）个元素的集合中寻找极大元和极小元。明显的方法是逐个的进行比较查找。(一次冒泡排序)m:=a1

20、;for i:=2 to n do if m ai then m:=ai;(或者一次选择排序)p:=1;for i:=2 to n doif apb then maxnum:=a else maxnum:=b;end;分析比较次数：比较运算均在函数maxnum和minnum中进行，当n=2时，比较次数T(n)=1当n2时，比较次数T(n)=2T(n/2)+2n是2的k次幂。设n=2k2、快速排序快速排序是基于分治策略的一个排序算法。按照分治法的思想分析快速排序：（1）分解(Divide)以元素ap为基准元素将ap：q-1划分为三段ap：q-1，aq和aq+1：r，使得ap：q-1中任何一个元素

21、都小于aq，aq+1：r中任何一个元素大于等于aq，下标q在划分中确定。（2）递归求解(Conquer)通过递归调用快速排序算法分别对ap:q-1 和aq+1:r进行排序。（3）合并(Merge)由于ap:q-1 和aq+1:r的排序都是在原位置进行的，所以不必进行任何合并操作就已经排好序了。在上面三个步骤中，第一步：分解是关键。一次快速排序确定划分元素的位置，具体参见排序算法-快速排序3、归并排序归并排序也是基于分治策略的另一个算法。归并的思路是把两个已经排好序的数组合并为一个。(源程序)路归并排序示例：初始值EYUKSLB一趟归并排序E YK UL SB两趟归并排序E K U YB L S

22、三趟归并排序B E K L S U Y习题:对数字49 38 40 97 76 13 27进行归并排序procedure mergesort(var r,r1:listtype;s,t:integer);r,r1：均为链表，存储排序数据；过程mergesort(r,r1,s,t)完成把链表r中的关键字进行归并排序、并存放到链表r1中，其中s是下界t是上界过程merge(r2,s,m,t,r1)把链表r2中排好序的子链r2s.m和子链r2m+1.t合并到r1中 if 问题不可分 then求解else（1）分出问题的一个子问题1，并求解子问题1（2）分出问题的一个子问题2，求解子问题2（3）合并子

23、问题1和子问题2if s=t thenr1s:=rselsemergesort(r,r2,s,(s+t)div 2);mergesort(r,r2,(s+t)div 2,t);merge(r2,s,(s+t)div 2,t,r1);4、循环赛问题（1999年广东省青少年信息学奥林匹克竞赛 第三题：棒球联赛）问题描述：广州市体委将举行一次由N支队伍（队伍编号为1.N）参加的少年棒球联赛。联赛总共不能多于N轮（同一时间内若干支队进行一次比赛为一轮），并且每两支队之间必须而且仅必须进行一次比赛。请编程为这次比赛设计一个赛程表。循环赛问题可以用分治法解决。下面是先假定n=2k procedure ta

24、ble(k:integer;a:array1.u1,1.u2 of integer);var n,i,j,m,s,t:integer;beginn:=1;for i:=1 to k do n:=n*2;for i:=1 to n do a1,i:=i;m:=1;for s:=1 to k dobeginn:=n/2;for t:=1 to n do for i:=m+1 to 2*m do for j:=m+1 to 2*m dobeginai,j+(t-1)*m*2:=ai-m,j+(t-1)*m*2-m;ai,j+(t-1)*m*2-m:=ai-m,j+(t-1)*m*2;end;m:=m

25、*2;end;for s end;三、练习题二分检索假定在A1.9中顺序存放这九个数：-7,-2,0,5,16,43,57,102,291 要求检索291,16,101是否在数组中。给定已排好序的n个元素A1,A2,A3,.，An,找出元素x是否在A中，如果x在A中，指出它在A中的位置。模拟随机函数及其应用：解决有些问题需要有一个产生随机数的函数。如果你使用的机器的Pascal未提供产生随机数的标准函数，这里就向你介绍一个实现这个要求的函数，并举若干应用例子。假定问题要在整区间ab集合中随机的选取一个整数r。如12上表示掷一枚硬币的正面或反面的结果；16上表示投一粒骰子的面值等。连续掷币，或连

26、续投骰子得到的结果序列：r1，r2，.称为随机序列。程序不能严格地产生ab上的随机序列，但能用数学方法产生满足应用上所要求的近似随机序列的随机数，通常称为伪随机数。程序产生伪随机数的最通常的方法是线性同余法。下面函数randomint就是这一方法编制的产生ab上伪随机数的函数。FUNCTION randomint(a,b:integer):integer;产生区间ab上的一个整数，使用并改变整体变量seedCONSTmaxseed=65536;=216multiplier=25173;adder=13849;BEGINseed:=(multiplier*seed+adder)MOD maxse

27、ed;randomint:=a+seed*(b-a+1)DIV maxseedEND;函数randomint通过保留一个整体变量seed而产生伪随机数。变量seed由主程序提供初值。为了产生一个伪随机数，应用线性同余法改变seed的值。seed 的取值范围0maxseed被分成(b-a+1)等分，每个等分内的值代表ab上的一个数。函数randomint不满足前面建议的函数不应改变整体量值这一规则。但是，为了满足每次调用randomint能得到一个不同的值，这又是必需的。例1：利用函数randomint编制的一个20以内整数加法教学程序。计算机随机产生两个整数，让学生回答。简单的算法分析：a.产

28、生第一个随机数x，x:=randomint(1,19)以保证两个数相加不超过20。b.产生第二个随机数y，y:=randomint(1,20-x)以保证两个数相加不超过20。【源程序:xoi00_13.pas】PROGRAM simpledrill(input,output);VARseed,i:integer;x,y,answer:integer;FUNCTION randomint(a,b:integer):integer;产生区间ab上的一个整数，使用并改变整体变量seedCONSTmaxseed=65536;multiplier=25173;adder=13849;beginseed:

29、=(multiplier*seed+adder)MOD maxseed;randomint:=a+seed*(b-a+1)DIV maxseedend;randomintbeginwriteln(Hello,I am a computer.);writeln(Today we are going to do addition problem.);seed:=1;for i:=1 to 10 dobeginx:=randomint(1,19);产生一个1-19的随机整数xy:=randomint(1,20-x);产生另一个随机整数y,并确保它与x之和小于等于20writeln(Please te

30、ll me,how much is,x:2,+,y:2,=?);write(Type the answer:);read(answer);if x+y=answer then 判断答案是否正确writeln(Correct.)elsewriteln(Thats not right.The answer is,x+y:2)endend.除了整随机数外，有时也需要（ab）区间上的实随机数。产生实伪随机数函数randomreal与函数randomint原理基本相同。FUNCTION randomreal(a,b:real):real;产生（ab）内的一个实数，使用并改变整体变量seed的值CONST

31、maxseed=65536;multiplier=25173;BEGINseed:=multiplier*seed MOD maxseed;randomreal:=a+seed*(b-a)/maxseedEND;例2：计算椭圆的面积。设椭圆方程为x2/32+y2/22=1算法思想：为了求一个不规则平面图S的面积，选取一个长方形C围住S。产生足够多的C中的随机点，则这些随机点同时落在S中的概率是 SA/CA，其中SA，CA分别是S和C的面积。如果有一个简单的标准能确定一个点是否在S内，就可通过产生随机点，计算落在S中的点数，估计S的面积。因为所给椭圆关于x轴和y轴对称，总面积是第一象限部分面积的

32、四倍。选取长方形C为0 x3,0y2,长方形C内的点（x,y）落在椭圆内的判别标准是x2/32+y2/22 1【xoi00_14.pas】PROGRAM area(input,output);VARtotal,inside,seed:integer;x,y:real;i:integer;FUNCTION randomreal(a,b:real):real;产生区间ab上的一个实数，使用并改变实型变量seedCONSTmaxseed=65536;multiplier=25173;beginseed:=multiplier*seed MOD maxseed;randomreal:=a+seed*(

33、b-a)/maxseedend;randomrealbeginread(total);读入要产生的随机点的数目inside:=0;seed:=1;for i:=1 to total dobeginx:=randomreal(0,3);y:=randomreal(0,2);if(x*x/9+y*y/4)30)and(time70)and(time100;在每次被调用时，函数AddCust就用Ran1或Random来产生到达付款处的顾客数目。AddQueue是依照Ran2的结果用来把顾客放到有服务的付款处排队，而且当每个付款处都客满时，它会再开放另一个付款处。Display会显示模拟的情形。Che

34、ck使用Ran2去设定每个顾客一个付款的次序，而且每次调用时，都会使计数器减一，直到计数器为0时，此顾客就离开了付款处了。变量time会改变产生顾客的速度，使得可以满足商店高峰时间的要求，循环每做完一次就表示过了一个小时的十分之一。你可以直接控制程序中的一些变量。首先，你可以更改顾客到达的方式和顾客到达的数目，你也能在快接近高峰时段或高峰时段快结束时，渐渐地增加或减少AddCust返回的顾客人数。此程序是假定顾客会随机的选择付款处，虽然有些人是这种情形，但是大部分人都会选择人较少的付款处，所以你可以把各付款处的人数记下来，然后更改AddQueue函数，改成有时把顾客放到人最少的付款处，而有时是

35、随机的选择付款处。这个程序没有考虑到一些突发状况。例如有人把酱油弄翻了，或是付款处有位叼钻的顾客，这两种情形都会使付款工作稍微停顿。关键路径：【源程序：xoi00_16.pas,演示程序：DEM00_07.zip】1.问题描述 下图是一个工程的AOE（Activity On Edge)网。图中N1至N10表示该工程由十项子工程组成。有向边a1至a14表示各子工程的活动情况，其权代表各项子工程持续的时间。对于AOE网，研究的问题是：(1)完成整个工程至少需要多少时间；(2)哪些活动是影响工程进度的关键。2.算法分析 完成工程的最少时间，是从开始点到完成点的最长路径长度（路径长度是这条路上的活动持

36、续时间之和），人们把路径长度最长的路径称为关键路径。分析关键路径的目的为辨别哪些是关键活动，以便提高关键活动的工效，缩短整个工程的期限。我们可以采用十字链表的结构来表示有向图AOE网。把每个子工程视为一个结点，并设置五个域，当作一个记录。其中TAIL和HEAD域分别表示有向边的尾顶点J和头顶点K，DUT表示活动的持续时间，HLINK链接以K为头的另一有向边，TLINK为链接以J为尾的另一有向边。则求关键路径的算法如下所示：(1)初始化十个结点。(2)从源点N1出发，令VE1=0，按拓扑有序求其余各顶点的最早发生时间VEi。如果得到的拓扑有序序列中顶点的个数小于10，则说明网中存在环，不能求关键

37、路径，算法终止；否则，执行步骤3。(3)从汇点N10出发，令VL10=VE10，按逆拓扑有序求其余各顶点的最迟发生时间VLi。(4)根据各顶点的VE和VL值，求每条弧R的最早发生时间ER和最迟发生时间LR。若某条弧满足条件ER=LR，则为关键活动。去掉网中的所有非关键路径，则变成下列有向图。在图中，由N1到N10的路径均为关键路径。此网中由N4至N9形成两条关键路径（N4，N5,N7,N9)和（N4，N5，N8和N9）。只有在这两条关键路径上同时提高活动速度，才能缩短工期。在非关键路径上提高工效的努力，对缩短完成整个工程的时间是毫无效果的。最优路线【源程序：xoi00_17.pas，演示程序：

38、DEM00_08.rar】1.问题描述 现有一个地铁网络，已知网络中各相邻结点间的票价（或距离），需要找出：(1)由一个指定的起点站到一个指定的终点站的费用最小（距离最短）的路线。(2)由一个指定的起点站到一切终点站的费用最小（距离最短）的路线。2.算法分析 我们可以把地铁网络看作一个有向图，因而图的处理算法可能是有用的。EWDijkstra设计了一个著名的算法，该算法能算出从一个起点站到所有终点站，并满足某些约束条件的最小费用的路线。在介绍这个算法之前，先给出术语固定的。它表示总费用额已不能再减少，因而保留不变。Dijkstra算法大体可叙述如下：begin第一步：对起点站，置其总费用为0，

39、固定这个费用；第二步：对其它所有的车站的总费用赋初值：若该站与起点站直接相连，则置总费用为此路程的费用（注意：尚未固定），否则置总费用为maxint；第三步：while 还有终点站的总费用未固定 do begin选择一个车站，它的费用最小，而且还未被固定，把这个车站记为w；固定w的总费用；检查可以由w直接到达的所有车站。若由起点站经w（由起点站到w的最小费用已被固定）到这些可直接到达的车站，其得出的总费用低于该车站迄今最优的总费用，则按此调整该站的总费用。endwhileend.下图是一个地铁网络（由于往返费用相同，我们把它画成无向图），每个车站可看成一个结点，共有九个结点。结点间的弧上标出有关车站之间的费用。对于每个车站结点，应该用一个记录来描述。它有下列诸域：名字，费用已固定，总费用，表示最优路线的指向结点的指针等四个域。由于开始顺序检查所有的结点时，结点个数未知，因此，我们把结点组成一个链表，所以车站结点中应有一个指向其它（rest）结点的指针。对于不同的车站结点，与之直接相连的结点数目相差很大，为了缩小存储空间并为了顺序访问这些结点，每个车站节点还应设置一个指针（next），用它来把与该结点直接相连的一串结点链接起来。准备工作完成后，可以参照算法写出程序。