線性鏈表

線性鏈表

具有鏈接存儲結構的線性表，它用一組地址任意的存儲單元存放線性表中的數據元素，邏輯上相鄰的元素在物理上不要求也相鄰，不能隨機存取。一般用結點描述：結點（表示數據元素） =數據域（數據元素的映象） + 指針域（指示後繼元素存儲位置）

目錄

1概念 2實現 3單鏈線性表

概念

在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關係可以不一致，而數據元素之間的邏輯關係是由指針域來確定的。鏈式存儲方式即可以用於表示線性結構，也可用於表示非線性結構。

一般來說，在線性表的鏈式存儲結構中，各數據結點的存儲符號是不連續的，並且各結點在存儲空間中的位置關係與邏輯關係也不一致。對於線性鏈表，可以從頭指針開始，沿各結點的指針掃描到鏈表中的所有結點。

實現

(1) 線性表的操作GetElem(L, i, &e)在鏈表中的實現:

基本操作為: 使指針p始終指向線性表中第j個數據元素

Status GetElem_L(LinkList L, int i, ElemType &e)// L為帶頭結點的單鏈表的頭指針。當線性表中存在第i個元素時，則將第i個數據元素的值賦給e並返回OK，否則返回ERROR

{p = L->next; j = 1; // 初始化，p指向第一個結點，j為計數器

while (p && j); // 順指針向後查找，直到p指向第i個元素或p為空

p = p->next; ++j; }

線性鏈表

線性鏈表

if ( !p || j>i ) return ERROR; // 第i個元素不存在

e = p->data; // 取第i個元素

return OK;

} // GetElem_L演演算法的時間複雜度為:O(ListLength(L))

(2) 線性表的操作ListInsert(&L, i, e)在鏈表中的實現:

基本操作為: 找到線性表中第i-1個結點，修改其指向後繼的指針

有序對改變為和

線性鏈表

線性鏈表

Status ListInsert_L(LinkList L, int i, ElemType e) {

// 在帶頭結點的單鏈表L中第i個數據元素之前插入數據元素e

p = L; j = 0;

while(p && j < i-1)

{ p = p->next; ++j; } // 尋找第i-1個結點

if (!p||j > i-1)returnERROR; // i小於1或者大於表長

s = (LinkList)malloc(sizeof(LNode)); // 生成新結點

s->data = e; s->next = p->next; // 插入L中

p->next = s;

returnOK;

} // LinstInsert_L演演算法的時間複雜度為:O(ListLength(L))

(3) 線性表的操作ListDelete(&L, i, &e)在鏈表中的實現：

基本操作為: 找到線性表中第i-1個結點，修改其指向後繼的指針

有序對和改變為

Status ListDelete_L(LinkList L, int i, ElemType &e)

{ p = L; j = 0;} // 在帶頭結點的單鏈表L中，刪除第i個元素，並由e返回其值

while (p->next && j < i-1)

{p = p->next; ++j; // 尋找第i個結點，並令p指向其前趨}

if (!(p->next) || j > i-1)returnERROR; // 刪除位置不合理

q = p->next; p->next = q->next; // 刪除並釋放結點

e = q->data; free(q);

returnOK;

} // ListDelete_L演演算法的時間複雜度為:O(ListLength(L))

單鏈線性表

在線性表的鏈接存儲中，為了方便在表頭插入和刪除結點的操作，經常在表頭結點（存儲第一個元素的結點）的前面增加一個結點，稱之為頭結點或表頭附加結點。這樣原來的表頭指針由指向第一個元素的結點改為指向頭結點，頭結點的數據域為空，頭結點的指針域指向第一個元素的結點。

定義一個帶頭結點的線性鏈表類型：

typedefstruct LNode // 結點類型

{

ElemType data;

structLNode*next;

}*Link,*Position;

typedef struct // 鏈表類型

{ Link head, tail; // 指向頭結點和最後一個結點

intlen; // 指示鏈表長度

Link current; // 指向當前訪問的結點的指針，初始位置指向頭結點

}

LinkList;

StatusMakeNode( Link&p, ElemType e );

// 分配由p指向的值為e的結點，並返回OK；若分配失敗，則返回ERROR

void FreeNode( Link&p ); // 釋放p所指結點

創建帶頭結點的單鏈線性表：

void CreateList_L(LinkList &L, int n) // 逆位序輸入n個元素的值，建立帶表頭結點的單鏈線性表L。

{ L = (LinkList)malloc(sizeof(LNode));

L->next =NULL; // 先建立一個帶頭結點的單鏈表

for(i = n; i > 0; --i) {

p = (LinkList)malloc(sizeof(LNode)); // 生成新結點

scanf(&p->data); // 輸入元素值

p->next = L->next; L->next = p; // 插入到表頭

}

} // CreateList_L演演算法的時間複雜度為:O(Listlength(L))

目錄