के एंड आर

Question

से तालिका लुकअप स्थापित फ़ंक्शन K & की धारा 6.6 एक लिंक की गई सूची का उपयोग करके हैश तालिका पर चर्चा करता है।

संक्षेप में, हैश तालिका पॉइंटर्स की एक सरणी है। पॉइंटर्स एक लिंक्ड सूची को इंगित करता है। लिंक्ड सूची एक struct की तरह लग रहा है जो:

struct nlist {    /* table entry: */ 
    struct nlist *next; /* next entry in chain */ 
    char *name;   /* defined name */ 
    char *defn;   /* replacement text */ 
}; 

नाम मिश्रित होता है, और इस हैश तालिका में सूचकांक निर्धारित करता है।

np->next = hashtab[hashval]; 
hashtab[hashval] = np; 

जब मैं इस को समझने की कोशिश, मैं आते रहते हैं:

struct nlist *install(char *name, char *defn) { 
    struct nlist *np; 
    unsigned hashval; 
    if ((np = lookup(name)) == NULL) { /* not found */ 
     np = (struct nlist *) malloc(sizeof(*np)); 
     if (np == NULL || (np->name = strdup(name)) == NULL) 
      return NULL; 
     hashval = hash(name); 
     np->next = hashtab[hashval]; 
     hashtab[hashval] = np; 
    } else /* already there */ 
     free((void *) np->defn); /*free previous defn */ 
    if ((np->defn = strdup(defn)) == NULL) 
     return NULL; 
    return np; 
} 

सब कुछ निम्नलिखित 2 लाइनों के अलावा समझ में आता है: अध्याय तो मेज पर एक नाम/defn जोड़ी जोड़ने के लिए कोड से पता चलता इस निष्कर्ष पर कि सूची अब खुद से जुड़ी हुई है और यदि आप लिंक की गई सूची को पार करने का प्रयास करते हैं तो यह कुत्ते की तरह अपनी पूंछ का पीछा करने जैसा होगा। मैं कोड को एनपीएल के आगे एनपी-> सेट करने की उम्मीद करता हूं।

मुझे क्या समझ में नहीं आ रहा है? यह कोड कैसे काम करता है?

Answer 1

इसके परिणामस्वरूप सूची की शुरुआत में नया मान डाला जा रहा है।

hashtab[hashval] --> original_list 

लिए:

hashtab[hashval] --> original_list 
np->next   --> original_list 

रहे हैं:

तो यह से चला जाता है

hashtab[hashval] --> *np 
     np->next --> original_list 

सुनहरा नियम है, लिंक्ड सूची कोड मतलब नहीं है अगर, हमेशा एक आरेख खींचें!

Answer 2

लेकिन यहां कोई मूल सूची नहीं है। यह एक नोड डालने वाला है जहां कोई कुंजी नहीं मिली है, है ना?

if ((np = lookup(name)) == NULL) { /* not found */ 

Answer 3

वहां पहले से ही एक नोड है। वह नोड शून्य है। Nlist संरचना को स्थिर के रूप में परिभाषित करके, यह स्वचालित रूप से अपने सभी तत्व पॉइंटर्स को NULL में प्रारंभ करता है।

अगर मैं गलत हूं तो मुझे सही करें।

Answer 4

हैशटैब [हैशवल] एक सूचक है, मूल्य नहीं। यह स्मृति में पते के लिए एक सूचक है जहां सूचक तालिका (स्थिर संरचना nlist * हैशटैब [HASHSIZE]) में उस विशेष पंक्ति का पहला तत्व रहता है। एनपी और एनपी-> अगला पॉइंटर्स भी हैं। तो यहां इन दो पंक्तियों में क्या होता है: पहली पंक्ति: तालिका की उस पंक्ति में पहले तत्व का सूचक np-> में कॉपी किया गया है। np-> अगली बार स्मृति में पते पर इंगित करता है जहां उस पंक्ति का पहला तत्व इंगित करता था। दूसरी पंक्ति: स्मृति में पते के लिए सूचक जहां नया * एनपी रहता है अब सूचक परिवर्तनीय hastab [हैशवल] में कॉपी किया गया है। hastab [हैशवल] अब एक बार फिर सूचक बन जाता है जहां उस तालिका पंक्ति का पहला तत्व रहता है। तो, जैसे ओली ने लिखा, नया * एनपी तालिका में उस विशेष पंक्ति की शुरुआत में डाला गया है।