Lab 5. 실습문제 (Double linked list)-1_해답.hwp

Size: px

Start display at page:

Download "Lab 5. 실습문제 (Double linked list)-1_해답.hwp"

정우 선우
5 years ago
Views:

1 Lab 5. Doubly-linked list 의구현 실험실습일시 : 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Doubly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Doubly-linked list의각함수를구현한다. 실습순서 단계 1. 주어지는코드와함수설계를참고해, mp3 플레이어의플레이리스트 (play list) 관리프로그램을구현하시오. 해당플레이리스트는원형이중-연결리스트로구현해야하며, 구현해야하는함수와자료구조, main 함수는주어진코드를이용해서구현해야한다. #include <stdio.h> #include <conio.h> #include <stdlib.h> //MP3 플레이어의최대용량 128MB #define MAX 128 // 한곡의용량 4MB #define SONGSIZE 4 // 리스트입력모드 flag #define NORMAL 0 #define FIRST 1 // 리스트노드구조체 struct ListNode char *title; // 제목 char *singer; // 가수 struct ListNode *next; // 다음노드의포인터 struct ListNode *previous; // 이전노드의포인터 ; typedef struct ListNode LISTNODE; // 리스트구조체 struct List int listsize; LISTNODE *play; LISTNODE *first; ; typedef struct List LIST; // 리스트의크기 // 현재재생중인곡 // 리스트의첫번째곡

2 void initlist(list *list); // 리스트초기화함수 void printlist(list *list); // 리스트출력함수 bool isempty(list *list); // 리스트가비어있는지확인하는함수 bool isfull(list *list); // 용량이가득차있는지확인하는함수 void insertmusic(list *list, int mode); // 곡을추가하는함수 void insertmusicsub(list *list, LISTNODE *node); // 리스트에노드추가 void insertmusicfirstsub(list *list, LISTNODE *node); // 리스트의처음위치에노드추가 void deletemusic(list *list); // 곡을삭제하는함수 void deletemusicsub(list *list, LISTNODE *node); // 리스트에서노드를삭제하는함수 void moveprev(list *list); // 앞곡으로이동 void movenext(list *list); // 뒷곡으로이동 void main() LIST *list; char cmd; // 리스트에동적으로메모리할당 list = (LIST *)malloc(sizeof(list)); // 리스트초기화 initlist(list); do printf("**************** Choose Command!! ******************* n"); printf("+: Insert song S: Insert song in the first n"); printf("-: Delete song P: Play previous song N: Play next song n"); printf("f: full check E: empty check Q: Quit n"); printf("***************************************************** n"); // 리스트출력 printlist(list); // 커맨드입력 printf("command: "); cmd = getch(); // 커맨드는무조건대문자로입력 cmd = toupper(cmd); putch(cmd); printf(" n"); switch (cmd) case '+' : // 곡추가 insertmusic(list,normal); case 'S' : // 처음위치에곡추가 insertmusic(list,first);

3 case '-' : // 곡삭제 deletemusic(list); case 'E' : // 비어있는지확인 if (isempty(list)) printf ("List is empty! n"); printf ("List isn't empty n"); case 'F' : // 가득찼는지확인 if (isfull(list)) printf ("List is full! n"); printf ("List isn't full! n"); case 'P' : // 왼쪽으로커서이동 moveprev(list); case 'N' : // 오른쪽으로커서이동 movenext(list); case 'Q' : // 종료 default : // 잘못된커맨드입력시 printf(" nwrong command! Retry! n"); while ( cmd!='q' ); 1) initlist(), isempty(), isfull(), printlist() 함수는아래코드를참고할것. initlist() 함수는리스트를초기화하는함수로리스트의멤버인 first, play, listsize를각각 0과 NULL로초기화한다. isempty() 와 isfull() 은리스트의상태를확인하는함수로 isempty() 는리스트가비어있는지확인하는함수로 listsize가 0이면 true를반환하고 1이상이면 false를반환한다. isfull() 은리스트에들어있는음악파일들의크기를계산해 ( 파일한개당크기는 4MB로가정 ) 최대크기를벗어나는지를확인하는함수로최대크기를넘어가면 true, 아닌경우에는 false를반환한다. printlist() 함수는리스트에들어있는곡을화면에출력해주는함수로각리스트노드의가수, 제목을순서대로출력한다. // 리스트초기화함수 void initlist(list *list) // 리스트구조체의멤버를각각초기화한다. // 리스트크기 = 0, 커서와첫번째노드 = NULL list->first = list->play = NULL; list->listsize = 0;

4 // 리스트가비어있는지확인 bool isempty(list *list) if (list->listsize == 0) return true; return false; // 용량이가득차있는지확인 bool isfull(list *list) if (list->listsize*songsize >= MAX) return true; return false; // 리스트출력 void printlist(list *list) int nnum = 1; // 임시사용포인터선언 LISTNODE *tempcursor; // 리스트의첫노드를가리킴 tempcursor = list->first; if (isempty(list)) // 리스트가비어있는경우 printf("list is empty! n"); printf("====================================== n"); printf("play : %s, t%s n",list->play->singer,list->play->title); printf("====================================== n"); do // Play list 출력 -> [ 곡번호 ] : [ 가수 ], [ 제목 ] printf("%d : %s, t%s n",nnum,tempcursor->singer,tempcursor->title); tempcursor = tempcursor->next; nnum++; while(tempcursor!= list->first); printf(" n");

5 2) 리스트에곡을추가하는함수 void insertmusic(list *list, int mode) 의 sub 함수들을구현하시오. 이함수는매개변수로받는 mode의값에따라 NORMAL 이면 void insertmusicsub(list *list, LISTNODE *node) 함수를호출하고 FIRST이면 void insertmusicfirstsub(list *list, LISTNODE *node) 를호출한다. void insertmusicsub(list *list, LISTNODE *node) 은현재플레이되고있는곡의다음위치에곡을추가하고플레이를하게하는함수이다. 매개변수로 LIST형의 list포인터와 LISTNODE 형의포인터를받으며매개변수 node는리스트에추가돼야하는노드이다. void insertmusicfirstsub(list *list, LISTNODE *node) 는앞의 sub함수와마찬가지역할을하지만리스트의제일처음에매개변수 node를추가하는함수이다. 위의두 sub 함수들은삽입이불가능한상황 (ex) 리스트가가득차있는경우 ) 에는그에따른에러메시지를출력해야한다. void insertmusic(list *list,int mode) // 새로운노드선언 LISTNODE *tempnode; // 새로운노드에동적메모리할당후 data 저장 tempnode = (LISTNODE *)malloc(sizeof(listnode)); tempnode->title = (char *)malloc(sizeof(char)*20); tempnode->singer = (char *)malloc(sizeof(char)*20); printf ("========================================== n"); // 가수입력 printf ("Singer : "); gets(tempnode->singer); // 제목입력 printf ("Title : "); gets(tempnode->title); printf(" n"); // sub 함수호출 if (mode == NORMAL) insertmusicsub(list, tempnode); if (mode == FIRST) insertmusicfirstsub(list, tempnode); void insertmusicsub(list *list, LISTNODE *node) if(isfull(list)) printf("list is full! Can't insert. n"); // 리스트가비어있는경우 list->first = node; list->play = node;

6 node->next = NULL; node->previous = NULL; if(list->play->next == NULL) // 리스트의끝에삽입할경우 node->next = NULL; node->previous = list->play; list->play->next = node; // 리스트에노드가존재하는경우 node->next = list->play->next; list->play->next->previous = node; list->play->next = node; node->previous = list->play; list->listsize++; // 리스트에 data를입력하는함수 void insertmusicfirstsub(list *list, LISTNODE *node) if(isfull(list)) printf("list is full! Can't insert. n"); // 리스트가비어있는경우 list->first = node; list->play = node; node->next = NULL; node->previous = NULL; // 리스트의처음에삽입할경우 list->first->previous = node; node->next = list->first; node->previous = NULL; list->first = node; list->listsize++;

7 3) 리스트에서현재플레이중인곡을삭제하는 void deletemusic(list *list) 의 sub 함수 void deletemusicsub(list *list, LISTNODE *node) 를구현하시오. 매개변수로받는 list 의현재플레이중인곡을리스트에서삭제하고, 그정보를출력해주는함수이다. void deletemusicsub(list *list, LISTNODE *node) 함수는매개변수로 LIST형의포인터 list를받아현재플레이중인곡을삭제하고그곡의정보를두번째매개변수인 node에저장하는함수이다. 위 sub 함수는삭제가불가능한상황 (ex) 리스트가비어있는경우 ) 에는그에따른에러메시지를출력해야한다. void deletemusic(list *list) // 삭제된노드의 data를임시저장할변수 LISTNODE *deletednode; deletednode = (LISTNODE *)malloc(sizeof(listnode)); deletednode->singer = NULL; deletednode->title = NULL; deletemusicsub(list, deletednode); printf (" ndeleted song is %s's %s n",deletednode->singer,deletednode->title); free(deletednode); // 리스트에서 data를삭제하는함수 void deletemusicsub(list *list, LISTNODE *node) printf("list is empty! Can't delete. n"); node->singer = list->play->singer; node->title = list->play->title; // 리스트에노드가한개만있는경우 if(list->listsize == 1) list->play = NULL; list->first = NULL; // 커서가리스트의첫노드에있는경우 if(list->first == list->play) list->first = list->play->next; list->play->previous = NULL;

8 // 커서가리스트의마지막노드에있는경우 if(list->play->next == NULL) list->play->previous->next = NULL; list->play = list->play->previous; // 그외의경우 list->play->previous->next = list->play->next; list->play->next->previous = list->play->previous; list->listsize--; 4) 플레이리스트에서재생곡을바꾸는함수 void moveprev (LIST *list) 와 void movenext (LIST *list) 를구현한다. 이함수들은각각현재재생곡을앞의곡과뒤의곡으로변경시키는함수이다. 매개변수로 LIST형의포인터 list를받고반환값은없다. 두함수는커서를이동시킬수없는상황에서이동을시키려고하면에러메시지를출력하며변경이불가능하게구현되어야한다. (ex) 리스트가비어있거나, 리스트에노드가한개만있는경우 ) // 앞곡으로변경 void moveprev(list *list) printf("list is empty! Can't move. n"); // 리스트에노드가 1개밖에없거나커서가첫노드에있는경우 if(list->play == list->first list->listsize == 1) printf("the course is in the first item! Can't move. n"); // 커서를왼쪽으로이동 list->play = list->play->previous; // 뒷곡으로변경 void movenext(list *list)

9 printf("list is empty! Can't move. n"); // 리스트에노드가 1개밖에없거나커서가마지막노드에있는경우 if(list->play->next == NULL list->listsize == 1) printf("the course is in the last item! Can't move. n"); // 커서를오른쪽으로이동 단계 2. 단계 1에서완성된프로그램을실행시켜각함수들을테스트해보고그결과화면을캡쳐하시오. Extra 문제 (+3점). 단계 2까지완성된프로그램에서리스트내의모든곡들을삭제하는 void clearlist(list *list) 함수를작성하시오. 리스트의포인터만을초기화하는것뿐만아니라, 동적할당을통해할당받은각노드의메모리공간을모두해제해야한다. Extra 문제 (+1점). 단계 2까지완성된프로그램에서 LISTNODE의자료구조와 insertmusic() 와 sub 함수, deletemusic() 와 sub함수, isfull() 을수정해각곡의크기를다르게저장할수있도록하시오. LISTNODE의자료구조에파일의크기를저장할수있는필드 unsigned int filesize를추가하시오. 이에따라 insertmusic() 에서는용량을입력하는코드를추가하고, deletemusic() 에서는삭제된파일의크기를출력하도록변경하시오. isfull() 함수에서는리스트에있는모든노드들의크기를합산해최대크기와비교하도록수정하시오. 과제수행결과 ( 결과화면및소감 )

10 [Source] #include <stdio.h> #include <conio.h> #include <stdlib.h> //MP3 플레이어의최대용량 128MB #define MAX 128 // 한곡의용량 4MB #define SONGSIZE 4 // 리스트입력모드 flag #define NORMAL 0 #define FIRST 1 // 리스트노드구조체 struct ListNode char *title; // 제목 char *singer; // 가수 struct ListNode *next; // 다음노드의포인터 struct ListNode *previous; // 이전노드의포인터 ; typedef struct ListNode LISTNODE; // 리스트구조체 struct List int listsize; LISTNODE *play; LISTNODE *first; ; typedef struct List LIST; // 리스트의크기 // 현재재생중인곡 // 리스트의첫번째곡 void initlist(list *list); // 리스트초기화함수 void printlist(list *list); // 리스트출력함수 bool isempty(list *list); // 리스트가비어있는지확인하는함수 bool isfull(list *list); // 용량이가득차있는지확인하는함수 void insertmusic(list *list, int mode); // 곡을추가하는함수 void insertmusicsub(list *list, LISTNODE *node); // 리스트에노드추가 void insertmusicfirstsub(list *list, LISTNODE *node); // 리스트의처음위치에노드추가 void deletemusic(list *list); // 곡을삭제하는함수 void deletemusicsub(list *list, LISTNODE *node); // 리스트에서노드를삭제하는함수 void moveprev(list *list); // 앞곡으로이동 void movenext(list *list); // 뒷곡으로이동 void main() LIST *list; char cmd; // 리스트에동적으로메모리할당 list = (LIST *)malloc(sizeof(list));

11 // 리스트초기화 initlist(list); do printf("**************** Choose Command!! ******************* n"); printf("+: Insert song S: Insert song in the first n"); printf("-: Delete song P: Play previous song N: Play next song n"); printf("f: full check E: empty check Q: Quit n"); printf("***************************************************** n"); // 리스트출력 printlist(list); // 커맨드입력 printf("command: "); cmd = getch(); // 커맨드는무조건대문자로입력 cmd = toupper(cmd); putch(cmd); printf(" n"); switch (cmd) case '+' : // 곡추가 insertmusic(list,normal); case 'S' : // 처음위치에곡추가 insertmusic(list,first); case '-' : // 곡삭제 deletemusic(list); case 'E' : // 비어있는지확인 if (isempty(list)) printf ("List is empty! n"); printf ("List isn't empty n"); case 'F' : // 가득찼는지확인 if (isfull(list)) printf ("List is full! n"); printf ("List isn't full! n"); case 'P' : // 왼쪽으로커서이동 moveprev(list); case 'N' : // 오른쪽으로커서이동 movenext(list); case 'Q' : // 종료

12 while ( cmd!='q' ); default : // 잘못된커맨드입력시 printf(" nwrong command! Retry! n"); // 리스트초기화함수 void initlist(list *list) // 리스트구조체의멤버를각각초기화한다. // 리스트크기 = 0, 커서와첫번째노드 = NULL list->first = list->play = NULL; list->listsize = 0; // 리스트가비어있는지확인 bool isempty(list *list) if (list->listsize == 0) return true; return false; // 용량이가득차있는지확인 bool isfull(list *list) if (list->listsize*songsize >= MAX) return true; return false; // 리스트출력 void printlist(list *list) int nnum = 1; // 임시사용포인터선언 LISTNODE *tempcursor; // 리스트의첫노드를가리킴 tempcursor = list->first; if (isempty(list)) // 리스트가비어있는경우 printf("list is empty! n"); printf("====================================== n"); printf("play : %s, t%s n",list->play->singer,list->play->title); printf("====================================== n"); do

13 // Play list 출력 -> [ 곡번호 ] : [ 가수 ], [ 제목 ] printf("%d : %s, t%s n",nnum,tempcursor->singer,tempcursor->title); tempcursor = tempcursor->next; nnum++; while(tempcursor!= NULL); printf(" n"); void insertmusic(list *list,int mode) // 새로운노드선언 LISTNODE *tempnode; // 새로운노드에동적메모리할당후 data 저장 tempnode = (LISTNODE *)malloc(sizeof(listnode)); tempnode->title = (char *)malloc(sizeof(char)*20); tempnode->singer = (char *)malloc(sizeof(char)*20); printf ("========================================== n"); // 가수입력 printf ("Singer : "); gets(tempnode->singer); // 제목입력 printf ("Title : "); gets(tempnode->title); printf(" n"); // sub 함수호출 if (mode == NORMAL) insertmusicsub(list, tempnode); if (mode == FIRST) insertmusicfirstsub(list, tempnode); void insertmusicsub(list *list, LISTNODE *node) if(isfull(list)) printf("list is full! Can't insert. n"); // 리스트가비어있는경우 list->first = node; list->play = node; node->next = NULL; node->previous = NULL; if(list->play->next == NULL) // 리스트의끝에삽입할경우 node->next = NULL; node->previous = list->play;

14 list->play->next = node; // 리스트에노드가존재하는경우 node->next = list->play->next; list->play->next->previous = node; list->play->next = node; node->previous = list->play; list->listsize++; // 리스트에 data를입력하는함수 void insertmusicfirstsub(list *list, LISTNODE *node) if(isfull(list)) printf("list is full! Can't insert. n"); // 리스트가비어있는경우 list->first = node; list->play = node; node->next = NULL; node->previous = NULL; // 리스트의처음에삽입할경우 list->first->previous = node; node->next = list->first; node->previous = NULL; list->first = node; list->listsize++; void deletemusic(list *list) // 삭제된노드의 data를임시저장할변수 LISTNODE *deletednode; deletednode = (LISTNODE *)malloc(sizeof(listnode)); deletednode->singer = NULL; deletednode->title = NULL;

15 deletemusicsub(list, deletednode); printf (" ndeleted song is %s's %s n",deletednode->singer,deletednode->title); free(deletednode); // 리스트에서 data를삭제하는함수 void deletemusicsub(list *list, LISTNODE *node) printf("list is empty! Can't delete. n"); node->singer = list->play->singer; node->title = list->play->title; // 리스트에노드가한개만있는경우 if(list->listsize == 1) list->play = NULL; list->first = NULL; // 커서가리스트의첫노드에있는경우 if(list->first == list->play) list->first = list->play->next; list->play->previous = NULL; // 커서가리스트의마지막노드에있는경우 if(list->play->next == NULL) list->play->previous->next = NULL; list->play = list->play->previous; // 그외의경우 list->play->previous->next = list->play->next; list->play->next->previous = list->play->previous; list->listsize--; // 앞곡으로변경 void moveprev(list *list)

16 printf("list is empty! Can't move. n"); // 리스트에노드가 1개밖에없거나커서가첫노드에있는경우 if(list->play == list->first list->listsize == 1) printf("the course is in the first item! Can't move. n"); // 커서를왼쪽으로이동 list->play = list->play->previous; // 뒷곡으로변경 void movenext(list *list) printf("list is empty! Can't move. n"); // 리스트에노드가 1개밖에없거나커서가마지막노드에있는경우 if(list->play->next == NULL list->listsize == 1) printf("the course is in the last item! Can't move. n"); // 커서를오른쪽으로이동

Lab 3. 실습문제 (Single linked list)_해답.hwp

Lab 3. 실습문제 (Single linked list)_해답.hwp Lab 3. Singly-linked list 의구현 실험실습일시 : 2009. 3. 30. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 5. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Singly-linked list의각함수를구현한다.