परिचय एल्गोरिथ्म के लिए, व्यायाम 10.2-4

Question

यह परिचय के व्यायाम से एक सवाल एल्गोरिदम है, 3 edtion: (मैं जानता हूँ कि यह तुच्छ सवाल है, लेकिन मैं इस के आसपास मेरे सिर नहीं मिल सकता है।)

अध्याय 10, पृष्ठ 240:

10.2-4

लिखा के रूप में, सूची-खोज procedur में प्रत्येक पाश यात्रा ई दो परीक्षणों की आवश्यकता है: x != L.nil और x.key != k के लिए एक। दिखाएं कि कैसे प्रत्येक पुनरावृत्ति में x != L.nil के परीक्षण को खत्म करें।

LIST-SEARCH(L, k) 
    x = L.nil.next 
    while x != L.nil and x.key != k 
    x = x.next 
    return x 

L परिपत्र, एक प्रहरी के साथ दोगुना लिंक्ड सूची है। (एक सेंटीनेल प्रारंभ में एक निश्चित स्थैतिक तत्व है, जो सीमा परिस्थितियों को सरल बनाने में मदद करता है। उदाहरण के लिए, मान लीजिए कि हम L एक ऑब्जेक्ट L.nil प्रदान करते हैं जो NIL का प्रतिनिधित्व करता है लेकिन सूची में अन्य ऑब्जेक्ट्स के सभी गुण हैं।)

जब तक कि आप हमेशा खोज नहीं करते हैं, x != L.nil को हटाने के लिए अनंत पुनरावृत्ति का कारण बनता है, जब तक कि k खोज नहीं होता है।

आप इस अभिव्यक्ति को x != L.nil अन्य अभिव्यक्तियों (जैसे सूची में तत्वों की गिनती) में बदल सकते हैं, लेकिन यह एक समाधान नहीं है, मुझे लगता है।

इस प्रश्न को हल करने में मुझे क्या कमी है?

Answer 1

सेंटीनेल तैयार करें। सेंटीनेल का उपयोग करके, x.key == k स्थिति वैसे भी मिलेगी। सेंटीनल हटाने को सुनिश्चित करें।

LIST-SEARCH(L, k) 
    LIST-INSERT(L, k) 
    x = L.head.next 
    while x.key != k 
     x = x.next 
    if x == L.head 
     ret = NIL 
    else 
     ret = x 
    LIST-DELETE(L, L.head) 
    return ret 

Answer 2

चाल लूप में प्रवेश करने से पहले 0 सेंमानने के लिए अपनी सेंटीनेल की कुंजी सेट करना है। इस तरह, आप nil को चेक कर सकते हैं और अभी भी सुनिश्चित करें कि लूप समाप्त हो गया है। जब k पाया जाता है, तो पाया गया नोड या तो भेजा गया है, या वह मान जिसे आप ढूंढना चाहते हैं।

Answer 3

कुछ इस तरह कार्य करें:

LIST-SEARCH(L,k) 
    nil.key = k; 
    currentPtr = nil.next; 
     while(currentPtr.key != k) 
    currentPtr = currentPtr.next; 
    nil.data = -1; // dummy key 
    return currentPtr;