Lab 3. Singly-linked list 의구현 실험실습일시 : 2009. 3. 30. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 5. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Singly-linked list의각함수를구현한다. 실습순서 단계 1. 주어지는코드와제시된함수설계를참고해각함수들을완성한다. 1) 리스트를초기화하는함수 void initlist(list *list) 를구현한다. 이함수는매개변수로 LIST 형의구조체포인터를받고반환값은없다. 매개변수 list의멤버인 listsize, cursor, first를각각 0과 NULL로초기화시킨다. 2) 리스트를출력하는함수 void pintlist(list *list) 를구현한다. 매개변수로출력할 LIST 형의구조체포인터를받고반환값은없다. 매개변수 list의첫번째노드부터시작해서모든노드의 data를출력한다. 단, 커서가위치한곳의 data는 [ ] 사이에출력해야한다. (ex) a b c d [e] f g h ) 3) 리스트의상태를알아보는 bool isempty(list *list) 와 bool isfull(list *list) 를구현한다. 이두함수는각각리스트가비어있는지가득차있는지를검사하는함수로 LIST형의구조체포인터를매개변수로받고반환값은 bool형의 true/false 이다. 4) 리스트에 data를하나삽입하는 void insertlistitem(list *list, char data) 을구현한다. 매개변수로 LIST형의구조체포인터와 char 형의 data를받으며반환값은없다. 이함수는매개변수로전달받은리스트에서커서가가리키는곳의다음위치에 data를삽입하는함수이다. 새로만들어지는노드는동적메모리할당을하는함수인 malloc() 을이용해서만든다. 5) 리스트에서 data를하나삭제하는 void deletelistitem(list *list, char *data) 을구현한다. 매개변수로 LIST형의구조체포인터와 char 형의포인터를받고반환값은없다. 이함수는매개변수로전달받은리스트의커서가가리키는곳에위치하는노드를삭제하는함수이다. 삭제된노드의 data는두번째매개변수인포인터형의 data에값을저장해외부로전달하고, 삭제된노드는더이상사용할필요가없으므로할당되어있는메모리를해제한다.
6) 리스트에서커서를이동시키는함수 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 *first; // 첫번째노드의주소 ; 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 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("l: move left R: move right Q: Quit n"); printf("**************************************************** n");
// 리스트에동적으로메모리할당 list = (LIST *)malloc(sizeof(list)); // 리스트초기화 initlist(list); do // 커맨드입력 printf("command: "); cmd = getch(); putch(cmd); printf(" n"); // 커맨드는무조건대문자로입력 cmd = toupper(cmd); switch (cmd) case '+' : // data 입력 printf("type the item that be inserted. :"); data = getch(); putch(data); printf(" n"); insertlistitem(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->first = 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; // 리스트의첫노드를가리킴 tempcursor = list->first; if (isempty(list)) // 리스트가비어있는경우 printf("list is empty! n"); printf("item list. n"); while(tempcursor!= NULL) // 커서가있는곳은 [] 로표시 if (tempcursor == list->cursor) printf(" [%c] ",tempcursor->data); printf(" %c ",tempcursor->data); tempcursor = tempcursor->next; printf(" n");
// 리스트에 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->first = tempnode; list->cursor = tempnode; tempnode->next = NULL; // 리스트에노드가존재하는경우 tempnode->next = list->cursor->next; list->cursor->next = tempnode; list->cursor = list->cursor->next; 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->first = NULL; // 커서가리스트의첫노드에있는경우 if (list->first == list->cursor) list->first = list->cursor->next; list->cursor = list->cursor->next; // 그외의경우 tempcursor = list->first; // 현재커서가가리키는노드의직전노드까지 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->cursor->next == NULL 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->cursor == list->first list->listsize == 1) printf("the cursor is in the first item! Can't move n"); tempcursor = list->first; // 현재커서가가리키는노드직전까지 tempcursor를이동시킴 while(tempcursor->next!= list->cursor) tempcursor=tempcursor->next; // 커서를왼쪽으로이동 list->cursor = tempcursor; 단계 2. 단계 1에서완성된프로그램을실행시켜각함수들을테스트해보고그결과화면을캡쳐하시오. 과제수행결과 ( 결과화면및소감 )