數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)之線性表邏輯結(jié)構(gòu)_跨考網(wǎng)

　　線性表的定義

　　線性表是一種線性結(jié)構(gòu)。線性結(jié)構(gòu)的特點是數(shù)據(jù)元素之間是一種線性關(guān)系，數(shù)據(jù)元素“一個接一個的排列”。在一個線性表中數(shù)據(jù)元素的類型是相同的，或者說線性表是由同一類型的數(shù)據(jù)元素構(gòu)成的線性結(jié)構(gòu)。在實際問題中線性表的例子是很多的，如學(xué)生情況信息表是一個線性表：表中數(shù)據(jù)元素的類型為學(xué)生類型; 一個字符串也是一個線性表：表中數(shù)據(jù)元素的類型為字符型，等等。

　　綜上所述，線性表定義如下：

　　線性表是具有相同數(shù)據(jù)類型的n(n>=0)個數(shù)據(jù)元素的有限序列，通常記為：

　　(a1，a2，… ai-1，ai，ai+1，…an)

　　其中n為表長， n=0 時稱為空表。

　　表中相鄰元素之間存在著順序關(guān)系。將 ai-1 稱為 ai 的直接前趨，ai+1 稱為 ai 的直接后繼。就是說：對于ai，當(dāng) i=2，...，n 時，有且僅有一個直接前趨 ai-1.，當(dāng)i=1，2，...，n-1 時，有且僅有一個直接后繼 ai+1，而 a1 是表中第一個元素，它沒有前趨，an 是最后一個元素?zé)o后繼。

　　需要說明的是：ai為序號為 i 的數(shù)據(jù)元素(i=1,2,…,n)，通常我們將它的數(shù)據(jù)類型抽象為datatype，datatype根據(jù)具體問題而定，如在學(xué)生情況信息表中，它是用戶自定義的學(xué)生類型; 在字符串中，它是字符型; 等等。

　　線性表的基本操作

　　在第一章中提到，數(shù)據(jù)結(jié)構(gòu)的運算是定義在邏輯結(jié)構(gòu)層次上的，而運算的具體實現(xiàn)是建立在存儲結(jié)構(gòu)上的，因此下面定義的線性表的基本運算作為邏輯結(jié)構(gòu)的一部分，每一個操作的具體實現(xiàn)只有在確定了線性表的存儲結(jié)構(gòu)之后才能完成。

　　線性表上的基本操作有：

　?、?線性表初始化：Init_List(L)

　　初始條件：表L不存在

　　操作結(jié)果：構(gòu)造一個空的線性表

　?、?求線性表的長度：Length_List(L)

　　初始條件：表L存在

　　操作結(jié)果：返回線性表中的所含元素的個數(shù)

　?、?取表元：Get_List(L,i)

　　初始條件：表L存在且1<=i<=Length_List(L)

　　操作結(jié)果：返回線性表L中的第i個元素的值或地址

　?、?按值查找：Locate_List(L,x)，x是給定的一個數(shù)據(jù)元素。

　　初始條件：線性表L存在

　　操作結(jié)果：在表L中查找值為x的數(shù)據(jù)元素，其結(jié)果返回在L中首次出現(xiàn)的值為x的那個元素的序號或地址，稱為查找成功; 否則，在L中未找到值為x的數(shù)據(jù)元素，返回一特殊值表示查找失敗。

　?、?插入操作：Insert_List(L,i,x)

　　初始條件：線性表L存在，插入位置正確 (1<=i<=n+1,n為插入前的表長)。

　　操作結(jié)果：在線性表L的第 i 個位置上插入一個值為 x 的新元素，這樣使原序號為 i , i+1, ... , n 的數(shù)據(jù)元素的序號變?yōu)?i+1,i+2, ... , n+1，插入后表長=原表長+1。

　?、?刪除操作：Delete_List(L,i)

　　初始條件：線性表L存在，1<=i<=n。

　　操作結(jié)果：在線性表L中刪除序號為i的數(shù)據(jù)元素，刪除后使序號為 i+1, i+2,..., n 的元素變?yōu)樾蛱枮?i, i+1,...,n-1，新表長=原表長-1。

　　需要說明的是：

　　1. 某數(shù)據(jù)結(jié)構(gòu)上的基本運算，不是它的全部運算，而是一些常用的基本的運算，而每一個基本運算在實現(xiàn)時也可能根據(jù)不同的存儲結(jié)構(gòu)派生出一系列相關(guān)的運算來。比如線性表的查找在鏈?zhǔn)酱鎯Y(jié)構(gòu)中還會有按序號查找; 再如插入運算，也可能是將新元素x插入到適當(dāng)位置上等等，不可能也沒有必要全部定義出它的運算集，讀者掌握了某一數(shù)據(jù)結(jié)構(gòu)上的基本運算后，其它的運算可以通過基本運算來實現(xiàn)，也可以直接去實現(xiàn)。

　　2. 在上面各操作中定義的線性表L僅僅是一個抽象在邏輯結(jié)構(gòu)層次的線性表，尚未涉及到它的存儲結(jié)構(gòu)，因此每個操作在邏輯結(jié)構(gòu)層次上尚不能用具體的某種程序語言寫出具體的算法，而算法的實現(xiàn)只有在存儲結(jié)構(gòu)確立之后。