数据结构教案-王全德

    早期的程序设计主要偏重于数值计算领域，采用的数据结构相对简单。例如FORTRAN语言仅定义了数组（包括数组）和复数两种结构型数据，这两种数据类型足以应付当时多数的科学计算问题。但是随着现代科技的发展，计算机逐渐应用于数据处理和非数值计算问题，从客观事物中抽象出的数据日益显现出多样化的特征，简单的数据类型已远远不能满足需要，各数据元素之间的复杂联系已经不是普通的数学方程式所能表达的了。在这种背景下，一种专门研究数据之间结构关系的学科—数据结构便应运而生。

数据结构专门研究各种数据的表示、数据的类型以及它们之间关系的集合，其研究范围主要包括各种数据结构的性质，即它们的逻辑结构、物理结构以及施于其上的操作。数据结构的类型种类繁多，可以从不同的角度来划分：若从数据元素的值在使用时具有不可分割的性质或者是它可以由更基本的成份组成这个角度来划分，数据结构可以分成简单类型和构造类型两大类；如果从数据所占据的内存空间在程序执行期间是否发生变化这个角度来划分，数据结构又可以分成静态结构和动态结构两大类；如果从数据结点后继关系的多少和是否具有层次性的角度划分，数据结构还可以分成线性结构和非线性结构两大类。表5给出了数据结构的一般分类

通常高级程序设计语言都提供了各种简单类型、静态构造类型和动态构造类型的数据结构。例如PASCAL就提供了１２种类型的定义。这１２种类型中除了文件和指针属于动态结构的构造类型外，其余１０种均属于简单类型和静态构造类型。在表5的数据结构中，像数组、栈、串和队列等数据结构属于线性数据结构，而树和图属于非线性数据结构。线性数据结构易于表示各结点之间的联系，其存储方式相对简单；非线性数据结构往往能比较形象地反映各结点之间的层次关系。无论是线性结构或非线性结构，若采用数组方式存储，则属于静态数据类型；若采用指针类型存储，则属于动态数据类型。考虑到篇幅和读者具备了Pascal语言的基础，我们侧重讲解线性结构和非线性结构两种，在分析程序时不提供可直接上机运行的源代码，而是采用贴近自然语言的类Pascal来描述算法的基本思想和步骤，为读者上机实践留下空间。

第五章 顺序存储结构的线性表

    线性表是最常用且比较简单的一种数据结构，它是由有限个数据元素组成的有序集合，每个数据元素有一个数据项或者含多个数据项。例如26个英文字母表(A，B，……，Z)是一个线性表，表中每一个数据元素由单个字母组成数据项。又如表5.1也是一个线性表，表中含8个数据元素，每一个数据元素由n个选手在该项目的竞赛成绩组成。

      学生

线性表具有如下结构特征：

均匀性：即同一线性表的各数据元素的数据类型一致且数据项数相同；

    有序性：表中数据元素之间的相对位置是线性的，即存在唯一的“第一个”和“最后一个”数据元素。除第一个和最后一个外，其它元素前面均只有一个数据元素（直接前趋）和后面均只有一个数据元素（直接后继）。

按照表中数据元素的存储方式分顺序存储结构和链式存储结构二类线性表

1.顺序存储结构

顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的元素，通常用数组实现。数组的物理实现是一块连续的存储空间，它是按首址（表中第1个元素的地址）十位移来访问每一个元素的。设

 loc(a[i])—A表中元素i的内存地址（c≤i≤d）； 

   loc(b[i，j])—B表中（i，j）元素的内存地址（c1≤i≤d1，c2≤j≤d2）；                                   

   loc(a[i])=loc(a[c])+(i-c)*la        la—atype类型的长度；   

                首址      位移     

   loc(b[i，j])=loc(b[c1，c2])+((d2-c2+1)*(i-c1)+(j-c2))*lb  lb—btype类型的长度；

                    首址              位移      

一维数组按照下标递增的顺序访问表中元素

          a[c]→a[c+1]→……→a[d]

二维数组按照先行后列的顺序访问表中元素

b[c1，c2]→b[c1，c2+1]→…→b[c1，d2]→…→b[i-1，d2]→b[i，c2]→…→b[d1，d2-1]→b[d1，d2]

在数组中，数据元素的下标间接反映了数据元素的存储地址。而计算机内存是随机存取的装置，所以在数组中存取一个数据元素只要通过下标计算它的存储地址就行了，数组中任意一个元素的存取时间都相等。从这个意义上讲，数组的存储结构是一个随机存取的结构。

但问题是，虽然数组的顺序分配结构比较简单，便于随机访问数组中的任一元素。但如果数组要保持线性表特征的话（由下标指明元素间的有序性），其增删操作的效率比较低。特别当数组很大时，插入与删除运算颇为费时。因此，比较小的数组或元素不常变动（很少进行插入与删除运算）的数组可用作线性表，而对于大的线性表或元素经常变动的线性表，可以采用链式存储结构。

2.链式存储结构

在链式存储结构的线性表中，逻辑上相邻的两元素，其物理位置不要求相邻。其实现即可采用静态数组，亦可采用动态指针。为了扩大用户空间和更多地体现链式存储结构的便利，实践中大都采用动态链表形式。我们在“§3.5指针类型”中介绍了最典型的链式存储结构—单链表，并剖析了单链表的存取操作。

为了避免重复，本章节在讲解顺序存储结构的线性表时，主要介绍几种特殊类型的线性表：栈、队列、串，这些线性表一般采用顺序存储结构

§5.1 栈

    栈是一种线性表，对它的插入和删除都地表的同一端进行。这一端叫做栈的“顶”，另一端则叫做栈的“底”。 

   根据栈的定义，每次删除的总是当前“最年轻”的表目，即最后插入的表目，而最先插入的表目则被放在栈的底部，要到最后才能删除。因此，栈又被称为“后进先出表”（LIFO—last input first output）或下推表。仿佛食堂里的一叠盘子，每次只许一个一个地往上堆，一个一个地往下取。

    通常栈可以用顺序的方式存储，分配一块连续的存储区域存放栈中的表目，并用一个变量t指向当前栈顶（图5．1.1）。

图5．1.1

假设栈中表目数的上限为m，所有表目都具有同一类型stype，则可以用下列方式定义栈：

      Const

        m=栈表目数的上限；

      Type

       stack=array[1‥m] of stype；                                            {栈类型}

      Var 

s：stack；                                                                  {栈}

t：integer；                                                          {栈顶指针}

1.过程push(s，x，t)—往栈s中压入一个值为x的表目

       procedure push (var s：stack； x：stype； var t：integer)；

        begin

          if t=m then writeln(’overflow’)                                       {上溢}

                 else begin t←t+1； s[t]←x； end；{else}                    {x入栈}

        end；{Push}

2.函数pop(s，t)—从栈中弹出一个表目

       function pop (var s：stack； var t：integer)：stype；

         begin

          if t=0 then writeln (’underflow’)                                     {下溢}

                 else begin pop←s[t]；  t←t-1； end；{else}           {栈顶元素出栈}

         end；{pop}

3 函数top(s，t)—读栈顶元素

       function top (s：stack； t：integer)：stype；

        begin

         if t=0 then writeln (’stack empty’)

                else top←s[t]；                                        {返回栈顶元素}

        end；{top}

【例5．1．1】四色问题

设有下列形状的图形：有n个区域（1≤n≤100）,各区域的相邻关系用0（不相邻）、1（相邻） 表示。例如表5.1.1的邻接矩阵对应图5.1.2。

图5.1.2

将上面图形的每一部分涂上红（1）、黄（2）、蓝（3）、绿（4）四种颜色之一，要求相邻部分的颜色不同。

输入文件为当前目录下的1.in，格式为

n

n*n的01矩阵

输出文件为当前目录下的1.out ，格式为

1→区域1的颜色码

2→区域2的颜色码

……

n→区域n的颜色码

例如，对于上例，应输出

1—>1

2—>2

3—>1

4—>2

5—>1

6—>3

7—>4

8—>2

题解

按照涂色的先后顺序将方案存入堆栈s中，其中s[k]为区域k的颜色码，区域k为第k个涂色的区域。在计算过程中，我们总是对最近涂色的区域进行颜色调整，即所谓的“后进先出”，为此，必须记住下一个涂色的区域号i，该区域称之为“栈顶”（如图5.1.3）。区域i准备涂颜色j(1≤j≤4)

       图5.1.3

我们采用试探法涂色。首先，将区域1涂红色（s[1]=1）,并准备涂区域2（i=2），从颜色1开始试探（j=1）。

区域i能否涂颜色j，关键取决于区域i的周边是否有同色区域。搜索已涂色的区域1…区域i-1中与区域i相邻的区域k，看一看这些区域是否涂了颜色j。判断条件是

 （kj)or(矩阵的（i,k）=0))

由于矩阵元素只有0、1两个值，因此判断条件可以简写为

矩阵的(i,k)*s[k]<>j

如果上述条件成立，则说明区域k是区域i相邻的不同色区域。搜索过程如下：

k:=1； 

while (kj)do k:=k+1；

搜索结束后，若k的值小于i，则说明区域i相邻的区域k已经涂了颜色j，按照颜色码递增顺序换一种颜色（j=j+1）；否则说明区域i的周边没有涂颜色j的区域，区域i可以涂颜色j(s[i]=j)。 “入栈”，准备涂区域i+1，从颜色1开始试探（i=i+1,j=1）。

我们对区域i，按照颜色码递增顺序试探颜色。如果区域i找不到合适的颜色（j>4）,则应该“出栈”，按照颜色码递增顺序调整区域i-1的颜色（i=i-1,j=s[i]+1）。

从区域1出发，依次类推，直至区域n涂好颜色为止（i>n）。由此得出算法：

var

 i,j,k,n:integer；

 r:array[1..100,1..100]of 0..1；                                             {邻接矩阵}

 s:array[1..100] of integer；                                            {区域的颜色表}

begin

readln(n)；                                                                  {读区域数}

for i:=1 to n do                                                            {读邻接矩阵}

  begin

   for j:=1 to n do read(r[i,j])；

   readln)；                                            

  end；{for}

s[1]:=1；                                                               {区域1涂红色}

 i:=2；j:=1；                                            {指向区域2，从颜色1开始试探}

 while i<=n do                                                {若区域n未涂色，则循环}

 begin

  while (j<=4)and(i<=n)do                                           {寻找区域i的颜色}begin

    k:=1；   {判断已涂色的区域1—区域i-1中是否存在与区域i相邻、且已涂了颜色j的区域}

while (kj)do k:=k+1；

    if k           else begin            {若相邻的所有区域未涂颜色j，则“入栈”，区域i涂颜色j}

                s[i]:=j；

i:=i+1；j:=1；                               {区域i+1从颜色1开始试探}

                end；{else}

   end；{while}

  if j>4 then             {若区域i找不到合适的颜色，则“出栈”，区域i-1改涂下一种颜色} 

begin i:=i-1； j:=s[i]+1；end；{then}

 end；{while}

for i:=1 to n do writeln(i,’---> ’,s[i])；                       {输出每一个区域的颜色}

end.{main}

【例题5.1.2】计算后缀表达式

    所谓后缀表达式是指这样的一种表达式：式中不再引入括号，运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严格地由左而右进行（不再考虑运算符的优先规则）。例如

   3*（5-2）+7  对应的后缀表达式为 3．5．2．-*7．+ @

其中’@’为后缀表达式的结束标记，’．’为操作数的结束符。

         3．5．2．-*7．+ 

         =3．3．*7．+ 

         =9．7．+

         =16

 输入：

   后缀表达式A（假定A合乎文法，不需判错）；

 输出：

   表达式的值。

题解

设后缀表达式串为A。操作数和计算结果存放在栈s中，s的元素类型stype为整型。计算过程如下：

    由左而右处理A中的每一个字符。如遇到一个操作数，就送入s栈中保存；如遇到一个运算符，就从栈中取出栈顶的两个操作数进行计算，然后将计算结果重新压入栈中。依次类推，直至表达式最后一个运算符处理完毕，这时的栈顶元素值即为计算结果：

    var 

      s： stack ；                                                                {栈}

      A： string；                                                        {后缀表达式}

      t，i，j，k ：integer；    {t—栈顶指针；i—后缀表达式的字符指针；k、j—操作数值}

      begin 

        读后缀表达式A；

        i←1； t←0；                            {后缀表达式的字符指针和栈顶指针初始化}

while A[i]<> ’@’  do                             {若后缀表达式末处理完，则循环}

          begin 

           case A[i] of 

             ’0’‥’9’： begin

                      k←0；

                      repeat                              {从后缀表达式中取出操作数k}

                       k←10*k+ord(A[i])-ord(’0’)；      

                       i←i+1；

                      until A[i]= ’．’；

                      push (s，k，t)；                              {操作数k压入栈中}

                     end；{ ’0’‥’9’}

             ’+’：      push(s，pop (s，t)+pop(s，t)，t)；

                                   {取出栈顶的两个操作数进行加法运算，其和重新压入栈中}

             ’-’：      begin      {取出栈顶的两个操作数进行减法运算，其差重新压入栈中}

                      j←pop (s，t)；

                      push (s，pop (s，t) –j， t)；

                     end；{ ’-’}

             ’*’：      push (s，pop(s，t)*pop(s，t)，t)；

                                   {取出栈顶的两个操作数进行乘法运算，其积重新压入栈中}

             ’/’：      begin      {取出栈顶的两个操作数进行除法运算，其商重新压入栈中}

                      j←pop(s，t)； push(s，pop(s，t)div j， t)；

                      end；{ ’/’}

           end；{case}

           i←i+1；

          end；{while}

         writeln(pop(s，t))；

       end；{main}

§5.2 队列

队列是不同于栈的另一种线性表。在日常生活中，无论是购物、订票或候车都有可能要排队。排队所遵循的原则是“先来先服务”，后来者总是加到队尾，排头者总是先离开队伍。队列就是从日常生活中的排队现象抽象出来的。所谓队列，就是允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针r指向队尾元素，即r总是指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指针f指向排头元素的前面。初始时f=r=0（如图5．2.1）。

图5．2.1

    显然，在队列这种数据结构中，最先插入在元素将是最先被删除；反之最后插入的元素将最后被删除，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。与栈相似，队列的顺序存储空间可以用一维数组q[1‥m]模拟：          

图5．2.2

我们按照如下方式定义队列：

Const

  m=队列元素的上限；

Type

  equeue=array[1…m] of qtype；                                        {队列的类型定义}

Var 

 q：equeue；                                                                    {队列}

 r，f：integer；                                                  {队尾指针和队首指针}

队列的运算主要有两种

1.过程ADD(q，x，r)—在队列q的尾端插入元素x

     procedure ADD(var q： equeue； x：qtype； var r：integer)；

       begin

        if r=m then writeln (’overflow’)                                        {上溢}

               else begin                                   {后移队尾指针并插入元素x}

                    r←r+1；  q[r]←x；

                    end；{else}

       end；{ADD}

2.过程DEL(q，y，f，r）—取出q队列的队首元素y

     procedure DEL(var q：equeue； var y：qtype； var f：integer)；

      begin

       if f=r then writeln (’under flow’)                                        {下溢}

              else begin                                  {后移队首指针并取出队首元素}

                   f←f+1；  y←q[f]；

                  end；{else}

      end；{DEL}

由于队列只能在一端插入，在另一端删除，因此随着入队及出队运算的不断进行，就会出现一种有别于栈的情形：队列在数组中不断地向队尾方向移动，而在队首的前面产生一片不能利用的空闲存储区，最后会导致当尾指针指向数组最后一个位置（即r=m）而不能再加入元素时，存储空间的前部却有一片存储区无端浪费，这种现象称为“假溢出”。图5．2.3给出了一个“假溢出”的示例：

         初始时队列空      加入三个元素     删除三个元素队列空    加入m-3个元素队列满

          f=r=0             f=0 r=3              f=r=3               r=m  f=3   

图5．2.3

为了解决“假溢出”的问题，我们不妨作这样的设想：在队列中，当存储空间的最后一个位置已被使用而要进行入队运算时，只要存储空间第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。采用首尾相接的队列结构后，可以有效地解决假溢出的问题，避免数据元素的移动，这就是所谓的循环队列。图5．2.4给出了循环队列的结构。

图5．2.4

循环队列将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用，循环队列的存取方法亦为““先进先出””。

对循环队列操作有以下几种状态：

●初始时队列空，队首指针和队尾指针均指向存储空间的最后一个位置，即f=r=m。

●入队运算时，尾指针进一，即

             r←r+1；  if r=m+1 then r←1；

    这两条语句可用一条语句替代：

              r←r mod m+1；

●出队运算时，首指针进一，即

              f←f+1；if f=m+1 then f←1；

    这两条语句可用一条语句替代：

              f←f mod m+1；

●队列空时有f=r。

●队列满时有f=r mod m+1。（为了区分队列空和队列满，改用“队尾指针追上队首指针” 这 一特征作为队列满标志。这种处理方法的缺点是浪费队列空间的一个存储单元）

循环队列的运算有两种：

1.过程ADD2(q，x，r）—在循环队列q中插入一个新元素x

   procedure ADD2 (var q：equeue； x：qtype； var r：integer)；

    begin 

     t←r mod m+1；                                                      {计算插入位置}

     if t=f then writeln(’full’)                                               {队列满}

            else begin                                              {新元素x插入队尾}

                 r←t； q[r]←x；

                 end；{else}

end；{ADD2}

2 过程DEL2(q，y，f)—从循环队列q中取出队首元素y

    procedure DEL2 (var q：equeue； var y：qtype； var f：inteqer)；

     begin

      if f=r then writeln (’empty’)                                           {队列空}

             else begin

                  f←f mod m+1；y←q[f]；                               {取出队首元素}

                  end；{else}

     end；{DEL2}

队列的应用范围很广，其中最为典型的应用是广义表的计算和图的宽度优先搜索。本章节着重讲解前者，至于后者，放到“§6．2 图”中详述。

【例题5.2.1】广义表的计算

    设有一个表l={a1，…，an}，其中l为表名，ai为表元素(１≤i≤n)。当ai为数值时，表示为元素；当ai为大写字母时，表示另一个表，但不能循环定义。例如下列定义是合法的（约定l是第一个表的表名）：

           l=(3，4，3，4，k，8，0，8，p)

           k=(5，5，8，9，9，4，)

           p=(4，7，8，9，)

程序要求：当全部表给出后，求出所有元素的最大元素。例如上例的最大元素为９,表中的全部元素和为98。

输入：

  输入全部表，每行一个表；

输出：

  最大元素值和全部元素和。

题解

  广义线性表（简称广义表）是线性表的一种推广。如果允许构成线性表的元素本身又可以是线性表的话，则该线性表既为广义表。由此可见，广义表是一个递归定义的表，允许其元素可以是本身的一个子表。题目约定表名为大写字母且L为第一个广义表的表名，所有广义表存储在数组t中。广义表t的定义如下：

const lmax=100；                                                     { 广义表串长的上限}

type

 tabtype=record                                                     {广义表的数据类型}

      length:0..lmax；                                                          {表长}

      element:array[1..lmax]of char；                                   {表的数据序列}

      end；

 var t:array[’A’..’Z’]of tabtype；                          {t[ch]—表名为ch的广义表}

1.构造广义表t

每一个广义表用一个字符串s读入，s中的所有数字和字母看作是表的元素，将其中的小写字母统一为大写。设队列q

type

qtype=record                                                    {队列的数据类型}

       base:array[0..lmax]of char；                                         {队列}

       front,rear:0..lmax；                                             {首尾指针}

      end；

var 

    q:qtype；                                                               {队列}

q队列依次存储L表中的字母元素（即表名）。先读入广义表L，将其元素存入t[L]中，表L中出现的字母依次进入队列q；若队列q不空，队首元素ch出队，读入广义表ch，将其元素存入t[ch]中，表ch中出现的字母再依次入队，……，直至队列空为止。

for ch：= ’A’to’Z’do t[ch].length：=0；                              {置所有广义表空}

 q.front:=0； q.rear:=0；                                        {队列的首尾指针初始化}

 inqueue(q,’L’)；                                                     {表名L进入队列}

 while q.front<>q.rear do                                          {若队列非空，则循环}

  begin

   ch:=outqueue(q)；                                               {取出队列首部的表名}

   write(ch,’= ’)；                                          {输入表名为ch的广义表串}

   readln(s)；

   i:=1；                                            {从广义表串的第1个字符开始取元素}

while s[i]<> ’(’do i:=i+1；

while s[i]<> ’)’do

    begin

      s[i]:=upcase(s[i])；                                    {将第i个字符统一为大写}

      if s[i] in[’A’..’Z’,’0’..’9’]    {若第i个字符为广义表元素，则该字符进入广义表}

       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])；  {若第i个字符为表名，则入队}

            end；{then}

     inc(i)；                                                 {分析输入串的下一个字符}

   end；{while}

  end；{while}

其中出队运算outqueue(q)和入队运算inqueue(q,s[i])的定义如下：

procedure inqueue(var q:qtype；c:char)；{表名c进入队列}

 begin

  q.rear:=q.rear+1；                                                      {队尾指针+1}

  q.base[q.rear]:=c；                                                           {入队}

 end；{inqueue}

function outqueue(var q:qtype):char；                              {队列首部的表名出队}

  begin

   q.front:=q.front+1 ；                                                  {队首指针+1}

   outqueue:=q.base[q.front]；                                                 { 出队}

  end；{outqueue}

2.计算广义表L的最大值

设广义表L中的最大数码为m，m设为全局变量。初始时，m= ’0’。我们从t[L]开始搜索：

若表中的第i个元素（t[L].element[i]）为数字码，则m与之比较，若m小于该数码，则被取代之；

若表中的第i个元素为字母，则递归搜索以该字母为表名的广义表。

依次类推，直至搜索了广义表L的所有元素为止。这一递归计算过程由子程序maxnumber描述：

function maxnumber(c:char):char；                {计算和返回表名为c的广义表的最大值}

var

 ch,m:char；

 i:integer；

 begin

  max:= ’0’；                                                         {最大数码初始化}

  for i:=1 to t[c].length do                                 {搜索广义表c的每一个元素}

   begin

    ch:=t[c].element[i]；                                     {取出广义表的第i个元素}

    if ch in[’A’..’Z’] then m:=maxnumber(ch)       {若该元素为表名，则递归计算最大数码}

                       else m:=ch；                            {若该元素为数码，则记下}

    if max   end；{for}

  maxnumber:=max；                                             {返回广义表c的最大数码}

 end；{maxnumber}

显然，主程序可通过语句

writeln(’the max number in table L is:’,maxnumber(’L’))；

直接计算和输出广义表L的最大值。

3.计算广义表L的数和

设广义表L中的数和K，初始时，K=0。我们从t[L]开始搜索：

若表中的第i个元素（t[L].element[i]）为数字码，则该数字码对应的数值累计入k；

若表中的第i个元素为字母，则递归搜索以该字母为表名的广义表。

依次类推，直至搜索了广义表L的所有元素为止。这一递归计算过程由函数total描述：

function total(c:char):integer；                   { 计算和返回表名为c的广义表的数和}

var

 k,i,m:integer；

 ch:char；

begin

 k:=0；                                                                   {数和初始化}

 for i:=1 to t[c].length do                                 {搜索广义表c的每一个元素}

  begin

   ch:=t[c].element[i]；                                      {取出广义表的第i个元素}

   if (ch in[’A’..’Z’]) then m:=total(ch)             {若该元素为表名，则递归计算数和}

                        else m:=ord(ch)-ord(’0’)；            {若该元素为数码，则记下}

   k:=k+m；                                                                 {累计数和}

  end；{for}

 total:=k；                                                      { 返回广义表c的数和}

end；{total}

显然，主程序可通过语句

   writeln(’Total is:’,total(’L’))；

直接计算和输出广义表L的数和。

§5.3 串

    前面介绍的线性表的操作都是对一个元素进行处理的，但实际中我们经常要对一串元素进行操作。如信息检查系统、文字编辑系统、自然语言翻译系统以及音乐分析程序等等，都是以字符串数据作为处理对象的。随着非数值的广泛应用，字符串的处理将显得越来越重要。

    串是由零个或多个字符组成的有限序列。一个串中包含的字符个数称为这个串的长度。长度为零的串称为空串，它不包含任何字符。

   通常用撇’’将字符串括起来。例如

  ⑴’x1’      长度为2的串

  ⑵’123’     长度为3的数串

  ⑶’’        长度为0的空串

  ⑷’ ’       包含一个空白字符（长度为1）的非空串

   假设s1和s2是两个串：

           s1=a1……an

           s2=b1……bm

其中ai、bi代表字符（0≤m≤n）。如果存在整数i（0≤i≤n-m），使得

            bj=ai+j    j=1‥m

同时成立，则称s2是s1的子串，又称串s1包含串s2。

    串中所能包含的字符依赖于具体机器的字符集，按字符的字符集中的次序可以规定字符的大小。目前世界上最为广泛的字符集是ASCII（美国信息变换标准码）和EBCDIC（扩充的二进制编码、十进制信息码），它们都规定数字字符’0’‥’9’的字符集是顺序排列的，字母字符’A’‥’Z’（’a’‥’z’）的字符集也是顺序排列的，因此用ord函数计算字符在字符集中的序号就有

ord(’a’)ord(’0’)并且对所有数字i（0≤i≤9）满足

                i=ord(’i’)-ord(’0’)

    通常可对两个字符ch1和ch2作比较，所谓ch1                 ’a’< ’abo’< ’x’

                 ’012’< ’123’< ’2’

程序中使用的串可以分成两种

1.串常数

   串常数具有固定的串值，即可以用直接量表示，用以原样输出，亦可以给串常数命名，以便反复使用时书写和修改方便。例如

            const   object= ’data structure’；                              {命名串常数}

            writeln (’overflow’)；                                      {原样输出串常数}

2.串变量

    串变量的取值是可以改变的，但必须用名字来识别，说明串变量的方法与其它变量相似。例如

          var

            s：string[30]；

上面定义了一个串变量s，s最多能容纳30个字符，且顺序存在一个字符数组中，类似于

           var

            s：array[0‥30]of char；

其中s[0]记载了s的实际长度。若string类型中省略长度标记，则串长上限为255个字符。

TURBO．PASCAL中提供了一些串运算的库函数，我们将作以简单的介绍

1.连接运算——函数concat(s1，[，s2，…，sn])

其中值参s1，‥，sn为string类型，函数值为string类型。若连接后的串长大于255，则自动截断超出部分。

2.求子串——函数copy(s，i，l)

其中值参s为string类型，i和l为integer类型。函数返回s串中第i个字符开始、长度为l的子串（string类型）。若i大于s的长度，则回送一个空串；若l大于第 i个字符开始的余串长度，则仅回送余串。

3.删子串——过程delete(var  s，i，l)

其中变量参数s为string类型，值参i、l为ingteger类型。该过程删去s中第i个字符开始的长度为l的子串，并返回剩余串s。若i大于原串s的长度，则不删任何字符；若l大于第i个字符开始的余串长度，则删去余串。

4.插入子串——过程insert(s1， var  s，i)

    变量参数s为string类型，值参s1为string类型。该过程将s1子串插入空串s的第i个字符位置处，并返回插入后的结果s。若插入后s的串长大于255个字符，则截断超出部分。

5.求串长——函数length(s)

    值参s为string类型。该函数返回s串的实际长度值（integer类型）。

6.搜索子串位置——函数pos(s1，s2)

值参s1和s2为string类型。若s1是s2的一个子串，则返回s1中第1个字符在s2串中的位置（integer类型）；若s1非s2的一个子串，则返回0。

7.数值转换为数串——过程str(x，var  s)

值参x为integer类型或real类型，变量参数s为string类型。该过程将返回数值x对应的数串s。

8.数串转换为数值——过程val(s，var v，var c)

值参s为string类型，变量参数v为integer类型或real类型，变量参数c为integer类型。该过程试将s串转换成数值v。若转换成功，则c为0，并返回对应的数值v；否则c为无效字符的序数。

9.字符的大写转换——函数upcase(ch)

值参ch为char类型。该函数返回ch字符的大写体（char类型）

【例题5.3.1】数码排序

设有n个正整数，将他们连接成一排，组成一个最大的多位整数.例如：n=3时，3个整数13，312，343，连成的最大整数为：34331213。又如：n=4时，4个整数7，13，4，246连接成的最大整数为7424613。

程序输入：N

          N个数

程序输出：连接成的多位数 

题解

在最大的多位整数中，每一个整数都处于最佳位置。即第i个整数si相对于其后的每一个整数sj(i+1≤j≤n)来说，si应排在先。我们按照上述要求排定每一个整数的位置。n个整数采用字符串类型存储。设

var 

s：array[1..100] of string；

s1：string；

无论n个整数怎样连接，连接后的数码个数一定，因此完全可以通过n个数串的递减排序计算连接方案。

for i←1 to n-1 do                                                    {顺序排定s1…sn-1}

    for j←i+1 to n do                                            {si依次与si+1…sn比较}

if s[i]        begin

          s1←s[i]；s[i] ←s[j]；s[j] ←s1；

        end；{then}

for i←1 to n do write(s[i])；                                        {输出最大的多位整数}

【例题5.3.2】字符串编辑

从键盘输入一个字符串(长度≤40个字符)，并以字符’.’结束.

例如：’This  is  a  book.’，现对该字符串进行编辑，编辑功能有：

D：删除一个字符，命令的方式为：

  D  a  其中a为被删除的字符

  例如：D  s  表示删除字符’s’，若字符串中有多个’s’，则删除第一次出现的，如上例中删除的结果为：

         ’Thi  is a book.’

I：插入一个字符，命令的格式为：

  I  a1  a2   其中a1表示插入到指定字符前面，a2表示将要插入的字符

  例如：I  s  d 表示在指定字符’s’的前面插入字符’d’，若原串中有多个’s’，则插入在最后一个字符的前面，

     如上例中，原串：’This is a book.’

            插入后：’This ids a book.’

R：替换一个字符，命令格式为：

  R  a1  a2 其中a1为被替换的字符，a2为替换的字符，若在原串中有多个a1，则应全部替换

  例如：原串：’This  is  a  book.’

       输入命令： R  o  e

     替换后：’ This  is a beek.’

在编辑过程中，若出现被指定的字符不存在时，则给出提示信息

题解

设

 s—原串和目标串；

 que—命令串。其中que[1]为命令字， que[2]和que[4]为空格。que[3]和que[5]的定义如下：

在D命令中，que[3]为被删字符；

在I命令中，que[3]为插入位置字符，que[5]为被插入字符；

在R命令中，que[3]为被替换字符， que[5]为替换字符；

删除操作

字串S中寻找que[3]。若找不到，则失败退出；否则，将该字符删去：

i←pos(que[3]，s)；

            if i=0 then begin writeln(’Error!’)；halt；end{then}

                   else delete(s，i，1)；

插入操作

从S串尾出发，由右而左寻找que[3]字符的位置。若找不到，失败退出；否则将que[5]字符插在该位置前：

i←length(s)；                             {由右而左寻找que[3]字符的位置i}

while (i>0)and(s[i] ≠que[3]) do i←i-1；

            if i≠0 then insert(que[5]，s，i)               { 将que[5]字符插在i位置前}

                else begin writeln(’Error!’)；halt；end；{else}

替换操作

从串首出发，由左而右寻找que[3]字符的位置。若找不到，失败退出；否则将que[5]替换所有的que[3]字符：

error←true；

            for i←1 to length(s) do                          {由左而右替换que[3]字符}

            if s[i]=que[3] then begin error←false；s[i]←que[5]；end；{then}  

if error then begin writeln(’Error!’)；halt；end{then} {若找不到，失败退出}

由此得出算法：

  输入原串s和命令串que；

    case que[1] of

       ’D’：begin

           删除操作；

          end；{ ’D’}

       ’I’：begin

           插入操作；

          end；{ ’I’}

       ’R’：begin

替换操作；          

           end；{ ’R’}

    end；{case}

输出s；

由于字符串类型string的长度上限为256，因此可以通过输入数串得到高精度数据，并通过对数串的数值转换进行高精度运算。我们不妨举一个例子：

【例题5.3.3】求回文数

    若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。例如：给定一个10进制数56，将56加65（即把56从右向左读），得到的121是一个回文数。

又如，对于10进制数87：

          STEP1：  87+78=165        STEP2：   165+561=726

          STEP3：  726+627=1353     STEP4：   1353+3531=4884

在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。

    写一个程序，给定一个N（2≤N≤10，N=16）进制数m，m的位数上限为20。求最少经过几步可以得到回文数。如果在30步以内（包括30步）不可能得到回文数，则输出“impossible”

 样例：

   INPUT                  OUTPUT

N=9   m=87            STEP=6

题解

1.将数串s转化为整数数组m

设数串s=s1‥sp，串长为p。其中si为第p-i+1位n进制数（1≤i≤p）。我们将s转化为整数数组m=m[p]‥m[1]，其中m[i]对应第i位n进制数。设

type

mtype=array[1..100]of integer；

var

  m：mtype；

按下述方法将s转化为整数数组m：

              p←length(s)；                                            {计算s的串长}

              for i←1 to p do                             {从最高位开始计算整数数组m }

                begin

                  k←p-i+1；                                {计算si对应于的m数组下标}

                  case s[i] of                                                {转换si}

                     ’a’．．’f’：m[k]←10+ord(s[i])-ord(’a’)；

                     ’0’．．’9’：m[k]←ord(s[i])-ord(’0’)；

                     else 输出错误信息并退出程序；

                 end；{case}

               end；{for}

2.判别整数数组m是否为回文数

function check (m： mtype) ：boolean；{若整数数组m为回文数，则返回true，否则返回false}

 var i：integer；

           begin

            check←false；

            for i←1todo if m[i] ≠m[p-i+1] then exit；      {返回m非回文数标志}

            check←true；                                         {返回m为回文数标志}

           end；{check}

3.n进制加法运算

 整数数组m1与其反序数m2进行n进制加法运算，得到结果m1

           procedure solve(var m1： mtype)；

            var m2： mtype；

              begin

                for i←1 to p do m2[i]←m1[p-i+1]；                      {计算反序数m2}

                for i←1 to p do                                     {由右而左逐位相加}

                    begin

                     m1[i]←m1[i]+m2[i]；

                     m1[i+1]←；                                  {进位}

                     m1[i]←m1[i]mod n；                                   {确定当前位}

                   end；{for}

                  if m1[p+1] ≠0 then p←p+1；                             {最高位进位}

                  if check (m1)then  输出步数并退出程序；  

                end；{solve}

4.算法流程

综合上述分析，不难得出算法流程：

            输入进制数n和数串s；

            fillchar(m，sizeof(m)，0)

将s转换为整数数组m；

            if check(m) then begin 输出步数0；halt；end；{then}

            步数初始化为0；

            while 步数≤30 do

             begin

              步数+1；solve(m)；

             end；{while}

输出无解信息； 

§5.4 例题

1.编号分别为1‥n的n辆列车顺序进入一个栈式结构的站台。试给出这n辆列车开出车站的所有可能次序。例如编号为1‥4的4辆列车按照push、push、pop、push、push、pop、pop、pop操作，可使得开出车站的次序为2、3、4、1。

1.银行有四个服务窗口，每天工作时间为8小时，假定每个客户办理业务的时间不超过15分钟，两个相邻到达银行的客户的时间间隔不超过10分钟，刚到达的客户必须按照顺序排队，且总是选择人数最少的队伍排，并设模拟程序从第一个客户到达时间为0开始运行。请编程模拟银行一天的这种业务活动，并计算一天中客户在银行逗留的平均时间。

2.将中缀表达式转换为后缀表达式。中缀表达式的输入格式与算术表达式大致相同，只不过增加了’@’(表达式的结束标志)和’，’（操作数的结束标志）。例如3.*(5.-2.)+7.@。

输入：中缀表达式E（E合乎文法，不需判错）；

输出：计算顺序和结果与E相同的后缀表达式。

4．设某汽车加油站有两台油泵，每台油泵无一辆车加油的时间为d分钟，现以知加油站的来车率为分钟。用计算机模拟此汽车加油站的工作方式。假设模拟时间长度为long分钟，并用步长法进行模拟，取采样时间间隔为dt，即每隔dt分钟对汽车加油站工作情况测试一次。

输入：d，q，long，dt；

输出：每隔dt分钟汽车的排队情况（等待加油的汽车队列），每台油泵的工作进程（四种情况之一：空闲、正在加油、已经加完油、刚加完油）和服务对象（为哪辆车加油）。

第六章 非线性结构—树和图

§6.1 树

第五章讨论的线性表（包括栈、队列、与串）属于线性结构。在这种结构中，不管其存储方式如何，数据元素的逻辑位置之间呈线性关系，每一个数据元素通常只有一个前件（除第一个元素外）和一个后件（除最后一个元素外）。在实际生活中，可以用线性结构描述数据元素之间逻辑关系的问题是很广泛的，但也有很多问题不能依靠线性结构来解决，因此在这类问题中，数据元素间的逻辑关系不能用线性结构明确、方便地描述出来。

例如某学校试图将学生成绩表中的百分制成绩转换成五个等级，其中成绩0～59分为不及格，60～69分为及格，70～79分为中，80～分为良，90～100分为优。现有n个学生的百分制成绩，如何将他们的成绩转换成五级分制。图6.1.1揭示了一个百分制成绩的判定转换过程。对于这样一张简单的表，已经不能用线性结构来表示。因为表中数据元素可能有两个后件，它们之间的关系已经不是线性的了。

图6.1.1

 至少存在一个结点（数据元素）有多于一个前件或后件的数据结构称为非线性结构。（图6.1.1）中所示的表是一个非线性结构。由该图可以看出，虽然每一个结点可能有多个后件，但它们的前件却只有一个（第一个结点无前件）。这种非线性结构称为树，树表示了数据元素之间的层次关系，而这种层次关系仿佛像一棵倒长的树。

下面讨论树的基本概念，其中重点讨论的是二叉树。

1.树的概念

树是一种常见的非线性的数据结构。树的递归定义如下：

    树是n(n>0)个结点的有限集，这个集合满足以下条件：

     ⑴有且仅有一个结点没有前件（父亲结点），该结点称为树的根；

     ⑵除根外，其余的每个结点都有且仅有一个前件；

     ⑶除根外，每一个结点都通过唯一的路径连到根上。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后件（儿子结点）；

由上述定义可知，树结构没有封闭的回路。图6.1.2给出了树的几个示例：

    图6.1.2

    在树中，一个结点包含一个元素以及所有指向其子树的分支，其中除根结点外，有后件的结点称为分支结点。而没有后件的结点称为树叶。由树的定义可知，树叶本身也是其父结点的子树。如（图6．1.2（b））中，r为根起点，w，h，e，f，s，m，o，n，j，u为叶结点；从根r到结点i的唯一路径为rcti。

 一个结点的子树数目称为该结点的度。在（图6．1.2（b））中，结点i度为3，结点t的度为2，结点b的度为1。显然，所有树叶的度为0。所有结点中最大的度称为该树的度。（图6．1.2（b））中的树的度为3。

树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的后件在第二层，其余各层依次类推。即若某个结点在第k层，则该结点的后件均处在第k+1层。（图6．1.2（b））中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。（图6．1.2（b））中树的深度为5。

所谓森林，是指若干棵互不相交的树的集合。如图6．1.2（b）去掉根结点r，其原来的三棵子树Ta，Tb，Tc的集合{Ta，Tb，Tc}就为森林，这三棵子树的具体形态如图6．1.2（b）。

所谓有序树是指树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树。

2.树的表示方法和存储结构

树的表示方法很多。例如（图6．1.2）采用的就是自然界的树形表示法，常用的还有括号表示法：

先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：

同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如（图6．1.2（b））可写成如下形式

   （r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））

而树的存储结构有多种，其中使用较多的是链式存储结构。由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n 为树的度)个指针域共n+1个域组成，其表示方法如下：

        Const n=树的度；

        Type 

           treetype=↑node；                                            {结点类型}

               node=record

                    data：datatype；                                      {数据域}

                    next：array[1‥n] of treetype；           {指向各儿子的指针域}

                   end；

        Var 

         root：treetype；                                             {根结点指针}

例如图6．1.2（b）中的树，其多重链表为图6.1.3

图6.1.3

    显然，取树的度作为每个结点的链域数（即指向儿子结点的指针数)虽使各种算法简化，但会造成存储空间的大量浪费。因为可能有很多结点中存在空链域。容易验证，一棵具有n个结点且度为K的树中必存在n*(k-1)+1个空链域，因此需要寻找一种恰当的树形式，即要使每个结点的结构相同、又要尽可能减少存储空间的浪费，方便运算。下面将要看到，用二叉树来表示树，就能达到这个目的。

3.二叉树

二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个后件，且其子树有左右之分（次序不能任意颠倒）。下面给出二叉树的递归定义：

   二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：

   ⑴有一个特定的结点称为根；

   ⑵余下的结点分为互不相交的子集L和R，其中R是根的左子树；L是根的右子树；L和R又是二叉树；

由上述定义可以看出，二叉树和树是两个不同的概念：树的每一个结点可以有任意多个后件，且子树可以不分次序（除有序树外）；而二叉树中每个结点的后件不能超过2且子树有左右之分。我们称二叉树中结点的左后件为左儿子，右后件为右儿子。前面引入的有关树的一些基本术语对二叉树仍然适用。图6．1.4列出二叉树的五种基本形态：

图6.1.4

  满二叉树和完全二叉树是二叉树的两个特殊形态：

满二叉树： 如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。（例如图(6.1.5(a)）可以验证具有n个叶结点的满二叉树共有2n-1个结点。

   完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如（图6.1.5(b)））

图6.1.5

下面介绍二叉树的三个主要性质

性质1：在二叉树的第i（≥1）层上，最多有2i-1个结点

证明  数学归纳法

⑴i=1时只有一个根结点，即2i-1=20=1，结论成立；

    ⑵假设第k(i=k)层上最多有2k-1个结点；

    ⑶考虑i=k+1。由归纳假设，在二叉树第k层上最多有2k-1个结点，而每一个结点的度数最大为2，因此在第k+1层上最多有2．2k-1=2(k+1)-1=2i，结论成立。

综上所述，性质1成立。

性质2：在深度为k(k≥1)的二叉树中最多有2k-1个结点。

证明 

  由性质1，在二叉树第i层上最多有2i-1个结点，因此深度为k的二叉树最多有个结点。

性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。

证明

  设n0—二叉树的叶结点数；n1—二叉树中度为1的结点数； n2—二叉树中度为2的结点数

                     n=n0+n1+n2            （1）

由于二叉树中除了根结点外，其余每个结点都有且仅有一个分支进入。设 B为进入分支的总数，因此

                 n=B+1                （2）  

又由于所有的进入分支是由度为1和度为2的结点射出的，因此又有

                 B=n1+2n2               (3)

将（3）代入（2）得出

                     n=n1+2n2+1             (4)

比较（1）和（4），得出

                      n0=n2+1

即叶子数比度为2的结点数多1

4.树或森林转换成二叉树

⑴普通有序树转换成二叉树

    我们在§3．1中曾讲过，在用多重链表示普通树时，会浪费存储空间。另外，由于树中各结点的度各不相同，因此对树中各结点的搜索比较困难。在实际应用中，往往将普通树转化成二叉树，这种处理是极其有利的。假设所讨论的普通树为有序树T，则将其转化成二叉树T’的规则如下：

     ⑴T中的结点与T’中的结点一一对应；

     ⑵T中某结点N的第一个儿子结点为N1，则在T’中N1为对应结点N的左儿子结点；

     ⑶T中某结点N的第一个儿子结点N1以后的其它子结点，在T’中被依次链接成一串开始于N1的右儿子结点；

由上述转化规则可以看出，一棵有序树转化成二叉树的根结点是没有右子树的，并且除保留每个结点的最左分支外，其余分支应去掉，然后从最左的儿子开始依次连接该结点的全部儿子。例如将（图6.1.6（a））所示的普通有序树转换成二叉树(图6.1.6（b）)

图6.1.6

⑵森林转换成二叉树    

如果m棵互不相交的普遍有序树组成了森林F={T1,…Tm}。我们可以按下述规则将森林F转换成一棵二叉树B={root，LB，RB}：

   ⑴若F为空（m=0），则B为空树；

   ⑵若F非空（m≠0），则B的根root即为森林中第一棵树的根root(T1)；B的左子树LB是从T1的根结点的子树森林F1={T11，T12，…T1k}转换而成的二叉树；其右子树RB是从森林F2={T2，T3，…，Tm}转换成的二叉树。

图6.1.7给出了森林转换成二叉树的示例

图6.1.7

由此可见，森林转换成二叉树的方法为

   ⑴将各棵树的根相连；

   ⑵将森林中的每棵树转换成相应的二叉树；

   ⑶以第一棵树为轴心，顺时针粗略地旋转900；

5.二叉树的存储结构

二叉树的存储结构有两种形式

⑴顺序存储结构

    将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括

    数据值：          data

    父结点编号：      prt

    左儿子结点编号：  lch

    右儿子结点编号：  rch

满二叉树和完全二叉树一般采用顺序存储结构

    Const  m=树中结点数上限；

    Type

      node=record                                                          {结点类型}

            data：datatype；                                                  {数据值}

            prt，lch，rch：0‥m；                         {父结点、左儿子、右儿子编号}

           end；

      treetype=array[1‥m] of node；                              {二叉树的顺序表类型}

    Var 

     Tree：treetype；                                                        {二叉树}

例如，采用数组tree存储二叉树（图6.1.8）

图6.1.8

下面我们将普通有序树转换成二叉树，并使用顺序存储结构Tree存储转换结果。普通有序树的输入信息含n行，其中第i行（1≤i≤n）的元素依次为结点i的数据值ai。以后各元素为结点i的儿子序列，以0结束。若ai后仅含一个0，则说明结点i为叶子。例如（图6．1．6（ａ））的多叉树对应的输入信息为

’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’ 0

’t’ 13 14 0

’u’ 0

’ ’d’ 15 0

’e’ 0

’i’ 16 17 18 0

’j’ 0

’h’ 0

’m’ 0

’o’ 0

’h’ 0

转换过程如下：

 fillchar（tree，sizeof（tree），0）；                                         {二叉树初始化}

i←1；                                                            {从结点1开始输入}

while i≤n do                                      {若多叉树信息末输入处理完,则重复}

 begin

  读结点i的数据值ai；tree[i] ．data←ai；

　读结点i的第一个儿子序号j；

　if j<>0 then                                                         {若结点j非叶子}

begin

 tree[i]．lch←j；tree[j]．prt←i；                      {结点j 作为结点i的左儿子}

 p←j；                                           {从结点j 出发转换其它兄弟结点}

 repeat　

  读结点i的下一个儿子序号j；

if j<>0 then begin

            tree[p]．rch←j；tree[j]．prt←p；          {结点j 作为结点p的右儿子}

            p←j；

            end；{then}

 until j=0；                                       {直至处理完结点i的所有儿子信息}

end；{then}

i←i+1；换行；                                       {准备输入结点i+1的儿子信息}

end；{while}

例如（图6．1．6（ａ））的多叉树经上述转换运算后得出的tree数组如下：

⑵链式存储结构

    对于一般的二叉树，通常采用链式分配，即用二重链表表示一般的二叉树。这种链式分配即可以采用静态数据结构（数组），又可以采用动态数据结构（指针）。人们一般采用后者。由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域：

                 值域：     data

                 左指针域： lch

                 右指针域： rch

这种链表也称为二叉链表。二叉链表头指针bt指向二叉树的根结点

        Type

           bitrpetr=↑bnode；                                       {结点指针类型}

           benode=record                                               {结点类型}

                  data：datatype；                                          {值域}

                  lch，rch：bitreptr；                        {左指针域和右指针域}

                  end；

        Var

           bt： bitreptr；                                                {头指针}

例如用图6．1．9（b）所示的二叉链表存储二叉树（图6．1．9（a））

图6.1.9

构造二叉链表的方法取决于二叉树的性质。例如最优表达树、二叉排序树的构造各有其方法。我们将在树的应用举例中作以介绍。

6.树或森林的遍历

⑴二叉树的遍历

    所谓二叉树的遍历是指按照一定的规律不重复地访问二叉树中的每一个结点。在访问到每个结点时，可以取出结点中的信息，亦可以对结点作其它的处理，对于线性结构来说，遍历并非难事，但对二叉树来说，由于它是一种非线性结构，必须要找到一种完全而有规则的遍历方法，通过遍历得到二叉树中各个结点信息的线性序列。

    如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种组合：

         LDR、 LRD、 DLR、 DRL、RDL、 RLD

若再限定先左后右的次序，则只剩下三种组合

         LDR、  LRD、  DLR

这三种遍历规则分别称为中序遍历。后序遍历和前序遍历。下面分别介绍这三种遍历的方法。在讲解过程中，二叉树的存储采用动态的二重链表形式。

为了方便叙述，我们以图6．1.10为例，解释三种遍历规则。

   图6.1.10

①前序遍历

前序遍历的规则如下：

若二叉树为空，则退出。否则

   ⑴访问处理根结点；

   ⑵前序遍历左子树；

   ⑶前序遍历右子树；

     例如对于如（图6．1.10）所示的二叉树，前序遍历的过程为：先访问根结点A，再遍历其左子树，然后遍历其右子树。在遍历其左子树时，也按照前序规则，即先访问根结点B，然后遍历其左子树，最后遍历右子树，…，依次类推，直到根结点A的左子树的所有结点全部被访问完毕；再以同样的规则访问A的右子树中的所有结点；最后可以得到如下的前序遍历序列（简称前序序列）

       a b d e h i c f g

算法如下：

        procedure preorder(bt：bitreptr)；

          begin

if bt<>nil

             then begin

                   访问处理bt↑．Data；

                   preorder(bt↑．lch)；                              {递归遍历左子树}

                   preorder(bt．↑rch)；                              {递归遍历右子树}

                 end；{then}

             end；{preorder}

②中序遍历

中序遍历的规则如下：

      若二叉树为空，则退出；否则

        ⑴中序遍历左子树；

        ⑵访问处理根结点；

        ⑶中序遍历右子树；

若中序遍历（图6．1.10）中的二叉树，可以得到如下的中序序列：

                d b h e i a f c g 

算法如下：

        procedure inorder(bt：bitreptr)；

         begin

if bt<>nil

             then begin

                  inorder(bt↑．lch)；                                {递归遍历左子树}

                  访问处理bt↑．data；

                  inorder(bt↑．rch)；                                {递归遍历右子树}

                  end；{then}

         end；{inorder}

③后序遍历

后序遍历的规则如下：

     若二叉树为空，则退出；否则

       ⑴后序遍历左子树；

       ⑵后序遍历右子树；

       ⑶访问处理根结点；

   若后序遍历（图6．1.10）中的二叉树，可以得到如下的后序序列

               d h i e b f g c a

算法如下：

        procedure postorder (bt：bitreptr)；

          begin

if bt<>nil

             then begin 

                  postorder (bt↑．lch)；                             {递归遍历左子树}

                  postorder(bt↑．rch)；                              {递归遍历右子树}

                  访问bt↑．data；

                  end；{then}

          end；{postorder}

⑵普遍有序树的遍历

    仿照二叉树的前序遍历和中序遍历，可以定义普遍有序树的两种遍历顺序。由于普遍有序树中的子女数可能多于两个，因此不好仿照二叉树遍历中根与其女子的对称次序。

①先根次序遍历树

  先根次序遍历的规则如下：

     若树为空，则退出；否则先根访问树的根结点，然后先根遍历根的每棵子树。

例如，对（图6．1.6(a)）中的树进行先根遍历，可得到树的先根序列为

           r  a  w  x  d  h  e  b  f  c  s  t  i  m  o  n  j  u

若对（图6．1.6(b)）中的二叉树进行前序遍历，得到的前序序列与之相同。由此可见，当采用二叉链表作树的存储结构时，可借用二叉树的前序遍历实现树的先根遍历。

②后根次序遍历树

  后根次序遍历的规则如下：

     若树为空，则退出；否则先依次后根遍历每棵子树，然后访问根结点。

例如对（图6．1.6(a)）中的树进行后根遍历，可得到树的后根序列为

          w  h  d  e  x  a  f  b  s  m  o  n  i  j  t  u  c  r

若对（图6.1.6(b)）中的二叉树进行中序遍历，得到的中序序列与之相同。由此可见，当采用二叉链表作为树的存储结构时，可借用二叉树的中序遍历实现树的后根遍历。

⑶森林的遍历

若有多棵互不相交的普通有序树组成森林，则同样可以导出森林的两种遍历规则：

①先根遍历森林

  若森林非空，则可按下述规则遍历之

1访问森林中第一棵树的根结点；

2先根遍历第一棵树中根结点的子树森林；

3先根遍历其余树构成的森林；

②后根遍历森林

  若森林非空，则可按下述规则遍历之

1后根遍历森林中第一棵树的根结点的子树森林；

2访问第一棵树的根结点；

3后根遍历其余树构成的森林；

若对（图6．1.7(a)）中的森林进行先根遍历和后根遍历，则分别得到森林的先根序列为A B C D E F G H I J ；后根序列为B C D A F E H J I G 。

    由森林与二叉树之间的转换规则可知，当森林转换成二叉树时，其第一棵树根结点的子树森林转换成左子树，剩余树的森林转换成右子树。由此得出森林的先根遍历和后根遍历即为其对应的二叉树的前序遍历和中序遍历。例如，对（图6．1.7(c)）中的二叉树分别进行前遍历和中序遍历，亦可得出对应森林（图6．1.7(a)）的先根序列和后根序列。

【例题6.1.1】求先序排列

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树节点用不同的大写字母表示，长度≤8）。

输入数据：中序与后序排列，输入数据不需判错

输出数据：先序排列

输入输出样例

输入：BADC  BDCA

输出：ABCD

题解

遍历二叉树（图6.1.11）有三种规则：    

  先序遍历：根—左子树—右子树；

  中序遍历：左子树—根—右子树；

  后序遍历：左子树—右子树—根；

图6.1.11

由上述遍历规则可以看出，后序排列的最后一个字符为根，中序排列中位于该字符左侧的子串为左子树中序遍历的结果；中序排列中位于该字符右侧的子串为右子树中序遍历的结果。设

  中序排列s’=s1’…sk’ …sn’

  后序排列s”=s1”……sn”

显然，后序排列中的sn”为二叉树的根。按照先序遍历的规则输出sn”。在中序排列中与sn”相同的字符为sk’。若k>1，说明左子树存在，位于sk’左侧的子串s1’…sk-1’为左子树中序遍历的结果，后序排列中的前缀s1”…sk-1”为左子树后序遍历的结果；若k中序排列s’= ’dbeafc’                   后序排列s”= ’debfca’

这棵二叉树的根为a。左子树中序遍历的结果为’dbe’， 左子树后序遍历的结果为’ deb’，由此得出二叉树的左根为b，b的左右儿子分别为d和e；右子树中序遍历的结果为’fc’， 右子树后序遍历的结果亦为’fc’。 由此得出二叉树的右根为c，c仅有左儿子f，该二叉树由图6.1.12所示：

图6.1.12

对应的先序排列为s= ’abdecf’。

按照上述遍历规则编写递归程序solve(s1，s2)。其中s1和s2分别为二叉树的中序排列和后序排列。Solve过程计算和输出s1和s2对应的先序排列：

procedure solve(s1，s2:string)；   { 计算和输出中序排列s1和后序排列s2对应的先序排列}

var

  k:integer；

    begin

      if length(s2)=1                                {若当前子树仅剩一个节点，则输出}

      then 输出s2

      else begin

            k←pos(s2[length(s2)]，s1)；                     {在中序排列中寻找子树根}

            输出子树根s1[k]；

            if k>1                                   {若左子树存在，则递归遍历左子树}

then solve(copy(s1，1，k-1)，copy(s2，1，k-1))；

            if k               then solve(copy(s1，k+1，length(s1)-k)，copy(s2，k，length(s2)-k))；

           end；{else}

    end；{ solve }

【例题6.1.2】根据根据前、中序遍历求后序遍历

  约定一棵二叉树的前序遍历和中序遍历序列，用你熟悉的程序设计语言生成该二叉树，并将其后序遍历打印出来。为便于编程，二叉树的结点用单个大写英文字母表示，且结点互不重复。比如，输入前序遍历序列为DBACPMZX，中序遍历序列为ABCDMPXZ，应生成的二叉树结构如图6.1.13所示：

图6.1.13 

应输出的后序遍历序列为ACBMXZPD

   注意：你的程序应能鉴别任何的错误输入。

题解

1鉴别错误输入

设

   predstr—前序串；           s1—前序串的字符集；

   midstr—中序串；           s2—中序串的字符集；

predstr串与midstr串必须同时满足下述三个条件方可对应同一棵二叉树：

●predstr串与midstr串的长度相等；

●两串的字符为{ ’A’‥’Z’}的子集且各不相同；

●在predstr串中的字符必须在midstr串出现；

    判别输入合法性的过程由布尔函数correct完成。若输入合法(即predstr串与midstr串可对应同一棵二叉树)，则返回true；否则返回false。

   fuction correct：boolean；

    begin 

     correct←false；

     if length(predstr)=length(minstr)                       {若两序列的长度相同}

       then begin

            s1←[]；                                        {前序串的字符集初始化}

            for i←1 to length(predstr) do               {分析前序串的每一个字符}

            if (predstr[i] s1)or(predstr[i] [ ’A’‥’Z’])

             then exit             {若前序串中字符重复或出现非法字符，则返回false}

             else s1←s1+[predstr[i]]；           {否则当前字符进入前序串的字符集}

            s2←[]；                                        {中序串的字符集初始化}

            for i←1 to length(midstr) do 

            if (midstr[i] s1)or(midstr[i] s2)

              then exit {若中序串的当前字符非前序串字符或者为重复字符，则返回false}

              else s2←s2+[midstr[i]]；            {否则当前字符进入中序串的字符集}

                correct←true；                                     {返回输入合法标志}

                end；{then}

        end；{correct}

2构造两个线性序列对应的二叉树

    若给出一棵二叉树的前序遍历和中序遍历，那么这两个线性序列可以唯一对应一棵二叉树。问题是如何由这两个线性序列推导出对应的二叉树呢？

设

    predstr= ’ABCD’

    midstr= ’BCAD’

    由前序遍历和中序遍的递归定义可以看出，前序遍历的首字符是树的根，例如上述前序序列中的’A’。我们根据该字符在中序序列中的位置i将中序序列一分为二，左端序列(即第1～i-1个字符)为左子树中序遍历的结果，例如上述中序序列中的’BC’； 右端序列(即第i+1个字符～尾字符)为右子树中序遍历的结果，例如上述中序序列中的’D’；前序序列的第2～i个字符为左子树的前序遍历的结果，例如上述前序遍历中的’BC’；前序序列的第i+1至尾部的字符为右子树前序遍历的结果。例如上述前序遍历中的’D’。这样便分别求出了左子树的根和左子树的前序序列、左子树的中序序列，右子树的根和右子树的前序序列、右子树的中序序列。再运用上述方法继续分别求解左子树和右子树。如此反复，直至对应的二叉树求出为止。显然，这一求解过程是递归的。根据上述思想，我们设计一个递归函数maketree。该函数的输入值参为前序序列和中序序列两个字串，返回的函数值为指向根结点的地址指针。

   设二叉树的定义为

       Type

         Link=↑node；                                                {结点的指针类型}

         node=record                                                 {结点的数据类型}

              val：char；                                                       {值域}

              left,right：link；                                          {左、右指针}

              end；

     var

         root：link；                                             {二叉树的根结点指针}

function maketree(predstr, midstr)：link；{输入前序串和中序串，计算和返回对应的二叉树}

 var

  root：link；                                                      {子树的根结点指针}

  s1，s2：string；                                               {子树的前序串和中序串}

 begin

  new (root)；                                                      {为子树根申请内存}

  root↑．val←predstr[1]；                                                 {设定根值}

  i←pos(root↑．val,midstr)；

  if i=1 

   then root↑．left←nil                                                {左子树为空}

else begin

    s1←copy(predstr,2，i-1)；

    s2←copy(midstr，1，i-1)；                        {计算左子树的前序串和中序串}

    root↑．left←maketree(s1,s2)；                                    {构造左子树}

    end；{else}

  if i=length (midstr)

   then root↑．rigth←nil                                                {右子树为空}

   else begin

    s1←copy(predstr,i+1，length(predstr)-i)；

    s2←copy(midstr，i+1，length(midstr)-i)；         {计算右子树的前序串和中序串}

        root↑．rigth←maketree(s1,s2)；                                   {构造右子树}

        end；{else} 

   maketree←root；                                                       {返回根结点}

end；{maketree}

   我们通过调用maketree(’ABCD’,’BCAD’)计算对应的二叉树，计算过程如图6.1.14所示

图6.1.14

3 输出二叉树的后序序列

    由maketree函数求出了前序序列和中序序列对应的二叉树的根结点指针后，便可以根据后序遍历的递归定义编写程序，输出这两棵二叉树的后序序列

        procedure out (root)；

          begin

if root<>nil

            then begin

                 out (root↑．left)；                                 {递归遍历左子树}

                 out(root↑．right)；                                 {递归遍历右子树}

                 输出root↑．val；

                 end；{then}

          end；{out}

4 算法流程

将上述子程序组合起来，便可以得出算法流程

        repeat

          输入前序序列predstr；

          输入中序序列 midstr；

        until correct；

        root←make(predstr,midstr)；

        out(root)；

【例题6.1.3】单词排列

   试将英文中出现的单词按词典顺序打印出来，同时应注明每个单词在该段文章中出现的次数。

输入数据：

  文章信息。其中’，’、’ ’和回车符为单词间的分隔符，文章以’.’结束。

输出数据：

  以词典顺序排列的单词列表。每行为一个单词及其该单词的频率。

输入/输出示例：

  输入：

    one day people will be able to run a kilometre in two minutes．

  输出：

             a         1

             able      1

             be        1

             day       1

             in        1

             kilometre 1

             minutes   1

             one       1

             people    1

             run       1

             to        1

             two       1

             will      1

题解

1.构造单词链表—inputword过程

    逐一输入单词，构造一个链表，将单词存放在链表中（链表中的单词互不重复），并统计单词的使用频率。单词链表定义为

           Type

             Link=↑linkword；                                    {单词链表的指针类型}

             Linkword=record                                     {单词链表的结点类型}

                      w：string；                                               {单词}

                      t：integer；                                          {单词频率}

                      next：link；                                          {后继指针}

                      end；

            Var 

h：link；                                            {单词链表的首指针}

单词链表的结构如图6.1.15所示：

图6.1.15

单词链表的构造过程如下：

        procedure inputword； 

          function words：string；                                    {读一个单词}

           begin

             s←’’； read(ch)；

             while ch{ ’ ’，#13，’，’} do 

               begin 

                s←s+ch；  read(ch)；

               end；{while}

             words←s；

            end；{words}

         begin

           wd←words；                                                {读一个单词}

           while wd<> ’．’ Do                              {若文章末输入完，则循环}

            begin

             p←h；                                     {在单词链表中搜索重复单词}

             while (p<>nil)and(p↑．w<>wd) do p←p↑．next；

             if p=nil 

              then begin                    {若单词不重复，则构造单词链表的新结点}

                   new(g)； g↑．w←wd； g↑．t←1； g↑．next←h； h←g；

                   end{then}

              else p↑．t←p↑．t+1；                     {否则计算重复单词的频率}

             wd←words；

           end；{while}

         end；{inputword}

2.构造二叉排序树—createtree过程

   所谓二叉排序树是指具有下列性质的非空二叉树

      ⑴若根结点的左子树不空，则左子树的所有结点值均小于根结点值；

      ⑵若根结点的右子树不空，则右子树的所有结点值均不小于根结点值；

      ⑶根结的左右树也分别为二叉排序树；

二叉排序树的定义如下

          Type

            tree=↑treeword；                               {二叉排序树结点的指针类型}

            treeword=record                                    {二叉排序树的结点类型}

                      w：string；                                               {单词}

                      t：integer；                                          {单词频率}

                      l，r：tree；                                {左儿子、右儿子指针}

                     end；

     Var

       Rt：tree；                                             {二叉排序树的根结点指针}

我们顺序搜索h链表中的每一个单词，并按下述规则生成二叉排序树：

      ⑴令a1为二叉树的根；

      ⑵若a2      ⑶对a3、a4、……、an递归重复步骤⑵；

 例如图6.1.16给出了一个h链表：

图6.1.16

按照上述规则，构造出图6.1.17中的二叉排序树

图6.1.17

二叉排序树的构造过程如下：

        procedure createtree；

          begin

            new(rt)；                         {令h表中的第1个单词为二叉排序树的树根}

            with rt↑do

             begin

              w←h↑．w；  t←h↑．t；  l←nil；  r←nil；

             end；{with}

            q←h↑．next；                                  {取h表中的下一个单词结点}

            while q<>nil do                         {若h表中的单词结点未取完，则循环}

             begin

              p←rt；

              new(r)；                                          {建立二叉树的新结点r}

              r↑．l←nil；  r↑．r←nil；  r↑．w←q↑．w；  r↑．t←q↑．t；

              f←true；                                         {设r未插入二叉树标志}

              while f do 

               begin

                if q↑．w                 then                                  {顺左指针方向寻找r的插入位置}

                   if p↑．l<>nil then p←p↑．l

                                  else begin p↑．l←r；f←false；end{else}

                 else                  {q↑．w≥p↑．w时顺右指针方向寻找r的插入位置}

                    if p↑．r<>nil then p←p↑．r

                                   else begin p↑．r←r； f←false； end；{else}

               end；{while}

               q←q↑．next；                                 {取h表的下一个单词结点}

              end；{while}

            end；{createtree}

3、中序遍历二叉排序树（outputtree过程）

对二叉排序树rt进行中序遍历，通过中序遍历输出按词典顺序排列的单词表：

          procedure outputtree (p：tree)；

           begin

             if p↑．l<>nil then outputtree (p↑．l)；{若左子树非空，则递归遍历左子树}

              输出p↑．w和p↑．t；

             if p↑．r<>nil then outputtree (p↑．r)；{若右子树非空，则递归遍历右子树}

           end；{outputtree}

 综合上述分析。可得出该题的算法流程：

        inputword；

if h<>nil then

          begin

           creatree；

           outputtree(rt)；

          end；{then}

【例题6.1.4】最优二叉树

在具有n个带权叶结点的二叉树中，使所有叶结点的带权路径长度之和（即二叉树的带权路径长度）为最小的二叉树，称为最优二叉树（又称最优搜索树或哈夫曼树），即最优二叉树使

      （wk—第k个叶结点的权值；pk—第k个叶结点的带权路径长度）

达到最小。例如（图6.1．18）为三棵二叉树，它们都有4个叶结点a、b、c、d，其权值分别为7、5、2、4。

图6.1.18

显然（图6．1.18(c)）所示的二叉树的带权路径长度和最小，并且可以验证，它恰为最优二叉树。

输入

n

n个叶结点的权w1w2…wn

输出

最优二叉树的带权路径长度

题解

从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。路径上的分支数目称为路径长度。树的路径长度是从树根到每一个叶子结点的路径长度之和。完全二叉树是路径长度最短的树。如果考虑带权的结点，则结点的带权路径长度即为从该结点到树根之间的路径长度与该结点权的乘积。树的带权路径长度为树中所有带权叶结点的带权路径长度之和。最优二叉树的带权路径长度最小。最优二叉树在实际生活中很有应用价值，例如全校学生的成绩由百分制转换成五等分制，在五个等次以上的分布不均匀，分布规律如表6.1.2：

现有n=10000个数据。图6.1.19分别列出两种判定转化过程：

图6.1.19

若按照（图6．1.19(a) ）的判定过程进行转换，则有80%的数据至少要进行3次比较才能得出结果。完成10000个数据转换的比较次数

             k=10000*（1*5%+2*15%+3*40%+4*(30%+10%)）=31500。

若按照（图6．1.19(b)）的判定过程进行转换，则有20%的数据需要进行3次比较才能得出结果，而有80%的数据至多仅需要进行2次比较就可得出结果。完成10000个数据转换的比较次数

             k=10000*（2*（10%+30%+40%）+3*（5%+15%））=22000次

显然后者的判定过程的效率比前者高。还有没有更好的判定过程可使比较次数进一步减少呢？回答是否定的，即（图6．1.19(b)）所示的判定过程是最优的。故称该二叉树为最优二叉树，这棵树的带权路径长度为（2*（10%+30%+40%）+3*（5%+15%））=2.2。

    假定给出n个结点ki(i=1‥n)，其权值分别为wi(i=1‥n)。要构造以此n个结点为叶结点的最优二叉树，其构造方法如下：

    首先，将给定的n个结点构成n棵二叉树的集合F={T1，T2，……，Tn}。其中每棵二叉树Ti中只有一个权值为wi的根结点ki，其左、右子树均为空。然后做以下两步

    ⑴在F中选取根结点权值最小的两棵二叉树作为左右子树，构造一棵新的二叉树，并且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和；

     ⑵在F中删除这两棵二叉树，同时将新得到的二叉树加入F中；

重复⑴、⑵，直到在F中只含有一棵二叉树为止。这棵二叉树便是最优二叉树。

以上构造最优二叉树的方法称为哈夫曼（huffmann）算法。

例如：给定五个结点k1，k2，k3，k4，k5，其权值分别为16、2、18、16、23。构造最优二叉树的过程如下：

⑴构造初始集合F，F中各二叉树根结点的权值分别为16，2，18，16，23（图6.1.20）：

图6.1.20

⑵以具有权值16及2的根结点的两棵二叉树为左、右子树，构造一棵根权值为18的新二叉树，并从F中删去这两棵二叉树（图6.1.21）：

图6.1.21

⑶以同样的方法，得到一个新二叉树的集合F，其根结点的权值分别为23，18，34（图6.1.22）：

图6.1.22

    ⑷ 又得到一个新二叉树的集合F，其根结点的权值分别为34，41（图6.1.23）：

图6.1.23

⑸最后得到最优二叉树（图6.1.24），其根结点的权值为75，结点数为2*5-1=9。

图6.1.24

    在最优二叉树中非叶结点的度均为2，为满二叉树，因此采用顺序存储结构为宜。如果带权叶结点数为n个，则最优二叉树的结点数为2n-1个。由此得出最优二叉树的定义

       Const

        n=叶结点数的上限；

        m=2*n-1；                                                 {最优二叉树的结点数}

       Type

        node=record                                                        {结点类型}

             data： integer；                                                   {权值}

             prt，lch，rch：0‥m；                                {父指针和左、右指针}

             end；

        wtype=array[1‥n] of integer；                           {n个叶结点权值的类型}

        treetype=array[1‥m] of node；                          {最优二叉树的数组类型}

       Var

        tree：treetype；                                                  {最优二叉树}

        bt：integer；                                               {最优二叉树头指针}

        w：wtype；                                                 { n个叶结点的权值}

在最优二叉树的顺序存储结构中前n个结点为叶结点。

构造最优二叉树的算法如下：

procedure hufm (w：wtype； var tree：treetype； var bt： integer)；

  function min (h：integer)：integer；{在前h个结点中选择父指针为0且权值最小的结点min}

   begin

     min←∞； 

     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；{then}

     min←i；

   end；{min}

  begin

   fillchar (tree，sizeof(tree)，0)；                                 {构造初始集合F}

   for i：=1 to n do tree[i]．data←w[i]；

   for k：=n+1 to m do                                                {构造最优二叉树}

     begin                                               {计算k为根的左儿子和右儿子}

      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；{for}

   bt←m；                                                    {设置最优二叉树的根序号}

 end；{hufm}

    在主程序中，首先输入结点数n和n个叶结点的权值w1…wn；然后通过调用过程hufm (w，tree， bt)计算最优二叉树tree和根序号bt。Tree[bt].data即为最优二叉树的带权路径长度。

§6.2 图

    图是较线性表和树更为复杂的一种数据结构。在这种数据结构中，数据结点间的联系是任意的，因此它可以更广泛地表示数据元素之间的关系。可以说，线性表和树是图的特例。实际生活中的许多事物可以抽象成图的形式。例如（图6．2．1）是一个公路网。为了方便地表示交通信息，我们用结点代表城市，每条边代表连接两个城市间的公路，边长的权表示公路长度。这种公路网的表现形式就是属于图的数据结构。

图6.2.1

图结构在人工智能、数学、物理、化学、计算机科学等许多领域被广泛应用。奥林匹克信息学竞赛的许多试题，亦需要用图来描述数据元素间的联系。

1. 图的基本概念和存储结构

    如果数据元素集合D中的各元素之间存在任意的前后件关系R，则此数据结构G=（D，R）称为图。如果将数据元素抽象为结点，元素之间的前后件关系用边表示，则图亦可以表示为G=（V，E），其中V是结点的有穷（非空）集合，E为边的集合。如果元素a是元素b的前件，这种前后件关系对应的边用(a，b)表示，即(a，b)∈E。

    在图G=（V，E）中，如果对于任意的a，b∈V，当(a，b)∈E时，必有（b，a）∈E（即关系R对称），对称此图为无向图；如果对于任意的a，b∈V，当(a，b)∈E时 ，(b，a)∈E未必成立，则称此图为有向图。在有向图中，通常用带箭头的边连接两个有关联的结点（方向由前件指向后件）；而对一无向图，用不带箭头的边连接两个有关联的结点。例如（图6．2．2（A））为无向图，（图6．2．2（B））为有向图。

图6.2.2

     在具有n个结点的无向图中，边的最大数目为。而边数达到最大值的图称为无向完全图。（图6．2．2(A)）所示的图是无向完全图。

    在无向图中一个结点相连的边数称为该结点的度，例如（图6．2．2(A)）中结点1、结点2、结点3、结点4的度分别为3。有向图中一个结点的后件个数称为该结点的出度，其前件个数称为该结点的入度。一个结点的入度和出度之和称为该结点的度。图中结点的最大度数称为图的度。例如（图6．2．2(B)）中结点1的出度和入度分别为1，结点1和的结点1度都为2。整个图的度为2。

    在图G=（V，E）中，如果对于结点a，b，存在满足下述条件的结点序列x1……xk(k>1)

        1 x1=a，xk=b

        2 (xi，xi+1)∈E         i=1‥k-1

则称结点序列x1=a，x2，…，xk=b为结点a到结点b的一条路径，而路径上边的数目k-1称为该路径的长度，并称结点集合{x1，…，xk}为连通集。如果一条路径上的结点除起点x1和终点xk可以相同外，其它结点均不相同，则称此路径为一条简单路径。（图6．2．2(A)）中v1→v2→v3是一条简单路径，v1→v3→v4→v1→v3不是简单路径。x1=xk的简单路径称为回路（也称为环）。例如（图6．2．2(B)）中，v1→v2→v1为一条回路。

    在一个有向图或无向图中，若存在一个结点w，它与其他结点都是连通的，则称此图为有根图，结点w即为它的根。（图6．2．2(A)）为有根图，v1、v2、v3、v4都可以作为根；（图6．2．2(B)）亦为有根图，v1或v2为它的根。若对于有向图的任意两个结点vi、vj间（vi≠vj），都有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称该有向图是强连通的。有向图中强连通的最大子图称为该图的强连通分支。（图6．2．2(B)）不是强连通的，因为v3到v2不存在路径。它含有两个强连通分支，如（图6．2．3）所示。

图6.2.3

    对于无向图而言，若其中任两个结点之间的连通，则称该图是连通的。一个无向图的连通分支定义为此图的最大连通子图。（图6．2．2(A)）所示的图是连通的，它的最大连通子图即为其本身。

    由于图的结构复杂且使用广泛，所以其存储结构也是多种多样的，对应于不同的应用问题可有不同的方法存储。这里，仅介绍其中两种：

1.图的相邻矩阵表示法

    相邻矩阵是表示结点间相邻关系的矩阵。若G=（V，E）是一个具有n个结点的图，则G的相邻矩阵是如下定义的二维数组A，其规模为n*n

图6.2.4

图6．2．4中的图G1和图G2对应的相邻矩阵分别为A1、A2：

        A1=    A2=

     由相邻矩阵A1和A2可以明显地看出，无向图的相邻矩阵A1[i，j]=A1[j，i](1≤i，j≤n)且对角线上的A[i，i]均为0（或）。正因为如此，在实际存储相邻矩阵时只需存储其上三角(或下三角)的元素。因此具有n个结点的无向图，其相邻矩阵的存储容量可节约至。而有向图的相邻矩阵中A2[i，j]不一定与A2[j，i](1≤i，j≤n)相同，且图中出现自反边时其对角线上的A2[i，i]也不一定是0（或）。

用相邻矩阵表示图，容易判定任意两个结点之间是否有边相联，并容易求得各个结点的度数。对于无权无向图的相邻矩阵，第i行元素值的和就是Vi的度数；对于无权有向图的相邻矩阵，第i行元素值的和就是Vi的出度，第i列元素值的和就是Vi的入度；对于有权无向图的相邻矩阵，第i行（或第i列）中元素值<>0的元素个数就是Vi的度数；对于有权有向图的相邻矩阵，第i行中元素值<>0的元素个数就是Vi的出度；第i列元素值<>0的元素个数就是Vi的入度。在无权有向图或无向图中，判定两个结点Vi、Vj之间是否存在长度为m的路径，只要考虑Am=A*A*……*A（m个A矩阵相乘后的乘积矩阵）中（i，j）的元素值是否为0就行了。

2.图的邻接表表示法

    用相邻矩阵表示图，占用的存储单元数只与结点数有关而与边数无关。一个含n个结点的图，若其边数比n2多得多，那么其相邻矩阵是一个稀疏矩阵，占用许多空间来存储0（或）当然是无端浪费。如果用邻接表表示法来存储图，则占用的存储单元既与图的结点数有关，又与边数有关。同样是n个结点的图，如果边数少，则占用的存储单元也少。

    同邻接表法表示图需要保存一个顺序存储的结点表和n个边表（每个边表为一个单链表，存储与一个结点相连的所有边的信息）。结点表的每个表目对应于图的一个结点，包括：

      ⑴结点信息，即

●与该结点相连的边数（m）；

●访问标志（visited）；

      ⑵边表的首指针（firstarc）。图中每个结点都有一个边表，其中每一个结点对应于与该结点相关联的一条边，包括

●与此边相关联的另一个结点序号（v）；

●若为带权图的话，该边的权值（w）；

●指向边表的下一个结点的后继指针（nextarc）；

邻接表的定义如下：

        const max=图的结点数上限；

         Type

           arcptr=↑arcnode；                                           {边表的指针类型}

           arcnode=record                                              {边表的结点类型}

                   v：integer；                                {关联该边的另一端点序号}

                   nextar：arcptr；                                     {边表的后继指针}

                    w：real；                                             {该边的权值}

                   end；

        vexnode=record                                              {结点表的表目类型}

                m：integer；                                       {与该结点相连的边数}

                visited：boolean；                                            {访问标志}

                firstarc：arcptr；                                         {边表的首指针}

                end；

         adjlist=array[1‥max]of vexnode；                                    {邻接表类型}

     var

        dig：adjlist；                                                          {邻接表}

        n,e ：integer；                                                   {结点数和边数}

用邻接表结构存贮图的过程如下：

       读n和e；

       for i←1 to n do                                                   {结点表初始化}

        begin

            with dig[i] do 

             begin 

              m←0；firstarc←nil；visited←false；

             end；{with}

        end；{for}

       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←wjk；nextarc←dig[j]．firstarc；

           end；{with}

          dig[j]．firstarc←q；

         end；{for}

例如图6．2．5(a)的有向图G，可由图6．2．5(b)中的邻接表表示：

图6.2.4

    用相邻表表示图，不仅是当e<2. 图的遍历和生成树

⑴图的遍历

    给出一个图G和其中任意一个结点V0，从V0出发系统地访问G中所有结点，每一个结点被访问一次，这就叫图的遍历。遍历图的结果是按访问顺序将结点排成一个线性序列。遍历图的算法是求解图的连通性问题、拓朴排序和求关键路径等算法的基础。通常有两种遍历方法：深度优先搜索和广度优先搜索，它们对无向图和有向图都适用。

①深度优先搜索

  深度优先搜索类似于树的前序遍历，是树的前序遍历的推广。

    假设初始时所有结点未曾被访问。深度优先搜索从某个结点V0出发，访问此结点。然后依次从V0的未被访问的邻接点出发深度优先遍历图，直至图中所有和V0有路径相连的结点都被访问到。若此时图中尚有结点未被访问，则另选一个未曾访问的结点作起始点，重复上述过程，直至图中所有结点都被访问为止。换句话说，深度优先搜索遍历图的过程是以V0为起始点，由左而右，依次访问由V0出发的每条路径。

    例如以（图6．2．5(a)）中的有向图G为例，从v3出发，按深度优先搜索的顺序遍历，得到的结点序列是

              v3→v2→v1→v5→v4

从vi出发，深度优先搜索的递归过程如下：

         procedure dfs (i：integer)；

           begin

             访问处理结点i；

             dig[i]．visited←true；                                     {置vi 已访问标志}

             q←dig[i]．firstarc；                    {按深度优先搜索的顺序遍历vi所有子树}

while q<>nil do

               begin

                if dig[q↑．v]．visited=false then dfs(q↑．v)；

                q←q↑．nextarc；

               end；{while}

             end；{dfs}

调用一次dfs(i)，可按深度优先搜索的顺序访问处理结点i所在的连通分支（或强连通分支）。整个图按深度优先搜索顺序遍历的过程如下：

      procedure traver1；

        begin

         for i←1 to n do dig[i]．visited←false；                     {置所有结点未访问标志}

         for i←1 to n do if dig[i]．visited=false then dfs (i)； {深度优先搜索每一个未访问的结点}

        end；{traver1}

②广度优先搜索

  广度优先搜索类似于树的按层次遍历的过程。

    假设从图中某结点v0出发，在访问了v0之后依次访问v0的各个未曾访问的邻接点，然后分别从这些邻接点出发按广度优先搜索的顺序遍历图，直至图中所有可被访问的结点都被访问到。若此时图中尚有结点未被访问，则任选其中的一个作起始点，重复上述过程，直至图中所有结点都被访问到为止。换句话说，按广度优先顺序搜索遍历图的过程是以v0为起始点，由近及远，依次访问和v0有路径相连且路径长度为1，2，3……的结点。

    假如以（图6．2．5(a)）中的有向图为例，从v3出发按广度优先搜索的顺序遍历，得到的结点序列是v3→v2→v4→v1→v5

由于队列“先进先出”的存取规则与广度优先搜索的遍历顺序相吻合，因此使用了一个工作队列q，按访问的先后顺序存储被访问过的结点序号。从结点vi出发广度优先搜索的过程如下：

    procedure bfs (i：integer)；

      begin

        访问处理结点i；

        dig[i]．visited←true；                                          {置vi 已访问标志}

        结点i进入队列q；

        while  队列q非空do 

         begin 

          从队列q中移出队首元素v；

          p←dig[v]．firstarc；                                {依次访问v的所有相邻结点}

while p<>nil do

           begin 

             if dig[p↑．v]．visited=false

               then begin

                   访问p↑．v； dig[p↑．v]．visited←true；

                   p↑．v进入队列q；

                   end；{then}

              p←p↑．nextarc；

            end；{while}

         end；{while}

      end；{bfs}

调用一次bfs(i)可按广度优先搜索的顺序访问处理结点i所在的连通分支（或强连通分支）。整个图按广度优先搜索顺序遍历的过程如下：

         procedure traver2；

           begin

           for i←1 to n do  dig[i]．visited←false；                  {置所有结点未访问标志}

           for i←1 to n do if dig[i]．visited=false then bfs[i]；{广度优先搜索每一个未访问的结点}

           end；{traver2}

⑵图的生成树

    若图是连通的无向图或强连通的有向图，则从其中任一个结点出发，调用dfs或bfs后便可以系统地访问图中所有结点；若图是有根的有向图，则从根出发通过调用dfs或bfs亦可以系统地访问遍历所有结点。在这种情况下，图中的所有结点加上遍历过程中经过的边所构成子图称作图的生成树。图6.2.6列举了图的生成树的几个示例：

图6.2.6

对于不连通的无向图和不是强连通的有向图，若无根，或者若从根外的任意结点出发，一次调用bfs或dfs后一般不能系统地访问遍历所有结点，而只能得到以出发结点为根的连通分支（或强连通分支）的生成树。要访问其它结点需要从没有访问过的结点中找一个结点作为起始点，再次调用bfs或dfs，这样得到的是生成森林。例如图6．2．6（b）所示的有向图G2非连通，v3是该图的根。我们分别从v1、v3出发作二次深度优先搜索，得到G2的生成森林（如图6.2.7）

图6.2.7

    由此可以看出，图的生成树不是唯一的，不同的搜索方法可以得出不同的生成树，即便是同一种搜索方法，但出发点不同亦可导致不同的生成树。具有n个结点的带权连通图，其对应的生成树有n-1条边。

【6.2.1】计算最少的公路造价

现有n个城市间的交通网，边上的权是公路造价，任一对城市都是可以连通。现在要用公路把n个城市联系起来，这至少需要修筑n-1条公路。如何设计可使得这n条公路的总造价最少。例如（图6．2．８.(a)）为6个城市间的交通网，边上的权是公路造价。修筑5条公路的方案如图6．2．８(b)）和（图6．2．８(c)

图6.2.8

输入

  顶点数n和边数e；

  以下有e行，每行一条边的两个顶点；

输出

  n-1行，每行为连接一条公路的两个城市序号；

题解

n个城市间的交通网是一张具有n个顶点的带权连通图，其对应的生成树有n-1条边。由此引出这样一个问题：如何找一个带权连通图的最小生成树，即各边的权的总和为最小的生成树。下面我们来讨论最小生成树的算法。

⑴数据结构

   　A—连通图的相邻矩阵。若Vi包括进生成树，则A[i，i]←1；若包括进生成树，则A[i，j]←-A[i，j](1≤i，j≤结点数n)。算法结束时，A矩阵中为负的元素指示最小生成树的边。

     t—存储相邻矩阵A的下三角元素。其中t[+j]存储A[i，j](j≤i)。t数组的长度为。显然

          若t[]=1，则vi在生成树中；

          若t[+j]取负时，则表明(i，j)边在生成树中。

     min—当前待扩展边的最小权。

⑵构造最小生成树

    从任意结点开始（不妨设为vn）构造最小生成树：首先把这个结点包括进生成树里，然后在那些其一个端点已在生成树里、另一端点还未在生成树里的所有边中找出权最小的一条边，并把这条边、包括不在生成树的另一端点包括进生成树，…。依次类推，直至将所有结点都包括进生成树为止。当有两条具有同样最小权的边可供选择时，选哪条都行。因此最小生成树的形式不是唯一的。例如（图6．2．８(b)）和（图6．2．８(c)）就是(图6．2．８(a))的两棵形式不同的最小生成树，但它们权的总和相等。

  我们可以通过反证法证明上述算法的正确性：

假设vx，vy∈V，(vx，vy)∈E，vx∈最小生成树T’，vy最小生成树T’，(vx，vy)的权值在待扩展边集中最小，而最终生成的最小生成树中并不包含这条边。由于T’是连通的，因此有从vx到vy的路径vx，…，vy。把边（vx，vy）加入Ｔ’中得到一个回路vx…vy，vx。子路径vx…vy中必有边e’=(vp，vq)，其中vp∈T’，vqT’，由条件可知W(e’)>W(e)。从回路中去掉e’，回路打开，成为另一棵生成树T”且各边权和不大于T’的各边权和，因此T”是一棵包括边（vx，vy）的最小生成树，与假设矛盾。

下面给出构造最小生成树的算法：

       for i：=1 to  do t[i]←∞ ；

       for i：=1 to n do t[]←0；                       {所有结点未包括进生成树}   

       for i：=1 to 边数e do                                  {输入相邻矩阵的下三角元素}

        begin

          读第i条边；

          if x>y then t[]←wxy

                         else t[]←wxy；

        end{for}       

       t[]←1；       　　　                               {vn进入最小生成树}

       for k：=2 to n do    　　　                         {顺序构造最小生成树的n-1条边}

        begin

         min←∞；

         for i：=1 to n do　 {搜索那些其一个端点已在生成树里、另一端点还未在生成树里的边}

           if t[]=1  　　　　　　　　　　　　　　　　　　　 {若vi在生成树中}

             then begin

                 for j：=1 to n do 

 　　　           if t[]=0         　　　　　　　　　　　 {若vj不在生成树中}

  　　　              then begin

        　　　            if j                         　　　else l←+i；

if t[l]的权目前最小，则记下}

                               begin min←t[l]；p←l；q←j；end；{then}

             　　　　　   end；{then}

              　　end；{then}

         t[]←1；t[p]←-t[p]；          {vq和相连的权最小的边el加入最小生成树}

        end；{for}

      for i：=2 to n do 

        for j：=1 to i-1 do 

          if t[+j ]<0 then 输出最小生成树的边（i，j）；

【6.2.2】计算单源最短路问题（Dijkstra算法）

设G=（V，E）是一个有向图，它的每一条边（U，V）∈Ｅ都有一个权W（U，V），在G中指定一个结点V0，要求把从V0到G的每一个结点Vj(VＪ∈Ｖ)的最短有向路找出来（或者指出不存在从V0到Vj的有向路，即V0不可达Vj）。

输入

  顶点数n

  n*n的带权矩阵

输出

  有n行，每行为顶点序号i和V0到Vi的最短路长

题解

１.算法的基本思路

解决单源最短路径的基本思想是把图中所有结点分为两组

     第一组：包括已确定最短路径的结点；

     第二组：包括尚未确定最短路径的结点；

我们按最短路径长度递增的顺序把第二组的结点加到第一组中去，直至v0可达的所有结点都包含于第一组。在这个过程中，总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。另外，每一个结点对应一个距离值。第一组结点对应的距离值就是由v0到此结点的最短路径长度；第二组结点对应的距离值就是v0经由第一组结点（中间结点）至此结点的最短路径长度。具体作法是：

    初始时v0进入第一组，v0的距离值为0；第二组包含其它所有结点，这些结点对应的距离值这样确定（设vi为第二组中的结点）

然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中。每往第一组加入一个结点vm，就要对第二组的各结点的距离值作一次修正（设vi为第二组的结点）：

若加进vm做中间结点使得v0至vi的路径长度更短（即vi的距离值>vm的距离值+Wmi），则要修改vi的距离（vi的距离值←vm的距离值+Wmi）。修改后再选距离值最小的一个结点加入到第一组中，…。如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在。下面，我们来证明这个算法：

    显然，初始时对两个组的划分及各结点距离值的确定符合上述基本思想。因此要证明算法正确性，关键是证明每次往第一组加入结点vm后，其两个组的划分及结点距离值仍然符合要求。也就是要证明第二组中距离值最小的结点vm，其距离值为v0到vm的最短路径长度，且vm就是第二组中路径长度最小的结点。我们来证明这两点：

⑴ 若vm的距离值不是从v0到vm的最短路径长度，另有一条v0经由第二组某些结点（其中第一个结点设为vs）到达vm的路径，其长度比vm的距离值更小，即

        vs的距离值   与vm是第二组中距离值最小的结点矛盾。所以vm的距离值就是从v0到vm的最短路径长度。

⑵设vx是第二组中除vm外的任何其它结点。若v0至vx的最短路径上的中间结点为第一组的结点，由距离值的定义可知，其路径长度势必大于等于v0至vm的最短路径长度；若v0至vx的最短路径不仅包含第一组的结点为中间结点。设路径上第一个在第二组的中间结点为vy，则v0至vy的路径长度就是vy的距离值，已大于等于v0至vm的最短路径长度，那么v0到vx的最短路径长度当然也不会小于v0到vm的最短路径长度了，所以vm是第二组中最短路径为最小的结点。

２.变量说明

下面给出算法中的变量说明

  设  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；                                           {路径集合}

３.算法流程

计算单源最短路径的过程如下：

        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               then begin

                   u←i； min←dist[i]．length；

                   end；{then}

          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；{then}

               end；{then}

         until u=0；   　　　　　　　　　　　　　　　　{直至n个结点全部加入第一组为止}

算法结束时，沿着结点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至所有结点的最短路径。

【6.2.3】Car的旅行路线

又到暑假了，住在城市A的 Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速公路（图6.2.9）。第i个城市中高速公路的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。

图6.2.9

那么Car应如何安排到城市B的路线才能尽可能的节省花费昵？她发现这并不是一个简单的问题，于是她来向你请教。

任务

找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。

输人文件：键盘输入文件名

输  出：到屏幕（输出最小费用，小数点后保留2位。）

输入格式

第一行为一个正整数n(0≤n≤10)，表示有n组测试数据。

每组的第一行有四个正整数s，t，A，B。

s（0＜S≤100）表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，（1≤A，B≤S）。

接下来有s行，其中第i行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第i个城市中任意三个机场的坐标，Ti为第i个城市高速公路单位里程的价格。

输出格式：

共有n行，每行一个数据对应测试数据。

输入输出样例

输入

1

3 10 1 3

1 1 1 3 3 1 30

2 5 7 4 5 2 1

     8 6 8 8 11 6 3

输出

47.55

题解

1、计算两点间的欧氏距离

输入信息给出了各城市内高速公路单位里程价格和城市间飞机的单位里程价格。要知道两个机场间的路程费用，必须知道两个机场间的距离。设两个机场的坐标分别为（x1，y1）和（x2，y2）。按照欧氏公式，它们之间的距离应为dist=。我们通过函数dist(x1，y1，x2，y2)计算和返回（x1，y1）和（x2，y2）间的欧氏距离：

function dist(x1，y1，x2，y2:integer):real；{计算和返回（x1，y1）与（x2，y2）间的欧氏距离}

begin

    dist←sqrt(sqr(x1-x2)+sqr(y1-y2))；

end；{dist}

2.计算每个机场的坐标序列

  每个城市的四个飞机场分别位于一个矩形的四个顶点上，输入信息仅给出了其中的三个坐标，如何计算第四个机场的坐标。设

p1=(x1，y1)   p2=(x2，y2)   p3=(x3，y3)

为某城市的三个机场坐标，要求计算该城市的第四个机场坐标p=(x，y)。显然，p1、p2和p3中必有一条边为矩形边。有三种可能：

●（p1，p2）为矩形边。在这种情况下，（p3，p）必为相对的矩形边，且（（=）∧（x1+x2=x3+x）∧(y1+y2=y3+y)）即   x=x1+x2-x3 y=y1+y2-y3

●（p1，p3）为矩形边。在这种情况下，（p2，p）必为相对的矩形边，且（（=）∧（x1+x3=x2+x）∧(y1+y3=y2+y)）即   x=x1+x3-x2 y=y1+y3-y2

●（p2，p3）为矩形边。在这种情况下，（p1，p）必为相对的矩形边，且（（=）∧（x2+x3=x1+x）∧(y2+y3=y1+y)）即   x=x2+x3-x1 y=y2+y3-y1

在上述三种可能性中，必有（且仅有）一种可能性成立。我们按照上述公式依次假设(x，y)的可能值，并代入公式检验，条件成立的(x，y)即为城市的第四个机场坐标。设

map为机场序列，该序列含4*n个坐标，其中（map[i*4-3，1]，map[i*4-3，2]）…（map[4*i，1]，map[4*i，1]）为城市i的四个机场坐标(1≤i≤n)。我们在输入测试数据的同时计算map：

读城市数n，飞机的单位里程价格t，出发城市序号a，目标城市序号b；

  for i←1 to n do 

begin

     读第i个城市的三个机场坐标(x1，y1)（x2，y2）（x3，y3）和高速公路的单位里程价格f[i])；

     x←x1+x2-x3；y←y1+y2-y3；{假设（p1，p2）和（p3，p）为相对的两条矩形边，计算p坐标}

     if dist(x1，y1，x2，x2)<>dist(x3，y3，x，y) {

then begin{若假设不成立，则假设（p1，p3）（p2，p）为相对的两条矩形边，计算p坐标}

           x←x1+x3-x2；    y←y1+y3-y2；

 if dist(x1，y1，x3，y3)<>dist(x2，y2，x，y){ 若假设不成立，则假设（p2，p3）（p1，p）为相对的两条矩形边，计算p坐标}

 then begin

                x←x2+x3-x1；y←y2+y3-y1；

                end；{then}

            end；{then}

    map[i*4-3，1]←x1；map[i*4-3，2]←y1；           {将矩形的四个顶点坐标存入map数组}

    map[i*4-2，1]←x2；map[i*4-2，2]←y2；

    map[i*4-1，1]←x3；map[i*4-1，2]←y3；

    map[i*4，1]←x；    map[i*4，2]←y；

end；{for}

3.使用Dijkstra算法计算最小费用

按照Dijkstra算法的思想，将所有机场分为两组

     第一组：包括已确定最小费用的机场；

第二组：包括尚未确定最小费用的机场；

设

used为机场的分组标志。其中used[i]= 

ans为第一组机场的最小费用序列。其中ans[i]为出发城市至第一组中机场i的最小费用

（1≤i≤4*n）

我们按最小费用递增的顺序把第二组的机场加到第一组中去，直至到达目标城市b中的任一个机场为止。在这个过程中，总保持从出发城市a到第一组各机场的最小费用都不大于从a至第二组任何机场的费用。另外，每一个机场对应一个费用值。第一组机场对应的费用值就是由a到此机场的最小费用；第二组机场对应的费用值就是a经由第一组机场（中间机场）至此机场的最小费用。具体作法是：

    初始时，出发城市a的四个机场进入第一组（used[a*4-3]、used[a*4-2]、used[a*4-1]、used[a*4]设为true）；所有机场的费用值为0；第二组包含其它所有机场。

然后每次从第二组中选一个机场mi加到第一组中。这个机场必须满足如下条件：

●出发城市a经由第一组的某机场i(used[i]=true)可直达mi机场；

●其费用（ans[i]+机场i至机场mi的直接费用）在第二组机场的所有费用中是最小的；

机场i至机场mi使用的交通工具不同，直接费用亦随之不同。问题是机场i至机场mi究竟使用哪一种交通工具。这取决于两个机场所属城市的关系：

  机场i所属的城市为now=。

若机场mi在城市now（4*now-3≤mi≤4*now），则从机场i坐火车至机场mi；

若机场mi在其他城市（1≤mi≤4*now-4，4*now+1≤mi≤4*n）,则从机场i坐飞机至机场mi。

按照上述规律依次往第一组加入一个机场mi，直至被加入的机场mi属于目标城市b为止（4*b-3≤mi≤4*b）。由此得出算法： 

procedure solve；

var

    used            :array[1..4*maxn] of boolean；                       {第一组的机场标志}

    min，u        :real；                 {目前为止的最小费用为min，当前方案的费用为u}

    mi，i，j，now:integer；      {被加入第一组的机场序号为mi，机场所在的城市序号为now}

begin

    if a=b                    {若出发城市即为目标城市，则输出最小费用为0，并退出程序}

then begin    writeln(0)；    exit；end；{then}

    fillchar(used，sizeof(used)，false)；{初始时所有机场在第二组，该组内所有机场的最小费用为0}

    fillchar(ans，sizeof(ans)，0)；

    used[a*4-1]←true；                               {出发城市a的四个机场进入第一组}

    used[a*4-2]←true；

    used[a*4-3]←true；

    used[a*4]←true；

    repeat

        min←maxint；                                                 {最小费用初始化}

        for i←1 to 4*n do                                  {搜索第一组内的每一个机场}

if used[i] then 

begin

            now←(i-1) div 4 +1；                          {计算机场i所在的城市序号}

            for j←1 to 4*now-4 do      {搜索第二组内城市1…城市now-1的每一个机场j}

if not used[j]

 then begin          {计算出发城市至机场i，然后坐飞机至机场j的最小费用}

                     u←ans[i]+dist(map[j，1]，map[j，2]，map[i，1]，map[i，2])*t；

                    if uthen begin min←u；mi←j；end；{then}

                     end；{then}

            for j←4*now-3 to 4*now do             {搜索第二组内城市now的每一个机场j }

 if not used[j] 

then begin          {计算出发城市至机场i，然后坐火车至机场j的最小费用}

                   u←ans[i]+dist(map[j，1]，map[j，2]，map[i，1]，map[i，2])*f[now]；

                   if uthen begin min←u；mi←j；end；{then}

                   end；{then}

            for j←4*now+1 to 4*n do     {搜索第二组内城市now+1…城市n的每一个机场j}

if not used[j]

 then begin          {计算出发城市至机场i，然后坐飞机至机场j的最小费用}

                     u←ans[i]+dist(map[j，1]，map[j，2]，map[i，1]，map[i，2])*t；

                    if uthen begin     min←u；mi←j；    end；{then}

                    end；{then}

            end；{then}

        if mi in [4*b-3..4*b]     {若到达目标城市的一个机场，则输出最小费用并退出程序}

then begin writeln(min:0:2)；exit；end{then}

          else begin       {否则置mi机场进入第一组，并记下出发城市至该机场的最小费用}

used[mi]←true；ans[mi]←min；

end；{else}

    until false；

end；{solve}

由此得出主程序：

读测试数据的组数st；

for s←1 to st do {依次计算每一组测试数据}

  begin

  输入第s组数据，计算每个机场的坐标序列map；

  solve；

end；{for}

【6.2.4】士兵排队

有n个士兵(1≤n≤26)，编号依次为A、B、C、……。队列训练时，指挥官要把一些士兵从高到矮依次排成一行。但现在指挥官不能直接获得每个人的身高信息，只能获得“p1比p2高”这样的比较结果（p1，p2∈{ ’A’‥’Z’}），记为p1>p2。例如A>B，B>D，F>D。士兵的身高关系如图６．２．10所示

图6.2.10

对应的排队方案有三个：AFBD、FABD、ABFD

输入k行，每行为a b，表示a>b

输出排队方案

题解

    士兵的身高关系对应一张有向图，图中的顶点对应一个士兵，有向边表示士兵i高于士兵j。我们按照从高到矮将士兵排出一个线性的顺序关系，即为对有向图的顶点进行拓扑排序。拓扑排序是有向图的另一种重要运算。给出有向图G=(V，E)。若顶点的线性序列v1’，…，vn’(vi’∈V，1≤i≤n)满足如下条件：

         vk’至vk+1’有一条路径（１≤k则称该序列为拓扑序列。 

由上面例子可以看出，一个有向图结点的拓扑序列不是唯一的。并不是任何有向图的顶点都可以排成拓扑序列，有环图是不能排的。例如图6．2．11所示的有环图

图6．2．11

从其中任何一个结点出发，都可经由其它两个项点返回本身，因此就无法把结点排成满足条件的序列。任何无环的有向图，其结点都可以排出一个拓扑序列。下面给出拓扑排序的方法

     ⑴从图中选择一个入度为0的结点且输出之；

     ⑵从图中删除该结点及其所有出边（即与之相邻的所有结点的入度减一）；

反复执行这两个步骤，直至所有结点都输出了，也就是整个拓扑排序完成了。或者直至剩图中再没有入度为0的结点，这就说明此图中有环，拓扑排序不能再进行下去了。

   对于士兵排队问题，我们首先构造一张有向图G：

       var 

         g：array[’A’‥’Z’，’A’‥’Z’] of 0‥1；                             {图的相邻矩阵}

         d：array[’A’‥’Z’] of integer；                                   {结点的度数序列}

         s：set of  ’A’‥’Z’；                                                {士兵名集合}

图中的结点为士兵。若a>b，则g[a，b]←1 （即a向b引入一条有向边）；计算结点b的入度（即比士兵b高的人数）d(b)←d(b)+1。显然最高士兵对应的结点入度为0：

         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 as then m←m+a；

         k←length(m)；

    接下来对有向图Ｇ作拓扑排序。若图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         {若入度为0的结点不存在，则队列不存在最高的士兵，无解退出}

            then begin 

                输出失败信息；halt；

                end；{then} 

             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；

【6.2.5】挖地雷

在一个地图上有n个地窖(n≤20)，每个地窖中埋有一定数量的地雷，同时，给出地窖之间的联系路径.例如： V1，V2，V3，...，V6表示地窖。图6．2．12给出了一个示例：

图6．2．12

 [题目要求]

当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖(仅能选择一条路径)，挖的过程中允许某人重复经过地窖。当无连接时，挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入格式：

n  (表示地窖的个数）

W1  W2  W3......Wn

A12.........A1n

A23.......A2n

.........

A(n-1，n)

表示地窖之间连接路径（其中Aij表示地窖i，j之间是否有通路：通Aij=1，不通Aij=0）

输出格式：

R1-R2-...-Rk  (挖地雷的顺序)

  max          （为挖地雷的数量）

例如图6．2．13：

图6．2．13

其输入格式为：

5

10  8  4  7  6

1  1  1  0

   0  0  0

      1  1

         1

输出：

2-1-3-4-5

max=35

题解

  我们将地窖设为顶点，地窖之间的通路设为边，每个地窖中的地雷数设为顶点的权，使得问题对应一个顶点带权的无向图，目的是要在这张图中寻找一条路径，该条路径经过的地窖所含的地雷数最多。但是，是否允许某人重复经过地窖是问题的关键。例如图6．2．14：

图6．2．14

如果不允许某人重复经过地窖，则最佳路径为1→2→3，挖到的地雷数为13；如果允许某人重复经过地窖，则最佳路径为1→2→4，挖到的地雷数为14。不允许重复的求解方法带有明显的阶段特征，允许重复则不具备阶段特征。允许重复与不允许重复对应两种不同的解决方法。

允许某人重复经过地窖实际上是允许挖地雷的顺序中出现回路。无论该人怎样挖法，其经过的路径必然在一个连通子图中。我们采用计算连通子图的方法计算其中一个含地雷数最多的方案。

①计算无向图的传递闭包

  设

var

   link，longlink：array[1..20，1..20] of boolean；{ 无向图和无向图的传递闭包。其中}

我们递推产生longlink(0)、longlink(1)、…longlink(n)。在递推过程中，路径长度的’+’运算和比较大小运算用相应的逻辑运算符’∧’和’∨’代替。对于i，j和k=1‥n，如果图中结点i至结点j间存在通路且所有结点序号均属于{1‥k}，则定义longlinkij(k)=1；否则longlinkij(k)=0。

且对于k≥1

           longlinkij(k)=longlinkij(k-1) ∨ (longlinkik(k-1) ∧longlinkkj(k-1))

由于布尔值的存储量少于整数且位逻辑运算的执行速度快于算术运算，因此后者无论在时间和空间上都优于前一种算法。具体运算过程如下：

传递闭包longlink的计算过程如下：

longlink←link；

  for k←1 to n do                                                       {枚举中间地窖}

    for i←1 to n do                                                   {枚举所有地窖对}

for j←1 to n do                                   {计算地窖i和地窖j的连通情况}

longlink[i，j]←longlink[i，j] or (longlink[i，k]and longlink[k，j])；

②计算每一个连通分支的地雷总数，找出含地雷数最多的连通分支及其代表地窖

设

 best，besti—最佳连通分支中的地雷数和代表地窖；

计算best和besti的过程如下：

for i←1 to n do　　　　　　　　　　  　　　　　　　　　　　　　{枚举每一个地窖}

  begin

    k←0；

    for j←1 to n do　　　　　　　    　 　{计算地窖i所在连通分支中的地雷总数k}

      if longlink[i，j] then inc(k，mines[j])；

if k>best 　　　　　　　　{若k为目前最大，则记入best，i作为代表地窖记入besti}

then begin best←k；besti←i；end；

    if k=total then break；　　　   　　　　　　　　　　{若整个图为连通图，则退出}

  end；{for}

输出最多地雷数best；

③从代表地窖出发，递归搜索最佳方案

假如地窖x所在的连通分支所含的地雷数最多。我们从地窖x出发，按照深度优先搜索的顺序访问该连通分支中的所有地窖，并累计地雷数。设

 visited—访问标志。其中visited [x]=true表明地窖x已经过；

 total—连通分支中地雷数。初始时，total=0。搜索过程中，将挖到的地雷记入total。当total=best时搜索结束；

递归搜索最佳方案的过程如下：

procedure search(x：shortint)；

var i：shortint；

begin

  if not visited[x] then inc(total，mines[x])；　　  　　{若地窖x未访问，则累计地雷数}

  if total=best then halt；　　　　　　　　　　　{若挖完了连通分支中的所有地雷，则退出}

  visited[x] ←true；　　　　　　　　　　　　  　　　　　　　　　　{设地窖x访问标志}

  for i←1 to n do　　　　　　　　　　 　　　  　{搜索与地窖x相连且未访问的所有地窖}

    if (link[x，i]) and (not visited[i]) then

    begin

write(’-> ’，i)；　　　　　　　　 　　　　  　　　　　　　　　　　{递归输出路径}

      search(i)；

      write(’-> ’，x)；

    end；{then}

end；{ search }

显然，在主程序中通过

  fillchar(visited，sizeof(visited)，false)；　　　  　　{访问序列和挖到的地雷数初始化}

  total←0；

write(besti)；　　　　　　　　　　　　　　　　　　  　{从地窖besti出发输出最佳路径}

  search(besti)；

输出挖地雷的方案。

§6.3 例题

1.输入一棵二叉树及其根，分别输出前序、中序、后序遍历的访问结果。

2.在例题1的基础上输入二叉树的两个顶点，输出它们的最近公共祖先极其最短路径。.

3.输入一棵普通树，计算这棵树的度和深度

4.现有12件产品，其中有一件是次品（外形与正品一样，但重量或轻或重）。若以天平为工具，希望以最少的称重次数选出次品，且指出该次品是重还是轻。

输入：产品序列（0：正品，-1：次品轻；次品重）

输出：称重方案，每一行为天平两端的产品序号

5.输入一个有向图，计算每一个顶点的入度和出度

6..输入一个有向图G=（V，E），计算和输出G的平方图G2=（V，E2）（若（u,w）∈E2，当且仅当存在一个顶点v，使得（u,v）∈E,(v,w) ∈E。即当有向图G中存在u到w的长度为2的路径时，（u,w）∈E2）。

7.输入无向图G，计算和输出G的所有连通分支。

8.输入图G，计算和输出图的所有圈（若图中没有圈，则输出“not found”）。

9.输入一个有向无圈图DAG，计算和输出DAG的根r（即r到其他任何顶点都有一条路。若图中没有根，则输出“not found”）。

10.输入一个有向无圈图DAG，计算和输出DAG中最长路的长度。

11.输入一个带权有向图G，计算和输出G的中心v(v是G的一个顶点，v的偏心距定义为。

12.输入一个由01字符组成的长度为2n的字串。按下述规则分解FBZ串：

若其中字符全“1”，则称其为’B’串

若其中字符全“0”，则称其为’Z’串

若不全为“0”，同时也不全为“1”，则称’F’串

若此串为F串，则应将此串分解为2个2n-1的子串。对分解后的子串，仍按以上规则继续分解，直至全部为B串或为Z串为止。例如

  输入：

  n=3；

10111001（图6．3．1给出了分解FBZ串的过程）；

图6．3．1

输出：

   FFFBZBFFBZFZB。

13.由n个顶点（编号为0‥n-1）构成一棵无根树。要求对n个顶点重新编号（编号取值为0‥n-1使得相邻顶点编号差的绝对值正好构成一个等差数列。例如图6．3．2对一棵无根树重新编号：

图6．3．2