2009-12-21 21 views
5

विजुअल स्टूडियो 2008 सीलिंक्ड सूची पूंछ को जोड़ने, भ्रम

क्या मैं इस लिंक्ड सूची के बारे में समझ में नहीं आता है, तो बयान के बाकी हिस्से में पूंछ को जोड़ने है।

जब सिर और पूंछ को नोड_टैम्प के स्मृति पते को दोनों पूंछ और सिर दोनों को उसी स्मृति स्थान पर इंगित किया जाता है।

हालांकि, अन्य भाग में वास्तव में सिर अभी भी पूंछ को इंगित कर रहा है। ऐसा कुछ है जिसे मैं समझा नहीं सकता और दूसरे भाग के बारे में नहीं समझता?

मुझे उम्मीद है कि कोई मेरे लिए बेहतर समझा सकता है।

static struct convert_temp 
{ 
    size_t cel; 
    size_t fah; 
    struct convert_temp *next; 
} *head = NULL, *tail = NULL; 

/** Add the new converted temperatures on the list */ 
void add(size_t cel, size_t fah) 
{ 
    struct convert_temp *node_temp = NULL; /* contain temp data */ 

    node_temp = malloc(sizeof(*node_temp)); 

    if(node_temp == NULL) 
    { 
     fprintf(stderr, "Cannot allocate memory [ %s ] : [ %d ]\n", 
      __FUNCTION__, __LINE__); 
     exit(0); 
    } 

    /* Assign data */ 
    node_temp->cel = cel; 
    node_temp->fah = fah; 
    node_temp->next = NULL; 

    if(head == NULL) 
    { 
     /* The list is at the beginning */ 
     head = node_temp; /* Head is the first node = same node */ 
     tail = node_temp; /* Tail is also the last node = same node */ 
    } 
    else 
    { 
     /* Append to the tail */ 
     tail->next = node_temp; 
     /* Point the tail at the end */ 
     tail = node_temp; 
    } 
} 
+1

डीबगर के साथ इसके माध्यम से जाएं। –

उत्तर

26

पहली बार जब आप कोई तत्व जोड़ते हैं (चलो इसे A पर कॉल करें), head शून्य है और आप if भाग से गुजरते हैं। इसका मतलब है कि head और पूंछ दोनों पहले तत्व को जोड़ते समय A पर इंगित करने के लिए सेट हैं।

अब चलिए एक और तत्व B जोड़ें। इस बार, head शून्य नहीं है, इसलिए यह else भाग से गुजरता है, tail को B पर इंगित करने के लिए सेट करता है लेकिन headA पर इंगित करता है।

यह अपेक्षा के अनुसार, अब आप head, A की ओर इशारा करते A, B कुछ भी नहीं (शून्य) और tailB की ओर इशारा करते की ओर इशारा करते B की ओर इशारा करते है।

चलिए इसे चरण-दर-चरण लेते हैं।

Initial state: head -+-> null 
         | 
       tail -+ 

Insert item A: head -+-> A ---> null 
         | 
       tail -+ 

Insert item B: head ---> A -+-> B ---> null 
          | 
       tail --------+ 

Insert item C: head ---> A ---> B -+-> C ---> null 
            | 
       tail ---------------+ 

आप प्रत्येक चरण है कि मौजूदा पूंछ नए नोड को इंगित करने के लिए निर्धारित है (प्रारंभिक के अलावा अन्य) (जो पहले से ही अपने अगले नोड के लिए शून्य की ओर इशारा करता है) तो पूंछ सूचक बात करने के लिए अद्यतन किया जाता है पर देख सकते हैं पर नया अंतिम नोड।

वास्तव में, के भी अधिक विस्तार से सी के अलावा (लाइन द्वारा लाइन) के माध्यम से चलते हैं तो आप देख सकते हैं क्या कोड की प्रत्येक पंक्ति (मैं node को node_temp नाम बदला है तो बस स्वरूपण के साथ मदद करने के लिए) कर :

Starting state:    head ---> A -+-> B ---> null 
              | 
           tail --------+ 

node = malloc(sizeof(*node)); node ---> C ----------> ? 
(allocate node C)    head ---> A -+-> B ---> null 
              | 
           tail --------+ 

node->next = NULL;    node ---> C --------+ 
(ignore payload cel/fah       | 
    for now since it's not  head ---> A -+-> B -+-> null 
    relevant to the list     | 
       structure)  tail --------+ 

tail->next = node;    node ---------------+ 
(first in else clause)       | 
           head ---> A -+-> B -+-> C ---> null 
              | 
           tail --------+ 

tail = node;     node ---------------+ 
(second in else clause)       | 
           head ---> A ---> B -+-> C ---> null 
                | 
           tail ---------------+ 

फिर अंत में node गायब हो जाता है, क्योंकि यह एक स्थानीय चर है और आप अपने अंतिम अवस्था है:

       head ---> A ---> B -+-> C ---> NULL 
                | 
           tail ---------------+ 

एकबनाए रखने का लाभ एक सिंगल-लिंक्ड लिस्ट मेंसूचक, अंत में एक आइटम जोड़ने की कोशिश कर रहे अंत को खोजने के लिए पूरी सूची के माध्यम से कदम उठाने से बचने के लिए है।

संपूर्ण सूची को स्थानांतरित करने से O(n) समय ऑपरेशन अंत में सम्मिलन होता है (समय लिया गया सूची में आइटमों की संख्या पर निर्भर करता है)। tail सूचक का उपयोग करता है कि O(1) समय ऑपरेशन (सूची आकार के बावजूद समय की समान राशि)।

एक अलग रूप में, एक दोगुना लिंक्ड सूची एक tail सूचक के लिए एक अतिरिक्त उपयोग है के रूप में - यह क्षमता जल्दी से शुरू करने के लिए सूची के अंत से एक ट्रेवर्सल शुरू करने के लिए tail का उपयोग करने और head के एवज में prev संकेत देता है और next पॉइंटर्स।

+3

उत्कृष्ट जवाब। यदि आप इसे समझ में नहीं आते हैं तो हमेशा अपने पॉइंटर्स के बारे में चित्र बनाएं! – Roalt

+1

+1: लिंकिंग सूचियों के सर्वोत्तम स्पष्टीकरणों में से एक मुझे याद है। (मेरी इच्छा है कि मेरे शिक्षक ने मुझे यह समझाया कि जब मैं 11 वीं कक्षा में था।)) –

4

बाकी-भाग सिर्फ अद्यतन करता है सूची के tail, के बाद से सिर जब आप किसी लिंक किए गए सूची में संलग्न नहीं बदलता है।

यह पूंछ तत्व को पॉइंटर को रखने के लिए एक अनुकूलन है, इसलिए आपको प्रत्येक परिशिष्ट पर सिर से पूरी सूची में कदम उठाने की आवश्यकता नहीं है।

1

ऐसा नहीं है कि सिर अभी भी पूंछ को इंगित कर रहा है। हेड पूर्व पूंछ को इंगित कर रहा है। जब सूची में केवल एक तत्व होता है, तो यह दोनों सिर और पूंछ था। जब नया नोड जोड़ा गया था, पूंछ सूचक अद्यतन किया गया था। हेड पॉइंटर अभी भी पहले नोड को इंगित करता है, जो सही है।

1

पहली कॉलिंग जोड़ने पर, सिर और पूंछ एक नव निर्मित स्मृति ब्लॉक को इंगित करेगा। जोड़ने के लिए आने वाली सभी कॉलों को दूसरे भाग में गिर जाएगा, जो मूल रूप से पुरानी पूंछ को संशोधित करके पूंछ सूचक को बदल देगा-> नए मेमोरी ब्लॉक पर इंगित करने के बाद, और फिर इस नई मेमोरी ब्लॉक को इंगित करने के लिए पूंछ अपडेट करें ।

यह संलग्न करने का एक प्रभावी तरीका है। यदि केवल सिर का उपयोग किया जाता है, तो प्रत्येक बार जब आप एक नया node_temp जोड़ते हैं, तो आपको सिर से शुरू होने वाले सभी अगले पॉइंटर्स को तब तक चलना होगा जब तक आप पहले जोड़े गए node_temp (जिसका अगला सूचक न्यूल होगा) तक पहुंच जाए, और फिर नए नोड में जोड़ें । यह उपर्युक्त ओ (1) की बजाय ओ (एन) एल्गोरिदम होगा।

संबंधित मुद्दे