數(shù)據(jù)結構—線性表

1.線性表的定義和基本操作

線性表的定義

定義：線性表是具有相同數(shù)據(jù)類型的n(n≥0)個數(shù)據(jù)元素的有限序列。（n=0時稱為空表）

線性表的特點

• 表中元素的個數(shù)有限。
• 表中元素具有邏輯上的順序性，表中元素有其先后次序。
• 表中元素都是數(shù)據(jù)元素，每個元素都是單個元素。
• 表中元素的數(shù)據(jù)類型都相同，這意味著每個元素占用相同大小的存儲空間。
• 表中元素具有抽象性，即討論元素間的邏輯關系，而不考慮元素元素的內容。

注意：線性表是一種邏輯結構，表示元素之間一對一的相鄰關系。順序表和鏈表是指存儲結構，兩者屬于不同層面的概念，因此不要將其混淆。

線性表的基本操作

• InitList(&L) 初始化表。操作結果：構造一個空的線性表L。
• GetElem(L，i，&e) 線性表的取值。初始條件：線性表L已存在，且1≤i≤ListLength(L)。操作結果：用e返回L中第i個數(shù)據(jù)元素的值。
• LocateElem(L，e) 線性表的查找。初始條件：線性表L已存在。操作結果：返回L中第1個值與e相同的元素在L中的位置。若這樣的數(shù)據(jù)元素不存在，則返回值為0。
• ListInsert(&L，i，e) 線性表的插入。初始條件：線性表L已存在，且1≤i≤ListLength(L)+1。操作結果：在L的第i個位置之前插入新的數(shù)據(jù)元素e，L的長度加1。
• ListDelete(&L，i) 線性表的刪除。初始條件：線性表L已存在且非空，且1≤i≤ListLength(L)。操作結果：刪除L的第i個數(shù)據(jù)元素，L的長度加1。

注意：符號“&”表示C++語言中的引用調用。

2.線性表的順序存儲和鏈式存儲表示

順序存儲

• 線性表的順序表示指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，這種表示也稱為線性表的順序存儲結構或順序映像。通常，稱這種存儲結構的線性表為順序表(Sequential List)。
• 特點：邏輯上相鄰的數(shù)據(jù)元素，其物理次序也是相鄰的。順序存儲結構是一種隨機存取的存儲結構。
• 假設線性表L存儲的起始位置為LOC(A)，sizeof(ElemType)是每個數(shù)據(jù)元素所占用存儲空間的大小。

數(shù)組下標	內存狀態(tài)	內存地址	位序
0	a1	LOC(A)	1
1	a2	LOC(A)+sizeof(ElemType)	2
i-1	ai	LOC(A)+(i-1)sizeof(ElemType)	i
n-1	an	LOC(A)+(n-1)sizeof(ElemType)	n

• 注意：要區(qū)分清楚位序和下標；線性表中元素的位序是從1開始的，而數(shù)組中元素的下標是從0開始的。

鏈式存儲

單鏈表

• 線性表的鏈式存儲又稱單鏈表，它是指通過一組任意的的存儲單元來存儲線性表中的數(shù)據(jù)元素。為了建立數(shù)據(jù)元素之間的線性關系，對每個鏈表結點，除存放元素自身的信息外，還需要存放一個指向其后繼結點的指針； 其中存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域(data)；存放直接后繼存儲位置的域稱為指針域(next)。
• 首元結點是指鏈表中存儲第一個元素a1的結點。
• 頭結點是在首元結點之前附設一個結點，其指針域指向首元結點。頭結點的數(shù)據(jù)域可以不存儲任何信息，也可以存儲與數(shù)據(jù)元素類型相同的其他附加信息。
• 鏈表增加頭結點的作用：
  1. 便于首元結點的處理：增加了頭結點后，首元結點的地址保存在頭結點的指針域中，則對鏈表的第一個數(shù)據(jù)元素的操作與其他數(shù)據(jù)元素相同，無需進行特殊處理。
  2. 便于空表與非空表的統(tǒng)一處理：當不設頭結點時，假設L為單鏈表的頭指針，它應該指向首元結點，則當鏈表長度為0時，L指針為空(判定空表的條件記為：L==NULL);增加頭結點后，無論鏈表是否為空，頭指針都是指向頭結點的非空指針。若為空表，則頭結點的指針域為空(判定空表的條件可記為：L->next==NULL)。
• 特點：邏輯上相鄰的數(shù)據(jù)元素，其物理次序不一定相鄰；單鏈表為順序存取結構。

循環(huán)鏈表

• 循環(huán)鏈表(Circular Linked List)：是一種頭尾相接的鏈表（即表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環(huán)）。
  

• 優(yōu)點：從表中任意一結點出發(fā)均可找到表中其他結點。

• 注意：由于循環(huán)鏈表中沒有NULL指針，故涉及遍歷操作時，其終止條件就不再像非循環(huán)鏈表那樣判斷P或P->next是否為空，而是判斷它們是否等于頭指針。

雙向鏈表

• 雙向鏈表(Double Linked List)：在單鏈表的每個節(jié)點里增加一個指向其直接前驅的指針域prior，這樣鏈表中就形成了有兩個方向不同的鏈，故稱為雙向鏈表。
  

• 在單鏈表中，查找直接后繼結點的執(zhí)行時間為O(1)，而查找直接前驅的執(zhí)行時間為O(n)。為了克服單鏈表這種單向性的缺點，可利用雙向鏈表。