#dokydoky

[연습문제] 열혈강의 자료구조 3장(1번~4번) 본문

Programming

[연습문제] 열혈강의 자료구조 3장(1번~4번)

dokydoky 2011. 8. 28. 02:21

1. 배열 리스트와 연결 리스트의 장점과 단점을 비교.

-> 배열리스트는 구현이 비교적 간단하고 탐색시간(원소에 접근시간)이 빠르나, 배열의 크기가 정해져 있으며 원소의 추가,

삭제시 다른 원소들까지 이동시켜야 한다는 단점이 있다. 이와 반대로, 연결 리스트는 비교적 구현이 복잡하고 탐색시간이

오래걸리지만, 원소의 추가/삭제가 간단하다.(단, 메모리를 좀 더 먹음)

결론적으로, 크기가 정해지지 않고 검색이 적으며, 원소의 추가/삭제가 빈번한 곳에는 연결리스트의 구현이 적당..


2. 단순연결리스트, 원형 연결리스트, 이중연결리스트의 차이점

-> 세가지 리스트의 차이점은 노드의 링크차이다. 단순 연결리스트는 한쪽으로만 링크가 되어있고 마지막 원소의 링크는

NULL, 원형 연결리스트는 단순연결리스트와 비슷하나 마지막노드가 다시 첫노드를 가리킨다. 그리고 이중연결리스트는

노드 하나에 L링크, R링크 가 있다는 점. 이중연결리스트가 가장 노드의 접근이 용이하나 메모리가 더 많이 차이한다는

단점이 있다.


3.
 1) 원소가 10개인 배열리스트에서 2번 위치에 원소를 추가할 경우, 몇개의 원소가 이동되어야 하느냐.
   -> index는 0부터 시작하므로 2~9번 원소들이 이동되더야 한다. 따라서 8번

 2) 이번엔 제거할때, 몇번이동해야되냐
    -> 제거는 3~9번이 한칸씩 앞으로 땡기기만 하면되니까 7번


4.

 정신없이 짜다가 논리적으로 뭔가가 꼬였다.. 이것때문에 2일동안 버그찾느라 고생함.. 도중에 짱나서 첨부터

다른방식으로 짜봤는데 또 버그... T^T..  천천히 맘잡고 디버깅해보다가 찾음. 별것도 아닌문제였음.

뭔가 안될 땐, 역시 조급하지 않고 천천히 생각해보는게 쵝외인듯..

첫번째 오류는... getCLElement() 함수에서 노드찾는 반복문에서 position대신 pList->curElementCnt를 썻음;;
(다른생각하면서 짯나????)

이것때문에 Add함수나 remove함수가 잘못된지알고 이것만 겁나게 들여다보다가 코드를 걍 새로 짯음...

그런데...... 두번째 오류.. 는 add함수에서...

int addCLElement(CircularList* pList, int position, CircularListNode element)
{
 int i = 0;
 int ret = FALSE;

 CircularListNode *pNewNode = NULL;
 CircularListNode *pPreNode = NULL;
 CircularListNode *pLastNode = NULL;

 if( pList != NULL )
 {
  if( position >= 0 && position <= pList->curElementCnt )
  {
   pNewNode = (CircularListNode*)malloc(sizeof(CircularListNode));
   if( pNewNode == NULL )
   {
    printf("addCLElement Error! pNewNode 할당실패\n");

    return ret;
   }

   *pNewNode = element;
   pNewNode->pLink = NULL;

   pPreNode = &(pList->headerNode);
   for(i=0; i<position; i++)
   {
    pPreNode = pPreNode->pLink;
   }

   pNewNode->pLink = pPreNode->pLink;
   pPreNode->pLink = pNewNode;

   pList->curElementCnt++;

   pLastNode = &(pList->headerNode);
   for(i=0; i<pList->curElementCnt; i++)
   {
    pLastNode = pLastNode->pLink;
   }
   
   pLastNode->pLink = pList->headerNode.pLink;

   ret = TRUE;
  }
  else
  {
   printf("addCLElement Error! position(%d) \n", position);
  }
 }

 return ret;
}


굵은 부분에서 노드를 추가한다음에 pLastNode를 찾아야 하는데, pPreNode와 pLastNode를 둘다 찾아놓고

진행했더니 생긴 문제였다.. ( 원소갯수가 0일때 오류남 )


첨부파일은 완성된 코드와 Add/Remove 함수를 두가지 방법으로 짜본것...

개인적인 생각으론 방법1이 좋은거같음... 방법2는 headerNode를 쓰는거랑 포인터쓰는거랑 같아서

headerNode를 쓰는 메리트가 없음..






 

Comments