線性表的邏輯定義
線性表（linear list）是由n（n≥0）個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）a1，a2，…，an組成的有限序列。
① 數(shù)據(jù)元素的個(gè)數(shù)n定義為表的長度（n=0時(shí)稱為空表）。
?、?將非空的線性表（n＞0）記作：（a1，a2，…，an）
?、?數(shù)據(jù)元素ai（1≤i≤n）只是個(gè)抽象符號(hào)，其具體含義在不同情況下可以不同。
【例1】英文字母表（a，b，…，z）是線性表，表中每個(gè)字母是一個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）
【例2】一副撲克牌的點(diǎn)數(shù)（2，3，…，10，j，q，k，a）也是一個(gè)線性表，其中數(shù)據(jù)元素是每張牌的點(diǎn)數(shù)
【例3】學(xué)生成績表（見概論中表1.1）中，每個(gè)學(xué)生及其成績是一個(gè)數(shù)據(jù)元素，其中數(shù)據(jù)元素由學(xué)號(hào)、姓名、各科成績及平均成績等數(shù)據(jù)項(xiàng)組成。
線性表的邏輯結(jié)構(gòu)特征
對(duì)于非空的線性表:
?、?有且僅有一個(gè)開始結(jié)點(diǎn)a1，沒有直接前趨，有且僅有一個(gè)直接后繼a2；
② 有且僅有一個(gè)終結(jié)結(jié)點(diǎn)an，沒有直接后繼，有且僅有一個(gè)直接前趨an-1；
?、?其余的內(nèi)部結(jié)點(diǎn)ai（2≤i≤n-1）都有且僅有一個(gè)直接前趨ai-1和一個(gè)ai+1。常見的線性表的基本運(yùn)算
1． initlist（l）
構(gòu)造一個(gè)空的線性表l，即表的初始化。
2． listlength（l）
求線性表l中的結(jié)點(diǎn)個(gè)數(shù)，即求表長。
3． getnode（l，i）
取線性表l中的第i個(gè)結(jié)點(diǎn)，這里要求1≤i≤listlength（l）
4． locatenode（l，x）
在l中查找值為x 的結(jié)點(diǎn)，并返回該結(jié)點(diǎn)在l中的位置。若l中有多個(gè)結(jié)點(diǎn)的值和x 相同，則返回首次找到的結(jié)點(diǎn)位置；若l中沒有結(jié)點(diǎn)的值為x ，則返回一個(gè)特殊值表示查找失敗。
5． insertlist（l，x，i）
在線性表l的第i個(gè)位置上插入一個(gè)值為x 的新結(jié)點(diǎn)，使得原編號(hào)為i，i+1，…，n的結(jié)點(diǎn)變?yōu)榫幪?hào)為i+1，i+2，…，n+1的結(jié)點(diǎn)。這里1≤i≤n+1，而n是原表l的長度。插入后，表l的長度加1。
6． deletelist（l，i）
刪除線性表l的第i個(gè)結(jié)點(diǎn)，使得原編號(hào)為i+1，i+2，…，n的結(jié)點(diǎn)變成編號(hào)為i，i+1，…，n-1的結(jié)點(diǎn)。這里1≤i≤n，而n是原表l的長度。刪除后表l的長度減1。
注意：
以上所提及的運(yùn)算是邏輯結(jié)構(gòu)上定義的運(yùn)算。只要給出這些運(yùn)算的功能是"做什么"，至于"如何做"等實(shí)現(xiàn)細(xì)節(jié)，只有待確定了存儲(chǔ)結(jié)構(gòu)之后才考慮。
組合基本運(yùn)算，實(shí)現(xiàn)復(fù)雜運(yùn)算
對(duì)于實(shí)際問題中涉及的其它更為復(fù)雜的運(yùn)算，可以用基本運(yùn)算的組合來實(shí)現(xiàn)。
線性表（linear list）是由n（n≥0）個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）a1，a2，…，an組成的有限序列。
① 數(shù)據(jù)元素的個(gè)數(shù)n定義為表的長度（n=0時(shí)稱為空表）。
?、?將非空的線性表（n＞0）記作：（a1，a2，…，an）
?、?數(shù)據(jù)元素ai（1≤i≤n）只是個(gè)抽象符號(hào)，其具體含義在不同情況下可以不同。
【例1】英文字母表（a，b，…，z）是線性表，表中每個(gè)字母是一個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）
【例2】一副撲克牌的點(diǎn)數(shù)（2，3，…，10，j，q，k，a）也是一個(gè)線性表，其中數(shù)據(jù)元素是每張牌的點(diǎn)數(shù)
【例3】學(xué)生成績表（見概論中表1.1）中，每個(gè)學(xué)生及其成績是一個(gè)數(shù)據(jù)元素，其中數(shù)據(jù)元素由學(xué)號(hào)、姓名、各科成績及平均成績等數(shù)據(jù)項(xiàng)組成。
線性表的邏輯結(jié)構(gòu)特征
對(duì)于非空的線性表:
?、?有且僅有一個(gè)開始結(jié)點(diǎn)a1，沒有直接前趨，有且僅有一個(gè)直接后繼a2；
② 有且僅有一個(gè)終結(jié)結(jié)點(diǎn)an，沒有直接后繼，有且僅有一個(gè)直接前趨an-1；
?、?其余的內(nèi)部結(jié)點(diǎn)ai（2≤i≤n-1）都有且僅有一個(gè)直接前趨ai-1和一個(gè)ai+1。常見的線性表的基本運(yùn)算
1． initlist（l）
構(gòu)造一個(gè)空的線性表l，即表的初始化。
2． listlength（l）
求線性表l中的結(jié)點(diǎn)個(gè)數(shù)，即求表長。
3． getnode（l，i）
取線性表l中的第i個(gè)結(jié)點(diǎn)，這里要求1≤i≤listlength（l）
4． locatenode（l，x）
在l中查找值為x 的結(jié)點(diǎn)，并返回該結(jié)點(diǎn)在l中的位置。若l中有多個(gè)結(jié)點(diǎn)的值和x 相同，則返回首次找到的結(jié)點(diǎn)位置；若l中沒有結(jié)點(diǎn)的值為x ，則返回一個(gè)特殊值表示查找失敗。
5． insertlist（l，x，i）
在線性表l的第i個(gè)位置上插入一個(gè)值為x 的新結(jié)點(diǎn)，使得原編號(hào)為i，i+1，…，n的結(jié)點(diǎn)變?yōu)榫幪?hào)為i+1，i+2，…，n+1的結(jié)點(diǎn)。這里1≤i≤n+1，而n是原表l的長度。插入后，表l的長度加1。
6． deletelist（l，i）
刪除線性表l的第i個(gè)結(jié)點(diǎn)，使得原編號(hào)為i+1，i+2，…，n的結(jié)點(diǎn)變成編號(hào)為i，i+1，…，n-1的結(jié)點(diǎn)。這里1≤i≤n，而n是原表l的長度。刪除后表l的長度減1。
注意：
以上所提及的運(yùn)算是邏輯結(jié)構(gòu)上定義的運(yùn)算。只要給出這些運(yùn)算的功能是"做什么"，至于"如何做"等實(shí)現(xiàn)細(xì)節(jié)，只有待確定了存儲(chǔ)結(jié)構(gòu)之后才考慮。
組合基本運(yùn)算，實(shí)現(xiàn)復(fù)雜運(yùn)算
對(duì)于實(shí)際問題中涉及的其它更為復(fù)雜的運(yùn)算，可以用基本運(yùn)算的組合來實(shí)現(xiàn)。