ප්රස්තාර ගබඩා කිරීම සඳහා දත්ත ව්යුහයන්: පවතින ඒවා සහ "පාහේ නව" දෙකක් පිළිබඳ සමාලෝචනයක්

හැමෝටම ආයුබෝවන්.

මෙම සටහනේදී, පරිගණක විද්‍යාවේ ප්‍රස්ථාර ගබඩා කිරීම සඳහා භාවිතා කරන ප්‍රධාන දත්ත ව්‍යුහයන් ලැයිස්තුගත කිරීමට මම තීරණය කළ අතර, කෙසේ හෝ මා වෙනුවෙන් “ස්ඵටිකීකරණය” කළ තවත් එවැනි ව්‍යුහ කිහිපයක් ගැන ද කතා කරමි.

ඉතින්, අපි පටන් ගනිමු. නමුත් මුල සිටම නොවේ - මම හිතන්නේ අපි හැමෝම දැනටමත් ප්‍රස්ථාරයක් යනු කුමක්ද සහ ඒවා මොනවාද යන්න (අධ්‍යක්ෂණය කරන ලද, යොමු නොකළ, බර, බර නොකළ, බහු දාර සහ ලූප ඇති හෝ රහිතව).

ඉතින්, අපි යමු. "ප්රස්තාර ගබඩා කිරීම" සඳහා දත්ත ව්යුහයන් සඳහා අපට ඇති විකල්ප මොනවාද?

1. Matrix දත්ත ව්යුහයන්

1.1 යාබද අනුකෘතිය. යාබද න්‍යාසය යනු පේළි සහ තීරු ශීර්ෂ ප්‍රස්ථාරයේ සිරස් සංඛ්‍යාවට අනුරූප වන න්‍යාසයකි, සහ එහි එක් එක් මූලද්‍රව්‍ය a(i,j) හි අගය තීරණය වන්නේ සිරස් අතර දාර තිබීම හෝ නොමැති වීම මගිනි. i සහ j (නොපැහැදිලි ප්‍රස්ථාරයක් සඳහා එවැනි න්‍යාසයක් සමමිතික වන බව පැහැදිලිය, නැතහොත් අපි සියලු අගයන් ගබඩා කරන්නේ ප්‍රධාන විකර්ණයට ඉහළින් පමණක් බව අපට එකඟ විය හැකිය). බර නොකළ ප්‍රස්ථාර සඳහා, a(i,j) i සිට j දක්වා දාර ගණනින් (එවැනි දාරයක් නොමැති නම්, a(i,j)= 0) සහ බර ප්‍රස්ථාර සඳහා බරින්ද සැකසිය හැක. (සම්පූර්ණ බර) සඳහන් කර ඇති දාරවල.

1.2 සිද්ධි අනුකෘතිය. මෙම අවස්ථාවෙහිදී, අපගේ ප්‍රස්ථාරය වගුවක ගබඩා කර ඇති අතර, රීතියක් ලෙස, පේළි අංක එහි සිරස් වල සංඛ්‍යා වලට අනුරූප වන අතර තීරු සංඛ්‍යා පෙර අංකිත දාරවලට අනුරූප වේ. ශීර්ෂයක් සහ දාරයක් එකිනෙක සම්බන්ධ වන්නේ නම්, ශුන්‍ය නොවන අගයක් අදාළ කොටුවේ ලියා ඇත (නොපැහැදිලි ප්‍රස්ථාර සඳහා, 1 ලියා ඇත්තේ සිරස් සහ දාරය සිදුවීම නම්, දිශානුගත ප්‍රස්ථාර සඳහා - "1" දාරය නම් ශීර්ෂයෙන් “පිටවීම” සහ එහි “ඇතුළත්” නම් “-1” (එය මතක තබා ගැනීම ප්‍රමාණවත්ය, මන්ද “අඩු” ලකුණ “-1” අංකයට “ඇතුළත්” වී ඇති බව පෙනේ)). බර ප්‍රස්ථාර සඳහා, නැවතත්, 1 සහ -1 වෙනුවට, ඔබට දාරයේ සම්පූර්ණ බර නියම කළ හැකිය.

2. ගණන් කිරීමේ දත්ත ව්යුහයන්

2.1 යාබද ලැයිස්තුව. හොඳයි, මෙහි සෑම දෙයක්ම සරල බව පෙනේ. ප්‍රස්ථාරයේ සෑම ශීර්ෂයක්ම, සාමාන්‍යයෙන්, ඕනෑම ගණන් කිරීමේ ව්‍යුහයක් (ලැයිස්තුව, දෛශිකය, අරාව, ...) සමඟ සම්බන්ධ කළ හැකිය, එමඟින් ලබා දී ඇති එකට යාබද සියලුම සිරස් වල සංඛ්‍යා ගබඩා කරනු ඇත. අධ්‍යක්ෂණය කරන ලද ප්‍රස්ථාර සඳහා, අපි එවැනි ලැයිස්තුවකට එකතු කරනු ලබන්නේ විශේෂාංග ශීර්ෂයකින් “දිශාගත” දාරයක් ඇති සිරස් පමණි. බර ප්රස්තාර සඳහා ක්රියාත්මක කිරීම වඩාත් සංකීර්ණ වනු ඇත.

2.2 ඉළ ඇට ලැයිස්තුව. තරමක් ජනප්‍රිය දත්ත ව්‍යුහයකි. Captain Obviousness අපට පවසන පරිදි දාර ලැයිස්තුව ඇත්ත වශයෙන්ම ප්‍රස්ථාරයේ දාර ලැයිස්තුවකි, ඒ සෑම එකක්ම ආරම්භක ශීර්ෂය, අවසන් ශීර්ෂය මගින් නියම කර ඇත (නොපැහැදිලි ප්‍රස්තාර සඳහා අනුපිළිවෙල මෙහි වැදගත් නොවේ, නමුත් ඒකාබද්ධ කිරීම සඳහා ඔබට හැකි විවිධ නීති භාවිතා කරන්න, උදාහරණයක් ලෙස, වැඩි කිරීම සඳහා සිරස් නියම කිරීම) සහ බර (බර ප්‍රස්තාර සඳහා පමණි).

ඔබට ඉහත ලැයිස්තුගත කර ඇති අනුකෘති ලැයිස්තු වඩාත් විස්තරාත්මකව (සහ නිදර්ශන සහිතව) බැලිය හැක, උදාහරණයක් ලෙස, මෙහි.

2.3 යාබද අරාව. වඩාත්ම පොදු ව්යුහය නොවේ. එහි හරය, එය එක් ගණන් කිරීමේ ව්‍යුහයකට යාබද ලැයිස්තු “ඇසුරුම්” ආකාරයකි (අරාව, දෛශිකය). එවැනි අරාවක පළමු n (ප්‍රස්ථාරයේ සිරස් ගණන අනුව) මූලද්‍රව්‍යවල එකම අරාවක ආරම්භක දර්ශක අඩංගු වේ, එයින් ආරම්භ වන පරිදි ලබා දී ඇති එකට යාබද සියලුම සිරස් පේළියක ලියා ඇත.

මෙන්න මම වඩාත් තේරුම්ගත හැකි (මට) පැහැදිලි කිරීම සොයාගත්තා: ejuo.livejournal.com/4518.html

3. Adjacency vector සහ Associative Adjacency Array

මෙම රේඛාවල කතුවරයා, වෘත්තීය ක්‍රමලේඛකයෙකු නොව, වරින් වර ප්‍රස්ථාර සමඟ කටයුතු කළ, බොහෝ විට දාර ලැයිස්තු සමඟ කටයුතු කරන බව පෙනී ගියේය. ඇත්ත වශයෙන්ම, ප්රස්ථාරයේ බහු ලූප සහ දාර තිබේ නම් එය පහසු වේ. එබැවින්, දාරවල සම්භාව්‍ය ලැයිස්තු සංවර්ධනය කිරීමේදී, ඒවායේ “සංවර්ධනය / ශාඛාව / වෙනස් කිරීම / විකෘතිය” කෙරෙහි අවධානය යොමු කිරීමට මම යෝජනා කරමි, එනම්: යාබද දෛශිකය සහ ආශ්‍රිත යාබද අරාව.

3.1 යාබද දෛශිකය

නඩුව (a1): බර නොකළ ප්‍රස්තාරය

බර නොකළ ප්‍රස්ථාරයක් සඳහා අපි යාබද දෛශිකයක් ලෙස හඳුන්වන්නේ එක් එක් සංඛ්‍යා යුගලයක් ඇති ඉරට්ටේ නිඛිල සංඛ්‍යාවක (a[2i], a[2i+1],..., i අංකනය කර ඇති තැන c 0 ක අනුපිළිවෙලක් සමූහයකි. a[2i], a[2i+1 ] පිළිවෙලින් a[2i] සහ a[2i+1] සිරස් අතර ප්‍රස්ථාර දාරයක් නියම කරයි.
මෙම පටිගත කිරීමේ ආකෘතියේ ප්‍රස්ථාරය යොමු කර තිබේද යන්න පිළිබඳ තොරතුරු අඩංගු නොවේ (විකල්ප දෙකම හැකි ය). digraph ආකෘතිය භාවිතා කරන විට, දාරය a[2i] සිට a[2i+1] දක්වා යොමු කිරීම ලෙස සැලකේ. මෙහි සහ පහත: යොමු නොකළ ප්‍රස්ථාර සඳහා, අවශ්‍ය නම්, පටිගත කිරීමේ සිරස් අනුපිළිවෙල සඳහා අවශ්‍යතා යෙදිය හැකිය (උදාහරණයක් ලෙස, එයට පවරා ඇති සංඛ්‍යාවේ අඩු අගය සහිත ශීර්ෂය පළමුව පැමිණේ).

C++ හි, std::vector භාවිතයෙන් යාබද දෛශිකයක් සඳහන් කිරීම සුදුසුය, එබැවින් මෙම දත්ත ව්‍යුහයේ නම.

නඩුව (a2): බර නොකළ ප්‍රස්තාරය, දාර බර නිඛිල වේ

නඩුව (a1) සමඟ සාදෘශ්‍යයෙන්, අපි පූර්ණ සංඛ්‍යා දාර බර සහිත බර ප්‍රස්ථාරයක් සඳහා යාබද දෛශිකය ලෙස හඳුන්වන්නේ අංක (a[3i], a[3i+1], a[3i+2], ..., i අංක කර ඇති තැන c 0), එහිදී a[3i], a[3i+1], a[3i+2] සංඛ්‍යාවල සෑම “ත්‍රිත්වයක්” a[3i] ශීර්ෂ අතර ප්‍රස්ථාරයේ දාරයක් නියම කරයි. සහ a[3i+1], පිළිවෙලින්, සහ a [3i+2] අගය මෙම දාරයේ බර වේ. එවැනි ප්රස්ථාරයක් ද යොමු කළ හැකි හෝ නොකළ හැකිය.

නඩුව (b): බර නොකළ ප්‍රස්ථාරය, නිඛිල නොවන දාර බර

එක් අරාවක (දෛශිකය) විෂමජාතීය මූලද්‍රව්‍ය ගබඩා කළ නොහැකි බැවින්, උදාහරණයක් ලෙස, පහත ක්‍රියාත්මක කිරීම කළ හැකිය. ප්‍රස්ථාරය දෛශික යුගලයක ගබඩා කර ඇති අතර, එහි පළමු දෛශිකය බර සඳහන් නොකර ප්‍රස්ථාරයේ යාබද දෛශිකය වන අතර දෙවන දෛශිකයේ අනුරූප බර අඩංගු වේ (C++: std:: pair සඳහා ක්‍රියාත්මක කළ හැක. ) මේ අනුව, පළමු දෛශිකයේ 2i, 2i+1 දර්ශක යටතේ සිරස් යුගලයකින් අර්ථ දක්වා ඇති දාරයක් සඳහා, බර දෙවන දෛශිකයේ i දර්ශකය යටතේ ඇති මූලද්‍රව්‍යයට සමාන වේ.

හොඳයි, මෙය අවශ්ය වන්නේ ඇයි?

හොඳයි, මෙම රේඛාවල කතුවරයා ගැටළු ගණනාවක් විසඳීම සඳහා එය බෙහෙවින් ප්රයෝජනවත් විය. හොඳයි, විධිමත් දෘෂ්ටි කෝණයකින්, පහත සඳහන් වාසි ඇත:

• යාබද දෛශිකය, වෙනත් ඕනෑම “සංඛ්‍යාංක” ව්‍යුහයක් මෙන්, තරමක් සංයුක්ත වේ, යාබද අනුකෘතියට වඩා අඩු මතකයක් ගනී (විරල ප්‍රස්තාර සඳහා), සහ ක්‍රියාත්මක කිරීමට සාපේක්ෂව පහසුය.
• ප්‍රස්ථාරයේ සිරස්, ප්‍රතිපත්තිමය වශයෙන්, සෘණ සංඛ්‍යා වලින් ද සලකුණු කළ හැක. එවැනි "විකෘතියක්" අවශ්ය නම්?
• ප්‍රස්ථාරවල විවිධ බර (ධන, සෘණ, ශුන්‍ය පවා) සහිත බහු දාර සහ බහු ලූප අඩංගු විය හැක. මෙහි සීමාවන් නොමැත.
• ඔබට දාරවලට විවිධ ගුණාංග පැවරිය හැකිය - නමුත් ඒ පිළිබඳ වැඩි විස්තර සඳහා, 4 කොටස බලන්න.

කෙසේ වෙතත්, මෙම "ලැයිස්තුව" කෙළවරට ඉක්මන් ප්රවේශයක් අදහස් නොකරන බව පිළිගත යුතුය. මෙන්න සහකාර යාබද අරාව ගලවා ගැනීමට පැමිණේ, එය පහත සාකච්ඡා කෙරේ.

3.2 ආශ්‍රිත යාබද අරාව

එබැවින්, නිශ්චිත දාරයකට ප්‍රවේශ වීම, එහි බර සහ අනෙකුත් ගුණාංග අපට තීරණාත්මක නම් සහ මතක අවශ්‍යතා අපට යාබද අනුකෘතිය භාවිතා කිරීමට ඉඩ නොදෙන්නේ නම්, මෙම ගැටළුව විසඳීම සඳහා යාබද දෛශිකය වෙනස් කරන්නේ කෙසේදැයි සිතා බලමු. එබැවින්, යතුර ප්‍රස්ථාරයේ කෙළවරක් වන අතර, එය ඇණවුම් කළ පූර්ණ සංඛ්‍යා යුගලයක් ලෙස දැක්විය හැක. මෙය පෙනෙන්නේ කෙසේද? එය ආශ්‍රිත අරාවක යතුරක් නොවේද? සහ, එසේ නම්, අපි එය ක්රියාත්මක නොකරන්නේ මන්ද? සෑම යතුරක්ම - ඇණවුම් කරන ලද පූර්ණ සංඛ්‍යා යුගලයක් - අගයක් සමඟ සම්බන්ධ වන ආශ්‍රිත අරාවක් අපි ලබා ගනිමු - දාරයේ බර සඳහන් කරන පූර්ණ සංඛ්‍යාවක් හෝ තාත්වික සංඛ්‍යාවක්. C++ හි, std::map බහාලුම් (std::map) මත පදනම්ව මෙම ව්‍යුහය ක්‍රියාත්මක කිරීම යෝග්‍ය වේ. , int> හෝ std:: map , ද්විත්ව>), හෝ බහු දාර බලාපොරොත්තු වන්නේ නම් std::multimap. හොඳයි, “matrix” ව්‍යුහයන්ට වඩා අඩු මතකයක් ගන්නා ප්‍රස්ථාර ගබඩා කිරීම සඳහා ව්‍යුහයක් අප සතුව ඇත, බහු ලූප සහ දාර සහිත ප්‍රස්ථාර නිර්වචනය කළ හැකි, සහ ශීර්ෂ සංඛ්‍යාවල සෘණ නොවන බව සඳහා දැඩි අවශ්‍යතා පවා නොමැත (මම නොදනිමි. මෙය අවශ්‍ය කාටද, නමුත් තවමත්).

4. දත්ත ව්‍යුහයන් පිරී ඇත, නමුත් යමක් අස්ථානගත වී ඇත

එය සත්‍යයකි: ගැටළු ගණනාවක් විසඳන විට, අපට ප්‍රස්ථාරයේ දාරවලට සමහර ලක්ෂණ පැවරීමට අවශ්‍ය විය හැකි අතර, ඒ අනුව ඒවා ගබඩා කරන්න. මෙම විශේෂාංග නිඛිල සංඛ්‍යාවලට නිරපේක්ෂ ලෙස අඩු කිරීමට හැකි නම්, යාබද දෛශිකයේ සහ ආශ්‍රිත යාබද අරාවේ විස්තීරණ අනුවාද භාවිතයෙන් එවැනි “අමතර විශේෂාංග සහිත ප්‍රස්ථාර” ගබඩා කළ හැකිය.

එබැවින්, අපට බර නොකළ ප්‍රස්ථාරයක් ලබා ගනිමු, එහි එක් එක් දාරය සඳහා ගබඩා කිරීම අවශ්‍ය වේ, උදාහරණයක් ලෙස, පූර්ණ සංඛ්‍යා මගින් නිශ්චිතව දක්වා ඇති අමතර විශේෂාංග 2 ක්. මෙම අවස්ථාවෙහිදී, එහි යාබද දෛශිකය "යුගල" නොව, නිඛිලවල "ක්වාර්ටේට්" (a[2i], a[2i+1], a[2i+2], a ලෙස නියම කළ කට්ටලයක් ලෙස අර්ථ දැක්විය හැක. [2i+3]...) , එහිදී a[2i+2] සහ a[2i+3] අනුරූප දාරයේ ලක්ෂණ තීරණය කරයි. දාරවල පූර්ණ සංඛ්‍යා බර සහිත ප්‍රස්ථාරයක් සඳහා, අනුපිළිවෙල සාමාන්‍යයෙන් සමාන වේ (එකම වෙනස වනුයේ උපලක්ෂණ දාරයේ බර අනුව ගමන් කිරීම සහ a[2i+3] සහ a[2i+4] මූලද්‍රව්‍ය මගින් නියම කරනු ලැබීමයි. , සහ දාරයම නියම කරනු ලබන්නේ 4 නොව, ඇණවුම් අංක 5). සහ නිඛිල නොවන දාර බර සහිත ප්‍රස්ථාරයක් සඳහා, එහි බර නොකළ සංරචකයට විශේෂාංග ලිවිය හැක.

නිඛිල දාර බර සහිත ප්‍රස්ථාර සඳහා ආශ්‍රිත යාබද අරාවක් භාවිතා කරන විට, අගයක් ලෙස තනි සංඛ්‍යාවක් නොව, දාරයක බරට අමතරව එහි අවශ්‍ය අනෙකුත් සියල්ල සඳහන් කරන සංඛ්‍යා අරාවක් (දෛශිකයක්) දැක්විය හැක. විශේෂාංග. ඒ අතරම, නිඛිල නොවන බර සඳහා වන අපහසුතාවයක් වනුයේ පාවෙන ලක්ෂ්‍ය අංකයක් සහිත ලකුණක් සඳහන් කිරීමේ අවශ්‍යතාවයයි (ඔව්, මෙය අපහසුතාවයකි, නමුත් එවැනි සලකුණු එතරම් නොමැති නම් සහ ඔබ එසේ නොකරන්නේ නම් ඒවා "උපක්‍රම" දෙගුණයක් සකසන්න එපා, එවිට එය කිසිවක් නොවිය හැකිය) . මෙයින් අදහස් කරන්නේ C++ දිගු ආශ්‍රිත යාබද අරාවන් පහත පරිදි අර්ථ දැක්විය හැකි බවයි: std::map , std::vector> හෝ std:: map , std:: දෛශිකය, එහි "ප්‍රධාන අගය-දෛශිකය" හි පළමු අගය දාරයේ බර වනු ඇත, පසුව එහි ලක්ෂණ වල සංඛ්‍යාත්මක තනතුරු පිහිටයි.

සාහිත්‍යය:

සාමාන්යයෙන් ප්රස්තාර සහ ඇල්ගොරිතම ගැන:

1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. ඇල්ගොරිතම: ඉදිකිරීම් සහ විශ්ලේෂණය, 2 වන සංස්කරණය: Trans. ඉංග්‍රීසියෙන් - එම්.: විලියම්ස් ප්‍රකාශන ආයතනය, 2011.
2. හරාරි ෆ්රෑන්ක්. ප්‍රස්තාර න්‍යාය. එම්.: මීර්, 1973.
මෙම එකම දෛශිකය සහ යාබදව ආශ්‍රිත අරාව පිළිබඳ කතුවරයාගේ වාර්තාව:
3. Chernoukhov S.A. ප්‍රස්ථාර නිරූපණය කිරීමට සහ ගබඩා කිරීමට ක්‍රම ලෙස යාබද දෛශිකය සහ ආශ්‍රිත යාබද අරාව / SA Chernouhov. ප්‍රස්ථාරයක් නිරූපණය කිරීම සඳහා දත්ත ව්‍යුහයන් ලෙස යාබද දෛශිකය සහ යාබද සිතියම // ජාත්‍යන්තර විද්‍යාත්මක හා ප්‍රායෝගික සම්මන්ත්‍රණයේ ලිපි එකතුව “නව්‍ය වර්ධනයන්හි ප්‍රතිඵල ක්‍රියාත්මක කිරීමේ ගැටළු සහ ඒවා විසඳීමට ක්‍රම” (Saratov, සැප්තැම්බර් 14.09.2019, 2019). - ස්ටර්ලිටමාක්: AMI, 65, පි. 69-XNUMX
මාතෘකාව පිළිබඳ ප්රයෝජනවත් මාර්ගගත මූලාශ්ර:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

මූලාශ්රය: www.habr.com