Lab 4. Circular singly-linked list 의구현 실험실습일시 : 2009. 4. 6. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 12. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Circular Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Circular Singly-linked list의각함수를구현한다. 실습순서 단계 1. 주어지는코드와제시된함수설계를참고해 Circular singly-linked list의각함수들을완성한다. ( 이 Circular singly-linked list는 head 포인터가리스트의첫번째노드를가리키고있는리스트이다.) 1) 리스트에 data를하나삽입하는 void insertlistitem(list *list, char data) 을구현한다. 매개변수로 LIST형의구조체포인터와 char 형의 data를받으며반환값은없다. 이함수는매개변수로전달받은리스트에서커서가가리키는곳의다음위치에 data를삽입하는함수이다. 새로만들어지는노드는동적메모리할당을하는함수인 malloc() 을이용해서만든다. 2) 리스트의처음위치에 data를하나삽입하는 void insertlistfirstitem(list *list, char data) 을구현한다. 매개변수로 LIST형의구조체포인터와 char 형의 data를받으며반환값은없다. 이함수는매개변수로전달받은리스트의처음위치에 data를삽입하는함수이다. 새로만들어지는노드는동적메모리할당을하는함수인 malloc() 을이용해서만든다. 3) 리스트에서 data를하나삭제하는 void deletelistitem(list *list, char *data) 을구현한다. 매개변수로 LIST형의구조체포인터와 char 형의포인터를받고반환값은없다. 이함수는매개변수로전달받은리스트의커서가가리키는곳에위치하는노드를삭제하는함수이다. 삭제된노드의 data는두번째매개변수인포인터형의 data에값을저장해외부로전달하고, 삭제된노드는더이상사용할필요가없으므로할당되어있는메모리를해제한다. 4) 리스트에서커서를이동시키는함수 void moveleft (LIST *list) 와 void moveright (LIST *list) 를선언한다. 이함수들은각각커서를왼쪽과오른쪽으로이동시키는함수이며, 매개변수로 LIST형의구조체포인터를받고반환값은없다. 두함수는커서를이동시킬수없는상황에서이동을시키려하면에러메시지를출력하며이동이불가능하게구현되어야한다. (ex) 리스트에노드가한개밖에없는경우등 )
#include <stdio.h> #include <conio.h> #include <stdlib.h> // 리스트의최대크기 #define MAX 10 // 리스트노드구조체 struct ListNode char data; // 저장 data struct ListNode *next; // 다음노드의포인터 ; typedef struct ListNode LISTNODE; // 리스트구조체 struct List int listsize; // 리스트의크기 LISTNODE *cursor; // 현재커서의위치 LISTNODE *head; // 첫번째노드의주소 ; typedef struct List LIST; void initlist(list *list); // 리스트초기화함수 void printlist(list *list); // 리스트출력함수 bool isempty(list *list); // 리스트가비어있는지확인하는함수 bool isfull(list *list); // 리스트가가득차있는지확인하는함수 void insertlistitem(list *list, char data); // 리스트에 data를입력하는함수 void insertlistfirstitem(list *list, char data); // 리스트의맨앞에 data를입력하는함수 void deletelistitem(list *list, char *data); // 리스트에서 data를삭제하는함수 void moveleft(list *list); // 리스트에서커서를왼쪽으로이동시키는함수 void moveright(list *list); // 리스트에서커서를오른쪽으로이동시키는함수 void main() LIST *list; char cmd; char data; printf("**************** Choose Command!! ****************** n"); printf("+: insert, -: delete, F: full check, E: empty check n"); printf("s: insert(first) L: move left R: move right Q: Quit n"); printf("**************************************************** n"); // 리스트에동적으로메모리할당 list = (LIST *)malloc(sizeof(list)); // 리스트초기화 initlist(list);
do // 커맨드입력 printf("command: "); cmd = getch(); // 커맨드는무조건대문자로입력 cmd = toupper(cmd); putch(cmd); switch (cmd) case '+' : // data 입력 printf("type the item that be inserted. :"); data = getch(); putch(data); insertlistitem(list,data); case 'S' : // data 입력 printf("type the item that be inserted. :"); data = getch(); putch(data); insertlistfirstitem(list,data); case '-' : // data 삭제 deletelistitem(list,&data); printf("deleted Item : %c n", data); 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 'L' : // 왼쪽으로커서이동 moveleft(list); case 'R' : // 오른쪽으로커서이동 moveright(list); case 'Q' : // 종료 default : // 잘못된커맨드입력시 printf(" nwrong command! Retry! n"); // 리스트출력 printlist(list); while ( cmd!='q' );
// 리스트초기화함수 void initlist(list *list) // 리스트구조체의멤버를각각초기화한다. // 리스트크기 = 0, 커서와첫번째노드 = NULL list->head = list->cursor = NULL; list->listsize = 0; // 리스트가비어있는지확인 bool isempty(list *list) if (list->listsize == 0) return true; return false; // 리스트가가득찼는지확인 bool isfull(list *list) if (list->listsize == MAX) return true; return false; // 리스트출력 void printlist(list *list) // 임시사용포인터선언 LISTNODE *tempcursor; // 리스트의첫노드를가리킴 if (isempty(list)) // 리스트가비어있는경우 printf("list is empty! n"); printf("item list. n"); do // 커서가있는곳은 [] 로표시 if (tempcursor == list->cursor) printf(" [%c] ",tempcursor->data); printf(" %c ",tempcursor->data); tempcursor = tempcursor->next; while(tempcursor!= list->head);
// 리스트에 data를입력하는함수 void insertlistitem(list *list, char data) if (isfull(list)) printf("list is full! Can't insert. n"); // 새로운노드선언 LISTNODE *tempnode; // 새로운노드에동적메모리할당후 data 저장 tempnode = (LISTNODE *)malloc(sizeof(listnode)); tempnode->data = data; if (isempty(list)) // 리스트가비어있는경우 list->head = tempnode; list->cursor = tempnode; tempnode->next = tempnode; // 그외의경우 ( 가운데 + 마지막위치에삽입 ) tempnode->next = list->cursor->next; list->cursor->next = tempnode; list->cursor = list->cursor->next; list->listsize++; // 리스트의처음위치에 data를삽입하는함수 void insertlistfirstitem(list *list, char data) if (isfull(list)) printf("list is full! Can't insert. n"); // 새로운노드선언 LISTNODE *tempnode, *tempcursor; // 새로운노드에동적메모리할당후 data 저장 tempnode = (LISTNODE *)malloc(sizeof(listnode)); tempnode->data = data; if (isempty(list)) // 리스트가비어있는경우 list->head = tempnode; list->cursor = tempnode; tempnode->next = tempnode;
// 그외의경우 // 리스트마지막노드까지 tempcusor를이동시킴 while(tempcursor->next!= list->head) tempcursor=tempcursor->next; tempnode->next = list->head; tempcursor->next = tempnode; list->head = tempnode; list->cursor = tempnode; list->listsize++; // 리스트에서 data를삭제하는함수 void deletelistitem(list *list, char *data) // 삭제된 data를저장할임시변수 char deleted = NULL; if (isempty(list)) printf("list is empty! Can't delete. n"); // 임시로사용할포인터선언 LISTNODE *tempcursor, *tempnode; // tempnode = 삭제될노드의위치 tempnode = list->cursor; deleted = list->cursor->data; // 리스트에노드가한개만있는경우 if (list->listsize == 1) list->cursor = NULL; list->head = NULL; // 커서가리스트의첫노드에있는경우 if (list->head == list->cursor) // 리스트마지막노드까지 tempcusor를이동시킴 while(tempcursor->next!= list->head) tempcursor=tempcursor->next; tempcursor->next = list->cursor->next; list->head = list->cursor->next; list->cursor = list->cursor->next;
// 그외의경우 ( 가운데 + 마지막노드삭제 ) // 현재커서가가리키는노드의직전노드까지 tempcusor를이동시킴 while(tempcursor->next!= list->cursor) tempcursor=tempcursor->next; tempcursor->next = list->cursor->next; list->cursor = tempcursor; list->listsize--; // 삭제할노드의메모리해제 free(tempnode); // 삭제된 data를외부에전달 *data = deleted; // 커서를오른쪽으로이동시키는함수 void moveright(list *list) if (isempty(list)) printf("list is empty! Can't move. n"); // 리스트에노드가 1개밖에없는경우 if (list->listsize == 1) printf("the cursor is in the last item! Can't move n"); list->cursor = list->cursor->next; // 커서를왼쪽으로이동시키는함수 void moveleft(list *list) if (isempty(list)) printf("list is empty! Can't move. n"); // 임시저장용포인터선언 LISTNODE *tempcursor;
// 리스트에노드가 1개밖에없는경우 if (list->listsize == 1) printf("the cursor is in the first item! Can't move n"); // 현재커서가가리키는노드직전까지 tempcursor를이동시킴 while(tempcursor->next!= list->cursor) tempcursor=tempcursor->next; list->cursor = tempcursor; 단계 2. 단계 1에서완성된프로그램을실행시켜각함수들을테스트해보고그결과화면을캡쳐하시오. 단계 3. 단계 1에서완성된프로그램을수정해서 head 포인터가리스트의마지막노드를가리키고있는형태의 Circular singly-linked list를구현하시오. 단계 1에서의프로그램과모든기능이동일하게동작하여야한다. ( 단, printlist() 함수는다음코드를참고해수정하시오.) // 리스트출력 void printlist(list *list) // 임시사용포인터선언 LISTNODE *tempcursor; if (isempty(list)) // 리스트가비어있는경우 printf("list is empty! n"); // 리스트의첫노드를가리킴 tempcursor = list->head->next; printf("item list. n");
do // 커서가있는곳은 [] 로표시 if (tempcursor == list->cursor) printf(" [%c] ",tempcursor->data); printf(" %c ",tempcursor->data); tempcursor = tempcursor->next; while(tempcursor!= list->head->next); 단계 4. 단계 1과단계 3에서완성된두가지종류의 Circular singly-linked List에대해삽입, 삭제의용이성을프로그래머의관점에서비교하시오. 과제수행결과 ( 결과화면및소감 )