एक सेट को कैसे कार्यान्वित करें?

मैं लागू करने के लिए सी में एक सेट यह ठीक एक लिंक की गई सूची का उपयोग करने है चाहता हूँ, जब सेट बनाने, या मैं एक और दृष्टिकोण का उपयोग करना चाहिए?एक सेट को कैसे कार्यान्वित करें?

कैसे आप आमतौर पर अपने स्वयं के सेट लागू करते हैं (यदि आवश्यक)।

नोट: अगर मैं लिंक्ड सूची दृष्टिकोण का उपयोग, मैं शायद सेट के लिए निम्नलिखित जटिलताओं मेरी संचालन करना होगा:

init: हे (1);
नष्ट: ओ (एन);
डालें: ओ (एन);
हटाएं: ओ (एन);
संघ: ओ (एन * एम);
चौराहे: ओ (एन * एम);
अंतर: ओ (एन * एम);
समेकक: ओ (एन);
जारीकर्ता: ओ (एन * एम);
सेटसेक्वल: ओ (एन * एम);

O (n * मी) विशेष रूप से विशाल डेटा के लिए बड़ा करने के लिए एक छोटे से हो सकता है लगता है ... मेरे सेट लागू करने के लिए एक तरह से और अधिक कुशल है?

स्रोत

2010-03-29 Andrei Ciobanu

बाहर के साथ जानते हुए भी कि तुम क्या यह मदद करने के लिए मुश्किल है को प्राप्त करने के लिए इच्छुक रहे हैं। यदि आप सिर्फ संरचना जैसे सरणी चाहते हैं तो वेक्टर शायद जाने का आपका तरीका है।मैंने माना है कि आप वास्तव में सी ++ का उपयोग कर रहे हैं। एसटीएल में सामानों का भार होता है जो आपकी मदद करने के लिए बाध्य है। – thecoshman

सी ++ एक संतुलित बाइनरी पेड़ के रूप में अपनी सेट कक्षा लागू करता है - यह शायद एक अच्छा विकल्प है। –

@thecoshman जैसा कि उनके प्रश्न को सी के रूप में टैग किया गया था, मुझे लगता है कि हम मान सकते हैं कि वह सी ++ का उपयोग नहीं कर रहा है। –

मैंने पहले भी लाल काले पेड़ों का इस्तेमाल किया है सेट बनाने के लिए।

यहाँ विकिपीडिया लेख से समय जटिलताओं हैं।

अंतरिक्ष हे (एन)
खोजें हे (लॉग एन)
सम्मिलित हे (लॉग एन)
हे (लॉग एन)

स्रोत

2010-03-29 12:18:31

क्या आप मुझे ओ (एन) जटिलता के बारे में कुछ संकेत दे सकते हैं? –

संपादित करें –

std::set अक्सर एक लाल, काले पेड़ के रूप में कार्यान्वित किया जाता है: http://en.wikipedia.org/wiki/Red-black_tree

यह दृष्टिकोण आप सभी सूचीबद्ध कार्यों पर ज्यादा बेहतर जटिलता दे देंगे।

स्रोत

2010-03-29 12:11:27

सेट लागू करने के लिए तरीकों की बहुत हैं। Here उनमें से कुछ हैं। MSDN के अलावा इसके बारे में बहुत अच्छा लेख है।

स्रोत

2010-03-29 12:17:22 malay

एमएसडीएन आलेख का उल्लेख करने के लिए धन्यवाद, बहुत अंतर लेख। –

हटाएँ के बाद से आप पहले से ही एक लिंक्ड सूची लागू किया है, सबसे आसान है एक skip list। यदि आप संतुलित पेड़ों का उपयोग करना चाहते हैं, तो मेरी राय में सबसे आसान treap है। ये यादृच्छिक डेटा संरचनाएं हैं, लेकिन आम तौर पर वे अपने निर्धारक समकक्षों के जितना ही कुशल होते हैं, यदि अधिक नहीं (और एक स्किप सूची निर्धारित की जा सकती है)।

स्रोत

2010-03-29 12:25:19 IVlad

में पोस्ट किया गया स्किप सूची का उल्लेख करने के लिए धन्यवाद (इसके बारे में पता नहीं था)। मैं शायद इसे किसी अन्य संदर्भ में उपयोग करूंगा। (Multumesc!) –

सेट आमतौर पर या तो लाल-काले पेड़ (जो एक कुल आदेश के लिए तत्वों की आवश्यकता होती है) के रूप में लागू किया जाता है, या कोई स्वचालित रूप से आकार बदलने hashtable (जो एक हैश समारोह की आवश्यकता है) के रूप में।

बाद आम तौर पर आकार में hashtable डबल होने और जब एक निश्चित क्षमता सीमा (75% अच्छी तरह से काम करता है) को पार कर गया है सभी तत्वों पुन: लगाने द्वारा कार्यान्वित किया जाता। इसका मतलब है कि व्यक्तिगत सम्मिलन संचालन ओ (एन) हो सकता है, लेकिन जब कई परिचालनों में अमूर्त हो, तो यह वास्तव में ओ (1) है।

स्रोत

2010-03-29 12:25:49

एक सेट को कैसे कार्यान्वित करें?

उत्तर

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