सी में व्यापक रूप से कौन सा डेटा संरचना का उपयोग किया जाता है?

Question

कुछ दिन पहले मैंने खुद से पूछा कि मुझे सी में किसी फ़ंक्शन में कौन सी डेटा-संरचना चाहिए। मैं आमतौर पर सी ++ में लिखता हूं और विकल्प std :: vector पर गिर जाता।

वहाँ एक कुछ संभावित विकल्प:

• एक स्थिर (बड़ा पर्याप्त) सरणी
• एक गतिशील सरणी है जो एक साथ struct के रूप में एक स्वयं की सूची कार्यान्वयन (इसके आकार को दोगुना करने जैसे)
• जब जरूरत होती है सूचक अगला

अंतिम विकल्प असामान्य प्रतीत होता है। क्या कोई बड़ी परियोजना है जहां कोई सूचियों जैसे स्वयं संरचनाओं का उपयोग करता है? क्या सरणी या डेटा-संरचनाओं के बीच निर्णय के लिए कोई सामान्य नियम है?

जब मुझे पेड़ की संरचना की आवश्यकता होगी तो मुझे दो बार सोचना नहीं होगा कि सिर्फ एक पेड़ लिखें। क्या ऐसी संरचनाओं के साथ व्यापक रूप से उपयोग किए जाने वाले libs हैं (जैसे सी ++ के लिए बढ़ावा)? या इसे खराब शैली के रूप में माना जाता है क्योंकि आपको वास्तविक प्रकार के बजाय शून्य * स्टोर करना होगा?

आपके अनुभव के लिए बहुत बहुत धन्यवाद!

Answer 1

प्रत्येक के अपने फायदे और नुकसान हैं।

• स्टेटिक सरणी: लुकअप टेबल और डेटा के लिए बिल्कुल सही है जो प्रोग्राम निष्पादन में अपना आकार नहीं बदलता है। उन्हें प्रोग्राम स्टार्टअप पर आवंटित किया जाता है, इसलिए आपको इस मेमोरी को किसी भी तरह से प्रबंधित करने की आवश्यकता नहीं है। एक नुकसान यह है कि आप एक स्थिर सरणी का आकार बदल या मुक्त नहीं कर सकते - यह प्रोग्राम समाप्त होने तक वहां रहता है।

• गतिशील रूप से बढ़ते सरणी: डेटा संरचना का प्रबंधन करना आसान है जो सी ++ में वेक्टर सरणी के लिए लगभग एक विकल्प हो सकता है। रनटाइम पर स्मृति आवंटित करने का ओवरहेड एक नुकसान है, लेकिन यदि आप एक बार में बड़े हिस्से आवंटित करते हैं तो इसे कम किया जा सकता है।

• लिंक्ड सूचियां: यदि आपके पास बहुत सारे तत्व होने जा रहे हैं तो सावधानी बरतें क्योंकि स्मृति पूल का उपयोग किये बिना अलग-अलग आवंटित करने से स्मृति अपशिष्ट और विखंडन हो सकता है।

Answer 2

डायनामिक लिंक सूचियों का व्यापक रूप से सी में उपयोग किया जाता है जहां वस्तुओं को संग्रहीत करने की संख्या ज्ञात नहीं है।

Answer 3

वेक्टर एक गतिशील सरणी है और आंतरिक रूप से गतिशील सरणी के रूप में कार्यान्वित किया जाता है। मैं आपको वेक्टर का उपयोग करने का सुझाव दूंगा क्योंकि मशीनों को लगातार स्मृति स्थानों को पुनर्प्राप्त करने के लिए अनुकूलित किया गया है, जबकि लिंक सूची निरंतर स्थान पर संग्रहीत नहीं की जाएगी।

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

Answer 4

विभिन्न डेटा संरचनाएं सम्मिलन, लुकअप और अन्य परिचालनों के लिए विभिन्न कम्प्यूटेशनल जटिलता प्रदान करती हैं।

अपने विशिष्ट उदाहरण लेते हैं, वहाँ एक सरणी और एक लिंक्ड सूची के बीच मतभेद की एक संख्या है:

• देखने सूचकांक द्वारा एक सरणी और एक सूची में O(n) में O(1) है; एक सूची में
• सम्मिलन O(1) या O(n) (चाहे वे ट्रेवर्सल की आवश्यकता के आधार पर) कर रहे हैं, और एक सरणी में O(1) परिशोधित कर रहे हैं अच्छी तरह से किया;
• किसी सरणी से हटाने O(n) हैं जबकि कुछ प्रकार की सूची हटाना O(1) समय में किया जा सकता है;
• सरणी संदर्भ के बेहतर इलाके और इसके परिणामस्वरूप बेहतर कैश प्रदर्शन प्रदान करते हैं।

आप निम्न पृष्ठ उपयोगी हो सकता है: http://essays.hexapodia.net/datastructures/

एक सामान्य नियम, जब एक डेटा संरचना चुनने मैं पहली बार विचार करें कि क्या मैं मजबूत कारणों प्रश्न में कोड की है कि प्रदर्शन विश्वास करना होगा के रूप में होने जा रहा है महत्वपूर्ण:

• अगर मैं नहीं करते हैं, मैं सबसे सरल डेटा संरचना है कि काम करना होगा, या जो अपने आप में स्पष्ट कोड के लिए उधार देता है चुनें;
• यदि मैं करता हूं, तो मुझे लगता है कि मैं संरचनाओं पर कौन से संचालन करने जा रहा हूं और तदनुसार चुनिंदा तरीके से चयन कर रहा हूं।

अच्छा सी डेटा संरचना पुस्तकालयों के लिए सिफारिशों का सवाल है, शुद्ध सी में Are there any open source C libraries with common data structures?

Answer 5

पर एक नज़र मैं ज्यादातर स्थिर सरणियों का उपयोग करते हैं। यह एम्बेडेड उपकरणों के प्रोग्रामिंग से जुड़ा हुआ है जिसमें मेमोरी आवंटित करने और मुक्त करने में समस्याएं हैं - ढेर विखंडन।

लेकिन यदि सूची का उपयोग करने की आवश्यकता है तो मैं खुद को लागू करता हूं - कभी-कभी इसका कार्यान्वयन स्थैतिक सरणी (फिर से) पर आधारित होता है।

मुझे लगता है कि सी के लिए पुस्तकालय हैं जो अधिक जटिल डेटा संरचनाओं के सभ्य कार्यान्वयन की पेशकश करते हैं। AFAIK glib व्यापक रूप से उपयोग किया जाता है और कम से कम लिंक्ड सूचियों की पेशकश करता है।

Answer 6

यह पूरी तरह से निर्भर करता है कि आप डेटा संरचना पर कौन से संचालन करने जा रहे हैं। यदि आप इंडेक्स (जैसे डेटा [3]) द्वारा डेटा पुनर्प्राप्त करेंगे, तो एक सूची एक भयानक विचार है क्योंकि प्रत्येक पढ़ने के लिए आपको सूची में चलने की आवश्यकता होगी। यदि आप पहली स्थिति में बहुत कुछ डालेंगे (उदाहरण के लिए, डेटा [0] = x), तो एक सरणी भयानक होगी क्योंकि आप प्रत्येक प्रविष्टि के लिए सभी डेटा ले जायेंगे।

यदि आप std :: vector का उपयोग करने जा रहे थे, तो एक गतिशील सरणी शायद सबसे अच्छा प्रतिस्थापन है। लेकिन शायद std :: वेक्टर सही विकल्प नहीं होता।

Answer 7

मुझे याद है मैं एप्पल से एक दस्तावेज़ पढ़ कुछ समय पहले कह रही है कि ऐसी बात भोलेपन से एक संरचना के लिए इसी तरह के साथ लागू किया जा सकता है:

struct { 
    void *data; //other type rather than void is easier 
    int length; 
} MyArray; 

MyArray *MyArrayCreate(){ 
    //mallocate memory 
    return ... 
} 
void MyArrayRelease(){ 
    free(...); 
} 

और एक समारोह है कि सरणी और उसके की लंबाई की जाँच करता है को लागू इतना लंबा नहीं है कि एक और बड़ी पर्याप्त सरणी आवंटित की जाएगी, पूर्व डेटा की प्रतिलिपि बनाई जाएगी और इसमें नया डेटा जोड़ा जाएगा।

MyArrayInsertAt(MyArray *array, index, void *object){ 
    if (length < index){ 
     //mallocate again, copy data 
     //update length 
    } 
    data[index] = object; 
} 

तो यह इसलिए की तरह इस्तेमाल किया जा सकता है:

MyArray *array = MyArrayCreate(); 
MyArrayInsertAt(array, 5, something); 
MyArrayRelease(array); 

MyArrayInsertAt() फ़ंक्शन इसके प्रदर्शन के लिए एक मूल्य नहीं जीत जाएगा, लेकिन यह कोई उच्च मांग की कार्यक्रमों/अनुप्रयोगों

के लिए एक समाधान हो सकता है

मुझे बस लिंक नहीं मिल रहा है ... शायद कोई इसे भी पढ़ सकता है?

जोड़ा गया: मुझे पता चला है कि GNU NSMutableArray (उद्देश्य-सी) विधियों का कार्यान्वयन सी में किया जाता है और वे ऊपर जैसा ही करते हैं। जब भी ऑब्जेक्ट को जोड़ना होता है तो वे सरणी के आकार को दोगुना करते हैं और सरणी में फिट नहीं होंगे। लाइन 131 से 145