鍊錶中的哨兵是怎麼乙個作用？

1樓：宇佐見蓮子

萌新正在自學演算法導論正好看見這個問題

1.A sentinel is a dummy object that allows us to simplify boundary conditions.

哨兵是用來簡化邊界問題的虛設物件

2.As shown in Figure 10.4, this change turns a regular doubly linked list into a circu-

lar, doubly linked list with a sentinel, in which the sentinel L:nil lies between the

head and tail. The attribute L:nil:

next points to the head of the list, and L:nil:pre points to the tail.

Similarly, both the next attribute of the tail and the pre at-

tribute of the head point to L: nil. Since L: nil: next points to the head, we can

eliminate the attribute L:head altogether, replacing references to it by references

to L:nil:next. Figure 10.4(a) shows that an empty list consists of just the sentinel,

and both L:nil:next and L:nil:pre point to L:nil.

哨兵優化雙向鍊錶貌似就把雙向鍊錶弄成了環形鍊錶

3.rbt中的哨兵

reference:Introduction to Algorithms

2樓：

哨兵這個說法說的太不大眾化了，說成援兵我都覺得比較好理解，說白了就是外援。

紅黑樹有乙個性質是：葉結點的左右兩邊必須為黑色。

也就是本來葉結點如果沒有左右孩子直接初始化為NULL就是了，但它居然要黑色，意味著我需要新分配兩塊記憶體空間啥資料也不儲存，tm就是為了給它塗上黑色然後掛到葉結點的left、right。當葉結點多起來的時候你說多浪費記憶體空間？理想的二叉樹結構是為了讓我們儲存資料（key），而不是為了儲存顏色吧？

所以哨兵這個外援就來了，我們申請一塊記憶體命名為哨兵，然後把這塊記憶體塗上黑色，之後所有沒有孩子的葉結點left、right都指向這個已塗上黑色的哨兵。

以上是紅黑樹哨兵的作用。

哨兵在每種情況下都是不同的，拿方程舉例：7x=14，讓兩邊同時除以7：，方程就化簡成x=2了，那個7相當於你定義的哨兵，用來化簡方程，同理3x=15的哨兵是多少你應該知道了，用了那個哨兵就能化簡成x=5。

數學題化簡就是用的哨兵來化簡，所以你可以回想下你曾經化簡數學題究竟用了多少哨兵。

還不理解我就拿演算法導論上的動態規劃裡的鋼管切割問題來說吧。

3樓：知鑑

假設某個漆黑的夜晚，諸位在海岸的懸崖邊上玩乙個遊戲。諸位站在距懸崖邊緣100公尺的地方，地上每隔1公尺就任意放1件物品。請找出這些物品中有沒有蘋果。

諸位每前進1公尺就要撿起地上的物品，檢查是否拿到了蘋果，同時還要檢查有沒有到達懸崖的邊緣（不檢查的話就有可能掉到海浬），也就是說要對這兩種檢查反覆若干次。

使用了哨兵以後，就要先把起點挪到距懸崖邊緣101公尺的地方，再在懸崖的邊緣放置乙個蘋果。這個蘋果就是哨兵，通過放置哨兵，諸位就一定能找到蘋果了。每前進1公尺只需檢查檢驗到的物品是不是蘋果就可以了。

發現是蘋果以後，只需站在原地再檢查一步開外的情況。如果還沒有到達懸崖邊緣，就意味著找到了真正要找的蘋果。已經達到了懸崖邊緣，則說明現在手中的蘋果是哨兵，而沒有找到真正要找的蘋果。