2010-01-03 13 views
11

मैं होमवर्क के रूप में दिया गया था को लागू करने Introduction to Algorithms व्यायाम 11.1-3 जो इस प्रकार है:एक सीधा पता तालिका

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

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

मेरी समस्या हटाएं ऑपरेशन के साथ है। यदि मैं इसे जोड़ने के लिए ऑब्जेक्ट को संशोधित सूची में अपने नोड में पॉइंटर जोड़ने के लिए संशोधित करता हूं, तो मैं ओ (1) में हटा सकता हूं, लेकिन मुझे यकीन नहीं है कि मुझे ऑब्जेक्ट को बदलने की अनुमति है। क्या ऑब्जेक्ट को बदले बिना ऐसा करने का कोई तरीका है?

+3

+1 प्रकटीकरण के साथ होमवर्क प्रश्न पोस्ट करने और यह दिखाने के लिए कि आपने पहले ही कुछ कोशिश की है। SO – JoshJordan

+0

में आपका स्वागत है मानक वेनिला लिंक्ड सूची आपको ओ (1) खोज प्रदर्शन नहीं देगी। –

+0

@ ग्रेग्स - मैंने कहा है कि मैं मेल खाने वाली कुंजी के साथ कोई तत्व वापस कर सकता हूं, जिसका अर्थ है कि मैं सिर्फ सूची के सिर को वापस कर सकता हूं, जो ओ (1) है। –

उत्तर

0

हैश टेबल आपके लिए एक निश्चित बिंदु तक काम करेंगे। एक बार जब आप टक्कर लगाना शुरू कर देते हैं, तो यह ओ (1 + के/एन) बन जाता है जहां के कुंजी की संख्या होती है और n आपकी तालिका का आकार होता है। यदि आप एक शेड्यूल हैश का आकार बदलते हैं और फिर से हैश करते हैं, तो आप इससे दूर हो सकते हैं। पता नहीं है कि इससे आपकी दक्षता रेटिंग प्रभावित होगी क्योंकि यह सम्मिलन, हटाने या खोज के दौरान नहीं होती है।

ऑब्जेक्ट को नहीं बदलकर हटाना हैश संदर्भ पॉइंटर को शून्य पर सेट करके हासिल किया जा सकता है। ऑब्जेक्ट में कोई प्रत्यक्ष परिवर्तन नहीं किया जाता है, लेकिन ऑब्जेक्ट कंटेनर में परिवर्तन किए जाते हैं।

मुझे लगता है कि आप जो अधिकांश प्रतिबंध दे रहे हैं, उनके लिए हैश टेबल को उनके आसपास आने के कुछ तरीकों से लागू किया जा सकता है। हैश तालिका को कार्यान्वित करने के तरीके पर http://en.wikipedia.org/wiki/Hash_table#Performance_analysis पर और जानकारी है।

6

क्या यह कॉर्मन पुस्तक से एक प्रश्न है? जैसा कि मैं इसे समझता हूं, उस पुस्तक में पिछले अनुच्छेदों को पढ़ने से, आप जिस वस्तु को सीधे एक्सेस तालिका में संग्रहीत करते हैं वह 'आपकी' वस्तु है। इसलिए, जैसा कि आप सुझाव देते हैं, तालिका में प्रत्येक बिंदु तत्व के साथ उपयोगकर्ता की ऑब्जेक्ट में पॉइंटर वाले तालिका में दोगुनी-लिंक्ड सूचियों को स्टोर पॉइंटर्स। फिर, शब्दकोश खोज ऑपरेशन एक सूची तत्व देता है और उपयोगकर्ता को अपनी वस्तु को प्राप्त करने के लिए एक और कदम का उपयोग करना चाहिए। इसी तरह डिलीट ऑपरेशन एक सूची तत्व में एक सूचक लेता है।

क्या यह समझ में आता है? मैं अपना होमवर्क खराब नहीं करना चाहता!

+0

क्या होगा यदि आपके पास एन डुप्लिकेट आइटम की सूची है? वह ओ (एन) होगा। –

+1

"यह न भूलें कि हटाए जाने के लिए किसी ऑब्जेक्ट को पॉइंटर को हटाए जाने के रूप में हटाएं" - इसलिए आपके पास एन -1 डुप्लिकेट आइटम की एक सूची होगी। –

+0

समझ गया। और उस स्थिति में आपको दोगुनी लिंक्ड सूची की भी आवश्यकता नहीं होगी। O (1) में वर्तमान नोड को हटाने का एक तरीका है। अब होमवर्क खराब नहीं होने जा रहा है ... –

1

मुझे लगता है कि आप माध्यमिक कुंजी के रूप में मैप किए जाने के लिए उपग्रह डेटा का उपयोग कर सकते हैं। फिर यह 2-स्तर की हैश तालिका का एक प्रकार है। DELETE ऑपरेशन से संबंधित, सबसे पहले हम प्राथमिक कुंजी का उपयोग करते हैं। और जब डुप्लिकेट प्राथमिक कुंजी हैं, तो हम वस्तु प्राप्त करने के लिए माध्यमिक कुंजी का उपयोग करते हैं। इसलिए कुल समय अभी भी ओ (1) है।

0

सबसे महत्वपूर्ण हिस्सा .. और "हे में शब्दकोश आपरेशन (1) समय" एक सीधा-पहुँच तालिका जो में संग्रहीत तत्वों की चाबियाँ अलग होने की जरूरत नहीं है को लागू "।

तत्वों के बराबर होने पर ओ (1) समय में सम्मिलन भी संभव नहीं है (जैसा कि क्यू कहता है कि तत्वों को अलग नहीं होना चाहिए)।

किसी विशेष वस्तु तक पहुंचने के लिए भाग को हटाने के लिए आपको किसी विशेष वस्तु तक पहुंचने के लिए कुंजी और साथ ही ऑब्जेक्ट्स लेना होगा और सैटेलाइट डेटा की कुंजी भी लेना होगा।

मुझे लगता है कि 2 केवल ऊपर विचारों हे (1) समय के लिए कोई मतलब।

1

हम प्रत्यक्ष-पता तालिका के प्रत्येक सूचकांक में एक डबल लिंक्ड-लिस्ट का उपयोग कर सकते हैं। स्लॉट जे में सूची के शीर्ष पर एक सूचक होता है, जिसमें कुंजी-मूल्य जे के साथ सभी तत्व होते हैं और यदि ऐसे तत्व स्लॉट जे में शून्य नहीं है। सूची के शीर्ष पर INSERT-inserting x केवल ओ (1) समय लेगा। खोज- यह किसी भी तत्व को वापस कर सकता है जो दिए गए कुंजी से मेल खाता है और इस प्रकार सूची के प्रमुख को वापस करने से ओ (1) समय लगेगा। DELETE- जैसा कि हमने डबल लिंक्ड-लिस्ट का उपयोग किया है, हम पिछले और अगले नोड्स में पॉइंटर का उपयोग करके ओ (1) समय में एक तत्व को हटा सकते हैं।

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