linked list good taste下載 - linked list good taste源代碼下載

linked list good taste

C#源碼

1.0.0

下載

鏈接列表，指針技巧和良好的品味

介紹
代碼
- CS101版本
- 更優雅的解決方案
它如何工作？
- 集成頭指針
- 保持手柄
超越
- 在現有項目之前插入
- 快速重構
- 實現insert_before（）
結論

介紹

在2016年的TED採訪（14:10）中，Linus Torvalds談到了他認為編碼的良好品味。例如，他在單鏈接列表中提出了兩個項目刪除的實現（以下複製）。為了從列表中刪除第一個項目，其中一個實現需要特殊情況，另一個實施情況不需要。顯然，Linus更喜歡後者。

他的評論是：

[...]我不想讓您理解為什麼它沒有if語句。但是我希望您理解，有時您可以以不同的方式看到一個問題並重寫它，以使特殊情況消失並成為正常情況，這是很好的代碼。 [...] - L. Torvalds

他提供的代碼片段是C風格的偽代碼，並且足夠簡單。但是，正如Linus在評論中提到的那樣，片段缺乏概念上的解釋，並且尚不明顯更優雅的解決方案的實際運作方式。

接下來的兩個部分詳細介紹了技術方法，並演示了間接尋址方法的方式以及為什麼如此整潔。最後一節將解決方案從項目刪除到插入。

代碼

整數列表的基本數據結構如圖1所示。

鏈接列表
圖1 ：整數列表。

數字是任意選擇的整數值和箭頭指示指示器。 head是類型list_item *的指針，每個框都是list_item struct的實例，每個框都帶有構件變量（在代碼中稱為next ）type list_item * ，指向下一個項目。

數據結構的C實施是：

 struct list_item {
        int value ;
        struct list_item * next ;
};
typedef struct list_item list_item ;

struct list {
        struct list_item * head ;
};
typedef struct list list ;

我們還包括（最小）API：

 /* The textbook version */
void remove_cs101 ( list * l , list_item * target );
/* A more elegant solution */
void remove_elegant ( list * l , list_item * target );

將其實現，讓我們看一下remove_cs101()和remove_elegant()的實現。這些示例的代碼符合Linus示例中的偽代碼以及編譯和運行。

CS101版本

簡單的數據模型
圖2 ：CS101算法中列表數據結構的概念模型。

 void remove_cs101 ( list * l , list_item * target )
{
        list_item * cur = l -> head , * prev = NULL ;
        while ( cur != target ) {
                prev = cur ;
                cur = cur -> next ;
        }
        if ( prev )
                prev -> next = cur -> next ;
        else
                l -> head = cur -> next ;
}

標準的CS101方法利用了兩個遍歷指針cur和prev ，分別標記了列表中的當前和先前的遍歷位置。 cur始於列表head ，然後前進，直到找到目標為止。 prev從NULL開始，隨後每次cur Advances cur的先前值都會更新。找到目標後，算法測試如果prev為非NULL 。如果是，則該項目不在列表的開頭，刪除包括重新列出cur圍繞的鏈接列表。如果prev為NULL ， cur指向列表中的第一個元素，在這種情況下，刪除意味著將列表向前移動。

更優雅的解決方案

更優雅的版本的代碼較少，並且不需要單獨的分支來處理列表中第一個元素的刪除。

 void remove_elegant ( list * l , list_item * target )
{
        list_item * * p = & l -> head ;
        while ( * p != target )
                p = & ( * p ) -> next ;
        * p = target -> next ;
}

該代碼使用間接指針p ，該指針p從head地址開始，該指針P指向列表項目的地址。在每次迭代中，指針都將要保存指針的下一個列表項目的地址，即當前list_item中next元素的地址。當指向列表項目*p等於target時，我們將退出搜索循環並從列表中刪除該項目。

它如何工作？

關鍵見解是，使用間接指針p具有兩個概念上的好處：

它使我們能夠以使head指針成為數據結構不可或缺的一部分的方式來解釋鏈接列表。這消除了特殊情況以刪除第一項的需求。
它還使我們能夠評估while循環的狀況，而不必放開target的指針。這使我們能夠修改指向target的指針，並逃脫單個迭代器，而不是prev和cur 。

讓我們依次看看這些要點。

集成`head`指針

標準模型將鏈接列表解釋為list_item實例的序列。可以通過head指針訪問序列的開始。這導致了上面圖2所示的概念模型。 head指針僅被視為訪問列表開始的處理方法。 prev和cur是類型list_item *的指針，始終指向項目或NULL 。

優雅的實施使用間接的尋址方案，對數據結構產生不同的看法：

間接地址的數據模型
圖3 ：更優雅的方法中列表數據結構的概念模型。

在這裡， p是類型list_item ** ，並保留指向當前列表項目的指針的地址。當我們推進指針時，我們將指針的地址轉發到下一個列表項目的地址。

在代碼中，這轉化為p = &(*p)->next ，意味著我們

(*p) ：取消指向當前列表項目的指針的地址
->next ：再次取消指針，然後選擇保留下一個列表項目地址的字段
& ：獲取該地址字段的地址（即獲取指針）

這對應於數據結構的解釋，其中列表是list_item s的一系列指針（參見圖3）。

保持手柄

該特定解釋的另一個好處是，它支持在整個遍歷中編輯當前項目的前身的next指針。

p持有指向列表項目的指針的地址，搜索循環中的比較變為

 while ( * p != target )

如果*p等於target ，則搜索循環將退出，一旦達到目標，我們仍然能夠修改*p ，因為我們持有其地址p 。因此，儘管迭代循環直到達到target ，但我們仍然維護一個手柄（ next字段或head指針的地址），該手柄可用於直接修改指向項目的指針。

這就是為什麼我們可以使用*p = target->next指向其他位置的輸入指針的原因，以及為什麼我們不需要prev和cur來穿越列表以刪除項目。

超越

事實證明，可以應用remove_elegant()背後的想法來產生列表API中另一個函數的特別簡潔實現： insert_before() ，即在另一個項目之前插入給定項目。

在現有項目之前插入

首先，讓我們將以下聲明添加到list.h中的列表API。

 void insert_before ( list * l , list_item * before , list_item * item );

該函數將在該列表中的項目before將指針轉到列表l ，並在該列表中的項目中進行指針，並將其指向該功能之前將在before插入的新列表item 。

快速重構

在繼續前進之前，我們將搜索循環重構為單獨的功能

 static inline list_item * * find_indirect ( list * l , list_item * target )
{
        list_item * * p = & l -> head ;
        while ( * p != target )
                p = & ( * p ) -> next ;
        return p ;
}

並在remove_elegant()中使用該功能

 void remove_elegant ( list * l , list_item * target )
{
        list_item * * p = find_indirect ( l , target );
        * p = target -> next ;
}

實現`insert_before()`

使用find_indirect() ，實現insert_before() ：

 void insert_before ( list * l , list_item * before , list_item * item )
{
        list_item * * p = find_indirect ( l , before );
        * p = item ;
        item -> next = before ;
}