3.1 引 言

线性表是一种最基本、最简单的数据结构，数据元素之间仅具有单一的前驱和后继关系。现实生活中，许多问题抽象出的数据模型是线性表，如何存储这种线性结构并实现插入、删除、查找等基本操作呢？请看下面两个例子。

【例3－1】 在学籍管理问题中，计算机的操作对象是每个学生的学籍信息——数据元素，各元素之间的关系可以用线性结构来描述，如图3-1所示。在工资管理问题中，计算机的操作对象是每个职工的工资信息——数据元素，各元素之间的关系也可以用线性结构来描述，如图3-2所示。

图3-1 学生学籍登记表及其数据模型

图3-2 职工工资表及其数据模型

学生学籍登记表的内容与职工工资表的内容完全不同，但数据元素之间的逻辑关系都是线性的。由此可见，一些表面上很不相同的数据可以有相同的逻辑结构。如何存储这种二维表并实现增、删、改、查等基本功能呢？

【例3－2】 约瑟夫环问题。约瑟夫环问题由古罗马史学家约瑟夫（Josephus）提出，他参加并记录了公元66—70年犹太人反抗罗马帝国的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。

可以将约瑟夫环问题抽象为如图3-3所示数据模型，具体描述为：设n（n＞0）个人围成一个环，n个人的编号分别为1，2，…，n，从第1个人开始报数，报到m时停止报数，报m的人出环；再从他的下一个人起重新报数，报到m时停止报数，报m的出环；……如此下去，直到所有人全部出环为止。当任意给定n和m后，求n个人出环的次序。可见，约瑟夫环问题的数据模型是一种典型的环状线性结构。如何存储这种环形结构并求解约瑟夫环的出环次序呢？

图3-3 约瑟夫环问题的数据模型（n=5，m=3时的出圈次序：3，1，5，2，4）