3.8.2?單鏈表的刪除

??????? 現在我們再來看單鏈表的刪除。設存儲元素ai的結點為q，要實現將結點q刪除單鏈表的操作，其實就是將它的前繼結點的指針繞過，指向它的后繼結點即可（如圖3-8-5所示）。
??????? 我們所要做的，只是實際上就是一步，p->next=p->next->next，用q來取代p->next，即是 q=p->next; p->next=q->next;

??????? 解讀這兩句代碼，也就是說讓p的后繼的后繼結點改成p的后繼結點。有點拗口呀，那我再打個形象的比方。本來是爸爸左牽著媽媽的手，右牽著寶寶的手在馬路邊散步。突然迎面走來一美女，爸爸一下子看呆了，此情景被媽媽逮個正著。于是她生氣地甩開牽著的爸爸的手，繞過他，扯開父子倆，拉起寶寶的左手就快步朝前走去。此時媽媽是p結點，媽媽的后繼是爸爸p->next，也可以叫q結點，媽媽的后繼的后繼是兒子p->next->next，即q->next。當媽媽去牽兒子的手時，這個爸爸就已經與母子倆沒有牽手聯系了（如圖3-8-6所示）。

??????? 單鏈表第i個數據刪除結點的算法思路：
??????? 1.?聲明一結點p指向鏈表第一個結點，初始化j從1開始；
??????? 2.?當j<i時，就遍歷鏈表，讓p的指針向后移動，不斷指向下一個結點，j累加1；
??????? 3.?若到鏈表末尾p為空，則說明第i個元素不存在；
??????? 4.?否則查找成功，將欲刪除的結點p->next賦值給q；
??????? 5.?單鏈表的刪除標準語句 p->next=q->next；
??????? 6.?將q結點中的數據賦值給e，作為返回；
??????? 7.?釋放q結點；
??????? 8.?返回成功。

??????? 實現代碼算法如下：

?

/*初始條件：順序線性表L已存在，1≤i≤ListLength(L) *//*操作結果：刪除L的第i個數據元素，并用e返回其值，L的長度減1*/Status ListDelete(LinkList *L, int i, ElemType *e) { int j;LinkList p, q;p = *L;j = 1;while (p->next && j < i) /*遍歷尋找第i個元素*/{p = p->next;++j;}if (!(p->next) || j > i) return ERROR; /*第i個元素不存在*/q = p->next;p->next = q->next; /*將q的后繼賦值給p的后繼*/*e = q->data; /*將q結點中的數據給e*/free(q); /*讓系統回收此結點，釋放內存*/return OK;}

??????? 這段算法代碼里，我們又用到了另一個C語言的標準函數free。它的作用就是讓系統回收一個Node結點，釋放內存。
????????分析一下剛才我們講解的單鏈表插入和刪除算法，我們發現，它們其實都是由兩部分組成：第一部分就是遍歷查找第i個元素；第二部分就是插入和刪除元素。從整個算法來說，我們很容易推導出：它們的時間復雜度都是O(n)。如果在我們不知道第i個元素的指針位置，單鏈表數據結構在插入和刪除操作上，與線性表的順序存儲結構是沒有太大優勢的。但如果，我們希望從第i個位置，插入10個元素，對于順序存儲結構意味著，每一次插入都需要移動n-i個元素，每次都是O(n)。而單鏈表，我們只需要在第一次時，找到第i個位置的指針，此時為O(n)，接下來只是簡單地通過賦值移動指針而已，時間復雜度都是O(1)。顯然，對于插入或刪除數據越頻繁的操作，單鏈表的效率優勢就越是明顯。

出處：http://www.cnblogs.com/cj723/archive/2011/03/07/1973295.html

總結

以上是生活随笔為你收集整理的《大话数据结构》第3章 线性表 3.8.2 单链表的删除的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。