1.1 什么是数据结构
随着计算机应用领域的不断扩大，简单的数据类型远远不能满足程序设计的需要，各元素之间的联系也不再是普通数学方程所能表达的。掌握数据结构和算法在很大程度上取决于描述实际问题的数据结构，那么数据结构究竟是研究什么的呢？
1.1.1 从数据结构实验演示系统认识数据结构
下面先介绍一个简单的数据结构实验演示系统。
在Windows等操作系统下运行本书提供的DS.exe文件，就会出现如下信息：
按提示进行选择，例如选择2，即进入栈子系统。
再按提示选择4，进入二进制和十进制转换的演示……
学过C（或C++）程序设计的人对结构化程序设计的一些特点应有一定的了解，但是对于数据，特别是数据结构往往缺乏更深层次的认识。著名的计算机科学家N.Writh提出“算法+数据结构=程序”的思想，明确地指出了数据结构实际上是程序的主要部分。
数据结构是一门介于数学、计算机硬件和计算机软件三者之间的核心课程。在计算机科学中，数据结构不仅是一般非数值计算程序设计的基础，还是设计和实现汇编语言、编译程序、操作系统、数据库系统，以及其他系统程序和大型应用程序的重要基础。打好“数据结构”这门课程的扎实基础，将会对程序设计有进一步的认识，使编程能力上一个台阶，从而使自己学习和开发应用软件的能力有明显的提高。
从我国计算机教学现状来看，数据结构不仅仅是计算机专业教学计划中的核心课程之一，而且已经逐步成为非计算机专业学生的重要选修课程。
1.1.2 数据结构研究的内容
用计算机解决一个具体问题时，大致需要经过以下几个步骤：
（1）从具体问题抽象出适当的数学模型。
（2）设计求解数学模型的算法。
（3）编制、运行并调试程序，直到解决实际问题。
寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间的关系，然后用数学语言加以描述。
下面请看几个例子。
【例1-1】学生入学情况登记简表，如表1-1所示。
表1-1 学生入学情况登记简表
续表
表1-1称为一个表数据结构，表中的每一行是一个结点（node），或称记录（record），由学号、姓名、性别、入学总分等数据项（item）组成。在此表中，第一条记录没有直接前驱，称为开始结点；最后一条记录没有直接后继，称为终端结点。除了第一条记录和最后一条记录以外，其余的记录，都有且仅有一条直接前驱记录和一条直接后继记录。这些结点之间是“一对一”的关系，它构成了“学生入学情况登记简表”的逻辑结构。
那么，“学生入学情况登记简表”在计算机的存储器中又是如何存储的呢？表中各元素是存储在存储器中连续的存储单元（顺序存储），还是用指针链接存储在不连续的存储单元（链接存储）呢？它构成了“学生入学情况登记简表”的存储结构。
如何在“学生入学情况登记简表”中查找、插入和删除记录，以及如何对记录进行排序、统计、分析等，构成了数据的运算。
【例1-2】井字棋对弈问题。
图1-1（a）是井字棋对弈过程中的一个格局，任何一方只要使相同的3个棋子连成一条直线（可以是一行、一列或一条对角线）即为胜方。如果下一步由“╳”方下，可以派生出5个子格局，如图1-1（b）所示；随后由“〇”方接着下，对于每个子格局又可以派生出4个子格局。
图1-1 井字棋对弈“树”
若将从对弈开始到结束的过程中所有可能的格局画在一张图上，即形成一棵倒挂的对弈“树”。“树根”是对弈开始时的第一步棋，而所有“叶子”便是可能出现的结局，对弈过程就是从树根沿树杈到某个叶子的过程。在本例中，对弈开始之前的棋盘格局没有直接前驱，称为开始结点（即根），以后每走一步棋，都有多种应对的策略，结点之间存在着“一对多”的关系，它构成了井字棋对弈的逻辑结构。
【例1-3】七桥问题。
位于俄罗斯境内的哥尼斯堡有一条小河叫勒格尔河，河有两条支流，一条叫新河，一条叫老河，它们在市中心汇合，在合流的地方中间有一座小岛，在小岛和两条支流上建有七座桥。于是哥尼斯堡可分为四块陆地，四周均为河流，四块陆地由七座桥相连。设四块陆地分别为A、B、C、D，可以用图1-2表示。
图1-2 七桥问题
哥尼斯堡的居民有个传统习惯，星期天沿着城市的河岸和小岛散步，同时试图找到一条可经过所有七座桥但又不重复经过任意一座桥的路线，这就是著名的“七桥问题”。1736年，正在哥尼斯堡的瑞士数学家欧拉对“七桥问题”产生了兴趣。他化繁为简，把四块陆地和七座桥抽象为四个点和七条线组成的几何图形，如图1-3所示，人们称之为欧拉回路。
图1-3 欧拉回路
欧拉对“七桥问题”的结论是：“所有结点的度（一个结点拥有的边数称为度）均为偶数时，原问题才有解”。换言之，“七桥问题”永远无解。在此，我们无意讨论数学证明问题，而仅对图1-3中每一个结点有多个直接前驱和多个直接后继这样一个结果产生兴趣，即那些结点之间存在“多对多”的关系，称之为图。
综上所述，非数值计算问题的数学模型不再是数学方程的问题，而是诸如上述的表（如例1-1）、树（如例1-2）、图（如例1-3）之类的数据结构。因此，简单地说，数据结构是一门研究非数值计算的程序设计问题的学科，主要研究数据的逻辑结构、存储结构和运算方法。
本章以下的三节就介绍这三方面的内容。