कार्यान्वयन छोड़ें सूची ++

Question

[हल]

तो मैं कोशिश करते हैं और एक हल कर दोगुना जुड़ा हुआ छोड़ सूची बनाने के लिए ...

मैं बहुत यकीन है कि मैं यह कैसे काम करता की अच्छी जानकारी होनी हूँ फैसला किया। जब आप एक्स डालते हैं तो प्रोग्राम एक्स को रखने के लिए उचित स्थान के लिए आधार सूची की खोज करता है (क्योंकि इसे सॉर्ट किया जाता है), (अवधारणात्मक रूप से) एक सिक्का फिसलता है, और यदि "सिक्का" भूमि पर तब होता है तो उस तत्व को ऊपर की सूची में जोड़ा जाता है (या उसमें तत्व के साथ एक नई सूची बनाई गई है), इसके नीचे के तत्व से जुड़ा हुआ है, और सिक्का फिर से फ़्लिप किया गया है, आदि। यदि "सिक्के" किसी भी समय बी पर उतरता है तो सम्मिलन समाप्त हो जाता है। आपके पास प्रत्येक सूची में शुरुआती बिंदु के रूप में एक-अनंत संग्रह भी होना चाहिए ताकि शुरुआती बिंदु से कम मूल्य (जो कि यह कभी नहीं पाया जा सके।)

खोजने के लिए एक्स, आप "टॉप-बाएं" (उच्चतम सूची निम्नतम मूल्य) से शुरू करते हैं और अगले तत्व पर "दाएं स्थानांतरित करें" से शुरू होते हैं। यदि आपके द्वारा अगले तत्व तक जारी रखने की तुलना में मान x से कम है, आदि। जब तक कि आप "बहुत दूर नहीं गए" और मान x से अधिक है। इस मामले में आप अंतिम तत्व पर वापस जाते हैं और एक स्तर को नीचे ले जाते हैं, जब तक आप या तो एक्स या एक्स नहीं पाते हैं तब तक इस श्रृंखला को जारी रखें।

एक्स को हटाने के लिए आप बस एक्स खोजते हैं और सूचियों में हर बार इसे हटा देते हैं।

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

समस्या जो मैं कर रहा हूं वह लिंक से निपट रहा है। मुझे पूरा यकीन है कि मैं पिछले तत्व और सूचक के सामने एक सूचक के साथ "क्षैतिज" लिंक को संभालने के लिए एक वर्ग बना सकता हूं, लेकिन मुझे यकीन नहीं है कि "लंबवत" लिंक से निपटने के लिए कैसे करें (संबंधित तत्व को इंगित करें ? अन्य सूची में)

अगर मेरे तर्क के किसी भी त्रुटिपूर्ण है कृपया मुझे बताओ, लेकिन मेरी मुख्य प्रश्न हैं:

1. कैसे खड़ी लिंक के साथ और क्या मेरी कड़ी विचार निपटने के लिए
2. अब यह सही है मैंने अपनी कक्षा सूची विचार पढ़ा है, मुझे लगता है कि एक सूची को एक पूर्णांक की बजाय पूर्णांक के वेक्टर रखना चाहिए। असल में मैं बहुत सकारात्मक हूं, लेकिन कुछ मान्यता पसंद करूंगा।
3. मुझे लगता है कि सिक्का फ्लिप बस इंट फ़ंक्शन को कॉल करेगा जहां रैंड()% 2 0 या 1 का मान देता है और यदि यह 0 है तो मान "स्तर ऊपर" और यदि यह 0 है तो सम्मिलित हो गया है। क्या यह गलत है?
4. -इन के समान मान कैसे स्टोर करें?

संपादित करें: मैं कुछ कोड लिखने शुरू कर दिया है और कैसे सूची निर्माता संभाल करने पर विचार कर रहा हूँ .... मुझे लगता है कि इसके निर्माण पर अनुमान लगा रहा हूँ, "-infinite" मूल्य vectorname में संग्रहित किया जाना चाहिए [ 0] तत्व और मैं उचित रूप से एक्स को रखने के लिए इसके निर्माण के बाद इसे सम्मिलित कर सकता हूं।

Answer 1

1. बस 2 पॉइंटर्स स्टोर करें। ऊपर एक कहा जाता है, और एक को आपके नोड वर्ग में नीचे बुलाया जाता है।
2. सुनिश्चित नहीं है कि आपका क्या मतलब है।
3. wikipedia के अनुसार आप एक ज्यामितीय वितरण भी कर सकते हैं। मुझे यकीन नहीं है कि वितरण का प्रकार पूरी तरह यादृच्छिक पहुंच के लिए मायने रखता है, लेकिन यदि आप अपना एक्सेस पैटर्न जानते हैं तो यह स्पष्ट रूप से मायने रखता है।
4. मुझे इस बात का अनिश्चितता है कि इसका मतलब क्या है।आप फ्लोटिंग पॉइंट नंबरों के साथ ऐसा कुछ प्रस्तुत कर सकते हैं।

Answer 2

http://msdn.microsoft.com/en-us/library/ms379573(VS.80).aspx#datastructures20_4_topic4

http://igoro.com/archive/skip-lists-are-fascinating/

ऊपर छोड़ सूचियों सी # में लागू किया जाता है, लेकिन उस कोड का उपयोग कर एक C++ कार्यान्वयन काम कर सकते हैं।

Answer 3

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

उदाहरण के लिए। एक "अगला" और "पिछला" पॉइंटर सटीक "उपरोक्त"/"नीचे" सूचक के समान होता है।

वैसे भी, आपके होमवर्क के साथ शुभकामनाएं। मुझे एक बार मेरे डेटा संरचना वर्ग में एक ही होमवर्क मिला।