第二章 线性表
一、线性结构的特点：
在数据元素的非空有限集中，1）存在唯一的一个被称做“第一个”的数据元素；2）存在唯一的一个被称做“最后一个”的数据元素；3）除第一个之外，集合中的每个数据元素均只有一个前驱；4）除最后一个之外，集合中每个数据元素均只有一个后继。
二、线性表的定义
线性表是最常用且最简单的一种数据结构。
一个线性表是n个数据元素的有限序列。
数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。
线性表例：
1、
1 2 3 4 5 6 7
2、
3、
学号 姓名 语文 数学 C语言
6201001 张三 85 54 92
6201002 李四 92 84 64
6201003 王五 87 74 73
6201004
...
数据元素也可由若干个数据项组成（如上例3）。这时常把数据元素称为记录。含有大量记录的线性表又称文件。
线性表中的数据元素类型多种多样，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。
a1 ... ai-1 ai ai+1 ... an
ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。
线性表中元素的个数n定义为线性表的长度，为0时称为空表。在非空表中的每个数据元素都有一个确定的位置。ai是第i个元素，把i称为数据元素ai在线性中的位序。
三、线性表的顺序存储结构
线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。因为内存中的地址空间是线性的，因此，用物理上的相邻实现数据元素之间的逻辑相邻关系是既简单，又自然的。如图 2.1 所示。设 a１的存储地址为Loc(a１)，每个数据元素占d个存储地址，则第i个数据元素的地址为：
Loc(ai)=Loc(a１)+(i-1)*d 1<=i<=n
这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点。
在程序设计语言中，一维数组在内存中占用的存储空间就是一组连续的存储区域，因此，用一维数组来表示顺序表的数据存储区域是再合适不过的。考虑到线性表的运算有插入、删除等运算，即表长是可变的，因此，数组的容量需设计的足够大，设用：data[MAXSIZE]来表示，其中MAXSIZE是一个根据实际问题定义的足够大的整数，线性表中的数据从 data[0] 开始依次顺序存放，但当前线性表中的实际元素个数可能未达到MAXSIZE多个，因此需用一个变量 last 记录当前线性表中最后一个元素在数组中的位置，即 last 起一个指针的作用，始终指向线性表中最后一个元素，因此，表空时last=-1。这种存储思想的具体描述可以是多样的。如可以是：
datatype data[MAXSIZE];
int last;
这样表示的顺序表如图2.1 所示。表长为 last+1，数据元素分别存放在data[0]到data[last]中。这样使用简单方便，但有时不便管理。
0 1 … i-1 i … n-1 ... MAXSIZE1-1
data a1 a2 … ai-1 ai ai+1 … an …
图2.1 线性表的顺序存储示意图
四、线性表的链式存储结构
由于顺序表的存贮特点是用物理上的相邻实现了逻辑上的相邻，它要求用连续的存储单元顺序存储线性表中各元素，因此，对顺序表插入、删除时需要通过移动数据元素来实现，影响了运行效率。本节介绍线性表链式存储结构，它不需要用地址连续的存储单元来实现，因为它不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过“链”建立起数据元素之间的逻辑关系来，因此对线性表的插入、删除不需要移动数据元素。
链表是通过一组任意的存储单元来存储线性表中的数据元素的，那么怎样表示出数据元素之间的线性关系呢？为建立起数据元素之间的线性关系，对每个数据元素ai，除了存放数据元素的自身的信息 ai 之外，还需要和ai一起存放其后继 ai+1 所在的存贮单元的地址，这两部分信息组成一个“结点”，结点的结构如图2.2 所示，每个元素都如此。存放数据元素信息的称为数据域，存放其后继地址的称为指针域。因此n个元素的线性表通过每个结点的指针域拉成了一个“链子”，称之为链表。因为每个结点中只有一个指向后继的指针，所以称其为单链表。
链表是由一个个结点构成的，结构如图2.2
last
图2.2 链表示意图
a1
an
∧
H
…
a2
PAGE
第4页第六章 图
图是比树更复杂的数据结构，树中结点之间具有明显的层次关系，图中任意两个结点之间都有可能存在一条连线（称为边）。
因此，图的应用极为广泛。如：电子线路分析、寻找最短路径、工程计划分析、统计力学、控制论等技术领域都把图结构作为解决问题的主要手段之一。
一、定义
1、图
图G由两个集合V和E组成。V是一个有限的非空的顶点集合，E是边的集合。图6.1中G1、G2、G3就是三个图。
图6.1
图G1、G2中代表边的顶点偶数对是无序的，则称图G1、G2为无向图，边(Vi，Vj) 和(Vj，Vi)代表的是同一条边。
图G3中代表边的顶点偶数对是有序的，则称图G3为有向图，有向图中的边又称为弧。弧(Vi，Vj)表示从顶点i指向顶点j，顶点Vi称为弧(Vi，Vj)的尾，Vj称为弧(Vi，Vj) 的头。故有向图中(Vi，Vj)和(Vj，Vi)代表着两条不同的弧。
在一个有ｎ个顶点的无向图中，若每一个顶点和其它（ｎ-1）个顶点之间都有边相连，则共有ｎ(ｎ－1)/2条边。这是任何ｎ个顶点的无向图的最大边数。一个拥有ｎ(ｎ－1)/2条边的ｎ个顶点的无向图称为无向完全图。如图6.1中的G1是有4 个顶点的无向完全图。类似地在有ｎ个顶点的有向图中，最多可能有ｎ（ｎ－１）条弧， 具有ｎ（ｎ－１）条弧的ｎ个顶点的有向图称为有向完全图。
在一些实际应用问题中，图的边往往与具有一定意义的数相关，这种与图的边相关的数叫权，这个权，可以表示从一个顶点到另一个顶点的距离或花费的代价等等。 我们称边拥有权的图为网。
2、邻接
若(V1，V2)是E(G)中的一条边，则称顶点V1和V2为相邻接的顶点，而称边(V1，V2)是依附于顶点V1和V2的边。
例如，在图6.1的G2中，与V2顶点相邻接的顶点是V1、V4和V5。若(V1，V2)是有向图G中的一条弧，则称顶点V1邻接至顶点V2，顶点V2邻接至顶点V1，弧(V1，V2) 依附于顶点V1和V2。
3、度
依附于顶点的边的数目称为该顶点的度。有向图中，把以顶点V 为头的弧的数目称作顶点V的入度，而把以V为尾的弧的数目称之为顶点V的出度，顶点V的出度与入度之和就是它的度。
4、路径
在图G中，从顶点Vp到顶点Vq的路径是顶点序列(Vp，Vi1，Vi2，......，Vin，Vq)，且( Vp，Vi1)，(Vi1，Vi2)，......，(Vin，Vq)是E(G)中的边。
若G是有向图，则路径也是有向的，由弧(Vp，Vi1)，(Vi1，Vi2)，......，(Vin， Vq)组成。路径上的边数称为路径长度。在一条路径中，如果除了第一个顶点和最后一个顶点外，其余顶点都各不相同，则称这样的路径为简单路径。
例如，在图6.1中，由边(V1，V2)，(V2，V4)，(V4，V3)构成从顶点V1到顶点V3的路径可以写成顶点序列(V1，V2，V4，V3)。路径(V1，V2，V4，V3)和(V1，V2，V4，V2)都是长度为3的路径，显然，前者是一条简单的路径，而后者则不是。 我们把第一个顶点和最后一个顶点相同的路径称为回路，若一个简单路径的第一个顶点和最后一个顶点相同，则称为简单回路。
二、图的存储结构
表示图的存储结构有多种形式，我们只介绍其中常用的两种，即邻接矩阵表示法和邻接表表示法。
1、邻接矩阵表示法
若某图G有ｎ个顶点V1，V2，......，Vn，则其邻接矩阵是这样的一个ｎ阶方阵：
1 (顶点Vi，Vj有相连)
A(i，j)＝{
0 (顶点Vi，Vj不相连)
显然，无向图的邻接矩阵是对称的，因此，在赋值时只要对上三角矩阵(或下三角矩阵)赋值即可。而有向图的邻接矩阵不一定是对称的。
对于网的邻接矩阵可定义为：
Wij (顶点Vi，Vj有相连时的权值)
A(i，j)＝{
0 (顶点Vi，Vj不相连)
采用邻接矩阵的方法来表示一个图，我们可以很容易地判定任意两个顶点之间是否有边相连，并容易求得各个顶点的度，但是所耗费的存储空间是十分大的--需要ｎ×ｎ个存储单元。当一个图的顶点数较多而边数较少时，这时对应的邻接矩阵为稀疏矩阵，这种存储结构浪费了许多存储单元，在这种情况下，也可采取图的另一种表示方法--邻接表表示法。
2、邻接表表示法
这种表示法是为图中的每一个顶点Vi建立一个链表，即把邻接矩阵中的ｎ行表示成ｎ个链表。对于无向图，第i个链表是把图中与顶点Vi相邻接的所有顶点链接在一起， 链表中的每个结点表示一条依附于顶点Vi的边（见图6.2(ａ)）。而有向图的第i 个链表是把邻接自顶点Vi的所有顶点链接在一起，链表中的每个结点表示一条以顶点Vi为尾的弧（见图6.2(ｂ)）。链表的结构为，每个结点有两个域：
顶点域--用来表示与顶点Vi相邻接的顶点序号；
指针域--用来指向依附于顶点Vi的另一条边或弧。
对于网，结点中还需增加一个存放权值的域，每个链表都有一个起始结点，为处理方便，我们把邻结表的所有链表的头指针集中存放在一个数组中，这样就可以方便地随机访问图中每个结点的链表。
图 6.2 图的邻接表表示法
对于一个有ｎ个顶点和ｍ条边的无向图，若采用这种存储表示法，需要ｎ个头结点和２ｍ个表结点，每个表结点有两个域（对于网则有三个）显然，在边稀疏的情况下，采用邻接表比邻接矩阵要省空间。
例题6_1、 有如图所示的七巧板，试编写一源程序如下，使用至多四种不同颜色对七巧板进行涂色(每块涂一种颜色)，要求相邻区域的颜色互不相同，打印输出所有可能有
涂色方案。
分析:本题实际上就是著名的"地图四色"问题。无论地图多么复杂，只需用四种颜色就可以将相邻的区域分开。
图
为了解题方便，我们可以把七巧板上每一个区域看成一个顶点，若两个区域相邻，则相应的顶点间用一条边相连，这样，该问题就转化为图的问题了。
算法步骤:
按顺序分别对１号、２号、......、７号区域进行试探性涂色，用１、２、３、４号代表４种颜色。数据采用邻接矩阵。
⒈对某一区域涂上与其相邻区域不同的颜色。
⒉若使用４种颜色进行涂色均不能满足要求，则回溯一步，更改前一区域的颜色。
⒊转步骤１继续涂色，直到全部结束为止，输出。
源程序如下: (例程见exm_6_1.pas)
program exm6_1 (input,output,fdat);
const
max=10;
type
gradat=array[1..max,1..max] of byte;
var
data:gradat;
n:byte;
color:array[1..max] of byte;
total:integer;
procedure getdata;{输入数据}
var
name:string[12];
fdat:text;
i,j:byte;
begin
write('use which file ');
readln(name);
assign(fdat,name);
reset(fdat);
read(fdat,n);
for i:=1 to n do
for j:=1 to n do
read(fdat,data[i,j]);
for i:=1 to n do
begin
for j:=1 to n do write(data[i,j]:5);
writeln;
end;
writeln;
end;
function colorsame(s:byte):boolean;{判断相邻点是否同色}
var
i:byte;
begin
colorsame:=false;
for i:=1 to s-1 do
if (data[i,s]=1) and (color[i]=color[s]) then colorsame:=true;
end;
procedure print;{输出}
var
i:byte;
begin
for i:=1 to n do write(color[i]:2);
inc(total);
writeln(' con:',total);
end;
procedure try(s:byte);{递归搜索}
var
i:byte;
begin
if s>7 then print
else
begin
i:=0;
repeat
inc(i);
color[s]:=i;
if not(colorsame(s)) then try(s+1);
until i=4
end;
end;
begin {主源程序如下}
getdata;
total:=0;
try(1);
writeln('Total=',total);
readln;
end.
fdat文件内容:
7
0 1 0 0 1 0 1
1 0 0 1 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 1 1
1 0 0 0 0 0 1
0 1 1 1 0 0 0
1 0 1 1 1 0 0
0
例题6_2、如图所示，从A到B有好几条可供选择的路线， 每条路线的长度均标示在图上，问选择什么样的路线，可使从A到B所走的路径最短？
图
分析：在一个有向图G=(V,E)中，给定一个始点V1和终点Vp，对每条弧(Vi,Vj) 相应地有一个权W(i,j)，最短路问题就是要求从始点V1到终点Vp的一条路径，使其在所有从V1到Vp的路径中，它是总权最小的一条。
当所有的W(i,j)>=0时，解决最短路径问题的比较好的方法是Dijkstra方法。 它是荷兰计算机科学家（E.W.Dijkstra）于1959年提出的。这个方法不仅求出了从A到顶点B的最短路径，而且求出了从A到各顶点的最短路径。
算法步骤：
从V1开始，给每一个顶点赋予一个标号，标号分为两种：
(1)T标号--V1到该顶点的最短路径的上界（临时标号）；
(2)P标号--V1到该顶点的最短路径（固定标号）。
若某一顶点已得到P标号，则表明已求出V1到该点的最路径，凡未得到P标号的顶点，一律标上T标号。
算法的每一步把某一顶点的T标号改变为P标号，最多经过（ｎ－１）步（ｎ为顶点个数），即可得到从V1到每一个顶点的最短路径。
⒈在初始状态下，令P(V1)=0，T(Vi)=+∞（ｉ＝1，2，3，......，ｎ）， 反复执行下面两个步骤；
⒉设Vi是已经得到P标号的点，考虑所有满足下列条件的顶点Vi的集合B:
B＝{ Vj|(Vi,Vj) E且Vj是T标号}
将集合B中的每一个顶点Vj的T标号修改为:
min{T(Vj),P(Vi)+W(i,j)}
⒊若G中已没有T标号的顶点，则结束，否则，将集合B中最小者的T标号改变为P 标号，然后转到２。
下面，以求Ｖ1到Ｖ7的最短路径为例，说明Dijkstra方法：
开始，令P(V1)＝0，T(Vj)＝＋∞（j=1,2,3,...,7）
第一步：考虑所有与V1相联且标有T标号的点的集合：
B={V2,V3,V4}；修改集合B中元素的T标号
T(V2)=min{T(V2)，P(V1)+W(1,2)}=min{+∞，2}=2
T(V3)=min{T(V3)，P(V1)+W(1,3)}=min{+∞，5}=5
T(V4)=min{T(V4)，P(V1)+W(1,4)}=min{+∞，3}=3
将其中最小者改为标号：P(2)=2
第二步：考虑所有与V1，V2相联且标有T标号的点集合：
B={V3，V4，V6}；修改集合B中元素的T标号
T(V3)=min{T(V3)，P(2)+W(2,3)}=min{5,4}=4
T(V4)=3 (同前面求法)
T(V6)=min{T(V6)，P(2)+W(2,6)}=min{+∞，9}=9
将其中最小者改变为P标号，P(V4)=3
第三步：考虑所有与V1,V2,V4相联且标有T标号的点的集合：
B={V3，V5，V6}；修改集合B中元素的T标号
T(V3)=4
T(V5)=min{T(V5)，P(V4)+W(4,5)}=min{+∞，8}=8
T(V6)=9
将其中最小者改变为P标号：P(V3)=4
第四步：考虑所有与V1，V2，V3，V4相联且标有T标号的点的集合：
B={V5，V6}；修改集合B中的元素的T标号
T(V5)=min{T(V5)，P(V3)+W(3,5)}=min{8，7}=7
T(V6)=min{T(V6)，P(V3)+W(3,6)}=min{9，9}=9
将其中最小者改变为P标号：P(V5)=7
第五步：考虑所有与V1，V2，V3，V4，V5相联且标有T标号的点的集合：
B={V6，V7}；修改集合B中的元素的T标号
T(V6)=min{T(V6)，P(V5)+W(5,6)}=min{9，8}=8
T(V7)=min{T(V7)，P(V5)+W(5,7)}=min{+∞，14}=14
将其中最小者改变为T标号：P(V6)=8
第六步：考虑所有与V1，V2，V3，V4，V5，V6相联且标有T标号的点的集合：
B={V7}；修改集合中B元素的T标号
T(V7)=min{T(V7)，P(V6)+W(6,7)}=min{14，13}=13
将其中最小者改变为P标号：P(V7)=13
至此，所有顶点的Ｔ标号均已改变为Ｐ标号了，说明Ｖ１到各顶点的最短路径已全部找到。
源程序如下：(例程见exm_6_2.pas)
program exm6_2;
const
max=10;
type
gradat=array[1..max,1..max] of real;
way=set of 1..max;
var
a,b:byte;
n:byte;
data:gradat;
path,path1:array[1..max] of byte;
least:real;
k:byte;
procedure getdata;{输入数据}
var
name:string[12];
fdat:text;
i,j:byte;
begin
write('use which file ');
readln(name);
assign(fdat,name);
reset(fdat);
read(fdat,n);
for i:=1 to n do
for j:=1 to n do
read(fdat,data[i,j]);
for i:=1 to n do
begin
for j:=1 to n do write(data[i,j]:5);
writeln;
end;
writeln;
end;
procedure print;{输出}
var
i:byte;
begin
i:=1;
write('Path is:',a:2);
while path[i]<>0 do
begin
write(path[i]:2);
inc(i);
end;
writeln;
writeln('Longth=',least);
end;
procedure lookfor(d:integer;s:real;k:integer;already:way);{求最短路径}
var
j:byte;
begin;
for j:=1 to n do
if (data[d,j]<>0) and not(j in already) then
begin
path1[k]:=j;
if (j=b) and (s+data[d,j]
begin
path:=path1;
least:=s+data[d,j];
path[k+1]:=0;
end
else lookfor(j,s+data[d,j],k+1,already+[j]);
end;
end;
begin
getdata;
write('From which>');
readln(a);
write(' To which>');
readln(b);
least:=1e+36;
lookfor(a,0,1,[a]);
print;
readln;
end.
fdat文件数据:
7
0 2 5 3 0 0 0
0 0 2 0 0 7 0
0 0 0 1 3 5 0
0 0 0 0 5 0 0
0 0 0 0 0 1 7
0 0 0 0 0 0 5
0 0 0 0 0 0 0
练习三、如图所示的网络代表6个城市间的交通网，边上权是公路的造价，现在要用公路把6个城市联系起来，这要修筑5条公路，如何设计使得这5 条公路总的造价最小。
图
PAGE
第28页数据结构基础
第一章 数据结构概要
一、什么是数据结构：（data structure）
一般来说，用计算机解决一个具体问题是，大致需要经过下列几个步骤：
1）从具体问题抽象出一个适当的数学模型；
2）设计一个解此数学模型的算法
3）编出程序
4）测试，调整，解答。
寻求数学模型的实质就是分析问题，从中提取操作的对象，并找出这些操作对象之间的关系，然后用数学的语言加以描述。
数据结构也就是非数值计算的问题的数学描述，因此研究数据结构的过程也就是数学建模的过程。
二、基本概念和术语
数据（data）输入到计算机中符号的总称。
数据元素（data element）
数据项（data item）
数据对象（data object）数据元素的集合，是数据的一个子集。
数据结构（data structure）是相互之间存在的一种或多种特定关系的元素的集合。
数据类型（data type）高级语言中的数据类型一般有三类：
1）简单类型：包括整型、实型和字符型数据；
2）构造类型：是由已知类型按一定规则构造而成。如数组。
3）指针类型：在构造时使用一种特殊的变量――指针，
主要用于构造诸如链表、树、有向图等各种复杂的数据结构。
元素之间的相互关系称之为结构（structure）系统论认为：世界中的一切事物都表现为系统，系统是由相互联系，相互制约的若干部分结合而成的，具有一定结构和功能的有机整体，它具有三个特点：
1）集合性 （元素）
2）关联性 （结构）
3）目的性 （功能）
由此可以看出，用计算机来解决某一实际问题，这一问题我们就可以把它看作一个系统来研究，数据结构的任务就是来研究每一个元素之间的结构关系。理顺数据元素之间的关系。数据结构就是元素与关系的集合。
数据结构的四种基本类型：
1）集合结构
2）线性结构
3）树形结构
4）图状结构（或网状结构）
数据结构的数学定义：
数据结构是一个二元组
data_structure = (D,S)
其中：D是数据元素的有限集
S是D上关系的有限集
与数据结构密切相关的是定义在数据结构上的一组操作，操作的种类和数目不同即使逻辑结构相同，这个数据结构的用途也会大为不同。
基本的操作主要有：
1）插入
2）删除
3）更新
4）查找
5）排序
从操作特性来分：
加工型操作(constructor)
引用型操作（selector） （查找）
算法（algorithm）
是对特定问题求解步骤的一种描述，它是指令的有限序列。
1）有穷性
2）确定性
3）可行性
4）输入
5）输出
三、数据结构（data structure）的发展
1968年美国唐.欧.克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一次较系统地阐述数据的逻辑结构和存储结构及其操作的著作。
PAGE
第2页第四章 栈和队列
栈和队列是两种重要的线性结构。
从数据结构角度看，栈和队也是线性表，其特殊性存于栈和队的基本操作是线性表操作的子集，它们是受限制的线性表。
一、栈（stack）
栈顶（top）
栈底（bottom）
空栈
栈又称为后进先出（last in first out）线性表。
关于栈的操作有：
1）inistack(s) 初始化操作，设定一个空栈要S。
2）empty(s)关栈空函数。空返回“true”。
3）push(s,x) 入栈操作。
4）pop(s) 出栈函数。
5）gettop(s) 取栈顶元素函数。
6）clear(s) 栈置空操作。
7）current_size(s) 求当前栈中元素个数函数。
栈的一个重要应用是在程序设计语言中实现递归过程。
递归算法作为计算机程序设计中的一种重要的算法，是较难理解的算法之一。简单地说，递归就是编写这样的一个特殊的过程，该过程体中有一个语句用于调用过程自身（称为递归调用）。递归过程由于实现了自我的嵌套执行，使这种过程的执行变得复杂起来，其执行的流程可以用图1所示。
图1 递归过程的执行流程
??从图1可以看出，递归过程的执行总是一个过程体未执行完， 就带着本次执行的结果又进入另一轮过程体的执行，……，如此反复，不断深入，直到某次过程的执行遇到终止递归调用的条件成立时，则不再深入，而执行本次的过程体余下的部分，然后又返回到上一次调用的过程体中，执行其余下的部分，……，如此反复，直到回到起始位置上，才最终结束整个递归过程的执行，得到相应的执行结果。递归过程的程序设计的核心就是参照这种执行流程，设计出一种适合"逐步深入，而后又逐步返回"的递归调用模型，以解决实际问题。
利用递归调用程序设计技术可以解决很复杂但规律性很强的问题，并且可以使程序变得十分简短。它经常出现在以下几个方面：
1）有很多数学函数是递归定义的。
如（1）阶乘函数 1 n=0
fact(n) = n*fact(n-1) n>0
（2）菲波拉契数列（Fibonacci） 0 n=0
fib(n) = 1 n=1
fib(n-1)+bib(n-2) 其它情形
（3）阿克曼函数（Ackerman） n+1 m=0
ack(m,n)= ack(m-1,1) n=0
ack(m-1,ack(m,n-1)) 其它情形
2）有的数据结构本身固有的递归特性。
如：二叉树 广义表等
3）还有一类问题，虽则问题本身没有明显的递归结构，但用递归求解比迭代求解更简单。
如：八皇后问题，汉诺塔（Hanoi）问题等。
例4_1 利用递归调用手段编程计算N!。
分析：根椐数学知识，1!=1，正整数N的阶乘为：N*(N-1)*(N-2)*…*2*1， 该阶乘序列可转换为求N*(N-1)!，而(N-1)!以可转换为(N-1)*(N-2)!，……，直至转换为2*1!，而1!=1。
源程序如下:( 例程见exm_4_1.pas)
program exm4_1;
var
n:integer;
y:real;
function fac (n:integer):real;
begin
if n=0 then fac:=1
else fac:=n*fac(n-1)
end;
begin
write('N=');readln(n);
y:=fac(n);
writeln(n,'!=',y:1:0);
readln;
end.
在函数fac中，当N>1时，又调用函数fac，参数为N-1，…，这种操作一直持续到N=1为止。 例如当N=5时，fac(5)的值变为5*fac(4)， 求 fac( 4)又变为4*fac(3)，…，当N= 1时递归停止，逐步返回到第一次调用的初始处，返回结果5*4*3*2*1，即5!。
练习一：利用递归调用技术求菲波拉契数列的第N项。
例4_2、相传在古印度的布拉玛婆罗门圣庙的僧侣在进行一种被称为汉诺塔的游戏，其装置是一块铜板，上面有三根杆（编号A、B、C），A杆上自下而上、由大到小按顺序串上64个金盘（如图3）。游戏的目标是把 A杆上的金盘全部移到C杆上，并仍原有顺序叠好。条件是每次只能移动一个盘，并且在每次移动都不允许大盘移到小盘之上。现要求利用递归调用技术给出N个盘从A杆移到C杆的移动过程。
图3 N阶汉诺塔
分析：这个移动过程很复杂与烦琐，但规律性却很强。使用递归调用技术来解决这个移动过程，先得找到一个递归调用模型。想要得到汉诺塔问题的简单解法，着眼点应该是移动A杆最底部的大盘，而不是其顶部的小盘。不考虑64个盘而考虑N个盘的一般情况。要想将A杆上的N个盘移至C杆，我们可以这样设想：
1.以C盘为临时杆，从A杆将1至N-1号盘移至B杆。
2.将A杆中剩下的第N号盘移至C杆。
3.以A杆为临时杆，从B杆将1至N-1号盘移至C杆。
我们看到，步骤2只需移动一次就可以完成；步骤1与3的操作则完全相同， 唯一区别仅在于各杆的作用有所不同。这样，原问题被转换为与原问题相同性质的、规模小一些的新问题（图4）。即： HANOI(N,A,B,C) 可转化为 HANOI(N-1,A,C,B)与 HANOI(N-1,B,A,B)
其中HANOI中的参数分别表示需移动的盘数、起始盘、临时盘与终止盘， 这种转换直至转入的盘数为0为止，因为这时已无盘可移了。 这就是需要找的递归调用模型。
图4 N-1阶汉诺塔
源程序如下:(例程见exm_4_2.pas)
program exm4_2;
var
a,b,c:char;
n:byte;
procedure hanoi(n:byte;a,b,c:char);
begin
if n>0 then
begin
hanoi(n-1,a,c,b);
writeln('Move ',a,' to ',c);
hanoi(n-1,b,a,c);
end;
end;
begin
a:='A';b:='B';c:='C';
write('N=');readln(n);
hanoi(n,a,b,c);
readln;
end.
如果说例1求N！无法体现递归算法的独特优点的话，那么，上HONOI塔的解法则很能说明问题，因为一般的算法是很难解决这个问题的，而过程HONOI只用了4个语句就解决这个难题。不过要说明的是，按照汉诺塔的移动原则，将N个盘从A杆移动到C 杆需要移动盘的次数是 2 的 N 次幂减 1 ， 那么 64 个盘移动次数就是18446744073709511615，近19亿亿次。这是一个天文数字，即使一台功能很强的现代计算机来解汉诺塔问题，恐怕也需要很长的时间，因此要想得到结果，在运行程序时，输入的N可不能太大。据说布拉玛婆罗门圣庙的僧侣声称， 汉诺塔游戏结束就标志着世界末日的到来，现在看来确实是有道理的。因为如果每秒移动一次，64个盘则大约需近5800亿年，而据科学家以能源角度推算，太阳系的寿命只不过150 亿年而已。
二、队列
队列是限定在一端进行插入，另一端进行删除和特殊线性表。正象排列买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队伍未尾（插入）。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。由于总是先入队的元素先出队（先排队的人先买完东西），这种表也称为先进先表（FIFO）表。
队列可以用数组Q[1…ｍ]来存储，数组的上界ｍ即是队列所容许的最大容量。在队列的运算中需设两个指针：
head：队头指针，指向实际队头元素的前一个位置
tall：队尾指针，指向实际队尾元素所在的位置
一般情况下，两个指针的初值设为０，这时队列为空，没有元素。图1 ( a)画出了一个由６个元素构成的队列，数组定义Q[1…10]。
Q(i) i=3,4,5,6,7,8
头指针head＝2，尾指针tail＝8。队列中拥有的元素个数为:L=tail-head
现要让排头的元素出队，则需将头指针加１。即head=head+1
这时头指针向上移动一个位置，指向Q(3)，表示Q(3)已出队。见图1 (b)。
如果想让一个新元素入队，则需尾指针向上移动一个位置。即tail=tail+1
这时Q(9)入队，见图1 (c)。
当队尾已经处理在最上面时，即tail=10，见图1 (d)，如果还要执行入队操作，则要发生"上溢"，但实际上队列中还有三个空位置，所以这种溢出称为"假溢出"。
克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就"翻转"为１。在结构上采用这种技巧来存储的队列称为循环队列，见图2
循环队的入队算法如下：
1、tail=tail+1；
2、若tail=n+1，则tail=1；
3、若head=tail尾指针与头指针重合了，表示元素已装满队列， 则作上溢出错处理；
4、否则，Q(tail)=X，结束（X为新入出元素）。
队列和栈一样，有着非常广泛的应用。
例4_3：设有ｎ个人依次围成一圈，从第１个人开始报数，数到第ｍ个人出列，然后从出列的下一个人开始报数，数到第ｍ个人又出列，…，如此反复到所有的人全部出列为止。设ｎ个人的编号分别为1，2，…，n，打印出出列的顺序。
分析
本题我们可以用数组建立标志位等方法求解，但如果用上数据结构中循环链的思想，则更贴切题意，解题效率更高。
ｎ人围成一圈，把一人看成一个结点，ｎ人之间的关系采用链接方式，即每一结点有一个前继结点和一个后继结点，每一个结点有一个指针指向下一个结点，最后一个结点指针指向第一个结点。这就是单循环链的数据结构。
当ｍ人出列时，将ｍ结点的前继结点指针指向ｍ结点的后继结点指针，即把ｍ结点驱出循环链。
1、建立循环链表。
当用数组实现本题链式结构时，数组a[i]作为"指针"变量来使用，a[i]存放下一个结点的位置。设立指针j指向当前结点，则移动结点过程为j:=a[j]，当数到m时，m结点出链，则a[j]:=a[a[j]]。
当直接用链来实现时，则比较直观，每个结点有两个域：一个数值域，一个指针域，当数到m时，m出链，将m结点的前继结点指针指向其后继结点；
2、设立指针，指向当前结点，设立计数器，计数数到多少人；
3、沿链移动指针，每移动一个结点，计数器值加１，当计数器值为ｍ时，则ｍ结点出链。计数器值置为１；
4、重复３、直到n个结点均出链为止。
源程序一：用数组实现单链环(例程见exm_4_3a.pas)
program exm4_3a;
const n=14;m=4;{设有14个人,报到4的人出列}
var a:array[1..n] of integer;
i,j,k,p:integer;
begin
for i:=1 to n-1 do a[i]:=i+1;{建立链表}
a[n]:=1;j:=n;k:=1;p:=0;{第n人指向第1人,并置初始}
repeat
j:=a[j];k:=k+1;{报数,计数器加1}
if k=m then {数到m,m人出队,计数器置1}
begin
write(a[j]:4);p:=p+1;a[j]:=a[a[j]];k:=1;
end
until p=n;{直到n个人均出队为止}
end.
源程序二：指针实现单链环(例程见exm_4_3b.pas)
program exm4_3b;
type pointer=^node;
node=record
val:integer;
link:pointer
end;
var ptr,ptb:pointer;
i,j,n,m:integer;
begin
readln(n,m);
new(ptb);ptb^.val:=1;ptr:=ptb;{申请第1个结点}
for i:=2 to n do
begin
new(ptr^.link);ptr:=ptr^.link; {申请第2到n结点}
ptr^.val:=i;
end;
ptr^.link:=ptb;j:=0;{第n结点指针指向第1个结点}
repeat
i:=1;
repeat {报数,报到m人出列}
ptr:=ptb;ptb:=ptb^.link;i:=i+1;
until i=m;
write(ptb^.val:2);
ptb:=ptb^.link;ptr^.link:=ptb;j:=j+1;{将m结点驱出链表}
until j=n-1;{直到n个人均出队为止}
writeln(ptb^.val:4)
end.
PAGE
第12页第五章 树
一、概念
树是n（n≥0）个元素的有限集合。n=0时称为空树。在任一非空树中，有且仅有一个称为根的元素；其余元素可分为m（m≥0）个互不相交的有限集T1，T2…Tm，其中每个集合本身又是一棵树，并且称为根的子树。树的结点包含一个数据元素及若干指向其子树的分支，结点拥有的子树数目称为结点的度。度为0的结点称为叶结点或终端结点，其余结点称为分支结点或非终端结点，树的度是树内各结点度的最大值。
如果将树中结点的各子树看成是从左到右有次序的（即不能互换），则称该树为有序树，否则称为无序树。
结点子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。
结点的层次定义为：根为第一层；若某结点在第P层，则其子树的根就在第P＋1层。树中结点的最大层次称为树的高度或深度。
二、二叉树
二叉树是有序树的特殊情形。在二叉树中，每个结点至多可以有两个子树，分别称为左子树和右子树，且左右子树不可交换。
在二叉树的第i层上至多有2i-1个结点（i≥1）。深度为k的二叉树至多有2k-1个结点（k≥1）。对任何一棵二叉树，若叶结点数为n0,度为2的结点数为n2,则n0=n2+1。
一个深度为k且有2k-1个结点的二叉树称为满二叉树。可以对满二叉树的结点进行从1开始的编号：根的编号为1然后自上而下、从左而右。
深度为k、有n个结点的二叉树，当且仅当其结点与深度为k的满二叉树中编号从1至n的结点一一对应，称之为完全二叉树。具有n个结点的完全二叉树的深度为、[log2n]+1。如果对一棵有n个结点的完全二叉树的结点编号（根为1，然后自上而下、从左而右），则对任一结点i(1≤i≤n)，有：
1）若i=1，则结点i是二叉树的根，无双亲；若i>1，则其双亲结点[i/2]。
2）结点i的左孩子是结点2i，右孩子是2i+1；若2i>n，则i无孩子；若2i=n，则无右孩子。
三、二叉树的遍历
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。
1）先根次序遍历的递归定义
若二叉树为空，则返回；否则，依次执行以下操作：
①访问根结点；
②按先根次序遍历左子树；
③按先根次序遍历右子树；
④返回。
例如图5.1为表示表达式 （ａ＋ｂ×（ｃ－ｄ））－ｅ/ｆ的二叉树。
图 5.1
先序遍历此树时，首先访问根结点，得到字符"－"。继而访问结点"－"的左子树，按递归定义，先访问子树的根结点，得到字符"＋"。类推访问结点"＋"的左子树，此时只有叶子。得到叶子"ａ"后，访问叶子"ａ"父结点的右子树，得到右子树的根结点字符"×"。再访问结点"×"的左子树，得到叶子字符"ｂ"后，访问字符"ｂ"父结点的右子树，得到右子树根结点字符"－"，……。先序遍历完整棵树，得到序列为： －＋ａ×ｂ－ｃｄ/ ｅｆ
这就是表达式的前缀表示或称波兰表示。
2）中根次序遍历的递归定义
若二叉树为空，则返回；否则，作如下操作：
①按中根次序遍历左子树；
②访问根结点；
③按中根次序遍历右子树；
④返回。
中序遍历图5.1二叉树时，引入栈，先将根结点字符"－"入栈，按定义访问根结点的左子树，遇到子树的根结点字符"＋"入栈，访问结点"＋"的左子树，到达叶子字符"ａ"，则字符"ａ"为第一个访问的结点。接着，将栈顶字符出栈，访问子树根结点字符"＋"。继而访问其右子树，方法同上，子树根结点"×"入栈，……。这样，中序遍历完整棵树后，得到的序列为： ａ＋ｂ×ｃ－ｄ－ｅ/ ｆ
这就是表达式的中缀表示。
3）后根次序遍历的递归定义
若二叉树为空，则返回；否则，作如下操作：
①按后根次序遍历左子树；
②按后根次序遍历右子树；
③访问根结点；
④返回。
对图5.1二叉树，后序遍历后得到的序列为： ａｂｃｄ－×＋ｄｆ/ －
这就是表达式的后缀表示或称表达式的逆波兰表示。逆波兰表示的表达式的优点在于它得到的是不加括号的表示式，但从表示式中确能确定表达式的运算先后顺序。故在源程序如下编译表达式值的处理等方面的应用中经常用到。
例题5_1 编一程序，按递增顺序产生序列M中最小的100个数，M定义如下：
1）数1属于M；
2）若X属于M，则Y＝2经X＋1，Z＝3X＋1也属于M；
3）除了条件1）和2）外，再无其它数属于M。
[分析] 此题的解题思路是，用二叉树表示M中的数；根的值为1；对树中任一结点X，其左孩子的值为2X＋1，右孩子的值为3X＋1，该树如图所示。
1
/ \
3 4
/ \ / \
7 10 9 13
/ \ / \ / \ / \
15 22 21 31 19 28 27 40
此树可用一维数组A存储。
A(1)
/ \
A(2) A(3)
/ \ / \
A(4) A(5) A(6) A(7)
/ \ / \ / \ / \
A(8) A(9) A(10) A(11) A(12) A(13) A(14) A(15)
显然，对树中任一结点A（i）,其左孩子为A(2*i)，右孩子为A(2*i+1)，其中左孩子的下标都是偶数，左孩子的下标都是奇数。
从根结点开始先序遍历二叉树（即先访问结点，再访问左子树，然后是右子树），访问一个结点就把其值插入到已访问数组的适当位置。
源程序：(附例程见：exm_5_1.pas)
program exm5_1;
type art=array[1..100] of integer;
var
a:art;
i,j,n:integer;
begin
a[1]:=1;
for i:=2 to 100 do
begin
n:=i div 2 ;
if i mod 2 =0
then a[i]:=a[n]*2+1
else a[i]:=a[n]*3+1;
end;
for j:=1 to 100 do
writeln(a[j]);
readln;
end.
例5_2、试将一段英文中出现的单词按词典的顺序打印出来，同时应注明每个单词在该段文章中出现的次数。
分析：将一段英文中的单词按词典顺序打印的过程， 就是由一个无序序列构造有序序列的过程，这个过程可以通过构造二叉排序树实现。
设A={a1,a2,a3,...,an}为一组元素的集合， 则按下列规则生成的二叉树就是一棵二叉排序树：
⒈令a1为二叉树的根；
⒉若a2 ⒊对a3,a4,...,an递归重复步骤２。
二叉排序树的意义在于，对它按中根次序遍历得到的序列是有序的。
算法步骤：
⒈以输入的第一个单词作为生成二叉树的树根；
⒉读入单词作为新结点，将新结点值与根结点值比较，将小于根结点值的结点，插入到左子树中去，否则插入到右子树中；若相同对应结点的计数器值加１；
⒊重复步骤２，直到文章结束，则整棵二叉树构造完毕。
⒋按中序遍历原则遍历此树，所得到的顺序，便是单词的词典顺序，同时输出对应单词计数器值。
假设输入英文段落为：
Everyone round you can hear you when you sperk
按算法构造的二叉排序树为:
图 3
源程序如下：(例程见exm_5_2.pas)
program exm5_2;{单词排序,用二叉排序树解决}
type
tree=^treetype;
treetype=record
wd:string;
tm:integer;
lt,rt:tree;
end;
link=^linktype;
linktype=record
wd:string;
tm:integer;
next:link;
end;
const
letter=['a'..'z','A'..'Z'];
var
head:link;
root:tree;
n,st:string;
procedure readword;{输入单词}
var
q,p:link;
w:string;
begin
head:=nil;
repeat
write('Word(return means end):');
readln(w);
if w<>'' then begin
p:=head;
while (p<>nil) and (p^.wd<>w) do p:=p^.next;
if p=nil then begin
new(q);q^.wd:=w;q^.tm:=1;q^.next:=head;head:=q;
end;
else inc(p^.tm);
end;
until w='';
end;
procedure create;{建立二叉排序树}
var
p,r:tree;
f:boolean;
q:link;
begin
new(root);
with root^ do begin
wd:=head^.wd;tm:=head^.tm;lt:=nil;rt:=nil;
end;
q:=head^.next;
while q<>nil do begin
p:=root;
new(r);
r^.lt:=nil;r^.rt:=nil;r^.wd:=q^.wd;r^.tm:=q^.tm;
f:=true;
while f do begin
if q^.wdif p^.lt<>nil then p:=p^.lt
else
begin p^.lt:=r;f:=false end
else
if p^.rt<>nil then p:=p^.rt
else
begin p^.rt:=r;f:=false end
end;
q:=q^.next;
end;
end;
procedure pr_tree(p:tree);{输出}
begin
if p^.lt<>nil then pr_tree(p^.lt);
writeln(p^.wd:20,p^.tm:5);
if p^.rt<>nil then pr_tree(p^.rt);
end;
begin
readword;
create;
pr_tree(root);
write('Press ...');readln;
end.
练习二、2003年安徽省青少年信息学（计算机）竞赛一试试题第一题：
PAGE
第17页第三章 数组
一、数组的结构
数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。图5.1是一个m行n列的二维数组。
数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，因此，在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。在数组中通常做下面两种操作：
取值操作：给定一组下标，读其对应的数据元素。
赋值操作：给定一组下标，存储或修改与其相对应的数据元素。
我们着重研究一维和二维数组，因为它们的应用是广泛的，尤其是一维数组。
例题3_1、编制用筛选法求N以内素数的程序。
分析：由希腊数学家埃拉托色尼提出的“筛选法”，步骤如下：
1）将所有候选放入筛中；
2）找了出筛中最小数（必为素数）P；
3）将P的所有倍数从筛中筛去；
4）重复2）至3）直到筛空。
编程时，用数组R表示筛子，R(i)为1时，表示i在筛中，R(i)为0时，表示i已从筛中筛去。
程序设计步骤：
1．建立一个包括2，3，…，N的数据“集合”R；
2．顺序取R中的数（从素数2开始），同时将其及能整除它的数从R中划去。“筛法求素数”的过程如下图示：
素数R[1] 数据集合R
2 { 2， 3， 4， 5， 6， 7， 8， 9，10，11，12，……}
3 { 3， 5， 7， 9， 11， ……}
5 { 5， 7， 11， ……}
…… ………
这样便可得到所求的素数：2，3，5，……。
[源程序] 例程见exm_3_1.pas
program Sushu;
var i,j,k,n,w,t:integer;
R,P:array [1..500] of integer;
Begin
write('N=');readln(n);
if (n<2) or (n>500) then begin writeln('Input N error!');halt end;
for i:=2 to n do R[i-1]:=i; writeln('Result:');t:=0;k:=n-1;
while k>0 do
begin P:=R; {数组R保存在P中}
write(R[1]:5); {输出素数} t:=t+1;w:=R[1];j:=0;
for i:=1 to k do
if P[i] mod w<>0 then {划去w及 W的倍数}
begin j:=j+1; R[j]:=P[i];end; {重新构造集合R}
k:=j; {新建后R的元素个数}
end; writeln;writeln('Total=',t);
end.
a11 a12 … a1n
a21 a22 … a2n
… … … …
am1 am2 … amn
图5.1 m行n列的二维数组
A=
PAGE
第5页