線性結(jié)構(gòu)是最簡單而應(yīng)用最廣泛的一種數(shù)據(jù)結(jié)構(gòu)，在不同的場合會采取不同的存儲結(jié)構(gòu)和實現(xiàn)方法。本模塊將介紹一種簡單的線性結(jié)構(gòu)——線性表，就是同類型的元素排成的一個線性序列，并且介紹了線性表的兩種實現(xiàn)方法，即順序表和鏈表。如何來實現(xiàn)順序表和鏈表？什么時候應(yīng)該用順序表，什么時候鏈表更好？這一模塊可以讓你學(xué)會使用線性表及其相關(guān)的一些操作，解決一些簡單問題，并考察分析時間空間上的效率，例如約瑟夫問題。重點：線性結(jié)構(gòu)的邏輯定義，線性表的各種分類，順序表、鏈表的定義和相關(guān)操作。難點：注意順序表、鏈表的各種時間空間效率討論，包括插入刪除檢索等在各種概率分布情況下的討論。鏈表要特別注意表頭結(jié)點的作用，鏈表指針的正確操作。

　基本概念和術(shù)語

 

　　1、數(shù)據(jù)(Data)

　　數(shù)據(jù)是外部世界信息的載體，它能夠被計算機識別、存儲和加工處理，是計算機程序加工的原料。計算機程序處理各種各樣的數(shù)據(jù)，可以是數(shù)值數(shù)據(jù)，如整數(shù)、實數(shù)或復(fù)數(shù)；也可以是非數(shù)值數(shù)據(jù)，如字符、文字、圖形、圖像、聲音等。

 

 

　　2、數(shù)據(jù)元素(Data Element)和數(shù)(DataItem)　　數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機程序中通常被作為一個整體進行考慮和處理。數(shù)據(jù)元素有時也被稱為元素、結(jié)點、頂點、記錄等。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(Data Item)組成。數(shù)據(jù)項是不可分割的、含有獨立意義的最小數(shù)據(jù)單位，數(shù)據(jù)項有時也稱為字段(Field)或域(Domain)。例如，在數(shù)據(jù)庫信息處理系統(tǒng)中，數(shù)據(jù)表中的一條記錄就是一個數(shù)據(jù)元素。這條記錄中的學(xué)生學(xué)號、姓名、性別、籍貫、出生年月、成績等字段就是數(shù)據(jù)項。數(shù)據(jù)項分為兩種，一種叫做初等項，如學(xué)生的性別、籍貫等，在處理時不能再進行分割；另一種叫做組合項，如學(xué)生的成績，它可以再分為數(shù)學(xué)、物理、化學(xué)等更小的項。                                                           　　　　　　     

 

　　3、數(shù)據(jù)對象(Data Object)數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如，整數(shù)數(shù)據(jù)對象是{0,±1,±2,±3,…}，字符數(shù)據(jù)對象是{a,b,c,…}。

 

　　4、數(shù)據(jù)類型(Data Type)

　　數(shù)據(jù)類型是高級程序設(shè)計語言中的概念，是數(shù)據(jù)的取值范圍和對數(shù)據(jù)進行操作的總和。數(shù)據(jù)類型規(guī)定了程序中對象的特性。程序中的每個變量、常量或表達式的結(jié)果都應(yīng)該屬于某種確定的數(shù)據(jù)類型。例如，C#語言中的字符串類型（String，經(jīng)常寫為string）。一個String表示一個恒定不變的字符序列集合，所有的字符序列集合構(gòu)成String的取值范圍。我們可以對String進行求長度、復(fù)制、連接兩個字符串等操作。

數(shù)據(jù)類型可分為兩類：一類是非結(jié)構(gòu)的原子類型，如C#語言中的基本類型（整型、實型、字符型等）；另一類是結(jié)構(gòu)類型，它的成分可以由多個結(jié)構(gòu)類型組成，并可以分解。結(jié)構(gòu)類型的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。例如，C#語言中數(shù)組的成分可以是整型等基本類型，也可以是數(shù)組等結(jié)構(gòu)類型。

 

　　5、數(shù)據(jù)結(jié)構(gòu)(Data Structure)

　　數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。在任何問題中，數(shù)據(jù)元素之間都不是孤立的，而是存在著一定的關(guān)系，這種關(guān)系稱為結(jié)構(gòu)(Structure)。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有4類基本數(shù)據(jù)結(jié)構(gòu)：

(1) 集合(Set)：如圖1.1(a)所示，該結(jié)構(gòu)中的數(shù)據(jù)元素除了存在“同屬于一個集合”的關(guān)系外，不存在任何其它關(guān)系。

(2) 線性結(jié)構(gòu)(Linear Structure)：如圖1.1(b)所示，該結(jié)構(gòu)中的數(shù)據(jù)元素存在著一對一的關(guān)系。

(3) 樹形結(jié)構(gòu)(Tree Structure)：如圖1.1(c)所示，該結(jié)構(gòu)中的數(shù)據(jù)元素存在著一對多的關(guān)系。

(4) 圖狀結(jié)構(gòu)(Graphic Structure)：如圖1.1(d)所示，該結(jié)構(gòu)中的數(shù)據(jù)元素存在著多對多的關(guān)系。