बी-पेड़ नोड का प्रतिनिधित्व कैसे किया जा सकता है?

Question

हम कक्षा में बी-पेड़ सीख रहे हैं और उन्हें कोड में लागू करने के लिए कहा गया है। शिक्षक ने हमें प्रोग्रामिंग भाषा पसंद कर दिया है और मैं इसे सी # में कोशिश करना और करना चाहता हूं। मेरी समस्या

unsafe struct BtreeNode 
     { 
      int key_num;  // The number of keys in a node 
      int[] key;   // Array of keys 
      bool leaf;   // Is it a leaf node or not? 
      BtreeNode*[] c;  // Pointers to next nodes 
     } 

विशेष रूप से, एक संरचना में ही बात करने के लिए एक सूचक बनाने के लिए अनुमति नहीं है, निम्न संरचना सी # में अवैध है। क्या मैं कुछ काम-आसपास या वैकल्पिक दृष्टिकोण का उपयोग कर सकता हूं? मैं काफी हद तक निश्चित हूं कि प्रबंधित कोड में ऐसा करने का एक तरीका होना चाहिए, लेकिन मैं इसे समझ नहीं सकता।

संपादित करें: एरिक के जवाब ने मुझे सही दिशा में इंगित किया। यहां मैं उपयोग कर रहा हूं,

class BtreeNode 
{ 
     public List<BtreeNode> children;  // The child nodes 
     public static int MinDeg;    // The Minimum Degree of the tree 
     public bool IsLeaf { get; set; }  // Is the current node a leaf or not? 
     public List<int> key;     // The list of keys 
... 
} 

Answer 1

संयोग से मैंने वास्तव में एक व्यक्तिगत परियोजना के लिए सी # में एक बिट्री लागू किया था। वह मज़ेदार था। मैंने लेक्सिकोोग्राफिक रूप से आदेशित चर आकार (64 बाइट तक) की एक बिट बनाई, जिसमें कई चुनौतियां सामने आईं, विशेष रूप से यह पता लगाना कि भंडारण का एक पृष्ठ बहुत भरा या बहुत खाली था।

मेरी सलाह, ऐसा करने के बाद, एक अमूर्त परत बनाने के लिए है जो केवल एक सार तत्व के रूप में अपने सबसे अमूर्त रूप में btree एल्गोरिदम को कैप्चर करता है। एक बार जब मुझे उस फॉर्म में कैप्चर किए गए सभी बीटी नियम मिल गए, तो मैंने बेस क्लास को कई अलग-अलग तरीकों से विशेषीकृत किया: एक नियमित फिक्स्ड-की-साइज 2-3 बिट्री के रूप में, मेरे फैंसी वैरिएबल-साइज-कीटी बीटीआरआई में से एक के रूप में, और इसी तरह ।

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

दूसरा, इस संरचना को बनाने का कोई कारण नहीं है। स्ट्रक्चर को सी # में मूल्य से कॉपी किया जाता है; एक btree नोड मूल्य नहीं है।

तीसरा, आपको नोड में चाबियों की संख्या रखने की आवश्यकता नहीं है; चाबियों की सरणी जानता है कि इसमें कितनी कुंजी हैं।

चौथा, मैं एक सरणी के बजाय List<T> का उपयोग करूंगा; वे अधिक लचीला हैं।

पांचवां, आप तय करने की जरूरत है कि क्या नोड में या माता पिता में महत्वपूर्ण रहता है। किसी भी तरह से काम कर सकते हैं; मेरी वरीयता नोड में रहने की कुंजी के लिए है, क्योंकि मुझे नोड से जुड़े होने के रूप में कुंजी दिखाई देती है।

छठी, यह जानना सहायक है कि कोई बीटी नोड रूट है या नहीं; आप दो बूल रखने पर विचार कर सकते हैं, एक "क्या यह एक पत्ता है?" और एक "क्या यह जड़ है?" बेशक इसमें एक आइटम के साथ एक ब्रीटी में एक नोड होता है जो पत्ती और जड़ दोनों होता है।

सातवां, आप शायद इस बात को उत्परिवर्तनीय बनाने जा रहे हैं; आम तौर पर एक सी # कक्षा पर सार्वजनिक उत्परिवर्तनीय फ़ील्ड नहीं बनाता है। आप उन्हें गुण बनाने पर विचार कर सकते हैं। इसके अलावा, बच्चों की सूची जा बड़े हो सकते हैं और सिकुड़, लेकिन इसकी पहचान परिवर्तन नहीं होता है, तो यह referentially केवल पढ़ने के लिए करते हैं:

:

तो मैं शायद अपने बुनियादी नोड के रूप में संरचना होगा

class Node 
{ 
    public int Key { get; set; } 
    public bool IsRoot { get; set; } 
    public bool IsLeaf { get; set; } 
    private List<Node> children = new List<Node>(); 
    public List<Node> Children { get { return this.children; } } 
} 

समझ में आओ?

Answer 2

एक स्टैक्ट के बजाय कक्षा का उपयोग करें। और पॉइंटर्स फेंक दें।

class BtreeNode 
{ 
    int key_num;  // The number of keys in a node 
    int[] key;   // Array of keys 
    bool leaf;   // Is it a leaf node or not? 
    BtreeNode[] c;  // Pointers to next nodes 
} 

जब आप एक वर्ग प्रकार का एक चर घोषित, यह परोक्ष एक संदर्भ (बहुत सी में एक सूचक के समान) के बाद से हर वर्ग के लिए एक संदर्भ प्रकार है।

Answer 3

आपको यह महसूस करने की आवश्यकता है कि सी में एक सूचक सी # में संदर्भ के लिए "कुछ हद तक समान" है। (इस प्रश्न के प्रयोजनों के लिए विभिन्न मतभेद हैं, आप समानताओं पर ध्यान केंद्रित कर सकते हैं।) दोनों संकेतों के स्तर की अनुमति देते हैं: मान डेटा नहीं है, यह डेटा प्राप्त करने का एक तरीका है।

की तरह कुछ ऊपर होगा के बराबर:

class BtreeNode 
{ 
    private int keyNumber; 
    private int[] keys; 
    private bool leaf; 
    private BtreeNode[] subNodes; 

    // Members (constructors etc) 
} 

(मैं बी पेड़ के बारे में ज्यादा याद नहीं है, लेकिन "कुंजी" सरणी यहाँ प्रत्येक की "keyNumber" मूल्य से मेल खाती है, तो उपनोड, आप keys वैरिएबल बिल्कुल नहीं चाहते हैं।)