1581, 79/80 ȸ¿ø°¡ÀÔ  ·Î±×ÀΠ 
   han0161
   ¿¬°á¸®½ºÆ®

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 : 7786     Date : 2007/06/21 09:34



    
21   ¿ìºÐÅõ¿¡¼­ ¹«¼±·£ Àâ±â[3]     lee73mu
02/01 8458
20   ¿Í¿ìÇØÄ¿ level1[3]     ÇÁ¶óÀ̵å
08/20 9206
19   ¿Í¿ìÇØÄ¿level2 ¹®Á¦Ç®ÀÌ[3]     ÇÁ¶óÀ̵å
08/20 9203
18   ¿ÕÃʺ¸ ÆÄÀ̽ã (Python) ¾ð¾î ¹è¿ì±â - Site Ãßõ[5]     Ǫ¸¥ÇÏ´Ã
12/14 10852
17   ¿ÕÃʺ¸ÀÚ µéÀ» À§ÇÑ C ¾ð¾î °­ÁÂ[7]     kevin0960
01/25 8625
16   ¿äÁò °øºÎÇÏ°í ÀÖ´Â JAVA¿¡ ´ëÇÑ Áú¹®°ú ´äº¯[3]     Àå¼¼¸¸
07/14 7852
15   ¿Ö C À̾î¾ß Çϴ°¡ ?[96]     ¼ÒÀ¯
04/09 24893
14   ¿Ö ÇØÄ¿°¡ µÇ·Á´Â°¡[6]     dontknow
07/22 10212
13   ¿Ö °íµîÇб³[5]     ÆĶõ´«¹°
02/05 7387
12   ¿ö°ÔÀÓ ¹®Á¦ ÈùÆ®Á» ÁֽǺР±¸ÇÔ     rabbitlycat
04/30 5926
11   ¿ö°ÔÀÓ »çÀÌÆ®ÀÔ´Ï´Ù. [4]     wkdqkf2
03/18 8124
10   ¿ö°ÔÀÓÀ» Çغ¾½Ã´Ù.hackthissite(basic 1)[2]     kjwon15
09/10 9226
9   ¿¡±×½© ¾µÁÙ ¸ð¸£½Ã´ÂºÐ..-_-Çʵ¶[9]     ÀºÁ¶
09/28 10848
8   ¿©·¯ºÐ[1]     phan_tom1
11/18 7488
7   ¿©·¯ºÐ! net send Á¤¸®ÇØ µå¸³´Ï´Ù.[11]     idl0521
12/13 10141
6   ¿©·¯¼±¹è´Ôµé Á»µµ¿ÍÁֽʽÿÀ..[2]     appleone
06/29 7472
  ¿¬°á¸®½ºÆ®     han0161
06/21 7785
4   ¿­(TR)°ú Çà(TD)ÀÇ È®Àå(Æß)     rahzzang
11/21 6692
3   ¿øÀç¾Æºü´ÔÀÇ gcc 2.96¿¡¼­ÀÇ ¹öÆÛ ±¸Á¶ °­ÁÂ.[9]     ttongfly
09/19 13122
2   ¿ø°ÝÁ¾·á....[39]     bsjzzz
01/02 11905
[1]..[71][72][73][74][75][76][77][78] 79 [80]

Copyright 1999-2024 Zeroboard / skin by Hackerschool.org / Secure Patch by Hackerschool.org