Theory
એક પ્રશ્ન, બે આકાર
Canteen જે બે નોંધ રાખે છે:
- આજની token ની યાદી: 1, 2, 3, 4... દરેક token ને બરાબર એક પહેલાં અને એક પછી છે.
- Menu નું પાટિયું: Menu નાસ્તો, ભોજન, પીણાંમાં વહેંચાય છે; ભોજન ત્રણ થાળીમાં વહેંચાય છે.
"આના પછી શું આવે છે?" પૂછો. Token ની યાદી એક જવાબ આપે છે. Menu ત્રણ આપે છે.
એ એક ભેદ, એક અનુગામી કે અનેક, એ બધી non-primitive data structures ની અધિકૃત વિભાજનરેખા છે.
Theory
હરોળ સામે વંશવૃક્ષ
પીરસવાની હરોળ માં તમારી આગળ બરાબર એક વ્યક્તિ છે અને પાછળ એક: શુદ્ધ ક્રમ.
તમારા વંશવૃક્ષ માં તમારા દાદા અનેક સંતાનો સાથે જોડાય છે, દરેક વળી અનેક સાથે: શુદ્ધ ફંટાવું.
કોઈ કુટુંબને હરોળ તરીકે દોરતું નથી, અને કોઈ ગ્રાહકોને વંશવૃક્ષ પ્રમાણે પીરસતું નથી. રચનાઓ એ આકારો છે, અને આકારો એ સંબંધો સાથે મળતા હોવા જોઈએ જે એ ધરાવે છે.
Theory
બે કુટુંબ, ઔપચારિક રીતે
Linear data structure: ઘટકો એક જ ક્રમ બનાવે છે. દરેક ઘટકને (પહેલા અને છેલ્લા સિવાય) બરાબર એક પુરોગામી અને એક અનુગામી હોય છે. તમે એક સીધા ફેરામાં બધું ફરી શકો છો.
ઉદાહરણ: array, stack, queue, linked list.
Non-linear data structure: ઘટકો ક્રમવ્યવસ્થા તરીકે કે જાળા તરીકે જોડાય છે; એક ઘટક અનેક સાથે જોડાયેલો હોઈ શકે. ફરવા માટે વ્યૂહ જોઈએ (પહેલાં કઈ ડાળી?).
ઉદાહરણ: tree, graph.
At a glance
પરીક્ષાનું કોષ્ટક
| પાસું | Linear | Non-linear |
|---|---|---|
| ગોઠવણ | એક જ ક્રમ | ક્રમવ્યવસ્થા કે જાળું |
| પડોશીઓ | એક પુરોગામી, એક અનુગામી | એક ઘટક, અનેક જોડાણ |
| ફરવું | એક સીધો ફેરો | વ્યૂહ જોઈએ (DFS, BFS) |
| અમલ | વધુ સાદો | વધુ જટિલ |
| ઉદાહરણ | Array, stack, queue, linked list | Tree, graph |
| લાક્ષણિક ઉપયોગ | Token ની યાદી, undo, સમયપત્રક | File systems, નકશા, જાળાં |
Quiz
કયા જૂથમાં **ફક્ત** linear data structures જ છે?
- Array, linked list, stack, queue
- Array, tree, stack, queue
- Stack, queue, graph, array
- Tree, graph, linked list, array
Show the answer
Array, linked list, stack, queue
ચાર linear રચનાઓ બરાબર array, linked list, stack અને queue છે: દરેક એક ક્રમ જાળવે છે. બાકીનો દરેક વિકલ્પ tree કે graph ને ચોરીછૂપીથી ઘુસાડે છે, જે બે non-linear સભ્યો છે. પરીક્ષકો આ પ્રશ્ન linear યાદીની અંદર એક ફંટાતી રચના છુપાવીને બનાવે છે; tree/graph શોધો અને ખોટા વિકલ્પો જાતે જ નીકળી જાય છે.
Think first
ગૂંચવતો કિસ્સો
એક student tree ને array ની અંદર સંઘરે છે (માતાપિતા index i પર, સંતાનો 2i અને 2i+1 પર, જાણીતી heap ની ગોઠવણ). હવે data એક linear array માં બેઠો છે. Tap કરતાં પહેલાં: રચના linear છે કે non-linear, અને શા માટે?
Show the answer
Non-linear. વર્ગીકરણ તાર્કિક સંબંધો ને અનુસરે છે, સંઘરવાના માધ્યમને નહીં: દરેક માતાપિતાને હજી બે સુધી સંતાનો છે, એટલે ઘટકોને હજી અનેક અનુગામી છે. Array તો ફક્ત એ છાજલી છે જેના પર એ મુકાયું છે. આ ભેદ (તાર્કિક રચના સામે ભૌતિક સંગ્રહ) બરાબર એ ફાંદો છે જે પરીક્ષાઓ આ પ્રશ્નથી ગોઠવે છે, અને પછીના semesters માં heaps એના પર જ ટકે છે.
Watch out
વર્ગીકરણની બે લપસણ
Linked list ફંટાયેલી લાગે છે કારણ કે આકૃતિઓમાં તીર હોય છે, પણ દરેક node બરાબર એક પછીના node તરફ ચીંધે છે: linear.
Array માં સંઘરાયેલું tree non-linear જ રહે છે (ઉપર જુઓ). ક્યારેય નિષ્ફળ ન જતી કસોટી: એક ઘટકને કેટલા અનુગામી હોઈ શકે એ ગણો. વધુમાં વધુ એક: linear. કદાચ અનેક: non-linear. યાદીઓ ગોખવાને બદલે કસોટી લગાડો અને પરીક્ષાનો કોઈ પણ ફેરવીને પુછાયેલો પ્રશ્ન તમને ડગાવી નહીં શકે.
Theory
આ ભાગલા આગળ કેમ મહત્ત્વના છે
BCA304 માં બાકી રહેલું બધું (stack ના ઉપયોગ, ત્રણ સ્વાદમાં queues) linear બાજુ વસે છે: અત્યારે ક્રમો પાકા કરો. Non-linear બાજુ (trees, graphs) પછીના semesters માં databases, file systems અને Google Maps જેવી રસ્તા શોધવાની વ્યવસ્થા લઈને આવે છે. આજે શીખેલી એક-અનુગામીની કસોટી ત્યાં પણ કામ કરતી રહે છે.
Summary
Key takeaways
- Linear: એક ક્રમ, દરેક ઘટકને વધુમાં વધુ એક પુરોગામી અને એક અનુગામી.
- Non-linear: ક્રમવ્યવસ્થા કે જાળું, એક ઘટક અનેક સાથે જોડાયેલો હોઈ શકે.
- Linear સભ્યો: array, stack, queue, linked list. Non-linear: tree, graph.
- ફરવું: એક સીધો ફેરો સામે વ્યૂહ આધારિત (DFS/BFS).
- વર્ગીકરણ તાર્કિક સંબંધોને અનુસરે છે, data ભૌતિક રીતે કેવી રીતે સંઘરાયો છે એને નહીં.
- Memory hook: પીરસવાની હરોળ સામે વંશવૃક્ષ.