線性表

?

讓編程改變世界

Change the world by program

---

?

感受線性表的存在

? 各位魚油大家好，從今天開始小甲魚帶大家開始學(xué)習(xí)第一個(gè)數(shù)據(jù)結(jié)構(gòu)：線性表 先讓我我們通過圖片來感受一下，線性表的特性吧。 [caption id="attachment_758" align="aligncenter" width="602"] 感受線性表的存在[/caption] ? 大家姑且可以把這幅圖想象為小甲魚組織魚油們外出野營(yíng)。因?yàn)樵埕~油隊(duì)伍強(qiáng)大，要小甲魚記住每位魚油并區(qū)分還真不是一件容易的事。 所以咱想到了一個(gè)辦法，讓大家按照一個(gè)約定排成一隊(duì)，以后大家要怎么記住自己的位置呢？沒錯(cuò)，大家只需要記住自己前邊的魚油即可。 小甲魚也可以很快的清點(diǎn)人數(shù)，萬一有人走丟，也能在最快時(shí)間內(nèi)知道是誰不見了，因?yàn)橹恍枰獑柲奈霍~油的“前驅(qū)”不見啦即可。 ?

線性表的定義

? 線性表，從剛才小甲魚的描述中我們可以很容易感受到是像排隊(duì)一樣，具有線一樣性質(zhì)的結(jié)構(gòu)。 如果像下邊這樣，我們就不能說是線性表了： [caption id="attachment_759" align="aligncenter" width="402"] 這不是線性表[/caption] ? 線性表（List）：由零個(gè)或多個(gè)數(shù)據(jù)元素組成的有限序列。 ?

這里需要強(qiáng)調(diào)幾個(gè)關(guān)鍵的地方：

首先它是一個(gè)序列，也就是說元素之間是有個(gè)先來后到的，像剛才的小蝌蚪就沒有順序。 若元素存在多個(gè)，則第一個(gè)元素?zé)o前驅(qū)，而最后一個(gè)元素?zé)o后繼，其他元素都有且只有一個(gè)前驅(qū)和后繼。 另外，線性表強(qiáng)調(diào)是有限的，事實(shí)上無論計(jì)算機(jī)發(fā)展到多強(qiáng)大，它所處理的元素都是有限的。 ?

如果用數(shù)學(xué)語言來進(jìn)行定義，可如下：

若將線性表記為（a1,…,ai-1,ai,ai+1,…an）,則表中ai-1領(lǐng)先于ai,ai領(lǐng)先于ai+1,稱ai-1是ai的直接前驅(qū)元素,ai+1是ai的直接后繼元素。 [caption id="attachment_760" align="aligncenter" width="600"] 線性表的定義[/caption] ? 所以線性表元素的個(gè)數(shù)n(n>=0)定義為線性表的長(zhǎng)度，當(dāng)n=0時(shí)，稱為空表。 ? ?

考題模擬

?

請(qǐng)問公司的組織架構(gòu)是否屬于線性關(guān)系？

分析：一般公司的總經(jīng)理管理幾個(gè)總監(jiān)，每個(gè)總監(jiān)管理幾個(gè)經(jīng)理，每個(gè)經(jīng)理都有各自的下屬和員工。 ?

那這樣的組織架構(gòu)是不是線性關(guān)系呢？

當(dāng)然不是啦！ 注意線性關(guān)系的條件是如果存在多個(gè)元素，則“第一個(gè)元素?zé)o前驅(qū)，而最后一個(gè)元素?zé)o后繼，其他元素都有且只有一個(gè)前驅(qū)和后繼。” ?

那么班級(jí)里同學(xué)之間的友誼呢？

當(dāng)然也不是，因?yàn)槊總€(gè)人都會(huì)跟許多同學(xué)建立純純的友誼關(guān)系。 ?

好，再來一題，那如果是情侶間的愛情關(guān)系呢？

哈，還是扯淡，這要是線性關(guān)系還哪里容得下第三者？！ ?

最后一個(gè)問題，一個(gè)班級(jí)里的點(diǎn)名冊(cè)，是不是線性表？

嗯，這個(gè)就是了。 [caption id="attachment_761" align="aligncenter" width="600"] 定義線性表[/caption] ?

抽象數(shù)據(jù)類型

? 因?yàn)橄鹿?jié)課我們會(huì)講線性表的抽象數(shù)據(jù)類型，所以這節(jié)課的末尾部分給大家介紹一下什么是抽象數(shù)據(jù)類型。 那在介紹抽象數(shù)據(jù)類型之前，我們應(yīng)該了解數(shù)據(jù)類型的定義是什么？ ? 數(shù)據(jù)類型：是指一組性質(zhì)相同的值的集合及定義在此集合上的一些操作的總稱。 例如很多編程語言的整型，浮點(diǎn)型，字符型這些指的就是數(shù)據(jù)類型。 ?

當(dāng)年那些設(shè)計(jì)計(jì)算機(jī)語言的人，為什么會(huì)考慮到數(shù)據(jù)類型呢？

比如，大家都需要住房子，也都希望房子越大越好。但顯然，沒有多少錢的話考慮房子是沒啥意義的。 于是商品房就出現(xiàn)了各種各樣的房型，有別墅的，有錯(cuò)層的，有單間的，甚至在北京還出現(xiàn)了膠囊公寓——只有兩平方米的房間。 這樣子就滿足了大家的不同需求。 ? 同樣，在計(jì)算機(jī)中，內(nèi)存也不是無限大的，你要計(jì)算入1+1=2這樣的整型數(shù)字的加減乘除運(yùn)算，顯然不需要開辟很大的內(nèi)存空間。 而如果要計(jì)算1.23456789+2.987654321這樣帶大量小數(shù)的，就需要開辟比較大的空間才存放的下。 ? 于是計(jì)算機(jī)的研究者們就考慮，要對(duì)數(shù)據(jù)類型進(jìn)行分類，分出多種數(shù)據(jù)類型來適合各種不同的計(jì)算條件差異。 ?

例如在C語言中，按照取值的不同，數(shù)據(jù)類型可以分為兩類：

原子類型：不可以再分解的基本類型，例如整型、浮點(diǎn)型、字符型等。 結(jié)構(gòu)類型：由若干個(gè)類型組合而成，是可以再分解的，例如整型數(shù)組是由若干整型數(shù)據(jù)組成的。 ? 抽象：是指抽取出事物具有的普遍性的本質(zhì)。它要求抽出問題的特征而忽略非本質(zhì)的細(xì)節(jié)，是對(duì)具體事物的一個(gè)概括。抽象是一種思考問題的方式，它隱藏了繁雜的細(xì)節(jié)。 我們對(duì)已有的數(shù)據(jù)類型進(jìn)行抽象，就有了抽象數(shù)據(jù)類型。 ? 抽象數(shù)據(jù)類型（Abstract Data Type，ADT）是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作。 抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)。 比如1+1=2這樣一個(gè)操作，在不同CPU的處理上可能不一樣，但由于其定義的數(shù)學(xué)特性相同，所以在計(jì)算機(jī)編程者看來，它們都是相同的。 ? “抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。 而且，抽象數(shù)據(jù)類型不僅僅指那些已經(jīng)定義并實(shí)現(xiàn)的數(shù)據(jù)類型，還可以是計(jì)算機(jī)編程者在設(shè)計(jì)軟件程序時(shí)自己定義的數(shù)據(jù)類型。 例如一個(gè)3D游戲中，要定位角色的位置，那么總會(huì)出現(xiàn)x,y,z三個(gè)整型數(shù)據(jù)組合在一起的坐標(biāo)。 我們就可以定義一個(gè)point的抽象數(shù)據(jù)類型，它擁有x,y,z三個(gè)整型變量，這樣我們就可以方便的對(duì)一個(gè)角色的位置進(jìn)行操作。 [caption id="attachment_762" align="aligncenter" width="600"] 抽象數(shù)據(jù)類型[/caption] ? 為了便于在之后的講解中對(duì)抽象數(shù)據(jù)類型進(jìn)行規(guī)范的描述，我們給出了描述抽象數(shù)據(jù)類型的標(biāo)準(zhǔn)格式： [codesyntax lang="php"] ADT 抽象數(shù)據(jù)類型名 Data數(shù)據(jù)元素之間邏輯關(guān)系的定義 Operation操作 endADT [/codesyntax] [buy]?獲得所有教學(xué)視頻、課件、源代碼等資源打包?[/buy] [Downlink href='http://kuai.xunlei.com/d/LZXTQVVGNHYI']視頻下載[/Downlink] [Downlink href='http://urlxf.qq.com/?yYB7jm6']備胎下載[/Downlink]

轉(zhuǎn)載于:https://www.cnblogs.com/LoveFishC/archive/2012/09/27/3847238.html

總結(jié)

以上是生活随笔為你收集整理的线性表 - 数据结构和算法06的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。