원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를

Transcription

1 리스트에대한설명중틀린것은 구조체도리스트의요소가될수있다 리스트의요소간에는순서가있다 리스트는여러가지방법으로구현될수있다 리스트는집합과동일하다 다음은순차적표현과연결된표현을비교한것이다 설명이틀린것은 연결된표현은포인터를가지고있어상대적으로크기가작아진다 연결된표현은삽입이용이하다 순차적표현은연결된표현보다액세스시간이많이걸린다 연결된표현으로작성된리스트를 개로분리하기가쉽다 다음은연결리스트에서있을수있는여러가지경우를설명했는데잘못된항목은 정적인데이터보다는다양하고변화있는데이터에서효과적인방법이다 모든노드는데이터와링크 포인터 를가지고있어야한다 연결리스트에서사용한기억장소는다시사용할수없다 데이터들이메모리상에흩어져서존재할수있다 삽입과삭제작업이자주발생할때실행시간이가장많이소요되는자료구조는 배열로구현된리스트 단순연결리스트 원형연결리스트 이중연결리스트 다음중 포인터 가존재하지않는구조는어느것인가 단순연결리스트 원형연결리스트 이중연결리스트 헤더노드를가지는단순연결리스트

2 원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를가리킨다고할때다음수식중 참인것은 last == NULL last->data == NULL last->link == NULL last->link->link == NULL 단순연결리스트의노드들을노드포인터 p 로탐색하고자한다 p 가현재가 리키는노드에서다음노드로가려면어떻게하여야하는가 p++; p--; p=p->link; p=p->data; 단순연결리스트의관련함수 f 가헤드포인터 head 를변경시켜야한다면 함수파라미터로무엇을받아야하는가 head &head *head head->link; 라는공백상태의리스트가있다고가정하자 이리스트에대하여다음과같 은연산들이적용된후의리스트의내용을그려라 add_first(a, "first"); add(a, 1, "second"); add_last(a,"third"); add(a,2,"fourth"); add(a,4,"fifth"); delete(a,2); delete(a,2); replace(a, 3, "sixth");

3 배열을이용하여구현한리스트의경우 리스트의연산중일부연산만구현 되어있다 본문의코드를참조하여리스트 의나머지연산들도구현하여 보라 #include <stdio.h> #include <stdlib.h> #define MAX_LIST_SIZE 100 배열의최대크기 #define TRUE 1 #define FALSE 0 typedef int element; typedef struct int list[max_list_size]; 배열정의 int length; 현재배열에저장된자료들의개수 ArrayListType; 오류처리함수 void error(char *message) fprintf(stderr,"%s\n",message); exit(1); 리스트초기화 void init(arraylisttype *L) L->length = 0; 리스트가비어있으면 1 을반환 그렇지않으면 0 을반환 int is_empty(arraylisttype *L) return L->length == 0;

4 리스트가가득차있으면 1 을반환 그렇지많으면 1 을반환 int is_full(arraylisttype *L) return L->length == MAX_LIST_SIZE; 리스트출력 void display(arraylisttype *L) int i; for(i=0;i<l->length;i++) printf("%d\n", L->list[i]); position: 삽입하고자하는위치 item: 삽입하고자하는자료 void add(arraylisttype *L, int position, element item) if(!is_full(l) && (position >= 0) && (position <= L->length) ) int i; for(i=(l->length-1); i>=position;i--) L->list[i+1] = L->list[i]; L->list[position] = item; L->length++; void add_first(arraylisttype *L, element item) add(l,0,item); void add_last(arraylisttype *L, element item) add(l,l->length,item); position: 삭제하고자하는위치 반환값 : 삭제되는자료 element delete(arraylisttype *L, int position) int i; element item; if( position < 0 position >= L->length ) error(" 위치오류 ");

5 item = L->list[position]; for(i=position; i<(l->length-1);i++) L->list[i] = L->list[i+1]; L->length--; return item; void clear(arraylisttype *L) L->length=0; void replace(arraylisttype *L, int position, element item) L->list[position]=item; int is_in_list(arraylisttype *L, element item) int i; for(i=0; i<(l->length);i++) if(l->list[i]==item) return TRUE; return FALSE; element get_entry(arraylisttype *L, int position) if( position < 0 position >= L->length ) error(" 위치오류 "); return L->list[position]; main() ArrayListType list1; ListType 를정적으로생성하고 ListType 를가리키는 포인터를함수의파라미터로전달한다. init(&list1); add_first(&list1, 10); add_first(&list1, 20); add_last(&list1, 30); display(&list1); 단순연결리스트에서삭제함수 delete 함수는사실은헤드포인터와선행노

6 드포인터의 개의파라미터만있으면작성이가능하다 이들두파라미터만을 사용하여다시작성하라 phead : 헤드포인터에대한포인터 p: 삭제될노드의선행노드 void remove_node( ListNode **phead, ListNode *p ) ListNode *removed; if( p == NULL ) removed = (*phead); *phead = (*phead)->link; else removed=p->link; p->link = removed->link; free(removed); 단순연결리스트에정수가저장되어있다 단순연결리스트의모든데이터 값을더한합을출력하는프로그램을작성하시오 int sum( ListNode *head ) ListNode *p=head; int sum=0; while( p!= NULL ) sum += p->data; p = p->link; return sum; 단순연결리스트에서특정한데이터값을갖는노드의개수를계산하는함수 를작성하라 int count( ListNode *head, int x ) ListNode *p=head;

7 int count=0; while( p!= NULL ) if( p->data == x ) count++; p = p->link; return count; 단순연결리스트에서의탐색함수를참고하여특정한데이터값을갖는노드 를삭제하는함수를작성하라 void search_remove(listnode **phead, int x) ListNode *p, *prev=null; p = *phead; while( p!= NULL ) if( p->data == x ) remove_node(phead, prev, p); if( prev!= NULL ) p=prev->link; else p=*phead; else prev=p; p = p->link; 단순연결리스트의헤드포인터가주어져있을때첫번째노드에서부터하 나씩건너서있는노드를전부삭제하는함수를작성하라 즉홀수번째있는노 드들이전부삭제된다 홀수번째노드삭제 void remove_odd(listnode **phead) ListNode *p, *prev=null; int count=0; p = *phead; while( p!= NULL ) if( (count%2)!=0 ) remove_node(phead, prev, p);

8 if( prev!= NULL ) p=prev->link; else p=*phead; else prev=p; p = p->link; count++; 두개의단순연결리스트 가주어져있을경우 alternate 함수를작 성하라 alternate 함수는 와 로부터노드를번갈아가져와서새로운리스 트 를만드는연산이다 만약입력리스트중에서하나가끝나게되면나머지 노드들을전부 로옮긴다 함수를구현하여올바르게동작하는지테스트하라 작성된함수의시간복잡도를구하라 A a1 a2 a3 NULL A a4 NULL NULL B b1 b2 b3 NULL B b4 NULL NULL C a1 b1 a2 NULL C b2 NULL NULL void insert_node_last(listnode **phead, element item) ListNode *new_node = create_node(item, NULL); if( *phead == NULL ) *phead = new_node; else ListNode *p = *phead; while(p->link!= NULL) p = p->link; p->link = new_node; ListNode *alternate(listnode *list1, ListNode *list2)

9 ListNode *list3=null; ListNode *p1, *p2, *p3=null; if( list1 == NULL ) return list2; else if( list2 == NULL ) return list1; else p1 = list1; p2 = list2; while(( p1!= NULL ) ( p2!= NULL )) if( p1!= NULL ) insert_node_last(&list3, p1->data); p1=p1->link; if( p2!= NULL ) insert_node_last(&list3, p2->data); p2=p2->link; return list3;