1

DATA TYPESडेटा प्रकार

A DATA TYPE tells the computer what kind of value a variable holds, and what you may do with it.

• PRIMITIVE types: integer, real or floating point, character and Boolean
• DERIVED or COMPOSITE types: arrays, records or structures, and strings
• An ARRAY holds items of ONE type in consecutive locations, reached by an index
• A RECORD groups fields of DIFFERENT types under one name
• An ABSTRACT DATA TYPE defines the operations, not the storage. Stacks and queues are examples

So an array holds one type, and a record mixes types.डेटा प्रकार कंप्यूटर को बताता है कि चर में किस तरह का मान है, और आप उसके साथ क्या कर सकते हैं।

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

अर्थात् ऐरे एक प्रकार रखता है, और रिकॉर्ड प्रकार मिलाता है।

2

STACKS AND QUEUESस्टैक और क्यू

• STACK: LIFO, LAST IN FIRST OUT. You add with PUSH and remove with POP, both at the TOP
• A stack serves function calls, expression evaluation and undo
• QUEUE: FIFO, FIRST IN FIRST OUT. You add at the REAR and remove from the FRONT
• A queue serves print spooling and CPU scheduling
• A CIRCULAR QUEUE reuses the freed front positions

Pushing onto a full stack is OVERFLOW; popping an empty stack is UNDERFLOW. So a stack of plates is LIFO, and a ticket line is FIFO.

• स्टैक: एलआईएफओ, लास्ट इन फर्स्ट आउट। आप पुश से जोड़ते और पॉप से हटाते हैं, दोनों टॉप पर
• स्टैक फंक्शन कॉल, व्यंजक मूल्यांकन और अनडू में काम आता है
• क्यू: एफआईएफओ, फर्स्ट इन फर्स्ट आउट। आप रियर पर जोड़ते और फ्रंट से हटाते हैं
• क्यू प्रिंट स्पूलिंग और सीपीयू शेड्यूलिंग में काम आती है
• सर्कुलर क्यू आगे खाली हुए स्थानों का फिर उपयोग करती है

भरे स्टैक पर पुश करना ओवरफ्लो है; खाली स्टैक से पॉप करना अंडरफ्लो। अर्थात् प्लेटों का ढेर एलआईएफओ है, और टिकट की कतार एफआईएफओ।

3

LINKED LISTS AND TREESलिंक्ड लिस्ट और ट्री

• LINKED LIST: each NODE holds data and a POINTER to the next node. Inserting and deleting need no shifting
• In a DOUBLY linked list each node also points back; in a CIRCULAR list the last node points to the first
• TREE: nodes in levels from a ROOT; each child has one parent, and nodes without children are LEAVES
• BINARY TREE: each node has at most TWO children
• BINARY SEARCH TREE: smaller keys go left and larger keys go right
• GRAPH: nodes joined by edges with no root, so cycles are allowed

You search a binary search tree by going left or right at each node. So a linked list grows freely, and a tree branches from a root.

• लिंक्ड लिस्ट: हर नोड में डेटा और अगले नोड का पॉइंटर होता है। जोड़ने और हटाने में खिसकाना नहीं पड़ता
• डबली लिंक्ड लिस्ट में हर नोड पीछे की ओर भी इंगित करता है; सर्कुलर लिस्ट में अंतिम नोड पहले को इंगित करता है
• ट्री: रूट से स्तरों में नोड; हर चाइल्ड का एक पैरेंट, और बिना चाइल्ड वाले नोड लीफ कहलाते हैं
• बाइनरी ट्री: हर नोड के अधिकतम दो चाइल्ड
• बाइनरी सर्च ट्री: छोटी कुंजियाँ बाएँ और बड़ी कुंजियाँ दाएँ जाती हैं
• ग्राफ: किनारों से जुड़े नोड, बिना रूट के, इसलिए चक्र संभव हैं

बाइनरी सर्च ट्री में आप हर नोड पर बाएँ या दाएँ जाकर खोजते हैं। अर्थात् लिंक्ड लिस्ट मुक्त रूप से बढ़ती है, और ट्री रूट से शाखाएँ बनाता है।

4

SEARCHING, SORTING AND COMPLEXITYसर्चिंग, सॉर्टिंग और जटिलता

COMPLEXITY measures how running time grows with the input size n, written in BIG-O notation.

• LINEAR SEARCH checks items one by one: O(n)
• BINARY SEARCH halves a SORTED list each step: O(log n)
• BUBBLE, SELECTION and INSERTION SORT: O(n squared)
• MERGE SORT: O(n log n) always; QUICK SORT: O(n log n) on average, O(n squared) at worst
• HEAP SORT: O(n log n)

Binary search works only on a list that you have already sorted. So binary search is O(log n), and merge sort is O(n log n).जटिलता मापती है कि इनपुट आकार n के साथ चलने का समय कैसे बढ़ता है, बिग-ओ संकेतन में।

• लीनियर सर्च मदों को एक-एक कर जाँचता है: O(n)
• बाइनरी सर्च हर चरण में क्रमबद्ध सूची को आधा करता है: O(log n)
• बबल, सेलेक्शन और इंसर्शन सॉर्ट: O(n का वर्ग)
• मर्ज सॉर्ट: सदा O(n log n); क्विक सॉर्ट: औसतन O(n log n), सबसे खराब में O(n का वर्ग)
• हीप सॉर्ट: O(n log n)

बाइनरी सर्च केवल उसी सूची पर काम करता है जिसे आप पहले क्रमबद्ध कर चुके हैं। अर्थात् बाइनरी सर्च O(log n) है, और मर्ज सॉर्ट O(n log n)।