本文是個人學(xué)習(xí)筆記，素材來自青島大學(xué)王卓老師的教學(xué)視頻。

一方面用于學(xué)習(xí)記錄與分享，另一方面是想讓更多的人看到這么好的《數(shù)據(jù)結(jié)構(gòu)與算法》的學(xué)習(xí)視頻。

如有侵權(quán)，請留言作刪文處理。

課程視頻鏈接：

數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)–第3周11–2.5線性表的鏈式表示和實現(xiàn)11–單鏈表基本操作9–查找插入刪除算法分析

?? ?? ?? ?? ?? ?? ? ?? ?? ? ?? ?? ?? ?? ?? ?? ?

?? 【W(wǎng)eek03】11_線性表的鏈式表示和實現(xiàn)10

單鏈表查找插入刪除算法分析

【查找算法】

【算法描述】按值查找：根據(jù)指定數(shù)據(jù)，獲取該數(shù)據(jù)地址（返回地址）

// 在線性表 L 中查找值為 e 的數(shù)據(jù)元素
// 找到，則返回 L 中值為 e 的數(shù)據(jù)元素的地址
// 查找失敗，返回 NULL
Lnode *LocateElem_L(LinkList L, ElemType e){
	// 初始化
    p = L->next;
    // 依次向后掃描
    while(p && (p->data!= e)){
        p = p->next;
    }
    
    return p;
}

【算法描述】按值查找：根據(jù)指定數(shù)據(jù)，獲取該數(shù)據(jù)位置序號（返回位置）

// 在線性表 L 中查找值為 e 數(shù)據(jù)元素的位置序號
// 找到，則返回 L 中值為 e 的數(shù)據(jù)元素的位置序號
// 查找失敗，返回 NULL
int LocateElem_L(LinkList L, ElemType e){
	// 初始化
    p = L->next;
    j = 1;
    // 依次向后掃描
    while(p && (p->data!= e)){
        p = p->next;
        j++;
    }
    if(p){
        return j;
    }
    else{
        return 0;
    }
}

【插入算法】

【算法描述】

// 在線性表 L 中第 i 個數(shù)據(jù)元素之前插入數(shù)據(jù)元素 e
Status ListInsert_L(LinkList L, int i, ElemType &e){
	// 初始化
    p = L;
    j = 0;
    // 尋找第 i-1 個結(jié)點，p 指向 i-1 結(jié)點
    while(p && (j<(i-1))){
        p = p->next;
        ++j;
    }
    // i 大于表長 +1 或者小于 1，插入位置非法
    if(!p || (j>(i-1))){
        // 第 i 個元素不存在
        return ERROR;
    }
    // 生成新結(jié)點 s，將結(jié)點 s 的數(shù)據(jù)域置為 e
    s = new LNode;
    s->data = e;
    // 將結(jié)點 s 插入 L 中
    s->next = p->next;
    p->next = s;
    
    return OK;
}// ListInsert_L

【刪除算法】

【算法描述】

// 將線性表 L 中第 i 個數(shù)據(jù)元素刪除
Status ListDelete_L(LinkList &L, int i, ElemType &e){
	// 初始化
    p = L;
    j = 0;
    // 尋找第 i-1 個結(jié)點，并令 p 指向其前驅(qū)
    while(p->next && (j<(i-1))){
        p = p->next;
        ++j;
    }
    // 刪除位置是否合理判斷
    if(!p->next || (j>(i-1))){
        // 第 i 個元素不存在
        return ERROR;
    }
    // 臨時保存被刪除結(jié)點的地址，以備釋放
    q = p->next;
    // 改變刪除結(jié)點前驅(qū)結(jié)點的指針域
    p->next = q->next;
    // 保存刪除結(jié)點的數(shù)據(jù)域
    e = q->data;
	// 釋放刪除結(jié)點的空間
    delete q;
    
    return OK;
}// ListDelete_L

??總結(jié)

(1) 查找算法

因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復(fù)雜度為 O(n)。

(2) 插入和刪除

因線性鏈表不需要移動元素，只要修改指針，一般情況下時間復(fù)雜度為 O(1)。

但是，如果要在單鏈表中進行前插和刪除操作，由于要從頭查找前驅(qū)結(jié)點，所耗時間復(fù)雜度為 O(n)。文章來源地址http://www.zghlxwxcb.cn/news/detail-516796.html

到了這里，關(guān)于青島大學(xué)_王卓老師【數(shù)據(jù)結(jié)構(gòu)與算法】Week03_11_線性表的鏈式表示和實現(xiàn)11_學(xué)習(xí)筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！