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

　基本概念和術(shù)語(yǔ)

 

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

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

 

 

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

 

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

 

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

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

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

 

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

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

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

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

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

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