線性結(jié)構(gòu)是最常用、最簡單的一種數(shù)據(jù)結(jié)構(gòu)。而線性表是一種典型的線性結(jié)構(gòu)。其基本特點是線性表中的數(shù)據(jù)元素是有序且是有限的。在這種結(jié)構(gòu)中：
?、?存在一個唯一的被稱為“第一個”的數(shù)據(jù)元素；
?、?存在一個唯一的被稱為“最后一個”的數(shù)據(jù)元素；
?、?除第一個元素外，每個元素均有唯一一個直接前驅(qū)；
?、?除最后一個元素外，每個元素均有唯一一個直接后繼。
線性表的定義
線性表(Linear List) ：是由n(n≧0)個數(shù)據(jù)元素(結(jié)點)a1，a2， …an組成的有限序列。該序列中的所有結(jié)點具有相同的數(shù)據(jù)類型。其中數(shù)據(jù)元素的個數(shù)n稱為線性表的長度。
- 當n=0時，稱為空表。
- 當n>0時，將非空的線性表記作： (a1，a2，…an)
- a1稱為線性表的第一個(首)結(jié)點，an稱為線性表的最后一個(尾)結(jié)點。
- a1，a2，…ai-1都是ai(2≦i≦n)的前驅(qū)，其中ai-1是ai的直接前驅(qū);
- ai+1，ai+2，…an都是ai(1≦i ≦n-1)的后繼，其中ai+1是ai的直接后繼。
線性表的順序存儲結(jié)構(gòu)
順序存儲 ：把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。
順序存儲的線性表的特點：
- 線性表的邏輯順序與物理順序一致;
- 數(shù)據(jù)元素之間的關(guān)系是以元素在計算機內(nèi)“物理位置相鄰”來體現(xiàn)。
設(shè)有非空的線性表：(a1，a2，…an) 。順序存儲如下圖1-1所示。
設(shè)線性表的每個元素需占用l個存儲單元，以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC(ai+1)和第i個數(shù)據(jù)元素的存儲位置LOC(ai)之間滿足下列關(guān)系：
LOC(ai+1)=LOC(ai)+l
線性表的第i個數(shù)據(jù)元素ai的存儲位置為：
LOC(ai)=LOC(a1)+(i-1)*l
線性表的鏈式存儲結(jié)構(gòu)
__鏈式存儲 __：用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素。用這種方法存儲的線性表簡稱線性鏈表。
存儲鏈表中結(jié)點的一組任意的存儲單元可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。
鏈表中結(jié)點的邏輯順序和物理順序不一定相同。
為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存儲指示其后繼結(jié)點的地址（或位置），稱為指針或鏈(link）
鏈表的結(jié)點結(jié)構(gòu)
┌───┬───┐
│data │next │
└───┴───┘
data域--存放結(jié)點值的數(shù)據(jù)域
next域--存放結(jié)點的直接后繼的地址（位置）的指針域（鏈域）
注意：
①鏈表通過每個結(jié)點的鏈域?qū)⒕€性表的n個結(jié)點按其邏輯順序鏈接在一起的。
②每個結(jié)點只有一個鏈域的鏈表稱為單鏈表（Single Linked List）
