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）