導(dǎo)言
大家好，很高興又和大家見面啦?。?！從今天開始，我們將進(jìn)入線性表的學(xué)習(xí)。
線性表是算法題命題的重點(diǎn)。這類算法題實(shí)現(xiàn)起來比較容易且代碼量較少，但是要求具有最優(yōu)的性能（時(shí)間復(fù)雜度、空間復(fù)雜度），因此，我們應(yīng)該牢固掌握線性表的各種基本操作（基于兩種存儲結(jié)構(gòu)），在平時(shí)的學(xué)習(xí)中多注重培養(yǎng)動(dòng)手能力。
今天這個(gè)篇章是對線性表的一個(gè)基本知識點(diǎn)的介紹，在這個(gè)篇章里，我們將學(xué)習(xí)到什么是線性表，線性表的基本操作又有哪些，下面我們開始介紹今天的內(nèi)容。
1.線性表的定義
線性表是具有相同數(shù)據(jù)類型的n(n>=0)個(gè)數(shù)據(jù)元素的有限序列，其中n為表長，當(dāng)n=0時(shí)線性表是一個(gè)空表。
1.1 理解定義
從線性表的定義中我們可以提取到幾個(gè)信息：
- 相同類型
- n>=0
- 有限序列
通過這幾個(gè)信息，我可以知道：
- 線性表的數(shù)據(jù)元素的元素類型，只要是相同的數(shù)據(jù)類型就行；
- 線性表的元素個(gè)數(shù)可以為0，即線性表中沒有元素；
- 線性表的元素個(gè)數(shù)是有上限的，即線性表的元素有一個(gè)終點(diǎn)；
- 線性表的元素的排列是有序的，并不是雜亂無章的；
大家現(xiàn)在可以思考一下，在我們學(xué)習(xí)C語言的過程中有沒有與線性表的這些條件吻合的知識點(diǎn)呢？
有朋友很快就想到了——數(shù)組。
現(xiàn)在我們來看一下數(shù)組的一些特點(diǎn)：
- 數(shù)組的元素是相同數(shù)據(jù)類型的；
- 數(shù)組的元素的下標(biāo)是從0開始依次遞增的；
- 在定義數(shù)組時(shí)是需要指定數(shù)組大小的；
- 數(shù)組最后一個(gè)元素的下標(biāo) = 數(shù)組大小 - 1；
現(xiàn)在咱們再來對比一下線性表的定義，是不是完全符合呀！因此我們可以得到結(jié)論：
- 數(shù)組就是一種線性表
在線性表中，數(shù)據(jù)元素因?yàn)槭怯行蚺帕械?，所以每一個(gè)元素都有自己對應(yīng)的序號，我們將這個(gè)序號稱為位序；
與數(shù)組下標(biāo)不同的是，線性表數(shù)據(jù)元素的位序是從1開始的，位序?yàn)?的元素就是線性表中的第一個(gè)元素，位序?yàn)閚的元素就是線性表中的第n個(gè)元素，若用L命名線性表，則其一般表示為：
L
=
(
a
1
,
a
2
,
…
…
,
a
i
,
a
i
+
1
,
…
…
,
a
n
)
L=(a_1,a_2,……,a_i,a_{i+1},……,a_n)
L=(a1?,a2?,……,ai?,ai+1?,……,an?)
在這個(gè)式子中 a 1 a_1 a1?和 a n a_n an?分別代表的是線性表的第一個(gè)元素和線性表的最后一個(gè)元素。
1.2 線性表的圖像
在線性表中，只有唯一的“第一個(gè)”數(shù)據(jù)元素，所以我們又將
a
1
a_1
a1?稱為表頭元素；
在線性表中，也只有唯一的“最后一個(gè)”數(shù)據(jù)元素，所以我們又將
a
n
a_n
an?稱為表尾元素；
如果用圖像來表示的話，線性表的圖像應(yīng)該如下所示：
從圖中可以看到，線性表就像是被一條線串起來的。
這時(shí)可能就有朋友有疑惑了，既然它是被一條線串起來的那為什么不叫他線性串呢？
對于這個(gè)問題，我是通過字符串來進(jìn)行理解的。
在數(shù)組篇章中，我們在介紹字符串時(shí)有說過，字符串是由雙引號引起的一個(gè)或多個(gè)字符，這里不管是一個(gè)字符也好，還是多個(gè)字符也好，它的本質(zhì)上就是單一的字符，就比如"abc123" 這個(gè)字符串，它是由字符a、b、c、1、2、3這六個(gè)字符加上\0組成的，我們在看到這些元素的時(shí)候能夠得到的信息也就是單一的信息。
而對于線性表而言，它的每一個(gè)數(shù)據(jù)元素都是由不同的數(shù)據(jù)項(xiàng)組成的，也就是說，一個(gè)數(shù)據(jù)元素中可能含有多個(gè)數(shù)據(jù)項(xiàng)，就比如班級里每次考試完會(huì)按學(xué)生的總分進(jìn)行排名，如下圖所示：
在這個(gè)排名表中，這里的數(shù)據(jù)元素
a
1
a_1
a1?到
a
6
0
a_60
a6?0它們包含了4個(gè)數(shù)據(jù)項(xiàng)，并不是像字符串這種只有單一數(shù)據(jù)項(xiàng)的元素，因此，我們在看到
a
1
a_1
a1?后可以了解到這所有的信息，就像這里的這張排名表一樣；
1.3 線性表的邏輯特性
同樣還是一張排名表，下面大家來判斷一下，這個(gè)排名表是不是線性表：
在這個(gè)排名表中，有兩個(gè)并列第一，兩個(gè)并列第五，三個(gè)并列第八，我們現(xiàn)在來根據(jù)線性表的定義來判斷；
- 這里的數(shù)據(jù)元素的數(shù)據(jù)類型都是相同的——由排名、姓名、學(xué)號、總分這四個(gè)元素組成的結(jié)構(gòu)體類型；
- 這里的排名都是有序的，按照從小到大的次序來排列的；
- 這里的元素是有限的，總共有十個(gè)元素；
單從這些點(diǎn)看的話，這張表也是屬于線性表的。但是對于一個(gè)線性表，它不僅僅只需要滿足這些條件，它還需要滿足以下的邏輯特性：
- 表頭元素與表尾元素都是唯一的；
- 除了表頭元素外，其它的每個(gè)元素有且僅有一個(gè)直接前驅(qū)；
- 除了表尾元素外，其它的每個(gè)元素有且僅有一個(gè)直接后繼；
下面我們再來看這張表：
- 劉一和陳二并列第一——并不滿足唯一的表頭元素；
- 對于張三來說，他擁有兩個(gè)直接前驅(qū)——并不滿足有且僅有一個(gè)直接前驅(qū)；
- 王五和趙六并列第五，對于李四來說，他擁有兩個(gè)直接后繼——并不滿足有且僅有一個(gè)直接后繼；
- 對于孫七來說，他擁有兩個(gè)直接前驅(qū)——并不滿足有且僅有一個(gè)直接前驅(qū)；
- 周八、吳九和鄭十并列第八——并不滿足唯一的表尾元素；
- 對于孫七來說，他擁有三個(gè)直接后繼——并不滿足有且僅有一個(gè)直接后繼；
通過這些邏輯特性判斷，這張表并不是一個(gè)線性表。
因此我們可以得知線性表是指這種線性有序的邏輯結(jié)構(gòu)，這也是線性表這個(gè)名字的由來；
2.線性表的特點(diǎn)
對于線性表這種線性有序的邏輯結(jié)構(gòu)，它具有以下的特點(diǎn)：
- 表中元素的個(gè)數(shù)是有限的；
- 表中元素具有邏輯上的順序性，表中元素有其先后次序；
- 表中元素都是數(shù)據(jù)元素，每個(gè)元素都是單個(gè)元素；
- 表中元素的數(shù)據(jù)類型都相同，這意味著每個(gè)元素占有相同大小的存儲空間；
- 表中元素具有抽象性，即僅討論元素間的邏輯關(guān)系，而不考慮元素究竟表示什么內(nèi)容。
注意：線性表是一種邏輯結(jié)構(gòu)，表示元素之間一對一的相鄰關(guān)系。后面提到的順序表和鏈表是指存儲結(jié)構(gòu)，兩者屬于不同層面的概念，因此不要將其混淆。
3.線性表的基本操作
一個(gè)數(shù)據(jù)結(jié)構(gòu)的基本操作是指其最核心、最基本的操作。其它較復(fù)雜的操作可通過調(diào)用其基本操作來實(shí)現(xiàn)。線性表最主要的操作如下：
- 創(chuàng)建與銷毀
- InitList(&L)：初始化表。構(gòu)造一個(gè)空的線性表；
- DestroyList(&L)：銷毀操作。銷毀線性表，并釋放線性表L所占用的內(nèi)存空間。
- 插入與刪除
- ListInSERT(&L,i,e)：插入操作。在表L中第i個(gè)位置插入指定元素e；
- ListDelete(&L,i,&e)：刪除操作。刪除表L中第i個(gè)位置的元素，并用e返回刪除元素的值；
- 查找
- LocateElem(L,e)：按值查找操作。在表L中查找具有給定關(guān)鍵字值的元素；
- GetElem(L,i)：按位查找操作。獲取表L中第i個(gè)位置的元素的值；
- 其它操作
- Length(L)：求表長。返回線性表L的長度，即L中數(shù)據(jù)元素的個(gè)數(shù)；
- PrintList(L)：輸出操作。按前后順序輸出線性表L的所有元素值；
- Empty(L)：判空操作。若L為空表，則返回true，否則返回false；
對于這些基本操作，有些地方我們需要注意：
- 對數(shù)據(jù)的操作無非就是——創(chuàng)建、銷毀、增刪改查；
- 我們可以根據(jù)實(shí)際情況來定義其它的基本操作，如這里的求表長、輸出、判空等；
- 這里的操作內(nèi)容并不是C語言提供的庫函數(shù)，而是需要我們自己進(jìn)行自定義的函數(shù)；
- 對于這些操作名，我們可以根據(jù)自己的喜好來定義，但是命名要有可讀性；
- 這里展示的符號&表示C++語言中的引用調(diào)用，在C語言中采用指針也可達(dá)到同樣的效果；
- 基本操作的實(shí)現(xiàn)取決于采用那種存儲結(jié)構(gòu)，存儲結(jié)構(gòu)不同，算法的實(shí)現(xiàn)也不同；
在了解完這些基本操作后，下面大家來思考一個(gè)問題：
為什么要實(shí)現(xiàn)對數(shù)據(jù)結(jié)構(gòu)的基本操作？
這是因?yàn)槲覀冊诮窈蟮墓ぷ髦薪?jīng)常是團(tuán)隊(duì)合作的形式進(jìn)行編程的，所以我們在編程的過程中需要將自己定義的數(shù)據(jù)結(jié)構(gòu)通過函數(shù)的形式進(jìn)行封裝，以此來方便其他的成員進(jìn)行使用；
其次將常用的操作/運(yùn)算封裝成函數(shù)也可以避免重復(fù)工作，降低出錯(cuò)的風(fēng)險(xiǎn)，大大的提高編程的效率；文章來源：http://www.zghlxwxcb.cn/news/detail-777809.html
結(jié)語
今天的內(nèi)容到這里就結(jié)束了，在這個(gè)篇章中，我們介紹了什么是線性表，線性表有哪些特點(diǎn)，以及對于線性表有哪些基本操作。
在介紹這些內(nèi)容的同時(shí)，我們了解了幾個(gè)重要的術(shù)語——表長、空表、表頭、表尾、前驅(qū)、后繼、數(shù)據(jù)元素的位序（從1開始）。
今天對線性表的基本操作只是簡單的提及了一下，并未展開進(jìn)行詳細(xì)介紹，在后續(xù)的篇章中，我會(huì)代碼來實(shí)現(xiàn)這些基本操作，大家在閱讀完這一篇章只需要了解這些基礎(chǔ)知識點(diǎn)就行。
最后，感謝大家的翻閱，咱們下一篇再見！?。?span toymoban-style="hidden">文章來源地址http://www.zghlxwxcb.cn/news/detail-777809.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】第二章——線性表(1)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
