線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) :

鏈?zhǔn)酱鎯?chǔ)表示 :

typedef struct LNode{

?

? ElemType ? data;

? Struct LNode *next;

?

}LNode,*LinkList;

基本操作在鏈表上的實(shí)現(xiàn) :

(1) ?? 單鏈表的取元素算法（經(jīng)典）

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

{

?

p=L->next; j=1;

while(p && j<i)

{

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

}

if(!p || j>i) return ERROR;

e=p->data;

return OK;

?

}

算法分析 :

基本操作是 : 比較 j 和 I, 并把指針后移 , 循環(huán)體執(zhí)行的次數(shù) , 與被查元素的位置有關(guān) . 假設(shè)表長為 n, 如果 1<=i<=n, 那么循環(huán)體中語句的執(zhí)行次數(shù)為 i-1. 否則次數(shù)為 n 所以時(shí)間復(fù)雜度為 O(n).

?

? (2) ?? 插入元素算法

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

{

?

?? p=L;j=0;

?? while(p&&j<i-1)

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

?? if(!p || j>i-1)

????? return ERROR;

?

?? s = (LinkList)malloc(sizeof(LNode));

?? s->data = e;

?? s->next = p->next;

?? p->next =s;

?? return OK;

}
(3) ?? 刪除元素算法

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

{

?? p=L;j=0;

while(p &&j<i-1)

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

if(!p ||j>i-1)

????? return? ERROR;

??

q=p->next;

?? p->next =q->next;

?? e =q->data;

?? free(q);

?? return OK;

}

?

算法分析 :

插入和刪除算法 , 都要先找到第 i-1 個(gè)節(jié)點(diǎn) , 所以時(shí)間復(fù)雜度為 O(n);

? (4) ?? 單鏈表的建立算法

?

void CreateList_L(LinkList &L,int n){

?

?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;

? }

?

}

算法分析 :

按照逆序循環(huán)輸入 n 個(gè)數(shù)據(jù)元素的值 , 建立新節(jié)點(diǎn) . 并插入 . 因此算法的時(shí)間復(fù)雜度為 O(n).