小树学数据结构:什么是数据结构的基础_学编程必须学数据结构吗

本文对应严蔚敏老师的《数据结构(C语言版)》第一章绪论的第一节，什么是数据结构

教材中通过列举了三个例题，分别说明了线性结构、树、图三种数据结构，然后介绍了数据结构学科的发展史还有数据结构的内含和外沿，这里边三个例题尤其是后两个例题，还是有很多可以分析的地方。

例题1-1 图书馆数目检索系统自动化问题

问题内容不在赘述，教材中给出的检索方法其实如下图：

教材提到引入登录号这个概念是为了解决书名等有重名的问题，按照登录顺序对所有数目进行编号，就不会有这个问题了。但是如果按照书名索引登录号，岂不是也要得到多个结果？可能通过提供多个条件合并查找的功能可以解决吧。
教材提到这是一种最简单的线性关系，对于线性关系的解释，没有明确定义。从例题的特征看，应该是具有逐条排列的特征，或者说，具有线性关系的数据，可以通过一个表格（结构体数组）把所有数据列出来。
比如教材中的例子：

例题1-2 计算机和人对弈问题

看这个例题第一感觉想到的不是数据结构，而是如果通过编程实现这个井字棋的游戏，应该挺有意思。随意想到的，可以划分成提供输入棋子的输入函数、打印棋局的输出函数、描述当前棋局的数据结构、穷举下一步到下N步的棋局的穷举函数、记录从当前棋局分析得到的所有可能结果的数据结构、判断哪一步更有利的算法实现函数等几个模块，有时间一定要写一下试试。
这个例题同样没有明确给出树形结构的定义，特征上，教材描述要具有从一个派生出多个的特点

例题1-3 多叉路口交通灯的管理问题

问题描述原文

这个问题最有意思，先将教材原文引用如下

例 1-3 多叉路口交通灯的管理问题。通常，在十字交叉路口只需设红、绿两色的交通灯便可保持正常的交通秩序，而在多叉路口需设几种颜色的交通灯才能既使车辆相互之间不碰撞，又能达到车辆的最大疏通。假设有一个如图1.3(a)所示的五叉路口，其中C和E为单行道。在路口有13条可行的通路，其中有的可以同时通行，如A→B和E→C，而有的不能同时同行，如E→B和A→D。那么，在路口应如何设置交通灯进行车辆的管理呢？

图1.3

对题目的理解

题目中类比了十字路口中需要设置红色、绿色两种信号灯。如下图所示

对于十字路口，穷举如下所有通行情况：
A→B，A→C，A→D，
B→A，B→C，B→D，
C→A，C→B，C→D，
D→A，D→B，D→C，
根据生活经验，A和C之间的通行影响B和D之间的通行，右转（A→D，D→C，C→B，B→A）不影响其他任何的通行，左转影响目的岔路的直行，例如，A→B影响B→D。（这里也许有个通用的N个岔路的影响情况的描述，我没总结到）
我们以A的视角，描述生活中给出的双色方案：
红灯时，直行：B→D，D→B，左转：D→A，B→C，右转：A→D，D→C，C→B，B→A
绿灯时，直行：A→C，C→A，左转：A→B，C→D，右转：A→D，D→C，C→B，B→A
原题中的五叉路口，问的应该怎样设置交通灯，其实就是要求给出一种方案描述，首先要提供需要几种颜色，每种颜色下，可以允许几种通行方式，并且需要满足，所有通行方式都在某一种或几种颜色下可以通行。

通行需求的数量

教材中直接给出了路口有13条可行的通路这样的结论，我想这个主要有两种算法：
第一是枚举法，可以列举所有方案，得到是13中通路
第二可以通过A₅²-4-4+1得到，这个公式不做解释
但是后边解决这个问题时还是免不了要枚举

问题抽象

如何从交通灯问题就变成了染色问题，这是整个例题的关键。

图1.3(b)的含义：

图中每个圆圈代表的是通路（A→B等），不是岔路（ABCDE）。
两个圆圈之间的连线表示这两个通路不能共存。比如，AB和DA之间有连线，从图1.3(a)可知，A→B和D→A时，会发生类似十字路口下直行和左拐的矛盾，所以不能并存。

从交通灯到染色问题的对应

原题要求可以拆解成如下几点：

• 提供需要几种颜色
• 提供每种颜色可通行几个通路，通路不能有矛盾
• 所有通路均要覆盖
• 颜色数量最少

当我们画出图1.3(b)后，这个问题可以类比为以下几点：

• 提供几种颜色对图中的圆圈染色
• 同一颜色的圆圈之间不能有连线（连线对应通行矛盾）
• 所有圆圈都要染色
• 颜色数量最少
  至此，交通灯问题可以类比为染色问题
  原题中给出了染色问题的最后答案（见图1.3(b)），但是没有给出解决步骤，我想这应该是学完第7章图以后才能解决吧。

教材中本节还介绍了数据结构学科的发展史和学科边界，本文不做赘述