1.1 数据结构的作用和意义

数据是外部世界信息的计算机化，是计算机加工处理的对象。运用计算机处理数据时，必须解决四个方面的问题：一是如何在计算机中方便、高效地表示和组织数据；二是如何在计算机存储器（内存和外存）中存储数据；三是如何对存储在计算机中的数据进行操作，可以有哪些操作，如何实现这些操作以及如何对同一问题的不同操作方法进行评价；四是必须理解每种数据结构的性能特征，以便选择一个适合于某个特定问题的数据结构。这些问题就是数据结构这门课程所要研究的主要问题。

1.1.1 数据结构的作用

我们知道，虽然每个人都懂得英语的语法与基本类型，但是对于同样的题目，每个人写出的作文，水平却高低不一。程序设计也和写英语作文一样，虽然程序员都懂得语言的语法与语义，但是对于同样的问题，不同的程序员会写出来不一样的程序。有的人写出来的程序效率很高，有的人却用复杂的方法来解决一个简单的问题。

当然，程序设计水平的提高仅仅靠看几本程序设计书是不行的。只有多思索，多练习，才能提高自己的程序设计水平，否则，书看得再多，提高也不大。程序设计水平要想提高，要多看别人写的程序，多去思考问题。从别人写的程序中，我们可以发现效率更高的解决方法；从思考问题的过程中，我们可以了解解决问题的方法常常不只一个。运用先前解决问题的经验，来解决更复杂更深入的问题，是提高程序设计水平的最有效途径。

数据结构正是前人在思索问题的过程中所想出的解决方法。一般而言，在学习程序设计一段时间后，学习“数据结构”便能让你的程序设计水平上一个台阶。如果只学会了程序设计的语法和语义，那么你只能解决程序设计三分之一的问题，而且运用的方法并不是最有效的。但如果学会了数据结构的概念，就能在程序设计上，运用最有效的方法来解决绝大多数的问题。

《数据结构》这门课程的目的有三个。第一个是讲授常用的数据结构，这些数据结构形成了程序员处理数据问题的基本工具。对于许多常见的问题，这些数据结构是理想的选择。程序员可以直接拿来或经过少许的修改就可以使用，非常方便。第二个是讲授常用的算法，这和数据结构一样，是人们在长期实践过程中的总结，程序员也可以直接拿来或经过少许的修改就可以使用，并且可以通过算法训练来提高程序设计水平。第三个目的是通过程序设计的技能训练促进程序员综合能力的提高。

1.1.2 数据结构的意义

当我们用计算机解决一个问题时，必须告诉计算机如何去做。这需要先分析问题，确定一个适合的数据模型；然后，需要设计一个求解这个数据模型的算法，最后编写程序，经过反复调试直至得到正确结果。这就像我们求解一个数学的应用题时，需要通过问题的描述列出一个方程或方程组，然后求解该方程（组）一样。但是，需要计算机求解的大多数问题比数学方程要复杂得多。下面给出几个简单的例子加以说明。

【例1-1】某公司有50名员工，现在需要设计一个管理系统，完成对员工信息的查找、修改、插入或删除。

首先需考虑如何表示这50名员工的信息。员工信息之间的关系可以看成是一个接一个排列的一对一关系，这是一种线性结构。可以建立一个线性表，线性表中的每一个元素表示一个员工信息，如表1-1所示，对员工信息的查找、修改、插入或删除都应该基于该线性表进行操作。

员工信息是按工号一个接一个存放的。要查找某个员工信息，可以从第一个员工开始，依次向后一一比较，找到后，就可以修改了。如果要插入一个员工信息，可以先找到插入位置，把插入位置到最后的所有员工信息依次向后移动，空出位置后插入。如果要删除一个员工信息，可以先找到删除位置，然后将后面的员工信息依次前移即可。

【例1-2】计算机和人对弈问题。由于对弈的过程是在一定的规则下进行的，为使计算机能灵活对弈就必须将对弈过程中所有可能发生的情况以及相应的对策都考虑周全，同时，作为一名“好”的棋手，还应能预测棋局的发展趋势，所以，为使计算机能够和人进行对弈，必须事先将对弈的策略存入计算机，图1.1（a）所示为一个九宫格的棋盘格局。

黑白双方交替落子，如将从对弈开始到结束过程中可能出现的棋盘格局画出来，则可得到一个倒长的“树”，图1.1（b）所示的是其中的一部分。“树根”是对弈开始前的棋盘格局，而“叶子”是可能出现的结局。可以看到与线性结构不同，一个格局可以派生出几个格局，也就是说，一个格局只能有一个前驱，而可以有多个后继。如果计算机对弈开始前就计算出这样一颗树，就可以知道在对弈过程哪一种走法获胜的概率大一些，就像一位高手能预测棋局发展的趋势一样，从而选择一种较好的走法。

【例1-3】田径比赛赛程安排问题。在一名选手参加多个项目的情况下，这些项目不能同时开始，否则会产生冲突。假设有一个比赛的参赛项目表如表1-2如示，那么A、B、E就不能同时开始。那么应如何安排赛程呢？

在此例中，可以把一个参赛项表示为图中的一个顶点，而当两个项目不能同时举行时，以两个顶点之间的连线表示互相矛盾的关系。如图1.2（a）所示，每个圆圈表示一个比赛项目，两个圆圈之间的连线表示这两个圆圈不能在同一时间安排。所以当安排项目A时，只能同时安排没有和A连线的项目，在此例中，应为C，可以按此方法将没有冲突（互相没有连线）的项目用同一种颜色涂色，图1.2（b）所示为一种涂色结果。该结果表示的安排方法为（A、C），（B、D），（E），（F）。

通常，这种模型中，每个项目表示为一个顶点。每个顶点可以和其他任意个顶点联系。这类问题的数学模型是一种称为“图”的数据结构。

综合前面3个例子，这类非数值计算问题的数学模型是诸如表、树、图之类的数据结构，因此，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系及操作的学科。

数据结构是一门介于数学、计算机硬件和计算机软件三者之间的核心课程。数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。

学习“数据结构”既为进一步学习其他计算机专业课程提供必要的准备知识，也有助于提高软件设计和程序编制水平。1968年，美国D.E.Kunth教授开创了数据结构的最初体系，他的名著《计算机程序设计技巧》较为系统地阐述了数据的逻辑结构和存储结构及其操作。随着计算机科学的飞速发展和应用领域的不断扩大，到20世纪80年代初期，数据结构的基础研究日臻成熟，已成为一门完整的学科。