Optimizing the Insert Function
二、優化插入函數
It appears that inserting a node at the beginning of the list must be a special case. After all, the pointer that must be adjusted to insert the first node is the root pointer. For every other node, the pointer to be adjusted is the link field of the previous node.These seemingly different operations are really the same.
看上去，把一個節點插入到連結清單的起始位置必須作為一種特殊情況進行處理。畢竟，我們此時插入新節點需要修改的指針是根指針。對于任何其他節點，對指針進行修改時實際修改的是前一個節點的link 字段。這兩個看上去不同的操作實際上是一樣的。
The key to eliminating the special case is to realize that every node in the list has a pointer somewhere pointing to it. For the first node, it is the root pointer, and for every other node it is the link field of the preceding node. The important point is that there is a pointer somewhere pointing to each node. Whether the pointer is or is not contained in a node is irrelevant.
消除特殊情況的關鍵在于:我們必須認識到，連結清單中的每個節點都有一個指向它的指針。對于第1 個節點，這個指針是根指針;對于其他節點，這個指針是前一個節點的l 燭字段。重點在于每個節點都有一個指針指向它。至于該指針是不是位于一個節點的内部則無關緊要。
Letʹs look at the list once more to clarify this point. Here is the first node and its corresponding pointer.
讓我們再次觀察這個連結清單，弄清這個概念。這是第1 個節點和指向它的指針。
If the new value is inserted before the first node, then this pointer must be changed.
如果新值插入到第1 個節點之前，這個指針就必須進行修改。
Here is the second node and its pointer.
下面是第2 個節點和指向它的指針。
If the new value is inserted before the second node, then this pointer must be changed.Note that weʹre concerned only with the pointer; the node that contains it is irrelevant.
The same pattern holds for every node in the list.
如果新值需要插入到第2 個節點之前，那麼這個指針必須進行修改。注意我們隻考慮指向這個節點的指針，至于哪個節點包含這個指針則無關緊要。對于連結清單中的其他節點，都可以應用這個模式。
Now letʹs take a look at the modified function as it begins to execute. Here are its variables as they appear just after the first assignment statement.
現在讓我們看一下修改後的函數〈當它開始執行時〉。下面顯示了第1 條指派語句之後各個變量的情況。
We have a pointer to the current node and a pointer to the link that points to the current node. We donʹt need anything else! If the value in the current node is larger than the new value, the rootp pointer tells us which link field must be changed to link the new node into the list. If insertions elsewhere in the list can be expressed the same way, the special case disappears. The key is the pointer/node relationship we saw earlier.
我們擁有一個指向目前節點的指針，以及一個"指向目前節點的link 字段的"指針。除此之外，我們就不需要别的了!如果目前節點的值大于新值，那麼rootp 指針就會告訴我們哪個link 字段必須進行修改，以便讓新節點連結到連結清單中。如果在連結清單其他位置的插入也可以用同樣的方式進行表示，就不存在前面提到的特殊情況了。其關鍵在于我們前面看到的指針/節點關系。
When moving to the next node, save a pointer to the link that points to the next node instead of keeping a pointer to the previous node. It is easy to diagram what is desired.
當移動到下一個節點時，我們儲存一個"指向下一個節點的Ii nk 字段的"指針，而不是儲存一個指向前一個節點的指針。我們很容易畫出一張描述這種情況的圖。
Notice here that rootp is not pointing to the node; it points to the link field within the node. This fact is the key to simplifying the insert function, but it depends upon our being able to obtain the address of the link field of the current node. This operation is easy in C. The expression ¤t->link does the trick. Program 12.3 is the final version of our insertion function. The rootp parameter is now called linkp, because it points to many different links now, not just the root. We donʹt need previous any more, because our link pointer takes care of locating the link that needs to be modified. The special case at the end of the function is gone because we always have a pointer to the link field that needs to be changed—we modify the root variable in exactly the same way as the link field of a node. Finally, register declarations have been added to the pointer variables to improve the efficiency of the resulting code.
注意，這裡rooφ 并不指向節點本身，而是指向節點内部的link 字段。這是簡化插入函數的關鍵所在，但我們必須能夠取得目前節點的link 字段的位址。在C 中，這種操作是非常容易的。表達式¤t-> link 就可以達到這個目的。程式12.3 是我們的插入函數的最終版本。rootp 參數現在稱為linkp，因為它現在指向的是不同的恤字段，而不僅僅是根指針。我們不再需要previous 指針，因為我們的恤指針可以負責尋找需要修改的link 字段。前面那個函數最後部分用于處理特殊情況的代碼也不見了，因為我們始終擁有一個指向需要修改的link 字段的指針一一我們用一種和修改節點的link 字段完全一樣的方式修改root 變量。最後，我們在函數的指針變量中增加了register 聲明，用于提高結果代碼的效率。
The while loop in this final version is trickier because of the embedded assignment to current. Here is an equivalent, though slightly longer loop.
我們在最終版本中的while 循環中增加了一個竅門，它嵌入了對current 的指派。下面是一個功能相同，但長度稍長的循環。
current = *linkp;
while( current != NULL && current->value < value ){
linkp = ¤t->link;
current = *linkp;
}
#include <stdlib.h>
#include <stdio.h>
#include "sll_node.h"
#define FALSE 0
#define TRUE 1
int
sll_insert( register Node **linkp, int new_value )
{
register Node *current;
register Node *new;
while( ( current = *linkp ) != NULL &&
current->value < new_value )
linkp = ¤t->link;
new = (Node *)malloc( sizeof( Node ) );
if( new == NULL )
return FALSE;
new->value = new_value;
new->link = current;
*linkp = new;
return TRUE;
}
Program 12.3 Insert into an ordered, singly linked list: final version insert3.c
To begin, current is set to point to the first node in the list. The while test checks whether weʹve reached the end of the list. If not, it then checks whether we are at the proper place for the insertion. If not, the body of the loop executes, which sets linkp to point to the link field in the current node, and advances current to the next node.
一開始， current 被設定為指向連結清單的第1 個節點。while 循環測試我們是否到達了連結清單的尾部。如果沒有，它接着檢查我們是否到達了正确的插入位置。如果不是，循環體繼續執行，并把linkp設定為指向目前節點的link 字段，并使current 指向下一個節點。
The fact that the last statement in the loop body is identical to the statement just prior to the loop leads to the ʺsimplificationʺ of embedding the assignment to current within the while expression. The result is a more complex but more compact loop,because we have eliminated the redundant assignment to current.
循環的最後一條語句和循環之前的那條語句相同，這就促使我們對它進行"簡化氣方法是把current 的指派嵌入到while 表達式中。其結果是一個稍為複雜但更加緊湊的循環，因為我們消除了current 的備援指派。
Eliminating the special case made this function simpler. There are two factors that make this improvement possible. The first factor is our ability to interpret the problem correctly. Unless you can identify the commonality in seemingly different operations,you will be stuck writing extra code to handle special cases. Often this knowledge is acquired only after you have worked with the data structure for a while and understand it more clearly. The second factor is that the C language provides the right tools for you to exploit the commonality.
消除特殊情況使這個函數更為簡單。這個改進之是以可行是由于兩方面的因素。第1 個因素是我們正确解釋問題的能力。除非你可以在看上去不同的操作中總結出共性，不然你隻能編寫額外的代碼來處理特殊情況。通常，這種知識隻有在你學習了一陣資料結構并對其有進一步的了解之後才能獲得。第2 個因素是C 語言提供了正确的工具幫助你歸納問題的共性。
The improved function depends on Cʹs ability to obtain the address of existing objects. Like many C features, this ability is both powerful and dangerous. In Modula and Pascal, for example, there isnʹt an ʺaddress ofʺ operator, so the only pointers that exist are those produced by dynamic memory allocation. It is not possible to obtain a pointer to an ordinary variable or even to a field of a dynamically allocated structure.Pointer arithmetic is not allowed, and there isnʹt any means for casting a pointer from one type to another. These restrictions are advantageous in that they prevent the programmer from making mistakes such as subscripting off the end of an array and generating pointers of one type that in fact point to objects of some other type.
這個改進的函數依賴于C 能夠取得現存對象的位址這一能力。和許多C 語言特性一樣，這個能力既成力巨大，又暗伏兇險。例如，在Modula 和Pascal 中并不存在"取位址"操作符，是以指針唯一的來源就是動态記憶體分自己。我們沒有辦法獲得一個指向普通變量的指針或甚至是指向一個動态分自己的結構的字段的指針。對指針不允許進行算術運算，也沒有辦法把一種類型的指針通過強制類型轉換為另一種類型的指針。這些限制的優點在于它們可以防止諸如"越界引用數紐元素"或"産生一種類型的指針但實際上指向另一種類型的對象" 這類錯誤。
There are far fewer restrictions on pointers in C, which is why we were able to improve the insertion function. On the other hand, C programmers must be more careful when using pointers to avoid mistakes. The Pascal philosophy to pointers is sort of like saying, ʺYou might hurt yourself with a hammer, so we wonʹt give you one.ʺ The C philosophy is, ʺHere is a hammer. In fact, here are several kinds of hammers. Good luck.ʺ With this power, C programmers can get into more trouble than Pascal programmers, but good C programmers can produce smaller, more efficient, and more maintainable code than their Pascal or Modula counterparts. This is one of the reasons why C is so popular in industry, and why experienced C programmers are in such demand.
C 的指針限制要少得多，這也是我們能改進插入函數的原因所在。另一方面， C 程式員在使用指針時必須加倍小心， 以避免産生錯誤。Pascal 語言的指針哲學有點類似下面這樣的說法:"使用錘子可能會傷着你自己， 是以我們不給你錘子。" C 語言的指針哲學則是: "給你錘子，實際上你可以使用好幾種錘子。權，你好運!"有了這個能力之後， C 程式員較之Pascal 程式員更容易陷入麻煩，但優秀的C 程式員可以比他們的Pascal 和Modula 同行産生體和、史小、效率更高、可維護性更佳的代碼。這也是C 語言在業界為何如此流行以及經驗豐富的C 程式員為何如此受青昧的原因之一。
上一章 Pointers on C——12 Using Structures and Pointers.3