बुनियादी डेटा संरचनाएँ। मैटेरियल। मूल बातें

तेजी से, मैं नोटिस करता हूं कि आधुनिक स्व-सिखाया लोगों में वास्तव में मातृ की कमी है। हर कोई भाषा जानता है, लेकिन डेटा बेस या एल्गोरिदम जैसी छोटी मूल बातें। डेटा प्रकारों के बारे में थोड़ा।

1976 में, स्विस वैज्ञानिक निकलॉस विर्थ ने अल्गोरिद्म + डेटा संरचना = कार्यक्रम पुस्तक लिखी ।

40+ साल बाद, यह समीकरण अभी भी सच है। और यदि आप एक स्वयं-सिखाया व्यक्ति हैं और प्रोग्रामिंग में लंबे समय तक लेख पर जाते हैं, तो आप तिरछे हो सकते हैं। आप कॉफ़ी को कूट सकते हैं।



लेख में प्रश्न भी होंगे जो आप साक्षात्कार में सुन सकते हैं।

डेटा संरचना क्या है?

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

कौन से हैं?

रैखिक , तत्व एक अनुक्रम या रैखिक सूची बनाते हैं, नोड को दरकिनार करके रैखिक होता है। उदाहरण: अर्र। लिंक की गई सूची, ढेर और कतारें।

गैर-रैखिक , यदि नोड्स का बाईपास गैर-रैखिक है, और डेटा अनुक्रमिक नहीं है। उदाहरण: ग्राफ और पेड़।

बुनियादी डेटा संरचनाएँ।

1. सरणियों
2. ढेर
3. कतारों
4. संबंधित सूची
5. गिनता
6. पेड़
7. उपसर्ग के पेड़
8. टेबल हैश

सरणियों

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

4 तत्वों (1, 2, 3, और 4) आकार के एक साधारण सरणी की छवि।



प्रत्येक डेटा आइटम को एक सकारात्मक संख्यात्मक मान (सूचकांक) सौंपा गया है, जो कि सरणी में आइटम की स्थिति से मेल खाती है। अधिकांश भाषाएँ किसी सरणी के शुरुआती सूचकांक को 0 के रूप में परिभाषित करती हैं।

हैं

एक-आयामी , जैसा कि ऊपर दिखाया गया है।
बहुआयामी , arrays के अंदर arrays।

मूल संचालन

• किसी दिए गए इंडेक्स में एक तत्व डालें-डालें
• किसी दिए गए सूचकांक में एक तत्व प्राप्त करें
• किसी दिए गए इंडेक्स पर किसी आइटम को डिलीट-डिलीट करें
• आकार-सरणी में तत्वों की कुल संख्या प्राप्त करें

सवाल

• दूसरा न्यूनतम सरणी तत्व खोजें
• किसी सरणी में पहला गैर-दोहराव पूर्णांक
• दो क्रमबद्ध सरणियों को मर्ज करें
• किसी सरणी में सकारात्मक और नकारात्मक मानों को पुन: व्यवस्थित करना

ढेर

स्टैक एक अमूर्त डेटा प्रकार है, जो कि LIFO सिद्धांत के अनुसार आयोजित तत्वों की एक सूची है (अंतिम में - पहले बाहर, आखिरी बार - पहले बाहर)।

ये सरणियाँ नहीं हैं। यह मोड़ है। एलन थुरिंग द्वारा आविष्कार किया गया।

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

स्टैक छवि, तीन तत्वों (1, 2 और 3) में, जहां 3 शीर्ष पर है और पहले हटा दिया जाएगा।

मूल संचालन

• पुश किसी आइटम को शीर्ष पर सम्मिलित करता है
• स्टैक से हटाने के बाद शीर्ष तत्व को पॉप-रिटर्न करता है
• यदि खाली है तो ईएमईटी-रिटर्न सही है
• स्टैक से हटाए बिना शीर्ष तत्व को शीर्ष-रिटर्न करता है

सवाल

• स्टैक का उपयोग करके एक कतार को लागू करें
• स्टैक पर मानों को क्रमबद्ध करें
• एक सरणी में दो ढेर को लागू करना
• स्टैक का उपयोग करके एक स्ट्रिंग को उल्टा करें

कतारों

ढेर की तरह, एक कतार एक तत्व को क्रमबद्ध तरीके से संग्रहीत करती है। स्टैक से एक महत्वपूर्ण अंतर LIFO के बजाय FIFO (फर्स्ट इन फर्स्ट आउट) का उपयोग है।

लाइन का एक उदाहरण लोगों की एक लाइन है। बाद वाले ने आखिरी और आपने लिया, और पहला उसे पहले छोड़ देगा।

कतार की छवि, चार तत्वों (1, 2, 3 और 4) में है, जहां 1 शीर्ष पर है और पहले हटा दिया जाएगा

मूल संचालन

• Enqueue-) - कतार के अंत में एक तत्व सम्मिलित करता है
• Dequeue () - कतार की शुरुआत से एक तत्व निकालता है
• isEmpty () - यदि कतार खाली है तो सही है
• शीर्ष () - कतार का पहला तत्व लौटाता है

सवाल

• एक कतार का उपयोग करके एक स्टैक को लागू करें
• एक कतार के पहले N तत्वों को उल्टा करें
• एक कतार का उपयोग करके 1 से एन तक द्विआधारी संख्या उत्पन्न करना

लिंक की गई सूची

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

सरणी पर प्रमुख लाभ संरचनात्मक लचीलापन है: लिंक की गई सूची के तत्वों का क्रम कंप्यूटर की मेमोरी में डेटा तत्वों के स्थान के आदेश के साथ मेल नहीं खा सकता है, और सूची के ट्रैवर्सल का क्रम हमेशा आपके आंतरिक संबंधों द्वारा स्पष्ट रूप से निर्धारित किया जाता है।

हैं

अप्रत्यक्ष , प्रत्येक नोड सूची में अगले नोड के पते या लिंक को संग्रहीत करता है और अंतिम नोड में अगला पता या लिंक NULL होता है।

1-> 2-> 3-> 4-> NULL

द्विदिश , प्रत्येक नोड से जुड़े दो लिंक, एक मजबूत बिंदु अगले नोड और एक पिछले नोड के लिए।

NULL <-1 <-> 2 <-> 3-> NULL

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

1-> 2-> 3-> 1

सबसे आम रेखीय यूनिडायरेक्शनल सूची। एक उदाहरण एक फ़ाइल सिस्टम है।

मूल संचालन

• InsertAtEnd - सूची के अंत में निर्दिष्ट आइटम डालें।
• InsertAtHead - सूची के शीर्ष पर एक आइटम सम्मिलित करता है
• हटाएं - सूची से निर्दिष्ट आइटम हटाता है।
• DeleteAtHead - सूची के पहले तत्व को हटाता है
• खोज - सूची से निर्दिष्ट आइटम लौटाता है
• अगर खाली सूची से जुड़ा हुआ है तो सही है

सवाल

• लिंक्ड लिस्ट रिवर्स
• लिंक की गई सूची में एक लूप को परिभाषित करना
• लिंक की गई सूची में अंत से एन आइटम लौटें
• एक लिंक की गई सूची से डुप्लिकेट निकालें

गिनता

एक ग्राफ नोड्स (कोने) का एक सेट है जो किनारों (आर्क्स) द्वारा एक नेटवर्क के रूप में एक दूसरे से जुड़ा हुआ है।

हैं

उन्मुख , पसलियां दिशात्मक हैं, अर्थात्। दो जुड़े हुए कोने के बीच केवल एक ही उपलब्ध दिशा है।
प्रत्येक पसलियों के बिना, आप दोनों दिशाओं में जा सकते हैं।
संकर

जैसे रूपों में मिला

• आसन्न मैट्रिक्स
• आसन्न सूची

सामान्य ग्राफ ट्रैवर्सल एल्गोरिदम

• चौड़ाई खोज - स्तर क्रॉल
• गहराई की खोज - चोटियों का पता लगाना

सवाल

• चौड़ाई और गहराई में खोज को लागू करें
• जाँच करें कि ग्राफ एक पेड़ है या नहीं
• एक ग्राफ में किनारों की संख्या की गणना करें
• दो चोटियों के बीच सबसे छोटा रास्ता खोजें

पेड़

एक पेड़ एक पदानुक्रमित डेटा संरचना है जिसमें नोड्स (कोने) और किनारों (चाप) होते हैं। पेड़ अनिवार्य रूप से छोरों के बिना ग्राफ़ से जुड़े होते हैं।

हर जगह पेड़ की संरचना। गेम्स में स्किल ट्री को हर कोई जानता है।

साधारण पेड़



पेड़ के प्रकार

• एन पेड़
• संतुलित वृक्ष
• बाइनरी ट्री
• बाइनरी सर्च ट्री
• आँवला का पेड़
• 2-3-4 पेड़

बाइनरी ट्री सबसे आम है।

"एक बाइनरी ट्री एक पदानुक्रमित डेटा संरचना है जिसमें प्रत्येक नोड का एक मूल्य होता है (यह इस मामले में भी महत्वपूर्ण है) और बाएं और दाएं वंशज का संदर्भ देता है। »- प्रोक

एक पेड़ के आसपास आने के तीन रास्ते

• प्रत्यक्ष क्रम में (ऊपर से नीचे तक) - उपसर्ग रूप।
• सममित क्रम में (बाएं से दाएं) - इन्फिक्स फॉर्म।
• रिवर्स ऑर्डर में (नीचे से ऊपर तक) - पोस्टफिक्स फॉर्म।

सवाल

• एक द्विआधारी पेड़ की ऊंचाई का पता लगाएं
• एक बाइनरी सर्च ट्री में एन सबसे छोटी वस्तु का पता लगाएं
• जड़ से N की दूरी पर नोड ज्ञात करें
• बाइनरी ट्री में एन नोड के पूर्वजों का पता लगाएं

ट्राइ (उपसर्ग वृक्ष)

तार के लिए एक प्रकार का पेड़, त्वरित खोज। शब्दकोश। T9।

इस तरह से एक पेड़ "शीर्ष", "इस प्रकार" और "उनके" शब्दों को संग्रहीत करता है।



शब्दों को ऊपर से नीचे तक संग्रहीत किया जाता है, हरे रंग के नोड्स "पी", "एस" और "आर" क्रमशः "शीर्ष", "इस प्रकार" और "उनके" के अंत तक।

सवाल

• शब्दों की कुल संख्या की गणना करें
• सभी शब्दों को प्रिंट करें
• उपसर्ग पेड़ से सरणी तत्वों को सॉर्ट करें
• T9 शब्दकोश बनाएँ

टेबल हैश

हैशिंग वस्तुओं को विशिष्ट रूप से पहचानने और प्रत्येक ऑब्जेक्ट को पूर्व-गणना किए गए अद्वितीय सूचकांक (कुंजी) में संग्रहीत करने के लिए उपयोग की जाने वाली प्रक्रिया है।

किसी ऑब्जेक्ट को कुंजी-मूल्य जोड़ी के रूप में संग्रहीत किया जाता है, और ऐसे तत्वों के संग्रह को एक शब्दकोश कहा जाता है। प्रत्येक कुंजी को इस कुंजी का उपयोग करके पाया जा सकता है।

संक्षेप में, यह एक सरणी है जिसमें कुंजी को हैश फ़ंक्शन के रूप में दर्शाया जाता है।

प्रदर्शन पर निर्भर करता है

• हैश फ़ंक्शन
• हैश टेबल का आकार
• टक्कर प्रबंधन के तरीके

एक सरणी में हैश मिलान का एक उदाहरण। इस सरणी के सूचकांक की गणना हैश फ़ंक्शन के माध्यम से की जाती है।

सवाल

• एक सरणी में सममित जोड़े खोजें
• खोजें कि क्या एक सरणी दूसरे सरणी का सबसेट है
• ओपन हैशिंग का वर्णन करें

संसाधनों की सूची

• medium.freecodecamp.org/the-top-data-structures-you-should-know-for-your-next-coding-interview-36af0831f5e3
• www.geeksforgeeks.org/commonly-asked-data-structure-interview-questions-set-1
• prog-cpp.ru/data-list
• habr.com/post/267855
• habr.com/post/273687
• habr.com/post/150732
• ruhighload.com/%D0%A7%D1%82%D0%BE+%D1%82%D0%B0%D0%BA%D0%BE%D0%B5+%D1%85%D0%B5%D1%88-% D1% 82% D0% B0% D0% B1% D0% BB% D0% B8% D1% 86% D1% 8B +% D0% B8 +% D0% BA% D0% B0% D0% BA +% D0% BE%% D0% BD% D0% B8 +% D1% 80% D0% B0% D0% B1% D0% BE% D1% 82% D0% B0% D1% 8E% D1% 82
• ru.wikipedia.org

एक निष्कर्ष के बजाय

मातृ भाषा जितनी रोचक है उतनी ही रोचक भी। शायद किसी व्यक्ति को उससे परिचित मूल संरचनाएं दिखाई देंगी और रुचि होगी।

पढ़ने के लिए धन्यवाद। मुझे आशा है कि समय बर्बाद नहीं होगा)

पुनश्च: मैं माफी माँगता हूँ, जैसा कि यह निकला, लेख का अनुवाद पहले से ही यहाँ था और बहुत हाल ही में, मैंने अनदेखी की।
अगर दिलचस्पी है, यहाँ वह है , धन्यवाद हुकुम , मैं और अधिक सावधान रहना होगा।