考點剖析

????????線性表是算法題命題的重點，該類題目實現(xiàn)相對容易且代碼量不高，但需要最優(yōu)的性能（也就是其時間復(fù)雜度以及空間復(fù)雜度最優(yōu)），這樣才可以獲得滿分。所以在考研復(fù)習(xí)中，我們需要掌握線性表的基本操作，在平時多進(jìn)行代碼練習(xí)。當(dāng)然在考場上，我們并不一定要求代碼具有實際的可執(zhí)行性，但我們需要去清晰的表達(dá)出算法的思路步驟，且算法題目只允許使用 C/C++ 語言進(jìn)行實現(xiàn)。

線性表知識點

? ? ? ? 關(guān)于線性表這章內(nèi)容其實并不多，我們將其分為兩大部分：順序存儲（也就是我們常說的順序表）和鏈?zhǔn)酱鎯Γㄦ湵恚?，其中對于鏈表部分我們需要掌握其中?單鏈表、雙鏈表、循環(huán)鏈表、靜態(tài)鏈表等部分鏈表。

? ? ? ? 關(guān)于線性表的內(nèi)容并不是太難，我將用3-4篇文章帶著大家一起了解線性表以及其實現(xiàn)，當(dāng)我們可以自己去實現(xiàn)其功能的時候，我們對于該部分內(nèi)容的知識掌握也就十分的熟練了，那么廢話不多說，我們下面開始正式的進(jìn)入線性表的學(xué)習(xí)。

線性表的定義

? ? ? ? 線性表是具有相同數(shù)據(jù)類型的 n ( n?? 0) 個數(shù)據(jù)元素的有限序列，其中n為表長；當(dāng)n=0時，線性表為空表。在這里我們以L命名線性表，可以將其表示為：

? ? ? ? 其中：?是線性表的第一個元素，我們也稱其為表頭元素；是線性表的最后一個元素，我們稱其為表尾元素。

? ? ? ??除了第一個元素外，每個元素有且僅有一個直接前驅(qū)（前一個元素）；除了最后一個元素外，每個元素有且僅有一個直接后續(xù)（后一個元素）。當(dāng)然我們也可以將“直接前驅(qū)”稱為“前驅(qū)”，將“直接后續(xù)”稱為“后續(xù)”。

? ? ? ? 通過已上知識我們總結(jié)出線性表的特點如下所示：

• 線性表元素個數(shù)有限
• 線性表元素都是數(shù)據(jù)元素，每個元素都是單個元素
• 線性表的元素具有邏輯上的順序性，表中的元素有其先后次序
• 線性表的數(shù)據(jù)類型都相同，所以其每個元素所占空間大小相同
• 線性表的元素具有抽象性，我們討論元素間的邏輯關(guān)系，不考慮元素究竟表示什么內(nèi)容

?注：線性表是邏輯結(jié)構(gòu)，表示元素一對一的相鄰關(guān)系，而我們前面所了解的鏈表以及順序表指的是存儲結(jié)構(gòu)。（也就是說線性表的順序存儲是順序表，線性表的鏈?zhǔn)酱鎯κ擎湵?；這兩個只是在存儲結(jié)構(gòu)上存在差異，而其邏輯結(jié)構(gòu)歸根結(jié)底都是線性表）。

線性表的基本操作

? ? ? ? 對于線性表，有一些基本操作是需要我們?nèi)W(xué)習(xí)的，至于為什么要學(xué)習(xí)這些基本操作，當(dāng)然408大綱要求是要學(xué)習(xí)的，但在這里我們還是可以了解一下原因的。我們?nèi)σ恍?shù)據(jù)結(jié)構(gòu)的基本操作進(jìn)行封裝實現(xiàn)，這樣我們在進(jìn)行復(fù)雜的操作時，可以去調(diào)用相關(guān)基本操作進(jìn)行實現(xiàn)，并且這樣進(jìn)行封裝也有利于減少錯誤的產(chǎn)生。

? ? ? ? 線性表的基本操作如下所示：

InitList(&L);    //線性表的初始化
DestroyList(&L);    //銷毀線性表

ListInsert(&L,i,e);    //線性表的插入
ListDelete(&L,i,&e);    //線性表的刪除

LocateElem(L,e);    //按值查找
GetElem(L,i);    //按位查找

Length(L);    //求線性表長
PrintList(L);    //按順序輸出線性表的所有值
Empty(L);    //判斷線性表是否為空

（如果不懂為什么要加“&”的同學(xué)可以去學(xué)習(xí)一下，簡單來說加“&”的元素我們可以修改其值，它會將其值帶回來，而不加的我們在函數(shù)中修改其值是在主函數(shù)中無效的）。? ? ? ??

注：在這里線性表只是一種邏輯結(jié)構(gòu)，我們對于其基本操作的實現(xiàn)是要基于存儲結(jié)構(gòu)的，不同的存儲結(jié)構(gòu)實現(xiàn)其功能的方法是不同的，所以對于這些基本操作的實現(xiàn)，我會在后面順序表和鏈表的講解中進(jìn)行代碼的實現(xiàn)，在這里我們僅對其基本操作有一個了解即可。?

小測試

1. ?線性表是一個可以存不同數(shù)據(jù)類型的n ( n?? 0) 個數(shù)據(jù)元素的有限序列嗎？
2. 在線性表中每一個元素都有自己的前驅(qū)和后續(xù)元素嗎？
3. 不同的線性表的邏輯結(jié)構(gòu)必然存在一些差異性。對嗎？

答案

1. 錯，線性表需要存儲相同的數(shù)據(jù)類型。

2. 錯，第一個元素不存在前驅(qū)，最后一個元素不存在后續(xù)。

3. 錯，線性表的邏輯結(jié)構(gòu)是相同的。?文章來源地址http://www.zghlxwxcb.cn/news/detail-825153.html

到了這里，關(guān)于【玩轉(zhuǎn)408數(shù)據(jù)結(jié)構(gòu)】線性表——定義和基本操作的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！