http://www.hackerschool.org/HS_Boards/zboard.php?id=Free_Lectures&no=748 [º¹»ç]
¿¬°á ¸®½ºÆ®(Linked List)
¿¬°á ¸®½ºÆ®´Â ³ëµå(node)¿Í ¸µÅ©(link)·Î ±¸¼ºµÇ¾î ÀÖ´Ù.³ëµå¶ó´Â °ÍÀº ½ÇÁ¦ÀÇ Á¤º¸¸¦ ´ã°í ÀÖ´Â ÇϳªÀÇ ´ÜÀ§¸¦ ¸»Çϸç, ¸µÅ©´Â ÀÎÁ¢ ³ëµåÀÇ À§Ä¡¸¦ ÀúÀå°í ÀÖ¾î ¿¬°á ¸®½ºÆ®ÀÇ ¼ø¼¸¦ À¯ÁöÇÒ ¼ö ÀÖ°Ô ÇÏ´Â ¿¬°á°í¸®¸¦ ¸»ÇÑ´Ù.
¿¬°á¸®½ºÆ®´Â Á¤ÀûÀÎ ÀÚ·á ±¸Á¶ÀÎ ¹è¿°ú´Â ´Þ¸® µ¿ÀûÀÎ ÀÚ·á ±¸Á¶ÀÌ´Ù.
ÇÊ¿äÇϸé ÇÒ´çÇÏ°í ÇÊ¿ä¾øÀ¸¸é ÇØÁ¦ÇÏ´Â ½ÄÀÇ ¸Þ¸ð¸® °ü¸®°¡ °¡´ÉÇϱ⠶§¹®¿¡ ¹è¿Ã³·³ ¿©ºÐÀÇ °ø°£À» ¸¶·ÃÇÒ ÇÊ¿ä°¡ ¾ø´Ù. ±×·¡¼ ¸Þ¸ð¸®¸¦ Àý¾àÇÒ ¼ö ÀÖ´Ù.
¶Ç ¿¬°á¸®½ºÆ®°¡ ¹è¿°ú ´Ù¸¥Á¡Àº ¹è¿Àº ¿¬¼ÓµÈ °ø°£À» Â÷ÁöÇϴµ¥ ºñÇؼ ¿¬°á¸®½ºÆ®´Â µ¿ÀûÀ¸·Î ¼ö½Ã·Î ÇÒ´ç ÇØÁ¦µÇ±â ¶§¹®¿¡ ¸Þ¸ð¸®ÀÇ ¿¬¼ÓµÈ °ø°£À» Â÷ÁöÇÏÁö ¸øÇÑ´Ù. ±×·¡¼ ¿¬°á ¸®½ºÆ®ÀÇ ¼ø¼¸¦ À¯Áö½ÃÄÑ ÁÖ´Â °ÍÀº ¸µÅ©(link)¿¡ ÀÇÇؼ °¡´ÉÇØÁø´Ù.
¿¬°á¸®½ºÆ®ÀÇ Á¾·ù·Î´Â ´Ü¼ø¿¬°á ¸®½ºÆ®,ÀÌÁß ¿¬°á¸®½ºÆ®,ȯÇü ¿¬°á¸®½ºÆ® µî ÀÌ ÀÖ´Ù.
´Ü¼ø ¿¬°á ¸®½ºÆ®(Simple Linked List)
´Ü¼ø ¿¬°á ¸®½ºÆ®´Â °¡Àå ´Ü¼øÇÑ ÇüÅÂÀÌ¸é¼ °¡Àå ¸¹ÀÌ ¾²À̱⵵ ÇÏ´Â ÇüÅÂÀÌ´Ù.´Ü¼ø ¿¬°á ¸®½ºÆ®´Â Á¤º¸¸¦ ÀúÀåÇÏ´Â ³ëµå¿Í ¹Ù·Î ´ÙÀ½ÀÇ ³ëµå¸¦ °¡¸®Å°´Â ¸µÅ© Çϳª·Î ±¸¼ºµÇ¾î ÀÖ´Ù.
ÀÚ·áÀÇ ¼ø¼¸¦ ¸¶±¸ ¹Ù²Ù¾î¾ß ÇÒ °æ¿ì ¹è¿ÀÇ °æ¿ì¿¡´Â ´ç±â°í ¹Ì´Â µîÀÇ ¸Þ¸ð¸® º¹»ç°¡ ÇÊ¿äÇÏÁö¸¸, ¿¬°á ¸®½ºÆ®ÀÇ °æ¿ì¿¡´Â ¸µÅ©°¡ °¡¸®Å°´Â ¹æÇ⸸ ¹Ù²Ù¾îÁÖ¸é µÈ´Ù.
´Ü¼ø ¿¬°á ¸®½ºÆ®´Â °¢°¢ÀÌ ´ÙÀ½ÀÇ ³ëµå¸¦ Á¤È®È÷ °¡¸®Å°°í ÀÖÁö¸¸ Á¦ÀÏ Ã³À½ÀÇ ³ëµå¸¦ °¡¸£Ä¡´Â ¸Ó¸®(head)°¡ ÇÊ¿äÇÏ´Ù.
ÀÌ´Â ÀϹÝÀûÀ¸·Î Àü¿ª º¯¼ö·Î ¼±¾ðÀÌ µÇ¾î ¸ðµâ ³»ÀÇ ¾î¶² ºÎºÐ¿¡¼µµ Á¢±Ù °¡´ÉÇϵµ·Ï °³¹æµÇ¾î ÀÖ°í, ¼Ò¸êµÇÁö ¾Ê´Â´Ù.
¿¬°á¸®½ºÆ®ÀÇ Á¦ÀÏ ¸¶Áö¸· ³ëµå´Â Ç×»ó ¹«¾ùÀΰ¡¸¦ °¡¸®ÄÑ¾ß Çϴµ¥ Ưº°È÷ ¸¶Áö¸·À» ³ªÅ¸³»´Â ²¿¸® tail ³ëµå¸¦ ¸¸µé¾î¼ ¸¶Áö¸· ³ëµåÀÓÀ» Ç¥½ÃÇÏ°Ô ÇÑ´Ù.
¿¬°á ¸®½ºÆ®ÀÇ ³ëµå¸¦ C·Î Á¤ÀÇÇغ¸ÀÚ
struct _node
{
int key;
struct _node *next;
};
CÀÇ Ãʺ¸ÀÚµéÀº À§ÀÇ ±¸Á¶Ã¼ Á¤ÀÇ¿¡ ±ÀåÇÑ ´çȤ°¨À» ´À³¥ °ÍÀÌ´Ù. ¿Ö³ÄÇϸé À§ÀÇ _node ±¸Á¶Ã¼ÀÇ Á¤ÀÇ ³»ºÎ¿¡ ´Ù½Ã _nodeÀÇ Æ÷ÀÎÅÍ°¡ µé¾î°¡ ÀÖ´Ù. Áï, _nodeÀÇ ±¸Á¶Ã¼°¡ ä Á¤ÀǵDZ⵵ Àü¿¡ _nodeÀÇ Æ÷ÀÎÅÍ°¡ ÀÖ´Ù´Â °ÍÀº ¸»ÀÌ µÇÁö ¾Ê´Â °Í °°´Ù. ÀÌ °°Àº ±¸Á¶Ã¼ Á¤ÀǸ¦ Àç±ÍÀûÀÎ Á¤ÀÇ ¶ó°í ÇÑ´Ù.
À§ÀÇ Àç±ÍÀûÀÎ Á¤ÀÇ°¡ ¸»ÀÌ µÇ´Â ÀÌÀ¯´Â Æ÷ÀÎÅͶó´Â °ÍÀº ¾î¶² ÇüÀÇ µ¥ÀÌÅ͸¦ °¡¸®Å°µçÁö ±× ÀÚüÀÇ Å©±â´Â º¯ÇÔÀÌ ¾ø±â ¶§¹®ÀÌ´Ù. ¿Ö³ÄÇϸé Æ÷ÀÎÅÍ´Â ÁÖ¼Ò¸¦ ÀúÀåÇϱ⠶§¹®ÀÌ´Ù.
±×·±µ¥ ÇüÅ»óÀ¸·Î ¾à°£Àº °³¼±ÇØ¾ß ÇÒ ¿©Áö°¡ ÀÖ´Ù. struct _node¿Í °°ÀÌ Á¤ÀÇÇÒ °æ¿ì º¯¼öÀÇ Á¤ÀÇ°¡ ¹ø°Å·Ó±â ¶§¹®ÀÌ´Ù.
Ex)struct _node *LinkedList;
_ node ±¸Á¶Ã¼¸¦ Á¤ÀÇÇÒ ¶§ ¾Õ¿¡ °è¼Ó struct¸¦ ºÙÀδٴ °ÍÀº Á¤¸»·Î ±ÍÂúÀº ÀÏÀÌ´Ù. °³¼±À» ÇÑ ³ëµå Á¤ÀǸ¦ º¸ÀÚ
Ex) typedef struct _node
{
int key;
struct _node *next;
}node;
À§ÀÇ typedefÀÇ ¶æÀº struct _node¿Í °°Àº ±¸Á¶Ã¼¸¦ node¶ó´Â µ¥ÀÌÅÍÇüÀ¸·Î Á¤ÀÇÇÑ´Ù´Â ¶æÀÌ´Ù.
º¯¼ö Á¤ÀǸ¦ ÇÏ°Ô µÇ¸é node *LinkedList;
ÈξÀ °£ÆíÇÏ°í º¸±â ÁÁÁö ¾Ê½À´Ï±î?
ÀÌÁ¨ node Á¤ÀǸ¦ °¡Áö°í node·Î ±¸¼ºµÇ´Â ¿¬°á¸®½ºÆ®¸¦ ÃʱâÈ ÇÏ´Â init-list()ÇÔ¼ö¸¦ ¸¸µé¾î º¸ÀÚ
node *head, *tail;
void init_list(void)
{
head=(node*) malloc(sizeof(node));
tail=(node*) malloc(sizeof(node));
head->next=tail;
tail->next=tail;
}
tail->next = tail;´Â ²¿¸®ÀÇ ´ÙÀ½Àº ²¿¸® ¶ó°í Çؼ®ÀÌ µÈ´Ù. ÀÌ·¸°Ô ÇÏ´Â °ÍÀº Áß¿äÇÑ ÀÌÀ¯°¡ Àֱ⠶§¹®ÀÌ´Ù.
t=t->next; ¿Í °°Àº ¹®ÀåÀÌ ÀÖ¾î¼ °è¼Ó ±× ´ÙÀ½ ³ëµå·Î À̵¿ÇÏ´Â °æ¿ì¿¡ ÇÁ·Î±×·¡¸ÓÀÇ ½Ç¼ö·Î ·çÇÁ¸¦ ³¡³»Áö ¸øÇÒ °æ¿ì tail¿¡ ±îÁö À̸£°Ô µÇ´Âµ¥ ÀÌ tailÀÌ NULLÀ̳ª ±âŸ ¾û¶×ÇÑ °÷À» °¡¸® Å°°í ÀÖ´Ù¸é t´Â ¸Þ¸ð¸®ÀÇ È²·®ÇÑ °÷À¸·Î ¼û¾î¹ö¸®°í ¸¸´Ù.
´ë½Å¿¡ ²¿¸®ÀÇ ´ÙÀ½Àº ²¿¸®¶ó°í ¼øȯÀûÀÎ ±¸Á¶¸¦ ÇØ µÑ °æ¿ì ´Ù¿îÀº µÇÁö ¾Ê°í ¹«ÇÑ ·çÇÁ¿¡ ºüÁö°Ô µÈ´Ù.
À§ Á¤ÀÇÇÑ ´ë·Î ÃʱâÈ Çϸé ÀÌ ¿¬°á¸®½ºÆ®´Â ½ÇÁ¦ ³»¿ëÀº ¾Æ¹«°Íµµ ¾ø´Â ºó ¿¬°á ¸®½ºÆ®ÀÌ´Ù.
ÀÌÁ¦ ºó ¿¬°á ¸®½ºÆ®¿¡ ´Ù¸¥ ³ëµå¸¦ »ðÀÔÇÏ´Â ÇÔ¼ö insert_atfer()ÇÔ¼ö¸¦ ¸¸µé¾î º¸ÀÚ
´Ü¼ø ¿¬°á ¸®½ºÆ®´Â t´Â µÚÀÇ ³ëµå¸¸À» ¾Ë ¼ö ÀÖÁö ¾ÕÀÇ ³ëµå°¡ ¹«¾ùÀÎÁö´Â ¾Ë ¼ö ¾ø´Ù.
±×·¡¼ tÀÇ µÚÀÇ ³ëµå¸¦ °¡¸®Å°´Â ¸µÅ©¸¸À» Á¶ÀÛÇÒ ¼ö ÀÖ¾î µÚ¿¡´Ù°¡ »ðÀÔÀ» ÇÒ ¼ö ¹Û¿¡ ¾ø´Â °ÍÀÌ´Ù.
Ex) node *insert_after(int k, node* t)
{
node *s;
s=(node*)malloc(sizeof(node));
s->key =k;
s->next=t->next;
t->next=s;
return s;
}
ÀÌÁ¦´Â »èÁ¦ÇÏ´Â ÇÔ¼ö delete_next() ÇÔ¼ö´Â
int delete_next (node *t)
{
node *s; //³ëµåÀÇ Æ÷ÀÎÅÍ Á¤ÀÇ
if(t->next ==tail) //tÀÇ ´ÙÀ½³ëµå°¡ tail°ú °°Àº°¡? ¸ÂÀ¸¸é ¸®ÅÏ 0
return 0;
s=t->next;// tÀÇ ´ÙÀ½³ëµå°¡ tail°ú °°Àº°¡? ¾Æ´Ï¸é s¿¡ tÀÇ ´ÙÀ½ ³ëµåÀÇ ÁÖ¼Ò°ªÀ» ³Ñ±ä´Ù.
t->next = t->next->next;//tÀÇ next¿¡ »èÁ¦ÇÒ ³ëµåÀÇ ´ÙÀ½ ³ëµåÀÇ ÁÖ¼Ò°ªÀ» ÀúÀåÇÑ´Ù.
free(s);//s°¡ °¡Áö°í ÀÖ´Â ÁÖ¼Ò°ªÀÇ ³ëµå¸¦ »èÁ¦ÇÑ´Ù. (free´Â mallocÇÔ¼ö·Î Á¤ÀÇÇÑ µ¥ÀÌÅ͸¦ »èÁ¦ÇÒ ¶§ »ç¿ëÇÑ´Ù.
return 1;
}
À§¿¡ ÁÖ¼®À» º¸°í ¼Ò½º¸¦ ºÐ¼®ÇØ º¸ÀÚ.
óÀ½º¸½Ã´Â ºÐµµ ¸î¹øº¸¸é ÀÌÇØ°¡ µÇ½Ç °ÍÀÌ´Ù.
±×·³ ³ª¸ÓÁö °Ë»öÇÏ´Â ÇÔ¼ö³ª Àüü»èÁ¦ °Ë»öÇÑ ´ÙÀ½ »ðÀÔ È¤Àº »èÁ¦ µî ÇÔ¼öµéÀº ¿©·¯ºÐµéÀÌ Á÷Á¢ ¸¸µé¾î º¸¼¼¿ä ^^.
|
Hit : 7866 Date : 2007/06/21 09:34
|