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

　　線性表的定義

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

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

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

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

　　其中n為表長(zhǎng)， n=0 時(shí)稱為空表。

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

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

　　線性表的基本操作

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

　　線性表上的基本操作有：

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

　　初始條件：表L不存在

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

　　⑵ 求線性表的長(zhǎng)度：Length_List(L)

　　初始條件：表L存在

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

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

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

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

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

　　初始條件：線性表L存在

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

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

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

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

　　⑹ 刪除操作：Delete_List(L,i)

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

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

　　需要說明的是：

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

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