1.1 问题求解与程序设计

用计算机求解任何问题都离不开程序设计，只有最终在计算机上能够运行良好的程序才能解决特定的实际问题，因此，程序设计的过程就是利用计算机求解问题的过程。

1.1.1 程序设计的一般过程

用计算机求解任何问题都离不开程序设计，但是计算机不能分析问题并产生问题的解决方案，必须由人（即程序设计者）分析问题，确定问题的解决方案，采用计算机能够理解的指令描述这个问题的求解步骤（即编写程序），然后让计算机执行程序最终获得问题的解。程序设计的一般过程如图1-1所示。

由问题到想法需要分析问题，抽象出具体的数据模型（待处理的数据以及数据之间的关系，也称数据结构），形成问题求解的基本思路。对于待求解的问题，首先搞清楚求解的目标是什么，给出了哪些已知信息、显式条件或隐含条件，应该用什么形式的数据表达计算结果。如果没有全面、准确和认真地分析问题，就急急忙忙地编写程序，结果往往是事倍功半，造成不必要的反复，甚至给程序留下严重隐患。

算法用来描述问题的解决方案，是具体的、机械的操作步骤。利用计算机解决问题的最重要一步是将人的想法描述成算法，即设计算法，也就是从计算机的角度设想计算机是如何一步一步完成这个任务的。有些问题很简单，很容易就可以得到问题的解决方案；如果问题比较复杂，就需要更多的思考才能得到问题的解决方案。由想法到算法需要完成数据表示和数据处理，即描述问题的数据模型（将数据从机外表示转换为机内表示），描述问题求解的基本思路（将问题的解决方案形成算法）。数据结构课程主要讨论非数值问题的数据表示和数据处理。

由算法到程序需要将算法的操作步骤转换为某种程序设计语言对应的语句，转换所依据的规则就是某种程序设计语言的语法，换言之，就是在某种编程环境下用程序设计语言描述要处理的数据以及数据处理的过程。

著名的计算机学者沃思给出了一个公式：数据结构+算法=程序。从这个公式可以看到，数据结构和算法是构成程序的两个重要的组成部分，一个“好”程序首先是将问题抽象出一个适当的数据结构，然后基于该数据结构设计一个“好”算法。下面以著名的哥尼斯堡七桥问题为例，说明程序设计的一般过程。

【问题】 哥尼斯堡七桥问题（以下简称七桥问题）。17世纪的东普鲁士有一座哥尼斯堡城（现在叫加里宁格勒，在波罗的海南岸），城中有一座岛，普雷格尔河的两条支流环绕其旁，并将整个城市分成北区、东区、南区和岛区4个区域，全城共有七座桥将4个城区连接起来，如图1-2（a）所示。于是，产生了一个有趣的问题：一个人是否能在一次步行中经过全部的七座桥后再回到起点，且每座桥只经过一次。

【想法】 将城区抽象为顶点，用A、B、C、D表示4个城区，将桥抽象为边，用7条边表示七座桥，抽象出七桥问题的数据模型如图1-2（b）所示，从而将七桥问题抽象为一个数学问题：求经过图中每条边一次且仅一次的回路，后来人们称之为欧拉回路。欧拉回路的判定规则是：

（1）如果通奇数个桥的城区多于两个，则不存在欧拉回路；

（2）如果只有两个城区通奇数个桥，则可以从这两个城区之一出发找到欧拉回路；

（3）如果没有一个城区通奇数个桥，则无论从哪里出发都能找到欧拉回路。

由上述判定规则得到求解七桥问题的基本思路：依次计算与每个顶点相关联的边的个数（称为顶点的度），根据度为奇数的顶点个数判定是否存在欧拉回路。

【算法】 进一步地，将顶点A、B、C、D编号为0、1、2、3，用二维数组mat[4][4]存储七桥问题的数据模型，如果顶点i（0≤i≤3）和顶点j（0≤i≤3）之间有k条边，则元素mat[i][j]的值为k，如图1-2（c）所示。求解七桥问题的关键是求与每个顶点相关联的边数，即在二维数组mat[4][4]中求每一行元素之和，算法描述如下：

【程序】 主函数首先初始化二维数组mat[4][4]，即建立七桥问题对应的数据模型，然后调用函数EulerCircuit计算图模型中通奇数个桥的顶点个数，再根据欧拉规则判定是否存在欧拉回路。程序如下：

            #include＜stdio.h＞                              //使用库函数printf和scanf
            intEulerCircuit（intmat[10][10]，intn）；        //函数声明

                                                             //空行，以下是主函数
            intmain（）
            {
                  intmat[10][10]={{0，1，2，2}，{1，0，1，1}，{2，1，0，0}，{2，1，0，0}}；
                  intnum=EulerCircuit（mat，4）；            //调用函数得到通奇数个桥的顶点个数
                  if（num＞2）                               //多于两个顶点通奇数个桥
                    printf（＂有%d个地方通奇数个桥，不存在欧拉回路\n＂，num）；
                  elseif（num==2||num==0）                   //两个顶点通奇数个桥或没有顶点通奇数个桥
                      printf（＂存在欧拉回路\n＂）；
                  return0；                                  //将0返回操作系统，表明程序正常结束
            }
                                                             //空行，以下是其他函数定义
            intEulerCircuit（intmat[10][10]，intn）          //函数定义，二维数组作为形参
            {
                  inti，j，degree，count=0；                 //count累计通奇数个桥的顶点个数
                  for（i=0；i＜n；i++）                      //依次累加每一行的元素
                  {
                    degree=0；                               //degree存储通过顶点i的桥数，初始化为0
                    for（j=0；j＜n；j++）                    //依次处理每一列的元素
                    {
                      degree=degree+mat[i][j]；              //将通过顶点i的桥数求和
                    }
                    if（degree% 2！=0）                      //桥数为奇数
                      count++；
                  }
                  returncount；                              //结束函数，并将count返回到调用处
            }

1.1.2 数据结构在程序设计中的作用

有些问题难以求解的原因是无从下手，如果能将问题抽象出一个合适的数据模型，则问题可能会变得豁然开朗。下面这个著名的握手问题是爱丁堡大学的PeterRoss提出来的。

【例1-1】 握手问题。Smith先生和太太邀请4对夫妻来参加晚宴。每个人来的时候，房间里的一些人都要和其他人握手。当然，每个人都不会和自己的配偶握手，也不会跟同一个人握手两次。之后，Smith先生问每个人和别人握了几次手，他们的答案都不一样。问题是，Smith太太和别人握了几次手？

解：这个问题具有挑战性的原因是因为它没有一个明显的起始点，但如果将此问题抽象出一个合适的数据模型，如图1-3（a）所示，问题就变得简单了。

让我们来收集一下已知条件。Smith先生问了房间中的9个人，每个人的答案都不相同，因此，每个答案都在0和8之间，相应地修改模型如图1-3（b）所示。

让我们来列出所有的握手信息。例如，8号除了他（她）自己和配偶，与房间里的其他人总共握了8次手。基于这个观察，我们可以画出8号的握手信息并且知道8号的配偶是0号；7号除了0号和1号，与房间里的其他人总共握了7次手，因此7号的配偶是1号；……问题是否变得豁然开朗了？

一个“好”程序首先是将问题抽象出一个适当的数据模型，基于不同数据模型的算法，其运行效率可能会有很大差别。举例如下。

【例1-2】 手机电话号码查询问题。假设某手机中存储了如表1-1所示的若干电话号码，如何在手机中查找某人的电话号码？

解：如果将电话号码集合线性排列，则某个人的电话号码只能进行顺序查找。

如果将电话号码集合进行分组，如图1-4所示，则查找某个人的电话号码可以只在某个分组中进行。显然，后者的查找效率更高，当数据量较大时差别就更大。

1.1.3 算法在程序设计中的作用

算法是问题的解决方案，这个解决方案本身并不是问题的答案，而是能获得答案的指令序列。对于许多实际的问题，写出一个正确的算法还不够，如果这个算法在规模较大的数据集上运行，那么运行效率就成为一个重要的问题。在选择和设计算法时要有效率的观念，这一点比提高计算机本身的速度更为重要。

【例1-3】 数组循环左移问题。将一个具有n个元素的数组向左循环移动i个位置。有许多应用程序会调用这个问题的算法，例如在文本编辑器中移动行的操作，磁盘整理时交换两个不同大小的相邻内存块等。所以，解决这个问题的算法要求有较高的时间性能和空间性能。

解法1：先将数组中的前i个元素存放在一个临时数组中，再将余下的n-i个元素左移i个位置，最后将前i个元素从临时数组复制回原数组中后面的i个位置，这个算法总共需要移动i+（n-i）+i=i+n次数组元素，但使用了i个额外的存储单元。

解法2：先设计一个函数将数组向左循环移动1个位置，然后再调用该算法i次，这个算法只使用了1个额外的存储单元，但总共需要移动i× n次数组元素。

解法3：现在我们换一个角度看这个问题，将这个问题看作是把数组AB转换成数组BA（A代表数组的前i个元素，B代表数组中余下的n-i个元素），先将A置逆得到A-1B，再将B置逆得到A-1B-1，最后将整个A-1B-1置逆得到（A-1B-1）-1=BA。设Reverse函数执行将数组元素置逆的操作，对abcdefgh向左循环移动3个位置的过程如下：

            Reverse（0，i-1）；              //得到cbadefgh
            Reverse（i，n-1）；              //得到cbahgfed
            Reverse（0，n-1）；              //得到defghabc

其原理可以用一个简单的游戏来理解：将两手的掌心对着自己，左手在右手上面，将一个具有10个元素的数组向左循环移动5位的操作过程如图1-5所示。

这个算法总共需要交换i+（n-i）+n=2n次数组元素，只使用了1个用来交换的临时单元，并且算法简单、易懂，想出错都很难。BrianKernighan在SoftwareToolsinPascal中使用了这个算法在文本编辑器中移动各行。

1.1.4 本书讨论的主要内容

计算机能够求解的问题一般可以分为数值问题和非数值问题。数值问题抽象出的数据模型通常是数学方程，非数值问题抽象出的数据模型通常是线性表、树、图等数据结构。下面请看几个例子。

【例1-4】 为百元买百鸡问题抽象数据模型。已知公鸡5元一只，母鸡3元一只，小鸡1元三只，花100元钱买100只鸡，问公鸡、母鸡、小鸡各多少只？

解：设x、y和z分别表示公鸡、母鸡和小鸡的个数，则有如下方程组成立：

【例1-5】 为学籍管理问题抽象数据模型。

解：用计算机来完成学籍管理，就是由计算机程序处理学生学籍登记表，实现增、删、改、查等功能。图1-6（a）所示为一张简单的学生学籍登记表。在学籍管理问题中，计算机的操作对象是每个学生的学籍信息——表项，各表项之间的关系可以用线性结构来描述，如图1-6（b）所示。

【例1-6】 为人机对弈问题抽象数据模型。

解：在对弈问题中，计算机的操作对象是对弈过程中可能出现的棋盘状态——格局，而格局之间的关系是由对弈规则决定的。因为从一个格局可以派生出多个格局，所以，这种关系通常不是线性的。例如，从三子连珠游戏的某格局出发可以派生出五个新的格局，从新的格局出发，还可以再派生出新的格局，如图1-7（a）所示；格局之间的关系可以用树结构来描述，如图1-7（b）所示。

【例1-7】 为七巧板涂色问题抽象数据模型。

解：假设有如图1-8（a）所示的七巧板，使用至多4种不同颜色对七巧板涂色，要求每个区域涂一种颜色，相邻区域的颜色互不相同。为了识别不同区域的相邻关系，可以将七巧板的每个区域看成一个顶点，如果两个区域相邻，则这两个顶点之间有边相连，将七巧板抽象为图结构，如图1-8（b）所示。

本书讨论非数值问题的数据组织和处理，主要内容如下：

（1）数据的逻辑结构：线性表、树、图等数据结构，其核心是如何组织待处理的数据以及数据之间的关系；

（2）数据的存储结构：如何将线性表、树、图等数据结构存储到计算机的存储器中，其核心是如何有效地存储数据以及数据之间的逻辑关系；

（3）算法：如何基于数据的某种存储结构实现插入、删除、查找等基本操作，其核心是如何有效地处理数据；

（4）常用的数据处理技术：包括查找技术和排序技术等；

（5）基本的算法设计技术：包括蛮力法、分治法、减治法、贪心法和动态规划法等，并从算法设计技术的角度讨论线性表、树和图等数据结构的基本操作，以及查找算法和排序算法的设计思想和设计过程。