線性結構是最簡單而應用最廣泛的一種數(shù)據(jù)結構，在不同的場合會采取不同的存儲結構和實現(xiàn)方法。本模塊將介紹一種簡單的線性結構——線性表，就是同類型的元素排成的一個線性序列，并且介紹了線性表的兩種實現(xiàn)方法，即順序表和鏈表。如何來實現(xiàn)順序表和鏈表？什么時候應該用順序表，什么時候鏈表更好？這一模塊可以讓你學會使用線性表及其相關的一些操作，解決一些簡單問題，并考察分析時間空間上的效率，例如約瑟夫問題。重點：線性結構的邏輯定義，線性表的各種分類，順序表、鏈表的定義和相關操作。難點：注意順序表、鏈表的各種時間空間效率討論，包括插入刪除檢索等在各種概率分布情況下的討論。鏈表要特別注意表頭結點的作用，鏈表指針的正確操作。
基本概念和術語
1、數(shù)據(jù)(Data)
數(shù)據(jù)是外部世界信息的載體，它能夠被計算機識別、存儲和加工處理，是計算機程序加工的原料。計算機程序處理各種各樣的數(shù)據(jù)，可以是數(shù)值數(shù)據(jù)，如整數(shù)、實數(shù)或復數(shù)；也可以是非數(shù)值數(shù)據(jù)，如字符、文字、圖形、圖像、聲音等。
2、數(shù)據(jù)元素(Data Element)和數(shù)(DataItem) 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機程序中通常被作為一個整體進行考慮和處理。數(shù)據(jù)元素有時也被稱為元素、結點、頂點、記錄等。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(Data Item)組成。數(shù)據(jù)項是不可分割的、含有獨立意義的最小數(shù)據(jù)單位，數(shù)據(jù)項有時也稱為字段(Field)或域(Domain)。例如，在數(shù)據(jù)庫信息處理系統(tǒng)中，數(shù)據(jù)表中的一條記錄就是一個數(shù)據(jù)元素。這條記錄中的學生學號、姓名、性別、籍貫、出生年月、成績等字段就是數(shù)據(jù)項。數(shù)據(jù)項分為兩種，一種叫做初等項，如學生的性別、籍貫等，在處理時不能再進行分割；另一種叫做組合項，如學生的成績，它可以再分為數(shù)學、物理、化學等更小的項。
3、數(shù)據(jù)對象(Data Object)數(shù)據(jù)對象是性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如，整數(shù)數(shù)據(jù)對象是{0,±1,±2,±3,…}，字符數(shù)據(jù)對象是{a,b,c,…}。
4、數(shù)據(jù)類型(Data Type)
數(shù)據(jù)類型是高級程序設計語言中的概念，是數(shù)據(jù)的取值范圍和對數(shù)據(jù)進行操作的總和。數(shù)據(jù)類型規(guī)定了程序中對象的特性。程序中的每個變量、常量或表達式的結果都應該屬于某種確定的數(shù)據(jù)類型。例如，C#語言中的字符串類型（String，經(jīng)常寫為string）。一個String表示一個恒定不變的字符序列集合，所有的字符序列集合構成String的取值范圍。我們可以對String進行求長度、復制、連接兩個字符串等操作。
數(shù)據(jù)類型可分為兩類：一類是非結構的原子類型，如C#語言中的基本類型（整型、實型、字符型等）；另一類是結構類型，它的成分可以由多個結構類型組成，并可以分解。結構類型的成分可以是非結構的，也可以是結構的。例如，C#語言中數(shù)組的成分可以是整型等基本類型，也可以是數(shù)組等結構類型。
5、數(shù)據(jù)結構(Data Structure)
數(shù)據(jù)結構是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。在任何問題中，數(shù)據(jù)元素之間都不是孤立的，而是存在著一定的關系，這種關系稱為結構(Structure)。根據(jù)數(shù)據(jù)元素之間關系的不同特性，通常有4類基本數(shù)據(jù)結構：
(1) 集合(Set)：如圖1.1(a)所示，該結構中的數(shù)據(jù)元素除了存在“同屬于一個集合”的關系外，不存在任何其它關系。
(2) 線性結構(Linear Structure)：如圖1.1(b)所示，該結構中的數(shù)據(jù)元素存在著一對一的關系。
(3) 樹形結構(Tree Structure)：如圖1.1(c)所示，該結構中的數(shù)據(jù)元素存在著一對多的關系。
(4) 圖狀結構(Graphic Structure)：如圖1.1(d)所示，該結構中的數(shù)據(jù)元素存在著多對多的關系。
