|
¿¬°á ¸®½ºÆ®(Linked List)
|
|
¡á Ãß»óÈ ÀÚ·áÇü(ADT : Abstract Data Type)
- ÀÚ·áÇü(°³³ä)°ú ±âº»¿¬»ê À¯ÇüÀÇ ÁýÇÕÀ¸·Î ±âº»¿¬»êÀ» ¹®Á¦ÇØ°á ÇÁ·Î±×·¥ÀÇ ±¸Çö°ú ºÐ¸®ÇÏ¿© ¸ðµâÈ ÇÁ·Î±×·¡¹ÖÀ» °¡´ÉÇÏ°Ô ÇÏ¿© µð¹ö±ë, °øµ¿ ÇÁ·Î±×·¡¹Ö, ½Ã½ºÅÛ È®Àå µîÀÌ ¿ëÀÌÇÔ. - »ç·Ê : ¸®½ºÆ®(list) ÀÏ·ÃÀÇ ¼ø¼°¡ ÀÖ´Â ÀÚ·á(node)µéÀÇ ÁýÇÕ (±âº»¿¬»ê : find, insert, delete, make_empty, print_list µî)
Ãß»óÈÀÚ·áÇüÀº ¸ðµâÈ ¼³°èÀÇ È®ÀåÀ¸·Î º¼ ¼ö ÀÖÀ¸¸ç, ÀÏ·ÃÀÇ ¿¬»êÇüŸ¦ ¸ð¾Æ ³õÀº °ÍÀ¸·Î ±×·¯ÇÑ ¿¬»êÀÇ ±¸Çö¹æ¹ý°ú ºÐ¸®ÇØ ÁÁÀº °ÍÀÌ´Ù. Á¤¼ö³ª ½Ç¼ö¸¦ ÀÚ·áÇüÀ̶ó°í ºÎ¸£µíÀÌ ¸®½ºÆ®, ÁýÇÕ, ±×·¡ÇÁ¸¦ Ãß»óÈÀÚ·áÇüÀ̶ó°í ºÎ¸¥´Ù. Á¤¼ö³ª ½Ç¼ö¸¦ °¡Áö°í µ¡¼À°ú °ö¼ÀÀ» ÇϵíÀÌ Ãß»óÈÀÚ·áÇüµµ ±âº»¿¬»êÀÌ ÀÖ´Ù. ¿¹¸¦ µé¸é ÁýÇÕ(set) Ãß»óÈÀÚ·áÇü¿¡¼ ÁýÇÕÀÇ ÅëÇÕ(union), ¿ä¼ÒÀÇ Å½»ö(find) µîÀ» ±âº»¿¬»êÀ¸·Î º¼ ¼ö ÀÖ´Ù. ÀÚ·áÃß»óÈÀÇ ±âº»°³³äÀº ÀÌ·¯ÇÑ ±âº»¿¬»êÀ» ¸ðµâÈÇÏ¿© ÇÁ·Î±×·¥ÇÏ¸é ´Ù¸¥ °÷¿¡¼´Â µµ´Ù½Ã ÇÁ·Î±×·¥ÇÏÁö ¾Ê°í ÇÔ¼öÈ£Ãâ¿¡ ÀÇÇÏ¿© ºÒ·¯ ¾²µµ·Ï ÇÑ´Ù´Â °ÍÀÌ´Ù. µû¶ó¼ ÇÁ·Î±×·¥ ¼öÁ¤½Ã ÃÖ¼ÒÇÑÀÇ ³ë·Â¸¸ ÇÊ¿äÇÏ°Ô µÈ´Ù. Ãß»óÈÀÚ·áÇüÀ» ±ÔÁ¤ÇÒ ¶§¿¡´Â ±âº»¿¬»êÀ» ÇÔ²² ±ÔÁ¤Çϴµ¥ ¾î¶°ÇÑ ¿¬»êµéÀ» ±âº»¿¬»êÀ¸·Î ÇÒ °ÍÀ̳Ĵ Á¤ÇØÁø ±ÔÄ¢ÀÌ ¾øÀ¸¸ç ¼³°èÀÚÀÇ Àǵµ¿¡ µû¶ó ´Þ¶óÁø´Ù. ¿ä¾àÇϸé Ãß»óÈÀÚ·áÇüÀ̶õ ÀÚ·áÇü°ú ±âº»¿¬»êÀÇ À¯ÇüÀ» ÇÔ²² ±ÔÁ¤ÇÏ°í ¿¬»êÀÇ ±¸ÇöÀº ºÐ¸®ÇÔÀ¸·Î½á ¸ðµâÈ ÇÁ·Î±×·¥À» °¡´ÉÇÏ°Ô ÇÏ´Â °ÍÀÌ´Ù.
|