線性結構是最簡單且最常用的數據結構線性表是一種典型的線性結構
線性表的邏輯定義
線性表(Linear List)是由n(n≥)個數據元素(結點)a a …a n 組成的有限序列
① 數據元素的個數n定義為表的長度(n=時稱為空表)
② 將非空的線性表(n>)記作(a a …a n )
③ 數據元素a i (≤i≤n)只是個抽象符號其具體含義在不同情況下可以不同
【例】英文字母表(AB…Z)是線性表表中每個字母是一個數據元素(結點)
【例】一副撲克牌的點數(…JQKA)也是一個線性表其中數據元素是每張牌的點數
【例】學生成績表(見概論中表)中每個學生及其成績是一個數據元素其中數據元素由學號姓名各科成績及平均成績等數據
項組成
線性表的邏輯結構特征
對於非空的線性表:
① 有且僅有一個開始結點a 沒有直接前趨有且僅有一個直接後繼a ;
② 有且僅有一個終結結點a n 沒有直接後繼有且僅有一個直接前趨a n ;
③ 其余的內部結點a i (≤i≤n)都有且僅有一個直接前趨a i 和一個a i+
常見的線性表的基本運算
InitList(L)
構造一個空的線性表L即表的初始化
ListLength(L)
求線性表L中的結點個數即求表長
GetNode(Li)
取線性表L中的第i個結點這裡要求≤i≤ListLength(L)
LocateNode(Lx)
在L中查找值為x 的結點並返回該結點在L中的位置若L中有多個結點的值和x 相同則返回首次找到的結點位置;若L中沒有結點的值為x
則返回一個特殊值表示查找失敗
InsertList(Lxi)
在線性表L的第i個位置上插入一個值為x 的新結點使得原編號為ii+…n的結點變為編號為i+i+…n+的結點這裡
≤i≤n+而n是原表L的長度插入後表L的長度加
DeleteList(Li)
刪除線性表L的第i個結點使得原編號為i+i+…n的結點變成編號為ii+…n的結點這裡≤i≤n而n是原表L的長度刪
除後表L的長度減
注意
以上所提及的運算是邏輯結構上定義的運算只要給出這些運算的功能是做什麼至於如何做等實現細節只有待確定了存儲結構之後
才考慮
組合基本運算實現復雜運算
對於實際問題中涉及的其它更為復雜的運算可以用基本運算的組合來實現具體請【參見參考書目】
From:http://tw.wingwit.com/Article/program/sjjg/201311/23581.html
